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