Reverted some now unnecessary changes. Reverted the infill to the original perl implementation.

12 files changed, 850 insertions, 48 deletions

diff --git a/lib/Slic3r/Fill.pm b/lib/Slic3r/Fill.pm
index ec9038b12..8c63fde59 100644
--- a/lib/Slic3r/Fill.pm
+++ b/lib/Slic3r/Fill.pm
@@ -3,25 +3,45 @@ use Moo;
 
 use List::Util qw(max);
 use Slic3r::ExtrusionPath ':roles';
-
+use Slic3r::Fill::3DHoneycomb;
+use Slic3r::Fill::Base;
+use Slic3r::Fill::Concentric;
+use Slic3r::Fill::Honeycomb;
+use Slic3r::Fill::PlanePath;
+use Slic3r::Fill::Rectilinear;
 use Slic3r::Flow ':roles';
 use Slic3r::Geometry qw(X Y PI scale chained_path deg2rad);
 use Slic3r::Geometry::Clipper qw(union union_ex diff diff_ex intersection_ex offset offset2);
 use Slic3r::Surface ':types';
 
+
 has 'bounding_box' => (is => 'ro', required => 0);
 has 'fillers'   => (is => 'rw', default => sub { {} });
 
+our %FillTypes = (
+    archimedeanchords   => 'Slic3r::Fill::ArchimedeanChords',
+    rectilinear         => 'Slic3r::Fill::Rectilinear',
+    grid                => 'Slic3r::Fill::Grid',
+    flowsnake           => 'Slic3r::Fill::Flowsnake',
+    octagramspiral      => 'Slic3r::Fill::OctagramSpiral',
+    hilbertcurve        => 'Slic3r::Fill::HilbertCurve',
+    line                => 'Slic3r::Fill::Line',
+    concentric          => 'Slic3r::Fill::Concentric',
+    honeycomb           => 'Slic3r::Fill::Honeycomb',
+    '3dhoneycomb'       => 'Slic3r::Fill::3DHoneycomb',
+);
+
 sub filler {
     my $self = shift;
     my ($filler) = @_;
     
     if (!ref $self) {
-       return Slic3r::Filler->new_from_type($filler);
+        return $FillTypes{$filler}->new;
     }
-
-    $self->fillers->{$filler} ||= Slic3r::Filler->new_from_type($filler);
-    $self->fillers->{$filler}->set_bounding_box($self->bounding_box);
+    
+    $self->fillers->{$filler} ||= $FillTypes{$filler}->new(
+        bounding_box => $self->bounding_box,
+    );
     return $self->fillers->{$filler};
 }
 
@@ -207,25 +227,25 @@ sub make_fill {
                 -1, # auto width
                 $layerm->layer->object,
             );
-            $f->set_spacing($internal_flow->spacing);
+            $f->spacing($internal_flow->spacing);
             $using_internal_flow = 1;
         } else {
-            $f->set_spacing($flow->spacing);
+            $f->spacing($flow->spacing);
         }
         
-        $f->set_layer_id($layerm->layer->id);
-        $f->set_z($layerm->layer->print_z);
-        $f->set_angle(deg2rad($layerm->region->config->fill_angle));
-        $f->set_loop_clipping(scale($flow->nozzle_diameter) * &Slic3r::LOOP_CLIPPING_LENGTH_OVER_NOZZLE_DIAMETER);
+        $f->layer_id($layerm->layer->id);
+        $f->z($layerm->layer->print_z);
+        $f->angle(deg2rad($layerm->region->config->fill_angle));
+        $f->loop_clipping(scale($flow->nozzle_diameter) * &Slic3r::LOOP_CLIPPING_LENGTH_OVER_NOZZLE_DIAMETER);
         
         # apply half spacing using this flow's own spacing and generate infill
-        my @polylines = $f->fill_surface(
-            $surface,
+        my @polylines = map $f->fill_surface(
+            $_,
             density         => $density/100,
             layer_height    => $h,
-        );
+        ), @{ $surface->offset(-scale($f->spacing)/2) };
+        
         next unless @polylines;
-
         
         # calculate actual flow from spacing (which might have been adjusted by the infill
         # pattern generator)
@@ -258,7 +278,7 @@ sub make_fill {
                     mm3_per_mm  => $mm3_per_mm,
                     width       => $flow->width,
                     height      => $flow->height,
-                ), map @$_, @polylines,
+                ), @polylines,
             );
         }
     }
