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