1 #include <catch2/catch.hpp>
2
3 #include <numeric>
4 #include <iostream>
5 #include <boost/filesystem.hpp>
6
7 #include "libslic3r/ClipperUtils.hpp"
8 #include "libslic3r/ExPolygon.hpp"
9 #include "libslic3r/SVG.hpp"
10
11 using namespace Slic3r;
12
13 SCENARIO("Various Clipper operations - xs/t/11_clipper.t", "[ClipperUtils]") {
14 // CCW oriented contour
15 Slic3r::Polygon square{ { 200, 100 }, {200, 200}, {100, 200}, {100, 100} };
16 // CW oriented contour
17 Slic3r::Polygon hole_in_square{ { 160, 140 }, { 140, 140 }, { 140, 160 }, { 160, 160 } };
18 Slic3r::ExPolygon square_with_hole(square, hole_in_square);
19 GIVEN("square_with_hole") {
20 WHEN("offset") {
21 Polygons result = Slic3r::offset(square_with_hole, 5.f);
22 THEN("offset matches") {
23 REQUIRE(result == Polygons {
24 { { 205, 205 }, { 95, 205 }, { 95, 95 }, { 205, 95 }, },
25 { { 145, 145 }, { 145, 155 }, { 155, 155 }, { 155, 145 } } });
26 }
27 }
28 WHEN("offset_ex") {
29 ExPolygons result = Slic3r::offset_ex(square_with_hole, 5.f);
30 THEN("offset matches") {
31 REQUIRE(result == ExPolygons { {
32 { { 205, 205 }, { 95, 205 }, { 95, 95 }, { 205, 95 }, },
33 { { 145, 145 }, { 145, 155 }, { 155, 155 }, { 155, 145 } } } } );
34 }
35 }
36 WHEN("offset2_ex") {
37 ExPolygons result = Slic3r::offset2_ex(square_with_hole, 5.f, -2.f);
38 THEN("offset matches") {
39 REQUIRE(result == ExPolygons { {
40 { { 203, 203 }, { 97, 203 }, { 97, 97 }, { 203, 97 } },
41 { { 143, 143 }, { 143, 157 }, { 157, 157 }, { 157, 143 } } } } );
42 }
43 }
44 }
45 GIVEN("square_with_hole 2") {
46 Slic3r::ExPolygon square_with_hole(
47 { { 20000000, 20000000 }, { 0, 20000000 }, { 0, 0 }, { 20000000, 0 } },
48 { { 5000000, 15000000 }, { 15000000, 15000000 }, { 15000000, 5000000 }, { 5000000, 5000000 } });
49 WHEN("offset2_ex") {
50 Slic3r::ExPolygons result = Slic3r::offset2_ex(ExPolygons { square_with_hole }, -1.f, 1.f);
51 THEN("offset matches") {
52 REQUIRE(result.size() == 1);
53 REQUIRE(square_with_hole.area() == result.front().area());
54 }
55 }
56 }
57 GIVEN("square and hole") {
58 WHEN("diff_ex") {
59 ExPolygons result = Slic3r::diff_ex({ square }, { hole_in_square });
60 THEN("hole is created") {
61 REQUIRE(result.size() == 1);
62 REQUIRE(square_with_hole.area() == result.front().area());
63 }
64 }
65 }
66 GIVEN("polyline") {
67 Polyline polyline { { 50, 150 }, { 300, 150 } };
68 WHEN("intersection_pl") {
69 Polylines result = Slic3r::intersection_pl({ polyline }, { square, hole_in_square });
70 THEN("correct number of result lines") {
71 REQUIRE(result.size() == 2);
72 }
73 THEN("result lines have correct length") {
74 // results are in no particular order
75 REQUIRE(result[0].length() == 40);
76 REQUIRE(result[1].length() == 40);
77 }
78 }
79 WHEN("diff_pl") {
80 Polylines result = Slic3r::diff_pl({ polyline }, { square, hole_in_square });
81 THEN("correct number of result lines") {
82 REQUIRE(result.size() == 3);
83 }
84 // results are in no particular order
85 THEN("the left result line has correct length") {
__anonc04cf4260102(const Polyline &pl) 86 REQUIRE(std::count_if(result.begin(), result.end(), [](const Polyline &pl) { return pl.length() == 50; }) == 1);
87 }
88 THEN("the right result line has correct length") {
__anonc04cf4260202(const Polyline &pl) 89 REQUIRE(std::count_if(result.begin(), result.end(), [](const Polyline &pl) { return pl.length() == 100; }) == 1);
90 }
91 THEN("the central result line has correct length") {
__anonc04cf4260302(const Polyline &pl) 92 REQUIRE(std::count_if(result.begin(), result.end(), [](const Polyline &pl) { return pl.length() == 20; }) == 1);
93 }
94 }
95 }
96 GIVEN("Clipper bug #96 / Slic3r issue #2028") {
97 Slic3r::Polyline subject{
98 { 44735000, 31936670 }, { 55270000, 31936670 }, { 55270000, 25270000 }, { 74730000, 25270000 }, { 74730000, 44730000 }, { 68063296, 44730000 }, { 68063296, 55270000 }, { 74730000, 55270000 },
99 { 74730000, 74730000 }, { 55270000, 74730000 }, { 55270000, 68063296 }, { 44730000, 68063296 }, { 44730000, 74730000 }, { 25270000, 74730000 }, { 25270000, 55270000 }, { 31936670, 55270000 },
100 { 31936670, 44730000 }, { 25270000, 44730000 }, { 25270000, 25270000 }, { 44730000, 25270000 }, { 44730000, 31936670 } };
101 Slic3r::Polygon clip { {75200000, 45200000}, {54800000, 45200000}, {54800000, 24800000}, {75200000, 24800000} };
102 Slic3r::Polylines result = Slic3r::intersection_pl({ subject }, { clip });
103 THEN("intersection_pl - result is not empty") {
104 REQUIRE(result.size() == 1);
105 }
106 }
107 GIVEN("Clipper bug #122") {
108 Slic3r::Polyline subject { { 1975, 1975 }, { 25, 1975 }, { 25, 25 }, { 1975, 25 }, { 1975, 1975 } };
109 Slic3r::Polygons clip { { { 2025, 2025 }, { -25, 2025 } , { -25, -25 }, { 2025, -25 } },
110 { { 525, 525 }, { 525, 1475 }, { 1475, 1475 }, { 1475, 525 } } };
111 Slic3r::Polylines result = Slic3r::intersection_pl({ subject }, clip);
112 THEN("intersection_pl - result is not empty") {
113 REQUIRE(result.size() == 1);
114 REQUIRE(result.front().points.size() == 5);
115 }
116 }
117 GIVEN("Clipper bug #126") {
118 Slic3r::Polyline subject { { 200000, 19799999 }, { 200000, 200000 }, { 24304692, 200000 }, { 15102879, 17506106 }, { 13883200, 19799999 }, { 200000, 19799999 } };
119 Slic3r::Polygon clip { { 15257205, 18493894 }, { 14350057, 20200000 }, { -200000, 20200000 }, { -200000, -200000 }, { 25196917, -200000 } };
120 Slic3r::Polylines result = Slic3r::intersection_pl({ subject }, { clip });
121 THEN("intersection_pl - result is not empty") {
122 REQUIRE(result.size() == 1);
123 }
124 THEN("intersection_pl - result has same length as subject polyline") {
125 REQUIRE(result.front().length() == Approx(subject.length()));
126 }
127 }
128
129 #if 0
130 {
131 # Clipper does not preserve polyline orientation
132 my $polyline = Slic3r::Polyline->new([50, 150], [300, 150]);
133 my $result = Slic3r::Geometry::Clipper::intersection_pl([$polyline], [$square]);
134 is scalar(@$result), 1, 'intersection_pl - correct number of result lines';
135 is_deeply $result->[0]->pp, [[100, 150], [200, 150]], 'clipped line orientation is preserved';
136 }
137 {
138 # Clipper does not preserve polyline orientation
139 my $polyline = Slic3r::Polyline->new([300, 150], [50, 150]);
140 my $result = Slic3r::Geometry::Clipper::intersection_pl([$polyline], [$square]);
141 is scalar(@$result), 1, 'intersection_pl - correct number of result lines';
142 is_deeply $result->[0]->pp, [[200, 150], [100, 150]], 'clipped line orientation is preserved';
143 }
144 {
145 # Disabled until Clipper bug #127 is fixed
146 my $subject = [
147 Slic3r::Polyline->new([-90000000, -100000000], [-90000000, 100000000]), # vertical
148 Slic3r::Polyline->new([-100000000, -10000000], [100000000, -10000000]), # horizontal
149 Slic3r::Polyline->new([-100000000, 0], [100000000, 0]), # horizontal
150 Slic3r::Polyline->new([-100000000, 10000000], [100000000, 10000000]), # horizontal
151 ];
152 my $clip = Slic3r::Polygon->new(# a circular, convex, polygon
153 [99452190, 10452846], [97814760, 20791169], [95105652, 30901699], [91354546, 40673664], [86602540, 50000000],
154 [80901699, 58778525], [74314483, 66913061], [66913061, 74314483], [58778525, 80901699], [50000000, 86602540],
155 [40673664, 91354546], [30901699, 95105652], [20791169, 97814760], [10452846, 99452190], [0, 100000000],
156 [-10452846, 99452190], [-20791169, 97814760], [-30901699, 95105652], [-40673664, 91354546],
157 [-50000000, 86602540], [-58778525, 80901699], [-66913061, 74314483], [-74314483, 66913061],
158 [-80901699, 58778525], [-86602540, 50000000], [-91354546, 40673664], [-95105652, 30901699],
159 [-97814760, 20791169], [-99452190, 10452846], [-100000000, 0], [-99452190, -10452846],
160 [-97814760, -20791169], [-95105652, -30901699], [-91354546, -40673664], [-86602540, -50000000],
161 [-80901699, -58778525], [-74314483, -66913061], [-66913061, -74314483], [-58778525, -80901699],
162 [-50000000, -86602540], [-40673664, -91354546], [-30901699, -95105652], [-20791169, -97814760],
163 [-10452846, -99452190], [0, -100000000], [10452846, -99452190], [20791169, -97814760],
164 [30901699, -95105652], [40673664, -91354546], [50000000, -86602540], [58778525, -80901699],
165 [66913061, -74314483], [74314483, -66913061], [80901699, -58778525], [86602540, -50000000],
166 [91354546, -40673664], [95105652, -30901699], [97814760, -20791169], [99452190, -10452846], [100000000, 0]
167 );
168 my $result = Slic3r::Geometry::Clipper::intersection_pl($subject, [$clip]);
169 is scalar(@$result), scalar(@$subject), 'intersection_pl - expected number of polylines';
170 is sum(map scalar(@$_), @$result), scalar(@$subject) * 2, 'intersection_pl - expected number of points in polylines';
171 }
172 #endif
173 }
174
175 SCENARIO("Various Clipper operations - t/clipper.t", "[ClipperUtils]") {
176 GIVEN("square with hole") {
177 // CCW oriented contour
178 Slic3r::Polygon square { { 10, 10 }, { 20, 10 }, { 20, 20 }, { 10, 20 } };
179 Slic3r::Polygon square2 { { 5, 12 }, { 25, 12 }, { 25, 18 }, { 5, 18 } };
180 // CW oriented contour
181 Slic3r::Polygon hole_in_square { { 14, 14 }, { 14, 16 }, { 16, 16 }, { 16, 14 } };
182 WHEN("intersection_ex with another square") {
183 ExPolygons intersection = Slic3r::intersection_ex({ square, hole_in_square }, { square2 });
184 THEN("intersection area matches (hole is preserved)") {
185 ExPolygon match({ { 20, 18 }, { 10, 18 }, { 10, 12 }, { 20, 12 } },
186 { { 14, 16 }, { 16, 16 }, { 16, 14 }, { 14, 14 } });
187 REQUIRE(intersection.size() == 1);
188 REQUIRE(intersection.front().area() == Approx(match.area()));
189 }
190 }
191 }
192 GIVEN("square with hole 2") {
193 // CCW oriented contour
194 Slic3r::Polygon square { { 0, 0 }, { 40, 0 }, { 40, 40 }, { 0, 40 } };
195 Slic3r::Polygon square2 { { 10, 10 }, { 30, 10 }, { 30, 30 }, { 10, 30 } };
196 // CW oriented contour
197 Slic3r::Polygon hole { { 15, 15 }, { 15, 25 }, { 25, 25 }, {25, 15 } };
198 WHEN("union_ex with another square") {
199 ExPolygons union_ = Slic3r::union_ex({ square, square2, hole });
200 THEN("union of two ccw and one cw is a contour with no holes") {
201 REQUIRE(union_.size() == 1);
202 REQUIRE(union_.front() == ExPolygon { { 40, 40 }, { 0, 40 }, { 0, 0 }, { 40, 0 } } );
203 }
204 }
205 WHEN("diff_ex with another square") {
206 ExPolygons diff = Slic3r::diff_ex({ square, square2 }, { hole });
207 THEN("difference of a cw from two ccw is a contour with one hole") {
208 REQUIRE(diff.size() == 1);
209 REQUIRE(diff.front().area() == Approx(ExPolygon({ {40, 40}, {0, 40}, {0, 0}, {40, 0} }, { {15, 25}, {25, 25}, {25, 15}, {15, 15} }).area()));
210 }
211 }
212 }
213 GIVEN("yet another square") {
214 Slic3r::Polygon square { { 10, 10 }, { 20, 10 }, { 20, 20 }, { 10, 20 } };
215 Slic3r::Polyline square_pl = square.split_at_first_point();
216 WHEN("no-op diff_pl") {
217 Slic3r::Polylines res = Slic3r::diff_pl({ square_pl }, {});
218 THEN("returns the right number of polylines") {
219 REQUIRE(res.size() == 1);
220 }
221 THEN("returns the unmodified input polyline") {
222 REQUIRE(res.front().points.size() == square_pl.points.size());
223 }
224 }
225 }
226 }
227
228 template<e_ordering o = e_ordering::OFF, class P, class Tree>
polytree_area(const Tree & tree,std::vector<P> * out)229 double polytree_area(const Tree &tree, std::vector<P> *out)
230 {
231 traverse_pt<o>(tree, out);
232
233 return std::accumulate(out->begin(), out->end(), 0.0,
234 [](double a, const P &p) { return a + p.area(); });
235 }
236
count_polys(const ExPolygons & expolys)237 size_t count_polys(const ExPolygons& expolys)
238 {
239 size_t c = 0;
240 for (auto &ep : expolys) c += ep.holes.size() + 1;
241
242 return c;
243 }
244
245 TEST_CASE("Traversing Clipper PolyTree", "[ClipperUtils]") {
246 // Create a polygon representing unit box
247 Polygon unitbox;
248 const auto UNIT = coord_t(1. / SCALING_FACTOR);
249 unitbox.points = { Vec2crd{0, 0}, Vec2crd{UNIT, 0}, Vec2crd{UNIT, UNIT}, Vec2crd{0, UNIT}};
250
251 Polygon box_frame = unitbox;
252 box_frame.scale(20, 10);
253
254 Polygon hole_left = unitbox;
255 hole_left.scale(8);
256 hole_left.translate(UNIT, UNIT);
257 hole_left.reverse();
258
259 Polygon hole_right = hole_left;
260 hole_right.translate(UNIT * 10, 0);
261
262 Polygon inner_left = unitbox;
263 inner_left.scale(4);
264 inner_left.translate(UNIT * 3, UNIT * 3);
265
266 Polygon inner_right = inner_left;
267 inner_right.translate(UNIT * 10, 0);
268
269 Polygons reference = union_({box_frame, hole_left, hole_right, inner_left, inner_right});
270
271 ClipperLib::PolyTree tree = union_pt(reference);
272 double area_sum = box_frame.area() + hole_left.area() +
273 hole_right.area() + inner_left.area() +
274 inner_right.area();
275
276 REQUIRE(area_sum > 0);
277
278 SECTION("Traverse into Polygons WITHOUT spatial ordering") {
279 Polygons output;
280 REQUIRE(area_sum == Approx(polytree_area(tree.GetFirst(), &output)));
281 REQUIRE(output.size() == reference.size());
282 }
283
284 SECTION("Traverse into ExPolygons WITHOUT spatial ordering") {
285 ExPolygons output;
286 REQUIRE(area_sum == Approx(polytree_area(tree.GetFirst(), &output)));
287 REQUIRE(count_polys(output) == reference.size());
288 }
289
290 SECTION("Traverse into Polygons WITH spatial ordering") {
291 Polygons output;
292 REQUIRE(area_sum == Approx(polytree_area<e_ordering::ON>(tree.GetFirst(), &output)));
293 REQUIRE(output.size() == reference.size());
294 }
295
296 SECTION("Traverse into ExPolygons WITH spatial ordering") {
297 ExPolygons output;
298 REQUIRE(area_sum == Approx(polytree_area<e_ordering::ON>(tree.GetFirst(), &output)));
299 REQUIRE(count_polys(output) == reference.size());
300 }
301 }
302