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