New --fill-every-layers option to get high accuracy on external surfaces while speeding up infill

16 files changed, 177 insertions, 43 deletions

diff --git a/MANIFEST b/MANIFEST
index b3ae6257b..822802e62 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -1,25 +1,42 @@
 Build.PL
 lib/Slic3r.pm
+lib/Slic3r/Config.pm
+lib/Slic3r/ExPolygon.pm
 lib/Slic3r/Extruder.pm
 lib/Slic3r/ExtrusionLoop.pm
 lib/Slic3r/ExtrusionPath.pm
 lib/Slic3r/ExtrusionPath/Collection.pm
 lib/Slic3r/Fill.pm
+lib/Slic3r/Fill/Base.pm
 lib/Slic3r/Fill/Rectilinear.pm
+lib/Slic3r/Fill/Rectilinear2.pm
 lib/Slic3r/Geometry.pm
+lib/Slic3r/Geometry/Clipper.pm
 lib/Slic3r/Geometry/DouglasPeucker.pm
+lib/Slic3r/GUI.pm
+lib/Slic3r/GUI/OptionsGroup.pm
+lib/Slic3r/GUI/SkeinPanel.pm
 lib/Slic3r/Layer.pm
 lib/Slic3r/Line.pm
+lib/Slic3r/Line/FacetEdge.pm
+lib/Slic3r/Line/FacetEdge/Bottom.pm
+lib/Slic3r/Line/FacetEdge/Top.pm
 lib/Slic3r/Perimeter.pm
 lib/Slic3r/Point.pm
+lib/Slic3r/Polygon.pm
 lib/Slic3r/Polyline.pm
 lib/Slic3r/Polyline/Closed.pm
 lib/Slic3r/Print.pm
+lib/Slic3r/Skein.pm
 lib/Slic3r/STL.pm
 lib/Slic3r/Surface.pm
-lib/Slic3r/Surface/Collection.pm
+lib/Slic3r/Surface/Bridge.pm
 lib/Slic3r/SVG.pm
 MANIFEST			This list of files
 README.markdown
 slic3r.pl
 t/clean_polylines.t
+t/clipper.t
+t/geometry.t
+t/polyclip.t
+t/stl.t
diff --git a/README.markdown b/README.markdown
index a713a243c..4aea5df45 100644
--- a/README.markdown
+++ b/README.markdown
@@ -40,7 +40,7 @@ Slic3r current features are:
 * retraction;
 * skirt (with rounded corners);
 * use relative or absolute extrusion commands;
-* high-res perimeters (like the "Skin" plugin for Skeinforge);
+* infill every N layers (like the "Skin" plugin for Skeinforge);
 * detect optimal infill direction for bridges;
 * save configuration profiles;
 * center print around bed center point;
@@ -53,6 +53,7 @@ Roadmap includes the following goals:
 
 * output some statistics;
 * support material for internal perimeters;
+* new and better GUI;
 * cool;
 * other fill patterns.
 
@@ -111,9 +112,8 @@ The author is Alessandro Ranellucci (me).
         
       Accuracy options:
         --layer-height      Layer height in mm (default: 0.4)
