1 #ifndef slic3r_EdgeGrid_hpp_ 2 #define slic3r_EdgeGrid_hpp_ 3 4 #include <stdint.h> 5 #include <math.h> 6 7 #include "Point.hpp" 8 #include "BoundingBox.hpp" 9 #include "ExPolygon.hpp" 10 #include "ExPolygonCollection.hpp" 11 12 namespace Slic3r { 13 namespace EdgeGrid { 14 15 class Grid 16 { 17 public: 18 Grid(); 19 ~Grid(); 20 set_bbox(const BoundingBox & bbox)21 void set_bbox(const BoundingBox &bbox) { m_bbox = bbox; } 22 23 void create(const Polygons &polygons, coord_t resolution); 24 void create(const std::vector<const Polygon*> &polygons, coord_t resolution); 25 void create(const std::vector<Points> &polygons, coord_t resolution); 26 void create(const ExPolygon &expoly, coord_t resolution); 27 void create(const ExPolygons &expolygons, coord_t resolution); 28 void create(const ExPolygonCollection &expolygons, coord_t resolution); 29 contours() const30 const std::vector<const Slic3r::Points*>& contours() const { return m_contours; } 31 32 #if 0 33 // Test, whether the edges inside the grid intersect with the polygons provided. 34 bool intersect(const MultiPoint &polyline, bool closed); 35 bool intersect(const Polygon &polygon) { return intersect(static_cast<const MultiPoint&>(polygon), true); } 36 bool intersect(const Polygons &polygons) { for (size_t i = 0; i < polygons.size(); ++ i) if (intersect(polygons[i])) return true; return false; } 37 bool intersect(const ExPolygon &expoly) { if (intersect(expoly.contour)) return true; for (size_t i = 0; i < expoly.holes.size(); ++ i) if (intersect(expoly.holes[i])) return true; return false; } 38 bool intersect(const ExPolygons &expolygons) { for (size_t i = 0; i < expolygons.size(); ++ i) if (intersect(expolygons[i])) return true; return false; } 39 bool intersect(const ExPolygonCollection &expolygons) { return intersect(expolygons.expolygons); } 40 41 // Test, whether a point is inside a contour. 42 bool inside(const Point &pt); 43 #endif 44 45 // Fill in a rough m_signed_distance_field from the edge grid. 46 // The rough SDF is used by signed_distance() for distances outside of the search_radius. 47 void calculate_sdf(); 48 49 // Return an estimate of the signed distance based on m_signed_distance_field grid. 50 float signed_distance_bilinear(const Point &pt) const; 51 52 // Calculate a signed distance to the contours in search_radius from the point. 53 struct ClosestPointResult { 54 size_t contour_idx = size_t(-1); 55 size_t start_point_idx = size_t(-1); 56 // Signed distance to the closest point. 57 double distance = std::numeric_limits<double>::max(); 58 // Parameter of the closest point on edge starting with start_point_idx <0, 1) 59 double t = 0.; 60 validSlic3r::EdgeGrid::Grid::ClosestPointResult61 bool valid() const { return contour_idx != size_t(-1); } 62 }; 63 ClosestPointResult closest_point(const Point &pt, coord_t search_radius) const; 64 65 bool signed_distance_edges(const Point &pt, coord_t search_radius, coordf_t &result_min_dist, bool *pon_segment = nullptr) const; 66 67 // Calculate a signed distance to the contours in search_radius from the point. If no edge is found in search_radius, 68 // return an interpolated value from m_signed_distance_field, if it exists. 69 bool signed_distance(const Point &pt, coord_t search_radius, coordf_t &result_min_dist) const; 70 bbox() const71 const BoundingBox& bbox() const { return m_bbox; } resolution() const72 const coord_t resolution() const { return m_resolution; } rows() const73 const size_t rows() const { return m_rows; } cols() const74 const size_t cols() const { return m_cols; } 75 76 // For supports: Contours enclosing the rasterized edges. 77 Polygons contours_simplified(coord_t offset, bool fill_holes) const; 78 79 typedef std::pair<const Slic3r::Points*, size_t> ContourPoint; 80 typedef std::pair<const Slic3r::Points*, size_t> ContourEdge; 81 std::vector<std::pair<ContourEdge, ContourEdge>> intersecting_edges() const; 82 bool has_intersecting_edges() const; 83 visit_cells_intersecting_line(Slic3r::Point p1,Slic3r::Point p2,VISITOR & visitor) const84 template<typename VISITOR> void visit_cells_intersecting_line(Slic3r::Point p1, Slic3r::Point p2, VISITOR &visitor) const 85 { 86 // End points of the line segment. 87 assert(m_bbox.contains(p1)); 88 assert(m_bbox.contains(p2)); 89 p1 -= m_bbox.min; 90 p2 -= m_bbox.min; 91 assert(p1.x() >= 0 && p1.x() < m_cols * m_resolution); 92 assert(p1.y() >= 0 && p1.y() < m_rows * m_resolution); 93 assert(p2.x() >= 0 && p2.x() < m_cols * m_resolution); 94 assert(p2.y() >= 0 && p2.y() < m_rows * m_resolution); 95 // Get the cells of the end points. 96 coord_t ix = p1(0) / m_resolution; 97 coord_t iy = p1(1) / m_resolution; 98 coord_t ixb = p2(0) / m_resolution; 99 coord_t iyb = p2(1) / m_resolution; 100 assert(ix >= 0 && size_t(ix) < m_cols); 101 assert(iy >= 0 && size_t(iy) < m_rows); 102 assert(ixb >= 0 && size_t(ixb) < m_cols); 103 assert(iyb >= 0 && size_t(iyb) < m_rows); 104 // Account for the end points. 105 if (! visitor(iy, ix) || (ix == ixb && iy == iyb)) 106 // Both ends fall into the same cell. 107 return; 108 // Raster the centeral part of the line. 109 coord_t dx = std::abs(p2(0) - p1(0)); 110 coord_t dy = std::abs(p2(1) - p1(1)); 111 if (p1(0) < p2(0)) { 112 int64_t ex = int64_t((ix + 1)*m_resolution - p1(0)) * int64_t(dy); 113 if (p1(1) < p2(1)) { 114 // x positive, y positive 115 int64_t ey = int64_t((iy + 1)*m_resolution - p1(1)) * int64_t(dx); 116 do { 117 assert(ix <= ixb && iy <= iyb); 118 if (ex < ey) { 119 ey -= ex; 120 ex = int64_t(dy) * m_resolution; 121 ix += 1; 122 assert(ix <= ixb); 123 } 124 else if (ex == ey) { 125 ex = int64_t(dy) * m_resolution; 126 ey = int64_t(dx) * m_resolution; 127 ix += 1; 128 iy += 1; 129 assert(ix <= ixb); 130 assert(iy <= iyb); 131 } 132 else { 133 assert(ex > ey); 134 ex -= ey; 135 ey = int64_t(dx) * m_resolution; 136 iy += 1; 137 assert(iy <= iyb); 138 } 139 if (! visitor(iy, ix)) 140 return; 141 } while (ix != ixb || iy != iyb); 142 } 143 else { 144 // x positive, y non positive 145 int64_t ey = int64_t(p1(1) - iy*m_resolution) * int64_t(dx); 146 do { 147 assert(ix <= ixb && iy >= iyb); 148 if (ex <= ey) { 149 ey -= ex; 150 ex = int64_t(dy) * m_resolution; 151 ix += 1; 152 assert(ix <= ixb); 153 } 154 else { 155 ex -= ey; 156 ey = int64_t(dx) * m_resolution; 157 iy -= 1; 158 assert(iy >= iyb); 159 } 160 if (! visitor(iy, ix)) 161 return; 162 } while (ix != ixb || iy != iyb); 163 } 164 } 165 else { 166 int64_t ex = int64_t(p1(0) - ix*m_resolution) * int64_t(dy); 167 if (p1(1) < p2(1)) { 168 // x non positive, y positive 169 int64_t ey = int64_t((iy + 1)*m_resolution - p1(1)) * int64_t(dx); 170 do { 171 assert(ix >= ixb && iy <= iyb); 172 if (ex < ey) { 173 ey -= ex; 174 ex = int64_t(dy) * m_resolution; 175 ix -= 1; 176 assert(ix >= ixb); 177 } 178 else { 179 assert(ex >= ey); 180 ex -= ey; 181 ey = int64_t(dx) * m_resolution; 182 iy += 1; 183 assert(iy <= iyb); 184 } 185 if (! visitor(iy, ix)) 186 return; 187 } while (ix != ixb || iy != iyb); 188 } 189 else { 190 // x non positive, y non positive 191 int64_t ey = int64_t(p1(1) - iy*m_resolution) * int64_t(dx); 192 do { 193 assert(ix >= ixb && iy >= iyb); 194 if (ex < ey) { 195 ey -= ex; 196 ex = int64_t(dy) * m_resolution; 197 ix -= 1; 198 assert(ix >= ixb); 199 } 200 else if (ex == ey) { 201 // The lower edge of a grid cell belongs to the cell. 202 // Handle the case where the ray may cross the lower left corner of a cell in a general case, 203 // or a left or lower edge in a degenerate case (horizontal or vertical line). 204 if (dx > 0) { 205 ex = int64_t(dy) * m_resolution; 206 ix -= 1; 207 assert(ix >= ixb); 208 } 209 if (dy > 0) { 210 ey = int64_t(dx) * m_resolution; 211 iy -= 1; 212 assert(iy >= iyb); 213 } 214 } 215 else { 216 assert(ex > ey); 217 ex -= ey; 218 ey = int64_t(dx) * m_resolution; 219 iy -= 1; 220 assert(iy >= iyb); 221 } 222 if (! visitor(iy, ix)) 223 return; 224 } while (ix != ixb || iy != iyb); 225 } 226 } 227 } 228 visit_cells_intersecting_box(BoundingBox bbox,VISITOR & visitor) const229 template<typename VISITOR> void visit_cells_intersecting_box(BoundingBox bbox, VISITOR &visitor) const 230 { 231 // End points of the line segment. 232 bbox.min -= m_bbox.min; 233 bbox.max -= m_bbox.min + Point(1, 1); 234 // Get the cells of the end points. 235 bbox.min /= m_resolution; 236 bbox.max /= m_resolution; 237 // Trim with the cells. 238 bbox.min.x() = std::max<coord_t>(bbox.min.x(), 0); 239 bbox.min.y() = std::max<coord_t>(bbox.min.y(), 0); 240 bbox.max.x() = std::min<coord_t>(bbox.max.x(), (coord_t)m_cols - 1); 241 bbox.max.y() = std::min<coord_t>(bbox.max.y(), (coord_t)m_rows - 1); 242 for (coord_t iy = bbox.min.y(); iy <= bbox.max.y(); ++ iy) 243 for (coord_t ix = bbox.min.x(); ix <= bbox.max.x(); ++ ix) 244 if (! visitor(iy, ix)) 245 return; 246 } 247 cell_data_range(coord_t row,coord_t col) const248 std::pair<std::vector<std::pair<size_t, size_t>>::const_iterator, std::vector<std::pair<size_t, size_t>>::const_iterator> cell_data_range(coord_t row, coord_t col) const 249 { 250 assert(row >= 0); 251 assert(row < m_rows); 252 assert(col >= 0); 253 assert(col < m_cols); 254 const EdgeGrid::Grid::Cell &cell = m_cells[row * m_cols + col]; 255 return std::make_pair(m_cell_data.begin() + cell.begin, m_cell_data.begin() + cell.end); 256 } 257 segment(const std::pair<size_t,size_t> & contour_and_segment_idx) const258 std::pair<const Slic3r::Point&, const Slic3r::Point&> segment(const std::pair<size_t, size_t> &contour_and_segment_idx) const 259 { 260 const Slic3r::Points &ipts = *m_contours[contour_and_segment_idx.first]; 261 size_t ipt = contour_and_segment_idx.second; 262 return std::pair<const Slic3r::Point&, const Slic3r::Point&>(ipts[ipt], ipts[ipt + 1 == ipts.size() ? 0 : ipt + 1]); 263 } 264 line(const std::pair<size_t,size_t> & contour_and_segment_idx) const265 Line line(const std::pair<size_t, size_t> &contour_and_segment_idx) const 266 { 267 const Slic3r::Points &ipts = *m_contours[contour_and_segment_idx.first]; 268 size_t ipt = contour_and_segment_idx.second; 269 return Line(ipts[ipt], ipts[ipt + 1 == ipts.size() ? 0 : ipt + 1]); 270 } 271 272 protected: 273 struct Cell { CellSlic3r::EdgeGrid::Grid::Cell274 Cell() : begin(0), end(0) {} 275 size_t begin; 276 size_t end; 277 }; 278 279 void create_from_m_contours(coord_t resolution); 280 #if 0 281 bool line_cell_intersect(const Point &p1, const Point &p2, const Cell &cell); 282 #endif cell_inside_or_crossing(int r,int c) const283 bool cell_inside_or_crossing(int r, int c) const 284 { 285 if (r < 0 || (size_t)r >= m_rows || 286 c < 0 || (size_t)c >= m_cols) 287 // The cell is outside the domain. Hoping that the contours were correctly oriented, so 288 // there is a CCW outmost contour so the out of domain cells are outside. 289 return false; 290 const Cell &cell = m_cells[r * m_cols + c]; 291 return 292 (cell.begin < cell.end) || 293 (! m_signed_distance_field.empty() && m_signed_distance_field[r * (m_cols + 1) + c] <= 0.f); 294 } 295 296 // Bounding box around the contours. 297 BoundingBox m_bbox; 298 // Grid dimensions. 299 coord_t m_resolution; 300 size_t m_rows; 301 size_t m_cols; 302 303 // Referencing the source contours. 304 // This format allows one to work with any Slic3r fixed point contour format 305 // (Polygon, ExPolygon, ExPolygonCollection etc). 306 std::vector<const Slic3r::Points*> m_contours; 307 308 // Referencing a contour and a line segment of m_contours. 309 std::vector<std::pair<size_t, size_t> > m_cell_data; 310 311 // Full grid of cells. 312 std::vector<Cell> m_cells; 313 314 // Distance field derived from the edge grid, seed filled by the Danielsson chamfer metric. 315 // May be empty. 316 std::vector<float> m_signed_distance_field; 317 }; 318 319 // Debugging utility. Save the signed distance field. 320 extern void save_png(const Grid &grid, const BoundingBox &bbox, coord_t resolution, const char *path, size_t scale = 1); 321 322 } // namespace EdgeGrid 323 324 // Find all pairs of intersectiong edges from the set of polygons. 325 extern std::vector<std::pair<EdgeGrid::Grid::ContourEdge, EdgeGrid::Grid::ContourEdge>> intersecting_edges(const Polygons &polygons); 326 327 // Find all pairs of intersectiong edges from the set of polygons, highlight them in an SVG. 328 extern void export_intersections_to_svg(const std::string &filename, const Polygons &polygons); 329 330 } // namespace Slic3r 331 332 #endif /* slic3r_EdgeGrid_hpp_ */ 333