diff --git a/lib/Slic3r/Fill/3DHoneycomb.pm b/lib/Slic3r/Fill/3DHoneycomb.pm
new file mode 100644
index 000000000..3bf7e547f
--- /dev/null
+++ b/lib/Slic3r/Fill/3DHoneycomb.pm
@@ -0,0 +1,230 @@
+package Slic3r::Fill::3DHoneycomb;
+use Moo;
+
+extends 'Slic3r::Fill::Base';
+
+use POSIX qw(ceil fmod);
+use Slic3r::Geometry qw(scale scaled_epsilon);
+use Slic3r::Geometry::Clipper qw(intersection_pl);
+
+# require bridge flow since most of this pattern hangs in air
+sub use_bridge_flow { 1 }
+
+sub fill_surface {
+    my ($self, $surface, %params) = @_;
+    
+    my $expolygon = $surface->expolygon;
+    my $bb = $expolygon->bounding_box;
+    my $size = $bb->size;
+    
+    my $distance = scale($self->spacing) / $params{density};
+    
+    # align bounding box to a multiple of our honeycomb grid module
+    # (a module is 2*$distance since one $distance half-module is 
+    # growing while the other $distance half-module is shrinking)
+    {
+        my $min = $bb->min_point;
+        $min->translate(
+            -($bb->x_min % (2*$distance)),
+            -($bb->y_min % (2*$distance)),
+        );
+        $bb->merge_point($min);
+    }
+    
+    # generate pattern
+    my @polylines = map Slic3r::Polyline->new(@$_),
+        makeGrid(
+            scale($self->z),
+            $distance,
+            ceil($size->x / $distance) + 1,
+            ceil($size->y / $distance) + 1,  #//
+            (($self->layer_id / $surface->thickness_layers) % 2) + 1,
+        );
+    
+    # move pattern in place
+    $_->translate($bb->x_min, $bb->y_min) for @polylines;
+    
+    # clip pattern to boundaries
+    @polylines = @{intersection_pl(\@polylines, \@$expolygon)};
+    
+    # connect lines
+    unless ($params{dont_connect} || !@polylines) {  # prevent calling leftmost_point() on empty collections
+        my ($expolygon_off) = @{$expolygon->offset_ex(scaled_epsilon)};
+        my $collection = Slic3r::Polyline::Collection->new(@polylines);
+        @polylines = ();
+        foreach my $polyline (@{$collection->chained_path_from($collection->leftmost_point, 0)}) {
+            # try to append this polyline to previous one if any
+            if (@polylines) {
+                my $line = Slic3r::Line->new($polylines[-1]->last_point, $polyline->first_point);
+                if ($line->length <= 1.5*$distance && $expolygon_off->contains_line($line)) {
+                    $polylines[-1]->append_polyline($polyline);
+                    next;
+                }
+            }
+            
+            # make a clone before $collection goes out of scope
+            push @polylines, $polyline->clone;
+        }
+    }
+    
+    # TODO: return ExtrusionLoop objects to get better chained paths
+    return @polylines;
+}
+
+
+=head1 DESCRIPTION
+
+Creates a contiguous sequence of points at a specified height that make
+up a horizontal slice of the edges of a space filling truncated
+octahedron tesselation. The octahedrons are oriented so that the
+square faces are in the horizontal plane with edges parallel to the X
+and Y axes.
+
+Credits: David Eccles (gringer).
+
+=head2 makeGrid(z, gridSize, gridWidth, gridHeight, curveType)
+
+Generate a set of curves (array of array of 2d points) that describe a
+horizontal slice of a truncated regular octahedron with a specified
+grid square size.
+
+=cut
+
+sub makeGrid {
+    my ($z, $gridSize, $gridWidth, $gridHeight, $curveType) = @_;
+    my $scaleFactor = $gridSize;
+    my $normalisedZ = $z / $scaleFactor;
+    my @points = makeNormalisedGrid($normalisedZ, $gridWidth, $gridHeight, $curveType);
+    foreach my $lineRef (@points) {
+        foreach my $pointRef (@$lineRef) {
+            $pointRef->[0] *= $scaleFactor;
+            $pointRef->[1] *= $scaleFactor;
+        }
+    }
+    return @points;
+}
+
+=head1 FUNCTIONS
+=cut
+
+=head2 colinearPoints(offset, gridLength)
+
+Generate an array of points that are in the same direction as the
+basic printing line (i.e. Y points for columns, X points for rows)
+
+Note: a negative offset only causes a change in the perpendicular
+direction
+
+=cut
+
+sub colinearPoints {
+    my ($offset, $baseLocation, $gridLength) = @_;
+    
+    my @points = ();
+    push @points, $baseLocation - abs($offset/2);
+    for (my $i = 0; $i < $gridLength; $i++) {
+        push @points, $baseLocation + $i + abs($offset/2);
+        push @points, $baseLocation + ($i+1) - abs($offset/2);
+    }
+    push @points, $baseLocation + $gridLength + abs($offset/2);
+    return @points;
+}
+
+=head2 colinearPoints(offset, baseLocation, gridLength)
+
+Generate an array of points for the dimension that is perpendicular to
+the basic printing line (i.e. X points for columns, Y points for rows)
+
+=cut
+
+sub perpendPoints {
+    my ($offset, $baseLocation, $gridLength) = @_;
+    
+    my @points = ();
+    my $side = 2*(($baseLocation) % 2) - 1;
+    push @points, $baseLocation - $offset/2 * $side;
+    for (my $i = 0; $i < $gridLength; $i++) {
+        $side = 2*(($i+$baseLocation) % 2) - 1;
+        push @points, $baseLocation + $offset/2 * $side;
+        push @points, $baseLocation + $offset/2 * $side;
+    }
+    push @points, $baseLocation - $offset/2 * $side;
+    
+    return @points;
+}
+
+=head2 trim(pointArrayRef, minX, minY, maxX, maxY)
+
+Trims an array of points to specified rectangular limits. Point
+components that are outside these limits are set to the limits.
+
+=cut
+
+sub trim {
+    my ($pointArrayRef, $minX, $minY, $maxX, $maxY) = @_;
+  
+    foreach (@$pointArrayRef) {
+        $_->[0] = ($_->[0] < $minX) ? $minX : (($_->[0] > $maxX) ? $maxX : $_->[0]);
+        $_->[1] = ($_->[1] < $minY) ? $minY : (($_->[1] > $maxY) ? $maxY : $_->[1]);
+    }
+}
+
+=head2 makeNormalisedGrid(z, gridWidth, gridHeight, curveType)
+
+Generate a set of curves (array of array of 2d points) that describe a
+horizontal slice of a truncated regular octahedron with edge length 1.
+
+curveType specifies which lines to print, 1 for vertical lines
+(columns), 2 for horizontal lines (rows), and 3 for both.
+
+=cut
+
+sub makeNormalisedGrid {
+    my ($z, $gridWidth, $gridHeight, $curveType) = @_;
+    
+    ## offset required to create a regular octagram
+    my $octagramGap = 0.5;
+    
+    # sawtooth wave function for range f($z) = [-$octagramGap .. $octagramGap]
+    my $a = sqrt(2);  # period
+    my $wave = abs(fmod($z, $a) - $a/2)/$a*4 - 1;
+    my $offset = $wave * $octagramGap;
+    
+    my @points = ();
+    if (($curveType & 1) != 0) {
+        for (my $x = 0; $x <= $gridWidth; $x++) {
+            my @xPoints = perpendPoints($offset, $x, $gridHeight);
+            my @yPoints = colinearPoints($offset, 0, $gridHeight);
+            # This is essentially @newPoints = zip(@xPoints, @yPoints)
+            my @newPoints = map [ $xPoints[$_], $yPoints[$_] ], 0..$#xPoints;
+            
+            # trim points to grid edges
+            #trim(\@newPoints, 0, 0, $gridWidth, $gridHeight);
+            
+            if ($x % 2 == 0){
+                push @points, [ @newPoints ];
+            } else {
+                push @points, [ reverse @newPoints ];
+            }
+        }
+    }
+    if (($curveType & 2) != 0) {
+        for (my $y = 0; $y <= $gridHeight; $y++) {
+            my @xPoints = colinearPoints($offset, 0, $gridWidth);
+            my @yPoints = perpendPoints($offset, $y, $gridWidth);
+            my @newPoints = map [ $xPoints[$_], $yPoints[$_] ], 0..$#xPoints;
+            
+            # trim points to grid edges
+            #trim(\@newPoints, 0, 0, $gridWidth, $gridHeight);
+            
+            if ($y % 2 == 0) {
+                push @points, [ @newPoints ];
+            } else {
+                push @points, [ reverse @newPoints ];
+            }
+        }
+    }
+    return @points;
+}
+
+1;
diff --git a/lib/Slic3r/Fill/Base.pm b/lib/Slic3r/Fill/Base.pm
new file mode 100644
index 000000000..75c8e03e6
--- /dev/null
+++ b/lib/Slic3r/Fill/Base.pm
@@ -0,0 +1,91 @@
+package Slic3r::Fill::Base;
+use Moo;
+
+has 'layer_id'            => (is => 'rw');
+has 'z'                   => (is => 'rw'); # in unscaled coordinates
+has 'angle'               => (is => 'rw'); # in radians, ccw, 0 = East
+has 'spacing'             => (is => 'rw'); # in unscaled coordinates
+has 'loop_clipping'       => (is => 'rw', default => sub { 0 }); # in scaled coordinates
+has 'bounding_box'        => (is => 'ro', required => 0);  # Slic3r::Geometry::BoundingBox object
+
+sub adjust_solid_spacing {
+    my $self = shift;
+    my %params = @_;
+    
+    my $number_of_lines = int($params{width} / $params{distance}) + 1;
+    return $params{distance} if $number_of_lines <= 1;
+    
+    my $extra_space = $params{width} % $params{distance};
+    return $params{distance} + $extra_space / ($number_of_lines - 1);
+}
+
+sub no_sort { 0 }
+sub use_bridge_flow { 0 }
+
+
+package Slic3r::Fill::WithDirection;
+use Moo::Role;
+
+use Slic3r::Geometry qw(PI rad2deg);
+
+sub angles () { [0, PI/2] }
+
+sub infill_direction {
+    my $self = shift;
+    my ($surface) = @_;
+    
+    if (!defined $self->angle) {
+        warn "Using undefined infill angle";
+        $self->angle(0);
+    }
+    
+    # set infill angle
+    my (@rotate);
+    $rotate[0] = $self->angle;
+    $rotate[1] = $self->bounding_box
+        ? $self->bounding_box->center
+        : $surface->expolygon->bounding_box->center;
+    my $shift = $rotate[1]->clone;
+    
+    if (defined $self->layer_id) {
+        # alternate fill direction
+        my $layer_num = $self->layer_id / $surface->thickness_layers;
+        my $angle = $self->angles->[$layer_num % @{$self->angles}];
+        $rotate[0] = $self->angle + $angle if $angle;
+    }
+        
+    # use bridge angle
+    if ($surface->bridge_angle >= 0) {
+        Slic3r::debugf "Filling bridge with angle %d\n", rad2deg($surface->bridge_angle);
+        $rotate[0] = $surface->bridge_angle;
+    }
+    
+    $rotate[0] += PI/2;
+    $shift->rotate(@rotate);
+    return [\@rotate, $shift];
+}
+
+# this method accepts any object that implements rotate() and translate()
+sub rotate_points {
+    my $self = shift;
+    my ($expolygon, $rotate_vector) = @_;
+    
+    # rotate points
+    my ($rotate, $shift) = @$rotate_vector;
+    $rotate = [ -$rotate->[0], $rotate->[1] ];
+    $expolygon->rotate(@$rotate);
+    $expolygon->translate(@$shift);
+}
+
+sub rotate_points_back {
+    my $self = shift;
+    my ($paths, $rotate_vector) = @_;
+    
+    my ($rotate, $shift) = @$rotate_vector;
+    $shift = [ map -$_, @$shift ];
+    
+    $_->translate(@$shift) for @$paths;
+    $_->rotate(@$rotate) for @$paths;
+}
+
+1;
diff --git a/lib/Slic3r/Fill/Concentric.pm b/lib/Slic3r/Fill/Concentric.pm
new file mode 100644
index 000000000..ca1837c4e
--- /dev/null
+++ b/lib/Slic3r/Fill/Concentric.pm
@@ -0,0 +1,57 @@
+package Slic3r::Fill::Concentric;
+use Moo;
+
+extends 'Slic3r::Fill::Base';
+
+use Slic3r::Geometry qw(scale unscale X);
+use Slic3r::Geometry::Clipper qw(offset offset2 union_pt_chained);
+
+sub no_sort { 1 }
+
+sub fill_surface {
+    my $self = shift;
+    my ($surface, %params) = @_;
+    
+    # no rotation is supported for this infill pattern
+    
+    my $expolygon = $surface->expolygon;
+    my $bounding_box = $expolygon->bounding_box;
+    
+    my $min_spacing = scale($self->spacing);
+    my $distance = $min_spacing / $params{density};
+    
+    if ($params{density} == 1 && !$params{dont_adjust}) {
+        $distance = $self->adjust_solid_spacing(
+            width       => $bounding_box->size->[X],
+            distance    => $distance,
+        );
+        $self->spacing(unscale $distance);
+    }
+    
+    my @loops = my @last = map $_->clone, @$expolygon;
+    while (@last) {
+        push @loops, @last = @{offset2(\@last, -($distance + 0.5*$min_spacing), +0.5*$min_spacing)};
+    }
+    
+    # generate paths from the outermost to the innermost, to avoid 
+    # adhesion problems of the first central tiny loops
+    @loops = map Slic3r::Polygon->new(@$_),
+        reverse @{union_pt_chained(\@loops)};
+    
+    # split paths using a nearest neighbor search
+    my @paths = ();
+    my $last_pos = Slic3r::Point->new(0,0);
+    foreach my $loop (@loops) {
+        push @paths, $loop->split_at_index($last_pos->nearest_point_index(\@$loop));
+        $last_pos = $paths[-1]->last_point;
+    }
+    
+    # clip the paths to prevent the extruder from getting exactly on the first point of the loop
+    $_->clip_end($self->loop_clipping) for @paths;
+    @paths = grep $_->is_valid, @paths;  # remove empty paths (too short, thus eaten by clipping)
+    
+    # TODO: return ExtrusionLoop objects to get better chained paths
+    return @paths;
+}
+
+1;
diff --git a/lib/Slic3r/Fill/Honeycomb.pm b/lib/Slic3r/Fill/Honeycomb.pm
new file mode 100644
index 000000000..b0fbd65ff
--- /dev/null
+++ b/lib/Slic3r/Fill/Honeycomb.pm
@@ -0,0 +1,129 @@
+package Slic3r::Fill::Honeycomb;
+use Moo;
+
+extends 'Slic3r::Fill::Base';
+with qw(Slic3r::Fill::WithDirection);
+
+has 'cache'         => (is => 'rw', default => sub {{}});
+
+use Slic3r::Geometry qw(PI X Y MIN MAX scale scaled_epsilon);
+use Slic3r::Geometry::Clipper qw(intersection intersection_pl);
+
+sub angles () { [0, PI/3, PI/3*2] }
+
+sub fill_surface {
+    my $self = shift;
+    my ($surface, %params) = @_;
+    
+    my $rotate_vector = $self->infill_direction($surface);
+    
+    # cache hexagons math
+    my $cache_id = sprintf "d%s_s%s", $params{density}, $self->spacing;
+    my $m;
+    if (!($m = $self->cache->{$cache_id})) {
+        $m = $self->cache->{$cache_id} = {};
+        my $min_spacing = scale($self->spacing);
+        $m->{distance} = $min_spacing / $params{density};
+        $m->{hex_side} = $m->{distance} / (sqrt(3)/2);
+        $m->{hex_width} = $m->{distance} * 2;  # $m->{hex_width} == $m->{hex_side} * sqrt(3);
+        my $hex_height = $m->{hex_side} * 2;
+        $m->{pattern_height} = $hex_height + $m->{hex_side};
+        $m->{y_short} = $m->{distance} * sqrt(3)/3;
+        $m->{x_offset} = $min_spacing / 2;
+        $m->{y_offset} = $m->{x_offset} * sqrt(3)/3;
+        $m->{hex_center} = Slic3r::Point->new($m->{hex_width}/2, $m->{hex_side});
+    }
+    
+    my @polygons = ();
+    {
+        # adjust actual bounding box to the nearest multiple of our hex pattern
+        # and align it so that it matches across layers
+        
+        my $bounding_box = $surface->expolygon->bounding_box;
+        {
+            # rotate bounding box according to infill direction
+            my $bb_polygon = $bounding_box->polygon;
+            $bb_polygon->rotate($rotate_vector->[0][0], $m->{hex_center});
+            $bounding_box = $bb_polygon->bounding_box;
+            
+            # extend bounding box so that our pattern will be aligned with other layers
+            # $bounding_box->[X1] and [Y1] represent the displacement between new bounding box offset and old one
+            $bounding_box->merge_point(Slic3r::Point->new(
+                $bounding_box->x_min - ($bounding_box->x_min % $m->{hex_width}),
+                $bounding_box->y_min - ($bounding_box->y_min % $m->{pattern_height}),
+            ));
+        }
+        
+        my $x = $bounding_box->x_min;
+        while ($x <= $bounding_box->x_max) {
+            my $p = [];
+            
+            my @x = ($x + $m->{x_offset}, $x + $m->{distance} - $m->{x_offset});
+            for (1..2) {
+                @$p = reverse @$p; # turn first half upside down
+                my @p = ();
+                for (my $y = $bounding_box->y_min; $y <= $bounding_box->y_max; $y += $m->{y_short} + $m->{hex_side} + $m->{y_short} + $m->{hex_side}) {
+                    push @$p,
+                        [ $x[1], $y + $m->{y_offset} ],
+                        [ $x[0], $y + $m->{y_short} - $m->{y_offset} ],
+                        [ $x[0], $y + $m->{y_short} + $m->{hex_side} + $m->{y_offset} ],
+                        [ $x[1], $y + $m->{y_short} + $m->{hex_side} + $m->{y_short} - $m->{y_offset} ],
+                        [ $x[1], $y + $m->{y_short} + $m->{hex_side} + $m->{y_short} + $m->{hex_side} + $m->{y_offset} ];
+                }
+                @x = map $_ + $m->{distance}, reverse @x; # draw symmetrical pattern
+                $x += $m->{distance};
+            }
+            
+            push @polygons, Slic3r::Polygon->new(@$p);
+        }
+        
+        $_->rotate(-$rotate_vector->[0][0], $m->{hex_center}) for @polygons;
+    }
+    
+    my @paths;
+    if ($params{complete} || 1) {
+        # we were requested to complete each loop;
+        # in this case we don't try to make more continuous paths
+        @paths = map $_->split_at_first_point,
+            @{intersection([ $surface->p ], \@polygons)};
+        
+    } else {
+        # consider polygons as polylines without re-appending the initial point:
+        # this cuts the last segment on purpose, so that the jump to the next 
+        # path is more straight
+        @paths = @{intersection_pl(
+            [ map Slic3r::Polyline->new(@$_), @polygons ],
+            [ @{$surface->expolygon} ],
+        )};
+        
+        # connect paths
+        if (@paths) {  # prevent calling leftmost_point() on empty collections
+            my $collection = Slic3r::Polyline::Collection->new(@paths);
+            @paths = ();
+            foreach my $path (@{$collection->chained_path_from($collection->leftmost_point, 0)}) {
+                if (@paths) {
+                    # distance between first point of this path and last point of last path
+                    my $distance = $paths[-1]->last_point->distance_to($path->first_point);
+                    
+                    if ($distance <= $m->{hex_width}) {
+                        $paths[-1]->append_polyline($path);
+                        next;
+                    }
+                }
+                
+                # make a clone before $collection goes out of scope
+                push @paths, $path->clone;
+            }
+        }
+        
+        # clip paths again to prevent connection segments from crossing the expolygon boundaries
+        @paths = @{intersection_pl(
+            \@paths,
+            [ map @$_, @{$surface->expolygon->offset_ex(scaled_epsilon)} ],
+        )};
+    }
+    
+    return @paths;
+}
+
+1;
diff --git a/lib/Slic3r/Fill/PlanePath.pm b/lib/Slic3r/Fill/PlanePath.pm
new file mode 100644
index 000000000..556835ec4
--- /dev/null
+++ b/lib/Slic3r/Fill/PlanePath.pm
@@ -0,0 +1,118 @@
+package Slic3r::Fill::PlanePath;
+use Moo;
+
+extends 'Slic3r::Fill::Base';
+with qw(Slic3r::Fill::WithDirection);
+
+use Slic3r::Geometry qw(scale X1 Y1 X2 Y2);
+use Slic3r::Geometry::Clipper qw(intersection_pl);
+
+sub angles () { [0] }
+sub multiplier () { 1 }
+
+sub process_polyline {}
+
+sub fill_surface {
+    my $self = shift;
+    my ($surface, %params) = @_;
+    
+    # rotate polygons
+    my $expolygon = $surface->expolygon->clone;
+    my $rotate_vector = $self->infill_direction($surface);
+    $self->rotate_points($expolygon, $rotate_vector);
+    
+    my $distance_between_lines = scale($self->spacing) / $params{density} * $self->multiplier;
+    
+    # align infill across layers using the object's bounding box
+    my $bb_polygon = $self->bounding_box->polygon;
+    $self->rotate_points($bb_polygon, $rotate_vector);
+    my $bounding_box = $bb_polygon->bounding_box;
+    
+    (ref $self) =~ /::([^:]+)$/;
+    my $path = "Math::PlanePath::$1"->new;
+    
+    my $translate = Slic3r::Point->new(0,0);  # vector
+    if ($path->x_negative || $path->y_negative) {
+        # if the curve extends on both positive and negative coordinate space,
+        # center our expolygon around origin
+        $translate = $bounding_box->center->negative;
+    } else {
+        # if the curve does not extend in negative coordinate space,
+        # move expolygon entirely in positive coordinate space
+        $translate = $bounding_box->min_point->negative;
+    }
+    $expolygon->translate(@$translate);
+    $bounding_box->translate(@$translate);
+    
+    my ($n_lo, $n_hi) = $path->rect_to_n_range(
+        map { $_ / $distance_between_lines }
+            @{$bounding_box->min_point},
+            @{$bounding_box->max_point},
+    );
+    
+    my $polyline = Slic3r::Polyline->new(
+        map [ map { $_ * $distance_between_lines } $path->n_to_xy($_) ], ($n_lo..$n_hi)
+    );
+    return {} if @$polyline <= 1;
+    
+    $self->process_polyline($polyline, $bounding_box);
+    
+    my @paths = @{intersection_pl([$polyline], \@$expolygon)};
+    
+    if (0) {
+        require "Slic3r/SVG.pm";
+        Slic3r::SVG::output("fill.svg",
+            no_arrows       => 1,
+            polygons        => \@$expolygon,
+            green_polygons  => [ $bounding_box->polygon ],
+            polylines       => [ $polyline ],
+            red_polylines   => \@paths,
+        );
+    }
+    
+    # paths must be repositioned and rotated back
+    $_->translate(@{$translate->negative}) for @paths;
+    $self->rotate_points_back(\@paths, $rotate_vector);
+    
+    return @paths;
+}
+
+
+package Slic3r::Fill::ArchimedeanChords;
+use Moo;
+extends 'Slic3r::Fill::PlanePath';
+use Math::PlanePath::ArchimedeanChords;
+
+
+package Slic3r::Fill::Flowsnake;
+use Moo;
+extends 'Slic3r::Fill::PlanePath';
+use Math::PlanePath::Flowsnake;
+use Slic3r::Geometry qw(X);
+
+# Sorry, this fill is currently broken.
+
+sub process_polyline {
+    my $self = shift;
+    my ($polyline, $bounding_box) = @_;
+    
+    $_->[X] += $bounding_box->center->[X] for @$polyline;
+}
+
+
+package Slic3r::Fill::HilbertCurve;
+use Moo;
+extends 'Slic3r::Fill::PlanePath';
+use Math::PlanePath::HilbertCurve;
+
+
+package Slic3r::Fill::OctagramSpiral;
+use Moo;
+extends 'Slic3r::Fill::PlanePath';
+use Math::PlanePath::OctagramSpiral;
+
+sub multiplier () { sqrt(2) }
+
+
+
+1;
diff --git a/lib/Slic3r/Fill/Rectilinear.pm b/lib/Slic3r/Fill/Rectilinear.pm
new file mode 100644
index 000000000..0922ff771
--- /dev/null
+++ b/lib/Slic3r/Fill/Rectilinear.pm
@@ -0,0 +1,168 @@
+package Slic3r::Fill::Rectilinear;
+use Moo;
+
+extends 'Slic3r::Fill::Base';
+with qw(Slic3r::Fill::WithDirection);
+
+has '_min_spacing'          => (is => 'rw');
+has '_line_spacing'         => (is => 'rw');
+has '_diagonal_distance'    => (is => 'rw');
+has '_line_oscillation'     => (is => 'rw');
+
+use Slic3r::Geometry qw(scale unscale scaled_epsilon);
+use Slic3r::Geometry::Clipper qw(intersection_pl);
+
+sub horizontal_lines { 0 }
+
+sub fill_surface {
+    my $self = shift;
+    my ($surface, %params) = @_;
+    
+    # rotate polygons so that we can work with vertical lines here
+    my $expolygon = $surface->expolygon->clone;
+    my $rotate_vector = $self->infill_direction($surface);
+    $self->rotate_points($expolygon, $rotate_vector);
+    
+    $self->_min_spacing(scale $self->spacing);
+    $self->_line_spacing($self->_min_spacing / $params{density});
+    $self->_diagonal_distance($self->_line_spacing * 2);
+    $self->_line_oscillation($self->_line_spacing - $self->_min_spacing);  # only for Line infill
+    my $bounding_box = $expolygon->bounding_box;
+    
+    # define flow spacing according to requested density
+    if ($params{density} == 1 && !$params{dont_adjust}) {
+        $self->_line_spacing($self->adjust_solid_spacing(
+            width       => $bounding_box->size->x,
+            distance    => $self->_line_spacing,
+        ));
+        $self->spacing(unscale $self->_line_spacing);
+    } else {
+        # extend bounding box so that our pattern will be aligned with other layers
+        $bounding_box->merge_point(Slic3r::Point->new(
+            $bounding_box->x_min - ($bounding_box->x_min % $self->_line_spacing),
+            $bounding_box->y_min - ($bounding_box->y_min % $self->_line_spacing),
+        ));
+    }
+    
+    # generate the basic pattern
+    my $x_max = $bounding_box->x_max + scaled_epsilon;
+    my @lines  = ();
+    for (my $x = $bounding_box->x_min; $x <= $x_max; $x += $self->_line_spacing) {
+        push @lines, $self->_line($#lines, $x, $bounding_box->y_min, $bounding_box->y_max);
+    }
+    if ($self->horizontal_lines) {
+        my $y_max = $bounding_box->y_max + scaled_epsilon;
+        for (my $y = $bounding_box->y_min; $y <= $y_max; $y += $self->_line_spacing) {
+            push @lines, Slic3r::Polyline->new(
+                [$bounding_box->x_min, $y],
+                [$bounding_box->x_max, $y],
+            );
+        }
+    }
+    
+    # clip paths against a slightly larger expolygon, so that the first and last paths
+    # are kept even if the expolygon has vertical sides
+    # the minimum offset for preventing edge lines from being clipped is scaled_epsilon;
+    # however we use a larger offset to support expolygons with slightly skewed sides and 
+    # not perfectly straight
+    my @polylines = @{intersection_pl(\@lines, $expolygon->offset(+scale 0.02))};
+    
+    my $extra = $self->_min_spacing * &Slic3r::INFILL_OVERLAP_OVER_SPACING;
+    foreach my $polyline (@polylines) {
+        my ($first_point, $last_point) = @$polyline[0,-1];
+        if ($first_point->y > $last_point->y) { #>
+            ($first_point, $last_point) = ($last_point, $first_point);
+        }
+        $first_point->set_y($first_point->y - $extra);  #--
+        $last_point->set_y($last_point->y + $extra);    #++
+    }
+    
+    # connect lines
+    unless ($params{dont_connect} || !@polylines) {  # prevent calling leftmost_point() on empty collections
+        # offset the expolygon by max(min_spacing/2, extra)
+        my ($expolygon_off) = @{$expolygon->offset_ex($self->_min_spacing/2)};
+        my $collection = Slic3r::Polyline::Collection->new(@polylines);
+        @polylines = ();
+        
+        foreach my $polyline (@{$collection->chained_path_from($collection->leftmost_point, 0)}) {
+            if (@polylines) {
+                my $first_point = $polyline->first_point;
+                my $last_point = $polylines[-1]->last_point;
+                my @distance = map abs($first_point->$_ - $last_point->$_), qw(x y);
+                
+                # TODO: we should also check that both points are on a fill_boundary to avoid 
+                # connecting paths on the boundaries of internal regions
+                if ($self->_can_connect(@distance) && $expolygon_off->contains_line(Slic3r::Line->new($last_point, $first_point))) {
+                    $polylines[-1]->append_polyline($polyline);
+                    next;
+                }
+            }
+            
+            # make a clone before $collection goes out of scope
+            push @polylines, $polyline->clone;
+        }
+    }
+    
+    # paths must be rotated back
+    $self->rotate_points_back(\@polylines, $rotate_vector);
+    
+    return @polylines;
+}
+
+sub _line {
+    my ($self, $i, $x, $y_min, $y_max) = @_;
+    
+    return Slic3r::Polyline->new(
+        [$x, $y_min],
+        [$x, $y_max],
+    );
+}
+
+sub _can_connect {
+    my ($self, $dist_X, $dist_Y) = @_;
+    
+    return $dist_X <= $self->_diagonal_distance
+        && $dist_Y <= $self->_diagonal_distance;
+}
+
+
+package Slic3r::Fill::Line;
+use Moo;
+extends 'Slic3r::Fill::Rectilinear';
+
+use Slic3r::Geometry qw(scaled_epsilon);
+
+sub _line {
+    my ($self, $i, $x, $y_min, $y_max) = @_;
+    
+    if ($i % 2) {
+        return Slic3r::Polyline->new(
+            [$x - $self->_line_oscillation, $y_min],
+            [$x + $self->_line_oscillation, $y_max],
+        );
+    } else {
+        return Slic3r::Polyline->new(
+            [$x, $y_min],
+            [$x, $y_max],
+        );
+    }
+}
+
+sub _can_connect {
+    my ($self, $dist_X, $dist_Y) = @_;
+    
+    my $TOLERANCE = 10 * scaled_epsilon;
+    return ($dist_X >= ($self->_line_spacing - $self->_line_oscillation) - $TOLERANCE)
+        && ($dist_X <= ($self->_line_spacing + $self->_line_oscillation) + $TOLERANCE)
+        && $dist_Y <= $self->_diagonal_distance;
+}
+
+
+package Slic3r::Fill::Grid;
+use Moo;
+extends 'Slic3r::Fill::Rectilinear';
+
+sub angles () { [0] }
+sub horizontal_lines { 1 }
+
+1;
diff --git a/lib/Slic3r/GUI.pm b/lib/Slic3r/GUI.pm
index 1c811fa78..7f4a028a5 100644
--- a/lib/Slic3r/GUI.pm
+++ b/lib/Slic3r/GUI.pm
@@ -40,7 +40,6 @@ use Wx 0.9901 qw(:bitmap :dialog :icon :id :misc :systemsettings :toplevelwindow
     :filedialog :font);
 use Wx::Event qw(EVT_IDLE EVT_COMMAND);
 use base 'Wx::App';
-#use base 'Wx::AppConsole';
 
 use constant FILE_WILDCARDS => {
     known   => 'Known files (*.stl, *.obj, *.amf, *.xml)|*.stl;*.STL;*.obj;*.OBJ;*.amf;*.AMF;*.xml;*.XML',
diff --git a/lib/Slic3r/GUI/MainFrame.pm b/lib/Slic3r/GUI/MainFrame.pm
index 4c04066bb..d97ad22ef 100644
--- a/lib/Slic3r/GUI/MainFrame.pm
+++ b/lib/Slic3r/GUI/MainFrame.pm
@@ -294,13 +294,8 @@ sub _init_menubar {
         $self->_append_menu_item($helpMenu, "&About Slic3r", 'Show about dialog', sub {
             wxTheApp->about;
         });
-        if (Slic3r::GUI::debugged()) {
-            $self->_append_menu_item($helpMenu, "&Debug", 'Break to debugger', sub {
-                Slic3r::GUI::break_to_debugger();
-            });
-        }
     }
-
+    
     # menubar
     # assign menubar to frame after appending items, otherwise special items
     # will not be handled correctly
diff --git a/lib/Slic3r/Print/SupportMaterial.pm b/lib/Slic3r/Print/SupportMaterial.pm
index acfa5efee..eea6397af 100644
--- a/lib/Slic3r/Print/SupportMaterial.pm
+++ b/lib/Slic3r/Print/SupportMaterial.pm
@@ -675,8 +675,8 @@ sub generate_toolpaths {
         
         # interface and contact infill
         if (@$interface || @$contact_infill) {
-            $fillers{interface}->set_angle($interface_angle);
-            $fillers{interface}->set_spacing($_interface_flow->spacing);
+            $fillers{interface}->angle($interface_angle);
+            $fillers{interface}->spacing($_interface_flow->spacing);
             
             # find centerline of the external loop
             $interface = offset2($interface, +scaled_epsilon, -(scaled_epsilon + $_interface_flow->scaled_width/2));
@@ -702,7 +702,7 @@ sub generate_toolpaths {
             
             my @paths = ();
             foreach my $expolygon (@{union_ex($interface)}) {
-                my $polylines = $fillers{interface}->fill_surface(
+                my @p = $fillers{interface}->fill_surface(
                     Slic3r::Surface->new(expolygon => $expolygon, surface_type => S_TYPE_INTERNAL),
                     density      => $interface_density,
                     layer_height => $layer->height,
@@ -711,12 +711,12 @@ sub generate_toolpaths {
                 my $mm3_per_mm = $_interface_flow->mm3_per_mm;
                 
                 push @paths, map Slic3r::ExtrusionPath->new(
-                    polyline    => $_,
+                    polyline    => Slic3r::Polyline->new(@$_),
                     role        => EXTR_ROLE_SUPPORTMATERIAL_INTERFACE,
                     mm3_per_mm  => $mm3_per_mm,
                     width       => $_interface_flow->width,
                     height      => $layer->height,
-                ), @$polylines,
+                ), @p;
             }
             
             $layer->support_interface_fills->append(@paths);
@@ -725,11 +725,11 @@ sub generate_toolpaths {
         # support or flange
         if (@$base) {
             my $filler = $fillers{support};
-            $filler->set_angle($angles[ ($layer_id) % @angles ]);
+            $filler->angle($angles[ ($layer_id) % @angles ]);
             
             # We don't use $base_flow->spacing because we need a constant spacing
             # value that guarantees that all layers are correctly aligned.
-            $filler->set_spacing($flow->spacing);
+            $filler->spacing($flow->spacing);
             
             my $density     = $support_density;
             my $base_flow   = $_flow;
@@ -742,13 +742,13 @@ sub generate_toolpaths {
             # base flange
             if ($layer_id == 0) {
                 $filler = $fillers{interface};
-                $filler->set_angle($self->object_config->support_material_angle + 90);
+                $filler->angle($self->object_config->support_material_angle + 90);
                 $density        = 0.5;
                 $base_flow      = $self->first_layer_flow;
                 
                 # use the proper spacing for first layer as we don't need to align
                 # its pattern to the other layers
-                $filler->set_spacing($base_flow->spacing);
+                $filler->spacing($base_flow->spacing);
             } else {
                 # draw a perimeter all around support infill
                 # TODO: use brim ordering algorithm
@@ -767,7 +767,7 @@ sub generate_toolpaths {
             
             my $mm3_per_mm = $base_flow->mm3_per_mm;
             foreach my $expolygon (@$to_infill) {
-                my $polylines = $filler->fill_surface(
+                my @p = $filler->fill_surface(
                     Slic3r::Surface->new(expolygon => $expolygon, surface_type => S_TYPE_INTERNAL),
                     density     => $density,
                     layer_height => $layer->height,
@@ -775,12 +775,12 @@ sub generate_toolpaths {
                 );
                 
                 push @paths, map Slic3r::ExtrusionPath->new(
-                    polyline    => $_,
+                    polyline    => Slic3r::Polyline->new(@$_),
                     role        => EXTR_ROLE_SUPPORTMATERIAL,
                     mm3_per_mm  => $mm3_per_mm,
                     width       => $base_flow->width,
                     height      => $layer->height,
-                ), @$polylines;
+                ), @p;
             }
             
             $layer->support_fills->append(@paths);
diff --git a/xs/Build.PL b/xs/Build.PL
index bdf5abbd3..5413952bb 100644
--- a/xs/Build.PL
+++ b/xs/Build.PL
@@ -40,15 +40,10 @@ if (defined $ENV{BOOST_INCLUDEDIR}) {
         push @boost_include, $ENV{BOOST_DIR};
     }
 } else {
-    push @boost_include, grep { -d $_ }
-        qw(/opt/local/include /usr/local/include /opt/include),
-        qw(/usr/include C:\Boost\include);
-    push @boost_libs, grep { -d $_ }
-        qw(/opt/local/lib /usr/local/lib /opt/lib /usr/lib),
-        qw(C:\Boost\lib /lib);
-    
-    if ($^O eq 'MSWin32') {
-        for my $path (glob('C:\dev\boost*'), glob ('C:\boost*'), glob ('d:\src\boost*')) {
+    # Boost library was not defined by the environment.
+    # Try to guess at some default paths.
+    if ($mswin) {
+        for my $path (glob('C:\dev\boost*\include'), glob ('C:\boost*\include')) {
             push @boost_include, $path;
         }
         if (! @boost_include) {
diff --git a/xs/src/libslic3r/Fill/FillRectilinear2.cpp b/xs/src/libslic3r/Fill/FillRectilinear2.cpp
index 1b9019305..40905de0d 100644
--- a/xs/src/libslic3r/Fill/FillRectilinear2.cpp
+++ b/xs/src/libslic3r/Fill/FillRectilinear2.cpp
@@ -17,7 +17,7 @@
 #include "SVG.hpp"
 #endif
 
-#if defined(SLIC3R_DEBUG) and defined(_WIN32)
+#if defined(SLIC3R_DEBUG) && defined(_WIN32)
 #include <Windows.h>
 #pragma comment(lib, "user32.lib")
     static inline void assert_fail(const char *assertion, const char *file, unsigned line, const char *function)
@@ -376,7 +376,7 @@ static inline int intersection_on_prev_vertical_line(
     return intersection_on_prev_next_vertical_line(poly_with_offset, segs, iVerticalLine, iInnerContour, iIntersection, false);
 }
 
-static inline intersection_on_next_vertical_line(
+static inline int intersection_on_next_vertical_line(
     const ExPolygonWithOffset                     &poly_with_offset, 
     const std::vector<SegmentedIntersectionLine>  &segs, 
     size_t                                         iVerticalLine, 
@@ -415,7 +415,7 @@ static inline int intersection_unused_on_prev_next_vertical_line(
     return iIntersectionOther;
 }
 
-static inline intersection_unused_on_prev_vertical_line(
+static inline int intersection_unused_on_prev_vertical_line(
     const ExPolygonWithOffset                     &poly_with_offset, 
     const std::vector<SegmentedIntersectionLine>  &segs, 
     size_t                                         iVerticalLine, 
@@ -425,7 +425,7 @@ static inline intersection_unused_on_prev_vertical_line(
     return intersection_unused_on_prev_next_vertical_line(poly_with_offset, segs, iVerticalLine, iInnerContour, iIntersection, false);
 }
 
-static inline intersection_unused_on_next_vertical_line(
+static inline int intersection_unused_on_next_vertical_line(
     const ExPolygonWithOffset                     &poly_with_offset, 
     const std::vector<SegmentedIntersectionLine>  &segs, 
     size_t                                         iVerticalLine,