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 ¢roid, 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