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
16enum {
17    kLine_SegType,
18    kQuad_SegType,
19    kCubic_SegType
20};
21
22#define kMaxTValue  32767
23
24static 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
34SkScalar SkPathMeasure::Segment::getScalarT() const {
35    return tValue2Scalar(fTValue);
36}
37
38const 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
49static 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
59static 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
71static 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
78static 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
88SkScalar 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
112SkScalar 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
136void 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::kMove_Verb:
156                ptIndex += 1;
157                fPts.append(1, pts);
158                if (!firstMoveTo) {
159                    done = true;
160                    break;
161                }
162                firstMoveTo = false;
163                break;
164
165            case SkPath::kLine_Verb: {
166                SkScalar d = SkPoint::Distance(pts[0], pts[1]);
167                SkASSERT(d >= 0);
168                SkScalar prevD = distance;
169                distance += d;
170                if (distance > prevD) {
171                    seg = fSegments.append();
172                    seg->fDistance = distance;
173                    seg->fPtIndex = ptIndex;
174                    seg->fType = kLine_SegType;
175                    seg->fTValue = kMaxTValue;
176                    fPts.append(1, pts + 1);
177                    ptIndex++;
178                }
179            } break;
180
181            case SkPath::kQuad_Verb: {
182                SkScalar prevD = distance;
183                distance = this->compute_quad_segs(pts, distance, 0,
184                                                   kMaxTValue, ptIndex);
185                if (distance > prevD) {
186                    fPts.append(2, pts + 1);
187                    ptIndex += 2;
188                }
189            } break;
190
191            case SkPath::kCubic_Verb: {
192                SkScalar prevD = distance;
193                distance = this->compute_cubic_segs(pts, distance, 0,
194                                                    kMaxTValue, ptIndex);
195                if (distance > prevD) {
196                    fPts.append(3, pts + 1);
197                    ptIndex += 3;
198                }
199            } break;
200
201            case SkPath::kClose_Verb:
202                isClosed = true;
203                break;
204
205            case SkPath::kDone_Verb:
206                done = true;
207                break;
208        }
209    } while (!done);
210
211    fLength = distance;
212    fIsClosed = isClosed;
213    fFirstPtIndex = ptIndex;
214
215#ifdef SK_DEBUG
216    {
217        const Segment* seg = fSegments.begin();
218        const Segment* stop = fSegments.end();
219        unsigned        ptIndex = 0;
220        SkScalar        distance = 0;
221
222        while (seg < stop) {
223            SkASSERT(seg->fDistance > distance);
224            SkASSERT(seg->fPtIndex >= ptIndex);
225            SkASSERT(seg->fTValue > 0);
226
227            const Segment* s = seg;
228            while (s < stop - 1 && s[0].fPtIndex == s[1].fPtIndex) {
229                SkASSERT(s[0].fType == s[1].fType);
230                SkASSERT(s[0].fTValue < s[1].fTValue);
231                s += 1;
232            }
233
234            distance = seg->fDistance;
235            ptIndex = seg->fPtIndex;
236            seg += 1;
237        }
238    //  SkDebugf("\n");
239    }
240#endif
241}
242
243static void compute_pos_tan(const SkPoint pts[], int segType,
244                            SkScalar t, SkPoint* pos, SkVector* tangent) {
245    switch (segType) {
246        case kLine_SegType:
247            if (pos) {
248                pos->set(SkScalarInterp(pts[0].fX, pts[1].fX, t),
249                         SkScalarInterp(pts[0].fY, pts[1].fY, t));
250            }
251            if (tangent) {
252                tangent->setNormalize(pts[1].fX - pts[0].fX, pts[1].fY - pts[0].fY);
253            }
254            break;
255        case kQuad_SegType:
256            SkEvalQuadAt(pts, t, pos, tangent);
257            if (tangent) {
258                tangent->normalize();
259            }
260            break;
261        case kCubic_SegType:
262            SkEvalCubicAt(pts, t, pos, tangent, NULL);
263            if (tangent) {
264                tangent->normalize();
265            }
266            break;
267        default:
268            SkDEBUGFAIL("unknown segType");
269    }
270}
271
272static void seg_to(const SkPoint pts[], int segType,
273                   SkScalar startT, SkScalar stopT, SkPath* dst) {
274    SkASSERT(startT >= 0 && startT <= SK_Scalar1);
275    SkASSERT(stopT >= 0 && stopT <= SK_Scalar1);
276    SkASSERT(startT <= stopT);
277
278    if (startT == stopT) {
279        return; // should we report this, to undo a moveTo?
280    }
281
282    SkPoint         tmp0[7], tmp1[7];
283
284    switch (segType) {
285        case kLine_SegType:
286            if (stopT == kMaxTValue) {
287                dst->lineTo(pts[1]);
288            } else {
289                dst->lineTo(SkScalarInterp(pts[0].fX, pts[1].fX, stopT),
290                            SkScalarInterp(pts[0].fY, pts[1].fY, stopT));
291            }
292            break;
293        case kQuad_SegType:
294            if (startT == 0) {
295                if (stopT == SK_Scalar1) {
296                    dst->quadTo(pts[1], pts[2]);
297                } else {
298                    SkChopQuadAt(pts, tmp0, stopT);
299                    dst->quadTo(tmp0[1], tmp0[2]);
300                }
301            } else {
302                SkChopQuadAt(pts, tmp0, startT);
303                if (stopT == SK_Scalar1) {
304                    dst->quadTo(tmp0[3], tmp0[4]);
305                } else {
306                    SkChopQuadAt(&tmp0[2], tmp1, SkScalarDiv(stopT - startT,
307                                                         SK_Scalar1 - startT));
308                    dst->quadTo(tmp1[1], tmp1[2]);
309                }
310            }
311            break;
312        case kCubic_SegType:
313            if (startT == 0) {
314                if (stopT == SK_Scalar1) {
315                    dst->cubicTo(pts[1], pts[2], pts[3]);
316                } else {
317                    SkChopCubicAt(pts, tmp0, stopT);
318                    dst->cubicTo(tmp0[1], tmp0[2], tmp0[3]);
319                }
320            } else {
321                SkChopCubicAt(pts, tmp0, startT);
322                if (stopT == SK_Scalar1) {
323                    dst->cubicTo(tmp0[4], tmp0[5], tmp0[6]);
324                } else {
325                    SkChopCubicAt(&tmp0[3], tmp1, SkScalarDiv(stopT - startT,
326                                                        SK_Scalar1 - startT));
327                    dst->cubicTo(tmp1[1], tmp1[2], tmp1[3]);
328                }
329            }
330            break;
331        default:
332            SkDEBUGFAIL("unknown segType");
333            sk_throw();
334    }
335}
336
337////////////////////////////////////////////////////////////////////////////////
338////////////////////////////////////////////////////////////////////////////////
339
340SkPathMeasure::SkPathMeasure() {
341    fPath = NULL;
342    fLength = -1;   // signal we need to compute it
343    fForceClosed = false;
344    fFirstPtIndex = -1;
345}
346
347SkPathMeasure::SkPathMeasure(const SkPath& path, bool forceClosed) {
348    fPath = &path;
349    fLength = -1;   // signal we need to compute it
350    fForceClosed = forceClosed;
351    fFirstPtIndex = -1;
352
353    fIter.setPath(path, forceClosed);
354}
355
356SkPathMeasure::~SkPathMeasure() {}
357
358/** Assign a new path, or null to have none.
359*/
360void SkPathMeasure::setPath(const SkPath* path, bool forceClosed) {
361    fPath = path;
362    fLength = -1;   // signal we need to compute it
363    fForceClosed = forceClosed;
364    fFirstPtIndex = -1;
365
366    if (path) {
367        fIter.setPath(*path, forceClosed);
368    }
369    fSegments.reset();
370    fPts.reset();
371}
372
373SkScalar SkPathMeasure::getLength() {
374    if (fPath == NULL) {
375        return 0;
376    }
377    if (fLength < 0) {
378        this->buildSegments();
379    }
380    SkASSERT(fLength >= 0);
381    return fLength;
382}
383
384const SkPathMeasure::Segment* SkPathMeasure::distanceToSegment(
385                                            SkScalar distance, SkScalar* t) {
386    SkDEBUGCODE(SkScalar length = ) this->getLength();
387    SkASSERT(distance >= 0 && distance <= length);
388
389    const Segment*  seg = fSegments.begin();
390    int             count = fSegments.count();
391
392    int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance,
393                                    sizeof(Segment));
394    // don't care if we hit an exact match or not, so we xor index if it is negative
395    index ^= (index >> 31);
396    seg = &seg[index];
397
398    // now interpolate t-values with the prev segment (if possible)
399    SkScalar    startT = 0, startD = 0;
400    // check if the prev segment is legal, and references the same set of points
401    if (index > 0) {
402        startD = seg[-1].fDistance;
403        if (seg[-1].fPtIndex == seg->fPtIndex) {
404            SkASSERT(seg[-1].fType == seg->fType);
405            startT = seg[-1].getScalarT();
406        }
407    }
408
409    SkASSERT(seg->getScalarT() > startT);
410    SkASSERT(distance >= startD);
411    SkASSERT(seg->fDistance > startD);
412
413    *t = startT + SkScalarMulDiv(seg->getScalarT() - startT,
414                                 distance - startD,
415                                 seg->fDistance - startD);
416    return seg;
417}
418
419bool SkPathMeasure::getPosTan(SkScalar distance, SkPoint* pos,
420                              SkVector* tangent) {
421    if (NULL == fPath) {
422        return false;
423    }
424
425    SkScalar    length = this->getLength(); // call this to force computing it
426    int         count = fSegments.count();
427
428    if (count == 0 || length == 0) {
429        return false;
430    }
431
432    // pin the distance to a legal range
433    if (distance < 0) {
434        distance = 0;
435    } else if (distance > length) {
436        distance = length;
437    }
438
439    SkScalar        t;
440    const Segment*  seg = this->distanceToSegment(distance, &t);
441
442    compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, t, pos, tangent);
443    return true;
444}
445
446bool SkPathMeasure::getMatrix(SkScalar distance, SkMatrix* matrix,
447                              MatrixFlags flags) {
448    if (NULL == fPath) {
449        return false;
450    }
451
452    SkPoint     position;
453    SkVector    tangent;
454
455    if (this->getPosTan(distance, &position, &tangent)) {
456        if (matrix) {
457            if (flags & kGetTangent_MatrixFlag) {
458                matrix->setSinCos(tangent.fY, tangent.fX, 0, 0);
459            } else {
460                matrix->reset();
461            }
462            if (flags & kGetPosition_MatrixFlag) {
463                matrix->postTranslate(position.fX, position.fY);
464            }
465        }
466        return true;
467    }
468    return false;
469}
470
471bool SkPathMeasure::getSegment(SkScalar startD, SkScalar stopD, SkPath* dst,
472                               bool startWithMoveTo) {
473    SkASSERT(dst);
474
475    SkScalar length = this->getLength();    // ensure we have built our segments
476
477    if (startD < 0) {
478        startD = 0;
479    }
480    if (stopD > length) {
481        stopD = length;
482    }
483    if (startD >= stopD) {
484        return false;
485    }
486
487    SkPoint  p;
488    SkScalar startT, stopT;
489    const Segment* seg = this->distanceToSegment(startD, &startT);
490    const Segment* stopSeg = this->distanceToSegment(stopD, &stopT);
491    SkASSERT(seg <= stopSeg);
492
493    if (startWithMoveTo) {
494        compute_pos_tan(&fPts[seg->fPtIndex], seg->fType, startT, &p, NULL);
495        dst->moveTo(p);
496    }
497
498    if (seg->fPtIndex == stopSeg->fPtIndex) {
499        seg_to(&fPts[seg->fPtIndex], seg->fType, startT, stopT, dst);
500    } else {
501        do {
502            seg_to(&fPts[seg->fPtIndex], seg->fType, startT, SK_Scalar1, dst);
503            seg = SkPathMeasure::NextSegment(seg);
504            startT = 0;
505        } while (seg->fPtIndex < stopSeg->fPtIndex);
506        seg_to(&fPts[seg->fPtIndex], seg->fType, 0, stopT, dst);
507    }
508    return true;
509}
510
511bool SkPathMeasure::isClosed() {
512    (void)this->getLength();
513    return fIsClosed;
514}
515
516/** Move to the next contour in the path. Return true if one exists, or false if
517    we're done with the path.
518*/
519bool SkPathMeasure::nextContour() {
520    fLength = -1;
521    return this->getLength() > 0;
522}
523
524///////////////////////////////////////////////////////////////////////////////
525///////////////////////////////////////////////////////////////////////////////
526
527#ifdef SK_DEBUG
528
529void SkPathMeasure::dump() {
530    SkDebugf("pathmeas: length=%g, segs=%d\n", fLength, fSegments.count());
531
532    for (int i = 0; i < fSegments.count(); i++) {
533        const Segment* seg = &fSegments[i];
534        SkDebugf("pathmeas: seg[%d] distance=%g, point=%d, t=%g, type=%d\n",
535                i, seg->fDistance, seg->fPtIndex, seg->getScalarT(),
536                 seg->fType);
537    }
538}
539
540#endif
541