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