Add scattered rectilinear infill method for optical diffusers

5 files changed, 154 insertions, 49 deletions

diff --git a/src/libslic3r/Fill/FillBase.cpp b/src/libslic3r/Fill/FillBase.cpp
index 1edfcb8bc..61fe00375 100644
--- a/src/libslic3r/Fill/FillBase.cpp
+++ b/src/libslic3r/Fill/FillBase.cpp
@@ -28,6 +28,7 @@ Fill* Fill::new_from_type(const InfillPattern type)
     case ipGyroid:              return new FillGyroid();
     case ipRectilinear:         return new FillRectilinear2();
 //  case ipRectilinear:         return new FillRectilinear();
+    case ipScatteredRectilinear:return new FillScatteredRectilinear();
     case ipLine:                return new FillLine();
     case ipGrid:                return new FillGrid2();
     case ipTriangles:           return new FillTriangles();
diff --git a/src/libslic3r/Fill/FillRectilinear2.cpp b/src/libslic3r/Fill/FillRectilinear2.cpp
index 545428b03..df4f9f42b 100644
--- a/src/libslic3r/Fill/FillRectilinear2.cpp
+++ b/src/libslic3r/Fill/FillRectilinear2.cpp
@@ -6,6 +6,9 @@
 #include <limits>
 
 #include <boost/static_assert.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_int_distribution.hpp>
+#include <boost/random/uniform_real_distribution.hpp>
 
 #include "../ExtrusionEntityCollection.hpp"
 #include "../ClipperUtils.hpp"
@@ -759,55 +762,9 @@ enum DirectionMask
     DIR_BACKWARD = 2
 };
 
-bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillParams &params, float angleBase, float pattern_shift, Polylines &polylines_out)
+// Intersect a set of equally spaced vertical lines with expolygon.
+std::vector<SegmentedIntersectionLine> FillRectilinear2::_vert_lines_for_polygon(const ExPolygonWithOffset &poly_with_offset, const BoundingBox &bounding_box, const FillParams &params, coord_t line_spacing) const
 {
-    // At the end, only the new polylines will be rotated back.
-    size_t n_polylines_out_initial = polylines_out.size();
-
-    // Shrink the input polygon a bit first to not push the infill lines out of the perimeters.
-//    const float INFILL_OVERLAP_OVER_SPACING = 0.3f;
-    const float INFILL_OVERLAP_OVER_SPACING = 0.45f;
-    assert(INFILL_OVERLAP_OVER_SPACING > 0 && INFILL_OVERLAP_OVER_SPACING < 0.5f);
-
-    // Rotate polygons so that we can work with vertical lines here
-    std::pair<float, Point> rotate_vector = this->_infill_direction(surface);
-    rotate_vector.first += angleBase;
-
-    assert(params.density > 0.0001f);
-    coord_t line_spacing = coord_t(scale_(this->spacing) / params.density);
-
-    // On the polygons of poly_with_offset, the infill lines will be connected.
-    ExPolygonWithOffset poly_with_offset(
-        surface->expolygon, 
-        - rotate_vector.first, 
-        scale_(0 - (0.5 - INFILL_OVERLAP_OVER_SPACING) * this->spacing),
-        scale_(0 - 0.5 * this->spacing));
-    if (poly_with_offset.n_contours_inner == 0) {
-        // Not a single infill line fits.
-        //FIXME maybe one shall trigger the gap fill here?
-        return true;
-    }
-
-    BoundingBox bounding_box = poly_with_offset.bounding_box_src();
-
-    // define flow spacing according to requested density
-    if (params.full_infill() && !params.dont_adjust) {
-        line_spacing = this->_adjust_solid_spacing(bounding_box.size()(0), line_spacing);
-        this->spacing = unscale<double>(line_spacing);
-    } else {
-        // extend bounding box so that our pattern will be aligned with other layers
-        // Transform the reference point to the rotated coordinate system.
-        Point refpt = rotate_vector.second.rotated(- rotate_vector.first);
-        // _align_to_grid will not work correctly with positive pattern_shift.
-        coord_t pattern_shift_scaled = coord_t(scale_(pattern_shift)) % line_spacing;
-        refpt(0) -= (pattern_shift_scaled >= 0) ? pattern_shift_scaled : (line_spacing + pattern_shift_scaled);
-        bounding_box.merge(_align_to_grid(
-            bounding_box.min, 
-            Point(line_spacing, line_spacing), 
-            refpt));
-    }
-
-    // Intersect a set of euqally spaced vertical lines wiht expolygon.
     // n_vlines = ceil(bbox_width / line_spacing)
     size_t  n_vlines = (bounding_box.max(0) - bounding_box.min(0) + line_spacing - 1) / line_spacing;
 	coord_t x0 = bounding_box.min(0);
@@ -902,6 +859,65 @@ bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillP
         }
     }
 
