Merge branch 'newslice'

3 files changed, 98 insertions, 185 deletions

diff --git a/lib/Slic3r/Layer/Region.pm b/lib/Slic3r/Layer/Region.pm
index 3b5bfe0da..870fb68f3 100644
--- a/lib/Slic3r/Layer/Region.pm
+++ b/lib/Slic3r/Layer/Region.pm
@@ -23,10 +23,6 @@ has 'top_infill_flow'   => (is => 'rw');
 has 'infill_area_threshold' => (is => 'lazy');
 has 'overhang_width'    => (is => 'lazy');
 
-# collection of spare segments generated by slicing the original geometry;
-# these need to be merged in continuos (closed) polylines
-has 'lines' => (is => 'rw', default => sub { [] });
-
 # collection of surfaces generated by slicing the original geometry
 # divided by type top/bottom/internal
 has 'slices' => (is => 'rw', default => sub { [] });
diff --git a/lib/Slic3r/Print/Object.pm b/lib/Slic3r/Print/Object.pm
index 65de510f5..ae7228ff3 100644
--- a/lib/Slic3r/Print/Object.pm
+++ b/lib/Slic3r/Print/Object.pm
@@ -129,10 +129,12 @@ sub slice {
     for my $region_id (0 .. $#{$self->meshes}) {
         my $mesh = $self->meshes->[$region_id];  # ignore undef meshes
         
+        my %lines = ();  # layer_id => [ lines ]
         my $apply_lines = sub {
             my $lines = shift;
             foreach my $layer_id (keys %$lines) {
-                push @{$self->layers->[$layer_id]->regions->[$region_id]->lines}, @{$lines->{$layer_id}};
+                $lines{$layer_id} ||= [];
+                push @{$lines{$layer_id}}, @{$lines->{$layer_id}};
             }
         };
         Slic3r::parallelize(
@@ -161,36 +163,31 @@ sub slice {
             },
         );
         
-        $self->meshes->[$region_id] = undef;  # free memory
+        # free memory
+        undef $mesh;
+        undef $self->meshes->[$region_id];
+        
+        foreach my $layer (@{ $self->layers }) {
+            Slic3r::debugf "Making surfaces for layer %d (slice z = %f):\n",
+                $layer->id, unscale $layer->slice_z if $Slic3r::debug;
+            
+            my $layerm = $layer->regions->[$region_id];
+            my ($slicing_errors, $loops) = Slic3r::TriangleMesh::make_loops($lines{$layer->id});
+            $layer->slicing_errors(1) if $slicing_errors;
+            $layerm->make_surfaces($loops);
+            
+            # free memory
+            delete $lines{$layer->id};
+        }
     }
     
     # free memory
     $self->meshes(undef);
     
     # remove last layer(s) if empty
-    pop @{$self->layers} while @{$self->layers} && (!map @{$_->lines}, @{$self->layers->[-1]->regions});
+    pop @{$self->layers} while @{$self->layers} && (!map @{$_->slices}, @{$self->layers->[-1]->regions});
     
     foreach my $layer (@{ $self->layers }) {
-        Slic3r::debugf "Making surfaces for layer %d (slice z = %f):\n",
-            $layer->id, unscale $layer->slice_z if $Slic3r::debug;
-        
-        # layer currently has many lines representing intersections of
-        # model facets with the layer plane. there may also be lines
-        # that we need to ignore (for example, when two non-horizontal
-        # facets share a common edge on our plane, we get a single line;
-        # however that line has no meaning for our layer as it's enclosed
-        # inside a closed polyline)
-        
-        # build surfaces from sparse lines
-        foreach my $layerm (@{$layer->regions}) {
-            my ($slicing_errors, $loops) = Slic3r::TriangleMesh::make_loops($layerm->lines);
-            $layer->slicing_errors(1) if $slicing_errors;
-            $layerm->make_surfaces($loops);
-            
-            # free memory
-            $layerm->lines(undef);
-        }
-        
         # merge all regions' slices to get islands
         $layer->make_slices;
     }
diff --git a/lib/Slic3r/TriangleMesh.pm b/lib/Slic3r/TriangleMesh.pm
index e0698b4a6..329070617 100644
--- a/lib/Slic3r/TriangleMesh.pm
+++ b/lib/Slic3r/TriangleMesh.pm
@@ -1,7 +1,7 @@
 package Slic3r::TriangleMesh;
 use Moo;
 
-use List::Util qw(reduce min max);
+use List::Util qw(reduce min max first);
 use Slic3r::Geometry qw(X Y Z A B unscale same_point);
 use Slic3r::Geometry::Clipper qw(union_ex);
 use Storable;
@@ -18,13 +18,13 @@ has 'edges_facets'  => (is => 'rw'); # id => [ $f1_id, $f2_id, (...) ]
 use constant MIN => 0;
 use constant MAX => 1;
 
-use constant I_FMT              => 'ffllLllc';
-use constant I_B                => 0;
-use constant I_A_ID             => 1;
-use constant I_B_ID             => 2;
-use constant I_FACET_INDEX      => 3;
-use constant I_PREV_FACET_INDEX => 4;
-use constant I_NEXT_FACET_INDEX => 5;
+use constant I_FMT              => 'ffffllllc';
+use constant I_A                => 0;
+use constant I_B                => 1;
+use constant I_A_ID             => 2;
+use constant I_B_ID             => 3;
+use constant I_EDGE_A_ID        => 4;
+use constant I_EDGE_B_ID        => 5;
 use constant I_FACET_EDGE       => 6;
 
 use constant FE_TOP             => 0;
@@ -151,9 +151,11 @@ sub check_manifoldness {
     
     $self->analyze;
     
-    # look for any edges not connected to exactly two facets
+    # look for any edges belonging to an odd number of facets
+    # we should actually check that each pair of facets belonging to this edge
+    # has compatible winding order
     my ($first_bad_edge_id) =
-        grep { @{ $self->edges_facets->[$_] } != 2 } 0..$#{$self->edges_facets};
+        grep { @{ $self->edges_facets->[$_] } % 2 } 0..$#{$self->edges_facets};
     if (defined $first_bad_edge_id) {
         warn sprintf "Warning: The input file contains a hole near edge %f,%f,%f-%f,%f,%f (not manifold). "
             . "You might want to repair it and retry, or to check the resulting G-code before printing anyway.\n",
@@ -171,8 +173,8 @@ sub unpack_line {
     my ($packed) = @_;
     
     my $data = [ unpack I_FMT, $packed ];
-    splice @$data, 0, 2, [ @$data[0,1] ];
-    $data->[$_] = undef for grep $data->[$_] == -1, I_A_ID, I_B_ID, I_FACET_EDGE, I_PREV_FACET_INDEX, I_NEXT_FACET_INDEX;
+    splice @$data, 0, 4, [ @$data[0,1] ], [ @$data[2,3] ];
+    $data->[$_] = undef for grep $data->[$_] == -1, I_A_ID, I_B_ID, I_EDGE_A_ID, I_EDGE_B_ID, I_FACET_EDGE;
     return $data;
 }
 
@@ -181,138 +183,69 @@ sub make_loops {
     my @lines = map unpack_line($_), @$lines;
     
     # remove tangent edges
-    {
-        for (my $i = 0; $i <= $#lines; $i++) {
-            next unless defined $lines[$i] && defined $lines[$i][I_FACET_EDGE];
-            # if the line is a facet edge, find another facet edge
-            # having the same endpoints but in reverse order
-            for (my $j = $i+1; $j <= $#lines; $j++) {
-                next unless defined $lines[$j] && defined $lines[$j][I_FACET_EDGE];
-                
-                # are these facets adjacent? (sharing a common edge on this layer)
-                if ($lines[$i][I_A_ID] == $lines[$j][I_B_ID] && $lines[$i][I_B_ID] == $lines[$j][I_A_ID]) {
-                
-                    # if they are both oriented upwards or downwards (like a 'V')
-                    # then we can remove both edges from this layer since it won't 
-                    # affect the sliced shape
-                    if ($lines[$j][I_FACET_EDGE] == $lines[$i][I_FACET_EDGE]) {
-                        $lines[$i] = undef;
-                        $lines[$j] = undef;
-                        last;
-                    }
-                    
-                    # if one of them is oriented upwards and the other is oriented
-                    # downwards, let's only keep one of them (it doesn't matter which
-                    # one since all 'top' lines were reversed at slicing)
-                    if ($lines[$i][I_FACET_EDGE] == FE_TOP && $lines[$j][I_FACET_EDGE] == FE_BOTTOM) {
-                        $lines[$j] = undef;
-                        last;
-                    }
+    for my $i (0 .. $#lines) {
+        next unless defined $lines[$i] && defined $lines[$i][I_FACET_EDGE];
+        # if the line is a facet edge, find another facet edge
+        # having the same endpoints but in reverse order
+        for my $j ($i+1 .. $#lines) {
+            next unless defined $lines[$j] && defined $lines[$j][I_FACET_EDGE];
+            
+            # are these facets adjacent? (sharing a common edge on this layer)
+            if ($lines[$i][I_A_ID] == $lines[$j][I_B_ID] && $lines[$i][I_B_ID] == $lines[$j][I_A_ID]) {
+            
+                # if they are both oriented upwards or downwards (like a 'V')
+                # then we can remove both edges from this layer since it won't 
+                # affect the sliced shape
+                if ($lines[$j][I_FACET_EDGE] == $lines[$i][I_FACET_EDGE]) {
+                    $lines[$i] = undef;
+                    $lines[$j] = undef;
+                    last;
                 }
                 
+                # if one of them is oriented upwards and the other is oriented
+                # downwards, let's only keep one of them (it doesn't matter which
+                # one since all 'top' lines were reversed at slicing)
+                if ($lines[$i][I_FACET_EDGE] == FE_TOP && $lines[$j][I_FACET_EDGE] == FE_BOTTOM) {
+                    $lines[$j] = undef;
+                    last;
+                }
             }
+            
         }
     }
-    
     @lines = grep $_, @lines;
     
-    # count relationships
-    my %prev_count = ();  # how many lines have the same prev_facet_index
-    my %a_count    = ();  # how many lines have the same a_id
-    foreach my $line (@lines) {
-        if (defined $line->[I_PREV_FACET_INDEX]) {
-            $prev_count{$line->[I_PREV_FACET_INDEX]}++;
-        }
-        if (defined $line->[I_A_ID]) {
-            $a_count{$line->[I_A_ID]}++;
-        }
-    }
-    
-    foreach my $point_id (grep $a_count{$_} > 1, keys %a_count) {
-        my @lines_starting_here = grep defined $_->[I_A_ID] && $_->[I_A_ID] == $point_id, @lines;
-        Slic3r::debugf "%d lines start at point %d\n", scalar(@lines_starting_here), $point_id;
-        
-        # if two lines start at this point, one being a 'top' facet edge and the other being a 'bottom' one,
-        # then remove the top one and those following it (removing the top or the bottom one is an arbitrary
-        # choice)
-        # The "// ''" on the next line avoids uninitialized value errors mentioned in issue #357 but these
-        # errors occur on fixed models so the root cause still needs to be found
-        if (@lines_starting_here == 2 && join('', sort map $_->[I_FACET_EDGE] // '', @lines_starting_here) eq FE_TOP.FE_BOTTOM) { #/
-            my @to_remove = grep $_->[I_FACET_EDGE] == FE_TOP, @lines_starting_here;
-            while (!grep defined $_->[I_B_ID] && $_->[I_B_ID] == $to_remove[-1]->[I_B_ID] && $_ ne $to_remove[-1], @lines) {
-                push @to_remove, grep defined $_->[I_A_ID] && $_->[I_A_ID] == $to_remove[-1]->[I_B_ID], @lines;
-            }
-            my %to_remove = map {$_ => 1} @to_remove;
-            @lines = grep !$to_remove{$_}, @lines;
-        } else {
-            Slic3r::debugf "  this shouldn't happen and should be further investigated\n";
-            if (0) {
-                require "Slic3r/SVG.pm";
-                Slic3r::SVG::output("same_point.svg",
-                    lines       => [ map $_->line, grep !defined $_->[I_FACET_EDGE], @lines ],
-                    red_lines   => [ map $_->line, grep defined $_->[I_FACET_EDGE], @lines ],
-                    #points      => [ $self->vertices->[$point_id] ],
-                    no_arrows => 0,
-                );
-            }
-        }
-    }
-    
-    # optimization: build indexes of lines
-    my %by_facet_index = map { $lines[$_][I_FACET_INDEX] => $_ }
-        grep defined $lines[$_][I_FACET_INDEX],
-        (0..$#lines);
-    my %by_a_id = map { $lines[$_][I_A_ID] => $_ }
-        grep defined $lines[$_][I_A_ID],
-        (0..$#lines);
-    
-    my (@polygons, @failed_loops, %visited_lines) = ();
-    my $slicing_errors = 0;
-    CYCLE: for (my $i = 0; $i <= $#lines; $i++) {
-        my $line = $lines[$i];
-        next if $visited_lines{$line};
-        my @points = ();
-        my $first_facet_index = $line->[I_FACET_INDEX];
+    my (@polygons, @failed_loops) = ();
+    CYCLE: while (@lines) {
+        # take first spare line and start a new loop
+        my @loop = (shift @lines);
         
-        do {
-            my $next_line;
-            if (defined $line->[I_NEXT_FACET_INDEX] && exists $by_facet_index{$line->[I_NEXT_FACET_INDEX]}) {
-                $next_line = $lines[$by_facet_index{$line->[I_NEXT_FACET_INDEX]}];
-            } elsif (defined $line->[I_B_ID] && exists $by_a_id{$line->[I_B_ID]}) {
-                $next_line = $lines[$by_a_id{$line->[I_B_ID]}];
-            } else {
-                Slic3r::debugf "  line has no next_facet_index or b_id\n";
-                $slicing_errors = 1;
-                push @failed_loops, [@points] if @points;
-                next CYCLE;
-            }
+        while (1) {
+            # find a line starting where last one finishes
+            my $line_idx;
+            $line_idx = first { defined $lines[$_][I_EDGE_A_ID] && $lines[$_][I_EDGE_A_ID] == $loop[-1][I_EDGE_B_ID] } 0..$#lines
+                if defined $loop[-1][I_EDGE_B_ID];
+            $line_idx ||= first { defined $lines[$_][I_A_ID] && $lines[$_][I_A_ID] == $loop[-1][I_B_ID] } 0..$#lines
+                if defined $loop[-1][I_B_ID];
             
-            if (!$next_line || $visited_lines{$next_line}) {
-                Slic3r::debugf "  failed to close this loop\n";
-                $slicing_errors = 1;
-                push @failed_loops, [@points] if @points;
-                next CYCLE;
-            } elsif (defined $next_line->[I_PREV_FACET_INDEX] && $next_line->[I_PREV_FACET_INDEX] != $line->[I_FACET_INDEX]) {
-                Slic3r::debugf "  wrong prev_facet_index\n";
-                $slicing_errors = 1;
-                push @failed_loops, [@points] if @points;
-                next CYCLE;
-            } elsif (defined $next_line->[I_A_ID] && $next_line->[I_A_ID] != $line->[I_B_ID]) {
-                Slic3r::debugf "  wrong a_id\n";
-                $slicing_errors = 1;
-                push @failed_loops, [@points] if @points;
+            if (!defined $line_idx) {
+                # check whether we closed this loop
+                if ((defined $loop[0][I_EDGE_A_ID] && defined $loop[-1][I_EDGE_B_ID] && $loop[0][I_EDGE_A_ID] == $loop[-1][I_EDGE_B_ID])
+                    || (defined $loop[0][I_A_ID] && defined $loop[-1][I_B_ID] && $loop[0][I_A_ID] == $loop[-1][I_B_ID])) {
+                    # loop is complete!
+                    push @polygons, Slic3r::Polygon->new([ map $_->[I_A], @loop ]);
+                    Slic3r::debugf "  Discovered %s polygon of %d points\n",
+                        ($polygons[-1]->is_counter_clockwise ? 'ccw' : 'cw'), scalar(@{$polygons[-1]})
+                        if $Slic3r::debug;
+                    next CYCLE;
+                }
+                
+                # we can't close this loop!
+                push @failed_loops, [@loop];
                 next CYCLE;
             }
-            
-            push @points, $next_line->[I_B];
-            $visited_lines{$next_line} = 1;
-            $line = $next_line;
-        } while ($first_facet_index != $line->[I_FACET_INDEX]);
-    
-        push @polygons, Slic3r::Polygon->new(@points);
-        Slic3r::debugf "  Discovered %s polygon of %d points\n",
-            ($polygons[-1]->is_counter_clockwise ? 'ccw' : 'cw'), scalar(@points)
-            if $Slic3r::debug;
+            push @loop, splice @lines, $line_idx, 1;
+        }
     }
     
     # TODO: we should try to combine failed loops
@@ -323,7 +256,7 @@ sub make_loops {
             if $Slic3r::debug;
     }
     
-    return ($slicing_errors, [@polygons]);
+    return (@failed_loops ? 1 : 0, [@polygons]);
 }
 
 sub rotate {
@@ -475,16 +408,13 @@ sub intersect_facet {
             # We assume that this method is never being called for horizontal
             # facets, so no other edge is going to be on this layer.
             return pack I_FMT, (
+                $a->[X], $a->[Y],       # I_A
                 $b->[X], $b->[Y],       # I_B
                 $a_id,                  # I_A_ID
                 $b_id,                  # I_B_ID
-                $facet_id,              # I_FACET_INDEX
-                -1,                     # I_PREV_FACET_INDEX
-                -1,                     # I_NEXT_FACET_INDEX
+                -1,                     # I_EDGE_A_ID
+                -1,                     # I_EDGE_B_ID
                 $edge_type,             # I_FACET_EDGE
-                
-                # Unused data:
-                # a             => [$a->[X], $a->[Y]],
             );
             #print "Horizontal edge at $z!\n";
             
@@ -511,35 +441,25 @@ sub intersect_facet {
         }
     }
     
-    if (@points_on_layer == 2 && @intersection_points == 1) {
-        $points[ $points_on_layer[1] ] = undef;
-        @points = grep $_, @points;
-    }
-    if (@points_on_layer == 2 && @intersection_points == 0) {
-        if (same_point(map $points[$_], @points_on_layer)) {
-            return ();
+    if (@points_on_layer == 2) {
+        if (@intersection_points == 1) {
+            splice @points, $points_on_layer[1], 1;
+        } elsif (@intersection_points == 0) {
+            return if same_point(@points[@points_on_layer]);
         }
     }
     
     if (@points) {
-        
         # defensive programming:
         die "Facets must intersect each plane 0 or 2 times" if @points != 2;
         
-        # connect points:
-        my ($prev_facet_index, $next_facet_index) = (undef, undef);
-        $prev_facet_index = +(grep $_ != $facet_id, @{$self->edges_facets->[$points[B][3]]})[0]
-            if defined $points[B][3];
-        $next_facet_index = +(grep $_ != $facet_id, @{$self->edges_facets->[$points[A][3]]})[0]
-            if defined $points[A][3];
-        
         return pack I_FMT, (
+            $points[B][X], $points[B][Y],   # I_A
             $points[A][X], $points[A][Y],   # I_B
             $points[B][2] // -1,            # I_A_ID /
             $points[A][2] // -1,            # I_B_ID /
-            $facet_id,                      # I_FACET_INDEX
-            $prev_facet_index // -1,        # I_PREV_FACET_INDEX  /
-            $next_facet_index // -1,        # I_NEXT_FACET_INDEX  /
+            $points[B][3] // -1,            # I_EDGE_A_ID  /
+            $points[A][3] // -1,            # I_EDGE_B_ID  /
             -1,                             # I_FACET_EDGE
         );
         #printf "  intersection points at z = %f: %f,%f - %f,%f\n", $z, map @$_, @intersection_points;