Bugfix of bottom bridges. If close regions shall be closed by bridges,

these regions are grown to anchor the bridge lines to the bottom surface.
The grown regions may overlap. In that case the regions are now merged
before the bridging direction is calculated for the merged region.

12 files changed, 265 insertions, 10 deletions

diff --git a/xs/src/libslic3r/BoundingBox.cpp b/xs/src/libslic3r/BoundingBox.cpp
index c16d92f4e..2b3f00df1 100644
--- a/xs/src/libslic3r/BoundingBox.cpp
+++ b/xs/src/libslic3r/BoundingBox.cpp
@@ -259,4 +259,21 @@ BoundingBox3Base<PointClass>::center() const
 }
 template Pointf3 BoundingBox3Base<Pointf3>::center() const;
 
+template <class PointClass> bool
+BoundingBoxBase<PointClass>::contains(const PointClass &point) const
+{
+    return point.x >= this->min.x && point.x <= this->max.x
+        && point.y >= this->min.y && point.y <= this->max.y;
+}
+template bool BoundingBoxBase<Point>::contains(const Point &point) const;
+template bool BoundingBoxBase<Pointf>::contains(const Pointf &point) const;
+
+template <class PointClass> bool
+BoundingBoxBase<PointClass>::overlap(const BoundingBoxBase<PointClass> &other) const
+{
+    return this->contains(other.min) || other.contains(this->min);
+}
+template bool BoundingBoxBase<Point>::overlap(const BoundingBoxBase<Point> &point) const;
+template bool BoundingBoxBase<Pointf>::overlap(const BoundingBoxBase<Pointf> &point) const;
+
 }
diff --git a/xs/src/libslic3r/BoundingBox.hpp b/xs/src/libslic3r/BoundingBox.hpp
index b4f101976..7746515cb 100644
--- a/xs/src/libslic3r/BoundingBox.hpp
+++ b/xs/src/libslic3r/BoundingBox.hpp
@@ -32,6 +32,8 @@ class BoundingBoxBase
     void translate(coordf_t x, coordf_t y);
     void offset(coordf_t delta);
     PointClass center() const;
+    bool contains(const PointClass &point) const;
+    bool overlap(const BoundingBoxBase<PointClass> &other) const;
 };
 
 template <class PointClass>
diff --git a/xs/src/libslic3r/ExPolygon.cpp b/xs/src/libslic3r/ExPolygon.cpp
index 2220772b8..76a48b46a 100644
--- a/xs/src/libslic3r/ExPolygon.cpp
+++ b/xs/src/libslic3r/ExPolygon.cpp
@@ -4,6 +4,7 @@
 #include "Polygon.hpp"
 #include "Line.hpp"
 #include "ClipperUtils.hpp"
+#include "SVG.hpp"
 #include "polypartition.h"
 #include "poly2tri/poly2tri.h"
 #include <algorithm>
@@ -34,6 +35,17 @@ ExPolygon::operator Polygons() const
     return polygons;
 }
 
+ExPolygon::operator Polylines() const
+{
+    Polylines polylines;
+    polylines.reserve(this->holes.size() + 1);
+    polylines.push_back((Polyline)this->contour);
+    for (Polygons::const_iterator it = this->holes.begin(); it != this->holes.end(); ++it) {
+        polylines.push_back((Polyline)*it);
+    }
+    return polylines;
+}
+
 void
 ExPolygon::scale(double factor)
 {
@@ -105,6 +117,25 @@ ExPolygon::contains(const Polyline &polyline) const
 }
 
 bool
+ExPolygon::contains(const Polylines &polylines) const
+{
+    #if 0
+    BoundingBox bbox = get_extents(polylines);
+    bbox.merge(get_extents(*this));
+    SVG svg("out\\ExPolygon_contains.svg", bbox);
+    svg.draw(*this);
+    svg.draw_outline(*this);
+    svg.draw(polylines, "blue");
+    #endif
+    Polylines pl_out;
+    diff(polylines, *this, &pl_out);
+    #if 0
+    svg.draw(pl_out, "red");
+    #endif
+    return pl_out.empty();
+}
+
+bool
 ExPolygon::contains(const Point &point) const
 {
     if (!this->contour.contains(point)) return false;
@@ -131,6 +162,16 @@ ExPolygon::has_boundary_point(const Point &point) const
     return false;
 }
 
