fix unwanted extra gapfill (boost::voronoi bug)

Mitigation: remove shallow angles that seems to make it appear.
As the previous remove_colinear was on a fixed dist (taht became too small on long segments)
I created a new one that work from an angle.
supermerill/SuperSlicer#2971

5 files changed, 70 insertions, 13 deletions

diff --git a/src/libslic3r/Geometry/MedialAxis.cpp b/src/libslic3r/Geometry/MedialAxis.cpp
index 670c8fb45..34d76844a 100644
--- a/src/libslic3r/Geometry/MedialAxis.cpp
+++ b/src/libslic3r/Geometry/MedialAxis.cpp
@@ -813,18 +813,18 @@ MedialAxis::polyline_from_voronoi(const ExPolygon& voronoi_polygon, ThickPolylin
     // iterate through the valid edges to build polylines
     while (!edges.empty()) {
         const edge_t* edge = *edges.begin();
-        if (thickness[edge].first > this->max_width * 1.001) {
+        //if (thickness[edge].first > this->max_width * 1.001) {
             //std::cerr << "Error, edge.first has a thickness of " << unscaled(this->thickness[edge].first) << " > " << unscaled(this->max_width) << "\n";
             //(void)this->edges.erase(edge);
             //(void)this->edges.erase(edge->twin());
             //continue;
-        }
-        if (thickness[edge].second > this->max_width * 1.001) {
+        //}
+        //if (thickness[edge].second > this->max_width * 1.001) {
             //std::cerr << "Error, edge.second has a thickness of " << unscaled(this->thickness[edge].second) << " > " << unscaled(this->max_width) << "\n";
             //(void)this->edges.erase(edge);
             //(void)this->edges.erase(edge->twin());
             //continue;
-        }
+        //}
 
         // start a polyline
         ThickPolyline polyline;
@@ -2414,9 +2414,9 @@ MedialAxis::simplify_polygon_frontier()
 {
     //it will remove every point in the surface contour that aren't on the bounds contour
     this->expolygon = this->surface;
-    this->expolygon.contour.remove_collinear(SCALED_EPSILON);
+    this->expolygon.contour.remove_collinear_angle(M_PI/180);
     for (Polygon& hole : this->expolygon.holes)
-        hole.remove_collinear(SCALED_EPSILON);
+        hole.remove_collinear_angle(M_PI / 180);
     if (&this->surface != this->bounds) {
         bool need_intersect = false;
         for (size_t i = 0; i < this->expolygon.contour.points.size(); i++) {
@@ -2445,9 +2445,9 @@ MedialAxis::simplify_polygon_frontier()
             } else {
                 //can't simplify that much, reuse the given one
                 this->expolygon = this->surface;
-                this->expolygon.contour.remove_collinear(SCALED_EPSILON);
+                this->expolygon.contour.remove_collinear_angle(M_PI / 180);
                 for (Polygon& hole : this->expolygon.holes)
-                    hole.remove_collinear(SCALED_EPSILON);
+                    hole.remove_collinear_angle(M_PI / 180);
             }
         }
     }
diff --git a/src/libslic3r/Polygon.cpp b/src/libslic3r/Polygon.cpp
index 27046c1d9..8badf41ea 100644
--- a/src/libslic3r/Polygon.cpp
+++ b/src/libslic3r/Polygon.cpp
@@ -298,15 +298,15 @@ size_t Polygon::remove_collinear(coord_t max_offset){
     size_t nb_del = 0;
     if (points.size() < 3) return 0;
 
-    coord_t min_dist = max_offset * max_offset;
-    while (points.size() > 2 && Line::distance_to_squared(points[0], points.back(), points[1]) < min_dist){
+    double min_dist_sq = coordf_t(max_offset) * max_offset;
+    while (points.size() > 2 && Line::distance_to_squared(points[0], points.back(), points[1]) < min_dist_sq){
         //colinear! delete!
         points.erase(points.begin());
         nb_del++;
     }
     for (size_t idx = 1; idx < points.size()-1; ) {
         //if (Line(previous, points[idx + 1]).distance_to(points[idx]) < SCALED_EPSILON){
-        if (Line::distance_to_squared(points[idx], points[idx-1], points[idx + 1]) < min_dist){
+        if (Line::distance_to_squared(points[idx], points[idx-1], points[idx + 1]) < min_dist_sq){
             //colinear! delete!
             points.erase(points.begin() + idx);
             nb_del++;
@@ -314,7 +314,7 @@ size_t Polygon::remove_collinear(coord_t max_offset){
             idx++;
         }
     }
-    while (points.size() > 2 && Line::distance_to_squared(points.back(), points[points.size()-2], points.front()) < min_dist) {
+    while (points.size() > 2 && Line::distance_to_squared(points.back(), points[points.size()-2], points.front()) < min_dist_sq) {
         //colinear! delete!
         points.erase(points.end()-1);
         nb_del++;
@@ -322,6 +322,46 @@ size_t Polygon::remove_collinear(coord_t max_offset){
 
     return nb_del;
 }
+
+size_t Polygon::remove_collinear_angle(double angle_radian) {
+    size_t nb_del = 0;
+    if (points.size() < 3) return 0;
+    //std::cout << "== remove_collinear_angle \n";
+    double min_dist_sq = std::sin(angle_radian);
+    min_dist_sq = min_dist_sq * min_dist_sq;
+    while (points.size() > 2 && Line::distance_to_squared(points.front(), points.back(), points[1]) < min_dist_sq * std::min(points.back().distance_to_square(points.front()), points.front().distance_to_square(points[1]))) {
+       /* if (Line::distance_to_squared(points.front(), points.back(), points[1]) > SCALED_EPSILON) {
+            std::cout << "Fcolinear angle " << Line::distance_to_squared(points[0], points.back(), points[1]) << " < " << (min_dist_sq * std::min(points.back().distance_to_square(points.front()), points.front().distance_to_square(points[1]))) << " (" << min_dist_sq << " * " << std::min(points.back().distance_to_square(points.front()), points.front().distance_to_square(points[1])) << ")\n";
+            std::cout << "      unscaled= " << unscaled(Line::distance_to(points[0], points.back(), points[1])) << " < " << unscaled(std::sin(angle_radian) * std::min(points.back().distance_to(points.front()), points.front().distance_to(points[1]))) << " (" << std::sin(angle_radian) << " * " << unscaled(std::min(points.back().distance_to(points.front()), points.front().distance_to(points[1]))) << ")\n";
+            std::cout << "      dists: " << unscaled(points.back().distance_to(points.front())) << " => " << unscaled(points.front().distance_to(points[1])) << "\n";
+        }*/
+        //colinear! delete!
+        points.erase(points.begin());
+        nb_del++;
+    }
+    for (size_t idx = 1; idx < points.size() - 1 && points.size() > 2; ) {
+        if (Line::distance_to_squared(points[idx], points[idx - 1], points[idx + 1]) < min_dist_sq * std::min(points[idx - 1].distance_to_square(points[idx]), points[idx].distance_to_square(points[idx + 1]))) {
+            /*if (Line::distance_to_squared(points[idx], points[idx - 1], points[idx + 1]) > SCALED_EPSILON) {
+                std::cout << " colinear angle " << Line::distance_to_squared(points[idx], points[idx - 1], points[idx + 1]) << " < " << (min_dist_sq * std::min(points[idx - 1].distance_to_square(points[idx]), points[idx].distance_to_square(points[idx + 1]))) << " (" << min_dist_sq << " * " << std::min(points[idx - 1].distance_to_square(points[idx]), points[idx].distance_to_square(points[idx + 1])) << ")\n";
+                std::cout << "      unscaled= " << unscaled(Line::distance_to(points[idx], points[idx - 1], points[idx + 1])) << " < " << unscaled(std::sin(angle_radian) * std::min(points[idx - 1].distance_to(points[idx]), points[idx].distance_to(points[idx + 1]))) << " (" << std::sin(angle_radian) << " * " << unscaled(std::min(points[idx - 1].distance_to(points[idx]), points[idx].distance_to(points[idx + 1]))) << ")\n";
+                std::cout << "      dists: " << unscaled(points[idx - 1].distance_to(points[idx])) << " => " << unscaled(points[idx].distance_to(points[idx + 1])) << "\n";
+            }*/
+            //colinear! delete!
+            points.erase(points.begin() + idx);
+            nb_del++;
+        } else {
+            idx++;
+        }
+    }
+    while (points.size() > 2 && Line::distance_to_squared(points.back(), points[points.size() - 2], points.front()) < min_dist_sq * std::min(points.back().distance_to_square(points[points.size() - 2]), points.front().distance_to_square(points.back()))) {
+        //colinear! delete!
+        points.erase(points.end() - 1);
+        nb_del++;
+    }
+
+    return nb_del;
+}
+
 BoundingBox get_extents(const Polygon &poly) 
 { 
     return poly.bounding_box();
diff --git a/src/libslic3r/Polygon.hpp b/src/libslic3r/Polygon.hpp
index 5390fccbd..029e3050e 100644
--- a/src/libslic3r/Polygon.hpp
+++ b/src/libslic3r/Polygon.hpp
@@ -73,6 +73,7 @@ public:
     /// remove points that are (almost) on an existing line from previous & next point.
     /// return number of point removed
     size_t remove_collinear(coord_t max_offset);
+    size_t remove_collinear_angle(double angle);
 
     using iterator = Points::iterator;
     using const_iterator = Points::const_iterator;
diff --git a/src/libslic3r/SVG.cpp b/src/libslic3r/SVG.cpp
index f88089ab7..48c54447a 100644
--- a/src/libslic3r/SVG.cpp
+++ b/src/libslic3r/SVG.cpp
@@ -194,6 +194,21 @@ void SVG::draw(const ThickLines &thicklines, const std::string &fill, const std:
         this->draw(*it, fill, stroke, stroke_width);
 }
 
+void SVG::draw(const ThickPolylines &polylines, const std::string &stroke)
+{
+    for (const ThickPolyline& poly : polylines) {
+        if (poly.points.size() < 2) continue;
+        Line l{ poly.points.front(), poly.points[1] };
+        this->draw(Line{ poly.points.front(), l.midpoint() }, stroke, poly.width.front() / 10);
+        for (int i = 1; i < poly.points.size()-1; ++i) {
+            Point first_point = l.midpoint();
+            l=Line{ poly.points[i], poly.points[i+1] };
+            this->draw(Line{ first_point, l.midpoint() }, stroke, poly.width[i]/10);
+        }
+        this->draw(Line{ l.midpoint(), poly.points.back() }, stroke, poly.width.back() / 10);
+    }
+}
+
 void SVG::draw(const ThickPolylines &polylines, const std::string &stroke, coordf_t stroke_width)
 {
     for (ThickPolylines::const_iterator it = polylines.begin(); it != polylines.end(); ++it)
diff --git a/src/libslic3r/SVG.hpp b/src/libslic3r/SVG.hpp
index cf9cbcbcd..d1911c066 100644
--- a/src/libslic3r/SVG.hpp
+++ b/src/libslic3r/SVG.hpp
@@ -65,7 +65,8 @@ public:
     void draw(const Polyline &polyline, std::string stroke = "black", coordf_t stroke_width = 0);
     void draw(const Polylines &polylines, std::string stroke = "black", coordf_t stroke_width = 0);
     void draw(const ThickLines &thicklines, const std::string &fill = "lime", const std::string &stroke = "black", coordf_t stroke_width = 0);
-    void draw(const ThickPolylines &polylines, const std::string &stroke = "black", coordf_t stroke_width = 0);
+    void draw(const ThickPolylines &thickpolylines, const std::string &stroke = "black");
+    void draw(const ThickPolylines &polylines, const std::string &stroke, coordf_t stroke_width);
     void draw(const ThickPolylines &thickpolylines, const std::string &fill, const std::string &stroke, coordf_t stroke_width);
     void draw(const Point &point, std::string fill = "black", coord_t radius = 0);
     void draw(const Points &points, std::string fill = "black", coord_t radius = 0);