Merge remote-tracking branch 'remotes/prusa/master' 2.4 into dev 2.3.58

still need much tests (& bugfixes) and finish some merging things.

1 files changed, 116 insertions, 11 deletions

diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp
index dd9c5e5f3..407a8d7ce 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
@@ -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) {
@@ -433,8 +433,116 @@ std::vector<BridgeDetector::BridgeDirection> BridgeDetector::bridge_direction_ca
     return angles;
 }
 
-Polygons BridgeDetector::coverage(double angle, bool precise) const {
+/*
+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<coord_t> 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<coord_t>::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
+            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));
+        }
+    }
+}
+
+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));
+}
+
 
+
+void get_trapezoids3_half(const ExPolygon& expoly, Polygons* polygons, float spacing)
+{
+
+    // get all points of this ExPolygon
+    Points pp = expoly;
+
+    if (pp.empty()) return;
+
+    // build our bounding box
+    BoundingBox bb(pp);
+
+    // get all x coordinates
+    coord_t min_x = pp[0].x(), max_x = pp[0].x();
+    std::vector<coord_t> xx;
+    for (Points::const_iterator p = pp.begin(); p != pp.end(); ++p) {
+        if (min_x > p->x()) min_x = p->x();
+        if (max_x < p->x()) max_x = p->x();
+    }
+    for (coord_t x = min_x; x < max_x - (coord_t)(spacing / 2); x += (coord_t)spacing) {
+        xx.push_back(x);
+    }
+    xx.push_back(max_x);
+    //std::sort(xx.begin(), xx.end());
+
+    // find trapezoids by looping from first to next-to-last coordinate
+    for (std::vector<coord_t>::const_iterator x = xx.begin(); x != xx.end() - 1; ++x) {
+        coord_t next_x = *(x + 1);
+        if (*x == next_x) continue;
+
+        // build rectangle
+        Polygon poly;
+        poly.points.resize(4);
+        poly[0].x() = *x + (coord_t)spacing / 4;
+        poly[0].y() = bb.min(1);
+        poly[1].x() = next_x - (coord_t)spacing / 4;
+        poly[1].y() = bb.min(1);
+        poly[2].x() = next_x - (coord_t)spacing / 4;
+        poly[2].y() = bb.max(1);
+        poly[3].x() = *x + (coord_t)spacing / 4;
+        poly[3].y() = bb.max(1);
+
+        // intersect with this expolygon
+        // append results to return value
+        polygons_append(*polygons, intersection(Polygons{ poly }, to_polygons(expoly)));
+    }
+}
+
+Polygons BridgeDetector::coverage(double angle, bool precise) const
+{
     if (angle == -1)
         angle = this->angle;
 
@@ -457,8 +565,8 @@ Polygons BridgeDetector::coverage(double angle, bool precise) const {
             for (ExPolygon &expoly : offset_ex(expolygon, 0.5f * float(this->spacing))) {
                 // Compute trapezoids according to a vertical orientation
                 Polygons trapezoids;
-                if (!precise) expoly.get_trapezoids2(&trapezoids, PI / 2);
-                else expoly.get_trapezoids3_half(&trapezoids, float(this->spacing));
+                if (!precise) get_trapezoids2(expoly, &trapezoids, PI / 2);
+                else get_trapezoids3_half(expoly, &trapezoids, float(this->spacing));
                 for (Polygon &trapezoid : trapezoids) {
                     size_t n_supported = 0;
                     if (!precise) {
@@ -511,7 +619,7 @@ Polygons BridgeDetector::coverage(double angle, bool precise) 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;
@@ -534,8 +642,7 @@ Polygons BridgeDetector::coverage(double angle, bool precise) const {
 /*  This method returns the bridge edges (as polylines) that are not supported
     but would allow the entire bridge area to be bridged with detected angle
     if supported too */
-void
-BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const
+void BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const
 {
     if (angle == -1) angle = this->angle;
     if (angle == -1) return;
@@ -575,9 +682,7 @@ BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const
     */
 }
 
-Polylines
-BridgeDetector::unsupported_edges(double angle) const
-{
+Polylines BridgeDetector::unsupported_edges(double angle) const {
     Polylines pp;
     this->unsupported_edges(angle, &pp);
     return pp;