+bool
+ExPolygon::overlaps(const ExPolygon &other) const
+{
+    Polylines pl_out;
+    intersection((Polylines)other, *this, &pl_out);
+    if (! pl_out.empty())
+        return true; 
+    return ! other.contour.points.empty() && this->contains_b(other.contour.points.front());
+}
+
 void
 ExPolygon::simplify_p(double tolerance, Polygons* polygons) const
 {
diff --git a/xs/src/libslic3r/ExPolygon.hpp b/xs/src/libslic3r/ExPolygon.hpp
index ada37cecc..f283822da 100644
--- a/xs/src/libslic3r/ExPolygon.hpp
+++ b/xs/src/libslic3r/ExPolygon.hpp
@@ -18,17 +18,28 @@ class ExPolygon
     Polygons holes;
     operator Points() const;
     operator Polygons() const;
+    operator Polylines() const;
+    void clear() { contour.points.clear(); holes.clear(); }
     void scale(double factor);
     void translate(double x, double y);
     void rotate(double angle);
     void rotate(double angle, const Point &center);
     double area() const;
     bool is_valid() const;
+
+    // Contains the line / polyline / polylines etc COMPLETELY.
     bool contains(const Line &line) const;
     bool contains(const Polyline &polyline) const;
+    bool contains(const Polylines &polylines) const;
     bool contains(const Point &point) const;
     bool contains_b(const Point &point) const;
     bool has_boundary_point(const Point &point) const;
+
+    // Does this expolygon overlap another expolygon?
+    // Either the ExPolygons intersect, or one is fully inside the other,
+    // and it is not inside a hole of the other expolygon.
+    bool overlap(const ExPolygon &other) const;
+
     void simplify_p(double tolerance, Polygons* polygons) const;
     Polygons simplify_p(double tolerance) const;
     ExPolygons simplify(double tolerance) const;
diff --git a/xs/src/libslic3r/LayerRegion.cpp b/xs/src/libslic3r/LayerRegion.cpp
index fe35fd04b..64482145e 100644
--- a/xs/src/libslic3r/LayerRegion.cpp
+++ b/xs/src/libslic3r/LayerRegion.cpp
@@ -4,6 +4,7 @@
 #include "PerimeterGenerator.hpp"
 #include "Print.hpp"
 #include "Surface.hpp"
+#include "BoundingBox.hpp"
 #include "SVG.hpp"
 
 #include <string>
@@ -103,11 +104,12 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer)
     export_region_fill_surfaces_to_svg_debug("3_process_external_surfaces-initial");
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
 
