1/*
2 * Copyright 2018 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 "src/core/SkGeometry.h"
11#include "src/core/SkPathMeasurePriv.h"
12#include "src/core/SkTSearch.h"
13
14#define kMaxTValue 0x3FFFFFFF
15
16constexpr static inline SkScalar tValue2Scalar(int t) {
17 SkASSERT((unsigned)t <= kMaxTValue);
18 // 1/kMaxTValue can't be represented as a float, but it's close and the limits work fine.
19 const SkScalar kMaxTReciprocal = 1.0f / (SkScalar)kMaxTValue;
20 return t * kMaxTReciprocal;
21}
22
23static_assert(0.0f == tValue2Scalar( 0), "Lower limit should be exact.");
24static_assert(1.0f == tValue2Scalar(kMaxTValue), "Upper limit should be exact.");
25
26SkScalar SkContourMeasure::Segment::getScalarT() const {
27 return tValue2Scalar(fTValue);
28}
29
30void SkContourMeasure_segTo(const SkPoint pts[], unsigned segType,
31 SkScalar startT, SkScalar stopT, SkPath* dst) {
32 SkASSERT(startT >= 0 && startT <= SK_Scalar1);
33 SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
34 SkASSERT(startT <= stopT);
35
36 if (startT == stopT) {
37 if (!dst->isEmpty()) {
38 /* if the dash as a zero-length on segment, add a corresponding zero-length line.
39 The stroke code will add end caps to zero length lines as appropriate */
40 SkPoint lastPt;
41 SkAssertResult(dst->getLastPt(&lastPt));
42 dst->lineTo(lastPt);
43 }
44 return;
45 }
46
47 SkPoint tmp0[7], tmp1[7];
48
49 switch (segType) {
50 case kLine_SegType:
51 if (SK_Scalar1 == stopT) {
52 dst->lineTo(pts[1]);
53 } else {
54 dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT),
55 SkScalarInterp(pts[0].fY, pts[1].fY, stopT));
56 }
57 break;
58 case kQuad_SegType:
59 if (0 == startT) {
60 if (SK_Scalar1 == stopT) {
61 dst->quadTo(pts[1], pts[2]);
62 } else {
63 SkChopQuadAt(pts, tmp0, stopT);
64 dst->quadTo(tmp0[1], tmp0[2]);
65 }
66 } else {
67 SkChopQuadAt(pts, tmp0, startT);
68 if (SK_Scalar1 == stopT) {
69 dst->quadTo(tmp0[3], tmp0[4]);
70 } else {
71 SkChopQuadAt(&tmp0[2], tmp1, (stopT - startT) / (1 - startT));
72 dst->quadTo(tmp1[1], tmp1[2]);
73 }
74 }
75 break;
76 case kConic_SegType: {
77 SkConic conic(pts[0], pts[2], pts[3], pts[1].fX);
78
79 if (0 == startT) {
80 if (SK_Scalar1 == stopT) {
81 dst->conicTo(conic.fPts[1], conic.fPts[2], conic.fW);
82 } else {
83 SkConic tmp[2];
84 if (conic.chopAt(stopT, tmp)) {
85 dst->conicTo(tmp[0].fPts[1], tmp[0].fPts[2], tmp[0].fW);
86 }
87 }
88 } else {
89 if (SK_Scalar1 == stopT) {
90 SkConic tmp1[2];
91 if (conic.chopAt(startT, tmp1)) {
92 dst->conicTo(tmp1[1].fPts[1], tmp1[1].fPts[2], tmp1[1].fW);
93 }
94 } else {
95 SkConic tmp;
96 conic.chopAt(startT, stopT, &tmp);
97 dst->conicTo(tmp.fPts[1], tmp.fPts[2], tmp.fW);
98 }
99 }
100 } break;
101 case kCubic_SegType:
102 if (0 == startT) {
103 if (SK_Scalar1 == stopT) {
104 dst->cubicTo(pts[1], pts[2], pts[3]);
105 } else {
106 SkChopCubicAt(pts, tmp0, stopT);
107 dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
108 }
109 } else {
110 SkChopCubicAt(pts, tmp0, startT);
111 if (SK_Scalar1 == stopT) {
112 dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
113 } else {
114 SkChopCubicAt(&tmp0[3], tmp1, (stopT - startT) / (1 - startT));
115 dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
116 }
117 }
118 break;
119 default:
120 SK_ABORT("unknown segType");
121 }
122}
123
124///////////////////////////////////////////////////////////////////////////////
125
126static inline int tspan_big_enough(int tspan) {
127 SkASSERT((unsigned)tspan <= kMaxTValue);
128 return tspan >> 10;
129}
130
131// can't use tangents, since we need [0..1..................2] to be seen
132// as definitely not a line (it is when drawn, but not parametrically)
133// so we compare midpoints
134#define CHEAP_DIST_LIMIT (SK_Scalar1/2) // just made this value up
135
136static bool quad_too_curvy(const SkPoint pts[3], SkScalar tolerance) {
137 // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
138 // diff = -a/4 + b/2 - c/4
139 SkScalar dx = SkScalarHalf(pts[1].fX) -
140 SkScalarHalf(SkScalarHalf(pts[0].fX + pts[2].fX));
141 SkScalar dy = SkScalarHalf(pts[1].fY) -
142 SkScalarHalf(SkScalarHalf(pts[0].fY + pts[2].fY));
143
144 SkScalar dist = std::max(SkScalarAbs(dx), SkScalarAbs(dy));
145 return dist > tolerance;
146}
147
148static bool conic_too_curvy(const SkPoint& firstPt, const SkPoint& midTPt,
149 const SkPoint& lastPt, SkScalar tolerance) {
150 SkPoint midEnds = firstPt + lastPt;
151 midEnds *= 0.5f;
152 SkVector dxy = midTPt - midEnds;
153 SkScalar dist = std::max(SkScalarAbs(dxy.fX), SkScalarAbs(dxy.fY));
154 return dist > tolerance;
155}
156
157static bool cheap_dist_exceeds_limit(const SkPoint& pt, SkScalar x, SkScalar y,
158 SkScalar tolerance) {
159 SkScalar dist = std::max(SkScalarAbs(x - pt.fX), SkScalarAbs(y - pt.fY));
160 // just made up the 1/2
161 return dist > tolerance;
162}
163
164static bool cubic_too_curvy(const SkPoint pts[4], SkScalar tolerance) {
165 return cheap_dist_exceeds_limit(pts[1],
166 SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1/3),
167 SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1/3), tolerance)
168 ||
169 cheap_dist_exceeds_limit(pts[2],
170 SkScalarInterp(pts[0].fX, pts[3].fX, SK_Scalar1*2/3),
171 SkScalarInterp(pts[0].fY, pts[3].fY, SK_Scalar1*2/3), tolerance);
172}
173
174SkScalar SkContourMeasureIter::compute_quad_segs(const SkPoint pts[3], SkScalar distance,
175 int mint, int maxt, unsigned ptIndex) {
176 if (tspan_big_enough(maxt - mint) && quad_too_curvy(pts, fTolerance)) {
177 SkPoint tmp[5];
178 int halft = (mint + maxt) >> 1;
179
180 SkChopQuadAtHalf(pts, tmp);
181 distance = this->compute_quad_segs(tmp, distance, mint, halft, ptIndex);
182 distance = this->compute_quad_segs(&tmp[2], distance, halft, maxt, ptIndex);
183 } else {
184 SkScalar d = SkPoint::Distance(pts[0], pts[2]);
185 SkScalar prevD = distance;
186 distance += d;
187 if (distance > prevD) {
188 SkASSERT(ptIndex < (unsigned)fPts.count());
189 SkContourMeasure::Segment* seg = fSegments.append();
190 seg->fDistance = distance;
191 seg->fPtIndex = ptIndex;
192 seg->fType = kQuad_SegType;
193 seg->fTValue = maxt;
194 }
195 }
196 return distance;
197}
198
199SkScalar SkContourMeasureIter::compute_conic_segs(const SkConic& conic, SkScalar distance,
200 int mint, const SkPoint& minPt,
201 int maxt, const SkPoint& maxPt,
202 unsigned ptIndex) {
203 int halft = (mint + maxt) >> 1;
204 SkPoint halfPt = conic.evalAt(tValue2Scalar(halft));
205 if (!halfPt.isFinite()) {
206 return distance;
207 }
208 if (tspan_big_enough(maxt - mint) && conic_too_curvy(minPt, halfPt, maxPt, fTolerance)) {
209 distance = this->compute_conic_segs(conic, distance, mint, minPt, halft, halfPt, ptIndex);
210 distance = this->compute_conic_segs(conic, distance, halft, halfPt, maxt, maxPt, ptIndex);
211 } else {
212 SkScalar d = SkPoint::Distance(minPt, maxPt);
213 SkScalar prevD = distance;
214 distance += d;
215 if (distance > prevD) {
216 SkASSERT(ptIndex < (unsigned)fPts.count());
217 SkContourMeasure::Segment* seg = fSegments.append();
218 seg->fDistance = distance;
219 seg->fPtIndex = ptIndex;
220 seg->fType = kConic_SegType;
221 seg->fTValue = maxt;
222 }
223 }
224 return distance;
225}
226
227SkScalar SkContourMeasureIter::compute_cubic_segs(const SkPoint pts[4], SkScalar distance,
228 int mint, int maxt, unsigned ptIndex) {
229 if (tspan_big_enough(maxt - mint) && cubic_too_curvy(pts, fTolerance)) {
230 SkPoint tmp[7];
231 int halft = (mint + maxt) >> 1;
232
233 SkChopCubicAtHalf(pts, tmp);
234 distance = this->compute_cubic_segs(tmp, distance, mint, halft, ptIndex);
235 distance = this->compute_cubic_segs(&tmp[3], distance, halft, maxt, ptIndex);
236 } else {
237 SkScalar d = SkPoint::Distance(pts[0], pts[3]);
238 SkScalar prevD = distance;
239 distance += d;
240 if (distance > prevD) {
241 SkASSERT(ptIndex < (unsigned)fPts.count());
242 SkContourMeasure::Segment* seg = fSegments.append();
243 seg->fDistance = distance;
244 seg->fPtIndex = ptIndex;
245 seg->fType = kCubic_SegType;
246 seg->fTValue = maxt;
247 }
248 }
249 return distance;
250}
251
252SkScalar SkContourMeasureIter::compute_line_seg(SkPoint p0, SkPoint p1, SkScalar distance,
253 unsigned ptIndex) {
254 SkScalar d = SkPoint::Distance(p0, p1);
255 SkASSERT(d >= 0);
256 SkScalar prevD = distance;
257 distance += d;
258 if (distance > prevD) {
259 SkASSERT((unsigned)ptIndex < (unsigned)fPts.count());
260 SkContourMeasure::Segment* seg = fSegments.append();
261 seg->fDistance = distance;
262 seg->fPtIndex = ptIndex;
263 seg->fType = kLine_SegType;
264 seg->fTValue = kMaxTValue;
265 }
266 return distance;
267}
268
269SkContourMeasure* SkContourMeasureIter::buildSegments() {
270 SkPoint pts[4];
271 int ptIndex = -1;
272 SkScalar distance = 0;
273 bool haveSeenClose = fForceClosed;
274 bool haveSeenMoveTo = false;
275
276 /* Note:
277 * as we accumulate distance, we have to check that the result of +=
278 * actually made it larger, since a very small delta might be > 0, but
279 * still have no effect on distance (if distance >>> delta).
280 *
281 * We do this check below, and in compute_quad_segs and compute_cubic_segs
282 */
283
284 fSegments.reset();
285 fPts.reset();
286
287 bool done = false;
288 do {
289 if (haveSeenMoveTo && fIter.peek() == SkPath::kMove_Verb) {
290 break;
291 }
292 switch (fIter.next(pts)) {
293 case SkPath::kMove_Verb:
294 ptIndex += 1;
295 fPts.append(1, pts);
296 SkASSERT(!haveSeenMoveTo);
297 haveSeenMoveTo = true;
298 break;
299
300 case SkPath::kLine_Verb: {
301 SkASSERT(haveSeenMoveTo);
302 SkScalar prevD = distance;
303 distance = this->compute_line_seg(pts[0], pts[1], distance, ptIndex);
304 if (distance > prevD) {
305 fPts.append(1, pts + 1);
306 ptIndex++;
307 }
308 } break;
309
310 case SkPath::kQuad_Verb: {
311 SkASSERT(haveSeenMoveTo);
312 SkScalar prevD = distance;
313 distance = this->compute_quad_segs(pts, distance, 0, kMaxTValue, ptIndex);
314 if (distance > prevD) {
315 fPts.append(2, pts + 1);
316 ptIndex += 2;
317 }
318 } break;
319
320 case SkPath::kConic_Verb: {
321 SkASSERT(haveSeenMoveTo);
322 const SkConic conic(pts, fIter.conicWeight());
323 SkScalar prevD = distance;
324 distance = this->compute_conic_segs(conic, distance, 0, conic.fPts[0],
325 kMaxTValue, conic.fPts[2], ptIndex);
326 if (distance > prevD) {
327 // we store the conic weight in our next point, followed by the last 2 pts
328 // thus to reconstitue a conic, you'd need to say
329 // SkConic(pts[0], pts[2], pts[3], weight = pts[1].fX)
330 fPts.append()->set(conic.fW, 0);
331 fPts.append(2, pts + 1);
332 ptIndex += 3;
333 }
334 } break;
335
336 case SkPath::kCubic_Verb: {
337 SkASSERT(haveSeenMoveTo);
338 SkScalar prevD = distance;
339 distance = this->compute_cubic_segs(pts, distance, 0, kMaxTValue, ptIndex);
340 if (distance > prevD) {
341 fPts.append(3, pts + 1);
342 ptIndex += 3;
343 }
344 } break;
345
346 case SkPath::kClose_Verb:
347 haveSeenClose = true;
348 break;
349
350 case SkPath::kDone_Verb:
351 done = true;
352 break;
353 }
354
355 } while (!done);
356
357 if (!SkScalarIsFinite(distance)) {
358 return nullptr;
359 }
360 if (fSegments.count() == 0) {
361 return nullptr;
362 }
363
364 // Handle the close segment ourselves, since we're using RawIter
365 if (haveSeenClose) {
366 SkScalar prevD = distance;
367 SkPoint firstPt = fPts[0];
368 distance = this->compute_line_seg(fPts[ptIndex], firstPt, distance, ptIndex);
369 if (distance > prevD) {
370 *fPts.append() = firstPt;
371 }
372 }
373
374#ifdef SK_DEBUG
375 {
376 const SkContourMeasure::Segment* seg = fSegments.begin();
377 const SkContourMeasure::Segment* stop = fSegments.end();
378 unsigned ptIndex = 0;
379 SkScalar distance = 0;
380 // limit the loop to a reasonable number; pathological cases can run for minutes
381 int maxChecks = 10000000; // set to INT_MAX to defeat the check
382 while (seg < stop) {
383 SkASSERT(seg->fDistance > distance);
384 SkASSERT(seg->fPtIndex >= ptIndex);
385 SkASSERT(seg->fTValue > 0);
386
387 const SkContourMeasure::Segment* s = seg;
388 while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex && --maxChecks > 0) {
389 SkASSERT(s[0].fType == s[1].fType);
390 SkASSERT(s[0].fTValue < s[1].fTValue);
391 s += 1;
392 }
393
394 distance = seg->fDistance;
395 ptIndex = seg->fPtIndex;
396 seg += 1;
397 }
398 // SkDebugf("\n");
399 }
400#endif
401
402 return new SkContourMeasure(std::move(fSegments), std::move(fPts), distance, haveSeenClose);
403}
404
405static void compute_pos_tan(const SkPoint pts[], unsigned segType,
406 SkScalar t, SkPoint* pos, SkVector* tangent) {
407 switch (segType) {
408 case kLine_SegType:
409 if (pos) {
410 pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t),
411 SkScalarInterp(pts[0].fY, pts[1].fY, t));
412 }
413 if (tangent) {
414 tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY);
415 }
416 break;
417 case kQuad_SegType:
418 SkEvalQuadAt(pts, t, pos, tangent);
419 if (tangent) {
420 tangent->normalize();
421 }
422 break;
423 case kConic_SegType: {
424 SkConic(pts[0], pts[2], pts[3], pts[1].fX).evalAt(t, pos, tangent);
425 if (tangent) {
426 tangent->normalize();
427 }
428 } break;
429 case kCubic_SegType:
430 SkEvalCubicAt(pts, t, pos, tangent, nullptr);
431 if (tangent) {
432 tangent->normalize();
433 }
434 break;
435 default:
436 SkDEBUGFAIL("unknown segType");
437 }
438}
439
440
441////////////////////////////////////////////////////////////////////////////////
442////////////////////////////////////////////////////////////////////////////////
443
444SkContourMeasureIter::SkContourMeasureIter() {
445 fTolerance = CHEAP_DIST_LIMIT;
446 fForceClosed = false;
447}
448
449SkContourMeasureIter::SkContourMeasureIter(const SkPath& path, bool forceClosed,
450 SkScalar resScale) {
451 fPath = path.isFinite() ? path : SkPath();
452 fTolerance = CHEAP_DIST_LIMIT * SkScalarInvert(resScale);
453 fForceClosed = forceClosed;
454
455 fIter.setPath(fPath);
456}
457
458SkContourMeasureIter::~SkContourMeasureIter() {}
459
460/** Assign a new path, or null to have none.
461*/
462void SkContourMeasureIter::reset(const SkPath& path, bool forceClosed, SkScalar resScale) {
463 if (path.isFinite()) {
464 fPath = path;
465 } else {
466 fPath.reset();
467 }
468 fForceClosed = forceClosed;
469
470 fIter.setPath(fPath);
471 fSegments.reset();
472 fPts.reset();
473}
474
475sk_sp<SkContourMeasure> SkContourMeasureIter::next() {
476 while (fIter.peek() != SkPath::kDone_Verb) {
477 auto cm = this->buildSegments();
478 if (cm) {
479 return sk_sp<SkContourMeasure>(cm);
480 }
481 }
482 return nullptr;
483}
484
485///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
486
487SkContourMeasure::SkContourMeasure(SkTDArray<Segment>&& segs, SkTDArray<SkPoint>&& pts, SkScalar length, bool isClosed)
488 : fSegments(std::move(segs))
489 , fPts(std::move(pts))
490 , fLength(length)
491 , fIsClosed(isClosed)
492 {}
493
494template <typename T, typename K>
495int SkTKSearch(const T base[], int count, const K& key) {
496 SkASSERT(count >= 0);
497 if (count <= 0) {
498 return ~0;
499 }
500
501 SkASSERT(base != nullptr); // base may be nullptr if count is zero
502
503 unsigned lo = 0;
504 unsigned hi = count - 1;
505
506 while (lo < hi) {
507 unsigned mid = (hi + lo) >> 1;
508 if (base[mid].fDistance < key) {
509 lo = mid + 1;
510 } else {
511 hi = mid;
512 }
513 }
514
515 if (base[hi].fDistance < key) {
516 hi += 1;
517 hi = ~hi;
518 } else if (key < base[hi].fDistance) {
519 hi = ~hi;
520 }
521 return hi;
522}
523
524const SkContourMeasure::Segment* SkContourMeasure::distanceToSegment( SkScalar distance,
525 SkScalar* t) const {
526 SkDEBUGCODE(SkScalar length = ) this->length();
527 SkASSERT(distance >= 0 && distance <= length);
528
529 const Segment* seg = fSegments.begin();
530 int count = fSegments.count();
531
532 int index = SkTKSearch<Segment, SkScalar>(seg, count, distance);
533 // don't care if we hit an exact match or not, so we xor index if it is negative
534 index ^= (index >> 31);
535 seg = &seg[index];
536
537 // now interpolate t-values with the prev segment (if possible)
538 SkScalar startT = 0, startD = 0;
539 // check if the prev segment is legal, and references the same set of points
540 if (index > 0) {
541 startD = seg[-1].fDistance;
542 if (seg[-1].fPtIndex == seg->fPtIndex) {
543 SkASSERT(seg[-1].fType == seg->fType);
544 startT = seg[-1].getScalarT();
545 }
546 }
547
548 SkASSERT(seg->getScalarT() > startT);
549 SkASSERT(distance >= startD);
550 SkASSERT(seg->fDistance > startD);
551
552 *t = startT + (seg->getScalarT() - startT) * (distance - startD) / (seg->fDistance - startD);
553 return seg;
554}
555
556bool SkContourMeasure::getPosTan(SkScalar distance, SkPoint* pos, SkVector* tangent) const {
557 if (SkScalarIsNaN(distance)) {
558 return false;
559 }
560
561 const SkScalar length = this->length();
562 SkASSERT(length > 0 && fSegments.count() > 0);
563
564 // pin the distance to a legal range
565 if (distance < 0) {
566 distance = 0;
567 } else if (distance > length) {
568 distance = length;
569 }
570
571 SkScalar t;
572 const Segment* seg = this->distanceToSegment(distance, &t);
573 if (SkScalarIsNaN(t)) {
574 return false;
575 }
576
577 SkASSERT((unsigned)seg->fPtIndex < (unsigned)fPts.count());
578 compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent);
579 return true;
580}
581
582bool SkContourMeasure::getMatrix(SkScalar distance, SkMatrix* matrix, MatrixFlags flags) const {
583 SkPoint position;
584 SkVector tangent;
585
586 if (this->getPosTan(distance, &position, &tangent)) {
587 if (matrix) {
588 if (flags & kGetTangent_MatrixFlag) {
589 matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
590 } else {
591 matrix->reset();
592 }
593 if (flags & kGetPosition_MatrixFlag) {
594 matrix->postTranslate(position.fX, position.fY);
595 }
596 }
597 return true;
598 }
599 return false;
600}
601
602bool SkContourMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
603 bool startWithMoveTo) const {
604 SkASSERT(dst);
605
606 SkScalar length = this->length(); // ensure we have built our segments
607
608 if (startD < 0) {
609 startD = 0;
610 }
611 if (stopD > length) {
612 stopD = length;
613 }
614 if (!(startD <= stopD)) { // catch NaN values as well
615 return false;
616 }
617 if (!fSegments.count()) {
618 return false;
619 }
620
621 SkPoint p;
622 SkScalar startT, stopT;
623 const Segment* seg = this->distanceToSegment(startD, &startT);
624 if (!SkScalarIsFinite(startT)) {
625 return false;
626 }
627 const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
628 if (!SkScalarIsFinite(stopT)) {
629 return false;
630 }
631 SkASSERT(seg <= stopSeg);
632 if (startWithMoveTo) {
633 compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, nullptr);
634 dst->moveTo(p);
635 }
636
637 if (seg->fPtIndex == stopSeg->fPtIndex) {
638 SkContourMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst);
639 } else {
640 do {
641 SkContourMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst);
642 seg = SkContourMeasure::Segment::Next(seg);
643 startT = 0;
644 } while (seg->fPtIndex < stopSeg->fPtIndex);
645 SkContourMeasure_segTo(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst);
646 }
647
648 return true;
649}
650