1 #include <libslic3r/SLA/ConcaveHull.hpp>
2 #include <libslic3r/SLA/SpatIndex.hpp>
3
4 #include <libslic3r/MTUtils.hpp>
5 #include <libslic3r/ClipperUtils.hpp>
6
7 #include <boost/log/trivial.hpp>
8
9 namespace Slic3r {
10 namespace sla {
11
to_vec3(const Vec2crd & v2)12 inline Vec3d to_vec3(const Vec2crd &v2) { return {double(v2(X)), double(v2(Y)), 0.}; }
to_vec3(const Vec2d & v2)13 inline Vec3d to_vec3(const Vec2d &v2) { return {v2(X), v2(Y), 0.}; }
to_vec2(const Vec3d & v3)14 inline Vec2crd to_vec2(const Vec3d &v3) { return {coord_t(v3(X)), coord_t(v3(Y))}; }
15
centroid(const Points & pp)16 Point ConcaveHull::centroid(const Points &pp)
17 {
18 Point c;
19 switch(pp.size()) {
20 case 0: break;
21 case 1: c = pp.front(); break;
22 case 2: c = (pp[0] + pp[1]) / 2; break;
23 default: {
24 auto MAX = std::numeric_limits<Point::coord_type>::max();
25 auto MIN = std::numeric_limits<Point::coord_type>::min();
26 Point min = {MAX, MAX}, max = {MIN, MIN};
27
28 for(auto& p : pp) {
29 if(p(0) < min(0)) min(0) = p(0);
30 if(p(1) < min(1)) min(1) = p(1);
31 if(p(0) > max(0)) max(0) = p(0);
32 if(p(1) > max(1)) max(1) = p(1);
33 }
34 c(0) = min(0) + (max(0) - min(0)) / 2;
35 c(1) = min(1) + (max(1) - min(1)) / 2;
36 break;
37 }
38 }
39
40 return c;
41 }
42
43 // As it shows, the current offset_ex in ClipperUtils hangs if used in jtRound
44 // mode
fast_offset(const ClipperLib::Paths & paths,coord_t delta,ClipperLib::JoinType jointype)45 static ClipperLib::Paths fast_offset(const ClipperLib::Paths &paths,
46 coord_t delta,
47 ClipperLib::JoinType jointype)
48 {
49 using ClipperLib::ClipperOffset;
50 using ClipperLib::etClosedPolygon;
51 using ClipperLib::Paths;
52 using ClipperLib::Path;
53
54 ClipperOffset offs;
55 offs.ArcTolerance = scaled<double>(0.01);
56
57 for (auto &p : paths)
58 // If the input is not at least a triangle, we can not do this algorithm
59 if(p.size() < 3) {
60 BOOST_LOG_TRIVIAL(error) << "Invalid geometry for offsetting!";
61 return {};
62 }
63
64 offs.AddPaths(paths, jointype, etClosedPolygon);
65
66 Paths result;
67 offs.Execute(result, static_cast<double>(delta));
68
69 return result;
70 }
71
calculate_centroids() const72 Points ConcaveHull::calculate_centroids() const
73 {
74 // We get the centroids of all the islands in the 2D slice
75 Points centroids = reserve_vector<Point>(m_polys.size());
76 std::transform(m_polys.begin(), m_polys.end(),
77 std::back_inserter(centroids),
78 [](const Polygon &poly) { return centroid(poly); });
79
80 return centroids;
81 }
82
merge_polygons()83 void ConcaveHull::merge_polygons() { m_polys = get_contours(union_ex(m_polys)); }
84
add_connector_rectangles(const Points & centroids,coord_t max_dist,ThrowOnCancel thr)85 void ConcaveHull::add_connector_rectangles(const Points ¢roids,
86 coord_t max_dist,
87 ThrowOnCancel thr)
88 {
89 // Centroid of the centroids of islands. This is where the additional
90 // connector sticks are routed.
91 Point cc = centroid(centroids);
92
93 PointIndex ctrindex;
94 unsigned idx = 0;
95 for(const Point &ct : centroids) ctrindex.insert(to_vec3(ct), idx++);
96
97 m_polys.reserve(m_polys.size() + centroids.size());
98
99 idx = 0;
100 for (const Point &c : centroids) {
101 thr();
102
103 double dx = c.x() - cc.x(), dy = c.y() - cc.y();
104 double l = std::sqrt(dx * dx + dy * dy);
105 double nx = dx / l, ny = dy / l;
106
107 const Point &ct = centroids[idx];
108
109 std::vector<PointIndexEl> result = ctrindex.nearest(to_vec3(ct), 2);
110
111 double dist = max_dist;
112 for (const PointIndexEl &el : result)
113 if (el.second != idx) {
114 dist = Line(to_vec2(el.first), ct).length();
115 break;
116 }
117
118 idx++;
119
120 if (dist >= max_dist) return;
121
122 Polygon r;
123 r.points.reserve(3);
124 r.points.emplace_back(cc);
125
126 Point n(scaled(nx), scaled(ny));
127 r.points.emplace_back(c + Point(n.y(), -n.x()));
128 r.points.emplace_back(c + Point(-n.y(), n.x()));
129 offset(r, scaled<float>(1.));
130
131 m_polys.emplace_back(r);
132 }
133 }
134
ConcaveHull(const Polygons & polys,double mergedist,ThrowOnCancel thr)135 ConcaveHull::ConcaveHull(const Polygons &polys, double mergedist, ThrowOnCancel thr)
136 {
137 if(polys.empty()) return;
138
139 m_polys = polys;
140 merge_polygons();
141
142 if(m_polys.size() == 1) return;
143
144 Points centroids = calculate_centroids();
145
146 add_connector_rectangles(centroids, scaled(mergedist), thr);
147
148 merge_polygons();
149 }
150
to_expolygons() const151 ExPolygons ConcaveHull::to_expolygons() const
152 {
153 auto ret = reserve_vector<ExPolygon>(m_polys.size());
154 for (const Polygon &p : m_polys) ret.emplace_back(ExPolygon(p));
155 return ret;
156 }
157
offset_waffle_style_ex(const ConcaveHull & hull,coord_t delta)158 ExPolygons offset_waffle_style_ex(const ConcaveHull &hull, coord_t delta)
159 {
160 ClipperLib::Paths paths = Slic3rMultiPoints_to_ClipperPaths(hull.polygons());
161 paths = fast_offset(paths, 2 * delta, ClipperLib::jtRound);
162 paths = fast_offset(paths, -delta, ClipperLib::jtRound);
163 ExPolygons ret = ClipperPaths_to_Slic3rExPolygons(paths);
164 for (ExPolygon &p : ret) p.holes = {};
165 return ret;
166 }
167
offset_waffle_style(const ConcaveHull & hull,coord_t delta)168 Polygons offset_waffle_style(const ConcaveHull &hull, coord_t delta)
169 {
170 return to_polygons(offset_waffle_style_ex(hull, delta));
171 }
172
173 }} // namespace Slic3r::sla
174