SkPath.cpp revision 85b6e399d56d2421980daa432f30910beda41922 
1/* libs/graphics/sgl/SkPath.cpp
2**
3** Copyright 2006, The Android Open Source Project
4**
5** Licensed under the Apache License, Version 2.0 (the "License");
6** you may not use this file except in compliance with the License.
7** You may obtain a copy of the License at
8**
9**     http://www.apache.org/licenses/LICENSE-2.0
10**
11** Unless required by applicable law or agreed to in writing, software
12** distributed under the License is distributed on an "AS IS" BASIS,
13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14** See the License for the specific language governing permissions and
15** limitations under the License.
16*/
17
18#include "SkPath.h"
19#include "SkReader32.h"
20#include "SkWriter32.h"
21#include "SkMath.h"
22
23////////////////////////////////////////////////////////////////////////////
24
25/*  This guy's constructor/destructor bracket a path editing operation. It is
26    used when we know the bounds of the amount we are going to add to the path
27    (usually a new contour, but not required).
28
29    It captures some state about the path up front (i.e. if it already has a
30    cached bounds), and the if it can, it updates the cache bounds explicitly,
31    avoiding the need to revisit all of the points in getBounds().
32
33    It also notes if the path was originally empty, and if so, sets isConvex
34    to true. Thus it can only be used if the contour being added is convex.
35 */
36class SkAutoPathBoundsUpdate {
37public:
38    SkAutoPathBoundsUpdate(SkPath* path, const SkRect& r) : fRect(r) {
39        this->init(path);
40    }
41
42    SkAutoPathBoundsUpdate(SkPath* path, SkScalar left, SkScalar top,
43                           SkScalar right, SkScalar bottom) {
44        fRect.set(left, top, right, bottom);
45        this->init(path);
46    }
47
48    ~SkAutoPathBoundsUpdate() {
49        fPath->setIsConvex(fEmpty);
50        if (fEmpty) {
51            fPath->fBounds = fRect;
52            fPath->fBoundsIsDirty = false;
53        } else if (!fDirty) {
54            fPath->fBounds.join(fRect);
55            fPath->fBoundsIsDirty = false;
56        }
57    }
58
59private:
60    SkPath* fPath;
61    SkRect  fRect;
62    bool    fDirty;
63    bool    fEmpty;
64
65    // returns true if we should proceed
66    void init(SkPath* path) {
67        fPath = path;
68        fDirty = SkToBool(path->fBoundsIsDirty);
69        fEmpty = path->isEmpty();
70        // Cannot use fRect for our bounds unless we know it is sorted
71        fRect.sort();
72    }
73};
74
75static void compute_pt_bounds(SkRect* bounds, const SkTDArray<SkPoint>& pts) {
76    if (pts.count() <= 1) {  // we ignore just 1 point (moveto)
77        bounds->set(0, 0, 0, 0);
78    } else {
79        bounds->set(pts.begin(), pts.count());
80//        SkDebugf("------- compute bounds %p %d", &pts, pts.count());
81    }
82}
83
84////////////////////////////////////////////////////////////////////////////
85
86/*
87    Stores the verbs and points as they are given to us, with exceptions:
88    - we only record "Close" if it was immediately preceeded by Line | Quad | Cubic
89    - we insert a Move(0,0) if Line | Quad | Cubic is our first command
90
91    The iterator does more cleanup, especially if forceClose == true
92    1. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt)
93    2. if we encounter Move without a preceeding Close, and forceClose is true, goto #1
94    3. if we encounter Line | Quad | Cubic after Close, cons up a Move
95*/
96
97////////////////////////////////////////////////////////////////////////////
98
99SkPath::SkPath() : fBoundsIsDirty(true), fFillType(kWinding_FillType) {
100    fConvexity = kUnknown_Convexity;
101#ifdef ANDROID
102    fGenerationID = 0;
103#endif
104}
105
106SkPath::SkPath(const SkPath& src) {
107    SkDEBUGCODE(src.validate();)
108    *this = src;
109#ifdef ANDROID
110    // the assignment operator above increments the ID so correct for that here
111    fGenerationID--;
112#endif
113}
114
115SkPath::~SkPath() {
116    SkDEBUGCODE(this->validate();)
117}
118
119SkPath& SkPath::operator=(const SkPath& src) {
120    SkDEBUGCODE(src.validate();)
121
122    if (this != &src) {
123        fBounds         = src.fBounds;
124        fPts            = src.fPts;
125        fVerbs          = src.fVerbs;
126        fFillType       = src.fFillType;
127        fBoundsIsDirty  = src.fBoundsIsDirty;
128        fConvexity      = src.fConvexity;
129        GEN_ID_INC;
130    }
131    SkDEBUGCODE(this->validate();)
132    return *this;
133}
134
135bool operator==(const SkPath& a, const SkPath& b) {
136    // note: don't need to look at isConvex or bounds, since just comparing the
137    // raw data is sufficient.
138    return &a == &b ||
139        (a.fFillType == b.fFillType && a.fVerbs == b.fVerbs && a.fPts == b.fPts);
140}
141
142void SkPath::swap(SkPath& other) {
143    SkASSERT(&other != NULL);
144
145    if (this != &other) {
146        SkTSwap<SkRect>(fBounds, other.fBounds);
147        fPts.swap(other.fPts);
148        fVerbs.swap(other.fVerbs);
149        SkTSwap<uint8_t>(fFillType, other.fFillType);
150        SkTSwap<uint8_t>(fBoundsIsDirty, other.fBoundsIsDirty);
151        SkTSwap<uint8_t>(fConvexity, other.fConvexity);
152        GEN_ID_INC;
153    }
154}
155
156#ifdef ANDROID
157uint32_t SkPath::getGenerationID() const {
158    return fGenerationID;
159}
160#endif
161
162void SkPath::reset() {
163    SkDEBUGCODE(this->validate();)
164
165    fPts.reset();
166    fVerbs.reset();
167    GEN_ID_INC;
168    fBoundsIsDirty = true;
169    fConvexity = kUnknown_Convexity;
170}
171
172void SkPath::rewind() {
173    SkDEBUGCODE(this->validate();)
174
175    fPts.rewind();
176    fVerbs.rewind();
177    GEN_ID_INC;
178    fBoundsIsDirty = true;
179    fConvexity = kUnknown_Convexity;
180}
181
182bool SkPath::isEmpty() const {
183    SkDEBUGCODE(this->validate();)
184
185    int count = fVerbs.count();
186    return count == 0 || (count == 1 && fVerbs[0] == kMove_Verb);
187}
188
189bool SkPath::isRect(SkRect*) const {
190    SkDEBUGCODE(this->validate();)
191
192    SkASSERT(!"unimplemented");
193    return false;
194}
195
196int SkPath::getPoints(SkPoint copy[], int max) const {
197    SkDEBUGCODE(this->validate();)
198
199    SkASSERT(max >= 0);
200    int count = fPts.count();
201    if (copy && max > 0 && count > 0) {
202        memcpy(copy, fPts.begin(), sizeof(SkPoint) * SkMin32(max, count));
203    }
204    return count;
205}
206
207SkPoint SkPath::getPoint(int index) const {
208    if ((unsigned)index < (unsigned)fPts.count()) {
209        return fPts[index];
210    }
211    return SkPoint::Make(0, 0);
212}
213
214void SkPath::getLastPt(SkPoint* lastPt) const {
215    SkDEBUGCODE(this->validate();)
216
217    if (lastPt) {
218        int count = fPts.count();
219        if (count == 0) {
220            lastPt->set(0, 0);
221        } else {
222            *lastPt = fPts[count - 1];
223        }
224    }
225}
226
227void SkPath::setLastPt(SkScalar x, SkScalar y) {
228    SkDEBUGCODE(this->validate();)
229
230    int count = fPts.count();
231    if (count == 0) {
232        this->moveTo(x, y);
233    } else {
234        fPts[count - 1].set(x, y);
235        GEN_ID_INC;
236    }
237}
238
239void SkPath::computeBounds() const {
240    SkDEBUGCODE(this->validate();)
241    SkASSERT(fBoundsIsDirty);
242
243    fBoundsIsDirty = false;
244    compute_pt_bounds(&fBounds, fPts);
245}
246
247void SkPath::setConvexity(Convexity c) {
248    if (fConvexity != c) {
249        fConvexity = c;
250        GEN_ID_INC;
251    }
252}
253
254//////////////////////////////////////////////////////////////////////////////
255//  Construction methods
256
257void SkPath::incReserve(U16CPU inc) {
258    SkDEBUGCODE(this->validate();)
259
260    fVerbs.setReserve(fVerbs.count() + inc);
261    fPts.setReserve(fPts.count() + inc);
262
263    SkDEBUGCODE(this->validate();)
264}
265
266void SkPath::moveTo(SkScalar x, SkScalar y) {
267    SkDEBUGCODE(this->validate();)
268
269    int      vc = fVerbs.count();
270    SkPoint* pt;
271
272    if (vc > 0 && fVerbs[vc - 1] == kMove_Verb) {
273        pt = &fPts[fPts.count() - 1];
274    } else {
275        pt = fPts.append();
276        *fVerbs.append() = kMove_Verb;
277    }
278    pt->set(x, y);
279
280    GEN_ID_INC;
281    fBoundsIsDirty = true;
282}
283
284void SkPath::rMoveTo(SkScalar x, SkScalar y) {
285    SkPoint pt;
286    this->getLastPt(&pt);
287    this->moveTo(pt.fX + x, pt.fY + y);
288}
289
290void SkPath::lineTo(SkScalar x, SkScalar y) {
291    SkDEBUGCODE(this->validate();)
292
293    if (fVerbs.count() == 0) {
294        fPts.append()->set(0, 0);
295        *fVerbs.append() = kMove_Verb;
296    }
297    fPts.append()->set(x, y);
298    *fVerbs.append() = kLine_Verb;
299
300    GEN_ID_INC;
301    fBoundsIsDirty = true;
302}
303
304void SkPath::rLineTo(SkScalar x, SkScalar y) {
305    SkPoint pt;
306    this->getLastPt(&pt);
307    this->lineTo(pt.fX + x, pt.fY + y);
308}
309
310void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
311    SkDEBUGCODE(this->validate();)
312
313    if (fVerbs.count() == 0) {
314        fPts.append()->set(0, 0);
315        *fVerbs.append() = kMove_Verb;
316    }
317
318    SkPoint* pts = fPts.append(2);
319    pts[0].set(x1, y1);
320    pts[1].set(x2, y2);
321    *fVerbs.append() = kQuad_Verb;
322
323    GEN_ID_INC;
324    fBoundsIsDirty = true;
325}
326
327void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
328    SkPoint pt;
329    this->getLastPt(&pt);
330    this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
331}
332
333void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
334                     SkScalar x3, SkScalar y3) {
335    SkDEBUGCODE(this->validate();)
336
337    if (fVerbs.count() == 0) {
338        fPts.append()->set(0, 0);
339        *fVerbs.append() = kMove_Verb;
340    }
341    SkPoint* pts = fPts.append(3);
342    pts[0].set(x1, y1);
343    pts[1].set(x2, y2);
344    pts[2].set(x3, y3);
345    *fVerbs.append() = kCubic_Verb;
346
347    GEN_ID_INC;
348    fBoundsIsDirty = true;
349}
350
351void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
352                      SkScalar x3, SkScalar y3) {
353    SkPoint pt;
354    this->getLastPt(&pt);
355    this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
356                  pt.fX + x3, pt.fY + y3);
357}
358
359void SkPath::close() {
360    SkDEBUGCODE(this->validate();)
361
362    int count = fVerbs.count();
363    if (count > 0) {
364        switch (fVerbs[count - 1]) {
365            case kLine_Verb:
366            case kQuad_Verb:
367            case kCubic_Verb:
368                *fVerbs.append() = kClose_Verb;
369                GEN_ID_INC;
370                break;
371            default:
372                // don't add a close if the prev wasn't a primitive
373                break;
374        }
375    }
376}
377
378///////////////////////////////////////////////////////////////////////////////
379
380void SkPath::addRect(const SkRect& rect, Direction dir) {
381    this->addRect(rect.fLeft, rect.fTop, rect.fRight, rect.fBottom, dir);
382}
383
384void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
385                     SkScalar bottom, Direction dir) {
386    SkAutoPathBoundsUpdate apbu(this, left, top, right, bottom);
387
388    this->incReserve(5);
389
390    this->moveTo(left, top);
391    if (dir == kCCW_Direction) {
392        this->lineTo(left, bottom);
393        this->lineTo(right, bottom);
394        this->lineTo(right, top);
395    } else {
396        this->lineTo(right, top);
397        this->lineTo(right, bottom);
398        this->lineTo(left, bottom);
399    }
400    this->close();
401}
402
403#define CUBIC_ARC_FACTOR    ((SK_ScalarSqrt2 - SK_Scalar1) * 4 / 3)
404
405void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
406                          Direction dir) {
407    SkScalar    w = rect.width();
408    SkScalar    halfW = SkScalarHalf(w);
409    SkScalar    h = rect.height();
410    SkScalar    halfH = SkScalarHalf(h);
411
412    if (halfW <= 0 || halfH <= 0) {
413        return;
414    }
415
416    bool skip_hori = rx >= halfW;
417    bool skip_vert = ry >= halfH;
418
419    if (skip_hori && skip_vert) {
420        this->addOval(rect, dir);
421        return;
422    }
423
424    SkAutoPathBoundsUpdate apbu(this, rect);
425
426    if (skip_hori) {
427        rx = halfW;
428    } else if (skip_vert) {
429        ry = halfH;
430    }
431
432    SkScalar    sx = SkScalarMul(rx, CUBIC_ARC_FACTOR);
433    SkScalar    sy = SkScalarMul(ry, CUBIC_ARC_FACTOR);
434
435    this->incReserve(17);
436    this->moveTo(rect.fRight - rx, rect.fTop);
437    if (dir == kCCW_Direction) {
438        if (!skip_hori) {
439            this->lineTo(rect.fLeft + rx, rect.fTop);       // top
440        }
441        this->cubicTo(rect.fLeft + rx - sx, rect.fTop,
442                      rect.fLeft, rect.fTop + ry - sy,
443                      rect.fLeft, rect.fTop + ry);          // top-left
444        if (!skip_vert) {
445            this->lineTo(rect.fLeft, rect.fBottom - ry);        // left
446        }
447        this->cubicTo(rect.fLeft, rect.fBottom - ry + sy,
448                      rect.fLeft + rx - sx, rect.fBottom,
449                      rect.fLeft + rx, rect.fBottom);       // bot-left
450        if (!skip_hori) {
451            this->lineTo(rect.fRight - rx, rect.fBottom);   // bottom
452        }
453        this->cubicTo(rect.fRight - rx + sx, rect.fBottom,
454                      rect.fRight, rect.fBottom - ry + sy,
455                      rect.fRight, rect.fBottom - ry);      // bot-right
456        if (!skip_vert) {
457            this->lineTo(rect.fRight, rect.fTop + ry);
458        }
459        this->cubicTo(rect.fRight, rect.fTop + ry - sy,
460                      rect.fRight - rx + sx, rect.fTop,
461                      rect.fRight - rx, rect.fTop);         // top-right
462    } else {
463        this->cubicTo(rect.fRight - rx + sx, rect.fTop,
464                      rect.fRight, rect.fTop + ry - sy,
465                      rect.fRight, rect.fTop + ry);         // top-right
466        if (!skip_vert) {
467            this->lineTo(rect.fRight, rect.fBottom - ry);
468        }
469        this->cubicTo(rect.fRight, rect.fBottom - ry + sy,
470                      rect.fRight - rx + sx, rect.fBottom,
471                      rect.fRight - rx, rect.fBottom);      // bot-right
472        if (!skip_hori) {
473            this->lineTo(rect.fLeft + rx, rect.fBottom);    // bottom
474        }
475        this->cubicTo(rect.fLeft + rx - sx, rect.fBottom,
476                      rect.fLeft, rect.fBottom - ry + sy,
477                      rect.fLeft, rect.fBottom - ry);       // bot-left
478        if (!skip_vert) {
479            this->lineTo(rect.fLeft, rect.fTop + ry);       // left
480        }
481        this->cubicTo(rect.fLeft, rect.fTop + ry - sy,
482                      rect.fLeft + rx - sx, rect.fTop,
483                      rect.fLeft + rx, rect.fTop);          // top-left
484        if (!skip_hori) {
485            this->lineTo(rect.fRight - rx, rect.fTop);      // top
486        }
487    }
488    this->close();
489}
490
491static void add_corner_arc(SkPath* path, const SkRect& rect,
492                           SkScalar rx, SkScalar ry, int startAngle,
493                           SkPath::Direction dir, bool forceMoveTo) {
494    rx = SkMinScalar(SkScalarHalf(rect.width()), rx);
495    ry = SkMinScalar(SkScalarHalf(rect.height()), ry);
496
497    SkRect   r;
498    r.set(-rx, -ry, rx, ry);
499
500    switch (startAngle) {
501        case   0:
502            r.offset(rect.fRight - r.fRight, rect.fBottom - r.fBottom);
503            break;
504        case  90:
505            r.offset(rect.fLeft - r.fLeft,   rect.fBottom - r.fBottom);
506            break;
507        case 180: r.offset(rect.fLeft - r.fLeft,   rect.fTop - r.fTop); break;
508        case 270: r.offset(rect.fRight - r.fRight, rect.fTop - r.fTop); break;
509        default: SkASSERT(!"unexpected startAngle in add_corner_arc");
510    }
511
512    SkScalar start = SkIntToScalar(startAngle);
513    SkScalar sweep = SkIntToScalar(90);
514    if (SkPath::kCCW_Direction == dir) {
515        start += sweep;
516        sweep = -sweep;
517    }
518
519    path->arcTo(r, start, sweep, forceMoveTo);
520}
521
522void SkPath::addRoundRect(const SkRect& rect, const SkScalar rad[],
523                          Direction dir) {
524    // abort before we invoke SkAutoPathBoundsUpdate()
525    if (rect.isEmpty()) {
526        return;
527    }
528
529    SkAutoPathBoundsUpdate apbu(this, rect);
530
531    if (kCW_Direction == dir) {
532        add_corner_arc(this, rect, rad[0], rad[1], 180, dir, true);
533        add_corner_arc(this, rect, rad[2], rad[3], 270, dir, false);
534        add_corner_arc(this, rect, rad[4], rad[5],   0, dir, false);
535        add_corner_arc(this, rect, rad[6], rad[7],  90, dir, false);
536    } else {
537        add_corner_arc(this, rect, rad[0], rad[1], 180, dir, true);
538        add_corner_arc(this, rect, rad[6], rad[7],  90, dir, false);
539        add_corner_arc(this, rect, rad[4], rad[5],   0, dir, false);
540        add_corner_arc(this, rect, rad[2], rad[3], 270, dir, false);
541    }
542    this->close();
543}
544
545void SkPath::addOval(const SkRect& oval, Direction dir) {
546    SkAutoPathBoundsUpdate apbu(this, oval);
547
548    SkScalar    cx = oval.centerX();
549    SkScalar    cy = oval.centerY();
550    SkScalar    rx = SkScalarHalf(oval.width());
551    SkScalar    ry = SkScalarHalf(oval.height());
552#if 0   // these seem faster than using quads (1/2 the number of edges)
553    SkScalar    sx = SkScalarMul(rx, CUBIC_ARC_FACTOR);
554    SkScalar    sy = SkScalarMul(ry, CUBIC_ARC_FACTOR);
555
556    this->incReserve(13);
557    this->moveTo(cx + rx, cy);
558    if (dir == kCCW_Direction) {
559        this->cubicTo(cx + rx, cy - sy, cx + sx, cy - ry, cx, cy - ry);
560        this->cubicTo(cx - sx, cy - ry, cx - rx, cy - sy, cx - rx, cy);
561        this->cubicTo(cx - rx, cy + sy, cx - sx, cy + ry, cx, cy + ry);
562        this->cubicTo(cx + sx, cy + ry, cx + rx, cy + sy, cx + rx, cy);
563    } else {
564        this->cubicTo(cx + rx, cy + sy, cx + sx, cy + ry, cx, cy + ry);
565        this->cubicTo(cx - sx, cy + ry, cx - rx, cy + sy, cx - rx, cy);
566        this->cubicTo(cx - rx, cy - sy, cx - sx, cy - ry, cx, cy - ry);
567        this->cubicTo(cx + sx, cy - ry, cx + rx, cy - sy, cx + rx, cy);
568    }
569#else
570    SkScalar    sx = SkScalarMul(rx, SK_ScalarTanPIOver8);
571    SkScalar    sy = SkScalarMul(ry, SK_ScalarTanPIOver8);
572    SkScalar    mx = SkScalarMul(rx, SK_ScalarRoot2Over2);
573    SkScalar    my = SkScalarMul(ry, SK_ScalarRoot2Over2);
574
575    /*
576        To handle imprecision in computing the center and radii, we revert to
577        the provided bounds when we can (i.e. use oval.fLeft instead of cx-rx)
578        to ensure that we don't exceed the oval's bounds *ever*, since we want
579        to use oval for our fast-bounds, rather than have to recompute it.
580    */
581    const SkScalar L = oval.fLeft;      // cx - rx
582    const SkScalar T = oval.fTop;       // cy - ry
583    const SkScalar R = oval.fRight;     // cx + rx
584    const SkScalar B = oval.fBottom;    // cy + ry
585
586    this->incReserve(17);   // 8 quads + close
587    this->moveTo(R, cy);
588    if (dir == kCCW_Direction) {
589        this->quadTo(      R, cy - sy, cx + mx, cy - my);
590        this->quadTo(cx + sx,       T, cx     ,       T);
591        this->quadTo(cx - sx,       T, cx - mx, cy - my);
592        this->quadTo(      L, cy - sy,       L, cy     );
593        this->quadTo(      L, cy + sy, cx - mx, cy + my);
594        this->quadTo(cx - sx,       B, cx     ,       B);
595        this->quadTo(cx + sx,       B, cx + mx, cy + my);
596        this->quadTo(      R, cy + sy,       R, cy     );
597    } else {
598        this->quadTo(      R, cy + sy, cx + mx, cy + my);
599        this->quadTo(cx + sx,       B, cx     ,       B);
600        this->quadTo(cx - sx,       B, cx - mx, cy + my);
601        this->quadTo(      L, cy + sy,       L, cy     );
602        this->quadTo(      L, cy - sy, cx - mx, cy - my);
603        this->quadTo(cx - sx,       T, cx     ,       T);
604        this->quadTo(cx + sx,       T, cx + mx, cy - my);
605        this->quadTo(      R, cy - sy,       R, cy     );
606    }
607#endif
608    this->close();
609}
610
611void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
612    if (r > 0) {
613        SkRect  rect;
614        rect.set(x - r, y - r, x + r, y + r);
615        this->addOval(rect, dir);
616    }
617}
618
619#include "SkGeometry.h"
620
621static int build_arc_points(const SkRect& oval, SkScalar startAngle,
622                            SkScalar sweepAngle,
623                            SkPoint pts[kSkBuildQuadArcStorage]) {
624    SkVector start, stop;
625
626    start.fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &start.fX);
627    stop.fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle),
628                             &stop.fX);
629
630    /*  If the sweep angle is nearly (but less than) 360, then due to precision
631        loss in radians-conversion and/or sin/cos, we may end up with coincident
632        vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
633        of drawing a nearly complete circle (good).
634             e.g. canvas.drawArc(0, 359.99, ...)
635             -vs- canvas.drawArc(0, 359.9, ...)
636        We try to detect this edge case, and tweak the stop vector
637     */
638    if (start == stop) {
639        SkScalar sw = SkScalarAbs(sweepAngle);
640        if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
641            SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle);
642            // make a guess at a tiny angle (in radians) to tweak by
643            SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
644            // not sure how much will be enough, so we use a loop
645            do {
646                stopRad -= deltaRad;
647                stop.fY = SkScalarSinCos(stopRad, &stop.fX);
648            } while (start == stop);
649        }
650    }
651
652    SkMatrix    matrix;
653
654    matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
655    matrix.postTranslate(oval.centerX(), oval.centerY());
656
657    return SkBuildQuadArc(start, stop,
658          sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection,
659                          &matrix, pts);
660}
661
662void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
663                   bool forceMoveTo) {
664    if (oval.width() < 0 || oval.height() < 0) {
665        return;
666    }
667
668    SkPoint pts[kSkBuildQuadArcStorage];
669    int count = build_arc_points(oval, startAngle, sweepAngle, pts);
670    SkASSERT((count & 1) == 1);
671
672    if (fVerbs.count() == 0) {
673        forceMoveTo = true;
674    }
675    this->incReserve(count);
676    forceMoveTo ? this->moveTo(pts[0]) : this->lineTo(pts[0]);
677    for (int i = 1; i < count; i += 2) {
678        this->quadTo(pts[i], pts[i+1]);
679    }
680}
681
682void SkPath::addArc(const SkRect& oval, SkScalar startAngle,
683                    SkScalar sweepAngle) {
684    if (oval.isEmpty() || 0 == sweepAngle) {
685        return;
686    }
687
688    const SkScalar kFullCircleAngle = SkIntToScalar(360);
689
690    if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
691        this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction);
692        return;
693    }
694
695    SkPoint pts[kSkBuildQuadArcStorage];
696    int count = build_arc_points(oval, startAngle, sweepAngle, pts);
697
698    this->incReserve(count);
699    this->moveTo(pts[0]);
700    for (int i = 1; i < count; i += 2) {
701        this->quadTo(pts[i], pts[i+1]);
702    }
703}
704
705/*
706    Need to handle the case when the angle is sharp, and our computed end-points
707    for the arc go behind pt1 and/or p2...
708*/
709void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
710                   SkScalar radius) {
711    SkVector    before, after;
712
713    // need to know our prev pt so we can construct tangent vectors
714    {
715        SkPoint start;
716        this->getLastPt(&start);
717        // Handle degenerate cases by adding a line to the first point and
718        // bailing out.
719        if ((x1 == start.fX && y1 == start.fY) ||
720            (x1 == x2 && y1 == y2) ||
721            radius == 0) {
722            this->lineTo(x1, y1);
723            return;
724        }
725        before.setNormalize(x1 - start.fX, y1 - start.fY);
726        after.setNormalize(x2 - x1, y2 - y1);
727    }
728
729    SkScalar cosh = SkPoint::DotProduct(before, after);
730    SkScalar sinh = SkPoint::CrossProduct(before, after);
731
732    if (SkScalarNearlyZero(sinh)) {   // angle is too tight
733        this->lineTo(x1, y1);
734        return;
735    }
736
737    SkScalar dist = SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh);
738    if (dist < 0) {
739        dist = -dist;
740    }
741
742    SkScalar xx = x1 - SkScalarMul(dist, before.fX);
743    SkScalar yy = y1 - SkScalarMul(dist, before.fY);
744    SkRotationDirection arcDir;
745
746    // now turn before/after into normals
747    if (sinh > 0) {
748        before.rotateCCW();
749        after.rotateCCW();
750        arcDir = kCW_SkRotationDirection;
751    } else {
752        before.rotateCW();
753        after.rotateCW();
754        arcDir = kCCW_SkRotationDirection;
755    }
756
757    SkMatrix    matrix;
758    SkPoint     pts[kSkBuildQuadArcStorage];
759
760    matrix.setScale(radius, radius);
761    matrix.postTranslate(xx - SkScalarMul(radius, before.fX),
762                         yy - SkScalarMul(radius, before.fY));
763
764    int count = SkBuildQuadArc(before, after, arcDir, &matrix, pts);
765
766    this->incReserve(count);
767    // [xx,yy] == pts[0]
768    this->lineTo(xx, yy);
769    for (int i = 1; i < count; i += 2) {
770        this->quadTo(pts[i], pts[i+1]);
771    }
772}
773
774///////////////////////////////////////////////////////////////////////////////
775
776void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy) {
777    SkMatrix matrix;
778
779    matrix.setTranslate(dx, dy);
780    this->addPath(path, matrix);
781}
782
783void SkPath::addPath(const SkPath& path, const SkMatrix& matrix) {
784    this->incReserve(path.fPts.count());
785
786    Iter    iter(path, false);
787    SkPoint pts[4];
788    Verb    verb;
789
790    SkMatrix::MapPtsProc proc = matrix.getMapPtsProc();
791
792    while ((verb = iter.next(pts)) != kDone_Verb) {
793        switch (verb) {
794            case kMove_Verb:
795                proc(matrix, &pts[0], &pts[0], 1);
796                this->moveTo(pts[0]);
797                break;
798            case kLine_Verb:
799                proc(matrix, &pts[1], &pts[1], 1);
800                this->lineTo(pts[1]);
801                break;
802            case kQuad_Verb:
803                proc(matrix, &pts[1], &pts[1], 2);
804                this->quadTo(pts[1], pts[2]);
805                break;
806            case kCubic_Verb:
807                proc(matrix, &pts[1], &pts[1], 3);
808                this->cubicTo(pts[1], pts[2], pts[3]);
809                break;
810            case kClose_Verb:
811                this->close();
812                break;
813            default:
814                SkASSERT(!"unknown verb");
815        }
816    }
817}
818
819///////////////////////////////////////////////////////////////////////////////
820
821static const uint8_t gPtsInVerb[] = {
822    1,  // kMove
823    1,  // kLine
824    2,  // kQuad
825    3,  // kCubic
826    0,  // kClose
827    0   // kDone
828};
829
830// ignore the initial moveto, and stop when the 1st contour ends
831void SkPath::pathTo(const SkPath& path) {
832    int i, vcount = path.fVerbs.count();
833    if (vcount == 0) {
834        return;
835    }
836
837    this->incReserve(vcount);
838
839    const uint8_t*  verbs = path.fVerbs.begin();
840    const SkPoint*  pts = path.fPts.begin() + 1;    // 1 for the initial moveTo
841
842    SkASSERT(verbs[0] == kMove_Verb);
843    for (i = 1; i < vcount; i++) {
844        switch (verbs[i]) {
845            case kLine_Verb:
846                this->lineTo(pts[0].fX, pts[0].fY);
847                break;
848            case kQuad_Verb:
849                this->quadTo(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY);
850                break;
851            case kCubic_Verb:
852                this->cubicTo(pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY,
853                              pts[2].fX, pts[2].fY);
854                break;
855            case kClose_Verb:
856                return;
857        }
858        pts += gPtsInVerb[verbs[i]];
859    }
860}
861
862// ignore the last point of the 1st contour
863void SkPath::reversePathTo(const SkPath& path) {
864    int i, vcount = path.fVerbs.count();
865    if (vcount == 0) {
866        return;
867    }
868
869    this->incReserve(vcount);
870
871    const uint8_t*  verbs = path.fVerbs.begin();
872    const SkPoint*  pts = path.fPts.begin();
873
874    SkASSERT(verbs[0] == kMove_Verb);
875    for (i = 1; i < vcount; i++) {
876        int n = gPtsInVerb[verbs[i]];
877        if (n == 0) {
878            break;
879        }
880        pts += n;
881    }
882
883    while (--i > 0) {
884        switch (verbs[i]) {
885            case kLine_Verb:
886                this->lineTo(pts[-1].fX, pts[-1].fY);
887                break;
888            case kQuad_Verb:
889                this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY);
890                break;
891            case kCubic_Verb:
892                this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY,
893                              pts[-3].fX, pts[-3].fY);
894                break;
895            default:
896                SkASSERT(!"bad verb");
897                break;
898        }
899        pts -= gPtsInVerb[verbs[i]];
900    }
901}
902
903///////////////////////////////////////////////////////////////////////////////
904
905void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
906    SkMatrix    matrix;
907
908    matrix.setTranslate(dx, dy);
909    this->transform(matrix, dst);
910}
911
912#include "SkGeometry.h"
913
914static void subdivide_quad_to(SkPath* path, const SkPoint pts[3],
915                              int level = 2) {
916    if (--level >= 0) {
917        SkPoint tmp[5];
918
919        SkChopQuadAtHalf(pts, tmp);
920        subdivide_quad_to(path, &tmp[0], level);
921        subdivide_quad_to(path, &tmp[2], level);
922    } else {
923        path->quadTo(pts[1], pts[2]);
924    }
925}
926
927static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
928                               int level = 2) {
929    if (--level >= 0) {
930        SkPoint tmp[7];
931
932        SkChopCubicAtHalf(pts, tmp);
933        subdivide_cubic_to(path, &tmp[0], level);
934        subdivide_cubic_to(path, &tmp[3], level);
935    } else {
936        path->cubicTo(pts[1], pts[2], pts[3]);
937    }
938}
939
940void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
941    SkDEBUGCODE(this->validate();)
942    if (dst == NULL) {
943        dst = (SkPath*)this;
944    }
945
946    if (matrix.getType() & SkMatrix::kPerspective_Mask) {
947        SkPath  tmp;
948        tmp.fFillType = fFillType;
949
950        SkPath::Iter    iter(*this, false);
951        SkPoint         pts[4];
952        SkPath::Verb    verb;
953
954        while ((verb = iter.next(pts)) != kDone_Verb) {
955            switch (verb) {
956                case kMove_Verb:
957                    tmp.moveTo(pts[0]);
958                    break;
959                case kLine_Verb:
960                    tmp.lineTo(pts[1]);
961                    break;
962                case kQuad_Verb:
963                    subdivide_quad_to(&tmp, pts);
964                    break;
965                case kCubic_Verb:
966                    subdivide_cubic_to(&tmp, pts);
967                    break;
968                case kClose_Verb:
969                    tmp.close();
970                    break;
971                default:
972                    SkASSERT(!"unknown verb");
973                    break;
974            }
975        }
976
977        dst->swap(tmp);
978        matrix.mapPoints(dst->fPts.begin(), dst->fPts.count());
979    } else {
980        // remember that dst might == this, so be sure to check
981        // fBoundsIsDirty before we set it
982        if (!fBoundsIsDirty && matrix.rectStaysRect() && fPts.count() > 1) {
983            // if we're empty, fastbounds should not be mapped
984            matrix.mapRect(&dst->fBounds, fBounds);
985            dst->fBoundsIsDirty = false;
986        } else {
987            GEN_ID_PTR_INC(dst);
988            dst->fBoundsIsDirty = true;
989        }
990
991        if (this != dst) {
992            dst->fVerbs = fVerbs;
993            dst->fPts.setCount(fPts.count());
994            dst->fFillType = fFillType;
995        }
996        matrix.mapPoints(dst->fPts.begin(), fPts.begin(), fPts.count());
997        SkDEBUGCODE(dst->validate();)
998    }
999}
1000
1001///////////////////////////////////////////////////////////////////////////////
1002///////////////////////////////////////////////////////////////////////////////
1003
1004enum NeedMoveToState {
1005    kAfterClose_NeedMoveToState,
1006    kAfterCons_NeedMoveToState,
1007    kAfterPrefix_NeedMoveToState
1008};
1009
1010SkPath::Iter::Iter() {
1011#ifdef SK_DEBUG
1012    fPts = NULL;
1013    fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1014    fForceClose = fNeedMoveTo = fCloseLine = false;
1015#endif
1016    // need to init enough to make next() harmlessly return kDone_Verb
1017    fVerbs = NULL;
1018    fVerbStop = NULL;
1019    fNeedClose = false;
1020}
1021
1022SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
1023    this->setPath(path, forceClose);
1024}
1025
1026void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
1027    fPts = path.fPts.begin();
1028    fVerbs = path.fVerbs.begin();
1029    fVerbStop = path.fVerbs.end();
1030    fForceClose = SkToU8(forceClose);
1031    fNeedClose = false;
1032    fNeedMoveTo = kAfterPrefix_NeedMoveToState;
1033}
1034
1035bool SkPath::Iter::isClosedContour() const {
1036    if (fVerbs == NULL || fVerbs == fVerbStop) {
1037        return false;
1038    }
1039    if (fForceClose) {
1040        return true;
1041    }
1042
1043    const uint8_t* verbs = fVerbs;
1044    const uint8_t* stop = fVerbStop;
1045
1046    if (kMove_Verb == *verbs) {
1047        verbs += 1; // skip the initial moveto
1048    }
1049
1050    while (verbs < stop) {
1051        unsigned v = *verbs++;
1052        if (kMove_Verb == v) {
1053            break;
1054        }
1055        if (kClose_Verb == v) {
1056            return true;
1057        }
1058    }
1059    return false;
1060}
1061
1062SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
1063    if (fLastPt != fMoveTo) {
1064        // A special case: if both points are NaN, SkPoint::operation== returns
1065        // false, but the iterator expects that they are treated as the same.
1066        // (consider SkPoint is a 2-dimension float point).
1067        if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
1068            SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
1069            return kClose_Verb;
1070        }
1071
1072        if (pts) {
1073            pts[0] = fLastPt;
1074            pts[1] = fMoveTo;
1075        }
1076        fLastPt = fMoveTo;
1077        fCloseLine = true;
1078        return kLine_Verb;
1079    }
1080    return kClose_Verb;
1081}
1082
1083bool SkPath::Iter::cons_moveTo(SkPoint pts[1]) {
1084    if (fNeedMoveTo == kAfterClose_NeedMoveToState) {
1085        if (pts) {
1086            *pts = fMoveTo;
1087        }
1088        fNeedClose = fForceClose;
1089        fNeedMoveTo = kAfterCons_NeedMoveToState;
1090        fVerbs -= 1;
1091        return true;
1092    }
1093
1094    if (fNeedMoveTo == kAfterCons_NeedMoveToState) {
1095        if (pts) {
1096            *pts = fMoveTo;
1097        }
1098        fNeedMoveTo = kAfterPrefix_NeedMoveToState;
1099    } else {
1100        SkASSERT(fNeedMoveTo == kAfterPrefix_NeedMoveToState);
1101        if (pts) {
1102            *pts = fPts[-1];
1103        }
1104    }
1105    return false;
1106}
1107
1108SkPath::Verb SkPath::Iter::next(SkPoint pts[4]) {
1109    if (fVerbs == fVerbStop) {
1110        if (fNeedClose) {
1111            if (kLine_Verb == this->autoClose(pts)) {
1112                return kLine_Verb;
1113            }
1114            fNeedClose = false;
1115            return kClose_Verb;
1116        }
1117        return kDone_Verb;
1118    }
1119
1120    unsigned        verb = *fVerbs++;
1121    const SkPoint*  srcPts = fPts;
1122
1123    switch (verb) {
1124        case kMove_Verb:
1125            if (fNeedClose) {
1126                fVerbs -= 1;
1127                verb = this->autoClose(pts);
1128                if (verb == kClose_Verb) {
1129                    fNeedClose = false;
1130                }
1131                return (Verb)verb;
1132            }
1133            if (fVerbs == fVerbStop) {    // might be a trailing moveto
1134                return kDone_Verb;
1135            }
1136            fMoveTo = *srcPts;
1137            if (pts) {
1138                pts[0] = *srcPts;
1139            }
1140            srcPts += 1;
1141            fNeedMoveTo = kAfterCons_NeedMoveToState;
1142            fNeedClose = fForceClose;
1143            break;
1144        case kLine_Verb:
1145            if (this->cons_moveTo(pts)) {
1146                return kMove_Verb;
1147            }
1148            if (pts) {
1149                pts[1] = srcPts[0];
1150            }
1151            fLastPt = srcPts[0];
1152            fCloseLine = false;
1153            srcPts += 1;
1154            break;
1155        case kQuad_Verb:
1156            if (this->cons_moveTo(pts)) {
1157                return kMove_Verb;
1158            }
1159            if (pts) {
1160                memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1161            }
1162            fLastPt = srcPts[1];
1163            srcPts += 2;
1164            break;
1165        case kCubic_Verb:
1166            if (this->cons_moveTo(pts)) {
1167                return kMove_Verb;
1168            }
1169            if (pts) {
1170                memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1171            }
1172            fLastPt = srcPts[2];
1173            srcPts += 3;
1174            break;
1175        case kClose_Verb:
1176            verb = this->autoClose(pts);
1177            if (verb == kLine_Verb) {
1178                fVerbs -= 1;
1179            } else {
1180                fNeedClose = false;
1181            }
1182            fNeedMoveTo = kAfterClose_NeedMoveToState;
1183            break;
1184    }
1185    fPts = srcPts;
1186    return (Verb)verb;
1187}
1188
1189///////////////////////////////////////////////////////////////////////////////
1190
1191static bool exceeds_dist(const SkScalar p[], const SkScalar q[], SkScalar dist,
1192                         int count) {
1193    SkASSERT(dist > 0);
1194
1195    count *= 2;
1196    for (int i = 0; i < count; i++) {
1197        if (SkScalarAbs(p[i] - q[i]) > dist) {
1198            return true;
1199        }
1200    }
1201    return false;
1202}
1203
1204static void subdivide_quad(SkPath* dst, const SkPoint pts[3], SkScalar dist,
1205                           int subLevel = 4) {
1206    if (--subLevel >= 0 && exceeds_dist(&pts[0].fX, &pts[1].fX, dist, 4)) {
1207        SkPoint tmp[5];
1208        SkChopQuadAtHalf(pts, tmp);
1209
1210        subdivide_quad(dst, &tmp[0], dist, subLevel);
1211        subdivide_quad(dst, &tmp[2], dist, subLevel);
1212    } else {
1213        dst->quadTo(pts[1], pts[2]);
1214    }
1215}
1216
1217static void subdivide_cubic(SkPath* dst, const SkPoint pts[4], SkScalar dist,
1218                            int subLevel = 4) {
1219    if (--subLevel >= 0 && exceeds_dist(&pts[0].fX, &pts[1].fX, dist, 6)) {
1220        SkPoint tmp[7];
1221        SkChopCubicAtHalf(pts, tmp);
1222
1223        subdivide_cubic(dst, &tmp[0], dist, subLevel);
1224        subdivide_cubic(dst, &tmp[3], dist, subLevel);
1225    } else {
1226        dst->cubicTo(pts[1], pts[2], pts[3]);
1227    }
1228}
1229
1230void SkPath::subdivide(SkScalar dist, bool bendLines, SkPath* dst) const {
1231    SkPath  tmpPath;
1232    if (NULL == dst || this == dst) {
1233        dst = &tmpPath;
1234    }
1235
1236    SkPath::Iter    iter(*this, false);
1237    SkPoint         pts[4];
1238
1239    for (;;) {
1240        switch (iter.next(pts)) {
1241            case SkPath::kMove_Verb:
1242                dst->moveTo(pts[0]);
1243                break;
1244            case SkPath::kLine_Verb:
1245                if (!bendLines) {
1246                    dst->lineTo(pts[1]);
1247                    break;
1248                }
1249                // construct a quad from the line
1250                pts[2] = pts[1];
1251                pts[1].set(SkScalarAve(pts[0].fX, pts[2].fX),
1252                           SkScalarAve(pts[0].fY, pts[2].fY));
1253                // fall through to the quad case
1254            case SkPath::kQuad_Verb:
1255                subdivide_quad(dst, pts, dist);
1256                break;
1257            case SkPath::kCubic_Verb:
1258                subdivide_cubic(dst, pts, dist);
1259                break;
1260            case SkPath::kClose_Verb:
1261                dst->close();
1262                break;
1263            case SkPath::kDone_Verb:
1264                goto DONE;
1265        }
1266    }
1267DONE:
1268    if (&tmpPath == dst) {   // i.e. the dst should be us
1269        dst->swap(*(SkPath*)this);
1270    }
1271}
1272
1273///////////////////////////////////////////////////////////////////////
1274/*
1275    Format in flattened buffer: [ptCount, verbCount, pts[], verbs[]]
1276*/
1277
1278void SkPath::flatten(SkWriter32& buffer) const {
1279    SkDEBUGCODE(this->validate();)
1280
1281    buffer.write32(fPts.count());
1282    buffer.write32(fVerbs.count());
1283    buffer.write32(fFillType);
1284    buffer.writeMul4(fPts.begin(), sizeof(SkPoint) * fPts.count());
1285    buffer.writePad(fVerbs.begin(), fVerbs.count());
1286}
1287
1288void SkPath::unflatten(SkReader32& buffer) {
1289    fPts.setCount(buffer.readS32());
1290    fVerbs.setCount(buffer.readS32());
1291    fFillType = buffer.readS32();
1292    buffer.read(fPts.begin(), sizeof(SkPoint) * fPts.count());
1293    buffer.read(fVerbs.begin(), fVerbs.count());
1294
1295    GEN_ID_INC;
1296    fBoundsIsDirty = true;
1297
1298    SkDEBUGCODE(this->validate();)
1299}
1300
1301///////////////////////////////////////////////////////////////////////////////
1302///////////////////////////////////////////////////////////////////////////////
1303
1304void SkPath::dump(bool forceClose, const char title[]) const {
1305    Iter    iter(*this, forceClose);
1306    SkPoint pts[4];
1307    Verb    verb;
1308
1309    SkDebugf("path: forceClose=%s %s\n", forceClose ? "true" : "false",
1310             title ? title : "");
1311
1312    while ((verb = iter.next(pts)) != kDone_Verb) {
1313        switch (verb) {
1314            case kMove_Verb:
1315#ifdef SK_CAN_USE_FLOAT
1316                SkDebugf("  path: moveTo [%g %g]\n",
1317                        SkScalarToFloat(pts[0].fX), SkScalarToFloat(pts[0].fY));
1318#else
1319                SkDebugf("  path: moveTo [%x %x]\n", pts[0].fX, pts[0].fY);
1320#endif
1321                break;
1322            case kLine_Verb:
1323#ifdef SK_CAN_USE_FLOAT
1324                SkDebugf("  path: lineTo [%g %g]\n",
1325                        SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY));
1326#else
1327                SkDebugf("  path: lineTo [%x %x]\n", pts[1].fX, pts[1].fY);
1328#endif
1329                break;
1330            case kQuad_Verb:
1331#ifdef SK_CAN_USE_FLOAT
1332                SkDebugf("  path: quadTo [%g %g] [%g %g]\n",
1333                        SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY),
1334                        SkScalarToFloat(pts[2].fX), SkScalarToFloat(pts[2].fY));
1335#else
1336                SkDebugf("  path: quadTo [%x %x] [%x %x]\n",
1337                         pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
1338#endif
1339                break;
1340            case kCubic_Verb:
1341#ifdef SK_CAN_USE_FLOAT
1342                SkDebugf("  path: cubeTo [%g %g] [%g %g] [%g %g]\n",
1343                        SkScalarToFloat(pts[1].fX), SkScalarToFloat(pts[1].fY),
1344                        SkScalarToFloat(pts[2].fX), SkScalarToFloat(pts[2].fY),
1345                        SkScalarToFloat(pts[3].fX), SkScalarToFloat(pts[3].fY));
1346#else
1347                SkDebugf("  path: cubeTo [%x %x] [%x %x] [%x %x]\n",
1348                         pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY,
1349                         pts[3].fX, pts[3].fY);
1350#endif
1351                break;
1352            case kClose_Verb:
1353                SkDebugf("  path: close\n");
1354                break;
1355            default:
1356                SkDebugf("  path: UNKNOWN VERB %d, aborting dump...\n", verb);
1357                verb = kDone_Verb;  // stop the loop
1358                break;
1359        }
1360    }
1361    SkDebugf("path: done %s\n", title ? title : "");
1362}
1363
1364void SkPath::dump() const {
1365    this->dump(false);
1366}
1367
1368#ifdef SK_DEBUG
1369void SkPath::validate() const {
1370    SkASSERT(this != NULL);
1371    SkASSERT((fFillType & ~3) == 0);
1372    fPts.validate();
1373    fVerbs.validate();
1374
1375    if (!fBoundsIsDirty) {
1376        SkRect bounds;
1377        compute_pt_bounds(&bounds, fPts);
1378        if (fPts.count() <= 1) {
1379            // if we're empty, fBounds may be empty but translated, so we can't
1380            // necessarily compare to bounds directly
1381            // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
1382            // be [2, 2, 2, 2]
1383            SkASSERT(bounds.isEmpty());
1384            SkASSERT(fBounds.isEmpty());
1385        } else {
1386            fBounds.contains(bounds);
1387        }
1388    }
1389}
1390#endif
1391
1392///////////////////////////////////////////////////////////////////////////////
1393
1394/**
1395 *  Returns -1 || 0 || 1 depending on the sign of value:
1396 *  -1 if value < 0
1397 *   0 if vlaue == 0
1398 *   1 if value > 0
1399 */
1400static int SkScalarSign(SkScalar value) {
1401    return value < 0 ? -1 : (value > 0);
1402}
1403
1404static int sign(SkScalar x) { return x < 0 ? -1 : 1; }
1405
1406static int CrossProductSign(const SkVector& a, const SkVector& b) {
1407    return SkScalarSign(SkPoint::CrossProduct(a, b));
1408}
1409
1410// only valid for a single contour
1411struct Convexicator {
1412    int fDx, fDy, fSx, fSy;
1413
1414    Convexicator() : fPtCount(0), fConvexity(SkPath::kUnknown_Convexity) {
1415        fSign = 0;
1416        // warnings
1417        fCurrPt.set(0, 0);
1418        fVec0.set(0, 0);
1419        fVec1.set(0, 0);
1420        fFirstVec.set(0, 0);
1421
1422        fDx = fDy = 0;
1423        fSx = fSy = 2;
1424    }
1425
1426    SkPath::Convexity getConvexity() const { return fConvexity; }
1427
1428    void addPt(const SkPoint& pt) {
1429        if (SkPath::kConcave_Convexity == fConvexity) {
1430            return;
1431        }
1432
1433        if (0 == fPtCount) {
1434            fCurrPt = pt;
1435            ++fPtCount;
1436        } else {
1437            SkVector vec = pt - fCurrPt;
1438            if (vec.fX || vec.fY) {
1439                fCurrPt = pt;
1440                if (++fPtCount == 2) {
1441                    fFirstVec = fVec1 = vec;
1442                } else {
1443                    SkASSERT(fPtCount > 2);
1444                    this->addVec(vec);
1445                }
1446
1447                int sx = sign(vec.fX);
1448                int sy = sign(vec.fY);
1449                fDx += (sx != fSx);
1450                fDy += (sy != fSy);
1451                fSx = sx;
1452                fSy = sy;
1453
1454                if (fDx > 3 || fDy > 3) {
1455                    fConvexity = SkPath::kConcave_Convexity;
1456                }
1457            }
1458        }
1459    }
1460
1461    void close() {
1462        if (fPtCount > 2) {
1463            this->addVec(fFirstVec);
1464        }
1465    }
1466
1467private:
1468    void addVec(const SkVector& vec) {
1469        SkASSERT(vec.fX || vec.fY);
1470        fVec0 = fVec1;
1471        fVec1 = vec;
1472        int sign = CrossProductSign(fVec0, fVec1);
1473        if (0 == fSign) {
1474            fSign = sign;
1475        } else if (sign) {
1476            if (fSign == sign) {
1477                fConvexity = SkPath::kConvex_Convexity;
1478            } else {
1479                fConvexity = SkPath::kConcave_Convexity;
1480            }
1481        }
1482    }
1483
1484    SkPoint             fCurrPt;
1485    SkVector            fVec0, fVec1, fFirstVec;
1486    int                 fPtCount;   // non-degenerate points
1487    int                 fSign;
1488    SkPath::Convexity   fConvexity;
1489};
1490
1491SkPath::Convexity SkPath::ComputeConvexity(const SkPath& path) {
1492    SkPoint         pts[4];
1493    SkPath::Verb    verb;
1494    SkPath::Iter    iter(path, true);
1495
1496    int             contourCount = 0;
1497    int             count;
1498    Convexicator    state;
1499
1500    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1501        switch (verb) {
1502            case kMove_Verb:
1503                if (++contourCount > 1) {
1504                    return kConcave_Convexity;
1505                }
1506                pts[1] = pts[0];
1507                count = 1;
1508                break;
1509            case kLine_Verb: count = 1; break;
1510            case kQuad_Verb: count = 2; break;
1511            case kCubic_Verb: count = 3; break;
1512            case kClose_Verb:
1513                state.close();
1514                count = 0;
1515                break;
1516            default:
1517                SkASSERT(!"bad verb");
1518                return kConcave_Convexity;
1519        }
1520
1521        for (int i = 1; i <= count; i++) {
1522            state.addPt(pts[i]);
1523        }
1524        // early exit
1525        if (kConcave_Convexity == state.getConvexity()) {
1526            return kConcave_Convexity;
1527        }
1528    }
1529    return state.getConvexity();
1530}
1531
1532