From 9a904dc88dae8253ac6c7b505fa26de39d779066 Mon Sep 17 00:00:00 2001 From: Alessandro Ranellucci Date: Sun, 23 Jun 2013 12:26:40 +0200 Subject: Lighter implementation of the slicing algorithm to save memory and time --- lib/Slic3r/Layer/Region.pm | 4 --- lib/Slic3r/Print/Object.pm | 43 +++++++++++------------- lib/Slic3r/TriangleMesh.pm | 82 ++++++++++++++++++---------------------------- 3 files changed, 52 insertions(+), 77 deletions(-) (limited to 'lib') diff --git a/lib/Slic3r/Layer/Region.pm b/lib/Slic3r/Layer/Region.pm index 3f71bfba9..238083270 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 0df58e872..e50814f8a 100644 --- a/lib/Slic3r/Print/Object.pm +++ b/lib/Slic3r/Print/Object.pm @@ -155,10 +155,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( @@ -187,36 +189,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 b4624250d..ebe4a6999 100644 --- a/lib/Slic3r/TriangleMesh.pm +++ b/lib/Slic3r/TriangleMesh.pm @@ -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; @@ -171,8 +171,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; } @@ -217,12 +217,8 @@ sub make_loops { @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]}++; } @@ -259,8 +255,8 @@ sub make_loops { } # optimization: build indexes of lines - my %by_facet_index = map { $lines[$_][I_FACET_INDEX] => $_ } - grep defined $lines[$_][I_FACET_INDEX], + my %by_edge_a_id = map { $lines[$_][I_EDGE_A_ID] => $_ } + grep defined $lines[$_][I_EDGE_A_ID], (0..$#lines); my %by_a_id = map { $lines[$_][I_A_ID] => $_ } grep defined $lines[$_][I_A_ID], @@ -269,17 +265,16 @@ sub make_loops { my (@polygons, @failed_loops, %visited_lines) = (); my $slicing_errors = 0; CYCLE: for (my $i = 0; $i <= $#lines; $i++) { - my $line = $lines[$i]; + my $line = my $first_line = $lines[$i]; next if $visited_lines{$line}; my @points = (); - my $first_facet_index = $line->[I_FACET_INDEX]; 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]}]; + if (defined $line->[I_EDGE_B_ID] && exists $by_edge_a_id{$line->[I_EDGE_B_ID]}) { + $next_line = $lines[ $by_edge_a_id{$line->[I_EDGE_B_ID]} ]; } elsif (defined $line->[I_B_ID] && exists $by_a_id{$line->[I_B_ID]}) { - $next_line = $lines[$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; @@ -292,11 +287,11 @@ sub make_loops { $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_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; @@ -307,7 +302,7 @@ sub make_loops { push @points, $next_line->[I_B]; $visited_lines{$next_line} = 1; $line = $next_line; - } while ($first_facet_index != $line->[I_FACET_INDEX]); + } while ($line ne $first_line); push @polygons, Slic3r::Polygon->new(@points); Slic3r::debugf " Discovered %s polygon of %d points\n", @@ -475,16 +470,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 +503,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; -- cgit v1.2.3 From 3622193c3f27b664e46591092f7f3d98845160ce Mon Sep 17 00:00:00 2001 From: Alessandro Ranellucci Date: Mon, 24 Jun 2013 00:02:01 +0200 Subject: Rewrite the algorithm that closes loops in order. We now tolerate the case when more than two facets share a common edge --- lib/Slic3r/TriangleMesh.pm | 89 ++++++++++++++++++---------------------------- 1 file changed, 34 insertions(+), 55 deletions(-) (limited to 'lib') diff --git a/lib/Slic3r/TriangleMesh.pm b/lib/Slic3r/TriangleMesh.pm index ebe4a6999..a3823c36a 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; @@ -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", @@ -254,61 +256,38 @@ sub make_loops { } } - # optimization: build indexes of lines - my %by_edge_a_id = map { $lines[$_][I_EDGE_A_ID] => $_ } - grep defined $lines[$_][I_EDGE_A_ID], - (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 = my $first_line = $lines[$i]; - next if $visited_lines{$line}; - my @points = (); + 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_EDGE_B_ID] && exists $by_edge_a_id{$line->[I_EDGE_B_ID]}) { - $next_line = $lines[ $by_edge_a_id{$line->[I_EDGE_B_ID]} ]; - } 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 ($line ne $first_line); - - 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 for (grep @$_ >= 3, @failed_loops) { @@ -318,7 +297,7 @@ sub make_loops { if $Slic3r::debug; } - return ($slicing_errors, [@polygons]); + return (@failed_loops ? 1 : 0, [@polygons]); } sub rotate { -- cgit v1.2.3 From a15884dac93c12a6b9f7ff14068217b381504f38 Mon Sep 17 00:00:00 2001 From: Alessandro Ranellucci Date: Mon, 24 Jun 2013 00:08:39 +0200 Subject: Remove useless algorithm in loop merging code --- lib/Slic3r/TriangleMesh.pm | 93 +++++++++++++--------------------------------- 1 file changed, 26 insertions(+), 67 deletions(-) (limited to 'lib') diff --git a/lib/Slic3r/TriangleMesh.pm b/lib/Slic3r/TriangleMesh.pm index a3823c36a..fc0525024 100644 --- a/lib/Slic3r/TriangleMesh.pm +++ b/lib/Slic3r/TriangleMesh.pm @@ -183,79 +183,38 @@ 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 %a_count = (); # how many lines have the same a_id - foreach my $line (@lines) { - 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, - ); - } - } - } - my (@polygons, @failed_loops) = (); CYCLE: while (@lines) { # take first spare line and start a new loop @@ -287,7 +246,7 @@ sub make_loops { } push @loop, splice @lines, $line_idx, 1; } - }; + } # TODO: we should try to combine failed loops for (grep @$_ >= 3, @failed_loops) { -- cgit v1.2.3