1 #include "ClipperUtils.hpp"
2 #include "Geometry.hpp"
3 #include "ShortestPath.hpp"
4
5 // #define CLIPPER_UTILS_DEBUG
6
7 #ifdef CLIPPER_UTILS_DEBUG
8 #include "SVG.hpp"
9 #endif /* CLIPPER_UTILS_DEBUG */
10
11 // Profiling support using the Shiny intrusive profiler
12 //#define CLIPPER_UTILS_PROFILE
13 #if defined(SLIC3R_PROFILE) && defined(CLIPPER_UTILS_PROFILE)
14 #include <Shiny/Shiny.h>
15 #define CLIPPERUTILS_PROFILE_FUNC() PROFILE_FUNC()
16 #define CLIPPERUTILS_PROFILE_BLOCK(name) PROFILE_BLOCK(name)
17 #else
18 #define CLIPPERUTILS_PROFILE_FUNC()
19 #define CLIPPERUTILS_PROFILE_BLOCK(name)
20 #endif
21
22 #define CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR (0.005f)
23
24 namespace Slic3r {
25
26 #ifdef CLIPPER_UTILS_DEBUG
27 bool clipper_export_enabled = false;
28 // For debugging the Clipper library, for providing bug reports to the Clipper author.
export_clipper_input_polygons_bin(const char * path,const ClipperLib::Paths & input_subject,const ClipperLib::Paths & input_clip)29 bool export_clipper_input_polygons_bin(const char *path, const ClipperLib::Paths &input_subject, const ClipperLib::Paths &input_clip)
30 {
31 FILE *pfile = fopen(path, "wb");
32 if (pfile == NULL)
33 return false;
34
35 uint32_t sz = uint32_t(input_subject.size());
36 fwrite(&sz, 1, sizeof(sz), pfile);
37 for (size_t i = 0; i < input_subject.size(); ++i) {
38 const ClipperLib::Path &path = input_subject[i];
39 sz = uint32_t(path.size());
40 ::fwrite(&sz, 1, sizeof(sz), pfile);
41 ::fwrite(path.data(), sizeof(ClipperLib::IntPoint), sz, pfile);
42 }
43 sz = uint32_t(input_clip.size());
44 ::fwrite(&sz, 1, sizeof(sz), pfile);
45 for (size_t i = 0; i < input_clip.size(); ++i) {
46 const ClipperLib::Path &path = input_clip[i];
47 sz = uint32_t(path.size());
48 ::fwrite(&sz, 1, sizeof(sz), pfile);
49 ::fwrite(path.data(), sizeof(ClipperLib::IntPoint), sz, pfile);
50 }
51 ::fclose(pfile);
52 return true;
53
54 err:
55 ::fclose(pfile);
56 return false;
57 }
58 #endif /* CLIPPER_UTILS_DEBUG */
59
scaleClipperPolygon(ClipperLib::Path & polygon)60 void scaleClipperPolygon(ClipperLib::Path &polygon)
61 {
62 CLIPPERUTILS_PROFILE_FUNC();
63 for (ClipperLib::Path::iterator pit = polygon.begin(); pit != polygon.end(); ++pit) {
64 pit->X <<= CLIPPER_OFFSET_POWER_OF_2;
65 pit->Y <<= CLIPPER_OFFSET_POWER_OF_2;
66 }
67 }
68
scaleClipperPolygons(ClipperLib::Paths & polygons)69 void scaleClipperPolygons(ClipperLib::Paths &polygons)
70 {
71 CLIPPERUTILS_PROFILE_FUNC();
72 for (ClipperLib::Paths::iterator it = polygons.begin(); it != polygons.end(); ++it)
73 for (ClipperLib::Path::iterator pit = (*it).begin(); pit != (*it).end(); ++pit) {
74 pit->X <<= CLIPPER_OFFSET_POWER_OF_2;
75 pit->Y <<= CLIPPER_OFFSET_POWER_OF_2;
76 }
77 }
78
unscaleClipperPolygon(ClipperLib::Path & polygon)79 void unscaleClipperPolygon(ClipperLib::Path &polygon)
80 {
81 CLIPPERUTILS_PROFILE_FUNC();
82 for (ClipperLib::Path::iterator pit = polygon.begin(); pit != polygon.end(); ++pit) {
83 pit->X += CLIPPER_OFFSET_SCALE_ROUNDING_DELTA;
84 pit->Y += CLIPPER_OFFSET_SCALE_ROUNDING_DELTA;
85 pit->X >>= CLIPPER_OFFSET_POWER_OF_2;
86 pit->Y >>= CLIPPER_OFFSET_POWER_OF_2;
87 }
88 }
89
unscaleClipperPolygons(ClipperLib::Paths & polygons)90 void unscaleClipperPolygons(ClipperLib::Paths &polygons)
91 {
92 CLIPPERUTILS_PROFILE_FUNC();
93 for (ClipperLib::Paths::iterator it = polygons.begin(); it != polygons.end(); ++it)
94 for (ClipperLib::Path::iterator pit = (*it).begin(); pit != (*it).end(); ++pit) {
95 pit->X += CLIPPER_OFFSET_SCALE_ROUNDING_DELTA;
96 pit->Y += CLIPPER_OFFSET_SCALE_ROUNDING_DELTA;
97 pit->X >>= CLIPPER_OFFSET_POWER_OF_2;
98 pit->Y >>= CLIPPER_OFFSET_POWER_OF_2;
99 }
100 }
101
102 //-----------------------------------------------------------
103 // legacy code from Clipper documentation
AddOuterPolyNodeToExPolygons(ClipperLib::PolyNode & polynode,ExPolygons * expolygons)104 void AddOuterPolyNodeToExPolygons(ClipperLib::PolyNode& polynode, ExPolygons* expolygons)
105 {
106 size_t cnt = expolygons->size();
107 expolygons->resize(cnt + 1);
108 (*expolygons)[cnt].contour = ClipperPath_to_Slic3rPolygon(polynode.Contour);
109 (*expolygons)[cnt].holes.resize(polynode.ChildCount());
110 for (int i = 0; i < polynode.ChildCount(); ++i)
111 {
112 (*expolygons)[cnt].holes[i] = ClipperPath_to_Slic3rPolygon(polynode.Childs[i]->Contour);
113 //Add outer polygons contained by (nested within) holes ...
114 for (int j = 0; j < polynode.Childs[i]->ChildCount(); ++j)
115 AddOuterPolyNodeToExPolygons(*polynode.Childs[i]->Childs[j], expolygons);
116 }
117 }
118
PolyTreeToExPolygons(ClipperLib::PolyTree & polytree)119 ExPolygons PolyTreeToExPolygons(ClipperLib::PolyTree& polytree)
120 {
121 ExPolygons retval;
122 for (int i = 0; i < polytree.ChildCount(); ++i)
123 AddOuterPolyNodeToExPolygons(*polytree.Childs[i], &retval);
124 return retval;
125 }
126 //-----------------------------------------------------------
127
ClipperPath_to_Slic3rPolygon(const ClipperLib::Path & input)128 Slic3r::Polygon ClipperPath_to_Slic3rPolygon(const ClipperLib::Path &input)
129 {
130 Polygon retval;
131 for (ClipperLib::Path::const_iterator pit = input.begin(); pit != input.end(); ++pit)
132 retval.points.emplace_back(pit->X, pit->Y);
133 return retval;
134 }
135
ClipperPath_to_Slic3rPolyline(const ClipperLib::Path & input)136 Slic3r::Polyline ClipperPath_to_Slic3rPolyline(const ClipperLib::Path &input)
137 {
138 Polyline retval;
139 for (ClipperLib::Path::const_iterator pit = input.begin(); pit != input.end(); ++pit)
140 retval.points.emplace_back(pit->X, pit->Y);
141 return retval;
142 }
143
ClipperPaths_to_Slic3rPolygons(const ClipperLib::Paths & input)144 Slic3r::Polygons ClipperPaths_to_Slic3rPolygons(const ClipperLib::Paths &input)
145 {
146 Slic3r::Polygons retval;
147 retval.reserve(input.size());
148 for (ClipperLib::Paths::const_iterator it = input.begin(); it != input.end(); ++it)
149 retval.emplace_back(ClipperPath_to_Slic3rPolygon(*it));
150 return retval;
151 }
152
ClipperPaths_to_Slic3rPolylines(const ClipperLib::Paths & input)153 Slic3r::Polylines ClipperPaths_to_Slic3rPolylines(const ClipperLib::Paths &input)
154 {
155 Slic3r::Polylines retval;
156 retval.reserve(input.size());
157 for (ClipperLib::Paths::const_iterator it = input.begin(); it != input.end(); ++it)
158 retval.emplace_back(ClipperPath_to_Slic3rPolyline(*it));
159 return retval;
160 }
161
ClipperPaths_to_Slic3rExPolygons(const ClipperLib::Paths & input)162 ExPolygons ClipperPaths_to_Slic3rExPolygons(const ClipperLib::Paths &input)
163 {
164 // init Clipper
165 ClipperLib::Clipper clipper;
166 clipper.Clear();
167
168 // perform union
169 clipper.AddPaths(input, ClipperLib::ptSubject, true);
170 ClipperLib::PolyTree polytree;
171 clipper.Execute(ClipperLib::ctUnion, polytree, ClipperLib::pftEvenOdd, ClipperLib::pftEvenOdd); // offset results work with both EvenOdd and NonZero
172
173 // write to ExPolygons object
174 return PolyTreeToExPolygons(polytree);
175 }
176
Slic3rMultiPoint_to_ClipperPath(const MultiPoint & input)177 ClipperLib::Path Slic3rMultiPoint_to_ClipperPath(const MultiPoint &input)
178 {
179 ClipperLib::Path retval;
180 for (Points::const_iterator pit = input.points.begin(); pit != input.points.end(); ++pit)
181 retval.emplace_back((*pit)(0), (*pit)(1));
182 return retval;
183 }
184
Slic3rMultiPoint_to_ClipperPath_reversed(const Slic3r::MultiPoint & input)185 ClipperLib::Path Slic3rMultiPoint_to_ClipperPath_reversed(const Slic3r::MultiPoint &input)
186 {
187 ClipperLib::Path output;
188 output.reserve(input.points.size());
189 for (Slic3r::Points::const_reverse_iterator pit = input.points.rbegin(); pit != input.points.rend(); ++pit)
190 output.emplace_back((*pit)(0), (*pit)(1));
191 return output;
192 }
193
Slic3rMultiPoints_to_ClipperPaths(const Polygons & input)194 ClipperLib::Paths Slic3rMultiPoints_to_ClipperPaths(const Polygons &input)
195 {
196 ClipperLib::Paths retval;
197 for (Polygons::const_iterator it = input.begin(); it != input.end(); ++it)
198 retval.emplace_back(Slic3rMultiPoint_to_ClipperPath(*it));
199 return retval;
200 }
201
Slic3rMultiPoints_to_ClipperPaths(const ExPolygons & input)202 ClipperLib::Paths Slic3rMultiPoints_to_ClipperPaths(const ExPolygons &input)
203 {
204 ClipperLib::Paths retval;
205 for (auto &ep : input) {
206 retval.emplace_back(Slic3rMultiPoint_to_ClipperPath(ep.contour));
207
208 for (auto &h : ep.holes)
209 retval.emplace_back(Slic3rMultiPoint_to_ClipperPath(h));
210 }
211
212 return retval;
213 }
214
Slic3rMultiPoints_to_ClipperPaths(const Polylines & input)215 ClipperLib::Paths Slic3rMultiPoints_to_ClipperPaths(const Polylines &input)
216 {
217 ClipperLib::Paths retval;
218 for (Polylines::const_iterator it = input.begin(); it != input.end(); ++it)
219 retval.emplace_back(Slic3rMultiPoint_to_ClipperPath(*it));
220 return retval;
221 }
222
_offset(ClipperLib::Paths && input,ClipperLib::EndType endType,const float delta,ClipperLib::JoinType joinType,double miterLimit)223 ClipperLib::Paths _offset(ClipperLib::Paths &&input, ClipperLib::EndType endType, const float delta, ClipperLib::JoinType joinType, double miterLimit)
224 {
225 // scale input
226 scaleClipperPolygons(input);
227
228 // perform offset
229 ClipperLib::ClipperOffset co;
230 if (joinType == jtRound)
231 co.ArcTolerance = miterLimit;
232 else
233 co.MiterLimit = miterLimit;
234 float delta_scaled = delta * float(CLIPPER_OFFSET_SCALE);
235 co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
236 co.AddPaths(input, joinType, endType);
237 ClipperLib::Paths retval;
238 co.Execute(retval, delta_scaled);
239
240 // unscale output
241 unscaleClipperPolygons(retval);
242 return retval;
243 }
244
_offset(ClipperLib::Path && input,ClipperLib::EndType endType,const float delta,ClipperLib::JoinType joinType,double miterLimit)245 ClipperLib::Paths _offset(ClipperLib::Path &&input, ClipperLib::EndType endType, const float delta, ClipperLib::JoinType joinType, double miterLimit)
246 {
247 ClipperLib::Paths paths;
248 paths.emplace_back(std::move(input));
249 return _offset(std::move(paths), endType, delta, joinType, miterLimit);
250 }
251
252 // This is a safe variant of the polygon offset, tailored for a single ExPolygon:
253 // a single polygon with multiple non-overlapping holes.
254 // Each contour and hole is offsetted separately, then the holes are subtracted from the outer contours.
_offset(const Slic3r::ExPolygon & expolygon,const float delta,ClipperLib::JoinType joinType,double miterLimit)255 ClipperLib::Paths _offset(const Slic3r::ExPolygon &expolygon, const float delta,
256 ClipperLib::JoinType joinType, double miterLimit)
257 {
258 // printf("new ExPolygon offset\n");
259 // 1) Offset the outer contour.
260 const float delta_scaled = delta * float(CLIPPER_OFFSET_SCALE);
261 ClipperLib::Paths contours;
262 {
263 ClipperLib::Path input = Slic3rMultiPoint_to_ClipperPath(expolygon.contour);
264 scaleClipperPolygon(input);
265 ClipperLib::ClipperOffset co;
266 if (joinType == jtRound)
267 co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
268 else
269 co.MiterLimit = miterLimit;
270 co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
271 co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
272 co.Execute(contours, delta_scaled);
273 }
274
275 // 2) Offset the holes one by one, collect the results.
276 ClipperLib::Paths holes;
277 {
278 holes.reserve(expolygon.holes.size());
279 for (Polygons::const_iterator it_hole = expolygon.holes.begin(); it_hole != expolygon.holes.end(); ++ it_hole) {
280 ClipperLib::Path input = Slic3rMultiPoint_to_ClipperPath_reversed(*it_hole);
281 scaleClipperPolygon(input);
282 ClipperLib::ClipperOffset co;
283 if (joinType == jtRound)
284 co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
285 else
286 co.MiterLimit = miterLimit;
287 co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
288 co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
289 ClipperLib::Paths out;
290 co.Execute(out, - delta_scaled);
291 holes.insert(holes.end(), out.begin(), out.end());
292 }
293 }
294
295 // 3) Subtract holes from the contours.
296 ClipperLib::Paths output;
297 if (holes.empty()) {
298 output = std::move(contours);
299 } else {
300 ClipperLib::Clipper clipper;
301 clipper.Clear();
302 clipper.AddPaths(contours, ClipperLib::ptSubject, true);
303 clipper.AddPaths(holes, ClipperLib::ptClip, true);
304 clipper.Execute(ClipperLib::ctDifference, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
305 }
306
307 // 4) Unscale the output.
308 unscaleClipperPolygons(output);
309 return output;
310 }
311
312 // This is a safe variant of the polygons offset, tailored for multiple ExPolygons.
313 // It is required, that the input expolygons do not overlap and that the holes of each ExPolygon don't intersect with their respective outer contours.
314 // Each ExPolygon is offsetted separately, then the offsetted ExPolygons are united.
_offset(const Slic3r::ExPolygons & expolygons,const float delta,ClipperLib::JoinType joinType,double miterLimit)315 ClipperLib::Paths _offset(const Slic3r::ExPolygons &expolygons, const float delta,
316 ClipperLib::JoinType joinType, double miterLimit)
317 {
318 const float delta_scaled = delta * float(CLIPPER_OFFSET_SCALE);
319 // Offsetted ExPolygons before they are united.
320 ClipperLib::Paths contours_cummulative;
321 contours_cummulative.reserve(expolygons.size());
322 // How many non-empty offsetted expolygons were actually collected into contours_cummulative?
323 // If only one, then there is no need to do a final union.
324 size_t expolygons_collected = 0;
325 for (Slic3r::ExPolygons::const_iterator it_expoly = expolygons.begin(); it_expoly != expolygons.end(); ++ it_expoly) {
326 // 1) Offset the outer contour.
327 ClipperLib::Paths contours;
328 {
329 ClipperLib::Path input = Slic3rMultiPoint_to_ClipperPath(it_expoly->contour);
330 scaleClipperPolygon(input);
331 ClipperLib::ClipperOffset co;
332 if (joinType == jtRound)
333 co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
334 else
335 co.MiterLimit = miterLimit;
336 co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
337 co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
338 co.Execute(contours, delta_scaled);
339 }
340 if (contours.empty())
341 // No need to try to offset the holes.
342 continue;
343
344 if (it_expoly->holes.empty()) {
345 // No need to subtract holes from the offsetted expolygon, we are done.
346 contours_cummulative.insert(contours_cummulative.end(), contours.begin(), contours.end());
347 ++ expolygons_collected;
348 } else {
349 // 2) Offset the holes one by one, collect the offsetted holes.
350 ClipperLib::Paths holes;
351 {
352 for (Polygons::const_iterator it_hole = it_expoly->holes.begin(); it_hole != it_expoly->holes.end(); ++ it_hole) {
353 ClipperLib::Path input = Slic3rMultiPoint_to_ClipperPath_reversed(*it_hole);
354 scaleClipperPolygon(input);
355 ClipperLib::ClipperOffset co;
356 if (joinType == jtRound)
357 co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
358 else
359 co.MiterLimit = miterLimit;
360 co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
361 co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
362 ClipperLib::Paths out;
363 co.Execute(out, - delta_scaled);
364 holes.insert(holes.end(), out.begin(), out.end());
365 }
366 }
367
368 // 3) Subtract holes from the contours.
369 if (holes.empty()) {
370 // No hole remaining after an offset. Just copy the outer contour.
371 contours_cummulative.insert(contours_cummulative.end(), contours.begin(), contours.end());
372 ++ expolygons_collected;
373 } else if (delta < 0) {
374 // Negative offset. There is a chance, that the offsetted hole intersects the outer contour.
375 // Subtract the offsetted holes from the offsetted contours.
376 ClipperLib::Clipper clipper;
377 clipper.Clear();
378 clipper.AddPaths(contours, ClipperLib::ptSubject, true);
379 clipper.AddPaths(holes, ClipperLib::ptClip, true);
380 ClipperLib::Paths output;
381 clipper.Execute(ClipperLib::ctDifference, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
382 if (! output.empty()) {
383 contours_cummulative.insert(contours_cummulative.end(), output.begin(), output.end());
384 ++ expolygons_collected;
385 } else {
386 // The offsetted holes have eaten up the offsetted outer contour.
387 }
388 } else {
389 // Positive offset. As long as the Clipper offset does what one expects it to do, the offsetted hole will have a smaller
390 // area than the original hole or even disappear, therefore there will be no new intersections.
391 // Just collect the reversed holes.
392 contours_cummulative.reserve(contours.size() + holes.size());
393 contours_cummulative.insert(contours_cummulative.end(), contours.begin(), contours.end());
394 // Reverse the holes in place.
395 for (size_t i = 0; i < holes.size(); ++ i)
396 std::reverse(holes[i].begin(), holes[i].end());
397 contours_cummulative.insert(contours_cummulative.end(), holes.begin(), holes.end());
398 ++ expolygons_collected;
399 }
400 }
401 }
402
403 // 4) Unite the offsetted expolygons.
404 ClipperLib::Paths output;
405 if (expolygons_collected > 1 && delta > 0) {
406 // There is a chance that the outwards offsetted expolygons may intersect. Perform a union.
407 ClipperLib::Clipper clipper;
408 clipper.Clear();
409 clipper.AddPaths(contours_cummulative, ClipperLib::ptSubject, true);
410 clipper.Execute(ClipperLib::ctUnion, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
411 } else {
412 // Negative offset. The shrunk expolygons shall not mutually intersect. Just copy the output.
413 output = std::move(contours_cummulative);
414 }
415
416 // 4) Unscale the output.
417 unscaleClipperPolygons(output);
418 return output;
419 }
420
421 ClipperLib::Paths
_offset2(const Polygons & polygons,const float delta1,const float delta2,const ClipperLib::JoinType joinType,const double miterLimit)422 _offset2(const Polygons &polygons, const float delta1, const float delta2,
423 const ClipperLib::JoinType joinType, const double miterLimit)
424 {
425 // read input
426 ClipperLib::Paths input = Slic3rMultiPoints_to_ClipperPaths(polygons);
427
428 // scale input
429 scaleClipperPolygons(input);
430
431 // prepare ClipperOffset object
432 ClipperLib::ClipperOffset co;
433 if (joinType == jtRound) {
434 co.ArcTolerance = miterLimit;
435 } else {
436 co.MiterLimit = miterLimit;
437 }
438 float delta_scaled1 = delta1 * float(CLIPPER_OFFSET_SCALE);
439 float delta_scaled2 = delta2 * float(CLIPPER_OFFSET_SCALE);
440 co.ShortestEdgeLength = double(std::max(std::abs(delta_scaled1), std::abs(delta_scaled2)) * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR);
441
442 // perform first offset
443 ClipperLib::Paths output1;
444 co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
445 co.Execute(output1, delta_scaled1);
446
447 // perform second offset
448 co.Clear();
449 co.AddPaths(output1, joinType, ClipperLib::etClosedPolygon);
450 ClipperLib::Paths retval;
451 co.Execute(retval, delta_scaled2);
452
453 // unscale output
454 unscaleClipperPolygons(retval);
455 return retval;
456 }
457
458 Polygons
offset2(const Polygons & polygons,const float delta1,const float delta2,const ClipperLib::JoinType joinType,const double miterLimit)459 offset2(const Polygons &polygons, const float delta1, const float delta2,
460 const ClipperLib::JoinType joinType, const double miterLimit)
461 {
462 // perform offset
463 ClipperLib::Paths output = _offset2(polygons, delta1, delta2, joinType, miterLimit);
464
465 // convert into ExPolygons
466 return ClipperPaths_to_Slic3rPolygons(output);
467 }
468
469 ExPolygons
offset2_ex(const Polygons & polygons,const float delta1,const float delta2,const ClipperLib::JoinType joinType,const double miterLimit)470 offset2_ex(const Polygons &polygons, const float delta1, const float delta2,
471 const ClipperLib::JoinType joinType, const double miterLimit)
472 {
473 // perform offset
474 ClipperLib::Paths output = _offset2(polygons, delta1, delta2, joinType, miterLimit);
475
476 // convert into ExPolygons
477 return ClipperPaths_to_Slic3rExPolygons(output);
478 }
479
480 //FIXME Vojtech: This functon may likely be optimized to avoid some of the Slic3r to Clipper
481 // conversions and unnecessary Clipper calls.
offset2_ex(const ExPolygons & expolygons,const float delta1,const float delta2,ClipperLib::JoinType joinType,double miterLimit)482 ExPolygons offset2_ex(const ExPolygons &expolygons, const float delta1,
483 const float delta2, ClipperLib::JoinType joinType, double miterLimit)
484 {
485 Polygons polys;
486 for (const ExPolygon &expoly : expolygons)
487 append(polys,
488 offset(offset_ex(expoly, delta1, joinType, miterLimit),
489 delta2, joinType, miterLimit));
490 return union_ex(polys);
491 }
492
493 template<class T, class TSubj, class TClip>
494 T _clipper_do(const ClipperLib::ClipType clipType,
495 TSubj && subject,
496 TClip && clip,
497 const ClipperLib::PolyFillType fillType,
498 const bool safety_offset_)
499 {
500 // read input
501 ClipperLib::Paths input_subject = Slic3rMultiPoints_to_ClipperPaths(std::forward<TSubj>(subject));
502 ClipperLib::Paths input_clip = Slic3rMultiPoints_to_ClipperPaths(std::forward<TClip>(clip));
503
504 // perform safety offset
505 if (safety_offset_) {
506 if (clipType == ClipperLib::ctUnion) {
507 safety_offset(&input_subject);
508 } else {
509 safety_offset(&input_clip);
510 }
511 }
512
513 // init Clipper
514 ClipperLib::Clipper clipper;
515 clipper.Clear();
516
517 // add polygons
518 clipper.AddPaths(input_subject, ClipperLib::ptSubject, true);
519 clipper.AddPaths(input_clip, ClipperLib::ptClip, true);
520
521 // perform operation
522 T retval;
523 clipper.Execute(clipType, retval, fillType, fillType);
524 return retval;
525 }
526
527 // Fix of #117: A large fractal pyramid takes ages to slice
528 // The Clipper library has difficulties processing overlapping polygons.
529 // Namely, the function ClipperLib::JoinCommonEdges() has potentially a terrible time complexity if the output
530 // of the operation is of the PolyTree type.
531 // This function implmenets a following workaround:
532 // 1) Peform the Clipper operation with the output to Paths. This method handles overlaps in a reasonable time.
533 // 2) Run Clipper Union once again to extract the PolyTree from the result of 1).
_clipper_do_polytree2(const ClipperLib::ClipType clipType,const Polygons & subject,const Polygons & clip,const ClipperLib::PolyFillType fillType,const bool safety_offset_)534 inline ClipperLib::PolyTree _clipper_do_polytree2(const ClipperLib::ClipType clipType, const Polygons &subject,
535 const Polygons &clip, const ClipperLib::PolyFillType fillType, const bool safety_offset_)
536 {
537 // read input
538 ClipperLib::Paths input_subject = Slic3rMultiPoints_to_ClipperPaths(subject);
539 ClipperLib::Paths input_clip = Slic3rMultiPoints_to_ClipperPaths(clip);
540
541 // perform safety offset
542 if (safety_offset_)
543 safety_offset((clipType == ClipperLib::ctUnion) ? &input_subject : &input_clip);
544
545 ClipperLib::Clipper clipper;
546 clipper.AddPaths(input_subject, ClipperLib::ptSubject, true);
547 clipper.AddPaths(input_clip, ClipperLib::ptClip, true);
548 // Perform the operation with the output to input_subject.
549 // This pass does not generate a PolyTree, which is a very expensive operation with the current Clipper library
550 // if there are overapping edges.
551 clipper.Execute(clipType, input_subject, fillType, fillType);
552 // Perform an additional Union operation to generate the PolyTree ordering.
553 clipper.Clear();
554 clipper.AddPaths(input_subject, ClipperLib::ptSubject, true);
555 ClipperLib::PolyTree retval;
556 clipper.Execute(ClipperLib::ctUnion, retval, fillType, fillType);
557 return retval;
558 }
559
_clipper_do_pl(const ClipperLib::ClipType clipType,const Polylines & subject,const Polygons & clip,const ClipperLib::PolyFillType fillType,const bool safety_offset_)560 ClipperLib::PolyTree _clipper_do_pl(const ClipperLib::ClipType clipType, const Polylines &subject,
561 const Polygons &clip, const ClipperLib::PolyFillType fillType,
562 const bool safety_offset_)
563 {
564 // read input
565 ClipperLib::Paths input_subject = Slic3rMultiPoints_to_ClipperPaths(subject);
566 ClipperLib::Paths input_clip = Slic3rMultiPoints_to_ClipperPaths(clip);
567
568 // perform safety offset
569 if (safety_offset_) safety_offset(&input_clip);
570
571 // init Clipper
572 ClipperLib::Clipper clipper;
573 clipper.Clear();
574
575 // add polygons
576 clipper.AddPaths(input_subject, ClipperLib::ptSubject, false);
577 clipper.AddPaths(input_clip, ClipperLib::ptClip, true);
578
579 // perform operation
580 ClipperLib::PolyTree retval;
581 clipper.Execute(clipType, retval, fillType, fillType);
582 return retval;
583 }
584
_clipper(ClipperLib::ClipType clipType,const Polygons & subject,const Polygons & clip,bool safety_offset_)585 Polygons _clipper(ClipperLib::ClipType clipType, const Polygons &subject, const Polygons &clip, bool safety_offset_)
586 {
587 return ClipperPaths_to_Slic3rPolygons(_clipper_do<ClipperLib::Paths>(clipType, subject, clip, ClipperLib::pftNonZero, safety_offset_));
588 }
589
_clipper_ex(ClipperLib::ClipType clipType,const Polygons & subject,const Polygons & clip,bool safety_offset_)590 ExPolygons _clipper_ex(ClipperLib::ClipType clipType, const Polygons &subject, const Polygons &clip, bool safety_offset_)
591 {
592 ClipperLib::PolyTree polytree = _clipper_do_polytree2(clipType, subject, clip, ClipperLib::pftNonZero, safety_offset_);
593 return PolyTreeToExPolygons(polytree);
594 }
595
_clipper_pl(ClipperLib::ClipType clipType,const Polylines & subject,const Polygons & clip,bool safety_offset_)596 Polylines _clipper_pl(ClipperLib::ClipType clipType, const Polylines &subject, const Polygons &clip, bool safety_offset_)
597 {
598 ClipperLib::Paths output;
599 ClipperLib::PolyTreeToPaths(_clipper_do_pl(clipType, subject, clip, ClipperLib::pftNonZero, safety_offset_), output);
600 return ClipperPaths_to_Slic3rPolylines(output);
601 }
602
_clipper_pl(ClipperLib::ClipType clipType,const Polygons & subject,const Polygons & clip,bool safety_offset_)603 Polylines _clipper_pl(ClipperLib::ClipType clipType, const Polygons &subject, const Polygons &clip, bool safety_offset_)
604 {
605 // transform input polygons into polylines
606 Polylines polylines;
607 polylines.reserve(subject.size());
608 for (Polygons::const_iterator polygon = subject.begin(); polygon != subject.end(); ++polygon)
609 polylines.emplace_back(polygon->operator Polyline()); // implicit call to split_at_first_point()
610
611 // perform clipping
612 Polylines retval = _clipper_pl(clipType, polylines, clip, safety_offset_);
613
614 /* If the split_at_first_point() call above happens to split the polygon inside the clipping area
615 we would get two consecutive polylines instead of a single one, so we go through them in order
616 to recombine continuous polylines. */
617 for (size_t i = 0; i < retval.size(); ++i) {
618 for (size_t j = i+1; j < retval.size(); ++j) {
619 if (retval[i].points.back() == retval[j].points.front()) {
620 /* If last point of i coincides with first point of j,
621 append points of j to i and delete j */
622 retval[i].points.insert(retval[i].points.end(), retval[j].points.begin()+1, retval[j].points.end());
623 retval.erase(retval.begin() + j);
624 --j;
625 } else if (retval[i].points.front() == retval[j].points.back()) {
626 /* If first point of i coincides with last point of j,
627 prepend points of j to i and delete j */
628 retval[i].points.insert(retval[i].points.begin(), retval[j].points.begin(), retval[j].points.end()-1);
629 retval.erase(retval.begin() + j);
630 --j;
631 } else if (retval[i].points.front() == retval[j].points.front()) {
632 /* Since Clipper does not preserve orientation of polylines,
633 also check the case when first point of i coincides with first point of j. */
634 retval[j].reverse();
635 retval[i].points.insert(retval[i].points.begin(), retval[j].points.begin(), retval[j].points.end()-1);
636 retval.erase(retval.begin() + j);
637 --j;
638 } else if (retval[i].points.back() == retval[j].points.back()) {
639 /* Since Clipper does not preserve orientation of polylines,
640 also check the case when last point of i coincides with last point of j. */
641 retval[j].reverse();
642 retval[i].points.insert(retval[i].points.end(), retval[j].points.begin()+1, retval[j].points.end());
643 retval.erase(retval.begin() + j);
644 --j;
645 }
646 }
647 }
648 return retval;
649 }
650
651 Lines
_clipper_ln(ClipperLib::ClipType clipType,const Lines & subject,const Polygons & clip,bool safety_offset_)652 _clipper_ln(ClipperLib::ClipType clipType, const Lines &subject, const Polygons &clip,
653 bool safety_offset_)
654 {
655 // convert Lines to Polylines
656 Polylines polylines;
657 polylines.reserve(subject.size());
658 for (const Line &line : subject)
659 polylines.emplace_back(Polyline(line.a, line.b));
660
661 // perform operation
662 polylines = _clipper_pl(clipType, polylines, clip, safety_offset_);
663
664 // convert Polylines to Lines
665 Lines retval;
666 for (Polylines::const_iterator polyline = polylines.begin(); polyline != polylines.end(); ++polyline)
667 retval.emplace_back(polyline->operator Line());
668 return retval;
669 }
670
union_pt(const Polygons & subject,bool safety_offset_)671 ClipperLib::PolyTree union_pt(const Polygons &subject, bool safety_offset_)
672 {
673 return _clipper_do<ClipperLib::PolyTree>(ClipperLib::ctUnion, subject, Polygons(), ClipperLib::pftEvenOdd, safety_offset_);
674 }
675
union_pt(const ExPolygons & subject,bool safety_offset_)676 ClipperLib::PolyTree union_pt(const ExPolygons &subject, bool safety_offset_)
677 {
678 return _clipper_do<ClipperLib::PolyTree>(ClipperLib::ctUnion, subject, Polygons(), ClipperLib::pftEvenOdd, safety_offset_);
679 }
680
union_pt(Polygons && subject,bool safety_offset_)681 ClipperLib::PolyTree union_pt(Polygons &&subject, bool safety_offset_)
682 {
683 return _clipper_do<ClipperLib::PolyTree>(ClipperLib::ctUnion, std::move(subject), Polygons(), ClipperLib::pftEvenOdd, safety_offset_);
684 }
685
union_pt(ExPolygons && subject,bool safety_offset_)686 ClipperLib::PolyTree union_pt(ExPolygons &&subject, bool safety_offset_)
687 {
688 return _clipper_do<ClipperLib::PolyTree>(ClipperLib::ctUnion, std::move(subject), Polygons(), ClipperLib::pftEvenOdd, safety_offset_);
689 }
690
691 // Simple spatial ordering of Polynodes
order_nodes(const ClipperLib::PolyNodes & nodes)692 ClipperLib::PolyNodes order_nodes(const ClipperLib::PolyNodes &nodes)
693 {
694 // collect ordering points
695 Points ordering_points;
696 ordering_points.reserve(nodes.size());
697
698 for (const ClipperLib::PolyNode *node : nodes)
699 ordering_points.emplace_back(
700 Point(node->Contour.front().X, node->Contour.front().Y));
701
702 // perform the ordering
703 ClipperLib::PolyNodes ordered_nodes =
704 chain_clipper_polynodes(ordering_points, nodes);
705
706 return ordered_nodes;
707 }
708
traverse_pt_noholes(const ClipperLib::PolyNodes & nodes,Polygons * out)709 static void traverse_pt_noholes(const ClipperLib::PolyNodes &nodes, Polygons *out)
710 {
711 foreach_node<e_ordering::ON>(nodes, [&out](const ClipperLib::PolyNode *node)
712 {
713 traverse_pt_noholes(node->Childs, out);
714 out->emplace_back(ClipperPath_to_Slic3rPolygon(node->Contour));
715 if (node->IsHole()) out->back().reverse(); // ccw
716 });
717 }
718
traverse_pt_outside_in(const ClipperLib::PolyNodes & nodes,Polygons * retval)719 static void traverse_pt_outside_in(const ClipperLib::PolyNodes &nodes, Polygons *retval)
720 {
721 // collect ordering points
722 Points ordering_points;
723 ordering_points.reserve(nodes.size());
724 for (const ClipperLib::PolyNode *node : nodes)
725 ordering_points.emplace_back(node->Contour.front().X, node->Contour.front().Y);
726
727 // Perform the ordering, push results recursively.
728 //FIXME pass the last point to chain_clipper_polynodes?
729 for (const ClipperLib::PolyNode *node : chain_clipper_polynodes(ordering_points, nodes)) {
730 retval->emplace_back(ClipperPath_to_Slic3rPolygon(node->Contour));
731 if (node->IsHole())
732 // Orient a hole, which is clockwise oriented, to CCW.
733 retval->back().reverse();
734 // traverse the next depth
735 traverse_pt_outside_in(node->Childs, retval);
736 }
737 }
738
union_pt_chained_outside_in(const Polygons & subject,bool safety_offset_)739 Polygons union_pt_chained_outside_in(const Polygons &subject, bool safety_offset_)
740 {
741 ClipperLib::PolyTree polytree = union_pt(subject, safety_offset_);
742
743 Polygons retval;
744 traverse_pt_outside_in(polytree.Childs, &retval);
745 return retval;
746 }
747
simplify_polygons(const Polygons & subject,bool preserve_collinear)748 Polygons simplify_polygons(const Polygons &subject, bool preserve_collinear)
749 {
750 // convert into Clipper polygons
751 ClipperLib::Paths input_subject = Slic3rMultiPoints_to_ClipperPaths(subject);
752
753 ClipperLib::Paths output;
754 if (preserve_collinear) {
755 ClipperLib::Clipper c;
756 c.PreserveCollinear(true);
757 c.StrictlySimple(true);
758 c.AddPaths(input_subject, ClipperLib::ptSubject, true);
759 c.Execute(ClipperLib::ctUnion, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
760 } else {
761 ClipperLib::SimplifyPolygons(input_subject, output, ClipperLib::pftNonZero);
762 }
763
764 // convert into Slic3r polygons
765 return ClipperPaths_to_Slic3rPolygons(output);
766 }
767
simplify_polygons_ex(const Polygons & subject,bool preserve_collinear)768 ExPolygons simplify_polygons_ex(const Polygons &subject, bool preserve_collinear)
769 {
770 if (! preserve_collinear)
771 return union_ex(simplify_polygons(subject, false));
772
773 // convert into Clipper polygons
774 ClipperLib::Paths input_subject = Slic3rMultiPoints_to_ClipperPaths(subject);
775
776 ClipperLib::PolyTree polytree;
777
778 ClipperLib::Clipper c;
779 c.PreserveCollinear(true);
780 c.StrictlySimple(true);
781 c.AddPaths(input_subject, ClipperLib::ptSubject, true);
782 c.Execute(ClipperLib::ctUnion, polytree, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
783
784 // convert into ExPolygons
785 return PolyTreeToExPolygons(polytree);
786 }
787
safety_offset(ClipperLib::Paths * paths)788 void safety_offset(ClipperLib::Paths* paths)
789 {
790 CLIPPERUTILS_PROFILE_FUNC();
791
792 // scale input
793 scaleClipperPolygons(*paths);
794
795 // perform offset (delta = scale 1e-05)
796 ClipperLib::ClipperOffset co;
797 #ifdef CLIPPER_UTILS_DEBUG
798 if (clipper_export_enabled) {
799 static int iRun = 0;
800 export_clipper_input_polygons_bin(debug_out_path("safety_offset-polygons-%d", ++iRun).c_str(), *paths, ClipperLib::Paths());
801 }
802 #endif /* CLIPPER_UTILS_DEBUG */
803 ClipperLib::Paths out;
804 for (size_t i = 0; i < paths->size(); ++ i) {
805 ClipperLib::Path &path = (*paths)[i];
806 co.Clear();
807 co.MiterLimit = 2;
808 bool ccw = ClipperLib::Orientation(path);
809 if (! ccw)
810 std::reverse(path.begin(), path.end());
811 {
812 CLIPPERUTILS_PROFILE_BLOCK(safety_offset_AddPaths);
813 co.AddPath((*paths)[i], ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
814 }
815 {
816 CLIPPERUTILS_PROFILE_BLOCK(safety_offset_Execute);
817 // offset outside by 10um
818 ClipperLib::Paths out_this;
819 co.Execute(out_this, ccw ? 10.f * float(CLIPPER_OFFSET_SCALE) : -10.f * float(CLIPPER_OFFSET_SCALE));
820 if (! ccw) {
821 // Reverse the resulting contours once again.
822 for (ClipperLib::Paths::iterator it = out_this.begin(); it != out_this.end(); ++ it)
823 std::reverse(it->begin(), it->end());
824 }
825 if (out.empty())
826 out = std::move(out_this);
827 else
828 std::move(std::begin(out_this), std::end(out_this), std::back_inserter(out));
829 }
830 }
831 *paths = std::move(out);
832
833 // unscale output
834 unscaleClipperPolygons(*paths);
835 }
836
top_level_islands(const Slic3r::Polygons & polygons)837 Polygons top_level_islands(const Slic3r::Polygons &polygons)
838 {
839 // init Clipper
840 ClipperLib::Clipper clipper;
841 clipper.Clear();
842 // perform union
843 clipper.AddPaths(Slic3rMultiPoints_to_ClipperPaths(polygons), ClipperLib::ptSubject, true);
844 ClipperLib::PolyTree polytree;
845 clipper.Execute(ClipperLib::ctUnion, polytree, ClipperLib::pftEvenOdd, ClipperLib::pftEvenOdd);
846 // Convert only the top level islands to the output.
847 Polygons out;
848 out.reserve(polytree.ChildCount());
849 for (int i = 0; i < polytree.ChildCount(); ++i)
850 out.emplace_back(ClipperPath_to_Slic3rPolygon(polytree.Childs[i]->Contour));
851 return out;
852 }
853
854 // Outer offset shall not split the input contour into multiples. It is expected, that the solution will be non empty and it will contain just a single polygon.
fix_after_outer_offset(const ClipperLib::Path & input,ClipperLib::PolyFillType filltype,bool reverse_result)855 ClipperLib::Paths fix_after_outer_offset(
856 const ClipperLib::Path &input,
857 // combination of default prameters to correspond to void ClipperOffset::Execute(Paths& solution, double delta)
858 // to produce a CCW output contour from CCW input contour for a positive offset.
859 ClipperLib::PolyFillType filltype, // = ClipperLib::pftPositive
860 bool reverse_result) // = false
861 {
862 ClipperLib::Paths solution;
863 if (! input.empty()) {
864 ClipperLib::Clipper clipper;
865 clipper.AddPath(input, ClipperLib::ptSubject, true);
866 clipper.ReverseSolution(reverse_result);
867 clipper.Execute(ClipperLib::ctUnion, solution, filltype, filltype);
868 }
869 return solution;
870 }
871
872 // Inner offset may split the source contour into multiple contours, but one resulting contour shall not lie inside the other.
fix_after_inner_offset(const ClipperLib::Path & input,ClipperLib::PolyFillType filltype,bool reverse_result)873 ClipperLib::Paths fix_after_inner_offset(
874 const ClipperLib::Path &input,
875 // combination of default prameters to correspond to void ClipperOffset::Execute(Paths& solution, double delta)
876 // to produce a CCW output contour from CCW input contour for a negative offset.
877 ClipperLib::PolyFillType filltype, // = ClipperLib::pftNegative
878 bool reverse_result) // = true
879 {
880 ClipperLib::Paths solution;
881 if (! input.empty()) {
882 ClipperLib::Clipper clipper;
883 clipper.AddPath(input, ClipperLib::ptSubject, true);
884 ClipperLib::IntRect r = clipper.GetBounds();
885 r.left -= 10; r.top -= 10; r.right += 10; r.bottom += 10;
886 if (filltype == ClipperLib::pftPositive)
887 clipper.AddPath({ ClipperLib::IntPoint(r.left, r.bottom), ClipperLib::IntPoint(r.left, r.top), ClipperLib::IntPoint(r.right, r.top), ClipperLib::IntPoint(r.right, r.bottom) }, ClipperLib::ptSubject, true);
888 else
889 clipper.AddPath({ ClipperLib::IntPoint(r.left, r.bottom), ClipperLib::IntPoint(r.right, r.bottom), ClipperLib::IntPoint(r.right, r.top), ClipperLib::IntPoint(r.left, r.top) }, ClipperLib::ptSubject, true);
890 clipper.ReverseSolution(reverse_result);
891 clipper.Execute(ClipperLib::ctUnion, solution, filltype, filltype);
892 if (! solution.empty())
893 solution.erase(solution.begin());
894 }
895 return solution;
896 }
897
mittered_offset_path_scaled(const Points & contour,const std::vector<float> & deltas,double miter_limit)898 ClipperLib::Path mittered_offset_path_scaled(const Points &contour, const std::vector<float> &deltas, double miter_limit)
899 {
900 assert(contour.size() == deltas.size());
901
902 #ifndef NDEBUG
903 // Verify that the deltas are either all positive, or all negative.
904 bool positive = false;
905 bool negative = false;
906 for (float delta : deltas)
907 if (delta < 0.f)
908 negative = true;
909 else if (delta > 0.f)
910 positive = true;
911 assert(! (negative && positive));
912 #endif /* NDEBUG */
913
914 ClipperLib::Path out;
915
916 if (deltas.size() > 2)
917 {
918 out.reserve(contour.size() * 2);
919
920 // Clamp miter limit to 2.
921 miter_limit = (miter_limit > 2.) ? 2. / (miter_limit * miter_limit) : 0.5;
922
923 // perpenduclar vector
924 auto perp = [](const Vec2d &v) -> Vec2d { return Vec2d(v.y(), - v.x()); };
925
926 // Add a new point to the output, scale by CLIPPER_OFFSET_SCALE and round to ClipperLib::cInt.
927 auto add_offset_point = [&out](Vec2d pt) {
928 pt *= double(CLIPPER_OFFSET_SCALE);
929 pt += Vec2d(0.5 - (pt.x() < 0), 0.5 - (pt.y() < 0));
930 out.emplace_back(ClipperLib::cInt(pt.x()), ClipperLib::cInt(pt.y()));
931 };
932
933 // Minimum edge length, squared.
934 double lmin = *std::max_element(deltas.begin(), deltas.end()) * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR;
935 double l2min = lmin * lmin;
936 // Minimum angle to consider two edges to be parallel.
937 // Vojtech's estimate.
938 // const double sin_min_parallel = EPSILON + 1. / double(CLIPPER_OFFSET_SCALE);
939 // Implementation equal to Clipper.
940 const double sin_min_parallel = 1.;
941
942 // Find the last point further from pt by l2min.
943 Vec2d pt = contour.front().cast<double>();
944 size_t iprev = contour.size() - 1;
945 Vec2d ptprev;
946 for (; iprev > 0; -- iprev) {
947 ptprev = contour[iprev].cast<double>();
948 if ((ptprev - pt).squaredNorm() > l2min)
949 break;
950 }
951
952 if (iprev != 0) {
953 size_t ilast = iprev;
954 // Normal to the (pt - ptprev) segment.
955 Vec2d nprev = perp(pt - ptprev).normalized();
956 for (size_t i = 0; ; ) {
957 // Find the next point further from pt by l2min.
958 size_t j = i + 1;
959 Vec2d ptnext;
960 for (; j <= ilast; ++ j) {
961 ptnext = contour[j].cast<double>();
962 double l2 = (ptnext - pt).squaredNorm();
963 if (l2 > l2min)
964 break;
965 }
966 if (j > ilast) {
967 assert(i <= ilast);
968 // If the last edge is too short, merge it with the previous edge.
969 i = ilast;
970 ptnext = contour.front().cast<double>();
971 }
972
973 // Normal to the (ptnext - pt) segment.
974 Vec2d nnext = perp(ptnext - pt).normalized();
975
976 double delta = deltas[i];
977 double sin_a = clamp(-1., 1., cross2(nprev, nnext));
978 double convex = sin_a * delta;
979 if (convex <= - sin_min_parallel) {
980 // Concave corner.
981 add_offset_point(pt + nprev * delta);
982 add_offset_point(pt);
983 add_offset_point(pt + nnext * delta);
984 } else {
985 double dot = nprev.dot(nnext);
986 if (convex < sin_min_parallel && dot > 0.) {
987 // Nearly parallel.
988 add_offset_point((nprev.dot(nnext) > 0.) ? (pt + nprev * delta) : pt);
989 } else {
990 // Convex corner, possibly extremely sharp if convex < sin_min_parallel.
991 double r = 1. + dot;
992 if (r >= miter_limit)
993 add_offset_point(pt + (nprev + nnext) * (delta / r));
994 else {
995 double dx = std::tan(std::atan2(sin_a, dot) / 4.);
996 Vec2d newpt1 = pt + (nprev - perp(nprev) * dx) * delta;
997 Vec2d newpt2 = pt + (nnext + perp(nnext) * dx) * delta;
998 #ifndef NDEBUG
999 Vec2d vedge = 0.5 * (newpt1 + newpt2) - pt;
1000 double dist_norm = vedge.norm();
1001 assert(std::abs(dist_norm - std::abs(delta)) < SCALED_EPSILON);
1002 #endif /* NDEBUG */
1003 add_offset_point(newpt1);
1004 add_offset_point(newpt2);
1005 }
1006 }
1007 }
1008
1009 if (i == ilast)
1010 break;
1011
1012 ptprev = pt;
1013 nprev = nnext;
1014 pt = ptnext;
1015 i = j;
1016 }
1017 }
1018 }
1019
1020 #if 0
1021 {
1022 ClipperLib::Path polytmp(out);
1023 unscaleClipperPolygon(polytmp);
1024 Slic3r::Polygon offsetted = ClipperPath_to_Slic3rPolygon(polytmp);
1025 BoundingBox bbox = get_extents(contour);
1026 bbox.merge(get_extents(offsetted));
1027 static int iRun = 0;
1028 SVG svg(debug_out_path("mittered_offset_path_scaled-%d.svg", iRun ++).c_str(), bbox);
1029 svg.draw_outline(Polygon(contour), "blue", scale_(0.01));
1030 svg.draw_outline(offsetted, "red", scale_(0.01));
1031 svg.draw(contour, "blue", scale_(0.03));
1032 svg.draw((Points)offsetted, "blue", scale_(0.03));
1033 }
1034 #endif
1035
1036 return out;
1037 }
1038
variable_offset_inner(const ExPolygon & expoly,const std::vector<std::vector<float>> & deltas,double miter_limit)1039 Polygons variable_offset_inner(const ExPolygon &expoly, const std::vector<std::vector<float>> &deltas, double miter_limit)
1040 {
1041 #ifndef NDEBUG
1042 // Verify that the deltas are all non positive.
1043 for (const std::vector<float> &ds : deltas)
1044 for (float delta : ds)
1045 assert(delta <= 0.);
1046 assert(expoly.holes.size() + 1 == deltas.size());
1047 #endif /* NDEBUG */
1048
1049 // 1) Offset the outer contour.
1050 ClipperLib::Paths contours = fix_after_inner_offset(mittered_offset_path_scaled(expoly.contour.points, deltas.front(), miter_limit), ClipperLib::pftNegative, true);
1051 #ifndef NDEBUG
1052 for (auto &c : contours)
1053 assert(ClipperLib::Area(c) > 0.);
1054 #endif /* NDEBUG */
1055
1056 // 2) Offset the holes one by one, collect the results.
1057 ClipperLib::Paths holes;
1058 holes.reserve(expoly.holes.size());
1059 for (const Polygon& hole : expoly.holes)
1060 append(holes, fix_after_outer_offset(mittered_offset_path_scaled(hole.points, deltas[1 + &hole - expoly.holes.data()], miter_limit), ClipperLib::pftNegative, false));
1061 #ifndef NDEBUG
1062 for (auto &c : holes)
1063 assert(ClipperLib::Area(c) > 0.);
1064 #endif /* NDEBUG */
1065
1066 // 3) Subtract holes from the contours.
1067 ClipperLib::Paths output;
1068 if (holes.empty())
1069 output = std::move(contours);
1070 else {
1071 ClipperLib::Clipper clipper;
1072 clipper.Clear();
1073 clipper.AddPaths(contours, ClipperLib::ptSubject, true);
1074 clipper.AddPaths(holes, ClipperLib::ptClip, true);
1075 clipper.Execute(ClipperLib::ctDifference, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
1076 }
1077
1078 // 4) Unscale the output.
1079 unscaleClipperPolygons(output);
1080 return ClipperPaths_to_Slic3rPolygons(output);
1081 }
1082
variable_offset_outer(const ExPolygon & expoly,const std::vector<std::vector<float>> & deltas,double miter_limit)1083 Polygons variable_offset_outer(const ExPolygon &expoly, const std::vector<std::vector<float>> &deltas, double miter_limit)
1084 {
1085 #ifndef NDEBUG
1086 // Verify that the deltas are all non positive.
1087 for (const std::vector<float>& ds : deltas)
1088 for (float delta : ds)
1089 assert(delta >= 0.);
1090 assert(expoly.holes.size() + 1 == deltas.size());
1091 #endif /* NDEBUG */
1092
1093 // 1) Offset the outer contour.
1094 ClipperLib::Paths contours = fix_after_outer_offset(mittered_offset_path_scaled(expoly.contour.points, deltas.front(), miter_limit), ClipperLib::pftPositive, false);
1095 #ifndef NDEBUG
1096 for (auto &c : contours)
1097 assert(ClipperLib::Area(c) > 0.);
1098 #endif /* NDEBUG */
1099
1100 // 2) Offset the holes one by one, collect the results.
1101 ClipperLib::Paths holes;
1102 holes.reserve(expoly.holes.size());
1103 for (const Polygon& hole : expoly.holes)
1104 append(holes, fix_after_inner_offset(mittered_offset_path_scaled(hole.points, deltas[1 + &hole - expoly.holes.data()], miter_limit), ClipperLib::pftPositive, true));
1105 #ifndef NDEBUG
1106 for (auto &c : holes)
1107 assert(ClipperLib::Area(c) > 0.);
1108 #endif /* NDEBUG */
1109
1110 // 3) Subtract holes from the contours.
1111 ClipperLib::Paths output;
1112 if (holes.empty())
1113 output = std::move(contours);
1114 else {
1115 ClipperLib::Clipper clipper;
1116 clipper.Clear();
1117 clipper.AddPaths(contours, ClipperLib::ptSubject, true);
1118 clipper.AddPaths(holes, ClipperLib::ptClip, true);
1119 clipper.Execute(ClipperLib::ctDifference, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
1120 }
1121
1122 // 4) Unscale the output.
1123 unscaleClipperPolygons(output);
1124 return ClipperPaths_to_Slic3rPolygons(output);
1125 }
1126
variable_offset_outer_ex(const ExPolygon & expoly,const std::vector<std::vector<float>> & deltas,double miter_limit)1127 ExPolygons variable_offset_outer_ex(const ExPolygon &expoly, const std::vector<std::vector<float>> &deltas, double miter_limit)
1128 {
1129 #ifndef NDEBUG
1130 // Verify that the deltas are all non positive.
1131 for (const std::vector<float>& ds : deltas)
1132 for (float delta : ds)
1133 assert(delta >= 0.);
1134 assert(expoly.holes.size() + 1 == deltas.size());
1135 #endif /* NDEBUG */
1136
1137 // 1) Offset the outer contour.
1138 ClipperLib::Paths contours = fix_after_outer_offset(mittered_offset_path_scaled(expoly.contour.points, deltas.front(), miter_limit), ClipperLib::pftPositive, false);
1139 #ifndef NDEBUG
1140 for (auto &c : contours)
1141 assert(ClipperLib::Area(c) > 0.);
1142 #endif /* NDEBUG */
1143
1144 // 2) Offset the holes one by one, collect the results.
1145 ClipperLib::Paths holes;
1146 holes.reserve(expoly.holes.size());
1147 for (const Polygon& hole : expoly.holes)
1148 append(holes, fix_after_inner_offset(mittered_offset_path_scaled(hole.points, deltas[1 + &hole - expoly.holes.data()], miter_limit), ClipperLib::pftPositive, true));
1149 #ifndef NDEBUG
1150 for (auto &c : holes)
1151 assert(ClipperLib::Area(c) > 0.);
1152 #endif /* NDEBUG */
1153
1154 // 3) Subtract holes from the contours.
1155 unscaleClipperPolygons(contours);
1156 ExPolygons output;
1157 if (holes.empty()) {
1158 output.reserve(contours.size());
1159 for (ClipperLib::Path &path : contours)
1160 output.emplace_back(ClipperPath_to_Slic3rPolygon(path));
1161 } else {
1162 ClipperLib::Clipper clipper;
1163 unscaleClipperPolygons(holes);
1164 clipper.AddPaths(contours, ClipperLib::ptSubject, true);
1165 clipper.AddPaths(holes, ClipperLib::ptClip, true);
1166 ClipperLib::PolyTree polytree;
1167 clipper.Execute(ClipperLib::ctDifference, polytree, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
1168 output = PolyTreeToExPolygons(polytree);
1169 }
1170
1171 return output;
1172 }
1173
1174
variable_offset_inner_ex(const ExPolygon & expoly,const std::vector<std::vector<float>> & deltas,double miter_limit)1175 ExPolygons variable_offset_inner_ex(const ExPolygon &expoly, const std::vector<std::vector<float>> &deltas, double miter_limit)
1176 {
1177 #ifndef NDEBUG
1178 // Verify that the deltas are all non positive.
1179 for (const std::vector<float>& ds : deltas)
1180 for (float delta : ds)
1181 assert(delta <= 0.);
1182 assert(expoly.holes.size() + 1 == deltas.size());
1183 #endif /* NDEBUG */
1184
1185 // 1) Offset the outer contour.
1186 ClipperLib::Paths contours = fix_after_inner_offset(mittered_offset_path_scaled(expoly.contour.points, deltas.front(), miter_limit), ClipperLib::pftNegative, true);
1187 #ifndef NDEBUG
1188 for (auto &c : contours)
1189 assert(ClipperLib::Area(c) > 0.);
1190 #endif /* NDEBUG */
1191
1192 // 2) Offset the holes one by one, collect the results.
1193 ClipperLib::Paths holes;
1194 holes.reserve(expoly.holes.size());
1195 for (const Polygon& hole : expoly.holes)
1196 append(holes, fix_after_outer_offset(mittered_offset_path_scaled(hole.points, deltas[1 + &hole - expoly.holes.data()], miter_limit), ClipperLib::pftNegative, false));
1197 #ifndef NDEBUG
1198 for (auto &c : holes)
1199 assert(ClipperLib::Area(c) > 0.);
1200 #endif /* NDEBUG */
1201
1202 // 3) Subtract holes from the contours.
1203 unscaleClipperPolygons(contours);
1204 ExPolygons output;
1205 if (holes.empty()) {
1206 output.reserve(contours.size());
1207 for (ClipperLib::Path &path : contours)
1208 output.emplace_back(ClipperPath_to_Slic3rPolygon(path));
1209 } else {
1210 ClipperLib::Clipper clipper;
1211 unscaleClipperPolygons(holes);
1212 clipper.AddPaths(contours, ClipperLib::ptSubject, true);
1213 clipper.AddPaths(holes, ClipperLib::ptClip, true);
1214 ClipperLib::PolyTree polytree;
1215 clipper.Execute(ClipperLib::ctDifference, polytree, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
1216 output = PolyTreeToExPolygons(polytree);
1217 }
1218
1219 return output;
1220 }
1221
1222 }
1223