1 #ifndef SLASUPPORTTREEALGORITHM_H
2 #define SLASUPPORTTREEALGORITHM_H
3
4 #include <cstdint>
5
6 #include <libslic3r/SLA/SupportTreeBuilder.hpp>
7 #include <libslic3r/SLA/Clustering.hpp>
8 #include <libslic3r/SLA/SpatIndex.hpp>
9
10 namespace Slic3r {
11 namespace sla {
12
13 // The minimum distance for two support points to remain valid.
14 const double /*constexpr*/ D_SP = 0.1;
15
16 enum { // For indexing Eigen vectors as v(X), v(Y), v(Z) instead of numbers
17 X, Y, Z
18 };
19
to_vec2(const Vec3d & v3)20 inline Vec2d to_vec2(const Vec3d &v3) { return {v3(X), v3(Y)}; }
21
dir_to_spheric(const Vec3d & n,double norm=1.)22 inline std::pair<double, double> dir_to_spheric(const Vec3d &n, double norm = 1.)
23 {
24 double z = n.z();
25 double r = norm;
26 double polar = std::acos(z / r);
27 double azimuth = std::atan2(n(1), n(0));
28 return {polar, azimuth};
29 }
30
spheric_to_dir(double polar,double azimuth)31 inline Vec3d spheric_to_dir(double polar, double azimuth)
32 {
33 return {std::cos(azimuth) * std::sin(polar),
34 std::sin(azimuth) * std::sin(polar), std::cos(polar)};
35 }
36
spheric_to_dir(const std::tuple<double,double> & v)37 inline Vec3d spheric_to_dir(const std::tuple<double, double> &v)
38 {
39 auto [plr, azm] = v;
40 return spheric_to_dir(plr, azm);
41 }
42
spheric_to_dir(const std::pair<double,double> & v)43 inline Vec3d spheric_to_dir(const std::pair<double, double> &v)
44 {
45 return spheric_to_dir(v.first, v.second);
46 }
47
spheric_to_dir(const std::array<double,2> & v)48 inline Vec3d spheric_to_dir(const std::array<double, 2> &v)
49 {
50 return spheric_to_dir(v[0], v[1]);
51 }
52
53 // Give points on a 3D ring with given center, radius and orientation
54 // method based on:
55 // https://math.stackexchange.com/questions/73237/parametric-equation-of-a-circle-in-3d-space
56 template<size_t N>
57 class PointRing {
58 std::array<double, N> m_phis;
59
60 // Two vectors that will be perpendicular to each other and to the
61 // axis. Values for a(X) and a(Y) are now arbitrary, a(Z) is just a
62 // placeholder.
63 // a and b vectors are perpendicular to the ring direction and to each other.
64 // Together they define the plane where we have to iterate with the
65 // given angles in the 'm_phis' vector
66 Vec3d a = {0, 1, 0}, b;
67 double m_radius = 0.;
68
is_one(double val)69 static inline bool constexpr is_one(double val)
70 {
71 return std::abs(std::abs(val) - 1) < 1e-20;
72 }
73
74 public:
75
PointRing(const Vec3d & n)76 PointRing(const Vec3d &n)
77 {
78 m_phis = linspace_array<N>(0., 2 * PI);
79
80 // We have to address the case when the direction vector v (same as
81 // dir) is coincident with one of the world axes. In this case two of
82 // its components will be completely zero and one is 1.0. Our method
83 // becomes dangerous here due to division with zero. Instead, vector
84 // 'a' can be an element-wise rotated version of 'v'
85 if(is_one(n(X)) || is_one(n(Y)) || is_one(n(Z))) {
86 a = {n(Z), n(X), n(Y)};
87 b = {n(Y), n(Z), n(X)};
88 }
89 else {
90 a(Z) = -(n(Y)*a(Y)) / n(Z); a.normalize();
91 b = a.cross(n);
92 }
93 }
94
get(size_t idx,const Vec3d src,double r) const95 Vec3d get(size_t idx, const Vec3d src, double r) const
96 {
97 double phi = m_phis[idx];
98 double sinphi = std::sin(phi);
99 double cosphi = std::cos(phi);
100
101 double rpscos = r * cosphi;
102 double rpssin = r * sinphi;
103
104 // Point on the sphere
105 return {src(X) + rpscos * a(X) + rpssin * b(X),
106 src(Y) + rpscos * a(Y) + rpssin * b(Y),
107 src(Z) + rpscos * a(Z) + rpssin * b(Z)};
108 }
109 };
110
111 //IndexedMesh::hit_result query_hit(const SupportableMesh &msh, const Bridge &br, double safety_d = std::nan(""));
112 //IndexedMesh::hit_result query_hit(const SupportableMesh &msh, const Head &br, double safety_d = std::nan(""));
113
dirv(const Vec3d & startp,const Vec3d & endp)114 inline Vec3d dirv(const Vec3d& startp, const Vec3d& endp) {
115 return (endp - startp).normalized();
116 }
117
118 class PillarIndex {
119 PointIndex m_index;
120 using Mutex = ccr::BlockingMutex;
121 mutable Mutex m_mutex;
122
123 public:
124
guarded_insert(Args &&...args)125 template<class...Args> inline void guarded_insert(Args&&...args)
126 {
127 std::lock_guard<Mutex> lck(m_mutex);
128 m_index.insert(std::forward<Args>(args)...);
129 }
130
131 template<class...Args>
guarded_query(Args &&...args) const132 inline std::vector<PointIndexEl> guarded_query(Args&&...args) const
133 {
134 std::lock_guard<Mutex> lck(m_mutex);
135 return m_index.query(std::forward<Args>(args)...);
136 }
137
insert(Args &&...args)138 template<class...Args> inline void insert(Args&&...args)
139 {
140 m_index.insert(std::forward<Args>(args)...);
141 }
142
143 template<class...Args>
query(Args &&...args) const144 inline std::vector<PointIndexEl> query(Args&&...args) const
145 {
146 return m_index.query(std::forward<Args>(args)...);
147 }
148
foreach(Fn fn)149 template<class Fn> inline void foreach(Fn fn) { m_index.foreach(fn); }
guarded_foreach(Fn fn)150 template<class Fn> inline void guarded_foreach(Fn fn)
151 {
152 std::lock_guard<Mutex> lck(m_mutex);
153 m_index.foreach(fn);
154 }
155
guarded_clone()156 PointIndex guarded_clone()
157 {
158 std::lock_guard<Mutex> lck(m_mutex);
159 return m_index;
160 }
161 };
162
163 // Helper function for pillar interconnection where pairs of already connected
164 // pillars should be checked for not to be processed again. This can be done
165 // in constant time with a set of hash values uniquely representing a pair of
166 // integers. The order of numbers within the pair should not matter, it has
167 // the same unique hash. The hash value has to have twice as many bits as the
168 // arguments need. If the same integral type is used for args and return val,
169 // make sure the arguments use only the half of the type's bit depth.
170 template<class I, class DoubleI = IntegerOnly<I>>
pairhash(I a,I b)171 IntegerOnly<DoubleI> pairhash(I a, I b)
172 {
173 using std::ceil; using std::log2; using std::max; using std::min;
174 static const auto constexpr Ibits = int(sizeof(I) * CHAR_BIT);
175 static const auto constexpr DoubleIbits = int(sizeof(DoubleI) * CHAR_BIT);
176 static const auto constexpr shift = DoubleIbits / 2 < Ibits ? Ibits / 2 : Ibits;
177
178 I g = min(a, b), l = max(a, b);
179
180 // Assume the hash will fit into the output variable
181 assert((g ? (ceil(log2(g))) : 0) <= shift);
182 assert((l ? (ceil(log2(l))) : 0) <= shift);
183
184 return (DoubleI(g) << shift) + l;
185 }
186
187 class SupportTreeBuildsteps {
188 const SupportTreeConfig& m_cfg;
189 const IndexedMesh& m_mesh;
190 const std::vector<SupportPoint>& m_support_pts;
191
192 using PtIndices = std::vector<unsigned>;
193
194 PtIndices m_iheads; // support points with pinhead
195 PtIndices m_iheads_onmodel;
196 PtIndices m_iheadless; // headless support points
197
198 std::map<unsigned, IndexedMesh::hit_result> m_head_to_ground_scans;
199
200 // normals for support points from model faces.
201 PointSet m_support_nmls;
202
203 // Clusters of points which can reach the ground directly and can be
204 // bridged to one central pillar
205 std::vector<PtIndices> m_pillar_clusters;
206
207 // This algorithm uses the SupportTreeBuilder class to fill gradually
208 // the support elements (heads, pillars, bridges, ...)
209 SupportTreeBuilder& m_builder;
210
211 // support points in Eigen/IGL format
212 PointSet m_points;
213
214 // throw if canceled: It will be called many times so a shorthand will
215 // come in handy.
216 ThrowOnCancel m_thr;
217
218 // A spatial index to easily find strong pillars to connect to.
219 PillarIndex m_pillar_index;
220
221 // When bridging heads to pillars... TODO: find a cleaner solution
222 ccr::BlockingMutex m_bridge_mutex;
223
ray_mesh_intersect(const Vec3d & s,const Vec3d & dir)224 inline IndexedMesh::hit_result ray_mesh_intersect(const Vec3d& s,
225 const Vec3d& dir)
226 {
227 return m_mesh.query_ray_hit(s, dir);
228 }
229
230 // This function will test if a future pinhead would not collide with the
231 // model geometry. It does not take a 'Head' object because those are
232 // created after this test. Parameters: s: The touching point on the model
233 // surface. dir: This is the direction of the head from the pin to the back
234 // r_pin, r_back: the radiuses of the pin and the back sphere width: This
235 // is the full width from the pin center to the back center m: The object
236 // mesh.
237 // The return value is the hit result from the ray casting. If the starting
238 // point was inside the model, an "invalid" hit_result will be returned
239 // with a zero distance value instead of a NAN. This way the result can
240 // be used safely for comparison with other distances.
241 IndexedMesh::hit_result pinhead_mesh_intersect(
242 const Vec3d& s,
243 const Vec3d& dir,
244 double r_pin,
245 double r_back,
246 double width,
247 double safety_d);
248
pinhead_mesh_intersect(const Vec3d & s,const Vec3d & dir,double r_pin,double r_back,double width)249 IndexedMesh::hit_result pinhead_mesh_intersect(
250 const Vec3d& s,
251 const Vec3d& dir,
252 double r_pin,
253 double r_back,
254 double width)
255 {
256 return pinhead_mesh_intersect(s, dir, r_pin, r_back, width,
257 r_back * m_cfg.safety_distance_mm /
258 m_cfg.head_back_radius_mm);
259 }
260
261 // Checking bridge (pillar and stick as well) intersection with the model.
262 // If the function is used for headless sticks, the ins_check parameter
263 // have to be true as the beginning of the stick might be inside the model
264 // geometry.
265 // The return value is the hit result from the ray casting. If the starting
266 // point was inside the model, an "invalid" hit_result will be returned
267 // with a zero distance value instead of a NAN. This way the result can
268 // be used safely for comparison with other distances.
269 IndexedMesh::hit_result bridge_mesh_intersect(
270 const Vec3d& s,
271 const Vec3d& dir,
272 double r,
273 double safety_d);
274
bridge_mesh_intersect(const Vec3d & s,const Vec3d & dir,double r)275 IndexedMesh::hit_result bridge_mesh_intersect(
276 const Vec3d& s,
277 const Vec3d& dir,
278 double r)
279 {
280 return bridge_mesh_intersect(s, dir, r,
281 r * m_cfg.safety_distance_mm /
282 m_cfg.head_back_radius_mm);
283 }
284
285 template<class...Args>
bridge_mesh_distance(Args &&...args)286 inline double bridge_mesh_distance(Args&&...args) {
287 return bridge_mesh_intersect(std::forward<Args>(args)...).distance();
288 }
289
290 // Helper function for interconnecting two pillars with zig-zag bridges.
291 bool interconnect(const Pillar& pillar, const Pillar& nextpillar);
292
293 // For connecting a head to a nearby pillar.
294 bool connect_to_nearpillar(const Head& head, long nearpillar_id);
295
296 // Find route for a head to the ground. Inserts additional bridge from the
297 // head to the pillar if cannot create pillar directly.
298 // The optional dir parameter is the direction of the bridge which is the
299 // direction of the pinhead if omitted.
300 bool connect_to_ground(Head& head, const Vec3d &dir);
301 inline bool connect_to_ground(Head& head);
302
303 bool connect_to_model_body(Head &head);
304
305 bool search_pillar_and_connect(const Head& source);
306
307 // This is a proxy function for pillar creation which will mind the gap
308 // between the pad and the model bottom in zero elevation mode.
309 // jp is the starting junction point which needs to be routed down.
310 // sourcedir is the allowed direction of an optional bridge between the
311 // jp junction and the final pillar.
312 bool create_ground_pillar(const Vec3d &jp,
313 const Vec3d &sourcedir,
314 double radius,
315 long head_id = SupportTreeNode::ID_UNSET);
316
add_pillar_base(long pid)317 void add_pillar_base(long pid)
318 {
319 m_builder.add_pillar_base(pid, m_cfg.base_height_mm, m_cfg.base_radius_mm);
320 }
321
322 std::optional<DiffBridge> search_widening_path(const Vec3d &jp,
323 const Vec3d &dir,
324 double radius,
325 double new_radius);
326
327 public:
328 SupportTreeBuildsteps(SupportTreeBuilder & builder, const SupportableMesh &sm);
329
330 // Now let's define the individual steps of the support generation algorithm
331
332 // Filtering step: here we will discard inappropriate support points
333 // and decide the future of the appropriate ones. We will check if a
334 // pinhead is applicable and adjust its angle at each support point. We
335 // will also merge the support points that are just too close and can
336 // be considered as one.
337 void filter();
338
339 // Pinhead creation: based on the filtering results, the Head objects
340 // will be constructed (together with their triangle meshes).
341 void add_pinheads();
342
343 // Further classification of the support points with pinheads. If the
344 // ground is directly reachable through a vertical line parallel to the
345 // Z axis we consider a support point as pillar candidate. If touches
346 // the model geometry, it will be marked as non-ground facing and
347 // further steps will process it. Also, the pillars will be grouped
348 // into clusters that can be interconnected with bridges. Elements of
349 // these groups may or may not be interconnected. Here we only run the
350 // clustering algorithm.
351 void classify();
352
353 // Step: Routing the ground connected pinheads, and interconnecting
354 // them with additional (angled) bridges. Not all of these pinheads
355 // will be a full pillar (ground connected). Some will connect to a
356 // nearby pillar using a bridge. The max number of such side-heads for
357 // a central pillar is limited to avoid bad weight distribution.
358 void routing_to_ground();
359
360 // Step: routing the pinheads that would connect to the model surface
361 // along the Z axis downwards. For now these will actually be connected with
362 // the model surface with a flipped pinhead. In the future here we could use
363 // some smart algorithms to search for a safe path to the ground or to a
364 // nearby pillar that can hold the supported weight.
365 void routing_to_model();
366
367 void interconnect_pillars();
368
merge_result()369 inline void merge_result() { m_builder.merged_mesh(); }
370
371 static bool execute(SupportTreeBuilder & builder, const SupportableMesh &sm);
372 };
373
374 }
375 }
376
377 #endif // SLASUPPORTTREEALGORITHM_H
378