+#if 0
     SurfaceCollection bottom;
     // For all stBottom && stBottomBridge surfaces:
     for (Surfaces::const_iterator surface = surfaces.begin(); surface != surfaces.end(); ++surface) {
         if (!surface->is_bottom()) continue;
-        // Grown by 3mm.
+        
         ExPolygons grown = offset_ex(surface->expolygon, +margin);
         
         /*  detect bridge direction before merging grown surfaces otherwise adjacent bridges
@@ -119,22 +121,19 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer)
             BridgeDetector bd(
                 surface->expolygon,
                 lower_layer->slices,
-                // Using extrusion width of an infill.
                 this->flow(frInfill, this->layer()->height, true).scaled_width()
             );
             
             #ifdef SLIC3R_DEBUG
-            printf("Processing bridge at layer %zu:\n", this->layer()->id());
+            printf("Processing bridge at layer %zu:\n", this->layer()->id();
             #endif
             
             if (bd.detect_angle()) {
                 angle = bd.angle;
-                // Are supports enabled?
+            
                 if (this->layer()->object()->config.support_material) {
                     Polygons coverage = bd.coverage();
-                    // Bridged polygons do not require supports.
                     this->bridged.insert(this->bridged.end(), coverage.begin(), coverage.end());
-                    // Unsupported edges of the infill.
                     this->unsupported_bridge_edges.append(bd.unsupported_edges()); 
                 }
             }
@@ -147,7 +146,140 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer)
             bottom.surfaces.push_back(s);
         }
     }
-    
+#else
+    // 1) Collect bottom and bridge surfaces, each of them grown by a fixed 3mm offset
+    // for better anchoring.
+    SurfaceCollection bottom;
+    SurfaceCollection bridges;
+    std::vector<BoundingBox> bridge_bboxes;
+    // For all stBottom && stBottomBridge surfaces:
+    for (Surfaces::const_iterator surface = surfaces.begin(); surface != surfaces.end(); ++surface) {
+        if (!surface->is_bottom()) continue;
+        // Grown by 3mm.
+        ExPolygons grown = offset_ex(surface->expolygon, +margin);
+        for (ExPolygons::const_iterator it = grown.begin(); it != grown.end(); ++it) {
+            Surface s       = *surface;
+            s.expolygon     = *it;
+            if (surface->surface_type == stBottomBridge) {
+                bridges.surfaces.push_back(s);
+                bridge_bboxes.push_back(get_extents(s));
+            } else
+                bottom.surfaces.push_back(s);
+        }
+    }
+
+#if 0
+    {
+        char path[2048];
+        static int iRun = 0;
+        sprintf(path, "out\\bridges-before-grouping-%d.svg", iRun ++);
+        bridges.export_to_svg(path, true);
+    }
+#endif
+
+    // 2) Group the bridge surfaces by overlaps.
+    std::vector<size_t> bridge_group(bridges.surfaces.size(), (size_t)-1);
+    size_t n_groups = 0; 
+    for (size_t i = 0; i < bridges.surfaces.size(); ++ i) {
+        // A grup id for this bridge.
+        size_t group_id = (bridge_group[i] == -1) ? (n_groups ++) : bridge_group[i];
+        bridge_group[i] = group_id;
+        // For all possibly overlaping bridges:
+        for (size_t j = i + 1; j < bridges.surfaces.size(); ++ j) {
+            if (! bridge_bboxes[i].overlap(bridge_bboxes[j]))
+                continue;
+            if (! bridges.surfaces[i].expolygon.overlaps(bridges.surfaces[j].expolygon))
+                continue;
+            // The two bridge regions intersect. Give them the same group id.
+            if (bridge_group[j] != -1) {
+                // The j'th bridge has been merged with some other bridge before.
+                size_t group_id_new = bridge_group[j];
+                for (size_t k = 0; k < j; ++ k)
+                    if (bridge_group[k] == group_id)
+                        bridge_group[k] = group_id_new;
+                group_id = group_id_new;
+            }
+            bridge_group[j] = group_id;
+        }
+    }
+
+    // 3) Merge the groups with the same group id.
+    {
+        SurfaceCollection bridges_merged;
+        bridges_merged.surfaces.reserve(n_groups);
+        for (size_t group_id = 0; group_id < n_groups; ++ group_id) {
+            size_t n_bridges_merged = 0;
+            size_t idx_last = (size_t)-1;
+            for (size_t i = 0; i < bridges.surfaces.size(); ++ i) {
+                if (bridge_group[i] == group_id) {
+                    ++ n_bridges_merged;
+                    idx_last = i;
+                }
+            }
+            if (n_bridges_merged == 1)
+                bridges_merged.surfaces.push_back(bridges.surfaces[idx_last]);
+            else if (n_bridges_merged > 1) {
+                Slic3r::Polygons polygons;
+                for (size_t i = 0; i < bridges.surfaces.size(); ++ i) {
+                    if (bridge_group[i] != group_id)
+                        continue;
+                    const Surface &surface = bridges.surfaces[i];
+                    polygons.push_back(surface.expolygon.contour);
+                    for (size_t j = 0; j < surface.expolygon.holes.size(); ++ j)
+                        polygons.push_back(surface.expolygon.holes[j]);
+                }
+                ExPolygons expp;
+                // without safety offset, artifacts are generated (GH #2494)
+                union_(polygons, &expp, true);
+                Surface &surface0 = bridges.surfaces[idx_last];
+                surface0.expolygon.clear();
+                for (size_t i = 0; i < expp.size(); ++ i) {
+                    surface0.expolygon = expp[i];
+                    bridges_merged.surfaces.push_back(surface0);
+                }
+            }
+        }
+        std::swap(bridges_merged, bridges);
+    }
+
+#if 0
+    {
+        char path[2048];
+        static int iRun = 0;
+        sprintf(path, "out\\bridges-after-grouping-%d.svg", iRun ++);
+        bridges.export_to_svg(path, true);
+    }
+#endif
+
+    // 4) Detect bridge directions.
+    if (lower_layer != NULL) {
+        for (size_t i = 0; i < bridges.surfaces.size(); ++ i) {
+            Surface &surface = bridges.surfaces[i];
+            /*  detect bridge direction before merging grown surfaces otherwise adjacent bridges
+                would get merged into a single one while they need different directions
+                also, supply the original expolygon instead of the grown one, because in case
+                of very thin (but still working) anchors, the grown expolygon would go beyond them */
+            BridgeDetector bd(
+                surface.expolygon,
+                lower_layer->slices,
+                this->flow(frInfill, this->layer()->height, true).scaled_width()
+            );
+            #ifdef SLIC3R_DEBUG
+            printf("Processing bridge at layer %zu:\n", this->layer()->id();
+            #endif            
+            if (bd.detect_angle()) {
+                surface.bridge_angle = bd.angle;
+                if (this->layer()->object()->config.support_material) {
+                    Polygons coverage = bd.coverage();
+                    this->bridged.insert(this->bridged.end(), coverage.begin(), coverage.end());
+                    this->unsupported_bridge_edges.append(bd.unsupported_edges()); 
+                }
+            }
+        }
+    }
+    bottom.surfaces.insert(bottom.surfaces.end(), bridges.surfaces.begin(), bridges.surfaces.end());
+#endif
+
     SurfaceCollection top;
     for (Surfaces::const_iterator surface = surfaces.begin(); surface != surfaces.end(); ++surface) {
         if (surface->surface_type != stTop) continue;
@@ -204,7 +336,7 @@ LayerRegion::process_external_surfaces(const Layer* lower_layer)
                 Surface s = *g->front();
                 s.expolygon = *ex;
                 new_surfaces.surfaces.push_back(s);
-            }
+            } 
         }
     }
     
