comparison: src/triangulate.cpp
src/triangulate.cpp
- changeset 320
- af6633412a6c
- parent 319
- 9727e545b0bc
- child 321
- 180072db4a83
equal
deleted
inserted
replaced
| 319:9727e545b0bc | 320:af6633412a6c |
|---|---|
| 11 template<> struct mapbox::util::nth<1, glm::vec3> | 11 template<> struct mapbox::util::nth<1, glm::vec3> |
| 12 { | 12 { |
| 13 static constexpr float get(const glm::vec3& t) { return t.y; } | 13 static constexpr float get(const glm::vec3& t) { return t.y; } |
| 14 }; | 14 }; |
| 15 | 15 |
| 16 using indextype = std::uint16_t; | 16 namespace triangulate |
| 17 using indexpair = std::pair<indextype, indextype>; | |
| 18 struct boundaryinfo | |
| 19 { | 17 { |
| 20 indextype third; | 18 struct triangleid |
| 21 std::size_t triangleid; | 19 { |
| 22 }; | 20 std::size_t id; |
| 23 using boundarymap_t = std::map<indexpair, boundaryinfo>; | 21 constexpr auto operator<=>(const triangleid&) const = default; |
| 24 | 22 }; |
| 25 struct MergedTriangles | 23 //! \brief Index type of vertex |
| 26 { | 24 using index_t = std::uint16_t; |
| 27 std::vector<Quadrilateral> quadrilaterals; | 25 //! \brief Pair of vertex indices, forming a triangle boundary |
| 28 std::set<std::size_t> cutTriangles; | 26 using boundary_t = std::pair<index_t, index_t>; |
| 29 }; | 27 //! \brief Additional information about a triangle boundary |
| 28 struct triangleinfo | |
| 29 { | |
| 30 //! \brief What's the third vertex of this triangle | |
| 31 index_t third_vertex; | |
| 32 //! \brief Id of triangle (starting position of the triangle in the result | |
| 33 //! value of mapbox::earcut) | |
| 34 triangleid triangleid; | |
| 35 }; | |
| 36 using triangleinfomap_t = std::map<boundary_t, triangleinfo>; | |
| 37 struct MergedTriangles | |
| 38 { | |
| 39 //! \brief List of merged quadrilaterals | |
| 40 std::vector<Quadrilateral> quadrilaterals; | |
| 41 //! \brief Ids of cut triangles | |
| 42 std::set<triangleid> cutTriangles; | |
| 43 }; | |
| 44 static MergedTriangles mergeTriangles( | |
| 45 const std::vector<std::uint16_t>& indices, | |
| 46 std::vector<glm::vec3>::const_iterator polyBegin); | |
| 47 } | |
| 30 | 48 |
| 31 static bool findQuadsToMerge( | 49 static bool findQuadsToMerge( |
| 32 const boundarymap_t& boundaries, | 50 const triangulate::triangleinfomap_t& boundaries, |
| 33 auto&& iscut, | 51 auto&& iscut, |
| 34 auto&& addMergedQuad | 52 auto&& addMergedQuad |
| 35 ) { | 53 ) { |
| 36 bool foundQuads = false; | 54 bool foundQuads = false; |
| 37 // Go through triangle boundaries | 55 // Go through triangle boundaries |
| 38 for (boundarymap_t::const_iterator it1 = boundaries.begin(); it1 != boundaries.end(); ++it1) { | 56 for ( |
| 39 const indexpair& pair1 = it1->first; | 57 triangulate::triangleinfomap_t::const_iterator it1 = boundaries.begin(); |
| 40 const boundaryinfo& boundary1 = it1->second; | 58 it1 != boundaries.end(); |
| 59 ++it1 | |
| 60 ) { | |
| 61 const triangulate::boundary_t& boundary = it1->first; | |
| 62 const triangulate::triangleinfo& earcut_triangle_1 = it1->second; | |
| 41 // .. the ones we haven't already been merged... | 63 // .. the ones we haven't already been merged... |
| 42 if (not iscut(boundary1.triangleid)) { | 64 if (not iscut(earcut_triangle_1.triangleid)) { |
| 43 // Look for its inverse boundary to find the touching triangle | 65 // Look for its inverse boundary to find the touching triangle |
| 44 const indexpair inverse_boundary_key = std::make_pair(pair1.second, pair1.first); | 66 const triangulate::boundary_t inverse_boundary = std::make_pair(boundary.second, boundary.first); |
| 45 const boundarymap_t::const_iterator it2 = boundaries.find(inverse_boundary_key); | 67 const triangulate::triangleinfomap_t::const_iterator it2 = boundaries.find(inverse_boundary); |
| 46 // Also if that hasn't been cut | 68 // Also if that hasn't been cut |
| 47 if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) { | 69 if (it2 != boundaries.end() and not iscut(it2->second.triangleid)) { |
| 48 // Continue until no more new quads are found | 70 // Continue until no more new quads are found |
| 49 foundQuads |= addMergedQuad(it1, it2); | 71 foundQuads |= addMergedQuad(it1, it2); |
| 50 } | 72 } |
| 51 } | 73 } |
| 52 } | 74 } |
| 53 return foundQuads; | 75 return foundQuads; |
| 54 } | 76 } |
| 55 | 77 |
| 56 static MergedTriangles mergeTriangles( | 78 static triangulate::MergedTriangles triangulate::mergeTriangles( |
| 57 const std::vector<std::uint16_t>& indices, | 79 const std::vector<std::uint16_t>& indices, |
| 58 std::vector<glm::vec3>::const_iterator polyBegin) | 80 std::vector<glm::vec3>::const_iterator polyBegin) |
| 59 { | 81 { |
| 60 MergedTriangles result; | 82 MergedTriangles result; |
| 61 const auto iscut = [&result](const std::size_t i){ | 83 const auto iscut = [&result](const triangleid i){ |
| 62 return result.cutTriangles.find(i) != result.cutTriangles.end(); | 84 return result.cutTriangles.find(i) != result.cutTriangles.end(); |
| 63 }; | 85 }; |
| 64 const auto addMergedQuad = [&result, polyBegin]( | 86 const auto addMergedQuad = [&result, polyBegin]( |
| 65 boundarymap_t::const_iterator it1, | 87 triangleinfomap_t::const_iterator it1, |
| 66 boundarymap_t::const_iterator it2 | 88 triangleinfomap_t::const_iterator it2 |
| 67 ) { | 89 ) { |
| 68 const indexpair& common_indices = it1->first; | 90 const boundary_t& shared_boundary = it1->first; |
| 69 const boundaryinfo& boundary_1 = it1->second; | 91 const triangleinfo& earcut_triangle_1 = it1->second; |
| 70 const boundaryinfo& boundary_2 = it2->second; | 92 const triangleinfo& earcut_triangle_2 = it2->second; |
| 71 const Quadrilateral quad{ | 93 const Quadrilateral quad{ |
| 72 *(polyBegin + common_indices.first), | 94 *(polyBegin + shared_boundary.first), |
| 73 *(polyBegin + boundary_2.third), | 95 *(polyBegin + earcut_triangle_2.third_vertex), |
| 74 *(polyBegin + common_indices.second), | 96 *(polyBegin + shared_boundary.second), |
| 75 *(polyBegin + boundary_1.third), | 97 *(polyBegin + earcut_triangle_1.third_vertex), |
| 76 }; | 98 }; |
| 77 if (isConvex(quad)) { | 99 if (isConvex(quad)) { |
| 78 result.quadrilaterals.push_back(quad); | 100 result.quadrilaterals.push_back(quad); |
| 79 result.cutTriangles.insert(boundary_1.triangleid); | 101 result.cutTriangles.insert(earcut_triangle_1.triangleid); |
| 80 result.cutTriangles.insert(boundary_2.triangleid); | 102 result.cutTriangles.insert(earcut_triangle_2.triangleid); |
| 81 return true; | 103 return true; |
| 82 } | 104 } |
| 83 else { | 105 else { |
| 84 return false; | 106 return false; |
| 85 } | 107 } |
| 86 }; | 108 }; |
| 87 boundarymap_t boundaries; | 109 triangleinfomap_t boundaries; |
| 88 for (std::size_t i = 0; i < indices.size(); i += 3) { | 110 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){ | 111 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]); | 112 const auto key = std::make_pair(indices[i + o1], indices[i + o2]); |
| 91 boundaries[key] = {indices[i + o3], i}; | 113 boundaries[key] = triangleinfo{ |
| 114 .third_vertex = indices[i + o3], | |
| 115 .triangleid = {i}, | |
| 116 }; | |
| 92 }; | 117 }; |
| 93 add(0, 1, 2); | 118 add(0, 1, 2); |
| 94 add(1, 2, 0); | 119 add(1, 2, 0); |
| 95 add(2, 0, 1); | 120 add(2, 0, 1); |
| 96 } | 121 } |
| 99 repeat = findQuadsToMerge(boundaries, iscut, addMergedQuad); | 124 repeat = findQuadsToMerge(boundaries, iscut, addMergedQuad); |
| 100 } | 125 } |
| 101 return result; | 126 return result; |
| 102 } | 127 } |
| 103 | 128 |
| 129 //! \brief Polygonize a polygon into triangles and try merge as many of them | |
| 130 //! as possible into quadrilaterals. The polygons must all reside in the same | |
| 131 //! plane. | |
| 104 std::vector<PlainPolygonElement> polygonize( | 132 std::vector<PlainPolygonElement> polygonize( |
| 105 std::vector<glm::vec3>::const_iterator begin, | 133 std::vector<glm::vec3>::const_iterator begin, |
| 106 std::vector<glm::vec3>::const_iterator end, | 134 std::vector<glm::vec3>::const_iterator end) |
| 107 const glm::mat4& planeMatrix) | |
| 108 { | 135 { |
| 109 std::vector<PlainPolygonElement> result; | 136 std::vector<PlainPolygonElement> result; |
| 110 const glm::mat4 inverseGrid = glm::inverse(planeMatrix); | 137 const glm::vec3 xvec = *begin - *(begin + 1); |
| 111 // mapbox::earcut will always produce a CCW polygon, so if we're drawing | 138 const glm::vec3 yvec = *(begin + 2) - *(begin + 1); |
| 112 // a CW polygon, we should invert the result afterwards | 139 const glm::vec3 zvec = glm::cross(xvec, yvec); |
| 113 const float shouldInvert = glm::dot( | 140 const glm::mat3 inverseMatrix = glm::inverse(glm::mat3{xvec, yvec, zvec}); |
| 114 glm::vec3{inverseGrid[2]}, | |
| 115 glm::cross(*begin - *(begin + 1), *(begin + 2) - *(begin + 1))); | |
| 116 std::vector<std::vector<glm::vec3>> polygons{1}; | 141 std::vector<std::vector<glm::vec3>> polygons{1}; |
| 117 std::vector<glm::vec3>& polygon2d = polygons.back(); | 142 std::vector<glm::vec3>& polygon2d = polygons.back(); |
| 118 polygon2d.reserve(static_cast<std::size_t>(end - begin)); | 143 polygon2d.reserve(static_cast<std::size_t>(end - begin)); |
| 119 for (std::vector<glm::vec3>::const_iterator it = begin; it != end; ++it) { | 144 for (std::vector<glm::vec3>::const_iterator it = begin; it != end; ++it) { |
| 120 polygon2d.push_back(inverseGrid * glm::vec4{*it, 1}); | 145 polygon2d.push_back(inverseMatrix * glm::vec4{*it, 1}); |
| 121 } | 146 } |
| 122 const std::vector<indextype> indices = mapbox::earcut<std::uint16_t>(polygons); | 147 const std::vector<triangulate::index_t> indices = mapbox::earcut<triangulate::index_t>(polygons); |
| 123 MergedTriangles mergedTriangles = mergeTriangles(indices, begin); | 148 triangulate::MergedTriangles mergedTriangles = triangulate::mergeTriangles(indices, begin); |
| 124 for (Quadrilateral& quad : mergedTriangles.quadrilaterals) { | 149 for (Quadrilateral& quad : mergedTriangles.quadrilaterals) { |
| 125 if (shouldInvert < 0) { | |
| 126 invert(quad); | |
| 127 } | |
| 128 result.push_back(quad); | 150 result.push_back(quad); |
| 129 } | 151 } |
| 130 for (std::size_t i = 0; i < indices.size(); i += 3) { | 152 for (std::size_t i = 0; i < indices.size(); i += 3) { |
| 131 if (mergedTriangles.cutTriangles.find(i) == mergedTriangles.cutTriangles.end()) { | 153 if (not mergedTriangles.cutTriangles.contains({i})) { |
| 132 Triangle tri = triangle( | 154 Triangle tri = triangle( |
| 133 *(begin + indices[i]), | 155 *(begin + indices[i]), |
| 134 *(begin + indices[i + 1]), | 156 *(begin + indices[i + 1]), |
| 135 *(begin + indices[i + 2])); | 157 *(begin + indices[i + 2])); |
| 136 if (shouldInvert < 0) { | |
| 137 invert(tri); | |
| 138 } | |
| 139 result.push_back(tri); | 158 result.push_back(tri); |
| 140 } | 159 } |
| 141 } | 160 } |
| 142 return result; | 161 return result; |
| 143 } | 162 } |
