From 5d72f18dc6cef37b984f6ed2a82d43f5b2640f8b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Luk=C3=A1=C5=A1=20Hejl?= Date: Wed, 16 Feb 2022 09:15:43 +0100 Subject: Follow-up to a4ecf2f2a6d140a25e9b76e90ae5f4cf8457bd91. Refactoring of the function for removing duplicate points. --- src/libslic3r/MultiMaterialSegmentation.cpp | 46 +---------------------------- src/libslic3r/MutablePolygon.cpp | 30 +++++++++++++++++++ src/libslic3r/MutablePolygon.hpp | 22 ++++++++++++++ 3 files changed, 53 insertions(+), 45 deletions(-) diff --git a/src/libslic3r/MultiMaterialSegmentation.cpp b/src/libslic3r/MultiMaterialSegmentation.cpp index f9a53b51d..9560096be 100644 --- a/src/libslic3r/MultiMaterialSegmentation.cpp +++ b/src/libslic3r/MultiMaterialSegmentation.cpp @@ -1676,50 +1676,6 @@ static bool has_layer_only_one_color(const std::vector> return true; } -// Remove nearly duplicate points. If a distance between two points is less than point_eps -// and if the angle between its surrounding lines is less than max_angle, the point will be removed. -void remove_duplicates_points(MutablePolygon &polygon, double point_eps, double max_angle) -{ - if (polygon.size() >= 3) { - auto eps2 = point_eps * point_eps; - auto begin = polygon.begin(); - auto it = begin; - for (++it; it != begin;) { - auto prev = it.prev(); - auto next = (it.next() == polygon.end() ? begin : it.next()); - if ((*it - *prev).cast().squaredNorm() < eps2) { - Vec2i64 vector1 = (*it - *prev).cast(); - Vec2i64 vector2 = (*next - *prev).cast(); - if (double angle = atan2(cross2(vector1, vector2), vector1.dot(vector2)); angle < max_angle) { - it = it.remove(); - continue; - } - } - ++it; - } - } -} - -// Remove nearly duplicate points. If a distance between two points is less than point_eps -// and if the angle between its surrounding lines is less than max_angle, the point will be removed. -inline ExPolygons remove_duplicates_points(ExPolygons expolygons, double point_eps, double max_angle) -{ - MutablePolygon mp; - for (ExPolygon &expolygon : expolygons) { - mp.assign(expolygon.contour, expolygon.contour.size() * 2); - remove_duplicates_points(mp, point_eps, max_angle); - mp.polygon(expolygon.contour); - for (Polygon &hole : expolygon.holes) { - mp.assign(hole, hole.size() * 2); - remove_duplicates_points(mp, point_eps, max_angle); - mp.polygon(hole); - } - expolygon.holes.erase(std::remove_if(expolygon.holes.begin(), expolygon.holes.end(), [](const auto &p) { return p.empty(); }), expolygon.holes.end()); - } - expolygons.erase(std::remove_if(expolygons.begin(), expolygons.end(), [](const auto &p) { return p.empty(); }), expolygons.end()); - return expolygons; -} - std::vector> multi_material_segmentation_by_painting(const PrintObject &print_object, const std::function &throw_on_cancel_callback) { const size_t num_extruders = print_object.print()->config().nozzle_diameter.size(); @@ -1755,7 +1711,7 @@ std::vector> multi_material_segmentation_by_painting(con // Such close points sometimes caused that the Voronoi diagram has self-intersecting edges around these vertices. // This consequently leads to issues with the extraction of colored segments by function extract_colored_segments. // Calling expolygons_simplify fixed these issues. - input_expolygons[layer_idx] = remove_duplicates_points(expolygons_simplify(offset_ex(ex_polygons, -10.f * float(SCALED_EPSILON)), 5 * SCALED_EPSILON), scaled(0.01), PI/6); + input_expolygons[layer_idx] = remove_duplicates(expolygons_simplify(offset_ex(ex_polygons, -10.f * float(SCALED_EPSILON)), 5 * SCALED_EPSILON), scaled(0.01), PI/6); #ifdef MMU_SEGMENTATION_DEBUG_INPUT { diff --git a/src/libslic3r/MutablePolygon.cpp b/src/libslic3r/MutablePolygon.cpp index 403d625bf..45c74d0a6 100644 --- a/src/libslic3r/MutablePolygon.cpp +++ b/src/libslic3r/MutablePolygon.cpp @@ -37,6 +37,36 @@ void remove_duplicates(MutablePolygon &polygon, double eps) } } +// Remove nearly duplicate points. If a distance between two points is less than scaled_eps +// and if the angle between its surrounding lines is less than max_angle, the point will be removed. +// May reduce the polygon down to empty polygon. +void remove_duplicates(MutablePolygon &polygon, coord_t scaled_eps, const double max_angle) +{ + if (polygon.size() >= 3) { + auto cos_max_angle_2 = Slic3r::sqr(cos(max_angle)); + auto scaled_eps_sqr = Slic3r::sqr(scaled_eps); + auto begin = polygon.begin(); + auto it = begin; + for (++it; it != begin;) { + auto prev = it.prev(); + auto next = it.next(); + Vec2i64 v1 = (*it - *prev).cast(); + int64_t v1_sqr_norm = v1.squaredNorm(); + if (v1_sqr_norm < scaled_eps_sqr) { + if (Vec2i64 v2 = (*next - *prev).cast(); + Slic3r::sqr(double(v1.dot(v2))) > cos_max_angle_2 * double(v1_sqr_norm) * double(v2.squaredNorm())) { + it = it.remove(); + continue; + } + } + it = next; + } + } + + if (polygon.size() < 3) + polygon.clear(); +} + // Adapted from Cura ConstPolygonRef::smooth_corner_complex() by Tim Kuipers. // A concave corner at it1 with position p1 has been removed by the caller between it0 and it2, where |p2 - p0| < shortcut_length. // Now try to close a concave crack by walking left from it0 and right from it2 as long as the new clipping edge is smaller than shortcut_length diff --git a/src/libslic3r/MutablePolygon.hpp b/src/libslic3r/MutablePolygon.hpp index 1b2b4e445..ea41d6fb4 100644 --- a/src/libslic3r/MutablePolygon.hpp +++ b/src/libslic3r/MutablePolygon.hpp @@ -309,6 +309,28 @@ inline bool operator!=(const MutablePolygon &p1, const MutablePolygon &p2) { ret void remove_duplicates(MutablePolygon &polygon); void remove_duplicates(MutablePolygon &polygon, double eps); +// Remove nearly duplicate points. If a distance between two points is less than scaled_eps +// and if the angle between its surrounding lines is less than max_angle, the point will be removed. +// May reduce the polygon down to empty polygon. +void remove_duplicates(MutablePolygon &polygon, coord_t scaled_eps, const double max_angle); +inline ExPolygons remove_duplicates(ExPolygons expolygons, coord_t scaled_eps, double max_angle) +{ + MutablePolygon mp; + for (ExPolygon &expolygon : expolygons) { + mp.assign(expolygon.contour, expolygon.contour.size() * 2); + remove_duplicates(mp, scaled_eps, max_angle); + mp.polygon(expolygon.contour); + for (Polygon &hole : expolygon.holes) { + mp.assign(hole, hole.size() * 2); + remove_duplicates(mp, scaled_eps, max_angle); + mp.polygon(hole); + } + expolygon.holes.erase(std::remove_if(expolygon.holes.begin(), expolygon.holes.end(), [](const auto &p) { return p.empty(); }), expolygon.holes.end()); + } + expolygons.erase(std::remove_if(expolygons.begin(), expolygons.end(), [](const auto &p) { return p.empty(); }), expolygons.end()); + return expolygons; +} + void smooth_outward(MutablePolygon &polygon, coord_t clip_dist_scaled); inline Polygon smooth_outward(Polygon polygon, coord_t clip_dist_scaled) -- cgit v1.2.3