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