-
-
Notifications
You must be signed in to change notification settings - Fork 1.2k
/
PolySetUtils.cc
181 lines (170 loc) · 5.99 KB
/
PolySetUtils.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include "PolySetUtils.h"
#include "PolySet.h"
#include "PolySetBuilder.h"
#include "Polygon2d.h"
#include "printutils.h"
#include "GeometryUtils.h"
#ifdef ENABLE_CGAL
#include "cgalutils.h"
#include "CGALHybridPolyhedron.h"
#endif
#ifdef ENABLE_MANIFOLD
#include "ManifoldGeometry.h"
#endif
namespace PolySetUtils {
// Project all polygons (also back-facing) into a Polygon2d instance.
// It is important to select all faces, since filtering by normal vector here
// will trigger floating point incertainties and cause problems later.
std::unique_ptr<Polygon2d> project(const PolySet& ps) {
auto poly = std::make_unique<Polygon2d>();
Vector3d pt;
for (const auto& p : ps.indices) {
Outline2d outline;
for (const auto& v : p) {
pt=ps.vertices[v];
outline.vertices.emplace_back(pt[0], pt[1]);
}
poly->addOutline(outline);
}
return poly;
}
/* Tessellation of 3d PolySet faces
This code is for tessellating the faces of a 3d PolySet, assuming that
the faces are near-planar polygons.
The purpose of this code is originally to fix github issue 349. Our CGAL
kernel does not accept polygons for Nef_Polyhedron_3 if each of the
points is not exactly coplanar. "Near-planar" or "Almost planar" polygons
often occur due to rounding issues on, for example, polyhedron() input.
By tessellating the 3d polygon into individual smaller tiles that
are perfectly coplanar (triangles, for example), we can get CGAL to accept
the polyhedron() input.
*/
/* Given a 3D PolySet with near planar polygonal faces, tessellate the
faces. As of writing, our only tessellation method is triangulation
using CGAL's Constrained Delaunay algorithm. This code assumes the input
polyset has simple polygon faces with no holes.
The tessellation will be robust wrt. degenerate and self-intersecting
*/
std::unique_ptr<PolySet> tessellate_faces(const PolySet& polyset)
{
int degeneratePolygons = 0;
auto result = std::make_unique<PolySet>(3, polyset.convexValue());
result->setConvexity(polyset.getConvexity());
result->setTriangular(true);
// ideally this should not require a copy...
if (polyset.isTriangular()) {
result->vertices = polyset.vertices;
result->indices = polyset.indices;
return result;
}
result->vertices.reserve(polyset.vertices.size());
result->indices.reserve(polyset.indices.size());
std::vector<bool> used(polyset.vertices.size(), false);
// best estimate without iterating all polygons, to reduce reallocations
std::vector<IndexedFace> polygons;
polygons.reserve(polyset.indices.size());
for (const auto& pgon : polyset.indices) {
if (pgon.size() < 3) {
degeneratePolygons++;
continue;
}
auto& currface = polygons.emplace_back();
for (const auto& ind : pgon) {
const Vector3f v = polyset.vertices[ind].cast<float>();
if (currface.empty() || v != polyset.vertices[currface.back()].cast<float>())
currface.push_back(ind);
}
const Vector3f head = polyset.vertices[currface.front()].cast<float>();
while (!currface.empty() && head == polyset.vertices[currface.back()].cast<float>())
currface.pop_back();
if (currface.size() < 3) {
polygons.pop_back();
continue;
}
for (const auto& ind : currface)
used[ind] = true;
}
// remove unreferenced vertices
std::vector<Vector3f> verts;
std::vector<int> indexMap(polyset.vertices.size());
verts.reserve(polyset.vertices.size());
for (size_t i = 0; i < polyset.vertices.size(); ++i) {
if (used[i]) {
indexMap[i] = verts.size();
verts.emplace_back(polyset.vertices[i].cast<float>());
result->vertices.push_back(polyset.vertices[i]);
}
}
if (verts.size() != polyset.vertices.size()) {
// only remap indices when some vertices are really removed
for (auto& face : polygons) {
for (auto& ind : face)
ind = indexMap[ind];
}
}
// we will reuse this memory instead of reallocating for each polygon
std::vector<IndexedTriangle> triangles;
std::vector<IndexedFace> facesBuffer(1);
for (const auto& face : polygons) {
if (face.size() == 3) {
// trivial case - triangles cannot be concave or have holes
result->indices.push_back({face[0],face[1],face[2]});
}
// Quads seem trivial, but can be concave, and can have degenerate cases.
// So everything more complex than triangles goes into the general case.
else {
triangles.clear();
facesBuffer[0] = face;
auto err = GeometryUtils::tessellatePolygonWithHoles(verts, facesBuffer, triangles, nullptr);
if (!err) {
for (const auto& t : triangles) {
result->indices.push_back({t[0],t[1],t[2]});
}
}
}
}
if (degeneratePolygons > 0) {
LOG(message_group::Warning, "PolySet has degenerate polygons");
}
return result;
}
bool is_approximately_convex(const PolySet& ps) {
#ifdef ENABLE_CGAL
return CGALUtils::is_approximately_convex(ps);
#else
return false;
#endif
}
// Get as or convert the geometry to a PolySet.
std::shared_ptr<const PolySet> getGeometryAsPolySet(const std::shared_ptr<const Geometry>& geom)
{
if (const auto geomlist = std::dynamic_pointer_cast<const GeometryList>(geom)) {
PolySetBuilder builder;
builder.appendGeometry(geom);
return builder.build();
} else if (auto ps = std::dynamic_pointer_cast<const PolySet>(geom)) {
return ps;
}
#ifdef ENABLE_CGAL
if (auto N = std::dynamic_pointer_cast<const CGAL_Nef_polyhedron>(geom)) {
if (!N->isEmpty()) {
if (auto ps = CGALUtils::createPolySetFromNefPolyhedron3(*N->p3)) {
ps->setConvexity(N->getConvexity());
return ps;
}
LOG(message_group::Error, "Nef->PolySet failed.");
}
return PolySet::createEmpty();
}
if (auto hybrid = std::dynamic_pointer_cast<const CGALHybridPolyhedron>(geom)) {
return hybrid->toPolySet();
}
#endif
#ifdef ENABLE_MANIFOLD
if (auto mani = std::dynamic_pointer_cast<const ManifoldGeometry>(geom)) {
return mani->toPolySet();
}
#endif
return nullptr;
}
} // namespace PolySetUtils