blob: f4195dfb03696d9384fa9a26a38f389069145f86 [file] [log] [blame]
ethannicholase9709e82016-01-07 13:34:16 -08001/*
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
ethannicholase9709e82016-01-07 13:34:16 -080010#include "GrPathUtils.h"
ethannicholase9709e82016-01-07 13:34:16 -080011
senorblanco6599eff2016-03-10 08:38:45 -080012#include "SkChunkAlloc.h"
13#include "SkGeometry.h"
14#include "SkPath.h"
ethannicholase9709e82016-01-07 13:34:16 -080015
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
84namespace {
85
86struct Vertex;
87struct Edge;
88struct Poly;
89
90template <class T, T* T::*Prev, T* T::*Next>
senorblancoe6eaa322016-03-08 09:06:44 -080091void list_insert(T* t, T* prev, T* next, T** head, T** tail) {
ethannicholase9709e82016-01-07 13:34:16 -080092 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
106template <class T, T* T::*Prev, T* T::*Next>
senorblancoe6eaa322016-03-08 09:06:44 -0800107void list_remove(T* t, T** head, T** tail) {
ethannicholase9709e82016-01-07 13:34:16 -0800108 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
132struct 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
157typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
158
159struct Comparator {
160 CompareFunc sweep_lt;
161 CompareFunc sweep_gt;
162};
163
164bool 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
168bool 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
172bool 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
176bool 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
180inline SkPoint* emit_vertex(Vertex* v, SkPoint* data) {
181 *data++ = v->fPoint;
182 return data;
183}
184
185SkPoint* 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
201struct EdgeList {
202 EdgeList() : fHead(nullptr), fTail(nullptr) {}
203 Edge* fHead;
204 Edge* fTail;
205};
206
senorblancoe6eaa322016-03-08 09:06:44 -0800207struct 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
ethannicholase9709e82016-01-07 13:34:16 -0800222/**
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
240struct 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
318struct 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)
ethannicholase9709e82016-01-07 13:34:16 -0800338 , fPrev(nullptr)
339 , fNext(nullptr) {}
340 Side fSide;
senorblancoe6eaa322016-03-08 09:06:44 -0800341 VertexList fVertices;
ethannicholase9709e82016-01-07 13:34:16 -0800342 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 }
senorblancoe6eaa322016-03-08 09:06:44 -0800352 if (fSide == kRight_Side) {
353 fVertices.append(newV);
ethannicholase9709e82016-01-07 13:34:16 -0800354 } else {
senorblancoe6eaa322016-03-08 09:06:44 -0800355 fVertices.prepend(newV);
ethannicholase9709e82016-01-07 13:34:16 -0800356 }
357 return done;
358 }
359
360 SkPoint* emit(SkPoint* data) {
senorblancoe6eaa322016-03-08 09:06:44 -0800361 Vertex* first = fVertices.fHead;
ethannicholase9709e82016-01-07 13:34:16 -0800362 Vertex* v = first->fNext;
senorblancoe6eaa322016-03-08 09:06:44 -0800363 while (v != fVertices.fTail) {
ethannicholase9709e82016-01-07 13:34:16 -0800364 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 ?
senorblancoe6eaa322016-03-08 09:06:44 -0800412 fActive->fVertices.fHead->fNext : fActive->fVertices.fTail->fPrev;
ethannicholase9709e82016-01-07 13:34:16 -0800413 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
452bool coincident(const SkPoint& a, const SkPoint& b) {
453 return a == b;
454}
455
456Poly* 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
464Vertex* 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
480Vertex* 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
505Vertex* 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
538void 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
622inline 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
638Edge* 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
645void remove_edge(Edge* edge, EdgeList* edges) {
646 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
647 SkASSERT(edge->isActive(edges));
senorblancoe6eaa322016-03-08 09:06:44 -0800648 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail);
ethannicholase9709e82016-01-07 13:34:16 -0800649}
650
651void 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;
senorblancoe6eaa322016-03-08 09:06:44 -0800655 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &edges->fTail);
ethannicholase9709e82016-01-07 13:34:16 -0800656}
657
658void 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;
ethannicholase9709e82016-01-07 13:34:16 -0800674}
675
676void 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;
ethannicholase9709e82016-01-07 13:34:16 -0800692}
693
694void 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
707void 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 }
senorblancoe6eaa322016-03-08 09:06:44 -0800721 list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
ethannicholase9709e82016-01-07 13:34:16 -0800722 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
723}
724
725void 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 }
senorblancoe6eaa322016-03-08 09:06:44 -0800739 list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
ethannicholase9709e82016-01-07 13:34:16 -0800740 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
741}
742
743void 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);
senorblancoe6eaa322016-03-08 09:06:44 -0800746 list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
ethannicholase9709e82016-01-07 13:34:16 -0800747 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
748}
749
750void 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);
senorblancoe6eaa322016-03-08 09:06:44 -0800753 list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
ethannicholase9709e82016-01-07 13:34:16 -0800754 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
755}
756
757void 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
769void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
770
771void 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
780void 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
789void 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
809void 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
829void 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
846void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkChunkAlloc& alloc);
847
848void 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
882void 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
901void 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 }
senorblancoe6eaa322016-03-08 09:06:44 -0800914 list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr);
ethannicholase9709e82016-01-07 13:34:16 -0800915}
916
917Vertex* 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
972void 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
996void 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
1009Vertex* 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
1043Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c);
1044
1045void 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
1070void 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
ethannicholase9709e82016-01-07 13:34:16 -08001085Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) {
senorblancoe6eaa322016-03-08 09:06:44 -08001086 VertexList vertices;
ethannicholase9709e82016-01-07 13:34:16 -08001087
1088 while (a && b) {
1089 if (c.sweep_lt(a->fPoint, b->fPoint)) {
1090 Vertex* next = a->fNext;
senorblancoe6eaa322016-03-08 09:06:44 -08001091 vertices.append(a);
ethannicholase9709e82016-01-07 13:34:16 -08001092 a = next;
1093 } else {
1094 Vertex* next = b->fNext;
senorblancoe6eaa322016-03-08 09:06:44 -08001095 vertices.append(b);
ethannicholase9709e82016-01-07 13:34:16 -08001096 b = next;
1097 }
1098 }
1099 if (a) {
senorblancoe6eaa322016-03-08 09:06:44 -08001100 vertices.insert(a, vertices.fTail, a->fNext);
ethannicholase9709e82016-01-07 13:34:16 -08001101 }
1102 if (b) {
senorblancoe6eaa322016-03-08 09:06:44 -08001103 vertices.insert(b, vertices.fTail, b->fNext);
ethannicholase9709e82016-01-07 13:34:16 -08001104 }
senorblancoe6eaa322016-03-08 09:06:44 -08001105 return vertices.fHead;
ethannicholase9709e82016-01-07 13:34:16 -08001106}
1107
1108// Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
1109
1110void 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
1162Poly* 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
1280Poly* 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
1319Poly* 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
1331void 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
1350int 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
1362namespace GrTessellator {
1363
1364// Stage 6: Triangulate the monotone polygons into a vertex buffer.
1365
1366int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
senorblanco6599eff2016-03-10 08:38:45 -08001367 VertexAllocator* vertexAllocator, bool* isLinear) {
ethannicholase9709e82016-01-07 13:34:16 -08001368 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
senorblanco6599eff2016-03-10 08:38:45 -08001383 SkPoint* verts = vertexAllocator->lock(count);
1384 if (!verts) {
ethannicholase9709e82016-01-07 13:34:16 -08001385 SkDebugf("Could not allocate vertices\n");
1386 return 0;
1387 }
ethannicholase9709e82016-01-07 13:34:16 -08001388 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);
senorblanco6599eff2016-03-10 08:38:45 -08001397 vertexAllocator->unlock(actualCount);
ethannicholase9709e82016-01-07 13:34:16 -08001398 return actualCount;
1399}
1400
1401int 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