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