SkPath.cpp revision e05fed0d6339c63c8cceff74af0b8d120c07e54c 
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 "SkStringUtils.h"
2025#include "SkStream.h"
2026
2027static void append_params(SkString* str, const char label[], const SkPoint pts[],
2028                          int count, SkScalarAsStringType strType, SkScalar conicWeight = -1) {
2029    str->append(label);
2030    str->append("(");
2031
2032    const SkScalar* values = &pts[0].fX;
2033    count *= 2;
2034
2035    for (int i = 0; i < count; ++i) {
2036        SkAppendScalar(str, values[i], strType);
2037        if (i < count - 1) {
2038            str->append(", ");
2039        }
2040    }
2041    if (conicWeight >= 0) {
2042        str->append(", ");
2043        SkAppendScalar(str, conicWeight, strType);
2044    }
2045    str->append(");");
2046    if (kHex_SkScalarAsStringType == strType) {
2047        str->append("  // ");
2048        for (int i = 0; i < count; ++i) {
2049            SkAppendScalarDec(str, values[i]);
2050            if (i < count - 1) {
2051                str->append(", ");
2052            }
2053        }
2054        if (conicWeight >= 0) {
2055            str->append(", ");
2056            SkAppendScalarDec(str, conicWeight);
2057        }
2058    }
2059    str->append("\n");
2060}
2061
2062void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const {
2063    SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
2064    Iter    iter(*this, forceClose);
2065    SkPoint pts[4];
2066    Verb    verb;
2067
2068    if (!wStream) {
2069        SkDebugf("path: forceClose=%s\n", forceClose ? "true" : "false");
2070    }
2071    SkString builder;
2072
2073    while ((verb = iter.next(pts, false)) != kDone_Verb) {
2074        switch (verb) {
2075            case kMove_Verb:
2076                append_params(&builder, "path.moveTo", &pts[0], 1, asType);
2077                break;
2078            case kLine_Verb:
2079                append_params(&builder, "path.lineTo", &pts[1], 1, asType);
2080                break;
2081            case kQuad_Verb:
2082                append_params(&builder, "path.quadTo", &pts[1], 2, asType);
2083                break;
2084            case kConic_Verb:
2085                append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight());
2086                break;
2087            case kCubic_Verb:
2088                append_params(&builder, "path.cubicTo", &pts[1], 3, asType);
2089                break;
2090            case kClose_Verb:
2091                builder.append("path.close();\n");
2092                break;
2093            default:
2094                SkDebugf("  path: UNKNOWN VERB %d, aborting dump...\n", verb);
2095                verb = kDone_Verb;  // stop the loop
2096                break;
2097        }
2098    }
2099    if (wStream) {
2100        wStream->writeText(builder.c_str());
2101    } else {
2102        SkDebugf("%s", builder.c_str());
2103    }
2104}
2105
2106void SkPath::dump() const {
2107    this->dump(NULL, false, false);
2108}
2109
2110void SkPath::dumpHex() const {
2111    this->dump(NULL, false, true);
2112}
2113
2114#ifdef SK_DEBUG
2115void SkPath::validate() const {
2116    SkASSERT(this != NULL);
2117    SkASSERT((fFillType & ~3) == 0);
2118
2119#ifdef SK_DEBUG_PATH
2120    if (!fBoundsIsDirty) {
2121        SkRect bounds;
2122
2123        bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
2124        SkASSERT(SkToBool(fIsFinite) == isFinite);
2125
2126        if (fPathRef->countPoints() <= 1) {
2127            // if we're empty, fBounds may be empty but translated, so we can't
2128            // necessarily compare to bounds directly
2129            // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
2130            // be [2, 2, 2, 2]
2131            SkASSERT(bounds.isEmpty());
2132            SkASSERT(fBounds.isEmpty());
2133        } else {
2134            if (bounds.isEmpty()) {
2135                SkASSERT(fBounds.isEmpty());
2136            } else {
2137                if (!fBounds.isEmpty()) {
2138                    SkASSERT(fBounds.contains(bounds));
2139                }
2140            }
2141        }
2142    }
2143#endif // SK_DEBUG_PATH
2144}
2145#endif // SK_DEBUG
2146
2147///////////////////////////////////////////////////////////////////////////////
2148
2149static int sign(SkScalar x) { return x < 0; }
2150#define kValueNeverReturnedBySign   2
2151
2152enum DirChange {
2153    kLeft_DirChange,
2154    kRight_DirChange,
2155    kStraight_DirChange,
2156    kBackwards_DirChange,
2157
2158    kInvalid_DirChange
2159};
2160
2161
2162static bool almost_equal(SkScalar compA, SkScalar compB) {
2163    // The error epsilon was empirically derived; worse case round rects
2164    // with a mid point outset by 2x float epsilon in tests had an error
2165    // of 12.
2166    const int epsilon = 16;
2167    if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
2168        return false;
2169    }
2170    // no need to check for small numbers because SkPath::Iter has removed degenerate values
2171    int aBits = SkFloatAs2sCompliment(compA);
2172    int bBits = SkFloatAs2sCompliment(compB);
2173    return aBits < bBits + epsilon && bBits < aBits + epsilon;
2174}
2175
2176static DirChange direction_change(const SkPoint& lastPt, const SkVector& curPt,
2177                                  const SkVector& lastVec, const SkVector& curVec) {
2178    SkScalar cross = SkPoint::CrossProduct(lastVec, curVec);
2179
2180    SkScalar smallest = SkTMin(curPt.fX, SkTMin(curPt.fY, SkTMin(lastPt.fX, lastPt.fY)));
2181    SkScalar largest = SkTMax(curPt.fX, SkTMax(curPt.fY, SkTMax(lastPt.fX, lastPt.fY)));
2182    largest = SkTMax(largest, -smallest);
2183
2184    if (!almost_equal(largest, largest + cross)) {
2185        int sign = SkScalarSignAsInt(cross);
2186        if (sign) {
2187            return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
2188        }
2189    }
2190
2191    if (!SkScalarNearlyZero(lastVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2192        !SkScalarNearlyZero(curVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2193        lastVec.dot(curVec) < 0.0f) {
2194        return kBackwards_DirChange;
2195    }
2196
2197    return kStraight_DirChange;
2198}
2199
2200// only valid for a single contour
2201struct Convexicator {
2202    Convexicator()
2203    : fPtCount(0)
2204    , fConvexity(SkPath::kConvex_Convexity)
2205    , fDirection(SkPath::kUnknown_Direction)
2206    , fIsFinite(true) {
2207        fExpectedDir = kInvalid_DirChange;
2208        // warnings
2209        fLastPt.set(0, 0);
2210        fCurrPt.set(0, 0);
2211        fLastVec.set(0, 0);
2212        fFirstVec.set(0, 0);
2213
2214        fDx = fDy = 0;
2215        fSx = fSy = kValueNeverReturnedBySign;
2216    }
2217
2218    SkPath::Convexity getConvexity() const { return fConvexity; }
2219
2220    /** The direction returned is only valid if the path is determined convex */
2221    SkPath::Direction getDirection() const { return fDirection; }
2222
2223    void addPt(const SkPoint& pt) {
2224        if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) {
2225            return;
2226        }
2227
2228        if (0 == fPtCount) {
2229            fCurrPt = pt;
2230            ++fPtCount;
2231        } else {
2232            SkVector vec = pt - fCurrPt;
2233            SkScalar lengthSqd = vec.lengthSqd();
2234            if (!SkScalarIsFinite(lengthSqd)) {
2235                fIsFinite = false;
2236            } else if (!SkScalarNearlyZero(lengthSqd, SK_ScalarNearlyZero*SK_ScalarNearlyZero)) {
2237                fLastPt = fCurrPt;
2238                fCurrPt = pt;
2239                if (++fPtCount == 2) {
2240                    fFirstVec = fLastVec = vec;
2241                } else {
2242                    SkASSERT(fPtCount > 2);
2243                    this->addVec(vec);
2244                }
2245
2246                int sx = sign(vec.fX);
2247                int sy = sign(vec.fY);
2248                fDx += (sx != fSx);
2249                fDy += (sy != fSy);
2250                fSx = sx;
2251                fSy = sy;
2252
2253                if (fDx > 3 || fDy > 3) {
2254                    fConvexity = SkPath::kConcave_Convexity;
2255                }
2256            }
2257        }
2258    }
2259
2260    void close() {
2261        if (fPtCount > 2) {
2262            this->addVec(fFirstVec);
2263        }
2264    }
2265
2266    bool isFinite() const {
2267        return fIsFinite;
2268    }
2269
2270private:
2271    void addVec(const SkVector& vec) {
2272        SkASSERT(vec.fX || vec.fY);
2273        DirChange dir = direction_change(fLastPt, fCurrPt, fLastVec, vec);
2274        switch (dir) {
2275            case kLeft_DirChange:       // fall through
2276            case kRight_DirChange:
2277                if (kInvalid_DirChange == fExpectedDir) {
2278                    fExpectedDir = dir;
2279                    fDirection = (kRight_DirChange == dir) ? SkPath::kCW_Direction
2280                                                           : SkPath::kCCW_Direction;
2281                } else if (dir != fExpectedDir) {
2282                    fConvexity = SkPath::kConcave_Convexity;
2283                    fDirection = SkPath::kUnknown_Direction;
2284                }
2285                fLastVec = vec;
2286                break;
2287            case kStraight_DirChange:
2288                break;
2289            case kBackwards_DirChange:
2290                fLastVec = vec;
2291                break;
2292            case kInvalid_DirChange:
2293                SkFAIL("Use of invalid direction change flag");
2294                break;
2295        }
2296    }
2297
2298    SkPoint             fLastPt;
2299    SkPoint             fCurrPt;
2300    // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product
2301    // value with the current vec is deemed to be of a significant value.
2302    SkVector            fLastVec, fFirstVec;
2303    int                 fPtCount;   // non-degenerate points
2304    DirChange           fExpectedDir;
2305    SkPath::Convexity   fConvexity;
2306    SkPath::Direction   fDirection;
2307    int                 fDx, fDy, fSx, fSy;
2308    bool                fIsFinite;
2309};
2310
2311SkPath::Convexity SkPath::internalGetConvexity() const {
2312    SkASSERT(kUnknown_Convexity == fConvexity);
2313    SkPoint         pts[4];
2314    SkPath::Verb    verb;
2315    SkPath::Iter    iter(*this, true);
2316
2317    int             contourCount = 0;
2318    int             count;
2319    Convexicator    state;
2320
2321    if (!isFinite()) {
2322        return kUnknown_Convexity;
2323    }
2324    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
2325        switch (verb) {
2326            case kMove_Verb:
2327                if (++contourCount > 1) {
2328                    fConvexity = kConcave_Convexity;
2329                    return kConcave_Convexity;
2330                }
2331                pts[1] = pts[0];
2332                count = 1;
2333                break;
2334            case kLine_Verb: count = 1; break;
2335            case kQuad_Verb: count = 2; break;
2336            case kConic_Verb: count = 2; break;
2337            case kCubic_Verb: count = 3; break;
2338            case kClose_Verb:
2339                state.close();
2340                count = 0;
2341                break;
2342            default:
2343                SkDEBUGFAIL("bad verb");
2344                fConvexity = kConcave_Convexity;
2345                return kConcave_Convexity;
2346        }
2347
2348        for (int i = 1; i <= count; i++) {
2349            state.addPt(pts[i]);
2350        }
2351        // early exit
2352        if (!state.isFinite()) {
2353            return kUnknown_Convexity;
2354        }
2355        if (kConcave_Convexity == state.getConvexity()) {
2356            fConvexity = kConcave_Convexity;
2357            return kConcave_Convexity;
2358        }
2359    }
2360    fConvexity = state.getConvexity();
2361    if (kConvex_Convexity == fConvexity && kUnknown_Direction == fDirection) {
2362        fDirection = state.getDirection();
2363    }
2364    return static_cast<Convexity>(fConvexity);
2365}
2366
2367///////////////////////////////////////////////////////////////////////////////
2368
2369class ContourIter {
2370public:
2371    ContourIter(const SkPathRef& pathRef);
2372
2373    bool done() const { return fDone; }
2374    // if !done() then these may be called
2375    int count() const { return fCurrPtCount; }
2376    const SkPoint* pts() const { return fCurrPt; }
2377    void next();
2378
2379private:
2380    int fCurrPtCount;
2381    const SkPoint* fCurrPt;
2382    const uint8_t* fCurrVerb;
2383    const uint8_t* fStopVerbs;
2384    const SkScalar* fCurrConicWeight;
2385    bool fDone;
2386    SkDEBUGCODE(int fContourCounter;)
2387};
2388
2389ContourIter::ContourIter(const SkPathRef& pathRef) {
2390    fStopVerbs = pathRef.verbsMemBegin();
2391    fDone = false;
2392    fCurrPt = pathRef.points();
2393    fCurrVerb = pathRef.verbs();
2394    fCurrConicWeight = pathRef.conicWeights();
2395    fCurrPtCount = 0;
2396    SkDEBUGCODE(fContourCounter = 0;)
2397    this->next();
2398}
2399
2400void ContourIter::next() {
2401    if (fCurrVerb <= fStopVerbs) {
2402        fDone = true;
2403    }
2404    if (fDone) {
2405        return;
2406    }
2407
2408    // skip pts of prev contour
2409    fCurrPt += fCurrPtCount;
2410
2411    SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
2412    int ptCount = 1;    // moveTo
2413    const uint8_t* verbs = fCurrVerb;
2414
2415    for (--verbs; verbs > fStopVerbs; --verbs) {
2416        switch (verbs[~0]) {
2417            case SkPath::kMove_Verb:
2418                goto CONTOUR_END;
2419            case SkPath::kLine_Verb:
2420                ptCount += 1;
2421                break;
2422            case SkPath::kConic_Verb:
2423                fCurrConicWeight += 1;
2424                // fall-through
2425            case SkPath::kQuad_Verb:
2426                ptCount += 2;
2427                break;
2428            case SkPath::kCubic_Verb:
2429                ptCount += 3;
2430                break;
2431            case SkPath::kClose_Verb:
2432                break;
2433            default:
2434                SkDEBUGFAIL("unexpected verb");
2435                break;
2436        }
2437    }
2438CONTOUR_END:
2439    fCurrPtCount = ptCount;
2440    fCurrVerb = verbs;
2441    SkDEBUGCODE(++fContourCounter;)
2442}
2443
2444// returns cross product of (p1 - p0) and (p2 - p0)
2445static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
2446    SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
2447    // We may get 0 when the above subtracts underflow. We expect this to be
2448    // very rare and lazily promote to double.
2449    if (0 == cross) {
2450        double p0x = SkScalarToDouble(p0.fX);
2451        double p0y = SkScalarToDouble(p0.fY);
2452
2453        double p1x = SkScalarToDouble(p1.fX);
2454        double p1y = SkScalarToDouble(p1.fY);
2455
2456        double p2x = SkScalarToDouble(p2.fX);
2457        double p2y = SkScalarToDouble(p2.fY);
2458
2459        cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
2460                                 (p1y - p0y) * (p2x - p0x));
2461
2462    }
2463    return cross;
2464}
2465
2466// Returns the first pt with the maximum Y coordinate
2467static int find_max_y(const SkPoint pts[], int count) {
2468    SkASSERT(count > 0);
2469    SkScalar max = pts[0].fY;
2470    int firstIndex = 0;
2471    for (int i = 1; i < count; ++i) {
2472        SkScalar y = pts[i].fY;
2473        if (y > max) {
2474            max = y;
2475            firstIndex = i;
2476        }
2477    }
2478    return firstIndex;
2479}
2480
2481static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
2482    int i = index;
2483    for (;;) {
2484        i = (i + inc) % n;
2485        if (i == index) {   // we wrapped around, so abort
2486            break;
2487        }
2488        if (pts[index] != pts[i]) { // found a different point, success!
2489            break;
2490        }
2491    }
2492    return i;
2493}
2494
2495/**
2496 *  Starting at index, and moving forward (incrementing), find the xmin and
2497 *  xmax of the contiguous points that have the same Y.
2498 */
2499static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
2500                               int* maxIndexPtr) {
2501    const SkScalar y = pts[index].fY;
2502    SkScalar min = pts[index].fX;
2503    SkScalar max = min;
2504    int minIndex = index;
2505    int maxIndex = index;
2506    for (int i = index + 1; i < n; ++i) {
2507        if (pts[i].fY != y) {
2508            break;
2509        }
2510        SkScalar x = pts[i].fX;
2511        if (x < min) {
2512            min = x;
2513            minIndex = i;
2514        } else if (x > max) {
2515            max = x;
2516            maxIndex = i;
2517        }
2518    }
2519    *maxIndexPtr = maxIndex;
2520    return minIndex;
2521}
2522
2523static void crossToDir(SkScalar cross, SkPath::Direction* dir) {
2524    *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
2525}
2526
2527/*
2528 *  We loop through all contours, and keep the computed cross-product of the
2529 *  contour that contained the global y-max. If we just look at the first
2530 *  contour, we may find one that is wound the opposite way (correctly) since
2531 *  it is the interior of a hole (e.g. 'o'). Thus we must find the contour
2532 *  that is outer most (or at least has the global y-max) before we can consider
2533 *  its cross product.
2534 */
2535bool SkPath::cheapComputeDirection(Direction* dir) const {
2536    if (kUnknown_Direction != fDirection) {
2537        *dir = static_cast<Direction>(fDirection);
2538        return true;
2539    }
2540
2541    // don't want to pay the cost for computing this if it
2542    // is unknown, so we don't call isConvex()
2543    if (kConvex_Convexity == this->getConvexityOrUnknown()) {
2544        SkASSERT(kUnknown_Direction == fDirection);
2545        *dir = static_cast<Direction>(fDirection);
2546        return false;
2547    }
2548
2549    ContourIter iter(*fPathRef.get());
2550
2551    // initialize with our logical y-min
2552    SkScalar ymax = this->getBounds().fTop;
2553    SkScalar ymaxCross = 0;
2554
2555    for (; !iter.done(); iter.next()) {
2556        int n = iter.count();
2557        if (n < 3) {
2558            continue;
2559        }
2560
2561        const SkPoint* pts = iter.pts();
2562        SkScalar cross = 0;
2563        int index = find_max_y(pts, n);
2564        if (pts[index].fY < ymax) {
2565            continue;
2566        }
2567
2568        // If there is more than 1 distinct point at the y-max, we take the
2569        // x-min and x-max of them and just subtract to compute the dir.
2570        if (pts[(index + 1) % n].fY == pts[index].fY) {
2571            int maxIndex;
2572            int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
2573            if (minIndex == maxIndex) {
2574                goto TRY_CROSSPROD;
2575            }
2576            SkASSERT(pts[minIndex].fY == pts[index].fY);
2577            SkASSERT(pts[maxIndex].fY == pts[index].fY);
2578            SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
2579            // we just subtract the indices, and let that auto-convert to
2580            // SkScalar, since we just want - or + to signal the direction.
2581            cross = minIndex - maxIndex;
2582        } else {
2583            TRY_CROSSPROD:
2584            // Find a next and prev index to use for the cross-product test,
2585            // but we try to find pts that form non-zero vectors from pts[index]
2586            //
2587            // Its possible that we can't find two non-degenerate vectors, so
2588            // we have to guard our search (e.g. all the pts could be in the
2589            // same place).
2590
2591            // we pass n - 1 instead of -1 so we don't foul up % operator by
2592            // passing it a negative LH argument.
2593            int prev = find_diff_pt(pts, index, n, n - 1);
2594            if (prev == index) {
2595                // completely degenerate, skip to next contour
2596                continue;
2597            }
2598            int next = find_diff_pt(pts, index, n, 1);
2599            SkASSERT(next != index);
2600            cross = cross_prod(pts[prev], pts[index], pts[next]);
2601            // if we get a zero and the points are horizontal, then we look at the spread in
2602            // x-direction. We really should continue to walk away from the degeneracy until
2603            // there is a divergence.
2604            if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
2605                // construct the subtract so we get the correct Direction below
2606                cross = pts[index].fX - pts[next].fX;
2607            }
2608        }
2609
2610        if (cross) {
2611            // record our best guess so far
2612            ymax = pts[index].fY;
2613            ymaxCross = cross;
2614        }
2615    }
2616    if (ymaxCross) {
2617        crossToDir(ymaxCross, dir);
2618        fDirection = *dir;
2619        return true;
2620    } else {
2621        return false;
2622    }
2623}
2624
2625///////////////////////////////////////////////////////////////////////////////
2626
2627static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
2628                                 SkScalar D, SkScalar t) {
2629    return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
2630}
2631
2632static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2633                               SkScalar t) {
2634    SkScalar A = c3 + 3*(c1 - c2) - c0;
2635    SkScalar B = 3*(c2 - c1 - c1 + c0);
2636    SkScalar C = 3*(c1 - c0);
2637    SkScalar D = c0;
2638    return eval_cubic_coeff(A, B, C, D, t);
2639}
2640
2641/*  Given 4 cubic points (either Xs or Ys), and a target X or Y, compute the
2642 t value such that cubic(t) = target
2643 */
2644static void chopMonoCubicAt(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2645                            SkScalar target, SkScalar* t) {
2646    //   SkASSERT(c0 <= c1 && c1 <= c2 && c2 <= c3);
2647    SkASSERT(c0 < target && target < c3);
2648
2649    SkScalar D = c0 - target;
2650    SkScalar A = c3 + 3*(c1 - c2) - c0;
2651    SkScalar B = 3*(c2 - c1 - c1 + c0);
2652    SkScalar C = 3*(c1 - c0);
2653
2654    const SkScalar TOLERANCE = SK_Scalar1 / 4096;
2655    SkScalar minT = 0;
2656    SkScalar maxT = SK_Scalar1;
2657    SkScalar mid;
2658    int i;
2659    for (i = 0; i < 16; i++) {
2660        mid = SkScalarAve(minT, maxT);
2661        SkScalar delta = eval_cubic_coeff(A, B, C, D, mid);
2662        if (delta < 0) {
2663            minT = mid;
2664            delta = -delta;
2665        } else {
2666            maxT = mid;
2667        }
2668        if (delta < TOLERANCE) {
2669            break;
2670        }
2671    }
2672    *t = mid;
2673}
2674
2675template <size_t N> static void find_minmax(const SkPoint pts[],
2676                                            SkScalar* minPtr, SkScalar* maxPtr) {
2677    SkScalar min, max;
2678    min = max = pts[0].fX;
2679    for (size_t i = 1; i < N; ++i) {
2680        min = SkMinScalar(min, pts[i].fX);
2681        max = SkMaxScalar(max, pts[i].fX);
2682    }
2683    *minPtr = min;
2684    *maxPtr = max;
2685}
2686
2687static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2688    SkPoint storage[4];
2689
2690    int dir = 1;
2691    if (pts[0].fY > pts[3].fY) {
2692        storage[0] = pts[3];
2693        storage[1] = pts[2];
2694        storage[2] = pts[1];
2695        storage[3] = pts[0];
2696        pts = storage;
2697        dir = -1;
2698    }
2699    if (y < pts[0].fY || y >= pts[3].fY) {
2700        return 0;
2701    }
2702
2703    // quickreject or quickaccept
2704    SkScalar min, max;
2705    find_minmax<4>(pts, &min, &max);
2706    if (x < min) {
2707        return 0;
2708    }
2709    if (x > max) {
2710        return dir;
2711    }
2712
2713    // compute the actual x(t) value
2714    SkScalar t;
2715    chopMonoCubicAt(pts[0].fY, pts[1].fY, pts[2].fY, pts[3].fY, y, &t);
2716    SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
2717    return xt < x ? dir : 0;
2718}
2719
2720static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
2721    SkPoint dst[10];
2722    int n = SkChopCubicAtYExtrema(pts, dst);
2723    int w = 0;
2724    for (int i = 0; i <= n; ++i) {
2725        w += winding_mono_cubic(&dst[i * 3], x, y);
2726    }
2727    return w;
2728}
2729
2730static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2731    SkScalar y0 = pts[0].fY;
2732    SkScalar y2 = pts[2].fY;
2733
2734    int dir = 1;
2735    if (y0 > y2) {
2736        SkTSwap(y0, y2);
2737        dir = -1;
2738    }
2739    if (y < y0 || y >= y2) {
2740        return 0;
2741    }
2742
2743    // bounds check on X (not required. is it faster?)
2744#if 0
2745    if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
2746        return 0;
2747    }
2748#endif
2749
2750    SkScalar roots[2];
2751    int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
2752                                2 * (pts[1].fY - pts[0].fY),
2753                                pts[0].fY - y,
2754                                roots);
2755    SkASSERT(n <= 1);
2756    SkScalar xt;
2757    if (0 == n) {
2758        SkScalar mid = SkScalarAve(y0, y2);
2759        // Need [0] and [2] if dir == 1
2760        // and  [2] and [0] if dir == -1
2761        xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
2762    } else {
2763        SkScalar t = roots[0];
2764        SkScalar C = pts[0].fX;
2765        SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
2766        SkScalar B = 2 * (pts[1].fX - C);
2767        xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
2768    }
2769    return xt < x ? dir : 0;
2770}
2771
2772static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
2773    //    return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
2774    if (y0 == y1) {
2775        return true;
2776    }
2777    if (y0 < y1) {
2778        return y1 <= y2;
2779    } else {
2780        return y1 >= y2;
2781    }
2782}
2783
2784static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
2785    SkPoint dst[5];
2786    int     n = 0;
2787
2788    if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
2789        n = SkChopQuadAtYExtrema(pts, dst);
2790        pts = dst;
2791    }
2792    int w = winding_mono_quad(pts, x, y);
2793    if (n > 0) {
2794        w += winding_mono_quad(&pts[2], x, y);
2795    }
2796    return w;
2797}
2798
2799static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
2800    SkScalar x0 = pts[0].fX;
2801    SkScalar y0 = pts[0].fY;
2802    SkScalar x1 = pts[1].fX;
2803    SkScalar y1 = pts[1].fY;
2804
2805    SkScalar dy = y1 - y0;
2806
2807    int dir = 1;
2808    if (y0 > y1) {
2809        SkTSwap(y0, y1);
2810        dir = -1;
2811    }
2812    if (y < y0 || y >= y1) {
2813        return 0;
2814    }
2815
2816    SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
2817    SkScalarMul(dy, x - pts[0].fX);
2818
2819    if (SkScalarSignAsInt(cross) == dir) {
2820        dir = 0;
2821    }
2822    return dir;
2823}
2824
2825static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
2826    return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
2827}
2828
2829bool SkPath::contains(SkScalar x, SkScalar y) const {
2830    bool isInverse = this->isInverseFillType();
2831    if (this->isEmpty()) {
2832        return isInverse;
2833    }
2834
2835    if (!contains_inclusive(this->getBounds(), x, y)) {
2836        return isInverse;
2837    }
2838
2839    SkPath::Iter iter(*this, true);
2840    bool done = false;
2841    int w = 0;
2842    do {
2843        SkPoint pts[4];
2844        switch (iter.next(pts, false)) {
2845            case SkPath::kMove_Verb:
2846            case SkPath::kClose_Verb:
2847                break;
2848            case SkPath::kLine_Verb:
2849                w += winding_line(pts, x, y);
2850                break;
2851            case SkPath::kQuad_Verb:
2852                w += winding_quad(pts, x, y);
2853                break;
2854            case SkPath::kConic_Verb:
2855                SkASSERT(0);
2856                break;
2857            case SkPath::kCubic_Verb:
2858                w += winding_cubic(pts, x, y);
2859                break;
2860            case SkPath::kDone_Verb:
2861                done = true;
2862                break;
2863       }
2864    } while (!done);
2865
2866    switch (this->getFillType()) {
2867        case SkPath::kEvenOdd_FillType:
2868        case SkPath::kInverseEvenOdd_FillType:
2869            w &= 1;
2870            break;
2871        default:
2872            break;
2873    }
2874    return SkToBool(w);
2875}
2876