Fixed an issue when the Lightning infill stuck in an infinite loop on some models.

Cased by two sampled points closer than chosen spacing.

4 files changed, 53 insertions, 12 deletions

diff --git a/src/libslic3r/Fill/FillRectilinear.cpp b/src/libslic3r/Fill/FillRectilinear.cpp
index 264ae8a59..ba7461c5f 100644
--- a/src/libslic3r/Fill/FillRectilinear.cpp
+++ b/src/libslic3r/Fill/FillRectilinear.cpp
@@ -3043,14 +3043,18 @@ Polylines FillSupportBase::fill_surface(const Surface *surface, const FillParams
     return polylines_out;
 }
 
-Points sample_grid_pattern(const ExPolygon &expolygon, coord_t spacing)
+// Lightning infill assumes that the distance between any two sampled points is always
+// at least equal to the value of spacing. To meet this assumption, we need to use
+// BoundingBox for whole layers instead of bounding box just around processing ExPolygon.
+// Using just BoundingBox around processing ExPolygon could produce two points closer
+// than spacing (in cases where two ExPolygon are closer than spacing).
+Points sample_grid_pattern(const ExPolygon &expolygon, coord_t spacing, const BoundingBox &global_bounding_box)
 {
     ExPolygonWithOffset poly_with_offset(expolygon, 0, 0, 0);
-    BoundingBox bounding_box = poly_with_offset.bounding_box_src();
     std::vector<SegmentedIntersectionLine> segs = slice_region_by_vertical_lines(
         poly_with_offset, 
-        (bounding_box.max.x() - bounding_box.min.x() + spacing - 1) / spacing, 
-        bounding_box.min.x(),
+        (global_bounding_box.max.x() - global_bounding_box.min.x() + spacing - 1) / spacing,
+        global_bounding_box.min.x(),
         spacing);
 
     Points out;
@@ -3066,17 +3070,17 @@ Points sample_grid_pattern(const ExPolygon &expolygon, coord_t spacing)
     return out;
 }
 
-Points sample_grid_pattern(const ExPolygons &expolygons, coord_t spacing)
+Points sample_grid_pattern(const ExPolygons &expolygons, coord_t spacing, const BoundingBox &global_bounding_box)
 {
     Points out;
     for (const ExPolygon &expoly : expolygons)
-        append(out, sample_grid_pattern(expoly, spacing));
+        append(out, sample_grid_pattern(expoly, spacing, global_bounding_box));
     return out;
 }
 
-Points sample_grid_pattern(const Polygons &polygons, coord_t spacing)
+Points sample_grid_pattern(const Polygons &polygons, coord_t spacing, const BoundingBox &global_bounding_box)
 {
-    return sample_grid_pattern(union_ex(polygons), spacing);
+    return sample_grid_pattern(union_ex(polygons), spacing, global_bounding_box);
 }
 
 } // namespace Slic3r
diff --git a/src/libslic3r/Fill/FillRectilinear.hpp b/src/libslic3r/Fill/FillRectilinear.hpp
index ba735dd02..0a6c976ad 100644
--- a/src/libslic3r/Fill/FillRectilinear.hpp
+++ b/src/libslic3r/Fill/FillRectilinear.hpp
@@ -109,9 +109,9 @@ protected:
     float _layer_angle(size_t idx) const override { return 0.f; }
 };
 
-Points sample_grid_pattern(const ExPolygon &expolygon, coord_t spacing);
-Points sample_grid_pattern(const ExPolygons &expolygons, coord_t spacing);
-Points sample_grid_pattern(const Polygons &polygons, coord_t spacing);
+Points sample_grid_pattern(const ExPolygon &expolygon, coord_t spacing, const BoundingBox &global_bounding_box);
+Points sample_grid_pattern(const ExPolygons &expolygons, coord_t spacing, const BoundingBox &global_bounding_box);
+Points sample_grid_pattern(const Polygons &polygons, coord_t spacing, const BoundingBox &global_bounding_box);
 
 } // namespace Slic3r
 
diff --git a/src/libslic3r/Fill/Lightning/DistanceField.cpp b/src/libslic3r/Fill/Lightning/DistanceField.cpp
index ef407664c..0cbfa9af5 100644
--- a/src/libslic3r/Fill/Lightning/DistanceField.cpp
+++ b/src/libslic3r/Fill/Lightning/DistanceField.cpp
@@ -7,11 +7,34 @@
 
 #include <tbb/parallel_for.h>
 
