Reworked the bridge detector to allow searching a single bridging

direction over multiple regions. This allows a single bridge to be
drawn over holes, which are too close to each other to allow
for separate bridges.
Fixes Bridging-Angle not optimal
https://github.com/prusa3d/Slic3r/issues/12

Re-allowed adaptive infill line width for solid infills. The adaptive
infill line width works in some circumstances, see Issue #15,
but the original implementation often changed the line width too
aggressively. The current implementation limits the line width change
to 20%.
Fixes Gaps between infill and perimeter leads to errors in laydown on following layer
https://github.com/prusa3d/Slic3r/issues/15

1 files changed, 190 insertions, 199 deletions

diff --git a/xs/src/libslic3r/BridgeDetector.cpp b/xs/src/libslic3r/BridgeDetector.cpp
index ec954e86c..d5250d03b 100644
--- a/xs/src/libslic3r/BridgeDetector.cpp
+++ b/xs/src/libslic3r/BridgeDetector.cpp
@@ -5,37 +5,48 @@
 
 namespace Slic3r {
 
-class BridgeDirectionComparator {
-    public:
-    std::map<double,double> dir_coverage;  // angle => score
-    
-    BridgeDirectionComparator(double _extrusion_width)
-        : extrusion_width(_extrusion_width)
-    {};
-    
-    // the best direction is the one causing most lines to be bridged (thus most coverage)
-    bool operator() (double a, double b) {
-        // Initial sort by coverage only - comparator must obey strict weak ordering
-        return (this->dir_coverage[a] > this->dir_coverage[b]);
-    };
-    
-    private:
-    double extrusion_width;
-};
+BridgeDetector::BridgeDetector(
+    ExPolygon                   _expolygon,
+    const ExPolygonCollection  &_lower_slices, 
+    coord_t                     _spacing) :
+    // The original infill polygon, not inflated.
+    expolygons(expolygons_owned),
+    // All surfaces of the object supporting this region.
+    lower_slices(_lower_slices),
+    spacing(_spacing)
+{
+    this->expolygons_owned.push_back(std::move(_expolygon));
+    initialize();
+}
+
+BridgeDetector::BridgeDetector(
+    const ExPolygons           &_expolygons,
+    const ExPolygonCollection  &_lower_slices,
+    coord_t                     _spacing) : 
+    // The original infill polygon, not inflated.
+    expolygons(_expolygons),
+    // All surfaces of the object supporting this region.
+    lower_slices(_lower_slices),
+    spacing(_spacing)
+{
+    initialize();
+}
 
-BridgeDetector::BridgeDetector(const ExPolygon &_expolygon, const ExPolygonCollection &_lower_slices,
-    coord_t _extrusion_width)
-    : expolygon(_expolygon), lower_slices(_lower_slices), extrusion_width(_extrusion_width),
-        resolution(PI/36.0), angle(-1)
+void BridgeDetector::initialize()
 {
-    /*  outset our bridge by an arbitrary amout; we'll use this outer margin
-        for detecting anchors */
-    Polygons grown;
-    offset((Polygons)this->expolygon, &grown, this->extrusion_width);
+    // 5 degrees stepping
+    this->resolution = PI/36.0; 
+    // output angle not known
+    this->angle = -1.;
+
+    // Outset our bridge by an arbitrary amout; we'll use this outer margin for detecting anchors.
+    Polygons grown = offset(this->expolygons, float(this->spacing));
     
-    // detect what edges lie on lower slices by turning bridge contour and holes
-    // into polylines and then clipping them with each lower slice's contour
-    intersection(grown, this->lower_slices.contours(), &this->_edges);
+    // Detect possible anchoring edges of this bridging region.
+    // Detect what edges lie on lower slices by turning bridge contour and holes
+    // into polylines and then clipping them with each lower slice's contour.
+    // Currently _edges are only used to set a candidate direction of the bridge (see bridge_direction_candidates()).
+    intersection(to_polylines(grown), this->lower_slices.contours(), &this->_edges);
     
     #ifdef SLIC3R_DEBUG
     printf("  bridge has " PRINTF_ZU " support(s)\n", this->_edges.size());
@@ -43,7 +54,7 @@ BridgeDetector::BridgeDetector(const ExPolygon &_expolygon, const ExPolygonColle
     
     // 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
-    intersection(grown, this->lower_slices, &this->_anchors, true);
+    this->_anchor_regions = intersection_ex(grown, to_polygons(this->lower_slices.expolygons), true);
     
     /*
     if (0) {
@@ -60,18 +71,103 @@ BridgeDetector::BridgeDetector(const ExPolygon &_expolygon, const ExPolygonColle
 bool
 BridgeDetector::detect_angle()
 {
-    if (this->_edges.empty() || this->_anchors.empty()) return false;
+    if (this->_edges.empty() || this->_anchor_regions.empty()) 
+        // The bridging region is completely in the air, there are no anchors available at the layer below.
+        return false;
+
+    std::vector<BridgeDirection> candidates;
+    {
+        std::vector<double> angles = bridge_direction_candidates();
+        candidates.reserve(angles.size());
+        for (size_t i = 0; i < angles.size(); ++ i)
+            candidates.push_back(BridgeDirection(angles[i]));
+    }
     
     /*  Outset the bridge expolygon by half the amount we used for detecting anchors;
         we'll use this one to clip our test lines and be sure that their endpoints
         are inside the anchors and not on their contours leading to false negatives. */
-    Polygons clip_area;
-    offset((const Slic3r::Polygons)this->expolygon, &clip_area, +this->extrusion_width/2);
+    Polygons clip_area = offset(this->expolygons, 0.5f * float(this->spacing));
     
     /*  we'll now try several directions using a rudimentary visibility check:
         bridge in several directions and then sum the length of lines having both
         endpoints within anchors */
+        
+    bool have_coverage = false;
+    for (size_t i_angle = 0; i_angle < candidates.size(); ++ i_angle)
+    {
+        const double angle = candidates[i_angle].angle;
+
+        Lines lines;
+        {
+            // Get an oriented bounding box around _anchor_regions.
+            BoundingBox bbox = get_extents_rotated(this->_anchor_regions, - angle);
+            // Cover the region with line segments.
+            lines.reserve((bbox.max.y - bbox.min.y + this->spacing) / this->spacing);
+            double s = sin(angle);
+            double c = cos(angle);
+            //FIXME Vojtech: The lines shall be spaced half the line width from the edge, but then 
+            // some of the test cases fail. Need to adjust the test cases then?
+//            for (coord_t y = bbox.min.y + this->spacing / 2; y <= bbox.max.y; y += this->spacing)
+            for (coord_t y = bbox.min.y; y <= bbox.max.y; y += this->spacing)
+                lines.push_back(Line(
+                    Point((coord_t)round(c * bbox.min.x - s * y), (coord_t)round(c * y + s * bbox.min.x)),
+                    Point((coord_t)round(c * bbox.max.x - s * y), (coord_t)round(c * y + s * bbox.max.x))));
+        }
+
+        double total_length = 0;
+        double max_length = 0;
+        {
+            Lines clipped_lines = intersection(lines, clip_area);
+            for (size_t i = 0; i < clipped_lines.size(); ++i) {
+                const Line &line = clipped_lines[i];
+                if (expolygons_contain(this->_anchor_regions, line.a) && expolygons_contain(this->_anchor_regions, line.b)) {
+                    // This line could be anchored.
+                    double len = line.length();
+                    total_length += len;
+                    max_length = std::max(max_length, len);
+                }
+            }        
+        }
+        if (total_length == 0.)
+            continue;
+
+        have_coverage = true;
+        // Sum length of bridged lines.
+        candidates[i_angle].coverage = total_length;
+        /*  The following produces more correct results in some cases and more broken in others.
+            TODO: investigate, as it looks more reliable than line clipping. */
+        // $directions_coverage{$angle} = sum(map $_->area, @{$self->coverage($angle)}) // 0;
+        // max length of bridged lines
+        candidates[i_angle].max_length = max_length;
+    }
+
+    // if no direction produced coverage, then there's no bridge direction
+    if (! have_coverage)
+        return false;
+    
+    // sort directions by coverage - most coverage first
+    std::sort(candidates.begin(), candidates.end());
+    
+    // if any other direction is within extrusion width of coverage, prefer it if shorter
+    // TODO: There are two options here - within width of the angle with most coverage, or within width of the currently perferred?
+    size_t i_best = 0;
+    for (size_t i = 1; i < candidates.size() && candidates[i_best].coverage - candidates[i].coverage < this->spacing; ++ i)
+        if (candidates[i].max_length < candidates[i_best].max_length)
+            i_best = i;
+
+    this->angle = candidates[i_best].angle;
+    if (this->angle >= PI)
+        this->angle -= PI;
     
+    #ifdef SLIC3R_DEBUG
+    printf("  Optimal infill angle is %d degrees\n", (int)Slic3r::Geometry::rad2deg(this->angle));
+    #endif
+    
+    return true;
+}
+
+std::vector<double> BridgeDetector::bridge_direction_candidates() const
+{
     // we test angles according to configured resolution
     std::vector<double> angles;
     for (int i = 0; i <= PI/this->resolution; ++i)
@@ -79,20 +175,16 @@ BridgeDetector::detect_angle()
     
     // we also test angles of each bridge contour
     {
-        Polygons pp = this->expolygon;
-        for (Polygons::const_iterator p = pp.begin(); p != pp.end(); ++p) {
-            Lines lines = p->lines();
-            for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line)
-                angles.push_back(line->direction());
-        }
+        Lines lines = to_lines(this->expolygons);
+        for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line)
+            angles.push_back(line->direction());
     }
     
     /*  we also test angles of each open supporting edge
         (this finds the optimal angle for C-shaped supports) */
-    for (Polylines::const_iterator edge = this->_edges.begin(); edge != this->_edges.end(); ++edge) {
-        if (edge->first_point().coincides_with(edge->last_point())) continue;
-        angles.push_back(Line(edge->first_point(), edge->last_point()).direction());
-    }
+    for (Polylines::const_iterator edge = this->_edges.begin(); edge != this->_edges.end(); ++edge)
+        if (! edge->first_point().coincides_with(edge->last_point()))
+            angles.push_back(Line(edge->first_point(), edge->last_point()).direction());
     
     // remove duplicates
     double min_resolution = PI/180.0;  // 1 degree
@@ -107,91 +199,8 @@ BridgeDetector::detect_angle()
         in case they are parallel (PI, 0) */
     if (Slic3r::Geometry::directions_parallel(angles.front(), angles.back(), min_resolution))
         angles.pop_back();
-    
-    BridgeDirectionComparator bdcomp(this->extrusion_width);
-    std::map<double,double> dir_avg_length;
-    double line_increment = this->extrusion_width;
-    bool have_coverage = false;
-    for (std::vector<double>::const_iterator angle = angles.begin(); angle != angles.end(); ++angle) {
-        Polygons my_clip_area = clip_area;
-        ExPolygons my_anchors = this->_anchors;
-        
-        // rotate everything - the center point doesn't matter
-        for (Polygons::iterator it = my_clip_area.begin(); it != my_clip_area.end(); ++it)
-            it->rotate(-*angle, Point(0,0));
-        for (ExPolygons::iterator it = my_anchors.begin(); it != my_anchors.end(); ++it)
-            it->rotate(-*angle, Point(0,0));
-    
-        // generate lines in this direction
-        BoundingBox bb;
-        for (ExPolygons::const_iterator it = my_anchors.begin(); it != my_anchors.end(); ++it)
-            bb.merge((Points)*it);
-        
-        Lines lines;
-        for (coord_t y = bb.min.y; y <= bb.max.y; y += line_increment)
-            lines.push_back(Line(Point(bb.min.x, y), Point(bb.max.x, y)));
-        
-        Lines clipped_lines;
-        intersection(lines, my_clip_area, &clipped_lines);
-        
-        // remove any line not having both endpoints within anchors
-        for (size_t i = 0; i < clipped_lines.size(); ++i) {
-            Line &line = clipped_lines[i];
-            if (!Slic3r::Geometry::contains(my_anchors, line.a)
-                || !Slic3r::Geometry::contains(my_anchors, line.b)) {
-                clipped_lines.erase(clipped_lines.begin() + i);
-                --i;
-            }
-        }
-        
-        std::vector<double> lengths;
-        double total_length = 0;
-        for (Lines::const_iterator line = clipped_lines.begin(); line != clipped_lines.end(); ++line) {
-            double len = line->length();
-            lengths.push_back(len);
-            total_length += len;
-        }
-        if (total_length) have_coverage = true;
-        
-        // sum length of bridged lines
-        bdcomp.dir_coverage[*angle] = total_length;
-        
-        /*  The following produces more correct results in some cases and more broken in others.
-            TODO: investigate, as it looks more reliable than line clipping. */
-        // $directions_coverage{$angle} = sum(map $_->area, @{$self->coverage($angle)}) // 0;
-        
-        // max length of bridged lines
-        dir_avg_length[*angle] = !lengths.empty()
-            ? *std::max_element(lengths.begin(), lengths.end())
-            : 0;
-    }
-    
-    // if no direction produced coverage, then there's no bridge direction
-    if (!have_coverage) return false;
-    
-    // sort directions by coverage - most coverage first
-    std::sort(angles.begin(), angles.end(), bdcomp);
-    this->angle = angles.front();
-    
-    // if any other direction is within extrusion width of coverage, prefer it if shorter
-    // TODO: There are two options here - within width of the angle with most coverage, or within width of the currently perferred?
-    double most_coverage_angle = this->angle;
-    for (std::vector<double>::const_iterator angle = angles.begin() + 1;
-        angle != angles.end() && bdcomp.dir_coverage[most_coverage_angle] - bdcomp.dir_coverage[*angle] < this->extrusion_width;
-        ++angle
-    ) {
-        if (dir_avg_length[*angle] < dir_avg_length[this->angle]) {
-            this->angle = *angle;
-        }
-    }
-    
-    if (this->angle >= PI) this->angle -= PI;
-    
-    #ifdef SLIC3R_DEBUG
-    printf("  Optimal infill angle is %d degrees\n", (int)Slic3r::Geometry::rad2deg(this->angle));
-    #endif
-    
-    return true;
+
+    return angles;
 }
 
 void
