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