New slicing algorithm based on a topological approach rather than numeric. It should be much more robust

6 files changed, 336 insertions, 268 deletions

diff --git a/lib/Slic3r/Print.pm b/lib/Slic3r/Print.pm
index 2825897f3..f79aaaee6 100644
--- a/lib/Slic3r/Print.pm
+++ b/lib/Slic3r/Print.pm
@@ -56,17 +56,8 @@ sub new_from_mesh {
         y_length => $size[Y],
     );
     
-    $mesh->make_edge_table;
-        
     # process facets
-    for (my $i = 0; $i <= $#{$mesh->facets}; $i++) {
-        my $facet = $mesh->facets->[$i];
-        
-        # transform vertex coordinates
-        my ($normal, @vertices) = @$facet;
-        $mesh->slice_facet($print, $i, $normal, @vertices);
-    }
-    
+    $mesh->slice_facet($print, $_) for 0..$#{$mesh->facets};
     die "Invalid input file\n" if !@{$print->layers};
     
     # remove last layer if empty
diff --git a/lib/Slic3r/STL.pm b/lib/Slic3r/STL.pm
index d27b95096..eec4fb6c0 100644
--- a/lib/Slic3r/STL.pm
+++ b/lib/Slic3r/STL.pm
@@ -42,15 +42,76 @@ sub read_file {
     
     my $vertices = [];
     {
-        my %vertices_map = ();
+        my %vertices_map = ();    # given a vertex's coordinates, what's its index?
+        my @vertices_facets = (); # given a vertex index, what are the indexes of its tangent facets?
         for (my $f = 0; $f <= $#$facets; $f++) {
             for (1..3) {
                 my $point_id = join ',', @{$facets->[$f][$_]};
                 if (exists $vertices_map{$point_id}) {
                     $facets->[$f][$_] = $vertices_map{$point_id};
+                    push @{$vertices_facets[$facets->[$f][$_]]}, $f;
                 } else {
                     push @$vertices, $facets->[$f][$_];
                     $facets->[$f][$_] = $vertices_map{$point_id} = $#$vertices;
+                    $vertices_facets[$#$vertices] = [$f];
+                }
+            }
+        }
+        
+        # The following loop checks that @vertices_facets only groups facets that
+        # are really connected together (i.e. neighbors or sharing neighbors);
+        # in other words it takes care of multiple vertices occupying the same
+        # point in space. It enforces topological correctness which is needed by
+        # the slicing algorithm.
+        # I'm keeping it disabled until I find a good test case.
+        if (0) {
+            my $vertices_count = $#$vertices; # store it to avoid processing newly created vertices
+            for (my $v = 0; $v <= $vertices_count; $v++) {
+                my $more_than_one_vertex_in_this_point = 0;
+                while (@{$vertices_facets[$v]}) {
+                    my @facets_indexes = @{$vertices_facets[$v]};
+                    @{$vertices_facets[$v]} = ();
+                    
+                    my @this_f = shift @facets_indexes;
+                    CYCLE: while (@facets_indexes && @this_f) {
+                        
+                        # look for a facet that is connected to $this_f[-1] and whose common line contains $v
+                        my @other_vertices_indexes = grep $_ != $v, @{$facets->[$this_f[-1]]}[1..3];
+                        
+                        OTHER: for my $other_f (@facets_indexes) {
+                            # facet is connected if it shares one more point
+                            for (grep $_ != $v, @{$facets->[$other_f]}[1..3]) {
+                                if ($_ ~~ @other_vertices_indexes) {
+                                    #printf "facet %d is connected to $other_f (sharing vertices $v and $_)\n", $this_f[-1];
+                                    
+                                    # TODO: we should ensure that the common edge has a different orientation
+                                    # for each of the two adjacent facets
+                                    
+                                    push @this_f, $other_f;
+                                    @facets_indexes = grep $_ != $other_f, @facets_indexes;
+                                    next CYCLE;
+                                }
+                            }
+                        }
+                        # if we're here, then we couldn't find any facet connected to $this_f[-1]
+                        # so we should move this one to a different cluster (that is, a new vertex)
+                        # (or ignore it if it turns to be a non-manifold facet)
+                        if (@this_f > 1) {
+                            push @{$vertices_facets[$v]}, $this_f[-1];
+                            pop @this_f;
+                            $more_than_one_vertex_in_this_point++;
+                        } else {
+                            last CYCLE;
+                        }
+                    }
+                    
+                    if ($more_than_one_vertex_in_this_point) {
+                        Slic3r::debugf "  more than one vertex in the same point\n";
+                        push @$vertices, $vertices->[$v];
+                        for my $f (@this_f) {
+                            $facets->[$f][$_] = $#$vertices for grep $facets->[$f][$_] == $v, 1..3;
+                        }
+                    }
                 }
             }
         }
@@ -67,7 +128,7 @@ sub _read_ascii {
     my $facet;
     seek $fh, 0, 0;
     while (<$fh>) {
-        chomp;
+        s/\R+$//;
         if (!$facet) {
             /^\s*facet\s+normal\s+$point_re/ or next;
             $facet = [ [$1, $2, $3] ];
@@ -77,7 +138,7 @@ sub _read_ascii {
                 undef $facet;
             } else {
                 /^\s*vertex\s+$point_re/ or next;
-                push @$facet, [$1, $2, $3];
+                push @$facet, [map $_ * 1, $1, $2, $3];
             }
         }
     }
@@ -106,31 +167,33 @@ sub write_file {
     open my $fh, '>', $file;
     
     $binary
-        ? _write_binary($fh, $mesh->facets)
-        : _write_ascii($fh, $mesh->facets);
+        ? _write_binary($fh, $mesh)
+        : _write_ascii($fh, $mesh);
     
     close $fh;
 }
 
 sub _write_binary {
-    my ($fh, $facets) = @_;
+    my ($fh, $mesh) = @_;
     
     die "bigfloat" unless length(pack "f", 1) == 4;
     
     binmode $fh;
     print $fh pack 'x80';
-    print $fh pack 'L', ($#$facets + 1);
-    print $fh pack '(f<3)4S', (map @$_, @$_), 0 for @$facets;
+    print $fh pack 'L', scalar(@{$mesh->facets});
+    foreach my $facet (@{$mesh->facets}) {
+        print $fh pack '(f<3)4S', @{$facet->[0]}, (map @{$mesh->vertices->[$_]}, @$facet[1,2,3]), 0;
+    }
 }
 
 sub _write_ascii {
-    my ($fh, $facets) = @_;
+    my ($fh, $mesh) = @_;
     
     printf $fh "solid\n";
-    foreach my $facet (@$facets) {
+    foreach my $facet (@{$mesh->facets}) {
         printf $fh "   facet normal %f %f %f\n", @{$facet->[0]};
         printf $fh "      outer loop\n";
-        printf $fh "         vertex %f %f %f\n", @$_ for @$facet[1,2,3];
+        printf $fh "         vertex %f %f %f\n", @{$mesh->vertices->[$_]} for @$facet[1,2,3];
         printf $fh "      endloop\n";
         printf $fh "   endfacet\n";
     }
diff --git a/lib/Slic3r/TriangleMesh.pm b/lib/Slic3r/TriangleMesh.pm
index 4d575f4e6..89835d179 100644
--- a/lib/Slic3r/TriangleMesh.pm
+++ b/lib/Slic3r/TriangleMesh.pm
@@ -1,46 +1,113 @@
 package Slic3r::TriangleMesh;
 use Moo;
 
-use Slic3r::Geometry qw(X Y Z A B PI epsilon same_point points_coincide angle3points
-    merge_collinear_lines nearest_point polyline_lines);
+use Slic3r::Geometry qw(X Y Z A B epsilon same_point);
 use XXX;
 
-has 'vertices'      => (is => 'ro', default => sub { [] });
-has 'facets'        => (is => 'ro', default => sub { [] });
-has 'edges'         => (is => 'ro', default => sub { [] });
-has 'edge_table'    => (is => 'ro', default => sub { {} });
-has 'edge_facets'   => (is => 'ro', default => sub { {} });
+# public
+has 'vertices'      => (is => 'ro', required => 1);         # id => [ [$x1,$y1],[$x2,$y2],[$x3,$y3] ]
+has 'facets'        => (is => 'ro', required => 1);         # id => [ $normal, $v1_id, $v2_id, $v3_id ]
+
+# private
+has 'edges'         => (is => 'ro', default => sub { [] }); # id => [ $v1_id, $v2_id ]
+has 'facets_edges'  => (is => 'ro', default => sub { [] }); # id => [ $e1_id, $e2_id, $e3_id ]
+has 'edges_facets'  => (is => 'ro', default => sub { [] }); # id => [ $f1_id, $f2_id, (...) ]
 
 use constant MIN => 0;
 use constant MAX => 1;
 
-sub make_edge_table {
+sub BUILD {
     my $self = shift;
     
     @{$self->edges} = ();
-    %{$self->edge_table} = ();
-    %{$self->edge_facets} = ();
-    for (my $facet_index = 0; $facet_index <= $#{$self->facets}; $facet_index++) {
-        my $facet = $self->facets->[$facet_index];
-        foreach my $edge ($self->facet_edges($facet)) {
-            my $edge_id = $self->edge_id($edge);
-            if (!exists $self->edge_table->{$edge_id}) {
+    @{$self->facets_edges} = ();
+    @{$self->edges_facets} = ();
+    my %table = ();  # edge_coordinates => edge_id
+    
+    for (my $facet_id = 0; $facet_id <= $#{$self->facets}; $facet_id++) {
+        my $facet = $self->facets->[$facet_id];
+        $self->facets_edges->[$facet_id] = [];
+        
+        # reorder vertices so that the first one is the one with lowest Z
+        # this is needed to get all intersection lines in a consistent order
+        # (external on the right of the line)
+        {
+            my @z_order = sort { $self->vertices->[$facet->[$a]][Z] <=> $self->vertices->[$facet->[$b]][Z] } 1..3;
+            @$facet[1..3] = (@$facet[$z_order[0]..3], @$facet[1..($z_order[0]-1)]);
+        }
+        
+        # ignore the normal if provided
+        my @vertices = @$facet[-3..-1];
+        
+        foreach my $edge ($self->_facet_edges($facet_id)) {
+            my $edge_coordinates = join ';', sort @$edge;
+            my $edge_id = $table{$edge_coordinates};
+            if (!defined $edge_id) {
+                # Note that the order of vertices in $self->edges is *casual* because it is only
+                # good for one of the two adjacent facets. For this reason, it must not be used
+                # when dealing with single facets.
                 push @{$self->edges}, $edge;
-                $self->edge_table->{$edge_id} = $#{$self->edges};
-                $self->edge_facets->{$edge_id} = [];
+                $edge_id = $#{$self->edges};
+                $table{$edge_coordinates} = $edge_id;
+                $self->edges_facets->[$edge_id] = [];
             }
-            my $edge_index = $self->edge_table->{$edge_id};
-            push @{$self->edge_facets->{$edge_id}}, $facet_index;
+            
+            push @{$self->facets_edges->[$facet_id]}, $edge_id;
+            push @{$self->edges_facets->[$edge_id]}, $facet_id;
         }
     }
 }
 
-sub check_manifoldness {
+sub _facet_edges {
     my $self = shift;
+    my ($facet_id) = @_;
     
-    $self->make_edge_table;
+    my $facet = $self->facets->[$facet_id];
+    return (
+        [ $facet->[1], $facet->[2] ],
+        [ $facet->[2], $facet->[3] ],
+        [ $facet->[3], $facet->[1] ],
+    );
+}
+
+# This method is supposed to remove narrow triangles, but it actually doesn't 
+# work much; I'm committing it for future reference but I'm going to remove it later.
+# Note: a 'clean' method should actually take care of non-manifold facets and remove
+# them.
+sub clean {
+    my $self = shift;
+    
+    # retrieve all edges shared by more than two facets;
+    my @weird_edges = grep { @{$self->edge_facets->{$_}} != 2 } keys %{$self->edge_facets};
+    
+    # usually most of these facets are very narrow triangles whose two edges
+    # are detected as collapsed, and thus added twice to the edge in edge_fasets table
+    # let's identify these triangles
+    my @narrow_facets_indexes = ();
+    foreach my $edge_id (@weird_edges) {
+        my %facet_count = ();
+        $facet_count{$_}++ for @{$self->edge_facets->{$edge_id}};
+        @{$self->edge_facets->{$edge_id}} = grep $facet_count{$_} == 1, keys %facet_count;
+        push @narrow_facets_indexes, grep $facet_count{$_} > 1, keys %facet_count;
+    }
     
-    if (grep { @$_ != 2 } values %{$self->edge_facets}) {
+    # remove identified narrow facets
+    foreach my $facet_id (@narrow_facets_indexes) {last;
+         splice @{$self->facets}, $facet_id, 1;
+         splice @{$self->facets_edges}, $facet_id, 1;
+         foreach my $facet_ides (values %{$self->edge_facets}) {
+            @$facet_ides = map { $_ > $facet_id ? ($_-1) : $_ } @$facet_ides;
+         }
+    }
+    
+    Slic3r::debugf "%d narrow facets removed\n", scalar(@narrow_facets_indexes)
+        if @narrow_facets_indexes;
+}
+
+sub check_manifoldness {
+    my $self = shift;
+    
+    if (grep { @$_ != 2 } @{$self->edges_facets}) {
         warn "Warning: The input file is not manifold. You might want to check the "
             . "resulting gcode before printing.\n";
     }
@@ -59,171 +126,127 @@ sub make_loops {
             # 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]->facet_edge;
-                next unless $lines[$j]->facet_edge eq $lines[$i]->facet_edge;
-                if (same_point($lines[$i]->a, $lines[$j]->b) && same_point($lines[$i]->b, $lines[$j]->a)) {
-                    $lines[$j] = undef;
-                    last;
+                next unless defined $lines[$j] && $lines[$j]->facet_edge;
+                
+                # are these facets adjacent? (sharing a common edge on this layer)
+                if ($lines[$i]->a_id == $lines[$j]->b_id && $lines[$i]->b_id == $lines[$j]->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]->facet_edge eq $lines[$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]->facet_edge eq 'top' && $lines[$j]->facet_edge eq 'bottom') {
+                        $lines[$j] = undef;
+                        last;
+                    }
                 }
+                
             }
         }
     }
     
-    my $sparse_lines = [ map $_->line, grep $_, @lines ];
-    
-    # detect closed loops
+    @lines = grep $_, @lines;
     
-    my (@polygons, %visited_lines, @discarded_lines, @discarded_polylines) = ();
+    # 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->prev_facet_index) {
+            $prev_count{$line->prev_facet_index}++;
+        }
+        if (defined $line->a_id) {
+            $a_count{$line->a_id}++;
+        }
+    }
     
-    my $detect = sub {
-        my @lines = @$sparse_lines;
-        (@polygons, %visited_lines, @discarded_lines, @discarded_polylines) = ();
-        my $get_point_id = sub { sprintf "%.0f,%.0f", @{$_[0]} };
+    foreach my $point_id (grep $a_count{$_} > 1, keys %a_count) {
+        my @lines_starting_here = grep defined $_->a_id && $_->a_id == $point_id, @lines;
+        Slic3r::debugf "%d lines start at point %d\n", scalar(@lines_starting_here), $point_id;
         
-        my (%pointmap, @pointmap_keys) = ();
-        foreach my $line (@lines) {
-            my $point_id = $get_point_id->($line->[A]);
-            if (!exists $pointmap{$point_id}) {
-                $pointmap{$point_id} = [];
-                push @pointmap_keys, $line->[A];
+        # 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)
+        if (@lines_starting_here == 2 && join(',', sort map $_->facet_edge, @lines_starting_here) eq 'bottom,top') {
+            my @to_remove = grep $_->facet_edge eq 'top', @lines_starting_here;
+            while (!grep defined $_->b_id && $_->b_id == $to_remove[-1]->b_id && $_ ne $to_remove[-1], @lines) {
+                push @to_remove, grep defined $_->a_id && $_->a_id == $to_remove[-1]->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(undef, "same_point.svg",
+                    lines       => [ map $_->line, grep !$_->facet_edge, @lines ],
+                    red_lines   => [ map $_->line, grep $_->facet_edge, @lines ],
+                    points      => [ $self->vertices->[$point_id] ],
+                    no_arrows => 0,
+                );
             }
-            push @{ $pointmap{$point_id} }, $line;
         }
+    }
+    
+    my (@polygons, %visited_lines) = ();
+    CYCLE: for (my $i = 0; $i <= $#lines; $i++) {
+        my $line = $lines[$i];
+        next if $visited_lines{$line};
+        my @points = ();
+        my $first_facet_index = $line->facet_index;
         
-        my $n = 0;
-        while (my $first_line = shift @lines) {
-            next if $visited_lines{ $first_line->id };
-            my @points = @$first_line;
-            
-            my @seen_lines = ($first_line);
-            my %seen_points = map { $get_point_id->($points[$_]) => $_ } 0..1;
-            
-            CYCLE: while (1) {
-                my $next_lines = $pointmap{ $get_point_id->($points[-1]) };
-                
-                # shouldn't we find the point, let's try with a slower algorithm
-                # as approximation may make the coordinates differ
-                if (!$next_lines) {
-                    my $nearest_point = nearest_point($points[-1], \@pointmap_keys);
-                    #printf "  we have a nearest point: %f,%f (%s)\n", @$nearest_point, $get_point_id->($nearest_point);
-                    
-                    if ($nearest_point) {
-                        local $Slic3r::Geometry::epsilon = 1000000;
-                        $next_lines = $pointmap{$get_point_id->($nearest_point)}
-                            if points_coincide($points[-1], $nearest_point);
+        do {
+            my $next_line;
+            if (defined $line->next_facet_index) {
+                for (@lines) {
+                    if ($_->facet_index == $line->next_facet_index) {
+                        $next_line = $_;
+                        last;
                     }
                 }
-                
-                if (0 && !$next_lines) {
-                    require "Slic3r/SVG.pm";
-                    Slic3r::SVG::output(undef, "no_lines.svg",
-                        lines       => [ grep !$_->isa('Slic3r::Line::FacetEdge'), @lines ],
-                        red_lines   => [ grep  $_->isa('Slic3r::Line::FacetEdge'), @lines ],
-                        points      => [ $points[-1] ],
-                        no_arrows => 1,
-                    );
-                }
-                
-                $next_lines
-                    or printf("No lines start at point %s. This shouldn't happen. Please check the model for manifoldness.\n", $get_point_id->($points[-1]));
-                last CYCLE if !$next_lines or !@$next_lines;
-                
-                my @ordered_next_lines = sort 
-                    { angle3points($points[-1], $points[-2], $next_lines->[$a][B]) <=> angle3points($points[-1], $points[-2], $next_lines->[$b][B]) } 
-                    0..$#$next_lines;
-                
-                #if (@$next_lines > 1) {
-                #    Slic3r::SVG::output(undef, "next_line.svg",
-                #        lines        => $next_lines,
-                #        red_lines    => [ polyline_lines([@points]) ],
-                #        green_lines  => [ $next_lines->[ $ordered_next_lines[0] ] ],
-                #    );
-                #}
-                
-                my ($next_line) = splice @$next_lines, $ordered_next_lines[0], 1;
-                push @seen_lines, $next_line;
-                
-                push @points, $next_line->[B];
-                
-                my $point_id = $get_point_id->($points[-1]);
-                if ($seen_points{$point_id}) {
-                    splice @points, 0, $seen_points{$point_id};
-                    last CYCLE;
-                }
-                
-                $seen_points{$point_id} = $#points;
-            }
-            
-            if (@points < 4 || !points_coincide($points[0], $points[-1])) {
-                # discarding polyline
-                push @discarded_lines, @seen_lines;
-                if (@points > 2) {
-                    push @discarded_polylines, [@points];
+            } elsif (defined $line->b_id) {
+                for (@lines) {
+                    next if !defined $_->a_id;
+                    if ($_->a_id == $line->b_id) {
+                        $next_line = $_;
+                        last;
+                    }
                 }
-                next;
-            }
-            
-            $visited_lines{ $_->id } = 1 for @seen_lines;
-            pop @points;
-            Slic3r::debugf "  Discovered polygon of %d points\n", scalar(@points);
-            push @polygons, Slic3r::Polygon->new(@points);
-            pop @polygons if !$polygons[-1]->cleanup;
-        }
-    };
-    
-    $detect->();
-    
-    # Now, if we got a clean and manifold model then @polygons would contain everything
-    # we need to draw our layer. In real life, sadly, things are different and it is likely
-    # that the above algorithm wasn't able to detect every polygon. This may happen because
-    # of non-manifoldness or because of many close lines, often overlapping; both situations
-    # make a head-to-tail search difficult.
-    # On the other hand, we can safely assume that every polygon we detected is correct, as 
-    # the above algorithm is quite strict. We can take a brute force approach to connect any
-    # other line.
-    
-    # So, let's first check what lines were not detected as part of polygons.
-    if (@discarded_lines) {
-        Slic3r::debugf "  %d lines out of %d were discarded and %d polylines were not closed\n",
-            scalar(@discarded_lines), scalar(@lines), scalar(@discarded_polylines);
-        print "  Warning: errors while parsing this layer (dirty or non-manifold model).\n";
-        
-        my $total_detected_length = 0;
-        $total_detected_length += $_->length for map $_->lines, @polygons;
-        my $total_discarded_length = 0;
-        $total_discarded_length += $_->length for map polyline_lines($_), @discarded_polylines;
-        $total_discarded_length += $_->length for @discarded_lines;
-        my $discarded_ratio = $total_detected_length
-            ? ($total_discarded_length / $total_detected_length)
-            : 0;
-        
-        Slic3r::debugf "  length ratio of discarded lines is %f\n", $discarded_ratio;
-        
-        if ($discarded_ratio > 0.00001) {
-            print "  Retrying with slower algorithm.\n";
-            
-            if (0) {
-                require "Slic3r/SVG.pm";
-                Slic3r::SVG::output(undef, "layer" . $layer->id . "_detected.svg",
-                    white_polygons => \@polygons,
-                );
-                Slic3r::SVG::output(undef, "layer" . $layer->id . "_discarded_lines.svg",
-                    red_lines   => \@discarded_lines,
-                );
-                Slic3r::SVG::output(undef, "layer" . $layer->id . "_discarded_polylines.svg",
-                    polylines   => \@discarded_polylines,
-                );
+            } else {
+                Slic3r::debugf "  line has no next_facet_index or b_id\n";
+                $layer->slicing_errors(1);
+                next CYCLE;
             }
             
-            $sparse_lines = merge_collinear_lines($sparse_lines);
-            eval { $detect->(); };
-            warn $@ if $@;
-            
-            if (@discarded_lines) {
-                print "  Warning: even slow detection algorithm threw errors. Review the output before printing.\n";
+            if (!$next_line) {
+                Slic3r::debugf "  failed to close this loop\n";
                 $layer->slicing_errors(1);
+                next CYCLE;
+            } elsif (defined $next_line->prev_facet_index && $next_line->prev_facet_index != $line->facet_index) {
+                Slic3r::debugf "  wrong prev_facet_index\n";
+                $layer->slicing_errors(1);
+                next CYCLE;
+            } elsif (defined $next_line->a_id && $next_line->a_id != $line->b_id) {
+                Slic3r::debugf "  wrong a_id\n";
+                $layer->slicing_errors(1);
+                next CYCLE;
             }
-        }
+            
+            push @points, $next_line->b;
+            $visited_lines{$next_line} = 1;
+            $line = $next_line;
+        } while ($first_facet_index != $line->facet_index);
+    
+        Slic3r::debugf "  Discovered polygon of %d points\n", scalar(@points);
+        push @polygons, Slic3r::Polygon->new(@points);
+        pop @polygons if !$polygons[-1]->cleanup;
     }
     
     return [@polygons];
@@ -303,18 +326,18 @@ sub size {
 
 sub slice_facet {
     my $self = shift;
-    my ($print, $facet_index, $normal, @vertices) = @_;
+    my ($print, $facet_id) = @_;
+    my ($normal, @vertices) = @{$self->facets->[$facet_id]};
     Slic3r::debugf "\n==> FACET %d (%f,%f,%f - %f,%f,%f - %f,%f,%f):\n",
-        $facet_index, map @{$self->vertices->[$_]}, @vertices
+        $facet_id, map @{$self->vertices->[$_]}, @vertices
         if $Slic3r::debug;
     
-    my @vertices_coordinates = map $self->vertices->[$_], @vertices;
-    
     # find the vertical extents of the facet
     my ($min_z, $max_z) = (99999999999, -99999999999);
-    foreach my $vertex (@vertices_coordinates) {
-        $min_z = $vertex->[Z] if $vertex->[Z] < $min_z;
-        $max_z = $vertex->[Z] if $vertex->[Z] > $max_z;
+    foreach my $vertex (@vertices) {
+        my $vertex_z = $self->vertices->[$vertex][Z];
+        $min_z = $vertex_z if $vertex_z < $min_z;
+        $max_z = $vertex_z if $vertex_z > $max_z;
     }
     Slic3r::debugf "z: min = %.0f, max = %.0f\n", $min_z, $max_z;
     
@@ -331,65 +354,62 @@ sub slice_facet {
     my $max_layer = int($max_z * $Slic3r::resolution / $Slic3r::layer_height) + 1;
     Slic3r::debugf "layers: min = %s, max = %s\n", $min_layer, $max_layer;
     
-    # reorder vertices so that the first one is the one with lowest Z
-    # this is needed to get all intersection lines in a consistent order
-    # (external on the right of the line)
-    {
-        my @z_order = sort { $vertices_coordinates[$a][Z] <=> $vertices_coordinates[$b][Z] } 0..2;
-        @vertices = (splice(@vertices, $z_order[0]), splice(@vertices, 0, $z_order[0]));
-    }
-    
     for (my $layer_id = $min_layer; $layer_id <= $max_layer; $layer_id++) {
         my $layer = $print->layer($layer_id);
-        $layer->add_line($_) for $self->intersect_facet($facet_index, \@vertices, $layer->slice_z);
+        $layer->add_line($_) for $self->intersect_facet($facet_id, $layer->slice_z);
     }
 }
 
 sub intersect_facet {
     my $self = shift;
-    my ($facet_index, $vertices, $z) = @_;
+    my ($facet_id, $z) = @_;
     
-    # build the three segments of the triangle facet
-    my @edges = $self->facet_edges($vertices);
+    my @vertices_ids        = @{$self->facets->[$facet_id]}[1..3];
+    my @edge_ids            = @{$self->facets_edges->[$facet_id]};
+    my @edge_vertices_ids   = $self->_facet_edges($facet_id);
     
     my (@lines, @points, @intersection_points, @points_on_layer) = ();
         
-    foreach my $edge (@edges) {
-        my ($a, $b) = @$edge;
-        my $edge_id = $self->edge_id($edge);
+    for my $e (0..2) {
+        my $edge_id         = $edge_ids[$e];
+        my ($a_id, $b_id)   = @{$edge_vertices_ids[$e]};
+        my ($a, $b)         = map $self->vertices->[$_], ($a_id, $b_id);
         #printf "Az = %f, Bz = %f, z = %f\n", $a->[Z], $b->[Z], $z;
         
-        if (abs($a->[Z] - $b->[Z]) < epsilon && abs($a->[Z] - $z) < epsilon) {
+        #if (abs($a->[Z] - $b->[Z]) < epsilon && abs($a->[Z] - $z) < epsilon) {
+        if ($a->[Z] == $b->[Z] && $a->[Z] == $z) {
             # edge is horizontal and belongs to the current layer
-            my $edge_type = (grep $self->vertices->[$_][Z] < $z - epsilon, @$vertices) ? 'top' : 'bottom';
-            ($a, $b) = ($b, $a) if $edge_type eq 'top';
+            my $edge_type = (grep $self->vertices->[$_][Z] < $z, @vertices_ids) ? 'top' : 'bottom';
+            if ($edge_type eq 'top') {
+                ($a, $b) = ($b, $a);
+                ($a_id, $b_id) = ($b_id, $a_id);
+            }
             push @lines, Slic3r::TriangleMesh::IntersectionLine->new(
                 a           => [$a->[X], $a->[Y]],
                 b           => [$b->[X], $b->[Y]],
-                a_id        => sprintf("%f,%f", @$a[X,Y]),
-                b_id        => sprintf("%f,%f", @$b[X,Y]),
+                a_id        => $a_id,
+                b_id        => $b_id,
                 facet_edge  => $edge_type,
-                facet_index => $facet_index,
+                facet_index => $facet_id,
             );
             #print "Horizontal edge at $z!\n";
             
-        } elsif (abs($a->[Z] - $z) < epsilon) {
+        } elsif ($a->[Z] == $z) {
             #print "A point on plane $z!\n";
-            push @points, [ $a->[X], $a->[Y], sprintf("%f,%f", @$a[X,Y]) ];
+            push @points, [ $a->[X], $a->[Y], $a_id ];
             push @points_on_layer, $#points;
             
-        } elsif (abs($b->[Z] - $z) < epsilon) {
+        } elsif ($b->[Z] == $z) {
             #print "B point on plane $z!\n";
-            push @points, [ $b->[X], $b->[Y], sprintf("%f,%f", @$b[X,Y]) ];
+            push @points, [ $b->[X], $b->[Y], $b_id ];
             push @points_on_layer, $#points;
             
-        } elsif (($a->[Z] < ($z - epsilon) && $b->[Z] > ($z + epsilon)) 
-            || ($b->[Z] < ($z - epsilon) && $a->[Z] > ($z + epsilon))) {
+        } elsif (($a->[Z] < $z && $b->[Z] > $z) || ($b->[Z] < $z && $a->[Z] > $z)) {
             # edge intersects the current layer; calculate intersection
             push @points, [
                 $b->[X] + ($a->[X] - $b->[X]) * ($z - $b->[Z]) / ($a->[Z] - $b->[Z]),
                 $b->[Y] + ($a->[Y] - $b->[Y]) * ($z - $b->[Z]) / ($a->[Z] - $b->[Z]),
-                $edge_id,
+                undef,
                 $edge_id,
             ];
             push @intersection_points, $#points;
@@ -414,14 +434,22 @@ sub intersect_facet {
         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 Slic3r::TriangleMesh::IntersectionLine->new(
             a      => [$points[B][X], $points[B][Y]],
             b      => [$points[A][X], $points[A][Y]],
             a_id   => $points[B][2],
             b_id   => $points[A][2],
-            facet_index => $facet_index,
-            prev_facet_index => ($points[B][3] ? +(grep $_ != $facet_index, @{$self->edge_facets->{$points[B][3]}})[0] || undef : undef),
-            next_facet_index => ($points[A][3] ? +(grep $_ != $facet_index, @{$self->edge_facets->{$points[A][3]}})[0] || undef : undef),
+            facet_index => $facet_id,
+            prev_edge_id => $points[B][3],
+            next_edge_id => $points[A][3],
+            prev_facet_index => $prev_facet_index,
+            next_facet_index => $next_facet_index,
         );
         #printf "  intersection points at z = %f: %f,%f - %f,%f\n", $z, map @$_, @intersection_points;
     }
@@ -429,42 +457,16 @@ sub intersect_facet {
     return ();
 }
 
-sub facet_edges {
-    my $self = shift;
-    my ($facet) = @_;
-    
-    # ignore the normal if provided
-    my @vertices = map $self->vertices->[$_], @$facet[-3..-1];
-    
-    return (
-        [ $vertices[0], $vertices[1] ],
-        [ $vertices[1], $vertices[2] ],
-        [ $vertices[2], $vertices[0] ],
-    )
-}
-
-sub edge_id {
-    my $self = shift;
-    my ($edge) = @_;
-    
-    my @point_ids = map sprintf("%d,%d,%d", map $_ / epsilon, @$_), @$edge;
-    return join "-", sort @point_ids;
-}
-
 sub get_connected_facets {
     my $self = shift;
     my ($facet_id) = @_;
     
-    my @facets = ();
-    foreach my $edge_facets (values %{$self->edge_facets}) {
-        if (grep $_ == $facet_id, @$edge_facets) {
-            # this edge belongs to the current facet, so let's get
-            # the other facet(s)
-            push @facets, grep $_ != $facet_id, @$edge_facets;
-        }
+    my %facets = ();
+    foreach my $edge_id (@{$self->facets_edges->[$facet_id]}) {
+        $facets{$_} = 1 for @{$self->edges_facets->[$edge_id]};
     }
-    
-    return @facets;
+    delete $facets{$facet_id};
+    return keys %facets;
 }
 
 1;
diff --git a/lib/Slic3r/TriangleMesh/IntersectionLine.pm b/lib/Slic3r/TriangleMesh/IntersectionLine.pm
index 9e2ca9be0..9ef4f0b6c 100644
--- a/lib/Slic3r/TriangleMesh/IntersectionLine.pm
+++ b/lib/Slic3r/TriangleMesh/IntersectionLine.pm
@@ -8,6 +8,8 @@ has 'b_id'          => (is => 'ro', required => 1);
 has 'facet_index'   => (is => 'ro', required => 1);
 has 'prev_facet_index' => (is => 'ro', required => 0);
 has 'next_facet_index' => (is => 'ro', required => 0);
+has 'prev_edge_id'  => (is => 'ro', required => 0);
+has 'next_edge_id'  => (is => 'ro', required => 0);
 has 'facet_edge'    => (is => 'ro', default => sub {0});
 
 sub points {
diff --git a/t/stl.t b/t/stl.t
index 64606f5f7..02212dfcd 100644
--- a/t/stl.t
+++ b/t/stl.t
@@ -13,12 +13,12 @@ use Slic3r;
 use Slic3r::Geometry qw(X Y Z A B);
 use XXX;
 
-my $mesh = Slic3r::TriangleMesh->new;
-
 my @lines;
 my $z = 20;
 my @points = ([3, 4], [8, 5], [1, 9]);  # XY coordinates of the facet vertices
 
+my $mesh = Slic3r::TriangleMesh->new(facets => [], vertices => []);
+
 is_deeply lines(20, 20, 20), [
     [ $points[0], $points[1] ],
     [ $points[1], $points[2] ],
@@ -40,8 +40,8 @@ is_deeply lines(28, 20, 30), [                            ], 'lower vertex on la
     my @z = (24, 10, 16);
     is_deeply lines(@z), [
         [
-            line_plane_intersection([ vertices(@z)->[2], vertices(@z)->[0] ]),
             line_plane_intersection([ vertices(@z)->[0], vertices(@z)->[1] ]),
+            line_plane_intersection([ vertices(@z)->[2], vertices(@z)->[0] ]),
         ]
     ], 'two edges intersect';
 }
@@ -70,8 +70,8 @@ is_deeply lines(28, 20, 30), [                            ], 'lower vertex on la
     my @z = (24, 10, 20);
     is_deeply lines(@z), [
         [
-            $points[2],
             line_plane_intersection([ vertices(@z)->[0], vertices(@z)->[1] ]),
+            $points[2],
         ]
     ], 'one vertex on plane and one edge intersects';
 }
@@ -96,8 +96,8 @@ is_deeply lines(28, 20, 30), [                            ], 'lower vertex on la
     ], 'one vertex on plane and one edge intersects';
 }
 
-my @lower = $mesh->intersect_facet(0, vertices(22, 20, 20), $z);
-my @upper = $mesh->intersect_facet(0, vertices(20, 20, 10), $z);
+my @lower = intersect(22, 20, 20);
+my @upper = intersect(20, 20, 10);
 is $lower[0]->facet_edge, 'bottom', 'bottom edge on layer';
 is $upper[0]->facet_edge, 'top', 'upper edge on layer';
 
@@ -106,8 +106,18 @@ sub vertices {
     [ ($#{$mesh->vertices}-2) .. $#{$mesh->vertices} ]
 }
 
+sub add_facet {
+    push @{$mesh->facets}, [ [0,0,0], @{vertices(@_)} ];
+    $mesh->BUILD;
+}
+
+sub intersect {
+    add_facet(@_);
+    return $mesh->intersect_facet($#{$mesh->facets}, $z);
+}
+
 sub lines {
-    my @lines = $mesh->intersect_facet(0, vertices(@_), $z);
+    my @lines = intersect(@_);
     $_->a->[X] = sprintf('%.0f', $_->a->[X]) for @lines;
     $_->a->[Y] = sprintf('%.0f', $_->a->[Y]) for @lines;
     $_->b->[X] = sprintf('%.0f', $_->b->[X]) for @lines;
diff --git a/utils/split_stl.pl b/utils/split_stl.pl
index ec35211b4..6fbc0b324 100755
--- a/utils/split_stl.pl
+++ b/utils/split_stl.pl
@@ -31,7 +31,6 @@ my %opt = ();
     
     # loop while we have remaining facets
     my $part_count = 0;
-    $mesh->make_edge_table;
     while (1) {
         # get the first facet
         my @facet_queue = ();
@@ -53,7 +52,8 @@ my %opt = ();
         
         my $output_file = sprintf '%s_%02d.stl', $basename, ++$part_count;
         printf "Writing to %s\n", basename($output_file);
-        Slic3r::STL->write_file($output_file, Slic3r::TriangleMesh->new(facets => \@facets), !$opt{ascii});
+        my $new_mesh = Slic3r::TriangleMesh->new(facets => \@facets, vertices => $mesh->vertices);
+        Slic3r::STL->write_file($output_file, $new_mesh, !$opt{ascii});
     }
 }