1 #include "Tesselate.hpp"
2
3 #include "ExPolygon.hpp"
4
5 #include <glu-libtess.h>
6
7 namespace Slic3r {
8
9 class GluTessWrapper {
10 public:
GluTessWrapper()11 GluTessWrapper() : m_tesselator(gluNewTess()) {
12 // register callback functions
13 gluTessCallback(m_tesselator, GLU_TESS_BEGIN_DATA, (_GLUfuncptr)tessBeginCB);
14 gluTessCallback(m_tesselator, GLU_TESS_END_DATA, (_GLUfuncptr)tessEndCB);
15 gluTessCallback(m_tesselator, GLU_TESS_ERROR_DATA, (_GLUfuncptr)tessErrorCB);
16 gluTessCallback(m_tesselator, GLU_TESS_VERTEX_DATA, (_GLUfuncptr)tessVertexCB);
17 gluTessCallback(m_tesselator, GLU_TESS_COMBINE_DATA, (_GLUfuncptr)tessCombineCB);
18 }
~GluTessWrapper()19 ~GluTessWrapper() {
20 gluDeleteTess(m_tesselator);
21 }
22
tesselate3d(const ExPolygon & expoly,double z_,bool flipped_)23 std::vector<Vec3d> tesselate3d(const ExPolygon &expoly, double z_, bool flipped_)
24 {
25 m_z = z_;
26 m_flipped = flipped_;
27 m_output_triangles.clear();
28 std::vector<GLdouble> coords;
29 {
30 size_t num_coords = expoly.contour.points.size();
31 for (const Polygon &poly : expoly.holes)
32 num_coords += poly.points.size();
33 coords.reserve(num_coords * 3);
34 }
35 gluTessBeginPolygon(m_tesselator, (void*)this);
36 gluTessBeginContour(m_tesselator);
37 for (const Point &pt : expoly.contour.points) {
38 coords.emplace_back(unscale<double>(pt[0]));
39 coords.emplace_back(unscale<double>(pt[1]));
40 coords.emplace_back(0.);
41 gluTessVertex(m_tesselator, &coords[coords.size() - 3], &coords[coords.size() - 3]);
42 }
43 gluTessEndContour(m_tesselator);
44 for (const Polygon &poly : expoly.holes) {
45 gluTessBeginContour(m_tesselator);
46 for (const Point &pt : poly.points) {
47 coords.emplace_back(unscale<double>(pt[0]));
48 coords.emplace_back(unscale<double>(pt[1]));
49 coords.emplace_back(0.);
50 gluTessVertex(m_tesselator, &coords[coords.size() - 3], &coords[coords.size() - 3]);
51 }
52 gluTessEndContour(m_tesselator);
53 }
54 gluTessEndPolygon(m_tesselator);
55 m_intersection_points.clear();
56 return std::move(m_output_triangles);
57 }
58
tesselate3d(const ExPolygons & expolygons,double z_,bool flipped_)59 std::vector<Vec3d> tesselate3d(const ExPolygons &expolygons, double z_, bool flipped_)
60 {
61 m_z = z_;
62 m_flipped = flipped_;
63 m_output_triangles.clear();
64 std::vector<GLdouble> coords;
65 {
66 size_t num_coords = 0;
67 for (const ExPolygon &expoly : expolygons) {
68 size_t num_coords_this = expoly.contour.points.size();
69 for (const Polygon &poly : expoly.holes)
70 num_coords_this += poly.points.size();
71 num_coords = std::max(num_coords, num_coords_this);
72 }
73 coords.assign(num_coords * 3, 0);
74 }
75 for (const ExPolygon &expoly : expolygons) {
76 gluTessBeginPolygon(m_tesselator, (void*)this);
77 gluTessBeginContour(m_tesselator);
78 size_t idx = 0;
79 for (const Point &pt : expoly.contour.points) {
80 coords[idx ++] = unscale<double>(pt[0]);
81 coords[idx ++] = unscale<double>(pt[1]);
82 coords[idx ++] = 0.;
83 gluTessVertex(m_tesselator, &coords[idx - 3], &coords[idx - 3]);
84 }
85 gluTessEndContour(m_tesselator);
86 for (const Polygon &poly : expoly.holes) {
87 gluTessBeginContour(m_tesselator);
88 for (const Point &pt : poly.points) {
89 coords[idx ++] = unscale<double>(pt[0]);
90 coords[idx ++] = unscale<double>(pt[1]);
91 coords[idx ++] = 0.;
92 gluTessVertex(m_tesselator, &coords[idx - 3], &coords[idx - 3]);
93 }
94 gluTessEndContour(m_tesselator);
95 }
96 gluTessEndPolygon(m_tesselator);
97 }
98 m_intersection_points.clear();
99 return std::move(m_output_triangles);
100 }
101
102 private:
tessBeginCB(GLenum which,void * polygonData)103 static void tessBeginCB(GLenum which, void *polygonData) { reinterpret_cast<GluTessWrapper*>(polygonData)->tessBegin(which); }
tessEndCB(void * polygonData)104 static void tessEndCB(void *polygonData) { reinterpret_cast<GluTessWrapper*>(polygonData)->tessEnd(); }
tessVertexCB(const GLvoid * data,void * polygonData)105 static void tessVertexCB(const GLvoid *data, void *polygonData) { reinterpret_cast<GluTessWrapper*>(polygonData)->tessVertex(data); }
tessCombineCB(const GLdouble newVertex[3],const GLdouble * neighborVertex[4],const GLfloat neighborWeight[4],GLdouble ** outData,void * polygonData)106 static void tessCombineCB(const GLdouble newVertex[3], const GLdouble *neighborVertex[4], const GLfloat neighborWeight[4], GLdouble **outData, void *polygonData)
107 { reinterpret_cast<GluTessWrapper*>(polygonData)->tessCombine(newVertex, neighborVertex, neighborWeight, outData); }
tessErrorCB(GLenum errorCode,void * polygonData)108 static void tessErrorCB(GLenum errorCode, void *polygonData) { reinterpret_cast<GluTessWrapper*>(polygonData)->tessError(errorCode); }
109
tessBegin(GLenum which)110 void tessBegin(GLenum which)
111 {
112 assert(which == GL_TRIANGLES || which == GL_TRIANGLE_FAN || which == GL_TRIANGLE_STRIP);
113 m_primitive_type = which;
114 m_num_points = 0;
115 }
116
tessEnd()117 void tessEnd()
118 {
119 m_num_points = 0;
120 }
121
tessVertex(const GLvoid * data)122 void tessVertex(const GLvoid *data)
123 {
124 if (data == nullptr)
125 return;
126 const GLdouble *ptr = (const GLdouble*)data;
127 ++ m_num_points;
128 if (m_num_points == 1) {
129 memcpy(m_pt0, ptr, sizeof(GLdouble) * 3);
130 } else if (m_num_points == 2) {
131 memcpy(m_pt1, ptr, sizeof(GLdouble) * 3);
132 } else {
133 bool flip = m_flipped;
134 if (m_primitive_type == GL_TRIANGLE_STRIP && m_num_points == 4) {
135 flip = !flip;
136 m_num_points = 2;
137 }
138 m_output_triangles.emplace_back(m_pt0[0], m_pt0[1], m_z);
139 if (flip) {
140 m_output_triangles.emplace_back(ptr[0], ptr[1], m_z);
141 m_output_triangles.emplace_back(m_pt1[0], m_pt1[1], m_z);
142 } else {
143 m_output_triangles.emplace_back(m_pt1[0], m_pt1[1], m_z);
144 m_output_triangles.emplace_back(ptr[0], ptr[1], m_z);
145 }
146 if (m_primitive_type == GL_TRIANGLE_STRIP) {
147 memcpy(m_pt0, m_pt1, sizeof(GLdouble) * 3);
148 memcpy(m_pt1, ptr, sizeof(GLdouble) * 3);
149 } else if (m_primitive_type == GL_TRIANGLE_FAN) {
150 memcpy(m_pt1, ptr, sizeof(GLdouble) * 3);
151 } else {
152 assert(m_primitive_type == GL_TRIANGLES);
153 assert(m_num_points == 3);
154 m_num_points = 0;
155 }
156 }
157 }
158
tessCombine(const GLdouble newVertex[3],const GLdouble * neighborVertex[4],const GLfloat neighborWeight[4],GLdouble ** outData)159 void tessCombine(const GLdouble newVertex[3], const GLdouble *neighborVertex[4], const GLfloat neighborWeight[4], GLdouble **outData)
160 {
161 m_intersection_points.emplace_back(newVertex[0], newVertex[1], m_z);
162 *outData = m_intersection_points.back().data();
163 }
164
tessError(GLenum errorCode)165 static void tessError(GLenum errorCode)
166 {
167 // const GLubyte *errorStr;
168 // errorStr = gluErrorString(errorCode);
169 // printf("Error: %s\n", (const char*)errorStr);
170 }
171
172 // Instance owned over the life time of this wrapper.
173 GLUtesselator *m_tesselator;
174
175 // Currently processed primitive type.
176 GLenum m_primitive_type;
177 // Two last vertices received for m_primitive_type. Used for processing triangle strips, fans etc.
178 GLdouble m_pt0[3];
179 GLdouble m_pt1[3];
180 // Number of points processed over m_primitive_type.
181 int m_num_points;
182 // Triangles generated by the tesselator.
183 Pointf3s m_output_triangles;
184 // Intersection points generated by tessCombine callback. There should be none if the input contour is not self intersecting.
185 std::deque<Vec3d> m_intersection_points;
186 // Fixed third coordinate.
187 double m_z;
188 // Output triangles shall be flipped (normal points down).
189 bool m_flipped;
190 };
191
triangulate_expolygon_3d(const ExPolygon & poly,coordf_t z,bool flip)192 std::vector<Vec3d> triangulate_expolygon_3d(const ExPolygon &poly, coordf_t z, bool flip)
193 {
194 GluTessWrapper tess;
195 return tess.tesselate3d(poly, z, flip);
196 }
197
triangulate_expolygons_3d(const ExPolygons & polys,coordf_t z,bool flip)198 std::vector<Vec3d> triangulate_expolygons_3d(const ExPolygons &polys, coordf_t z, bool flip)
199 {
200 GluTessWrapper tess;
201 return tess.tesselate3d(polys, z, flip);
202 }
203
triangulate_expolygon_2d(const ExPolygon & poly,bool flip)204 std::vector<Vec2d> triangulate_expolygon_2d(const ExPolygon &poly, bool flip)
205 {
206 GluTessWrapper tess;
207 std::vector<Vec3d> triangles = tess.tesselate3d(poly, 0, flip);
208 std::vector<Vec2d> out;
209 out.reserve(triangles.size());
210 for (const Vec3d &pt : triangles)
211 out.emplace_back(pt.x(), pt.y());
212 return out;
213 }
214
triangulate_expolygons_2d(const ExPolygons & polys,bool flip)215 std::vector<Vec2d> triangulate_expolygons_2d(const ExPolygons &polys, bool flip)
216 {
217 GluTessWrapper tess;
218 std::vector<Vec3d> triangles = tess.tesselate3d(polys, 0, flip);
219 std::vector<Vec2d> out;
220 out.reserve(triangles.size());
221 for (const Vec3d &pt : triangles)
222 out.emplace_back(pt.x(), pt.y());
223 return out;
224 }
225
triangulate_expolygon_2f(const ExPolygon & poly,bool flip)226 std::vector<Vec2f> triangulate_expolygon_2f(const ExPolygon &poly, bool flip)
227 {
228 GluTessWrapper tess;
229 std::vector<Vec3d> triangles = tess.tesselate3d(poly, 0, flip);
230 std::vector<Vec2f> out;
231 out.reserve(triangles.size());
232 for (const Vec3d &pt : triangles)
233 out.emplace_back(float(pt.x()), float(pt.y()));
234 return out;
235 }
236
triangulate_expolygons_2f(const ExPolygons & polys,bool flip)237 std::vector<Vec2f> triangulate_expolygons_2f(const ExPolygons &polys, bool flip)
238 {
239 GluTessWrapper tess;
240 std::vector<Vec3d> triangles = tess.tesselate3d(polys, 0, flip);
241 std::vector<Vec2f> out;
242 out.reserve(triangles.size());
243 for (const Vec3d &pt : triangles)
244 out.emplace_back(float(pt.x()), float(pt.y()));
245 return out;
246 }
247
248 } // namespace Slic3r
249