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