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    return t * 3.05185e-5f; // t / 32767
27}
28
29SkScalar SkPathMeasure::Segment::getScalarT() const {
30    return tValue2Scalar(fTValue);
31}
32
33const 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
44static 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
54static 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
66static 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
73static 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
83SkScalar 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
107SkScalar 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
131void 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
241static 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
270static 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
338SkPathMeasure::SkPathMeasure() {
339    fPath = NULL;
340    fLength = -1;   // signal we need to compute it
341    fForceClosed = false;
342    fFirstPtIndex = -1;
343}
344
345SkPathMeasure::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
354SkPathMeasure::~SkPathMeasure() {}
355
356/** Assign a new path, or null to have none.
357*/
358void 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
371SkScalar 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
382const 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
416bool 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
443bool 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
468bool 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
508bool 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*/
516bool SkPathMeasure::nextContour() {
517    fLength = -1;
518    return this->getLength() > 0;
519}
520
521///////////////////////////////////////////////////////////////////////////////
522///////////////////////////////////////////////////////////////////////////////
523
524#ifdef SK_DEBUG
525
526void 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