src/triangulate.cpp

Wed, 20 Jul 2022 21:48:46 +0300

author
Teemu Piippo <teemu.s.piippo@gmail.com>
date
Wed, 20 Jul 2022 21:48:46 +0300
changeset 338
719b909a7d2b
parent 321
180072db4a83
child 369
57de8fab2237
permissions
-rw-r--r--

Delete unused code
Remove Model legacy type alias, QTextDocument is used now instead

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

mercurial