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