New experimental --gcode-arcs options to generate G2/G3 commands. #23

13 files changed, 333 insertions, 21 deletions

diff --git a/MANIFEST b/MANIFEST
index 822802e62..d2d0d7343 100644
--- a/MANIFEST
+++ b/MANIFEST
@@ -5,6 +5,7 @@ lib/Slic3r/ExPolygon.pm
 lib/Slic3r/Extruder.pm
 lib/Slic3r/ExtrusionLoop.pm
 lib/Slic3r/ExtrusionPath.pm
+lib/Slic3r/ExtrusionPath/Arc.pm
 lib/Slic3r/ExtrusionPath/Collection.pm
 lib/Slic3r/Fill.pm
 lib/Slic3r/Fill/Base.pm
diff --git a/MANIFEST.SKIP b/MANIFEST.SKIP
new file mode 100644
index 000000000..fae34e019
--- /dev/null
+++ b/MANIFEST.SKIP
@@ -0,0 +1,72 @@
+
+#!start included /opt/local/lib/perl5/5.12.3/ExtUtils/MANIFEST.SKIP
+# Avoid version control files.
+\bRCS\b
+\bCVS\b
+\bSCCS\b
+,v$
+\B\.svn\b
+\B\.git\b
+\B\.gitignore\b
+\b_darcs\b
+\B\.cvsignore$
+
+# Avoid VMS specific MakeMaker generated files
+\bDescrip.MMS$
+\bDESCRIP.MMS$
+\bdescrip.mms$
+
+# Avoid Makemaker generated and utility files.
+\bMANIFEST\.bak
+\bMakefile$
+\bblib/
+\bMakeMaker-\d
+\bpm_to_blib\.ts$
+\bpm_to_blib$
+\bblibdirs\.ts$         # 6.18 through 6.25 generated this
+
+# Avoid Module::Build generated and utility files.
+\bBuild$
+\b_build/
+\bBuild.bat$
+\bBuild.COM$
+\bBUILD.COM$
+\bbuild.com$
+
+# Avoid temp and backup files.
+~$
+\.old$
+\#$
+\b\.#
+\.bak$
+\.tmp$
+\.#
+\.rej$
+
+# Avoid OS-specific files/dirs
+# Mac OSX metadata
+\B\.DS_Store
+# Mac OSX SMB mount metadata files
+\B\._
+
+# Avoid Devel::Cover files.
+\bcover_db\b
+#!end included /opt/local/lib/perl5/5.12.3/ExtUtils/MANIFEST.SKIP
+
+# Avoid configuration metadata file
+^MYMETA\.
+
+# Avoid Module::Build generated and utility files.
+\bBuild$
+\bBuild.bat$
+\b_build
+\bBuild.COM$
+\bBUILD.COM$
+\bbuild.com$
+^MANIFEST\.SKIP
+
+# Avoid archives of this distribution
+\bSlic3r-[\d\.\_]+
+
+\.git$
+^\.DS_Store$
diff --git a/README.markdown b/README.markdown
index 4aea5df45..120633c61 100644
--- a/README.markdown
+++ b/README.markdown
@@ -47,7 +47,8 @@ Slic3r current features are:
 * multiple solid layers near horizontal external surfaces;
 * ability to scale, rotate and multiply input object;
 * customizable initial and final GCODE (using command line only);
-* use different speed for bottom layer and perimeters.
+* use different speed for bottom layer and perimeters;
+* experimental support for G2/G3 native arcs.
 
 Roadmap includes the following goals:
 
diff --git a/lib/Slic3r.pm b/lib/Slic3r.pm
index 03deb859e..e5b2126a7 100644
--- a/lib/Slic3r.pm
+++ b/lib/Slic3r.pm
@@ -13,6 +13,7 @@ use Slic3r::ExPolygon;
 use Slic3r::Extruder;
 use Slic3r::ExtrusionLoop;
 use Slic3r::ExtrusionPath;
+use Slic3r::ExtrusionPath::Arc;
 use Slic3r::ExtrusionPath::Collection;
 use Slic3r::Fill;
 use Slic3r::Geometry;
@@ -34,7 +35,8 @@ use Slic3r::Surface::Bridge;
 our $nozzle_diameter    = 0.5;
 our $print_center       = [100,100];  # object will be centered around this point
 our $use_relative_e_distances = 0;
