1 #include <libslic3r/SLA/Pad.hpp>
2 #include <libslic3r/SLA/SpatIndex.hpp>
3 #include <libslic3r/SLA/BoostAdapter.hpp>
4 #include <libslic3r/SLA/Contour3D.hpp>
5
6 #include "ConcaveHull.hpp"
7
8 #include "boost/log/trivial.hpp"
9 #include "ClipperUtils.hpp"
10 #include "Tesselate.hpp"
11 #include "MTUtils.hpp"
12
13 #include "TriangulateWall.hpp"
14
15 // For debugging:
16 // #include <fstream>
17 // #include <libnest2d/tools/benchmark.h>
18 #include "SVG.hpp"
19
20 #include "I18N.hpp"
21 #include <boost/log/trivial.hpp>
22
23 //! macro used to mark string used at localization,
24 //! return same string
25 #define L(s) Slic3r::I18N::translate(s)
26
27 namespace Slic3r { namespace sla {
28
29 namespace {
30
walls(const Polygon & lower,const Polygon & upper,double lower_z_mm,double upper_z_mm)31 Contour3D walls(
32 const Polygon &lower,
33 const Polygon &upper,
34 double lower_z_mm,
35 double upper_z_mm)
36 {
37 Wall w = triangulate_wall(lower, upper, lower_z_mm, upper_z_mm);
38
39 Contour3D ret;
40 ret.points = std::move(w.first);
41 ret.faces3 = std::move(w.second);
42
43 return ret;
44 }
45
46 // Same as walls() but with identical higher and lower polygons.
straight_walls(const Polygon & plate,double lo_z,double hi_z)47 Contour3D inline straight_walls(const Polygon &plate,
48 double lo_z,
49 double hi_z)
50 {
51 return walls(plate, plate, lo_z, hi_z);
52 }
53
54 // Function to cut tiny connector cavities for a given polygon. The input poly
55 // will be offsetted by "padding" and small rectangle shaped cavities will be
56 // inserted along the perimeter in every "stride" distance. The stick rectangles
57 // will have a with about "stick_width". The input dimensions are in world
58 // measure, not the scaled clipper units.
breakstick_holes(Points & pts,double padding,double stride,double stick_width,double penetration)59 void breakstick_holes(Points& pts,
60 double padding,
61 double stride,
62 double stick_width,
63 double penetration)
64 {
65 if(stride <= EPSILON || stick_width <= EPSILON || padding <= EPSILON)
66 return;
67
68 // SVG svg("bridgestick_plate.svg");
69 // svg.draw(poly);
70
71 // The connector stick will be a small rectangle with dimensions
72 // stick_width x (penetration + padding) to have some penetration
73 // into the input polygon.
74
75 Points out;
76 out.reserve(2 * pts.size()); // output polygon points
77
78 // stick bottom and right edge dimensions
79 double sbottom = scaled(stick_width);
80 double sright = scaled(penetration + padding);
81
82 // scaled stride distance
83 double sstride = scaled(stride);
84 double t = 0;
85
86 // process pairs of vertices as an edge, start with the last and
87 // first point
88 for (size_t i = pts.size() - 1, j = 0; j < pts.size(); i = j, ++j) {
89 // Get vertices and the direction vectors
90 const Point &a = pts[i], &b = pts[j];
91 Vec2d dir = b.cast<double>() - a.cast<double>();
92 double nrm = dir.norm();
93 dir /= nrm;
94 Vec2d dirp(-dir(Y), dir(X));
95
96 // Insert start point
97 out.emplace_back(a);
98
99 // dodge the start point, do not make sticks on the joins
100 while (t < sbottom) t += sbottom;
101 double tend = nrm - sbottom;
102
103 while (t < tend) { // insert the stick on the polygon perimeter
104
105 // calculate the stick rectangle vertices and insert them
106 // into the output.
107 Point p1 = a + (t * dir).cast<coord_t>();
108 Point p2 = p1 + (sright * dirp).cast<coord_t>();
109 Point p3 = p2 + (sbottom * dir).cast<coord_t>();
110 Point p4 = p3 + (sright * -dirp).cast<coord_t>();
111 out.insert(out.end(), {p1, p2, p3, p4});
112
113 // continue along the perimeter
114 t += sstride;
115 }
116
117 t = t - nrm;
118
119 // Insert edge endpoint
120 out.emplace_back(b);
121 }
122
123 // move the new points
124 out.shrink_to_fit();
125 pts.swap(out);
126 }
127
128 template<class...Args>
breakstick_holes(const ExPolygons & input,Args...args)129 ExPolygons breakstick_holes(const ExPolygons &input, Args...args)
130 {
131 ExPolygons ret = input;
132 for (ExPolygon &p : ret) {
133 breakstick_holes(p.contour.points, args...);
134 for (auto &h : p.holes) breakstick_holes(h.points, args...);
135 }
136
137 return ret;
138 }
139
get_waffle_offset(const PadConfig & c)140 static inline coord_t get_waffle_offset(const PadConfig &c)
141 {
142 return scaled(c.brim_size_mm + c.wing_distance());
143 }
144
get_merge_distance(const PadConfig & c)145 static inline double get_merge_distance(const PadConfig &c)
146 {
147 return 2. * (1.8 * c.wall_thickness_mm) + c.max_merge_dist_mm;
148 }
149
150 // Part of the pad configuration that is used for 3D geometry generation
151 struct PadConfig3D {
152 double thickness, height, wing_height, slope;
153
PadConfig3DSlic3r::sla::__anon8f5f78410111::PadConfig3D154 explicit PadConfig3D(const PadConfig &cfg2d)
155 : thickness{cfg2d.wall_thickness_mm}
156 , height{cfg2d.full_height()}
157 , wing_height{cfg2d.wall_height_mm}
158 , slope{cfg2d.wall_slope}
159 {}
160
bottom_offsetSlic3r::sla::__anon8f5f78410111::PadConfig3D161 inline double bottom_offset() const
162 {
163 return (thickness + wing_height) / std::tan(slope);
164 }
165 };
166
167 // Outer part of the skeleton is used to generate the waffled edges of the pad.
168 // Inner parts will not be waffled or offsetted. Inner parts are only used if
169 // pad is generated around the object and correspond to holes and inner polygons
170 // in the model blueprint.
171 struct PadSkeleton { ExPolygons inner, outer; };
172
divide_blueprint(const ExPolygons & bp)173 PadSkeleton divide_blueprint(const ExPolygons &bp)
174 {
175 ClipperLib::PolyTree ptree = union_pt(bp);
176
177 PadSkeleton ret;
178 ret.inner.reserve(size_t(ptree.Total()));
179 ret.outer.reserve(size_t(ptree.Total()));
180
181 for (ClipperLib::PolyTree::PolyNode *node : ptree.Childs) {
182 ExPolygon poly(ClipperPath_to_Slic3rPolygon(node->Contour));
183 for (ClipperLib::PolyTree::PolyNode *child : node->Childs) {
184 poly.holes.emplace_back(
185 ClipperPath_to_Slic3rPolygon(child->Contour));
186
187 traverse_pt(child->Childs, &ret.inner);
188 }
189
190 ret.outer.emplace_back(poly);
191 }
192
193 return ret;
194 }
195
196 // A helper class for storing polygons and maintaining a spatial index of their
197 // bounding boxes.
198 class Intersector {
199 BoxIndex m_index;
200 ExPolygons m_polys;
201
202 public:
203
204 // Add a new polygon to the index
add(const ExPolygon & ep)205 void add(const ExPolygon &ep)
206 {
207 m_polys.emplace_back(ep);
208 m_index.insert(BoundingBox{ep}, unsigned(m_index.size()));
209 }
210
211 // Check an arbitrary polygon for intersection with the indexed polygons
intersects(const ExPolygon & poly)212 bool intersects(const ExPolygon &poly)
213 {
214 // Create a suitable query bounding box.
215 auto bb = poly.contour.bounding_box();
216
217 std::vector<BoxIndexEl> qres = m_index.query(bb, BoxIndex::qtIntersects);
218
219 // Now check intersections on the actual polygons (not just the boxes)
220 bool is_overlap = false;
221 auto qit = qres.begin();
222 while (!is_overlap && qit != qres.end())
223 is_overlap = is_overlap || poly.overlaps(m_polys[(qit++)->second]);
224
225 return is_overlap;
226 }
227 };
228
229 // This dummy intersector to implement the "force pad everywhere" feature
230 struct DummyIntersector
231 {
addSlic3r::sla::__anon8f5f78410111::DummyIntersector232 inline void add(const ExPolygon &) {}
intersectsSlic3r::sla::__anon8f5f78410111::DummyIntersector233 inline bool intersects(const ExPolygon &) { return true; }
234 };
235
236 template<class _Intersector>
237 class _AroundPadSkeleton : public PadSkeleton
238 {
239 // A spatial index used to be able to efficiently find intersections of
240 // support polygons with the model polygons.
241 _Intersector m_intersector;
242
243 public:
_AroundPadSkeleton(const ExPolygons & support_blueprint,const ExPolygons & model_blueprint,const PadConfig & cfg,ThrowOnCancel thr)244 _AroundPadSkeleton(const ExPolygons &support_blueprint,
245 const ExPolygons &model_blueprint,
246 const PadConfig & cfg,
247 ThrowOnCancel thr)
248 {
249 // We need to merge the support and the model contours in a special
250 // way in which the model contours have to be substracted from the
251 // support contours. The pad has to have a hole in which the model can
252 // fit perfectly (thus the substraction -- diff_ex). Also, the pad has
253 // to be eliminated from areas where there is no need for a pad, due
254 // to missing supports.
255
256 add_supports_to_index(support_blueprint);
257
258 auto model_bp_offs =
259 offset_ex(model_blueprint,
260 scaled<float>(cfg.embed_object.object_gap_mm),
261 ClipperLib::jtMiter, 1);
262
263 ExPolygons fullcvh =
264 wafflized_concave_hull(support_blueprint, model_bp_offs, cfg, thr);
265
266 auto model_bp_sticks =
267 breakstick_holes(model_bp_offs, cfg.embed_object.object_gap_mm,
268 cfg.embed_object.stick_stride_mm,
269 cfg.embed_object.stick_width_mm,
270 cfg.embed_object.stick_penetration_mm);
271
272 ExPolygons fullpad = diff_ex(fullcvh, model_bp_sticks);
273
274 PadSkeleton divided = divide_blueprint(fullpad);
275
276 remove_redundant_parts(divided.outer);
277 remove_redundant_parts(divided.inner);
278
279 outer = std::move(divided.outer);
280 inner = std::move(divided.inner);
281 }
282
283 private:
284
285 // Add the support blueprint to the search index to be queried later
add_supports_to_index(const ExPolygons & supp_bp)286 void add_supports_to_index(const ExPolygons &supp_bp)
287 {
288 for (auto &ep : supp_bp) m_intersector.add(ep);
289 }
290
291 // Create the wafflized pad around all object in the scene. This pad doesnt
292 // have any holes yet.
wafflized_concave_hull(const ExPolygons & supp_bp,const ExPolygons & model_bp,const PadConfig & cfg,ThrowOnCancel thr)293 ExPolygons wafflized_concave_hull(const ExPolygons &supp_bp,
294 const ExPolygons &model_bp,
295 const PadConfig &cfg,
296 ThrowOnCancel thr)
297 {
298 auto allin = reserve_vector<ExPolygon>(supp_bp.size() + model_bp.size());
299
300 for (auto &ep : supp_bp) allin.emplace_back(ep.contour);
301 for (auto &ep : model_bp) allin.emplace_back(ep.contour);
302
303 ConcaveHull cchull{allin, get_merge_distance(cfg), thr};
304 return offset_waffle_style_ex(cchull, get_waffle_offset(cfg));
305 }
306
307 // To remove parts of the pad skeleton which do not host any supports
remove_redundant_parts(ExPolygons & parts)308 void remove_redundant_parts(ExPolygons &parts)
309 {
310 auto endit = std::remove_if(parts.begin(), parts.end(),
311 [this](const ExPolygon &p) {
312 return !m_intersector.intersects(p);
313 });
314
315 parts.erase(endit, parts.end());
316 }
317 };
318
319 using AroundPadSkeleton = _AroundPadSkeleton<Intersector>;
320 using BrimPadSkeleton = _AroundPadSkeleton<DummyIntersector>;
321
322 class BelowPadSkeleton : public PadSkeleton
323 {
324 public:
BelowPadSkeleton(const ExPolygons & support_blueprint,const ExPolygons & model_blueprint,const PadConfig & cfg,ThrowOnCancel thr)325 BelowPadSkeleton(const ExPolygons &support_blueprint,
326 const ExPolygons &model_blueprint,
327 const PadConfig & cfg,
328 ThrowOnCancel thr)
329 {
330 outer.reserve(support_blueprint.size() + model_blueprint.size());
331
332 for (auto &ep : support_blueprint) outer.emplace_back(ep.contour);
333 for (auto &ep : model_blueprint) outer.emplace_back(ep.contour);
334
335 ConcaveHull ochull{outer, get_merge_distance(cfg), thr};
336
337 outer = offset_waffle_style_ex(ochull, get_waffle_offset(cfg));
338 }
339 };
340
341 // Offset the contour only, leave the holes untouched
342 template<class...Args>
offset_contour_only(const ExPolygon & poly,coord_t delta,Args...args)343 ExPolygon offset_contour_only(const ExPolygon &poly, coord_t delta, Args...args)
344 {
345 ExPolygons tmp = offset_ex(poly.contour, float(delta), args...);
346
347 if (tmp.empty()) return {};
348
349 Polygons holes = poly.holes;
350 for (auto &h : holes) h.reverse();
351
352 tmp = diff_ex(to_polygons(tmp), holes);
353
354 if (tmp.empty()) return {};
355
356 return tmp.front();
357 }
358
add_cavity(Contour3D & pad,ExPolygon & top_poly,const PadConfig3D & cfg,ThrowOnCancel thr)359 bool add_cavity(Contour3D &pad, ExPolygon &top_poly, const PadConfig3D &cfg,
360 ThrowOnCancel thr)
361 {
362 auto logerr = []{BOOST_LOG_TRIVIAL(error)<<"Could not create pad cavity";};
363
364 double wing_distance = cfg.wing_height / std::tan(cfg.slope);
365 coord_t delta_inner = -scaled(cfg.thickness + wing_distance);
366 coord_t delta_middle = -scaled(cfg.thickness);
367 ExPolygon inner_base = offset_contour_only(top_poly, delta_inner);
368 ExPolygon middle_base = offset_contour_only(top_poly, delta_middle);
369
370 if (inner_base.empty() || middle_base.empty()) { logerr(); return false; }
371
372 ExPolygons pdiff = diff_ex((Polygons)top_poly, (Polygons)middle_base.contour);
373
374 if (pdiff.size() != 1) { logerr(); return false; }
375
376 top_poly = pdiff.front();
377
378 double z_min = -cfg.wing_height, z_max = 0;
379 pad.merge(walls(inner_base.contour, middle_base.contour, z_min, z_max));
380 thr();
381 pad.merge(triangulate_expolygon_3d(inner_base, z_min, NORMALS_UP));
382
383 return true;
384 }
385
create_outer_pad_geometry(const ExPolygons & skeleton,const PadConfig3D & cfg,ThrowOnCancel thr)386 Contour3D create_outer_pad_geometry(const ExPolygons & skeleton,
387 const PadConfig3D &cfg,
388 ThrowOnCancel thr)
389 {
390 Contour3D ret;
391
392 for (const ExPolygon &pad_part : skeleton) {
393 ExPolygon top_poly{pad_part};
394 ExPolygon bottom_poly =
395 offset_contour_only(pad_part, -scaled(cfg.bottom_offset()));
396
397 if (bottom_poly.empty()) continue;
398 thr();
399
400 double z_min = -cfg.height, z_max = 0;
401 ret.merge(walls(top_poly.contour, bottom_poly.contour, z_max, z_min));
402
403 if (cfg.wing_height > 0. && add_cavity(ret, top_poly, cfg, thr))
404 z_max = -cfg.wing_height;
405
406 for (auto &h : bottom_poly.holes)
407 ret.merge(straight_walls(h, z_max, z_min));
408
409 ret.merge(triangulate_expolygon_3d(bottom_poly, z_min, NORMALS_DOWN));
410 ret.merge(triangulate_expolygon_3d(top_poly, NORMALS_UP));
411 }
412
413 return ret;
414 }
415
create_inner_pad_geometry(const ExPolygons & skeleton,const PadConfig3D & cfg,ThrowOnCancel thr)416 Contour3D create_inner_pad_geometry(const ExPolygons & skeleton,
417 const PadConfig3D &cfg,
418 ThrowOnCancel thr)
419 {
420 Contour3D ret;
421
422 double z_max = 0., z_min = -cfg.height;
423 for (const ExPolygon &pad_part : skeleton) {
424 thr();
425 ret.merge(straight_walls(pad_part.contour, z_max, z_min));
426
427 for (auto &h : pad_part.holes)
428 ret.merge(straight_walls(h, z_max, z_min));
429
430 ret.merge(triangulate_expolygon_3d(pad_part, z_min, NORMALS_DOWN));
431 ret.merge(triangulate_expolygon_3d(pad_part, z_max, NORMALS_UP));
432 }
433
434 return ret;
435 }
436
create_pad_geometry(const PadSkeleton & skelet,const PadConfig & cfg,ThrowOnCancel thr)437 Contour3D create_pad_geometry(const PadSkeleton &skelet,
438 const PadConfig & cfg,
439 ThrowOnCancel thr)
440 {
441 #ifndef NDEBUG
442 SVG svg("pad_skeleton.svg");
443 svg.draw(skelet.outer, "green");
444 svg.draw(skelet.inner, "blue");
445 svg.Close();
446 #endif
447
448 PadConfig3D cfg3d(cfg);
449 return create_outer_pad_geometry(skelet.outer, cfg3d, thr)
450 .merge(create_inner_pad_geometry(skelet.inner, cfg3d, thr));
451 }
452
create_pad_geometry(const ExPolygons & supp_bp,const ExPolygons & model_bp,const PadConfig & cfg,ThrowOnCancel thr)453 Contour3D create_pad_geometry(const ExPolygons &supp_bp,
454 const ExPolygons &model_bp,
455 const PadConfig & cfg,
456 ThrowOnCancel thr)
457 {
458 PadSkeleton skelet;
459
460 if (cfg.embed_object.enabled) {
461 if (cfg.embed_object.everywhere)
462 skelet = BrimPadSkeleton(supp_bp, model_bp, cfg, thr);
463 else
464 skelet = AroundPadSkeleton(supp_bp, model_bp, cfg, thr);
465 } else
466 skelet = BelowPadSkeleton(supp_bp, model_bp, cfg, thr);
467
468 return create_pad_geometry(skelet, cfg, thr);
469 }
470
471 } // namespace
472
pad_blueprint(const TriangleMesh & mesh,ExPolygons & output,const std::vector<float> & heights,ThrowOnCancel thrfn)473 void pad_blueprint(const TriangleMesh & mesh,
474 ExPolygons & output,
475 const std::vector<float> &heights,
476 ThrowOnCancel thrfn)
477 {
478 if (mesh.empty()) return;
479 TriangleMeshSlicer slicer(&mesh);
480
481 auto out = reserve_vector<ExPolygons>(heights.size());
482 slicer.slice(heights, SlicingMode::Regular, 0.f, &out, thrfn);
483
484 size_t count = 0;
485 for(auto& o : out) count += o.size();
486
487 // Unification is expensive, a simplify also speeds up the pad generation
488 auto tmp = reserve_vector<ExPolygon>(count);
489 for(ExPolygons& o : out)
490 for(ExPolygon& e : o) {
491 auto&& exss = e.simplify(scaled<double>(0.1));
492 for(ExPolygon& ep : exss) tmp.emplace_back(std::move(ep));
493 }
494
495 ExPolygons utmp = union_ex(tmp);
496
497 for(auto& o : utmp) {
498 auto&& smp = o.simplify(scaled<double>(0.1));
499 output.insert(output.end(), smp.begin(), smp.end());
500 }
501 }
502
pad_blueprint(const TriangleMesh & mesh,ExPolygons & output,float h,float layerh,ThrowOnCancel thrfn)503 void pad_blueprint(const TriangleMesh &mesh,
504 ExPolygons & output,
505 float h,
506 float layerh,
507 ThrowOnCancel thrfn)
508 {
509 float gnd = float(mesh.bounding_box().min(Z));
510
511 std::vector<float> slicegrid = grid(gnd, gnd + h, layerh);
512 pad_blueprint(mesh, output, slicegrid, thrfn);
513 }
514
create_pad(const ExPolygons & sup_blueprint,const ExPolygons & model_blueprint,TriangleMesh & out,const PadConfig & cfg,ThrowOnCancel thr)515 void create_pad(const ExPolygons &sup_blueprint,
516 const ExPolygons &model_blueprint,
517 TriangleMesh & out,
518 const PadConfig & cfg,
519 ThrowOnCancel thr)
520 {
521 Contour3D t = create_pad_geometry(sup_blueprint, model_blueprint, cfg, thr);
522 out.merge(to_triangle_mesh(std::move(t)));
523 }
524
validate() const525 std::string PadConfig::validate() const
526 {
527 static const double constexpr MIN_BRIM_SIZE_MM = .1;
528
529 if (brim_size_mm < MIN_BRIM_SIZE_MM ||
530 bottom_offset() > brim_size_mm + wing_distance() ||
531 get_waffle_offset(*this) <= MIN_BRIM_SIZE_MM)
532 return L("Pad brim size is too small for the current configuration.");
533
534 return "";
535 }
536
537 }} // namespace Slic3r::sla
538