diff --git a/xs/src/libslic3r/Polyline.cpp b/xs/src/libslic3r/Polyline.cpp
index baa2bbf5d..08717b57c 100644
--- a/xs/src/libslic3r/Polyline.cpp
+++ b/xs/src/libslic3r/Polyline.cpp
@@ -1,3 +1,4 @@
+#include "BoundingBox.hpp"
 #include "Polyline.hpp"
 #include "ExPolygon.hpp"
 #include "ExPolygonCollection.hpp"
@@ -220,6 +221,22 @@ Polyline::wkt() const
     return wkt.str();
 }
 
+BoundingBox get_extents(const Polyline &polyline)
+{
+    return polyline.bounding_box();
+}
+
+BoundingBox get_extents(const Polylines &polylines)
+{
+    BoundingBox bb;
+    if (! polylines.empty()) {
+        bb = polylines.front().bounding_box();
+        for (size_t i = 1; i < polylines.size(); ++ i)
+            bb.merge(polylines[i]);
+    }
+    return bb;
+}
+
 ThickLines
 ThickPolyline::thicklines() const
 {
diff --git a/xs/src/libslic3r/Polyline.hpp b/xs/src/libslic3r/Polyline.hpp
index 4d6673f2c..dd2818199 100644
--- a/xs/src/libslic3r/Polyline.hpp
+++ b/xs/src/libslic3r/Polyline.hpp
@@ -33,6 +33,9 @@ class Polyline : public MultiPoint {
     std::string wkt() const;
 };
 
+extern BoundingBox get_extents(const Polyline &polyline);
+extern BoundingBox get_extents(const Polylines &polylines);
+
 class ThickPolyline : public Polyline {
     public:
     std::vector<coordf_t> width;
diff --git a/xs/src/libslic3r/SVG.cpp b/xs/src/libslic3r/SVG.cpp
index d89602046..8b6d86622 100644
--- a/xs/src/libslic3r/SVG.cpp
+++ b/xs/src/libslic3r/SVG.cpp
@@ -182,7 +182,7 @@ void
 SVG::draw(const Polylines &polylines, std::string stroke, coordf_t stroke_width)
 {
     for (Polylines::const_iterator it = polylines.begin(); it != polylines.end(); ++it)
-        this->draw(*it, fill, stroke_width);
+        this->draw(*it, stroke, stroke_width);
 }
 
 void SVG::draw(const ThickLines &thicklines, const std::string &fill, const std::string &stroke, coordf_t stroke_width)
diff --git a/xs/src/libslic3r/SurfaceCollection.cpp b/xs/src/libslic3r/SurfaceCollection.cpp
index 5fbb913b1..c30998df4 100644
--- a/xs/src/libslic3r/SurfaceCollection.cpp
+++ b/xs/src/libslic3r/SurfaceCollection.cpp
@@ -1,4 +1,7 @@
 #include "SurfaceCollection.hpp"
+#include "BoundingBox.hpp"
+#include "SVG.hpp"
+
 #include <map>
 
 namespace Slic3r {
@@ -213,4 +216,28 @@ SurfaceCollection::append(const SurfaceType surfaceType, const Slic3r::ExPolygon
         this->surfaces.push_back(Slic3r::Surface(surfaceType, *it));
 }
 
+void SurfaceCollection::export_to_svg(const char *path, bool show_labels) 
+{
+    BoundingBox bbox;
+    for (Surfaces::const_iterator surface = this->surfaces.begin(); surface != this->surfaces.end(); ++surface)
+        bbox.merge(get_extents(surface->expolygon));
+    Point legend_size = export_surface_type_legend_to_svg_box_size();
+    Point legend_pos(bbox.min.x, bbox.max.y);
+    bbox.merge(Point(std::max(bbox.min.x + legend_size.x, bbox.max.x), bbox.max.y + legend_size.y));
+
+    SVG svg(path, bbox);
+    const float transparency = 0.5f;
+    for (Surfaces::const_iterator surface = this->surfaces.begin(); surface != this->surfaces.end(); ++surface) {
+        svg.draw(surface->expolygon, surface_type_to_color_name(surface->surface_type), transparency);
+        if (show_labels) {
+            int idx = int(surface - this->surfaces.cbegin());
+            char label[64];
+            sprintf(label, "%d", idx);
+            svg.draw_text(surface->expolygon.contour.points.front(), label, "black");
+        }
+    }
+    export_surface_type_legend_to_svg(svg, legend_pos);
+    svg.Close();
+}
+
 }
diff --git a/xs/src/libslic3r/SurfaceCollection.hpp b/xs/src/libslic3r/SurfaceCollection.hpp
index 07d0b0029..43835841d 100644
--- a/xs/src/libslic3r/SurfaceCollection.hpp
+++ b/xs/src/libslic3r/SurfaceCollection.hpp
@@ -30,6 +30,9 @@ class SurfaceCollection
     void filter_by_type(SurfaceType type, Polygons* polygons);
     void append(const SurfaceCollection &coll);
     void append(const SurfaceType surfaceType, const Slic3r::ExPolygons &expoly);
+
+    // For debugging purposes:
+    void export_to_svg(const char *path, bool show_labels);
 };
 
 }
