diff options
| -rw-r--r-- | lib/Slic3r.pm | 1 | ||||
| -rw-r--r-- | lib/Slic3r/Geometry.pm | 32 | ||||
| -rw-r--r-- | lib/Slic3r/Layer.pm | 18 | ||||
| -rw-r--r-- | lib/Slic3r/Line.pm | 15 | ||||
| -rw-r--r-- | lib/Slic3r/Line/FacetEdge.pm | 8 | ||||
| -rw-r--r-- | lib/Slic3r/Perimeter.pm | 11 | ||||
| -rw-r--r-- | lib/Slic3r/Polyline.pm | 10 | ||||
| -rw-r--r-- | lib/Slic3r/Print.pm | 91 | ||||
| -rw-r--r-- | lib/Slic3r/STL.pm | 7 | ||||
| -rw-r--r-- | lib/Slic3r/Skein.pm | 5 | ||||
| -rw-r--r-- | t/clipper.t | 51 | ||||
| -rw-r--r-- | t/polyclip.t | 9 | ||||
| -rw-r--r-- | t/stl.t | 11 |
13 files changed, 202 insertions, 67 deletions
diff --git a/lib/Slic3r.pm b/lib/Slic3r.pm index 823f33fb2..ab5457f68 100644 --- a/lib/Slic3r.pm +++ b/lib/Slic3r.pm @@ -17,6 +17,7 @@ use Slic3r::Fill; use Slic3r::Geometry; use Slic3r::Layer; use Slic3r::Line; +use Slic3r::Line::FacetEdge; use Slic3r::Perimeter; use Slic3r::Point; use Slic3r::Polyline; diff --git a/lib/Slic3r/Geometry.pm b/lib/Slic3r/Geometry.pm index 5f8b6ad6a..8b4794460 100644 --- a/lib/Slic3r/Geometry.pm +++ b/lib/Slic3r/Geometry.pm @@ -11,7 +11,6 @@ use constant B => 1; use constant X => 0; use constant Y => 1; use constant epsilon => 1E-6; -use constant epsilon2 => epsilon**2; our $parallel_degrees_limit = abs(deg2rad(3)); sub slope { @@ -92,20 +91,35 @@ sub point_in_polygon { # if point is not in polygon, let's check whether it belongs to the contour if (!$side && 0) { foreach my $line (polygon_lines($polygon)) { - # calculate the Y in line at X of the point - if ($line->[A][X] == $line->[B][X]) { - return 1 if abs($x - $line->[A][X]) < epsilon; - next; - } - my $y3 = $line->[A][Y] + ($line->[B][Y] - $line->[A][Y]) - * ($x - $line->[A][X]) / ($line->[B][X] - $line->[A][X]); - return 1 if abs($y3 - $y) < epsilon2; + return 1 if point_in_segment($point, $line); } } return $side; } +sub point_in_segment { + my ($point, $line) = @_; + + my ($x, $y) = @$point; + my @line_x = sort { $a <=> $b } $line->[A][X], $line->[B][X]; + my @line_y = sort { $a <=> $b } $line->[A][Y], $line->[B][Y]; + + # check whether the point is in the segment bounding box + return 0 unless $x >= ($line_x[0] - epsilon) && $x <= ($line_x[1] + epsilon) + && $y >= ($line_y[0] - epsilon) && $y <= ($line_y[1] + epsilon); + + # if line is vertical, check whether point's X is the same as the line + if ($line->[A][X] == $line->[B][X]) { + return 1 if abs($x - $line->[A][X]) < epsilon; + } + + # calculate the Y in line at X of the point + my $y3 = $line->[A][Y] + ($line->[B][Y] - $line->[A][Y]) + * ($x - $line->[A][X]) / ($line->[B][X] - $line->[A][X]); + return abs($y3 - $y) < epsilon ? 1 : 0; +} + sub polygon_lines { my ($polygon) = @_; diff --git a/lib/Slic3r/Layer.pm b/lib/Slic3r/Layer.pm index 30cfdd182..c6e1a9503 100644 --- a/lib/Slic3r/Layer.pm +++ b/lib/Slic3r/Layer.pm @@ -112,6 +112,24 @@ sub make_polylines { @{ $self->lines } = grep $lines_map{"$_"}, @{ $self->lines }; } + # now remove lines that are already part of a surface + { + my @lines = @{ $self->lines }; + @{ $self->lines } = (); + LINE: foreach my $line (@lines) { + if (!$line->isa('Slic3r::Line::FacetEdge')) { + push @{ $self->lines }, $line; + next LINE; + } + foreach my $surface (@{$self->surfaces}) { + if ($surface->surface_type eq $line->edge_type && $surface->contour->has_segment($line)) { + next LINE; + } + } + push @{ $self->lines }, $line; + } + } + # make a cache of line endpoints my %pointmap = (); foreach my $line (@{ $self->lines }) { diff --git a/lib/Slic3r/Line.pm b/lib/Slic3r/Line.pm index 5f7242609..5d7a4a5be 100644 --- a/lib/Slic3r/Line.pm +++ b/lib/Slic3r/Line.pm @@ -10,10 +10,10 @@ has 'points' => ( sub cast { my $class = shift; - my ($line) = @_; + my ($line, %args) = @_; if (ref $line eq 'ARRAY') { @$line == 2 or die "Line needs two points!"; - return Slic3r::Line->new(points => [ map Slic3r::Point->cast($_), @$line ]); + return $class->new(points => [ map Slic3r::Point->cast($_), @$line ], %args); } else { return $line; } @@ -51,6 +51,17 @@ sub has_endpoint { return $point->coincides_with($self->a) || $point->coincides_with($self->b); } +sub has_segment { + my $self = shift; + my ($line) = @_; + + $line = $line->p if $line->isa('Slic3r::Line'); + + # a segment belongs to another segment if its points belong to it + return Slic3r::Geometry::point_in_segment($line->[0], $self->p) + && Slic3r::Geometry::point_in_segment($line->[1], $self->p); +} + sub parallel_to { my $self = shift; my ($line) = @_; diff --git a/lib/Slic3r/Line/FacetEdge.pm b/lib/Slic3r/Line/FacetEdge.pm new file mode 100644 index 000000000..d229c7ca4 --- /dev/null +++ b/lib/Slic3r/Line/FacetEdge.pm @@ -0,0 +1,8 @@ +package Slic3r::Line::FacetEdge; +use Moo; + +extends 'Slic3r::Line'; + +has 'edge_type' => (is => 'ro'); # top/bottom + +1; diff --git a/lib/Slic3r/Perimeter.pm b/lib/Slic3r/Perimeter.pm index 3d26588c0..9bde8f01a 100644 --- a/lib/Slic3r/Perimeter.pm +++ b/lib/Slic3r/Perimeter.pm @@ -113,12 +113,11 @@ sub offset_polygon { } } - # apply all holes to all contours; - # this is improper, but Math::Clipper handles it - return map {{ - outer => $_, - holes => [ @hole_offsets ], - }} @contour_offsets; + # apply holes to the right contours + my $clipper = Math::Clipper->new; + $clipper->add_subject_polygons($offsets); + my $results = $clipper->ex_execute(CT_UNION, PFT_NONZERO, PFT_NONZERO); + return @$results; } sub _mgp_from_points_ref { diff --git a/lib/Slic3r/Polyline.pm b/lib/Slic3r/Polyline.pm index 27adc0ca1..23bfca9a2 100644 --- a/lib/Slic3r/Polyline.pm +++ b/lib/Slic3r/Polyline.pm @@ -97,4 +97,14 @@ sub nearest_point_to { return Slic3r::Point->cast($point); } +sub has_segment { + my $self = shift; + my ($line) = @_; + + for ($self->lines) { + return 1 if $_->has_segment($line); + } + return 0; +} + 1; diff --git a/lib/Slic3r/Print.pm b/lib/Slic3r/Print.pm index 51e556d98..51a82d8ba 100644 --- a/lib/Slic3r/Print.pm +++ b/lib/Slic3r/Print.pm @@ -46,9 +46,6 @@ sub new_from_stl { $layer->merge_contiguous_surfaces; } - # detect which surfaces are near external layers - $print->discover_horizontal_shells; - return $print; } @@ -88,7 +85,7 @@ sub discover_horizontal_shells { my $layer = $self->layers->[$i]; foreach my $type (qw(top bottom)) { # find surfaces of current type for current layer - my @surfaces = grep $_->surface_type eq $type, @{$layer->surfaces} or next; + my @surfaces = grep $_->surface_type eq $type, map @{$_->surfaces}, @{$layer->fill_surfaces} or next; Slic3r::debugf "Layer %d has %d surfaces of type '%s'\n", $i, scalar(@surfaces), $type; @@ -99,47 +96,51 @@ sub discover_horizontal_shells { next if $n < 0 || $n >= $self->layer_count; Slic3r::debugf " looking for neighbors on layer %d...\n", $n; - my $neighbor_polygons = [ map $_->p, grep $_->surface_type eq 'internal', @{$self->layers->[$n]->surfaces} ]; - # find intersection between @surfaces and current layer's surfaces - $clipper->add_subject_polygons([ map $_->p, @surfaces ]); - $clipper->add_clip_polygons($neighbor_polygons); - - # intersections have contours and holes - my $intersections = $clipper->ex_execute(CT_INTERSECTION, PFT_NONZERO, PFT_NONZERO); - $clipper->clear; - next if @$intersections == 0; - Slic3r::debugf " %d intersections found\n", scalar @$intersections; - - # subtract intersections from layer surfaces to get resulting inner surfaces - $clipper->add_subject_polygons($neighbor_polygons); - $clipper->add_clip_polygons([ map { $_->{outer}, @{$_->{holes}} } @$intersections ]); - my $internal_polygons = $clipper->ex_execute(CT_DIFFERENCE, PFT_NONZERO, PFT_NONZERO); - $clipper->clear; - - # Note: due to floating point math we're going to get some very small - # polygons as $internal_polygons; they will be removed by removed_small_features() - - # assign resulting inner surfaces to layer - $self->layers->[$n]->surfaces([]); - foreach my $p (@$internal_polygons) { - push @{$self->layers->[$n]->surfaces}, Slic3r::Surface->new( - surface_type => 'internal', - contour => Slic3r::Polyline::Closed->cast($p->{outer}), - holes => [ - map Slic3r::Polyline::Closed->cast($_), @{$p->{holes}} - ], - ); - } - - # assign new internal-solid surfaces to layer - foreach my $p (@$intersections) { - push @{$self->layers->[$n]->surfaces}, Slic3r::Surface->new( - surface_type => 'internal-solid', - contour => Slic3r::Polyline::Closed->cast($p->{outer}), - holes => [ - map Slic3r::Polyline::Closed->cast($_), @{$p->{holes}} - ], - ); + foreach my $surf_coll (@{$self->layers->[$n]->fill_surfaces}) { + my $neighbor_polygons = [ map $_->p, grep $_->surface_type eq 'internal', @{$surf_coll->surfaces} ]; + + # find intersection between @surfaces and current layer's surfaces + $clipper->add_subject_polygons([ map $_->p, @surfaces ]); + $clipper->add_clip_polygons($neighbor_polygons); + + # intersections have contours and holes + my $intersections = $clipper->ex_execute(CT_INTERSECTION, PFT_NONZERO, PFT_NONZERO); + $clipper->clear; + + next if @$intersections == 0; + Slic3r::debugf " %d intersections found\n", scalar @$intersections; + + # subtract intersections from layer surfaces to get resulting inner surfaces + $clipper->add_subject_polygons($neighbor_polygons); + $clipper->add_clip_polygons([ map { $_->{outer}, @{$_->{holes}} } @$intersections ]); + my $internal_polygons = $clipper->ex_execute(CT_DIFFERENCE, PFT_NONZERO, PFT_NONZERO); + $clipper->clear; + + # Note: due to floating point math we're going to get some very small + # polygons as $internal_polygons; they will be removed by removed_small_features() + + # assign resulting inner surfaces to layer + $surf_coll->surfaces([]); + foreach my $p (@$internal_polygons) { + push @{$surf_coll->surfaces}, Slic3r::Surface->new( + surface_type => 'internal', + contour => Slic3r::Polyline::Closed->cast($p->{outer}), + holes => [ + map Slic3r::Polyline::Closed->cast($_), @{$p->{holes}} + ], + ); + } + + # assign new internal-solid surfaces to layer + foreach my $p (@$intersections) { + push @{$surf_coll->surfaces}, Slic3r::Surface->new( + surface_type => 'internal-solid', + contour => Slic3r::Polyline::Closed->cast($p->{outer}), + holes => [ + map Slic3r::Polyline::Closed->cast($_), @{$p->{holes}} + ], + ); + } } } } diff --git a/lib/Slic3r/STL.pm b/lib/Slic3r/STL.pm index cf9ade6d4..44a229357 100644 --- a/lib/Slic3r/STL.pm +++ b/lib/Slic3r/STL.pm @@ -176,7 +176,10 @@ sub intersect_facet { if ($a->[Z] == $b->[Z] && $a->[Z] == $z) { # edge is horizontal and belongs to the current layer - push @lines, [ [$a->[X], $a->[Y]], [$b->[X], $b->[Y]] ]; + push @lines, Slic3r::Line::FacetEdge->cast( + [ [$a->[X], $a->[Y]], [$b->[X], $b->[Y]] ], + edge_type => (grep $_->[Z] > $z, @$vertices) ? 'bottom' : 'top', + ); #print "Horizontal!\n"; } elsif (($a->[Z] < $z && $b->[Z] > $z) || ($b->[Z] < $z && $a->[Z] > $z)) { @@ -213,7 +216,7 @@ sub intersect_facet { #} # connect points: - push @lines, [ @intersection_points ]; + push @lines, Slic3r::Line->cast([ @intersection_points ]); } return @lines; diff --git a/lib/Slic3r/Skein.pm b/lib/Slic3r/Skein.pm index eedc570d1..b51054082 100644 --- a/lib/Slic3r/Skein.pm +++ b/lib/Slic3r/Skein.pm @@ -2,6 +2,7 @@ package Slic3r::Skein; use Moo; use Time::HiRes qw(gettimeofday tv_interval); +use XXX; has 'input_file' => (is => 'ro', required => 1); has 'output_file' => (is => 'rw', required => 0); @@ -16,6 +17,10 @@ sub go { my $print = Slic3r::Print->new_from_stl($self->input_file); $print->extrude_perimeters; $print->remove_small_features; + + # detect which surfaces are near external layers + $print->discover_horizontal_shells; + $print->extrude_fills; diff --git a/t/clipper.t b/t/clipper.t new file mode 100644 index 000000000..f860d2e46 --- /dev/null +++ b/t/clipper.t @@ -0,0 +1,51 @@ +use Test::More; + +plan tests => 1; + +use Math::Clipper ':all'; + +my $clipper = Math::Clipper->new; + +my $square = [ # ccw + [10, 10], + [20, 10], + [20, 20], + [10, 20], +]; + +my $hole_in_square = [ # cw + [14, 14], + [14, 16], + [16, 16], + [16, 14], +]; + +my $square = [ # ccw + [5, 12], + [25, 12], + [25, 18], + [5, 18], +]; + +$clipper->add_subject_polygons([ $square, $hole_in_square ]); +$clipper->add_clip_polygons([ $square ]); +my $intersection = $clipper->ex_execute(CT_INTERSECTION, PFT_NONZERO, PFT_NONZERO); + +is_deeply $intersection, [ + { + holes => [ + [ + [14, 16], + [16, 16], + [16, 14], + [14, 14], + ], + ], + outer => [ + [5, 18], + [5, 12], + [25, 12], + [25, 18], + ], + }, +], 'hole is preserved after intersection'; diff --git a/t/polyclip.t b/t/polyclip.t index 821e7011f..605c4834b 100644 --- a/t/polyclip.t +++ b/t/polyclip.t @@ -1,6 +1,6 @@ use Test::More; -plan tests => 4; +plan tests => 9; BEGIN { use FindBin; @@ -29,3 +29,10 @@ is $intersection, undef, 'external lines are ignored 2'; $intersection = Slic3r::Geometry::clip_segment_polygon([ [12, 12], [18, 16] ], $square); is_deeply $intersection, [ [12, 12], [18, 16] ], 'internal lines are preserved'; + +is Slic3r::Geometry::point_in_segment([10, 10], [ [5, 10], [20, 10] ]), 1, 'point in horizontal segment'; +is Slic3r::Geometry::point_in_segment([30, 10], [ [5, 10], [20, 10] ]), 0, 'point not in horizontal segment'; +is Slic3r::Geometry::point_in_segment([10, 10], [ [10, 5], [10, 20] ]), 1, 'point in vertical segment'; +is Slic3r::Geometry::point_in_segment([10, 30], [ [10, 5], [10, 20] ]), 0, 'point not in vertical segment'; +is Slic3r::Geometry::point_in_segment([15, 15], [ [10, 10], [20, 20] ]), 1, 'point in diagonal segment'; +is Slic3r::Geometry::point_in_segment([20, 15], [ [10, 10], [20, 20] ]), 0, 'point not in diagonal segment'; @@ -1,6 +1,6 @@ use Test::More; -plan tests => 7; +plan tests => 11; BEGIN { use FindBin; @@ -28,10 +28,17 @@ is_deeply lines(28, 20, 30), [ ], 'lower vertex on la is_deeply lines(24, 10, 16), [ [ [4, 4], [2, 6] ] ], 'two edges intersect'; is_deeply lines(24, 10, 20), [ [ [4, 4], [1, 9] ] ], 'one vertex on plane and one edge intersects'; +my @lower = $stl->intersect_facet(vertices(22, 20, 20), $z, $dz); +my @upper = $stl->intersect_facet(vertices(20, 20, 10), $z, $dz); +isa_ok $lower[0], 'Slic3r::Line::FacetEdge', 'bottom edge on layer'; +isa_ok $upper[0], 'Slic3r::Line::FacetEdge', 'upper edge on layer'; +is $lower[0]->edge_type, 'bottom', 'lower edge is detected as bottom'; +is $upper[0]->edge_type, 'top', 'upper edge is detected as top'; + sub vertices { [ map [ @{$points[$_]}, $_[$_] ], 0..2 ] } sub lines { - [ map [ map ref $_ eq 'Slic3r::Point' ? $_->p : [ map sprintf('%.0f', $_), @$_ ], @$_ ], $stl->intersect_facet(vertices(@_), $z, $dz) ]; + [ map [ map ref $_ eq 'Slic3r::Point' ? $_->p : [ map sprintf('%.0f', $_), @$_ ], @$_ ], map $_->p, $stl->intersect_facet(vertices(@_), $z, $dz) ]; } |