+    return segs;
+}
+
+coord_t FillRectilinear2::_line_spacing_for_density(float density) const
+{
+    return coord_t(scale_(this->spacing) / density);
+}
+
+bool FillRectilinear2::fill_surface_by_lines(const Surface *surface, const FillParams &params, float angleBase, float pattern_shift, Polylines &polylines_out)
+{
+    // At the end, only the new polylines will be rotated back.
+    size_t n_polylines_out_initial = polylines_out.size();
+
+    // Shrink the input polygon a bit first to not push the infill lines out of the perimeters.
+//    const float INFILL_OVERLAP_OVER_SPACING = 0.3f;
+    const float INFILL_OVERLAP_OVER_SPACING = 0.45f;
+    assert(INFILL_OVERLAP_OVER_SPACING > 0 && INFILL_OVERLAP_OVER_SPACING < 0.5f);
+
+    // Rotate polygons so that we can work with vertical lines here
+    std::pair<float, Point> rotate_vector = this->_infill_direction(surface);
+    rotate_vector.first += angleBase;
+
+    assert(params.density > 0.0001f && params.density <= 1.f);
+    coord_t line_spacing = _line_spacing_for_density(params.density);
+
+    // On the polygons of poly_with_offset, the infill lines will be connected.
+    ExPolygonWithOffset poly_with_offset(
+        surface->expolygon, 
+        - rotate_vector.first, 
+        scale_(this->overlap - (0.5 - INFILL_OVERLAP_OVER_SPACING) * this->spacing),
+        scale_(this->overlap - 0.5 * this->spacing));
+    if (poly_with_offset.n_contours_inner == 0) {
+        // Not a single infill line fits.
+        //FIXME maybe one shall trigger the gap fill here?
+        return true;
+    }
+
+    BoundingBox bounding_box = poly_with_offset.bounding_box_src();
+
+    // define flow spacing according to requested density
+    if (params.full_infill() && !params.dont_adjust) {
+        line_spacing = this->_adjust_solid_spacing(bounding_box.size()(0), line_spacing);
+        this->spacing = unscale<double>(line_spacing);
+    } else {
+        // extend bounding box so that our pattern will be aligned with other layers
+        // Transform the reference point to the rotated coordinate system.
+        Point refpt = rotate_vector.second.rotated(- rotate_vector.first);
+        // _align_to_grid will not work correctly with positive pattern_shift.
+        coord_t pattern_shift_scaled = coord_t(scale_(pattern_shift)) % line_spacing;
+        refpt(0) -= (pattern_shift_scaled >= 0) ? pattern_shift_scaled : (line_spacing + pattern_shift_scaled);
+        bounding_box.merge(_align_to_grid(
+            bounding_box.min, 
+            Point(line_spacing, line_spacing), 
+            refpt));
+    }
+
+    // Intersect a set of equally spaced vertical lines with expolygon.
+    std::vector<SegmentedIntersectionLine> segs = _vert_lines_for_polygon(poly_with_offset, bounding_box, params, line_spacing);
+
     // Sort the intersections along their segments, specify the intersection types.
     for (size_t i_seg = 0; i_seg < segs.size(); ++ i_seg) {
         SegmentedIntersectionLine &sil = segs[i_seg];
@@ -1569,4 +1585,68 @@ FillRectilinear2Peri::fill_surface_extrusion(const Surface *surface, const FillP
 
 }
 
+/* Returns a float uniformly distributed in the range [0..1.0) using the given integer as the seed
+*
+* N.B. calling this is super slow as it must rebuild the initial state for a Mersenne Twister with each call, so
+* don't call this in a loop if you can avoid it.
+*/
+static float randomFloatFromSeed(uint32_t x)
+{
+    boost::random::mt19937 rng(x);
+    boost::random::uniform_real_distribution<> dist;
+
+    return (float) dist(rng);
+}
+
+float FillScatteredRectilinear::_layer_angle(size_t idx) const
+{
+    // Angle chosen at random using the layer index as a key
+    return randomFloatFromSeed((uint32_t) idx) * (float) M_PI;
+}
+
+coord_t FillScatteredRectilinear::_line_spacing_for_density(float density) const
+{
+    /* The density argument is ignored, we first generate lines at 100% density, then prune some generated lines
+     * later to achieve the target density
+     */
+    (void) density;
+
+    return coord_t(scale_(this->spacing) / 1.0);
+}
+
+Polylines FillScatteredRectilinear::fill_surface(const Surface *surface, const FillParams &params)
+{
+    Polylines polylines_out;
+
+    // Offset the pattern randomly using the current layer index as the generator
+    float offset = randomFloatFromSeed((uint32_t) layer_id) * 0.5f * (float) this->spacing;
+
+    if (!fill_surface_by_lines(surface, params, 0.f, offset, polylines_out)) {
+        printf("FillScatteredRectilinear::fill_surface() failed to fill a region.\n");
+    }
+    return polylines_out;
+}
+
+std::vector<SegmentedIntersectionLine> FillScatteredRectilinear::_vert_lines_for_polygon(const ExPolygonWithOffset &poly_with_offset, const BoundingBox &bounding_box, const FillParams &params, coord_t line_spacing) const
+{
+    std::vector<SegmentedIntersectionLine> segs = FillRectilinear2::_vert_lines_for_polygon(poly_with_offset, bounding_box, params, line_spacing);
+
+    if (!params.full_infill()) {
+        boost::random::mt19937 rng((uint32_t) layer_id);
+        boost::random::uniform_real_distribution<> dist;
+
+        // Remove generated lines with a probability that'll achieve the required density on average
+        for (auto iter = segs.begin(); iter != segs.end(); ) {
+            if (dist(rng) >= params.density) {
+                iter = segs.erase(iter);
+            } else {
+                ++iter;
+            }
+        }
+    }
+
+    return segs;
+}
+
+
 } // namespace Slic3r
diff --git a/src/libslic3r/Fill/FillRectilinear2.hpp b/src/libslic3r/Fill/FillRectilinear2.hpp
index 3457fad95..21afacc71 100644
--- a/src/libslic3r/Fill/FillRectilinear2.hpp
+++ b/src/libslic3r/Fill/FillRectilinear2.hpp
@@ -8,6 +8,8 @@
 namespace Slic3r {
 
 class Surface;
+class SegmentedIntersectionLine;
+struct ExPolygonWithOffset;
 
 class FillRectilinear2 : public Fill
 {
@@ -17,6 +19,9 @@ public:
     virtual Polylines fill_surface(const Surface *surface, const FillParams &params);
 
 protected:
+    virtual std::vector<SegmentedIntersectionLine> _vert_lines_for_polygon(const ExPolygonWithOffset &poly_with_offset, const BoundingBox &bounding_box, const FillParams &params, coord_t line_spacing) const;
+    virtual coord_t _line_spacing_for_density(float density) const;
+
 	bool fill_surface_by_lines(const Surface *surface, const FillParams &params, float angleBase, float pattern_shift, Polylines &polylines_out);
 };
 
@@ -81,6 +86,22 @@ public:
 
 };
 
+
+class FillScatteredRectilinear : public FillRectilinear2
+{
+public:
+    virtual Fill* clone() const { return new FillScatteredRectilinear(*this); };
+    virtual ~FillScatteredRectilinear() {}
+virtual Polylines fill_surface(const Surface *surface, const FillParams &params);
+
+protected:
+    virtual float _layer_angle(size_t idx) const;
+    virtual std::vector<SegmentedIntersectionLine> _vert_lines_for_polygon(const ExPolygonWithOffset &poly_with_offset, const BoundingBox &bounding_box, const FillParams &params, coord_t line_spacing) const;
+    virtual coord_t _line_spacing_for_density(float density) const;
+};
+
+
+
 }; // namespace Slic3r
 
 #endif // slic3r_FillRectilinear2_hpp_
