Refactoring: move direction math into a single function. Includes some fixes and adjustments

9 files changed, 59 insertions, 13 deletions

diff --git a/lib/Slic3r/Geometry.pm b/lib/Slic3r/Geometry.pm
index d647f2a85..18c05dfa5 100644
--- a/lib/Slic3r/Geometry.pm
+++ b/lib/Slic3r/Geometry.pm
@@ -20,7 +20,7 @@ our @EXPORT_OK = qw(
     rad2deg_dir bounding_box_center line_intersects_any douglas_peucker
     polyline_remove_short_segments normal triangle_normal polygon_is_convex
     scaled_epsilon bounding_box_3D size_3D size_2D
-    convex_hull
+    convex_hull directions_parallel directions_parallel_within
 );
 
 
diff --git a/lib/Slic3r/Layer/BridgeDetector.pm b/lib/Slic3r/Layer/BridgeDetector.pm
index f27cda3b2..795f5a624 100644
--- a/lib/Slic3r/Layer/BridgeDetector.pm
+++ b/lib/Slic3r/Layer/BridgeDetector.pm
@@ -2,7 +2,7 @@ package Slic3r::Layer::BridgeDetector;
 use Moo;
 
 use List::Util qw(first sum max min);
-use Slic3r::Geometry qw(PI unscale scaled_epsilon rad2deg epsilon);
+use Slic3r::Geometry qw(PI unscale scaled_epsilon rad2deg epsilon directions_parallel_within);
 use Slic3r::Geometry::Clipper qw(intersection_pl intersection_ex union offset diff_pl union_ex);
 
 has 'expolygon'         => (is => 'ro', required => 1);
