SkPath.cpp revision 08fa28cd31c96b4ebd9cb532539c3a8c88803d90 
1
2/*
3 * Copyright 2006 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 "SkBuffer.h"
11#include "SkErrorInternals.h"
12#include "SkMath.h"
13#include "SkPath.h"
14#include "SkPathRef.h"
15#include "SkRRect.h"
16#include "SkThread.h"
17
18////////////////////////////////////////////////////////////////////////////
19
20/**
21 *  Path.bounds is defined to be the bounds of all the control points.
22 *  If we called bounds.join(r) we would skip r if r was empty, which breaks
23 *  our promise. Hence we have a custom joiner that doesn't look at emptiness
24 */
25static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) {
26    dst->fLeft = SkMinScalar(dst->fLeft, src.fLeft);
27    dst->fTop = SkMinScalar(dst->fTop, src.fTop);
28    dst->fRight = SkMaxScalar(dst->fRight, src.fRight);
29    dst->fBottom = SkMaxScalar(dst->fBottom, src.fBottom);
30}
31
32static bool is_degenerate(const SkPath& path) {
33    SkPath::Iter iter(path, false);
34    SkPoint pts[4];
35    return SkPath::kDone_Verb == iter.next(pts);
36}
37
38class SkAutoDisableDirectionCheck {
39public:
40    SkAutoDisableDirectionCheck(SkPath* path) : fPath(path) {
41        fSaved = static_cast<SkPath::Direction>(fPath->fDirection);
42    }
43
44    ~SkAutoDisableDirectionCheck() {
45        fPath->fDirection = fSaved;
46    }
47
48private:
49    SkPath*              fPath;
50    SkPath::Direction    fSaved;
51};
52#define SkAutoDisableDirectionCheck(...) SK_REQUIRE_LOCAL_VAR(SkAutoDisableDirectionCheck)
53
54/*  This guy's constructor/destructor bracket a path editing operation. It is
55    used when we know the bounds of the amount we are going to add to the path
56    (usually a new contour, but not required).
57
58    It captures some state about the path up front (i.e. if it already has a
59    cached bounds), and then if it can, it updates the cache bounds explicitly,
60    avoiding the need to revisit all of the points in getBounds().
61
62    It also notes if the path was originally degenerate, and if so, sets
63    isConvex to true. Thus it can only be used if the contour being added is
64    convex.
65 */
66class SkAutoPathBoundsUpdate {
67public:
68    SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) {
69        this->init(path);
70    }
71
72    SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top,
73                           SkScalar right, SkScalar bottom) {
74        fRect.set(left, top, right, bottom);
75        this->init(path);
76    }
77
78    ~SkAutoPathBoundsUpdate() {
79        fPath->setConvexity(fDegenerate ? SkPath::kConvex_Convexity
80                                        : SkPath::kUnknown_Convexity);
81        if (fEmpty || fHasValidBounds) {
82            fPath->setBounds(fRect);
83        }
84    }
85
86private:
87    SkPath* fPath;
88    SkRect  fRect;
89    bool    fHasValidBounds;
90    bool    fDegenerate;
91    bool    fEmpty;
92
93    void init(SkPath* path) {
94        // Cannot use fRect for our bounds unless we know it is sorted
95        fRect.sort();
96        fPath = path;
97        // Mark the path's bounds as dirty if (1) they are, or (2) the path
98        // is non-finite, and therefore its bounds are not meaningful
99        fHasValidBounds = path->hasComputedBounds() && path->isFinite();
100        fEmpty = path->isEmpty();
101        if (fHasValidBounds && !fEmpty) {
102            joinNoEmptyChecks(&fRect, fPath->getBounds());
103        }
104        fDegenerate = is_degenerate(*path);
105    }
106};
107#define SkAutoPathBoundsUpdate(...) SK_REQUIRE_LOCAL_VAR(SkAutoPathBoundsUpdate)
108
109////////////////////////////////////////////////////////////////////////////
110
111/*
112    Stores the verbs and points as they are given to us, with exceptions:
113    - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic
114    - we insert a Move(0,0) if Line | Quad | Cubic is our first command
115
116    The iterator does more cleanup, especially if forceClose == true
117    1. If we encounter degenerate segments, remove them
118    2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt)
119    3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2
120    4. if we encounter Line | Quad | Cubic after Close, cons up a Move
121*/
122
123////////////////////////////////////////////////////////////////////////////
124
125// flag to require a moveTo if we begin with something else, like lineTo etc.
126#define INITIAL_LASTMOVETOINDEX_VALUE   ~0
127
128SkPath::SkPath()
129    : fPathRef(SkPathRef::CreateEmpty())
130#ifdef SK_BUILD_FOR_ANDROID
131    , fSourcePath(NULL)
132#endif
133{
134    this->resetFields();
135}
136
137void SkPath::resetFields() {
138    //fPathRef is assumed to have been emptied by the caller.
139    fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
140    fFillType = kWinding_FillType;
141    fConvexity = kUnknown_Convexity;
142    fDirection = kUnknown_Direction;
143
144    // We don't touch Android's fSourcePath.  It's used to track texture garbage collection, so we
145    // don't want to muck with it if it's been set to something non-NULL.
146}
147
148SkPath::SkPath(const SkPath& that)
149    : fPathRef(SkRef(that.fPathRef.get())) {
150    this->copyFields(that);
151#ifdef SK_BUILD_FOR_ANDROID
152    fSourcePath   = that.fSourcePath;
153#endif
154    SkDEBUGCODE(that.validate();)
155}
156
157SkPath::~SkPath() {
158    SkDEBUGCODE(this->validate();)
159}
160
161SkPath& SkPath::operator=(const SkPath& that) {
162    SkDEBUGCODE(that.validate();)
163
164    if (this != &that) {
165        fPathRef.reset(SkRef(that.fPathRef.get()));
166        this->copyFields(that);
167#ifdef SK_BUILD_FOR_ANDROID
168        fSourcePath = that.fSourcePath;
169#endif
170    }
171    SkDEBUGCODE(this->validate();)
172    return *this;
173}
174
175void SkPath::copyFields(const SkPath& that) {
176    //fPathRef is assumed to have been set by the caller.
177    fLastMoveToIndex = that.fLastMoveToIndex;
178    fFillType        = that.fFillType;
179    fConvexity       = that.fConvexity;
180    fDirection       = that.fDirection;
181}
182
183bool operator==(const SkPath& a, const SkPath& b) {
184    // note: don't need to look at isConvex or bounds, since just comparing the
185    // raw data is sufficient.
186    return &a == &b ||
187        (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get());
188}
189
190void SkPath::swap(SkPath& that) {
191    SkASSERT(&that != NULL);
192
193    if (this != &that) {
194        fPathRef.swap(&that.fPathRef);
195        SkTSwap<int>(fLastMoveToIndex, that.fLastMoveToIndex);
196        SkTSwap<uint8_t>(fFillType, that.fFillType);
197        SkTSwap<uint8_t>(fConvexity, that.fConvexity);
198        SkTSwap<uint8_t>(fDirection, that.fDirection);
199#ifdef SK_BUILD_FOR_ANDROID
200        SkTSwap<const SkPath*>(fSourcePath, that.fSourcePath);
201#endif
202    }
203}
204
205static inline bool check_edge_against_rect(const SkPoint& p0,
206                                           const SkPoint& p1,
207                                           const SkRect& rect,
208                                           SkPath::Direction dir) {
209    const SkPoint* edgeBegin;
210    SkVector v;
211    if (SkPath::kCW_Direction == dir) {
212        v = p1 - p0;
213        edgeBegin = &p0;
214    } else {
215        v = p0 - p1;
216        edgeBegin = &p1;
217    }
218    if (v.fX || v.fY) {
219        // check the cross product of v with the vec from edgeBegin to each rect corner
220        SkScalar yL = SkScalarMul(v.fY, rect.fLeft - edgeBegin->fX);
221        SkScalar xT = SkScalarMul(v.fX, rect.fTop - edgeBegin->fY);
222        SkScalar yR = SkScalarMul(v.fY, rect.fRight - edgeBegin->fX);
223        SkScalar xB = SkScalarMul(v.fX, rect.fBottom - edgeBegin->fY);
224        if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
225            return false;
226        }
227    }
228    return true;
229}
230
231bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
232    // This only handles non-degenerate convex paths currently.
233    if (kConvex_Convexity != this->getConvexity()) {
234        return false;
235    }
236
237    Direction direction;
238    if (!this->cheapComputeDirection(&direction)) {
239        return false;
240    }
241
242    SkPoint firstPt;
243    SkPoint prevPt;
244    RawIter iter(*this);
245    SkPath::Verb verb;
246    SkPoint pts[4];
247    SkDEBUGCODE(int moveCnt = 0;)
248    SkDEBUGCODE(int segmentCount = 0;)
249    SkDEBUGCODE(int closeCount = 0;)
250
251    while ((verb = iter.next(pts)) != kDone_Verb) {
252        int nextPt = -1;
253        switch (verb) {
254            case kMove_Verb:
255                SkASSERT(!segmentCount && !closeCount);
256                SkDEBUGCODE(++moveCnt);
257                firstPt = prevPt = pts[0];
258                break;
259            case kLine_Verb:
260                nextPt = 1;
261                SkASSERT(moveCnt && !closeCount);
262                SkDEBUGCODE(++segmentCount);
263                break;
264            case kQuad_Verb:
265            case kConic_Verb:
266                SkASSERT(moveCnt && !closeCount);
267                SkDEBUGCODE(++segmentCount);
268                nextPt = 2;
269                break;
270            case kCubic_Verb:
271                SkASSERT(moveCnt && !closeCount);
272                SkDEBUGCODE(++segmentCount);
273                nextPt = 3;
274                break;
275            case kClose_Verb:
276                SkDEBUGCODE(++closeCount;)
277                break;
278            default:
279                SkDEBUGFAIL("unknown verb");
280        }
281        if (-1 != nextPt) {
282            if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) {
283                return false;
284            }
285            prevPt = pts[nextPt];
286        }
287    }
288
289    return check_edge_against_rect(prevPt, firstPt, rect, direction);
290}
291
292uint32_t SkPath::getGenerationID() const {
293    uint32_t genID = fPathRef->genID();
294#ifdef SK_BUILD_FOR_ANDROID
295    SkASSERT((unsigned)fFillType < (1 << (32 - kPathRefGenIDBitCnt)));
296    genID |= static_cast<uint32_t>(fFillType) << kPathRefGenIDBitCnt;
297#endif
298    return genID;
299}
300
301#ifdef SK_BUILD_FOR_ANDROID
302const SkPath* SkPath::getSourcePath() const {
303    return fSourcePath;
304}
305
306void SkPath::setSourcePath(const SkPath* path) {
307    fSourcePath = path;
308}
309#endif
310
311void SkPath::reset() {
312    SkDEBUGCODE(this->validate();)
313
314    fPathRef.reset(SkPathRef::CreateEmpty());
315    this->resetFields();
316}
317
318void SkPath::rewind() {
319    SkDEBUGCODE(this->validate();)
320
321    SkPathRef::Rewind(&fPathRef);
322    this->resetFields();
323}
324
325bool SkPath::isLine(SkPoint line[2]) const {
326    int verbCount = fPathRef->countVerbs();
327
328    if (2 == verbCount) {
329        SkASSERT(kMove_Verb == fPathRef->atVerb(0));
330        if (kLine_Verb == fPathRef->atVerb(1)) {
331            SkASSERT(2 == fPathRef->countPoints());
332            if (line) {
333                const SkPoint* pts = fPathRef->points();
334                line[0] = pts[0];
335                line[1] = pts[1];
336            }
337            return true;
338        }
339    }
340    return false;
341}
342
343/*
344 Determines if path is a rect by keeping track of changes in direction
345 and looking for a loop either clockwise or counterclockwise.
346
347 The direction is computed such that:
348  0: vertical up
349  1: horizontal left
350  2: vertical down
351  3: horizontal right
352
353A rectangle cycles up/right/down/left or up/left/down/right.
354
355The test fails if:
356  The path is closed, and followed by a line.
357  A second move creates a new endpoint.
358  A diagonal line is parsed.
359  There's more than four changes of direction.
360  There's a discontinuity on the line (e.g., a move in the middle)
361  The line reverses direction.
362  The path contains a quadratic or cubic.
363  The path contains fewer than four points.
364 *The rectangle doesn't complete a cycle.
365 *The final point isn't equal to the first point.
366
367  *These last two conditions we relax if we have a 3-edge path that would
368   form a rectangle if it were closed (as we do when we fill a path)
369
370It's OK if the path has:
371  Several colinear line segments composing a rectangle side.
372  Single points on the rectangle side.
373
374The direction takes advantage of the corners found since opposite sides
375must travel in opposite directions.
376
377FIXME: Allow colinear quads and cubics to be treated like lines.
378FIXME: If the API passes fill-only, return true if the filled stroke
379       is a rectangle, though the caller failed to close the path.
380
381 first,last,next direction state-machine:
382    0x1 is set if the segment is horizontal
383    0x2 is set if the segment is moving to the right or down
384 thus:
385    two directions are opposites iff (dirA ^ dirB) == 0x2
386    two directions are perpendicular iff (dirA ^ dirB) == 0x1
387
388 */
389static int rect_make_dir(SkScalar dx, SkScalar dy) {
390    return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
391}
392bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr,
393        bool* isClosed, Direction* direction) const {
394    int corners = 0;
395    SkPoint first, last;
396    const SkPoint* pts = *ptsPtr;
397    const SkPoint* savePts = NULL;
398    first.set(0, 0);
399    last.set(0, 0);
400    int firstDirection = 0;
401    int lastDirection = 0;
402    int nextDirection = 0;
403    bool closedOrMoved = false;
404    bool autoClose = false;
405    int verbCnt = fPathRef->countVerbs();
406    while (*currVerb < verbCnt && (!allowPartial || !autoClose)) {
407        switch (fPathRef->atVerb(*currVerb)) {
408            case kClose_Verb:
409                savePts = pts;
410                pts = *ptsPtr;
411                autoClose = true;
412            case kLine_Verb: {
413                SkScalar left = last.fX;
414                SkScalar top = last.fY;
415                SkScalar right = pts->fX;
416                SkScalar bottom = pts->fY;
417                ++pts;
418                if (left != right && top != bottom) {
419                    return false; // diagonal
420                }
421                if (left == right && top == bottom) {
422                    break; // single point on side OK
423                }
424                nextDirection = rect_make_dir(right - left, bottom - top);
425                if (0 == corners) {
426                    firstDirection = nextDirection;
427                    first = last;
428                    last = pts[-1];
429                    corners = 1;
430                    closedOrMoved = false;
431                    break;
432                }
433                if (closedOrMoved) {
434                    return false; // closed followed by a line
435                }
436                if (autoClose && nextDirection == firstDirection) {
437                    break; // colinear with first
438                }
439                closedOrMoved = autoClose;
440                if (lastDirection != nextDirection) {
441                    if (++corners > 4) {
442                        return false; // too many direction changes
443                    }
444                }
445                last = pts[-1];
446                if (lastDirection == nextDirection) {
447                    break; // colinear segment
448                }
449                // Possible values for corners are 2, 3, and 4.
450                // When corners == 3, nextDirection opposes firstDirection.
451                // Otherwise, nextDirection at corner 2 opposes corner 4.
452                int turn = firstDirection ^ (corners - 1);
453                int directionCycle = 3 == corners ? 0 : nextDirection ^ turn;
454                if ((directionCycle ^ turn) != nextDirection) {
455                    return false; // direction didn't follow cycle
456                }
457                break;
458            }
459            case kQuad_Verb:
460            case kConic_Verb:
461            case kCubic_Verb:
462                return false; // quadratic, cubic not allowed
463            case kMove_Verb:
464                last = *pts++;
465                closedOrMoved = true;
466                break;
467            default:
468                SkDEBUGFAIL("unexpected verb");
469                break;
470        }
471        *currVerb += 1;
472        lastDirection = nextDirection;
473    }
474    // Success if 4 corners and first point equals last
475    bool result = 4 == corners && (first == last || autoClose);
476    if (!result) {
477        // check if we are just an incomplete rectangle, in which case we can
478        // return true, but not claim to be closed.
479        // e.g.
480        //    3 sided rectangle
481        //    4 sided but the last edge is not long enough to reach the start
482        //
483        SkScalar closeX = first.x() - last.x();
484        SkScalar closeY = first.y() - last.y();
485        if (closeX && closeY) {
486            return false;   // we're diagonal, abort (can we ever reach this?)
487        }
488        int closeDirection = rect_make_dir(closeX, closeY);
489        // make sure the close-segment doesn't double-back on itself
490        if (3 == corners || (4 == corners && closeDirection == lastDirection)) {
491            result = true;
492            autoClose = false;  // we are not closed
493        }
494    }
495    if (savePts) {
496        *ptsPtr = savePts;
497    }
498    if (result && isClosed) {
499        *isClosed = autoClose;
500    }
501    if (result && direction) {
502        *direction = firstDirection == ((lastDirection + 1) & 3) ? kCCW_Direction : kCW_Direction;
503    }
504    return result;
505}
506
507SkPath::PathAsRect SkPath::asRect(Direction* direction) const {
508    SK_COMPILE_ASSERT(0 == kNone_PathAsRect, path_as_rect_mismatch);
509    SK_COMPILE_ASSERT(1 == kFill_PathAsRect, path_as_rect_mismatch);
510    SK_COMPILE_ASSERT(2 == kStroke_PathAsRect, path_as_rect_mismatch);
511    bool isClosed = false;
512    return (PathAsRect) (isRect(&isClosed, direction) + isClosed);
513}
514
515bool SkPath::isRect(SkRect* rect) const {
516    SkDEBUGCODE(this->validate();)
517    int currVerb = 0;
518    const SkPoint* pts = fPathRef->points();
519    bool result = isRectContour(false, &currVerb, &pts, NULL, NULL);
520    if (result && rect) {
521        *rect = getBounds();
522    }
523    return result;
524}
525
526bool SkPath::isRect(bool* isClosed, Direction* direction) const {
527    SkDEBUGCODE(this->validate();)
528    int currVerb = 0;
529    const SkPoint* pts = fPathRef->points();
530    return isRectContour(false, &currVerb, &pts, isClosed, direction);
531}
532
533bool SkPath::isNestedRects(SkRect rects[2], Direction dirs[2]) const {
534    SkDEBUGCODE(this->validate();)
535    int currVerb = 0;
536    const SkPoint* pts = fPathRef->points();
537    const SkPoint* first = pts;
538    Direction testDirs[2];
539    if (!isRectContour(true, &currVerb, &pts, NULL, &testDirs[0])) {
540        return false;
541    }
542    const SkPoint* last = pts;
543    SkRect testRects[2];
544    if (isRectContour(false, &currVerb, &pts, NULL, &testDirs[1])) {
545        testRects[0].set(first, SkToS32(last - first));
546        testRects[1].set(last, SkToS32(pts - last));
547        if (testRects[0].contains(testRects[1])) {
548            if (rects) {
549                rects[0] = testRects[0];
550                rects[1] = testRects[1];
551            }
552            if (dirs) {
553                dirs[0] = testDirs[0];
554                dirs[1] = testDirs[1];
555            }
556            return true;
557        }
558        if (testRects[1].contains(testRects[0])) {
559            if (rects) {
560                rects[0] = testRects[1];
561                rects[1] = testRects[0];
562            }
563            if (dirs) {
564                dirs[0] = testDirs[1];
565                dirs[1] = testDirs[0];
566            }
567            return true;
568        }
569    }
570    return false;
571}
572
573int SkPath::countPoints() const {
574    return fPathRef->countPoints();
575}
576
577int SkPath::getPoints(SkPoint dst[], int max) const {
578    SkDEBUGCODE(this->validate();)
579
580    SkASSERT(max >= 0);
581    SkASSERT(!max || dst);
582    int count = SkMin32(max, fPathRef->countPoints());
583    memcpy(dst, fPathRef->points(), count * sizeof(SkPoint));
584    return fPathRef->countPoints();
585}
586
587SkPoint SkPath::getPoint(int index) const {
588    if ((unsigned)index < (unsigned)fPathRef->countPoints()) {
589        return fPathRef->atPoint(index);
590    }
591    return SkPoint::Make(0, 0);
592}
593
594int SkPath::countVerbs() const {
595    return fPathRef->countVerbs();
596}
597
598static inline void copy_verbs_reverse(uint8_t* inorderDst,
599                                      const uint8_t* reversedSrc,
600                                      int count) {
601    for (int i = 0; i < count; ++i) {
602        inorderDst[i] = reversedSrc[~i];
603    }
604}
605
606int SkPath::getVerbs(uint8_t dst[], int max) const {
607    SkDEBUGCODE(this->validate();)
608
609    SkASSERT(max >= 0);
610    SkASSERT(!max || dst);
611    int count = SkMin32(max, fPathRef->countVerbs());
612    copy_verbs_reverse(dst, fPathRef->verbs(), count);
613    return fPathRef->countVerbs();
614}
615
616bool SkPath::getLastPt(SkPoint* lastPt) const {
617    SkDEBUGCODE(this->validate();)
618
619    int count = fPathRef->countPoints();
620    if (count > 0) {
621        if (lastPt) {
622            *lastPt = fPathRef->atPoint(count - 1);
623        }
624        return true;
625    }
626    if (lastPt) {
627        lastPt->set(0, 0);
628    }
629    return false;
630}
631
632void SkPath::setLastPt(SkScalar x, SkScalar y) {
633    SkDEBUGCODE(this->validate();)
634
635    int count = fPathRef->countPoints();
636    if (count == 0) {
637        this->moveTo(x, y);
638    } else {
639        SkPathRef::Editor ed(&fPathRef);
640        ed.atPoint(count-1)->set(x, y);
641    }
642}
643
644void SkPath::setConvexity(Convexity c) {
645    if (fConvexity != c) {
646        fConvexity = c;
647    }
648}
649
650//////////////////////////////////////////////////////////////////////////////
651//  Construction methods
652
653#define DIRTY_AFTER_EDIT                 \
654    do {                                 \
655        fConvexity = kUnknown_Convexity; \
656        fDirection = kUnknown_Direction; \
657    } while (0)
658
659void SkPath::incReserve(U16CPU inc) {
660    SkDEBUGCODE(this->validate();)
661    SkPathRef::Editor(&fPathRef, inc, inc);
662    SkDEBUGCODE(this->validate();)
663}
664
665void SkPath::moveTo(SkScalar x, SkScalar y) {
666    SkDEBUGCODE(this->validate();)
667
668    SkPathRef::Editor ed(&fPathRef);
669
670    // remember our index
671    fLastMoveToIndex = fPathRef->countPoints();
672
673    ed.growForVerb(kMove_Verb)->set(x, y);
674
675    DIRTY_AFTER_EDIT;
676}
677
678void SkPath::rMoveTo(SkScalar x, SkScalar y) {
679    SkPoint pt;
680    this->getLastPt(&pt);
681    this->moveTo(pt.fX + x, pt.fY + y);
682}
683
684void SkPath::injectMoveToIfNeeded() {
685    if (fLastMoveToIndex < 0) {
686        SkScalar x, y;
687        if (fPathRef->countVerbs() == 0) {
688            x = y = 0;
689        } else {
690            const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex);
691            x = pt.fX;
692            y = pt.fY;
693        }
694        this->moveTo(x, y);
695    }
696}
697
698void SkPath::lineTo(SkScalar x, SkScalar y) {
699    SkDEBUGCODE(this->validate();)
700
701    this->injectMoveToIfNeeded();
702
703    SkPathRef::Editor ed(&fPathRef);
704    ed.growForVerb(kLine_Verb)->set(x, y);
705
706    DIRTY_AFTER_EDIT;
707}
708
709void SkPath::rLineTo(SkScalar x, SkScalar y) {
710    this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
711    SkPoint pt;
712    this->getLastPt(&pt);
713    this->lineTo(pt.fX + x, pt.fY + y);
714}
715
716void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
717    SkDEBUGCODE(this->validate();)
718
719    this->injectMoveToIfNeeded();
720
721    SkPathRef::Editor ed(&fPathRef);
722    SkPoint* pts = ed.growForVerb(kQuad_Verb);
723    pts[0].set(x1, y1);
724    pts[1].set(x2, y2);
725
726    DIRTY_AFTER_EDIT;
727}
728
729void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
730    this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
731    SkPoint pt;
732    this->getLastPt(&pt);
733    this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
734}
735
736void SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
737                     SkScalar w) {
738    // check for <= 0 or NaN with this test
739    if (!(w > 0)) {
740        this->lineTo(x2, y2);
741    } else if (!SkScalarIsFinite(w)) {
742        this->lineTo(x1, y1);
743        this->lineTo(x2, y2);
744    } else if (SK_Scalar1 == w) {
745        this->quadTo(x1, y1, x2, y2);
746    } else {
747        SkDEBUGCODE(this->validate();)
748
749        this->injectMoveToIfNeeded();
750
751        SkPathRef::Editor ed(&fPathRef);
752        SkPoint* pts = ed.growForVerb(kConic_Verb, w);
753        pts[0].set(x1, y1);
754        pts[1].set(x2, y2);
755
756        DIRTY_AFTER_EDIT;
757    }
758}
759
760void SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2,
761                      SkScalar w) {
762    this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
763    SkPoint pt;
764    this->getLastPt(&pt);
765    this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w);
766}
767
768void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
769                     SkScalar x3, SkScalar y3) {
770    SkDEBUGCODE(this->validate();)
771
772    this->injectMoveToIfNeeded();
773
774    SkPathRef::Editor ed(&fPathRef);
775    SkPoint* pts = ed.growForVerb(kCubic_Verb);
776    pts[0].set(x1, y1);
777    pts[1].set(x2, y2);
778    pts[2].set(x3, y3);
779
780    DIRTY_AFTER_EDIT;
781}
782
783void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
784                      SkScalar x3, SkScalar y3) {
785    this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
786    SkPoint pt;
787    this->getLastPt(&pt);
788    this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
789                  pt.fX + x3, pt.fY + y3);
790}
791
792void SkPath::close() {
793    SkDEBUGCODE(this->validate();)
794
795    int count = fPathRef->countVerbs();
796    if (count > 0) {
797        switch (fPathRef->atVerb(count - 1)) {
798            case kLine_Verb:
799            case kQuad_Verb:
800            case kConic_Verb:
801            case kCubic_Verb:
802            case kMove_Verb: {
803                SkPathRef::Editor ed(&fPathRef);
804                ed.growForVerb(kClose_Verb);
805                break;
806            }
807            case kClose_Verb:
808                // don't add a close if it's the first verb or a repeat
809                break;
810            default:
811                SkDEBUGFAIL("unexpected verb");
812                break;
813        }
814    }
815
816    // signal that we need a moveTo to follow us (unless we're done)
817#if 0
818    if (fLastMoveToIndex >= 0) {
819        fLastMoveToIndex = ~fLastMoveToIndex;
820    }
821#else
822    fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
823#endif
824}
825
826///////////////////////////////////////////////////////////////////////////////
827
828static void assert_known_direction(int dir) {
829    SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir);
830}
831
832void SkPath::addRect(const SkRect& rect, Direction dir) {
833    this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir);
834}
835
836void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
837                     SkScalar bottom, Direction dir) {
838    assert_known_direction(dir);
839    fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
840    SkAutoDisableDirectionCheck addc(this);
841
842    SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom);
843
844    this->incReserve(5);
845
846    this->moveTo(left, top);
847    if (dir == kCCW_Direction) {
848        this->lineTo(left, bottom);
849        this->lineTo(right, bottom);
850        this->lineTo(right, top);
851    } else {
852        this->lineTo(right, top);
853        this->lineTo(right, bottom);
854        this->lineTo(left, bottom);
855    }
856    this->close();
857}
858
859void SkPath::addPoly(const SkPoint pts[], int count, bool close) {
860    SkDEBUGCODE(this->validate();)
861    if (count <= 0) {
862        return;
863    }
864
865    fLastMoveToIndex = fPathRef->countPoints();
866
867    // +close makes room for the extra kClose_Verb
868    SkPathRef::Editor ed(&fPathRef, count+close, count);
869
870    ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
871    if (count > 1) {
872        SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1);
873        memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
874    }
875
876    if (close) {
877        ed.growForVerb(kClose_Verb);
878    }
879
880    DIRTY_AFTER_EDIT;
881    SkDEBUGCODE(this->validate();)
882}
883
884#include "SkGeometry.h"
885
886static int build_arc_points(const SkRect& oval, SkScalar startAngle,
887                            SkScalar sweepAngle,
888                            SkPoint pts[kSkBuildQuadArcStorage]) {
889
890    if (0 == sweepAngle &&
891        (0 == startAngle || SkIntToScalar(360) == startAngle)) {
892        // Chrome uses this path to move into and out of ovals. If not
893        // treated as a special case the moves can distort the oval's
894        // bounding box (and break the circle special case).
895        pts[0].set(oval.fRight, oval.centerY());
896        return 1;
897    } else if (0 == oval.width() && 0 == oval.height()) {
898        // Chrome will sometimes create 0 radius round rects. Having degenerate
899        // quad segments in the path prevents the path from being recognized as
900        // a rect.
901        // TODO: optimizing the case where only one of width or height is zero
902        // should also be considered. This case, however, doesn't seem to be
903        // as common as the single point case.
904        pts[0].set(oval.fRight, oval.fTop);
905        return 1;
906    }
907
908    SkVector start, stop;
909
910    start.fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &start.fX);
911    stop.fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle),
912                             &stop.fX);
913
914    /*  If the sweep angle is nearly (but less than) 360, then due to precision
915        loss in radians-conversion and/or sin/cos, we may end up with coincident
916        vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
917        of drawing a nearly complete circle (good).
918             e.g. canvas.drawArc(0, 359.99, ...)
919             -vs- canvas.drawArc(0, 359.9, ...)
920        We try to detect this edge case, and tweak the stop vector
921     */
922    if (start == stop) {
923        SkScalar sw = SkScalarAbs(sweepAngle);
924        if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
925            SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle);
926            // make a guess at a tiny angle (in radians) to tweak by
927            SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
928            // not sure how much will be enough, so we use a loop
929            do {
930                stopRad -= deltaRad;
931                stop.fY = SkScalarSinCos(stopRad, &stop.fX);
932            } while (start == stop);
933        }
934    }
935
936    SkMatrix    matrix;
937
938    matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
939    matrix.postTranslate(oval.centerX(), oval.centerY());
940
941    return SkBuildQuadArc(start, stop,
942                          sweepAngle > 0 ? kCW_SkRotationDirection :
943                                           kCCW_SkRotationDirection,
944                          &matrix, pts);
945}
946
947void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
948                          Direction dir) {
949    SkRRect rrect;
950    rrect.setRectRadii(rect, (const SkVector*) radii);
951    this->addRRect(rrect, dir);
952}
953
954/* The inline clockwise and counterclockwise round rect quad approximations
955   make it easier to see the symmetry patterns used by add corner quads.
956Clockwise                                                     corner value
957    path->lineTo(rect.fLeft,           rect.fTop    + ry);    0 upper left
958    path->quadTo(rect.fLeft,           rect.fTop    + offPtY,
959                 rect.fLeft  + midPtX, rect.fTop    + midPtY);
960    path->quadTo(rect.fLeft  + offPtX, rect.fTop,
961                 rect.fLeft  + rx,     rect.fTop);
962
963    path->lineTo(rect.fRight - rx,     rect.fTop);            1 upper right
964    path->quadTo(rect.fRight - offPtX, rect.fTop,
965                 rect.fRight - midPtX, rect.fTop    + midPtY);
966    path->quadTo(rect.fRight,          rect.fTop    + offPtY,
967                 rect.fRight,          rect.fTop    + ry);
968
969    path->lineTo(rect.fRight,          rect.fBottom - ry);    2 lower right
970    path->quadTo(rect.fRight,          rect.fBottom - offPtY,
971                 rect.fRight - midPtX, rect.fBottom - midPtY);
972    path->quadTo(rect.fRight - offPtX, rect.fBottom,
973                 rect.fRight - rx,     rect.fBottom);
974
975    path->lineTo(rect.fLeft  + rx,     rect.fBottom);         3 lower left
976    path->quadTo(rect.fLeft  + offPtX, rect.fBottom,
977                 rect.fLeft  + midPtX, rect.fBottom - midPtY);
978    path->quadTo(rect.fLeft,           rect.fBottom - offPtY,
979                 rect.fLeft,           rect.fBottom - ry);
980
981Counterclockwise
982    path->lineTo(rect.fLeft,           rect.fBottom - ry);    3 lower left
983    path->quadTo(rect.fLeft,           rect.fBottom - offPtY,
984                 rect.fLeft  + midPtX, rect.fBottom - midPtY);
985    path->quadTo(rect.fLeft  + offPtX, rect.fBottom,
986                 rect.fLeft  + rx,     rect.fBottom);
987
988    path->lineTo(rect.fRight - rx,     rect.fBottom);         2 lower right
989    path->quadTo(rect.fRight - offPtX, rect.fBottom,
990                 rect.fRight - midPtX, rect.fBottom - midPtY);
991    path->quadTo(rect.fRight,          rect.fBottom - offPtY,
992                 rect.fRight,          rect.fBottom - ry);
993
994    path->lineTo(rect.fRight,          rect.fTop    + ry);    1 upper right
995    path->quadTo(rect.fRight,          rect.fTop    + offPtY,
996                 rect.fRight - midPtX, rect.fTop    + midPtY);
997    path->quadTo(rect.fRight - offPtX, rect.fTop,
998                 rect.fRight - rx,     rect.fTop);
999
1000    path->lineTo(rect.fLeft  + rx,     rect.fTop);            0 upper left
1001    path->quadTo(rect.fLeft  + offPtX, rect.fTop,
1002                 rect.fLeft  + midPtX, rect.fTop    + midPtY);
1003    path->quadTo(rect.fLeft,           rect.fTop    + offPtY,
1004                 rect.fLeft,           rect.fTop    + ry);
1005*/
1006static void add_corner_quads(SkPath* path, const SkRRect& rrect,
1007                             SkRRect::Corner corner, SkPath::Direction dir) {
1008    const SkRect& rect = rrect.rect();
1009    const SkVector& radii = rrect.radii(corner);
1010    SkScalar rx = radii.fX;
1011    SkScalar ry = radii.fY;
1012    // The mid point of the quadratic arc approximation is half way between the two
1013    // control points.
1014    const SkScalar mid = 1 - (SK_Scalar1 + SK_ScalarTanPIOver8) / 2;
1015    SkScalar midPtX = rx * mid;
1016    SkScalar midPtY = ry * mid;
1017    const SkScalar control = 1 - SK_ScalarTanPIOver8;
1018    SkScalar offPtX = rx * control;
1019    SkScalar offPtY = ry * control;
1020    static const int kCornerPts = 5;
1021    SkScalar xOff[kCornerPts];
1022    SkScalar yOff[kCornerPts];
1023
1024    if ((corner & 1) == (dir == SkPath::kCCW_Direction)) {  // corners always alternate direction
1025        SkASSERT(dir == SkPath::kCCW_Direction
1026             ? corner == SkRRect::kLowerLeft_Corner || corner == SkRRect::kUpperRight_Corner
1027             : corner == SkRRect::kUpperLeft_Corner || corner == SkRRect::kLowerRight_Corner);
1028        xOff[0] = xOff[1] = 0;
1029        xOff[2] = midPtX;
1030        xOff[3] = offPtX;
1031        xOff[4] = rx;
1032        yOff[0] = ry;
1033        yOff[1] = offPtY;
1034        yOff[2] = midPtY;
1035        yOff[3] = yOff[4] = 0;
1036    } else {
1037        xOff[0] = rx;
1038        xOff[1] = offPtX;
1039        xOff[2] = midPtX;
1040        xOff[3] = xOff[4] = 0;
1041        yOff[0] = yOff[1] = 0;
1042        yOff[2] = midPtY;
1043        yOff[3] = offPtY;
1044        yOff[4] = ry;
1045    }
1046    if ((corner - 1) & 2) {
1047        SkASSERT(corner == SkRRect::kLowerLeft_Corner || corner == SkRRect::kUpperLeft_Corner);
1048        for (int i = 0; i < kCornerPts; ++i) {
1049            xOff[i] = rect.fLeft + xOff[i];
1050        }
1051    } else {
1052        SkASSERT(corner == SkRRect::kLowerRight_Corner || corner == SkRRect::kUpperRight_Corner);
1053        for (int i = 0; i < kCornerPts; ++i) {
1054            xOff[i] = rect.fRight - xOff[i];
1055        }
1056    }
1057    if (corner < SkRRect::kLowerRight_Corner) {
1058        for (int i = 0; i < kCornerPts; ++i) {
1059            yOff[i] = rect.fTop + yOff[i];
1060        }
1061    } else {
1062        for (int i = 0; i < kCornerPts; ++i) {
1063            yOff[i] = rect.fBottom - yOff[i];
1064        }
1065    }
1066
1067    SkPoint lastPt;
1068    SkAssertResult(path->getLastPt(&lastPt));
1069    if (lastPt.fX != xOff[0] || lastPt.fY != yOff[0]) {
1070        path->lineTo(xOff[0], yOff[0]);
1071    }
1072    if (rx || ry) {
1073        path->quadTo(xOff[1], yOff[1], xOff[2], yOff[2]);
1074        path->quadTo(xOff[3], yOff[3], xOff[4], yOff[4]);
1075    } else {
1076        path->lineTo(xOff[2], yOff[2]);
1077        path->lineTo(xOff[4], yOff[4]);
1078    }
1079}
1080
1081void SkPath::addRRect(const SkRRect& rrect, Direction dir) {
1082    assert_known_direction(dir);
1083
1084    if (rrect.isEmpty()) {
1085        return;
1086    }
1087
1088    const SkRect& bounds = rrect.getBounds();
1089
1090    if (rrect.isRect()) {
1091        this->addRect(bounds, dir);
1092    } else if (rrect.isOval()) {
1093        this->addOval(bounds, dir);
1094    } else {
1095        fDirection = this->hasOnlyMoveTos() ? dir : kUnknown_Direction;
1096
1097        SkAutoPathBoundsUpdate apbu(this, bounds);
1098        SkAutoDisableDirectionCheck addc(this);
1099
1100        this->incReserve(21);
1101        if (kCW_Direction == dir) {
1102            this->moveTo(bounds.fLeft,
1103                         bounds.fBottom - rrect.fRadii[SkRRect::kLowerLeft_Corner].fY);
1104            add_corner_quads(this, rrect, SkRRect::kUpperLeft_Corner, dir);
1105            add_corner_quads(this, rrect, SkRRect::kUpperRight_Corner, dir);
1106            add_corner_quads(this, rrect, SkRRect::kLowerRight_Corner, dir);
1107            add_corner_quads(this, rrect, SkRRect::kLowerLeft_Corner, dir);
1108        } else {
1109            this->moveTo(bounds.fLeft,
1110                         bounds.fTop + rrect.fRadii[SkRRect::kUpperLeft_Corner].fY);
1111            add_corner_quads(this, rrect, SkRRect::kLowerLeft_Corner, dir);
1112            add_corner_quads(this, rrect, SkRRect::kLowerRight_Corner, dir);
1113            add_corner_quads(this, rrect, SkRRect::kUpperRight_Corner, dir);
1114            add_corner_quads(this, rrect, SkRRect::kUpperLeft_Corner, dir);
1115        }
1116        this->close();
1117    }
1118}
1119
1120bool SkPath::hasOnlyMoveTos() const {
1121    int count = fPathRef->countVerbs();
1122    const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin();
1123    for (int i = 0; i < count; ++i) {
1124        if (*verbs == kLine_Verb ||
1125            *verbs == kQuad_Verb ||
1126            *verbs == kConic_Verb ||
1127            *verbs == kCubic_Verb) {
1128            return false;
1129        }
1130        ++verbs;
1131    }
1132    return true;
1133}
1134
1135void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
1136                          Direction dir) {
1137    assert_known_direction(dir);
1138
1139    if (rx < 0 || ry < 0) {
1140        SkErrorInternals::SetError( kInvalidArgument_SkError,
1141                                    "I got %f and %f as radii to SkPath::AddRoundRect, "
1142                                    "but negative radii are not allowed.",
1143                                    SkScalarToDouble(rx), SkScalarToDouble(ry) );
1144        return;
1145    }
1146
1147    SkRRect rrect;
1148    rrect.setRectXY(rect, rx, ry);
1149    this->addRRect(rrect, dir);
1150}
1151
1152void SkPath::addOval(const SkRect& oval, Direction dir) {
1153    assert_known_direction(dir);
1154
1155    /* If addOval() is called after previous moveTo(),
1156       this path is still marked as an oval. This is used to
1157       fit into WebKit's calling sequences.
1158       We can't simply check isEmpty() in this case, as additional
1159       moveTo() would mark the path non empty.
1160     */
1161    bool isOval = hasOnlyMoveTos();
1162    if (isOval) {
1163        fDirection = dir;
1164    } else {
1165        fDirection = kUnknown_Direction;
1166    }
1167
1168    SkAutoDisableDirectionCheck addc(this);
1169
1170    SkAutoPathBoundsUpdate apbu(this, oval);
1171
1172    SkScalar    cx = oval.centerX();
1173    SkScalar    cy = oval.centerY();
1174    SkScalar    rx = SkScalarHalf(oval.width());
1175    SkScalar    ry = SkScalarHalf(oval.height());
1176
1177    SkScalar    sx = SkScalarMul(rx, SK_ScalarTanPIOver8);
1178    SkScalar    sy = SkScalarMul(ry, SK_ScalarTanPIOver8);
1179    SkScalar    mx = SkScalarMul(rx, SK_ScalarRoot2Over2);
1180    SkScalar    my = SkScalarMul(ry, SK_ScalarRoot2Over2);
1181
1182    /*
1183        To handle imprecision in computing the center and radii, we revert to
1184        the provided bounds when we can (i.e. use oval.fLeft instead of cx-rx)
1185        to ensure that we don't exceed the oval's bounds *ever*, since we want
1186        to use oval for our fast-bounds, rather than have to recompute it.
1187    */
1188    const SkScalar L = oval.fLeft;      // cx - rx
1189    const SkScalar T = oval.fTop;       // cy - ry
1190    const SkScalar R = oval.fRight;     // cx + rx
1191    const SkScalar B = oval.fBottom;    // cy + ry
1192
1193    this->incReserve(17);   // 8 quads + close
1194    this->moveTo(R, cy);
1195    if (dir == kCCW_Direction) {
1196        this->quadTo(      R, cy - sy, cx + mx, cy - my);
1197        this->quadTo(cx + sx,       T, cx     ,       T);
1198        this->quadTo(cx - sx,       T, cx - mx, cy - my);
1199        this->quadTo(      L, cy - sy,       L, cy     );
1200        this->quadTo(      L, cy + sy, cx - mx, cy + my);
1201        this->quadTo(cx - sx,       B, cx     ,       B);
1202        this->quadTo(cx + sx,       B, cx + mx, cy + my);
1203        this->quadTo(      R, cy + sy,       R, cy     );
1204    } else {
1205        this->quadTo(      R, cy + sy, cx + mx, cy + my);
1206        this->quadTo(cx + sx,       B, cx     ,       B);
1207        this->quadTo(cx - sx,       B, cx - mx, cy + my);
1208        this->quadTo(      L, cy + sy,       L, cy     );
1209        this->quadTo(      L, cy - sy, cx - mx, cy - my);
1210        this->quadTo(cx - sx,       T, cx     ,       T);
1211        this->quadTo(cx + sx,       T, cx + mx, cy - my);
1212        this->quadTo(      R, cy - sy,       R, cy     );
1213    }
1214    this->close();
1215
1216    SkPathRef::Editor ed(&fPathRef);
1217
1218    ed.setIsOval(isOval);
1219}
1220
1221void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
1222    if (r > 0) {
1223        SkRect  rect;
1224        rect.set(x - r, y - r, x + r, y + r);
1225        this->addOval(rect, dir);
1226    }
1227}
1228
1229void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
1230                   bool forceMoveTo) {
1231    if (oval.width() < 0 || oval.height() < 0) {
1232        return;
1233    }
1234
1235    SkPoint pts[kSkBuildQuadArcStorage];
1236    int count = build_arc_points(oval, startAngle, sweepAngle, pts);
1237    SkASSERT((count & 1) == 1);
1238
1239    if (fPathRef->countVerbs() == 0) {
1240        forceMoveTo = true;
1241    }
1242    this->incReserve(count);
1243    forceMoveTo ? this->moveTo(pts[0]) : this->lineTo(pts[0]);
1244    for (int i = 1; i < count; i += 2) {
1245        this->quadTo(pts[i], pts[i+1]);
1246    }
1247}
1248
1249void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
1250    if (oval.isEmpty() || 0 == sweepAngle) {
1251        return;
1252    }
1253
1254    const SkScalar kFullCircleAngle = SkIntToScalar(360);
1255
1256    if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
1257        this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction);
1258        return;
1259    }
1260
1261    SkPoint pts[kSkBuildQuadArcStorage];
1262    int count = build_arc_points(oval, startAngle, sweepAngle, pts);
1263
1264    SkDEBUGCODE(this->validate();)
1265    SkASSERT(count & 1);
1266
1267    fLastMoveToIndex = fPathRef->countPoints();
1268
1269    SkPathRef::Editor ed(&fPathRef, 1+(count-1)/2, count);
1270
1271    ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
1272    if (count > 1) {
1273        SkPoint* p = ed.growForRepeatedVerb(kQuad_Verb, (count-1)/2);
1274        memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
1275    }
1276
1277    DIRTY_AFTER_EDIT;
1278    SkDEBUGCODE(this->validate();)
1279}
1280
1281/*
1282    Need to handle the case when the angle is sharp, and our computed end-points
1283    for the arc go behind pt1 and/or p2...
1284*/
1285void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
1286                   SkScalar radius) {
1287    SkVector    before, after;
1288
1289    // need to know our prev pt so we can construct tangent vectors
1290    {
1291        SkPoint start;
1292        this->getLastPt(&start);
1293        // Handle degenerate cases by adding a line to the first point and
1294        // bailing out.
1295        if ((x1 == start.fX && y1 == start.fY) ||
1296            (x1 == x2 && y1 == y2) ||
1297            radius == 0) {
1298            this->lineTo(x1, y1);
1299            return;
1300        }
1301        before.setNormalize(x1 - start.fX, y1 - start.fY);
1302        after.setNormalize(x2 - x1, y2 - y1);
1303    }
1304
1305    SkScalar cosh = SkPoint::DotProduct(before, after);
1306    SkScalar sinh = SkPoint::CrossProduct(before, after);
1307
1308    if (SkScalarNearlyZero(sinh)) {   // angle is too tight
1309        this->lineTo(x1, y1);
1310        return;
1311    }
1312
1313    SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh);
1314    if (dist < 0) {
1315        dist = -dist;
1316    }
1317
1318    SkScalar xx = x1 - SkScalarMul(dist, before.fX);
1319    SkScalar yy = y1 - SkScalarMul(dist, before.fY);
1320    SkRotationDirection arcDir;
1321
1322    // now turn before/after into normals
1323    if (sinh > 0) {
1324        before.rotateCCW();
1325        after.rotateCCW();
1326        arcDir = kCW_SkRotationDirection;
1327    } else {
1328        before.rotateCW();
1329        after.rotateCW();
1330        arcDir = kCCW_SkRotationDirection;
1331    }
1332
1333    SkMatrix    matrix;
1334    SkPoint     pts[kSkBuildQuadArcStorage];
1335
1336    matrix.setScale(radius, radius);
1337    matrix.postTranslate(xx - SkScalarMul(radius, before.fX),
1338                         yy - SkScalarMul(radius, before.fY));
1339
1340    int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts);
1341
1342    this->incReserve(count);
1343    // [xx,yy] == pts[0]
1344    this->lineTo(xx, yy);
1345    for (int i = 1; i < count; i += 2) {
1346        this->quadTo(pts[i], pts[i+1]);
1347    }
1348}
1349
1350///////////////////////////////////////////////////////////////////////////////
1351
1352void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
1353    SkMatrix matrix;
1354
1355    matrix.setTranslate(dx, dy);
1356    this->addPath(path, matrix, mode);
1357}
1358
1359void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) {
1360    SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints());
1361
1362    RawIter iter(path);
1363    SkPoint pts[4];
1364    Verb    verb;
1365
1366    SkMatrix::MapPtsProc proc = matrix.getMapPtsProc();
1367    bool firstVerb = true;
1368    while ((verb = iter.next(pts)) != kDone_Verb) {
1369        switch (verb) {
1370            case kMove_Verb:
1371                proc(matrix, &pts[0], &pts[0], 1);
1372                if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) {
1373                    injectMoveToIfNeeded(); // In case last contour is closed
1374                    this->lineTo(pts[0]);
1375                } else {
1376                    this->moveTo(pts[0]);
1377                }
1378                break;
1379            case kLine_Verb:
1380                proc(matrix, &pts[1], &pts[1], 1);
1381                this->lineTo(pts[1]);
1382                break;
1383            case kQuad_Verb:
1384                proc(matrix, &pts[1], &pts[1], 2);
1385                this->quadTo(pts[1], pts[2]);
1386                break;
1387            case kConic_Verb:
1388                proc(matrix, &pts[1], &pts[1], 2);
1389                this->conicTo(pts[1], pts[2], iter.conicWeight());
1390                break;
1391            case kCubic_Verb:
1392                proc(matrix, &pts[1], &pts[1], 3);
1393                this->cubicTo(pts[1], pts[2], pts[3]);
1394                break;
1395            case kClose_Verb:
1396                this->close();
1397                break;
1398            default:
1399                SkDEBUGFAIL("unknown verb");
1400        }
1401        firstVerb = false;
1402    }
1403}
1404
1405///////////////////////////////////////////////////////////////////////////////
1406
1407static int pts_in_verb(unsigned verb) {
1408    static const uint8_t gPtsInVerb[] = {
1409        1,  // kMove
1410        1,  // kLine
1411        2,  // kQuad
1412        2,  // kConic
1413        3,  // kCubic
1414        0,  // kClose
1415        0   // kDone
1416    };
1417
1418    SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
1419    return gPtsInVerb[verb];
1420}
1421
1422// ignore the last point of the 1st contour
1423void SkPath::reversePathTo(const SkPath& path) {
1424    int i, vcount = path.fPathRef->countVerbs();
1425    // exit early if the path is empty, or just has a moveTo.
1426    if (vcount < 2) {
1427        return;
1428    }
1429
1430    SkPathRef::Editor(&fPathRef, vcount, path.countPoints());
1431
1432    const uint8_t*  verbs = path.fPathRef->verbs();
1433    const SkPoint*  pts = path.fPathRef->points();
1434    const SkScalar* conicWeights = path.fPathRef->conicWeights();
1435
1436    SkASSERT(verbs[~0] == kMove_Verb);
1437    for (i = 1; i < vcount; ++i) {
1438        unsigned v = verbs[~i];
1439        int n = pts_in_verb(v);
1440        if (n == 0) {
1441            break;
1442        }
1443        pts += n;
1444        conicWeights += (SkPath::kConic_Verb == v);
1445    }
1446
1447    while (--i > 0) {
1448        switch (verbs[~i]) {
1449            case kLine_Verb:
1450                this->lineTo(pts[-1].fX, pts[-1].fY);
1451                break;
1452            case kQuad_Verb:
1453                this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY);
1454                break;
1455            case kConic_Verb:
1456                this->conicTo(pts[-1], pts[-2], *--conicWeights);
1457                break;
1458            case kCubic_Verb:
1459                this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY,
1460                              pts[-3].fX, pts[-3].fY);
1461                break;
1462            default:
1463                SkDEBUGFAIL("bad verb");
1464                break;
1465        }
1466        pts -= pts_in_verb(verbs[~i]);
1467    }
1468}
1469
1470void SkPath::reverseAddPath(const SkPath& src) {
1471    SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs());
1472
1473    const SkPoint* pts = src.fPathRef->pointsEnd();
1474    // we will iterator through src's verbs backwards
1475    const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb
1476    const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb
1477    const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd();
1478
1479    bool needMove = true;
1480    bool needClose = false;
1481    while (verbs < verbsEnd) {
1482        uint8_t v = *(verbs++);
1483        int n = pts_in_verb(v);
1484
1485        if (needMove) {
1486            --pts;
1487            this->moveTo(pts->fX, pts->fY);
1488            needMove = false;
1489        }
1490        pts -= n;
1491        switch (v) {
1492            case kMove_Verb:
1493                if (needClose) {
1494                    this->close();
1495                    needClose = false;
1496                }
1497                needMove = true;
1498                pts += 1;   // so we see the point in "if (needMove)" above
1499                break;
1500            case kLine_Verb:
1501                this->lineTo(pts[0]);
1502                break;
1503            case kQuad_Verb:
1504                this->quadTo(pts[1], pts[0]);
1505                break;
1506            case kConic_Verb:
1507                this->conicTo(pts[1], pts[0], *--conicWeights);
1508                break;
1509            case kCubic_Verb:
1510                this->cubicTo(pts[2], pts[1], pts[0]);
1511                break;
1512            case kClose_Verb:
1513                needClose = true;
1514                break;
1515            default:
1516                SkDEBUGFAIL("unexpected verb");
1517        }
1518    }
1519}
1520
1521///////////////////////////////////////////////////////////////////////////////
1522
1523void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
1524    SkMatrix    matrix;
1525
1526    matrix.setTranslate(dx, dy);
1527    this->transform(matrix, dst);
1528}
1529
1530#include "SkGeometry.h"
1531
1532static void subdivide_quad_to(SkPath* path, const SkPoint pts[3],
1533                              int level = 2) {
1534    if (--level >= 0) {
1535        SkPoint tmp[5];
1536
1537        SkChopQuadAtHalf(pts, tmp);
1538        subdivide_quad_to(path, &tmp[0], level);
1539        subdivide_quad_to(path, &tmp[2], level);
1540    } else {
1541        path->quadTo(pts[1], pts[2]);
1542    }
1543}
1544
1545static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
1546                               int level = 2) {
1547    if (--level >= 0) {
1548        SkPoint tmp[7];
1549
1550        SkChopCubicAtHalf(pts, tmp);
1551        subdivide_cubic_to(path, &tmp[0], level);
1552        subdivide_cubic_to(path, &tmp[3], level);
1553    } else {
1554        path->cubicTo(pts[1], pts[2], pts[3]);
1555    }
1556}
1557
1558void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
1559    SkDEBUGCODE(this->validate();)
1560    if (dst == NULL) {
1561        dst = (SkPath*)this;
1562    }
1563
1564    if (matrix.hasPerspective()) {
1565        SkPath  tmp;
1566        tmp.fFillType = fFillType;
1567
1568        SkPath::Iter    iter(*this, false);
1569        SkPoint         pts[4];
1570        SkPath::Verb    verb;
1571
1572        while ((verb = iter.next(pts, false)) != kDone_Verb) {
1573            switch (verb) {
1574                case kMove_Verb:
1575                    tmp.moveTo(pts[0]);
1576                    break;
1577                case kLine_Verb:
1578                    tmp.lineTo(pts[1]);
1579                    break;
1580                case kQuad_Verb:
1581                    subdivide_quad_to(&tmp, pts);
1582                    break;
1583                case kConic_Verb:
1584                    SkDEBUGFAIL("TODO: compute new weight");
1585                    tmp.conicTo(pts[1], pts[2], iter.conicWeight());
1586                    break;
1587                case kCubic_Verb:
1588                    subdivide_cubic_to(&tmp, pts);
1589                    break;
1590                case kClose_Verb:
1591                    tmp.close();
1592                    break;
1593                default:
1594                    SkDEBUGFAIL("unknown verb");
1595                    break;
1596            }
1597        }
1598
1599        dst->swap(tmp);
1600        SkPathRef::Editor ed(&dst->fPathRef);
1601        matrix.mapPoints(ed.points(), ed.pathRef()->countPoints());
1602        dst->fDirection = kUnknown_Direction;
1603    } else {
1604        SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix);
1605
1606        if (this != dst) {
1607            dst->fFillType = fFillType;
1608            dst->fConvexity = fConvexity;
1609        }
1610
1611        if (kUnknown_Direction == fDirection) {
1612            dst->fDirection = kUnknown_Direction;
1613        } else {
1614            SkScalar det2x2 =
1615                SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) -
1616                SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY));
1617            if (det2x2 < 0) {
1618                dst->fDirection = SkPath::OppositeDirection(static_cast<Direction>(fDirection));
1619            } else if (det2x2 > 0) {
1620                dst->fDirection = fDirection;
1621            } else {
1622                dst->fConvexity = kUnknown_Convexity;
1623                dst->fDirection = kUnknown_Direction;
1624            }
1625        }
1626
1627        SkDEBUGCODE(dst->validate();)
1628    }
1629}
1630
1631///////////////////////////////////////////////////////////////////////////////
1632///////////////////////////////////////////////////////////////////////////////
1633
1634enum SegmentState {
1635    kEmptyContour_SegmentState,   // The current contour is empty. We may be
1636                                  // starting processing or we may have just
1637                                  // closed a contour.
1638    kAfterMove_SegmentState,      // We have seen a move, but nothing else.
1639    kAfterPrimitive_SegmentState  // We have seen a primitive but not yet
1640                                  // closed the path. Also the initial state.
1641};
1642
1643SkPath::Iter::Iter() {
1644#ifdef SK_DEBUG
1645    fPts = NULL;
1646    fConicWeights = NULL;
1647    fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1648    fForceClose = fCloseLine = false;
1649    fSegmentState = kEmptyContour_SegmentState;
1650#endif
1651    // need to init enough to make next() harmlessly return kDone_Verb
1652    fVerbs = NULL;
1653    fVerbStop = NULL;
1654    fNeedClose = false;
1655}
1656
1657SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
1658    this->setPath(path, forceClose);
1659}
1660
1661void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
1662    fPts = path.fPathRef->points();
1663    fVerbs = path.fPathRef->verbs();
1664    fVerbStop = path.fPathRef->verbsMemBegin();
1665    fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind
1666    fLastPt.fX = fLastPt.fY = 0;
1667    fMoveTo.fX = fMoveTo.fY = 0;
1668    fForceClose = SkToU8(forceClose);
1669    fNeedClose = false;
1670    fSegmentState = kEmptyContour_SegmentState;
1671}
1672
1673bool SkPath::Iter::isClosedContour() const {
1674    if (fVerbs == NULL || fVerbs == fVerbStop) {
1675        return false;
1676    }
1677    if (fForceClose) {
1678        return true;
1679    }
1680
1681    const uint8_t* verbs = fVerbs;
1682    const uint8_t* stop = fVerbStop;
1683
1684    if (kMove_Verb == *(verbs - 1)) {
1685        verbs -= 1; // skip the initial moveto
1686    }
1687
1688    while (verbs > stop) {
1689        // verbs points one beyond the current verb, decrement first.
1690        unsigned v = *(--verbs);
1691        if (kMove_Verb == v) {
1692            break;
1693        }
1694        if (kClose_Verb == v) {
1695            return true;
1696        }
1697    }
1698    return false;
1699}
1700
1701SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
1702    SkASSERT(pts);
1703    if (fLastPt != fMoveTo) {
1704        // A special case: if both points are NaN, SkPoint::operation== returns
1705        // false, but the iterator expects that they are treated as the same.
1706        // (consider SkPoint is a 2-dimension float point).
1707        if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
1708            SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
1709            return kClose_Verb;
1710        }
1711
1712        pts[0] = fLastPt;
1713        pts[1] = fMoveTo;
1714        fLastPt = fMoveTo;
1715        fCloseLine = true;
1716        return kLine_Verb;
1717    } else {
1718        pts[0] = fMoveTo;
1719        return kClose_Verb;
1720    }
1721}
1722
1723const SkPoint& SkPath::Iter::cons_moveTo() {
1724    if (fSegmentState == kAfterMove_SegmentState) {
1725        // Set the first return pt to the move pt
1726        fSegmentState = kAfterPrimitive_SegmentState;
1727        return fMoveTo;
1728    } else {
1729        SkASSERT(fSegmentState == kAfterPrimitive_SegmentState);
1730         // Set the first return pt to the last pt of the previous primitive.
1731        return fPts[-1];
1732    }
1733}
1734
1735void SkPath::Iter::consumeDegenerateSegments() {
1736    // We need to step over anything that will not move the current draw point
1737    // forward before the next move is seen
1738    const uint8_t* lastMoveVerb = 0;
1739    const SkPoint* lastMovePt = 0;
1740    SkPoint lastPt = fLastPt;
1741    while (fVerbs != fVerbStop) {
1742        unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb
1743        switch (verb) {
1744            case kMove_Verb:
1745                // Keep a record of this most recent move
1746                lastMoveVerb = fVerbs;
1747                lastMovePt = fPts;
1748                lastPt = fPts[0];
1749                fVerbs--;
1750                fPts++;
1751                break;
1752
1753            case kClose_Verb:
1754                // A close when we are in a segment is always valid except when it
1755                // follows a move which follows a segment.
1756                if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) {
1757                    return;
1758                }
1759                // A close at any other time must be ignored
1760                fVerbs--;
1761                break;
1762
1763            case kLine_Verb:
1764                if (!IsLineDegenerate(lastPt, fPts[0])) {
1765                    if (lastMoveVerb) {
1766                        fVerbs = lastMoveVerb;
1767                        fPts = lastMovePt;
1768                        return;
1769                    }
1770                    return;
1771                }
1772                // Ignore this line and continue
1773                fVerbs--;
1774                fPts++;
1775                break;
1776
1777            case kConic_Verb:
1778            case kQuad_Verb:
1779                if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1])) {
1780                    if (lastMoveVerb) {
1781                        fVerbs = lastMoveVerb;
1782                        fPts = lastMovePt;
1783                        return;
1784                    }
1785                    return;
1786                }
1787                // Ignore this line and continue
1788                fVerbs--;
1789                fPts += 2;
1790                fConicWeights += (kConic_Verb == verb);
1791                break;
1792
1793            case kCubic_Verb:
1794                if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2])) {
1795                    if (lastMoveVerb) {
1796                        fVerbs = lastMoveVerb;
1797                        fPts = lastMovePt;
1798                        return;
1799                    }
1800                    return;
1801                }
1802                // Ignore this line and continue
1803                fVerbs--;
1804                fPts += 3;
1805                break;
1806
1807            default:
1808                SkDEBUGFAIL("Should never see kDone_Verb");
1809        }
1810    }
1811}
1812
1813SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) {
1814    SkASSERT(ptsParam);
1815
1816    if (fVerbs == fVerbStop) {
1817        // Close the curve if requested and if there is some curve to close
1818        if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) {
1819            if (kLine_Verb == this->autoClose(ptsParam)) {
1820                return kLine_Verb;
1821            }
1822            fNeedClose = false;
1823            return kClose_Verb;
1824        }
1825        return kDone_Verb;
1826    }
1827
1828    // fVerbs is one beyond the current verb, decrement first
1829    unsigned verb = *(--fVerbs);
1830    const SkPoint* SK_RESTRICT srcPts = fPts;
1831    SkPoint* SK_RESTRICT       pts = ptsParam;
1832
1833    switch (verb) {
1834        case kMove_Verb:
1835            if (fNeedClose) {
1836                fVerbs++; // move back one verb
1837                verb = this->autoClose(pts);
1838                if (verb == kClose_Verb) {
1839                    fNeedClose = false;
1840                }
1841                return (Verb)verb;
1842            }
1843            if (fVerbs == fVerbStop) {    // might be a trailing moveto
1844                return kDone_Verb;
1845            }
1846            fMoveTo = *srcPts;
1847            pts[0] = *srcPts;
1848            srcPts += 1;
1849            fSegmentState = kAfterMove_SegmentState;
1850            fLastPt = fMoveTo;
1851            fNeedClose = fForceClose;
1852            break;
1853        case kLine_Verb:
1854            pts[0] = this->cons_moveTo();
1855            pts[1] = srcPts[0];
1856            fLastPt = srcPts[0];
1857            fCloseLine = false;
1858            srcPts += 1;
1859            break;
1860        case kConic_Verb:
1861            fConicWeights += 1;
1862            // fall-through
1863        case kQuad_Verb:
1864            pts[0] = this->cons_moveTo();
1865            memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1866            fLastPt = srcPts[1];
1867            srcPts += 2;
1868            break;
1869        case kCubic_Verb:
1870            pts[0] = this->cons_moveTo();
1871            memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1872            fLastPt = srcPts[2];
1873            srcPts += 3;
1874            break;
1875        case kClose_Verb:
1876            verb = this->autoClose(pts);
1877            if (verb == kLine_Verb) {
1878                fVerbs++; // move back one verb
1879            } else {
1880                fNeedClose = false;
1881                fSegmentState = kEmptyContour_SegmentState;
1882            }
1883            fLastPt = fMoveTo;
1884            break;
1885    }
1886    fPts = srcPts;
1887    return (Verb)verb;
1888}
1889
1890///////////////////////////////////////////////////////////////////////////////
1891
1892SkPath::RawIter::RawIter() {
1893#ifdef SK_DEBUG
1894    fPts = NULL;
1895    fConicWeights = NULL;
1896    fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1897#endif
1898    // need to init enough to make next() harmlessly return kDone_Verb
1899    fVerbs = NULL;
1900    fVerbStop = NULL;
1901}
1902
1903SkPath::RawIter::RawIter(const SkPath& path) {
1904    this->setPath(path);
1905}
1906
1907void SkPath::RawIter::setPath(const SkPath& path) {
1908    fPts = path.fPathRef->points();
1909    fVerbs = path.fPathRef->verbs();
1910    fVerbStop = path.fPathRef->verbsMemBegin();
1911    fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind
1912    fMoveTo.fX = fMoveTo.fY = 0;
1913    fLastPt.fX = fLastPt.fY = 0;
1914}
1915
1916SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) {
1917    SkASSERT(pts);
1918    if (fVerbs == fVerbStop) {
1919        return kDone_Verb;
1920    }
1921
1922    // fVerbs points one beyond next verb so decrement first.
1923    unsigned verb = *(--fVerbs);
1924    const SkPoint* srcPts = fPts;
1925
1926    switch (verb) {
1927        case kMove_Verb:
1928            pts[0] = *srcPts;
1929            fMoveTo = srcPts[0];
1930            fLastPt = fMoveTo;
1931            srcPts += 1;
1932            break;
1933        case kLine_Verb:
1934            pts[0] = fLastPt;
1935            pts[1] = srcPts[0];
1936            fLastPt = srcPts[0];
1937            srcPts += 1;
1938            break;
1939        case kConic_Verb:
1940            fConicWeights += 1;
1941            // fall-through
1942        case kQuad_Verb:
1943            pts[0] = fLastPt;
1944            memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1945            fLastPt = srcPts[1];
1946            srcPts += 2;
1947            break;
1948        case kCubic_Verb:
1949            pts[0] = fLastPt;
1950            memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1951            fLastPt = srcPts[2];
1952            srcPts += 3;
1953            break;
1954        case kClose_Verb:
1955            fLastPt = fMoveTo;
1956            pts[0] = fMoveTo;
1957            break;
1958    }
1959    fPts = srcPts;
1960    return (Verb)verb;
1961}
1962
1963///////////////////////////////////////////////////////////////////////////////
1964
1965/*
1966    Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]]
1967*/
1968
1969size_t SkPath::writeToMemory(void* storage) const {
1970    SkDEBUGCODE(this->validate();)
1971
1972    if (NULL == storage) {
1973        const int byteCount = sizeof(int32_t) + fPathRef->writeSize();
1974        return SkAlign4(byteCount);
1975    }
1976
1977    SkWBuffer   buffer(storage);
1978
1979    int32_t packed = (fConvexity << kConvexity_SerializationShift) |
1980                     (fFillType << kFillType_SerializationShift) |
1981                     (fDirection << kDirection_SerializationShift);
1982
1983    buffer.write32(packed);
1984
1985    fPathRef->writeToBuffer(&buffer);
1986
1987    buffer.padToAlign4();
1988    return buffer.pos();
1989}
1990
1991size_t SkPath::readFromMemory(const void* storage, size_t length) {
1992    SkRBufferWithSizeCheck buffer(storage, length);
1993
1994    int32_t packed;
1995    if (!buffer.readS32(&packed)) {
1996        return 0;
1997    }
1998
1999    fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF;
2000    fFillType = (packed >> kFillType_SerializationShift) & 0xFF;
2001    fDirection = (packed >> kDirection_SerializationShift) & 0x3;
2002    SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer);
2003
2004    size_t sizeRead = 0;
2005    if (buffer.isValid()) {
2006        fPathRef.reset(pathRef);
2007        SkDEBUGCODE(this->validate();)
2008        buffer.skipToAlign4();
2009        sizeRead = buffer.pos();
2010    } else if (pathRef) {
2011        // If the buffer is not valid, pathRef should be NULL
2012        sk_throw();
2013    }
2014    return sizeRead;
2015}
2016
2017///////////////////////////////////////////////////////////////////////////////
2018
2019#include "SkString.h"
2020#include "SkStream.h"
2021
2022static void append_scalar(SkString* str, SkScalar value, bool dumpAsHex) {
2023    if (dumpAsHex) {
2024        str->appendf("SkBits2Float(0x%08x)", SkFloat2Bits(value));
2025        return;
2026    }
2027    SkString tmp;
2028    tmp.printf("%g", value);
2029    if (tmp.contains('.')) {
2030        tmp.appendUnichar('f');
2031    }
2032    str->append(tmp);
2033}
2034
2035static void append_params(SkString* str, const char label[], const SkPoint pts[],
2036                          int count, bool dumpAsHex, SkScalar conicWeight = -1) {
2037    str->append(label);
2038    str->append("(");
2039
2040    const SkScalar* values = &pts[0].fX;
2041    count *= 2;
2042
2043    for (int i = 0; i < count; ++i) {
2044        append_scalar(str, values[i], dumpAsHex);
2045        if (i < count - 1) {
2046            str->append(", ");
2047        }
2048    }
2049    if (conicWeight >= 0) {
2050        str->append(", ");
2051        append_scalar(str, conicWeight, dumpAsHex);
2052    }
2053    str->append(");");
2054    if (dumpAsHex) {
2055        str->append("  // ");
2056        for (int i = 0; i < count; ++i) {
2057            append_scalar(str, values[i], false);
2058            if (i < count - 1) {
2059                str->append(", ");
2060            }
2061        }
2062        if (conicWeight >= 0) {
2063            str->append(", ");
2064            append_scalar(str, conicWeight, false);
2065        }
2066    }
2067    str->append("\n");
2068}
2069
2070void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const {
2071    Iter    iter(*this, forceClose);
2072    SkPoint pts[4];
2073    Verb    verb;
2074
2075    if (!wStream) {
2076        SkDebugf("path: forceClose=%s\n", forceClose ? "true" : "false");
2077    }
2078    SkString builder;
2079
2080    while ((verb = iter.next(pts, false)) != kDone_Verb) {
2081        switch (verb) {
2082            case kMove_Verb:
2083                append_params(&builder, "path.moveTo", &pts[0], 1, dumpAsHex);
2084                break;
2085            case kLine_Verb:
2086                append_params(&builder, "path.lineTo", &pts[1], 1, dumpAsHex);
2087                break;
2088            case kQuad_Verb:
2089                append_params(&builder, "path.quadTo", &pts[1], 2, dumpAsHex);
2090                break;
2091            case kConic_Verb:
2092                append_params(&builder, "path.conicTo", &pts[1], 2, dumpAsHex, iter.conicWeight());
2093                break;
2094            case kCubic_Verb:
2095                append_params(&builder, "path.cubicTo", &pts[1], 3, dumpAsHex);
2096                break;
2097            case kClose_Verb:
2098                builder.append("path.close();\n");
2099                break;
2100            default:
2101                SkDebugf("  path: UNKNOWN VERB %d, aborting dump...\n", verb);
2102                verb = kDone_Verb;  // stop the loop
2103                break;
2104        }
2105    }
2106    if (wStream) {
2107        wStream->writeText(builder.c_str());
2108    } else {
2109        SkDebugf("%s", builder.c_str());
2110    }
2111}
2112
2113void SkPath::dump() const {
2114    this->dump(NULL, false, false);
2115}
2116
2117void SkPath::dumpHex() const {
2118    this->dump(NULL, false, true);
2119}
2120
2121#ifdef SK_DEBUG
2122void SkPath::validate() const {
2123    SkASSERT(this != NULL);
2124    SkASSERT((fFillType & ~3) == 0);
2125
2126#ifdef SK_DEBUG_PATH
2127    if (!fBoundsIsDirty) {
2128        SkRect bounds;
2129
2130        bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
2131        SkASSERT(SkToBool(fIsFinite) == isFinite);
2132
2133        if (fPathRef->countPoints() <= 1) {
2134            // if we're empty, fBounds may be empty but translated, so we can't
2135            // necessarily compare to bounds directly
2136            // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
2137            // be [2, 2, 2, 2]
2138            SkASSERT(bounds.isEmpty());
2139            SkASSERT(fBounds.isEmpty());
2140        } else {
2141            if (bounds.isEmpty()) {
2142                SkASSERT(fBounds.isEmpty());
2143            } else {
2144                if (!fBounds.isEmpty()) {
2145                    SkASSERT(fBounds.contains(bounds));
2146                }
2147            }
2148        }
2149    }
2150#endif // SK_DEBUG_PATH
2151}
2152#endif // SK_DEBUG
2153
2154///////////////////////////////////////////////////////////////////////////////
2155
2156static int sign(SkScalar x) { return x < 0; }
2157#define kValueNeverReturnedBySign   2
2158
2159enum DirChange {
2160    kLeft_DirChange,
2161    kRight_DirChange,
2162    kStraight_DirChange,
2163    kBackwards_DirChange,
2164
2165    kInvalid_DirChange
2166};
2167
2168
2169static bool almost_equal(SkScalar compA, SkScalar compB) {
2170    // The error epsilon was empirically derived; worse case round rects
2171    // with a mid point outset by 2x float epsilon in tests had an error
2172    // of 12.
2173    const int epsilon = 16;
2174    if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
2175        return false;
2176    }
2177    // no need to check for small numbers because SkPath::Iter has removed degenerate values
2178    int aBits = SkFloatAs2sCompliment(compA);
2179    int bBits = SkFloatAs2sCompliment(compB);
2180    return aBits < bBits + epsilon && bBits < aBits + epsilon;
2181}
2182
2183static DirChange direction_change(const SkPoint& lastPt, const SkVector& curPt,
2184                                  const SkVector& lastVec, const SkVector& curVec) {
2185    SkScalar cross = SkPoint::CrossProduct(lastVec, curVec);
2186
2187    SkScalar smallest = SkTMin(curPt.fX, SkTMin(curPt.fY, SkTMin(lastPt.fX, lastPt.fY)));
2188    SkScalar largest = SkTMax(curPt.fX, SkTMax(curPt.fY, SkTMax(lastPt.fX, lastPt.fY)));
2189    largest = SkTMax(largest, -smallest);
2190
2191    if (!almost_equal(largest, largest + cross)) {
2192        int sign = SkScalarSignAsInt(cross);
2193        if (sign) {
2194            return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
2195        }
2196    }
2197
2198    if (!SkScalarNearlyZero(lastVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2199        !SkScalarNearlyZero(curVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2200        lastVec.dot(curVec) < 0.0f) {
2201        return kBackwards_DirChange;
2202    }
2203
2204    return kStraight_DirChange;
2205}
2206
2207// only valid for a single contour
2208struct Convexicator {
2209    Convexicator()
2210    : fPtCount(0)
2211    , fConvexity(SkPath::kConvex_Convexity)
2212    , fDirection(SkPath::kUnknown_Direction) {
2213        fExpectedDir = kInvalid_DirChange;
2214        // warnings
2215        fLastPt.set(0, 0);
2216        fCurrPt.set(0, 0);
2217        fLastVec.set(0, 0);
2218        fFirstVec.set(0, 0);
2219
2220        fDx = fDy = 0;
2221        fSx = fSy = kValueNeverReturnedBySign;
2222    }
2223
2224    SkPath::Convexity getConvexity() const { return fConvexity; }
2225
2226    /** The direction returned is only valid if the path is determined convex */
2227    SkPath::Direction getDirection() const { return fDirection; }
2228
2229    void addPt(const SkPoint& pt) {
2230        if (SkPath::kConcave_Convexity == fConvexity) {
2231            return;
2232        }
2233
2234        if (0 == fPtCount) {
2235            fCurrPt = pt;
2236            ++fPtCount;
2237        } else {
2238            SkVector vec = pt - fCurrPt;
2239            if (vec.fX || vec.fY) {
2240                fLastPt = fCurrPt;
2241                fCurrPt = pt;
2242                if (++fPtCount == 2) {
2243                    fFirstVec = fLastVec = vec;
2244                } else {
2245                    SkASSERT(fPtCount > 2);
2246                    this->addVec(vec);
2247                }
2248
2249                int sx = sign(vec.fX);
2250                int sy = sign(vec.fY);
2251                fDx += (sx != fSx);
2252                fDy += (sy != fSy);
2253                fSx = sx;
2254                fSy = sy;
2255
2256                if (fDx > 3 || fDy > 3) {
2257                    fConvexity = SkPath::kConcave_Convexity;
2258                }
2259            }
2260        }
2261    }
2262
2263    void close() {
2264        if (fPtCount > 2) {
2265            this->addVec(fFirstVec);
2266        }
2267    }
2268
2269private:
2270    void addVec(const SkVector& vec) {
2271        SkASSERT(vec.fX || vec.fY);
2272        DirChange dir = direction_change(fLastPt, fCurrPt, fLastVec, vec);
2273        switch (dir) {
2274            case kLeft_DirChange:       // fall through
2275            case kRight_DirChange:
2276                if (kInvalid_DirChange == fExpectedDir) {
2277                    fExpectedDir = dir;
2278                    fDirection = (kRight_DirChange == dir) ? SkPath::kCW_Direction
2279                                                           : SkPath::kCCW_Direction;
2280                } else if (dir != fExpectedDir) {
2281                    fConvexity = SkPath::kConcave_Convexity;
2282                    fDirection = SkPath::kUnknown_Direction;
2283                }
2284                fLastVec = vec;
2285                break;
2286            case kStraight_DirChange:
2287                break;
2288            case kBackwards_DirChange:
2289                fLastVec = vec;
2290                break;
2291            case kInvalid_DirChange:
2292                SkFAIL("Use of invalid direction change flag");
2293                break;
2294        }
2295    }
2296
2297    SkPoint             fLastPt;
2298    SkPoint             fCurrPt;
2299    // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product
2300    // value with the current vec is deemed to be of a significant value.
2301    SkVector            fLastVec, fFirstVec;
2302    int                 fPtCount;   // non-degenerate points
2303    DirChange           fExpectedDir;
2304    SkPath::Convexity   fConvexity;
2305    SkPath::Direction   fDirection;
2306    int                 fDx, fDy, fSx, fSy;
2307};
2308
2309SkPath::Convexity SkPath::internalGetConvexity() const {
2310    SkASSERT(kUnknown_Convexity == fConvexity);
2311    SkPoint         pts[4];
2312    SkPath::Verb    verb;
2313    SkPath::Iter    iter(*this, true);
2314
2315    int             contourCount = 0;
2316    int             count;
2317    Convexicator    state;
2318
2319    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
2320        switch (verb) {
2321            case kMove_Verb:
2322                if (++contourCount > 1) {
2323                    fConvexity = kConcave_Convexity;
2324                    return kConcave_Convexity;
2325                }
2326                pts[1] = pts[0];
2327                count = 1;
2328                break;
2329            case kLine_Verb: count = 1; break;
2330            case kQuad_Verb: count = 2; break;
2331            case kConic_Verb: count = 2; break;
2332            case kCubic_Verb: count = 3; break;
2333            case kClose_Verb:
2334                state.close();
2335                count = 0;
2336                break;
2337            default:
2338                SkDEBUGFAIL("bad verb");
2339                fConvexity = kConcave_Convexity;
2340                return kConcave_Convexity;
2341        }
2342
2343        for (int i = 1; i <= count; i++) {
2344            state.addPt(pts[i]);
2345        }
2346        // early exit
2347        if (kConcave_Convexity == state.getConvexity()) {
2348            fConvexity = kConcave_Convexity;
2349            return kConcave_Convexity;
2350        }
2351    }
2352    fConvexity = state.getConvexity();
2353    if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) {
2354        fDirection = state.getDirection();
2355    }
2356    return static_cast<Convexity>(fConvexity);
2357}
2358
2359///////////////////////////////////////////////////////////////////////////////
2360
2361class ContourIter {
2362public:
2363    ContourIter(const SkPathRef& pathRef);
2364
2365    bool done() const { return fDone; }
2366    // if !done() then these may be called
2367    int count() const { return fCurrPtCount; }
2368    const SkPoint* pts() const { return fCurrPt; }
2369    void next();
2370
2371private:
2372    int fCurrPtCount;
2373    const SkPoint* fCurrPt;
2374    const uint8_t* fCurrVerb;
2375    const uint8_t* fStopVerbs;
2376    const SkScalar* fCurrConicWeight;
2377    bool fDone;
2378    SkDEBUGCODE(int fContourCounter;)
2379};
2380
2381ContourIter::ContourIter(const SkPathRef& pathRef) {
2382    fStopVerbs = pathRef.verbsMemBegin();
2383    fDone = false;
2384    fCurrPt = pathRef.points();
2385    fCurrVerb = pathRef.verbs();
2386    fCurrConicWeight = pathRef.conicWeights();
2387    fCurrPtCount = 0;
2388    SkDEBUGCODE(fContourCounter = 0;)
2389    this->next();
2390}
2391
2392void ContourIter::next() {
2393    if (fCurrVerb <= fStopVerbs) {
2394        fDone = true;
2395    }
2396    if (fDone) {
2397        return;
2398    }
2399
2400    // skip pts of prev contour
2401    fCurrPt += fCurrPtCount;
2402
2403    SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
2404    int ptCount = 1;    // moveTo
2405    const uint8_t* verbs = fCurrVerb;
2406
2407    for (--verbs; verbs > fStopVerbs; --verbs) {
2408        switch (verbs[~0]) {
2409            case SkPath::kMove_Verb:
2410                goto CONTOUR_END;
2411            case SkPath::kLine_Verb:
2412                ptCount += 1;
2413                break;
2414            case SkPath::kConic_Verb:
2415                fCurrConicWeight += 1;
2416                // fall-through
2417            case SkPath::kQuad_Verb:
2418                ptCount += 2;
2419                break;
2420            case SkPath::kCubic_Verb:
2421                ptCount += 3;
2422                break;
2423            case SkPath::kClose_Verb:
2424                break;
2425            default:
2426                SkDEBUGFAIL("unexpected verb");
2427                break;
2428        }
2429    }
2430CONTOUR_END:
2431    fCurrPtCount = ptCount;
2432    fCurrVerb = verbs;
2433    SkDEBUGCODE(++fContourCounter;)
2434}
2435
2436// returns cross product of (p1 - p0) and (p2 - p0)
2437static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
2438    SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
2439    // We may get 0 when the above subtracts underflow. We expect this to be
2440    // very rare and lazily promote to double.
2441    if (0 == cross) {
2442        double p0x = SkScalarToDouble(p0.fX);
2443        double p0y = SkScalarToDouble(p0.fY);
2444
2445        double p1x = SkScalarToDouble(p1.fX);
2446        double p1y = SkScalarToDouble(p1.fY);
2447
2448        double p2x = SkScalarToDouble(p2.fX);
2449        double p2y = SkScalarToDouble(p2.fY);
2450
2451        cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
2452                                 (p1y - p0y) * (p2x - p0x));
2453
2454    }
2455    return cross;
2456}
2457
2458// Returns the first pt with the maximum Y coordinate
2459static int find_max_y(const SkPoint pts[], int count) {
2460    SkASSERT(count > 0);
2461    SkScalar max = pts[0].fY;
2462    int firstIndex = 0;
2463    for (int i = 1; i < count; ++i) {
2464        SkScalar y = pts[i].fY;
2465        if (y > max) {
2466            max = y;
2467            firstIndex = i;
2468        }
2469    }
2470    return firstIndex;
2471}
2472
2473static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
2474    int i = index;
2475    for (;;) {
2476        i = (i + inc) % n;
2477        if (i == index) {   // we wrapped around, so abort
2478            break;
2479        }
2480        if (pts[index] != pts[i]) { // found a different point, success!
2481            break;
2482        }
2483    }
2484    return i;
2485}
2486
2487/**
2488 *  Starting at index, and moving forward (incrementing), find the xmin and
2489 *  xmax of the contiguous points that have the same Y.
2490 */
2491static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
2492                               int* maxIndexPtr) {
2493    const SkScalar y = pts[index].fY;
2494    SkScalar min = pts[index].fX;
2495    SkScalar max = min;
2496    int minIndex = index;
2497    int maxIndex = index;
2498    for (int i = index + 1; i < n; ++i) {
2499        if (pts[i].fY != y) {
2500            break;
2501        }
2502        SkScalar x = pts[i].fX;
2503        if (x < min) {
2504            min = x;
2505            minIndex = i;
2506        } else if (x > max) {
2507            max = x;
2508            maxIndex = i;
2509        }
2510    }
2511    *maxIndexPtr = maxIndex;
2512    return minIndex;
2513}
2514
2515static void crossToDir(SkScalar cross, SkPath::Direction* dir) {
2516    *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
2517}
2518
2519/*
2520 *  We loop through all contours, and keep the computed cross-product of the
2521 *  contour that contained the global y-max. If we just look at the first
2522 *  contour, we may find one that is wound the opposite way (correctly) since
2523 *  it is the interior of a hole (e.g. 'o'). Thus we must find the contour
2524 *  that is outer most (or at least has the global y-max) before we can consider
2525 *  its cross product.
2526 */
2527bool SkPath::cheapComputeDirection(Direction* dir) const {
2528    if (kUnknown_Direction != fDirection) {
2529        *dir = static_cast<Direction>(fDirection);
2530        return true;
2531    }
2532
2533    // don't want to pay the cost for computing this if it
2534    // is unknown, so we don't call isConvex()
2535    if (kConvex_Convexity == this->getConvexityOrUnknown()) {
2536        SkASSERT(kUnknown_Direction == fDirection);
2537        *dir = static_cast<Direction>(fDirection);
2538        return false;
2539    }
2540
2541    ContourIter iter(*fPathRef.get());
2542
2543    // initialize with our logical y-min
2544    SkScalar ymax = this->getBounds().fTop;
2545    SkScalar ymaxCross = 0;
2546
2547    for (; !iter.done(); iter.next()) {
2548        int n = iter.count();
2549        if (n < 3) {
2550            continue;
2551        }
2552
2553        const SkPoint* pts = iter.pts();
2554        SkScalar cross = 0;
2555        int index = find_max_y(pts, n);
2556        if (pts[index].fY < ymax) {
2557            continue;
2558        }
2559
2560        // If there is more than 1 distinct point at the y-max, we take the
2561        // x-min and x-max of them and just subtract to compute the dir.
2562        if (pts[(index + 1) % n].fY == pts[index].fY) {
2563            int maxIndex;
2564            int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
2565            if (minIndex == maxIndex) {
2566                goto TRY_CROSSPROD;
2567            }
2568            SkASSERT(pts[minIndex].fY == pts[index].fY);
2569            SkASSERT(pts[maxIndex].fY == pts[index].fY);
2570            SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
2571            // we just subtract the indices, and let that auto-convert to
2572            // SkScalar, since we just want - or + to signal the direction.
2573            cross = minIndex - maxIndex;
2574        } else {
2575            TRY_CROSSPROD:
2576            // Find a next and prev index to use for the cross-product test,
2577            // but we try to find pts that form non-zero vectors from pts[index]
2578            //
2579            // Its possible that we can't find two non-degenerate vectors, so
2580            // we have to guard our search (e.g. all the pts could be in the
2581            // same place).
2582
2583            // we pass n - 1 instead of -1 so we don't foul up % operator by
2584            // passing it a negative LH argument.
2585            int prev = find_diff_pt(pts, index, n, n - 1);
2586            if (prev == index) {
2587                // completely degenerate, skip to next contour
2588                continue;
2589            }
2590            int next = find_diff_pt(pts, index, n, 1);
2591            SkASSERT(next != index);
2592            cross = cross_prod(pts[prev], pts[index], pts[next]);
2593            // if we get a zero and the points are horizontal, then we look at the spread in
2594            // x-direction. We really should continue to walk away from the degeneracy until
2595            // there is a divergence.
2596            if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
2597                // construct the subtract so we get the correct Direction below
2598                cross = pts[index].fX - pts[next].fX;
2599            }
2600        }
2601
2602        if (cross) {
2603            // record our best guess so far
2604            ymax = pts[index].fY;
2605            ymaxCross = cross;
2606        }
2607    }
2608    if (ymaxCross) {
2609        crossToDir(ymaxCross, dir);
2610        fDirection = *dir;
2611        return true;
2612    } else {
2613        return false;
2614    }
2615}
2616
2617///////////////////////////////////////////////////////////////////////////////
2618
2619static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
2620                                 SkScalar D, SkScalar t) {
2621    return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
2622}
2623
2624static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2625                               SkScalar t) {
2626    SkScalar A = c3 + 3*(c1 - c2) - c0;
2627    SkScalar B = 3*(c2 - c1 - c1 + c0);
2628    SkScalar C = 3*(c1 - c0);
2629    SkScalar D = c0;
2630    return eval_cubic_coeff(A, B, C, D, t);
2631}
2632
2633/*  Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
2634 t value such that cubic(t) = target
2635 */
2636static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2637                            SkScalar target, SkScalar* t) {
2638    //   SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
2639    SkASSERT(c0 < target && target < c3);
2640
2641    SkScalar D = c0 - target;
2642    SkScalar A = c3 + 3*(c1 - c2) - c0;
2643    SkScalar B = 3*(c2 - c1 - c1 + c0);
2644    SkScalar C = 3*(c1 - c0);
2645
2646    const SkScalar TOLERANCE = SK_Scalar1 / 4096;
2647    SkScalar minT = 0;
2648    SkScalar maxT = SK_Scalar1;
2649    SkScalar mid;
2650    int i;
2651    for (i = 0; i < 16; i++) {
2652        mid = SkScalarAve(minT, maxT);
2653        SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
2654        if (delta < 0) {
2655            minT = mid;
2656            delta = -delta;
2657        } else {
2658            maxT = mid;
2659        }
2660        if (delta < TOLERANCE) {
2661            break;
2662        }
2663    }
2664    *t = mid;
2665}
2666
2667template <size_t N> static void find_minmax(const SkPoint pts[],
2668                                            SkScalar* minPtr, SkScalar* maxPtr) {
2669    SkScalar min, max;
2670    min = max = pts[0].fX;
2671    for (size_t i = 1; i < N; ++i) {
2672        min = SkMinScalar(min, pts[i].fX);
2673        max = SkMaxScalar(max, pts[i].fX);
2674    }
2675    *minPtr = min;
2676    *maxPtr = max;
2677}
2678
2679static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2680    SkPoint storage[4];
2681
2682    int dir = 1;
2683    if (pts[0].fY > pts[3].fY) {
2684        storage[0] = pts[3];
2685        storage[1] = pts[2];
2686        storage[2] = pts[1];
2687        storage[3] = pts[0];
2688        pts = storage;
2689        dir = -1;
2690    }
2691    if (y < pts[0].fY || y >= pts[3].fY) {
2692        return 0;
2693    }
2694
2695    // quickreject or quickaccept
2696    SkScalar min, max;
2697    find_minmax<4>(pts, &min, &max);
2698    if (x < min) {
2699        return 0;
2700    }
2701    if (x > max) {
2702        return dir;
2703    }
2704
2705    // compute the actual x(t) value
2706    SkScalar t;
2707    chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t);
2708    SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
2709    return xt < x ? dir : 0;
2710}
2711
2712static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2713    SkPoint dst[10];
2714    int n = SkChopCubicAtYExtrema(pts, dst);
2715    int w = 0;
2716    for (int i = 0; i <= n; ++i) {
2717        w += winding_mono_cubic(&dst[i * 3], x, y);
2718    }
2719    return w;
2720}
2721
2722static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2723    SkScalar y0 = pts[0].fY;
2724    SkScalar y2 = pts[2].fY;
2725
2726    int dir = 1;
2727    if (y0 > y2) {
2728        SkTSwap(y0, y2);
2729        dir = -1;
2730    }
2731    if (y < y0 || y >= y2) {
2732        return 0;
2733    }
2734
2735    // bounds check on X (not required. is it faster?)
2736#if 0
2737    if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
2738        return 0;
2739    }
2740#endif
2741
2742    SkScalar roots[2];
2743    int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
2744                                2 * (pts[1].fY - pts[0].fY),
2745                                pts[0].fY - y,
2746                                roots);
2747    SkASSERT(n <= 1);
2748    SkScalar xt;
2749    if (0 == n) {
2750        SkScalar mid = SkScalarAve(y0, y2);
2751        // Need [0] and [2] if dir == 1
2752        // and  [2] and [0] if dir == -1
2753        xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
2754    } else {
2755        SkScalar t = roots[0];
2756        SkScalar C = pts[0].fX;
2757        SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
2758        SkScalar B = 2 * (pts[1].fX - C);
2759        xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
2760    }
2761    return xt < x ? dir : 0;
2762}
2763
2764static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
2765    //    return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
2766    if (y0 == y1) {
2767        return true;
2768    }
2769    if (y0 < y1) {
2770        return y1 <= y2;
2771    } else {
2772        return y1 >= y2;
2773    }
2774}
2775
2776static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2777    SkPoint dst[5];
2778    int     n = 0;
2779
2780    if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
2781        n = SkChopQuadAtYExtrema(pts, dst);
2782        pts = dst;
2783    }
2784    int w = winding_mono_quad(pts, x, y);
2785    if (n > 0) {
2786        w += winding_mono_quad(&pts[2], x, y);
2787    }
2788    return w;
2789}
2790
2791static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
2792    SkScalar x0 = pts[0].fX;
2793    SkScalar y0 = pts[0].fY;
2794    SkScalar x1 = pts[1].fX;
2795    SkScalar y1 = pts[1].fY;
2796
2797    SkScalar dy = y1 - y0;
2798
2799    int dir = 1;
2800    if (y0 > y1) {
2801        SkTSwap(y0, y1);
2802        dir = -1;
2803    }
2804    if (y < y0 || y >= y1) {
2805        return 0;
2806    }
2807
2808    SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
2809    SkScalarMul(dy, x - pts[0].fX);
2810
2811    if (SkScalarSignAsInt(cross) == dir) {
2812        dir = 0;
2813    }
2814    return dir;
2815}
2816
2817static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
2818    return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
2819}
2820
2821bool SkPath::contains(SkScalar x, SkScalar y) const {
2822    bool isInverse = this->isInverseFillType();
2823    if (this->isEmpty()) {
2824        return isInverse;
2825    }
2826
2827    if (!contains_inclusive(this->getBounds(), x, y)) {
2828        return isInverse;
2829    }
2830
2831    SkPath::Iter iter(*this, true);
2832    bool done = false;
2833    int w = 0;
2834    do {
2835        SkPoint pts[4];
2836        switch (iter.next(pts, false)) {
2837            case SkPath::kMove_Verb:
2838            case SkPath::kClose_Verb:
2839                break;
2840            case SkPath::kLine_Verb:
2841                w += winding_line(pts, x, y);
2842                break;
2843            case SkPath::kQuad_Verb:
2844                w += winding_quad(pts, x, y);
2845                break;
2846            case SkPath::kConic_Verb:
2847                SkASSERT(0);
2848                break;
2849            case SkPath::kCubic_Verb:
2850                w += winding_cubic(pts, x, y);
2851                break;
2852            case SkPath::kDone_Verb:
2853                done = true;
2854                break;
2855       }
2856    } while (!done);
2857
2858    switch (this->getFillType()) {
2859        case SkPath::kEvenOdd_FillType:
2860        case SkPath::kInverseEvenOdd_FillType:
2861            w &= 1;
2862            break;
2863        default:
2864            break;
2865    }
2866    return SkToBool(w);
2867}
2868