Optimizations in the algorithm that builds loops

1 files changed, 23 insertions, 5 deletions

diff --git a/lib/Slic3r/TriangleMesh.pm b/lib/Slic3r/TriangleMesh.pm
index 5f58d0e20..be43be1de 100644
--- a/lib/Slic3r/TriangleMesh.pm
+++ b/lib/Slic3r/TriangleMesh.pm
@@ -215,17 +215,34 @@ sub make_loops {
     }
     @lines = grep $_, @lines;
     
+    # build a map of lines by EDGE_A_ID and A_ID
+    my %by_edge_a_id = my %by_a_id = ();
+    for (0..$#lines) {
+        if (defined(my $edge_a_id = $lines[$_][I_EDGE_A_ID])) {
+            $by_edge_a_id{$edge_a_id} //= [];
+            push @{ $by_edge_a_id{$edge_a_id} }, $_;
+        }
+        if (defined(my $a_id = $lines[$_][I_A_ID])) {
+            $by_a_id{$a_id} //= [];
+            push @{ $by_a_id{$a_id} }, $_;
+        }
+    }
+    
     my (@polygons, @failed_loops) = ();
-    CYCLE: while (@lines) {
+    my %used_lines = ();
+    CYCLE: while (1) {
         # take first spare line and start a new loop
-        my @loop = (shift @lines);
+        my $first_idx = first { !exists $used_lines{$_} } 0..$#lines;
+        last if !defined $first_idx;
+        $used_lines{$first_idx} = 1;
+        my @loop = ($lines[$first_idx]);
         
         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
+            $line_idx = first { !exists $used_lines{$_} } @{ $by_edge_a_id{$loop[-1][I_EDGE_B_ID]} // [] }
                 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
+            $line_idx //= first { !exists $used_lines{$_} } @{ $by_a_id{$loop[-1][I_B_ID]} // [] }
                 if defined $loop[-1][I_B_ID];
             
             if (!defined $line_idx) {
@@ -244,7 +261,8 @@ sub make_loops {
                 push @failed_loops, [@loop];
                 next CYCLE;
             }
-            push @loop, splice @lines, $line_idx, 1;
+            push @loop, $lines[$line_idx];
+            $used_lines{$line_idx} = 1;
         }
     }