Don't merge adjacent bridges so that more correct angles can be detected for each one

1 files changed, 142 insertions, 148 deletions

diff --git a/lib/Slic3r/Layer/Region.pm b/lib/Slic3r/Layer/Region.pm
index 16baf95d9..653931d8d 100644
--- a/lib/Slic3r/Layer/Region.pm
+++ b/lib/Slic3r/Layer/Region.pm
@@ -411,177 +411,171 @@ sub prepare_fill_surfaces {
 sub process_external_surfaces {
     my $self = shift;
     
-    # 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};
-        
-        # if we're slicing with no infill, we can't extend external surfaces
-        # over non-existent infill
-        my @fill_boundaries = $Slic3r::Config->fill_density > 0
-            ? @{$self->fill_surfaces}
-            : grep $_->surface_type != S_TYPE_INTERNAL, @{$self->fill_surfaces};
+    my $margin = scale 3;  # TODO: ensure this is greater than the total thickness of the perimeters
+    
+    my @bottom = ();
+    foreach my $surface (grep $_->surface_type == S_TYPE_BOTTOM, @{$self->fill_surfaces}) {
+        my ($grown) = $surface->expolygon->offset_ex(+$margin);
         
-        # 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, @fill_boundaries ],
-            undef,
-            1,  # to ensure adjacent expolygons are unified
-        )};
-        @bottom = @{intersection_ex(
-            [ Slic3r::Geometry::Clipper::offset([ map $_->p, @bottom ], +$margin) ],
-            [ map $_->p, @fill_boundaries ],
-            undef,
-            1,  # to ensure adjacent expolygons are unified
-        )};
+        # detect bridge direction before merging grown surfaces otherwise adjacent bridges
+        # would get merged into a single one while they need different directions
+        my $angle = $self->id > 0
+            ? $self->_detect_bridge_direction($grown)
+            : undef;
         
+        push @bottom, $surface->clone(expolygon => $grown, bridge_angle => $angle);
+    }
+    
+    my @top = ();
+    foreach my $surface (grep $_->surface_type == S_TYPE_TOP, @{$self->fill_surfaces}) {
         # give priority to bottom surfaces
-        @top = @{diff_ex(
-            [ map @$_, @top ],
-            [ map @$_, @bottom ],
-        )};
-        
-        # 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;
-        
-        # 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 $group->[0]->clone(expolygon => $_), @{diff_ex(
+        my $grown = diff_ex(
+            [ $surface->expolygon->offset(+$margin) ],
+            [ map $_->p, @bottom ],
+        );
+        push @top, map $surface->clone(expolygon => $_), @$grown;
+    }
+    
+    # if we're slicing with no infill, we can't extend external surfaces
+    # over non-existent infill
+    my @fill_boundaries = $Slic3r::Config->fill_density > 0
+        ? @{$self->fill_surfaces}
+        : grep $_->surface_type != S_TYPE_INTERNAL, @{$self->fill_surfaces};
+    
+    # intersect the grown surfaces with the actual fill boundaries
+    my @new_surfaces = ();
+    foreach my $group (Slic3r::Surface->group(@top, @bottom)) {
+        push @new_surfaces,
+            map $group->[0]->clone(expolygon => $_),
+            @{intersection_ex(
                 [ map $_->p, @$group ],
-                [ map $_->p, @new_surfaces ],
+                [ map $_->p, @fill_boundaries ],
+                undef,
+                1,  # to ensure adjacent expolygons are unified
             )};
-        }
-        @{$self->fill_surfaces} = @new_surfaces;
     }
     
-    # detect bridge direction (skip bottom layer)
-    $self->_detect_bridges if $self->id > 0;
+    # 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 $group->[0]->clone(expolygon => $_), @{diff_ex(
+            [ map $_->p, @$group ],
+            [ map $_->p, @new_surfaces ],
+        )};
+    }
+    @{$self->fill_surfaces} = @new_surfaces;
 }
 
