Enhanced avoid_crossing_perimeter: now try to follow the second perimeter where possible

And also trigger as early as 3 nozzle diameter when retract_before_travel is higher
Can trigger without only_retract_when_crossing_perimeters
supermerill/SuperSlicer#1794
supermerill/SuperSlicer#1793
supermerill/SuperSlicer#1790
supermerill/SuperSlicer#1349
supermerill/SuperSlicer#1061
supermerill/SuperSlicer#810
supermerill/SuperSlicer#173
supermerill/SuperSlicer#20

7 files changed, 183 insertions, 41 deletions

diff --git a/src/libslic3r/GCode.cpp b/src/libslic3r/GCode.cpp
index 2b55f0af5..b318d56ad 100644
--- a/src/libslic3r/GCode.cpp
+++ b/src/libslic3r/GCode.cpp
@@ -4128,19 +4128,20 @@ void GCode::_add_object_change_labels(std::string& gcode) {
 // This method accepts &point in print coordinates.
 Polyline GCode::travel_to(std::string &gcode, const Point &point, ExtrusionRole role)
 {
-    /*  Define the travel move as a line between current position and the taget point.
+        /*  Define the travel move as a line between current position and the taget point.
         This is expressed in print coordinates, so it will need to be translated by
         this->origin in order to get G-code coordinates.  */
     Polyline travel { this->last_pos(), point };
 
     // check whether a straight travel move would need retraction
-    bool needs_retraction       = this->needs_retraction(travel, role);
+    bool will_cross_perimeter = this->can_cross_perimeter(travel);
+    bool needs_retraction = will_cross_perimeter && this->needs_retraction(travel, role);
     // check whether wipe could be disabled without causing visible stringing
     bool could_be_wipe_disabled = false;
 
-    // if a retraction would be needed, try to use avoid_crossing_perimeters to plan a
+    // if a retraction would be needed (with a low min_dist threshold), try to use avoid_crossing_perimeters to plan a
     // multi-hop travel path inside the configuration space
-    if (needs_retraction
+    if (will_cross_perimeter && this->needs_retraction(travel, role, scale_d(EXTRUDER_CONFIG_WITH_DEFAULT(nozzle_diameter, 0.4)) * 3)
         && m_config.avoid_crossing_perimeters
         && ! m_avoid_crossing_perimeters.disabled_once()
         && m_avoid_crossing_perimeters.is_init()
@@ -4168,10 +4169,10 @@ Polyline GCode::travel_to(std::string &gcode, const Point &point, ExtrusionRole
             append(retract_travel.points, travel.points);
             travel = std::move(retract_travel);
         }
-    } else
+    } else {
         // Reset the wipe path when traveling, so one would not wipe along an old path.
         m_wipe.reset_path();
-
+    }
     //if needed, write the gcode_label_objects_end then gcode_label_objects_start
     _add_object_change_labels(gcode);
 
@@ -4188,9 +4189,13 @@ void GCode::write_travel_to(std::string &gcode, const Polyline& travel, std::str
         this->set_last_pos(travel.points.back());
     }
 }
-bool GCode::needs_retraction(const Polyline &travel, ExtrusionRole role)
+
+bool GCode::needs_retraction(const Polyline& travel, ExtrusionRole role /*=erNone*/, coordf_t max_min_dist /*=0*/)
 {
-    if (travel.length() < scale_(EXTRUDER_CONFIG_WITH_DEFAULT(retract_before_travel, 0))) {
+    coordf_t min_dist = scale_d(EXTRUDER_CONFIG_WITH_DEFAULT(retract_before_travel, 0));
+    if (max_min_dist > 0)
+        min_dist = std::min(max_min_dist, min_dist);
+    if (travel.length() < min_dist) {
         // skip retraction if the move is shorter than the configured threshold
         return false;
     }
@@ -4202,15 +4207,43 @@ bool GCode::needs_retraction(const Polyline &travel, ExtrusionRole role)
             // skip retraction if this is a travel move inside a support material island
             //FIXME not retracting over a long path may cause oozing, which in turn may result in missing material
             // at the end of the extrusion path!
-            return false;
+        return false;
     }
 
-    if (m_config.only_retract_when_crossing_perimeters && m_layer != nullptr &&
-        m_config.fill_density.value > 0 && m_layer->any_internal_region_slice_contains(travel))
+    return true;
+}
+
+bool GCode::can_cross_perimeter(const Polyline& travel)
+{
+    if(m_layer != nullptr)
+    if ( (m_config.only_retract_when_crossing_perimeters && m_config.fill_density.value > 0) || m_config.avoid_crossing_perimeters)
+         {
+        //test && m_layer->any_internal_region_slice_contains(travel)
         // Skip retraction if travel is contained in an internal slice *and*
         // internal infill is enabled (so that stringing is entirely not visible).
-        //FIXME any_internal_region_slice_contains() is potentionally very slow, it shall test for the bounding boxes first.
-        return false;
+        //note: any_internal_region_slice_contains() is potentionally very slow, it shall test for the bounding boxes first.
+        //bool inside = false;
+        //BoundingBox bbtravel(travel.points);
+        //for (const BoundingBox &bbox : m_layer->lslices_bboxes) {
+        //    inside = bbox.overlap(bbtravel);
+        //    if(inside) break;
+        //}
+        ////have to do a bit more work to be sure
+        //if (inside) {
+            //contained inside at least one bb
+            //construct m_layer_slices_offseted if needed
+            if (m_layer_slices_offseted.layer != m_layer) {
+                m_layer_slices_offseted.layer = m_layer;
+                m_layer_slices_offseted.diameter = scale_t(EXTRUDER_CONFIG_WITH_DEFAULT(nozzle_diameter, 0.4));
+                m_layer_slices_offseted.slices = offset_ex(m_layer->lslices, - m_layer_slices_offseted.diameter * 1.5);
+            }
+            // test if a expoly contains the entire travel
+            for (const ExPolygon &poly : m_layer_slices_offseted.slices)
+                if (poly.contains(travel)) {
+                    return false;
+                }
+        //}
+    }
 
     // retract if only_retract_when_crossing_perimeters is disabled or doesn't apply
     return true;
diff --git a/src/libslic3r/GCode.hpp b/src/libslic3r/GCode.hpp
index 27b016b4e..8c2bc4242 100644
--- a/src/libslic3r/GCode.hpp
+++ b/src/libslic3r/GCode.hpp
@@ -318,7 +318,8 @@ private:
 
     Polyline        travel_to(std::string& gcode, const Point &point, ExtrusionRole role);
     void            write_travel_to(std::string& gcode, const Polyline& travel, std::string comment);
-    bool            needs_retraction(const Polyline &travel, ExtrusionRole role = erNone);
+    bool            can_cross_perimeter(const Polyline& travel);
+    bool            needs_retraction(const Polyline& travel, ExtrusionRole role = erNone, coordf_t max_min_dist = 0);
     std::string     retract(bool toolchange = false);
     std::string     unretract() { return m_writer.unlift() + m_writer.unretract(); }
     std::string     set_extruder(uint16_t extruder_id, double print_z, bool no_toolchange = false);
@@ -361,6 +362,11 @@ private:
     // Current layer processed. Insequential printing mode, only a single copy will be printed.
     // In non-sequential mode, all its copies will be printed.
     const Layer*                        m_layer;
+    // For crossing perimeter retraction detection  (contain the layer & nozzle widdth used to construct it)
+    // !!!! not thread-safe !!!! if threaded per layer, please store it in the thread.
+    struct SliceOffsetted {
+        ExPolygons slices; const Layer* layer; coord_t diameter;
+    }                                   m_layer_slices_offseted{ {},nullptr, 0};
     double                              m_volumetric_speed;
     // Support for the extrusion role markers. Which marker is active?
     ExtrusionRole                       m_last_extrusion_role;
diff --git a/src/libslic3r/GCode/AvoidCrossingPerimeters.cpp b/src/libslic3r/GCode/AvoidCrossingPerimeters.cpp
index 0a3a3eabb..1d40a62bd 100644
--- a/src/libslic3r/GCode/AvoidCrossingPerimeters.cpp
+++ b/src/libslic3r/GCode/AvoidCrossingPerimeters.cpp
@@ -268,14 +268,97 @@ static std::vector<TravelPoint> simplify_travel(const AvoidCrossingPerimeters::B
     return simplified_path;
 }
 
+bool is_in_internal_boundary(const AvoidCrossingPerimeters::Boundary& boundary, const Point& pt) {
+    for (const std::pair<ExPolygon, ExPolygons>& bound : boundary.boundary_growth)
+        for (const ExPolygon& poly : bound.second)
+            if (poly.contains(pt))
+                return true;
+    return false;
+}
+
+bool find_point_on_boundary(Point& pt_to_move, const AvoidCrossingPerimeters::Boundary& boundary, coord_t max_dist) {
+
+    if (!is_in_internal_boundary(boundary, pt_to_move)) {
+        //get nearest point
+        EdgeGrid::Grid::ClosestPointResult pt_closest = boundary.grid.closest_point(pt_to_move, max_dist);
+        Point contour_pt;
+        if (pt_closest.contour_idx == size_t(-1)) {
+            //manual search on edges
+            bool found = false;
+            for (const std::pair<ExPolygon, ExPolygons>& bound : boundary.boundary_growth)
+                if (bound.first.contains(pt_to_move)) {
+                    coordf_t dist2 = std::numeric_limits<coordf_t>::max();
+                    for (const Polygon& poly : to_polygons(bound.second)) {
+                        Point test_point = *poly.closest_point(pt_to_move);
+                        coordf_t dist2_test = test_point.distance_to_square(pt_to_move);
+                        if (dist2_test < dist2) {
+                            dist2 = dist2_test;
+                            contour_pt = test_point;
+                            found = true;
+                        }
+                    }
+                    if(std::sqrt(dist2) > max_dist)
+                        for (const Polygon& poly : to_polygons(bound.second)) {
+                            Point test_point = pt_to_move.projection_onto(poly);
+                            coordf_t dist2_test = test_point.distance_to_square(pt_to_move);
+                            if (dist2_test < dist2) {
+                                dist2 = dist2_test;
+                                contour_pt = test_point;
+                                found = true;
+                            }
+                        }
+                    break;
+                }
+            if (!found) {
+                return false;
+            }
+        } else {
+            const Slic3r::Points& pts = *boundary.grid.contours()[pt_closest.contour_idx];
+            contour_pt = pts[pt_closest.start_point_idx].interpolate(pt_closest.t, pts[(pt_closest.start_point_idx + 1 == pts.size()) ? 0 : pt_closest.start_point_idx + 1]);
+        }
+        //push it a bit to be sure it's inside
+        Line l{ pt_to_move, contour_pt };
+        l.extend_end(SCALED_EPSILON);
+        pt_to_move = l.b;
+    }
+    return true;
+}
+
 // Called by avoid_perimeters() and by simplify_travel_heuristics().
 static size_t avoid_perimeters_inner(const AvoidCrossingPerimeters::Boundary &boundary,
-                                     const Point                             &start,
-                                     const Point                             &end,
+                                     const Point                             &real_start,
+                                     const Point                             &real_end,
+                                           coord_t                            extrusion_spacing,
                                      std::vector<TravelPoint>                &result_out)
 {
     const Polygons           &boundaries = boundary.boundaries;
     const EdgeGrid::Grid     &edge_grid  = boundary.grid;
+
+    Point start = real_start;
+    Point end = real_end;
+
+    //ensure that start & end are inside
+    if(extrusion_spacing > 0)
+        if (!find_point_on_boundary(start, boundary, (extrusion_spacing * 3)/2) || !find_point_on_boundary(end, boundary, (extrusion_spacing * 3) / 2)) {
+            BOOST_LOG_TRIVIAL(info) << "Fail to find a point in the contour for avoid_perimeter.";
+            //{
+            //    static int isazfn = 0;
+            //    std::stringstream stri;
+            //    stri << "avoid_peri_initbad_" << isazfn++ << ".svg";
+            //    SVG svg(stri.str());
+            //    for (auto elt : boundary.boundary_growth)
+            //        svg.draw((elt.first), "grey");
+            //    for (auto elt : boundary.boundary_growth)
+            //        svg.draw((elt.second), "pink");
+            //    //svg.draw((boundary.boundaries), "pink");
+            //    svg.draw((Line{ start,end }), "red");
+            //    svg.draw((Line{ real_start,real_end }), "green");
+            //    svg.Close();
+            //}
+            result_out = { {start,-1}, {end,-1} };
+            return 0;
+        }
+
     // Find all intersections between boundaries and the line segment, sort them along the line segment.
     std::vector<Intersection> intersections;
     {
@@ -366,8 +449,11 @@ static size_t avoid_perimeters_inner(const AvoidCrossingPerimeters::Boundary &bo
                              debug_out_path("AvoidCrossingPerimetersInner-final-%d.svg", iRun++));
     }
 #endif /* AVOID_CROSSING_PERIMETERS_DEBUG_OUTPUT */
-
+    if(start != real_start)
+        result_out.push_back({ real_start, -1 });
     append(result_out, std::move(result));
+    if (end != real_end)
+        result_out.push_back({ real_end, -1 });
     return intersections.size();
 }
 
@@ -375,11 +461,12 @@ static size_t avoid_perimeters_inner(const AvoidCrossingPerimeters::Boundary &bo
 static size_t avoid_perimeters(const AvoidCrossingPerimeters::Boundary &boundary,
                                const Point                             &start,
                                const Point                             &end,
+                                   coord_t                              spacing,
                                Polyline                                &result_out)
 {
     // Travel line is completely or partially inside the bounding box.
     std::vector<TravelPoint> path;
-    size_t num_intersections = avoid_perimeters_inner(boundary, start, end, path);
+    size_t num_intersections = avoid_perimeters_inner(boundary, start, end, spacing, path);
     result_out = to_polyline(path);
 
 #ifdef AVOID_CROSSING_PERIMETERS_DEBUG_OUTPUT
@@ -796,7 +883,7 @@ static ExPolygons get_boundary(const Layer &layer)
         append(boundary, inner_offset(support_layer->support_islands.expolygons, perimeter_offset));
 #endif
         auto *layer_below = layer.object()->get_first_layer_bellow_printz(layer.print_z, EPSILON);
-        if (layer_below)
+        if (layer_below) //why?
             append(boundary, inner_offset(layer_below->lslices, perimeter_offset));
         // After calling inner_offset it is necessary to call union_ex because of the possibility of intersection ExPolygons
         boundary = union_ex(boundary);
@@ -913,14 +1000,41 @@ Polyline AvoidCrossingPerimeters::travel_to(const GCode &gcodegen, const Point &
     const ExPolygons               &lslices          = gcodegen.layer()->lslices;
     const std::vector<BoundingBox> &lslices_bboxes   = gcodegen.layer()->lslices_bboxes;
     bool                            is_support_layer = dynamic_cast<const SupportLayer *>(gcodegen.layer()) != nullptr;
-    if (!use_external && (is_support_layer || (!lslices.empty() && !any_expolygon_contains(lslices, lslices_bboxes, m_grid_lslice, travel)))) {
+    const float perimeter_spacing = get_perimeter_spacing(*gcodegen.layer());
+    if (!use_external && (is_support_layer || !lslices.empty()
+        /*|| (!lslices.empty() && !any_expolygon_contains(lslices, lslices_bboxes, m_grid_lslice, travel)) already done by the caller */
+        )) {
         // Initialize m_internal only when it is necessary.
-        if (m_internal.boundaries.empty())
-            init_boundary(&m_internal, to_polygons(get_boundary(*gcodegen.layer())));
+        if (m_internal.boundaries.empty()) {
+            std::vector<std::pair<ExPolygon, ExPolygons>> boundary_growth;
+            //create better slice (on second perimeter instead of the first)
+            ExPolygons expoly_boundary;
+            //as we are going to reduce, do it expoli per expoli
+            for (const ExPolygon& origin : lslices) {
+                ExPolygons second_peri = offset_ex(origin, -perimeter_spacing * 1.5f);
+                //there is a collapse! try to add missing parts
+                if (second_peri.size() > 1) {
+                    // get the bits that are collapsed
+                    ExPolygons missing_parts = diff_ex({ origin }, offset_ex(second_peri, perimeter_spacing * 1.51f), true);
+                    //have to grow a bit to be able to fit inside the reduced thing
+                    // then intersect to be sure it don't stick out of the initial poly
+                    missing_parts = intersection_ex({ origin }, offset_ex(missing_parts, perimeter_spacing * 1.1f));
+                    // offset to second peri (-first) where possible, then union and reduce to the first.
+                    second_peri = offset_ex(union_ex(missing_parts, offset_ex(origin, -perimeter_spacing * 0.9f)), -perimeter_spacing * .6f);
+                } else if (second_peri.size() == 0) {
+                    // try again with the first perimeter (should be 0.5, but even with overlapping peri, it's almost never a 50% overlap, so it's better that way)
+                    second_peri = offset_ex(origin, -perimeter_spacing * .6f);
+                }
+                append(expoly_boundary, second_peri);
+                boundary_growth.push_back({ origin, second_peri });
+            }
+            init_boundary(&m_internal, to_polygons(expoly_boundary));
+            m_internal.boundary_growth = boundary_growth;
+        }
 
         // Trim the travel line by the bounding box.
         if (!m_internal.boundaries.empty() && Geometry::liang_barsky_line_clipping(startf, endf, m_internal.bbox)) {
-            travel_intersection_count = avoid_perimeters(m_internal, startf.cast<coord_t>(), endf.cast<coord_t>(), result_pl);
+            travel_intersection_count = avoid_perimeters(m_internal, startf.cast<coord_t>(), endf.cast<coord_t>(), perimeter_spacing, result_pl);
             result_pl.points.front()  = start;
             result_pl.points.back()   = end;
         }
@@ -931,7 +1045,7 @@ Polyline AvoidCrossingPerimeters::travel_to(const GCode &gcodegen, const Point &
 
         // Trim the travel line by the bounding box.
         if (!m_external.boundaries.empty() && Geometry::liang_barsky_line_clipping(startf, endf, m_external.bbox)) {
-            travel_intersection_count = avoid_perimeters(m_external, startf.cast<coord_t>(), endf.cast<coord_t>(), result_pl);
+            travel_intersection_count = avoid_perimeters(m_external, startf.cast<coord_t>(), endf.cast<coord_t>(), 0, result_pl);
             result_pl.points.front()  = start;
             result_pl.points.back()   = end;
         }
diff --git a/src/libslic3r/GCode/AvoidCrossingPerimeters.hpp b/src/libslic3r/GCode/AvoidCrossingPerimeters.hpp
index 307527af2..90cf3281e 100644
--- a/src/libslic3r/GCode/AvoidCrossingPerimeters.hpp
+++ b/src/libslic3r/GCode/AvoidCrossingPerimeters.hpp
@@ -42,11 +42,14 @@ public:
         std::vector<std::vector<float>> boundaries_params;
         // Used for detection of intersection between line and any polygon from boundaries
         EdgeGrid::Grid grid;
+        //used to move the point inside the boundary
+        std::vector<std::pair<ExPolygon, ExPolygons>> boundary_growth;
 
         void clear()
         {
             boundaries.clear();
             boundaries_params.clear();
+            boundary_growth.clear();
         }
     };
 
diff --git a/src/libslic3r/Layer.hpp b/src/libslic3r/Layer.hpp
index ed0c70071..c11ae3100 100644
--- a/src/libslic3r/Layer.hpp
+++ b/src/libslic3r/Layer.hpp
@@ -143,14 +143,6 @@ public:
     void                    restore_untyped_slices();
     // Slices merged into islands, to be used by the elephant foot compensation to trim the individual surfaces with the shrunk merged slices.
     ExPolygons              merged(float offset) const;
-    template <class T> bool any_internal_region_slice_contains(const T &item) const {
-        for (const LayerRegion *layerm : m_regions) if (layerm->slices().any_internal_contains(item)) return true;
-        return false;
-    }
-    template <class T> bool any_bottom_region_slice_contains(const T &item) const {
-        for (const LayerRegion *layerm : m_regions) if (layerm->slices().any_bottom_contains(item)) return true;
-        return false;
-    }
     void                    make_perimeters();
 
     void                    make_milling_post_process();    void                    make_fills() { this->make_fills(nullptr, nullptr); };
diff --git a/src/libslic3r/Line.cpp b/src/libslic3r/Line.cpp
index 762425cd5..de98c3e92 100644
--- a/src/libslic3r/Line.cpp
+++ b/src/libslic3r/Line.cpp
@@ -123,7 +123,9 @@ BoundingBox get_extents(const Lines &lines)
     }
     return bbox;
 
-}Point Line::point_at(double distance) const {
+}
+
+Point Line::point_at(double distance) const {
     Point point;
     double len = this->length();
     point = this->a;
diff --git a/src/libslic3r/SurfaceCollection.hpp b/src/libslic3r/SurfaceCollection.hpp
index cd775764b..12677be72 100644
--- a/src/libslic3r/SurfaceCollection.hpp
+++ b/src/libslic3r/SurfaceCollection.hpp
@@ -19,14 +19,6 @@ public:
     operator ExPolygons() const;
     void simplify(double tolerance);
     void group(std::vector<SurfacesPtr> *retval);
-    template <class T> bool any_internal_contains(const T &item) const {
-        for (const Surface &surface : this->surfaces) if (surface.has_pos_internal() && surface.expolygon.contains(item)) return true;
-        return false;
-    }
-    template <class T> bool any_bottom_contains(const T &item) const {
-        for (const Surface &surface : this->surfaces) if (surface.has_pos_bottom() && surface.expolygon.contains(item)) return true;
-        return false;
-    }
     SurfacesConstPtr filter_by_type(const SurfaceType type) const;
     SurfacesConstPtr filter_by_type_flag(const SurfaceType allowed, const SurfaceType not_allowed = stNone) const;
     SurfacesConstPtr filter_by_types(const SurfaceType *types, int ntypes) const;