1 /*
2 * Copyright 2011 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "include/core/SkContourMeasure.h"
9 #include "include/core/SkPath.h"
10 #include "include/core/SkPathMeasure.h"
11 #include "include/core/SkPathTypes.h"
12 #include "include/core/SkPoint.h"
13 #include "include/core/SkRefCnt.h"
14 #include "include/core/SkScalar.h"
15 #include "include/core/SkTypes.h"
16 #include "src/core/SkPathMeasurePriv.h"
17 #include "src/core/SkPathPriv.h"
18 #include "tests/Test.h"
19
20 #include <array>
21 #include <cstddef>
22 #include <initializer_list>
23 #include <utility>
24
test_small_segment3(skiatest::Reporter * reporter)25 static void test_small_segment3(skiatest::Reporter* reporter) {
26 SkPath path;
27 const SkPoint pts[] = {
28 { 0, 0 },
29 { 100000000000.0f, 100000000000.0f }, { 0, 0 }, { 10, 10 },
30 { 10, 10 }, { 0, 0 }, { 10, 10 }
31 };
32
33 path.moveTo(pts[0]);
34 for (size_t i = 1; i < std::size(pts); i += 3) {
35 path.cubicTo(pts[i], pts[i + 1], pts[i + 2]);
36 }
37
38 SkPathMeasure meas(path, false);
39 meas.getLength();
40
41 // Now check that we cap the segment size even with very large resolution scales.
42 // Earlier versions allowed the pathmeasure to recurse without limit in the face
43 // of a very large scale.
44 //
45 // Before this limit, the above meas had 15K segments, and when built with
46 // a resScale of 100, it had 184K segments -- for 1 cubic!
47 {
48 auto n = SkPathMeasurePriv::CountSegments(meas);
49 REPORTER_ASSERT(reporter, n < 300);
50
51 constexpr float resScale = 1000;
52 n = SkPathMeasurePriv::CountSegments(SkPathMeasure(path, false, resScale));
53 REPORTER_ASSERT(reporter, n < 300);
54 }
55 }
56
test_small_segment2()57 static void test_small_segment2() {
58 SkPath path;
59 const SkPoint pts[] = {
60 { 0, 0 },
61 { 100000000000.0f, 100000000000.0f }, { 0, 0 },
62 { 10, 10 }, { 0, 0 },
63 };
64
65 path.moveTo(pts[0]);
66 for (size_t i = 1; i < std::size(pts); i += 2) {
67 path.quadTo(pts[i], pts[i + 1]);
68 }
69 SkPathMeasure meas(path, false);
70 meas.getLength();
71 }
72
test_small_segment()73 static void test_small_segment() {
74 SkPath path;
75 const SkPoint pts[] = {
76 { 100000, 100000},
77 // big jump between these points, makes a big segment
78 { 1.0005f, 0.9999f },
79 // tiny (non-zero) jump between these points
80 { SK_Scalar1, SK_Scalar1 },
81 };
82
83 path.moveTo(pts[0]);
84 for (size_t i = 1; i < std::size(pts); ++i) {
85 path.lineTo(pts[i]);
86 }
87 SkPathMeasure meas(path, false);
88
89 /* this would assert (before a fix) because we added a segment with
90 the same length as the prev segment, due to the follow (bad) pattern
91
92 d = distance(pts[0], pts[1]);
93 distance += d;
94 seg->fDistance = distance;
95
96 SkASSERT(d > 0); // TRUE
97 SkASSERT(seg->fDistance > prevSeg->fDistance); // FALSE
98
99 This 2nd assert failes because (distance += d) didn't affect distance
100 because distance >>> d.
101 */
102 meas.getLength();
103 }
104
DEF_TEST(PathMeasure,reporter)105 DEF_TEST(PathMeasure, reporter) {
106 SkPath path;
107
108 path.moveTo(0, 0);
109 path.lineTo(SK_Scalar1, 0);
110 path.lineTo(SK_Scalar1, SK_Scalar1);
111 path.lineTo(0, SK_Scalar1);
112
113 SkPathMeasure meas(path, true);
114 SkScalar length = meas.getLength();
115 SkASSERT(length == SK_Scalar1*4);
116
117 path.reset();
118 path.moveTo(0, 0);
119 path.lineTo(SK_Scalar1*3, SK_Scalar1*4);
120 meas.setPath(&path, false);
121 length = meas.getLength();
122 REPORTER_ASSERT(reporter, length == SK_Scalar1*5);
123
124 path.reset();
125 path.addCircle(0, 0, SK_Scalar1);
126 meas.setPath(&path, true);
127 length = meas.getLength();
128 // SkDebugf("circle arc-length = %g\n", length);
129
130 // Test the behavior following a close not followed by a move.
131 path.reset();
132 path.lineTo(SK_Scalar1, 0);
133 path.lineTo(SK_Scalar1, SK_Scalar1);
134 path.lineTo(0, SK_Scalar1);
135 path.close();
136 path.lineTo(-SK_Scalar1, 0);
137 meas.setPath(&path, false);
138 length = meas.getLength();
139 REPORTER_ASSERT(reporter, length == SK_Scalar1 * 4);
140 meas.nextContour();
141 length = meas.getLength();
142 REPORTER_ASSERT(reporter, length == SK_Scalar1);
143 SkPoint position;
144 SkVector tangent;
145 REPORTER_ASSERT(reporter, meas.getPosTan(SK_ScalarHalf, &position, &tangent));
146 REPORTER_ASSERT(reporter,
147 SkScalarNearlyEqual(position.fX,
148 -SK_ScalarHalf,
149 0.0001f));
150 REPORTER_ASSERT(reporter, position.fY == 0);
151 REPORTER_ASSERT(reporter, tangent.fX == -SK_Scalar1);
152 REPORTER_ASSERT(reporter, tangent.fY == 0);
153
154 // Test degenerate paths
155 path.reset();
156 path.moveTo(0, 0);
157 path.lineTo(0, 0);
158 path.lineTo(SK_Scalar1, 0);
159 path.quadTo(SK_Scalar1, 0, SK_Scalar1, 0);
160 path.quadTo(SK_Scalar1, SK_Scalar1, SK_Scalar1, SK_Scalar1 * 2);
161 path.cubicTo(SK_Scalar1, SK_Scalar1 * 2,
162 SK_Scalar1, SK_Scalar1 * 2,
163 SK_Scalar1, SK_Scalar1 * 2);
164 path.cubicTo(SK_Scalar1*2, SK_Scalar1 * 2,
165 SK_Scalar1*3, SK_Scalar1 * 2,
166 SK_Scalar1*4, SK_Scalar1 * 2);
167 meas.setPath(&path, false);
168 length = meas.getLength();
169 REPORTER_ASSERT(reporter, length == SK_Scalar1 * 6);
170 REPORTER_ASSERT(reporter, meas.getPosTan(SK_ScalarHalf, &position, &tangent));
171 REPORTER_ASSERT(reporter,
172 SkScalarNearlyEqual(position.fX,
173 SK_ScalarHalf,
174 0.0001f));
175 REPORTER_ASSERT(reporter, position.fY == 0);
176 REPORTER_ASSERT(reporter, tangent.fX == SK_Scalar1);
177 REPORTER_ASSERT(reporter, tangent.fY == 0);
178 REPORTER_ASSERT(reporter, meas.getPosTan(2.5f, &position, &tangent));
179 REPORTER_ASSERT(reporter,
180 SkScalarNearlyEqual(position.fX, SK_Scalar1, 0.0001f));
181 REPORTER_ASSERT(reporter,
182 SkScalarNearlyEqual(position.fY, 1.5f));
183 REPORTER_ASSERT(reporter, tangent.fX == 0);
184 REPORTER_ASSERT(reporter, tangent.fY == SK_Scalar1);
185 REPORTER_ASSERT(reporter, meas.getPosTan(4.5f, &position, &tangent));
186 REPORTER_ASSERT(reporter,
187 SkScalarNearlyEqual(position.fX,
188 2.5f,
189 0.0001f));
190 REPORTER_ASSERT(reporter,
191 SkScalarNearlyEqual(position.fY,
192 2.0f,
193 0.0001f));
194 REPORTER_ASSERT(reporter, tangent.fX == SK_Scalar1);
195 REPORTER_ASSERT(reporter, tangent.fY == 0);
196
197 path.reset();
198 path.moveTo(0, 0);
199 path.lineTo(SK_Scalar1, 0);
200 path.moveTo(SK_Scalar1, SK_Scalar1);
201 path.moveTo(SK_Scalar1 * 2, SK_Scalar1 * 2);
202 path.lineTo(SK_Scalar1, SK_Scalar1 * 2);
203 meas.setPath(&path, false);
204 length = meas.getLength();
205 REPORTER_ASSERT(reporter, length == SK_Scalar1);
206 REPORTER_ASSERT(reporter, meas.getPosTan(SK_ScalarHalf, &position, &tangent));
207 REPORTER_ASSERT(reporter,
208 SkScalarNearlyEqual(position.fX,
209 SK_ScalarHalf,
210 0.0001f));
211 REPORTER_ASSERT(reporter, position.fY == 0);
212 REPORTER_ASSERT(reporter, tangent.fX == SK_Scalar1);
213 REPORTER_ASSERT(reporter, tangent.fY == 0);
214 meas.nextContour();
215 length = meas.getLength();
216 REPORTER_ASSERT(reporter, length == SK_Scalar1);
217 REPORTER_ASSERT(reporter, meas.getPosTan(SK_ScalarHalf, &position, &tangent));
218 REPORTER_ASSERT(reporter,
219 SkScalarNearlyEqual(position.fX,
220 1.5f,
221 0.0001f));
222 REPORTER_ASSERT(reporter,
223 SkScalarNearlyEqual(position.fY,
224 2.0f,
225 0.0001f));
226 REPORTER_ASSERT(reporter, tangent.fX == -SK_Scalar1);
227 REPORTER_ASSERT(reporter, tangent.fY == 0);
228
229 test_small_segment();
230 test_small_segment2();
231 test_small_segment3(reporter);
232
233 // SkPathMeasure isn't copyable, but it should be move-able
234 SkPathMeasure meas2(std::move(meas));
235 meas = std::move(meas2);
236 }
237
DEF_TEST(PathMeasureConic,reporter)238 DEF_TEST(PathMeasureConic, reporter) {
239 SkPoint stdP, hiP, pts[] = {{0,0}, {100,0}, {100,0}};
240 SkPath p;
241 p.moveTo(0, 0);
242 p.conicTo(pts[1], pts[2], 1);
243 SkPathMeasure stdm(p, false);
244 REPORTER_ASSERT(reporter, stdm.getPosTan(20, &stdP, nullptr));
245 p.reset();
246 p.moveTo(0, 0);
247 p.conicTo(pts[1], pts[2], 10);
248 stdm.setPath(&p, false);
249 REPORTER_ASSERT(reporter, stdm.getPosTan(20, &hiP, nullptr));
250 REPORTER_ASSERT(reporter, 19.5f < stdP.fX && stdP.fX < 20.5f);
251 REPORTER_ASSERT(reporter, 19.5f < hiP.fX && hiP.fX < 20.5f);
252 }
253
254 // Regression test for b/26425223
DEF_TEST(PathMeasure_nextctr,reporter)255 DEF_TEST(PathMeasure_nextctr, reporter) {
256 SkPath path;
257 path.moveTo(0, 0); path.lineTo(100, 0);
258
259 SkPathMeasure meas(path, false);
260 // only expect 1 contour, even if we didn't explicitly call getLength() ourselves
261 REPORTER_ASSERT(reporter, !meas.nextContour());
262 }
263
test_90_degrees(const sk_sp<SkContourMeasure> & cm,SkScalar radius,skiatest::Reporter * reporter)264 static void test_90_degrees(const sk_sp<SkContourMeasure>& cm, SkScalar radius,
265 skiatest::Reporter* reporter) {
266 SkPoint pos;
267 SkVector tan;
268 SkScalar distance = cm->length() / 4;
269 bool success = cm->getPosTan(distance, &pos, &tan);
270
271 REPORTER_ASSERT(reporter, success);
272 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(pos.fX, 0));
273 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(pos.fY, radius));
274 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(tan.fX, -1));
275 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(tan.fY, 0));
276 }
277
test_empty_contours(skiatest::Reporter * reporter)278 static void test_empty_contours(skiatest::Reporter* reporter) {
279 SkPath path;
280
281 path.moveTo(0, 0).lineTo(100, 100).lineTo(200, 100);
282 path.moveTo(2, 2).moveTo(3, 3); // zero-length(s)
283 path.moveTo(4, 4).close().close().close(); // zero-length
284 path.moveTo(5, 5).lineTo(5, 5); // zero-length
285 path.moveTo(5, 5).lineTo(5, 5).close(); // zero-length
286 path.moveTo(5, 5).lineTo(5, 5).close().close(); // zero-length
287 path.moveTo(6, 6).lineTo(7, 7);
288 path.moveTo(10, 10); // zero-length
289
290 SkContourMeasureIter fact(path, false);
291
292 // given the above construction, we expect only 2 contours (the rest are "empty")
293
294 REPORTER_ASSERT(reporter, fact.next());
295 REPORTER_ASSERT(reporter, fact.next());
296 REPORTER_ASSERT(reporter, !fact.next());
297 }
298
test_MLM_contours(skiatest::Reporter * reporter)299 static void test_MLM_contours(skiatest::Reporter* reporter) {
300 SkPath path;
301
302 // This odd sequence (with a trailing moveTo) used to return a 2nd contour, which is
303 // wrong, since the contract for a measure is to only return non-zero length contours.
304 path.moveTo(10, 10).lineTo(20, 20).moveTo(30, 30);
305
306 for (bool forceClosed : {false, true}) {
307 SkContourMeasureIter fact(path, forceClosed);
308 REPORTER_ASSERT(reporter, fact.next());
309 REPORTER_ASSERT(reporter, !fact.next());
310 }
311 }
312
test_shrink(skiatest::Reporter * reporter)313 static void test_shrink(skiatest::Reporter* reporter) {
314 SkPath path;
315 path.addRect({1, 2, 3, 4});
316 path.incReserve(100); // give shrinkToFit() something to do
317
318 SkContourMeasureIter iter(path, false);
319
320 // shrinks the allocation, possibly relocating the underlying arrays.
321 // The contouremasureiter needs to have safely copied path, to be unaffected by this
322 // change to "path".
323 SkPathPriv::ShrinkToFit(&path);
324
325 // Note, this failed (before the fix) on an ASAN build, which notices that we were
326 // using an internal iterator of the passed-in path, not our copy.
327 while (iter.next())
328 ;
329 }
330
DEF_TEST(contour_measure,reporter)331 DEF_TEST(contour_measure, reporter) {
332 SkPath path;
333 path.addCircle(0, 0, 100);
334 path.addCircle(0, 0, 10);
335
336 SkContourMeasureIter fact(path, false);
337 path.reset(); // we should not need the path avert we created the factory
338
339 auto cm0 = fact.next();
340 auto cm1 = fact.next();
341
342 REPORTER_ASSERT(reporter, cm0->isClosed());
343 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(cm0->length(), 200 * SK_ScalarPI, 1.5f));
344
345 test_90_degrees(cm0, 100, reporter);
346
347 REPORTER_ASSERT(reporter, cm1->isClosed());
348 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(cm1->length(), 20 * SK_ScalarPI, 0.5f));
349
350 test_90_degrees(cm1, 10, reporter);
351
352 auto cm2 = fact.next();
353 REPORTER_ASSERT(reporter, !cm2);
354
355 test_empty_contours(reporter);
356 test_MLM_contours(reporter);
357
358 test_shrink(reporter);
359 }
360
DEF_TEST(contour_measure_verbs,reporter)361 DEF_TEST(contour_measure_verbs, reporter) {
362 SkPath path;
363 path.moveTo(10, 10);
364 path.lineTo(10, 30);
365 path.lineTo(30, 30);
366 path.quadTo({40, 30}, {40, 40});
367 path.cubicTo({50, 40}, {50, 50}, {40, 50});
368 path.conicTo({50, 50}, {50, 60}, 1.2f);
369
370 SkContourMeasureIter measure(path, false);
371
372 sk_sp<SkContourMeasure> cmeasure = measure.next();
373 REPORTER_ASSERT(reporter, cmeasure);
374
375 SkContourMeasure::ForwardVerbIterator viter = cmeasure->begin();
376 {
377 REPORTER_ASSERT(reporter, viter != cmeasure->end());
378 const auto vmeasure = *viter;
379 REPORTER_ASSERT(reporter, vmeasure.fVerb == SkPathVerb::kLine);
380 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(vmeasure.fDistance, 20));
381 REPORTER_ASSERT(reporter, vmeasure.fPts.size() == 2);
382 REPORTER_ASSERT(reporter, vmeasure.fPts[0] == SkPoint::Make(10, 10));
383 REPORTER_ASSERT(reporter, vmeasure.fPts[1] == SkPoint::Make(10, 30));
384 }
385
386 ++viter;
387 {
388 REPORTER_ASSERT(reporter, viter != cmeasure->end());
389 const auto vmeasure = *viter;
390 REPORTER_ASSERT(reporter, vmeasure.fVerb == SkPathVerb::kLine);
391 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(vmeasure.fDistance, 40));
392 REPORTER_ASSERT(reporter, vmeasure.fPts.size() == 2);
393 REPORTER_ASSERT(reporter, vmeasure.fPts[0] == SkPoint::Make(10, 30));
394 REPORTER_ASSERT(reporter, vmeasure.fPts[1] == SkPoint::Make(30, 30));
395 }
396
397 ++viter;
398 {
399 REPORTER_ASSERT(reporter, viter != cmeasure->end());
400 const auto vmeasure = *viter;
401 REPORTER_ASSERT(reporter, vmeasure.fVerb == SkPathVerb::kQuad);
402 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(vmeasure.fDistance, 56.127525f));
403 REPORTER_ASSERT(reporter, vmeasure.fPts.size() == 3);
404 REPORTER_ASSERT(reporter, vmeasure.fPts[0] == SkPoint::Make(30, 30));
405 REPORTER_ASSERT(reporter, vmeasure.fPts[1] == SkPoint::Make(40, 30));
406 REPORTER_ASSERT(reporter, vmeasure.fPts[2] == SkPoint::Make(40, 40));
407 }
408
409 ++viter;
410 {
411 REPORTER_ASSERT(reporter, viter != cmeasure->end());
412 const auto vmeasure = *viter;
413 REPORTER_ASSERT(reporter, vmeasure.fVerb == SkPathVerb::kCubic);
414 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(vmeasure.fDistance, 76.004692f));
415 REPORTER_ASSERT(reporter, vmeasure.fPts.size() == 4);
416 REPORTER_ASSERT(reporter, vmeasure.fPts[0] == SkPoint::Make(40, 40));
417 REPORTER_ASSERT(reporter, vmeasure.fPts[1] == SkPoint::Make(50, 40));
418 REPORTER_ASSERT(reporter, vmeasure.fPts[2] == SkPoint::Make(50, 50));
419 REPORTER_ASSERT(reporter, vmeasure.fPts[3] == SkPoint::Make(40, 50));
420 }
421
422 ++viter;
423 {
424 REPORTER_ASSERT(reporter, viter != cmeasure->end());
425 const auto vmeasure = *viter;
426 REPORTER_ASSERT(reporter, vmeasure.fVerb == SkPathVerb::kConic);
427 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(vmeasure.fDistance, 92.428185f));
428 REPORTER_ASSERT(reporter, vmeasure.fPts.size() == 4);
429 REPORTER_ASSERT(reporter, vmeasure.fPts[0] == SkPoint::Make(40, 50));
430 REPORTER_ASSERT(reporter, vmeasure.fPts[1] == SkPoint::Make(1.2f, 0));
431 REPORTER_ASSERT(reporter, vmeasure.fPts[2] == SkPoint::Make(50, 50));
432 REPORTER_ASSERT(reporter, vmeasure.fPts[3] == SkPoint::Make(50, 60));
433
434 // The last verb distance should also match the contour length.
435 REPORTER_ASSERT(reporter, SkScalarNearlyEqual(vmeasure.fDistance, cmeasure->length()));
436 }
437
438 ++viter;
439 {
440 REPORTER_ASSERT(reporter, viter == cmeasure->end());
441 }
442
443 // Exercise the range iterator form.
444 float current_distance = 0;
445 size_t verb_count = 0;
446 for (const auto vmeasure : *cmeasure) {
447 REPORTER_ASSERT(reporter, vmeasure.fDistance > current_distance);
448 current_distance = vmeasure.fDistance;
449 verb_count++;
450 }
451 REPORTER_ASSERT(reporter, verb_count == 5);
452 }
453