diff --git a/xs/src/libslic3r/libslic3r.h b/xs/src/libslic3r/libslic3r.h
index 431b6fb45..e92124536 100644
--- a/xs/src/libslic3r/libslic3r.h
+++ b/xs/src/libslic3r/libslic3r.h
@@ -63,6 +63,6 @@ void confess_at(const char *file, int line, const char *func, const char *pat, .
 #endif
 
 // Write slices as SVG images into out directory during the 2D processing of the slices.
-#define SLIC3R_DEBUG_SLICE_PROCESSING
+// #define SLIC3R_DEBUG_SLICE_PROCESSING
 
 #endif
diff --git a/xs/xsp/BoundingBox.xsp b/xs/xsp/BoundingBox.xsp
index 948042eaf..efb5dea3b 100644
--- a/xs/xsp/BoundingBox.xsp
+++ b/xs/xsp/BoundingBox.xsp
@@ -16,6 +16,8 @@
     void scale(double factor);
     void translate(double x, double y);
     void offset(double delta);
+    bool contains_point(Point* point) %code{% RETVAL = THIS->contains(*point); %};
+    bool overlap(BoundingBox* bbox) %code{% RETVAL = THIS->overlap(*bbox); %};
     Clone<Polygon> polygon();
     Clone<Point> size();
     Clone<Point> center();