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 #include "SkPointPriv.h" 17 #include "SkTDPQueue.h" 18 19 #include <algorithm> 20 #include <stdio.h> 21 22 /* 23 * There are six stages to the basic algorithm: 24 * 25 * 1) Linearize the path contours into piecewise linear segments (path_to_contours()). 26 * 2) Build a mesh of edges connecting the vertices (build_edges()). 27 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). 28 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplify()). 29 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). 30 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_triangles()). 31 * 32 * For screenspace antialiasing, the algorithm is modified as follows: 33 * 34 * Run steps 1-5 above to produce polygons. 35 * 5b) Apply fill rules to extract boundary contours from the polygons (extract_boundaries()). 36 * 5c) Simplify boundaries to remove "pointy" vertices that cause inversions (simplify_boundary()). 37 * 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find 38 * new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a new 39 * antialiased mesh from those vertices (stroke_boundary()). 40 * Run steps 3-6 above on the new mesh, and produce antialiased triangles. 41 * 42 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list 43 * of vertices (and the necessity of inserting new vertices on intersection). 44 * 45 * Stages (4) and (5) use an active edge list -- a list of all edges for which the 46 * sweep line has crossed the top vertex, but not the bottom vertex. It's sorted 47 * left-to-right based on the point where both edges are active (when both top vertices 48 * have been seen, so the "lower" top vertex of the two). If the top vertices are equal 49 * (shared), it's sorted based on the last point where both edges are active, so the 50 * "upper" bottom vertex. 51 * 52 * The most complex step is the simplification (4). It's based on the Bentley-Ottman 53 * line-sweep algorithm, but due to floating point inaccuracy, the intersection points are 54 * not exact and may violate the mesh topology or active edge list ordering. We 55 * accommodate this by adjusting the topology of the mesh and AEL to match the intersection 56 * points. This occurs in two ways: 57 * 58 * A) Intersections may cause a shortened edge to no longer be ordered with respect to its 59 * neighbouring edges at the top or bottom vertex. This is handled by merging the 60 * edges (merge_collinear_edges()). 61 * B) Intersections may cause an edge to violate the left-to-right ordering of the 62 * active edge list. This is handled by detecting potential violations and rewinding 63 * the active edge list to the vertex before they occur (rewind() during merging, 64 * rewind_if_necessary() during splitting). 65 * 66 * The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and 67 * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it 68 * currently uses a linked list for the active edge list, rather than a 2-3 tree as the 69 * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also 70 * become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N) 71 * insertions and removals was greater than the cost of infrequent O(N) lookups with the 72 * linked list implementation. With the latter, all removals are O(1), and most insertions 73 * are O(1), since we know the adjacent edge in the active edge list based on the topology. 74 * Only type 2 vertices (see paper) require the O(N) lookups, and these are much less 75 * frequent. There may be other data structures worth investigating, however. 76 * 77 * Note that the orientation of the line sweep algorithms is determined by the aspect ratio of the 78 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y 79 * coordinate, and secondarily by increasing X coordinate. When the path is wider than it is tall, 80 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordinate. This is so 81 * that the "left" and "right" orientation in the code remains correct (edges to the left are 82 * increasing in Y; edges to the right are decreasing in Y). That is, the setting rotates 90 83 * degrees counterclockwise, rather that transposing. 84 */ 85 86 #define LOGGING_ENABLED 0 87 88 #if LOGGING_ENABLED 89 #define LOG printf 90 #else 91 #define LOG(...) 92 #endif 93 94 namespace { 95 96 const int kArenaChunkSize = 16 * 1024; 97 #ifndef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 98 const float kCosMiterAngle = 0.97f; // Corresponds to an angle of ~14 degrees. 99 #endif 100 101 struct Vertex; 102 struct Edge; 103 struct Event; 104 struct Poly; 105 106 template <class T, T* T::*Prev, T* T::*Next> 107 void list_insert(T* t, T* prev, T* next, T** head, T** tail) { 108 t->*Prev = prev; 109 t->*Next = next; 110 if (prev) { 111 prev->*Next = t; 112 } else if (head) { 113 *head = t; 114 } 115 if (next) { 116 next->*Prev = t; 117 } else if (tail) { 118 *tail = t; 119 } 120 } 121 122 template <class T, T* T::*Prev, T* T::*Next> 123 void list_remove(T* t, T** head, T** tail) { 124 if (t->*Prev) { 125 t->*Prev->*Next = t->*Next; 126 } else if (head) { 127 *head = t->*Next; 128 } 129 if (t->*Next) { 130 t->*Next->*Prev = t->*Prev; 131 } else if (tail) { 132 *tail = t->*Prev; 133 } 134 t->*Prev = t->*Next = nullptr; 135 } 136 137 /** 138 * Vertices are used in three ways: first, the path contours are converted into a 139 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices 140 * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing 141 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid 142 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of 143 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since 144 * an individual Vertex from the path mesh may belong to multiple 145 * MonotonePolys, so the original Vertices cannot be re-used. 146 */ 147 148 struct Vertex { 149 Vertex(const SkPoint& point, uint8_t alpha) 150 : fPoint(point), fPrev(nullptr), fNext(nullptr) 151 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) 152 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) 153 , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr) 154 , fPartner(nullptr) 155 , fAlpha(alpha) 156 #if LOGGING_ENABLED 157 , fID (-1.0f) 158 #endif 159 {} 160 SkPoint fPoint; // Vertex position 161 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices. 162 Vertex* fNext; // " 163 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. 164 Edge* fLastEdgeAbove; // " 165 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. 166 Edge* fLastEdgeBelow; // " 167 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex. 168 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex. 169 Vertex* fPartner; // Corresponding inner or outer vertex (for AA). 170 uint8_t fAlpha; 171 #if LOGGING_ENABLED 172 float fID; // Identifier used for logging. 173 #endif 174 }; 175 176 /***************************************************************************************/ 177 178 struct AAParams { 179 bool fTweakAlpha; 180 GrColor fColor; 181 }; 182 183 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b); 184 185 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { 186 return a.fX < b.fX || (a.fX == b.fX && a.fY > b.fY); 187 } 188 189 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { 190 return a.fY < b.fY || (a.fY == b.fY && a.fX < b.fX); 191 } 192 193 struct Comparator { 194 enum class Direction { kVertical, kHorizontal }; 195 Comparator(Direction direction) : fDirection(direction) {} 196 bool sweep_lt(const SkPoint& a, const SkPoint& b) const { 197 return fDirection == Direction::kHorizontal ? sweep_lt_horiz(a, b) : sweep_lt_vert(a, b); 198 } 199 Direction fDirection; 200 }; 201 202 inline void* emit_vertex(Vertex* v, const AAParams* aaParams, void* data) { 203 if (!aaParams) { 204 SkPoint* d = static_cast<SkPoint*>(data); 205 *d++ = v->fPoint; 206 return d; 207 } 208 if (aaParams->fTweakAlpha) { 209 auto d = static_cast<GrDefaultGeoProcFactory::PositionColorAttr*>(data); 210 d->fPosition = v->fPoint; 211 d->fColor = SkAlphaMulQ(aaParams->fColor, SkAlpha255To256(v->fAlpha)); 212 d++; 213 return d; 214 } 215 auto d = static_cast<GrDefaultGeoProcFactory::PositionColorCoverageAttr*>(data); 216 d->fPosition = v->fPoint; 217 d->fColor = aaParams->fColor; 218 d->fCoverage = GrNormalizeByteToFloat(v->fAlpha); 219 d++; 220 return d; 221 } 222 223 void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, const AAParams* aaParams, void* data) { 224 LOG("emit_triangle %g (%g, %g) %d\n", v0->fID, v0->fPoint.fX, v0->fPoint.fY, v0->fAlpha); 225 LOG(" %g (%g, %g) %d\n", v1->fID, v1->fPoint.fX, v1->fPoint.fY, v1->fAlpha); 226 LOG(" %g (%g, %g) %d\n", v2->fID, v2->fPoint.fX, v2->fPoint.fY, v2->fAlpha); 227 #if TESSELLATOR_WIREFRAME 228 data = emit_vertex(v0, aaParams, data); 229 data = emit_vertex(v1, aaParams, data); 230 data = emit_vertex(v1, aaParams, data); 231 data = emit_vertex(v2, aaParams, data); 232 data = emit_vertex(v2, aaParams, data); 233 data = emit_vertex(v0, aaParams, data); 234 #else 235 data = emit_vertex(v0, aaParams, data); 236 data = emit_vertex(v1, aaParams, data); 237 data = emit_vertex(v2, aaParams, data); 238 #endif 239 return data; 240 } 241 242 struct VertexList { 243 VertexList() : fHead(nullptr), fTail(nullptr) {} 244 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {} 245 Vertex* fHead; 246 Vertex* fTail; 247 void insert(Vertex* v, Vertex* prev, Vertex* next) { 248 list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail); 249 } 250 void append(Vertex* v) { 251 insert(v, fTail, nullptr); 252 } 253 void append(const VertexList& list) { 254 if (!list.fHead) { 255 return; 256 } 257 if (fTail) { 258 fTail->fNext = list.fHead; 259 list.fHead->fPrev = fTail; 260 } else { 261 fHead = list.fHead; 262 } 263 fTail = list.fTail; 264 } 265 void prepend(Vertex* v) { 266 insert(v, nullptr, fHead); 267 } 268 void remove(Vertex* v) { 269 list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, &fHead, &fTail); 270 } 271 void close() { 272 if (fHead && fTail) { 273 fTail->fNext = fHead; 274 fHead->fPrev = fTail; 275 } 276 } 277 }; 278 279 // Round to nearest quarter-pixel. This is used for screenspace tessellation. 280 281 inline void round(SkPoint* p) { 282 p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f); 283 p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f); 284 } 285 286 inline SkScalar double_to_clamped_scalar(double d) { 287 return SkDoubleToScalar(std::min((double) SK_ScalarMax, std::max(d, (double) -SK_ScalarMax))); 288 } 289 290 // A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line. 291 struct Line { 292 Line(double a, double b, double c) : fA(a), fB(b), fC(c) {} 293 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {} 294 Line(const SkPoint& p, const SkPoint& q) 295 : fA(static_cast<double>(q.fY) - p.fY) // a = dY 296 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX 297 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p) 298 static_cast<double>(p.fX) * q.fY) {} 299 double dist(const SkPoint& p) const { 300 return fA * p.fX + fB * p.fY + fC; 301 } 302 Line operator*(double v) const { 303 return Line(fA * v, fB * v, fC * v); 304 } 305 double magSq() const { 306 return fA * fA + fB * fB; 307 } 308 void normalize() { 309 double len = sqrt(this->magSq()); 310 if (len == 0.0) { 311 return; 312 } 313 double scale = 1.0f / len; 314 fA *= scale; 315 fB *= scale; 316 fC *= scale; 317 } 318 bool nearParallel(const Line& o) const { 319 return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001; 320 } 321 322 // Compute the intersection of two (infinite) Lines. 323 bool intersect(const Line& other, SkPoint* point) const { 324 double denom = fA * other.fB - fB * other.fA; 325 if (denom == 0.0) { 326 return false; 327 } 328 double scale = 1.0 / denom; 329 point->fX = double_to_clamped_scalar((fB * other.fC - other.fB * fC) * scale); 330 point->fY = double_to_clamped_scalar((other.fA * fC - fA * other.fC) * scale); 331 round(point); 332 return true; 333 } 334 double fA, fB, fC; 335 }; 336 337 /** 338 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and 339 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf(). 340 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating 341 * point). For speed, that case is only tested by the callers that require it (e.g., 342 * rewind_if_necessary()). Edges also handle checking for intersection with other edges. 343 * Currently, this converts the edges to the parametric form, in order to avoid doing a division 344 * until an intersection has been confirmed. This is slightly slower in the "found" case, but 345 * a lot faster in the "not found" case. 346 * 347 * The coefficients of the line equation stored in double precision to avoid catastrphic 348 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is 349 * correct in float, since it's a polynomial of degree 2. The intersect() function, being 350 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its 351 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of 352 * this file). 353 */ 354 355 struct Edge { 356 enum class Type { kInner, kOuter, kConnector }; 357 Edge(Vertex* top, Vertex* bottom, int winding, Type type) 358 : fWinding(winding) 359 , fTop(top) 360 , fBottom(bottom) 361 , fType(type) 362 , fLeft(nullptr) 363 , fRight(nullptr) 364 , fPrevEdgeAbove(nullptr) 365 , fNextEdgeAbove(nullptr) 366 , fPrevEdgeBelow(nullptr) 367 , fNextEdgeBelow(nullptr) 368 , fLeftPoly(nullptr) 369 , fRightPoly(nullptr) 370 , fEvent(nullptr) 371 , fLeftPolyPrev(nullptr) 372 , fLeftPolyNext(nullptr) 373 , fRightPolyPrev(nullptr) 374 , fRightPolyNext(nullptr) 375 , fOverlap(false) 376 , fUsedInLeftPoly(false) 377 , fUsedInRightPoly(false) 378 , fLine(top, bottom) { 379 } 380 int fWinding; // 1 == edge goes downward; -1 = edge goes upward. 381 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt). 382 Vertex* fBottom; // The bottom vertex in vertex-sort-order. 383 Type fType; 384 Edge* fLeft; // The linked list of edges in the active edge list. 385 Edge* fRight; // " 386 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above". 387 Edge* fNextEdgeAbove; // " 388 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below". 389 Edge* fNextEdgeBelow; // " 390 Poly* fLeftPoly; // The Poly to the left of this edge, if any. 391 Poly* fRightPoly; // The Poly to the right of this edge, if any. 392 Event* fEvent; 393 Edge* fLeftPolyPrev; 394 Edge* fLeftPolyNext; 395 Edge* fRightPolyPrev; 396 Edge* fRightPolyNext; 397 bool fOverlap; // True if there's an overlap region adjacent to this edge. 398 bool fUsedInLeftPoly; 399 bool fUsedInRightPoly; 400 Line fLine; 401 double dist(const SkPoint& p) const { 402 return fLine.dist(p); 403 } 404 bool isRightOf(Vertex* v) const { 405 return fLine.dist(v->fPoint) < 0.0; 406 } 407 bool isLeftOf(Vertex* v) const { 408 return fLine.dist(v->fPoint) > 0.0; 409 } 410 void recompute() { 411 fLine = Line(fTop, fBottom); 412 } 413 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const { 414 LOG("intersecting %g -> %g with %g -> %g\n", 415 fTop->fID, fBottom->fID, 416 other.fTop->fID, other.fBottom->fID); 417 if (fTop == other.fTop || fBottom == other.fBottom) { 418 return false; 419 } 420 double denom = fLine.fA * other.fLine.fB - fLine.fB * other.fLine.fA; 421 if (denom == 0.0) { 422 return false; 423 } 424 double dx = static_cast<double>(other.fTop->fPoint.fX) - fTop->fPoint.fX; 425 double dy = static_cast<double>(other.fTop->fPoint.fY) - fTop->fPoint.fY; 426 double sNumer = dy * other.fLine.fB + dx * other.fLine.fA; 427 double tNumer = dy * fLine.fB + dx * fLine.fA; 428 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. 429 // This saves us doing the divide below unless absolutely necessary. 430 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom) 431 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) { 432 return false; 433 } 434 double s = sNumer / denom; 435 SkASSERT(s >= 0.0 && s <= 1.0); 436 p->fX = SkDoubleToScalar(fTop->fPoint.fX - s * fLine.fB); 437 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fLine.fA); 438 if (alpha) { 439 if (fType == Type::kConnector) { 440 *alpha = (1.0 - s) * fTop->fAlpha + s * fBottom->fAlpha; 441 } else if (other.fType == Type::kConnector) { 442 double t = tNumer / denom; 443 *alpha = (1.0 - t) * other.fTop->fAlpha + t * other.fBottom->fAlpha; 444 } else if (fType == Type::kOuter && other.fType == Type::kOuter) { 445 *alpha = 0; 446 } else { 447 *alpha = 255; 448 } 449 } 450 return true; 451 } 452 }; 453 454 struct EdgeList { 455 EdgeList() : fHead(nullptr), fTail(nullptr) {} 456 Edge* fHead; 457 Edge* fTail; 458 void insert(Edge* edge, Edge* prev, Edge* next) { 459 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail); 460 } 461 void append(Edge* e) { 462 insert(e, fTail, nullptr); 463 } 464 void remove(Edge* edge) { 465 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail); 466 } 467 void removeAll() { 468 while (fHead) { 469 this->remove(fHead); 470 } 471 } 472 void close() { 473 if (fHead && fTail) { 474 fTail->fRight = fHead; 475 fHead->fLeft = fTail; 476 } 477 } 478 bool contains(Edge* edge) const { 479 return edge->fLeft || edge->fRight || fHead == edge; 480 } 481 }; 482 483 #ifndef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 484 struct Event { 485 Event(Edge* edge, const SkPoint& point, uint8_t alpha) 486 : fEdge(edge), fPoint(point), fAlpha(alpha), fPrev(nullptr), fNext(nullptr) { 487 } 488 Edge* fEdge; 489 SkPoint fPoint; 490 uint8_t fAlpha; 491 Event* fPrev; 492 Event* fNext; 493 void apply(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc); 494 }; 495 496 bool compare(Event* const& e1, Event* const& e2) { 497 return e1->fAlpha > e2->fAlpha; 498 } 499 500 struct EventList : public SkTDPQueue<Event*, &compare> {}; 501 502 void create_event(Edge* e, EventList* events, SkArenaAlloc& alloc) { 503 Edge bisector1(e->fTop, e->fTop->fPartner, 1, Edge::Type::kConnector); 504 Edge bisector2(e->fBottom, e->fBottom->fPartner, 1, Edge::Type::kConnector); 505 SkPoint p; 506 uint8_t alpha; 507 if (bisector1.intersect(bisector2, &p, &alpha)) { 508 LOG("found overlap edge %g -> %g, will collapse to %g,%g alpha %d\n", 509 e->fTop->fID, e->fBottom->fID, p.fX, p.fY, alpha); 510 e->fEvent = alloc.make<Event>(e, p, alpha); 511 events->insert(e->fEvent); 512 } 513 } 514 #endif 515 516 /***************************************************************************************/ 517 518 struct Poly { 519 Poly(Vertex* v, int winding) 520 : fFirstVertex(v) 521 , fWinding(winding) 522 , fHead(nullptr) 523 , fTail(nullptr) 524 , fNext(nullptr) 525 , fPartner(nullptr) 526 , fCount(0) 527 { 528 #if LOGGING_ENABLED 529 static int gID = 0; 530 fID = gID++; 531 LOG("*** created Poly %d\n", fID); 532 #endif 533 } 534 typedef enum { kLeft_Side, kRight_Side } Side; 535 struct MonotonePoly { 536 MonotonePoly(Edge* edge, Side side) 537 : fSide(side) 538 , fFirstEdge(nullptr) 539 , fLastEdge(nullptr) 540 , fPrev(nullptr) 541 , fNext(nullptr) { 542 this->addEdge(edge); 543 } 544 Side fSide; 545 Edge* fFirstEdge; 546 Edge* fLastEdge; 547 MonotonePoly* fPrev; 548 MonotonePoly* fNext; 549 void addEdge(Edge* edge) { 550 if (fSide == kRight_Side) { 551 SkASSERT(!edge->fUsedInRightPoly); 552 list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>( 553 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge); 554 edge->fUsedInRightPoly = true; 555 } else { 556 SkASSERT(!edge->fUsedInLeftPoly); 557 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>( 558 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge); 559 edge->fUsedInLeftPoly = true; 560 } 561 } 562 563 void* emit(const AAParams* aaParams, void* data) { 564 Edge* e = fFirstEdge; 565 VertexList vertices; 566 vertices.append(e->fTop); 567 int count = 1; 568 while (e != nullptr) { 569 if (kRight_Side == fSide) { 570 vertices.append(e->fBottom); 571 e = e->fRightPolyNext; 572 } else { 573 vertices.prepend(e->fBottom); 574 e = e->fLeftPolyNext; 575 } 576 count++; 577 } 578 Vertex* first = vertices.fHead; 579 Vertex* v = first->fNext; 580 while (v != vertices.fTail) { 581 SkASSERT(v && v->fPrev && v->fNext); 582 Vertex* prev = v->fPrev; 583 Vertex* curr = v; 584 Vertex* next = v->fNext; 585 if (count == 3) { 586 return emit_triangle(prev, curr, next, aaParams, data); 587 } 588 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX; 589 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY; 590 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX; 591 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY; 592 if (ax * by - ay * bx >= 0.0) { 593 data = emit_triangle(prev, curr, next, aaParams, data); 594 v->fPrev->fNext = v->fNext; 595 v->fNext->fPrev = v->fPrev; 596 count--; 597 if (v->fPrev == first) { 598 v = v->fNext; 599 } else { 600 v = v->fPrev; 601 } 602 } else { 603 v = v->fNext; 604 } 605 } 606 return data; 607 } 608 }; 609 Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc) { 610 LOG("addEdge (%g -> %g) to poly %d, %s side\n", 611 e->fTop->fID, e->fBottom->fID, fID, side == kLeft_Side ? "left" : "right"); 612 Poly* partner = fPartner; 613 Poly* poly = this; 614 if (side == kRight_Side) { 615 if (e->fUsedInRightPoly) { 616 return this; 617 } 618 } else { 619 if (e->fUsedInLeftPoly) { 620 return this; 621 } 622 } 623 if (partner) { 624 fPartner = partner->fPartner = nullptr; 625 } 626 if (!fTail) { 627 fHead = fTail = alloc.make<MonotonePoly>(e, side); 628 fCount += 2; 629 } else if (e->fBottom == fTail->fLastEdge->fBottom) { 630 return poly; 631 } else if (side == fTail->fSide) { 632 fTail->addEdge(e); 633 fCount++; 634 } else { 635 e = alloc.make<Edge>(fTail->fLastEdge->fBottom, e->fBottom, 1, Edge::Type::kInner); 636 fTail->addEdge(e); 637 fCount++; 638 if (partner) { 639 partner->addEdge(e, side, alloc); 640 poly = partner; 641 } else { 642 MonotonePoly* m = alloc.make<MonotonePoly>(e, side); 643 m->fPrev = fTail; 644 fTail->fNext = m; 645 fTail = m; 646 } 647 } 648 return poly; 649 } 650 void* emit(const AAParams* aaParams, void *data) { 651 if (fCount < 3) { 652 return data; 653 } 654 LOG("emit() %d, size %d\n", fID, fCount); 655 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { 656 data = m->emit(aaParams, data); 657 } 658 return data; 659 } 660 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; } 661 Vertex* fFirstVertex; 662 int fWinding; 663 MonotonePoly* fHead; 664 MonotonePoly* fTail; 665 Poly* fNext; 666 Poly* fPartner; 667 int fCount; 668 #if LOGGING_ENABLED 669 int fID; 670 #endif 671 }; 672 673 /***************************************************************************************/ 674 675 bool coincident(const SkPoint& a, const SkPoint& b) { 676 return a == b; 677 } 678 679 Poly* new_poly(Poly** head, Vertex* v, int winding, SkArenaAlloc& alloc) { 680 Poly* poly = alloc.make<Poly>(v, winding); 681 poly->fNext = *head; 682 *head = poly; 683 return poly; 684 } 685 686 void append_point_to_contour(const SkPoint& p, VertexList* contour, SkArenaAlloc& alloc) { 687 Vertex* v = alloc.make<Vertex>(p, 255); 688 #if LOGGING_ENABLED 689 static float gID = 0.0f; 690 v->fID = gID++; 691 #endif 692 contour->append(v); 693 } 694 695 SkScalar quad_error_at(const SkPoint pts[3], SkScalar t, SkScalar u) { 696 SkQuadCoeff quad(pts); 697 SkPoint p0 = to_point(quad.eval(t - 0.5f * u)); 698 SkPoint mid = to_point(quad.eval(t)); 699 SkPoint p1 = to_point(quad.eval(t + 0.5f * u)); 700 if (!p0.isFinite() || !mid.isFinite() || !p1.isFinite()) { 701 return 0; 702 } 703 return SkPointPriv::DistanceToLineSegmentBetweenSqd(mid, p0, p1); 704 } 705 706 void append_quadratic_to_contour(const SkPoint pts[3], SkScalar toleranceSqd, VertexList* contour, 707 SkArenaAlloc& alloc) { 708 SkQuadCoeff quad(pts); 709 Sk2s aa = quad.fA * quad.fA; 710 SkScalar denom = 2.0f * (aa[0] + aa[1]); 711 Sk2s ab = quad.fA * quad.fB; 712 SkScalar t = denom ? (-ab[0] - ab[1]) / denom : 0.0f; 713 int nPoints = 1; 714 SkScalar u = 1.0f; 715 // Test possible subdivision values only at the point of maximum curvature. 716 // If it passes the flatness metric there, it'll pass everywhere. 717 while (nPoints < GrPathUtils::kMaxPointsPerCurve) { 718 u = 1.0f / nPoints; 719 if (quad_error_at(pts, t, u) < toleranceSqd) { 720 break; 721 } 722 nPoints++; 723 } 724 for (int j = 1; j <= nPoints; j++) { 725 append_point_to_contour(to_point(quad.eval(j * u)), contour, alloc); 726 } 727 } 728 729 void generate_cubic_points(const SkPoint& p0, 730 const SkPoint& p1, 731 const SkPoint& p2, 732 const SkPoint& p3, 733 SkScalar tolSqd, 734 VertexList* contour, 735 int pointsLeft, 736 SkArenaAlloc& alloc) { 737 SkScalar d1 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3); 738 SkScalar d2 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3); 739 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || 740 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) { 741 append_point_to_contour(p3, contour, alloc); 742 return; 743 } 744 const SkPoint q[] = { 745 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, 746 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, 747 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } 748 }; 749 const SkPoint r[] = { 750 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, 751 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } 752 }; 753 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) }; 754 pointsLeft >>= 1; 755 generate_cubic_points(p0, q[0], r[0], s, tolSqd, contour, pointsLeft, alloc); 756 generate_cubic_points(s, r[1], q[2], p3, tolSqd, contour, pointsLeft, alloc); 757 } 758 759 // Stage 1: convert the input path to a set of linear contours (linked list of Vertices). 760 761 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 762 VertexList* contours, SkArenaAlloc& alloc, bool *isLinear) { 763 SkScalar toleranceSqd = tolerance * tolerance; 764 765 SkPoint pts[4]; 766 *isLinear = true; 767 VertexList* contour = contours; 768 SkPath::Iter iter(path, false); 769 if (path.isInverseFillType()) { 770 SkPoint quad[4]; 771 clipBounds.toQuad(quad); 772 for (int i = 3; i >= 0; i--) { 773 append_point_to_contour(quad[i], contours, alloc); 774 } 775 contour++; 776 } 777 SkAutoConicToQuads converter; 778 SkPath::Verb verb; 779 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 780 switch (verb) { 781 case SkPath::kConic_Verb: { 782 SkScalar weight = iter.conicWeight(); 783 const SkPoint* quadPts = converter.computeQuads(pts, weight, toleranceSqd); 784 for (int i = 0; i < converter.countQuads(); ++i) { 785 append_quadratic_to_contour(quadPts, toleranceSqd, contour, alloc); 786 quadPts += 2; 787 } 788 *isLinear = false; 789 break; 790 } 791 case SkPath::kMove_Verb: 792 if (contour->fHead) { 793 contour++; 794 } 795 append_point_to_contour(pts[0], contour, alloc); 796 break; 797 case SkPath::kLine_Verb: { 798 append_point_to_contour(pts[1], contour, alloc); 799 break; 800 } 801 case SkPath::kQuad_Verb: { 802 append_quadratic_to_contour(pts, toleranceSqd, contour, alloc); 803 *isLinear = false; 804 break; 805 } 806 case SkPath::kCubic_Verb: { 807 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance); 808 generate_cubic_points(pts[0], pts[1], pts[2], pts[3], toleranceSqd, contour, 809 pointsLeft, alloc); 810 *isLinear = false; 811 break; 812 } 813 case SkPath::kClose_Verb: 814 case SkPath::kDone_Verb: 815 break; 816 } 817 } 818 } 819 820 inline bool apply_fill_type(SkPath::FillType fillType, int winding) { 821 switch (fillType) { 822 case SkPath::kWinding_FillType: 823 return winding != 0; 824 case SkPath::kEvenOdd_FillType: 825 return (winding & 1) != 0; 826 case SkPath::kInverseWinding_FillType: 827 return winding == 1; 828 case SkPath::kInverseEvenOdd_FillType: 829 return (winding & 1) == 1; 830 default: 831 SkASSERT(false); 832 return false; 833 } 834 } 835 836 inline bool apply_fill_type(SkPath::FillType fillType, Poly* poly) { 837 return poly && apply_fill_type(fillType, poly->fWinding); 838 } 839 840 Edge* new_edge(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc) { 841 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; 842 Vertex* top = winding < 0 ? next : prev; 843 Vertex* bottom = winding < 0 ? prev : next; 844 return alloc.make<Edge>(top, bottom, winding, type); 845 } 846 847 void remove_edge(Edge* edge, EdgeList* edges) { 848 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); 849 SkASSERT(edges->contains(edge)); 850 edges->remove(edge); 851 } 852 853 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) { 854 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); 855 SkASSERT(!edges->contains(edge)); 856 Edge* next = prev ? prev->fRight : edges->fHead; 857 edges->insert(edge, prev, next); 858 } 859 860 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) { 861 if (v->fFirstEdgeAbove && v->fLastEdgeAbove) { 862 *left = v->fFirstEdgeAbove->fLeft; 863 *right = v->fLastEdgeAbove->fRight; 864 return; 865 } 866 Edge* next = nullptr; 867 Edge* prev; 868 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { 869 if (prev->isLeftOf(v)) { 870 break; 871 } 872 next = prev; 873 } 874 *left = prev; 875 *right = next; 876 } 877 878 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { 879 if (edge->fTop->fPoint == edge->fBottom->fPoint || 880 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) { 881 return; 882 } 883 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID); 884 Edge* prev = nullptr; 885 Edge* next; 886 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { 887 if (next->isRightOf(edge->fTop)) { 888 break; 889 } 890 prev = next; 891 } 892 list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( 893 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); 894 } 895 896 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { 897 if (edge->fTop->fPoint == edge->fBottom->fPoint || 898 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) { 899 return; 900 } 901 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID); 902 Edge* prev = nullptr; 903 Edge* next; 904 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { 905 if (next->isRightOf(edge->fBottom)) { 906 break; 907 } 908 prev = next; 909 } 910 list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( 911 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow); 912 } 913 914 void remove_edge_above(Edge* edge) { 915 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, 916 edge->fBottom->fID); 917 list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( 918 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove); 919 } 920 921 void remove_edge_below(Edge* edge) { 922 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, 923 edge->fTop->fID); 924 list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( 925 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow); 926 } 927 928 void disconnect(Edge* edge) 929 { 930 remove_edge_above(edge); 931 remove_edge_below(edge); 932 } 933 934 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c); 935 936 void rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, Comparator& c) { 937 if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) { 938 return; 939 } 940 Vertex* v = *current; 941 LOG("rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID); 942 while (v != dst) { 943 v = v->fPrev; 944 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 945 remove_edge(e, activeEdges); 946 } 947 Edge* leftEdge = v->fLeftEnclosingEdge; 948 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 949 insert_edge(e, leftEdge, activeEdges); 950 leftEdge = e; 951 } 952 } 953 *current = v; 954 } 955 956 void rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) { 957 if (!activeEdges || !current) { 958 return; 959 } 960 Vertex* top = edge->fTop; 961 Vertex* bottom = edge->fBottom; 962 if (edge->fLeft) { 963 Vertex* leftTop = edge->fLeft->fTop; 964 Vertex* leftBottom = edge->fLeft->fBottom; 965 if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) { 966 rewind(activeEdges, current, leftTop, c); 967 } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) { 968 rewind(activeEdges, current, top, c); 969 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && 970 !edge->fLeft->isLeftOf(bottom)) { 971 rewind(activeEdges, current, leftTop, c); 972 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) { 973 rewind(activeEdges, current, top, c); 974 } 975 } 976 if (edge->fRight) { 977 Vertex* rightTop = edge->fRight->fTop; 978 Vertex* rightBottom = edge->fRight->fBottom; 979 if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) { 980 rewind(activeEdges, current, rightTop, c); 981 } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) { 982 rewind(activeEdges, current, top, c); 983 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && 984 !edge->fRight->isRightOf(bottom)) { 985 rewind(activeEdges, current, rightTop, c); 986 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && 987 !edge->isLeftOf(rightBottom)) { 988 rewind(activeEdges, current, top, c); 989 } 990 } 991 } 992 993 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) { 994 remove_edge_below(edge); 995 edge->fTop = v; 996 edge->recompute(); 997 insert_edge_below(edge, v, c); 998 rewind_if_necessary(edge, activeEdges, current, c); 999 merge_collinear_edges(edge, activeEdges, current, c); 1000 } 1001 1002 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) { 1003 remove_edge_above(edge); 1004 edge->fBottom = v; 1005 edge->recompute(); 1006 insert_edge_above(edge, v, c); 1007 rewind_if_necessary(edge, activeEdges, current, c); 1008 merge_collinear_edges(edge, activeEdges, current, c); 1009 } 1010 1011 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, 1012 Comparator& c) { 1013 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { 1014 LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n", 1015 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY, 1016 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY); 1017 rewind(activeEdges, current, edge->fTop, c); 1018 other->fWinding += edge->fWinding; 1019 disconnect(edge); 1020 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) { 1021 rewind(activeEdges, current, edge->fTop, c); 1022 other->fWinding += edge->fWinding; 1023 set_bottom(edge, other->fTop, activeEdges, current, c); 1024 } else { 1025 rewind(activeEdges, current, other->fTop, c); 1026 edge->fWinding += other->fWinding; 1027 set_bottom(other, edge->fTop, activeEdges, current, c); 1028 } 1029 } 1030 1031 void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, 1032 Comparator& c) { 1033 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) { 1034 LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n", 1035 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY, 1036 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY); 1037 rewind(activeEdges, current, edge->fTop, c); 1038 other->fWinding += edge->fWinding; 1039 disconnect(edge); 1040 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) { 1041 rewind(activeEdges, current, other->fTop, c); 1042 edge->fWinding += other->fWinding; 1043 set_top(other, edge->fBottom, activeEdges, current, c); 1044 } else { 1045 rewind(activeEdges, current, edge->fTop, c); 1046 other->fWinding += edge->fWinding; 1047 set_top(edge, other->fBottom, activeEdges, current, c); 1048 } 1049 } 1050 1051 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) { 1052 for (;;) { 1053 if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop || 1054 !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) { 1055 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, current, c); 1056 } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop || 1057 !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) { 1058 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, current, c); 1059 } else if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom || 1060 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) { 1061 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, current, c); 1062 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom || 1063 !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) { 1064 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, current, c); 1065 } else { 1066 break; 1067 } 1068 } 1069 SkASSERT(!edge->fPrevEdgeAbove || edge->fPrevEdgeAbove->isLeftOf(edge->fTop)); 1070 SkASSERT(!edge->fPrevEdgeBelow || edge->fPrevEdgeBelow->isLeftOf(edge->fBottom)); 1071 SkASSERT(!edge->fNextEdgeAbove || edge->fNextEdgeAbove->isRightOf(edge->fTop)); 1072 SkASSERT(!edge->fNextEdgeBelow || edge->fNextEdgeBelow->isRightOf(edge->fBottom)); 1073 } 1074 1075 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c, 1076 SkArenaAlloc& alloc) { 1077 if (v == edge->fTop || v == edge->fBottom) { 1078 return; 1079 } 1080 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", 1081 edge->fTop->fID, edge->fBottom->fID, 1082 v->fID, v->fPoint.fX, v->fPoint.fY); 1083 Vertex* top; 1084 Vertex* bottom; 1085 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) { 1086 top = v; 1087 bottom = edge->fTop; 1088 set_top(edge, v, activeEdges, current, c); 1089 } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) { 1090 top = edge->fBottom; 1091 bottom = v; 1092 set_bottom(edge, v, activeEdges, current, c); 1093 } else { 1094 top = v; 1095 bottom = edge->fBottom; 1096 set_bottom(edge, v, activeEdges, current, c); 1097 } 1098 Edge* newEdge = alloc.make<Edge>(top, bottom, edge->fWinding, edge->fType); 1099 insert_edge_below(newEdge, top, c); 1100 insert_edge_above(newEdge, bottom, c); 1101 merge_collinear_edges(newEdge, activeEdges, current, c); 1102 } 1103 1104 Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc, 1105 int winding_scale = 1) { 1106 if (!prev || !next || prev->fPoint == next->fPoint) { 1107 return nullptr; 1108 } 1109 Edge* edge = new_edge(prev, next, type, c, alloc); 1110 insert_edge_below(edge, edge->fTop, c); 1111 insert_edge_above(edge, edge->fBottom, c); 1112 edge->fWinding *= winding_scale; 1113 merge_collinear_edges(edge, nullptr, nullptr, c); 1114 return edge; 1115 } 1116 1117 void merge_vertices(Vertex* src, Vertex* dst, VertexList* mesh, Comparator& c, 1118 SkArenaAlloc& alloc) { 1119 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX, src->fPoint.fY, 1120 src->fID, dst->fID); 1121 dst->fAlpha = SkTMax(src->fAlpha, dst->fAlpha); 1122 if (src->fPartner) { 1123 src->fPartner->fPartner = dst; 1124 } 1125 for (Edge* edge = src->fFirstEdgeAbove; edge;) { 1126 Edge* next = edge->fNextEdgeAbove; 1127 set_bottom(edge, dst, nullptr, nullptr, c); 1128 edge = next; 1129 } 1130 for (Edge* edge = src->fFirstEdgeBelow; edge;) { 1131 Edge* next = edge->fNextEdgeBelow; 1132 set_top(edge, dst, nullptr, nullptr, c); 1133 edge = next; 1134 } 1135 mesh->remove(src); 1136 } 1137 1138 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1139 uint8_t max_edge_alpha(Edge* a, Edge* b) { 1140 if (a->fType == Edge::Type::kInner || b->fType == Edge::Type::kInner) { 1141 return 255; 1142 } else if (a->fType == Edge::Type::kOuter && b->fType == Edge::Type::kOuter) { 1143 return 0; 1144 } else { 1145 return SkTMax(SkTMax(a->fTop->fAlpha, a->fBottom->fAlpha), 1146 SkTMax(b->fTop->fAlpha, b->fBottom->fAlpha)); 1147 } 1148 } 1149 #endif 1150 1151 bool out_of_range_and_collinear(const SkPoint& p, Edge* edge, Comparator& c) { 1152 if (c.sweep_lt(p, edge->fTop->fPoint) && 1153 !Line(p, edge->fBottom->fPoint).dist(edge->fTop->fPoint)) { 1154 return true; 1155 } else if (c.sweep_lt(edge->fBottom->fPoint, p) && 1156 !Line(edge->fTop->fPoint, p).dist(edge->fBottom->fPoint)) { 1157 return true; 1158 } 1159 return false; 1160 } 1161 1162 Vertex* create_sorted_vertex(const SkPoint& p, uint8_t alpha, VertexList* mesh, 1163 Vertex* reference, Comparator& c, SkArenaAlloc& alloc) { 1164 Vertex* prevV = reference; 1165 while (prevV && c.sweep_lt(p, prevV->fPoint)) { 1166 prevV = prevV->fPrev; 1167 } 1168 Vertex* nextV = prevV ? prevV->fNext : mesh->fHead; 1169 while (nextV && c.sweep_lt(nextV->fPoint, p)) { 1170 prevV = nextV; 1171 nextV = nextV->fNext; 1172 } 1173 Vertex* v; 1174 if (prevV && coincident(prevV->fPoint, p)) { 1175 v = prevV; 1176 } else if (nextV && coincident(nextV->fPoint, p)) { 1177 v = nextV; 1178 } else { 1179 v = alloc.make<Vertex>(p, alpha); 1180 #if LOGGING_ENABLED 1181 if (!prevV) { 1182 v->fID = mesh->fHead->fID - 1.0f; 1183 } else if (!nextV) { 1184 v->fID = mesh->fTail->fID + 1.0f; 1185 } else { 1186 v->fID = (prevV->fID + nextV->fID) * 0.5f; 1187 } 1188 #endif 1189 mesh->insert(v, prevV, nextV); 1190 } 1191 return v; 1192 } 1193 1194 bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, 1195 VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1196 if (!edge || !other) { 1197 return false; 1198 } 1199 SkPoint p; 1200 uint8_t alpha; 1201 if (edge->intersect(*other, &p, &alpha) && p.isFinite()) { 1202 // Ignore any out-of-range intersections which are also collinear, 1203 // since the resulting edges would cancel each other out by merging. 1204 if (out_of_range_and_collinear(p, edge, c) || 1205 out_of_range_and_collinear(p, other, c)) { 1206 return false; 1207 } 1208 Vertex* v; 1209 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); 1210 Vertex* top = *current; 1211 // If the intersection point is above the current vertex, rewind to the vertex above the 1212 // intersection. 1213 while (top && c.sweep_lt(p, top->fPoint)) { 1214 top = top->fPrev; 1215 } 1216 if (p == edge->fTop->fPoint) { 1217 v = edge->fTop; 1218 } else if (p == edge->fBottom->fPoint) { 1219 v = edge->fBottom; 1220 } else if (p == other->fTop->fPoint) { 1221 v = other->fTop; 1222 } else if (p == other->fBottom->fPoint) { 1223 v = other->fBottom; 1224 } else { 1225 v = create_sorted_vertex(p, alpha, mesh, top, c, alloc); 1226 #ifndef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1227 if (edge->fTop->fPartner) { 1228 Line line1 = edge->fLine; 1229 Line line2 = other->fLine; 1230 int dir = edge->fType == Edge::Type::kOuter ? -1 : 1; 1231 line1.fC += sqrt(edge->fLine.magSq()) * (edge->fWinding > 0 ? 1 : -1) * dir; 1232 line2.fC += sqrt(other->fLine.magSq()) * (other->fWinding > 0 ? 1 : -1) * dir; 1233 SkPoint p; 1234 if (line1.intersect(line2, &p)) { 1235 LOG("synthesizing partner (%g,%g) for intersection vertex %g\n", 1236 p.fX, p.fY, v->fID); 1237 v->fPartner = alloc.make<Vertex>(p, 255 - v->fAlpha); 1238 } 1239 } 1240 #endif 1241 } 1242 rewind(activeEdges, current, top ? top : v, c); 1243 split_edge(edge, v, activeEdges, current, c, alloc); 1244 split_edge(other, v, activeEdges, current, c, alloc); 1245 v->fAlpha = SkTMax(v->fAlpha, alpha); 1246 return true; 1247 } 1248 return false; 1249 } 1250 1251 void sanitize_contours(VertexList* contours, int contourCnt, bool approximate) { 1252 for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) { 1253 SkASSERT(contour->fHead); 1254 Vertex* prev = contour->fTail; 1255 if (approximate) { 1256 round(&prev->fPoint); 1257 } 1258 for (Vertex* v = contour->fHead; v;) { 1259 if (approximate) { 1260 round(&v->fPoint); 1261 } 1262 Vertex* next = v->fNext; 1263 if (coincident(prev->fPoint, v->fPoint)) { 1264 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY); 1265 contour->remove(v); 1266 } else if (!v->fPoint.isFinite()) { 1267 LOG("vertex %g,%g non-finite; removing\n", v->fPoint.fX, v->fPoint.fY); 1268 contour->remove(v); 1269 } 1270 prev = v; 1271 v = next; 1272 } 1273 } 1274 } 1275 1276 bool merge_coincident_vertices(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1277 if (!mesh->fHead) { 1278 return false; 1279 } 1280 bool merged = false; 1281 for (Vertex* v = mesh->fHead->fNext; v;) { 1282 Vertex* next = v->fNext; 1283 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { 1284 v->fPoint = v->fPrev->fPoint; 1285 } 1286 if (coincident(v->fPrev->fPoint, v->fPoint)) { 1287 merge_vertices(v, v->fPrev, mesh, c, alloc); 1288 merged = true; 1289 } 1290 v = next; 1291 } 1292 return merged; 1293 } 1294 1295 // Stage 2: convert the contours to a mesh of edges connecting the vertices. 1296 1297 void build_edges(VertexList* contours, int contourCnt, VertexList* mesh, Comparator& c, 1298 SkArenaAlloc& alloc) { 1299 for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) { 1300 Vertex* prev = contour->fTail; 1301 for (Vertex* v = contour->fHead; v;) { 1302 Vertex* next = v->fNext; 1303 connect(prev, v, Edge::Type::kInner, c, alloc); 1304 mesh->append(v); 1305 prev = v; 1306 v = next; 1307 } 1308 } 1309 } 1310 1311 void connect_partners(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1312 for (Vertex* outer = mesh->fHead; outer; outer = outer->fNext) { 1313 if (Vertex* inner = outer->fPartner) { 1314 if ((inner->fPrev || inner->fNext) && (outer->fPrev || outer->fNext)) { 1315 // Connector edges get zero winding, since they're only structural (i.e., to ensure 1316 // no 0-0-0 alpha triangles are produced), and shouldn't affect the poly winding 1317 // number. 1318 connect(outer, inner, Edge::Type::kConnector, c, alloc, 0); 1319 inner->fPartner = outer->fPartner = nullptr; 1320 } 1321 } 1322 } 1323 } 1324 1325 template <CompareFunc sweep_lt> 1326 void sorted_merge(VertexList* front, VertexList* back, VertexList* result) { 1327 Vertex* a = front->fHead; 1328 Vertex* b = back->fHead; 1329 while (a && b) { 1330 if (sweep_lt(a->fPoint, b->fPoint)) { 1331 front->remove(a); 1332 result->append(a); 1333 a = front->fHead; 1334 } else { 1335 back->remove(b); 1336 result->append(b); 1337 b = back->fHead; 1338 } 1339 } 1340 result->append(*front); 1341 result->append(*back); 1342 } 1343 1344 void sorted_merge(VertexList* front, VertexList* back, VertexList* result, Comparator& c) { 1345 if (c.fDirection == Comparator::Direction::kHorizontal) { 1346 sorted_merge<sweep_lt_horiz>(front, back, result); 1347 } else { 1348 sorted_merge<sweep_lt_vert>(front, back, result); 1349 } 1350 #if LOGGING_ENABLED 1351 float id = 0.0f; 1352 for (Vertex* v = result->fHead; v; v = v->fNext) { 1353 v->fID = id++; 1354 } 1355 #endif 1356 } 1357 1358 // Stage 3: sort the vertices by increasing sweep direction. 1359 1360 template <CompareFunc sweep_lt> 1361 void merge_sort(VertexList* vertices) { 1362 Vertex* slow = vertices->fHead; 1363 if (!slow) { 1364 return; 1365 } 1366 Vertex* fast = slow->fNext; 1367 if (!fast) { 1368 return; 1369 } 1370 do { 1371 fast = fast->fNext; 1372 if (fast) { 1373 fast = fast->fNext; 1374 slow = slow->fNext; 1375 } 1376 } while (fast); 1377 VertexList front(vertices->fHead, slow); 1378 VertexList back(slow->fNext, vertices->fTail); 1379 front.fTail->fNext = back.fHead->fPrev = nullptr; 1380 1381 merge_sort<sweep_lt>(&front); 1382 merge_sort<sweep_lt>(&back); 1383 1384 vertices->fHead = vertices->fTail = nullptr; 1385 sorted_merge<sweep_lt>(&front, &back, vertices); 1386 } 1387 1388 void dump_mesh(const VertexList& mesh) { 1389 #if LOGGING_ENABLED 1390 for (Vertex* v = mesh.fHead; v; v = v->fNext) { 1391 LOG("vertex %g (%g, %g) alpha %d", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha); 1392 if (Vertex* p = v->fPartner) { 1393 LOG(", partner %g (%g, %g) alpha %d\n", p->fID, p->fPoint.fX, p->fPoint.fY, p->fAlpha); 1394 } else { 1395 LOG(", null partner\n"); 1396 } 1397 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1398 LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding); 1399 } 1400 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1401 LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding); 1402 } 1403 } 1404 #endif 1405 } 1406 1407 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. 1408 1409 bool simplify(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1410 LOG("simplifying complex polygons\n"); 1411 EdgeList activeEdges; 1412 bool found = false; 1413 for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) { 1414 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1415 continue; 1416 } 1417 Edge* leftEnclosingEdge; 1418 Edge* rightEnclosingEdge; 1419 bool restartChecks; 1420 do { 1421 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha); 1422 restartChecks = false; 1423 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1424 if (rightEnclosingEdge && !rightEnclosingEdge->isRightOf(v)) { 1425 split_edge(rightEnclosingEdge, v, &activeEdges, &v, c, alloc); 1426 restartChecks = true; 1427 continue; 1428 } 1429 SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v)); 1430 v->fLeftEnclosingEdge = leftEnclosingEdge; 1431 v->fRightEnclosingEdge = rightEnclosingEdge; 1432 if (v->fFirstEdgeBelow) { 1433 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) { 1434 if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, &v, mesh, c, 1435 alloc)) { 1436 restartChecks = true; 1437 break; 1438 } 1439 if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, &v, mesh, c, 1440 alloc)) { 1441 restartChecks = true; 1442 break; 1443 } 1444 } 1445 } else { 1446 if (check_for_intersection(leftEnclosingEdge, rightEnclosingEdge, 1447 &activeEdges, &v, mesh, c, alloc)) { 1448 restartChecks = true; 1449 } 1450 1451 } 1452 found = found || restartChecks; 1453 } while (restartChecks); 1454 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1455 if (v->fAlpha == 0) { 1456 if ((leftEnclosingEdge && leftEnclosingEdge->fWinding < 0) && 1457 (rightEnclosingEdge && rightEnclosingEdge->fWinding > 0)) { 1458 v->fAlpha = max_edge_alpha(leftEnclosingEdge, rightEnclosingEdge); 1459 } 1460 } 1461 #endif 1462 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1463 remove_edge(e, &activeEdges); 1464 } 1465 Edge* leftEdge = leftEnclosingEdge; 1466 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1467 insert_edge(e, leftEdge, &activeEdges); 1468 leftEdge = e; 1469 } 1470 } 1471 SkASSERT(!activeEdges.fHead && !activeEdges.fTail); 1472 return found; 1473 } 1474 1475 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1476 // This is a stripped-down version of simplify() (the Bentley-Ottmann algorithm) that 1477 // early-returns true on the first found intersection, false if none. 1478 bool is_complex(const VertexList& vertices) { 1479 LOG("testing polygon complexity\n"); 1480 EdgeList activeEdges; 1481 for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) { 1482 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1483 continue; 1484 } 1485 Edge* leftEnclosingEdge; 1486 Edge* rightEnclosingEdge; 1487 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1488 SkPoint dummy; 1489 if (v->fFirstEdgeBelow) { 1490 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) { 1491 if (edge && leftEnclosingEdge && edge->intersect(*leftEnclosingEdge, &dummy)) { 1492 activeEdges.removeAll(); 1493 return true; 1494 } 1495 if (edge && rightEnclosingEdge && edge->intersect(*rightEnclosingEdge, &dummy)) { 1496 activeEdges.removeAll(); 1497 return true; 1498 } 1499 } 1500 } else if (leftEnclosingEdge && rightEnclosingEdge && 1501 leftEnclosingEdge->intersect(*rightEnclosingEdge, &dummy)) { 1502 activeEdges.removeAll(); 1503 return true; 1504 } 1505 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1506 remove_edge(e, &activeEdges); 1507 } 1508 Edge* leftEdge = leftEnclosingEdge; 1509 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1510 insert_edge(e, leftEdge, &activeEdges); 1511 leftEdge = e; 1512 } 1513 } 1514 activeEdges.removeAll(); 1515 return false; 1516 } 1517 #endif 1518 1519 // Stage 5: Tessellate the simplified mesh into monotone polygons. 1520 1521 Poly* tessellate(const VertexList& vertices, SkArenaAlloc& alloc) { 1522 LOG("\ntessellating simple polygons\n"); 1523 EdgeList activeEdges; 1524 Poly* polys = nullptr; 1525 for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) { 1526 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1527 continue; 1528 } 1529 #if LOGGING_ENABLED 1530 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha); 1531 #endif 1532 Edge* leftEnclosingEdge; 1533 Edge* rightEnclosingEdge; 1534 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1535 Poly* leftPoly; 1536 Poly* rightPoly; 1537 if (v->fFirstEdgeAbove) { 1538 leftPoly = v->fFirstEdgeAbove->fLeftPoly; 1539 rightPoly = v->fLastEdgeAbove->fRightPoly; 1540 } else { 1541 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullptr; 1542 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nullptr; 1543 } 1544 #if LOGGING_ENABLED 1545 LOG("edges above:\n"); 1546 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { 1547 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, 1548 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1); 1549 } 1550 LOG("edges below:\n"); 1551 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1552 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, 1553 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1); 1554 } 1555 #endif 1556 if (v->fFirstEdgeAbove) { 1557 if (leftPoly) { 1558 leftPoly = leftPoly->addEdge(v->fFirstEdgeAbove, Poly::kRight_Side, alloc); 1559 } 1560 if (rightPoly) { 1561 rightPoly = rightPoly->addEdge(v->fLastEdgeAbove, Poly::kLeft_Side, alloc); 1562 } 1563 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) { 1564 Edge* rightEdge = e->fNextEdgeAbove; 1565 remove_edge(e, &activeEdges); 1566 if (e->fRightPoly) { 1567 e->fRightPoly->addEdge(e, Poly::kLeft_Side, alloc); 1568 } 1569 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != e->fRightPoly) { 1570 rightEdge->fLeftPoly->addEdge(e, Poly::kRight_Side, alloc); 1571 } 1572 } 1573 remove_edge(v->fLastEdgeAbove, &activeEdges); 1574 if (!v->fFirstEdgeBelow) { 1575 if (leftPoly && rightPoly && leftPoly != rightPoly) { 1576 SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartner == nullptr); 1577 rightPoly->fPartner = leftPoly; 1578 leftPoly->fPartner = rightPoly; 1579 } 1580 } 1581 } 1582 if (v->fFirstEdgeBelow) { 1583 if (!v->fFirstEdgeAbove) { 1584 if (leftPoly && rightPoly) { 1585 if (leftPoly == rightPoly) { 1586 if (leftPoly->fTail && leftPoly->fTail->fSide == Poly::kLeft_Side) { 1587 leftPoly = new_poly(&polys, leftPoly->lastVertex(), 1588 leftPoly->fWinding, alloc); 1589 leftEnclosingEdge->fRightPoly = leftPoly; 1590 } else { 1591 rightPoly = new_poly(&polys, rightPoly->lastVertex(), 1592 rightPoly->fWinding, alloc); 1593 rightEnclosingEdge->fLeftPoly = rightPoly; 1594 } 1595 } 1596 Edge* join = alloc.make<Edge>(leftPoly->lastVertex(), v, 1, Edge::Type::kInner); 1597 leftPoly = leftPoly->addEdge(join, Poly::kRight_Side, alloc); 1598 rightPoly = rightPoly->addEdge(join, Poly::kLeft_Side, alloc); 1599 } 1600 } 1601 Edge* leftEdge = v->fFirstEdgeBelow; 1602 leftEdge->fLeftPoly = leftPoly; 1603 insert_edge(leftEdge, leftEnclosingEdge, &activeEdges); 1604 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge; 1605 rightEdge = rightEdge->fNextEdgeBelow) { 1606 insert_edge(rightEdge, leftEdge, &activeEdges); 1607 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWinding : 0; 1608 winding += leftEdge->fWinding; 1609 if (winding != 0) { 1610 Poly* poly = new_poly(&polys, v, winding, alloc); 1611 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; 1612 } 1613 leftEdge = rightEdge; 1614 } 1615 v->fLastEdgeBelow->fRightPoly = rightPoly; 1616 } 1617 #if LOGGING_ENABLED 1618 LOG("\nactive edges:\n"); 1619 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { 1620 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, 1621 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1); 1622 } 1623 #endif 1624 } 1625 return polys; 1626 } 1627 1628 void remove_non_boundary_edges(const VertexList& mesh, SkPath::FillType fillType, 1629 SkArenaAlloc& alloc) { 1630 LOG("removing non-boundary edges\n"); 1631 EdgeList activeEdges; 1632 for (Vertex* v = mesh.fHead; v != nullptr; v = v->fNext) { 1633 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1634 continue; 1635 } 1636 Edge* leftEnclosingEdge; 1637 Edge* rightEnclosingEdge; 1638 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1639 bool prevFilled = leftEnclosingEdge && 1640 apply_fill_type(fillType, leftEnclosingEdge->fWinding); 1641 for (Edge* e = v->fFirstEdgeAbove; e;) { 1642 Edge* next = e->fNextEdgeAbove; 1643 remove_edge(e, &activeEdges); 1644 bool filled = apply_fill_type(fillType, e->fWinding); 1645 if (filled == prevFilled) { 1646 disconnect(e); 1647 } 1648 prevFilled = filled; 1649 e = next; 1650 } 1651 Edge* prev = leftEnclosingEdge; 1652 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1653 if (prev) { 1654 e->fWinding += prev->fWinding; 1655 } 1656 insert_edge(e, prev, &activeEdges); 1657 prev = e; 1658 } 1659 } 1660 } 1661 1662 // Note: this is the normal to the edge, but not necessarily unit length. 1663 void get_edge_normal(const Edge* e, SkVector* normal) { 1664 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1665 normal->set(SkDoubleToScalar(e->fLine.fA) * e->fWinding, 1666 SkDoubleToScalar(e->fLine.fB) * e->fWinding); 1667 #else 1668 normal->set(SkDoubleToScalar(e->fLine.fA), 1669 SkDoubleToScalar(e->fLine.fB)); 1670 #endif 1671 } 1672 1673 #ifndef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1674 void reconnect(Edge* edge, Vertex* src, Vertex* dst, Comparator& c) { 1675 disconnect(edge); 1676 if (src == edge->fTop) { 1677 edge->fTop = dst; 1678 } else { 1679 SkASSERT(src == edge->fBottom); 1680 edge->fBottom = dst; 1681 } 1682 if (edge->fEvent) { 1683 edge->fEvent->fEdge = nullptr; 1684 } 1685 if (edge->fTop == edge->fBottom) { 1686 return; 1687 } 1688 if (c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) { 1689 SkTSwap(edge->fTop, edge->fBottom); 1690 edge->fWinding *= -1; 1691 } 1692 edge->recompute(); 1693 insert_edge_below(edge, edge->fTop, c); 1694 insert_edge_above(edge, edge->fBottom, c); 1695 merge_collinear_edges(edge, nullptr, nullptr, c); 1696 } 1697 #endif 1698 1699 // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions 1700 // and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to 1701 // invert on stroking. 1702 1703 void simplify_boundary(EdgeList* boundary, Comparator& c, SkArenaAlloc& alloc) { 1704 Edge* prevEdge = boundary->fTail; 1705 SkVector prevNormal; 1706 get_edge_normal(prevEdge, &prevNormal); 1707 for (Edge* e = boundary->fHead; e != nullptr;) { 1708 Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBottom; 1709 Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop; 1710 double dist = e->dist(prev->fPoint); 1711 SkVector normal; 1712 get_edge_normal(e, &normal); 1713 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1714 double denom = 0.0625f * e->fLine.magSq(); 1715 #else 1716 double denom = 0.0625f; 1717 #endif 1718 if (prevNormal.dot(normal) < 0.0 && (dist * dist) <= denom) { 1719 Edge* join = new_edge(prev, next, Edge::Type::kInner, c, alloc); 1720 #ifndef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1721 if (prev->fPoint != next->fPoint) { 1722 join->fLine.normalize(); 1723 join->fLine = join->fLine * join->fWinding; 1724 } 1725 #endif 1726 insert_edge(join, e, boundary); 1727 remove_edge(prevEdge, boundary); 1728 remove_edge(e, boundary); 1729 if (join->fLeft && join->fRight) { 1730 prevEdge = join->fLeft; 1731 e = join; 1732 } else { 1733 prevEdge = boundary->fTail; 1734 e = boundary->fHead; // join->fLeft ? join->fLeft : join; 1735 } 1736 get_edge_normal(prevEdge, &prevNormal); 1737 } else { 1738 prevEdge = e; 1739 prevNormal = normal; 1740 e = e->fRight; 1741 } 1742 } 1743 } 1744 1745 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1746 void fix_inversions(Vertex* prev, Vertex* next, Edge* prevBisector, Edge* nextBisector, 1747 Edge* prevEdge, Comparator& c) { 1748 if (!prev || !next) { 1749 return; 1750 } 1751 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; 1752 SkPoint p; 1753 uint8_t alpha; 1754 if (winding != prevEdge->fWinding && prevBisector->intersect(*nextBisector, &p, &alpha)) { 1755 prev->fPoint = next->fPoint = p; 1756 prev->fAlpha = next->fAlpha = alpha; 1757 } 1758 } 1759 #else 1760 void reconnect_all_overlap_edges(Vertex* src, Vertex* dst, Edge* current, Comparator& c) { 1761 if (src->fPartner) { 1762 src->fPartner->fPartner = dst; 1763 } 1764 for (Edge* e = src->fFirstEdgeAbove; e; ) { 1765 Edge* next = e->fNextEdgeAbove; 1766 if (e->fOverlap && e != current) { 1767 reconnect(e, src, dst, c); 1768 } 1769 e = next; 1770 } 1771 for (Edge* e = src->fFirstEdgeBelow; e; ) { 1772 Edge* next = e->fNextEdgeBelow; 1773 if (e->fOverlap && e != current) { 1774 reconnect(e, src, dst, c); 1775 } 1776 e = next; 1777 } 1778 } 1779 1780 void Event::apply(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1781 if (!fEdge) { 1782 return; 1783 } 1784 Vertex* top = fEdge->fTop; 1785 Vertex* bottom = fEdge->fBottom; 1786 Vertex* dest = create_sorted_vertex(fPoint, fAlpha, mesh, fEdge->fTop, c, alloc); 1787 LOG("collapsing edge %g -> %g to %g (%g, %g) alpha %d\n", 1788 top->fID, bottom->fID, dest->fID, fPoint.fX, fPoint.fY, fAlpha); 1789 reconnect_all_overlap_edges(top, dest, fEdge, c); 1790 reconnect_all_overlap_edges(bottom, dest, fEdge, c); 1791 1792 // Since the destination has multiple partners, give it none. 1793 dest->fPartner = nullptr; 1794 disconnect(fEdge); 1795 1796 // If top still has some connected edges, set its partner to dest. 1797 top->fPartner = top->fFirstEdgeAbove || top->fFirstEdgeBelow ? dest : nullptr; 1798 1799 // If bottom still has some connected edges, set its partner to dest. 1800 bottom->fPartner = bottom->fFirstEdgeAbove || bottom->fFirstEdgeBelow ? dest : nullptr; 1801 } 1802 1803 bool is_overlap_edge(Edge* e) { 1804 if (e->fType == Edge::Type::kOuter) { 1805 return e->fWinding != 0 && e->fWinding != 1; 1806 } else if (e->fType == Edge::Type::kInner) { 1807 return e->fWinding != 0 && e->fWinding != -2; 1808 } else { 1809 return false; 1810 } 1811 } 1812 1813 // This is a stripped-down version of tessellate() which computes edges which 1814 // join two filled regions, which represent overlap regions, and collapses them. 1815 bool collapse_overlap_regions(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 1816 LOG("\nfinding overlap regions\n"); 1817 EdgeList activeEdges; 1818 EventList events; 1819 for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) { 1820 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { 1821 continue; 1822 } 1823 Edge* leftEnclosingEdge; 1824 Edge* rightEnclosingEdge; 1825 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge); 1826 for (Edge* e = v->fLastEdgeAbove; e; e = e->fPrevEdgeAbove) { 1827 Edge* prev = e->fPrevEdgeAbove ? e->fPrevEdgeAbove : leftEnclosingEdge; 1828 remove_edge(e, &activeEdges); 1829 if (prev) { 1830 e->fWinding -= prev->fWinding; 1831 } 1832 } 1833 Edge* prev = leftEnclosingEdge; 1834 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 1835 if (prev) { 1836 e->fWinding += prev->fWinding; 1837 e->fOverlap = e->fOverlap || is_overlap_edge(prev); 1838 } 1839 e->fOverlap = e->fOverlap || is_overlap_edge(e); 1840 if (e->fOverlap) { 1841 create_event(e, &events, alloc); 1842 } 1843 insert_edge(e, prev, &activeEdges); 1844 prev = e; 1845 } 1846 } 1847 LOG("\ncollapsing overlap regions\n"); 1848 if (events.count() == 0) { 1849 return false; 1850 } 1851 while (events.count() > 0) { 1852 Event* event = events.peek(); 1853 events.pop(); 1854 event->apply(mesh, c, alloc); 1855 } 1856 return true; 1857 } 1858 1859 bool inversion(Vertex* prev, Vertex* next, Edge* origEdge, Comparator& c) { 1860 if (!prev || !next) { 1861 return true; 1862 } 1863 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; 1864 return winding != origEdge->fWinding; 1865 } 1866 #endif 1867 1868 // Stage 5d: Displace edges by half a pixel inward and outward along their normals. Intersect to 1869 // find new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a 1870 // new antialiased mesh from those vertices. 1871 1872 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 1873 void stroke_boundary(EdgeList* boundary, VertexList* innerMesh, VertexList* outerMesh, 1874 Comparator& c, SkArenaAlloc& alloc) { 1875 // A boundary with fewer than 3 edges is degenerate. 1876 if (!boundary->fHead || !boundary->fHead->fRight || !boundary->fHead->fRight->fRight) { 1877 return; 1878 } 1879 Edge* prevEdge = boundary->fTail; 1880 float radius = 0.5f; 1881 double offset = radius * sqrt(prevEdge->fLine.magSq()) * prevEdge->fWinding; 1882 Line prevInner(prevEdge->fLine); 1883 prevInner.fC -= offset; 1884 Line prevOuter(prevEdge->fLine); 1885 prevOuter.fC += offset; 1886 VertexList innerVertices; 1887 VertexList outerVertices; 1888 Edge* prevBisector = nullptr; 1889 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) { 1890 double offset = radius * sqrt(e->fLine.magSq()) * e->fWinding; 1891 Line inner(e->fLine); 1892 inner.fC -= offset; 1893 Line outer(e->fLine); 1894 outer.fC += offset; 1895 SkPoint innerPoint, outerPoint; 1896 if (prevInner.intersect(inner, &innerPoint) && 1897 prevOuter.intersect(outer, &outerPoint)) { 1898 Vertex* innerVertex = alloc.make<Vertex>(innerPoint, 255); 1899 Vertex* outerVertex = alloc.make<Vertex>(outerPoint, 0); 1900 Edge* bisector = new_edge(outerVertex, innerVertex, Edge::Type::kConnector, c, alloc); 1901 fix_inversions(innerVertices.fTail, innerVertex, prevBisector, bisector, prevEdge, c); 1902 fix_inversions(outerVertices.fTail, outerVertex, prevBisector, bisector, prevEdge, c); 1903 innerVertex->fPartner = outerVertex; 1904 outerVertex->fPartner = innerVertex; 1905 innerVertices.append(innerVertex); 1906 outerVertices.append(outerVertex); 1907 prevBisector = bisector; 1908 } 1909 prevInner = inner; 1910 prevOuter = outer; 1911 prevEdge = e; 1912 } 1913 1914 Vertex* innerVertex = innerVertices.fHead; 1915 Vertex* outerVertex = outerVertices.fHead; 1916 if (!innerVertex || !outerVertex) { 1917 return; 1918 } 1919 Edge* bisector = new_edge(outerVertices.fHead, innerVertices.fHead, Edge::Type::kConnector, c, 1920 alloc); 1921 fix_inversions(innerVertices.fTail, innerVertices.fHead, prevBisector, bisector, prevEdge, c); 1922 fix_inversions(outerVertices.fTail, outerVertices.fHead, prevBisector, bisector, prevEdge, c); 1923 Vertex* prevInnerVertex = innerVertices.fTail; 1924 Vertex* prevOuterVertex = outerVertices.fTail; 1925 while (innerVertex && outerVertex) { 1926 // Connect vertices into a quad mesh. Outer edges get default (1) winding. 1927 // Inner edges get -2 winding. This ensures that the interior is always filled 1928 // (-1 winding number for normal cases, 3 for thin features where the interior inverts). 1929 connect(prevOuterVertex, outerVertex, Edge::Type::kOuter, c, alloc); 1930 connect(prevInnerVertex, innerVertex, Edge::Type::kInner, c, alloc, -2); 1931 prevInnerVertex = innerVertex; 1932 prevOuterVertex = outerVertex; 1933 innerVertex = innerVertex->fNext; 1934 outerVertex = outerVertex->fNext; 1935 } 1936 innerMesh->append(innerVertices); 1937 outerMesh->append(outerVertices); 1938 } 1939 #else 1940 void stroke_boundary(EdgeList* boundary, VertexList* innerMesh, VertexList* outerMesh, 1941 Comparator& c, SkArenaAlloc& alloc) { 1942 LOG("\nstroking boundary\n"); 1943 // A boundary with fewer than 3 edges is degenerate. 1944 if (!boundary->fHead || !boundary->fHead->fRight || !boundary->fHead->fRight->fRight) { 1945 return; 1946 } 1947 Edge* prevEdge = boundary->fTail; 1948 Vertex* prevV = prevEdge->fWinding > 0 ? prevEdge->fTop : prevEdge->fBottom; 1949 SkVector prevNormal; 1950 get_edge_normal(prevEdge, &prevNormal); 1951 double radius = 0.5; 1952 Line prevInner(prevEdge->fLine); 1953 prevInner.fC -= radius; 1954 Line prevOuter(prevEdge->fLine); 1955 prevOuter.fC += radius; 1956 VertexList innerVertices; 1957 VertexList outerVertices; 1958 bool innerInversion = true; 1959 bool outerInversion = true; 1960 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) { 1961 Vertex* v = e->fWinding > 0 ? e->fTop : e->fBottom; 1962 SkVector normal; 1963 get_edge_normal(e, &normal); 1964 Line inner(e->fLine); 1965 inner.fC -= radius; 1966 Line outer(e->fLine); 1967 outer.fC += radius; 1968 SkPoint innerPoint, outerPoint; 1969 LOG("stroking vertex %g (%g, %g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); 1970 if (!prevEdge->fLine.nearParallel(e->fLine) && prevInner.intersect(inner, &innerPoint) && 1971 prevOuter.intersect(outer, &outerPoint)) { 1972 float cosAngle = normal.dot(prevNormal); 1973 if (cosAngle < -kCosMiterAngle) { 1974 Vertex* nextV = e->fWinding > 0 ? e->fBottom : e->fTop; 1975 1976 // This is a pointy vertex whose angle is smaller than the threshold; miter it. 1977 Line bisector(innerPoint, outerPoint); 1978 Line tangent(v->fPoint, v->fPoint + SkPoint::Make(bisector.fA, bisector.fB)); 1979 if (tangent.fA == 0 && tangent.fB == 0) { 1980 continue; 1981 } 1982 tangent.normalize(); 1983 Line innerTangent(tangent); 1984 Line outerTangent(tangent); 1985 innerTangent.fC -= 0.5; 1986 outerTangent.fC += 0.5; 1987 SkPoint innerPoint1, innerPoint2, outerPoint1, outerPoint2; 1988 if (prevNormal.cross(normal) > 0) { 1989 // Miter inner points 1990 if (!innerTangent.intersect(prevInner, &innerPoint1) || 1991 !innerTangent.intersect(inner, &innerPoint2) || 1992 !outerTangent.intersect(bisector, &outerPoint)) { 1993 continue; 1994 } 1995 Line prevTangent(prevV->fPoint, 1996 prevV->fPoint + SkVector::Make(prevOuter.fA, prevOuter.fB)); 1997 Line nextTangent(nextV->fPoint, 1998 nextV->fPoint + SkVector::Make(outer.fA, outer.fB)); 1999 if (prevTangent.dist(outerPoint) > 0) { 2000 bisector.intersect(prevTangent, &outerPoint); 2001 } 2002 if (nextTangent.dist(outerPoint) < 0) { 2003 bisector.intersect(nextTangent, &outerPoint); 2004 } 2005 outerPoint1 = outerPoint2 = outerPoint; 2006 } else { 2007 // Miter outer points 2008 if (!outerTangent.intersect(prevOuter, &outerPoint1) || 2009 !outerTangent.intersect(outer, &outerPoint2)) { 2010 continue; 2011 } 2012 Line prevTangent(prevV->fPoint, 2013 prevV->fPoint + SkVector::Make(prevInner.fA, prevInner.fB)); 2014 Line nextTangent(nextV->fPoint, 2015 nextV->fPoint + SkVector::Make(inner.fA, inner.fB)); 2016 if (prevTangent.dist(innerPoint) > 0) { 2017 bisector.intersect(prevTangent, &innerPoint); 2018 } 2019 if (nextTangent.dist(innerPoint) < 0) { 2020 bisector.intersect(nextTangent, &innerPoint); 2021 } 2022 innerPoint1 = innerPoint2 = innerPoint; 2023 } 2024 LOG("inner (%g, %g), (%g, %g), ", 2025 innerPoint1.fX, innerPoint1.fY, innerPoint2.fX, innerPoint2.fY); 2026 LOG("outer (%g, %g), (%g, %g)\n", 2027 outerPoint1.fX, outerPoint1.fY, outerPoint2.fX, outerPoint2.fY); 2028 Vertex* innerVertex1 = alloc.make<Vertex>(innerPoint1, 255); 2029 Vertex* innerVertex2 = alloc.make<Vertex>(innerPoint2, 255); 2030 Vertex* outerVertex1 = alloc.make<Vertex>(outerPoint1, 0); 2031 Vertex* outerVertex2 = alloc.make<Vertex>(outerPoint2, 0); 2032 innerVertex1->fPartner = outerVertex1; 2033 innerVertex2->fPartner = outerVertex2; 2034 outerVertex1->fPartner = innerVertex1; 2035 outerVertex2->fPartner = innerVertex2; 2036 if (!inversion(innerVertices.fTail, innerVertex1, prevEdge, c)) { 2037 innerInversion = false; 2038 } 2039 if (!inversion(outerVertices.fTail, outerVertex1, prevEdge, c)) { 2040 outerInversion = false; 2041 } 2042 innerVertices.append(innerVertex1); 2043 innerVertices.append(innerVertex2); 2044 outerVertices.append(outerVertex1); 2045 outerVertices.append(outerVertex2); 2046 } else { 2047 LOG("inner (%g, %g), ", innerPoint.fX, innerPoint.fY); 2048 LOG("outer (%g, %g)\n", outerPoint.fX, outerPoint.fY); 2049 Vertex* innerVertex = alloc.make<Vertex>(innerPoint, 255); 2050 Vertex* outerVertex = alloc.make<Vertex>(outerPoint, 0); 2051 innerVertex->fPartner = outerVertex; 2052 outerVertex->fPartner = innerVertex; 2053 if (!inversion(innerVertices.fTail, innerVertex, prevEdge, c)) { 2054 innerInversion = false; 2055 } 2056 if (!inversion(outerVertices.fTail, outerVertex, prevEdge, c)) { 2057 outerInversion = false; 2058 } 2059 innerVertices.append(innerVertex); 2060 outerVertices.append(outerVertex); 2061 } 2062 } 2063 prevInner = inner; 2064 prevOuter = outer; 2065 prevV = v; 2066 prevEdge = e; 2067 prevNormal = normal; 2068 } 2069 if (!inversion(innerVertices.fTail, innerVertices.fHead, prevEdge, c)) { 2070 innerInversion = false; 2071 } 2072 if (!inversion(outerVertices.fTail, outerVertices.fHead, prevEdge, c)) { 2073 outerInversion = false; 2074 } 2075 // Outer edges get 1 winding, and inner edges get -2 winding. This ensures that the interior 2076 // is always filled (1 + -2 = -1 for normal cases, 1 + 2 = 3 for thin features where the 2077 // interior inverts). 2078 // For total inversion cases, the shape has now reversed handedness, so invert the winding 2079 // so it will be detected during collapse_overlap_regions(). 2080 int innerWinding = innerInversion ? 2 : -2; 2081 int outerWinding = outerInversion ? -1 : 1; 2082 for (Vertex* v = innerVertices.fHead; v && v->fNext; v = v->fNext) { 2083 connect(v, v->fNext, Edge::Type::kInner, c, alloc, innerWinding); 2084 } 2085 connect(innerVertices.fTail, innerVertices.fHead, Edge::Type::kInner, c, alloc, innerWinding); 2086 for (Vertex* v = outerVertices.fHead; v && v->fNext; v = v->fNext) { 2087 connect(v, v->fNext, Edge::Type::kOuter, c, alloc, outerWinding); 2088 } 2089 connect(outerVertices.fTail, outerVertices.fHead, Edge::Type::kOuter, c, alloc, outerWinding); 2090 innerMesh->append(innerVertices); 2091 outerMesh->append(outerVertices); 2092 } 2093 #endif 2094 2095 void extract_boundary(EdgeList* boundary, Edge* e, SkPath::FillType fillType, SkArenaAlloc& alloc) { 2096 LOG("\nextracting boundary\n"); 2097 bool down = apply_fill_type(fillType, e->fWinding); 2098 while (e) { 2099 e->fWinding = down ? 1 : -1; 2100 Edge* next; 2101 #ifndef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 2102 e->fLine.normalize(); 2103 e->fLine = e->fLine * e->fWinding; 2104 #endif 2105 boundary->append(e); 2106 if (down) { 2107 // Find outgoing edge, in clockwise order. 2108 if ((next = e->fNextEdgeAbove)) { 2109 down = false; 2110 } else if ((next = e->fBottom->fLastEdgeBelow)) { 2111 down = true; 2112 } else if ((next = e->fPrevEdgeAbove)) { 2113 down = false; 2114 } 2115 } else { 2116 // Find outgoing edge, in counter-clockwise order. 2117 if ((next = e->fPrevEdgeBelow)) { 2118 down = true; 2119 } else if ((next = e->fTop->fFirstEdgeAbove)) { 2120 down = false; 2121 } else if ((next = e->fNextEdgeBelow)) { 2122 down = true; 2123 } 2124 } 2125 disconnect(e); 2126 e = next; 2127 } 2128 } 2129 2130 // Stage 5b: Extract boundaries from mesh, simplify and stroke them into a new mesh. 2131 2132 void extract_boundaries(const VertexList& inMesh, VertexList* innerVertices, 2133 VertexList* outerVertices, SkPath::FillType fillType, 2134 Comparator& c, SkArenaAlloc& alloc) { 2135 remove_non_boundary_edges(inMesh, fillType, alloc); 2136 for (Vertex* v = inMesh.fHead; v; v = v->fNext) { 2137 while (v->fFirstEdgeBelow) { 2138 EdgeList boundary; 2139 extract_boundary(&boundary, v->fFirstEdgeBelow, fillType, alloc); 2140 simplify_boundary(&boundary, c, alloc); 2141 stroke_boundary(&boundary, innerVertices, outerVertices, c, alloc); 2142 } 2143 } 2144 } 2145 2146 // This is a driver function that calls stages 2-5 in turn. 2147 2148 void contours_to_mesh(VertexList* contours, int contourCnt, bool antialias, 2149 VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) { 2150 #if LOGGING_ENABLED 2151 for (int i = 0; i < contourCnt; ++i) { 2152 Vertex* v = contours[i].fHead; 2153 SkASSERT(v); 2154 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); 2155 for (v = v->fNext; v; v = v->fNext) { 2156 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); 2157 } 2158 } 2159 #endif 2160 sanitize_contours(contours, contourCnt, antialias); 2161 build_edges(contours, contourCnt, mesh, c, alloc); 2162 } 2163 2164 void sort_mesh(VertexList* vertices, Comparator& c, SkArenaAlloc& alloc) { 2165 if (!vertices || !vertices->fHead) { 2166 return; 2167 } 2168 2169 // Sort vertices in Y (secondarily in X). 2170 if (c.fDirection == Comparator::Direction::kHorizontal) { 2171 merge_sort<sweep_lt_horiz>(vertices); 2172 } else { 2173 merge_sort<sweep_lt_vert>(vertices); 2174 } 2175 #if LOGGING_ENABLED 2176 for (Vertex* v = vertices->fHead; v != nullptr; v = v->fNext) { 2177 static float gID = 0.0f; 2178 v->fID = gID++; 2179 } 2180 #endif 2181 } 2182 2183 Poly* contours_to_polys(VertexList* contours, int contourCnt, SkPath::FillType fillType, 2184 const SkRect& pathBounds, bool antialias, VertexList* outerMesh, 2185 SkArenaAlloc& alloc) { 2186 Comparator c(pathBounds.width() > pathBounds.height() ? Comparator::Direction::kHorizontal 2187 : Comparator::Direction::kVertical); 2188 VertexList mesh; 2189 contours_to_mesh(contours, contourCnt, antialias, &mesh, c, alloc); 2190 sort_mesh(&mesh, c, alloc); 2191 merge_coincident_vertices(&mesh, c, alloc); 2192 simplify(&mesh, c, alloc); 2193 if (antialias) { 2194 VertexList innerMesh; 2195 extract_boundaries(mesh, &innerMesh, outerMesh, fillType, c, alloc); 2196 sort_mesh(&innerMesh, c, alloc); 2197 sort_mesh(outerMesh, c, alloc); 2198 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 2199 if (is_complex(innerMesh) || is_complex(*outerMesh)) { 2200 #else 2201 merge_coincident_vertices(&innerMesh, c, alloc); 2202 bool was_complex = merge_coincident_vertices(outerMesh, c, alloc); 2203 was_complex = simplify(&innerMesh, c, alloc) || was_complex; 2204 was_complex = simplify(outerMesh, c, alloc) || was_complex; 2205 LOG("\ninner mesh before:\n"); 2206 dump_mesh(innerMesh); 2207 LOG("\nouter mesh before:\n"); 2208 dump_mesh(*outerMesh); 2209 was_complex = collapse_overlap_regions(&innerMesh, c, alloc) || was_complex; 2210 was_complex = collapse_overlap_regions(outerMesh, c, alloc) || was_complex; 2211 if (was_complex) { 2212 #endif 2213 LOG("found complex mesh; taking slow path\n"); 2214 VertexList aaMesh; 2215 LOG("\ninner mesh after:\n"); 2216 dump_mesh(innerMesh); 2217 LOG("\nouter mesh after:\n"); 2218 dump_mesh(*outerMesh); 2219 connect_partners(outerMesh, c, alloc); 2220 connect_partners(&innerMesh, c, alloc); 2221 sorted_merge(&innerMesh, outerMesh, &aaMesh, c); 2222 merge_coincident_vertices(&aaMesh, c, alloc); 2223 simplify(&aaMesh, c, alloc); 2224 dump_mesh(aaMesh); 2225 outerMesh->fHead = outerMesh->fTail = nullptr; 2226 return tessellate(aaMesh, alloc); 2227 } else { 2228 LOG("no complex polygons; taking fast path\n"); 2229 #ifdef GR_TESSELLATOR_LEGACY_INVERSION_HANDLING 2230 merge_coincident_vertices(&innerMesh, c, alloc); 2231 #endif 2232 return tessellate(innerMesh, alloc); 2233 } 2234 } else { 2235 return tessellate(mesh, alloc); 2236 } 2237 } 2238 2239 // Stage 6: Triangulate the monotone polygons into a vertex buffer. 2240 void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, const AAParams* aaParams, 2241 void* data) { 2242 for (Poly* poly = polys; poly; poly = poly->fNext) { 2243 if (apply_fill_type(fillType, poly)) { 2244 data = poly->emit(aaParams, data); 2245 } 2246 } 2247 return data; 2248 } 2249 2250 Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 2251 int contourCnt, SkArenaAlloc& alloc, bool antialias, bool* isLinear, 2252 VertexList* outerMesh) { 2253 SkPath::FillType fillType = path.getFillType(); 2254 if (SkPath::IsInverseFillType(fillType)) { 2255 contourCnt++; 2256 } 2257 std::unique_ptr<VertexList[]> contours(new VertexList[contourCnt]); 2258 2259 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinear); 2260 return contours_to_polys(contours.get(), contourCnt, path.getFillType(), path.getBounds(), 2261 antialias, outerMesh, alloc); 2262 } 2263 2264 int get_contour_count(const SkPath& path, SkScalar tolerance) { 2265 int contourCnt; 2266 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tolerance); 2267 if (maxPts <= 0) { 2268 return 0; 2269 } 2270 if (maxPts > ((int)SK_MaxU16 + 1)) { 2271 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); 2272 return 0; 2273 } 2274 return contourCnt; 2275 } 2276 2277 int count_points(Poly* polys, SkPath::FillType fillType) { 2278 int count = 0; 2279 for (Poly* poly = polys; poly; poly = poly->fNext) { 2280 if (apply_fill_type(fillType, poly) && poly->fCount >= 3) { 2281 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3); 2282 } 2283 } 2284 return count; 2285 } 2286 2287 int count_outer_mesh_points(const VertexList& outerMesh) { 2288 int count = 0; 2289 for (Vertex* v = outerMesh.fHead; v; v = v->fNext) { 2290 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 2291 count += TESSELLATOR_WIREFRAME ? 12 : 6; 2292 } 2293 } 2294 return count; 2295 } 2296 2297 void* outer_mesh_to_triangles(const VertexList& outerMesh, const AAParams* aaParams, void* data) { 2298 for (Vertex* v = outerMesh.fHead; v; v = v->fNext) { 2299 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { 2300 Vertex* v0 = e->fTop; 2301 Vertex* v1 = e->fBottom; 2302 Vertex* v2 = e->fBottom->fPartner; 2303 Vertex* v3 = e->fTop->fPartner; 2304 data = emit_triangle(v0, v1, v2, aaParams, data); 2305 data = emit_triangle(v0, v2, v3, aaParams, data); 2306 } 2307 } 2308 return data; 2309 } 2310 2311 } // namespace 2312 2313 namespace GrTessellator { 2314 2315 // Stage 6: Triangulate the monotone polygons into a vertex buffer. 2316 2317 int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 2318 VertexAllocator* vertexAllocator, bool antialias, const GrColor& color, 2319 bool canTweakAlphaForCoverage, bool* isLinear) { 2320 int contourCnt = get_contour_count(path, tolerance); 2321 if (contourCnt <= 0) { 2322 *isLinear = true; 2323 return 0; 2324 } 2325 SkArenaAlloc alloc(kArenaChunkSize); 2326 VertexList outerMesh; 2327 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, antialias, 2328 isLinear, &outerMesh); 2329 SkPath::FillType fillType = antialias ? SkPath::kWinding_FillType : path.getFillType(); 2330 int count = count_points(polys, fillType); 2331 if (antialias) { 2332 count += count_outer_mesh_points(outerMesh); 2333 } 2334 if (0 == count) { 2335 return 0; 2336 } 2337 2338 void* verts = vertexAllocator->lock(count); 2339 if (!verts) { 2340 SkDebugf("Could not allocate vertices\n"); 2341 return 0; 2342 } 2343 2344 LOG("emitting %d verts\n", count); 2345 AAParams aaParams; 2346 aaParams.fTweakAlpha = canTweakAlphaForCoverage; 2347 aaParams.fColor = color; 2348 2349 void* end = polys_to_triangles(polys, fillType, antialias ? &aaParams : nullptr, verts); 2350 end = outer_mesh_to_triangles(outerMesh, &aaParams, end); 2351 int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast<uint8_t*>(verts)) 2352 / vertexAllocator->stride()); 2353 SkASSERT(actualCount <= count); 2354 vertexAllocator->unlock(actualCount); 2355 return actualCount; 2356 } 2357 2358 int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, 2359 GrTessellator::WindingVertex** verts) { 2360 int contourCnt = get_contour_count(path, tolerance); 2361 if (contourCnt <= 0) { 2362 *verts = nullptr; 2363 return 0; 2364 } 2365 SkArenaAlloc alloc(kArenaChunkSize); 2366 bool isLinear; 2367 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, false, &isLinear, 2368 nullptr); 2369 SkPath::FillType fillType = path.getFillType(); 2370 int count = count_points(polys, fillType); 2371 if (0 == count) { 2372 *verts = nullptr; 2373 return 0; 2374 } 2375 2376 *verts = new GrTessellator::WindingVertex[count]; 2377 GrTessellator::WindingVertex* vertsEnd = *verts; 2378 SkPoint* points = new SkPoint[count]; 2379 SkPoint* pointsEnd = points; 2380 for (Poly* poly = polys; poly; poly = poly->fNext) { 2381 if (apply_fill_type(fillType, poly)) { 2382 SkPoint* start = pointsEnd; 2383 pointsEnd = static_cast<SkPoint*>(poly->emit(nullptr, pointsEnd)); 2384 while (start != pointsEnd) { 2385 vertsEnd->fPos = *start; 2386 vertsEnd->fWinding = poly->fWinding; 2387 ++start; 2388 ++vertsEnd; 2389 } 2390 } 2391 } 2392 int actualCount = static_cast<int>(vertsEnd - *verts); 2393 SkASSERT(actualCount <= count); 2394 SkASSERT(pointsEnd - points == actualCount); 2395 delete[] points; 2396 return actualCount; 2397 } 2398 2399 } // namespace 2400