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