1 #ifndef SLA_SUPPORTPOINTGENERATOR_HPP
2 #define SLA_SUPPORTPOINTGENERATOR_HPP
3 
4 #include <random>
5 
6 #include <libslic3r/SLA/SupportPoint.hpp>
7 #include <libslic3r/SLA/IndexedMesh.hpp>
8 
9 #include <libslic3r/BoundingBox.hpp>
10 #include <libslic3r/ClipperUtils.hpp>
11 #include <libslic3r/Point.hpp>
12 
13 #include <boost/container/small_vector.hpp>
14 
15 // #define SLA_SUPPORTPOINTGEN_DEBUG
16 
17 namespace Slic3r { namespace sla {
18 
19 class SupportPointGenerator {
20 public:
21     struct Config {
22         float density_relative {1.f};
23         float minimal_distance {1.f};
24         float head_diameter {0.4f};
25 
26         // Originally calibrated to 7.7f, reduced density by Tamas to 70% which is 11.1 (7.7 / 0.7) to adjust for new algorithm changes in tm_suppt_gen_improve
support_forceSlic3r::sla::SupportPointGenerator::Config27         inline float support_force() const { return 11.1f / density_relative; } // a force one point can support       (arbitrary force unit)
tear_pressureSlic3r::sla::SupportPointGenerator::Config28         inline float tear_pressure() const { return 1.f; }  // pressure that the display exerts    (the force unit per mm2)
29     };
30 
31     SupportPointGenerator(const IndexedMesh& emesh, const std::vector<ExPolygons>& slices,
32                     const std::vector<float>& heights, const Config& config, std::function<void(void)> throw_on_cancel, std::function<void(int)> statusfn);
33 
34     SupportPointGenerator(const IndexedMesh& emesh, const Config& config, std::function<void(void)> throw_on_cancel, std::function<void(int)> statusfn);
35 
output() const36     const std::vector<SupportPoint>& output() const { return m_output; }
output()37     std::vector<SupportPoint>& output() { return m_output; }
38 
39     struct MyLayer;
40 
41     struct Structure {
StructureSlic3r::sla::SupportPointGenerator::Structure42         Structure(MyLayer &layer, const ExPolygon& poly, const BoundingBox &bbox, const Vec2f &centroid, float area, float h) :
43             layer(&layer), polygon(&poly), bbox(bbox), centroid(centroid), area(area), zlevel(h)
44 #ifdef SLA_SUPPORTPOINTGEN_DEBUG
45             , unique_id(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()))
46 #endif /* SLA_SUPPORTPOINTGEN_DEBUG */
47         {}
48         MyLayer *layer;
49         const ExPolygon* polygon = nullptr;
50         const BoundingBox bbox;
51         const Vec2f centroid = Vec2f::Zero();
52         const float area = 0.f;
53         float zlevel = 0;
54         // How well is this ExPolygon held to the print base?
55         // Positive number, the higher the better.
56         float supports_force_this_layer     = 0.f;
57         float supports_force_inherited      = 0.f;
supports_force_totalSlic3r::sla::SupportPointGenerator::Structure58         float supports_force_total() const { return this->supports_force_this_layer + this->supports_force_inherited; }
59 #ifdef SLA_SUPPORTPOINTGEN_DEBUG
60         std::chrono::milliseconds unique_id;
61 #endif /* SLA_SUPPORTPOINTGEN_DEBUG */
62 
63         struct Link {
LinkSlic3r::sla::SupportPointGenerator::Structure::Link64             Link(Structure *island, float overlap_area) : island(island), overlap_area(overlap_area) {}
65             Structure   *island;
66             float        overlap_area;
67         };
68 
69 #ifdef NDEBUG
70         // In release mode, use the optimized container.
71         boost::container::small_vector<Link, 4> islands_above;
72         boost::container::small_vector<Link, 4> islands_below;
73 #else
74         // In debug mode, use the standard vector, which is well handled by debugger visualizer.
75         std::vector<Link>					 	islands_above;
76         std::vector<Link>						islands_below;
77 #endif
78         // Overhangs, that are dangling considerably.
79         ExPolygons                              dangling_areas;
80         // Complete overhands.
81         ExPolygons                              overhangs;
82         // Overhangs, where the surface must slope.
83         ExPolygons                              overhangs_slopes;
84         float                                   overhangs_area = 0.f;
85 
overlapsSlic3r::sla::SupportPointGenerator::Structure86         bool overlaps(const Structure &rhs) const {
87             return this->bbox.overlap(rhs.bbox) && (this->polygon->overlaps(*rhs.polygon) || rhs.polygon->overlaps(*this->polygon));
88         }
overlap_areaSlic3r::sla::SupportPointGenerator::Structure89         float overlap_area(const Structure &rhs) const {
90             double out = 0.;
91             if (this->bbox.overlap(rhs.bbox)) {
92                 Polygons polys = intersection(to_polygons(*this->polygon), to_polygons(*rhs.polygon), false);
93                 for (const Polygon &poly : polys)
94                     out += poly.area();
95             }
96             return float(out);
97         }
area_belowSlic3r::sla::SupportPointGenerator::Structure98         float area_below() const {
99             float area = 0.f;
100             for (const Link &below : this->islands_below)
101                 area += below.island->area;
102             return area;
103         }
polygons_belowSlic3r::sla::SupportPointGenerator::Structure104         Polygons polygons_below() const {
105             size_t cnt = 0;
106             for (const Link &below : this->islands_below)
107                 cnt += 1 + below.island->polygon->holes.size();
108             Polygons out;
109             out.reserve(cnt);
110             for (const Link &below : this->islands_below) {
111                 out.emplace_back(below.island->polygon->contour);
112                 append(out, below.island->polygon->holes);
113             }
114             return out;
115         }
expolygons_belowSlic3r::sla::SupportPointGenerator::Structure116         ExPolygons expolygons_below() const {
117             ExPolygons out;
118             out.reserve(this->islands_below.size());
119             for (const Link &below : this->islands_below)
120                 out.emplace_back(*below.island->polygon);
121             return out;
122         }
123         // Positive deficit of the supports. If negative, this area is well supported. If positive, more supports need to be added.
support_force_deficitSlic3r::sla::SupportPointGenerator::Structure124         float support_force_deficit(const float tear_pressure) const { return this->area * tear_pressure - this->supports_force_total(); }
125     };
126 
127     struct MyLayer {
MyLayerSlic3r::sla::SupportPointGenerator::MyLayer128         MyLayer(const size_t layer_id, coordf_t print_z) : layer_id(layer_id), print_z(print_z) {}
129         size_t                  layer_id;
130         coordf_t                print_z;
131         std::vector<Structure>  islands;
132     };
133 
134     struct RichSupportPoint {
135         Vec3f        position;
136         Structure   *island;
137     };
138 
139     struct PointGrid3D {
140         struct GridHash {
operator ()Slic3r::sla::SupportPointGenerator::PointGrid3D::GridHash141             std::size_t operator()(const Vec3i &cell_id) const {
142                 return std::hash<int>()(cell_id.x()) ^ std::hash<int>()(cell_id.y() * 593) ^ std::hash<int>()(cell_id.z() * 7919);
143             }
144         };
145         typedef std::unordered_multimap<Vec3i, RichSupportPoint, GridHash> Grid;
146 
147         Vec3f   cell_size;
148         Grid    grid;
149 
cell_idSlic3r::sla::SupportPointGenerator::PointGrid3D150         Vec3i cell_id(const Vec3f &pos) {
151             return Vec3i(int(floor(pos.x() / cell_size.x())),
152                          int(floor(pos.y() / cell_size.y())),
153                          int(floor(pos.z() / cell_size.z())));
154         }
155 
insertSlic3r::sla::SupportPointGenerator::PointGrid3D156         void insert(const Vec2f &pos, Structure *island) {
157             RichSupportPoint pt;
158             pt.position = Vec3f(pos.x(), pos.y(), float(island->layer->print_z));
159             pt.island   = island;
160             grid.emplace(cell_id(pt.position), pt);
161         }
162 
collides_withSlic3r::sla::SupportPointGenerator::PointGrid3D163         bool collides_with(const Vec2f &pos, float print_z, float radius) {
164             Vec3f pos3d(pos.x(), pos.y(), print_z);
165             Vec3i cell = cell_id(pos3d);
166             std::pair<Grid::const_iterator, Grid::const_iterator> it_pair = grid.equal_range(cell);
167             if (collides_with(pos3d, radius, it_pair.first, it_pair.second))
168                 return true;
169             for (int i = -1; i < 2; ++ i)
170                 for (int j = -1; j < 2; ++ j)
171                     for (int k = -1; k < 1; ++ k) {
172                         if (i == 0 && j == 0 && k == 0)
173                             continue;
174                         it_pair = grid.equal_range(cell + Vec3i(i, j, k));
175                         if (collides_with(pos3d, radius, it_pair.first, it_pair.second))
176                             return true;
177                     }
178             return false;
179         }
180 
181     private:
collides_withSlic3r::sla::SupportPointGenerator::PointGrid3D182         bool collides_with(const Vec3f &pos, float radius, Grid::const_iterator it_begin, Grid::const_iterator it_end) {
183             for (Grid::const_iterator it = it_begin; it != it_end; ++ it) {
184                 float dist2 = (it->second.position - pos).squaredNorm();
185                 if (dist2 < radius * radius)
186                     return true;
187             }
188             return false;
189         }
190     };
191 
192     void execute(const std::vector<ExPolygons> &slices,
193                  const std::vector<float> &     heights);
194 
seed(std::mt19937::result_type s)195     void seed(std::mt19937::result_type s) { m_rng.seed(s); }
196 private:
197     std::vector<SupportPoint> m_output;
198 
199     SupportPointGenerator::Config m_config;
200 
201     void process(const std::vector<ExPolygons>& slices, const std::vector<float>& heights);
202 
203 public:
204     enum IslandCoverageFlags : uint8_t { icfNone = 0x0, icfIsNew = 0x1, icfWithBoundary = 0x2 };
205 
206 private:
207 
208     void uniformly_cover(const ExPolygons& islands, Structure& structure, float deficit, PointGrid3D &grid3d, IslandCoverageFlags flags = icfNone);
209 
210     void add_support_points(Structure& structure, PointGrid3D &grid3d);
211 
212     void project_onto_mesh(std::vector<SupportPoint>& points) const;
213 
214 #ifdef SLA_SUPPORTPOINTGEN_DEBUG
215     static void output_expolygons(const ExPolygons& expolys, const std::string &filename);
216     static void output_structures(const std::vector<Structure> &structures);
217 #endif // SLA_SUPPORTPOINTGEN_DEBUG
218 
219     const IndexedMesh& m_emesh;
220     std::function<void(void)> m_throw_on_cancel;
221     std::function<void(int)>  m_statusfn;
222 
223     std::mt19937 m_rng;
224 };
225 
226 void remove_bottom_points(std::vector<SupportPoint> &pts, float lvl);
227 
228 std::vector<Vec2f> sample_expolygon(const ExPolygon &expoly, float samples_per_mm2, std::mt19937 &rng);
229 void sample_expolygon_boundary(const ExPolygon &expoly, float samples_per_mm, std::vector<Vec2f> &out, std::mt19937 &rng);
230 
231 }} // namespace Slic3r::sla
232 
233 #endif // SUPPORTPOINTGENERATOR_HPP
234