src/gpu/GrTessellatingPathRenderer.cpp

   1 /*
   2  * Copyright 2015 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 "GrTessellatingPathRenderer.h"
   9
  10 #include "GrBatch.h"
  11 #include "GrBatchTarget.h"
  12 #include "GrDefaultGeoProcFactory.h"
  13 #include "GrPathUtils.h"
  14 #include "SkChunkAlloc.h"
  15 #include "SkGeometry.h"
  16
  17 #include <stdio.h>
  18
  19 /*
  20  * This path renderer tessellates the path into triangles, uploads the triangles to a
  21  * vertex buffer, and renders them with a single draw call. It does not currently do
  22  * antialiasing, so it must be used in conjunction with multisampling.
  23  *
  24  * There are six stages to the algorithm:
  25  *
  26  * 1) Linearize the path contours into piecewise linear segments (path_to_contours()).
  27  * 2) Build a mesh of edges connecting the vertices (build_edges()).
  28  * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()).
  29  * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplify()).
  30  * 5) Tessellate the simplified mesh into monotone polygons (tessellate()).
  31  * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_triangles()).
  32  *
  33  * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
  34  * of vertices (and the necessity of inserting new vertices on intersection).
  35  *
  36  * Stages (4) and (5) use an active edge list, which a list of all edges for which the
  37  * sweep line has crossed the top vertex, but not the bottom vertex.  It's sorted
  38  * left-to-right based on the point where both edges are active (when both top vertices
  39  * have been seen, so the "lower" top vertex of the two). If the top vertices are equal
  40  * (shared), it's sorted based on the last point where both edges are active, so the
  41  * "upper" bottom vertex.
  42  *
  43  * The most complex step is the simplification (4). It's based on the Bentley-Ottman
  44  * line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
  45  * not exact and may violate the mesh topology or active edge list ordering. We
  46  * accommodate this by adjusting the topology of the mesh and AEL to match the intersection
  47  * points. This occurs in three ways:
  48  *
  49  * A) Intersections may cause a shortened edge to no longer be ordered with respect to its
  50  *    neighbouring edges at the top or bottom vertex. This is handled by merging the
  51  *    edges (merge_collinear_edges()).
  52  * B) Intersections may cause an edge to violate the left-to-right ordering of the
  53  *    active edge list. This is handled by splitting the neighbour edge on the
  54  *    intersected vertex (cleanup_active_edges()).
  55  * C) Shortening an edge may cause an active edge to become inactive or an inactive edge
  56  *    to become active. This is handled by removing or inserting the edge in the active
  57  *    edge list (fix_active_state()).
  58  *
  59  * The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
  60  * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
  61  * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
  62  * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
  63  * become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
  64  * insertions and removals was greater than the cost of infrequent O(N) lookups with the
  65  * linked list implementation. With the latter, all removals are O(1), and most insertions
  66  * are O(1), since we know the adjacent edge in the active edge list based on the topology.
  67  * Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
  68  * frequent. There may be other data structures worth investigating, however.
  69  *
  70  * Note that there is a compile-time flag (SWEEP_IN_X) which changes the orientation of the
  71  * line sweep algorithms. When SWEEP_IN_X is unset, we sort vertices based on increasing
  72  * Y coordinate, and secondarily by increasing X coordinate. When SWEEP_IN_X is set, we sort by
  73  * increasing X coordinate, but secondarily by *decreasing* Y coordinate. This is so that the
  74  * "left" and "right" orientation in the code remains correct (edges to the left are increasing
  75  * in Y; edges to the right are decreasing in Y). That is, the setting rotates 90 degrees
  76  * counterclockwise, rather that transposing.
  77  *
  78  * The choice is arbitrary, but most test cases are wider than they are tall, so the
  79  * default is to sweep in X. In the future, we may want to make this a runtime parameter
  80  * and base it on the aspect ratio of the clip bounds.
  81  */
  82 #define LOGGING_ENABLED 0
  83 #define WIREFRAME 0
  84 #define SWEEP_IN_X 1
  85
  86 #if LOGGING_ENABLED
  87 #define LOG printf
  88 #else
  89 #define LOG(...)
  90 #endif
  91
  92 #define ALLOC_NEW(Type, args, alloc) \
  93     SkNEW_PLACEMENT_ARGS(alloc.allocThrow(sizeof(Type)), Type, args)
  94
  95 namespace {
  96
  97 struct Vertex;
  98 struct Edge;
  99 struct Poly;
 100
 101 template <class T, T* T::*Prev, T* T::*Next>
 102 void insert(T* t, T* prev, T* next, T** head, T** tail) {
 103     t->*Prev = prev;
 104     t->*Next = next;
 105     if (prev) {
 106         prev->*Next = t;
 107     } else if (head) {
 108         *head = t;
 109     }
 110     if (next) {
 111         next->*Prev = t;
 112     } else if (tail) {
 113         *tail = t;
 114     }
 115 }
 116
 117 template <class T, T* T::*Prev, T* T::*Next>
 118 void remove(T* t, T** head, T** tail) {
 119     if (t->*Prev) {
 120         t->*Prev->*Next = t->*Next;
 121     } else if (head) {
 122         *head = t->*Next;
 123     }
 124     if (t->*Next) {
 125         t->*Next->*Prev = t->*Prev;
 126     } else if (tail) {
 127         *tail = t->*Prev;
 128     }
 129     t->*Prev = t->*Next = NULL;
 130 }
 131
 132 /**
 133  * Vertices are used in three ways: first, the path contours are converted into a
 134  * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
 135  * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
 136  * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
 137  * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
 138  * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
 139  * an individual Vertex from the path mesh may belong to multiple
 140  * MonotonePolys, so the original Vertices cannot be re-used.
 141  */
 142
 143 struct Vertex {
 144   Vertex(const SkPoint& point)
 145     : fPoint(point), fPrev(NULL), fNext(NULL)
 146     , fFirstEdgeAbove(NULL), fLastEdgeAbove(NULL)
 147     , fFirstEdgeBelow(NULL), fLastEdgeBelow(NULL)
 148     , fProcessed(false)
 149 #if LOGGING_ENABLED
 150     , fID (-1.0f)
 151 #endif
 152     {}
 153     SkPoint fPoint;           // Vertex position
 154     Vertex* fPrev;            // Linked list of contours, then Y-sorted vertices.
 155     Vertex* fNext;            // "
 156     Edge*   fFirstEdgeAbove;  // Linked list of edges above this vertex.
 157     Edge*   fLastEdgeAbove;   // "
 158     Edge*   fFirstEdgeBelow;  // Linked list of edges below this vertex.
 159     Edge*   fLastEdgeBelow;   // "
 160     bool    fProcessed;       // Has this vertex been seen in simplify()?
 161 #if LOGGING_ENABLED
 162     float   fID;              // Identifier used for logging.
 163 #endif
 164 };
 165
 166 /***************************************************************************************/
 167
 168 bool sweep_lt(const SkPoint& a, const SkPoint& b) {
 169 #if SWEEP_IN_X
 170     return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX;
 171 #else
 172     return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY;
 173 #endif
 174 }
 175
 176 bool sweep_gt(const SkPoint& a, const SkPoint& b) {
 177 #if SWEEP_IN_X
 178     return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX;
 179 #else
 180     return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY;
 181 #endif
 182 }
 183
 184 inline void* emit_vertex(Vertex* v, void* data) {
 185     SkPoint* d = static_cast<SkPoint*>(data);
 186     *d++ = v->fPoint;
 187     return d;
 188 }
 189
 190 void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, void* data) {
 191 #if WIREFRAME
 192     data = emit_vertex(v0, data);
 193     data = emit_vertex(v1, data);
 194     data = emit_vertex(v1, data);
 195     data = emit_vertex(v2, data);
 196     data = emit_vertex(v2, data);
 197     data = emit_vertex(v0, data);
 198 #else
 199     data = emit_vertex(v0, data);
 200     data = emit_vertex(v1, data);
 201     data = emit_vertex(v2, data);
 202 #endif
 203     return data;
 204 }
 205
 206 /**
 207  * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
 208  * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
 209  * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
 210  * point). For speed, that case is only tested by the callers which require it (e.g.,
 211  * cleanup_active_edges()). Edges also handle checking for intersection with other edges.
 212  * Currently, this converts the edges to the parametric form, in order to avoid doing a division
 213  * until an intersection has been confirmed. This is slightly slower in the "found" case, but
 214  * a lot faster in the "not found" case.
 215  *
 216  * The coefficients of the line equation stored in double precision to avoid catastrphic
 217  * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
 218  * correct in float, since it's a polynomial of degree 2. The intersect() function, being
 219  * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
 220  * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
 221  * this file).
 222  */
 223
 224 struct Edge {
 225     Edge(Vertex* top, Vertex* bottom, int winding)
 226         : fWinding(winding)
 227         , fTop(top)
 228         , fBottom(bottom)
 229         , fLeft(NULL)
 230         , fRight(NULL)
 231         , fPrevEdgeAbove(NULL)
 232         , fNextEdgeAbove(NULL)
 233         , fPrevEdgeBelow(NULL)
 234         , fNextEdgeBelow(NULL)
 235         , fLeftPoly(NULL)
 236         , fRightPoly(NULL) {
 237             recompute();
 238         }
 239     int      fWinding;          // 1 == edge goes downward; -1 = edge goes upward.
 240     Vertex*  fTop;              // The top vertex in vertex-sort-order (sweep_lt).
 241     Vertex*  fBottom;           // The bottom vertex in vertex-sort-order.
 242     Edge*    fLeft;             // The linked list of edges in the active edge list.
 243     Edge*    fRight;            // "
 244     Edge*    fPrevEdgeAbove;    // The linked list of edges in the bottom Vertex's "edges above".
 245     Edge*    fNextEdgeAbove;    // "
 246     Edge*    fPrevEdgeBelow;    // The linked list of edges in the top Vertex's "edges below".
 247     Edge*    fNextEdgeBelow;    // "
 248     Poly*    fLeftPoly;         // The Poly to the left of this edge, if any.
 249     Poly*    fRightPoly;        // The Poly to the right of this edge, if any.
 250     double   fDX;               // The line equation for this edge, in implicit form.
 251     double   fDY;               // fDY * x + fDX * y + fC = 0, for point (x, y) on the line.
 252     double   fC;
 253     double dist(const SkPoint& p) const {
 254         return fDY * p.fX - fDX * p.fY + fC;
 255     }
 256     bool isRightOf(Vertex* v) const {
 257         return dist(v->fPoint) < 0.0;
 258     }
 259     bool isLeftOf(Vertex* v) const {
 260         return dist(v->fPoint) > 0.0;
 261     }
 262     void recompute() {
 263         fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX;
 264         fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY;
 265         fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX -
 266              static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY;
 267     }
 268     bool intersect(const Edge& other, SkPoint* p) {
 269         LOG("intersecting %g -> %g with %g -> %g\n",
 270                fTop->fID, fBottom->fID,
 271                other.fTop->fID, other.fBottom->fID);
 272         if (fTop == other.fTop || fBottom == other.fBottom) {
 273             return false;
 274         }
 275         double denom = fDX * other.fDY - fDY * other.fDX;
 276         if (denom == 0.0) {
 277             return false;
 278         }
 279         double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX;
 280         double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY;
 281         double sNumer = dy * other.fDX - dx * other.fDY;
 282         double tNumer = dy * fDX - dx * fDY;
 283         // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early.
 284         // This saves us doing the divide below unless absolutely necessary.
 285         if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
 286                         : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
 287             return false;
 288         }
 289         double s = sNumer / denom;
 290         SkASSERT(s >= 0.0 && s <= 1.0);
 291         p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX);
 292         p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY);
 293         return true;
 294     }
 295     bool isActive(Edge** activeEdges) const {
 296         return activeEdges && (fLeft || fRight || *activeEdges == this);
 297     }
 298 };
 299
 300 /***************************************************************************************/
 301
 302 struct Poly {
 303     Poly(int winding)
 304         : fWinding(winding)
 305         , fHead(NULL)
 306         , fTail(NULL)
 307         , fActive(NULL)
 308         , fNext(NULL)
 309         , fPartner(NULL)
 310         , fCount(0)
 311     {
 312 #if LOGGING_ENABLED
 313         static int gID = 0;
 314         fID = gID++;
 315         LOG("*** created Poly %d\n", fID);
 316 #endif
 317     }
 318     typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side;
 319     struct MonotonePoly {
 320         MonotonePoly()
 321             : fSide(kNeither_Side)
 322             , fHead(NULL)
 323             , fTail(NULL)
 324             , fPrev(NULL)
 325             , fNext(NULL) {}
 326         Side          fSide;
 327         Vertex*       fHead;
 328         Vertex*       fTail;
 329         MonotonePoly* fPrev;
 330         MonotonePoly* fNext;
 331         bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
 332             Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc);
 333             bool done = false;
 334             if (fSide == kNeither_Side) {
 335                 fSide = side;
 336             } else {
 337                 done = side != fSide;
 338             }
 339             if (fHead == NULL) {
 340                 fHead = fTail = newV;
 341             } else if (fSide == kRight_Side) {
 342                 newV->fPrev = fTail;
 343                 fTail->fNext = newV;
 344                 fTail = newV;
 345             } else {
 346                 newV->fNext = fHead;
 347                 fHead->fPrev = newV;
 348                 fHead = newV;
 349             }
 350             return done;
 351         }
 352
 353         void* emit(void* data) {
 354             Vertex* first = fHead;
 355             Vertex* v = first->fNext;
 356             while (v != fTail) {
 357                 SkASSERT(v && v->fPrev && v->fNext);
 358 #ifdef SK_DEBUG
 359                 validate();
 360 #endif
 361                 Vertex* prev = v->fPrev;
 362                 Vertex* curr = v;
 363                 Vertex* next = v->fNext;
 364                 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX;
 365                 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY;
 366                 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX;
 367                 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY;
 368                 if (ax * by - ay * bx >= 0.0) {
 369                     data = emit_triangle(prev, curr, next, data);
 370                     v->fPrev->fNext = v->fNext;
 371                     v->fNext->fPrev = v->fPrev;
 372                     if (v->fPrev == first) {
 373                         v = v->fNext;
 374                     } else {
 375                         v = v->fPrev;
 376                     }
 377                 } else {
 378                     v = v->fNext;
 379                     SkASSERT(v != fTail);
 380                 }
 381             }
 382             return data;
 383         }
 384
 385 #ifdef SK_DEBUG
 386         void validate() {
 387             int winding = sweep_lt(fHead->fPoint, fTail->fPoint) ? 1 : -1;
 388             Vertex* top = winding < 0 ? fTail : fHead;
 389             Vertex* bottom = winding < 0 ? fHead : fTail;
 390             Edge e(top, bottom, winding);
 391             for (Vertex* v = fHead->fNext; v != fTail; v = v->fNext) {
 392                 if (fSide == kRight_Side) {
 393                     SkASSERT(!e.isRightOf(v));
 394                 } else if (fSide == Poly::kLeft_Side) {
 395                     SkASSERT(!e.isLeftOf(v));
 396                 }
 397             }
 398         }
 399 #endif
 400     };
 401     Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
 402         LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoint.fX, v->fPoint.fY,
 403                side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "neither");
 404         Poly* partner = fPartner;
 405         Poly* poly = this;
 406         if (partner) {
 407             fPartner = partner->fPartner = NULL;
 408         }
 409         if (!fActive) {
 410             fActive = ALLOC_NEW(MonotonePoly, (), alloc);
 411         }
 412         if (fActive->addVertex(v, side, alloc)) {
 413 #ifdef SK_DEBUG
 414             fActive->validate();
 415 #endif
 416             if (fTail) {
 417                 fActive->fPrev = fTail;
 418                 fTail->fNext = fActive;
 419                 fTail = fActive;
 420             } else {
 421                 fHead = fTail = fActive;
 422             }
 423             if (partner) {
 424                 partner->addVertex(v, side, alloc);
 425                 poly = partner;
 426             } else {
 427                 Vertex* prev = fActive->fSide == Poly::kLeft_Side ?
 428                                fActive->fHead->fNext : fActive->fTail->fPrev;
 429                 fActive = ALLOC_NEW(MonotonePoly, , alloc);
 430                 fActive->addVertex(prev, Poly::kNeither_Side, alloc);
 431                 fActive->addVertex(v, side, alloc);
 432             }
 433         }
 434         fCount++;
 435         return poly;
 436     }
 437     void end(Vertex* v, SkChunkAlloc& alloc) {
 438         LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY);
 439         if (fPartner) {
 440             fPartner = fPartner->fPartner = NULL;
 441         }
 442         addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, alloc);
 443     }
 444     void* emit(void *data) {
 445         if (fCount < 3) {
 446             return data;
 447         }
 448         LOG("emit() %d, size %d\n", fID, fCount);
 449         for (MonotonePoly* m = fHead; m != NULL; m = m->fNext) {
 450             data = m->emit(data);
 451         }
 452         return data;
 453     }
 454     int fWinding;
 455     MonotonePoly* fHead;
 456     MonotonePoly* fTail;
 457     MonotonePoly* fActive;
 458     Poly* fNext;
 459     Poly* fPartner;
 460     int fCount;
 461 #if LOGGING_ENABLED
 462     int fID;
 463 #endif
 464 };
 465
 466 /***************************************************************************************/
 467
 468 bool coincident(const SkPoint& a, const SkPoint& b) {
 469     return a == b;
 470 }
 471
 472 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) {
 473     Poly* poly = ALLOC_NEW(Poly, (winding), alloc);
 474     poly->addVertex(v, Poly::kNeither_Side, alloc);
 475     poly->fNext = *head;
 476     *head = poly;
 477     return poly;
 478 }
 479
 480 #ifdef SK_DEBUG
 481 void validate_edges(Edge* head) {
 482     for (Edge* e = head; e != NULL; e = e->fRight) {
 483         SkASSERT(e->fTop != e->fBottom);
 484         if (e->fLeft) {
 485             SkASSERT(e->fLeft->fRight == e);
 486             if (sweep_gt(e->fTop->fPoint, e->fLeft->fTop->fPoint)) {
 487                 SkASSERT(e->fLeft->isLeftOf(e->fTop));
 488             }
 489             if (sweep_lt(e->fBottom->fPoint, e->fLeft->fBottom->fPoint)) {
 490                 SkASSERT(e->fLeft->isLeftOf(e->fBottom));
 491             }
 492         } else {
 493             SkASSERT(e == head);
 494         }
 495         if (e->fRight) {
 496             SkASSERT(e->fRight->fLeft == e);
 497             if (sweep_gt(e->fTop->fPoint, e->fRight->fTop->fPoint)) {
 498                 SkASSERT(e->fRight->isRightOf(e->fTop));
 499             }
 500             if (sweep_lt(e->fBottom->fPoint, e->fRight->fBottom->fPoint)) {
 501                 SkASSERT(e->fRight->isRightOf(e->fBottom));
 502             }
 503         }
 504     }
 505 }
 506
 507 void validate_connectivity(Vertex* v) {
 508     for (Edge* e = v->fFirstEdgeAbove; e != NULL; e = e->fNextEdgeAbove) {
 509         SkASSERT(e->fBottom == v);
 510         if (e->fPrevEdgeAbove) {
 511             SkASSERT(e->fPrevEdgeAbove->fNextEdgeAbove == e);
 512             SkASSERT(e->fPrevEdgeAbove->isLeftOf(e->fTop));
 513         } else {
 514             SkASSERT(e == v->fFirstEdgeAbove);
 515         }
 516         if (e->fNextEdgeAbove) {
 517             SkASSERT(e->fNextEdgeAbove->fPrevEdgeAbove == e);
 518             SkASSERT(e->fNextEdgeAbove->isRightOf(e->fTop));
 519         } else {
 520             SkASSERT(e == v->fLastEdgeAbove);
 521         }
 522     }
 523     for (Edge* e = v->fFirstEdgeBelow; e != NULL; e = e->fNextEdgeBelow) {
 524         SkASSERT(e->fTop == v);
 525         if (e->fPrevEdgeBelow) {
 526             SkASSERT(e->fPrevEdgeBelow->fNextEdgeBelow == e);
 527             SkASSERT(e->fPrevEdgeBelow->isLeftOf(e->fBottom));
 528         } else {
 529             SkASSERT(e == v->fFirstEdgeBelow);
 530         }
 531         if (e->fNextEdgeBelow) {
 532             SkASSERT(e->fNextEdgeBelow->fPrevEdgeBelow == e);
 533             SkASSERT(e->fNextEdgeBelow->isRightOf(e->fBottom));
 534         } else {
 535             SkASSERT(e == v->fLastEdgeBelow);
 536         }
 537     }
 538 }
 539 #endif
 540
 541 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head,
 542                                 SkChunkAlloc& alloc) {
 543     Vertex* v = ALLOC_NEW(Vertex, (p), alloc);
 544 #if LOGGING_ENABLED
 545     static float gID = 0.0f;
 546     v->fID = gID++;
 547 #endif
 548     if (prev) {
 549         prev->fNext = v;
 550         v->fPrev = prev;
 551     } else {
 552         *head = v;
 553     }
 554     return v;
 555 }
 556
 557 Vertex* generate_quadratic_points(const SkPoint& p0,
 558                                   const SkPoint& p1,
 559                                   const SkPoint& p2,
 560                                   SkScalar tolSqd,
 561                                   Vertex* prev,
 562                                   Vertex** head,
 563                                   int pointsLeft,
 564                                   SkChunkAlloc& alloc) {
 565     SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2);
 566     if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) {
 567         return append_point_to_contour(p2, prev, head, alloc);
 568     }
 569
 570     const SkPoint q[] = {
 571         { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
 572         { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
 573     };
 574     const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) };
 575
 576     pointsLeft >>= 1;
 577     prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, pointsLeft, alloc);
 578     prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, pointsLeft, alloc);
 579     return prev;
 580 }
 581
 582 Vertex* generate_cubic_points(const SkPoint& p0,
 583                               const SkPoint& p1,
 584                               const SkPoint& p2,
 585                               const SkPoint& p3,
 586                               SkScalar tolSqd,
 587                               Vertex* prev,
 588                               Vertex** head,
 589                               int pointsLeft,
 590                               SkChunkAlloc& alloc) {
 591     SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3);
 592     SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3);
 593     if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) ||
 594         !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) {
 595         return append_point_to_contour(p3, prev, head, alloc);
 596     }
 597     const SkPoint q[] = {
 598         { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
 599         { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
 600         { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
 601     };
 602     const SkPoint r[] = {
 603         { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
 604         { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
 605     };
 606     const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
 607     pointsLeft >>= 1;
 608     prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, pointsLeft, alloc);
 609     prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, pointsLeft, alloc);
 610     return prev;
 611 }
 612
 613 // Stage 1: convert the input path to a set of linear contours (linked list of Vertices).
 614
 615 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
 616                       Vertex** contours, SkChunkAlloc& alloc) {
 617
 618     SkScalar toleranceSqd = tolerance * tolerance;
 619
 620     SkPoint pts[4];
 621     bool done = false;
 622     SkPath::Iter iter(path, false);
 623     Vertex* prev = NULL;
 624     Vertex* head = NULL;
 625     if (path.isInverseFillType()) {
 626         SkPoint quad[4];
 627         clipBounds.toQuad(quad);
 628         for (int i = 3; i >= 0; i--) {
 629             prev = append_point_to_contour(quad[i], prev, &head, alloc);
 630         }
 631         head->fPrev = prev;
 632         prev->fNext = head;
 633         *contours++ = head;
 634         head = prev = NULL;
 635     }
 636     SkAutoConicToQuads converter;
 637     while (!done) {
 638         SkPath::Verb verb = iter.next(pts);
 639         switch (verb) {
 640             case SkPath::kConic_Verb: {
 641                 SkScalar weight = iter.conicWeight();
 642                 const SkPoint* quadPts = converter.computeQuads(pts, weight, toleranceSqd);
 643                 for (int i = 0; i < converter.countQuads(); ++i) {
 644                     int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, toleranceSqd);
 645                     prev = generate_quadratic_points(quadPts[0], quadPts[1], quadPts[2],
 646                                                      toleranceSqd, prev, &head, pointsLeft, alloc);
 647                     quadPts += 2;
 648                 }
 649                 break;
 650             }
 651             case SkPath::kMove_Verb:
 652                 if (head) {
 653                     head->fPrev = prev;
 654                     prev->fNext = head;
 655                     *contours++ = head;
 656                 }
 657                 head = prev = NULL;
 658                 prev = append_point_to_contour(pts[0], prev, &head, alloc);
 659                 break;
 660             case SkPath::kLine_Verb: {
 661                 prev = append_point_to_contour(pts[1], prev, &head, alloc);
 662                 break;
 663             }
 664             case SkPath::kQuad_Verb: {
 665                 int pointsLeft = GrPathUtils::quadraticPointCount(pts, toleranceSqd);
 666                 prev = generate_quadratic_points(pts[0], pts[1], pts[2], toleranceSqd, prev,
 667                                                  &head, pointsLeft, alloc);
 668                 break;
 669             }
 670             case SkPath::kCubic_Verb: {
 671                 int pointsLeft = GrPathUtils::cubicPointCount(pts, toleranceSqd);
 672                 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3],
 673                                 toleranceSqd, prev, &head, pointsLeft, alloc);
 674                 break;
 675             }
 676             case SkPath::kClose_Verb:
 677                 if (head) {
 678                     head->fPrev = prev;
 679                     prev->fNext = head;
 680                     *contours++ = head;
 681                 }
 682                 head = prev = NULL;
 683                 break;
 684             case SkPath::kDone_Verb:
 685                 if (head) {
 686                     head->fPrev = prev;
 687                     prev->fNext = head;
 688                     *contours++ = head;
 689                 }
 690                 done = true;
 691                 break;
 692         }
 693     }
 694 }
 695
 696 inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
 697     switch (fillType) {
 698         case SkPath::kWinding_FillType:
 699             return winding != 0;
 700         case SkPath::kEvenOdd_FillType:
 701             return (winding & 1) != 0;
 702         case SkPath::kInverseWinding_FillType:
 703             return winding == 1;
 704         case SkPath::kInverseEvenOdd_FillType:
 705             return (winding & 1) == 1;
 706         default:
 707             SkASSERT(false);
 708             return false;
 709     }
 710 }
 711
 712 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc) {
 713     int winding = sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
 714     Vertex* top = winding < 0 ? next : prev;
 715     Vertex* bottom = winding < 0 ? prev : next;
 716     return ALLOC_NEW(Edge, (top, bottom, winding), alloc);
 717 }
 718
 719 void remove_edge(Edge* edge, Edge** head) {
 720     LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
 721     SkASSERT(edge->isActive(head));
 722     remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, head, NULL);
 723 }
 724
 725 void insert_edge(Edge* edge, Edge* prev, Edge** head) {
 726     LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
 727     SkASSERT(!edge->isActive(head));
 728     Edge* next = prev ? prev->fRight : *head;
 729     insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, head, NULL);
 730 }
 731
 732 void find_enclosing_edges(Vertex* v, Edge* head, Edge** left, Edge** right) {
 733     if (v->fFirstEdgeAbove) {
 734         *left = v->fFirstEdgeAbove->fLeft;
 735         *right = v->fLastEdgeAbove->fRight;
 736         return;
 737     }
 738     Edge* prev = NULL;
 739     Edge* next;
 740     for (next = head; next != NULL; next = next->fRight) {
 741         if (next->isRightOf(v)) {
 742             break;
 743         }
 744         prev = next;
 745     }
 746     *left = prev;
 747     *right = next;
 748     return;
 749 }
 750
 751 void find_enclosing_edges(Edge* edge, Edge* head, Edge** left, Edge** right) {
 752     Edge* prev = NULL;
 753     Edge* next;
 754     for (next = head; next != NULL; next = next->fRight) {
 755         if ((sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
 756             (sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||
 757             (sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
 758              next->isRightOf(edge->fBottom)) ||
 759             (sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
 760              edge->isLeftOf(next->fBottom))) {
 761             break;
 762         }
 763         prev = next;
 764     }
 765     *left = prev;
 766     *right = next;
 767     return;
 768 }
 769
 770 void fix_active_state(Edge* edge, Edge** activeEdges) {
 771     if (edge->isActive(activeEdges)) {
 772         if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
 773             remove_edge(edge, activeEdges);
 774         }
 775     } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
 776         Edge* left;
 777         Edge* right;
 778         find_enclosing_edges(edge, *activeEdges, &left, &right);
 779         insert_edge(edge, left, activeEdges);
 780     }
 781 }
 782
 783 void insert_edge_above(Edge* edge, Vertex* v) {
 784     if (edge->fTop->fPoint == edge->fBottom->fPoint ||
 785         sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
 786         SkASSERT(false);
 787         return;
 788     }
 789     LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
 790     Edge* prev = NULL;
 791     Edge* next;
 792     for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
 793         if (next->isRightOf(edge->fTop)) {
 794             break;
 795         }
 796         prev = next;
 797     }
 798     insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
 799         edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
 800 }
 801
 802 void insert_edge_below(Edge* edge, Vertex* v) {
 803     if (edge->fTop->fPoint == edge->fBottom->fPoint ||
 804         sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) {
 805         SkASSERT(false);
 806         return;
 807     }
 808     LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
 809     Edge* prev = NULL;
 810     Edge* next;
 811     for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
 812         if (next->isRightOf(edge->fBottom)) {
 813             break;
 814         }
 815         prev = next;
 816     }
 817     insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
 818         edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
 819 }
 820
 821 void remove_edge_above(Edge* edge) {
 822     LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
 823         edge->fBottom->fID);
 824     remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
 825         edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
 826 }
 827
 828 void remove_edge_below(Edge* edge) {
 829     LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
 830         edge->fTop->fID);
 831     remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
 832         edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
 833 }
 834
 835 void erase_edge_if_zero_winding(Edge* edge, Edge** head) {
 836     if (edge->fWinding != 0) {
 837         return;
 838     }
 839     LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
 840     remove_edge_above(edge);
 841     remove_edge_below(edge);
 842     if (edge->isActive(head)) {
 843         remove_edge(edge, head);
 844     }
 845 }
 846
 847 void merge_collinear_edges(Edge* edge, Edge** activeEdges);
 848
 849 void set_top(Edge* edge, Vertex* v, Edge** activeEdges) {
 850     remove_edge_below(edge);
 851     edge->fTop = v;
 852     edge->recompute();
 853     insert_edge_below(edge, v);
 854     fix_active_state(edge, activeEdges);
 855     merge_collinear_edges(edge, activeEdges);
 856 }
 857
 858 void set_bottom(Edge* edge, Vertex* v, Edge** activeEdges) {
 859     remove_edge_above(edge);
 860     edge->fBottom = v;
 861     edge->recompute();
 862     insert_edge_above(edge, v);
 863     fix_active_state(edge, activeEdges);
 864     merge_collinear_edges(edge, activeEdges);
 865 }
 866
 867 void merge_edges_above(Edge* edge, Edge* other, Edge** activeEdges) {
 868     if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
 869         LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
 870             edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
 871             edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
 872         other->fWinding += edge->fWinding;
 873         erase_edge_if_zero_winding(other, activeEdges);
 874         edge->fWinding = 0;
 875         erase_edge_if_zero_winding(edge, activeEdges);
 876     } else if (sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
 877         other->fWinding += edge->fWinding;
 878         erase_edge_if_zero_winding(other, activeEdges);
 879         set_bottom(edge, other->fTop, activeEdges);
 880     } else {
 881         edge->fWinding += other->fWinding;
 882         erase_edge_if_zero_winding(edge, activeEdges);
 883         set_bottom(other, edge->fTop, activeEdges);
 884     }
 885 }
 886
 887 void merge_edges_below(Edge* edge, Edge* other, Edge** activeEdges) {
 888     if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
 889         LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
 890             edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
 891             edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
 892         other->fWinding += edge->fWinding;
 893         erase_edge_if_zero_winding(other, activeEdges);
 894         edge->fWinding = 0;
 895         erase_edge_if_zero_winding(edge, activeEdges);
 896     } else if (sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
 897         edge->fWinding += other->fWinding;
 898         erase_edge_if_zero_winding(edge, activeEdges);
 899         set_top(other, edge->fBottom, activeEdges);
 900     } else {
 901         other->fWinding += edge->fWinding;
 902         erase_edge_if_zero_winding(other, activeEdges);
 903         set_top(edge, other->fBottom, activeEdges);
 904     }
 905 }
 906
 907 void merge_collinear_edges(Edge* edge, Edge** activeEdges) {
 908     if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
 909                                  !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
 910         merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges);
 911     } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
 912                                         !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
 913         merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges);
 914     }
 915     if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
 916                                  !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
 917         merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges);
 918     } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||
 919                                         !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {
 920         merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges);
 921     }
 922 }
 923
 924 void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc);
 925
 926 void cleanup_active_edges(Edge* edge, Edge** activeEdges, SkChunkAlloc& alloc) {
 927     Vertex* top = edge->fTop;
 928     Vertex* bottom = edge->fBottom;
 929     if (edge->fLeft) {
 930         Vertex* leftTop = edge->fLeft->fTop;
 931         Vertex* leftBottom = edge->fLeft->fBottom;
 932         if (sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(top)) {
 933             split_edge(edge->fLeft, edge->fTop, activeEdges, alloc);
 934         } else if (sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf(leftTop)) {
 935             split_edge(edge, leftTop, activeEdges, alloc);
 936         } else if (sweep_lt(bottom->fPoint, leftBottom->fPoint) && !edge->fLeft->isLeftOf(bottom)) {
 937             split_edge(edge->fLeft, bottom, activeEdges, alloc);
 938         } else if (sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
 939             split_edge(edge, leftBottom, activeEdges, alloc);
 940         }
 941     }
 942     if (edge->fRight) {
 943         Vertex* rightTop = edge->fRight->fTop;
 944         Vertex* rightBottom = edge->fRight->fBottom;
 945         if (sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightOf(top)) {
 946             split_edge(edge->fRight, top, activeEdges, alloc);
 947         } else if (sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf(rightTop)) {
 948             split_edge(edge, rightTop, activeEdges, alloc);
 949         } else if (sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
 950                    !edge->fRight->isRightOf(bottom)) {
 951             split_edge(edge->fRight, bottom, activeEdges, alloc);
 952         } else if (sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
 953                    !edge->isLeftOf(rightBottom)) {
 954             split_edge(edge, rightBottom, activeEdges, alloc);
 955         }
 956     }
 957 }
 958
 959 void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc) {
 960     LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
 961         edge->fTop->fID, edge->fBottom->fID,
 962         v->fID, v->fPoint.fX, v->fPoint.fY);
 963     if (sweep_lt(v->fPoint, edge->fTop->fPoint)) {
 964         set_top(edge, v, activeEdges);
 965     } else if (sweep_gt(v->fPoint, edge->fBottom->fPoint)) {
 966         set_bottom(edge, v, activeEdges);
 967     } else {
 968         Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc);
 969         insert_edge_below(newEdge, v);
 970         insert_edge_above(newEdge, edge->fBottom);
 971         set_bottom(edge, v, activeEdges);
 972         cleanup_active_edges(edge, activeEdges, alloc);
 973         fix_active_state(newEdge, activeEdges);
 974         merge_collinear_edges(newEdge, activeEdges);
 975     }
 976 }
 977
 978 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, SkChunkAlloc& alloc) {
 979     LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX, src->fPoint.fY,
 980         src->fID, dst->fID);
 981     for (Edge* edge = src->fFirstEdgeAbove; edge;) {
 982         Edge* next = edge->fNextEdgeAbove;
 983         set_bottom(edge, dst, NULL);
 984         edge = next;
 985     }
 986     for (Edge* edge = src->fFirstEdgeBelow; edge;) {
 987         Edge* next = edge->fNextEdgeBelow;
 988         set_top(edge, dst, NULL);
 989         edge = next;
 990     }
 991     remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, NULL);
 992 }
 993
 994 Vertex* check_for_intersection(Edge* edge, Edge* other, Edge** activeEdges, SkChunkAlloc& alloc) {
 995     SkPoint p;
 996     if (!edge || !other) {
 997         return NULL;
 998     }
 999     if (edge->intersect(*other, &p)) {
1000         Vertex* v;
1001         LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
1002         if (p == edge->fTop->fPoint || sweep_lt(p, edge->fTop->fPoint)) {
1003             split_edge(other, edge->fTop, activeEdges, alloc);
1004             v = edge->fTop;
1005         } else if (p == edge->fBottom->fPoint || sweep_gt(p, edge->fBottom->fPoint)) {
1006             split_edge(other, edge->fBottom, activeEdges, alloc);
1007             v = edge->fBottom;
1008         } else if (p == other->fTop->fPoint || sweep_lt(p, other->fTop->fPoint)) {
1009             split_edge(edge, other->fTop, activeEdges, alloc);
1010             v = other->fTop;
1011         } else if (p == other->fBottom->fPoint || sweep_gt(p, other->fBottom->fPoint)) {
1012             split_edge(edge, other->fBottom, activeEdges, alloc);
1013             v = other->fBottom;
1014         } else {
1015             Vertex* nextV = edge->fTop;
1016             while (sweep_lt(p, nextV->fPoint)) {
1017                 nextV = nextV->fPrev;
1018             }
1019             while (sweep_lt(nextV->fPoint, p)) {
1020                 nextV = nextV->fNext;
1021             }
1022             Vertex* prevV = nextV->fPrev;
1023             if (coincident(prevV->fPoint, p)) {
1024                 v = prevV;
1025             } else if (coincident(nextV->fPoint, p)) {
1026                 v = nextV;
1027             } else {
1028                 v = ALLOC_NEW(Vertex, (p), alloc);
1029                 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n",
1030                     prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY,
1031                     nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY);
1032 #if LOGGING_ENABLED
1033                 v->fID = (nextV->fID + prevV->fID) * 0.5f;
1034 #endif
1035                 v->fPrev = prevV;
1036                 v->fNext = nextV;
1037                 prevV->fNext = v;
1038                 nextV->fPrev = v;
1039             }
1040             split_edge(edge, v, activeEdges, alloc);
1041             split_edge(other, v, activeEdges, alloc);
1042         }
1043 #ifdef SK_DEBUG
1044         validate_connectivity(v);
1045 #endif
1046         return v;
1047     }
1048     return NULL;
1049 }
1050
1051 void sanitize_contours(Vertex** contours, int contourCnt) {
1052     for (int i = 0; i < contourCnt; ++i) {
1053         SkASSERT(contours[i]);
1054         for (Vertex* v = contours[i];;) {
1055             if (coincident(v->fPrev->fPoint, v->fPoint)) {
1056                 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY);
1057                 if (v->fPrev == v) {
1058                     contours[i] = NULL;
1059                     break;
1060                 }
1061                 v->fPrev->fNext = v->fNext;
1062                 v->fNext->fPrev = v->fPrev;
1063                 if (contours[i] == v) {
1064                     contours[i] = v->fNext;
1065                 }
1066                 v = v->fPrev;
1067             } else {
1068                 v = v->fNext;
1069                 if (v == contours[i]) break;
1070             }
1071         }
1072     }
1073 }
1074
1075 void merge_coincident_vertices(Vertex** vertices, SkChunkAlloc& alloc) {
1076     for (Vertex* v = (*vertices)->fNext; v != NULL; v = v->fNext) {
1077         if (sweep_lt(v->fPoint, v->fPrev->fPoint)) {
1078             v->fPoint = v->fPrev->fPoint;
1079         }
1080         if (coincident(v->fPrev->fPoint, v->fPoint)) {
1081             merge_vertices(v->fPrev, v, vertices, alloc);
1082         }
1083     }
1084 }
1085
1086 // Stage 2: convert the contours to a mesh of edges connecting the vertices.
1087
1088 Vertex* build_edges(Vertex** contours, int contourCnt, SkChunkAlloc& alloc) {
1089     Vertex* vertices = NULL;
1090     Vertex* prev = NULL;
1091     for (int i = 0; i < contourCnt; ++i) {
1092         for (Vertex* v = contours[i]; v != NULL;) {
1093             Vertex* vNext = v->fNext;
1094             Edge* edge = new_edge(v->fPrev, v, alloc);
1095             if (edge->fWinding > 0) {
1096                 insert_edge_below(edge, v->fPrev);
1097                 insert_edge_above(edge, v);
1098             } else {
1099                 insert_edge_below(edge, v);
1100                 insert_edge_above(edge, v->fPrev);
1101             }
1102             merge_collinear_edges(edge, NULL);
1103             if (prev) {
1104                 prev->fNext = v;
1105                 v->fPrev = prev;
1106             } else {
1107                 vertices = v;
1108             }
1109             prev = v;
1110             v = vNext;
1111             if (v == contours[i]) break;
1112         }
1113     }
1114     if (prev) {
1115         prev->fNext = vertices->fPrev = NULL;
1116     }
1117     return vertices;
1118 }
1119
1120 // Stage 3: sort the vertices by increasing Y (or X if SWEEP_IN_X is on).
1121
1122 Vertex* sorted_merge(Vertex* a, Vertex* b);
1123
1124 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) {
1125     Vertex* fast;
1126     Vertex* slow;
1127     if (!v || !v->fNext) {
1128         *pFront = v;
1129         *pBack = NULL;
1130     } else {
1131         slow = v;
1132         fast = v->fNext;
1133
1134         while (fast != NULL) {
1135             fast = fast->fNext;
1136             if (fast != NULL) {
1137                 slow = slow->fNext;
1138                 fast = fast->fNext;
1139             }
1140         }
1141
1142         *pFront = v;
1143         *pBack = slow->fNext;
1144         slow->fNext->fPrev = NULL;
1145         slow->fNext = NULL;
1146     }
1147 }
1148
1149 void merge_sort(Vertex** head) {
1150     if (!*head || !(*head)->fNext) {
1151         return;
1152     }
1153
1154     Vertex* a;
1155     Vertex* b;
1156     front_back_split(*head, &a, &b);
1157
1158     merge_sort(&a);
1159     merge_sort(&b);
1160
1161     *head = sorted_merge(a, b);
1162 }
1163
1164 Vertex* sorted_merge(Vertex* a, Vertex* b) {
1165     if (!a) {
1166         return b;
1167     } else if (!b) {
1168         return a;
1169     }
1170
1171     Vertex* result = NULL;
1172
1173     if (sweep_lt(a->fPoint, b->fPoint)) {
1174         result = a;
1175         result->fNext = sorted_merge(a->fNext, b);
1176     } else {
1177         result = b;
1178         result->fNext = sorted_merge(a, b->fNext);
1179     }
1180     result->fNext->fPrev = result;
1181     return result;
1182 }
1183
1184 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
1185
1186 void simplify(Vertex* vertices, SkChunkAlloc& alloc) {
1187     LOG("simplifying complex polygons\n");
1188     Edge* activeEdges = NULL;
1189     for (Vertex* v = vertices; v != NULL; v = v->fNext) {
1190         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1191             continue;
1192         }
1193 #if LOGGING_ENABLED
1194         LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1195 #endif
1196 #ifdef SK_DEBUG
1197         validate_connectivity(v);
1198 #endif
1199         Edge* leftEnclosingEdge = NULL;
1200         Edge* rightEnclosingEdge = NULL;
1201         bool restartChecks;
1202         do {
1203             restartChecks = false;
1204             find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
1205             if (v->fFirstEdgeBelow) {
1206                 for (Edge* edge = v->fFirstEdgeBelow; edge != NULL; edge = edge->fNextEdgeBelow) {
1207                     if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, alloc)) {
1208                         restartChecks = true;
1209                         break;
1210                     }
1211                     if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, alloc)) {
1212                         restartChecks = true;
1213                         break;
1214                     }
1215                 }
1216             } else {
1217                 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
1218                                                         &activeEdges, alloc)) {
1219                     if (sweep_lt(pv->fPoint, v->fPoint)) {
1220                         v = pv;
1221                     }
1222                     restartChecks = true;
1223                 }
1224
1225             }
1226         } while (restartChecks);
1227         SkASSERT(!leftEnclosingEdge || leftEnclosingEdge->isLeftOf(v));
1228         SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v));
1229 #ifdef SK_DEBUG
1230         validate_edges(activeEdges);
1231 #endif
1232         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1233             remove_edge(e, &activeEdges);
1234         }
1235         Edge* leftEdge = leftEnclosingEdge;
1236         for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1237             insert_edge(e, leftEdge, &activeEdges);
1238             leftEdge = e;
1239         }
1240         v->fProcessed = true;
1241     }
1242 }
1243
1244 // Stage 5: Tessellate the simplified mesh into monotone polygons.
1245
1246 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
1247     LOG("tessellating simple polygons\n");
1248     Edge* activeEdges = NULL;
1249     Poly* polys = NULL;
1250     for (Vertex* v = vertices; v != NULL; v = v->fNext) {
1251         if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
1252             continue;
1253         }
1254 #if LOGGING_ENABLED
1255         LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
1256 #endif
1257 #ifdef SK_DEBUG
1258         validate_connectivity(v);
1259 #endif
1260         Edge* leftEnclosingEdge = NULL;
1261         Edge* rightEnclosingEdge = NULL;
1262         find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
1263         SkASSERT(!leftEnclosingEdge || leftEnclosingEdge->isLeftOf(v));
1264         SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v));
1265 #ifdef SK_DEBUG
1266         validate_edges(activeEdges);
1267 #endif
1268         Poly* leftPoly = NULL;
1269         Poly* rightPoly = NULL;
1270         if (v->fFirstEdgeAbove) {
1271             leftPoly = v->fFirstEdgeAbove->fLeftPoly;
1272             rightPoly = v->fLastEdgeAbove->fRightPoly;
1273         } else {
1274             leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : NULL;
1275             rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : NULL;
1276         }
1277 #if LOGGING_ENABLED
1278         LOG("edges above:\n");
1279         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1280             LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1281                 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
1282         }
1283         LOG("edges below:\n");
1284         for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1285             LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1286                 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
1287         }
1288 #endif
1289         if (v->fFirstEdgeAbove) {
1290             if (leftPoly) {
1291                 leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1292             }
1293             if (rightPoly) {
1294                 rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1295             }
1296             for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
1297                 Edge* leftEdge = e;
1298                 Edge* rightEdge = e->fNextEdgeAbove;
1299                 SkASSERT(rightEdge->isRightOf(leftEdge->fTop));
1300                 remove_edge(leftEdge, &activeEdges);
1301                 if (leftEdge->fRightPoly) {
1302                     leftEdge->fRightPoly->end(v, alloc);
1303                 }
1304                 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fRightPoly) {
1305                     rightEdge->fLeftPoly->end(v, alloc);
1306                 }
1307             }
1308             remove_edge(v->fLastEdgeAbove, &activeEdges);
1309             if (!v->fFirstEdgeBelow) {
1310                 if (leftPoly && rightPoly && leftPoly != rightPoly) {
1311                     SkASSERT(leftPoly->fPartner == NULL && rightPoly->fPartner == NULL);
1312                     rightPoly->fPartner = leftPoly;
1313                     leftPoly->fPartner = rightPoly;
1314                 }
1315             }
1316         }
1317         if (v->fFirstEdgeBelow) {
1318             if (!v->fFirstEdgeAbove) {
1319                 if (leftPoly && leftPoly == rightPoly) {
1320                     // Split the poly.
1321                     if (leftPoly->fActive->fSide == Poly::kLeft_Side) {
1322                         leftPoly = new_poly(&polys, leftEnclosingEdge->fTop, leftPoly->fWinding,
1323                                             alloc);
1324                         leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1325                         rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1326                         leftEnclosingEdge->fRightPoly = leftPoly;
1327                     } else {
1328                         rightPoly = new_poly(&polys, rightEnclosingEdge->fTop, rightPoly->fWinding,
1329                                              alloc);
1330                         rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1331                         leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1332                         rightEnclosingEdge->fLeftPoly = rightPoly;
1333                     }
1334                 } else {
1335                     if (leftPoly) {
1336                         leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, alloc);
1337                     }
1338                     if (rightPoly) {
1339                         rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
1340                     }
1341                 }
1342             }
1343             Edge* leftEdge = v->fFirstEdgeBelow;
1344             leftEdge->fLeftPoly = leftPoly;
1345             insert_edge(leftEdge, leftEnclosingEdge, &activeEdges);
1346             for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
1347                  rightEdge = rightEdge->fNextEdgeBelow) {
1348                 insert_edge(rightEdge, leftEdge, &activeEdges);
1349                 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWinding : 0;
1350                 winding += leftEdge->fWinding;
1351                 if (winding != 0) {
1352                     Poly* poly = new_poly(&polys, v, winding, alloc);
1353                     leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
1354                 }
1355                 leftEdge = rightEdge;
1356             }
1357             v->fLastEdgeBelow->fRightPoly = rightPoly;
1358         }
1359 #ifdef SK_DEBUG
1360         validate_edges(activeEdges);
1361 #endif
1362 #if LOGGING_ENABLED
1363         LOG("\nactive edges:\n");
1364         for (Edge* e = activeEdges; e != NULL; e = e->fRight) {
1365             LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1366                 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
1367         }
1368 #endif
1369     }
1370     return polys;
1371 }
1372
1373 // This is a driver function which calls stages 2-5 in turn.
1374
1375 Poly* contours_to_polys(Vertex** contours, int contourCnt, SkChunkAlloc& alloc) {
1376 #if LOGGING_ENABLED
1377     for (int i = 0; i < contourCnt; ++i) {
1378         Vertex* v = contours[i];
1379         SkASSERT(v);
1380         LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1381         for (v = v->fNext; v != contours[i]; v = v->fNext) {
1382             LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1383         }
1384     }
1385 #endif
1386     sanitize_contours(contours, contourCnt);
1387     Vertex* vertices = build_edges(contours, contourCnt, alloc);
1388     if (!vertices) {
1389         return NULL;
1390     }
1391
1392     // Sort vertices in Y (secondarily in X).
1393     merge_sort(&vertices);
1394     merge_coincident_vertices(&vertices, alloc);
1395 #if LOGGING_ENABLED
1396     for (Vertex* v = vertices; v != NULL; v = v->fNext) {
1397         static float gID = 0.0f;
1398         v->fID = gID++;
1399     }
1400 #endif
1401     simplify(vertices, alloc);
1402     return tessellate(vertices, alloc);
1403 }
1404
1405 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
1406
1407 void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, void* data) {
1408     void* d = data;
1409     for (Poly* poly = polys; poly; poly = poly->fNext) {
1410         if (apply_fill_type(fillType, poly->fWinding)) {
1411             d = poly->emit(d);
1412         }
1413     }
1414     return d;
1415 }
1416
1417 };
1418
1419 GrTessellatingPathRenderer::GrTessellatingPathRenderer() {
1420 }
1421
1422 GrPathRenderer::StencilSupport GrTessellatingPathRenderer::onGetStencilSupport(
1423                                                             const GrDrawTarget*,
1424                                                             const GrPipelineBuilder*,
1425                                                             const SkPath&,
1426                                                             const SkStrokeRec&) const {
1427     return GrPathRenderer::kNoSupport_StencilSupport;
1428 }
1429
1430 bool GrTessellatingPathRenderer::canDrawPath(const GrDrawTarget* target,
1431                                              const GrPipelineBuilder* pipelineBuilder,
1432                                              const SkMatrix& viewMatrix,
1433                                              const SkPath& path,
1434                                              const SkStrokeRec& stroke,
1435                                              bool antiAlias) const {
1436     // This path renderer can draw all fill styles, but does not do antialiasing. It can do convex
1437     // and concave paths, but we'll leave the convex ones to simpler algorithms.
1438     return stroke.isFillStyle() && !antiAlias && !path.isConvex();
1439 }
1440
1441 class TessellatingPathBatch : public GrBatch {
1442 public:
1443
1444     static GrBatch* Create(const GrColor& color,
1445                            const SkPath& path,
1446                            const SkMatrix& viewMatrix,
1447                            SkRect clipBounds) {
1448         return SkNEW_ARGS(TessellatingPathBatch, (color, path, viewMatrix, clipBounds));
1449     }
1450
1451     const char* name() const SK_OVERRIDE { return "TessellatingPathBatch"; }
1452
1453     void getInvariantOutputColor(GrInitInvariantOutput* out) const SK_OVERRIDE {
1454         out->setKnownFourComponents(fColor);
1455     }
1456
1457     void getInvariantOutputCoverage(GrInitInvariantOutput* out) const SK_OVERRIDE {
1458         out->setUnknownSingleComponent();
1459     }
1460
1461     void initBatchTracker(const GrPipelineInfo& init) SK_OVERRIDE {
1462         // Handle any color overrides
1463         if (init.fColorIgnored) {
1464             fColor = GrColor_ILLEGAL;
1465         } else if (GrColor_ILLEGAL != init.fOverrideColor) {
1466             fColor = init.fOverrideColor;
1467         }
1468         fPipelineInfo = init;
1469     }
1470
1471     void generateGeometry(GrBatchTarget* batchTarget, const GrPipeline* pipeline) SK_OVERRIDE {
1472         SkScalar tol = GrPathUtils::scaleToleranceToSrc(SK_Scalar1, fViewMatrix, fPath.getBounds());
1473         int contourCnt;
1474         int maxPts = GrPathUtils::worstCasePointCount(fPath, &contourCnt, tol);
1475         if (maxPts <= 0) {
1476             return;
1477         }
1478         if (maxPts > ((int)SK_MaxU16 + 1)) {
1479             SkDebugf("Path not rendered, too many verts (%d)\n", maxPts);
1480             return;
1481         }
1482         SkPath::FillType fillType = fPath.getFillType();
1483         if (SkPath::IsInverseFillType(fillType)) {
1484             contourCnt++;
1485         }
1486
1487         LOG("got %d pts, %d contours\n", maxPts, contourCnt);
1488         uint32_t flags = GrDefaultGeoProcFactory::kPosition_GPType;
1489         SkAutoTUnref<const GrGeometryProcessor> gp(
1490             GrDefaultGeoProcFactory::Create(flags, fColor, fViewMatrix, SkMatrix::I()));
1491         batchTarget->initDraw(gp, pipeline);
1492         gp->initBatchTracker(batchTarget->currentBatchTracker(), fPipelineInfo);
1493
1494         SkAutoTDeleteArray<Vertex*> contours(SkNEW_ARRAY(Vertex *, contourCnt));
1495
1496         // For the initial size of the chunk allocator, estimate based on the point count:
1497         // one vertex per point for the initial passes, plus two for the vertices in the
1498         // resulting Polys, since the same point may end up in two Polys.  Assume minimal
1499         // connectivity of one Edge per Vertex (will grow for intersections).
1500         SkChunkAlloc alloc(maxPts * (3 * sizeof(Vertex) + sizeof(Edge)));
1501         path_to_contours(fPath, tol, fClipBounds, contours.get(), alloc);
1502         Poly* polys;
1503         polys = contours_to_polys(contours.get(), contourCnt, alloc);
1504         int count = 0;
1505         for (Poly* poly = polys; poly; poly = poly->fNext) {
1506             if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) {
1507                 count += (poly->fCount - 2) * (WIREFRAME ? 6 : 3);
1508             }
1509         }
1510
1511         size_t stride = gp->getVertexStride();
1512         const GrVertexBuffer* vertexBuffer;
1513         int firstVertex;
1514         void* vertices = batchTarget->vertexPool()->makeSpace(stride,
1515                                                               count,
1516                                                               &vertexBuffer,
1517                                                               &firstVertex);
1518
1519         if (!vertices) {
1520             SkDebugf("Could not allocate vertices\n");
1521             return;
1522         }
1523
1524         LOG("emitting %d verts\n", count);
1525         void* end = polys_to_triangles(polys, fillType, vertices);
1526         int actualCount = static_cast<int>(
1527             (static_cast<char*>(end) - static_cast<char*>(vertices)) / stride);
1528         LOG("actual count: %d\n", actualCount);
1529         SkASSERT(actualCount <= count);
1530
1531         GrPrimitiveType primitiveType = WIREFRAME ? kLines_GrPrimitiveType
1532                                                   : kTriangles_GrPrimitiveType;
1533         GrDrawTarget::DrawInfo drawInfo;
1534         drawInfo.setPrimitiveType(primitiveType);
1535         drawInfo.setVertexBuffer(vertexBuffer);
1536         drawInfo.setStartVertex(firstVertex);
1537         drawInfo.setVertexCount(actualCount);
1538         drawInfo.setStartIndex(0);
1539         drawInfo.setIndexCount(0);
1540         batchTarget->draw(drawInfo);
1541
1542         batchTarget->putBackVertices((size_t)(count - actualCount), stride);
1543         return;
1544     }
1545
1546     bool onCombineIfPossible(GrBatch*) SK_OVERRIDE {
1547         return false;
1548     }
1549
1550 private:
1551     TessellatingPathBatch(const GrColor& color,
1552                           const SkPath& path,
1553                           const SkMatrix& viewMatrix,
1554                           const SkRect& clipBounds)
1555       : fColor(color)
1556       , fPath(path)
1557       , fViewMatrix(viewMatrix)
1558       , fClipBounds(clipBounds) {
1559         this->initClassID<TessellatingPathBatch>();
1560     }
1561
1562     GrColor        fColor;
1563     SkPath         fPath;
1564     SkMatrix       fViewMatrix;
1565     SkRect         fClipBounds; // in source space
1566     GrPipelineInfo fPipelineInfo;
1567 };
1568
1569 bool GrTessellatingPathRenderer::onDrawPath(GrDrawTarget* target,
1570                                             GrPipelineBuilder* pipelineBuilder,
1571                                             GrColor color,
1572                                             const SkMatrix& viewM,
1573                                             const SkPath& path,
1574                                             const SkStrokeRec& stroke,
1575                                             bool antiAlias) {
1576     SkASSERT(!antiAlias);
1577     const GrRenderTarget* rt = pipelineBuilder->getRenderTarget();
1578     if (NULL == rt) {
1579         return false;
1580     }
1581
1582     SkIRect clipBoundsI;
1583     pipelineBuilder->clip().getConservativeBounds(rt, &clipBoundsI);
1584     SkRect clipBounds = SkRect::Make(clipBoundsI);
1585     SkMatrix vmi;
1586     if (!viewM.invert(&vmi)) {
1587         return false;
1588     }
1589     vmi.mapRect(&clipBounds);
1590     SkAutoTUnref<GrBatch> batch(TessellatingPathBatch::Create(color, path, viewM, clipBounds));
1591     target->drawBatch(pipelineBuilder, batch);
1592
1593     return true;
1594 }