From 2e55898d78ddca4753adb60c9222c52bc9ee8ba8 Mon Sep 17 00:00:00 2001 From: Vojtech Bubnik Date: Tue, 9 Feb 2021 18:36:28 +0100 Subject: Removal of not numerically robust libraries "poly2tree" and "polypartition". Adjustment of GUI/3DBed.cpp,hpp to use the more stable triangulation algoritm derived from SGI glut. Fix of an extremely slow bridging calculation, caused by an extremely slow bridged area detection function, of which the results were never used. Fixes "slicing fails or takes too long #5974" --- src/libslic3r/BridgeDetector.cpp | 58 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 57 insertions(+), 1 deletion(-) (limited to 'src/libslic3r/BridgeDetector.cpp') diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp index bf8907c3f..ff33e81d5 100644 --- a/src/libslic3r/BridgeDetector.cpp +++ b/src/libslic3r/BridgeDetector.cpp @@ -207,6 +207,62 @@ std::vector BridgeDetector::bridge_direction_candidates() const return angles; } +/* +static void get_trapezoids(const ExPolygon &expoly, Polygons* polygons) const +{ + ExPolygons expp; + expp.push_back(expoly); + boost::polygon::get_trapezoids(*polygons, expp); +} + +void ExPolygon::get_trapezoids(ExPolygon clone, Polygons* polygons, double angle) const +{ + clone.rotate(PI/2 - angle, Point(0,0)); + clone.get_trapezoids(polygons); + for (Polygons::iterator polygon = polygons->begin(); polygon != polygons->end(); ++polygon) + polygon->rotate(-(PI/2 - angle), Point(0,0)); +} +*/ + +// This algorithm may return more trapezoids than necessary +// (i.e. it may break a single trapezoid in several because +// other parts of the object have x coordinates in the middle) +static void get_trapezoids2(const ExPolygon &expoly, Polygons* polygons) +{ + Polygons src_polygons = to_polygons(expoly); + // get all points of this ExPolygon + const Points pp = to_points(src_polygons); + + // build our bounding box + BoundingBox bb(pp); + + // get all x coordinates + std::vector xx; + xx.reserve(pp.size()); + for (Points::const_iterator p = pp.begin(); p != pp.end(); ++p) + xx.push_back(p->x()); + std::sort(xx.begin(), xx.end()); + + // find trapezoids by looping from first to next-to-last coordinate + for (std::vector::const_iterator x = xx.begin(); x != xx.end()-1; ++x) { + coord_t next_x = *(x + 1); + if (*x != next_x) + // intersect with rectangle + // append results to return value + polygons_append(*polygons, intersection({ { { *x, bb.min.y() }, { next_x, bb.min.y() }, { next_x, bb.max.y() }, { *x, bb.max.y() } } }, src_polygons)); + } +} + +static void get_trapezoids2(const ExPolygon &expoly, Polygons* polygons, double angle) +{ + ExPolygon clone = expoly; + clone.rotate(PI/2 - angle, Point(0,0)); + get_trapezoids2(clone, polygons); + for (Polygon &polygon : *polygons) + polygon.rotate(-(PI/2 - angle), Point(0,0)); +} + +// Coverage is currently only used by the unit tests. It is extremely slow and unreliable! Polygons BridgeDetector::coverage(double angle) const { if (angle == -1) @@ -228,7 +284,7 @@ Polygons BridgeDetector::coverage(double angle) const for (ExPolygon &expoly : offset_ex(expolygon, 0.5f * float(this->spacing))) { // Compute trapezoids according to a vertical orientation Polygons trapezoids; - expoly.get_trapezoids2(&trapezoids, PI/2.0); + get_trapezoids2(expoly, &trapezoids, PI/2.0); for (const Polygon &trapezoid : trapezoids) { // not nice, we need a more robust non-numeric check size_t n_supported = 0; -- cgit v1.2.3 From c1179fc2c7f9048a315a38d390e55d2052b1213d Mon Sep 17 00:00:00 2001 From: Vojtech Bubnik Date: Tue, 13 Apr 2021 13:28:21 +0200 Subject: Marked the unsafe ClipperUtils offset functions with CLIPPERUTILS_UNSAFE_OFFSET Replaced some of the unsafe offset functions with safe variants. Please test the 1) print bed from STL function 2) concentric infill --- src/libslic3r/BridgeDetector.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libslic3r/BridgeDetector.cpp') diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp index ff33e81d5..671ebbdaa 100644 --- a/src/libslic3r/BridgeDetector.cpp +++ b/src/libslic3r/BridgeDetector.cpp @@ -40,7 +40,7 @@ void BridgeDetector::initialize() this->angle = -1.; // Outset our bridge by an arbitrary amout; we'll use this outer margin for detecting anchors. - Polygons grown = offset(to_polygons(this->expolygons), float(this->spacing)); + Polygons grown = offset(this->expolygons, float(this->spacing)); // Detect possible anchoring edges of this bridging region. // Detect what edges lie on lower slices by turning bridge contour and holes -- cgit v1.2.3 From 09a80d954cc066c1f752a8a2762907ad0b46cd56 Mon Sep 17 00:00:00 2001 From: Vojtech Bubnik Date: Mon, 3 May 2021 11:39:53 +0200 Subject: Further rework of ClipperUtils: Replaced many to_polygons() / to_expolygons() calls with templated ClipperUtils variants to avoid memory allocation and copying. --- src/libslic3r/BridgeDetector.cpp | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) (limited to 'src/libslic3r/BridgeDetector.cpp') diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp index 671ebbdaa..cd90a1f03 100644 --- a/src/libslic3r/BridgeDetector.cpp +++ b/src/libslic3r/BridgeDetector.cpp @@ -227,29 +227,33 @@ void ExPolygon::get_trapezoids(ExPolygon clone, Polygons* polygons, double angle // This algorithm may return more trapezoids than necessary // (i.e. it may break a single trapezoid in several because // other parts of the object have x coordinates in the middle) -static void get_trapezoids2(const ExPolygon &expoly, Polygons* polygons) +static void get_trapezoids2(const ExPolygon& expoly, Polygons* polygons) { Polygons src_polygons = to_polygons(expoly); // get all points of this ExPolygon - const Points pp = to_points(src_polygons); - + const Points pp = to_points(src_polygons); + // build our bounding box BoundingBox bb(pp); - + // get all x coordinates std::vector xx; xx.reserve(pp.size()); for (Points::const_iterator p = pp.begin(); p != pp.end(); ++p) xx.push_back(p->x()); std::sort(xx.begin(), xx.end()); - + // find trapezoids by looping from first to next-to-last coordinate + Polygons rectangle; + rectangle.emplace_back(Polygon()); for (std::vector::const_iterator x = xx.begin(); x != xx.end()-1; ++x) { coord_t next_x = *(x + 1); - if (*x != next_x) + if (*x != next_x) { // intersect with rectangle // append results to return value - polygons_append(*polygons, intersection({ { { *x, bb.min.y() }, { next_x, bb.min.y() }, { next_x, bb.max.y() }, { *x, bb.max.y() } } }, src_polygons)); + rectangle.front() = { { *x, bb.min.y() }, { next_x, bb.min.y() }, { next_x, bb.max.y() }, { *x, bb.max.y() } }; + polygons_append(*polygons, intersection(rectangle, src_polygons)); + } } } @@ -302,7 +306,7 @@ Polygons BridgeDetector::coverage(double angle) const covered = union_(covered); // Intersect trapezoids with actual bridge area to remove extra margins and append it to result. polygons_rotate(covered, -(PI/2.0 - angle)); - covered = intersection(covered, to_polygons(this->expolygons)); + covered = intersection(this->expolygons, covered); #if 0 { my @lines = map @{$_->lines}, @$trapezoids; -- cgit v1.2.3 From 7d4b3f29923839a0fc3033ef089e6eff5f5fa4a3 Mon Sep 17 00:00:00 2001 From: Vojtech Bubnik Date: Wed, 5 May 2021 12:16:40 +0200 Subject: Fix of safety_offset() after ClipperUtils refactoring. Fixes Solid infill where there should be none #6482 Also the safety offsetting was revised to be enabled only where needed, the "do safety offset" is now easy to discover by a new ApplySafetyOffset::Yes enum, and safety offset over union, which is better done by offset() / offset_ex() has been replaced with new union_safety_offset() / union_safety_offset_ex() functions, which better convey their meaning and which could be better optimized than union() with the safety offset applied. --- src/libslic3r/BridgeDetector.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libslic3r/BridgeDetector.cpp') diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp index cd90a1f03..03d671db4 100644 --- a/src/libslic3r/BridgeDetector.cpp +++ b/src/libslic3r/BridgeDetector.cpp @@ -58,7 +58,7 @@ void BridgeDetector::initialize() // detect anchors as intersection between our bridge expolygon and the lower slices // safety offset required to avoid Clipper from detecting empty intersection while Boost actually found some edges - this->_anchor_regions = intersection_ex(grown, to_polygons(this->lower_slices), true); + this->_anchor_regions = intersection_ex(grown, union_safety_offset(this->lower_slices)); /* if (0) { -- cgit v1.2.3