Fix bridge detector

Reduce the number of angle to choose from
If two angle are too close, keep the one from the longest line.
supermerill/SuperSlicer#1824

2 files changed, 63 insertions, 15 deletions

diff --git a/src/libslic3r/BridgeDetector.cpp b/src/libslic3r/BridgeDetector.cpp
index 7b33a6dd5..1df8af4f6 100644
--- a/src/libslic3r/BridgeDetector.cpp
+++ b/src/libslic3r/BridgeDetector.cpp
@@ -258,7 +258,7 @@ bool BridgeDetector::detect_angle(double bridge_direction_override)
         double ratio_max = 1 - double(c.max_length_anchored - min_max_length) / (double)std::max(1., max_max_length - min_max_length);
         c.coverage += 15 * ratio_max;
         //bonus for perimeter dir
-        if (c.along_perimeter)
+        if (c.along_perimeter_length > 0)
             c.coverage += 5;
 
     }
@@ -293,8 +293,21 @@ std::vector<BridgeDetector::BridgeDirection> BridgeDetector::bridge_direction_ca
     // we also test angles of each bridge contour
     {
         Lines lines = to_lines(this->expolygons);
-        for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line)
-            angles.emplace_back(line->direction(), true);
+        //if many lines, only takes the bigger ones.
+        float mean_sqr_size = 0;
+        if (lines.size() > 200) {
+            for (int i = 0; i < 200; i++) {
+                mean_sqr_size += (float)lines[i].a.distance_to_square(lines[i].b);
+            }
+            mean_sqr_size /= 200;
+            for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line) {
+                float dist_sqr = line->a.distance_to_square(line->b);
+                if (dist_sqr > mean_sqr_size)
+                    angles.emplace_back(line->direction(), dist_sqr);
+            }
+        }else
+            for (Lines::const_iterator line = lines.begin(); line != lines.end(); ++line)
+                angles.emplace_back(line->direction(), line->a.distance_to_square(line->b));
     }
     
     /*  we also test angles of each open supporting edge
@@ -304,12 +317,51 @@ std::vector<BridgeDetector::BridgeDirection> BridgeDetector::bridge_direction_ca
             angles.emplace_back(Line(edge.first_point(), edge.last_point()).direction());
     
     // remove duplicates
-    double min_resolution = PI/(4*180.0);  // /180 = 1 degree
-    std::sort(angles.begin(), angles.end());
+    std::sort(angles.begin(), angles.end(), [](const BridgeDirection& bt1, const BridgeDirection& bt2) { return bt1.angle < bt2.angle; });
+
+    //first delete angles too close to an angle from a perimeter  
+    for (size_t i = 1; i < angles.size(); ++i) {
+        if (angles[i - 1].along_perimeter_length > 0 && angles[i].along_perimeter_length == 0)
+            if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, this->resolution)) {
+                angles.erase(angles.begin() + i);
+                --i;
+                continue;
+            }
+        if (angles[i].along_perimeter_length > 0 && angles[i - 1].along_perimeter_length == 0)
+            if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, this->resolution)) {
+                angles.erase(angles.begin() + (i-1));
+                --i;
+                continue;
+            }
+    }
+    //then delete angle to close to each other (high resolution)
+    double min_resolution = this->resolution / 8;
     for (size_t i = 1; i < angles.size(); ++i) {
-        if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i-1].angle, min_resolution)) {
-            angles.erase(angles.begin() + i);
-            --i;
+        if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, min_resolution)) {
+            // keep the longest of the two.
+            if (angles[i].along_perimeter_length < angles[i - 1].along_perimeter_length) {
+                angles.erase(angles.begin() + i);
+                --i;
+            } else {
+                angles.erase(angles.begin() + (i-1));
+                --i;
+            }
+        }
+    }
+    //then, if too much angles, delete more
+    while (angles.size() > 200) {
+        min_resolution *= 2;
+        for (size_t i = 1; i < angles.size(); ++i) {
+            if (Slic3r::Geometry::directions_parallel(angles[i].angle, angles[i - 1].angle, min_resolution)) {
+                // keep the longest of the two.
+                if (angles[i].along_perimeter_length < angles[i - 1].along_perimeter_length) {
+                    angles.erase(angles.begin() + i);
+                    --i;
+                } else {
+                    angles.erase(angles.begin() + (i - 1));
+                    --i;
+                }
+            }
         }
     }
     /*  compare first value with last one and remove the greatest one (PI) 
diff --git a/src/libslic3r/BridgeDetector.hpp b/src/libslic3r/BridgeDetector.hpp
index 9a81aa06f..0416a48cf 100644
--- a/src/libslic3r/BridgeDetector.hpp
+++ b/src/libslic3r/BridgeDetector.hpp
@@ -43,16 +43,12 @@ private:
     void initialize();
 
     struct BridgeDirection {
-        BridgeDirection(double a = -1., bool along_perimeter = false) : angle(a), coverage(0.), along_perimeter(along_perimeter){}
-        // the best direction is the one causing most lines to be bridged (thus most coverage)
-        bool operator<(const BridgeDirection &other) const {
-            // Initial sort by coverage only - comparator must obey strict weak ordering
-            return this->coverage > other.coverage;
-        };
+        BridgeDirection(double a = -1., float along_perimeter = 0) : angle(a), coverage(0.), along_perimeter_length(along_perimeter){}
+
         double angle;
         double coverage;
 
-        bool along_perimeter;
+        float along_perimeter_length;
         coordf_t total_length_anchored = 0;
         coordf_t median_length_anchor = 0;
         coordf_t max_length_anchored = 0;