comparison: src/triangulate.cpp
src/triangulate.cpp
- changeset 319
- 9727e545b0bc
- child 320
- af6633412a6c
equal
deleted
inserted
replaced
| 318:216f02b50b0a | 319:9727e545b0bc |
|---|---|
| 1 #include "src/triangulate.h" | |
| 2 #include "thirdparty/earcut.h" | |
| 3 #include "src/invert.h" | |
| 4 | |
| 5 // Make mapbox::earcut work with glm::vec3 | |
| 6 template<> struct mapbox::util::nth<0, glm::vec3> | |
| 7 { | |
| 8 static constexpr float get(const glm::vec3& t) { return t.x; } | |
| 9 }; | |
| 10 | |
| 11 template<> struct mapbox::util::nth<1, glm::vec3> | |
| 12 { | |
| 13 static constexpr float get(const glm::vec3& t) { return t.y; } | |
| 14 }; | |
| 15 | |
| 16 using indextype = std::uint16_t; | |
| 17 using indexpair = std::pair<indextype, indextype>; | |
| 18 struct boundaryinfo | |
| 19 { | |
| 20 indextype third; | |
| 21 std::size_t triangleid; | |
| 22 }; | |
| 23 using boundarymap_t = std::map<indexpair, boundaryinfo>; | |
| 24 | |
| 25 struct MergedTriangles | |
| 26 { | |
| 27 std::vector<Quadrilateral> quadrilaterals; | |
| 28 std::set<std::size_t> cutTriangles; | |
| 29 }; | |
| 30 | |
| 31 static bool findQuadsToMerge( | |
| 32 const boundarymap_t& boundaries, | |
| 33 auto&& iscut, | |
| 34 auto&& addMergedQuad | |
| 35 ) { | |
| 36 bool foundQuads = false; | |
| 37 // Go through triangle boundaries | |
| 38 for (boundarymap_t::const_iterator it1 = boundaries.begin(); it1 != boundaries.end(); ++it1) { | |
| 39 const indexpair& pair1 = it1->first; | |
| 40 const boundaryinfo& boundary1 = it1->second; | |
| 41 // .. the ones we haven't already been merged... | |
| 42 if (not iscut(boundary1.triangleid)) { | |
| 43 // Look for its inverse boundary to find the touching triangle | |
| 44 const indexpair inverse_boundary_key = std::make_pair(pair1.second, pair1.first); | |
| 45 const boundarymap_t::const_iterator it2 = boundaries.find(inverse_boundary_key); | |
| 46 // Also if that hasn't been cut | |
| 47 if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) { | |
| 48 // Continue until no more new quads are found | |
| 49 foundQuads |= addMergedQuad(it1, it2); | |
| 50 } | |
| 51 } | |
| 52 } | |
| 53 return foundQuads; | |
| 54 } | |
| 55 | |
| 56 static MergedTriangles mergeTriangles( | |
| 57 const std::vector<std::uint16_t>& indices, | |
| 58 std::vector<glm::vec3>::const_iterator polyBegin) | |
| 59 { | |
| 60 MergedTriangles result; | |
| 61 const auto iscut = [&result](const std::size_t i){ | |
| 62 return result.cutTriangles.find(i) != result.cutTriangles.end(); | |
| 63 }; | |
| 64 const auto addMergedQuad = [&result, polyBegin]( | |
| 65 boundarymap_t::const_iterator it1, | |
| 66 boundarymap_t::const_iterator it2 | |
| 67 ) { | |
| 68 const indexpair& common_indices = it1->first; | |
| 69 const boundaryinfo& boundary_1 = it1->second; | |
| 70 const boundaryinfo& boundary_2 = it2->second; | |
| 71 const Quadrilateral quad{ | |
| 72 *(polyBegin + common_indices.first), | |
| 73 *(polyBegin + boundary_2.third), | |
| 74 *(polyBegin + common_indices.second), | |
| 75 *(polyBegin + boundary_1.third), | |
| 76 }; | |
| 77 if (isConvex(quad)) { | |
| 78 result.quadrilaterals.push_back(quad); | |
| 79 result.cutTriangles.insert(boundary_1.triangleid); | |
| 80 result.cutTriangles.insert(boundary_2.triangleid); | |
| 81 return true; | |
| 82 } | |
| 83 else { | |
| 84 return false; | |
| 85 } | |
| 86 }; | |
| 87 boundarymap_t boundaries; | |
| 88 for (std::size_t i = 0; i < indices.size(); i += 3) { | |
| 89 const auto add = [&](const std::size_t o1, const std::size_t o2, const std::size_t o3){ | |
| 90 const auto key = std::make_pair(indices[i + o1], indices[i + o2]); | |
| 91 boundaries[key] = {indices[i + o3], i}; | |
| 92 }; | |
| 93 add(0, 1, 2); | |
| 94 add(1, 2, 0); | |
| 95 add(2, 0, 1); | |
| 96 } | |
| 97 bool repeat = true; | |
| 98 while (repeat) { | |
| 99 repeat = findQuadsToMerge(boundaries, iscut, addMergedQuad); | |
| 100 } | |
| 101 return result; | |
| 102 } | |
| 103 | |
| 104 std::vector<PlainPolygonElement> polygonize( | |
| 105 std::vector<glm::vec3>::const_iterator begin, | |
| 106 std::vector<glm::vec3>::const_iterator end, | |
| 107 const glm::mat4& planeMatrix) | |
| 108 { | |
| 109 std::vector<PlainPolygonElement> result; | |
| 110 const glm::mat4 inverseGrid = glm::inverse(planeMatrix); | |
| 111 // mapbox::earcut will always produce a CCW polygon, so if we're drawing | |
| 112 // a CW polygon, we should invert the result afterwards | |
| 113 const float shouldInvert = glm::dot( | |
| 114 glm::vec3{inverseGrid[2]}, | |
| 115 glm::cross(*begin - *(begin + 1), *(begin + 2) - *(begin + 1))); | |
| 116 std::vector<std::vector<glm::vec3>> polygons{1}; | |
| 117 std::vector<glm::vec3>& polygon2d = polygons.back(); | |
| 118 polygon2d.reserve(static_cast<std::size_t>(end - begin)); | |
| 119 for (std::vector<glm::vec3>::const_iterator it = begin; it != end; ++it) { | |
| 120 polygon2d.push_back(inverseGrid * glm::vec4{*it, 1}); | |
| 121 } | |
| 122 const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons); | |
| 123 MergedTriangles mergedTriangles = mergeTriangles(indices, begin); | |
| 124 for (Quadrilateral& quad : mergedTriangles.quadrilaterals) { | |
| 125 if (shouldInvert < 0) { | |
| 126 invert(quad); | |
| 127 } | |
| 128 result.push_back(quad); | |
| 129 } | |
| 130 for (std::size_t i = 0; i < indices.size(); i += 3) { | |
| 131 if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) { | |
| 132 Triangle tri = triangle( | |
| 133 *(begin + indices[i]), | |
| 134 *(begin + indices[i + 1]), | |
| 135 *(begin + indices[i + 2])); | |
| 136 if (shouldInvert < 0) { | |
| 137 invert(tri); | |
| 138 } | |
| 139 result.push_back(tri); | |
| 140 } | |
| 141 } | |
| 142 return result; | |
| 143 } |
