diff options
author | bubnikv <bubnikv@gmail.com> | 2016-11-29 21:28:33 +0300 |
---|---|---|
committer | bubnikv <bubnikv@gmail.com> | 2016-11-29 21:28:33 +0300 |
commit | 5c23ee504c82b2c4c2f97cb98c42e257311589cb (patch) | |
tree | a059989b32148a2d66bfa6d009294f16c2f5b807 /xs/src/libslic3r/EdgeGrid.cpp | |
parent | ca5ad58ad2acbc9d9011b76775c0293f3486012c (diff) |
EdgeGrid::contours_simplified for supports
Diffstat (limited to 'xs/src/libslic3r/EdgeGrid.cpp')
-rw-r--r-- | xs/src/libslic3r/EdgeGrid.cpp | 112 |
1 files changed, 110 insertions, 2 deletions
diff --git a/xs/src/libslic3r/EdgeGrid.cpp b/xs/src/libslic3r/EdgeGrid.cpp index 67c438f8e..4d1432722 100644 --- a/xs/src/libslic3r/EdgeGrid.cpp +++ b/xs/src/libslic3r/EdgeGrid.cpp @@ -1,6 +1,7 @@ #include <algorithm> #include <vector> #include <float.h> +#include <unordered_map> #ifdef SLIC3R_GUI #include <wx/image.h> @@ -109,7 +110,6 @@ void EdgeGrid::Grid::create(const ExPolygonCollection &expolygons, coord_t resol void EdgeGrid::Grid::create_from_m_contours(coord_t resolution) { // 1) Measure the bounding box. - m_bbox.defined = false; for (size_t i = 0; i < m_contours.size(); ++ i) { const Slic3r::Points &pts = *m_contours[i]; for (size_t j = 0; j < pts.size(); ++ j) @@ -1118,7 +1118,7 @@ float EdgeGrid::Grid::signed_distance_bilinear(const Point &pt) const return f; } - + bool EdgeGrid::Grid::signed_distance_edges(const Point &pt, coord_t search_radius, coordf_t &result_min_dist, bool *pon_segment) const { BoundingBox bbox; bbox.min = bbox.max = Point(pt.x - m_bbox.min.x, pt.y - m_bbox.min.y); @@ -1222,6 +1222,114 @@ bool EdgeGrid::Grid::signed_distance(const Point &pt, coord_t search_radius, coo return true; } +Polygons EdgeGrid::Grid::contours_simplified() const +{ + typedef std::unordered_multimap<Point, int, PointHash> EndPointMapType; + // 1) Collect the lines. + std::vector<Line> lines; + EndPointMapType start_point_to_line_idx; + for (int r = 0; r <= int(m_rows); ++ r) { + for (int c = 0; c <= int(m_cols); ++ c) { + bool left = cell_inside_or_crossing(r , c-1); + bool top = cell_inside_or_crossing(r-1, c ); + bool current = cell_inside_or_crossing(r , c ); + if (left != current) { + lines.push_back( + left ? + Line(Point(c, r+1), Point(c, r )) : + Line(Point(c, r ), Point(c, r+1))); + start_point_to_line_idx.insert(std::pair<Point, int>(lines.back().a, int(lines.size()) - 1)); + } + if (top != current) { + lines.push_back( + top ? + Line(Point(c , r), Point(c+1, r)) : + Line(Point(c+1, r), Point(c , r))); + start_point_to_line_idx.insert(std::pair<Point, int>(lines.back().a, int(lines.size()) - 1)); + } + } + } + + // 2) Chain the lines. + std::vector<char> line_processed(lines.size(), false); + Polygons out; + for (int i_candidate = 0; i_candidate < int(lines.size()); ++ i_candidate) { + if (line_processed[i_candidate]) + continue; + Polygon poly; + line_processed[i_candidate] = true; + poly.points.push_back(lines[i_candidate].b); + int i_line_current = i_candidate; + for (;;) { + std::pair<EndPointMapType::iterator,EndPointMapType::iterator> line_range = + start_point_to_line_idx.equal_range(lines[i_line_current].b); + // The interval has to be non empty, there shall be at least one line continuing the current one. + assert(line_range.first != line_range.second); + int i_next = -1; + for (EndPointMapType::iterator it = line_range.first; it != line_range.second; ++ it) { + if (it->second == i_candidate) { + // closing the loop. + goto end_of_poly; + } + if (line_processed[it->second]) + continue; + if (i_next == -1) { + i_next = it->second; + } else { + // This is a corner, where two lines meet exactly. Pick the line, which encloses a smallest angle with + // the current edge. + const Line &line_current = lines[i_line_current]; + const Line &line_next = lines[it->second]; + const Vector v1 = line_current.vector(); + const Vector v2 = line_next.vector(); + int64_t cross = int64_t(v1.x) * int64_t(v2.y) - int64_t(v2.x) * int64_t(v1.y); + if (cross > 0) { + // This has to be a convex right angle. There is no better next line. + i_next = it->second; + break; + } + } + } + line_processed[i_next] = true; + i_line_current = i_next; + poly.points.push_back(lines[i_line_current].b); + } + end_of_poly: + out.push_back(std::move(poly)); + } + + // 3) Scale the polygons back into world, shrink slightly and remove collinear points. + for (size_t i = 0; i < out.size(); ++ i) { + Polygon &poly = out[i]; + for (size_t j = 0; j < poly.points.size(); ++ j) { + Point &p = poly.points[j]; + p.x *= m_resolution; + p.y *= m_resolution; + p.x += m_bbox.min.x; + p.y += m_bbox.min.y; + } + // Shrink the contour slightly, so if the same contour gets discretized and simplified again, one will get the same result. + // Remove collineaer points. + Points pts; + pts.reserve(poly.points.size()); + coord_t downscale = 5; + for (size_t j = 0; j < poly.points.size(); ++ j) { + size_t j0 = (j == 0) ? poly.points.size() - 1 : j - 1; + size_t j2 = (j + 1 == poly.points.size()) ? 0 : j + 1; + Point v = poly.points[j2] - poly.points[j0]; + if (v.x != 0 && v.y != 0) { + // This is a corner point. Copy it to the output contour. + Point p = poly.points[j]; + p.y += (v.x < 0) ? downscale : -downscale; + p.x += (v.y > 0) ? downscale : -downscale; + pts.push_back(p); + } + } + poly.points = std::move(pts); + } + return out; +} + #ifdef SLIC3R_GUI void EdgeGrid::save_png(const EdgeGrid::Grid &grid, const BoundingBox &bbox, coord_t resolution, const char *path) { |