-        --high-res-perimeters
-                            Print perimeters at half layer height to get surface accuracy
-                            (default: disabled)
+        --infill-every-layers
+                            Infill every N layers (default: 1)
       
       Print options:
         --perimeters        Number of perimeters/horizontal skins (range: 1+, 
diff --git a/lib/Slic3r.pm b/lib/Slic3r.pm
index 3310e9ed9..03deb859e 100644
--- a/lib/Slic3r.pm
+++ b/lib/Slic3r.pm
@@ -50,7 +50,7 @@ our $bottom_layer_speed_ratio   = 0.3;
 # accuracy options
 our $resolution             = 0.00000001;
 our $layer_height           = 0.4;
-our $high_res_perimeters    = 0;
+our $infill_every_layers    = 1;
 our $thickness_ratio        = 1;
 our $flow_width;
 
diff --git a/lib/Slic3r/Config.pm b/lib/Slic3r/Config.pm
index 05363b2a0..79e3a764e 100644
--- a/lib/Slic3r/Config.pm
+++ b/lib/Slic3r/Config.pm
@@ -64,9 +64,9 @@ our $Options = {
         label   => 'Layer height (mm)',
         type    => 'f',
     },
-    'high_res_perimeters' => {
-        label   => 'High-res perimeters',
-        type    => 'bool',
+    'infill_every_layers' => {
+        label   => 'Infill every N layers',
+        type    => 'i',
     },
     
     # print options
@@ -262,6 +262,12 @@ sub validate {
     die "Invalid value for --fill-density\n"
         if $Slic3r::fill_density < 0 || $Slic3r::fill_density > 1;
     
+    # --infill-every-layers
+    die "Invalid value for --infill-every-layers\n"
+        if $Slic3r::infill_every_layers !~ /^\d+$/ || $Slic3r::infill_every_layers < 1;
+    die "Maximum infill thickness can't exceed nozzle diameter\n"
+        if $Slic3r::infill_every_layers * $Slic3r::layer_height > $Slic3r::nozzle_diameter;
+    
     # --scale
     die "Invalid value for --scale\n"
         if $Slic3r::scale <= 0;
diff --git a/lib/Slic3r/Extruder.pm b/lib/Slic3r/Extruder.pm
index 31a25243c..a03880f04 100644
--- a/lib/Slic3r/Extruder.pm
+++ b/lib/Slic3r/Extruder.pm
@@ -84,7 +84,7 @@ sub extrude {
     
     # compensate retraction
     $gcode .= $self->unretract if $self->retracted;
-    
+    XXX "yes!\n" if $path->depth_layers > 1;
     # extrude while going to next points
     foreach my $line ($path->lines) {
         # calculate how much filament to drive into the extruder
@@ -93,7 +93,8 @@ sub extrude {
             * (($Slic3r::nozzle_diameter**2) / ($Slic3r::filament_diameter ** 2))
             * $Slic3r::thickness_ratio 
             * $self->flow_ratio
-            * $Slic3r::filament_packing_density;
+            * $Slic3r::filament_packing_density
+            * $path->depth_layers;
         
         $gcode .= $self->G1($line->b, undef, $e, $description);
     }
diff --git a/lib/Slic3r/ExtrusionPath.pm b/lib/Slic3r/ExtrusionPath.pm
index 975167e29..dfc5a83f2 100644
--- a/lib/Slic3r/ExtrusionPath.pm
+++ b/lib/Slic3r/ExtrusionPath.pm
@@ -3,6 +3,10 @@ use Moo;
 
 extends 'Slic3r::Polyline';
 
+# this integer represents the vertical thickness of the extrusion
+# expressed in layers
+has 'depth_layers' => (is => 'ro', default => sub {1});
+
 use constant PI => 4 * atan2(1, 1);
 
 sub clip_end {
diff --git a/lib/Slic3r/Fill.pm b/lib/Slic3r/Fill.pm
index 1f52bbbab..0703fff6a 100644
--- a/lib/Slic3r/Fill.pm
+++ b/lib/Slic3r/Fill.pm
@@ -48,14 +48,20 @@ sub make_fill {
                 $filler = 'rectilinear';
             }
             
-            push @path_collection, $self->fillers->{$filler}->fill_surface($surface,
+            my @paths = $self->fillers->{$filler}->fill_surface(
+                $surface,
                 density => $density,
             );
+            
+            push @path_collection, map Slic3r::ExtrusionPath->cast(
+                [ @$_ ],
+                depth_layers => $surface->depth_layers,
+            ), @paths;
         }
         
         # save into layer
         push @{ $layer->fills }, Slic3r::ExtrusionPath::Collection->new(
-            paths => [ map Slic3r::ExtrusionPath->cast([ @$_ ]), @path_collection ],
+            paths => [ @path_collection ],
         );
         $layer->fills->[-1]->cleanup;
     }
diff --git a/lib/Slic3r/Fill/Base.pm b/lib/Slic3r/Fill/Base.pm
index da71d4e57..30b49e6e9 100644
--- a/lib/Slic3r/Fill/Base.pm
+++ b/lib/Slic3r/Fill/Base.pm
@@ -19,7 +19,7 @@ sub infill_direction {
     @shift = @{$rotate[1]};
     
     # alternate fill direction
-    if ($self->layer->id % 2) {
+    if (($self->layer->id / $surface->depth_layers) % 2) {
         $rotate[0] = Slic3r::Geometry::deg2rad($Slic3r::fill_angle) + PI/2;
     }
     
diff --git a/lib/Slic3r/GUI/SkeinPanel.pm b/lib/Slic3r/GUI/SkeinPanel.pm
index 8b68ae32d..53a7a7c22 100644
--- a/lib/Slic3r/GUI/SkeinPanel.pm
+++ b/lib/Slic3r/GUI/SkeinPanel.pm
@@ -29,7 +29,7 @@ sub new {
         ),
         accuracy => Slic3r::GUI::OptionsGroup->new($self,
             title => 'Accuracy',
-            options => [qw(layer_height high_res_perimeters)],
+            options => [qw(layer_height infill_every_layers)],
         ),
         print => Slic3r::GUI::OptionsGroup->new($self,
             title => 'Print settings',
diff --git a/lib/Slic3r/Geometry/Clipper.pm b/lib/Slic3r/Geometry/Clipper.pm
index 374b64d83..ec1f312a1 100644
--- a/lib/Slic3r/Geometry/Clipper.pm
+++ b/lib/Slic3r/Geometry/Clipper.pm
@@ -4,11 +4,27 @@ use warnings;
 
 require Exporter;
 our @ISA = qw(Exporter);
-our @EXPORT_OK = qw(diff_ex diff union_ex);
+our @EXPORT_OK = qw(explode_expolygon explode_expolygons safety_offset
+    diff_ex diff union_ex intersection_ex);
 
 use Math::Clipper 1.02 ':all';
 our $clipper = Math::Clipper->new;
 
+sub explode_expolygon {
+    my ($expolygon) = @_;
+    return ($expolygon->{outer}, @{ $expolygon->{holes} });
+}
+
+sub explode_expolygons {
+    my ($expolygons) = @_;
+    return map explode_expolygon($_), @$expolygons;
+}
+
+sub safety_offset {
+    my ($polygons) = @_;
+    return Math::Clipper::offset($polygons, 100, 100, JT_MITER, 2);
+}
+
 sub diff_ex {
     my ($subject, $clip) = @_;
     
@@ -29,4 +45,13 @@ sub union_ex {
     return $clipper->ex_execute(CT_UNION, PFT_NONZERO, PFT_NONZERO);
 }
 
+sub intersection_ex {
+    my ($subject, $clip) = @_;
+    
+    $clipper->clear;
+    $clipper->add_subject_polygons($subject);
+    $clipper->add_clip_polygons($clip);
+    return $clipper->ex_execute(CT_INTERSECTION, PFT_NONZERO, PFT_NONZERO);
+}
+
 1;
diff --git a/lib/Slic3r/Layer.pm b/lib/Slic3r/Layer.pm
index ad5a3dcd5..aa0448dda 100644
--- a/lib/Slic3r/Layer.pm
+++ b/lib/Slic3r/Layer.pm
@@ -4,7 +4,7 @@ use Moo;
 use Math::Clipper ':all';
 use Slic3r::Geometry qw(polygon_lines points_coincide angle3points polyline_lines nearest_point
     line_length);
-use Slic3r::Geometry::Clipper qw(union_ex);
+use Slic3r::Geometry::Clipper qw(safety_offset union_ex);
 use XXX;
 
 use constant PI => 4 * atan2(1, 1);
@@ -184,7 +184,7 @@ sub make_surfaces {
             #) if !$next_lines;
             
             $next_lines
-                or die sprintf("No lines start at point %s. This shouldn't happen", $get_point_id->($points[-1]));
+                or die sprintf("No lines start at point %s. This shouldn't happen. Please check the model for manifoldness.", $get_point_id->($points[-1]));
             last CYCLE if !@$next_lines;
             
             my @ordered_next_lines = sort 
@@ -284,10 +284,7 @@ sub process_bridges {
         # offset the surface a bit to avoid approximation issues when doing the
         # intersection below (this is to make sure we overlap with supporting
         # surfaces, otherwise a little gap will result from intersection)
-        {
-            my $offset = offset([$surface_p], 100, 100, JT_MITER, 2);
-            $surface_p = $offset->[0];
-        }
+        $surface_p = safety_offset([$surface_p])->[0];
         
             #use Slic3r::SVG;
             #Slic3r::SVG::output(undef, "bridge.svg",
diff --git a/lib/Slic3r/Polyline.pm b/lib/Slic3r/Polyline.pm
index 5d8e46f27..a0b381132 100644
--- a/lib/Slic3r/Polyline.pm
+++ b/lib/Slic3r/Polyline.pm
@@ -22,10 +22,10 @@ sub id {
 
 sub cast {
     my $class = shift;
-    my ($points) = @_;
+    my ($points, %args) = @_;
     
     $points = [ map { ref $_ eq 'ARRAY' ? Slic3r::Point->new($_) : $_ } @$points ];
-    return $class->new(points => $points);
+    return $class->new(points => $points, %args);
 }
 
 sub lines {
diff --git a/lib/Slic3r/Print.pm b/lib/Slic3r/Print.pm
index f6e230495..f05e5eef2 100644
--- a/lib/Slic3r/Print.pm
+++ b/lib/Slic3r/Print.pm
@@ -2,7 +2,7 @@ package Slic3r::Print;
 use Moo;
 
 use Math::Clipper ':all';
-use Slic3r::Geometry::Clipper qw(diff_ex union_ex);
+use Slic3r::Geometry::Clipper qw(explode_expolygons safety_offset diff_ex union_ex intersection_ex);
 use XXX;
 
 use constant X => 0;
@@ -145,7 +145,7 @@ sub detect_surfaces_type {
         
                 # okay, this is an Ugly Hack(tm) to avoid floating point math problems
                 # with diagonal bridges. will find a nicer solution, promised.
-                my $offset = offset([$surface->contour->p], 100, 100, JT_MITER, 2);
+                my $offset = safety_offset([$surface->contour->p]);
                 @{$surface->contour->points} = map Slic3r::Point->new($_), @{ $offset->[0] };
             }
             
@@ -301,6 +301,91 @@ sub split_bridges_fills {
     $_->split_bridges_fills for @{$self->layers};
 }
 
+# combine fill surfaces across layers
+sub infill_every_layers {
+    my $self = shift;
+    return unless $Slic3r::infill_every_layers > 1;
+    
+    printf "==> COMBINING INFILL\n";
+    
+    # start from bottom, skip first layer
+    for (my $i = 1; $i < $self->layer_count; $i++) {
+        my $layer = $self->layer($i);
+        
+        # skip layer if no internal fill surfaces
+        next if !grep $_->surface_type eq 'internal', map @$_, @{$layer->fill_surfaces};
+        
+        # for each possible depth, look for intersections with the lower layer
+        # we do this from the greater depth to the smaller
+        for (my $d = $Slic3r::infill_every_layers - 1; $d >= 1; $d--) {
+            next if ($i - $d) < 0;
+            my $lower_layer = $self->layer($i - 1);
+            
+            # select surfaces of the lower layer having the depth we're looking for
+            my @lower_surfaces = grep $_->depth_layers == $d && $_->surface_type eq 'internal',
+                map @$_, @{$lower_layer->fill_surfaces};
+            next if !@lower_surfaces;
+            # process each group of surfaces separately
+            foreach my $surfaces (@{$layer->fill_surfaces}) {
+                # calculate intersection between our surfaces and theirs
+                my $intersection = intersection_ex(
+                    [ map $_->p, grep $_->depth_layers <= $d, @lower_surfaces ],
+                    [ map $_->p, grep $_->surface_type eq 'internal', @$surfaces ],
+                );
+                next if !@$intersection;
+                
+                # new fill surfaces of the current layer are:
+                # - any non-internal surface
+                # - intersections found (with a $d + 1 depth)
+                # - any internal surface not belonging to the intersection (with its original depth)
+                {
+                    my @new_surfaces = ();
+                    push @new_surfaces, grep $_->surface_type ne 'internal', @$surfaces;
+                    push @new_surfaces, map Slic3r::Surface->cast_from_expolygon
+                        ($_, surface_type => 'internal', depth_layers => $d + 1), @$intersection;
+                    
+                    foreach my $depth (reverse $d..$Slic3r::infill_every_layers) {
+                        push @new_surfaces, map Slic3r::Surface->cast_from_expolygon
+                            ($_, surface_type => 'internal', depth_layers => $depth),
+                            
+                            # difference between our internal layers with depth == $depth
+                            # and the intersection found
+                            @{diff_ex(
+                                [
+                                    map $_->p, grep $_->surface_type eq 'internal' && $_->depth_layers == $depth, 
+                                        @$surfaces,
+                                ],
+                                safety_offset([ explode_expolygons($intersection) ]),
+                            )};
+                    }
+                    @$surfaces = @new_surfaces;
+                }
+                
+                # now we remove the intersections from lower layer
+                foreach my $lower_surfaces (@{$lower_layer->fill_surfaces}) {
+                    my @new_surfaces = ();
+                    push @new_surfaces, grep $_->surface_type ne 'internal', @$lower_surfaces;
+                    foreach my $depth (1..$Slic3r::infill_every_layers) {
+                        push @new_surfaces, map Slic3r::Surface->cast_from_expolygon
+                            ($_, surface_type => 'internal', depth_layers => $depth),
+                            
+                            # difference between internal layers with depth == $depth
+                            # and the intersection found
+                            @{diff_ex(
+                                [
+                                    map $_->p, grep $_->surface_type eq 'internal' && $_->depth_layers == $depth, 
+                                        @$lower_surfaces,
+                                ],
+                                safety_offset([ explode_expolygons($intersection) ]),
+                            )};
+                    }
+                    @$lower_surfaces = @new_surfaces;
+                }
+            }
+        }
+    }
+}
+
 sub extrude_fills {
     my $self = shift;
     
@@ -345,19 +430,6 @@ sub export_gcode {
     
     # write gcode commands layer by layer
     foreach my $layer (@{ $self->layers }) {
-        
-        # with the --high-res-perimeters options enabled we extrude perimeters for
-        # each layer twice at half height
-        if ($Slic3r::high_res_perimeters && $layer->id > 0) {
-            # go to half-layer
-            printf $fh $extruder->move_z($Slic3r::z_offset + $layer->z * $Slic3r::resolution - $Slic3r::layer_height/2);
-            
-            # extrude perimeters
-            $extruder->flow_ratio(0.5);
-            printf $fh $extruder->extrude_loop($_, 'perimeter') for @{ $layer->perimeters };
-            $extruder->flow_ratio(1);
-        }
-        
         # go to layer
         printf $fh $extruder->move_z($Slic3r::z_offset + $layer->z * $Slic3r::resolution);
         
diff --git a/lib/Slic3r/Skein.pm b/lib/Slic3r/Skein.pm
index 887260624..a9790ce32 100644
--- a/lib/Slic3r/Skein.pm
+++ b/lib/Slic3r/Skein.pm
@@ -47,6 +47,9 @@ sub go {
     # they will be split in internal and internal-solid surfaces
     $print->discover_horizontal_shells;
     
+    # combine fill surfaces to honor the "infill every N layers" option
+    $print->infill_every_layers;
+    
     # this will generate extrusion paths for each layer
     $print->extrude_fills;
     
diff --git a/lib/Slic3r/Surface.pm b/lib/Slic3r/Surface.pm
index c487b0863..f43903984 100644
--- a/lib/Slic3r/Surface.pm
+++ b/lib/Slic3r/Surface.pm
@@ -19,6 +19,9 @@ has 'surface_type' => (
     #isa     => enum([qw(internal internal-solid bottom top)]),
 );
 
+# this integer represents the thickness of the surface expressed in layers
+has 'depth_layers' => (is => 'ro', default => sub {1});
+
 sub cast_from_polygon {
     my $class = shift;
     my ($polygon, %args) = @_;
@@ -34,6 +37,7 @@ sub cast_from_expolygon {
     my ($expolygon, %args) = @_;
     
     if (ref $expolygon ne 'HASH') {
+        use XXX; ZZZ $expolygon if ref $expolygon eq 'ARRAY';
         $expolygon = $expolygon->clipper_expolygon;
     }
     
diff --git a/slic3r.pl b/slic3r.pl
index d434a4e0e..75f64f3a3 100755
--- a/slic3r.pl
+++ b/slic3r.pl
@@ -41,7 +41,7 @@ GetOptions(
     
     # accuracy options
     'layer-height=f'        => \$Slic3r::layer_height,
-    'high-res-perimeters'   => \$Slic3r::high_res_perimeters,
+    'infill-every-layers=i' => \$Slic3r::infill_every_layers,
     
     # print options
     'perimeters=i'          => \$Slic3r::perimeter_offsets,
@@ -147,9 +147,8 @@ Usage: slic3r.pl [ OPTIONS ] file.stl
     
   Accuracy options:
     --layer-height      Layer height in mm (default: $Slic3r::layer_height)
-    --high-res-perimeters
-                        Print perimeters at half layer height to get surface accuracy
-                        (default: disabled)
+    --infill-every-layers
+                        Infill every N layers (default: $Slic3r::infill_every_layers)
   
   Print options:
     --perimeters        Number of perimeters/horizontal skins (range: 1+,