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