submodule/skia/src/utils/SkPolyUtils.cpp

   1 /*
   2  * Copyright 2017 Google Inc.
   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 "src/utils/SkPolyUtils.h"
   9
  10 #include "include/core/SkRect.h"
  11 #include "include/core/SkTypes.h"
  12 #include "include/private/SkFloatingPoint.h"
  13 #include "include/private/SkMalloc.h"
  14 #include "include/private/SkTArray.h"
  15 #include "include/private/SkTDArray.h"
  16 #include "include/private/SkTemplates.h"
  17 #include "include/private/SkVx.h"
  18 #include "src/core/SkPointPriv.h"
  19 #include "src/core/SkRectPriv.h"
  20 #include "src/core/SkTDPQueue.h"
  21 #include "src/core/SkTInternalLList.h"
  22
  23 #include <algorithm>
  24 #include <cstdint>
  25 #include <limits>
  26 #include <new>
  27
  28 //////////////////////////////////////////////////////////////////////////////////
  29 // Helper data structures and functions
  30
  31 struct OffsetSegment {
  32     SkPoint fP0;
  33     SkVector fV;
  34 };
  35
  36 constexpr SkScalar kCrossTolerance = SK_ScalarNearlyZero * SK_ScalarNearlyZero;
  37
  38 // Computes perpDot for point p compared to segment defined by origin p0 and vector v.
  39 // A positive value means the point is to the left of the segment,
  40 // negative is to the right, 0 is collinear.
  41 static int compute_side(const SkPoint& p0, const SkVector& v, const SkPoint& p) {
  42     SkVector w = p - p0;
  43     SkScalar perpDot = v.cross(w);
  44     if (!SkScalarNearlyZero(perpDot, kCrossTolerance)) {
  45         return ((perpDot > 0) ? 1 : -1);
  46     }
  47
  48     return 0;
  49 }
  50
  51 // Returns 1 for cw, -1 for ccw and 0 if zero signed area (either degenerate or self-intersecting)
  52 int SkGetPolygonWinding(const SkPoint* polygonVerts, int polygonSize) {
  53     if (polygonSize < 3) {
  54         return 0;
  55     }
  56
  57     // compute area and use sign to determine winding
  58     SkScalar quadArea = 0;
  59     SkVector v0 = polygonVerts[1] - polygonVerts[0];
  60     for (int curr = 2; curr < polygonSize; ++curr) {
  61         SkVector v1 = polygonVerts[curr] - polygonVerts[0];
  62         quadArea += v0.cross(v1);
  63         v0 = v1;
  64     }
  65     if (SkScalarNearlyZero(quadArea, kCrossTolerance)) {
  66         return 0;
  67     }
  68     // 1 == ccw, -1 == cw
  69     return (quadArea > 0) ? 1 : -1;
  70 }
  71
  72 // Compute difference vector to offset p0-p1 'offset' units in direction specified by 'side'
  73 bool compute_offset_vector(const SkPoint& p0, const SkPoint& p1, SkScalar offset, int side,
  74                            SkPoint* vector) {
  75     SkASSERT(side == -1 || side == 1);
  76     // if distances are equal, can just outset by the perpendicular
  77     SkVector perp = SkVector::Make(p0.fY - p1.fY, p1.fX - p0.fX);
  78     if (!perp.setLength(offset*side)) {
  79         return false;
  80     }
  81     *vector = perp;
  82     return true;
  83 }
  84
  85 // check interval to see if intersection is in segment
  86 static inline bool outside_interval(SkScalar numer, SkScalar denom, bool denomPositive) {
  87     return (denomPositive && (numer < 0 || numer > denom)) ||
  88            (!denomPositive && (numer > 0 || numer < denom));
  89 }
  90
  91 // special zero-length test when we're using vdotv as a denominator
  92 static inline bool zero_length(const SkPoint& v, SkScalar vdotv) {
  93     return !(SkScalarsAreFinite(v.fX, v.fY) && vdotv);
  94 }
  95
  96 // Compute the intersection 'p' between segments s0 and s1, if any.
  97 // 's' is the parametric value for the intersection along 's0' & 't' is the same for 's1'.
  98 // Returns false if there is no intersection.
  99 // If the length squared of a segment is 0, then we treat the segment as degenerate
 100 // and use only the first endpoint for tests.
 101 static bool compute_intersection(const OffsetSegment& s0, const OffsetSegment& s1,
 102                                  SkPoint* p, SkScalar* s, SkScalar* t) {
 103     const SkVector& v0 = s0.fV;
 104     const SkVector& v1 = s1.fV;
 105     SkVector w = s1.fP0 - s0.fP0;
 106     SkScalar denom = v0.cross(v1);
 107     bool denomPositive = (denom > 0);
 108     SkScalar sNumer, tNumer;
 109     if (SkScalarNearlyZero(denom, kCrossTolerance)) {
 110         // segments are parallel, but not collinear
 111         if (!SkScalarNearlyZero(w.cross(v0), kCrossTolerance) ||
 112             !SkScalarNearlyZero(w.cross(v1), kCrossTolerance)) {
 113             return false;
 114         }
 115
 116         // Check for zero-length segments
 117         SkScalar v0dotv0 = v0.dot(v0);
 118         if (zero_length(v0, v0dotv0)) {
 119             // Both are zero-length
 120             SkScalar v1dotv1 = v1.dot(v1);
 121             if (zero_length(v1, v1dotv1)) {
 122                 // Check if they're the same point
 123                 if (!SkPointPriv::CanNormalize(w.fX, w.fY)) {
 124                     *p = s0.fP0;
 125                     *s = 0;
 126                     *t = 0;
 127                     return true;
 128                 } else {
 129                     // Intersection is indeterminate
 130                     return false;
 131                 }
 132             }
 133             // Otherwise project segment0's origin onto segment1
 134             tNumer = v1.dot(-w);
 135             denom = v1dotv1;
 136             if (outside_interval(tNumer, denom, true)) {
 137                 return false;
 138             }
 139             sNumer = 0;
 140         } else {
 141             // Project segment1's endpoints onto segment0
 142             sNumer = v0.dot(w);
 143             denom = v0dotv0;
 144             tNumer = 0;
 145             if (outside_interval(sNumer, denom, true)) {
 146                 // The first endpoint doesn't lie on segment0
 147                 // If segment1 is degenerate, then there's no collision
 148                 SkScalar v1dotv1 = v1.dot(v1);
 149                 if (zero_length(v1, v1dotv1)) {
 150                     return false;
 151                 }
 152
 153                 // Otherwise try the other one
 154                 SkScalar oldSNumer = sNumer;
 155                 sNumer = v0.dot(w + v1);
 156                 tNumer = denom;
 157                 if (outside_interval(sNumer, denom, true)) {
 158                     // it's possible that segment1's interval surrounds segment0
 159                     // this is false if params have the same signs, and in that case no collision
 160                     if (sNumer*oldSNumer > 0) {
 161                         return false;
 162                     }
 163                     // otherwise project segment0's endpoint onto segment1 instead
 164                     sNumer = 0;
 165                     tNumer = v1.dot(-w);
 166                     denom = v1dotv1;
 167                 }
 168             }
 169         }
 170     } else {
 171         sNumer = w.cross(v1);
 172         if (outside_interval(sNumer, denom, denomPositive)) {
 173             return false;
 174         }
 175         tNumer = w.cross(v0);
 176         if (outside_interval(tNumer, denom, denomPositive)) {
 177             return false;
 178         }
 179     }
 180
 181     SkScalar localS = sNumer/denom;
 182     SkScalar localT = tNumer/denom;
 183
 184     *p = s0.fP0 + v0*localS;
 185     *s = localS;
 186     *t = localT;
 187
 188     return true;
 189 }
 190
 191 bool SkIsConvexPolygon(const SkPoint* polygonVerts, int polygonSize) {
 192     if (polygonSize < 3) {
 193         return false;
 194     }
 195
 196     SkScalar lastPerpDot = 0;
 197     int xSignChangeCount = 0;
 198     int ySignChangeCount = 0;
 199
 200     int prevIndex = polygonSize - 1;
 201     int currIndex = 0;
 202     int nextIndex = 1;
 203     SkVector v0 = polygonVerts[currIndex] - polygonVerts[prevIndex];
 204     SkScalar lastVx = v0.fX;
 205     SkScalar lastVy = v0.fY;
 206     SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
 207     for (int i = 0; i < polygonSize; ++i) {
 208         if (!polygonVerts[i].isFinite()) {
 209             return false;
 210         }
 211
 212         // Check that winding direction is always the same (otherwise we have a reflex vertex)
 213         SkScalar perpDot = v0.cross(v1);
 214         if (lastPerpDot*perpDot < 0) {
 215             return false;
 216         }
 217         if (0 != perpDot) {
 218             lastPerpDot = perpDot;
 219         }
 220
 221         // Check that the signs of the edge vectors don't change more than twice per coordinate
 222         if (lastVx*v1.fX < 0) {
 223             xSignChangeCount++;
 224         }
 225         if (lastVy*v1.fY < 0) {
 226             ySignChangeCount++;
 227         }
 228         if (xSignChangeCount > 2 || ySignChangeCount > 2) {
 229             return false;
 230         }
 231         prevIndex = currIndex;
 232         currIndex = nextIndex;
 233         nextIndex = (currIndex + 1) % polygonSize;
 234         if (v1.fX != 0) {
 235             lastVx = v1.fX;
 236         }
 237         if (v1.fY != 0) {
 238             lastVy = v1.fY;
 239         }
 240         v0 = v1;
 241         v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
 242     }
 243
 244     return true;
 245 }
 246
 247 struct OffsetEdge {
 248     OffsetEdge*   fPrev;
 249     OffsetEdge*   fNext;
 250     OffsetSegment fOffset;
 251     SkPoint       fIntersection;
 252     SkScalar      fTValue;
 253     uint16_t      fIndex;
 254     uint16_t      fEnd;
 255
 256     void init(uint16_t start = 0, uint16_t end = 0) {
 257         fIntersection = fOffset.fP0;
 258         fTValue = SK_ScalarMin;
 259         fIndex = start;
 260         fEnd = end;
 261     }
 262
 263     // special intersection check that looks for endpoint intersection
 264     bool checkIntersection(const OffsetEdge* that,
 265                            SkPoint* p, SkScalar* s, SkScalar* t) {
 266         if (this->fEnd == that->fIndex) {
 267             SkPoint p1 = this->fOffset.fP0 + this->fOffset.fV;
 268             if (SkPointPriv::EqualsWithinTolerance(p1, that->fOffset.fP0)) {
 269                 *p = p1;
 270                 *s = SK_Scalar1;
 271                 *t = 0;
 272                 return true;
 273             }
 274         }
 275
 276         return compute_intersection(this->fOffset, that->fOffset, p, s, t);
 277     }
 278
 279     // computes the line intersection and then the "distance" from that to this
 280     // this is really a signed squared distance, where negative means that
 281     // the intersection lies inside this->fOffset
 282     SkScalar computeCrossingDistance(const OffsetEdge* that) {
 283         const OffsetSegment& s0 = this->fOffset;
 284         const OffsetSegment& s1 = that->fOffset;
 285         const SkVector& v0 = s0.fV;
 286         const SkVector& v1 = s1.fV;
 287
 288         SkScalar denom = v0.cross(v1);
 289         if (SkScalarNearlyZero(denom, kCrossTolerance)) {
 290             // segments are parallel
 291             return SK_ScalarMax;
 292         }
 293
 294         SkVector w = s1.fP0 - s0.fP0;
 295         SkScalar localS = w.cross(v1) / denom;
 296         if (localS < 0) {
 297             localS = -localS;
 298         } else {
 299             localS -= SK_Scalar1;
 300         }
 301
 302         localS *= SkScalarAbs(localS);
 303         localS *= v0.dot(v0);
 304
 305         return localS;
 306     }
 307
 308 };
 309
 310 static void remove_node(const OffsetEdge* node, OffsetEdge** head) {
 311     // remove from linked list
 312     node->fPrev->fNext = node->fNext;
 313     node->fNext->fPrev = node->fPrev;
 314     if (node == *head) {
 315         *head = (node->fNext == node) ? nullptr : node->fNext;
 316     }
 317 }
 318
 319 //////////////////////////////////////////////////////////////////////////////////
 320
 321 // The objective here is to inset all of the edges by the given distance, and then
 322 // remove any invalid inset edges by detecting right-hand turns. In a ccw polygon,
 323 // we should only be making left-hand turns (for cw polygons, we use the winding
 324 // parameter to reverse this). We detect this by checking whether the second intersection
 325 // on an edge is closer to its tail than the first one.
 326 //
 327 // We might also have the case that there is no intersection between two neighboring inset edges.
 328 // In this case, one edge will lie to the right of the other and should be discarded along with
 329 // its previous intersection (if any).
 330 //
 331 // Note: the assumption is that inputPolygon is convex and has no coincident points.
 332 //
 333 bool SkInsetConvexPolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
 334                           SkScalar inset, SkTDArray<SkPoint>* insetPolygon) {
 335     if (inputPolygonSize < 3) {
 336         return false;
 337     }
 338
 339     // restrict this to match other routines
 340     // practically we don't want anything bigger than this anyway
 341     if (inputPolygonSize > std::numeric_limits<uint16_t>::max()) {
 342         return false;
 343     }
 344
 345     // can't inset by a negative or non-finite amount
 346     if (inset < -SK_ScalarNearlyZero || !SkScalarIsFinite(inset)) {
 347         return false;
 348     }
 349
 350     // insetting close to zero just returns the original poly
 351     if (inset <= SK_ScalarNearlyZero) {
 352         for (int i = 0; i < inputPolygonSize; ++i) {
 353             *insetPolygon->push() = inputPolygonVerts[i];
 354         }
 355         return true;
 356     }
 357
 358     // get winding direction
 359     int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
 360     if (0 == winding) {
 361         return false;
 362     }
 363
 364     // set up
 365     SkAutoSTMalloc<64, OffsetEdge> edgeData(inputPolygonSize);
 366     int prev = inputPolygonSize - 1;
 367     for (int curr = 0; curr < inputPolygonSize; prev = curr, ++curr) {
 368         int next = (curr + 1) % inputPolygonSize;
 369         if (!inputPolygonVerts[curr].isFinite()) {
 370             return false;
 371         }
 372         // check for convexity just to be sure
 373         if (compute_side(inputPolygonVerts[prev], inputPolygonVerts[curr] - inputPolygonVerts[prev],
 374                          inputPolygonVerts[next])*winding < 0) {
 375             return false;
 376         }
 377         SkVector v = inputPolygonVerts[next] - inputPolygonVerts[curr];
 378         SkVector perp = SkVector::Make(-v.fY, v.fX);
 379         perp.setLength(inset*winding);
 380         edgeData[curr].fPrev = &edgeData[prev];
 381         edgeData[curr].fNext = &edgeData[next];
 382         edgeData[curr].fOffset.fP0 = inputPolygonVerts[curr] + perp;
 383         edgeData[curr].fOffset.fV = v;
 384         edgeData[curr].init();
 385     }
 386
 387     OffsetEdge* head = &edgeData[0];
 388     OffsetEdge* currEdge = head;
 389     OffsetEdge* prevEdge = currEdge->fPrev;
 390     int insetVertexCount = inputPolygonSize;
 391     unsigned int iterations = 0;
 392     unsigned int maxIterations = inputPolygonSize * inputPolygonSize;
 393     while (head && prevEdge != currEdge) {
 394         ++iterations;
 395         // we should check each edge against each other edge at most once
 396         if (iterations > maxIterations) {
 397             return false;
 398         }
 399
 400         SkScalar s, t;
 401         SkPoint intersection;
 402         if (compute_intersection(prevEdge->fOffset, currEdge->fOffset,
 403                                  &intersection, &s, &t)) {
 404             // if new intersection is further back on previous inset from the prior intersection
 405             if (s < prevEdge->fTValue) {
 406                 // no point in considering this one again
 407                 remove_node(prevEdge, &head);
 408                 --insetVertexCount;
 409                 // go back one segment
 410                 prevEdge = prevEdge->fPrev;
 411             // we've already considered this intersection, we're done
 412             } else if (currEdge->fTValue > SK_ScalarMin &&
 413                        SkPointPriv::EqualsWithinTolerance(intersection,
 414                                                           currEdge->fIntersection,
 415                                                           1.0e-6f)) {
 416                 break;
 417             } else {
 418                 // add intersection
 419                 currEdge->fIntersection = intersection;
 420                 currEdge->fTValue = t;
 421
 422                 // go to next segment
 423                 prevEdge = currEdge;
 424                 currEdge = currEdge->fNext;
 425             }
 426         } else {
 427             // if prev to right side of curr
 428             int side = winding*compute_side(currEdge->fOffset.fP0,
 429                                             currEdge->fOffset.fV,
 430                                             prevEdge->fOffset.fP0);
 431             if (side < 0 &&
 432                 side == winding*compute_side(currEdge->fOffset.fP0,
 433                                              currEdge->fOffset.fV,
 434                                              prevEdge->fOffset.fP0 + prevEdge->fOffset.fV)) {
 435                 // no point in considering this one again
 436                 remove_node(prevEdge, &head);
 437                 --insetVertexCount;
 438                 // go back one segment
 439                 prevEdge = prevEdge->fPrev;
 440             } else {
 441                 // move to next segment
 442                 remove_node(currEdge, &head);
 443                 --insetVertexCount;
 444                 currEdge = currEdge->fNext;
 445             }
 446         }
 447     }
 448
 449     // store all the valid intersections that aren't nearly coincident
 450     // TODO: look at the main algorithm and see if we can detect these better
 451     insetPolygon->reset();
 452     if (!head) {
 453         return false;
 454     }
 455
 456     static constexpr SkScalar kCleanupTolerance = 0.01f;
 457     if (insetVertexCount >= 0) {
 458         insetPolygon->setReserve(insetVertexCount);
 459     }
 460     int currIndex = 0;
 461     *insetPolygon->push() = head->fIntersection;
 462     currEdge = head->fNext;
 463     while (currEdge != head) {
 464         if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
 465                                                 (*insetPolygon)[currIndex],
 466                                                 kCleanupTolerance)) {
 467             *insetPolygon->push() = currEdge->fIntersection;
 468             currIndex++;
 469         }
 470         currEdge = currEdge->fNext;
 471     }
 472     // make sure the first and last points aren't coincident
 473     if (currIndex >= 1 &&
 474         SkPointPriv::EqualsWithinTolerance((*insetPolygon)[0], (*insetPolygon)[currIndex],
 475                                             kCleanupTolerance)) {
 476         insetPolygon->pop();
 477     }
 478
 479     return SkIsConvexPolygon(insetPolygon->begin(), insetPolygon->count());
 480 }
 481
 482 ///////////////////////////////////////////////////////////////////////////////////////////
 483
 484 // compute the number of points needed for a circular join when offsetting a reflex vertex
 485 bool SkComputeRadialSteps(const SkVector& v1, const SkVector& v2, SkScalar offset,
 486                           SkScalar* rotSin, SkScalar* rotCos, int* n) {
 487     const SkScalar kRecipPixelsPerArcSegment = 0.25f;
 488
 489     SkScalar rCos = v1.dot(v2);
 490     if (!SkScalarIsFinite(rCos)) {
 491         return false;
 492     }
 493     SkScalar rSin = v1.cross(v2);
 494     if (!SkScalarIsFinite(rSin)) {
 495         return false;
 496     }
 497     SkScalar theta = SkScalarATan2(rSin, rCos);
 498
 499     SkScalar floatSteps = SkScalarAbs(offset*theta*kRecipPixelsPerArcSegment);
 500     // limit the number of steps to at most max uint16_t (that's all we can index)
 501     // knock one value off the top to account for rounding
 502     if (floatSteps >= std::numeric_limits<uint16_t>::max()) {
 503         return false;
 504     }
 505     int steps = SkScalarRoundToInt(floatSteps);
 506
 507     SkScalar dTheta = steps > 0 ? theta / steps : 0;
 508     *rotSin = SkScalarSin(dTheta);
 509     *rotCos = SkScalarCos(dTheta);
 510     // Our offset may be so large that we end up with a tiny dTheta, in which case we
 511     // lose precision when computing rotSin and rotCos.
 512     if (steps > 0 && (*rotSin == 0 || *rotCos == 1)) {
 513         return false;
 514     }
 515     *n = steps;
 516     return true;
 517 }
 518
 519 ///////////////////////////////////////////////////////////////////////////////////////////
 520
 521 // a point is "left" to another if its x-coord is less, or if equal, its y-coord is greater
 522 static bool left(const SkPoint& p0, const SkPoint& p1) {
 523     return p0.fX < p1.fX || (!(p0.fX > p1.fX) && p0.fY > p1.fY);
 524 }
 525
 526 // a point is "right" to another if its x-coord is greater, or if equal, its y-coord is less
 527 static bool right(const SkPoint& p0, const SkPoint& p1) {
 528     return p0.fX > p1.fX || (!(p0.fX < p1.fX) && p0.fY < p1.fY);
 529 }
 530
 531 struct Vertex {
 532     static bool Left(const Vertex& qv0, const Vertex& qv1) {
 533         return left(qv0.fPosition, qv1.fPosition);
 534     }
 535
 536     // packed to fit into 16 bytes (one cache line)
 537     SkPoint  fPosition;
 538     uint16_t fIndex;       // index in unsorted polygon
 539     uint16_t fPrevIndex;   // indices for previous and next vertex in unsorted polygon
 540     uint16_t fNextIndex;
 541     uint16_t fFlags;
 542 };
 543
 544 enum VertexFlags {
 545     kPrevLeft_VertexFlag = 0x1,
 546     kNextLeft_VertexFlag = 0x2,
 547 };
 548
 549 struct ActiveEdge {
 550     ActiveEdge() : fChild{ nullptr, nullptr }, fAbove(nullptr), fBelow(nullptr), fRed(false) {}
 551     ActiveEdge(const SkPoint& p0, const SkVector& v, uint16_t index0, uint16_t index1)
 552         : fSegment({ p0, v })
 553         , fIndex0(index0)
 554         , fIndex1(index1)
 555         , fAbove(nullptr)
 556         , fBelow(nullptr)
 557         , fRed(true) {
 558         fChild[0] = nullptr;
 559         fChild[1] = nullptr;
 560     }
 561
 562     // Returns true if "this" is above "that", assuming this->p0 is to the left of that->p0
 563     // This is only used to verify the edgelist -- the actual test for insertion/deletion is much
 564     // simpler because we can make certain assumptions then.
 565     bool aboveIfLeft(const ActiveEdge* that) const {
 566         const SkPoint& p0 = this->fSegment.fP0;
 567         const SkPoint& q0 = that->fSegment.fP0;
 568         SkASSERT(p0.fX <= q0.fX);
 569         SkVector d = q0 - p0;
 570         const SkVector& v = this->fSegment.fV;
 571         const SkVector& w = that->fSegment.fV;
 572         // The idea here is that if the vector between the origins of the two segments (d)
 573         // rotates counterclockwise up to the vector representing the "this" segment (v),
 574         // then we know that "this" is above "that". If the result is clockwise we say it's below.
 575         if (this->fIndex0 != that->fIndex0) {
 576             SkScalar cross = d.cross(v);
 577             if (cross > kCrossTolerance) {
 578                 return true;
 579             } else if (cross < -kCrossTolerance) {
 580                 return false;
 581             }
 582         } else if (this->fIndex1 == that->fIndex1) {
 583             return false;
 584         }
 585         // At this point either the two origins are nearly equal or the origin of "that"
 586         // lies on dv. So then we try the same for the vector from the tail of "this"
 587         // to the head of "that". Again, ccw means "this" is above "that".
 588         // d = that.P1 - this.P0
 589         //   = that.fP0 + that.fV - this.fP0
 590         //   = that.fP0 - this.fP0 + that.fV
 591         //   = old_d + that.fV
 592         d += w;
 593         SkScalar cross = d.cross(v);
 594         if (cross > kCrossTolerance) {
 595             return true;
 596         } else if (cross < -kCrossTolerance) {
 597             return false;
 598         }
 599         // If the previous check fails, the two segments are nearly collinear
 600         // First check y-coord of first endpoints
 601         if (p0.fX < q0.fX) {
 602             return (p0.fY >= q0.fY);
 603         } else if (p0.fY > q0.fY) {
 604             return true;
 605         } else if (p0.fY < q0.fY) {
 606             return false;
 607         }
 608         // The first endpoints are the same, so check the other endpoint
 609         SkPoint p1 = p0 + v;
 610         SkPoint q1 = q0 + w;
 611         if (p1.fX < q1.fX) {
 612             return (p1.fY >= q1.fY);
 613         } else {
 614             return (p1.fY > q1.fY);
 615         }
 616     }
 617
 618     // same as leftAndAbove(), but generalized
 619     bool above(const ActiveEdge* that) const {
 620         const SkPoint& p0 = this->fSegment.fP0;
 621         const SkPoint& q0 = that->fSegment.fP0;
 622         if (right(p0, q0)) {
 623             return !that->aboveIfLeft(this);
 624         } else {
 625             return this->aboveIfLeft(that);
 626         }
 627     }
 628
 629     bool intersect(const SkPoint& q0, const SkVector& w, uint16_t index0, uint16_t index1) const {
 630         // check first to see if these edges are neighbors in the polygon
 631         if (this->fIndex0 == index0 || this->fIndex1 == index0 ||
 632             this->fIndex0 == index1 || this->fIndex1 == index1) {
 633             return false;
 634         }
 635
 636         // We don't need the exact intersection point so we can do a simpler test here.
 637         const SkPoint& p0 = this->fSegment.fP0;
 638         const SkVector& v = this->fSegment.fV;
 639         SkPoint p1 = p0 + v;
 640         SkPoint q1 = q0 + w;
 641
 642         // We assume some x-overlap due to how the edgelist works
 643         // This allows us to simplify our test
 644         // We need some slop here because storing the vector and recomputing the second endpoint
 645         // doesn't necessary give us the original result in floating point.
 646         // TODO: Store vector as double? Store endpoint as well?
 647         SkASSERT(q0.fX <= p1.fX + SK_ScalarNearlyZero);
 648
 649         // if each segment straddles the other (i.e., the endpoints have different sides)
 650         // then they intersect
 651         bool result;
 652         if (p0.fX < q0.fX) {
 653             if (q1.fX < p1.fX) {
 654                 result = (compute_side(p0, v, q0)*compute_side(p0, v, q1) < 0);
 655             } else {
 656                 result = (compute_side(p0, v, q0)*compute_side(q0, w, p1) > 0);
 657             }
 658         } else {
 659             if (p1.fX < q1.fX) {
 660                 result = (compute_side(q0, w, p0)*compute_side(q0, w, p1) < 0);
 661             } else {
 662                 result = (compute_side(q0, w, p0)*compute_side(p0, v, q1) > 0);
 663             }
 664         }
 665         return result;
 666     }
 667
 668     bool intersect(const ActiveEdge* edge) {
 669         return this->intersect(edge->fSegment.fP0, edge->fSegment.fV, edge->fIndex0, edge->fIndex1);
 670     }
 671
 672     bool lessThan(const ActiveEdge* that) const {
 673         SkASSERT(!this->above(this));
 674         SkASSERT(!that->above(that));
 675         SkASSERT(!(this->above(that) && that->above(this)));
 676         return this->above(that);
 677     }
 678
 679     bool equals(uint16_t index0, uint16_t index1) const {
 680         return (this->fIndex0 == index0 && this->fIndex1 == index1);
 681     }
 682
 683     OffsetSegment fSegment;
 684     uint16_t fIndex0;   // indices for previous and next vertex in polygon
 685     uint16_t fIndex1;
 686     ActiveEdge* fChild[2];
 687     ActiveEdge* fAbove;
 688     ActiveEdge* fBelow;
 689     int32_t  fRed;
 690 };
 691
 692 class ActiveEdgeList {
 693 public:
 694     ActiveEdgeList(int maxEdges) {
 695         fAllocation = (char*) sk_malloc_throw(sizeof(ActiveEdge)*maxEdges);
 696         fCurrFree = 0;
 697         fMaxFree = maxEdges;
 698     }
 699     ~ActiveEdgeList() {
 700         fTreeHead.fChild[1] = nullptr;
 701         sk_free(fAllocation);
 702     }
 703
 704     bool insert(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
 705         SkVector v = p1 - p0;
 706         if (!v.isFinite()) {
 707             return false;
 708         }
 709         // empty tree case -- easy
 710         if (!fTreeHead.fChild[1]) {
 711             ActiveEdge* root = fTreeHead.fChild[1] = this->allocate(p0, v, index0, index1);
 712             SkASSERT(root);
 713             if (!root) {
 714                 return false;
 715             }
 716             root->fRed = false;
 717             return true;
 718         }
 719
 720         // set up helpers
 721         ActiveEdge* top = &fTreeHead;
 722         ActiveEdge *grandparent = nullptr;
 723         ActiveEdge *parent = nullptr;
 724         ActiveEdge *curr = top->fChild[1];
 725         int dir = 0;
 726         int last = 0; // ?
 727         // predecessor and successor, for intersection check
 728         ActiveEdge* pred = nullptr;
 729         ActiveEdge* succ = nullptr;
 730
 731         // search down the tree
 732         while (true) {
 733             if (!curr) {
 734                 // check for intersection with predecessor and successor
 735                 if ((pred && pred->intersect(p0, v, index0, index1)) ||
 736                     (succ && succ->intersect(p0, v, index0, index1))) {
 737                     return false;
 738                 }
 739                 // insert new node at bottom
 740                 parent->fChild[dir] = curr = this->allocate(p0, v, index0, index1);
 741                 SkASSERT(curr);
 742                 if (!curr) {
 743                     return false;
 744                 }
 745                 curr->fAbove = pred;
 746                 curr->fBelow = succ;
 747                 if (pred) {
 748                     if (pred->fSegment.fP0 == curr->fSegment.fP0 &&
 749                         pred->fSegment.fV == curr->fSegment.fV) {
 750                         return false;
 751                     }
 752                     pred->fBelow = curr;
 753                 }
 754                 if (succ) {
 755                     if (succ->fSegment.fP0 == curr->fSegment.fP0 &&
 756                         succ->fSegment.fV == curr->fSegment.fV) {
 757                         return false;
 758                     }
 759                     succ->fAbove = curr;
 760                 }
 761                 if (IsRed(parent)) {
 762                     int dir2 = (top->fChild[1] == grandparent);
 763                     if (curr == parent->fChild[last]) {
 764                         top->fChild[dir2] = SingleRotation(grandparent, !last);
 765                     } else {
 766                         top->fChild[dir2] = DoubleRotation(grandparent, !last);
 767                     }
 768                 }
 769                 break;
 770             } else if (IsRed(curr->fChild[0]) && IsRed(curr->fChild[1])) {
 771                 // color flip
 772                 curr->fRed = true;
 773                 curr->fChild[0]->fRed = false;
 774                 curr->fChild[1]->fRed = false;
 775                 if (IsRed(parent)) {
 776                     int dir2 = (top->fChild[1] == grandparent);
 777                     if (curr == parent->fChild[last]) {
 778                         top->fChild[dir2] = SingleRotation(grandparent, !last);
 779                     } else {
 780                         top->fChild[dir2] = DoubleRotation(grandparent, !last);
 781                     }
 782                 }
 783             }
 784
 785             last = dir;
 786             int side;
 787             // check to see if segment is above or below
 788             if (curr->fIndex0 == index0) {
 789                 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
 790             } else {
 791                 side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
 792             }
 793             if (0 == side) {
 794                 return false;
 795             }
 796             dir = (side < 0);
 797
 798             if (0 == dir) {
 799                 succ = curr;
 800             } else {
 801                 pred = curr;
 802             }
 803
 804             // update helpers
 805             if (grandparent) {
 806                 top = grandparent;
 807             }
 808             grandparent = parent;
 809             parent = curr;
 810             curr = curr->fChild[dir];
 811         }
 812
 813         // update root and make it black
 814         fTreeHead.fChild[1]->fRed = false;
 815
 816         SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
 817
 818         return true;
 819     }
 820
 821     // replaces edge p0p1 with p1p2
 822     bool replace(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
 823                  uint16_t index0, uint16_t index1, uint16_t index2) {
 824         if (!fTreeHead.fChild[1]) {
 825             return false;
 826         }
 827
 828         SkVector v = p2 - p1;
 829         ActiveEdge* curr = &fTreeHead;
 830         ActiveEdge* found = nullptr;
 831         int dir = 1;
 832
 833         // search
 834         while (curr->fChild[dir] != nullptr) {
 835             // update helpers
 836             curr = curr->fChild[dir];
 837             // save found node
 838             if (curr->equals(index0, index1)) {
 839                 found = curr;
 840                 break;
 841             } else {
 842                 // check to see if segment is above or below
 843                 int side;
 844                 if (curr->fIndex1 == index1) {
 845                     side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
 846                 } else {
 847                     side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
 848                 }
 849                 if (0 == side) {
 850                     return false;
 851                 }
 852                 dir = (side < 0);
 853             }
 854         }
 855
 856         if (!found) {
 857             return false;
 858         }
 859
 860         // replace if found
 861         ActiveEdge* pred = found->fAbove;
 862         ActiveEdge* succ = found->fBelow;
 863         // check deletion and insert intersection cases
 864         if (pred && (pred->intersect(found) || pred->intersect(p1, v, index1, index2))) {
 865             return false;
 866         }
 867         if (succ && (succ->intersect(found) || succ->intersect(p1, v, index1, index2))) {
 868             return false;
 869         }
 870         found->fSegment.fP0 = p1;
 871         found->fSegment.fV = v;
 872         found->fIndex0 = index1;
 873         found->fIndex1 = index2;
 874         // above and below should stay the same
 875
 876         SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
 877
 878         return true;
 879     }
 880
 881     bool remove(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
 882         if (!fTreeHead.fChild[1]) {
 883             return false;
 884         }
 885
 886         ActiveEdge* curr = &fTreeHead;
 887         ActiveEdge* parent = nullptr;
 888         ActiveEdge* grandparent = nullptr;
 889         ActiveEdge* found = nullptr;
 890         int dir = 1;
 891
 892         // search and push a red node down
 893         while (curr->fChild[dir] != nullptr) {
 894             int last = dir;
 895
 896             // update helpers
 897             grandparent = parent;
 898             parent = curr;
 899             curr = curr->fChild[dir];
 900             // save found node
 901             if (curr->equals(index0, index1)) {
 902                 found = curr;
 903                 dir = 0;
 904             } else {
 905                 // check to see if segment is above or below
 906                 int side;
 907                 if (curr->fIndex1 == index1) {
 908                     side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
 909                 } else {
 910                     side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
 911                 }
 912                 if (0 == side) {
 913                     return false;
 914                 }
 915                 dir = (side < 0);
 916             }
 917
 918             // push the red node down
 919             if (!IsRed(curr) && !IsRed(curr->fChild[dir])) {
 920                 if (IsRed(curr->fChild[!dir])) {
 921                     parent = parent->fChild[last] = SingleRotation(curr, dir);
 922                 } else {
 923                     ActiveEdge *s = parent->fChild[!last];
 924
 925                     if (s != nullptr) {
 926                         if (!IsRed(s->fChild[!last]) && !IsRed(s->fChild[last])) {
 927                             // color flip
 928                             parent->fRed = false;
 929                             s->fRed = true;
 930                             curr->fRed = true;
 931                         } else {
 932                             int dir2 = (grandparent->fChild[1] == parent);
 933
 934                             if (IsRed(s->fChild[last])) {
 935                                 grandparent->fChild[dir2] = DoubleRotation(parent, last);
 936                             } else if (IsRed(s->fChild[!last])) {
 937                                 grandparent->fChild[dir2] = SingleRotation(parent, last);
 938                             }
 939
 940                             // ensure correct coloring
 941                             curr->fRed = grandparent->fChild[dir2]->fRed = true;
 942                             grandparent->fChild[dir2]->fChild[0]->fRed = false;
 943                             grandparent->fChild[dir2]->fChild[1]->fRed = false;
 944                         }
 945                     }
 946                 }
 947             }
 948         }
 949
 950         // replace and remove if found
 951         if (found) {
 952             ActiveEdge* pred = found->fAbove;
 953             ActiveEdge* succ = found->fBelow;
 954             if ((pred && pred->intersect(found)) || (succ && succ->intersect(found))) {
 955                 return false;
 956             }
 957             if (found != curr) {
 958                 found->fSegment = curr->fSegment;
 959                 found->fIndex0 = curr->fIndex0;
 960                 found->fIndex1 = curr->fIndex1;
 961                 found->fAbove = curr->fAbove;
 962                 pred = found->fAbove;
 963                 // we don't need to set found->fBelow here
 964             } else {
 965                 if (succ) {
 966                     succ->fAbove = pred;
 967                 }
 968             }
 969             if (pred) {
 970                 pred->fBelow = curr->fBelow;
 971             }
 972             parent->fChild[parent->fChild[1] == curr] = curr->fChild[!curr->fChild[0]];
 973
 974             // no need to delete
 975             curr->fAbove = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
 976             curr->fBelow = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
 977             if (fTreeHead.fChild[1]) {
 978                 fTreeHead.fChild[1]->fRed = false;
 979             }
 980         }
 981
 982         // update root and make it black
 983         if (fTreeHead.fChild[1]) {
 984             fTreeHead.fChild[1]->fRed = false;
 985         }
 986
 987         SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
 988
 989         return true;
 990     }
 991
 992 private:
 993     // allocator
 994     ActiveEdge * allocate(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
 995         if (fCurrFree >= fMaxFree) {
 996             return nullptr;
 997         }
 998         char* bytes = fAllocation + sizeof(ActiveEdge)*fCurrFree;
 999         ++fCurrFree;
1000         return new(bytes) ActiveEdge(p0, p1, index0, index1);
1001     }
1002
1003     ///////////////////////////////////////////////////////////////////////////////////
1004     // Red-black tree methods
1005     ///////////////////////////////////////////////////////////////////////////////////
1006     static bool IsRed(const ActiveEdge* node) {
1007         return node && node->fRed;
1008     }
1009
1010     static ActiveEdge* SingleRotation(ActiveEdge* node, int dir) {
1011         ActiveEdge* tmp = node->fChild[!dir];
1012
1013         node->fChild[!dir] = tmp->fChild[dir];
1014         tmp->fChild[dir] = node;
1015
1016         node->fRed = true;
1017         tmp->fRed = false;
1018
1019         return tmp;
1020     }
1021
1022     static ActiveEdge* DoubleRotation(ActiveEdge* node, int dir) {
1023         node->fChild[!dir] = SingleRotation(node->fChild[!dir], !dir);
1024
1025         return SingleRotation(node, dir);
1026     }
1027
1028     // returns black link count
1029     static int VerifyTree(const ActiveEdge* tree) {
1030         if (!tree) {
1031             return 1;
1032         }
1033
1034         const ActiveEdge* left = tree->fChild[0];
1035         const ActiveEdge* right = tree->fChild[1];
1036
1037         // no consecutive red links
1038         if (IsRed(tree) && (IsRed(left) || IsRed(right))) {
1039             SkASSERT(false);
1040             return 0;
1041         }
1042
1043         // check secondary links
1044         if (tree->fAbove) {
1045             SkASSERT(tree->fAbove->fBelow == tree);
1046             SkASSERT(tree->fAbove->lessThan(tree));
1047         }
1048         if (tree->fBelow) {
1049             SkASSERT(tree->fBelow->fAbove == tree);
1050             SkASSERT(tree->lessThan(tree->fBelow));
1051         }
1052
1053         // violates binary tree order
1054         if ((left && tree->lessThan(left)) || (right && right->lessThan(tree))) {
1055             SkASSERT(false);
1056             return 0;
1057         }
1058
1059         int leftCount = VerifyTree(left);
1060         int rightCount = VerifyTree(right);
1061
1062         // return black link count
1063         if (leftCount != 0 && rightCount != 0) {
1064             // black height mismatch
1065             if (leftCount != rightCount) {
1066                 SkASSERT(false);
1067                 return 0;
1068             }
1069             return IsRed(tree) ? leftCount : leftCount + 1;
1070         } else {
1071             return 0;
1072         }
1073     }
1074
1075     ActiveEdge fTreeHead;
1076     char*      fAllocation;
1077     int        fCurrFree;
1078     int        fMaxFree;
1079 };
1080
1081 // Here we implement a sweep line algorithm to determine whether the provided points
1082 // represent a simple polygon, i.e., the polygon is non-self-intersecting.
1083 // We first insert the vertices into a priority queue sorting horizontally from left to right.
1084 // Then as we pop the vertices from the queue we generate events which indicate that an edge
1085 // should be added or removed from an edge list. If any intersections are detected in the edge
1086 // list, then we know the polygon is self-intersecting and hence not simple.
1087 bool SkIsSimplePolygon(const SkPoint* polygon, int polygonSize) {
1088     if (polygonSize < 3) {
1089         return false;
1090     }
1091
1092     // If it's convex, it's simple
1093     if (SkIsConvexPolygon(polygon, polygonSize)) {
1094         return true;
1095     }
1096
1097     // practically speaking, it takes too long to process large polygons
1098     if (polygonSize > 2048) {
1099         return false;
1100     }
1101
1102     SkTDPQueue <Vertex, Vertex::Left> vertexQueue(polygonSize);
1103     for (int i = 0; i < polygonSize; ++i) {
1104         Vertex newVertex;
1105         if (!polygon[i].isFinite()) {
1106             return false;
1107         }
1108         newVertex.fPosition = polygon[i];
1109         newVertex.fIndex = i;
1110         newVertex.fPrevIndex = (i - 1 + polygonSize) % polygonSize;
1111         newVertex.fNextIndex = (i + 1) % polygonSize;
1112         newVertex.fFlags = 0;
1113         // The two edges adjacent to this vertex are the same, so polygon is not simple
1114         if (polygon[newVertex.fPrevIndex] == polygon[newVertex.fNextIndex]) {
1115             return false;
1116         }
1117         if (left(polygon[newVertex.fPrevIndex], polygon[i])) {
1118             newVertex.fFlags |= kPrevLeft_VertexFlag;
1119         }
1120         if (left(polygon[newVertex.fNextIndex], polygon[i])) {
1121             newVertex.fFlags |= kNextLeft_VertexFlag;
1122         }
1123         vertexQueue.insert(newVertex);
1124     }
1125
1126     // pop each vertex from the queue and generate events depending on
1127     // where it lies relative to its neighboring edges
1128     ActiveEdgeList sweepLine(polygonSize);
1129     while (vertexQueue.count() > 0) {
1130         const Vertex& v = vertexQueue.peek();
1131
1132         // both to the right -- insert both
1133         if (v.fFlags == 0) {
1134             if (!sweepLine.insert(v.fPosition, polygon[v.fPrevIndex], v.fIndex, v.fPrevIndex)) {
1135                 break;
1136             }
1137             if (!sweepLine.insert(v.fPosition, polygon[v.fNextIndex], v.fIndex, v.fNextIndex)) {
1138                 break;
1139             }
1140         // both to the left -- remove both
1141         } else if (v.fFlags == (kPrevLeft_VertexFlag | kNextLeft_VertexFlag)) {
1142             if (!sweepLine.remove(polygon[v.fPrevIndex], v.fPosition, v.fPrevIndex, v.fIndex)) {
1143                 break;
1144             }
1145             if (!sweepLine.remove(polygon[v.fNextIndex], v.fPosition, v.fNextIndex, v.fIndex)) {
1146                 break;
1147             }
1148         // one to left and right -- replace one with another
1149         } else {
1150             if (v.fFlags & kPrevLeft_VertexFlag) {
1151                 if (!sweepLine.replace(polygon[v.fPrevIndex], v.fPosition, polygon[v.fNextIndex],
1152                                        v.fPrevIndex, v.fIndex, v.fNextIndex)) {
1153                     break;
1154                 }
1155             } else {
1156                 SkASSERT(v.fFlags & kNextLeft_VertexFlag);
1157                 if (!sweepLine.replace(polygon[v.fNextIndex], v.fPosition, polygon[v.fPrevIndex],
1158                                        v.fNextIndex, v.fIndex, v.fPrevIndex)) {
1159                     break;
1160                 }
1161             }
1162         }
1163
1164         vertexQueue.pop();
1165     }
1166
1167     return (vertexQueue.count() == 0);
1168 }
1169
1170 ///////////////////////////////////////////////////////////////////////////////////////////
1171
1172 // helper function for SkOffsetSimplePolygon
1173 static void setup_offset_edge(OffsetEdge* currEdge,
1174                               const SkPoint& endpoint0, const SkPoint& endpoint1,
1175                               uint16_t startIndex, uint16_t endIndex) {
1176     currEdge->fOffset.fP0 = endpoint0;
1177     currEdge->fOffset.fV = endpoint1 - endpoint0;
1178     currEdge->init(startIndex, endIndex);
1179 }
1180
1181 static bool is_reflex_vertex(const SkPoint* inputPolygonVerts, int winding, SkScalar offset,
1182                              uint16_t prevIndex, uint16_t currIndex, uint16_t nextIndex) {
1183     int side = compute_side(inputPolygonVerts[prevIndex],
1184                             inputPolygonVerts[currIndex] - inputPolygonVerts[prevIndex],
1185                             inputPolygonVerts[nextIndex]);
1186     // if reflex point, we need to add extra edges
1187     return (side*winding*offset < 0);
1188 }
1189
1190 bool SkOffsetSimplePolygon(const SkPoint* inputPolygonVerts, int inputPolygonSize,
1191                            const SkRect& bounds, SkScalar offset,
1192                            SkTDArray<SkPoint>* offsetPolygon, SkTDArray<int>* polygonIndices) {
1193     if (inputPolygonSize < 3) {
1194         return false;
1195     }
1196
1197     // need to be able to represent all the vertices in the 16-bit indices
1198     if (inputPolygonSize >= std::numeric_limits<uint16_t>::max()) {
1199         return false;
1200     }
1201
1202     if (!SkScalarIsFinite(offset)) {
1203         return false;
1204     }
1205
1206     // can't inset more than the half bounds of the polygon
1207     if (offset > std::min(SkTAbs(SkRectPriv::HalfWidth(bounds)),
1208                           SkTAbs(SkRectPriv::HalfHeight(bounds)))) {
1209         return false;
1210     }
1211
1212     // offsetting close to zero just returns the original poly
1213     if (SkScalarNearlyZero(offset)) {
1214         for (int i = 0; i < inputPolygonSize; ++i) {
1215             *offsetPolygon->push() = inputPolygonVerts[i];
1216             if (polygonIndices) {
1217                 *polygonIndices->push() = i;
1218             }
1219         }
1220         return true;
1221     }
1222
1223     // get winding direction
1224     int winding = SkGetPolygonWinding(inputPolygonVerts, inputPolygonSize);
1225     if (0 == winding) {
1226         return false;
1227     }
1228
1229     // build normals
1230     SkAutoSTMalloc<64, SkVector> normals(inputPolygonSize);
1231     unsigned int numEdges = 0;
1232     for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
1233          currIndex < inputPolygonSize;
1234          prevIndex = currIndex, ++currIndex) {
1235         if (!inputPolygonVerts[currIndex].isFinite()) {
1236             return false;
1237         }
1238         int nextIndex = (currIndex + 1) % inputPolygonSize;
1239         if (!compute_offset_vector(inputPolygonVerts[currIndex], inputPolygonVerts[nextIndex],
1240                                    offset, winding, &normals[currIndex])) {
1241             return false;
1242         }
1243         if (currIndex > 0) {
1244             // if reflex point, we need to add extra edges
1245             if (is_reflex_vertex(inputPolygonVerts, winding, offset,
1246                                  prevIndex, currIndex, nextIndex)) {
1247                 SkScalar rotSin, rotCos;
1248                 int numSteps;
1249                 if (!SkComputeRadialSteps(normals[prevIndex], normals[currIndex], offset,
1250                                           &rotSin, &rotCos, &numSteps)) {
1251                     return false;
1252                 }
1253                 numEdges += std::max(numSteps, 1);
1254             }
1255         }
1256         numEdges++;
1257     }
1258     // finish up the edge counting
1259     if (is_reflex_vertex(inputPolygonVerts, winding, offset, inputPolygonSize-1, 0, 1)) {
1260         SkScalar rotSin, rotCos;
1261         int numSteps;
1262         if (!SkComputeRadialSteps(normals[inputPolygonSize-1], normals[0], offset,
1263                                   &rotSin, &rotCos, &numSteps)) {
1264             return false;
1265         }
1266         numEdges += std::max(numSteps, 1);
1267     }
1268
1269     // Make sure we don't overflow the max array count.
1270     // We shouldn't overflow numEdges, as SkComputeRadialSteps returns a max of 2^16-1,
1271     // and we have a max of 2^16-1 original vertices.
1272     if (numEdges > (unsigned int)std::numeric_limits<int32_t>::max()) {
1273         return false;
1274     }
1275
1276     // build initial offset edge list
1277     SkSTArray<64, OffsetEdge> edgeData(numEdges);
1278     OffsetEdge* prevEdge = nullptr;
1279     for (int currIndex = 0, prevIndex = inputPolygonSize - 1;
1280          currIndex < inputPolygonSize;
1281          prevIndex = currIndex, ++currIndex) {
1282         int nextIndex = (currIndex + 1) % inputPolygonSize;
1283         // if reflex point, fill in curve
1284         if (is_reflex_vertex(inputPolygonVerts, winding, offset,
1285                              prevIndex, currIndex, nextIndex)) {
1286             SkScalar rotSin, rotCos;
1287             int numSteps;
1288             SkVector prevNormal = normals[prevIndex];
1289             if (!SkComputeRadialSteps(prevNormal, normals[currIndex], offset,
1290                                       &rotSin, &rotCos, &numSteps)) {
1291                 return false;
1292             }
1293             auto currEdge = edgeData.push_back_n(std::max(numSteps, 1));
1294             for (int i = 0; i < numSteps - 1; ++i) {
1295                 SkVector currNormal = SkVector::Make(prevNormal.fX*rotCos - prevNormal.fY*rotSin,
1296                                                      prevNormal.fY*rotCos + prevNormal.fX*rotSin);
1297                 setup_offset_edge(currEdge,
1298                                   inputPolygonVerts[currIndex] + prevNormal,
1299                                   inputPolygonVerts[currIndex] + currNormal,
1300                                   currIndex, currIndex);
1301                 prevNormal = currNormal;
1302                 currEdge->fPrev = prevEdge;
1303                 if (prevEdge) {
1304                     prevEdge->fNext = currEdge;
1305                 }
1306                 prevEdge = currEdge;
1307                 ++currEdge;
1308             }
1309             setup_offset_edge(currEdge,
1310                               inputPolygonVerts[currIndex] + prevNormal,
1311                               inputPolygonVerts[currIndex] + normals[currIndex],
1312                               currIndex, currIndex);
1313             currEdge->fPrev = prevEdge;
1314             if (prevEdge) {
1315                 prevEdge->fNext = currEdge;
1316             }
1317             prevEdge = currEdge;
1318         }
1319
1320         // Add the edge
1321         auto currEdge = edgeData.push_back_n(1);
1322         setup_offset_edge(currEdge,
1323                           inputPolygonVerts[currIndex] + normals[currIndex],
1324                           inputPolygonVerts[nextIndex] + normals[currIndex],
1325                           currIndex, nextIndex);
1326         currEdge->fPrev = prevEdge;
1327         if (prevEdge) {
1328             prevEdge->fNext = currEdge;
1329         }
1330         prevEdge = currEdge;
1331     }
1332     // close up the linked list
1333     SkASSERT(prevEdge);
1334     prevEdge->fNext = &edgeData[0];
1335     edgeData[0].fPrev = prevEdge;
1336
1337     // now clip edges
1338     SkASSERT(edgeData.count() == (int)numEdges);
1339     auto head = &edgeData[0];
1340     auto currEdge = head;
1341     unsigned int offsetVertexCount = numEdges;
1342     unsigned long long iterations = 0;
1343     unsigned long long maxIterations = (unsigned long long)(numEdges) * numEdges;
1344     while (head && prevEdge != currEdge && offsetVertexCount > 0) {
1345         ++iterations;
1346         // we should check each edge against each other edge at most once
1347         if (iterations > maxIterations) {
1348             return false;
1349         }
1350
1351         SkScalar s, t;
1352         SkPoint intersection;
1353         if (prevEdge->checkIntersection(currEdge, &intersection, &s, &t)) {
1354             // if new intersection is further back on previous inset from the prior intersection
1355             if (s < prevEdge->fTValue) {
1356                 // no point in considering this one again
1357                 remove_node(prevEdge, &head);
1358                 --offsetVertexCount;
1359                 // go back one segment
1360                 prevEdge = prevEdge->fPrev;
1361                 // we've already considered this intersection, we're done
1362             } else if (currEdge->fTValue > SK_ScalarMin &&
1363                        SkPointPriv::EqualsWithinTolerance(intersection,
1364                                                           currEdge->fIntersection,
1365                                                           1.0e-6f)) {
1366                 break;
1367             } else {
1368                 // add intersection
1369                 currEdge->fIntersection = intersection;
1370                 currEdge->fTValue = t;
1371                 currEdge->fIndex = prevEdge->fEnd;
1372
1373                 // go to next segment
1374                 prevEdge = currEdge;
1375                 currEdge = currEdge->fNext;
1376             }
1377         } else {
1378             // If there is no intersection, we want to minimize the distance between
1379             // the point where the segment lines cross and the segments themselves.
1380             OffsetEdge* prevPrevEdge = prevEdge->fPrev;
1381             OffsetEdge* currNextEdge = currEdge->fNext;
1382             SkScalar dist0 = currEdge->computeCrossingDistance(prevPrevEdge);
1383             SkScalar dist1 = prevEdge->computeCrossingDistance(currNextEdge);
1384             // if both lead to direct collision
1385             if (dist0 < 0 && dist1 < 0) {
1386                 // check first to see if either represent parts of one contour
1387                 SkPoint p1 = prevPrevEdge->fOffset.fP0 + prevPrevEdge->fOffset.fV;
1388                 bool prevSameContour = SkPointPriv::EqualsWithinTolerance(p1,
1389                                                                           prevEdge->fOffset.fP0);
1390                 p1 = currEdge->fOffset.fP0 + currEdge->fOffset.fV;
1391                 bool currSameContour = SkPointPriv::EqualsWithinTolerance(p1,
1392                                                                          currNextEdge->fOffset.fP0);
1393
1394                 // want to step along contour to find intersections rather than jump to new one
1395                 if (currSameContour && !prevSameContour) {
1396                     remove_node(currEdge, &head);
1397                     currEdge = currNextEdge;
1398                     --offsetVertexCount;
1399                     continue;
1400                 } else if (prevSameContour && !currSameContour) {
1401                     remove_node(prevEdge, &head);
1402                     prevEdge = prevPrevEdge;
1403                     --offsetVertexCount;
1404                     continue;
1405                 }
1406             }
1407
1408             // otherwise minimize collision distance along segment
1409             if (dist0 < dist1) {
1410                 remove_node(prevEdge, &head);
1411                 prevEdge = prevPrevEdge;
1412             } else {
1413                 remove_node(currEdge, &head);
1414                 currEdge = currNextEdge;
1415             }
1416             --offsetVertexCount;
1417         }
1418     }
1419
1420     // store all the valid intersections that aren't nearly coincident
1421     // TODO: look at the main algorithm and see if we can detect these better
1422     offsetPolygon->reset();
1423     if (!head || offsetVertexCount == 0 ||
1424         offsetVertexCount >= std::numeric_limits<uint16_t>::max()) {
1425         return false;
1426     }
1427
1428     static constexpr SkScalar kCleanupTolerance = 0.01f;
1429     offsetPolygon->setReserve(offsetVertexCount);
1430     int currIndex = 0;
1431     *offsetPolygon->push() = head->fIntersection;
1432     if (polygonIndices) {
1433         *polygonIndices->push() = head->fIndex;
1434     }
1435     currEdge = head->fNext;
1436     while (currEdge != head) {
1437         if (!SkPointPriv::EqualsWithinTolerance(currEdge->fIntersection,
1438                                                 (*offsetPolygon)[currIndex],
1439                                                 kCleanupTolerance)) {
1440             *offsetPolygon->push() = currEdge->fIntersection;
1441             if (polygonIndices) {
1442                 *polygonIndices->push() = currEdge->fIndex;
1443             }
1444             currIndex++;
1445         }
1446         currEdge = currEdge->fNext;
1447     }
1448     // make sure the first and last points aren't coincident
1449     if (currIndex >= 1 &&
1450         SkPointPriv::EqualsWithinTolerance((*offsetPolygon)[0], (*offsetPolygon)[currIndex],
1451                                             kCleanupTolerance)) {
1452         offsetPolygon->pop();
1453         if (polygonIndices) {
1454             polygonIndices->pop();
1455         }
1456     }
1457
1458     // check winding of offset polygon (it should be same as the original polygon)
1459     SkScalar offsetWinding = SkGetPolygonWinding(offsetPolygon->begin(), offsetPolygon->count());
1460
1461     return (winding*offsetWinding > 0 &&
1462             SkIsSimplePolygon(offsetPolygon->begin(), offsetPolygon->count()));
1463 }
1464
1465 //////////////////////////////////////////////////////////////////////////////////////////
1466
1467 struct TriangulationVertex {
1468     SK_DECLARE_INTERNAL_LLIST_INTERFACE(TriangulationVertex);
1469
1470     enum class VertexType { kConvex, kReflex };
1471
1472     SkPoint    fPosition;
1473     VertexType fVertexType;
1474     uint16_t   fIndex;
1475     uint16_t   fPrevIndex;
1476     uint16_t   fNextIndex;
1477 };
1478
1479 static void compute_triangle_bounds(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
1480                                     SkRect* bounds) {
1481     skvx::float4 min, max;
1482     min = max = skvx::float4(p0.fX, p0.fY, p0.fX, p0.fY);
1483     skvx::float4 xy(p1.fX, p1.fY, p2.fX, p2.fY);
1484     min = skvx::min(min, xy);
1485     max = skvx::max(max, xy);
1486     bounds->setLTRB(std::min(min[0], min[2]), std::min(min[1], min[3]),
1487                     std::max(max[0], max[2]), std::max(max[1], max[3]));
1488 }
1489
1490 // test to see if point p is in triangle p0p1p2.
1491 // for now assuming strictly inside -- if on the edge it's outside
1492 static bool point_in_triangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
1493                               const SkPoint& p) {
1494     SkVector v0 = p1 - p0;
1495     SkVector v1 = p2 - p1;
1496     SkScalar n = v0.cross(v1);
1497
1498     SkVector w0 = p - p0;
1499     if (n*v0.cross(w0) < SK_ScalarNearlyZero) {
1500         return false;
1501     }
1502
1503     SkVector w1 = p - p1;
1504     if (n*v1.cross(w1) < SK_ScalarNearlyZero) {
1505         return false;
1506     }
1507
1508     SkVector v2 = p0 - p2;
1509     SkVector w2 = p - p2;
1510     if (n*v2.cross(w2) < SK_ScalarNearlyZero) {
1511         return false;
1512     }
1513
1514     return true;
1515 }
1516
1517 // Data structure to track reflex vertices and check whether any are inside a given triangle
1518 class ReflexHash {
1519 public:
1520     bool init(const SkRect& bounds, int vertexCount) {
1521         fBounds = bounds;
1522         fNumVerts = 0;
1523         SkScalar width = bounds.width();
1524         SkScalar height = bounds.height();
1525         if (!SkScalarIsFinite(width) || !SkScalarIsFinite(height)) {
1526             return false;
1527         }
1528
1529         // We want vertexCount grid cells, roughly distributed to match the bounds ratio
1530         SkScalar hCount = SkScalarSqrt(sk_ieee_float_divide(vertexCount*width, height));
1531         if (!SkScalarIsFinite(hCount)) {
1532             return false;
1533         }
1534         fHCount = std::max(std::min(SkScalarRoundToInt(hCount), vertexCount), 1);
1535         fVCount = vertexCount/fHCount;
1536         fGridConversion.set(sk_ieee_float_divide(fHCount - 0.001f, width),
1537                             sk_ieee_float_divide(fVCount - 0.001f, height));
1538         if (!fGridConversion.isFinite()) {
1539             return false;
1540         }
1541
1542         fGrid.setCount(fHCount*fVCount);
1543         for (int i = 0; i < fGrid.count(); ++i) {
1544             fGrid[i].reset();
1545         }
1546
1547         return true;
1548     }
1549
1550     void add(TriangulationVertex* v) {
1551         int index = hash(v);
1552         fGrid[index].addToTail(v);
1553         ++fNumVerts;
1554     }
1555
1556     void remove(TriangulationVertex* v) {
1557         int index = hash(v);
1558         fGrid[index].remove(v);
1559         --fNumVerts;
1560     }
1561
1562     bool checkTriangle(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
1563                        uint16_t ignoreIndex0, uint16_t ignoreIndex1) const {
1564         if (!fNumVerts) {
1565             return false;
1566         }
1567
1568         SkRect triBounds;
1569         compute_triangle_bounds(p0, p1, p2, &triBounds);
1570         int h0 = (triBounds.fLeft - fBounds.fLeft)*fGridConversion.fX;
1571         int h1 = (triBounds.fRight - fBounds.fLeft)*fGridConversion.fX;
1572         int v0 = (triBounds.fTop - fBounds.fTop)*fGridConversion.fY;
1573         int v1 = (triBounds.fBottom - fBounds.fTop)*fGridConversion.fY;
1574
1575         for (int v = v0; v <= v1; ++v) {
1576             for (int h = h0; h <= h1; ++h) {
1577                 int i = v * fHCount + h;
1578                 for (SkTInternalLList<TriangulationVertex>::Iter reflexIter = fGrid[i].begin();
1579                      reflexIter != fGrid[i].end(); ++reflexIter) {
1580                     TriangulationVertex* reflexVertex = *reflexIter;
1581                     if (reflexVertex->fIndex != ignoreIndex0 &&
1582                         reflexVertex->fIndex != ignoreIndex1 &&
1583                         point_in_triangle(p0, p1, p2, reflexVertex->fPosition)) {
1584                         return true;
1585                     }
1586                 }
1587
1588             }
1589         }
1590
1591         return false;
1592     }
1593
1594 private:
1595     int hash(TriangulationVertex* vert) const {
1596         int h = (vert->fPosition.fX - fBounds.fLeft)*fGridConversion.fX;
1597         int v = (vert->fPosition.fY - fBounds.fTop)*fGridConversion.fY;
1598         SkASSERT(v*fHCount + h >= 0);
1599         return v*fHCount + h;
1600     }
1601
1602     SkRect fBounds;
1603     int fHCount;
1604     int fVCount;
1605     int fNumVerts;
1606     // converts distance from the origin to a grid location (when cast to int)
1607     SkVector fGridConversion;
1608     SkTDArray<SkTInternalLList<TriangulationVertex>> fGrid;
1609 };
1610
1611 // Check to see if a reflex vertex has become a convex vertex after clipping an ear
1612 static void reclassify_vertex(TriangulationVertex* p, const SkPoint* polygonVerts,
1613                               int winding, ReflexHash* reflexHash,
1614                               SkTInternalLList<TriangulationVertex>* convexList) {
1615     if (TriangulationVertex::VertexType::kReflex == p->fVertexType) {
1616         SkVector v0 = p->fPosition - polygonVerts[p->fPrevIndex];
1617         SkVector v1 = polygonVerts[p->fNextIndex] - p->fPosition;
1618         if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
1619             p->fVertexType = TriangulationVertex::VertexType::kConvex;
1620             reflexHash->remove(p);
1621             p->fPrev = p->fNext = nullptr;
1622             convexList->addToTail(p);
1623         }
1624     }
1625 }
1626
1627 bool SkTriangulateSimplePolygon(const SkPoint* polygonVerts, uint16_t* indexMap, int polygonSize,
1628                                 SkTDArray<uint16_t>* triangleIndices) {
1629     if (polygonSize < 3) {
1630         return false;
1631     }
1632     // need to be able to represent all the vertices in the 16-bit indices
1633     if (polygonSize >= std::numeric_limits<uint16_t>::max()) {
1634         return false;
1635     }
1636
1637     // get bounds
1638     SkRect bounds;
1639     if (!bounds.setBoundsCheck(polygonVerts, polygonSize)) {
1640         return false;
1641     }
1642     // get winding direction
1643     // TODO: we do this for all the polygon routines -- might be better to have the client
1644     // compute it and pass it in
1645     int winding = SkGetPolygonWinding(polygonVerts, polygonSize);
1646     if (0 == winding) {
1647         return false;
1648     }
1649
1650     // Set up vertices
1651     SkAutoSTArray<64, TriangulationVertex> triangulationVertices(polygonSize);
1652     int prevIndex = polygonSize - 1;
1653     SkVector v0 = polygonVerts[0] - polygonVerts[prevIndex];
1654     for (int currIndex = 0; currIndex < polygonSize; ++currIndex) {
1655         int nextIndex = (currIndex + 1) % polygonSize;
1656
1657         triangulationVertices[currIndex] = TriangulationVertex{};
1658         triangulationVertices[currIndex].fPosition = polygonVerts[currIndex];
1659         triangulationVertices[currIndex].fIndex = currIndex;
1660         triangulationVertices[currIndex].fPrevIndex = prevIndex;
1661         triangulationVertices[currIndex].fNextIndex = nextIndex;
1662         SkVector v1 = polygonVerts[nextIndex] - polygonVerts[currIndex];
1663         if (winding*v0.cross(v1) > SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
1664             triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kConvex;
1665         } else {
1666             triangulationVertices[currIndex].fVertexType = TriangulationVertex::VertexType::kReflex;
1667         }
1668
1669         prevIndex = currIndex;
1670         v0 = v1;
1671     }
1672
1673     // Classify initial vertices into a list of convex vertices and a hash of reflex vertices
1674     // TODO: possibly sort the convexList in some way to get better triangles
1675     SkTInternalLList<TriangulationVertex> convexList;
1676     ReflexHash reflexHash;
1677     if (!reflexHash.init(bounds, polygonSize)) {
1678         return false;
1679     }
1680     prevIndex = polygonSize - 1;
1681     for (int currIndex = 0; currIndex < polygonSize; prevIndex = currIndex, ++currIndex) {
1682         TriangulationVertex::VertexType currType = triangulationVertices[currIndex].fVertexType;
1683         if (TriangulationVertex::VertexType::kConvex == currType) {
1684             int nextIndex = (currIndex + 1) % polygonSize;
1685             TriangulationVertex::VertexType prevType = triangulationVertices[prevIndex].fVertexType;
1686             TriangulationVertex::VertexType nextType = triangulationVertices[nextIndex].fVertexType;
1687             // We prioritize clipping vertices with neighboring reflex vertices.
1688             // The intent here is that it will cull reflex vertices more quickly.
1689             if (TriangulationVertex::VertexType::kReflex == prevType ||
1690                 TriangulationVertex::VertexType::kReflex == nextType) {
1691                 convexList.addToHead(&triangulationVertices[currIndex]);
1692             } else {
1693                 convexList.addToTail(&triangulationVertices[currIndex]);
1694             }
1695         } else {
1696             // We treat near collinear vertices as reflex
1697             reflexHash.add(&triangulationVertices[currIndex]);
1698         }
1699     }
1700
1701     // The general concept: We are trying to find three neighboring vertices where
1702     // no other vertex lies inside the triangle (an "ear"). If we find one, we clip
1703     // that ear off, and then repeat on the new polygon. Once we get down to three vertices
1704     // we have triangulated the entire polygon.
1705     // In the worst case this is an n^2 algorithm. We can cut down the search space somewhat by
1706     // noting that only convex vertices can be potential ears, and we only need to check whether
1707     // any reflex vertices lie inside the ear.
1708     triangleIndices->setReserve(triangleIndices->count() + 3 * (polygonSize - 2));
1709     int vertexCount = polygonSize;
1710     while (vertexCount > 3) {
1711         bool success = false;
1712         TriangulationVertex* earVertex = nullptr;
1713         TriangulationVertex* p0 = nullptr;
1714         TriangulationVertex* p2 = nullptr;
1715         // find a convex vertex to clip
1716         for (SkTInternalLList<TriangulationVertex>::Iter convexIter = convexList.begin();
1717              convexIter != convexList.end(); ++convexIter) {
1718             earVertex = *convexIter;
1719             SkASSERT(TriangulationVertex::VertexType::kReflex != earVertex->fVertexType);
1720
1721             p0 = &triangulationVertices[earVertex->fPrevIndex];
1722             p2 = &triangulationVertices[earVertex->fNextIndex];
1723
1724             // see if any reflex vertices are inside the ear
1725             bool failed = reflexHash.checkTriangle(p0->fPosition, earVertex->fPosition,
1726                                                    p2->fPosition, p0->fIndex, p2->fIndex);
1727             if (failed) {
1728                 continue;
1729             }
1730
1731             // found one we can clip
1732             success = true;
1733             break;
1734         }
1735         // If we can't find any ears to clip, this probably isn't a simple polygon
1736         if (!success) {
1737             return false;
1738         }
1739
1740         // add indices
1741         auto indices = triangleIndices->append(3);
1742         indices[0] = indexMap[p0->fIndex];
1743         indices[1] = indexMap[earVertex->fIndex];
1744         indices[2] = indexMap[p2->fIndex];
1745
1746         // clip the ear
1747         convexList.remove(earVertex);
1748         --vertexCount;
1749
1750         // reclassify reflex verts
1751         p0->fNextIndex = earVertex->fNextIndex;
1752         reclassify_vertex(p0, polygonVerts, winding, &reflexHash, &convexList);
1753
1754         p2->fPrevIndex = earVertex->fPrevIndex;
1755         reclassify_vertex(p2, polygonVerts, winding, &reflexHash, &convexList);
1756     }
1757
1758     // output indices
1759     for (SkTInternalLList<TriangulationVertex>::Iter vertexIter = convexList.begin();
1760          vertexIter != convexList.end(); ++vertexIter) {
1761         TriangulationVertex* vertex = *vertexIter;
1762         *triangleIndices->push() = indexMap[vertex->fIndex];
1763     }
1764
1765     return true;
1766 }
1767
1768 ///////////
1769
1770 static double crs(SkVector a, SkVector b) {
1771     return a.fX * b.fY - a.fY * b.fX;
1772 }
1773
1774 static int sign(SkScalar v) {
1775     return v < 0 ? -1 : (v > 0);
1776 }
1777
1778 struct SignTracker {
1779     int fSign;
1780     int fSignChanges;
1781
1782     void reset() {
1783         fSign = 0;
1784         fSignChanges = 0;
1785     }
1786
1787     void init(int s) {
1788         SkASSERT(fSignChanges == 0);
1789         SkASSERT(s == 1 || s == -1 || s == 0);
1790         fSign = s;
1791         fSignChanges = 1;
1792     }
1793
1794     void update(int s) {
1795         if (s) {
1796             if (fSign != s) {
1797                 fSignChanges += 1;
1798                 fSign = s;
1799             }
1800         }
1801     }
1802 };
1803
1804 struct ConvexTracker {
1805     SkVector    fFirst, fPrev;
1806     SignTracker fDSign, fCSign;
1807     int         fVecCounter;
1808     bool        fIsConcave;
1809
1810     ConvexTracker() { this->reset(); }
1811
1812     void reset() {
1813         fPrev = {0, 0};
1814         fDSign.reset();
1815         fCSign.reset();
1816         fVecCounter = 0;
1817         fIsConcave = false;
1818     }
1819
1820     void addVec(SkPoint p1, SkPoint p0) {
1821         this->addVec(p1 - p0);
1822     }
1823     void addVec(SkVector v) {
1824         if (v.fX == 0 && v.fY == 0) {
1825             return;
1826         }
1827
1828         fVecCounter += 1;
1829         if (fVecCounter == 1) {
1830             fFirst = fPrev = v;
1831             fDSign.update(sign(v.fX));
1832             return;
1833         }
1834
1835         SkScalar d = v.fX;
1836         SkScalar c = crs(fPrev, v);
1837         int sign_c;
1838         if (c) {
1839             sign_c = sign(c);
1840         } else {
1841             if (d >= 0) {
1842                 sign_c = fCSign.fSign;
1843             } else {
1844                 sign_c = -fCSign.fSign;
1845             }
1846         }
1847
1848         fDSign.update(sign(d));
1849         fCSign.update(sign_c);
1850         fPrev = v;
1851
1852         if (fDSign.fSignChanges > 3 || fCSign.fSignChanges > 1) {
1853             fIsConcave = true;
1854         }
1855     }
1856
1857     void finalCross() {
1858         this->addVec(fFirst);
1859     }
1860 };
1861
1862 bool SkIsPolyConvex_experimental(const SkPoint pts[], int count) {
1863     if (count <= 3) {
1864         return true;
1865     }
1866
1867     ConvexTracker tracker;
1868
1869     for (int i = 0; i < count - 1; ++i) {
1870         tracker.addVec(pts[i + 1], pts[i]);
1871         if (tracker.fIsConcave) {
1872             return false;
1873         }
1874     }
1875     tracker.addVec(pts[0], pts[count - 1]);
1876     tracker.finalCross();
1877     return !tracker.fIsConcave;
1878 }