src/core/SkPath.cpp

   1 /*
   2  * Copyright 2006 The Android Open Source Project
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #include <cmath>
   9 #include "SkBuffer.h"
  10 #include "SkCubicClipper.h"
  11 #include "SkErrorInternals.h"
  12 #include "SkGeometry.h"
  13 #include "SkMath.h"
  14 #include "SkPathPriv.h"
  15 #include "SkPathRef.h"
  16 #include "SkRRect.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<SkPathPriv::FirstDirection>(fPath->fFirstDirection.load());
  42     }
  43
  44     ~SkAutoDisableDirectionCheck() {
  45         fPath->fFirstDirection = fSaved;
  46     }
  47
  48 private:
  49     SkPath*                     fPath;
  50     SkPathPriv::FirstDirection  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     this->resetFields();
 131     fIsVolatile = false;
 132 }
 133
 134 void SkPath::resetFields() {
 135     //fPathRef is assumed to have been emptied by the caller.
 136     fLastMoveToIndex = INITIAL_LASTMOVETOINDEX_VALUE;
 137     fFillType = kWinding_FillType;
 138     fConvexity = kUnknown_Convexity;
 139     fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
 140
 141     // We don't touch Android's fSourcePath.  It's used to track texture garbage collection, so we
 142     // don't want to muck with it if it's been set to something non-nullptr.
 143 }
 144
 145 SkPath::SkPath(const SkPath& that)
 146     : fPathRef(SkRef(that.fPathRef.get())) {
 147     this->copyFields(that);
 148     SkDEBUGCODE(that.validate();)
 149 }
 150
 151 SkPath::~SkPath() {
 152     SkDEBUGCODE(this->validate();)
 153 }
 154
 155 SkPath& SkPath::operator=(const SkPath& that) {
 156     SkDEBUGCODE(that.validate();)
 157
 158     if (this != &that) {
 159         fPathRef.reset(SkRef(that.fPathRef.get()));
 160         this->copyFields(that);
 161     }
 162     SkDEBUGCODE(this->validate();)
 163     return *this;
 164 }
 165
 166 void SkPath::copyFields(const SkPath& that) {
 167     //fPathRef is assumed to have been set by the caller.
 168     fLastMoveToIndex = that.fLastMoveToIndex;
 169     fFillType        = that.fFillType;
 170     fConvexity       = that.fConvexity;
 171     // Simulate fFirstDirection  = that.fFirstDirection;
 172     fFirstDirection.store(that.fFirstDirection.load());
 173     fIsVolatile      = that.fIsVolatile;
 174 }
 175
 176 bool operator==(const SkPath& a, const SkPath& b) {
 177     // note: don't need to look at isConvex or bounds, since just comparing the
 178     // raw data is sufficient.
 179     return &a == &b ||
 180         (a.fFillType == b.fFillType && *a.fPathRef.get() == *b.fPathRef.get());
 181 }
 182
 183 void SkPath::swap(SkPath& that) {
 184     if (this != &that) {
 185         fPathRef.swap(that.fPathRef);
 186         SkTSwap<int>(fLastMoveToIndex, that.fLastMoveToIndex);
 187         SkTSwap<uint8_t>(fFillType, that.fFillType);
 188         SkTSwap<uint8_t>(fConvexity, that.fConvexity);
 189         // Simulate SkTSwap<uint8_t>(fFirstDirection, that.fFirstDirection);
 190         uint8_t temp = fFirstDirection;
 191         fFirstDirection.store(that.fFirstDirection.load());
 192         that.fFirstDirection.store(temp);
 193         SkTSwap<SkBool8>(fIsVolatile, that.fIsVolatile);
 194     }
 195 }
 196
 197 bool SkPath::isInterpolatable(const SkPath& compare) const {
 198     int count = fPathRef->countVerbs();
 199     if (count != compare.fPathRef->countVerbs()) {
 200         return false;
 201     }
 202     if (!count) {
 203         return true;
 204     }
 205     if (memcmp(fPathRef->verbsMemBegin(), compare.fPathRef->verbsMemBegin(),
 206                count)) {
 207         return false;
 208     }
 209     return !fPathRef->countWeights() ||
 210             !SkToBool(memcmp(fPathRef->conicWeights(), compare.fPathRef->conicWeights(),
 211             fPathRef->countWeights() * sizeof(*fPathRef->conicWeights())));
 212 }
 213
 214 bool SkPath::interpolate(const SkPath& ending, SkScalar weight, SkPath* out) const {
 215     int verbCount = fPathRef->countVerbs();
 216     if (verbCount != ending.fPathRef->countVerbs()) {
 217         return false;
 218     }
 219     if (!verbCount) {
 220         return true;
 221     }
 222     out->reset();
 223     out->addPath(*this);
 224     fPathRef->interpolate(*ending.fPathRef, weight, out->fPathRef);
 225     return true;
 226 }
 227
 228 static inline bool check_edge_against_rect(const SkPoint& p0,
 229                                            const SkPoint& p1,
 230                                            const SkRect& rect,
 231                                            SkPathPriv::FirstDirection dir) {
 232     const SkPoint* edgeBegin;
 233     SkVector v;
 234     if (SkPathPriv::kCW_FirstDirection == dir) {
 235         v = p1 - p0;
 236         edgeBegin = &p0;
 237     } else {
 238         v = p0 - p1;
 239         edgeBegin = &p1;
 240     }
 241     if (v.fX || v.fY) {
 242         // check the cross product of v with the vec from edgeBegin to each rect corner
 243         SkScalar yL = SkScalarMul(v.fY, rect.fLeft - edgeBegin->fX);
 244         SkScalar xT = SkScalarMul(v.fX, rect.fTop - edgeBegin->fY);
 245         SkScalar yR = SkScalarMul(v.fY, rect.fRight - edgeBegin->fX);
 246         SkScalar xB = SkScalarMul(v.fX, rect.fBottom - edgeBegin->fY);
 247         if ((xT < yL) || (xT < yR) || (xB < yL) || (xB < yR)) {
 248             return false;
 249         }
 250     }
 251     return true;
 252 }
 253
 254 bool SkPath::conservativelyContainsRect(const SkRect& rect) const {
 255     // This only handles non-degenerate convex paths currently.
 256     if (kConvex_Convexity != this->getConvexity()) {
 257         return false;
 258     }
 259
 260     SkPathPriv::FirstDirection direction;
 261     if (!SkPathPriv::CheapComputeFirstDirection(*this, &direction)) {
 262         return false;
 263     }
 264
 265     SkPoint firstPt;
 266     SkPoint prevPt;
 267     RawIter iter(*this);
 268     SkPath::Verb verb;
 269     SkPoint pts[4];
 270     SkDEBUGCODE(int moveCnt = 0;)
 271     SkDEBUGCODE(int segmentCount = 0;)
 272     SkDEBUGCODE(int closeCount = 0;)
 273
 274     while ((verb = iter.next(pts)) != kDone_Verb) {
 275         int nextPt = -1;
 276         switch (verb) {
 277             case kMove_Verb:
 278                 SkASSERT(!segmentCount && !closeCount);
 279                 SkDEBUGCODE(++moveCnt);
 280                 firstPt = prevPt = pts[0];
 281                 break;
 282             case kLine_Verb:
 283                 nextPt = 1;
 284                 SkASSERT(moveCnt && !closeCount);
 285                 SkDEBUGCODE(++segmentCount);
 286                 break;
 287             case kQuad_Verb:
 288             case kConic_Verb:
 289                 SkASSERT(moveCnt && !closeCount);
 290                 SkDEBUGCODE(++segmentCount);
 291                 nextPt = 2;
 292                 break;
 293             case kCubic_Verb:
 294                 SkASSERT(moveCnt && !closeCount);
 295                 SkDEBUGCODE(++segmentCount);
 296                 nextPt = 3;
 297                 break;
 298             case kClose_Verb:
 299                 SkDEBUGCODE(++closeCount;)
 300                 break;
 301             default:
 302                 SkDEBUGFAIL("unknown verb");
 303         }
 304         if (-1 != nextPt) {
 305             if (SkPath::kConic_Verb == verb) {
 306                 SkConic orig;
 307                 orig.set(pts, iter.conicWeight());
 308                 SkPoint quadPts[5];
 309                 int count = orig.chopIntoQuadsPOW2(quadPts, 1);
 310                 SkASSERT_RELEASE(2 == count);
 311
 312                 if (!check_edge_against_rect(quadPts[0], quadPts[2], rect, direction)) {
 313                     return false;
 314                 }
 315                 if (!check_edge_against_rect(quadPts[2], quadPts[4], rect, direction)) {
 316                     return false;
 317                 }
 318             } else {
 319                 if (!check_edge_against_rect(prevPt, pts[nextPt], rect, direction)) {
 320                     return false;
 321                 }
 322             }
 323             prevPt = pts[nextPt];
 324         }
 325     }
 326
 327     return check_edge_against_rect(prevPt, firstPt, rect, direction);
 328 }
 329
 330 uint32_t SkPath::getGenerationID() const {
 331     uint32_t genID = fPathRef->genID();
 332 #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
 333     SkASSERT((unsigned)fFillType < (1 << (32 - kPathRefGenIDBitCnt)));
 334     genID |= static_cast<uint32_t>(fFillType) << kPathRefGenIDBitCnt;
 335 #endif
 336     return genID;
 337 }
 338
 339 void SkPath::reset() {
 340     SkDEBUGCODE(this->validate();)
 341
 342     fPathRef.reset(SkPathRef::CreateEmpty());
 343     this->resetFields();
 344 }
 345
 346 void SkPath::rewind() {
 347     SkDEBUGCODE(this->validate();)
 348
 349     SkPathRef::Rewind(&fPathRef);
 350     this->resetFields();
 351 }
 352
 353 bool SkPath::isLastContourClosed() const {
 354     int verbCount = fPathRef->countVerbs();
 355     if (0 == verbCount) {
 356         return false;
 357     }
 358     return kClose_Verb == fPathRef->atVerb(verbCount - 1);
 359 }
 360
 361 bool SkPath::isLine(SkPoint line[2]) const {
 362     int verbCount = fPathRef->countVerbs();
 363
 364     if (2 == verbCount) {
 365         SkASSERT(kMove_Verb == fPathRef->atVerb(0));
 366         if (kLine_Verb == fPathRef->atVerb(1)) {
 367             SkASSERT(2 == fPathRef->countPoints());
 368             if (line) {
 369                 const SkPoint* pts = fPathRef->points();
 370                 line[0] = pts[0];
 371                 line[1] = pts[1];
 372             }
 373             return true;
 374         }
 375     }
 376     return false;
 377 }
 378
 379 /*
 380  Determines if path is a rect by keeping track of changes in direction
 381  and looking for a loop either clockwise or counterclockwise.
 382
 383  The direction is computed such that:
 384   0: vertical up
 385   1: horizontal left
 386   2: vertical down
 387   3: horizontal right
 388
 389 A rectangle cycles up/right/down/left or up/left/down/right.
 390
 391 The test fails if:
 392   The path is closed, and followed by a line.
 393   A second move creates a new endpoint.
 394   A diagonal line is parsed.
 395   There's more than four changes of direction.
 396   There's a discontinuity on the line (e.g., a move in the middle)
 397   The line reverses direction.
 398   The path contains a quadratic or cubic.
 399   The path contains fewer than four points.
 400  *The rectangle doesn't complete a cycle.
 401  *The final point isn't equal to the first point.
 402
 403   *These last two conditions we relax if we have a 3-edge path that would
 404    form a rectangle if it were closed (as we do when we fill a path)
 405
 406 It's OK if the path has:
 407   Several colinear line segments composing a rectangle side.
 408   Single points on the rectangle side.
 409
 410 The direction takes advantage of the corners found since opposite sides
 411 must travel in opposite directions.
 412
 413 FIXME: Allow colinear quads and cubics to be treated like lines.
 414 FIXME: If the API passes fill-only, return true if the filled stroke
 415        is a rectangle, though the caller failed to close the path.
 416
 417  first,last,next direction state-machine:
 418     0x1 is set if the segment is horizontal
 419     0x2 is set if the segment is moving to the right or down
 420  thus:
 421     two directions are opposites iff (dirA ^ dirB) == 0x2
 422     two directions are perpendicular iff (dirA ^ dirB) == 0x1
 423
 424  */
 425 static int rect_make_dir(SkScalar dx, SkScalar dy) {
 426     return ((0 != dx) << 0) | ((dx > 0 || dy > 0) << 1);
 427 }
 428 bool SkPath::isRectContour(bool allowPartial, int* currVerb, const SkPoint** ptsPtr,
 429         bool* isClosed, Direction* direction) const {
 430     int corners = 0;
 431     SkPoint first, last;
 432     const SkPoint* pts = *ptsPtr;
 433     const SkPoint* savePts = nullptr;
 434     first.set(0, 0);
 435     last.set(0, 0);
 436     int firstDirection = 0;
 437     int lastDirection = 0;
 438     int nextDirection = 0;
 439     bool closedOrMoved = false;
 440     bool autoClose = false;
 441     bool insertClose = false;
 442     int verbCnt = fPathRef->countVerbs();
 443     while (*currVerb < verbCnt && (!allowPartial || !autoClose)) {
 444         uint8_t verb = insertClose ? (uint8_t) kClose_Verb : fPathRef->atVerb(*currVerb);
 445         switch (verb) {
 446             case kClose_Verb:
 447                 savePts = pts;
 448                 pts = *ptsPtr;
 449                 autoClose = true;
 450                 insertClose = false;
 451             case kLine_Verb: {
 452                 SkScalar left = last.fX;
 453                 SkScalar top = last.fY;
 454                 SkScalar right = pts->fX;
 455                 SkScalar bottom = pts->fY;
 456                 ++pts;
 457                 if (left != right && top != bottom) {
 458                     return false; // diagonal
 459                 }
 460                 if (left == right && top == bottom) {
 461                     break; // single point on side OK
 462                 }
 463                 nextDirection = rect_make_dir(right - left, bottom - top);
 464                 if (0 == corners) {
 465                     firstDirection = nextDirection;
 466                     first = last;
 467                     last = pts[-1];
 468                     corners = 1;
 469                     closedOrMoved = false;
 470                     break;
 471                 }
 472                 if (closedOrMoved) {
 473                     return false; // closed followed by a line
 474                 }
 475                 if (autoClose && nextDirection == firstDirection) {
 476                     break; // colinear with first
 477                 }
 478                 closedOrMoved = autoClose;
 479                 if (lastDirection != nextDirection) {
 480                     if (++corners > 4) {
 481                         return false; // too many direction changes
 482                     }
 483                 }
 484                 last = pts[-1];
 485                 if (lastDirection == nextDirection) {
 486                     break; // colinear segment
 487                 }
 488                 // Possible values for corners are 2, 3, and 4.
 489                 // When corners == 3, nextDirection opposes firstDirection.
 490                 // Otherwise, nextDirection at corner 2 opposes corner 4.
 491                 int turn = firstDirection ^ (corners - 1);
 492                 int directionCycle = 3 == corners ? 0 : nextDirection ^ turn;
 493                 if ((directionCycle ^ turn) != nextDirection) {
 494                     return false; // direction didn't follow cycle
 495                 }
 496                 break;
 497             }
 498             case kQuad_Verb:
 499             case kConic_Verb:
 500             case kCubic_Verb:
 501                 return false; // quadratic, cubic not allowed
 502             case kMove_Verb:
 503                 if (allowPartial && !autoClose && firstDirection) {
 504                     insertClose = true;
 505                     *currVerb -= 1;  // try move again afterwards
 506                     goto addMissingClose;
 507                 }
 508                 last = *pts++;
 509                 closedOrMoved = true;
 510                 break;
 511             default:
 512                 SkDEBUGFAIL("unexpected verb");
 513                 break;
 514         }
 515         *currVerb += 1;
 516         lastDirection = nextDirection;
 517 addMissingClose:
 518         ;
 519     }
 520     // Success if 4 corners and first point equals last
 521     bool result = 4 == corners && (first == last || autoClose);
 522     if (!result) {
 523         // check if we are just an incomplete rectangle, in which case we can
 524         // return true, but not claim to be closed.
 525         // e.g.
 526         //    3 sided rectangle
 527         //    4 sided but the last edge is not long enough to reach the start
 528         //
 529         SkScalar closeX = first.x() - last.x();
 530         SkScalar closeY = first.y() - last.y();
 531         if (closeX && closeY) {
 532             return false;   // we're diagonal, abort (can we ever reach this?)
 533         }
 534         int closeDirection = rect_make_dir(closeX, closeY);
 535         // make sure the close-segment doesn't double-back on itself
 536         if (3 == corners || (4 == corners && closeDirection == lastDirection)) {
 537             result = true;
 538             autoClose = false;  // we are not closed
 539         }
 540     }
 541     if (savePts) {
 542         *ptsPtr = savePts;
 543     }
 544     if (result && isClosed) {
 545         *isClosed = autoClose;
 546     }
 547     if (result && direction) {
 548         *direction = firstDirection == ((lastDirection + 1) & 3) ? kCCW_Direction : kCW_Direction;
 549     }
 550     return result;
 551 }
 552
 553 bool SkPath::isRect(SkRect* rect, bool* isClosed, Direction* direction) const {
 554     SkDEBUGCODE(this->validate();)
 555     int currVerb = 0;
 556     const SkPoint* pts = fPathRef->points();
 557     const SkPoint* first = pts;
 558     if (!this->isRectContour(false, &currVerb, &pts, isClosed, direction)) {
 559         return false;
 560     }
 561     if (rect) {
 562         int32_t num = SkToS32(pts - first);
 563         if (num) {
 564             rect->set(first, num);
 565         } else {
 566             // 'pts' isn't updated for open rects
 567             *rect = this->getBounds();
 568         }
 569     }
 570     return true;
 571 }
 572
 573 bool SkPath::isNestedFillRects(SkRect rects[2], Direction dirs[2]) const {
 574     SkDEBUGCODE(this->validate();)
 575     int currVerb = 0;
 576     const SkPoint* pts = fPathRef->points();
 577     const SkPoint* first = pts;
 578     Direction testDirs[2];
 579     if (!isRectContour(true, &currVerb, &pts, nullptr, &testDirs[0])) {
 580         return false;
 581     }
 582     const SkPoint* last = pts;
 583     SkRect testRects[2];
 584     bool isClosed;
 585     if (isRectContour(false, &currVerb, &pts, &isClosed, &testDirs[1])) {
 586         testRects[0].set(first, SkToS32(last - first));
 587         if (!isClosed) {
 588             pts = fPathRef->points() + fPathRef->countPoints();
 589         }
 590         testRects[1].set(last, SkToS32(pts - last));
 591         if (testRects[0].contains(testRects[1])) {
 592             if (rects) {
 593                 rects[0] = testRects[0];
 594                 rects[1] = testRects[1];
 595             }
 596             if (dirs) {
 597                 dirs[0] = testDirs[0];
 598                 dirs[1] = testDirs[1];
 599             }
 600             return true;
 601         }
 602         if (testRects[1].contains(testRects[0])) {
 603             if (rects) {
 604                 rects[0] = testRects[1];
 605                 rects[1] = testRects[0];
 606             }
 607             if (dirs) {
 608                 dirs[0] = testDirs[1];
 609                 dirs[1] = testDirs[0];
 610             }
 611             return true;
 612         }
 613     }
 614     return false;
 615 }
 616
 617 int SkPath::countPoints() const {
 618     return fPathRef->countPoints();
 619 }
 620
 621 int SkPath::getPoints(SkPoint dst[], int max) const {
 622     SkDEBUGCODE(this->validate();)
 623
 624     SkASSERT(max >= 0);
 625     SkASSERT(!max || dst);
 626     int count = SkMin32(max, fPathRef->countPoints());
 627     sk_careful_memcpy(dst, fPathRef->points(), count * sizeof(SkPoint));
 628     return fPathRef->countPoints();
 629 }
 630
 631 SkPoint SkPath::getPoint(int index) const {
 632     if ((unsigned)index < (unsigned)fPathRef->countPoints()) {
 633         return fPathRef->atPoint(index);
 634     }
 635     return SkPoint::Make(0, 0);
 636 }
 637
 638 int SkPath::countVerbs() const {
 639     return fPathRef->countVerbs();
 640 }
 641
 642 static inline void copy_verbs_reverse(uint8_t* inorderDst,
 643                                       const uint8_t* reversedSrc,
 644                                       int count) {
 645     for (int i = 0; i < count; ++i) {
 646         inorderDst[i] = reversedSrc[~i];
 647     }
 648 }
 649
 650 int SkPath::getVerbs(uint8_t dst[], int max) const {
 651     SkDEBUGCODE(this->validate();)
 652
 653     SkASSERT(max >= 0);
 654     SkASSERT(!max || dst);
 655     int count = SkMin32(max, fPathRef->countVerbs());
 656     copy_verbs_reverse(dst, fPathRef->verbs(), count);
 657     return fPathRef->countVerbs();
 658 }
 659
 660 bool SkPath::getLastPt(SkPoint* lastPt) const {
 661     SkDEBUGCODE(this->validate();)
 662
 663     int count = fPathRef->countPoints();
 664     if (count > 0) {
 665         if (lastPt) {
 666             *lastPt = fPathRef->atPoint(count - 1);
 667         }
 668         return true;
 669     }
 670     if (lastPt) {
 671         lastPt->set(0, 0);
 672     }
 673     return false;
 674 }
 675
 676 void SkPath::setPt(int index, SkScalar x, SkScalar y) {
 677     SkDEBUGCODE(this->validate();)
 678
 679     int count = fPathRef->countPoints();
 680     if (count <= index) {
 681         return;
 682     } else {
 683         SkPathRef::Editor ed(&fPathRef);
 684         ed.atPoint(index)->set(x, y);
 685     }
 686 }
 687
 688 void SkPath::setLastPt(SkScalar x, SkScalar y) {
 689     SkDEBUGCODE(this->validate();)
 690
 691     int count = fPathRef->countPoints();
 692     if (count == 0) {
 693         this->moveTo(x, y);
 694     } else {
 695         SkPathRef::Editor ed(&fPathRef);
 696         ed.atPoint(count-1)->set(x, y);
 697     }
 698 }
 699
 700 void SkPath::setConvexity(Convexity c) {
 701     if (fConvexity != c) {
 702         fConvexity = c;
 703     }
 704 }
 705
 706 //////////////////////////////////////////////////////////////////////////////
 707 //  Construction methods
 708
 709 #define DIRTY_AFTER_EDIT                                        \
 710     do {                                                        \
 711         fConvexity = kUnknown_Convexity;                        \
 712         fFirstDirection = SkPathPriv::kUnknown_FirstDirection;  \
 713     } while (0)
 714
 715 void SkPath::incReserve(U16CPU inc) {
 716     SkDEBUGCODE(this->validate();)
 717     SkPathRef::Editor(&fPathRef, inc, inc);
 718     SkDEBUGCODE(this->validate();)
 719 }
 720
 721 void SkPath::moveTo(SkScalar x, SkScalar y) {
 722     SkDEBUGCODE(this->validate();)
 723
 724     SkPathRef::Editor ed(&fPathRef);
 725
 726     // remember our index
 727     fLastMoveToIndex = fPathRef->countPoints();
 728
 729     ed.growForVerb(kMove_Verb)->set(x, y);
 730
 731     DIRTY_AFTER_EDIT;
 732 }
 733
 734 void SkPath::rMoveTo(SkScalar x, SkScalar y) {
 735     SkPoint pt;
 736     this->getLastPt(&pt);
 737     this->moveTo(pt.fX + x, pt.fY + y);
 738 }
 739
 740 void SkPath::injectMoveToIfNeeded() {
 741     if (fLastMoveToIndex < 0) {
 742         SkScalar x, y;
 743         if (fPathRef->countVerbs() == 0) {
 744             x = y = 0;
 745         } else {
 746             const SkPoint& pt = fPathRef->atPoint(~fLastMoveToIndex);
 747             x = pt.fX;
 748             y = pt.fY;
 749         }
 750         this->moveTo(x, y);
 751     }
 752 }
 753
 754 void SkPath::lineTo(SkScalar x, SkScalar y) {
 755     SkDEBUGCODE(this->validate();)
 756
 757     this->injectMoveToIfNeeded();
 758
 759     SkPathRef::Editor ed(&fPathRef);
 760     ed.growForVerb(kLine_Verb)->set(x, y);
 761
 762     DIRTY_AFTER_EDIT;
 763 }
 764
 765 void SkPath::rLineTo(SkScalar x, SkScalar y) {
 766     this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
 767     SkPoint pt;
 768     this->getLastPt(&pt);
 769     this->lineTo(pt.fX + x, pt.fY + y);
 770 }
 771
 772 void SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
 773     SkDEBUGCODE(this->validate();)
 774
 775     this->injectMoveToIfNeeded();
 776
 777     SkPathRef::Editor ed(&fPathRef);
 778     SkPoint* pts = ed.growForVerb(kQuad_Verb);
 779     pts[0].set(x1, y1);
 780     pts[1].set(x2, y2);
 781
 782     DIRTY_AFTER_EDIT;
 783 }
 784
 785 void SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) {
 786     this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
 787     SkPoint pt;
 788     this->getLastPt(&pt);
 789     this->quadTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2);
 790 }
 791
 792 void SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
 793                      SkScalar w) {
 794     // check for <= 0 or NaN with this test
 795     if (!(w > 0)) {
 796         this->lineTo(x2, y2);
 797     } else if (!SkScalarIsFinite(w)) {
 798         this->lineTo(x1, y1);
 799         this->lineTo(x2, y2);
 800     } else if (SK_Scalar1 == w) {
 801         this->quadTo(x1, y1, x2, y2);
 802     } else {
 803         SkDEBUGCODE(this->validate();)
 804
 805         this->injectMoveToIfNeeded();
 806
 807         SkPathRef::Editor ed(&fPathRef);
 808         SkPoint* pts = ed.growForVerb(kConic_Verb, w);
 809         pts[0].set(x1, y1);
 810         pts[1].set(x2, y2);
 811
 812         DIRTY_AFTER_EDIT;
 813     }
 814 }
 815
 816 void SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2,
 817                       SkScalar w) {
 818     this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
 819     SkPoint pt;
 820     this->getLastPt(&pt);
 821     this->conicTo(pt.fX + dx1, pt.fY + dy1, pt.fX + dx2, pt.fY + dy2, w);
 822 }
 823
 824 void SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
 825                      SkScalar x3, SkScalar y3) {
 826     SkDEBUGCODE(this->validate();)
 827
 828     this->injectMoveToIfNeeded();
 829
 830     SkPathRef::Editor ed(&fPathRef);
 831     SkPoint* pts = ed.growForVerb(kCubic_Verb);
 832     pts[0].set(x1, y1);
 833     pts[1].set(x2, y2);
 834     pts[2].set(x3, y3);
 835
 836     DIRTY_AFTER_EDIT;
 837 }
 838
 839 void SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2,
 840                       SkScalar x3, SkScalar y3) {
 841     this->injectMoveToIfNeeded();  // This can change the result of this->getLastPt().
 842     SkPoint pt;
 843     this->getLastPt(&pt);
 844     this->cubicTo(pt.fX + x1, pt.fY + y1, pt.fX + x2, pt.fY + y2,
 845                   pt.fX + x3, pt.fY + y3);
 846 }
 847
 848 void SkPath::close() {
 849     SkDEBUGCODE(this->validate();)
 850
 851     int count = fPathRef->countVerbs();
 852     if (count > 0) {
 853         switch (fPathRef->atVerb(count - 1)) {
 854             case kLine_Verb:
 855             case kQuad_Verb:
 856             case kConic_Verb:
 857             case kCubic_Verb:
 858             case kMove_Verb: {
 859                 SkPathRef::Editor ed(&fPathRef);
 860                 ed.growForVerb(kClose_Verb);
 861                 break;
 862             }
 863             case kClose_Verb:
 864                 // don't add a close if it's the first verb or a repeat
 865                 break;
 866             default:
 867                 SkDEBUGFAIL("unexpected verb");
 868                 break;
 869         }
 870     }
 871
 872     // signal that we need a moveTo to follow us (unless we're done)
 873 #if 0
 874     if (fLastMoveToIndex >= 0) {
 875         fLastMoveToIndex = ~fLastMoveToIndex;
 876     }
 877 #else
 878     fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
 879 #endif
 880 }
 881
 882 ///////////////////////////////////////////////////////////////////////////////
 883
 884 namespace {
 885
 886 template <unsigned N>
 887 class PointIterator {
 888 public:
 889     PointIterator(SkPath::Direction dir, unsigned startIndex)
 890         : fCurrent(startIndex % N)
 891         , fAdvance(dir == SkPath::kCW_Direction ? 1 : N - 1) { }
 892
 893     const SkPoint& current() const {
 894         SkASSERT(fCurrent < N);
 895         return fPts[fCurrent];
 896     }
 897
 898     const SkPoint& next() {
 899         fCurrent = (fCurrent + fAdvance) % N;
 900         return this->current();
 901     }
 902
 903 protected:
 904     SkPoint fPts[N];
 905
 906 private:
 907     unsigned fCurrent;
 908     unsigned fAdvance;
 909 };
 910
 911 class RectPointIterator : public PointIterator<4> {
 912 public:
 913     RectPointIterator(const SkRect& rect, SkPath::Direction dir, unsigned startIndex)
 914         : PointIterator(dir, startIndex) {
 915
 916         fPts[0] = SkPoint::Make(rect.fLeft, rect.fTop);
 917         fPts[1] = SkPoint::Make(rect.fRight, rect.fTop);
 918         fPts[2] = SkPoint::Make(rect.fRight, rect.fBottom);
 919         fPts[3] = SkPoint::Make(rect.fLeft, rect.fBottom);
 920     }
 921 };
 922
 923 class OvalPointIterator : public PointIterator<4> {
 924 public:
 925     OvalPointIterator(const SkRect& oval, SkPath::Direction dir, unsigned startIndex)
 926         : PointIterator(dir, startIndex) {
 927
 928         const SkScalar cx = oval.centerX();
 929         const SkScalar cy = oval.centerY();
 930
 931         fPts[0] = SkPoint::Make(cx, oval.fTop);
 932         fPts[1] = SkPoint::Make(oval.fRight, cy);
 933         fPts[2] = SkPoint::Make(cx, oval.fBottom);
 934         fPts[3] = SkPoint::Make(oval.fLeft, cy);
 935     }
 936 };
 937
 938 class RRectPointIterator : public PointIterator<8> {
 939 public:
 940     RRectPointIterator(const SkRRect& rrect, SkPath::Direction dir, unsigned startIndex)
 941         : PointIterator(dir, startIndex) {
 942
 943         const SkRect& bounds = rrect.getBounds();
 944         const SkScalar L = bounds.fLeft;
 945         const SkScalar T = bounds.fTop;
 946         const SkScalar R = bounds.fRight;
 947         const SkScalar B = bounds.fBottom;
 948
 949         fPts[0] = SkPoint::Make(L + rrect.radii(SkRRect::kUpperLeft_Corner).fX, T);
 950         fPts[1] = SkPoint::Make(R - rrect.radii(SkRRect::kUpperRight_Corner).fX, T);
 951         fPts[2] = SkPoint::Make(R, T + rrect.radii(SkRRect::kUpperRight_Corner).fY);
 952         fPts[3] = SkPoint::Make(R, B - rrect.radii(SkRRect::kLowerRight_Corner).fY);
 953         fPts[4] = SkPoint::Make(R - rrect.radii(SkRRect::kLowerRight_Corner).fX, B);
 954         fPts[5] = SkPoint::Make(L + rrect.radii(SkRRect::kLowerLeft_Corner).fX, B);
 955         fPts[6] = SkPoint::Make(L, B - rrect.radii(SkRRect::kLowerLeft_Corner).fY);
 956         fPts[7] = SkPoint::Make(L, T + rrect.radii(SkRRect::kUpperLeft_Corner).fY);
 957     }
 958 };
 959
 960 } // anonymous namespace
 961
 962 static void assert_known_direction(int dir) {
 963     SkASSERT(SkPath::kCW_Direction == dir || SkPath::kCCW_Direction == dir);
 964 }
 965
 966 void SkPath::addRect(const SkRect& rect, Direction dir) {
 967     this->addRect(rect, dir, 0);
 968 }
 969
 970 void SkPath::addRect(SkScalar left, SkScalar top, SkScalar right,
 971                      SkScalar bottom, Direction dir) {
 972     this->addRect(SkRect::MakeLTRB(left, top, right, bottom), dir, 0);
 973 }
 974
 975 void SkPath::addRect(const SkRect &rect, Direction dir, unsigned startIndex) {
 976     assert_known_direction(dir);
 977     fFirstDirection = this->hasOnlyMoveTos() ?
 978         (SkPathPriv::FirstDirection)dir : SkPathPriv::kUnknown_FirstDirection;
 979     SkAutoDisableDirectionCheck addc(this);
 980     SkAutoPathBoundsUpdate apbu(this, rect);
 981
 982     SkDEBUGCODE(int initialVerbCount = this->countVerbs());
 983
 984     const int kVerbs = 5; // moveTo + 3x lineTo + close
 985     this->incReserve(kVerbs);
 986
 987     RectPointIterator iter(rect, dir, startIndex);
 988
 989     this->moveTo(iter.current());
 990     this->lineTo(iter.next());
 991     this->lineTo(iter.next());
 992     this->lineTo(iter.next());
 993     this->close();
 994
 995     SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
 996 }
 997
 998 void SkPath::addPoly(const SkPoint pts[], int count, bool close) {
 999     SkDEBUGCODE(this->validate();)
1000     if (count <= 0) {
1001         return;
1002     }
1003
1004     fLastMoveToIndex = fPathRef->countPoints();
1005
1006     // +close makes room for the extra kClose_Verb
1007     SkPathRef::Editor ed(&fPathRef, count+close, count);
1008
1009     ed.growForVerb(kMove_Verb)->set(pts[0].fX, pts[0].fY);
1010     if (count > 1) {
1011         SkPoint* p = ed.growForRepeatedVerb(kLine_Verb, count - 1);
1012         memcpy(p, &pts[1], (count-1) * sizeof(SkPoint));
1013     }
1014
1015     if (close) {
1016         ed.growForVerb(kClose_Verb);
1017         fLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
1018     }
1019
1020     DIRTY_AFTER_EDIT;
1021     SkDEBUGCODE(this->validate();)
1022 }
1023
1024 #include "SkGeometry.h"
1025
1026 static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
1027                               SkPoint* pt) {
1028     if (0 == sweepAngle && (0 == startAngle || SkIntToScalar(360) == startAngle)) {
1029         // Chrome uses this path to move into and out of ovals. If not
1030         // treated as a special case the moves can distort the oval's
1031         // bounding box (and break the circle special case).
1032         pt->set(oval.fRight, oval.centerY());
1033         return true;
1034     } else if (0 == oval.width() && 0 == oval.height()) {
1035         // Chrome will sometimes create 0 radius round rects. Having degenerate
1036         // quad segments in the path prevents the path from being recognized as
1037         // a rect.
1038         // TODO: optimizing the case where only one of width or height is zero
1039         // should also be considered. This case, however, doesn't seem to be
1040         // as common as the single point case.
1041         pt->set(oval.fRight, oval.fTop);
1042         return true;
1043     }
1044     return false;
1045 }
1046
1047 // Return the unit vectors pointing at the start/stop points for the given start/sweep angles
1048 //
1049 static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle,
1050                                    SkVector* startV, SkVector* stopV, SkRotationDirection* dir) {
1051     startV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle), &startV->fX);
1052     stopV->fY = SkScalarSinCos(SkDegreesToRadians(startAngle + sweepAngle), &stopV->fX);
1053
1054     /*  If the sweep angle is nearly (but less than) 360, then due to precision
1055      loss in radians-conversion and/or sin/cos, we may end up with coincident
1056      vectors, which will fool SkBuildQuadArc into doing nothing (bad) instead
1057      of drawing a nearly complete circle (good).
1058      e.g. canvas.drawArc(0, 359.99, ...)
1059      -vs- canvas.drawArc(0, 359.9, ...)
1060      We try to detect this edge case, and tweak the stop vector
1061      */
1062     if (*startV == *stopV) {
1063         SkScalar sw = SkScalarAbs(sweepAngle);
1064         if (sw < SkIntToScalar(360) && sw > SkIntToScalar(359)) {
1065             SkScalar stopRad = SkDegreesToRadians(startAngle + sweepAngle);
1066             // make a guess at a tiny angle (in radians) to tweak by
1067             SkScalar deltaRad = SkScalarCopySign(SK_Scalar1/512, sweepAngle);
1068             // not sure how much will be enough, so we use a loop
1069             do {
1070                 stopRad -= deltaRad;
1071                 stopV->fY = SkScalarSinCos(stopRad, &stopV->fX);
1072             } while (*startV == *stopV);
1073         }
1074     }
1075     *dir = sweepAngle > 0 ? kCW_SkRotationDirection : kCCW_SkRotationDirection;
1076 }
1077
1078 /**
1079  *  If this returns 0, then the caller should just line-to the singlePt, else it should
1080  *  ignore singlePt and append the specified number of conics.
1081  */
1082 static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop,
1083                             SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc],
1084                             SkPoint* singlePt) {
1085     SkMatrix    matrix;
1086
1087     matrix.setScale(SkScalarHalf(oval.width()), SkScalarHalf(oval.height()));
1088     matrix.postTranslate(oval.centerX(), oval.centerY());
1089
1090     int count = SkConic::BuildUnitArc(start, stop, dir, &matrix, conics);
1091     if (0 == count) {
1092         matrix.mapXY(start.x(), start.y(), singlePt);
1093     }
1094     return count;
1095 }
1096
1097 void SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[],
1098                           Direction dir) {
1099     SkRRect rrect;
1100     rrect.setRectRadii(rect, (const SkVector*) radii);
1101     this->addRRect(rrect, dir);
1102 }
1103
1104 void SkPath::addRRect(const SkRRect& rrect, Direction dir) {
1105     // legacy start indices: 6 (CW) and 7(CCW)
1106     this->addRRect(rrect, dir, dir == kCW_Direction ? 6 : 7);
1107 }
1108
1109 void SkPath::addRRect(const SkRRect &rrect, Direction dir, unsigned startIndex) {
1110         assert_known_direction(dir);
1111
1112         if (rrect.isEmpty()) {
1113             return;
1114         }
1115
1116         bool isRRect = hasOnlyMoveTos();
1117         const SkRect& bounds = rrect.getBounds();
1118
1119         if (rrect.isRect()) {
1120             // degenerate(rect) => radii points are collapsing
1121             this->addRect(bounds, dir, (startIndex + 1) / 2);
1122         } else if (rrect.isOval()) {
1123             // degenerate(oval) => line points are collapsing
1124             this->addOval(bounds, dir, startIndex / 2);
1125         } else {
1126             fFirstDirection = this->hasOnlyMoveTos() ?
1127                                 (SkPathPriv::FirstDirection)dir : SkPathPriv::kUnknown_FirstDirection;
1128
1129             SkAutoPathBoundsUpdate apbu(this, bounds);
1130             SkAutoDisableDirectionCheck addc(this);
1131
1132             // we start with a conic on odd indices when moving CW vs. even indices when moving CCW
1133             const bool startsWithConic = ((startIndex & 1) == (dir == kCW_Direction));
1134             const SkScalar weight = SK_ScalarRoot2Over2;
1135
1136             SkDEBUGCODE(int initialVerbCount = this->countVerbs());
1137             const int kVerbs = startsWithConic
1138                 ? 9   // moveTo + 4x conicTo + 3x lineTo + close
1139                 : 10; // moveTo + 4x lineTo + 4x conicTo + close
1140             this->incReserve(kVerbs);
1141
1142             RRectPointIterator rrectIter(rrect, dir, startIndex);
1143             // Corner iterator indices follow the collapsed radii model,
1144             // adjusted such that the start pt is "behind" the radii start pt.
1145             const unsigned rectStartIndex = startIndex / 2 + (dir == kCW_Direction ? 0 : 1);
1146             RectPointIterator rectIter(bounds, dir, rectStartIndex);
1147
1148             this->moveTo(rrectIter.current());
1149             if (startsWithConic) {
1150                 for (unsigned i = 0; i < 3; ++i) {
1151                     this->conicTo(rectIter.next(), rrectIter.next(), weight);
1152                     this->lineTo(rrectIter.next());
1153                 }
1154                 this->conicTo(rectIter.next(), rrectIter.next(), weight);
1155                 // final lineTo handled by close().
1156             } else {
1157                 for (unsigned i = 0; i < 4; ++i) {
1158                     this->lineTo(rrectIter.next());
1159                     this->conicTo(rectIter.next(), rrectIter.next(), weight);
1160                 }
1161             }
1162             this->close();
1163
1164             SkPathRef::Editor ed(&fPathRef);
1165             ed.setIsRRect(isRRect, dir, startIndex % 8);
1166
1167             SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
1168         }
1169
1170         SkDEBUGCODE(fPathRef->validate();)
1171 }
1172
1173 bool SkPath::hasOnlyMoveTos() const {
1174     int count = fPathRef->countVerbs();
1175     const uint8_t* verbs = const_cast<const SkPathRef*>(fPathRef.get())->verbsMemBegin();
1176     for (int i = 0; i < count; ++i) {
1177         if (*verbs == kLine_Verb ||
1178             *verbs == kQuad_Verb ||
1179             *verbs == kConic_Verb ||
1180             *verbs == kCubic_Verb) {
1181             return false;
1182         }
1183         ++verbs;
1184     }
1185     return true;
1186 }
1187
1188 bool SkPath::isZeroLength() const {
1189     int count = fPathRef->countPoints();
1190     if (count < 2) {
1191         return true;
1192     }
1193     const SkPoint* pts = fPathRef.get()->points();
1194     const SkPoint& first = *pts;
1195     for (int index = 1; index < count; ++index) {
1196         if (first != pts[index]) {
1197             return false;
1198         }
1199     }
1200     return true;
1201 }
1202
1203 void SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry,
1204                           Direction dir) {
1205     assert_known_direction(dir);
1206
1207     if (rx < 0 || ry < 0) {
1208         SkErrorInternals::SetError( kInvalidArgument_SkError,
1209                                     "I got %f and %f as radii to SkPath::AddRoundRect, "
1210                                     "but negative radii are not allowed.",
1211                                     SkScalarToDouble(rx), SkScalarToDouble(ry) );
1212         return;
1213     }
1214
1215     SkRRect rrect;
1216     rrect.setRectXY(rect, rx, ry);
1217     this->addRRect(rrect, dir);
1218 }
1219
1220 void SkPath::addOval(const SkRect& oval, Direction dir) {
1221     // legacy start index: 1
1222     this->addOval(oval, dir, 1);
1223 }
1224
1225 void SkPath::addOval(const SkRect &oval, Direction dir, unsigned startPointIndex) {
1226     assert_known_direction(dir);
1227
1228     /* If addOval() is called after previous moveTo(),
1229        this path is still marked as an oval. This is used to
1230        fit into WebKit's calling sequences.
1231        We can't simply check isEmpty() in this case, as additional
1232        moveTo() would mark the path non empty.
1233      */
1234     bool isOval = hasOnlyMoveTos();
1235     if (isOval) {
1236         fFirstDirection = (SkPathPriv::FirstDirection)dir;
1237     } else {
1238         fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
1239     }
1240
1241     SkAutoDisableDirectionCheck addc(this);
1242     SkAutoPathBoundsUpdate apbu(this, oval);
1243
1244     SkDEBUGCODE(int initialVerbCount = this->countVerbs());
1245     const int kVerbs = 6; // moveTo + 4x conicTo + close
1246     this->incReserve(kVerbs);
1247
1248     OvalPointIterator ovalIter(oval, dir, startPointIndex);
1249     // The corner iterator pts are tracking "behind" the oval/radii pts.
1250     RectPointIterator rectIter(oval, dir, startPointIndex + (dir == kCW_Direction ? 0 : 1));
1251     const SkScalar weight = SK_ScalarRoot2Over2;
1252
1253     this->moveTo(ovalIter.current());
1254     for (unsigned i = 0; i < 4; ++i) {
1255         this->conicTo(rectIter.next(), ovalIter.next(), weight);
1256     }
1257     this->close();
1258
1259     SkASSERT(this->countVerbs() == initialVerbCount + kVerbs);
1260
1261     SkPathRef::Editor ed(&fPathRef);
1262
1263     ed.setIsOval(isOval, kCCW_Direction == dir, startPointIndex % 4);
1264 }
1265
1266 void SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, Direction dir) {
1267     if (r > 0) {
1268         this->addOval(SkRect::MakeLTRB(x - r, y - r, x + r, y + r), dir);
1269     }
1270 }
1271
1272 void SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle,
1273                    bool forceMoveTo) {
1274     if (oval.width() < 0 || oval.height() < 0) {
1275         return;
1276     }
1277
1278     if (fPathRef->countVerbs() == 0) {
1279         forceMoveTo = true;
1280     }
1281
1282     SkPoint lonePt;
1283     if (arc_is_lone_point(oval, startAngle, sweepAngle, &lonePt)) {
1284         forceMoveTo ? this->moveTo(lonePt) : this->lineTo(lonePt);
1285         return;
1286     }
1287
1288     SkVector startV, stopV;
1289     SkRotationDirection dir;
1290     angles_to_unit_vectors(startAngle, sweepAngle, &startV, &stopV, &dir);
1291
1292     SkPoint singlePt;
1293     SkConic conics[SkConic::kMaxConicsForArc];
1294     int count = build_arc_conics(oval, startV, stopV, dir, conics, &singlePt);
1295     if (count) {
1296         this->incReserve(count * 2 + 1);
1297         const SkPoint& pt = conics[0].fPts[0];
1298         forceMoveTo ? this->moveTo(pt) : this->lineTo(pt);
1299         for (int i = 0; i < count; ++i) {
1300             this->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW);
1301         }
1302     } else {
1303         forceMoveTo ? this->moveTo(singlePt) : this->lineTo(singlePt);
1304     }
1305 }
1306
1307 // This converts the SVG arc to conics.
1308 // Partly adapted from Niko's code in kdelibs/kdecore/svgicons.
1309 // Then transcribed from webkit/chrome's SVGPathNormalizer::decomposeArcToCubic()
1310 // See also SVG implementation notes:
1311 // http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
1312 // Note that arcSweep bool value is flipped from the original implementation.
1313 void SkPath::arcTo(SkScalar rx, SkScalar ry, SkScalar angle, SkPath::ArcSize arcLarge,
1314                    SkPath::Direction arcSweep, SkScalar x, SkScalar y) {
1315     this->injectMoveToIfNeeded();
1316     SkPoint srcPts[2];
1317     this->getLastPt(&srcPts[0]);
1318     // If rx = 0 or ry = 0 then this arc is treated as a straight line segment (a "lineto")
1319     // joining the endpoints.
1320     // http://www.w3.org/TR/SVG/implnote.html#ArcOutOfRangeParameters
1321     if (!rx || !ry) {
1322         this->lineTo(x, y);
1323         return;
1324     }
1325     // If the current point and target point for the arc are identical, it should be treated as a
1326     // zero length path. This ensures continuity in animations.
1327     srcPts[1].set(x, y);
1328     if (srcPts[0] == srcPts[1]) {
1329         this->lineTo(x, y);
1330         return;
1331     }
1332     rx = SkScalarAbs(rx);
1333     ry = SkScalarAbs(ry);
1334     SkVector midPointDistance = srcPts[0] - srcPts[1];
1335     midPointDistance *= 0.5f;
1336
1337     SkMatrix pointTransform;
1338     pointTransform.setRotate(-angle);
1339
1340     SkPoint transformedMidPoint;
1341     pointTransform.mapPoints(&transformedMidPoint, &midPointDistance, 1);
1342     SkScalar squareRx = rx * rx;
1343     SkScalar squareRy = ry * ry;
1344     SkScalar squareX = transformedMidPoint.fX * transformedMidPoint.fX;
1345     SkScalar squareY = transformedMidPoint.fY * transformedMidPoint.fY;
1346
1347     // Check if the radii are big enough to draw the arc, scale radii if not.
1348     // http://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
1349     SkScalar radiiScale = squareX / squareRx + squareY / squareRy;
1350     if (radiiScale > 1) {
1351         radiiScale = SkScalarSqrt(radiiScale);
1352         rx *= radiiScale;
1353         ry *= radiiScale;
1354     }
1355
1356     pointTransform.setScale(1 / rx, 1 / ry);
1357     pointTransform.preRotate(-angle);
1358
1359     SkPoint unitPts[2];
1360     pointTransform.mapPoints(unitPts, srcPts, (int) SK_ARRAY_COUNT(unitPts));
1361     SkVector delta = unitPts[1] - unitPts[0];
1362
1363     SkScalar d = delta.fX * delta.fX + delta.fY * delta.fY;
1364     SkScalar scaleFactorSquared = SkTMax(1 / d - 0.25f, 0.f);
1365
1366     SkScalar scaleFactor = SkScalarSqrt(scaleFactorSquared);
1367     if (SkToBool(arcSweep) != SkToBool(arcLarge)) {  // flipped from the original implementation
1368         scaleFactor = -scaleFactor;
1369     }
1370     delta.scale(scaleFactor);
1371     SkPoint centerPoint = unitPts[0] + unitPts[1];
1372     centerPoint *= 0.5f;
1373     centerPoint.offset(-delta.fY, delta.fX);
1374     unitPts[0] -= centerPoint;
1375     unitPts[1] -= centerPoint;
1376     SkScalar theta1 = SkScalarATan2(unitPts[0].fY, unitPts[0].fX);
1377     SkScalar theta2 = SkScalarATan2(unitPts[1].fY, unitPts[1].fX);
1378     SkScalar thetaArc = theta2 - theta1;
1379     if (thetaArc < 0 && !arcSweep) {  // arcSweep flipped from the original implementation
1380         thetaArc += SK_ScalarPI * 2;
1381     } else if (thetaArc > 0 && arcSweep) {  // arcSweep flipped from the original implementation
1382         thetaArc -= SK_ScalarPI * 2;
1383     }
1384     pointTransform.setRotate(angle);
1385     pointTransform.preScale(rx, ry);
1386
1387     int segments = SkScalarCeilToInt(SkScalarAbs(thetaArc / (SK_ScalarPI / 2)));
1388     SkScalar thetaWidth = thetaArc / segments;
1389     SkScalar t = SkScalarTan(0.5f * thetaWidth);
1390     if (!SkScalarIsFinite(t)) {
1391         return;
1392     }
1393     SkScalar startTheta = theta1;
1394     SkScalar w = SkScalarSqrt(SK_ScalarHalf + SkScalarCos(thetaWidth) * SK_ScalarHalf);
1395     for (int i = 0; i < segments; ++i) {
1396         SkScalar endTheta = startTheta + thetaWidth;
1397         SkScalar cosEndTheta, sinEndTheta = SkScalarSinCos(endTheta, &cosEndTheta);
1398
1399         unitPts[1].set(cosEndTheta, sinEndTheta);
1400         unitPts[1] += centerPoint;
1401         unitPts[0] = unitPts[1];
1402         unitPts[0].offset(t * sinEndTheta, -t * cosEndTheta);
1403         SkPoint mapped[2];
1404         pointTransform.mapPoints(mapped, unitPts, (int) SK_ARRAY_COUNT(unitPts));
1405         this->conicTo(mapped[0], mapped[1], w);
1406         startTheta = endTheta;
1407     }
1408 }
1409
1410 void SkPath::rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, SkPath::ArcSize largeArc,
1411                     SkPath::Direction sweep, SkScalar dx, SkScalar dy) {
1412     SkPoint currentPoint;
1413     this->getLastPt(&currentPoint);
1414     this->arcTo(rx, ry, xAxisRotate, largeArc, sweep, currentPoint.fX + dx, currentPoint.fY + dy);
1415 }
1416
1417 void SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) {
1418     if (oval.isEmpty() || 0 == sweepAngle) {
1419         return;
1420     }
1421
1422     const SkScalar kFullCircleAngle = SkIntToScalar(360);
1423
1424     if (sweepAngle >= kFullCircleAngle || sweepAngle <= -kFullCircleAngle) {
1425         // We can treat the arc as an oval if it begins at one of our legal starting positions.
1426         // See SkPath::addOval() docs.
1427         SkScalar startOver90 = startAngle / 90.f;
1428         SkScalar startOver90I = SkScalarRoundToScalar(startOver90);
1429         SkScalar error = startOver90 - startOver90I;
1430         if (SkScalarNearlyEqual(error, 0)) {
1431             // Index 1 is at startAngle == 0.
1432             SkScalar startIndex = std::fmod(startOver90I + 1.f, 4.f);
1433             startIndex = startIndex < 0 ? startIndex + 4.f : startIndex;
1434             this->addOval(oval, sweepAngle > 0 ? kCW_Direction : kCCW_Direction,
1435                           (unsigned) startIndex);
1436             return;
1437         }
1438     }
1439     this->arcTo(oval, startAngle, sweepAngle, true);
1440 }
1441
1442 /*
1443     Need to handle the case when the angle is sharp, and our computed end-points
1444     for the arc go behind pt1 and/or p2...
1445 */
1446 void SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) {
1447     if (radius == 0) {
1448         this->lineTo(x1, y1);
1449         return;
1450     }
1451
1452     SkVector before, after;
1453
1454     // need to know our prev pt so we can construct tangent vectors
1455     {
1456         SkPoint start;
1457         this->getLastPt(&start);
1458         // Handle degenerate cases by adding a line to the first point and
1459         // bailing out.
1460         before.setNormalize(x1 - start.fX, y1 - start.fY);
1461         after.setNormalize(x2 - x1, y2 - y1);
1462     }
1463
1464     SkScalar cosh = SkPoint::DotProduct(before, after);
1465     SkScalar sinh = SkPoint::CrossProduct(before, after);
1466
1467     if (SkScalarNearlyZero(sinh)) {   // angle is too tight
1468         this->lineTo(x1, y1);
1469         return;
1470     }
1471
1472     SkScalar dist = SkScalarAbs(SkScalarMulDiv(radius, SK_Scalar1 - cosh, sinh));
1473
1474     SkScalar xx = x1 - SkScalarMul(dist, before.fX);
1475     SkScalar yy = y1 - SkScalarMul(dist, before.fY);
1476     after.setLength(dist);
1477     this->lineTo(xx, yy);
1478     SkScalar weight = SkScalarSqrt(SK_ScalarHalf + cosh * SK_ScalarHalf);
1479     this->conicTo(x1, y1, x1 + after.fX, y1 + after.fY, weight);
1480 }
1481
1482 ///////////////////////////////////////////////////////////////////////////////
1483
1484 void SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) {
1485     SkMatrix matrix;
1486
1487     matrix.setTranslate(dx, dy);
1488     this->addPath(path, matrix, mode);
1489 }
1490
1491 void SkPath::addPath(const SkPath& path, const SkMatrix& matrix, AddPathMode mode) {
1492     SkPathRef::Editor(&fPathRef, path.countVerbs(), path.countPoints());
1493
1494     RawIter iter(path);
1495     SkPoint pts[4];
1496     Verb    verb;
1497
1498     SkMatrix::MapPtsProc proc = matrix.getMapPtsProc();
1499     bool firstVerb = true;
1500     while ((verb = iter.next(pts)) != kDone_Verb) {
1501         switch (verb) {
1502             case kMove_Verb:
1503                 proc(matrix, &pts[0], &pts[0], 1);
1504                 if (firstVerb && mode == kExtend_AddPathMode && !isEmpty()) {
1505                     injectMoveToIfNeeded(); // In case last contour is closed
1506                     this->lineTo(pts[0]);
1507                 } else {
1508                     this->moveTo(pts[0]);
1509                 }
1510                 break;
1511             case kLine_Verb:
1512                 proc(matrix, &pts[1], &pts[1], 1);
1513                 this->lineTo(pts[1]);
1514                 break;
1515             case kQuad_Verb:
1516                 proc(matrix, &pts[1], &pts[1], 2);
1517                 this->quadTo(pts[1], pts[2]);
1518                 break;
1519             case kConic_Verb:
1520                 proc(matrix, &pts[1], &pts[1], 2);
1521                 this->conicTo(pts[1], pts[2], iter.conicWeight());
1522                 break;
1523             case kCubic_Verb:
1524                 proc(matrix, &pts[1], &pts[1], 3);
1525                 this->cubicTo(pts[1], pts[2], pts[3]);
1526                 break;
1527             case kClose_Verb:
1528                 this->close();
1529                 break;
1530             default:
1531                 SkDEBUGFAIL("unknown verb");
1532         }
1533         firstVerb = false;
1534     }
1535 }
1536
1537 ///////////////////////////////////////////////////////////////////////////////
1538
1539 static int pts_in_verb(unsigned verb) {
1540     static const uint8_t gPtsInVerb[] = {
1541         1,  // kMove
1542         1,  // kLine
1543         2,  // kQuad
1544         2,  // kConic
1545         3,  // kCubic
1546         0,  // kClose
1547         0   // kDone
1548     };
1549
1550     SkASSERT(verb < SK_ARRAY_COUNT(gPtsInVerb));
1551     return gPtsInVerb[verb];
1552 }
1553
1554 // ignore the last point of the 1st contour
1555 void SkPath::reversePathTo(const SkPath& path) {
1556     int i, vcount = path.fPathRef->countVerbs();
1557     // exit early if the path is empty, or just has a moveTo.
1558     if (vcount < 2) {
1559         return;
1560     }
1561
1562     SkPathRef::Editor(&fPathRef, vcount, path.countPoints());
1563
1564     const uint8_t*  verbs = path.fPathRef->verbs();
1565     const SkPoint*  pts = path.fPathRef->points();
1566     const SkScalar* conicWeights = path.fPathRef->conicWeights();
1567
1568     SkASSERT(verbs[~0] == kMove_Verb);
1569     for (i = 1; i < vcount; ++i) {
1570         unsigned v = verbs[~i];
1571         int n = pts_in_verb(v);
1572         if (n == 0) {
1573             break;
1574         }
1575         pts += n;
1576         conicWeights += (SkPath::kConic_Verb == v);
1577     }
1578
1579     while (--i > 0) {
1580         switch (verbs[~i]) {
1581             case kLine_Verb:
1582                 this->lineTo(pts[-1].fX, pts[-1].fY);
1583                 break;
1584             case kQuad_Verb:
1585                 this->quadTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY);
1586                 break;
1587             case kConic_Verb:
1588                 this->conicTo(pts[-1], pts[-2], *--conicWeights);
1589                 break;
1590             case kCubic_Verb:
1591                 this->cubicTo(pts[-1].fX, pts[-1].fY, pts[-2].fX, pts[-2].fY,
1592                               pts[-3].fX, pts[-3].fY);
1593                 break;
1594             default:
1595                 SkDEBUGFAIL("bad verb");
1596                 break;
1597         }
1598         pts -= pts_in_verb(verbs[~i]);
1599     }
1600 }
1601
1602 void SkPath::reverseAddPath(const SkPath& src) {
1603     SkPathRef::Editor ed(&fPathRef, src.fPathRef->countPoints(), src.fPathRef->countVerbs());
1604
1605     const SkPoint* pts = src.fPathRef->pointsEnd();
1606     // we will iterator through src's verbs backwards
1607     const uint8_t* verbs = src.fPathRef->verbsMemBegin(); // points at the last verb
1608     const uint8_t* verbsEnd = src.fPathRef->verbs(); // points just past the first verb
1609     const SkScalar* conicWeights = src.fPathRef->conicWeightsEnd();
1610
1611     bool needMove = true;
1612     bool needClose = false;
1613     while (verbs < verbsEnd) {
1614         uint8_t v = *(verbs++);
1615         int n = pts_in_verb(v);
1616
1617         if (needMove) {
1618             --pts;
1619             this->moveTo(pts->fX, pts->fY);
1620             needMove = false;
1621         }
1622         pts -= n;
1623         switch (v) {
1624             case kMove_Verb:
1625                 if (needClose) {
1626                     this->close();
1627                     needClose = false;
1628                 }
1629                 needMove = true;
1630                 pts += 1;   // so we see the point in "if (needMove)" above
1631                 break;
1632             case kLine_Verb:
1633                 this->lineTo(pts[0]);
1634                 break;
1635             case kQuad_Verb:
1636                 this->quadTo(pts[1], pts[0]);
1637                 break;
1638             case kConic_Verb:
1639                 this->conicTo(pts[1], pts[0], *--conicWeights);
1640                 break;
1641             case kCubic_Verb:
1642                 this->cubicTo(pts[2], pts[1], pts[0]);
1643                 break;
1644             case kClose_Verb:
1645                 needClose = true;
1646                 break;
1647             default:
1648                 SkDEBUGFAIL("unexpected verb");
1649         }
1650     }
1651 }
1652
1653 ///////////////////////////////////////////////////////////////////////////////
1654
1655 void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const {
1656     SkMatrix    matrix;
1657
1658     matrix.setTranslate(dx, dy);
1659     this->transform(matrix, dst);
1660 }
1661
1662 static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4],
1663                                int level = 2) {
1664     if (--level >= 0) {
1665         SkPoint tmp[7];
1666
1667         SkChopCubicAtHalf(pts, tmp);
1668         subdivide_cubic_to(path, &tmp[0], level);
1669         subdivide_cubic_to(path, &tmp[3], level);
1670     } else {
1671         path->cubicTo(pts[1], pts[2], pts[3]);
1672     }
1673 }
1674
1675 void SkPath::transform(const SkMatrix& matrix, SkPath* dst) const {
1676     SkDEBUGCODE(this->validate();)
1677     if (dst == nullptr) {
1678         dst = (SkPath*)this;
1679     }
1680
1681     if (matrix.hasPerspective()) {
1682         SkPath  tmp;
1683         tmp.fFillType = fFillType;
1684
1685         SkPath::Iter    iter(*this, false);
1686         SkPoint         pts[4];
1687         SkPath::Verb    verb;
1688
1689         while ((verb = iter.next(pts, false)) != kDone_Verb) {
1690             switch (verb) {
1691                 case kMove_Verb:
1692                     tmp.moveTo(pts[0]);
1693                     break;
1694                 case kLine_Verb:
1695                     tmp.lineTo(pts[1]);
1696                     break;
1697                 case kQuad_Verb:
1698                     // promote the quad to a conic
1699                     tmp.conicTo(pts[1], pts[2],
1700                                 SkConic::TransformW(pts, SK_Scalar1, matrix));
1701                     break;
1702                 case kConic_Verb:
1703                     tmp.conicTo(pts[1], pts[2],
1704                                 SkConic::TransformW(pts, iter.conicWeight(), matrix));
1705                     break;
1706                 case kCubic_Verb:
1707                     subdivide_cubic_to(&tmp, pts);
1708                     break;
1709                 case kClose_Verb:
1710                     tmp.close();
1711                     break;
1712                 default:
1713                     SkDEBUGFAIL("unknown verb");
1714                     break;
1715             }
1716         }
1717
1718         dst->swap(tmp);
1719         SkPathRef::Editor ed(&dst->fPathRef);
1720         matrix.mapPoints(ed.points(), ed.pathRef()->countPoints());
1721         dst->fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
1722     } else {
1723         SkPathRef::CreateTransformedCopy(&dst->fPathRef, *fPathRef.get(), matrix);
1724
1725         if (this != dst) {
1726             dst->fFillType = fFillType;
1727             dst->fConvexity = fConvexity;
1728             dst->fIsVolatile = fIsVolatile;
1729         }
1730
1731         if (SkPathPriv::kUnknown_FirstDirection == fFirstDirection) {
1732             dst->fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
1733         } else {
1734             SkScalar det2x2 =
1735                 SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) -
1736                 SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY));
1737             if (det2x2 < 0) {
1738                 dst->fFirstDirection = SkPathPriv::OppositeFirstDirection(
1739                         (SkPathPriv::FirstDirection)fFirstDirection.load());
1740             } else if (det2x2 > 0) {
1741                 dst->fFirstDirection = fFirstDirection.load();
1742             } else {
1743                 dst->fConvexity = kUnknown_Convexity;
1744                 dst->fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
1745             }
1746         }
1747
1748         SkDEBUGCODE(dst->validate();)
1749     }
1750 }
1751
1752 ///////////////////////////////////////////////////////////////////////////////
1753 ///////////////////////////////////////////////////////////////////////////////
1754
1755 enum SegmentState {
1756     kEmptyContour_SegmentState,   // The current contour is empty. We may be
1757                                   // starting processing or we may have just
1758                                   // closed a contour.
1759     kAfterMove_SegmentState,      // We have seen a move, but nothing else.
1760     kAfterPrimitive_SegmentState  // We have seen a primitive but not yet
1761                                   // closed the path. Also the initial state.
1762 };
1763
1764 SkPath::Iter::Iter() {
1765 #ifdef SK_DEBUG
1766     fPts = nullptr;
1767     fConicWeights = nullptr;
1768     fMoveTo.fX = fMoveTo.fY = fLastPt.fX = fLastPt.fY = 0;
1769     fForceClose = fCloseLine = false;
1770     fSegmentState = kEmptyContour_SegmentState;
1771 #endif
1772     // need to init enough to make next() harmlessly return kDone_Verb
1773     fVerbs = nullptr;
1774     fVerbStop = nullptr;
1775     fNeedClose = false;
1776 }
1777
1778 SkPath::Iter::Iter(const SkPath& path, bool forceClose) {
1779     this->setPath(path, forceClose);
1780 }
1781
1782 void SkPath::Iter::setPath(const SkPath& path, bool forceClose) {
1783     fPts = path.fPathRef->points();
1784     fVerbs = path.fPathRef->verbs();
1785     fVerbStop = path.fPathRef->verbsMemBegin();
1786     fConicWeights = path.fPathRef->conicWeights() - 1; // begin one behind
1787     fLastPt.fX = fLastPt.fY = 0;
1788     fMoveTo.fX = fMoveTo.fY = 0;
1789     fForceClose = SkToU8(forceClose);
1790     fNeedClose = false;
1791     fSegmentState = kEmptyContour_SegmentState;
1792 }
1793
1794 bool SkPath::Iter::isClosedContour() const {
1795     if (fVerbs == nullptr || fVerbs == fVerbStop) {
1796         return false;
1797     }
1798     if (fForceClose) {
1799         return true;
1800     }
1801
1802     const uint8_t* verbs = fVerbs;
1803     const uint8_t* stop = fVerbStop;
1804
1805     if (kMove_Verb == *(verbs - 1)) {
1806         verbs -= 1; // skip the initial moveto
1807     }
1808
1809     while (verbs > stop) {
1810         // verbs points one beyond the current verb, decrement first.
1811         unsigned v = *(--verbs);
1812         if (kMove_Verb == v) {
1813             break;
1814         }
1815         if (kClose_Verb == v) {
1816             return true;
1817         }
1818     }
1819     return false;
1820 }
1821
1822 SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) {
1823     SkASSERT(pts);
1824     if (fLastPt != fMoveTo) {
1825         // A special case: if both points are NaN, SkPoint::operation== returns
1826         // false, but the iterator expects that they are treated as the same.
1827         // (consider SkPoint is a 2-dimension float point).
1828         if (SkScalarIsNaN(fLastPt.fX) || SkScalarIsNaN(fLastPt.fY) ||
1829             SkScalarIsNaN(fMoveTo.fX) || SkScalarIsNaN(fMoveTo.fY)) {
1830             return kClose_Verb;
1831         }
1832
1833         pts[0] = fLastPt;
1834         pts[1] = fMoveTo;
1835         fLastPt = fMoveTo;
1836         fCloseLine = true;
1837         return kLine_Verb;
1838     } else {
1839         pts[0] = fMoveTo;
1840         return kClose_Verb;
1841     }
1842 }
1843
1844 const SkPoint& SkPath::Iter::cons_moveTo() {
1845     if (fSegmentState == kAfterMove_SegmentState) {
1846         // Set the first return pt to the move pt
1847         fSegmentState = kAfterPrimitive_SegmentState;
1848         return fMoveTo;
1849     } else {
1850         SkASSERT(fSegmentState == kAfterPrimitive_SegmentState);
1851          // Set the first return pt to the last pt of the previous primitive.
1852         return fPts[-1];
1853     }
1854 }
1855
1856 void SkPath::Iter::consumeDegenerateSegments(bool exact) {
1857     // We need to step over anything that will not move the current draw point
1858     // forward before the next move is seen
1859     const uint8_t* lastMoveVerb = 0;
1860     const SkPoint* lastMovePt = 0;
1861     const SkScalar* lastMoveWeight = nullptr;
1862     SkPoint lastPt = fLastPt;
1863     while (fVerbs != fVerbStop) {
1864         unsigned verb = *(fVerbs - 1); // fVerbs is one beyond the current verb
1865         switch (verb) {
1866             case kMove_Verb:
1867                 // Keep a record of this most recent move
1868                 lastMoveVerb = fVerbs;
1869                 lastMovePt = fPts;
1870                 lastMoveWeight = fConicWeights;
1871                 lastPt = fPts[0];
1872                 fVerbs--;
1873                 fPts++;
1874                 break;
1875
1876             case kClose_Verb:
1877                 // A close when we are in a segment is always valid except when it
1878                 // follows a move which follows a segment.
1879                 if (fSegmentState == kAfterPrimitive_SegmentState && !lastMoveVerb) {
1880                     return;
1881                 }
1882                 // A close at any other time must be ignored
1883                 fVerbs--;
1884                 break;
1885
1886             case kLine_Verb:
1887                 if (!IsLineDegenerate(lastPt, fPts[0], exact)) {
1888                     if (lastMoveVerb) {
1889                         fVerbs = lastMoveVerb;
1890                         fPts = lastMovePt;
1891                         fConicWeights = lastMoveWeight;
1892                         return;
1893                     }
1894                     return;
1895                 }
1896                 // Ignore this line and continue
1897                 fVerbs--;
1898                 fPts++;
1899                 break;
1900
1901             case kConic_Verb:
1902             case kQuad_Verb:
1903                 if (!IsQuadDegenerate(lastPt, fPts[0], fPts[1], exact)) {
1904                     if (lastMoveVerb) {
1905                         fVerbs = lastMoveVerb;
1906                         fPts = lastMovePt;
1907                         fConicWeights = lastMoveWeight;
1908                         return;
1909                     }
1910                     return;
1911                 }
1912                 // Ignore this line and continue
1913                 fVerbs--;
1914                 fPts += 2;
1915                 fConicWeights += (kConic_Verb == verb);
1916                 break;
1917
1918             case kCubic_Verb:
1919                 if (!IsCubicDegenerate(lastPt, fPts[0], fPts[1], fPts[2], exact)) {
1920                     if (lastMoveVerb) {
1921                         fVerbs = lastMoveVerb;
1922                         fPts = lastMovePt;
1923                         fConicWeights = lastMoveWeight;
1924                         return;
1925                     }
1926                     return;
1927                 }
1928                 // Ignore this line and continue
1929                 fVerbs--;
1930                 fPts += 3;
1931                 break;
1932
1933             default:
1934                 SkDEBUGFAIL("Should never see kDone_Verb");
1935         }
1936     }
1937 }
1938
1939 SkPath::Verb SkPath::Iter::doNext(SkPoint ptsParam[4]) {
1940     SkASSERT(ptsParam);
1941
1942     if (fVerbs == fVerbStop) {
1943         // Close the curve if requested and if there is some curve to close
1944         if (fNeedClose && fSegmentState == kAfterPrimitive_SegmentState) {
1945             if (kLine_Verb == this->autoClose(ptsParam)) {
1946                 return kLine_Verb;
1947             }
1948             fNeedClose = false;
1949             return kClose_Verb;
1950         }
1951         return kDone_Verb;
1952     }
1953
1954     // fVerbs is one beyond the current verb, decrement first
1955     unsigned verb = *(--fVerbs);
1956     const SkPoint* SK_RESTRICT srcPts = fPts;
1957     SkPoint* SK_RESTRICT       pts = ptsParam;
1958
1959     switch (verb) {
1960         case kMove_Verb:
1961             if (fNeedClose) {
1962                 fVerbs++; // move back one verb
1963                 verb = this->autoClose(pts);
1964                 if (verb == kClose_Verb) {
1965                     fNeedClose = false;
1966                 }
1967                 return (Verb)verb;
1968             }
1969             if (fVerbs == fVerbStop) {    // might be a trailing moveto
1970                 return kDone_Verb;
1971             }
1972             fMoveTo = *srcPts;
1973             pts[0] = *srcPts;
1974             srcPts += 1;
1975             fSegmentState = kAfterMove_SegmentState;
1976             fLastPt = fMoveTo;
1977             fNeedClose = fForceClose;
1978             break;
1979         case kLine_Verb:
1980             pts[0] = this->cons_moveTo();
1981             pts[1] = srcPts[0];
1982             fLastPt = srcPts[0];
1983             fCloseLine = false;
1984             srcPts += 1;
1985             break;
1986         case kConic_Verb:
1987             fConicWeights += 1;
1988             // fall-through
1989         case kQuad_Verb:
1990             pts[0] = this->cons_moveTo();
1991             memcpy(&pts[1], srcPts, 2 * sizeof(SkPoint));
1992             fLastPt = srcPts[1];
1993             srcPts += 2;
1994             break;
1995         case kCubic_Verb:
1996             pts[0] = this->cons_moveTo();
1997             memcpy(&pts[1], srcPts, 3 * sizeof(SkPoint));
1998             fLastPt = srcPts[2];
1999             srcPts += 3;
2000             break;
2001         case kClose_Verb:
2002             verb = this->autoClose(pts);
2003             if (verb == kLine_Verb) {
2004                 fVerbs++; // move back one verb
2005             } else {
2006                 fNeedClose = false;
2007                 fSegmentState = kEmptyContour_SegmentState;
2008             }
2009             fLastPt = fMoveTo;
2010             break;
2011     }
2012     fPts = srcPts;
2013     return (Verb)verb;
2014 }
2015
2016 ///////////////////////////////////////////////////////////////////////////////
2017
2018 /*
2019     Format in compressed buffer: [ptCount, verbCount, pts[], verbs[]]
2020 */
2021
2022 size_t SkPath::writeToMemory(void* storage) const {
2023     SkDEBUGCODE(this->validate();)
2024
2025     if (nullptr == storage) {
2026         const int byteCount = sizeof(int32_t) * 2 + fPathRef->writeSize();
2027         return SkAlign4(byteCount);
2028     }
2029
2030     SkWBuffer   buffer(storage);
2031
2032     int32_t packed = (fConvexity << kConvexity_SerializationShift) |
2033                      (fFillType << kFillType_SerializationShift) |
2034                      (fFirstDirection << kDirection_SerializationShift) |
2035                      (fIsVolatile << kIsVolatile_SerializationShift) |
2036                      kCurrent_Version;
2037
2038     buffer.write32(packed);
2039     buffer.write32(fLastMoveToIndex);
2040
2041     fPathRef->writeToBuffer(&buffer);
2042
2043     buffer.padToAlign4();
2044     return buffer.pos();
2045 }
2046
2047 size_t SkPath::readFromMemory(const void* storage, size_t length) {
2048     SkRBufferWithSizeCheck buffer(storage, length);
2049
2050     int32_t packed;
2051     if (!buffer.readS32(&packed)) {
2052         return 0;
2053     }
2054
2055     unsigned version = packed & 0xFF;
2056     if (version >= kPathPrivLastMoveToIndex_Version && !buffer.readS32(&fLastMoveToIndex)) {
2057         return 0;
2058     }
2059
2060     fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF;
2061     fFillType = (packed >> kFillType_SerializationShift) & 0x3;
2062     uint8_t dir = (packed >> kDirection_SerializationShift) & 0x3;
2063     fIsVolatile = (packed >> kIsVolatile_SerializationShift) & 0x1;
2064     SkPathRef* pathRef = SkPathRef::CreateFromBuffer(&buffer);
2065     if (!pathRef) {
2066         return 0;
2067     }
2068
2069     fPathRef.reset(pathRef);
2070     SkDEBUGCODE(this->validate();)
2071     buffer.skipToAlign4();
2072
2073     // compatibility check
2074     if (version < kPathPrivFirstDirection_Version) {
2075         switch (dir) {  // old values
2076             case 0:
2077                 fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
2078                 break;
2079             case 1:
2080                 fFirstDirection = SkPathPriv::kCW_FirstDirection;
2081                 break;
2082             case 2:
2083                 fFirstDirection = SkPathPriv::kCCW_FirstDirection;
2084                 break;
2085             default:
2086                 SkASSERT(false);
2087         }
2088     } else {
2089         fFirstDirection = dir;
2090     }
2091
2092     return buffer.pos();
2093 }
2094
2095 ///////////////////////////////////////////////////////////////////////////////
2096
2097 #include "SkStringUtils.h"
2098 #include "SkStream.h"
2099
2100 static void append_params(SkString* str, const char label[], const SkPoint pts[],
2101                           int count, SkScalarAsStringType strType, SkScalar conicWeight = -1) {
2102     str->append(label);
2103     str->append("(");
2104
2105     const SkScalar* values = &pts[0].fX;
2106     count *= 2;
2107
2108     for (int i = 0; i < count; ++i) {
2109         SkAppendScalar(str, values[i], strType);
2110         if (i < count - 1) {
2111             str->append(", ");
2112         }
2113     }
2114     if (conicWeight >= 0) {
2115         str->append(", ");
2116         SkAppendScalar(str, conicWeight, strType);
2117     }
2118     str->append(");");
2119     if (kHex_SkScalarAsStringType == strType) {
2120         str->append("  // ");
2121         for (int i = 0; i < count; ++i) {
2122             SkAppendScalarDec(str, values[i]);
2123             if (i < count - 1) {
2124                 str->append(", ");
2125             }
2126         }
2127         if (conicWeight >= 0) {
2128             str->append(", ");
2129             SkAppendScalarDec(str, conicWeight);
2130         }
2131     }
2132     str->append("\n");
2133 }
2134
2135 void SkPath::dump(SkWStream* wStream, bool forceClose, bool dumpAsHex) const {
2136     SkScalarAsStringType asType = dumpAsHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
2137     Iter    iter(*this, forceClose);
2138     SkPoint pts[4];
2139     Verb    verb;
2140
2141     if (!wStream) {
2142         SkDebugf("path: forceClose=%s\n", forceClose ? "true" : "false");
2143     }
2144     SkString builder;
2145
2146     while ((verb = iter.next(pts, false)) != kDone_Verb) {
2147         switch (verb) {
2148             case kMove_Verb:
2149                 append_params(&builder, "path.moveTo", &pts[0], 1, asType);
2150                 break;
2151             case kLine_Verb:
2152                 append_params(&builder, "path.lineTo", &pts[1], 1, asType);
2153                 break;
2154             case kQuad_Verb:
2155                 append_params(&builder, "path.quadTo", &pts[1], 2, asType);
2156                 break;
2157             case kConic_Verb:
2158                 append_params(&builder, "path.conicTo", &pts[1], 2, asType, iter.conicWeight());
2159                 break;
2160             case kCubic_Verb:
2161                 append_params(&builder, "path.cubicTo", &pts[1], 3, asType);
2162                 break;
2163             case kClose_Verb:
2164                 builder.append("path.close();\n");
2165                 break;
2166             default:
2167                 SkDebugf("  path: UNKNOWN VERB %d, aborting dump...\n", verb);
2168                 verb = kDone_Verb;  // stop the loop
2169                 break;
2170         }
2171         if (!wStream && builder.size()) {
2172             SkDebugf("%s", builder.c_str());
2173             builder.reset();
2174         }
2175     }
2176     if (wStream) {
2177         wStream->writeText(builder.c_str());
2178     }
2179 }
2180
2181 void SkPath::dump() const {
2182     this->dump(nullptr, false, false);
2183 }
2184
2185 void SkPath::dumpHex() const {
2186     this->dump(nullptr, false, true);
2187 }
2188
2189 #ifdef SK_DEBUG
2190 void SkPath::validate() const {
2191     SkASSERT((fFillType & ~3) == 0);
2192
2193 #ifdef SK_DEBUG_PATH
2194     if (!fBoundsIsDirty) {
2195         SkRect bounds;
2196
2197         bool isFinite = compute_pt_bounds(&bounds, *fPathRef.get());
2198         SkASSERT(SkToBool(fIsFinite) == isFinite);
2199
2200         if (fPathRef->countPoints() <= 1) {
2201             // if we're empty, fBounds may be empty but translated, so we can't
2202             // necessarily compare to bounds directly
2203             // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
2204             // be [2, 2, 2, 2]
2205             SkASSERT(bounds.isEmpty());
2206             SkASSERT(fBounds.isEmpty());
2207         } else {
2208             if (bounds.isEmpty()) {
2209                 SkASSERT(fBounds.isEmpty());
2210             } else {
2211                 if (!fBounds.isEmpty()) {
2212                     SkASSERT(fBounds.contains(bounds));
2213                 }
2214             }
2215         }
2216     }
2217 #endif // SK_DEBUG_PATH
2218 }
2219 #endif // SK_DEBUG
2220
2221 ///////////////////////////////////////////////////////////////////////////////
2222
2223 static int sign(SkScalar x) { return x < 0; }
2224 #define kValueNeverReturnedBySign   2
2225
2226 enum DirChange {
2227     kLeft_DirChange,
2228     kRight_DirChange,
2229     kStraight_DirChange,
2230     kBackwards_DirChange,
2231
2232     kInvalid_DirChange
2233 };
2234
2235
2236 static bool almost_equal(SkScalar compA, SkScalar compB) {
2237     // The error epsilon was empirically derived; worse case round rects
2238     // with a mid point outset by 2x float epsilon in tests had an error
2239     // of 12.
2240     const int epsilon = 16;
2241     if (!SkScalarIsFinite(compA) || !SkScalarIsFinite(compB)) {
2242         return false;
2243     }
2244     // no need to check for small numbers because SkPath::Iter has removed degenerate values
2245     int aBits = SkFloatAs2sCompliment(compA);
2246     int bBits = SkFloatAs2sCompliment(compB);
2247     return aBits < bBits + epsilon && bBits < aBits + epsilon;
2248 }
2249
2250 static bool approximately_zero_when_compared_to(double x, double y) {
2251     return x == 0 || fabs(x) < fabs(y * FLT_EPSILON);
2252 }
2253
2254
2255 // only valid for a single contour
2256 struct Convexicator {
2257     Convexicator()
2258     : fPtCount(0)
2259     , fConvexity(SkPath::kConvex_Convexity)
2260     , fFirstDirection(SkPathPriv::kUnknown_FirstDirection)
2261     , fIsFinite(true)
2262     , fIsCurve(false) {
2263         fExpectedDir = kInvalid_DirChange;
2264         // warnings
2265         fPriorPt.set(0,0);
2266         fLastPt.set(0, 0);
2267         fCurrPt.set(0, 0);
2268         fLastVec.set(0, 0);
2269         fFirstVec.set(0, 0);
2270
2271         fDx = fDy = 0;
2272         fSx = fSy = kValueNeverReturnedBySign;
2273     }
2274
2275     SkPath::Convexity getConvexity() const { return fConvexity; }
2276
2277     /** The direction returned is only valid if the path is determined convex */
2278     SkPathPriv::FirstDirection getFirstDirection() const { return fFirstDirection; }
2279
2280     void addPt(const SkPoint& pt) {
2281         if (SkPath::kConcave_Convexity == fConvexity || !fIsFinite) {
2282             return;
2283         }
2284
2285         if (0 == fPtCount) {
2286             fCurrPt = pt;
2287             ++fPtCount;
2288         } else {
2289             SkVector vec = pt - fCurrPt;
2290             SkScalar lengthSqd = vec.lengthSqd();
2291             if (!SkScalarIsFinite(lengthSqd)) {
2292                 fIsFinite = false;
2293             } else if (lengthSqd) {
2294                 fPriorPt = fLastPt;
2295                 fLastPt = fCurrPt;
2296                 fCurrPt = pt;
2297                 if (++fPtCount == 2) {
2298                     fFirstVec = fLastVec = vec;
2299                 } else {
2300                     SkASSERT(fPtCount > 2);
2301                     this->addVec(vec);
2302                 }
2303
2304                 int sx = sign(vec.fX);
2305                 int sy = sign(vec.fY);
2306                 fDx += (sx != fSx);
2307                 fDy += (sy != fSy);
2308                 fSx = sx;
2309                 fSy = sy;
2310
2311                 if (fDx > 3 || fDy > 3) {
2312                     fConvexity = SkPath::kConcave_Convexity;
2313                 }
2314             }
2315         }
2316     }
2317
2318     void close() {
2319         if (fPtCount > 2) {
2320             this->addVec(fFirstVec);
2321         }
2322     }
2323
2324     DirChange directionChange(const SkVector& curVec) {
2325         SkScalar cross = SkPoint::CrossProduct(fLastVec, curVec);
2326
2327         SkScalar smallest = SkTMin(fCurrPt.fX, SkTMin(fCurrPt.fY, SkTMin(fLastPt.fX, fLastPt.fY)));
2328         SkScalar largest = SkTMax(fCurrPt.fX, SkTMax(fCurrPt.fY, SkTMax(fLastPt.fX, fLastPt.fY)));
2329         largest = SkTMax(largest, -smallest);
2330
2331         if (!almost_equal(largest, largest + cross)) {
2332             int sign = SkScalarSignAsInt(cross);
2333             if (sign) {
2334                 return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
2335             }
2336         }
2337
2338         if (cross) {
2339             double dLastVecX = SkScalarToDouble(fLastPt.fX) - SkScalarToDouble(fPriorPt.fX);
2340             double dLastVecY = SkScalarToDouble(fLastPt.fY) - SkScalarToDouble(fPriorPt.fY);
2341             double dCurrVecX = SkScalarToDouble(fCurrPt.fX) - SkScalarToDouble(fLastPt.fX);
2342             double dCurrVecY = SkScalarToDouble(fCurrPt.fY) - SkScalarToDouble(fLastPt.fY);
2343             double dCross = dLastVecX * dCurrVecY - dLastVecY * dCurrVecX;
2344             if (!approximately_zero_when_compared_to(dCross, SkScalarToDouble(largest))) {
2345                 int sign = SkScalarSignAsInt(SkDoubleToScalar(dCross));
2346                 if (sign) {
2347                     return (1 == sign) ? kRight_DirChange : kLeft_DirChange;
2348                 }
2349             }
2350         }
2351
2352         if (!SkScalarNearlyZero(fLastVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2353             !SkScalarNearlyZero(curVec.lengthSqd(), SK_ScalarNearlyZero*SK_ScalarNearlyZero) &&
2354             fLastVec.dot(curVec) < 0.0f) {
2355             return kBackwards_DirChange;
2356         }
2357
2358         return kStraight_DirChange;
2359     }
2360
2361
2362     bool isFinite() const {
2363         return fIsFinite;
2364     }
2365
2366     void setCurve(bool isCurve) {
2367         fIsCurve = isCurve;
2368     }
2369
2370 private:
2371     void addVec(const SkVector& vec) {
2372         SkASSERT(vec.fX || vec.fY);
2373         DirChange dir = this->directionChange(vec);
2374         switch (dir) {
2375             case kLeft_DirChange:       // fall through
2376             case kRight_DirChange:
2377                 if (kInvalid_DirChange == fExpectedDir) {
2378                     fExpectedDir = dir;
2379                     fFirstDirection = (kRight_DirChange == dir) ? SkPathPriv::kCW_FirstDirection
2380                                                                 : SkPathPriv::kCCW_FirstDirection;
2381                 } else if (dir != fExpectedDir) {
2382                     fConvexity = SkPath::kConcave_Convexity;
2383                     fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
2384                 }
2385                 fLastVec = vec;
2386                 break;
2387             case kStraight_DirChange:
2388                 break;
2389             case kBackwards_DirChange:
2390                 if (fIsCurve) {
2391                     fConvexity = SkPath::kConcave_Convexity;
2392                     fFirstDirection = SkPathPriv::kUnknown_FirstDirection;
2393                 }
2394                 fLastVec = vec;
2395                 break;
2396             case kInvalid_DirChange:
2397                 SkFAIL("Use of invalid direction change flag");
2398                 break;
2399         }
2400     }
2401
2402     SkPoint             fPriorPt;
2403     SkPoint             fLastPt;
2404     SkPoint             fCurrPt;
2405     // fLastVec does not necessarily start at fLastPt. We only advance it when the cross product
2406     // value with the current vec is deemed to be of a significant value.
2407     SkVector            fLastVec, fFirstVec;
2408     int                 fPtCount;   // non-degenerate points
2409     DirChange           fExpectedDir;
2410     SkPath::Convexity   fConvexity;
2411     SkPathPriv::FirstDirection   fFirstDirection;
2412     int                 fDx, fDy, fSx, fSy;
2413     bool                fIsFinite;
2414     bool                fIsCurve;
2415 };
2416
2417 SkPath::Convexity SkPath::internalGetConvexity() const {
2418     SkASSERT(kUnknown_Convexity == fConvexity);
2419     SkPoint         pts[4];
2420     SkPath::Verb    verb;
2421     SkPath::Iter    iter(*this, true);
2422
2423     int             contourCount = 0;
2424     int             count;
2425     Convexicator    state;
2426
2427     if (!isFinite()) {
2428         return kUnknown_Convexity;
2429     }
2430     while ((verb = iter.next(pts, true, true)) != SkPath::kDone_Verb) {
2431         switch (verb) {
2432             case kMove_Verb:
2433                 if (++contourCount > 1) {
2434                     fConvexity = kConcave_Convexity;
2435                     return kConcave_Convexity;
2436                 }
2437                 pts[1] = pts[0];
2438                 // fall through
2439             case kLine_Verb:
2440                 count = 1;
2441                 state.setCurve(false);
2442                 break;
2443             case kQuad_Verb:
2444                 // fall through
2445             case kConic_Verb:
2446                 // fall through
2447             case kCubic_Verb:
2448                 count = 2 + (kCubic_Verb == verb);
2449                 // As an additional enhancement, this could set curve true only
2450                 // if the curve is nonlinear
2451                 state.setCurve(true);
2452                 break;
2453             case kClose_Verb:
2454                 state.setCurve(false);
2455                 state.close();
2456                 count = 0;
2457                 break;
2458             default:
2459                 SkDEBUGFAIL("bad verb");
2460                 fConvexity = kConcave_Convexity;
2461                 return kConcave_Convexity;
2462         }
2463
2464         for (int i = 1; i <= count; i++) {
2465             state.addPt(pts[i]);
2466         }
2467         // early exit
2468         if (!state.isFinite()) {
2469             return kUnknown_Convexity;
2470         }
2471         if (kConcave_Convexity == state.getConvexity()) {
2472             fConvexity = kConcave_Convexity;
2473             return kConcave_Convexity;
2474         }
2475     }
2476     fConvexity = state.getConvexity();
2477     if (kConvex_Convexity == fConvexity && SkPathPriv::kUnknown_FirstDirection == fFirstDirection) {
2478         fFirstDirection = state.getFirstDirection();
2479     }
2480     return static_cast<Convexity>(fConvexity);
2481 }
2482
2483 ///////////////////////////////////////////////////////////////////////////////
2484
2485 class ContourIter {
2486 public:
2487     ContourIter(const SkPathRef& pathRef);
2488
2489     bool done() const { return fDone; }
2490     // if !done() then these may be called
2491     int count() const { return fCurrPtCount; }
2492     const SkPoint* pts() const { return fCurrPt; }
2493     void next();
2494
2495 private:
2496     int fCurrPtCount;
2497     const SkPoint* fCurrPt;
2498     const uint8_t* fCurrVerb;
2499     const uint8_t* fStopVerbs;
2500     const SkScalar* fCurrConicWeight;
2501     bool fDone;
2502     SkDEBUGCODE(int fContourCounter;)
2503 };
2504
2505 ContourIter::ContourIter(const SkPathRef& pathRef) {
2506     fStopVerbs = pathRef.verbsMemBegin();
2507     fDone = false;
2508     fCurrPt = pathRef.points();
2509     fCurrVerb = pathRef.verbs();
2510     fCurrConicWeight = pathRef.conicWeights();
2511     fCurrPtCount = 0;
2512     SkDEBUGCODE(fContourCounter = 0;)
2513     this->next();
2514 }
2515
2516 void ContourIter::next() {
2517     if (fCurrVerb <= fStopVerbs) {
2518         fDone = true;
2519     }
2520     if (fDone) {
2521         return;
2522     }
2523
2524     // skip pts of prev contour
2525     fCurrPt += fCurrPtCount;
2526
2527     SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
2528     int ptCount = 1;    // moveTo
2529     const uint8_t* verbs = fCurrVerb;
2530
2531     for (--verbs; verbs > fStopVerbs; --verbs) {
2532         switch (verbs[~0]) {
2533             case SkPath::kMove_Verb:
2534                 goto CONTOUR_END;
2535             case SkPath::kLine_Verb:
2536                 ptCount += 1;
2537                 break;
2538             case SkPath::kConic_Verb:
2539                 fCurrConicWeight += 1;
2540                 // fall-through
2541             case SkPath::kQuad_Verb:
2542                 ptCount += 2;
2543                 break;
2544             case SkPath::kCubic_Verb:
2545                 ptCount += 3;
2546                 break;
2547             case SkPath::kClose_Verb:
2548                 break;
2549             default:
2550                 SkDEBUGFAIL("unexpected verb");
2551                 break;
2552         }
2553     }
2554 CONTOUR_END:
2555     fCurrPtCount = ptCount;
2556     fCurrVerb = verbs;
2557     SkDEBUGCODE(++fContourCounter;)
2558 }
2559
2560 // returns cross product of (p1 - p0) and (p2 - p0)
2561 static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
2562     SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
2563     // We may get 0 when the above subtracts underflow. We expect this to be
2564     // very rare and lazily promote to double.
2565     if (0 == cross) {
2566         double p0x = SkScalarToDouble(p0.fX);
2567         double p0y = SkScalarToDouble(p0.fY);
2568
2569         double p1x = SkScalarToDouble(p1.fX);
2570         double p1y = SkScalarToDouble(p1.fY);
2571
2572         double p2x = SkScalarToDouble(p2.fX);
2573         double p2y = SkScalarToDouble(p2.fY);
2574
2575         cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
2576                                  (p1y - p0y) * (p2x - p0x));
2577
2578     }
2579     return cross;
2580 }
2581
2582 // Returns the first pt with the maximum Y coordinate
2583 static int find_max_y(const SkPoint pts[], int count) {
2584     SkASSERT(count > 0);
2585     SkScalar max = pts[0].fY;
2586     int firstIndex = 0;
2587     for (int i = 1; i < count; ++i) {
2588         SkScalar y = pts[i].fY;
2589         if (y > max) {
2590             max = y;
2591             firstIndex = i;
2592         }
2593     }
2594     return firstIndex;
2595 }
2596
2597 static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
2598     int i = index;
2599     for (;;) {
2600         i = (i + inc) % n;
2601         if (i == index) {   // we wrapped around, so abort
2602             break;
2603         }
2604         if (pts[index] != pts[i]) { // found a different point, success!
2605             break;
2606         }
2607     }
2608     return i;
2609 }
2610
2611 /**
2612  *  Starting at index, and moving forward (incrementing), find the xmin and
2613  *  xmax of the contiguous points that have the same Y.
2614  */
2615 static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
2616                                int* maxIndexPtr) {
2617     const SkScalar y = pts[index].fY;
2618     SkScalar min = pts[index].fX;
2619     SkScalar max = min;
2620     int minIndex = index;
2621     int maxIndex = index;
2622     for (int i = index + 1; i < n; ++i) {
2623         if (pts[i].fY != y) {
2624             break;
2625         }
2626         SkScalar x = pts[i].fX;
2627         if (x < min) {
2628             min = x;
2629             minIndex = i;
2630         } else if (x > max) {
2631             max = x;
2632             maxIndex = i;
2633         }
2634     }
2635     *maxIndexPtr = maxIndex;
2636     return minIndex;
2637 }
2638
2639 static void crossToDir(SkScalar cross, SkPathPriv::FirstDirection* dir) {
2640     *dir = cross > 0 ? SkPathPriv::kCW_FirstDirection : SkPathPriv::kCCW_FirstDirection;
2641 }
2642
2643 /*
2644  *  We loop through all contours, and keep the computed cross-product of the
2645  *  contour that contained the global y-max. If we just look at the first
2646  *  contour, we may find one that is wound the opposite way (correctly) since
2647  *  it is the interior of a hole (e.g. 'o'). Thus we must find the contour
2648  *  that is outer most (or at least has the global y-max) before we can consider
2649  *  its cross product.
2650  */
2651 bool SkPathPriv::CheapComputeFirstDirection(const SkPath& path, FirstDirection* dir) {
2652     if (kUnknown_FirstDirection != path.fFirstDirection.load()) {
2653         *dir = static_cast<FirstDirection>(path.fFirstDirection.load());
2654         return true;
2655     }
2656
2657     // don't want to pay the cost for computing this if it
2658     // is unknown, so we don't call isConvex()
2659     if (SkPath::kConvex_Convexity == path.getConvexityOrUnknown()) {
2660         SkASSERT(kUnknown_FirstDirection == path.fFirstDirection);
2661         *dir = static_cast<FirstDirection>(path.fFirstDirection.load());
2662         return false;
2663     }
2664
2665     ContourIter iter(*path.fPathRef.get());
2666
2667     // initialize with our logical y-min
2668     SkScalar ymax = path.getBounds().fTop;
2669     SkScalar ymaxCross = 0;
2670
2671     for (; !iter.done(); iter.next()) {
2672         int n = iter.count();
2673         if (n < 3) {
2674             continue;
2675         }
2676
2677         const SkPoint* pts = iter.pts();
2678         SkScalar cross = 0;
2679         int index = find_max_y(pts, n);
2680         if (pts[index].fY < ymax) {
2681             continue;
2682         }
2683
2684         // If there is more than 1 distinct point at the y-max, we take the
2685         // x-min and x-max of them and just subtract to compute the dir.
2686         if (pts[(index + 1) % n].fY == pts[index].fY) {
2687             int maxIndex;
2688             int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
2689             if (minIndex == maxIndex) {
2690                 goto TRY_CROSSPROD;
2691             }
2692             SkASSERT(pts[minIndex].fY == pts[index].fY);
2693             SkASSERT(pts[maxIndex].fY == pts[index].fY);
2694             SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
2695             // we just subtract the indices, and let that auto-convert to
2696             // SkScalar, since we just want - or + to signal the direction.
2697             cross = minIndex - maxIndex;
2698         } else {
2699             TRY_CROSSPROD:
2700             // Find a next and prev index to use for the cross-product test,
2701             // but we try to find pts that form non-zero vectors from pts[index]
2702             //
2703             // Its possible that we can't find two non-degenerate vectors, so
2704             // we have to guard our search (e.g. all the pts could be in the
2705             // same place).
2706
2707             // we pass n - 1 instead of -1 so we don't foul up % operator by
2708             // passing it a negative LH argument.
2709             int prev = find_diff_pt(pts, index, n, n - 1);
2710             if (prev == index) {
2711                 // completely degenerate, skip to next contour
2712                 continue;
2713             }
2714             int next = find_diff_pt(pts, index, n, 1);
2715             SkASSERT(next != index);
2716             cross = cross_prod(pts[prev], pts[index], pts[next]);
2717             // if we get a zero and the points are horizontal, then we look at the spread in
2718             // x-direction. We really should continue to walk away from the degeneracy until
2719             // there is a divergence.
2720             if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
2721                 // construct the subtract so we get the correct Direction below
2722                 cross = pts[index].fX - pts[next].fX;
2723             }
2724         }
2725
2726         if (cross) {
2727             // record our best guess so far
2728             ymax = pts[index].fY;
2729             ymaxCross = cross;
2730         }
2731     }
2732     if (ymaxCross) {
2733         crossToDir(ymaxCross, dir);
2734         path.fFirstDirection = *dir;
2735         return true;
2736     } else {
2737         return false;
2738     }
2739 }
2740
2741 ///////////////////////////////////////////////////////////////////////////////
2742
2743 static bool between(SkScalar a, SkScalar b, SkScalar c) {
2744     SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
2745             || (SkScalarNearlyZero(a) && SkScalarNearlyZero(b) && SkScalarNearlyZero(c)));
2746     return (a - b) * (c - b) <= 0;
2747 }
2748
2749 static SkScalar eval_cubic_coeff(SkScalar A, SkScalar B, SkScalar C,
2750                                  SkScalar D, SkScalar t) {
2751     return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D);
2752 }
2753
2754 static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3,
2755                                SkScalar t) {
2756     SkScalar A = c3 + 3*(c1 - c2) - c0;
2757     SkScalar B = 3*(c2 - c1 - c1 + c0);
2758     SkScalar C = 3*(c1 - c0);
2759     SkScalar D = c0;
2760     return eval_cubic_coeff(A, B, C, D, t);
2761 }
2762
2763 template <size_t N> static void find_minmax(const SkPoint pts[],
2764                                             SkScalar* minPtr, SkScalar* maxPtr) {
2765     SkScalar min, max;
2766     min = max = pts[0].fX;
2767     for (size_t i = 1; i < N; ++i) {
2768         min = SkMinScalar(min, pts[i].fX);
2769         max = SkMaxScalar(max, pts[i].fX);
2770     }
2771     *minPtr = min;
2772     *maxPtr = max;
2773 }
2774
2775 static bool checkOnCurve(SkScalar x, SkScalar y, const SkPoint& start, const SkPoint& end) {
2776     if (start.fY == end.fY) {
2777         return between(start.fX, x, end.fX) && x != end.fX;
2778     } else {
2779         return x == start.fX && y == start.fY;
2780     }
2781 }
2782
2783 static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2784     SkScalar y0 = pts[0].fY;
2785     SkScalar y3 = pts[3].fY;
2786
2787     int dir = 1;
2788     if (y0 > y3) {
2789         SkTSwap(y0, y3);
2790         dir = -1;
2791     }
2792     if (y < y0 || y > y3) {
2793         return 0;
2794     }
2795     if (checkOnCurve(x, y, pts[0], pts[3])) {
2796         *onCurveCount += 1;
2797         return 0;
2798     }
2799     if (y == y3) {
2800         return 0;
2801     }
2802
2803     // quickreject or quickaccept
2804     SkScalar min, max;
2805     find_minmax<4>(pts, &min, &max);
2806     if (x < min) {
2807         return 0;
2808     }
2809     if (x > max) {
2810         return dir;
2811     }
2812
2813     // compute the actual x(t) value
2814     SkScalar t;
2815     if (!SkCubicClipper::ChopMonoAtY(pts, y, &t)) {
2816         return 0;
2817     }
2818     SkScalar xt = eval_cubic_pts(pts[0].fX, pts[1].fX, pts[2].fX, pts[3].fX, t);
2819     if (SkScalarNearlyEqual(xt, x)) {
2820         if (x != pts[3].fX || y != pts[3].fY) {  // don't test end points; they're start points
2821             *onCurveCount += 1;
2822             return 0;
2823         }
2824     }
2825     return xt < x ? dir : 0;
2826 }
2827
2828 static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2829     SkPoint dst[10];
2830     int n = SkChopCubicAtYExtrema(pts, dst);
2831     int w = 0;
2832     for (int i = 0; i <= n; ++i) {
2833         w += winding_mono_cubic(&dst[i * 3], x, y, onCurveCount);
2834     }
2835     return w;
2836 }
2837
2838 static double conic_eval_numerator(const SkScalar src[], SkScalar w, SkScalar t) {
2839     SkASSERT(src);
2840     SkASSERT(t >= 0 && t <= 1);
2841     SkScalar src2w = src[2] * w;
2842     SkScalar C = src[0];
2843     SkScalar A = src[4] - 2 * src2w + C;
2844     SkScalar B = 2 * (src2w - C);
2845     return (A * t + B) * t + C;
2846 }
2847
2848
2849 static double conic_eval_denominator(SkScalar w, SkScalar t) {
2850     SkScalar B = 2 * (w - 1);
2851     SkScalar C = 1;
2852     SkScalar A = -B;
2853     return (A * t + B) * t + C;
2854 }
2855
2856 static int winding_mono_conic(const SkConic& conic, SkScalar x, SkScalar y, int* onCurveCount) {
2857     const SkPoint* pts = conic.fPts;
2858     SkScalar y0 = pts[0].fY;
2859     SkScalar y2 = pts[2].fY;
2860
2861     int dir = 1;
2862     if (y0 > y2) {
2863         SkTSwap(y0, y2);
2864         dir = -1;
2865     }
2866     if (y < y0 || y > y2) {
2867         return 0;
2868     }
2869     if (checkOnCurve(x, y, pts[0], pts[2])) {
2870         *onCurveCount += 1;
2871         return 0;
2872     }
2873     if (y == y2) {
2874         return 0;
2875     }
2876
2877     SkScalar roots[2];
2878     SkScalar A = pts[2].fY;
2879     SkScalar B = pts[1].fY * conic.fW - y * conic.fW + y;
2880     SkScalar C = pts[0].fY;
2881     A += C - 2 * B;  // A = a + c - 2*(b*w - yCept*w + yCept)
2882     B -= C;  // B = b*w - w * yCept + yCept - a
2883     C -= y;
2884     int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
2885     SkASSERT(n <= 1);
2886     SkScalar xt;
2887     if (0 == n) {
2888         // zero roots are returned only when y0 == y
2889         // Need [0] if dir == 1
2890         // and  [2] if dir == -1
2891         xt = pts[1 - dir].fX;
2892     } else {
2893         SkScalar t = roots[0];
2894         xt = conic_eval_numerator(&pts[0].fX, conic.fW, t) / conic_eval_denominator(conic.fW, t);
2895     }
2896     if (SkScalarNearlyEqual(xt, x)) {
2897         if (x != pts[2].fX || y != pts[2].fY) {  // don't test end points; they're start points
2898             *onCurveCount += 1;
2899             return 0;
2900         }
2901     }
2902     return xt < x ? dir : 0;
2903 }
2904
2905 static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) {
2906     //    return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
2907     if (y0 == y1) {
2908         return true;
2909     }
2910     if (y0 < y1) {
2911         return y1 <= y2;
2912     } else {
2913         return y1 >= y2;
2914     }
2915 }
2916
2917 static int winding_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar weight,
2918                          int* onCurveCount) {
2919     SkConic conic(pts, weight);
2920     SkConic chopped[2];
2921     // If the data points are very large, the conic may not be monotonic but may also
2922     // fail to chop. Then, the chopper does not split the original conic in two.
2923     bool isMono = is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY) || !conic.chopAtYExtrema(chopped);
2924     int w = winding_mono_conic(isMono ? conic : chopped[0], x, y, onCurveCount);
2925     if (!isMono) {
2926         w += winding_mono_conic(chopped[1], x, y, onCurveCount);
2927     }
2928     return w;
2929 }
2930
2931 static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2932     SkScalar y0 = pts[0].fY;
2933     SkScalar y2 = pts[2].fY;
2934
2935     int dir = 1;
2936     if (y0 > y2) {
2937         SkTSwap(y0, y2);
2938         dir = -1;
2939     }
2940     if (y < y0 || y > y2) {
2941         return 0;
2942     }
2943     if (checkOnCurve(x, y, pts[0], pts[2])) {
2944         *onCurveCount += 1;
2945         return 0;
2946     }
2947     if (y == y2) {
2948         return 0;
2949     }
2950     // bounds check on X (not required. is it faster?)
2951 #if 0
2952     if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
2953         return 0;
2954     }
2955 #endif
2956
2957     SkScalar roots[2];
2958     int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
2959                                 2 * (pts[1].fY - pts[0].fY),
2960                                 pts[0].fY - y,
2961                                 roots);
2962     SkASSERT(n <= 1);
2963     SkScalar xt;
2964     if (0 == n) {
2965         // zero roots are returned only when y0 == y
2966         // Need [0] if dir == 1
2967         // and  [2] if dir == -1
2968         xt = pts[1 - dir].fX;
2969     } else {
2970         SkScalar t = roots[0];
2971         SkScalar C = pts[0].fX;
2972         SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
2973         SkScalar B = 2 * (pts[1].fX - C);
2974         xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
2975     }
2976     if (SkScalarNearlyEqual(xt, x)) {
2977         if (x != pts[2].fX || y != pts[2].fY) {  // don't test end points; they're start points
2978             *onCurveCount += 1;
2979             return 0;
2980         }
2981     }
2982     return xt < x ? dir : 0;
2983 }
2984
2985 static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
2986     SkPoint dst[5];
2987     int     n = 0;
2988
2989     if (!is_mono_quad(pts[0].fY, pts[1].fY, pts[2].fY)) {
2990         n = SkChopQuadAtYExtrema(pts, dst);
2991         pts = dst;
2992     }
2993     int w = winding_mono_quad(pts, x, y, onCurveCount);
2994     if (n > 0) {
2995         w += winding_mono_quad(&pts[2], x, y, onCurveCount);
2996     }
2997     return w;
2998 }
2999
3000 static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) {
3001     SkScalar x0 = pts[0].fX;
3002     SkScalar y0 = pts[0].fY;
3003     SkScalar x1 = pts[1].fX;
3004     SkScalar y1 = pts[1].fY;
3005
3006     SkScalar dy = y1 - y0;
3007
3008     int dir = 1;
3009     if (y0 > y1) {
3010         SkTSwap(y0, y1);
3011         dir = -1;
3012     }
3013     if (y < y0 || y > y1) {
3014         return 0;
3015     }
3016     if (checkOnCurve(x, y, pts[0], pts[1])) {
3017         *onCurveCount += 1;
3018         return 0;
3019     }
3020     if (y == y1) {
3021         return 0;
3022     }
3023     SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) - SkScalarMul(dy, x - x0);
3024
3025     if (!cross) {
3026         // zero cross means the point is on the line, and since the case where
3027         // y of the query point is at the end point is handled above, we can be
3028         // sure that we're on the line (excluding the end point) here
3029         if (x != x1 || y != pts[1].fY) {
3030             *onCurveCount += 1;
3031         }
3032         dir = 0;
3033     } else if (SkScalarSignAsInt(cross) == dir) {
3034         dir = 0;
3035     }
3036     return dir;
3037 }
3038
3039 static void tangent_cubic(const SkPoint pts[], SkScalar x, SkScalar y,
3040         SkTDArray<SkVector>* tangents) {
3041     if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)
3042              && !between(pts[2].fY, y, pts[3].fY)) {
3043         return;
3044     }
3045     if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)
3046              && !between(pts[2].fX, x, pts[3].fX)) {
3047         return;
3048     }
3049     SkPoint dst[10];
3050     int n = SkChopCubicAtYExtrema(pts, dst);
3051     for (int i = 0; i <= n; ++i) {
3052         SkPoint* c = &dst[i * 3];
3053         SkScalar t;
3054         if (!SkCubicClipper::ChopMonoAtY(c, y, &t)) {
3055             continue;
3056         }
3057         SkScalar xt = eval_cubic_pts(c[0].fX, c[1].fX, c[2].fX, c[3].fX, t);
3058         if (!SkScalarNearlyEqual(x, xt)) {
3059             continue;
3060         }
3061         SkVector tangent;
3062         SkEvalCubicAt(c, t, nullptr, &tangent, nullptr);
3063         tangents->push(tangent);
3064     }
3065 }
3066
3067 static void tangent_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar w,
3068             SkTDArray<SkVector>* tangents) {
3069     if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
3070         return;
3071     }
3072     if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
3073         return;
3074     }
3075     SkScalar roots[2];
3076     SkScalar A = pts[2].fY;
3077     SkScalar B = pts[1].fY * w - y * w + y;
3078     SkScalar C = pts[0].fY;
3079     A += C - 2 * B;  // A = a + c - 2*(b*w - yCept*w + yCept)
3080     B -= C;  // B = b*w - w * yCept + yCept - a
3081     C -= y;
3082     int n = SkFindUnitQuadRoots(A, 2 * B, C, roots);
3083     for (int index = 0; index < n; ++index) {
3084         SkScalar t = roots[index];
3085         SkScalar xt = conic_eval_numerator(&pts[0].fX, w, t) / conic_eval_denominator(w, t);
3086         if (!SkScalarNearlyEqual(x, xt)) {
3087             continue;
3088         }
3089         SkConic conic(pts, w);
3090         tangents->push(conic.evalTangentAt(t));
3091     }
3092 }
3093
3094 static void tangent_quad(const SkPoint pts[], SkScalar x, SkScalar y,
3095         SkTDArray<SkVector>* tangents) {
3096     if (!between(pts[0].fY, y, pts[1].fY) && !between(pts[1].fY, y, pts[2].fY)) {
3097         return;
3098     }
3099     if (!between(pts[0].fX, x, pts[1].fX) && !between(pts[1].fX, x, pts[2].fX)) {
3100         return;
3101     }
3102     SkScalar roots[2];
3103     int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
3104                                 2 * (pts[1].fY - pts[0].fY),
3105                                 pts[0].fY - y,
3106                                 roots);
3107     for (int index = 0; index < n; ++index) {
3108         SkScalar t = roots[index];
3109         SkScalar C = pts[0].fX;
3110         SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
3111         SkScalar B = 2 * (pts[1].fX - C);
3112         SkScalar xt = (A * t + B) * t + C;
3113         if (!SkScalarNearlyEqual(x, xt)) {
3114             continue;
3115         }
3116         tangents->push(SkEvalQuadTangentAt(pts, t));
3117     }
3118 }
3119
3120 static void tangent_line(const SkPoint pts[], SkScalar x, SkScalar y,
3121         SkTDArray<SkVector>* tangents) {
3122     SkScalar y0 = pts[0].fY;
3123     SkScalar y1 = pts[1].fY;
3124     if (!between(y0, y, y1)) {
3125         return;
3126     }
3127     SkScalar x0 = pts[0].fX;
3128     SkScalar x1 = pts[1].fX;
3129     if (!between(x0, x, x1)) {
3130         return;
3131     }
3132     SkScalar dx = x1 - x0;
3133     SkScalar dy = y1 - y0;
3134     if (!SkScalarNearlyEqual((x - x0) * dy, dx * (y - y0))) {
3135         return;
3136     }
3137     SkVector v;
3138     v.set(dx, dy);
3139     tangents->push(v);
3140 }
3141
3142 static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) {
3143     return r.fLeft <= x && x <= r.fRight && r.fTop <= y && y <= r.fBottom;
3144 }
3145
3146 bool SkPath::contains(SkScalar x, SkScalar y) const {
3147     bool isInverse = this->isInverseFillType();
3148     if (this->isEmpty()) {
3149         return isInverse;
3150     }
3151
3152     if (!contains_inclusive(this->getBounds(), x, y)) {
3153         return isInverse;
3154     }
3155
3156     SkPath::Iter iter(*this, true);
3157     bool done = false;
3158     int w = 0;
3159     int onCurveCount = 0;
3160     do {
3161         SkPoint pts[4];
3162         switch (iter.next(pts, false)) {
3163             case SkPath::kMove_Verb:
3164             case SkPath::kClose_Verb:
3165                 break;
3166             case SkPath::kLine_Verb:
3167                 w += winding_line(pts, x, y, &onCurveCount);
3168                 break;
3169             case SkPath::kQuad_Verb:
3170                 w += winding_quad(pts, x, y, &onCurveCount);
3171                 break;
3172             case SkPath::kConic_Verb:
3173                 w += winding_conic(pts, x, y, iter.conicWeight(), &onCurveCount);
3174                 break;
3175             case SkPath::kCubic_Verb:
3176                 w += winding_cubic(pts, x, y, &onCurveCount);
3177                 break;
3178             case SkPath::kDone_Verb:
3179                 done = true;
3180                 break;
3181        }
3182     } while (!done);
3183     bool evenOddFill = SkPath::kEvenOdd_FillType == this->getFillType()
3184             || SkPath::kInverseEvenOdd_FillType == this->getFillType();
3185     if (evenOddFill) {
3186         w &= 1;
3187     }
3188     if (w) {
3189         return !isInverse;
3190     }
3191     if (onCurveCount <= 1) {
3192         return SkToBool(onCurveCount) ^ isInverse;
3193     }
3194     if ((onCurveCount & 1) || evenOddFill) {
3195         return SkToBool(onCurveCount & 1) ^ isInverse;
3196     }
3197     // If the point touches an even number of curves, and the fill is winding, check for
3198     // coincidence. Count coincidence as places where the on curve points have identical tangents.
3199     iter.setPath(*this, true);
3200     done = false;
3201     SkTDArray<SkVector> tangents;
3202     do {
3203         SkPoint pts[4];
3204         int oldCount = tangents.count();
3205         switch (iter.next(pts, false)) {
3206             case SkPath::kMove_Verb:
3207             case SkPath::kClose_Verb:
3208                 break;
3209             case SkPath::kLine_Verb:
3210                 tangent_line(pts, x, y, &tangents);
3211                 break;
3212             case SkPath::kQuad_Verb:
3213                 tangent_quad(pts, x, y, &tangents);
3214                 break;
3215             case SkPath::kConic_Verb:
3216                 tangent_conic(pts, x, y, iter.conicWeight(), &tangents);
3217                 break;
3218             case SkPath::kCubic_Verb:
3219                 tangent_cubic(pts, x, y, &tangents);
3220                 break;
3221             case SkPath::kDone_Verb:
3222                 done = true;
3223                 break;
3224        }
3225        if (tangents.count() > oldCount) {
3226             int last = tangents.count() - 1;
3227             const SkVector& tangent = tangents[last];
3228             if (SkScalarNearlyZero(tangent.lengthSqd())) {
3229                 tangents.remove(last);
3230             } else {
3231                 for (int index = 0; index < last; ++index) {
3232                     const SkVector& test = tangents[index];
3233                     if (SkScalarNearlyZero(test.cross(tangent))
3234                             && SkScalarSignAsInt(tangent.fX * test.fX) <= 0
3235                             && SkScalarSignAsInt(tangent.fY * test.fY) <= 0) {
3236                         tangents.remove(last);
3237                         tangents.removeShuffle(index);
3238                         break;
3239                     }
3240                 }
3241             }
3242         }
3243     } while (!done);
3244     return SkToBool(tangents.count()) ^ isInverse;
3245 }
3246
3247 int SkPath::ConvertConicToQuads(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
3248                                 SkScalar w, SkPoint pts[], int pow2) {
3249     const SkConic conic(p0, p1, p2, w);
3250     return conic.chopIntoQuadsPOW2(pts, pow2);
3251 }
3252
3253 bool SkPathPriv::IsSimpleClosedRect(const SkPath& path, SkRect* rect, SkPath::Direction* direction,
3254                                     unsigned* start) {
3255     if (path.getSegmentMasks() != SkPath::kLine_SegmentMask) {
3256         return false;
3257     }
3258     SkPath::RawIter iter(path);
3259     SkPoint verbPts[4];
3260     SkPath::Verb v;
3261     SkPoint rectPts[5];
3262     int rectPtCnt = 0;
3263     while ((v = iter.next(verbPts)) != SkPath::kDone_Verb) {
3264         switch (v) {
3265             case SkPath::kMove_Verb:
3266                 if (0 != rectPtCnt) {
3267                     return false;
3268                 }
3269                 rectPts[0] = verbPts[0];
3270                 ++rectPtCnt;
3271                 break;
3272             case SkPath::kLine_Verb:
3273                 if (5 == rectPtCnt) {
3274                     return false;
3275                 }
3276                 rectPts[rectPtCnt] = verbPts[1];
3277                 ++rectPtCnt;
3278                 break;
3279             case SkPath::kClose_Verb:
3280                 if (4 == rectPtCnt) {
3281                     rectPts[4] = rectPts[0];
3282                     rectPtCnt = 5;
3283                 }
3284                 break;
3285             default:
3286                 return false;
3287         }
3288     }
3289     if (rectPtCnt < 5) {
3290         return false;
3291     }
3292     if (rectPts[0] != rectPts[4]) {
3293         return false;
3294     }
3295     int verticalCnt = 0;
3296     int horizontalCnt = 0;
3297     // dirs are 0 - right, 1 - down, 2 - left, 3 - up.
3298     int firstDir = 0;
3299     int secondDir = 0;
3300     SkRect tempRect;
3301     for (int i = 0; i < 4; ++i) {
3302         int sameCnt = 0;
3303         if (rectPts[i].fX == rectPts[i + 1].fX) {
3304             verticalCnt += 1;
3305             sameCnt = 1;
3306             if (0 == i) {
3307                 if (rectPts[1].fY > rectPts[0].fY) {
3308                     firstDir = 1;
3309                     tempRect.fTop = rectPts[0].fY;
3310                     tempRect.fBottom = rectPts[1].fY;
3311                 } else {
3312                     firstDir = 3;
3313                     tempRect.fTop = rectPts[1].fY;
3314                     tempRect.fBottom = rectPts[0].fY;
3315                 }
3316             } else if (1 == i) {
3317                 if (rectPts[2].fY > rectPts[1].fY) {
3318                     secondDir = 1;
3319                     tempRect.fTop = rectPts[1].fY;
3320                     tempRect.fBottom = rectPts[2].fY;
3321                 } else {
3322                     secondDir = 3;
3323                     tempRect.fTop = rectPts[2].fY;
3324                     tempRect.fBottom = rectPts[1].fY;
3325                 }
3326             }
3327         }
3328         if (rectPts[i].fY == rectPts[i + 1].fY) {
3329             horizontalCnt += 1;
3330             sameCnt += 1;
3331             if (0 == i) {
3332                 if (rectPts[1].fX > rectPts[0].fX) {
3333                     firstDir = 0;
3334                     tempRect.fLeft = rectPts[0].fX;
3335                     tempRect.fRight = rectPts[1].fX;
3336                 } else {
3337                     firstDir = 2;
3338                     tempRect.fLeft = rectPts[1].fX;
3339                     tempRect.fRight = rectPts[0].fX;
3340                 }
3341             } else if (1 == i) {
3342                 if (rectPts[2].fX > rectPts[1].fX) {
3343                     secondDir = 0;
3344                     tempRect.fLeft = rectPts[1].fX;
3345                     tempRect.fRight = rectPts[2].fX;
3346                 } else {
3347                     secondDir = 2;
3348                     tempRect.fLeft = rectPts[2].fX;
3349                     tempRect.fRight = rectPts[1].fX;
3350                 }
3351             }
3352         }
3353         if (sameCnt != 1) {
3354             return false;
3355         }
3356     }
3357     if (2 != horizontalCnt || 2 != verticalCnt) {
3358         return false;
3359     }
3360     // low bit indicates a vertical dir
3361     SkASSERT((firstDir ^ secondDir) & 0b1);
3362     if (((firstDir + 1) & 0b11) == secondDir) {
3363         *direction = SkPath::kCW_Direction;
3364         *start = firstDir;
3365     } else {
3366         SkASSERT(((secondDir + 1) & 0b11) == firstDir);
3367         *direction = SkPath::kCCW_Direction;
3368         *start = secondDir;
3369     }
3370     *rect = tempRect;
3371     return true;
3372 }