-sub _detect_bridges {
+sub _detect_bridge_direction {
     my $self = shift;
+    my ($expolygon) = @_;
+    
+    my @lower = @{$self->layer->object->layers->[ $self->id - 1 ]->slices};       # expolygons
     
-    my @bottom  = grep $_->surface_type == S_TYPE_BOTTOM, @{$self->fill_surfaces};  # surfaces
-    my @lower   = @{$self->layer->object->layers->[ $self->id - 1 ]->slices};       # expolygons
-    
-    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]}));
-                }
+    # 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), @$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, @clipped;
         }
-        
-        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_$surface.svg",
-                expolygons      => [ $surface->expolygon ],
-                red_expolygons  => [ @lower ],
-                polylines       => [ @edges ],
-            );
+        push @edges, @clipped;
+    }
+    
+    Slic3r::debugf "Found bridge on layer %d with %d support(s)\n", $self->id, scalar(@edges);
+    return undef if !@edges;
+    
+    my $bridge_angle = undef;
+    
+    if (0) {
+        require "Slic3r/SVG.pm";
+        Slic3r::SVG::output("bridge_$expolygon.svg",
+            expolygons      => [ $expolygon ],
+            red_expolygons  => [ @lower ],
+            polylines       => [ @edges ],
+        );
+    }
+    
+    if (@edges == 2) {
+        my @chords = map Slic3r::Line->new($_->[0], $_->[-1]), @edges;
+        my @midpoints = map $_->midpoint, @chords;
+        my $line_between_midpoints = Slic3r::Line->new(@midpoints);
+        $bridge_angle = Slic3r::Geometry::rad2deg_dir($line_between_midpoints->direction);
+    } elsif (@edges == 1) {
+        # TODO: this case includes both U-shaped bridges and plain overhangs;
+        # we need a trapezoidation algorithm to detect the actual bridged area
+        # and separate it from the overhang area.
+        # in the mean time, we're treating as overhangs all cases where
+        # our supporting edge is a straight line
+        if (@{$edges[0]} > 2) {
+            my $line = Slic3r::Line->new($edges[0]->[0], $edges[0]->[-1]);
+            $bridge_angle = Slic3r::Geometry::rad2deg_dir($line->direction);
         }
+    } elsif (@edges) {
+        # inset the bridge expolygon; we'll use this one to clip our test lines
+        my $inset = [ $expolygon->offset_ex($self->infill_flow->scaled_width) ];
         
-        if (@edges == 2) {
-            my @chords = map Slic3r::Line->new($_->[0], $_->[-1]), @edges;
-            my @midpoints = map $_->midpoint, @chords;
-            my $line_between_midpoints = Slic3r::Line->new(@midpoints);
-            $bridge_angle = Slic3r::Geometry::rad2deg_dir($line_between_midpoints->direction);
-        } elsif (@edges == 1) {
-            # TODO: this case includes both U-shaped bridges and plain overhangs;
-            # we need a trapezoidation algorithm to detect the actual bridged area
-            # and separate it from the overhang area.
-            # in the mean time, we're treating as overhangs all cases where
-            # our supporting edge is a straight line
-            if (@{$edges[0]} > 2) {
-                my $line = Slic3r::Line->new($edges[0]->[0], $edges[0]->[-1]);
-                $bridge_angle = Slic3r::Geometry::rad2deg_dir($line->direction);
-            }
-        } elsif (@edges) {
-            # inset the bridge expolygon; we'll use this one to clip our test lines
-            my $inset = [ $surface->expolygon->offset_ex($self->infill_flow->scaled_width) ];
-            
-            # detect anchors as intersection between our bridge expolygon and the lower slices
-            my $anchors = intersection_ex(
-                [ $surface->p ],
-                [ map @$_, @lower ],
-                undef,
-                1,  # safety offset required to avoid Clipper from detecting empty intersection while Boost actually found some @edges
-            );
+        # detect anchors as intersection between our bridge expolygon and the lower slices
+        my $anchors = intersection_ex(
+            [ @$expolygon ],
+            [ map @$_, @lower ],
+            undef,
+            1,  # safety offset required to avoid Clipper from detecting empty intersection while Boost actually found some @edges
+        );
+        
+        # we'll now try several directions using a rudimentary visibility check:
+        # bridge in several directions and then sum the length of lines having both
+        # endpoints within anchors
+        my %directions = ();  # angle => score
+        my $angle_increment = PI/36; # 5°
+        my $line_increment = $self->infill_flow->scaled_width;
+        for (my $angle = 0; $angle <= PI; $angle += $angle_increment) {
+            # rotate everything - the center point doesn't matter
+            $_->rotate($angle, [0,0]) for @$inset, @$anchors;
             
-            # we'll now try several directions using a rudimentary visibility check:
-            # bridge in several directions and then sum the length of lines having both
-            # endpoints within anchors
-            my %directions = ();  # angle => score
-            my $angle_increment = PI/36; # 5°
-            my $line_increment = $self->infill_flow->scaled_width;
-            for (my $angle = 0; $angle <= PI; $angle += $angle_increment) {
-                # rotate everything - the center point doesn't matter
-                $_->rotate($angle, [0,0]) for @$inset, @$anchors;
-                
-                # generate lines in this direction
-                my $bounding_box = Slic3r::Geometry::BoundingBox->new_from_points([ map @$_, map @$_, @$anchors ]);
-                my @lines = ();
-                for (my $x = $bounding_box->x_min; $x <= $bounding_box->x_max; $x += $line_increment) {
-                    push @lines, [ [$x, $bounding_box->y_min], [$x, $bounding_box->y_max] ];
-                }
-                
-                # TODO: use a multi_polygon_multi_linestring_intersection() call
-                my @clipped_lines = map @{ Boost::Geometry::Utils::polygon_multi_linestring_intersection($_, \@lines) }, @$inset;
-                
-                # remove any line not having both endpoints within anchors
-                @clipped_lines = grep {
-                    my $line = $_;
-                    !(first { $_->encloses_point_quick($line->[A]) } @$anchors)
-                        && !(first { $_->encloses_point_quick($line->[B]) } @$anchors);
-                } @clipped_lines;
-                
-                # sum length of bridged lines
-                $directions{-$angle} = sum(map Slic3r::Geometry::line_length($_), @clipped_lines) // 0;
+            # generate lines in this direction
+            my $bounding_box = Slic3r::Geometry::BoundingBox->new_from_points([ map @$_, map @$_, @$anchors ]);
+            my @lines = ();
+            for (my $x = $bounding_box->x_min; $x <= $bounding_box->x_max; $x += $line_increment) {
+                push @lines, [ [$x, $bounding_box->y_min], [$x, $bounding_box->y_max] ];
             }
             
-            # this could be slightly optimized with a max search instead of the sort
-            my @sorted_directions = sort { $directions{$a} <=> $directions{$b} } keys %directions;
+            # TODO: use a multi_polygon_multi_linestring_intersection() call
+            my @clipped_lines = map @{ Boost::Geometry::Utils::polygon_multi_linestring_intersection($_, \@lines) }, @$inset;
             
-            # the best direction is the one causing most lines to be bridged
-            $bridge_angle = Slic3r::Geometry::rad2deg_dir($sorted_directions[-1]);
+            # remove any line not having both endpoints within anchors
+            @clipped_lines = grep {
+                my $line = $_;
+                !(first { $_->encloses_point_quick($line->[A]) } @$anchors)
+                    && !(first { $_->encloses_point_quick($line->[B]) } @$anchors);
+            } @clipped_lines;
+            
+            # sum length of bridged lines
+            $directions{-$angle} = sum(map Slic3r::Geometry::line_length($_), @clipped_lines) // 0;
         }
         
-        Slic3r::debugf "  Optimal infill angle of bridge on layer %d is %d degrees\n",
-            $self->id, $bridge_angle if defined $bridge_angle;
+        # this could be slightly optimized with a max search instead of the sort
+        my @sorted_directions = sort { $directions{$a} <=> $directions{$b} } keys %directions;
         
-        $surface->bridge_angle($bridge_angle);
+        # the best direction is the one causing most lines to be bridged
+        $bridge_angle = Slic3r::Geometry::rad2deg_dir($sorted_directions[-1]);
     }
+    
+    Slic3r::debugf "  Optimal infill angle of bridge on layer %d is %d degrees\n",
+        $self->id, $bridge_angle if defined $bridge_angle;
+    
+    return $bridge_angle;
 }
 
 1;