@@ -84,10 +84,11 @@ sub detect_angle {
     
     # remove duplicates
     my $min_resolution = PI/180; # 1 degree
-    @angles = map { ($_ >= &PI-&epsilon) ? ($_-&PI) : $_ } @angles;
-    @angles = sort @angles;
-    for (my $i = 1; $i <= $#angles; ++$i) {
-        if (abs($angles[$i] - $angles[$i-1]) < $min_resolution) {
+    # proceed in reverse order so that when we compare first value with last one (-1)
+    # we remove the greatest one (PI) in case they are parallel (PI, 0)
+    @angles = reverse sort @angles;
+    for (my $i = 0; $i <= $#angles; ++$i) {
+        if (directions_parallel_within($angles[$i], $angles[$i-1], $min_resolution)) {
             splice @angles, $i, 1;
             --$i;
         }
@@ -246,8 +247,13 @@ sub unsupported_edges {
     );
     
     # split into individual segments and filter out edges parallel to the bridging angle
+    # TODO: angle tolerance should probably be based on segment length and flow width,
+    # so that we build supports whenever there's a chance that at least one or two bridge
+    # extrusions would be anchored within such length (i.e. a slightly non-parallel bridging
+    # direction might still benefit from anchors if long enough)
+    my $angle_tolerance = PI/180*5;
     @$unsupported = map $_->as_polyline,
-        grep !$_->parallel_to($angle),
+        grep !directions_parallel_within($_->direction, $angle, $angle_tolerance),
         map @{$_->lines},
         @$unsupported;
     
diff --git a/lib/Slic3r/Polyline.pm b/lib/Slic3r/Polyline.pm
index d4517895c..eeda93047 100644
--- a/lib/Slic3r/Polyline.pm
+++ b/lib/Slic3r/Polyline.pm
@@ -34,7 +34,7 @@ sub is_straight {
     # first point and last point. (Checking each line against the previous
     # one would have caused the error to accumulate.)
     my $dir = Slic3r::Line->new($self->first_point, $self->last_point)->direction;
-    return !defined first { abs($_->direction - $dir) > epsilon } @{$self->lines};
+    return !defined first { !$_->parallel_to($dir) } @{$self->lines};
 }
 
 1;
diff --git a/xs/src/Geometry.cpp b/xs/src/Geometry.cpp
index bb673813b..c0d9e66cd 100644
--- a/xs/src/Geometry.cpp
+++ b/xs/src/Geometry.cpp
@@ -93,6 +93,14 @@ chained_path_items(Points &points, T &items, T &retval)
 }
 template void chained_path_items(Points &points, ClipperLib::PolyNodes &items, ClipperLib::PolyNodes &retval);
 
+bool
+directions_parallel(double angle1, double angle2, double max_diff)
+{
+    double diff = fabs(angle1 - angle2);
+    max_diff += EPSILON;
+    return diff < max_diff || fabs(diff - PI) < max_diff;
+}
+
 Line
 MedialAxis::edge_to_line(const VD::edge_type &edge) const
 {
diff --git a/xs/src/Geometry.hpp b/xs/src/Geometry.hpp
index 9c758c616..2dc183f82 100644
--- a/xs/src/Geometry.hpp
+++ b/xs/src/Geometry.hpp
@@ -15,6 +15,7 @@ void convex_hull(Points &points, Polygon* hull);
 void chained_path(Points &points, std::vector<Points::size_type> &retval, Point start_near);
 void chained_path(Points &points, std::vector<Points::size_type> &retval);
 template<class T> void chained_path_items(Points &points, T &items, T &retval);
+bool directions_parallel(double angle1, double angle2, double max_diff = 0);
 
 class MedialAxis {
     public:
diff --git a/xs/src/Line.cpp b/xs/src/Line.cpp
index 8efa4442a..fb66629d6 100644
--- a/xs/src/Line.cpp
+++ b/xs/src/Line.cpp
@@ -1,3 +1,4 @@
+#include "Geometry.hpp"
 #include "Line.hpp"
 #include "Polyline.hpp"
 #include <algorithm>
@@ -113,8 +114,7 @@ Line::direction() const
 
 bool
 Line::parallel_to(double angle) const {
-    double diff = abs(this->direction() - angle);
-    return (diff < EPSILON) || (abs(diff - PI) < EPSILON);
+    return Slic3r::Geometry::directions_parallel(this->direction(), angle);
 }
 
 bool
diff --git a/xs/t/10_line.t b/xs/t/10_line.t
index dc1ad7dc7..b6ec3c316 100644
--- a/xs/t/10_line.t
+++ b/xs/t/10_line.t
@@ -54,12 +54,12 @@ foreach my $base_angle (0, PI/4, PI/2, PI) {
     }
     {
         my $line2 = $line->clone;
-        $line2->rotate(+EPSILON/2, [0,0]);
+        $line2->rotate(+(EPSILON)/2, [0,0]);
         ok $line->parallel_to_line($line2), 'line is parallel within epsilon';
     }
     {
         my $line2 = $line->clone;
-        $line2->rotate(-EPSILON/2, [0,0]);
+        $line2->rotate(-(EPSILON)/2, [0,0]);
         ok $line->parallel_to_line($line2), 'line is parallel within epsilon';
     }
 }
diff --git a/xs/t/14_geometry.t b/xs/t/14_geometry.t
index 4324da818..8dfdecb78 100644
--- a/xs/t/14_geometry.t
+++ b/xs/t/14_geometry.t
@@ -4,7 +4,9 @@ use strict;
 use warnings;
 
 use Slic3r::XS;
-use Test::More tests => 2;
+use Test::More tests => 8;
+
+use constant PI => 4 * atan2(1, 1);
 
 {
     my @points = (
@@ -19,4 +21,14 @@ use Test::More tests => 2;
     is scalar(@$hull), 4, 'convex_hull returns the correct number of points';
 }
 
+# directions_parallel() and directions_parallel_within() are tested
+# also with Slic3r::Line::parallel_to() tests in 10_line.t
+{
+    ok Slic3r::Geometry::directions_parallel_within(0, 0, 0), 'directions_parallel_within';
+    ok Slic3r::Geometry::directions_parallel_within(0, PI, 0), 'directions_parallel_within';
+    ok Slic3r::Geometry::directions_parallel_within(0, 0, PI/180), 'directions_parallel_within';
+    ok Slic3r::Geometry::directions_parallel_within(0, PI, PI/180), 'directions_parallel_within';
+    ok !Slic3r::Geometry::directions_parallel_within(PI/2, PI, 0), 'directions_parallel_within';
+    ok !Slic3r::Geometry::directions_parallel_within(PI/2, PI, PI/180), 'directions_parallel_within';
+}
 __END__
diff --git a/xs/xsp/Geometry.xsp b/xs/xsp/Geometry.xsp
index b0497e356..85d2d359b 100644
--- a/xs/xsp/Geometry.xsp
+++ b/xs/xsp/Geometry.xsp
@@ -11,6 +11,25 @@
 
 %{
 
+bool
+directions_parallel(angle1, angle2)
+    double      angle1
+    double      angle2
+    CODE:
+        RETVAL = Slic3r::Geometry::directions_parallel(angle1, angle2);
+    OUTPUT:
+        RETVAL
+
+bool
+directions_parallel_within(angle1, angle2, max_diff)
+    double      angle1
+    double      angle2
+    double      max_diff
+    CODE:
+        RETVAL = Slic3r::Geometry::directions_parallel(angle1, angle2, max_diff);
+    OUTPUT:
+        RETVAL
+
 Polygon*
 convex_hull(points)
     Points      points