From dba1179708a88c425be5374666e6d68ec64ed7c1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Luk=C3=A1=C5=A1=20Hejl?= Date: Fri, 10 Jun 2022 15:19:26 +0200 Subject: Fixed an issue when the Lightning infill stuck in an infinite loop on some models. Cased by two sampled points closer than chosen spacing. --- src/libslic3r/Fill/FillRectilinear.cpp | 20 +++++++++------- src/libslic3r/Fill/FillRectilinear.hpp | 6 ++--- src/libslic3r/Fill/Lightning/DistanceField.cpp | 33 +++++++++++++++++++++++++- src/libslic3r/Fill/Lightning/DistanceField.hpp | 6 +++++ 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 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 +#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 &unsupported_points, const Points &points = {}) +{ + coordf_t stroke_width = scaled(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 &unsupported_points, const Points &points); +#endif }; } // namespace Slic3r::FillLightning -- cgit v1.2.3