Infill refactoring and cleanup complete

7 files changed, 106 insertions, 160 deletions

diff --git a/lib/Slic3r/Fill.pm b/lib/Slic3r/Fill.pm
index 025a1cc00..6e9dcaf45 100644
--- a/lib/Slic3r/Fill.pm
+++ b/lib/Slic3r/Fill.pm
@@ -54,7 +54,7 @@ sub make_fill {
     
     # merge adjacent surfaces
     # in case of bridge surfaces, the ones with defined angle will be attached to the ones
-    # without any angle (shouldn't this logic be moved to process_bridges()?)
+    # without any angle (shouldn't this logic be moved to process_external_surfaces()?)
     my @surfaces = ();
     {
         my @surfaces_with_bridge_angle = grep defined $_->bridge_angle, @{$layerm->fill_surfaces};
diff --git a/lib/Slic3r/Layer/Region.pm b/lib/Slic3r/Layer/Region.pm
index 80f5aaa96..f98bfc9a7 100644
--- a/lib/Slic3r/Layer/Region.pm
+++ b/lib/Slic3r/Layer/Region.pm
@@ -2,7 +2,7 @@ package Slic3r::Layer::Region;
 use Moo;
 
 use Slic3r::ExtrusionPath ':roles';
-use Slic3r::Geometry qw(PI scale chained_path_items);
+use Slic3r::Geometry qw(PI scale chained_path_items points_coincide);
 use Slic3r::Geometry::Clipper qw(safety_offset union_ex diff_ex intersection_ex);
 use Slic3r::Surface ':types';
 
@@ -422,7 +422,7 @@ sub _add_perimeter {
     my $self = shift;
     my ($polygon, $role) = @_;
     
-    return unless $polygon->is_printable($self->perimeter_flow);
+    return unless $polygon->is_printable($self->perimeter_flow->scaled_width);
     push @{ $self->perimeters }, Slic3r::ExtrusionLoop->pack(
         polygon         => $polygon,
         role            => ($role // EXTR_ROLE_PERIMETER),
@@ -433,6 +433,11 @@ sub _add_perimeter {
 sub prepare_fill_surfaces {
     my $self = shift;
     
+    # if hollow object is requested, remove internal surfaces
+    if ($Slic3r::Config->fill_density == 0) {
+        @{$self->fill_surfaces} = grep $_->surface_type != S_TYPE_INTERNAL, @{$self->fill_surfaces};
+    }
+    
     # if no solid layers are requested, turn top/bottom surfaces to internal
     if ($Slic3r::Config->top_solid_layers == 0) {
         $_->surface_type(S_TYPE_INTERNAL) for grep $_->surface_type == S_TYPE_TOP, @{$self->fill_surfaces};
@@ -441,7 +446,7 @@ sub prepare_fill_surfaces {
         $_->surface_type(S_TYPE_INTERNAL) for grep $_->surface_type == S_TYPE_BOTTOM, @{$self->fill_surfaces};
     }
         
-    # turn too small internal regions into solid regions
+    # turn too small internal regions into solid regions according to the user setting
     {
         my $min_area = scale scale $Slic3r::Config->solid_infill_below_area; # scaling an area requires two calls!
         my @small = grep $_->surface_type == S_TYPE_INTERNAL && $_->expolygon->contour->area <= $min_area, @{$self->fill_surfaces};
@@ -450,76 +455,99 @@ sub prepare_fill_surfaces {
     }
 }
 
-# make bridges printable
-sub process_bridges {
+sub process_external_surfaces {
     my $self = shift;
     
-    # no bridges are possible if we have no internal surfaces
-    return if $Slic3r::Config->fill_density == 0;
-    
-    my @bridges = ();
-    
-    # a bottom surface on a layer > 0 is either a bridge or a overhang 
-    # or a combination of both; any top surface is a candidate for
-    # reverse bridge processing
-    
-    my @solid_surfaces = grep {
-        ($_->surface_type == S_TYPE_BOTTOM && $self->id > 0) || $_->surface_type == S_TYPE_TOP
-    } @{$self->fill_surfaces} or return;
-    
-    my @internal_surfaces = grep $_->is_internal, @{$self->slices};
-    
-    SURFACE: foreach my $surface (@solid_surfaces) {
-        my $expolygon = $surface->expolygon->safety_offset;
-        my $description = $surface->surface_type == S_TYPE_BOTTOM ? 'bridge/overhang' : 'reverse bridge';
+    # enlarge top and bottom surfaces
+    {
+        # get all external surfaces
+        my @top     = grep $_->surface_type == S_TYPE_TOP, @{$self->fill_surfaces};
+        my @bottom  = grep $_->surface_type == S_TYPE_BOTTOM, @{$self->fill_surfaces};
         
-        # offset the contour and intersect it with the internal surfaces to discover 
-        # which of them has contact with our bridge
-        my @supporting_surfaces = ();
-        my ($contour_offset) = $expolygon->contour->offset(scale $self->infill_flow->spacing * sqrt(2));
-        foreach my $internal_surface (@internal_surfaces) {
-            my $intersection = intersection_ex([$contour_offset], [$internal_surface->p]);
-            if (@$intersection) {
-                push @supporting_surfaces, $internal_surface;
-            }
-        }
+        # offset them and intersect the results with the actual fill boundaries
+        my $margin = scale 3;  # TODO: ensure this is greater than the total thickness of the perimeters
+        @top = @{intersection_ex(
+            [ Slic3r::Geometry::Clipper::offset([ map $_->p, @top ], +$margin) ],
+            [ map $_->p, @{$self->fill_surfaces} ],
+            undef,
+            1,  # to ensure adjacent expolygons are unified
+        )};
+        @bottom = @{intersection_ex(
+            [ Slic3r::Geometry::Clipper::offset([ map $_->p, @bottom ], +$margin) ],
+            [ map $_->p, @{$self->fill_surfaces} ],
+            undef,
+            1,  # to ensure adjacent expolygons are unified
+        )};
         
-        if (0) {
-            require "Slic3r/SVG.pm";
-            Slic3r::SVG::output("bridge_surfaces.svg",
-                green_polygons  => [ map $_->p, @supporting_surfaces ],
-                red_polygons    => [ @$expolygon ],
-            );
-        }
+        # give priority to bottom surfaces
+        @top = @{diff_ex(
+            [ map @$_, @top ],
+            [ map @$_, @bottom ],
+        )};
         
-        Slic3r::debugf "Found $description on layer %d with %d support(s)\n", 
-            $self->id, scalar(@supporting_surfaces);
+        # generate new surfaces
+        my @new_surfaces = ();
+        push @new_surfaces, map Slic3r::Surface->new(
+                expolygon       => $_,
+                surface_type    => S_TYPE_TOP,
+            ), @top;
+        push @new_surfaces, map Slic3r::Surface->new(
+                expolygon       => $_,
+                surface_type    => S_TYPE_BOTTOM,
+            ), @bottom;
         
-        next SURFACE unless @supporting_surfaces;
+        # subtract the new top surfaces from the other non-top surfaces and re-add them
+        my @other = grep $_->surface_type != S_TYPE_TOP && $_->surface_type != S_TYPE_BOTTOM, @{$self->fill_surfaces};
+        foreach my $group (Slic3r::Surface->group(@other)) {
+            push @new_surfaces, map Slic3r::Surface->new(
+                expolygon       => $_,
+                surface_type    => $group->[0]->surface_type,
+            ), @{diff_ex(
+                [ map $_->p, @$group ],
+                [ map $_->p, @new_surfaces ],
+            )};
+        }
+        @{$self->fill_surfaces} = @new_surfaces;
+    }
+    
+    # detect bridge direction (skip bottom layer)
+    if ($self->id > 0) {
+        my @bottom  = grep $_->surface_type == S_TYPE_BOTTOM, @{$self->fill_surfaces};  # surfaces
+        my @lower   = @{$self->layer->object->layers->[ $self->id - 1 ]->slices};       # expolygons
         
-        my $bridge_angle = undef;
-        if ($surface->surface_type == S_TYPE_BOTTOM) {
-            # detect optimal bridge angle
-            
-            my $bridge_over_hole = 0;
-            my @edges = ();  # edges are POLYLINES
-            foreach my $supporting_surface (@supporting_surfaces) {
-                my @surface_edges = map $_->clip_with_polygon($contour_offset),
-                    ($supporting_surface->contour, $supporting_surface->holes);
-                
-                if (@supporting_surfaces == 1 && @surface_edges == 1
-                    && @{$supporting_surface->contour} == @{$surface_edges[0]}) {
-                    $bridge_over_hole = 1;
+        foreach my $surface (@bottom) {
+            # detect what edges lie on lower slices
+            my @edges = (); # polylines
+            foreach my $lower (@lower) {
+                # turn bridge contour and holes into polylines and then clip them
+                # with each lower slice's contour
+                my @clipped = map $_->split_at_first_point->clip_with_polygon($lower->contour), @{$surface->expolygon};
+                if (@clipped == 2) {
+                    # If the split_at_first_point() call above happens to split the polygon inside the clipping area
+                    # we would get two consecutive polylines instead of a single one, so we use this ugly hack to 
+                    # recombine them back into a single one in order to trigger the @edges == 2 logic below.
+                    # This needs to be replaced with something way better.
+                    if (points_coincide($clipped[0][0], $clipped[-1][-1])) {
+                        @clipped = (Slic3r::Polyline->new(@{$clipped[-1]}, @{$clipped[0]}));
+                    }
+                    if (points_coincide($clipped[-1][0], $clipped[0][-1])) {
+                        @clipped = (Slic3r::Polyline->new(@{$clipped[0]}, @{$clipped[1]}));
+                    }
                 }
-                push @edges, grep { @$_ } @surface_edges;
+                push @edges, @clipped;
             }
-            Slic3r::debugf "  Bridge is supported on %d edge(s)\n", scalar(@edges);
-            Slic3r::debugf "  and covers a hole\n" if $bridge_over_hole;
+            
+            Slic3r::debugf "Found bridge on layer %d with %d support(s)\n", $self->id, scalar(@edges);
+            next if !@edges;
+            
+            my $bridge_angle = undef;
             
             if (0) {
                 require "Slic3r/SVG.pm";
-                Slic3r::SVG::output("bridge_edges.svg",
-                    polylines       => [ map $_->p, @edges ],
+                Slic3r::SVG::output("bridge.svg",
+                    polygons        => [ $surface->p ],
+                    red_polygons    => [ map @$_, @lower ],
+                    polylines       => [ @edges ],
                 );
             }
             
@@ -553,80 +581,8 @@ sub process_bridges {
             
             Slic3r::debugf "  Optimal infill angle of bridge on layer %d is %d degrees\n",
                 $self->id, $bridge_angle if defined $bridge_angle;
-        }
-        
-        # now, extend our bridge by taking a portion of supporting surfaces
-        {
-            # offset the bridge by the specified amount of mm (minimum 3)
-            my $bridge_overlap = scale 3;
-            my ($bridge_offset) = $expolygon->contour->offset($bridge_overlap);
-            
-            # calculate the new bridge
-            my $intersection = intersection_ex(
-                [ @$expolygon, map $_->p, @supporting_surfaces ],
-                [ $bridge_offset ],
-            );
-            
-            push @bridges, map Slic3r::Surface->new(
-                expolygon => $_,
-                surface_type => $surface->surface_type,
-                bridge_angle => $bridge_angle,
-            ), @$intersection;
-        }
-    }
-    
-    # now we need to merge bridges to avoid overlapping
-    {
-        # build a list of unique bridge types
-        my @surface_groups = Slic3r::Surface->group(@bridges);
-        
-        # merge bridges of the same type, removing any of the bridges already merged;
-        # the order of @surface_groups determines the priority between bridges having 
-        # different surface_type or bridge_angle
-        @bridges = ();
-        foreach my $surfaces (@surface_groups) {
-            my $union = union_ex([ map $_->p, @$surfaces ]);
-            my $diff = diff_ex(
-                [ map @$_, @$union ],
-                [ map $_->p, @bridges ],
-            );
             
-            push @bridges, map Slic3r::Surface->new(
-                expolygon => $_,
-                surface_type => $surfaces->[0]->surface_type,
-                bridge_angle => $surfaces->[0]->bridge_angle,
-            ), @$union;
-        }
-    }
-    
-    # apply bridges to layer
-    {
-        my @surfaces = @{$self->fill_surfaces};
-        @{$self->fill_surfaces} = ();
-        
-        # intersect layer surfaces with bridges to get actual bridges
-        foreach my $bridge (@bridges) {
-            my $actual_bridge = intersection_ex(
-                [ map $_->p, @surfaces ],
-                [ $bridge->p ],
-            );
-            
-            push @{$self->fill_surfaces}, map Slic3r::Surface->new(
-                expolygon => $_,
-                surface_type => $bridge->surface_type,
-                bridge_angle => $bridge->bridge_angle,
-            ), @$actual_bridge;
-        }
-        
-        # difference between layer surfaces and bridges are the other surfaces
-        foreach my $group (Slic3r::Surface->group(@surfaces)) {
-            my $difference = diff_ex(
-                [ map $_->p, @$group ],
-                [ map $_->p, @bridges ],
-            );
-            push @{$self->fill_surfaces}, map Slic3r::Surface->new(
-                expolygon => $_,
-                surface_type => $group->[0]->surface_type), @$difference;
+            $surface->bridge_angle($bridge_angle);
         }
     }
 }
diff --git a/lib/Slic3r/Polygon.pm b/lib/Slic3r/Polygon.pm
index 0f3827381..4af44acc9 100644
--- a/lib/Slic3r/Polygon.pm
+++ b/lib/Slic3r/Polygon.pm
@@ -118,7 +118,7 @@ sub subdivide {
 # returns false if the polyline is too tight to be printed
 sub is_printable {
     my $self = shift;
-    my ($flow) = @_;
+    my ($width) = @_;
     
     # try to get an inwards offset
     # for a distance equal to half of the extrusion width;
@@ -129,7 +129,7 @@ sub is_printable {
     # detect them and we would be discarding them.
     my $p = $self->clone;
     $p->make_counter_clockwise;
-    return $p->offset(-$flow->scaled_width / 2) ? 1 : 0;
+    return $p->offset(-$width / 2) ? 1 : 0;
 }
 
 sub is_valid {
diff --git a/lib/Slic3r/Print.pm b/lib/Slic3r/Print.pm
index 1aad0ae39..56b868335 100644
--- a/lib/Slic3r/Print.pm
+++ b/lib/Slic3r/Print.pm
@@ -337,7 +337,8 @@ sub export_gcode {
             for @{$layer->slices}, (map $_->expolygon, map @{$_->slices}, @{$layer->regions});
     }
     
-    # this will transform $layer->fill_surfaces from expolygon 
+    # this will assign a type (top/bottom/internal) to $layerm->slices
+    # and transform $layerm->fill_surfaces from expolygon 
     # to typed top/bottom/internal surfaces;
     $status_cb->(30, "Detecting solid surfaces");
     $_->detect_surfaces_type for @{$self->objects};
@@ -349,7 +350,7 @@ sub export_gcode {
     # this will detect bridges and reverse bridges
     # and rearrange top/bottom/internal surfaces
     $status_cb->(45, "Detect bridges");
-    $_->process_bridges for map @{$_->regions}, map @{$_->layers}, @{$self->objects};
+    $_->process_external_surfaces for map @{$_->regions}, map @{$_->layers}, @{$self->objects};
     
     # detect which fill surfaces are near external layers
     # they will be split in internal and internal-solid surfaces
diff --git a/lib/Slic3r/Print/Object.pm b/lib/Slic3r/Print/Object.pm
index 08be02388..c77fd228f 100644
--- a/lib/Slic3r/Print/Object.pm
+++ b/lib/Slic3r/Print/Object.pm
@@ -300,7 +300,7 @@ sub detect_surfaces_type {
             [ map @$_, @$clip_surfaces ],
             1,
         );
-        return grep $_->contour->is_printable($layerm->perimeter_flow),
+        return grep $_->contour->is_printable($layerm->perimeter_flow->scaled_width),
             map Slic3r::Surface->new(expolygon => $_, surface_type => $result_type), 
             @$expolygons;
     };
@@ -515,7 +515,9 @@ sub discover_horizontal_shells {
             
             foreach my $type (S_TYPE_TOP, S_TYPE_BOTTOM) {
                 # find slices of current type for current layer
-                my @surfaces = grep $_->surface_type == $type, @{$layerm->slices} or next;
+                # get both slices and fill_surfaces before the former contains the perimeters area
+                # and the latter contains the enlarged external surfaces
+                my @surfaces = grep $_->surface_type == $type, @{$layerm->slices}, @{$layerm->fill_surfaces} or next;
                 my $surfaces_p = [ map $_->p, @surfaces ];
                 Slic3r::debugf "Layer %d has %d surfaces of type '%s'\n",
                     $i, scalar(@surfaces), ($type == S_TYPE_TOP ? 'top' : 'bottom');
@@ -548,7 +550,7 @@ sub discover_horizontal_shells {
                         ( map @$_, @$new_internal_solid ),
                     ]);
                     
-                    # subtract intersections from layer surfaces to get resulting inner surfaces
+                    # subtract intersections from layer surfaces to get resulting internal surfaces
                     my $internal = diff_ex(
                         [ map $_->p, grep $_->surface_type == S_TYPE_INTERNAL, @neighbor_fill_surfaces ],
                         [ map @$_, @$internal_solid ],
@@ -557,10 +559,7 @@ sub discover_horizontal_shells {
                     Slic3r::debugf "    %d internal-solid and %d internal surfaces found\n",
                         scalar(@$internal_solid), scalar(@$internal);
                     
-                    # Note: due to floating point math we're going to get some very small
-                    # polygons as $internal; they will be removed by removed_small_features()
-                    
-                    # assign resulting inner surfaces to layer
+                    # assign resulting internal surfaces to layer
                     my $neighbor_fill_surfaces = $self->layers->[$n]->regions->[$region_id]->fill_surfaces;
                     @$neighbor_fill_surfaces = ();
                     push @$neighbor_fill_surfaces, Slic3r::Surface->new
@@ -586,17 +585,7 @@ sub discover_horizontal_shells {
                 }
             }
             
-            my $area_threshold = $layerm->infill_area_threshold;
-            @{$layerm->fill_surfaces} = grep $_->expolygon->area > $area_threshold, @{$layerm->fill_surfaces};
-        }
-        
-        for (my $i = 0; $i < $self->layer_count; $i++) {
-            my $layerm = $self->layers->[$i]->regions->[$region_id];
-            
-            # if hollow object is requested, remove internal surfaces
-            if ($Slic3r::Config->fill_density == 0) {
-                @{$layerm->fill_surfaces} = grep $_->surface_type != S_TYPE_INTERNAL, @{$layerm->fill_surfaces};
-            }
+            @{$layerm->fill_surfaces} = grep $_->expolygon->area > $layerm->infill_area_threshold, @{$layerm->fill_surfaces};
         }
     }
 }
diff --git a/lib/Slic3r/Surface.pm b/lib/Slic3r/Surface.pm
index a3cbe4b08..d5ec9838e 100644
--- a/lib/Slic3r/Surface.pm
+++ b/lib/Slic3r/Surface.pm
@@ -35,8 +35,8 @@ sub new {
 sub expolygon       { $_[0][S_EXPOLYGON] }
 sub surface_type    { $_[0][S_SURFACE_TYPE] = $_[1] if defined $_[1]; $_[0][S_SURFACE_TYPE] }
 sub depth_layers    { $_[0][S_DEPTH_LAYERS] } # this integer represents the thickness of the surface expressed in layers
-sub bridge_angle    { $_[0][S_BRIDGE_ANGLE] }
-sub additional_inner_perimeters { $_[0][S_ADDITIONAL_INNER_PERIMETERS] = $_[1] if $_[1]; $_[0][S_ADDITIONAL_INNER_PERIMETERS] }
+sub bridge_angle    { $_[0][S_BRIDGE_ANGLE] = $_[1] if defined $_[1]; $_[0][S_BRIDGE_ANGLE] }
+sub additional_inner_perimeters { $_[0][S_ADDITIONAL_INNER_PERIMETERS] = $_[1] if defined $_[1]; $_[0][S_ADDITIONAL_INNER_PERIMETERS] }
 
 # delegate handles
 sub encloses_point  { $_[0]->expolygon->encloses_point }
diff --git a/t/combineinfill.t b/t/combineinfill.t
index aa4ed91a1..e2e63f4a0 100644
--- a/t/combineinfill.t
+++ b/t/combineinfill.t
@@ -48,7 +48,7 @@ use Slic3r::Test;
         }
         $_->detect_surfaces_type for @{$self->objects};
         $_->prepare_fill_surfaces for map @{$_->regions}, map @{$_->layers}, @{$self->objects};
-        $_->process_bridges for map @{$_->regions}, map @{$_->layers}, @{$self->objects};
+        $_->process_external_surfaces for map @{$_->regions}, map @{$_->layers}, @{$self->objects};
         $_->discover_horizontal_shells for @{$self->objects};
         $_->combine_infill for @{$self->objects};