src/third_party/skia/src/core/SkPath.cpp

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