New 3D Honeycomb infill pattern (credits: David Eccles (gringer)). #1646

6 files changed, 222 insertions, 1 deletions

diff --git a/Build.PL b/Build.PL
index 335ad0504..8b21c15ba 100644
--- a/Build.PL
+++ b/Build.PL
@@ -16,6 +16,7 @@ my %prereqs = qw(
     Math::PlanePath                 53
     Module::Build::WithXSpp         0.14
     Moo                             1.003001
+    POSIX                           0
     Scalar::Util                    0
     Test::Harness                   0
     Test::More                      0
diff --git a/lib/Slic3r/Fill.pm b/lib/Slic3r/Fill.pm
index 3bdaa3e8f..6c8a76b94 100644
--- a/lib/Slic3r/Fill.pm
+++ b/lib/Slic3r/Fill.pm
@@ -2,6 +2,7 @@ package Slic3r::Fill;
 use Moo;
 
 use Slic3r::ExtrusionPath ':roles';
+use Slic3r::Fill::3DHoneycomb;
 use Slic3r::Fill::ArchimedeanChords;
 use Slic3r::Fill::Base;
 use Slic3r::Fill::Concentric;
@@ -30,6 +31,7 @@ our %FillTypes = (
     line                => 'Slic3r::Fill::Line',
     concentric          => 'Slic3r::Fill::Concentric',
     honeycomb           => 'Slic3r::Fill::Honeycomb',
+    '3dhoneycomb'       => 'Slic3r::Fill::3DHoneycomb',
 );
 
 sub filler {
@@ -213,6 +215,7 @@ sub make_fill {
         
         my $f = $self->filler($filler);
         $f->layer_id($layerm->id);
+        $f->z($layerm->print_z);
         $f->angle(deg2rad($layerm->config->fill_angle));
         my ($params, @polylines) = $f->fill_surface(
             $surface,
diff --git a/lib/Slic3r/Fill/3DHoneycomb.pm b/lib/Slic3r/Fill/3DHoneycomb.pm
new file mode 100644
index 000000000..f67fb9227
--- /dev/null
+++ b/lib/Slic3r/Fill/3DHoneycomb.pm
@@ -0,0 +1,213 @@
+package Slic3r::Fill::3DHoneycomb;
+use Moo;
+
+extends 'Slic3r::Fill::Base';
+
+use POSIX qw(ceil fmod);
+use Slic3r::Geometry qw(scale scaled_epsilon);
+use Slic3r::Geometry::Clipper qw(intersection_pl);
+
+sub fill_surface {
+    my ($self, $surface, %params) = @_;
+    
+    my $expolygon = $surface->expolygon;
+    my $bb = $expolygon->bounding_box;
+    my $size = $bb->size;
+    
+    my $distance = $params{flow}->scaled_spacing / $params{density};
+    
+    # generate pattern
+    my @polylines = map Slic3r::Polyline->new(@$_),
+        makeGrid(
+            scale($self->z),
+            $distance,
+            ceil($size->x / $distance),
+            ceil($size->y / $distance),  #//
+            ($self->layer_id % 2) + 1,
+        );
+    
+    # move pattern in place
+    $_->translate($bb->x_min, $bb->y_min) for @polylines;
+    
+    # clip pattern to boundaries
+    @polylines = @{intersection_pl(\@polylines, \@$expolygon)};
+    
+    # connect lines
+    unless ($params{dont_connect} || !@polylines) {  # prevent calling leftmost_point() on empty collections
+        my ($expolygon_off) = @{$expolygon->offset_ex(scaled_epsilon)};
+        my $collection = Slic3r::Polyline::Collection->new(@polylines);
+        @polylines = ();
+        foreach my $polyline (@{$collection->chained_path_from($collection->leftmost_point, 0)}) {
+            # try to append this polyline to previous one if any
+            if (@polylines) {
+                my $line = Slic3r::Line->new($polylines[-1]->last_point, $polyline->first_point);
+                if ($line->length <= 1.5*$distance && $expolygon_off->contains_line($line)) {
+                    $polylines[-1]->append_polyline($polyline);
+                    next;
+                }
+            }
+            
+            # make a clone before $collection goes out of scope
+            push @polylines, $polyline->clone;
+        }
+    }
+    
+    # TODO: return ExtrusionLoop objects to get better chained paths
+    return { flow => $params{flow} }, @polylines;
+}
+
+
+=head1 DESCRIPTION
+
+Creates a contiguous sequence of points at a specified height that make
+up a horizontal slice of the edges of a space filling truncated
+octahedron tesselation. The octahedrons are oriented so that the
+square faces are in the horizontal plane with edges parallel to the X
+and Y axes.
+
+Credits: David Eccles (gringer).
+
+=head2 makeGrid(z, gridSize, gridWidth, gridHeight, curveType)
+
+Generate a set of curves (array of array of 2d points) that describe a
+horizontal slice of a truncated regular octahedron with a specified
+grid square size.
+
+=cut
+
+sub makeGrid {
+    my ($z, $gridSize, $gridWidth, $gridHeight, $curveType) = @_;
+    my $scaleFactor = $gridSize;
+    my $normalisedZ = $z / $scaleFactor;
+    my @points = makeNormalisedGrid($normalisedZ, $gridWidth, $gridHeight, $curveType);
+    foreach my $lineRef (@points) {
+        foreach my $pointRef (@$lineRef) {
+            $pointRef->[0] *= $scaleFactor;
+            $pointRef->[1] *= $scaleFactor;
+        }
+    }
+    return @points;
+}
+
+=head1 FUNCTIONS
+=cut
+
+=head2 colinearPoints(offset, gridLength)
+
+Generate an array of points that are in the same direction as the
+basic printing line (i.e. Y points for columns, X points for rows)
+
+Note: a negative offset only causes a change in the perpendicular
+direction
+
+=cut
+
+sub colinearPoints {
+    my ($offset, $baseLocation, $gridLength) = @_;
+    
+    my @points = ();
+    push @points, $baseLocation - abs($offset/2);
+    for (my $i = 0; $i < $gridLength; $i++) {
+        push @points, $baseLocation + $i + abs($offset/2);
+        push @points, $baseLocation + ($i+1) - abs($offset/2);
+    }
+    push @points, $baseLocation + $gridLength + abs($offset/2);
+    return @points;
+}
+
+=head2 colinearPoints(offset, baseLocation, gridLength)
+
+Generate an array of points for the dimension that is perpendicular to
+the basic printing line (i.e. X points for columns, Y points for rows)
+
+=cut
+
+sub perpendPoints {
+    my ($offset, $baseLocation, $gridLength) = @_;
+    
+    my @points = ();
+    my $side = 2*(($baseLocation) % 2) - 1;
+    push @points, $baseLocation - $offset/2 * $side;
+    for (my $i = 0; $i < $gridLength; $i++) {
+        $side = 2*(($i+$baseLocation) % 2) - 1;
+        push @points, $baseLocation + $offset/2 * $side;
+        push @points, $baseLocation + $offset/2 * $side;
+    }
+    push @points, $baseLocation - $offset/2 * $side;
+    
+    return @points;
+}
+
+=head2 trim(pointArrayRef, minX, minY, maxX, maxY)
+
+Trims an array of points to specified rectangular limits. Point
+components that are outside these limits are set to the limits.
+
+=cut
+
+sub trim {
+    my ($pointArrayRef, $minX, $minY, $maxX, $maxY) = @_;
+  
+    foreach (@$pointArrayRef) {
+        $_->[0] = ($_->[0] < $minX) ? $minX : (($_->[0] > $maxX) ? $maxX : $_->[0]);
+        $_->[1] = ($_->[1] < $minY) ? $minY : (($_->[1] > $maxY) ? $maxY : $_->[1]);
+    }
+}
+
+=head2 makeNormalisedGrid(z, gridWidth, gridHeight, curveType)
+
+Generate a set of curves (array of array of 2d points) that describe a
+horizontal slice of a truncated regular octahedron with edge length 1.
+
+curveType specifies which lines to print, 1 for vertical lines
+(columns), 2 for horizontal lines (rows), and 3 for both.
+
+=cut
+
+sub makeNormalisedGrid {
+    my ($z, $gridWidth, $gridHeight, $curveType) = @_;
+    
+    # offset required to create a regular octagram
+    my $octagramGap = 1 / (1 + sqrt(2));
+    
+    # sawtooth wave function for range f($z) = [-$octagramGap .. $octagramGap]
+    my $offset = (abs((fmod($z * sqrt(2), 4)) - 2) - 1) * $octagramGap;
+    
+    my @points = ();
+    if (($curveType & 1) != 0) {
+        for (my $x = 0; $x <= $gridWidth; $x++) {
+            my @xPoints = perpendPoints($offset, $x, $gridHeight);
+            my @yPoints = colinearPoints($offset, 0, $gridHeight);
+            # This is essentially @newPoints = zip(@xPoints, @yPoints)
+            my @newPoints = map [ $xPoints[$_], $yPoints[$_] ], 0..$#xPoints;
+            
+            # trim points to grid edges
+            #trim(\@newPoints, 0, 0, $gridWidth, $gridHeight);
+            
+            if ($x % 2 == 0){
+                push @points, [ @newPoints ];
+            } else {
+                push @points, [ reverse @newPoints ];
+            }
+        }
+    }
+    if (($curveType & 2) != 0) {
+        for (my $y = 0; $y <= $gridHeight; $y++) {
+            my @xPoints = colinearPoints($offset, 0, $gridWidth);
+            my @yPoints = perpendPoints($offset, $y, $gridWidth);
+            my @newPoints = map [ $xPoints[$_], $yPoints[$_] ], 0..$#xPoints;
+            
+            # trim points to grid edges
+            #trim(\@newPoints, 0, 0, $gridWidth, $gridHeight);
+            
+            if ($y % 2 == 0) {
+                push @points, [ @newPoints ];
+            } else {
+                push @points, [ reverse @newPoints ];
+            }
+        }
+    }
+    return @points;
+}
+
+1;
diff --git a/lib/Slic3r/Fill/Base.pm b/lib/Slic3r/Fill/Base.pm
index 21a802058..34b47243b 100644
--- a/lib/Slic3r/Fill/Base.pm
+++ b/lib/Slic3r/Fill/Base.pm
@@ -2,6 +2,7 @@ package Slic3r::Fill::Base;
 use Moo;
 
 has 'layer_id'            => (is => 'rw');
+has 'z'                   => (is => 'rw'); # in unscaled coordinates
 has 'angle'               => (is => 'rw'); # in radians, ccw, 0 = East
 has 'bounding_box'        => (is => 'ro', required => 0);  # Slic3r::Geometry::BoundingBox object
 
diff --git a/xs/src/PrintConfig.cpp b/xs/src/PrintConfig.cpp
index 24b169ad8..2e9d8a6bf 100644
--- a/xs/src/PrintConfig.cpp
+++ b/xs/src/PrintConfig.cpp
@@ -271,6 +271,7 @@ PrintConfigDef::build_def() {
     Options["fill_pattern"].enum_values.push_back("line");
     Options["fill_pattern"].enum_values.push_back("concentric");
     Options["fill_pattern"].enum_values.push_back("honeycomb");
+    Options["fill_pattern"].enum_values.push_back("3dhoneycomb");
     Options["fill_pattern"].enum_values.push_back("hilbertcurve");
     Options["fill_pattern"].enum_values.push_back("archimedeanchords");
     Options["fill_pattern"].enum_values.push_back("octagramspiral");
@@ -278,6 +279,7 @@ PrintConfigDef::build_def() {
     Options["fill_pattern"].enum_labels.push_back("line");
     Options["fill_pattern"].enum_labels.push_back("concentric");
     Options["fill_pattern"].enum_labels.push_back("honeycomb");
+    Options["fill_pattern"].enum_labels.push_back("3D honeycomb");
     Options["fill_pattern"].enum_labels.push_back("hilbertcurve (slow)");
     Options["fill_pattern"].enum_labels.push_back("archimedeanchords (slow)");
     Options["fill_pattern"].enum_labels.push_back("octagramspiral (slow)");
diff --git a/xs/src/PrintConfig.hpp b/xs/src/PrintConfig.hpp
index 3b919c03c..cdc3d7173 100644
--- a/xs/src/PrintConfig.hpp
+++ b/xs/src/PrintConfig.hpp
@@ -10,7 +10,7 @@ enum GCodeFlavor {
 };
 
 enum InfillPattern {
-    ipRectilinear, ipLine, ipConcentric, ipHoneycomb,
+    ipRectilinear, ipLine, ipConcentric, ipHoneycomb, ip3DHoneycomb,
     ipHilbertCurve, ipArchimedeanChords, ipOctagramSpiral,
 };
 
@@ -39,6 +39,7 @@ template<> inline t_config_enum_values ConfigOptionEnum<InfillPattern>::get_enum
     keys_map["line"]                = ipLine;
     keys_map["concentric"]          = ipConcentric;
     keys_map["honeycomb"]           = ipHoneycomb;
+    keys_map["3dhoneycomb"]         = ip3DHoneycomb;
     keys_map["hilbertcurve"]        = ipHilbertCurve;
     keys_map["archimedeanchords"]   = ipArchimedeanChords;
     keys_map["octagramspiral"]      = ipOctagramSpiral;