+#ifdef LIGHTNING_DISTANCE_FIELD_DEBUG_OUTPUT
+#include "../../SVG.hpp"
+#endif
+
 namespace Slic3r::FillLightning
 {
 
 constexpr coord_t radius_per_cell_size = 6;  // The cell-size should be small compared to the radius, but not so small as to be inefficient.
 
+#ifdef LIGHTNING_DISTANCE_FIELD_DEBUG_OUTPUT
+void export_distance_field_to_svg(const std::string &path, const Polygons &outline, const Polygons &overhang, const std::list<DistanceField::UnsupportedCell> &unsupported_points, const Points &points = {})
+{
+    coordf_t    stroke_width = scaled<coordf_t>(0.01);
+    BoundingBox bbox         = get_extents(outline);
+
+    bbox.offset(SCALED_EPSILON);
+    SVG svg(path, bbox);
+    svg.draw_outline(outline, "green", stroke_width);
+    svg.draw_outline(overhang, "blue", stroke_width);
+
+    for (const DistanceField::UnsupportedCell &cell : unsupported_points)
+        svg.draw(cell.loc, "cyan", coord_t(stroke_width));
+
+    for (const Point &pt : points)
+        svg.draw(pt, "red", coord_t(stroke_width));
+}
+#endif
+
 DistanceField::DistanceField(const coord_t& radius, const Polygons& current_outline, const BoundingBox& current_outlines_bbox, const Polygons& current_overhang) :
     m_cell_size(radius / radius_per_cell_size),
     m_supporting_radius(radius),
@@ -19,8 +42,9 @@ DistanceField::DistanceField(const coord_t& radius, const Polygons& current_outl
 {
     m_supporting_radius2 = Slic3r::sqr(int64_t(radius));
     // Sample source polygons with a regular grid sampling pattern.
+    const BoundingBox overhang_bbox = get_extents(current_overhang);
     for (const ExPolygon &expoly : union_ex(current_overhang)) {
-        const Points sampled_points               = sample_grid_pattern(expoly, m_cell_size);
+        const Points sampled_points               = sample_grid_pattern(expoly, m_cell_size, overhang_bbox);
         const size_t unsupported_points_prev_size = m_unsupported_points.size();
         m_unsupported_points.resize(unsupported_points_prev_size + sampled_points.size());
 
@@ -59,6 +83,13 @@ DistanceField::DistanceField(const coord_t& radius, const Polygons& current_outl
     // Because the distance between two points is at least one axis equal to m_cell_size, every cell
     // in m_unsupported_points_grid contains exactly one point.
     assert(m_unsupported_points.size() == m_unsupported_points_grid.size());
+
+#ifdef LIGHTNING_DISTANCE_FIELD_DEBUG_OUTPUT
+    {
+        static int iRun = 0;
+        export_distance_field_to_svg(debug_out_path("FillLightning-DistanceField-%d.svg", iRun++), current_outline, current_overhang, m_unsupported_points);
+    }
+#endif
 }
 
 void DistanceField::update(const Point& to_node, const Point& added_leaf)
diff --git a/src/libslic3r/Fill/Lightning/DistanceField.hpp b/src/libslic3r/Fill/Lightning/DistanceField.hpp
index 1a47ee6ca..007ac235e 100644
--- a/src/libslic3r/Fill/Lightning/DistanceField.hpp
+++ b/src/libslic3r/Fill/Lightning/DistanceField.hpp
@@ -8,6 +8,8 @@
 #include "../../Point.hpp"
 #include "../../Polygon.hpp"
 
+//#define LIGHTNING_DISTANCE_FIELD_DEBUG_OUTPUT
+
 namespace Slic3r::FillLightning
 {
 
@@ -196,6 +198,10 @@ protected:
     Point from_grid_point(const Point &point) const {
         return point * m_cell_size + m_unsupported_points_bbox.min;
     }
+
+#ifdef LIGHTNING_DISTANCE_FIELD_DEBUG_OUTPUT
+    friend void export_distance_field_to_svg(const std::string &path, const Polygons &outline, const Polygons &overhang, const std::list<DistanceField::UnsupportedCell> &unsupported_points, const Points &points);
+#endif
 };
 
 } // namespace Slic3r::FillLightning