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