@@ -199,58 +208,48 @@ BridgeDetector::coverage(double angle, Polygons* coverage) const
 {
     if (angle == -1) angle = this->angle;
     if (angle == -1) return;
-    
-    // Clone our expolygon and rotate it so that we work with vertical lines.
-    ExPolygon expolygon = this->expolygon;
-    expolygon.rotate(PI/2.0 - angle, Point(0,0));
-    
-    /*  Outset the bridge expolygon by half the amount we used for detecting anchors;
-        we'll use this one to generate our trapezoids and be sure that their vertices
-        are inside the anchors and not on their contours leading to false negatives. */
-    ExPolygons grown;
-    offset(expolygon, &grown, this->extrusion_width/2.0);
-    
-    // Compute trapezoids according to a vertical orientation
-    Polygons trapezoids;
-    for (ExPolygons::const_iterator it = grown.begin(); it != grown.end(); ++it)
-        it->get_trapezoids2(&trapezoids, PI/2.0);
-    
-    // get anchors, convert them to Polygons and rotate them too
-    Polygons anchors;
-    for (ExPolygons::const_iterator anchor = this->_anchors.begin(); anchor != this->_anchors.end(); ++anchor) {
-        Polygons pp = *anchor;
-        for (Polygons::iterator p = pp.begin(); p != pp.end(); ++p)
-            p->rotate(PI/2.0 - angle, Point(0,0));
-        anchors.insert(anchors.end(), pp.begin(), pp.end());
-    }
+
+    // Get anchors, convert them to Polygons and rotate them.
+    Polygons anchors = to_polygons(this->_anchor_regions);
+    polygons_rotate(anchors, PI/2.0 - angle);
     
     Polygons covered;
-    for (Polygons::const_iterator trapezoid = trapezoids.begin(); trapezoid != trapezoids.end(); ++trapezoid) {
-        Lines lines = trapezoid->lines();
-        Lines supported;
-        intersection(lines, anchors, &supported);
+    for (ExPolygons::const_iterator it_expoly = this->expolygons.begin(); it_expoly != this->expolygons.end(); ++ it_expoly)
+    {
+        // Clone our expolygon and rotate it so that we work with vertical lines.
+        ExPolygon expolygon = *it_expoly;
+        expolygon.rotate(PI/2.0 - angle);
         
-        // not nice, we need a more robust non-numeric check
-        for (size_t i = 0; i < supported.size(); ++i) {
-            if (supported[i].length() < this->extrusion_width) {
-                supported.erase(supported.begin() + i);
-                i--;
-            }
+        /*  Outset the bridge expolygon by half the amount we used for detecting anchors;
+            we'll use this one to generate our trapezoids and be sure that their vertices
+            are inside the anchors and not on their contours leading to false negatives. */
+        ExPolygons grown = offset_ex(expolygon, 0.5f * float(this->spacing));
+        
+        // Compute trapezoids according to a vertical orientation
+        Polygons trapezoids;
+        for (ExPolygons::const_iterator it = grown.begin(); it != grown.end(); ++it)
+            it->get_trapezoids2(&trapezoids, PI/2.0);
+        
+        for (Polygons::iterator trapezoid = trapezoids.begin(); trapezoid != trapezoids.end(); ++trapezoid) {
+            Lines supported = intersection(trapezoid->lines(), anchors);
+            size_t n_supported = 0;
+            // not nice, we need a more robust non-numeric check
+            for (size_t i = 0; i < supported.size(); ++i)
+                if (supported[i].length() >= this->spacing)
+                    ++ n_supported;
+            if (n_supported >= 2) 
+                covered.push_back(STDMOVE(*trapezoid));
         }
-
-        if (supported.size() >= 2) covered.push_back(*trapezoid);        
     }
-    
-    // merge trapezoids and rotate them back
-    Polygons _coverage;
-    union_(covered, &_coverage);
-    for (Polygons::iterator p = _coverage.begin(); p != _coverage.end(); ++p)
-        p->rotate(-(PI/2.0 - angle), Point(0,0));
-    
-    // intersect trapezoids with actual bridge area to remove extra margins
-    // and append it to result
-    intersection(_coverage, this->expolygon, coverage);
-    
+
+    // Unite the trapezoids before rotation, as the rotation creates tiny gaps and intersections between the trapezoids
+    // instead of exact overlaps.
+    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));
+    intersection(covered, to_polygons(this->expolygons), coverage);
+
     /*
     if (0) {
         my @lines = map @{$_->lines}, @$trapezoids;
@@ -260,7 +259,7 @@ BridgeDetector::coverage(double angle, Polygons* coverage) const
         Slic3r::SVG::output(
             "coverage_" . rad2deg($angle) . ".svg",
             expolygons          => [$self->expolygon],
-            green_expolygons    => $self->_anchors,
+            green_expolygons    => $self->_anchor_regions,
             red_expolygons      => $coverage,
             lines               => \@lines,
         );
@@ -284,29 +283,21 @@ BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const
 {
     if (angle == -1) angle = this->angle;
     if (angle == -1) return;
-    
-    // get bridge edges (both contour and holes)
-    Polylines bridge_edges;
-    {
-        Polygons pp = this->expolygon;
-        bridge_edges.insert(bridge_edges.end(), pp.begin(), pp.end());  // this uses split_at_first_point()
-    }
-    
-    // get unsupported edges
-    Polygons grown_lower;
-    offset(this->lower_slices, &grown_lower, +this->extrusion_width);
-    Polylines _unsupported;
-    diff(bridge_edges, grown_lower, &_unsupported);
-    
-    /*  Split into individual segments and filter out edges parallel to the bridging angle
-        TODO: angle tolerance should probably be based on segment length and flow width,
-        so that we build supports whenever there's a chance that at least one or two bridge
-        extrusions would be anchored within such length (i.e. a slightly non-parallel bridging
-        direction might still benefit from anchors if long enough)
-        double angle_tolerance = PI / 180.0 * 5.0; */
-    for (Polylines::const_iterator polyline = _unsupported.begin(); polyline != _unsupported.end(); ++polyline) {
-        Lines lines = polyline->lines();
-        for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line) {
+
+    Polygons grown_lower = offset(this->lower_slices.expolygons, float(this->spacing));
+
+    for (ExPolygons::const_iterator it_expoly = this->expolygons.begin(); it_expoly != this->expolygons.end(); ++ it_expoly) {    
+        // get unsupported bridge edges (both contour and holes)
+        Polylines unuspported_polylines;
+        diff(to_polylines(*it_expoly), grown_lower, &unuspported_polylines);
+        Lines unsupported_lines = to_lines(unuspported_polylines);
+        /*  Split into individual segments and filter out edges parallel to the bridging angle
+            TODO: angle tolerance should probably be based on segment length and flow width,
+            so that we build supports whenever there's a chance that at least one or two bridge
+            extrusions would be anchored within such length (i.e. a slightly non-parallel bridging
+            direction might still benefit from anchors if long enough)
+            double angle_tolerance = PI / 180.0 * 5.0; */
+        for (Lines::const_iterator line = unsupported_lines.begin(); line != unsupported_lines.end(); ++line) {
             if (!Slic3r::Geometry::directions_parallel(line->direction(), angle))
                 unsupported->push_back(*line);
         }
@@ -318,7 +309,7 @@ BridgeDetector::unsupported_edges(double angle, Polylines* unsupported) const
         Slic3r::SVG::output(
             "unsupported_" . rad2deg($angle) . ".svg",
             expolygons          => [$self->expolygon],
-            green_expolygons    => $self->_anchors,
+            green_expolygons    => $self->_anchor_regions,
             red_expolygons      => union_ex($grown_lower),
             no_arrows           => 1,
             polylines           => \@bridge_edges,