-our $z_offset = 0;
+our $z_offset           = 0;
+our $gcode_arcs         = 0;
 
 # filament options
 our $filament_diameter  = 3;    # mm
diff --git a/lib/Slic3r/Extruder.pm b/lib/Slic3r/Extruder.pm
index a03880f04..c58eab823 100644
--- a/lib/Slic3r/Extruder.pm
+++ b/lib/Slic3r/Extruder.pm
@@ -30,6 +30,7 @@ has 'retract_speed' => (
     default => sub { $Slic3r::retract_speed * 60 },  # mm/min
 );
 
+use Slic3r::Geometry qw(points_coincide);
 use XXX;
 
 use constant PI => 4 * atan2(1, 1);
@@ -67,7 +68,13 @@ sub extrude_loop {
 
 sub extrude {
     my $self = shift;
-    my ($path, $description) = @_;
+    my ($path, $description, $recursive) = @_;
+    
+    if ($Slic3r::gcode_arcs && !$recursive) {
+        my $gcode = "";
+        $gcode .= $self->extrude($_, $description, 1) for $path->detect_arcs;
+        return $gcode;
+    }
     
     my $gcode = "";
     
@@ -80,23 +87,28 @@ sub extrude {
     }
     
     # go to first point of extrusion path
-    $gcode .= $self->G1($path->points->[0], undef, 0, "move to first $description point");
+    $gcode .= $self->G1($path->points->[0], undef, 0, "move to first $description point")
+        if !points_coincide($self->last_pos, $path->points->[0]);
     
     # compensate retraction
     $gcode .= $self->unretract if $self->retracted;
-    XXX "yes!\n" if $path->depth_layers > 1;
-    # extrude while going to next points
-    foreach my $line ($path->lines) {
-        # calculate how much filament to drive into the extruder
-        # to get the desired amount of extruded plastic
-        my $e = $line->a->distance_to($line->b) * $Slic3r::resolution
-            * (($Slic3r::nozzle_diameter**2) / ($Slic3r::filament_diameter ** 2))
-            * $Slic3r::thickness_ratio 
-            * $self->flow_ratio
-            * $Slic3r::filament_packing_density
-            * $path->depth_layers;
-        
-        $gcode .= $self->G1($line->b, undef, $e, $description);
+    
+    # calculate extrusion length per distance unit
+    my $e = $Slic3r::resolution
+        * (($Slic3r::nozzle_diameter**2) / ($Slic3r::filament_diameter ** 2))
+        * $Slic3r::thickness_ratio 
+        * $self->flow_ratio
+        * $Slic3r::filament_packing_density
+        * $path->depth_layers;
+    
+    # extrude arc or line
+    if ($path->isa('Slic3r::ExtrusionPath::Arc')) {
+        $gcode .= $self->G2_G3($path->points->[-1], $path->orientation, 
+            $path->center, $e * $path->length, $description);
+    } else {
+        foreach my $line ($path->lines) {
+            $gcode .= $self->G1($line->b, undef, $e * $line->length, $description);
+        }
     }
     
     return $gcode;
@@ -145,6 +157,34 @@ sub G1 {
         $gcode .= sprintf " Z%.${dec}f", $z;
     }
     
+    return $self->_Gx($gcode, $e, $comment);
+}
+
+sub G2_G3 {
+    my $self = shift;
+    my ($point, $orientation, $center, $e, $comment) = @_;
+    my $dec = $self->dec;
+    
+    my $gcode = $orientation eq 'cw' ? "G2" : "G3";
+    
+    $gcode .= sprintf " X%.${dec}f Y%.${dec}f", 
+        ($point->x * $Slic3r::resolution) + $self->shift_x, 
+        ($point->y * $Slic3r::resolution) + $self->shift_y; #**
+    $self->last_pos($point);
+    
+    # XY distance of the center from the start position
+    $gcode .= sprintf " I%.${dec}f J%.${dec}f",
+        ($point->[X] - $self->last_pos->[X]) * $Slic3r::resolution + $self->shift_x,
+        ($point->[Y] - $self->last_pos->[Y]) * $Slic3r::resolution + $self->shift_y;
+    
+    return $self->_Gx($gcode, $e, $comment);
+}
+
+sub _Gx {
+    my $self = shift;
+    my ($gcode, $e, $comment) = @_;
+    my $dec = $self->dec;
+    
     # apply the speed reduction for print moves on bottom layer
     my $speed_multiplier = $e && $self->z == $Slic3r::z_offset
         ? $Slic3r::bottom_layer_speed_ratio 
diff --git a/lib/Slic3r/ExtrusionPath.pm b/lib/Slic3r/ExtrusionPath.pm
index dfc5a83f2..67c32807d 100644
--- a/lib/Slic3r/ExtrusionPath.pm
+++ b/lib/Slic3r/ExtrusionPath.pm
@@ -7,7 +7,11 @@ extends 'Slic3r::Polyline';
 # expressed in layers
 has 'depth_layers' => (is => 'ro', default => sub {1});
 
-use constant PI => 4 * atan2(1, 1);
+use constant X => 0;
+use constant Y => 1;
+
+use Slic3r::Geometry qw(PI epsilon deg2rad rotate_points);
+use XXX;
 
 sub clip_end {
     my $self = shift;
@@ -70,4 +74,110 @@ sub split_at_acute_angles {
     return @paths;
 }
 
+sub detect_arcs {
+    my $self = shift;
+    
+    my $max_angle = deg2rad(40);
+    my $len_epsilon = 1000000;
+    
+    my @points = @{$self->points};
+    my @paths = ();
+    
+    # we require at least 3 consecutive segments to form an arc
+    CYCLE: while (@points >= 4) {
+        for (my $i = 0; $i <= $#points - 3; $i++) {
+            my $s1 = Slic3r::Line->new($points[$i],   $points[$i+1]);
+            my $s2 = Slic3r::Line->new($points[$i+1], $points[$i+2]);
+            my $s3 = Slic3r::Line->new($points[$i+2], $points[$i+3]);
+            my $s1_len = $s1->length;
+            my $s2_len = $s2->length;
+            my $s3_len = $s3->length;
+            
+            # segments must have the same length
+            if (abs($s3_len - $s2_len) > $len_epsilon) {
+                # optimization: skip a cycle
+                $i++;
+                next;
+            }
+            next if abs($s2_len - $s1_len) > $len_epsilon;
+            
+            # segments must have the same relative angle
+            my $s1_angle = $s1->atan;
+            my $s2_angle = $s2->atan;
+            my $s3_angle = $s3->atan;
+            $s1_angle += 2*PI if $s1_angle < 0;
+            $s2_angle += 2*PI if $s2_angle < 0;
+            $s3_angle += 2*PI if $s3_angle < 0;
+            my $s1s2_angle = $s2_angle - $s1_angle;
+            my $s2s3_angle = $s3_angle - $s2_angle;
+            next if abs($s1s2_angle - $s2s3_angle) > $Slic3r::Geometry::parallel_degrees_limit;
+            next if $s1s2_angle < $Slic3r::Geometry::parallel_degrees_limit;     # ignore parallel lines
+            next if $s1s2_angle > $max_angle;  # ignore too sharp vertices
+            
+            # s1, s2, s3 form an arc
+            my $orientation = $s1->point_on_left($points[$i+2]) ? 'ccw' : 'cw';
+            
+            # to find the center, we intersect the perpendicular lines
+            # passing by midpoints of $s1 and $s3
+            my $arc_center;
+            {
+                my $s1_mid = $s1->midpoint;
+                my $s3_mid = $s2->midpoint;
+                my $rotation_angle = PI/2 * ($orientation eq 'ccw' ? -1 : 1);
+                my $ray1 = Slic3r::Line->new($s1_mid, rotate_points($rotation_angle, $s1_mid, $points[$i+1]));
+                my $ray3 = Slic3r::Line->new($s3_mid, rotate_points($rotation_angle, $s3_mid, $points[$i+3]));
+                $arc_center = $ray1->intersection($ray3, 0);
+            }
+            
+            my $arc = Slic3r::ExtrusionPath::Arc->new(
+                points      => [$points[$i], $points[$i+3]],  # first and last points
+                orientation => $orientation,
+                center      => $arc_center,
+                radius      => $arc_center->distance_to($points[$i]),
+            );
+            
+            # now look for more points
+            my $last_line_angle = $s3_angle;
+            my $last_j = $points[$i+3];
+            for (my $j = $i+3; $j < $#points; $j++) {
+                my $line = Slic3r::Line->new($points[$j], $points[$j+1]);
+                last if abs($line->length - $s1_len) > $len_epsilon;
+                my $line_angle = $line->atan;
+                $line_angle += 2*PI if $line_angle < 0;
+                my $anglediff = $line_angle - $last_line_angle;
+                last if abs($s1s2_angle - $anglediff) > $Slic3r::Geometry::parallel_degrees_limit;
+                
+                # point $j+1 belongs to the arc
+                $arc->points->[-1] = $points[$j+1];
+                $last_j = $j+1;
+                
+                $last_line_angle = $line_angle;
+            }
+            
+            # points 0..$i form a linear path
+            push @paths, (ref $self)->new(
+                points       => [ @points[0..$i] ],
+                depth_layers => $self->depth_layers,
+            ) if $i > 0;
+            
+            # add our arc
+            push @paths, $arc;
+            print "ARC DETECTED\n";
+            # remove arc points from path, leaving one
+            splice @points, 0, $last_j, ();
+            
+            next CYCLE;
+        }
+        last;
+    }
+    
+    # remaining points form a linear path
+    push @paths, (ref $self)->new(
+        points => [@points],
+        depth_layers => $self->depth_layers
+    ) if @points;
+    
+    return @paths;
+}
+
 1;
diff --git a/lib/Slic3r/ExtrusionPath/Arc.pm b/lib/Slic3r/ExtrusionPath/Arc.pm
new file mode 100644
index 000000000..59c65c75c
--- /dev/null
+++ b/lib/Slic3r/ExtrusionPath/Arc.pm
@@ -0,0 +1,23 @@
+package Slic3r::ExtrusionPath::Arc;
+use Moo;
+
+extends 'Slic3r::ExtrusionPath';
+
+has 'center' => (is => 'ro', required => 1);
+has 'radius' => (is => 'ro', required => 1);
+has 'orientation' => (is => 'ro', required => 1);  # cw/ccw
+
+use Slic3r::Geometry qw(PI angle3points);
+
+sub angle {
+    my $self = shift;
+    return angle3points($self->center, @{$self->points});
+}
+
+sub length {
+    my $self = shift;
+    
+    return $self->radius * $self->angle;
+}
+
+1;
diff --git a/lib/Slic3r/ExtrusionPath/Collection.pm b/lib/Slic3r/ExtrusionPath/Collection.pm
index 1601bcdbc..4a4358617 100644
--- a/lib/Slic3r/ExtrusionPath/Collection.pm
+++ b/lib/Slic3r/ExtrusionPath/Collection.pm
@@ -55,4 +55,9 @@ sub cleanup {
     @{$self->paths} = map $_->split_at_acute_angles, @{$self->paths};
 }
 
+sub detect_arcs {
+    my $self = shift;
+    @{$self->paths} = map $_->detect_arcs, @{$self->paths};
+}
+
 1;
diff --git a/lib/Slic3r/Geometry.pm b/lib/Slic3r/Geometry.pm
index ac33a2197..fa7180c72 100644
--- a/lib/Slic3r/Geometry.pm
+++ b/lib/Slic3r/Geometry.pm
@@ -429,7 +429,7 @@ sub _line_intersection {
     # Take this test away and the line segments are
     # turned into lines going from infinite to another.
     # bounding_box_intersect() defined later in this chapter.
-    return "out of bounding box" unless bounding_box_intersect( 2, @box_a, @box_b );
+    ###return "out of bounding box" unless bounding_box_intersect( 2, @box_a, @box_b );
   }
   elsif ( @_ == 4 ) { # The parametric form.
     $x0 = $x2 = 0;
@@ -509,7 +509,7 @@ sub _line_intersection {
   my $h10 = $dx10 ? ($x - $x0) / $dx10 : ($dy10 ? ($y - $y0) / $dy10 : 1);
   my $h32 = $dx32 ? ($x - $x2) / $dx32 : ($dy32 ? ($y - $y2) / $dy32 : 1);
 
-  return [[$x, $y], $h10 >= 0 && $h10 <= 1 && $h32 >= 0 && $h32 <= 1];
+  return [Slic3r::Point->new($x, $y), $h10 >= 0 && $h10 <= 1 && $h32 >= 0 && $h32 <= 1];
 }
 
 # 2D
diff --git a/lib/Slic3r/Line.pm b/lib/Slic3r/Line.pm
index 9f0dc21d0..3f218f80c 100644
--- a/lib/Slic3r/Line.pm
+++ b/lib/Slic3r/Line.pm
@@ -2,6 +2,11 @@ package Slic3r::Line;
 use strict;
 use warnings;
 
+use constant A => 0;
+use constant B => 1;
+use constant X => 0;
+use constant Y => 1;
+
 sub new {
     my $class = shift;
     my $self;
@@ -70,4 +75,29 @@ sub length {
     return Slic3r::Geometry::line_length($self);
 }
 
+sub atan {
+    my $self = shift;
+    return Slic3r::Geometry::line_atan($self);
+}
+
+sub intersection {
+    my $self = shift;
+    my ($line, $require_crossing) = @_;
+    return Slic3r::Geometry::line_intersection($self, $line, $require_crossing);
+}
+
+sub point_on_left {
+    my $self = shift;
+    my ($point) = @_;
+    return Slic3r::Geometry::point_is_on_left_of_segment($point, $self);
+}
+
+sub midpoint {
+    my $self = shift;
+    return Slic3r::Point->new(
+        ($self->[A][X] + $self->[B][X]) / 2,
+        ($self->[A][Y] + $self->[B][Y]) / 2,
+    );
+}
+
 1;
diff --git a/lib/Slic3r/Point.pm b/lib/Slic3r/Point.pm
index 5ddb4f495..e8570ef8a 100644
--- a/lib/Slic3r/Point.pm
+++ b/lib/Slic3r/Point.pm
@@ -4,7 +4,7 @@ use warnings;
 
 sub new {
     my $class = shift;
-    my $self;
+    my $self;use XXX; ZZZ if !defined $_[0];
     if (@_ == 2) {
         $self = [@_];
     } elsif (ref $_[0] eq 'ARRAY') {
diff --git a/slic3r.pl b/slic3r.pl
index 75f64f3a3..8af77f704 100755
--- a/slic3r.pl
+++ b/slic3r.pl
@@ -27,6 +27,7 @@ GetOptions(
     'print-center=s'            => \$Slic3r::print_center,
     'use-relative-e-distances'  => \$Slic3r::use_relative_e_distances,
     'z-offset=f'                => \$Slic3r::z_offset,
+    'gcode-arcs'                => \$Slic3r::gcode_arcs,
     
     # filament options
     'filament-diameter=f'           => \$Slic3r::filament_diameter,
@@ -128,6 +129,8 @@ Usage: slic3r.pl [ OPTIONS ] file.stl
                         Use relative distances for extrusion in GCODE output
     --z-offset          Additional height in mm to add to vertical coordinates
                         (+/-, default: $Slic3r::z_offset)
+    --gcode-arcs        Use G2/G3 commands for native arcs (experimental, not supported
+                        by all firmwares)
     
   Filament options:
     --filament-diameter Diameter of your raw filament (default: $Slic3r::filament_diameter)
diff --git a/t/arcs.t b/t/arcs.t
new file mode 100644
index 000000000..2d604d578
--- /dev/null
+++ b/t/arcs.t
@@ -0,0 +1,25 @@
+use Test::More;
+use strict;
+use warnings;
+
+plan tests => 2;
+
+BEGIN {
+    use FindBin;
+    use lib "$FindBin::Bin/../lib";
+}
+
+use Slic3r;
+
+my $path = Slic3r::ExtrusionPath->cast([
+    [135322.42,26654.96], [187029.11,99546.23], [222515.14,92381.93], [258001.16,99546.23], 
+    [286979.42,119083.91], [306517.1,148062.17], [313681.4,183548.2],
+    [306517.1,219034.23], [286979.42,248012.49], [258001.16,267550.17], [222515.14,274714.47], 
+    [187029.11,267550.17], [158050.85,248012.49], [138513.17,219034.23], [131348.87,183548.2], 
+    [86948.77,175149.09], [119825.35,100585],
+]);
+my $collection = Slic3r::ExtrusionPath::Collection->new(paths => [$path]);
+$collection->detect_arcs;
+
+is scalar(@{$collection->paths}), 3, 'path collection now contains three paths';
+isa_ok $collection->paths->[1], 'Slic3r::ExtrusionPath::Arc', 'second one';