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 "GrTessellator.h" 9 10#include "GrDefaultGeoProcFactory.h" 11#include "GrPathUtils.h" 12 13#include "SkArenaAlloc.h" 14#include "SkGeometry.h" 15#include "SkPath.h" 16 17#include <stdio.h> 18 19/* 20 * There are six stages to the basic algorithm: 21 * 22 * 1) Linearize the path contours into piecewise linear segments (path_to_contours()). 23 * 2) Build a mesh of edges connecting the vertices (build_edges()). 24 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). 25 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplify()). 26 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). 27 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_triangles()). 28 * 29 * For screenspace antialiasing, the algorithm is modified as follows: 30 * 31 * Run steps 1-5 above to produce polygons. 32 * 5b) Apply fill rules to extract boundary contours from the polygons (extract_boundaries()). 33 * 5c) Simplify boundaries to remove "pointy" vertices that cause inversions (simplify_boundary()). 34 * 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find 35 * new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a new 36 * antialiased mesh from those vertices (stroke_boundary()). 37 * Run steps 3-6 above on the new mesh, and produce antialiased triangles. 38 * 39 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list 40 * of vertices (and the necessity of inserting new vertices on intersection). 41 * 42 * Stages (4) and (5) use an active edge list -- a list of all edges for which the 43 * sweep line has crossed the top vertex, but not the bottom vertex. It's sorted 44 * left-to-right based on the point where both edges are active (when both top vertices 45 * have been seen, so the "lower" top vertex of the two). If the top vertices are equal 46 * (shared), it's sorted based on the last point where both edges are active, so the 47 * "upper" bottom vertex. 48 * 49 * The most complex step is the simplification (4). It's based on the Bentley-Ottman 50 * line-sweep algorithm, but due to floating point inaccuracy, the intersection points are 51 * not exact and may violate the mesh topology or active edge list ordering. We 52 * accommodate this by adjusting the topology of the mesh and AEL to match the intersection 53 * points. This occurs in three ways: 54 * 55 * A) Intersections may cause a shortened edge to no longer be ordered with respect to its 56 * neighbouring edges at the top or bottom vertex. This is handled by merging the 57 * edges (merge_collinear_edges()). 58 * B) Intersections may cause an edge to violate the left-to-right ordering of the 59 * active edge list. This is handled by splitting the neighbour edge on the 60 * intersected vertex (cleanup_active_edges()). 61 * C) Shortening an edge may cause an active edge to become inactive or an inactive edge 62 * to become active. This is handled by removing or inserting the edge in the active 63 * edge list (fix_active_state()). 64 * 65 * The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and 66 * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it 67 * currently uses a linked list for the active edge list, rather than a 2-3 tree as the 68 * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also 69 * become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N) 70 * insertions and removals was greater than the cost of infrequent O(N) lookups with the 71 * linked list implementation. With the latter, all removals are O(1), and most insertions 72 * are O(1), since we know the adjacent edge in the active edge list based on the topology. 73 * Only type 2 vertices (see paper) require the O(N) lookups, and these are much less 74 * frequent. There may be other data structures worth investigating, however. 75 * 76 * Note that the orientation of the line sweep algorithms is determined by the aspect ratio of the 77 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y 78 * coordinate, and secondarily by increasing X coordinate. When the path is wider than it is tall, 79 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordinate. This is so 80 * that the "left" and "right" orientation in the code remains correct (edges to the left are 81 * increasing in Y; edges to the right are decreasing in Y). That is, the setting rotates 90 82 * degrees counterclockwise, rather that transposing. 83 */ 84 85#define LOGGING_ENABLED 0 86 87#if LOGGING_ENABLED 88#define LOG printf 89#else 90#define LOG(...) 91#endif 92 93namespace { 94 95const int kArenaChunkSize = 16 * 1024; 96 97struct Vertex; 98struct Edge; 99struct Poly; 100 101template <class T, T* T::*Prev, T* T::*Next> 102void list_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 117template <class T, T* T::*Prev, T* T::*Next> 118void list_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 = nullptr; 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 143struct Vertex { 144 Vertex(const SkPoint& point, uint8_t alpha) 145 : fPoint(point), fPrev(nullptr), fNext(nullptr) 146 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) 147 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) 148 , fPartner(nullptr) 149 , fProcessed(false) 150 , fAlpha(alpha) 151#if LOGGING_ENABLED 152 , fID (-1.0f) 153#endif 154 {} 155 SkPoint fPoint; // Vertex position 156 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices. 157 Vertex* fNext; // " 158 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. 159 Edge* fLastEdgeAbove; // " 160 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. 161 Edge* fLastEdgeBelow; // " 162 Vertex* fPartner; // Corresponding inner or outer vertex (for AA). 163 bool fProcessed; // Has this vertex been seen in simplify()? 164 uint8_t fAlpha; 165#if LOGGING_ENABLED 166 float fID; // Identifier used for logging. 167#endif 168}; 169 170/***************************************************************************************/ 171 172struct AAParams { 173 bool fTweakAlpha; 174 GrColor fColor; 175}; 176 177typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b); 178 179bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { 180 return a.fX < b.fX || (a.fX == b.fX && a.fY > b.fY); 181} 182 183bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { 184 return a.fY < b.fY || (a.fY == b.fY && a.fX < b.fX); 185} 186 187struct Comparator { 188 enum class Direction { kVertical, kHorizontal }; 189 Comparator(Direction direction) : fDirection(direction) {} 190 bool sweep_lt(const SkPoint& a, const SkPoint& b) const { 191 return fDirection == Direction::kHorizontal ? sweep_lt_horiz(a, b) : sweep_lt_vert(a, b); 192 } 193 Direction fDirection; 194}; 195 196inline void* emit_vertex(Vertex* v, const AAParams* aaParams, void* data) { 197 if (!aaParams) { 198 SkPoint* d = static_cast<SkPoint*>(data); 199 *d++ = v->fPoint; 200 return d; 201 } 202 if (aaParams->fTweakAlpha) { 203 auto d = static_cast<GrDefaultGeoProcFactory::PositionColorAttr*>(data); 204 d->fPosition = v->fPoint; 205 d->fColor = SkAlphaMulQ(aaParams->fColor, SkAlpha255To256(v->fAlpha)); 206 d++; 207 return d; 208 } 209 auto d = static_cast<GrDefaultGeoProcFactory::PositionColorCoverageAttr*>(data); 210 d->fPosition = v->fPoint; 211 d->fColor = aaParams->fColor; 212 d->fCoverage = GrNormalizeByteToFloat(v->fAlpha); 213 d++; 214 return d; 215} 216 217void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, const AAParams* aaParams, void* data) { 218 LOG("emit_triangle (%g, %g) %d\n", v0->fPoint.fX, v0->fPoint.fY, v0->fAlpha); 219 LOG(" (%g, %g) %d\n", v1->fPoint.fX, v1->fPoint.fY, v1->fAlpha); 220 LOG(" (%g, %g) %d\n", v2->fPoint.fX, v2->fPoint.fY, v2->fAlpha); 221#if TESSELLATOR_WIREFRAME 222 data = emit_vertex(v0, aaParams, data); 223 data = emit_vertex(v1, aaParams, data); 224 data = emit_vertex(v1, aaParams, data); 225 data = emit_vertex(v2, aaParams, data); 226 data = emit_vertex(v2, aaParams, data); 227 data = emit_vertex(v0, aaParams, data); 228#else 229 data = emit_vertex(v0, aaParams, data); 230 data = emit_vertex(v1, aaParams, data); 231 data = emit_vertex(v2, aaParams, data); 232#endif 233 return data; 234} 235 236struct VertexList { 237 VertexList() : fHead(nullptr), fTail(nullptr) {} 238 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {} 239 Vertex* fHead; 240 Vertex* fTail; 241 void insert(Vertex* v, Vertex* prev, Vertex* next) { 242 list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail); 243 } 244 void append(Vertex* v) { 245 insert(v, fTail, nullptr); 246 } 247 void append(const VertexList& list) { 248 if (!list.fHead) { 249 return; 250 } 251 if (fTail) { 252 fTail->fNext = list.fHead; 253 list.fHead->fPrev = fTail; 254 } else { 255 fHead = list.fHead; 256 } 257 fTail = list.fTail; 258 } 259 void prepend(Vertex* v) { 260 insert(v, nullptr, fHead); 261 } 262 void remove(Vertex* v) { 263 list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, &fHead, &fTail); 264 } 265 void close() { 266 if (fHead && fTail) { 267 fTail->fNext = fHead; 268 fHead->fPrev = fTail; 269 } 270 } 271}; 272 273// Round to nearest quarter-pixel. This is used for screenspace tessellation. 274 275inline void round(SkPoint* p) { 276 p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f); 277 p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f); 278} 279 280// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line. 281struct Line { 282 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {} 283 Line(const SkPoint& p, const SkPoint& q) 284 : fA(static_cast<double>(q.fY) - p.fY) // a = dY 285 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX 286 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p) 287 static_cast<double>(p.fX) * q.fY) {} 288 double dist(const SkPoint& p) const { 289 return fA * p.fX + fB * p.fY + fC; 290 } 291 double magSq() const { 292 return fA * fA + fB * fB; 293 } 294 295 // Compute the intersection of two (infinite) Lines. 296 bool intersect(const Line& other, SkPoint* point) { 297 double denom = fA * other.fB - fB * other.fA; 298 if (denom == 0.0) { 299 return false; 300 } 301 double scale = 1.0f / denom; 302 point->fX = SkDoubleToScalar((fB * other.fC - other.fB * fC) * scale); 303 point->fY = SkDoubleToScalar((other.fA * fC - fA * other.fC) * scale); 304 round(point); 305 return true; 306 } 307 double fA, fB, fC; 308}; 309 310/** 311 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and 312 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf(). 313 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating 314 * point). For speed, that case is only tested by the callers that require it (e.g., 315 * cleanup_active_edges()). Edges also handle checking for intersection with other edges. 316 * Currently, this converts the edges to the parametric form, in order to avoid doing a division 317 * until an intersection has been confirmed. This is slightly slower in the "found" case, but 318 * a lot faster in the "not found" case. 319 * 320 * The coefficients of the line equation stored in double precision to avoid catastrphic 321 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is 322 * correct in float, since it's a polynomial of degree 2. The intersect() function, being 323 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its 324 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of 325 * this file). 326 */ 327 328struct Edge { 329 enum class Type { kInner, kOuter, kConnector }; 330 Edge(Vertex* top, Vertex* bottom, int winding, Type type) 331 : fWinding(winding) 332 , fTop(top) 333 , fBottom(bottom) 334 , fType(type) 335 , fLeft(nullptr) 336 , fRight(nullptr) 337 , fPrevEdgeAbove(nullptr) 338 , fNextEdgeAbove(nullptr) 339 , fPrevEdgeBelow(nullptr) 340 , fNextEdgeBelow(nullptr) 341 , fLeftPoly(nullptr) 342 , fRightPoly(nullptr) 343 , fLeftPolyPrev(nullptr) 344 , fLeftPolyNext(nullptr) 345 , fRightPolyPrev(nullptr) 346 , fRightPolyNext(nullptr) 347 , fUsedInLeftPoly(false) 348 , fUsedInRightPoly(false) 349 , fLine(top, bottom) { 350 } 351 int fWinding; // 1 == edge goes downward; -1 = edge goes upward. 352 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt). 353 Vertex* fBottom; // The bottom vertex in vertex-sort-order. 354 Type fType; 355 Edge* fLeft; // The linked list of edges in the active edge list. 356 Edge* fRight; // " 357 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above". 358 Edge* fNextEdgeAbove; // " 359 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below". 360 Edge* fNextEdgeBelow; // " 361 Poly* fLeftPoly; // The Poly to the left of this edge, if any. 362 Poly* fRightPoly; // The Poly to the right of this edge, if any. 363 Edge* fLeftPolyPrev; 364 Edge* fLeftPolyNext; 365 Edge* fRightPolyPrev; 366 Edge* fRightPolyNext; 367 bool fUsedInLeftPoly; 368 bool fUsedInRightPoly; 369 Line fLine; 370 double dist(const SkPoint& p) const { 371 return fLine.dist(p); 372 } 373 bool isRightOf(Vertex* v) const { 374 return fLine.dist(v->fPoint) < 0.0; 375 } 376 bool isLeftOf(Vertex* v) const { 377 return fLine.dist(v->fPoint) > 0.0; 378 } 379 void recompute() { 380 fLine = Line(fTop, fBottom); 381 } 382 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) { 383 LOG("intersecting %g -> %g with %g -> %g\n", 384 fTop->fID, fBottom->fID, 385 other.fTop->fID, other.fBottom->fID); 386 if (fTop == other.fTop || fBottom == other.fBottom) { 387 return false; 388 } 389 double denom = fLine.fA * other.fLine.fB - fLine.fB * other.fLine.fA; 390 if (denom == 0.0) { 391 return false; 392 } 393 double dx = static_cast<double>(other.fTop->fPoint.fX) - fTop->fPoint.fX; 394 double dy = static_cast<double>(other.fTop->fPoint.fY) - fTop->fPoint.fY; 395 double sNumer = dy * other.fLine.fB + dx * other.fLine.fA; 396 double tNumer = dy * fLine.fB + dx * fLine.fA; 397 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. 398 // This saves us doing the divide below unless absolutely necessary. 399 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom) 400 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) { 401 return false; 402 } 403 double s = sNumer / denom; 404 SkASSERT(s >= 0.0 && s <= 1.0); 405 p->fX = SkDoubleToScalar(fTop->fPoint.fX - s * fLine.fB); 406 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fLine.fA); 407 if (alpha) { 408 if (fType == Type::kConnector) { 409 *alpha = (1.0 - s) * fTop->fAlpha + s * fBottom->fAlpha; 410 } else if (other.fType == Type::kConnector) { 411 double t = tNumer / denom; 412 *alpha = (1.0 - t) * other.fTop->fAlpha + t * other.fBottom->fAlpha; 413 } else if (fType == Type::kOuter && other.fType == Type::kOuter) { 414 *alpha = 0; 415 } else { 416 *alpha = 255; 417 } 418 } 419 return true; 420 } 421}; 422 423struct EdgeList { 424 EdgeList() : fHead(nullptr), fTail(nullptr) {} 425 Edge* fHead; 426 Edge* fTail; 427 void insert(Edge* edge, Edge* prev, Edge* next) { 428 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail); 429 } 430 void append(Edge* e) { 431 insert(e, fTail, nullptr); 432 } 433 void remove(Edge* edge) { 434 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail); 435 } 436 void removeAll() { 437 while (fHead) { 438 this->remove(fHead); 439 } 440 } 441 void close() { 442 if (fHead && fTail) { 443 fTail->fRight = fHead; 444 fHead->fLeft = fTail; 445 } 446 } 447 bool contains(Edge* edge) const { 448 return edge->fLeft || edge->fRight || fHead == edge; 449 } 450}; 451 452/***************************************************************************************/ 453 454struct Poly { 455 Poly(Vertex* v, int winding) 456 : fFirstVertex(v) 457 , fWinding(winding) 458 , fHead(nullptr) 459 , fTail(nullptr) 460 , fNext(nullptr) 461 , fPartner(nullptr) 462 , fCount(0) 463 { 464#if LOGGING_ENABLED 465 static int gID = 0; 466 fID = gID++; 467 LOG("*** created Poly %d\n", fID); 468#endif 469 } 470 typedef enum { kLeft_Side, kRight_Side } Side; 471 struct MonotonePoly { 472 MonotonePoly(Edge* edge, Side side) 473 : fSide(side) 474 , fFirstEdge(nullptr) 475 , fLastEdge(nullptr) 476 , fPrev(nullptr) 477 , fNext(nullptr) { 478 this->addEdge(edge); 479 } 480 Side fSide; 481 Edge* fFirstEdge; 482 Edge* fLastEdge; 483 MonotonePoly* fPrev; 484 MonotonePoly* fNext; 485 void addEdge(Edge* edge) { 486 if (fSide == kRight_Side) { 487 SkASSERT(!edge->fUsedInRightPoly); 488 list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>( 489 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge); 490 edge->fUsedInRightPoly = true; 491 } else { 492 SkASSERT(!edge->fUsedInLeftPoly); 493 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>( 494 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge); 495 edge->fUsedInLeftPoly = true; 496 } 497 } 498 499 void* emit(const AAParams* aaParams, void* data) { 500 Edge* e = fFirstEdge; 501 VertexList vertices; 502 vertices.append(e->fTop); 503 int count = 1; 504 while (e != nullptr) { 505 if (kRight_Side == fSide) { 506 vertices.append(e->fBottom); 507 e = e->fRightPolyNext; 508 } else { 509 vertices.prepend(e->fBottom); 510 e = e->fLeftPolyNext; 511 } 512 count++; 513 } 514 Vertex* first = vertices.fHead; 515 Vertex* v = first->fNext; 516 while (v != vertices.fTail) { 517 SkASSERT(v && v->fPrev && v->fNext); 518 Vertex* prev = v->fPrev; 519 Vertex* curr = v; 520 Vertex* next = v->fNext; 521 if (count == 3) { 522 return emit_triangle(prev, curr, next, aaParams, data); 523 } 524 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX; 525 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY; 526 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX; 527 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY; 528 if (ax * by - ay * bx >= 0.0) { 529 data = emit_triangle(prev, curr, next, aaParams, data); 530 v->fPrev->fNext = v->fNext; 531 v->fNext->fPrev = v->fPrev; 532 count--; 533 if (v->fPrev == first) { 534 v = v->fNext; 535 } else { 536 v = v->fPrev; 537 } 538 } else { 539 v = v->fNext; 540 } 541 } 542 return data; 543 } 544 }; 545 Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc) { 546 LOG("addEdge (%g -> %g) to poly %d, %s side\n", 547 e->fTop->fID, e->fBottom->fID, fID, side == kLeft_Side ? "left" : "right"); 548 Poly* partner = fPartner; 549 Poly* poly = this; 550 if (side == kRight_Side) { 551 if (e->fUsedInRightPoly) { 552 return this; 553 } 554 } else { 555 if (e->fUsedInLeftPoly) { 556 return this; 557 } 558 } 559 if (partner) { 560 fPartner = partner->fPartner = nullptr; 561 } 562 if (!fTail) { 563 fHead = fTail = alloc.make<MonotonePoly>(e, side); 564 fCount += 2; 565 } else if (e->fBottom == fTail->fLastEdge->fBottom) { 566 return poly; 567 } else if (side == fTail->fSide) { 568 fTail->addEdge(e); 569 fCount++; 570 } else { 571 e = alloc.make<Edge>(fTail->fLastEdge->fBottom, e->fBottom, 1, Edge::Type::kInner); 572 fTail->addEdge(e); 573 fCount++; 574 if (partner) { 575 partner->addEdge(e, side, alloc); 576 poly = partner; 577 } else { 578 MonotonePoly* m = alloc.make<MonotonePoly>(e, side); 579 m->fPrev = fTail; 580 fTail->fNext = m; 581 fTail = m; 582 } 583 } 584 return poly; 585 } 586 void* emit(const AAParams* aaParams, void *data) { 587 if (fCount < 3) { 588 return data; 589 } 590 LOG("emit() %d, size %d\n", fID, fCount); 591 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { 592 data = m->emit(aaParams, data); 593 } 594 return data; 595 } 596 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; } 597 Vertex* fFirstVertex; 598 int fWinding; 599 MonotonePoly* fHead; 600 MonotonePoly* fTail; 601 Poly* fNext; 602 Poly* fPartner; 603 int fCount; 604#if LOGGING_ENABLED 605 int fID; 606#endif 607}; 608 609/***************************************************************************************/ 610 611bool coincident(const SkPoint& a, const SkPoint& b) { 612 return a == b; 613} 614 615Poly* new_poly(Poly** head, Vertex* v, int winding, SkArenaAlloc& alloc) { 616 Poly* poly = alloc.make<Poly>(v, winding); 617 poly->fNext = *head; 618 *head = poly; 619 return poly; 620} 621 622void append_point_to_contour(const SkPoint& p, VertexList* contour, SkArenaAlloc& alloc) { 623 Vertex* v = alloc.make<Vertex>(p, 255); 624#if LOGGING_ENABLED 625 static float gID = 0.0f; 626 v->fID = gID++; 627#endif 628 contour->append(v); 629} 630 631void generate_quadratic_points(const SkPoint& p0, 632 const SkPoint& p1, 633 const SkPoint& p2, 634 SkScalar tolSqd, 635 VertexList* contour, 636 int pointsLeft, 637 SkArenaAlloc& alloc) { 638 SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2); 639 if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) { 640 append_point_to_contour(p2, contour, alloc); 641 return; 642 } 643 644 const SkPoint q[] = { 645 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 646 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 647 }; 648 const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }; 649 650 pointsLeft >>= 1; 651 generate_quadratic_points(p0, q[0], r, tolSqd, contour, pointsLeft, alloc); 652 generate_quadratic_points(r, q[1], p2, tolSqd, contour, pointsLeft, alloc); 653} 654 655void generate_cubic_points(const SkPoint& p0, 656 const SkPoint& p1, 657 const SkPoint& p2, 658 const SkPoint& p3, 659 SkScalar tolSqd, 660 VertexList* contour, 661 int pointsLeft, 662 SkArenaAlloc& alloc) { 663 SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3); 664 SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3); 665 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || 666 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) { 667 append_point_to_contour(p3, contour, alloc); 668 return; 669 } 670 const SkPoint q[] = { 671 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 672 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 673 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } 674 }; 675 const SkPoint r[] = { 676 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, 677 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } 678 }; 679 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) }; 680 pointsLeft >>= 1; 681 generate_cubic_points(p0, q[0], r[0], s, tolSqd, contour, pointsLeft, alloc); 682 generate_cubic_points(s, r[1], q[2], p3, tolSqd, contour, pointsLeft, alloc); 683} 684 685// Stage 1: convert the input path to a set of linear contours (linked list of Vertices). 686 687void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 688 VertexList* contours, SkArenaAlloc& alloc, bool *isLinear) { 689 SkScalar toleranceSqd = tolerance * tolerance; 690 691 SkPoint pts[4]; 692 *isLinear = true; 693 VertexList* contour = contours; 694 SkPath::Iter iter(path, false); 695 if (path.isInverseFillType()) { 696 SkPoint quad[4]; 697 clipBounds.toQuad(quad); 698 for (int i = 3; i >= 0; i--) { 699 append_point_to_contour(quad[i], contours, alloc); 700 } 701 contour++; 702 } 703 SkAutoConicToQuads converter; 704 SkPath::Verb verb; 705 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 706 switch (verb) { 707 case SkPath::kConic_Verb: { 708 SkScalar weight = iter.conicWeight(); 709 const SkPoint* quadPts = converter.computeQuads(pts, weight, toleranceSqd); 710 for (int i = 0; i < converter.countQuads(); ++i) { 711 int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, tolerance); 712 generate_quadratic_points(quadPts[0], quadPts[1], quadPts[2], toleranceSqd, 713 contour, pointsLeft, alloc); 714 quadPts += 2; 715 } 716 *isLinear = false; 717 break; 718 } 719 case SkPath::kMove_Verb: 720 if (contour->fHead) { 721 contour++; 722 } 723 append_point_to_contour(pts[0], contour, alloc); 724 break; 725 case SkPath::kLine_Verb: { 726 append_point_to_contour(pts[1], contour, alloc); 727 break; 728 } 729 case SkPath::kQuad_Verb: { 730 int pointsLeft = GrPathUtils::quadraticPointCount(pts, tolerance); 731 generate_quadratic_points(pts[0], pts[1], pts[2], toleranceSqd, contour, 732 pointsLeft, alloc); 733 *isLinear = false; 734 break; 735 } 736 case SkPath::kCubic_Verb: { 737 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance); 738 generate_cubic_points(pts[0], pts[1], pts[2], pts[3], toleranceSqd, contour, 739 pointsLeft, alloc); 740 *isLinear = false; 741 break; 742 } 743 case SkPath::kClose_Verb: 744 case SkPath::kDone_Verb: 745 break; 746 } 747 } 748} 749 750inline bool apply_fill_type(SkPath::FillType fillType, int winding) { 751 switch (fillType) { 752 case SkPath::kWinding_FillType: 753 return winding != 0; 754 case SkPath::kEvenOdd_FillType: 755 return (winding & 1) != 0; 756 case SkPath::kInverseWinding_FillType: 757 return winding == 1; 758 case SkPath::kInverseEvenOdd_FillType: 759 return (winding & 1) == 1; 760 default: 761 SkASSERT(false); 762 return false; 763 } 764} 765 766inline bool apply_fill_type(SkPath::FillType fillType, Poly* poly) { 767 return poly && apply_fill_type(fillType, poly->fWinding); 768} 769 770Edge* new_edge(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc) { 771 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; 772 Vertex* top = winding < 0 ? next : prev; 773 Vertex* bottom = winding < 0 ? prev : next; 774 return alloc.make<Edge>(top, bottom, winding, type); 775} 776 777void remove_edge(Edge* edge, EdgeList* edges) { 778 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); 779 SkASSERT(edges->contains(edge)); 780 edges->remove(edge); 781} 782 783void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) { 784 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); 785 SkASSERT(!edges->contains(edge)); 786 Edge* next = prev ? prev->fRight : edges->fHead; 787 edges->insert(edge, prev, next); 788} 789 790void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) { 791 if (v->fFirstEdgeAbove && v->fLastEdgeAbove) { 792 *left = v->fFirstEdgeAbove->fLeft; 793 *right = v->fLastEdgeAbove->fRight; 794 return; 795 } 796 Edge* next = nullptr; 797 Edge* prev; 798 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { 799 if (prev->isLeftOf(v)) { 800 break; 801 } 802 next = prev; 803 } 804 *left = prev; 805 *right = next; 806} 807 808void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) { 809 Edge* prev = nullptr; 810 Edge* next; 811 for (next = edges->fHead; next != nullptr; next = next->fRight) { 812 if ((c.sweep_lt(next->fTop->fPoint, edge->fTop->fPoint) && next->isRightOf(edge->fTop)) || 813 (c.sweep_lt(edge->fTop->fPoint, next->fTop->fPoint) && edge->isLeftOf(next->fTop)) || 814 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) && 815 next->isRightOf(edge->fBottom)) || 816 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) && 817 edge->isLeftOf(next->fBottom))) { 818 break; 819 } 820 prev = next; 821 } 822 *left = prev; 823 *right = next; 824} 825 826void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) { 827 if (!activeEdges) { 828 return; 829 } 830 if (activeEdges->contains(edge)) { 831 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) { 832 remove_edge(edge, activeEdges); 833 } 834 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) { 835 Edge* left; 836 Edge* right; 837 find_enclosing_edges(edge, activeEdges, c, &left, &right); 838 insert_edge(edge, left, activeEdges); 839 } 840} 841 842void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { 843 if (edge->fTop->fPoint == edge->fBottom->fPoint || 844 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) { 845 return; 846 } 847 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID); 848 Edge* prev = nullptr; 849 Edge* next; 850 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { 851 if (next->isRightOf(edge->fTop)) { 852 break; 853 } 854 prev = next; 855 } 856 list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( 857 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); 858} 859 860void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { 861 if (edge->fTop->fPoint == edge->fBottom->fPoint || 862 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) { 863 return; 864 } 865 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID); 866 Edge* prev = nullptr; 867 Edge* next; 868 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { 869 if (next->isRightOf(edge->fBottom)) { 870 break; 871 } 872 prev = next; 873 } 874 list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( 875 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow); 876} 877 878void remove_edge_above(Edge* edge) { 879 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, 880 edge->fBottom->fID); 881 list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( 882 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove); 883} 884 885void remove_edge_below(Edge* edge) { 886 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, 887 edge->fTop->fID); 888 list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( 889 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow); 890} 891 892void disconnect(Edge* edge) 893{ 894 remove_edge_above(edge); 895 remove_edge_below(edge); 896} 897 898void erase_edge(Edge* edge, EdgeList* edges) { 899 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID); 900 disconnect(edge); 901 if (edges && edges->contains(edge)) { 902 remove_edge(edge, edges); 903 } 904} 905 906void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c); 907 908void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) { 909 remove_edge_below(edge); 910 edge->fTop = v; 911 edge->recompute(); 912 insert_edge_below(edge, v, c); 913 fix_active_state(edge, activeEdges, c); 914 merge_collinear_edges(edge, activeEdges, c); 915} 916 917void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) { 918 remove_edge_above(edge); 919 edge->fBottom = v; 920 edge->recompute(); 921 insert_edge_above(edge, v, c); 922 fix_active_state(edge, activeEdges, c); 923 merge_collinear_edges(edge, activeEdges, c); 924} 925 926void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) { 927 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { 928 LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n", 929 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY, 930 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY); 931 other->fWinding += edge->fWinding; 932 erase_edge(edge, activeEdges); 933 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) { 934 other->fWinding += edge->fWinding; 935 set_bottom(edge, other->fTop, activeEdges, c); 936 } else { 937 edge->fWinding += other->fWinding; 938 set_bottom(other, edge->fTop, activeEdges, c); 939 } 940} 941 942void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) { 943 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) { 944 LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n", 945 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY, 946 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY); 947 other->fWinding += edge->fWinding; 948 erase_edge(edge, activeEdges); 949 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) { 950 edge->fWinding += other->fWinding; 951 set_top(other, edge->fBottom, activeEdges, c); 952 } else { 953 other->fWinding += edge->fWinding; 954 set_top(edge, other->fBottom, activeEdges, c); 955 } 956} 957 958void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) { 959 if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop || 960 !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) { 961 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c); 962 } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop || 963 !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) { 964 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c); 965 } 966 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom || 967 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) { 968 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c); 969 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom || 970 !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) { 971 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c); 972 } 973} 974 975void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc); 976 977void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc) { 978 Vertex* top = edge->fTop; 979 Vertex* bottom = edge->fBottom; 980 if (edge->fLeft) { 981 Vertex* leftTop = edge->fLeft->fTop; 982 Vertex* leftBottom = edge->fLeft->fBottom; 983 if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) { 984 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc); 985 } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) { 986 split_edge(edge, leftTop, activeEdges, c, alloc); 987 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && 988 !edge->fLeft->isLeftOf(bottom)) { 989 split_edge(edge->fLeft, bottom, activeEdges, c, alloc); 990 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) { 991 split_edge(edge, leftBottom, activeEdges, c, alloc); 992 } 993 } 994 if (edge->fRight) { 995 Vertex* rightTop = edge->fRight->fTop; 996 Vertex* rightBottom = edge->fRight->fBottom; 997 if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) { 998 split_edge(edge->fRight, top, activeEdges, c, alloc); 999 } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) { 1000 split_edge(edge, rightTop, activeEdges, c, alloc); 1001 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && 1002 !edge->fRight->isRightOf(bottom)) { 1003 split_edge(edge->fRight, bottom, activeEdges, c, alloc); 1004 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && 1005 !edge->isLeftOf(rightBottom)) { 1006 split_edge(edge, rightBottom, activeEdges, c, alloc); 1007 } 1008 } 1009} 1010 1011void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc) { 1012 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", 1013 edge->fTop->fID, edge->fBottom->fID, 1014 v->fID, v->fPoint.fX, v->fPoint.fY); 1015 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) { 1016 set_top(edge, v, activeEdges, c); 1017 } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) { 1018 set_bottom(edge, v, activeEdges, c); 1019 } else { 1020 Edge* newEdge = alloc.make<Edge>(v, edge->fBottom, edge->fWinding, edge->fType); 1021 insert_edge_below(newEdge, v, c); 1022 insert_edge_above(newEdge, edge->fBottom, c); 1023 set_bottom(edge, v, activeEdges, c); 1024 cleanup_active_edges(edge, activeEdges, c, alloc); 1025 fix_active_state(newEdge, activeEdges, c); 1026 merge_collinear_edges(newEdge, activeEdges, c); 1027 } 1028} 1029 1030Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc, 1031 int winding_scale = 1) { 1032 Edge* edge = new_edge(prev, next, type, c, alloc); 1033 insert_edge_below(edge, edge->fTop, c); 1034 insert_edge_above(edge, edge->fBottom, c); 1035 edge->fWinding *= winding_scale; 1036 merge_collinear_edges(edge, nullptr, c); 1037 return edge; 1038} 1039 1040void merge_vertices(Vertex* src, Vertex* dst, VertexList* mesh, Comparator& c, 1041 SkArenaAlloc& alloc) { 1042 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX, src->fPoint.fY, 1043 src->fID, dst->fID); 1044 dst->fAlpha = SkTMax(src->fAlpha, dst->fAlpha); 1045 if (src->fPartner) { 1046 src->fPartner->fPartner = dst; 1047 } 1048 for (Edge* edge = src->fFirstEdgeAbove; edge;) { 1049 Edge* next = edge->fNextEdgeAbove; 1050 set_bottom(edge, dst, nullptr, c); 1051 edge = next; 1052 } 1053 for (Edge* edge = src->fFirstEdgeBelow; edge;) { 1054 Edge* next = edge->fNextEdgeBelow; 1055 set_top(edge, dst, nullptr, c); 1056 edge = next; 1057 } 1058 mesh->remove(src); 1059} 1060 1061uint8_t max_edge_alpha(Edge* a, Edge* b) { 1062 if (a->fType == Edge::Type::kInner || b->fType == Edge::Type::kInner) { 1063 return 255; 1064 } else if (a->fType == Edge::Type::kOuter && b->fType == Edge::Type::kOuter) { 1065 return 0; 1066 } else { 1067 return SkTMax(SkTMax(a->fTop->fAlpha, a->fBottom->fAlpha), 1068 SkTMax(b->fTop->fAlpha, b->fBottom->fAlpha)); 1069 } 1070} 1071 1072Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c, 1073 SkArenaAlloc& alloc) { 1074 if (!edge || !other) { 1075 return nullptr; 1076 } 1077 SkPoint p; 1078 uint8_t alpha; 1079 if (edge->intersect(*other, &p, &alpha)) { 1080 Vertex* v; 1081 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); 1082 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { 1083 split_edge(other, edge->fTop, activeEdges, c, alloc); 1084 v = edge->fTop; 1085 } else if (p == edge->fBottom->fPoint || c.sweep_lt(edge->fBottom->fPoint, p)) { 1086 split_edge(other, edge->fBottom, activeEdges, c, alloc); 1087 v = edge->fBottom; 1088 } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint)) { 1089 split_edge(edge, other->fTop, activeEdges, c, alloc); 1090 v = other->fTop; 1091 } else if (p == other->fBottom->fPoint || c.sweep_lt(other->fBottom->fPoint, p)) { 1092 split_edge(edge, other->fBottom, activeEdges, c, alloc); 1093 v = other->fBottom; 1094 } else { 1095 Vertex* nextV = edge->fTop; 1096 while (c.sweep_lt(p, nextV->fPoint)) { 1097 nextV = nextV->fPrev; 1098 } 1099 while (c.sweep_lt(nextV->fPoint, p)) { 1100 nextV = nextV->fNext; 1101 } 1102 Vertex* prevV = nextV->fPrev; 1103 if (coincident(prevV->fPoint, p)) { 1104 v = prevV; 1105 } else if (coincident(nextV->fPoint, p)) { 1106 v = nextV; 1107 } else { 1108 v = alloc.make<Vertex>(p, alpha); 1109 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", 1110 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY, 1111 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY); 1112#if LOGGING_ENABLED 1113 v->fID = (nextV->fID + prevV->fID) * 0.5f; 1114#endif 1115 v->fPrev = prevV; 1116 v->fNext = nextV; 1117 prevV->fNext = v; 1118 nextV->fPrev = v; 1119 } 1120 split_edge(edge, v, activeEdges, c, alloc); 1121 split_edge(other, v, activeEdges, c, alloc); 1122 } 1123 v->fAlpha = SkTMax(v->fAlpha, alpha); 1124 return v; 1125 } 1126 return nullptr; 1127} 1128 1129void sanitize_contours(VertexList* contours, int contourCnt, bool approximate) { 1130 for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) { 1131 SkASSERT(contour->fHead); 1132 Vertex* prev = contour->fTail; 1133 if (approximate) { 1134 round(&prev->fPoint); 1135 } 1136 for (Vertex* v = contour->fHead; v;) { 1137 if (approximate) { 1138 round(&v->fPoint); 1139 } 1140 Vertex* next = v->fNext; 1141 if (coincident(prev->fPoint, v->fPoint)) { 1142 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY); 1143 contour->remove(v); 1144 } 1145 prev = v; 1146 v = next; 1147 } 1148 } 1149} 1150 1151void merge_coincident_vertices(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1152 if (!mesh->fHead) { 1153 return; 1154 } 1155 for (Vertex* v = mesh->fHead->fNext; v != nullptr; v = v->fNext) { 1156 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { 1157 v->fPoint = v->fPrev->fPoint; 1158 } 1159 if (coincident(v->fPrev->fPoint, v->fPoint)) { 1160 merge_vertices(v->fPrev, v, mesh, c, alloc); 1161 } 1162 } 1163} 1164 1165// Stage 2: convert the contours to a mesh of edges connecting the vertices. 1166 1167void build_edges(VertexList* contours, int contourCnt, VertexList* mesh, Comparator& c, 1168 SkArenaAlloc& alloc) { 1169 for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) { 1170 Vertex* prev = contour->fTail; 1171 for (Vertex* v = contour->fHead; v;) { 1172 Vertex* next = v->fNext; 1173 connect(prev, v, Edge::Type::kInner, c, alloc); 1174 mesh->append(v); 1175 prev = v; 1176 v = next; 1177 } 1178 } 1179} 1180 1181void connect_partners(VertexList* outerVertices, Comparator& c, SkArenaAlloc& alloc) { 1182 for (Vertex* outer = outerVertices->fHead; outer; outer = outer->fNext) { 1183 if (Vertex* inner = outer->fPartner) { 1184 // Connector edges get zero winding, since they're only structural (i.e., to ensure 1185 // no 0-0-0 alpha triangles are produced), and shouldn't affect the poly winding number. 1186 connect(outer, inner, Edge::Type::kConnector, c, alloc, 0); 1187 inner->fPartner = outer->fPartner = nullptr; 1188 } 1189 } 1190} 1191 1192template <CompareFunc sweep_lt> 1193void sorted_merge(VertexList* front, VertexList* back, VertexList* result) { 1194 Vertex* a = front->fHead; 1195 Vertex* b = back->fHead; 1196 while (a && b) { 1197 if (sweep_lt(a->fPoint, b->fPoint)) { 1198 front->remove(a); 1199 result->append(a); 1200 a = front->fHead; 1201 } else { 1202 back->remove(b); 1203 result->append(b); 1204 b = back->fHead; 1205 } 1206 } 1207 result->append(*front); 1208 result->append(*back); 1209} 1210 1211void sorted_merge(VertexList* front, VertexList* back, VertexList* result, Comparator& c) { 1212 if (c.fDirection == Comparator::Direction::kHorizontal) { 1213 sorted_merge<sweep_lt_horiz>(front, back, result); 1214 } else { 1215 sorted_merge<sweep_lt_vert>(front, back, result); 1216 } 1217} 1218 1219// Stage 3: sort the vertices by increasing sweep direction. 1220 1221template <CompareFunc sweep_lt> 1222void merge_sort(VertexList* vertices) { 1223 Vertex* slow = vertices->fHead; 1224 if (!slow) { 1225 return; 1226 } 1227 Vertex* fast = slow->fNext; 1228 if (!fast) { 1229 return; 1230 } 1231 do { 1232 fast = fast->fNext; 1233 if (fast) { 1234 fast = fast->fNext; 1235 slow = slow->fNext; 1236 } 1237 } while (fast); 1238 VertexList front(vertices->fHead, slow); 1239 VertexList back(slow->fNext, vertices->fTail); 1240 front.fTail->fNext = back.fHead->fPrev = nullptr; 1241 1242 merge_sort<sweep_lt>(&front); 1243 merge_sort<sweep_lt>(&back); 1244 1245 vertices->fHead = vertices->fTail = nullptr; 1246 sorted_merge<sweep_lt>(&front, &back, vertices); 1247} 1248 1249// Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. 1250 1251void simplify(const VertexList& vertices, Comparator& c, SkArenaAlloc& alloc) { 1252 LOG("simplifying complex polygons\n"); 1253 EdgeList activeEdges; 1254 for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) { 1255 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1256 continue; 1257 } 1258#if LOGGING_ENABLED 1259 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha); 1260#endif 1261 Edge* leftEnclosingEdge; 1262 Edge* rightEnclosingEdge; 1263 bool restartChecks; 1264 do { 1265 restartChecks = false; 1266 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1267 if (v->fFirstEdgeBelow) { 1268 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) { 1269 if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) { 1270 restartChecks = true; 1271 break; 1272 } 1273 if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) { 1274 restartChecks = true; 1275 break; 1276 } 1277 } 1278 } else { 1279 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, rightEnclosingEdge, 1280 &activeEdges, c, alloc)) { 1281 if (c.sweep_lt(pv->fPoint, v->fPoint)) { 1282 v = pv; 1283 } 1284 restartChecks = true; 1285 } 1286 1287 } 1288 } while (restartChecks); 1289 if (v->fAlpha == 0) { 1290 if ((leftEnclosingEdge && leftEnclosingEdge->fWinding < 0) && 1291 (rightEnclosingEdge && rightEnclosingEdge->fWinding > 0)) { 1292 v->fAlpha = max_edge_alpha(leftEnclosingEdge, rightEnclosingEdge); 1293 } 1294 } 1295 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1296 remove_edge(e, &activeEdges); 1297 } 1298 Edge* leftEdge = leftEnclosingEdge; 1299 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1300 insert_edge(e, leftEdge, &activeEdges); 1301 leftEdge = e; 1302 } 1303 v->fProcessed = true; 1304 } 1305} 1306 1307// This is a stripped-down version of simplify() (the Bentley-Ottmann algorithm) that 1308// early-returns true on the first found intersection, false if none. 1309bool is_complex(const VertexList& vertices) { 1310 LOG("testing polygon complexity\n"); 1311 EdgeList activeEdges; 1312 for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) { 1313 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1314 continue; 1315 } 1316 Edge* leftEnclosingEdge; 1317 Edge* rightEnclosingEdge; 1318 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1319 SkPoint dummy; 1320 if (v->fFirstEdgeBelow) { 1321 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) { 1322 if (edge && leftEnclosingEdge && edge->intersect(*leftEnclosingEdge, &dummy)) { 1323 activeEdges.removeAll(); 1324 return true; 1325 } 1326 if (edge && rightEnclosingEdge && edge->intersect(*rightEnclosingEdge, &dummy)) { 1327 activeEdges.removeAll(); 1328 return true; 1329 } 1330 } 1331 } else if (leftEnclosingEdge && rightEnclosingEdge && 1332 leftEnclosingEdge->intersect(*rightEnclosingEdge, &dummy)) { 1333 activeEdges.removeAll(); 1334 return true; 1335 } 1336 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1337 remove_edge(e, &activeEdges); 1338 } 1339 Edge* leftEdge = leftEnclosingEdge; 1340 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1341 insert_edge(e, leftEdge, &activeEdges); 1342 leftEdge = e; 1343 } 1344 } 1345 activeEdges.removeAll(); 1346 return false; 1347} 1348 1349// Stage 5: Tessellate the simplified mesh into monotone polygons. 1350 1351Poly* tessellate(const VertexList& vertices, SkArenaAlloc& alloc) { 1352 LOG("tessellating simple polygons\n"); 1353 EdgeList activeEdges; 1354 Poly* polys = nullptr; 1355 for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) { 1356 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1357 continue; 1358 } 1359#if LOGGING_ENABLED 1360 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha); 1361#endif 1362 Edge* leftEnclosingEdge; 1363 Edge* rightEnclosingEdge; 1364 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1365 Poly* leftPoly; 1366 Poly* rightPoly; 1367 if (v->fFirstEdgeAbove) { 1368 leftPoly = v->fFirstEdgeAbove->fLeftPoly; 1369 rightPoly = v->fLastEdgeAbove->fRightPoly; 1370 } else { 1371 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullptr; 1372 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nullptr; 1373 } 1374#if LOGGING_ENABLED 1375 LOG("edges above:\n"); 1376 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1377 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, 1378 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1); 1379 } 1380 LOG("edges below:\n"); 1381 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1382 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, 1383 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1); 1384 } 1385#endif 1386 if (v->fFirstEdgeAbove) { 1387 if (leftPoly) { 1388 leftPoly = leftPoly->addEdge(v->fFirstEdgeAbove, Poly::kRight_Side, alloc); 1389 } 1390 if (rightPoly) { 1391 rightPoly = rightPoly->addEdge(v->fLastEdgeAbove, Poly::kLeft_Side, alloc); 1392 } 1393 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) { 1394 Edge* rightEdge = e->fNextEdgeAbove; 1395 SkASSERT(rightEdge->isRightOf(e->fTop)); 1396 remove_edge(e, &activeEdges); 1397 if (e->fRightPoly) { 1398 e->fRightPoly->addEdge(e, Poly::kLeft_Side, alloc); 1399 } 1400 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != e->fRightPoly) { 1401 rightEdge->fLeftPoly->addEdge(e, Poly::kRight_Side, alloc); 1402 } 1403 } 1404 remove_edge(v->fLastEdgeAbove, &activeEdges); 1405 if (!v->fFirstEdgeBelow) { 1406 if (leftPoly && rightPoly && leftPoly != rightPoly) { 1407 SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartner == nullptr); 1408 rightPoly->fPartner = leftPoly; 1409 leftPoly->fPartner = rightPoly; 1410 } 1411 } 1412 } 1413 if (v->fFirstEdgeBelow) { 1414 if (!v->fFirstEdgeAbove) { 1415 if (leftPoly && rightPoly) { 1416 if (leftPoly == rightPoly) { 1417 if (leftPoly->fTail && leftPoly->fTail->fSide == Poly::kLeft_Side) { 1418 leftPoly = new_poly(&polys, leftPoly->lastVertex(), 1419 leftPoly->fWinding, alloc); 1420 leftEnclosingEdge->fRightPoly = leftPoly; 1421 } else { 1422 rightPoly = new_poly(&polys, rightPoly->lastVertex(), 1423 rightPoly->fWinding, alloc); 1424 rightEnclosingEdge->fLeftPoly = rightPoly; 1425 } 1426 } 1427 Edge* join = alloc.make<Edge>(leftPoly->lastVertex(), v, 1, Edge::Type::kInner); 1428 leftPoly = leftPoly->addEdge(join, Poly::kRight_Side, alloc); 1429 rightPoly = rightPoly->addEdge(join, Poly::kLeft_Side, alloc); 1430 } 1431 } 1432 Edge* leftEdge = v->fFirstEdgeBelow; 1433 leftEdge->fLeftPoly = leftPoly; 1434 insert_edge(leftEdge, leftEnclosingEdge, &activeEdges); 1435 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge; 1436 rightEdge = rightEdge->fNextEdgeBelow) { 1437 insert_edge(rightEdge, leftEdge, &activeEdges); 1438 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWinding : 0; 1439 winding += leftEdge->fWinding; 1440 if (winding != 0) { 1441 Poly* poly = new_poly(&polys, v, winding, alloc); 1442 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; 1443 } 1444 leftEdge = rightEdge; 1445 } 1446 v->fLastEdgeBelow->fRightPoly = rightPoly; 1447 } 1448#if LOGGING_ENABLED 1449 LOG("\nactive edges:\n"); 1450 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { 1451 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, 1452 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1); 1453 } 1454#endif 1455 } 1456 return polys; 1457} 1458 1459void remove_non_boundary_edges(const VertexList& mesh, SkPath::FillType fillType, 1460 SkArenaAlloc& alloc) { 1461 LOG("removing non-boundary edges\n"); 1462 EdgeList activeEdges; 1463 for (Vertex* v = mesh.fHead; v != nullptr; v = v->fNext) { 1464 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1465 continue; 1466 } 1467 Edge* leftEnclosingEdge; 1468 Edge* rightEnclosingEdge; 1469 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1470 bool prevFilled = leftEnclosingEdge && 1471 apply_fill_type(fillType, leftEnclosingEdge->fWinding); 1472 for (Edge* e = v->fFirstEdgeAbove; e;) { 1473 Edge* next = e->fNextEdgeAbove; 1474 remove_edge(e, &activeEdges); 1475 bool filled = apply_fill_type(fillType, e->fWinding); 1476 if (filled == prevFilled) { 1477 disconnect(e); 1478 } 1479 prevFilled = filled; 1480 e = next; 1481 } 1482 Edge* prev = leftEnclosingEdge; 1483 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1484 if (prev) { 1485 e->fWinding += prev->fWinding; 1486 } 1487 insert_edge(e, prev, &activeEdges); 1488 prev = e; 1489 } 1490 } 1491} 1492 1493// Note: this is the normal to the edge, but not necessarily unit length. 1494void get_edge_normal(const Edge* e, SkVector* normal) { 1495 normal->set(SkDoubleToScalar(e->fLine.fA) * e->fWinding, 1496 SkDoubleToScalar(e->fLine.fB) * e->fWinding); 1497} 1498 1499// Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions 1500// and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to 1501// invert on stroking. 1502 1503void simplify_boundary(EdgeList* boundary, Comparator& c, SkArenaAlloc& alloc) { 1504 Edge* prevEdge = boundary->fTail; 1505 SkVector prevNormal; 1506 get_edge_normal(prevEdge, &prevNormal); 1507 for (Edge* e = boundary->fHead; e != nullptr;) { 1508 Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBottom; 1509 Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop; 1510 double dist = e->dist(prev->fPoint); 1511 SkVector normal; 1512 get_edge_normal(e, &normal); 1513 double denom = 0.0625f * e->fLine.magSq(); 1514 if (prevNormal.dot(normal) < 0.0 && (dist * dist) <= denom) { 1515 Edge* join = new_edge(prev, next, Edge::Type::kInner, c, alloc); 1516 insert_edge(join, e, boundary); 1517 remove_edge(prevEdge, boundary); 1518 remove_edge(e, boundary); 1519 if (join->fLeft && join->fRight) { 1520 prevEdge = join->fLeft; 1521 e = join; 1522 } else { 1523 prevEdge = boundary->fTail; 1524 e = boundary->fHead; // join->fLeft ? join->fLeft : join; 1525 } 1526 get_edge_normal(prevEdge, &prevNormal); 1527 } else { 1528 prevEdge = e; 1529 prevNormal = normal; 1530 e = e->fRight; 1531 } 1532 } 1533} 1534 1535void fix_inversions(Vertex* prev, Vertex* next, Edge* prevBisector, Edge* nextBisector, 1536 Edge* prevEdge, Comparator& c) { 1537 if (!prev || !next) { 1538 return; 1539 } 1540 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; 1541 SkPoint p; 1542 uint8_t alpha; 1543 if (winding != prevEdge->fWinding && prevBisector->intersect(*nextBisector, &p, &alpha)) { 1544 prev->fPoint = next->fPoint = p; 1545 prev->fAlpha = next->fAlpha = alpha; 1546 } 1547} 1548 1549// Stage 5d: Displace edges by half a pixel inward and outward along their normals. Intersect to 1550// find new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a 1551// new antialiased mesh from those vertices. 1552 1553void stroke_boundary(EdgeList* boundary, VertexList* innerMesh, VertexList* outerMesh, 1554 Comparator& c, SkArenaAlloc& alloc) { 1555 // A boundary with fewer than 3 edges is degenerate. 1556 if (!boundary->fHead || !boundary->fHead->fRight || !boundary->fHead->fRight->fRight) { 1557 return; 1558 } 1559 Edge* prevEdge = boundary->fTail; 1560 float radius = 0.5f; 1561 double offset = radius * sqrt(prevEdge->fLine.magSq()) * prevEdge->fWinding; 1562 Line prevInner(prevEdge->fLine); 1563 prevInner.fC -= offset; 1564 Line prevOuter(prevEdge->fLine); 1565 prevOuter.fC += offset; 1566 VertexList innerVertices; 1567 VertexList outerVertices; 1568 Edge* prevBisector = nullptr; 1569 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) { 1570 double offset = radius * sqrt(e->fLine.magSq()) * e->fWinding; 1571 Line inner(e->fLine); 1572 inner.fC -= offset; 1573 Line outer(e->fLine); 1574 outer.fC += offset; 1575 SkPoint innerPoint, outerPoint; 1576 if (prevInner.intersect(inner, &innerPoint) && 1577 prevOuter.intersect(outer, &outerPoint)) { 1578 Vertex* innerVertex = alloc.make<Vertex>(innerPoint, 255); 1579 Vertex* outerVertex = alloc.make<Vertex>(outerPoint, 0); 1580 Edge* bisector = new_edge(outerVertex, innerVertex, Edge::Type::kConnector, c, alloc); 1581 fix_inversions(innerVertices.fTail, innerVertex, prevBisector, bisector, prevEdge, c); 1582 fix_inversions(outerVertices.fTail, outerVertex, prevBisector, bisector, prevEdge, c); 1583 innerVertex->fPartner = outerVertex; 1584 outerVertex->fPartner = innerVertex; 1585 innerVertices.append(innerVertex); 1586 outerVertices.append(outerVertex); 1587 prevBisector = bisector; 1588 } 1589 prevInner = inner; 1590 prevOuter = outer; 1591 prevEdge = e; 1592 } 1593 1594 Vertex* innerVertex = innerVertices.fHead; 1595 Vertex* outerVertex = outerVertices.fHead; 1596 if (!innerVertex || !outerVertex) { 1597 return; 1598 } 1599 Edge* bisector = new_edge(outerVertices.fHead, innerVertices.fHead, Edge::Type::kConnector, c, 1600 alloc); 1601 fix_inversions(innerVertices.fTail, innerVertices.fHead, prevBisector, bisector, prevEdge, c); 1602 fix_inversions(outerVertices.fTail, outerVertices.fHead, prevBisector, bisector, prevEdge, c); 1603 Vertex* prevInnerVertex = innerVertices.fTail; 1604 Vertex* prevOuterVertex = outerVertices.fTail; 1605 while (innerVertex && outerVertex) { 1606 // Connect vertices into a quad mesh. Outer edges get default (1) winding. 1607 // Inner edges get -2 winding. This ensures that the interior is always filled 1608 // (-1 winding number for normal cases, 3 for thin features where the interior inverts). 1609 connect(prevOuterVertex, outerVertex, Edge::Type::kOuter, c, alloc); 1610 connect(prevInnerVertex, innerVertex, Edge::Type::kInner, c, alloc, -2); 1611 prevInnerVertex = innerVertex; 1612 prevOuterVertex = outerVertex; 1613 innerVertex = innerVertex->fNext; 1614 outerVertex = outerVertex->fNext; 1615 } 1616 innerMesh->append(innerVertices); 1617 outerMesh->append(outerVertices); 1618} 1619 1620void extract_boundary(EdgeList* boundary, Edge* e, SkPath::FillType fillType, SkArenaAlloc& alloc) { 1621 bool down = apply_fill_type(fillType, e->fWinding); 1622 while (e) { 1623 e->fWinding = down ? 1 : -1; 1624 Edge* next; 1625 boundary->append(e); 1626 if (down) { 1627 // Find outgoing edge, in clockwise order. 1628 if ((next = e->fNextEdgeAbove)) { 1629 down = false; 1630 } else if ((next = e->fBottom->fLastEdgeBelow)) { 1631 down = true; 1632 } else if ((next = e->fPrevEdgeAbove)) { 1633 down = false; 1634 } 1635 } else { 1636 // Find outgoing edge, in counter-clockwise order. 1637 if ((next = e->fPrevEdgeBelow)) { 1638 down = true; 1639 } else if ((next = e->fTop->fFirstEdgeAbove)) { 1640 down = false; 1641 } else if ((next = e->fNextEdgeBelow)) { 1642 down = true; 1643 } 1644 } 1645 disconnect(e); 1646 e = next; 1647 } 1648} 1649 1650// Stage 5b: Extract boundaries from mesh, simplify and stroke them into a new mesh. 1651 1652void extract_boundaries(const VertexList& inMesh, VertexList* innerVertices, 1653 VertexList* outerVertices, SkPath::FillType fillType, 1654 Comparator& c, SkArenaAlloc& alloc) { 1655 remove_non_boundary_edges(inMesh, fillType, alloc); 1656 for (Vertex* v = inMesh.fHead; v; v = v->fNext) { 1657 while (v->fFirstEdgeBelow) { 1658 EdgeList boundary; 1659 extract_boundary(&boundary, v->fFirstEdgeBelow, fillType, alloc); 1660 simplify_boundary(&boundary, c, alloc); 1661 stroke_boundary(&boundary, innerVertices, outerVertices, c, alloc); 1662 } 1663 } 1664} 1665 1666// This is a driver function that calls stages 2-5 in turn. 1667 1668void contours_to_mesh(VertexList* contours, int contourCnt, bool antialias, 1669 VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1670#if LOGGING_ENABLED 1671 for (int i = 0; i < contourCnt; ++i) { 1672 Vertex* v = contours[i].fHead; 1673 SkASSERT(v); 1674 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); 1675 for (v = v->fNext; v; v = v->fNext) { 1676 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); 1677 } 1678 } 1679#endif 1680 sanitize_contours(contours, contourCnt, antialias); 1681 build_edges(contours, contourCnt, mesh, c, alloc); 1682} 1683 1684void sort_mesh(VertexList* vertices, Comparator& c, SkArenaAlloc& alloc) { 1685 if (!vertices || !vertices->fHead) { 1686 return; 1687 } 1688 1689 // Sort vertices in Y (secondarily in X). 1690 if (c.fDirection == Comparator::Direction::kHorizontal) { 1691 merge_sort<sweep_lt_horiz>(vertices); 1692 } else { 1693 merge_sort<sweep_lt_vert>(vertices); 1694 } 1695#if LOGGING_ENABLED 1696 for (Vertex* v = vertices->fHead; v != nullptr; v = v->fNext) { 1697 static float gID = 0.0f; 1698 v->fID = gID++; 1699 } 1700#endif 1701} 1702 1703Poly* contours_to_polys(VertexList* contours, int contourCnt, SkPath::FillType fillType, 1704 const SkRect& pathBounds, bool antialias, VertexList* outerMesh, 1705 SkArenaAlloc& alloc) { 1706 Comparator c(pathBounds.width() > pathBounds.height() ? Comparator::Direction::kHorizontal 1707 : Comparator::Direction::kVertical); 1708 VertexList mesh; 1709 contours_to_mesh(contours, contourCnt, antialias, &mesh, c, alloc); 1710 sort_mesh(&mesh, c, alloc); 1711 merge_coincident_vertices(&mesh, c, alloc); 1712 simplify(mesh, c, alloc); 1713 if (antialias) { 1714 VertexList innerMesh; 1715 extract_boundaries(mesh, &innerMesh, outerMesh, fillType, c, alloc); 1716 sort_mesh(&innerMesh, c, alloc); 1717 sort_mesh(outerMesh, c, alloc); 1718 if (is_complex(innerMesh) || is_complex(*outerMesh)) { 1719 LOG("found complex mesh; taking slow path\n"); 1720 VertexList aaMesh; 1721 connect_partners(outerMesh, c, alloc); 1722 sorted_merge(&innerMesh, outerMesh, &aaMesh, c); 1723 merge_coincident_vertices(&aaMesh, c, alloc); 1724 simplify(aaMesh, c, alloc); 1725 outerMesh->fHead = outerMesh->fTail = nullptr; 1726 return tessellate(aaMesh, alloc); 1727 } else { 1728 LOG("no complex polygons; taking fast path\n"); 1729 merge_coincident_vertices(&innerMesh, c, alloc); 1730 return tessellate(innerMesh, alloc); 1731 } 1732 } else { 1733 return tessellate(mesh, alloc); 1734 } 1735} 1736 1737// Stage 6: Triangulate the monotone polygons into a vertex buffer. 1738void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, const AAParams* aaParams, 1739 void* data) { 1740 for (Poly* poly = polys; poly; poly = poly->fNext) { 1741 if (apply_fill_type(fillType, poly)) { 1742 data = poly->emit(aaParams, data); 1743 } 1744 } 1745 return data; 1746} 1747 1748Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 1749 int contourCnt, SkArenaAlloc& alloc, bool antialias, bool* isLinear, 1750 VertexList* outerMesh) { 1751 SkPath::FillType fillType = path.getFillType(); 1752 if (SkPath::IsInverseFillType(fillType)) { 1753 contourCnt++; 1754 } 1755 std::unique_ptr<VertexList[]> contours(new VertexList[contourCnt]); 1756 1757 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinear); 1758 return contours_to_polys(contours.get(), contourCnt, path.getFillType(), path.getBounds(), 1759 antialias, outerMesh, alloc); 1760} 1761 1762int get_contour_count(const SkPath& path, SkScalar tolerance) { 1763 int contourCnt; 1764 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tolerance); 1765 if (maxPts <= 0) { 1766 return 0; 1767 } 1768 if (maxPts > ((int)SK_MaxU16 + 1)) { 1769 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); 1770 return 0; 1771 } 1772 return contourCnt; 1773} 1774 1775int count_points(Poly* polys, SkPath::FillType fillType) { 1776 int count = 0; 1777 for (Poly* poly = polys; poly; poly = poly->fNext) { 1778 if (apply_fill_type(fillType, poly) && poly->fCount >= 3) { 1779 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3); 1780 } 1781 } 1782 return count; 1783} 1784 1785int count_outer_mesh_points(const VertexList& outerMesh) { 1786 int count = 0; 1787 for (Vertex* v = outerMesh.fHead; v; v = v->fNext) { 1788 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1789 count += TESSELLATOR_WIREFRAME ? 12 : 6; 1790 } 1791 } 1792 return count; 1793} 1794 1795void* outer_mesh_to_triangles(const VertexList& outerMesh, const AAParams* aaParams, void* data) { 1796 for (Vertex* v = outerMesh.fHead; v; v = v->fNext) { 1797 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1798 Vertex* v0 = e->fTop; 1799 Vertex* v1 = e->fBottom; 1800 Vertex* v2 = e->fBottom->fPartner; 1801 Vertex* v3 = e->fTop->fPartner; 1802 data = emit_triangle(v0, v1, v2, aaParams, data); 1803 data = emit_triangle(v0, v2, v3, aaParams, data); 1804 } 1805 } 1806 return data; 1807} 1808 1809} // namespace 1810 1811namespace GrTessellator { 1812 1813// Stage 6: Triangulate the monotone polygons into a vertex buffer. 1814 1815int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 1816 VertexAllocator* vertexAllocator, bool antialias, const GrColor& color, 1817 bool canTweakAlphaForCoverage, bool* isLinear) { 1818 int contourCnt = get_contour_count(path, tolerance); 1819 if (contourCnt <= 0) { 1820 *isLinear = true; 1821 return 0; 1822 } 1823 SkArenaAlloc alloc(kArenaChunkSize); 1824 VertexList outerMesh; 1825 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, antialias, 1826 isLinear, &outerMesh); 1827 SkPath::FillType fillType = antialias ? SkPath::kWinding_FillType : path.getFillType(); 1828 int count = count_points(polys, fillType); 1829 if (0 == count) { 1830 return 0; 1831 } 1832 if (antialias) { 1833 count += count_outer_mesh_points(outerMesh); 1834 } 1835 1836 void* verts = vertexAllocator->lock(count); 1837 if (!verts) { 1838 SkDebugf("Could not allocate vertices\n"); 1839 return 0; 1840 } 1841 1842 LOG("emitting %d verts\n", count); 1843 AAParams aaParams; 1844 aaParams.fTweakAlpha = canTweakAlphaForCoverage; 1845 aaParams.fColor = color; 1846 1847 void* end = polys_to_triangles(polys, fillType, antialias ? &aaParams : nullptr, verts); 1848 end = outer_mesh_to_triangles(outerMesh, &aaParams, end); 1849 int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast<uint8_t*>(verts)) 1850 / vertexAllocator->stride()); 1851 SkASSERT(actualCount <= count); 1852 vertexAllocator->unlock(actualCount); 1853 return actualCount; 1854} 1855 1856int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 1857 GrTessellator::WindingVertex** verts) { 1858 int contourCnt = get_contour_count(path, tolerance); 1859 if (contourCnt <= 0) { 1860 return 0; 1861 } 1862 SkArenaAlloc alloc(kArenaChunkSize); 1863 bool isLinear; 1864 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, false, &isLinear, 1865 nullptr); 1866 SkPath::FillType fillType = path.getFillType(); 1867 int count = count_points(polys, fillType); 1868 if (0 == count) { 1869 *verts = nullptr; 1870 return 0; 1871 } 1872 1873 *verts = new GrTessellator::WindingVertex[count]; 1874 GrTessellator::WindingVertex* vertsEnd = *verts; 1875 SkPoint* points = new SkPoint[count]; 1876 SkPoint* pointsEnd = points; 1877 for (Poly* poly = polys; poly; poly = poly->fNext) { 1878 if (apply_fill_type(fillType, poly)) { 1879 SkPoint* start = pointsEnd; 1880 pointsEnd = static_cast<SkPoint*>(poly->emit(nullptr, pointsEnd)); 1881 while (start != pointsEnd) { 1882 vertsEnd->fPos = *start; 1883 vertsEnd->fWinding = poly->fWinding; 1884 ++start; 1885 ++vertsEnd; 1886 } 1887 } 1888 } 1889 int actualCount = static_cast<int>(vertsEnd - *verts); 1890 SkASSERT(actualCount <= count); 1891 SkASSERT(pointsEnd - points == actualCount); 1892 delete[] points; 1893 return actualCount; 1894} 1895 1896} // namespace 1897