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