diff --git a/src/libslic3r/PrintConfig.cpp b/src/libslic3r/PrintConfig.cpp
index 3b55e7ab3..32d4ee101 100644
--- a/src/libslic3r/PrintConfig.cpp
+++ b/src/libslic3r/PrintConfig.cpp
@@ -955,6 +955,7 @@ void PrintConfigDef::init_fff_params()
     def->enum_values.push_back("hilbertcurve");
     def->enum_values.push_back("archimedeanchords");
     def->enum_values.push_back("octagramspiral");
+    def->enum_values.push_back("scatteredrectilinear");
     def->enum_labels.push_back(L("Rectilinear"));
     def->enum_labels.push_back(L("Grid"));
     def->enum_labels.push_back(L("Triangles"));
@@ -968,6 +969,7 @@ void PrintConfigDef::init_fff_params()
     def->enum_labels.push_back(L("Hilbert Curve"));
     def->enum_labels.push_back(L("Archimedean Chords"));
     def->enum_labels.push_back(L("Octagram Spiral"));
+    def->enum_labels.push_back(L("Scattered Rectilinear"));
     def->default_value = new ConfigOptionEnum<InfillPattern>(ipStars);
 
     def = this->add("first_layer_acceleration", coFloat);
diff --git a/src/libslic3r/PrintConfig.hpp b/src/libslic3r/PrintConfig.hpp
index be1bc9f1f..607ca2596 100644
--- a/src/libslic3r/PrintConfig.hpp
+++ b/src/libslic3r/PrintConfig.hpp
@@ -42,7 +42,7 @@ enum PrintHostType {
 enum InfillPattern {
     ipRectilinear, ipGrid, ipTriangles, ipStars, ipCubic, ipLine, ipConcentric, ipHoneycomb, ip3DHoneycomb,
     ipGyroid, ipHilbertCurve, ipArchimedeanChords, ipOctagramSpiral, ipSmooth, ipSmoothHilbert, ipSmoothTriple,
-    ipRectiWithPerimeter, ipConcentricGapFill
+    ipRectiWithPerimeter, ipConcentricGapFill, ipScatteredRectilinear
 };
 
 enum SupportMaterialPattern {
@@ -122,6 +122,7 @@ template<> inline const t_config_enum_values& ConfigOptionEnum<InfillPattern>::g
         keys_map["smoothtriple"]        = ipSmoothTriple;
         keys_map["smoothhilbert"]       = ipSmoothHilbert;
         keys_map["rectiwithperimeter"]  = ipRectiWithPerimeter;
+        keys_map["scatteredrectilinear"]= ipScatteredRectilinear;
     }
     return keys_map;
 }