blob: 0a0cef91145ea8f28f41e3b69a490e6b701f4765 [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
Mike Kleinc0bd9f92019-04-23 12:05:21 -05008#include "src/gpu/GrTessellator.h"
ethannicholase9709e82016-01-07 13:34:16 -08009
Mike Kleinc0bd9f92019-04-23 12:05:21 -050010#include "src/gpu/GrDefaultGeoProcFactory.h"
11#include "src/gpu/GrPathUtils.h"
12#include "src/gpu/GrVertexWriter.h"
ethannicholase9709e82016-01-07 13:34:16 -080013
Mike Kleinc0bd9f92019-04-23 12:05:21 -050014#include "include/core/SkPath.h"
Ben Wagner729a23f2019-05-17 16:29:34 -040015#include "src/core/SkArenaAlloc.h"
Mike Kleinc0bd9f92019-04-23 12:05:21 -050016#include "src/core/SkGeometry.h"
17#include "src/core/SkPointPriv.h"
ethannicholase9709e82016-01-07 13:34:16 -080018
Stephen White94b7e542018-01-04 14:01:10 -050019#include <algorithm>
Ben Wagnerf08d1d02018-06-18 15:11:00 -040020#include <cstdio>
Stephen Whitec4dbc372019-05-22 10:50:14 -040021#include <queue>
22#include <unordered_map>
Ben Wagnerf08d1d02018-06-18 15:11:00 -040023#include <utility>
ethannicholase9709e82016-01-07 13:34:16 -080024
25/*
senorblancof57372d2016-08-31 10:36:19 -070026 * There are six stages to the basic algorithm:
ethannicholase9709e82016-01-07 13:34:16 -080027 *
28 * 1) Linearize the path contours into piecewise linear segments (path_to_contours()).
29 * 2) Build a mesh of edges connecting the vertices (build_edges()).
30 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()).
31 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplify()).
32 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()).
33 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_triangles()).
34 *
senorblancof57372d2016-08-31 10:36:19 -070035 * For screenspace antialiasing, the algorithm is modified as follows:
36 *
37 * Run steps 1-5 above to produce polygons.
38 * 5b) Apply fill rules to extract boundary contours from the polygons (extract_boundaries()).
Stephen Whitebda29c02017-03-13 15:10:13 -040039 * 5c) Simplify boundaries to remove "pointy" vertices that cause inversions (simplify_boundary()).
senorblancof57372d2016-08-31 10:36:19 -070040 * 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find
41 * new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a new
Stephen Whitebda29c02017-03-13 15:10:13 -040042 * antialiased mesh from those vertices (stroke_boundary()).
senorblancof57372d2016-08-31 10:36:19 -070043 * Run steps 3-6 above on the new mesh, and produce antialiased triangles.
44 *
ethannicholase9709e82016-01-07 13:34:16 -080045 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
46 * of vertices (and the necessity of inserting new vertices on intersection).
47 *
Stephen Whitebda29c02017-03-13 15:10:13 -040048 * Stages (4) and (5) use an active edge list -- a list of all edges for which the
ethannicholase9709e82016-01-07 13:34:16 -080049 * sweep line has crossed the top vertex, but not the bottom vertex. It's sorted
50 * left-to-right based on the point where both edges are active (when both top vertices
51 * have been seen, so the "lower" top vertex of the two). If the top vertices are equal
52 * (shared), it's sorted based on the last point where both edges are active, so the
53 * "upper" bottom vertex.
54 *
55 * The most complex step is the simplification (4). It's based on the Bentley-Ottman
56 * line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
57 * not exact and may violate the mesh topology or active edge list ordering. We
58 * accommodate this by adjusting the topology of the mesh and AEL to match the intersection
Stephen White3b5a3fa2017-06-06 14:51:19 -040059 * points. This occurs in two ways:
ethannicholase9709e82016-01-07 13:34:16 -080060 *
61 * A) Intersections may cause a shortened edge to no longer be ordered with respect to its
62 * neighbouring edges at the top or bottom vertex. This is handled by merging the
63 * edges (merge_collinear_edges()).
64 * B) Intersections may cause an edge to violate the left-to-right ordering of the
Stephen White019f6c02017-06-09 10:06:26 -040065 * active edge list. This is handled by detecting potential violations and rewinding
Stephen White3b5a3fa2017-06-06 14:51:19 -040066 * the active edge list to the vertex before they occur (rewind() during merging,
67 * rewind_if_necessary() during splitting).
ethannicholase9709e82016-01-07 13:34:16 -080068 *
69 * The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
70 * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
71 * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
72 * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
73 * become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
74 * insertions and removals was greater than the cost of infrequent O(N) lookups with the
75 * linked list implementation. With the latter, all removals are O(1), and most insertions
76 * are O(1), since we know the adjacent edge in the active edge list based on the topology.
77 * Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
78 * frequent. There may be other data structures worth investigating, however.
79 *
80 * Note that the orientation of the line sweep algorithms is determined by the aspect ratio of the
81 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y
82 * coordinate, and secondarily by increasing X coordinate. When the path is wider than it is tall,
83 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordinate. This is so
84 * that the "left" and "right" orientation in the code remains correct (edges to the left are
85 * increasing in Y; edges to the right are decreasing in Y). That is, the setting rotates 90
86 * degrees counterclockwise, rather that transposing.
87 */
88
89#define LOGGING_ENABLED 0
90
91#if LOGGING_ENABLED
92#define LOG printf
93#else
94#define LOG(...)
95#endif
96
ethannicholase9709e82016-01-07 13:34:16 -080097namespace {
98
Stephen White11f65e02017-02-16 19:00:39 -050099const int kArenaChunkSize = 16 * 1024;
Stephen Whitee260c462017-12-19 18:09:54 -0500100const float kCosMiterAngle = 0.97f; // Corresponds to an angle of ~14 degrees.
Stephen White11f65e02017-02-16 19:00:39 -0500101
ethannicholase9709e82016-01-07 13:34:16 -0800102struct Vertex;
103struct Edge;
Stephen Whitee260c462017-12-19 18:09:54 -0500104struct Event;
ethannicholase9709e82016-01-07 13:34:16 -0800105struct Poly;
106
107template <class T, T* T::*Prev, T* T::*Next>
senorblancoe6eaa322016-03-08 09:06:44 -0800108void list_insert(T* t, T* prev, T* next, T** head, T** tail) {
ethannicholase9709e82016-01-07 13:34:16 -0800109 t->*Prev = prev;
110 t->*Next = next;
111 if (prev) {
112 prev->*Next = t;
113 } else if (head) {
114 *head = t;
115 }
116 if (next) {
117 next->*Prev = t;
118 } else if (tail) {
119 *tail = t;
120 }
121}
122
123template <class T, T* T::*Prev, T* T::*Next>
senorblancoe6eaa322016-03-08 09:06:44 -0800124void list_remove(T* t, T** head, T** tail) {
ethannicholase9709e82016-01-07 13:34:16 -0800125 if (t->*Prev) {
126 t->*Prev->*Next = t->*Next;
127 } else if (head) {
128 *head = t->*Next;
129 }
130 if (t->*Next) {
131 t->*Next->*Prev = t->*Prev;
132 } else if (tail) {
133 *tail = t->*Prev;
134 }
135 t->*Prev = t->*Next = nullptr;
136}
137
138/**
139 * Vertices are used in three ways: first, the path contours are converted into a
140 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
141 * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
142 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
143 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
144 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
145 * an individual Vertex from the path mesh may belong to multiple
146 * MonotonePolys, so the original Vertices cannot be re-used.
147 */
148
149struct Vertex {
senorblancof57372d2016-08-31 10:36:19 -0700150 Vertex(const SkPoint& point, uint8_t alpha)
ethannicholase9709e82016-01-07 13:34:16 -0800151 : fPoint(point), fPrev(nullptr), fNext(nullptr)
152 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
153 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
Stephen White3b5a3fa2017-06-06 14:51:19 -0400154 , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
Stephen Whitebda29c02017-03-13 15:10:13 -0400155 , fPartner(nullptr)
senorblancof57372d2016-08-31 10:36:19 -0700156 , fAlpha(alpha)
Stephen Whitec4dbc372019-05-22 10:50:14 -0400157 , fSynthetic(false)
ethannicholase9709e82016-01-07 13:34:16 -0800158#if LOGGING_ENABLED
159 , fID (-1.0f)
160#endif
161 {}
Stephen White3b5a3fa2017-06-06 14:51:19 -0400162 SkPoint fPoint; // Vertex position
163 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
164 Vertex* fNext; // "
165 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
166 Edge* fLastEdgeAbove; // "
167 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
168 Edge* fLastEdgeBelow; // "
169 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
170 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
171 Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
senorblancof57372d2016-08-31 10:36:19 -0700172 uint8_t fAlpha;
Stephen Whitec4dbc372019-05-22 10:50:14 -0400173 bool fSynthetic; // Is this a synthetic vertex?
ethannicholase9709e82016-01-07 13:34:16 -0800174#if LOGGING_ENABLED
Stephen White3b5a3fa2017-06-06 14:51:19 -0400175 float fID; // Identifier used for logging.
ethannicholase9709e82016-01-07 13:34:16 -0800176#endif
177};
178
179/***************************************************************************************/
180
181typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
182
ethannicholase9709e82016-01-07 13:34:16 -0800183bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) {
Stephen White16a40cb2017-02-23 11:10:01 -0500184 return a.fX < b.fX || (a.fX == b.fX && a.fY > b.fY);
ethannicholase9709e82016-01-07 13:34:16 -0800185}
186
187bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) {
Stephen White16a40cb2017-02-23 11:10:01 -0500188 return a.fY < b.fY || (a.fY == b.fY && a.fX < b.fX);
ethannicholase9709e82016-01-07 13:34:16 -0800189}
190
Stephen White16a40cb2017-02-23 11:10:01 -0500191struct Comparator {
192 enum class Direction { kVertical, kHorizontal };
193 Comparator(Direction direction) : fDirection(direction) {}
194 bool sweep_lt(const SkPoint& a, const SkPoint& b) const {
195 return fDirection == Direction::kHorizontal ? sweep_lt_horiz(a, b) : sweep_lt_vert(a, b);
196 }
Stephen White16a40cb2017-02-23 11:10:01 -0500197 Direction fDirection;
198};
199
Brian Osman0995fd52019-01-09 09:52:25 -0500200inline void* emit_vertex(Vertex* v, bool emitCoverage, void* data) {
Brian Osmanf9aabff2018-11-13 16:11:38 -0500201 GrVertexWriter verts{data};
202 verts.write(v->fPoint);
203
Brian Osman80879d42019-01-07 16:15:27 -0500204 if (emitCoverage) {
205 verts.write(GrNormalizeByteToFloat(v->fAlpha));
206 }
Brian Osman0995fd52019-01-09 09:52:25 -0500207
Brian Osmanf9aabff2018-11-13 16:11:38 -0500208 return verts.fPtr;
ethannicholase9709e82016-01-07 13:34:16 -0800209}
210
Brian Osman0995fd52019-01-09 09:52:25 -0500211void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, bool emitCoverage, void* data) {
Stephen White95152e12017-12-18 10:52:44 -0500212 LOG("emit_triangle %g (%g, %g) %d\n", v0->fID, v0->fPoint.fX, v0->fPoint.fY, v0->fAlpha);
213 LOG(" %g (%g, %g) %d\n", v1->fID, v1->fPoint.fX, v1->fPoint.fY, v1->fAlpha);
214 LOG(" %g (%g, %g) %d\n", v2->fID, v2->fPoint.fX, v2->fPoint.fY, v2->fAlpha);
senorblancof57372d2016-08-31 10:36:19 -0700215#if TESSELLATOR_WIREFRAME
Brian Osman0995fd52019-01-09 09:52:25 -0500216 data = emit_vertex(v0, emitCoverage, data);
217 data = emit_vertex(v1, emitCoverage, data);
218 data = emit_vertex(v1, emitCoverage, data);
219 data = emit_vertex(v2, emitCoverage, data);
220 data = emit_vertex(v2, emitCoverage, data);
221 data = emit_vertex(v0, emitCoverage, data);
ethannicholase9709e82016-01-07 13:34:16 -0800222#else
Brian Osman0995fd52019-01-09 09:52:25 -0500223 data = emit_vertex(v0, emitCoverage, data);
224 data = emit_vertex(v1, emitCoverage, data);
225 data = emit_vertex(v2, emitCoverage, data);
ethannicholase9709e82016-01-07 13:34:16 -0800226#endif
227 return data;
228}
229
senorblancoe6eaa322016-03-08 09:06:44 -0800230struct VertexList {
231 VertexList() : fHead(nullptr), fTail(nullptr) {}
Stephen White16a40cb2017-02-23 11:10:01 -0500232 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {}
senorblancoe6eaa322016-03-08 09:06:44 -0800233 Vertex* fHead;
234 Vertex* fTail;
235 void insert(Vertex* v, Vertex* prev, Vertex* next) {
236 list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail);
237 }
238 void append(Vertex* v) {
239 insert(v, fTail, nullptr);
240 }
Stephen Whitebda29c02017-03-13 15:10:13 -0400241 void append(const VertexList& list) {
242 if (!list.fHead) {
243 return;
244 }
245 if (fTail) {
246 fTail->fNext = list.fHead;
247 list.fHead->fPrev = fTail;
248 } else {
249 fHead = list.fHead;
250 }
251 fTail = list.fTail;
252 }
senorblancoe6eaa322016-03-08 09:06:44 -0800253 void prepend(Vertex* v) {
254 insert(v, nullptr, fHead);
255 }
Stephen Whitebf6137e2017-01-04 15:43:26 -0500256 void remove(Vertex* v) {
257 list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, &fHead, &fTail);
258 }
senorblancof57372d2016-08-31 10:36:19 -0700259 void close() {
260 if (fHead && fTail) {
261 fTail->fNext = fHead;
262 fHead->fPrev = fTail;
263 }
264 }
senorblancoe6eaa322016-03-08 09:06:44 -0800265};
266
senorblancof57372d2016-08-31 10:36:19 -0700267// Round to nearest quarter-pixel. This is used for screenspace tessellation.
268
269inline void round(SkPoint* p) {
270 p->fX = SkScalarRoundToScalar(p->fX * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
271 p->fY = SkScalarRoundToScalar(p->fY * SkFloatToScalar(4.0f)) * SkFloatToScalar(0.25f);
272}
273
Stephen White94b7e542018-01-04 14:01:10 -0500274inline SkScalar double_to_clamped_scalar(double d) {
275 return SkDoubleToScalar(std::min((double) SK_ScalarMax, std::max(d, (double) -SK_ScalarMax)));
276}
277
senorblanco49df8d12016-10-07 08:36:56 -0700278// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
279struct Line {
Stephen Whitee260c462017-12-19 18:09:54 -0500280 Line(double a, double b, double c) : fA(a), fB(b), fC(c) {}
senorblanco49df8d12016-10-07 08:36:56 -0700281 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
282 Line(const SkPoint& p, const SkPoint& q)
283 : fA(static_cast<double>(q.fY) - p.fY) // a = dY
284 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX
285 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p)
286 static_cast<double>(p.fX) * q.fY) {}
287 double dist(const SkPoint& p) const {
288 return fA * p.fX + fB * p.fY + fC;
289 }
Stephen Whitee260c462017-12-19 18:09:54 -0500290 Line operator*(double v) const {
291 return Line(fA * v, fB * v, fC * v);
292 }
senorblanco49df8d12016-10-07 08:36:56 -0700293 double magSq() const {
294 return fA * fA + fB * fB;
295 }
Stephen Whitee260c462017-12-19 18:09:54 -0500296 void normalize() {
297 double len = sqrt(this->magSq());
298 if (len == 0.0) {
299 return;
300 }
301 double scale = 1.0f / len;
302 fA *= scale;
303 fB *= scale;
304 fC *= scale;
305 }
306 bool nearParallel(const Line& o) const {
307 return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001;
308 }
senorblanco49df8d12016-10-07 08:36:56 -0700309
310 // Compute the intersection of two (infinite) Lines.
Stephen White95152e12017-12-18 10:52:44 -0500311 bool intersect(const Line& other, SkPoint* point) const {
senorblanco49df8d12016-10-07 08:36:56 -0700312 double denom = fA * other.fB - fB * other.fA;
313 if (denom == 0.0) {
314 return false;
315 }
Stephen White94b7e542018-01-04 14:01:10 -0500316 double scale = 1.0 / denom;
317 point->fX = double_to_clamped_scalar((fB * other.fC - other.fB * fC) * scale);
318 point->fY = double_to_clamped_scalar((other.fA * fC - fA * other.fC) * scale);
Stephen Whiteb56dedf2017-03-02 10:35:56 -0500319 round(point);
senorblanco49df8d12016-10-07 08:36:56 -0700320 return true;
321 }
322 double fA, fB, fC;
323};
324
ethannicholase9709e82016-01-07 13:34:16 -0800325/**
326 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
327 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
328 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
Stephen Whitebda29c02017-03-13 15:10:13 -0400329 * point). For speed, that case is only tested by the callers that require it (e.g.,
Stephen White3b5a3fa2017-06-06 14:51:19 -0400330 * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
ethannicholase9709e82016-01-07 13:34:16 -0800331 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
332 * until an intersection has been confirmed. This is slightly slower in the "found" case, but
333 * a lot faster in the "not found" case.
334 *
335 * The coefficients of the line equation stored in double precision to avoid catastrphic
336 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
337 * correct in float, since it's a polynomial of degree 2. The intersect() function, being
338 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
339 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
340 * this file).
341 */
342
343struct Edge {
Stephen White2f4686f2017-01-03 16:20:01 -0500344 enum class Type { kInner, kOuter, kConnector };
345 Edge(Vertex* top, Vertex* bottom, int winding, Type type)
ethannicholase9709e82016-01-07 13:34:16 -0800346 : fWinding(winding)
347 , fTop(top)
348 , fBottom(bottom)
Stephen White2f4686f2017-01-03 16:20:01 -0500349 , fType(type)
ethannicholase9709e82016-01-07 13:34:16 -0800350 , fLeft(nullptr)
351 , fRight(nullptr)
352 , fPrevEdgeAbove(nullptr)
353 , fNextEdgeAbove(nullptr)
354 , fPrevEdgeBelow(nullptr)
355 , fNextEdgeBelow(nullptr)
356 , fLeftPoly(nullptr)
senorblanco531237e2016-06-02 11:36:48 -0700357 , fRightPoly(nullptr)
358 , fLeftPolyPrev(nullptr)
359 , fLeftPolyNext(nullptr)
360 , fRightPolyPrev(nullptr)
senorblanco70f52512016-08-17 14:56:22 -0700361 , fRightPolyNext(nullptr)
362 , fUsedInLeftPoly(false)
senorblanco49df8d12016-10-07 08:36:56 -0700363 , fUsedInRightPoly(false)
364 , fLine(top, bottom) {
ethannicholase9709e82016-01-07 13:34:16 -0800365 }
366 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
367 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt).
368 Vertex* fBottom; // The bottom vertex in vertex-sort-order.
Stephen White2f4686f2017-01-03 16:20:01 -0500369 Type fType;
ethannicholase9709e82016-01-07 13:34:16 -0800370 Edge* fLeft; // The linked list of edges in the active edge list.
371 Edge* fRight; // "
372 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
373 Edge* fNextEdgeAbove; // "
374 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
375 Edge* fNextEdgeBelow; // "
376 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
377 Poly* fRightPoly; // The Poly to the right of this edge, if any.
senorblanco531237e2016-06-02 11:36:48 -0700378 Edge* fLeftPolyPrev;
379 Edge* fLeftPolyNext;
380 Edge* fRightPolyPrev;
381 Edge* fRightPolyNext;
senorblanco70f52512016-08-17 14:56:22 -0700382 bool fUsedInLeftPoly;
383 bool fUsedInRightPoly;
senorblanco49df8d12016-10-07 08:36:56 -0700384 Line fLine;
ethannicholase9709e82016-01-07 13:34:16 -0800385 double dist(const SkPoint& p) const {
senorblanco49df8d12016-10-07 08:36:56 -0700386 return fLine.dist(p);
ethannicholase9709e82016-01-07 13:34:16 -0800387 }
388 bool isRightOf(Vertex* v) const {
senorblanco49df8d12016-10-07 08:36:56 -0700389 return fLine.dist(v->fPoint) < 0.0;
ethannicholase9709e82016-01-07 13:34:16 -0800390 }
391 bool isLeftOf(Vertex* v) const {
senorblanco49df8d12016-10-07 08:36:56 -0700392 return fLine.dist(v->fPoint) > 0.0;
ethannicholase9709e82016-01-07 13:34:16 -0800393 }
394 void recompute() {
senorblanco49df8d12016-10-07 08:36:56 -0700395 fLine = Line(fTop, fBottom);
ethannicholase9709e82016-01-07 13:34:16 -0800396 }
Stephen White95152e12017-12-18 10:52:44 -0500397 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const {
ethannicholase9709e82016-01-07 13:34:16 -0800398 LOG("intersecting %g -> %g with %g -> %g\n",
399 fTop->fID, fBottom->fID,
400 other.fTop->fID, other.fBottom->fID);
401 if (fTop == other.fTop || fBottom == other.fBottom) {
402 return false;
403 }
senorblanco49df8d12016-10-07 08:36:56 -0700404 double denom = fLine.fA * other.fLine.fB - fLine.fB * other.fLine.fA;
ethannicholase9709e82016-01-07 13:34:16 -0800405 if (denom == 0.0) {
406 return false;
407 }
Stephen White8a0bfc52017-02-21 15:24:13 -0500408 double dx = static_cast<double>(other.fTop->fPoint.fX) - fTop->fPoint.fX;
409 double dy = static_cast<double>(other.fTop->fPoint.fY) - fTop->fPoint.fY;
410 double sNumer = dy * other.fLine.fB + dx * other.fLine.fA;
411 double tNumer = dy * fLine.fB + dx * fLine.fA;
ethannicholase9709e82016-01-07 13:34:16 -0800412 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early.
413 // This saves us doing the divide below unless absolutely necessary.
414 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
415 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
416 return false;
417 }
418 double s = sNumer / denom;
419 SkASSERT(s >= 0.0 && s <= 1.0);
senorblanco49df8d12016-10-07 08:36:56 -0700420 p->fX = SkDoubleToScalar(fTop->fPoint.fX - s * fLine.fB);
421 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fLine.fA);
Stephen White56158ae2017-01-30 14:31:31 -0500422 if (alpha) {
Stephen White92eba8a2017-02-06 09:50:27 -0500423 if (fType == Type::kConnector) {
424 *alpha = (1.0 - s) * fTop->fAlpha + s * fBottom->fAlpha;
425 } else if (other.fType == Type::kConnector) {
426 double t = tNumer / denom;
427 *alpha = (1.0 - t) * other.fTop->fAlpha + t * other.fBottom->fAlpha;
Stephen White56158ae2017-01-30 14:31:31 -0500428 } else if (fType == Type::kOuter && other.fType == Type::kOuter) {
429 *alpha = 0;
430 } else {
Stephen White92eba8a2017-02-06 09:50:27 -0500431 *alpha = 255;
Stephen White56158ae2017-01-30 14:31:31 -0500432 }
433 }
ethannicholase9709e82016-01-07 13:34:16 -0800434 return true;
435 }
senorblancof57372d2016-08-31 10:36:19 -0700436};
437
Stephen Whitec4dbc372019-05-22 10:50:14 -0400438struct SSEdge;
439
440struct SSVertex {
441 SSVertex(Vertex* v) : fVertex(v), fPrev(nullptr), fNext(nullptr) {}
442 Vertex* fVertex;
443 SSEdge* fPrev;
444 SSEdge* fNext;
445};
446
447struct SSEdge {
448 SSEdge(Edge* edge, SSVertex* prev, SSVertex* next)
449 : fEdge(edge), fEvent(nullptr), fPrev(prev), fNext(next) {
450 }
451 Edge* fEdge;
452 Event* fEvent;
453 SSVertex* fPrev;
454 SSVertex* fNext;
455};
456
457typedef std::unordered_map<Vertex*, SSVertex*> SSVertexMap;
458typedef std::vector<SSEdge*> SSEdgeList;
459
senorblancof57372d2016-08-31 10:36:19 -0700460struct EdgeList {
Stephen White5ad721e2017-02-23 16:50:47 -0500461 EdgeList() : fHead(nullptr), fTail(nullptr) {}
senorblancof57372d2016-08-31 10:36:19 -0700462 Edge* fHead;
463 Edge* fTail;
senorblancof57372d2016-08-31 10:36:19 -0700464 void insert(Edge* edge, Edge* prev, Edge* next) {
465 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail);
senorblancof57372d2016-08-31 10:36:19 -0700466 }
467 void append(Edge* e) {
468 insert(e, fTail, nullptr);
469 }
470 void remove(Edge* edge) {
471 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
senorblancof57372d2016-08-31 10:36:19 -0700472 }
Stephen Whitebda29c02017-03-13 15:10:13 -0400473 void removeAll() {
474 while (fHead) {
475 this->remove(fHead);
476 }
477 }
senorblancof57372d2016-08-31 10:36:19 -0700478 void close() {
479 if (fHead && fTail) {
480 fTail->fRight = fHead;
481 fHead->fLeft = fTail;
482 }
483 }
484 bool contains(Edge* edge) const {
485 return edge->fLeft || edge->fRight || fHead == edge;
ethannicholase9709e82016-01-07 13:34:16 -0800486 }
487};
488
Stephen Whitec4dbc372019-05-22 10:50:14 -0400489struct EventList;
490
Stephen Whitee260c462017-12-19 18:09:54 -0500491struct Event {
Stephen Whitec4dbc372019-05-22 10:50:14 -0400492 Event(SSEdge* edge, const SkPoint& point, uint8_t alpha)
493 : fEdge(edge), fPoint(point), fAlpha(alpha) {
Stephen Whitee260c462017-12-19 18:09:54 -0500494 }
Stephen Whitec4dbc372019-05-22 10:50:14 -0400495 SSEdge* fEdge;
Stephen Whitee260c462017-12-19 18:09:54 -0500496 SkPoint fPoint;
497 uint8_t fAlpha;
Stephen Whitec4dbc372019-05-22 10:50:14 -0400498 void apply(VertexList* mesh, Comparator& c, EventList* events, SkArenaAlloc& alloc);
Stephen Whitee260c462017-12-19 18:09:54 -0500499};
500
Stephen Whitec4dbc372019-05-22 10:50:14 -0400501struct EventComparator {
502 enum class Op { kLessThan, kGreaterThan };
503 EventComparator(Op op) : fOp(op) {}
504 bool operator() (Event* const &e1, Event* const &e2) {
505 return fOp == Op::kLessThan ? e1->fAlpha < e2->fAlpha
506 : e1->fAlpha > e2->fAlpha;
507 }
508 Op fOp;
509};
Stephen Whitee260c462017-12-19 18:09:54 -0500510
Stephen Whitec4dbc372019-05-22 10:50:14 -0400511typedef std::priority_queue<Event*, std::vector<Event*>, EventComparator> EventPQ;
Stephen Whitee260c462017-12-19 18:09:54 -0500512
Stephen Whitec4dbc372019-05-22 10:50:14 -0400513struct EventList : EventPQ {
514 EventList(EventComparator comparison) : EventPQ(comparison) {
515 }
516};
517
518void create_event(SSEdge* e, EventList* events, SkArenaAlloc& alloc) {
519 Vertex* prev = e->fPrev->fVertex;
520 Vertex* next = e->fNext->fVertex;
521 if (prev == next || !prev->fPartner || !next->fPartner) {
522 return;
523 }
524 Edge bisector1(prev, prev->fPartner, 1, Edge::Type::kConnector);
525 Edge bisector2(next, next->fPartner, 1, Edge::Type::kConnector);
Stephen Whitee260c462017-12-19 18:09:54 -0500526 SkPoint p;
527 uint8_t alpha;
528 if (bisector1.intersect(bisector2, &p, &alpha)) {
Stephen Whitec4dbc372019-05-22 10:50:14 -0400529 LOG("found edge event for %g, %g (original %g -> %g), will collapse to %g,%g alpha %d\n",
530 prev->fID, next->fID, e->fEdge->fTop->fID, e->fEdge->fBottom->fID, p.fX, p.fY, alpha);
531 e->fEvent = alloc.make<Event>(e, p, alpha);
532 events->push(e->fEvent);
533 }
534}
535
536void create_event(SSEdge* edge, Vertex* v, SSEdge* other, Vertex* dest, EventList* events,
537 Comparator& c, SkArenaAlloc& alloc) {
538 if (!v->fPartner) {
539 return;
540 }
541 Line line = edge->fEdge->fLine;
542 line.fC = -(dest->fPoint.fX * line.fA + dest->fPoint.fY * line.fB);
543 Edge bisector(v, v->fPartner, 1, Edge::Type::kConnector);
544 SkPoint p;
545 uint8_t alpha = dest->fAlpha;
546 if (line.intersect(bisector.fLine, &p) && !c.sweep_lt(p, edge->fEdge->fTop->fPoint) &&
547 c.sweep_lt(p, edge->fEdge->fBottom->fPoint)) {
548 LOG("found p edge event for %g, %g (original %g -> %g), will collapse to %g,%g alpha %d\n",
549 dest->fID, v->fID, edge->fEdge->fTop->fID, edge->fEdge->fBottom->fID, p.fX, p.fY,
550 alpha);
551 edge->fEvent = alloc.make<Event>(edge, p, alpha);
552 events->push(edge->fEvent);
Stephen Whitee260c462017-12-19 18:09:54 -0500553 }
554}
Stephen Whitee260c462017-12-19 18:09:54 -0500555
ethannicholase9709e82016-01-07 13:34:16 -0800556/***************************************************************************************/
557
558struct Poly {
senorblanco531237e2016-06-02 11:36:48 -0700559 Poly(Vertex* v, int winding)
560 : fFirstVertex(v)
561 , fWinding(winding)
ethannicholase9709e82016-01-07 13:34:16 -0800562 , fHead(nullptr)
563 , fTail(nullptr)
ethannicholase9709e82016-01-07 13:34:16 -0800564 , fNext(nullptr)
565 , fPartner(nullptr)
566 , fCount(0)
567 {
568#if LOGGING_ENABLED
569 static int gID = 0;
570 fID = gID++;
571 LOG("*** created Poly %d\n", fID);
572#endif
573 }
senorblanco531237e2016-06-02 11:36:48 -0700574 typedef enum { kLeft_Side, kRight_Side } Side;
ethannicholase9709e82016-01-07 13:34:16 -0800575 struct MonotonePoly {
senorblanco531237e2016-06-02 11:36:48 -0700576 MonotonePoly(Edge* edge, Side side)
577 : fSide(side)
578 , fFirstEdge(nullptr)
579 , fLastEdge(nullptr)
ethannicholase9709e82016-01-07 13:34:16 -0800580 , fPrev(nullptr)
senorblanco531237e2016-06-02 11:36:48 -0700581 , fNext(nullptr) {
582 this->addEdge(edge);
583 }
ethannicholase9709e82016-01-07 13:34:16 -0800584 Side fSide;
senorblanco531237e2016-06-02 11:36:48 -0700585 Edge* fFirstEdge;
586 Edge* fLastEdge;
ethannicholase9709e82016-01-07 13:34:16 -0800587 MonotonePoly* fPrev;
588 MonotonePoly* fNext;
senorblanco531237e2016-06-02 11:36:48 -0700589 void addEdge(Edge* edge) {
senorblancoe6eaa322016-03-08 09:06:44 -0800590 if (fSide == kRight_Side) {
senorblanco212c7c32016-08-18 10:20:47 -0700591 SkASSERT(!edge->fUsedInRightPoly);
senorblanco531237e2016-06-02 11:36:48 -0700592 list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>(
593 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
senorblanco70f52512016-08-17 14:56:22 -0700594 edge->fUsedInRightPoly = true;
ethannicholase9709e82016-01-07 13:34:16 -0800595 } else {
senorblanco212c7c32016-08-18 10:20:47 -0700596 SkASSERT(!edge->fUsedInLeftPoly);
senorblanco531237e2016-06-02 11:36:48 -0700597 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
598 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
senorblanco70f52512016-08-17 14:56:22 -0700599 edge->fUsedInLeftPoly = true;
ethannicholase9709e82016-01-07 13:34:16 -0800600 }
ethannicholase9709e82016-01-07 13:34:16 -0800601 }
602
Brian Osman0995fd52019-01-09 09:52:25 -0500603 void* emit(bool emitCoverage, void* data) {
senorblanco531237e2016-06-02 11:36:48 -0700604 Edge* e = fFirstEdge;
senorblanco531237e2016-06-02 11:36:48 -0700605 VertexList vertices;
606 vertices.append(e->fTop);
Stephen White651cbe92017-03-03 12:24:16 -0500607 int count = 1;
senorblanco531237e2016-06-02 11:36:48 -0700608 while (e != nullptr) {
senorblanco531237e2016-06-02 11:36:48 -0700609 if (kRight_Side == fSide) {
610 vertices.append(e->fBottom);
611 e = e->fRightPolyNext;
612 } else {
613 vertices.prepend(e->fBottom);
614 e = e->fLeftPolyNext;
615 }
Stephen White651cbe92017-03-03 12:24:16 -0500616 count++;
senorblanco531237e2016-06-02 11:36:48 -0700617 }
618 Vertex* first = vertices.fHead;
ethannicholase9709e82016-01-07 13:34:16 -0800619 Vertex* v = first->fNext;
senorblanco531237e2016-06-02 11:36:48 -0700620 while (v != vertices.fTail) {
ethannicholase9709e82016-01-07 13:34:16 -0800621 SkASSERT(v && v->fPrev && v->fNext);
622 Vertex* prev = v->fPrev;
623 Vertex* curr = v;
624 Vertex* next = v->fNext;
Stephen White651cbe92017-03-03 12:24:16 -0500625 if (count == 3) {
Brian Osman0995fd52019-01-09 09:52:25 -0500626 return emit_triangle(prev, curr, next, emitCoverage, data);
Stephen White651cbe92017-03-03 12:24:16 -0500627 }
ethannicholase9709e82016-01-07 13:34:16 -0800628 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX;
629 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY;
630 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX;
631 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY;
632 if (ax * by - ay * bx >= 0.0) {
Brian Osman0995fd52019-01-09 09:52:25 -0500633 data = emit_triangle(prev, curr, next, emitCoverage, data);
ethannicholase9709e82016-01-07 13:34:16 -0800634 v->fPrev->fNext = v->fNext;
635 v->fNext->fPrev = v->fPrev;
Stephen White651cbe92017-03-03 12:24:16 -0500636 count--;
ethannicholase9709e82016-01-07 13:34:16 -0800637 if (v->fPrev == first) {
638 v = v->fNext;
639 } else {
640 v = v->fPrev;
641 }
642 } else {
643 v = v->fNext;
644 }
645 }
646 return data;
647 }
648 };
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500649 Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc) {
senorblanco70f52512016-08-17 14:56:22 -0700650 LOG("addEdge (%g -> %g) to poly %d, %s side\n",
651 e->fTop->fID, e->fBottom->fID, fID, side == kLeft_Side ? "left" : "right");
ethannicholase9709e82016-01-07 13:34:16 -0800652 Poly* partner = fPartner;
653 Poly* poly = this;
senorblanco212c7c32016-08-18 10:20:47 -0700654 if (side == kRight_Side) {
655 if (e->fUsedInRightPoly) {
656 return this;
657 }
658 } else {
659 if (e->fUsedInLeftPoly) {
660 return this;
661 }
662 }
ethannicholase9709e82016-01-07 13:34:16 -0800663 if (partner) {
664 fPartner = partner->fPartner = nullptr;
665 }
senorblanco531237e2016-06-02 11:36:48 -0700666 if (!fTail) {
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500667 fHead = fTail = alloc.make<MonotonePoly>(e, side);
senorblanco531237e2016-06-02 11:36:48 -0700668 fCount += 2;
senorblanco93e3fff2016-06-07 12:36:00 -0700669 } else if (e->fBottom == fTail->fLastEdge->fBottom) {
670 return poly;
senorblanco531237e2016-06-02 11:36:48 -0700671 } else if (side == fTail->fSide) {
672 fTail->addEdge(e);
673 fCount++;
674 } else {
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500675 e = alloc.make<Edge>(fTail->fLastEdge->fBottom, e->fBottom, 1, Edge::Type::kInner);
senorblanco531237e2016-06-02 11:36:48 -0700676 fTail->addEdge(e);
677 fCount++;
ethannicholase9709e82016-01-07 13:34:16 -0800678 if (partner) {
senorblanco531237e2016-06-02 11:36:48 -0700679 partner->addEdge(e, side, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800680 poly = partner;
681 } else {
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500682 MonotonePoly* m = alloc.make<MonotonePoly>(e, side);
senorblanco531237e2016-06-02 11:36:48 -0700683 m->fPrev = fTail;
684 fTail->fNext = m;
685 fTail = m;
ethannicholase9709e82016-01-07 13:34:16 -0800686 }
687 }
ethannicholase9709e82016-01-07 13:34:16 -0800688 return poly;
689 }
Brian Osman0995fd52019-01-09 09:52:25 -0500690 void* emit(bool emitCoverage, void *data) {
ethannicholase9709e82016-01-07 13:34:16 -0800691 if (fCount < 3) {
692 return data;
693 }
694 LOG("emit() %d, size %d\n", fID, fCount);
695 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) {
Brian Osman0995fd52019-01-09 09:52:25 -0500696 data = m->emit(emitCoverage, data);
ethannicholase9709e82016-01-07 13:34:16 -0800697 }
698 return data;
699 }
senorblanco531237e2016-06-02 11:36:48 -0700700 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
701 Vertex* fFirstVertex;
ethannicholase9709e82016-01-07 13:34:16 -0800702 int fWinding;
703 MonotonePoly* fHead;
704 MonotonePoly* fTail;
ethannicholase9709e82016-01-07 13:34:16 -0800705 Poly* fNext;
706 Poly* fPartner;
707 int fCount;
708#if LOGGING_ENABLED
709 int fID;
710#endif
711};
712
713/***************************************************************************************/
714
715bool coincident(const SkPoint& a, const SkPoint& b) {
716 return a == b;
717}
718
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500719Poly* new_poly(Poly** head, Vertex* v, int winding, SkArenaAlloc& alloc) {
720 Poly* poly = alloc.make<Poly>(v, winding);
ethannicholase9709e82016-01-07 13:34:16 -0800721 poly->fNext = *head;
722 *head = poly;
723 return poly;
724}
725
Stephen White3a9aab92017-03-07 14:07:18 -0500726void append_point_to_contour(const SkPoint& p, VertexList* contour, SkArenaAlloc& alloc) {
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500727 Vertex* v = alloc.make<Vertex>(p, 255);
ethannicholase9709e82016-01-07 13:34:16 -0800728#if LOGGING_ENABLED
729 static float gID = 0.0f;
730 v->fID = gID++;
731#endif
Stephen White3a9aab92017-03-07 14:07:18 -0500732 contour->append(v);
ethannicholase9709e82016-01-07 13:34:16 -0800733}
734
Stephen White36e4f062017-03-27 16:11:31 -0400735SkScalar quad_error_at(const SkPoint pts[3], SkScalar t, SkScalar u) {
736 SkQuadCoeff quad(pts);
737 SkPoint p0 = to_point(quad.eval(t - 0.5f * u));
738 SkPoint mid = to_point(quad.eval(t));
739 SkPoint p1 = to_point(quad.eval(t + 0.5f * u));
Stephen Whitee3a0be72017-06-12 11:43:18 -0400740 if (!p0.isFinite() || !mid.isFinite() || !p1.isFinite()) {
741 return 0;
742 }
Cary Clarkdf429f32017-11-08 11:44:31 -0500743 return SkPointPriv::DistanceToLineSegmentBetweenSqd(mid, p0, p1);
Stephen White36e4f062017-03-27 16:11:31 -0400744}
745
746void append_quadratic_to_contour(const SkPoint pts[3], SkScalar toleranceSqd, VertexList* contour,
747 SkArenaAlloc& alloc) {
748 SkQuadCoeff quad(pts);
749 Sk2s aa = quad.fA * quad.fA;
750 SkScalar denom = 2.0f * (aa[0] + aa[1]);
751 Sk2s ab = quad.fA * quad.fB;
752 SkScalar t = denom ? (-ab[0] - ab[1]) / denom : 0.0f;
753 int nPoints = 1;
Stephen Whitee40c3612018-01-09 11:49:08 -0500754 SkScalar u = 1.0f;
Stephen White36e4f062017-03-27 16:11:31 -0400755 // Test possible subdivision values only at the point of maximum curvature.
756 // If it passes the flatness metric there, it'll pass everywhere.
Stephen Whitee40c3612018-01-09 11:49:08 -0500757 while (nPoints < GrPathUtils::kMaxPointsPerCurve) {
Stephen White36e4f062017-03-27 16:11:31 -0400758 u = 1.0f / nPoints;
759 if (quad_error_at(pts, t, u) < toleranceSqd) {
760 break;
761 }
762 nPoints++;
ethannicholase9709e82016-01-07 13:34:16 -0800763 }
Stephen White36e4f062017-03-27 16:11:31 -0400764 for (int j = 1; j <= nPoints; j++) {
765 append_point_to_contour(to_point(quad.eval(j * u)), contour, alloc);
766 }
ethannicholase9709e82016-01-07 13:34:16 -0800767}
768
Stephen White3a9aab92017-03-07 14:07:18 -0500769void generate_cubic_points(const SkPoint& p0,
770 const SkPoint& p1,
771 const SkPoint& p2,
772 const SkPoint& p3,
773 SkScalar tolSqd,
774 VertexList* contour,
775 int pointsLeft,
776 SkArenaAlloc& alloc) {
Cary Clarkdf429f32017-11-08 11:44:31 -0500777 SkScalar d1 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3);
778 SkScalar d2 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3);
ethannicholase9709e82016-01-07 13:34:16 -0800779 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) ||
780 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) {
Stephen White3a9aab92017-03-07 14:07:18 -0500781 append_point_to_contour(p3, contour, alloc);
782 return;
ethannicholase9709e82016-01-07 13:34:16 -0800783 }
784 const SkPoint q[] = {
785 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
786 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
787 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
788 };
789 const SkPoint r[] = {
790 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
791 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
792 };
793 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
794 pointsLeft >>= 1;
Stephen White3a9aab92017-03-07 14:07:18 -0500795 generate_cubic_points(p0, q[0], r[0], s, tolSqd, contour, pointsLeft, alloc);
796 generate_cubic_points(s, r[1], q[2], p3, tolSqd, contour, pointsLeft, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800797}
798
799// Stage 1: convert the input path to a set of linear contours (linked list of Vertices).
800
801void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
Stephen White3a9aab92017-03-07 14:07:18 -0500802 VertexList* contours, SkArenaAlloc& alloc, bool *isLinear) {
ethannicholase9709e82016-01-07 13:34:16 -0800803 SkScalar toleranceSqd = tolerance * tolerance;
804
805 SkPoint pts[4];
ethannicholase9709e82016-01-07 13:34:16 -0800806 *isLinear = true;
Stephen White3a9aab92017-03-07 14:07:18 -0500807 VertexList* contour = contours;
ethannicholase9709e82016-01-07 13:34:16 -0800808 SkPath::Iter iter(path, false);
ethannicholase9709e82016-01-07 13:34:16 -0800809 if (path.isInverseFillType()) {
810 SkPoint quad[4];
811 clipBounds.toQuad(quad);
senorblanco7ab96e92016-10-12 06:47:44 -0700812 for (int i = 3; i >= 0; i--) {
Stephen White3a9aab92017-03-07 14:07:18 -0500813 append_point_to_contour(quad[i], contours, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800814 }
Stephen White3a9aab92017-03-07 14:07:18 -0500815 contour++;
ethannicholase9709e82016-01-07 13:34:16 -0800816 }
817 SkAutoConicToQuads converter;
Stephen White3a9aab92017-03-07 14:07:18 -0500818 SkPath::Verb verb;
Stephen White2cee2832017-08-23 09:37:16 -0400819 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
ethannicholase9709e82016-01-07 13:34:16 -0800820 switch (verb) {
821 case SkPath::kConic_Verb: {
822 SkScalar weight = iter.conicWeight();
823 const SkPoint* quadPts = converter.computeQuads(pts, weight, toleranceSqd);
824 for (int i = 0; i < converter.countQuads(); ++i) {
Stephen White36e4f062017-03-27 16:11:31 -0400825 append_quadratic_to_contour(quadPts, toleranceSqd, contour, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800826 quadPts += 2;
827 }
828 *isLinear = false;
829 break;
830 }
831 case SkPath::kMove_Verb:
Stephen White3a9aab92017-03-07 14:07:18 -0500832 if (contour->fHead) {
833 contour++;
ethannicholase9709e82016-01-07 13:34:16 -0800834 }
Stephen White3a9aab92017-03-07 14:07:18 -0500835 append_point_to_contour(pts[0], contour, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800836 break;
837 case SkPath::kLine_Verb: {
Stephen White3a9aab92017-03-07 14:07:18 -0500838 append_point_to_contour(pts[1], contour, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800839 break;
840 }
841 case SkPath::kQuad_Verb: {
Stephen White36e4f062017-03-27 16:11:31 -0400842 append_quadratic_to_contour(pts, toleranceSqd, contour, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800843 *isLinear = false;
844 break;
845 }
846 case SkPath::kCubic_Verb: {
847 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance);
Stephen White3a9aab92017-03-07 14:07:18 -0500848 generate_cubic_points(pts[0], pts[1], pts[2], pts[3], toleranceSqd, contour,
849 pointsLeft, alloc);
ethannicholase9709e82016-01-07 13:34:16 -0800850 *isLinear = false;
851 break;
852 }
853 case SkPath::kClose_Verb:
ethannicholase9709e82016-01-07 13:34:16 -0800854 case SkPath::kDone_Verb:
ethannicholase9709e82016-01-07 13:34:16 -0800855 break;
856 }
857 }
858}
859
Stephen White49789062017-02-21 10:35:49 -0500860inline bool apply_fill_type(SkPath::FillType fillType, int winding) {
ethannicholase9709e82016-01-07 13:34:16 -0800861 switch (fillType) {
862 case SkPath::kWinding_FillType:
863 return winding != 0;
864 case SkPath::kEvenOdd_FillType:
865 return (winding & 1) != 0;
866 case SkPath::kInverseWinding_FillType:
senorblanco7ab96e92016-10-12 06:47:44 -0700867 return winding == 1;
ethannicholase9709e82016-01-07 13:34:16 -0800868 case SkPath::kInverseEvenOdd_FillType:
869 return (winding & 1) == 1;
870 default:
871 SkASSERT(false);
872 return false;
873 }
874}
875
Stephen White49789062017-02-21 10:35:49 -0500876inline bool apply_fill_type(SkPath::FillType fillType, Poly* poly) {
877 return poly && apply_fill_type(fillType, poly->fWinding);
878}
879
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500880Edge* new_edge(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc) {
Stephen White2f4686f2017-01-03 16:20:01 -0500881 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
ethannicholase9709e82016-01-07 13:34:16 -0800882 Vertex* top = winding < 0 ? next : prev;
883 Vertex* bottom = winding < 0 ? prev : next;
Herb Derby5cdc9dd2017-02-13 12:10:46 -0500884 return alloc.make<Edge>(top, bottom, winding, type);
ethannicholase9709e82016-01-07 13:34:16 -0800885}
886
887void remove_edge(Edge* edge, EdgeList* edges) {
888 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
senorblancof57372d2016-08-31 10:36:19 -0700889 SkASSERT(edges->contains(edge));
890 edges->remove(edge);
ethannicholase9709e82016-01-07 13:34:16 -0800891}
892
893void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
894 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
senorblancof57372d2016-08-31 10:36:19 -0700895 SkASSERT(!edges->contains(edge));
ethannicholase9709e82016-01-07 13:34:16 -0800896 Edge* next = prev ? prev->fRight : edges->fHead;
senorblancof57372d2016-08-31 10:36:19 -0700897 edges->insert(edge, prev, next);
ethannicholase9709e82016-01-07 13:34:16 -0800898}
899
900void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
Stephen White90732fd2017-03-02 16:16:33 -0500901 if (v->fFirstEdgeAbove && v->fLastEdgeAbove) {
ethannicholase9709e82016-01-07 13:34:16 -0800902 *left = v->fFirstEdgeAbove->fLeft;
903 *right = v->fLastEdgeAbove->fRight;
904 return;
905 }
906 Edge* next = nullptr;
907 Edge* prev;
908 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) {
909 if (prev->isLeftOf(v)) {
910 break;
911 }
912 next = prev;
913 }
914 *left = prev;
915 *right = next;
ethannicholase9709e82016-01-07 13:34:16 -0800916}
917
ethannicholase9709e82016-01-07 13:34:16 -0800918void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
919 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
Stephen Whitee30cf802017-02-27 11:37:55 -0500920 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
ethannicholase9709e82016-01-07 13:34:16 -0800921 return;
922 }
923 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
924 Edge* prev = nullptr;
925 Edge* next;
926 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
927 if (next->isRightOf(edge->fTop)) {
928 break;
929 }
930 prev = next;
931 }
senorblancoe6eaa322016-03-08 09:06:44 -0800932 list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
ethannicholase9709e82016-01-07 13:34:16 -0800933 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
934}
935
936void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
937 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
Stephen Whitee30cf802017-02-27 11:37:55 -0500938 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
ethannicholase9709e82016-01-07 13:34:16 -0800939 return;
940 }
941 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
942 Edge* prev = nullptr;
943 Edge* next;
944 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
945 if (next->isRightOf(edge->fBottom)) {
946 break;
947 }
948 prev = next;
949 }
senorblancoe6eaa322016-03-08 09:06:44 -0800950 list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
ethannicholase9709e82016-01-07 13:34:16 -0800951 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
952}
953
954void remove_edge_above(Edge* edge) {
Stephen White7b376942018-05-22 11:51:32 -0400955 SkASSERT(edge->fTop && edge->fBottom);
ethannicholase9709e82016-01-07 13:34:16 -0800956 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
957 edge->fBottom->fID);
senorblancoe6eaa322016-03-08 09:06:44 -0800958 list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
ethannicholase9709e82016-01-07 13:34:16 -0800959 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
960}
961
962void remove_edge_below(Edge* edge) {
Stephen White7b376942018-05-22 11:51:32 -0400963 SkASSERT(edge->fTop && edge->fBottom);
ethannicholase9709e82016-01-07 13:34:16 -0800964 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
965 edge->fTop->fID);
senorblancoe6eaa322016-03-08 09:06:44 -0800966 list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
ethannicholase9709e82016-01-07 13:34:16 -0800967 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
968}
969
Stephen Whitee7a364d2017-01-11 16:19:26 -0500970void disconnect(Edge* edge)
971{
ethannicholase9709e82016-01-07 13:34:16 -0800972 remove_edge_above(edge);
973 remove_edge_below(edge);
Stephen Whitee7a364d2017-01-11 16:19:26 -0500974}
975
Stephen White3b5a3fa2017-06-06 14:51:19 -0400976void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c);
977
978void rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, Comparator& c) {
979 if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) {
980 return;
981 }
982 Vertex* v = *current;
983 LOG("rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID);
984 while (v != dst) {
985 v = v->fPrev;
986 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
987 remove_edge(e, activeEdges);
988 }
989 Edge* leftEdge = v->fLeftEnclosingEdge;
990 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
991 insert_edge(e, leftEdge, activeEdges);
992 leftEdge = e;
993 }
994 }
995 *current = v;
996}
997
998void rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
999 if (!activeEdges || !current) {
1000 return;
1001 }
1002 Vertex* top = edge->fTop;
1003 Vertex* bottom = edge->fBottom;
1004 if (edge->fLeft) {
1005 Vertex* leftTop = edge->fLeft->fTop;
1006 Vertex* leftBottom = edge->fLeft->fBottom;
1007 if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) {
1008 rewind(activeEdges, current, leftTop, c);
1009 } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) {
1010 rewind(activeEdges, current, top, c);
1011 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
1012 !edge->fLeft->isLeftOf(bottom)) {
1013 rewind(activeEdges, current, leftTop, c);
1014 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
1015 rewind(activeEdges, current, top, c);
1016 }
1017 }
1018 if (edge->fRight) {
1019 Vertex* rightTop = edge->fRight->fTop;
1020 Vertex* rightBottom = edge->fRight->fBottom;
1021 if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) {
1022 rewind(activeEdges, current, rightTop, c);
1023 } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) {
1024 rewind(activeEdges, current, top, c);
1025 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
1026 !edge->fRight->isRightOf(bottom)) {
1027 rewind(activeEdges, current, rightTop, c);
1028 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
1029 !edge->isLeftOf(rightBottom)) {
1030 rewind(activeEdges, current, top, c);
1031 }
ethannicholase9709e82016-01-07 13:34:16 -08001032 }
1033}
1034
Stephen White3b5a3fa2017-06-06 14:51:19 -04001035void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
ethannicholase9709e82016-01-07 13:34:16 -08001036 remove_edge_below(edge);
1037 edge->fTop = v;
1038 edge->recompute();
1039 insert_edge_below(edge, v, c);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001040 rewind_if_necessary(edge, activeEdges, current, c);
1041 merge_collinear_edges(edge, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001042}
1043
Stephen White3b5a3fa2017-06-06 14:51:19 -04001044void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
ethannicholase9709e82016-01-07 13:34:16 -08001045 remove_edge_above(edge);
1046 edge->fBottom = v;
1047 edge->recompute();
1048 insert_edge_above(edge, v, c);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001049 rewind_if_necessary(edge, activeEdges, current, c);
1050 merge_collinear_edges(edge, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001051}
1052
Stephen White3b5a3fa2017-06-06 14:51:19 -04001053void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
1054 Comparator& c) {
ethannicholase9709e82016-01-07 13:34:16 -08001055 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
1056 LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
1057 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
1058 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001059 rewind(activeEdges, current, edge->fTop, c);
ethannicholase9709e82016-01-07 13:34:16 -08001060 other->fWinding += edge->fWinding;
Stephen White3b5a3fa2017-06-06 14:51:19 -04001061 disconnect(edge);
Stephen Whiteec79c392018-05-18 11:49:21 -04001062 edge->fTop = edge->fBottom = nullptr;
ethannicholase9709e82016-01-07 13:34:16 -08001063 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001064 rewind(activeEdges, current, edge->fTop, c);
ethannicholase9709e82016-01-07 13:34:16 -08001065 other->fWinding += edge->fWinding;
Stephen White3b5a3fa2017-06-06 14:51:19 -04001066 set_bottom(edge, other->fTop, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001067 } else {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001068 rewind(activeEdges, current, other->fTop, c);
ethannicholase9709e82016-01-07 13:34:16 -08001069 edge->fWinding += other->fWinding;
Stephen White3b5a3fa2017-06-06 14:51:19 -04001070 set_bottom(other, edge->fTop, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001071 }
1072}
1073
Stephen White3b5a3fa2017-06-06 14:51:19 -04001074void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
1075 Comparator& c) {
ethannicholase9709e82016-01-07 13:34:16 -08001076 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
1077 LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
1078 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
1079 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001080 rewind(activeEdges, current, edge->fTop, c);
ethannicholase9709e82016-01-07 13:34:16 -08001081 other->fWinding += edge->fWinding;
Stephen White3b5a3fa2017-06-06 14:51:19 -04001082 disconnect(edge);
Stephen Whiteec79c392018-05-18 11:49:21 -04001083 edge->fTop = edge->fBottom = nullptr;
ethannicholase9709e82016-01-07 13:34:16 -08001084 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001085 rewind(activeEdges, current, other->fTop, c);
ethannicholase9709e82016-01-07 13:34:16 -08001086 edge->fWinding += other->fWinding;
Stephen White3b5a3fa2017-06-06 14:51:19 -04001087 set_top(other, edge->fBottom, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001088 } else {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001089 rewind(activeEdges, current, edge->fTop, c);
ethannicholase9709e82016-01-07 13:34:16 -08001090 other->fWinding += edge->fWinding;
Stephen White3b5a3fa2017-06-06 14:51:19 -04001091 set_top(edge, other->fBottom, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001092 }
1093}
1094
Stephen Whited26b4d82018-07-26 10:02:27 -04001095bool top_collinear(Edge* left, Edge* right) {
1096 if (!left || !right) {
1097 return false;
1098 }
1099 return left->fTop->fPoint == right->fTop->fPoint ||
1100 !left->isLeftOf(right->fTop) || !right->isRightOf(left->fTop);
1101}
1102
1103bool bottom_collinear(Edge* left, Edge* right) {
1104 if (!left || !right) {
1105 return false;
1106 }
1107 return left->fBottom->fPoint == right->fBottom->fPoint ||
1108 !left->isLeftOf(right->fBottom) || !right->isRightOf(left->fBottom);
1109}
1110
Stephen White3b5a3fa2017-06-06 14:51:19 -04001111void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
Stephen White6eca90f2017-05-25 14:47:11 -04001112 for (;;) {
Stephen Whited26b4d82018-07-26 10:02:27 -04001113 if (top_collinear(edge->fPrevEdgeAbove, edge)) {
Stephen White24289e02018-06-29 17:02:21 -04001114 merge_edges_above(edge->fPrevEdgeAbove, edge, activeEdges, current, c);
Stephen Whited26b4d82018-07-26 10:02:27 -04001115 } else if (top_collinear(edge, edge->fNextEdgeAbove)) {
Stephen White24289e02018-06-29 17:02:21 -04001116 merge_edges_above(edge->fNextEdgeAbove, edge, activeEdges, current, c);
Stephen Whited26b4d82018-07-26 10:02:27 -04001117 } else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) {
Stephen White24289e02018-06-29 17:02:21 -04001118 merge_edges_below(edge->fPrevEdgeBelow, edge, activeEdges, current, c);
Stephen Whited26b4d82018-07-26 10:02:27 -04001119 } else if (bottom_collinear(edge, edge->fNextEdgeBelow)) {
Stephen White24289e02018-06-29 17:02:21 -04001120 merge_edges_below(edge->fNextEdgeBelow, edge, activeEdges, current, c);
Stephen White6eca90f2017-05-25 14:47:11 -04001121 } else {
1122 break;
1123 }
ethannicholase9709e82016-01-07 13:34:16 -08001124 }
Stephen Whited26b4d82018-07-26 10:02:27 -04001125 SkASSERT(!top_collinear(edge->fPrevEdgeAbove, edge));
1126 SkASSERT(!top_collinear(edge, edge->fNextEdgeAbove));
1127 SkASSERT(!bottom_collinear(edge->fPrevEdgeBelow, edge));
1128 SkASSERT(!bottom_collinear(edge, edge->fNextEdgeBelow));
ethannicholase9709e82016-01-07 13:34:16 -08001129}
1130
Stephen White89042d52018-06-08 12:18:22 -04001131bool split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c,
Stephen White3b5a3fa2017-06-06 14:51:19 -04001132 SkArenaAlloc& alloc) {
Stephen Whiteec79c392018-05-18 11:49:21 -04001133 if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom) {
Stephen White89042d52018-06-08 12:18:22 -04001134 return false;
Stephen White0cb31672017-06-08 14:41:01 -04001135 }
ethannicholase9709e82016-01-07 13:34:16 -08001136 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
1137 edge->fTop->fID, edge->fBottom->fID,
1138 v->fID, v->fPoint.fX, v->fPoint.fY);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001139 Vertex* top;
1140 Vertex* bottom;
Stephen White531a48e2018-06-01 09:49:39 -04001141 int winding = edge->fWinding;
ethannicholase9709e82016-01-07 13:34:16 -08001142 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001143 top = v;
1144 bottom = edge->fTop;
1145 set_top(edge, v, activeEdges, current, c);
Stephen Whitee30cf802017-02-27 11:37:55 -05001146 } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001147 top = edge->fBottom;
1148 bottom = v;
1149 set_bottom(edge, v, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001150 } else {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001151 top = v;
1152 bottom = edge->fBottom;
1153 set_bottom(edge, v, activeEdges, current, c);
ethannicholase9709e82016-01-07 13:34:16 -08001154 }
Stephen White531a48e2018-06-01 09:49:39 -04001155 Edge* newEdge = alloc.make<Edge>(top, bottom, winding, edge->fType);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001156 insert_edge_below(newEdge, top, c);
1157 insert_edge_above(newEdge, bottom, c);
1158 merge_collinear_edges(newEdge, activeEdges, current, c);
Stephen White89042d52018-06-08 12:18:22 -04001159 return true;
1160}
1161
1162bool intersect_edge_pair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current, Comparator& c, SkArenaAlloc& alloc) {
1163 if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) {
1164 return false;
1165 }
Stephen White1c5fd182018-07-12 15:54:05 -04001166 if (left->fTop == right->fTop || left->fBottom == right->fBottom) {
1167 return false;
1168 }
Stephen White89042d52018-06-08 12:18:22 -04001169 if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) {
1170 if (!left->isLeftOf(right->fTop)) {
Stephen White1c5fd182018-07-12 15:54:05 -04001171 rewind(activeEdges, current, right->fTop, c);
Stephen White89042d52018-06-08 12:18:22 -04001172 return split_edge(left, right->fTop, activeEdges, current, c, alloc);
1173 }
1174 } else {
1175 if (!right->isRightOf(left->fTop)) {
Stephen White1c5fd182018-07-12 15:54:05 -04001176 rewind(activeEdges, current, left->fTop, c);
Stephen White89042d52018-06-08 12:18:22 -04001177 return split_edge(right, left->fTop, activeEdges, current, c, alloc);
1178 }
1179 }
1180 if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) {
1181 if (!left->isLeftOf(right->fBottom)) {
Stephen White1c5fd182018-07-12 15:54:05 -04001182 rewind(activeEdges, current, right->fBottom, c);
Stephen White89042d52018-06-08 12:18:22 -04001183 return split_edge(left, right->fBottom, activeEdges, current, c, alloc);
1184 }
1185 } else {
1186 if (!right->isRightOf(left->fBottom)) {
Stephen White1c5fd182018-07-12 15:54:05 -04001187 rewind(activeEdges, current, left->fBottom, c);
Stephen White89042d52018-06-08 12:18:22 -04001188 return split_edge(right, left->fBottom, activeEdges, current, c, alloc);
1189 }
1190 }
1191 return false;
ethannicholase9709e82016-01-07 13:34:16 -08001192}
1193
Herb Derby5cdc9dd2017-02-13 12:10:46 -05001194Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc,
Stephen White48ded382017-02-03 10:15:16 -05001195 int winding_scale = 1) {
Stephen Whitee260c462017-12-19 18:09:54 -05001196 if (!prev || !next || prev->fPoint == next->fPoint) {
1197 return nullptr;
1198 }
Stephen Whitebf6137e2017-01-04 15:43:26 -05001199 Edge* edge = new_edge(prev, next, type, c, alloc);
Stephen White8a0bfc52017-02-21 15:24:13 -05001200 insert_edge_below(edge, edge->fTop, c);
1201 insert_edge_above(edge, edge->fBottom, c);
Stephen White48ded382017-02-03 10:15:16 -05001202 edge->fWinding *= winding_scale;
Stephen White3b5a3fa2017-06-06 14:51:19 -04001203 merge_collinear_edges(edge, nullptr, nullptr, c);
senorblancof57372d2016-08-31 10:36:19 -07001204 return edge;
1205}
1206
Stephen Whitebf6137e2017-01-04 15:43:26 -05001207void merge_vertices(Vertex* src, Vertex* dst, VertexList* mesh, Comparator& c,
Herb Derby5cdc9dd2017-02-13 12:10:46 -05001208 SkArenaAlloc& alloc) {
ethannicholase9709e82016-01-07 13:34:16 -08001209 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX, src->fPoint.fY,
1210 src->fID, dst->fID);
senorblancof57372d2016-08-31 10:36:19 -07001211 dst->fAlpha = SkTMax(src->fAlpha, dst->fAlpha);
Stephen Whitebda29c02017-03-13 15:10:13 -04001212 if (src->fPartner) {
1213 src->fPartner->fPartner = dst;
1214 }
Stephen White7b376942018-05-22 11:51:32 -04001215 while (Edge* edge = src->fFirstEdgeAbove) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001216 set_bottom(edge, dst, nullptr, nullptr, c);
ethannicholase9709e82016-01-07 13:34:16 -08001217 }
Stephen White7b376942018-05-22 11:51:32 -04001218 while (Edge* edge = src->fFirstEdgeBelow) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001219 set_top(edge, dst, nullptr, nullptr, c);
ethannicholase9709e82016-01-07 13:34:16 -08001220 }
Stephen Whitebf6137e2017-01-04 15:43:26 -05001221 mesh->remove(src);
Stephen Whitec4dbc372019-05-22 10:50:14 -04001222 dst->fSynthetic = true;
ethannicholase9709e82016-01-07 13:34:16 -08001223}
1224
Stephen White95152e12017-12-18 10:52:44 -05001225Vertex* create_sorted_vertex(const SkPoint& p, uint8_t alpha, VertexList* mesh,
1226 Vertex* reference, Comparator& c, SkArenaAlloc& alloc) {
1227 Vertex* prevV = reference;
1228 while (prevV && c.sweep_lt(p, prevV->fPoint)) {
1229 prevV = prevV->fPrev;
1230 }
1231 Vertex* nextV = prevV ? prevV->fNext : mesh->fHead;
1232 while (nextV && c.sweep_lt(nextV->fPoint, p)) {
1233 prevV = nextV;
1234 nextV = nextV->fNext;
1235 }
1236 Vertex* v;
1237 if (prevV && coincident(prevV->fPoint, p)) {
1238 v = prevV;
1239 } else if (nextV && coincident(nextV->fPoint, p)) {
1240 v = nextV;
1241 } else {
1242 v = alloc.make<Vertex>(p, alpha);
1243#if LOGGING_ENABLED
1244 if (!prevV) {
1245 v->fID = mesh->fHead->fID - 1.0f;
1246 } else if (!nextV) {
1247 v->fID = mesh->fTail->fID + 1.0f;
1248 } else {
1249 v->fID = (prevV->fID + nextV->fID) * 0.5f;
1250 }
1251#endif
1252 mesh->insert(v, prevV, nextV);
1253 }
1254 return v;
1255}
1256
Stephen White53a02982018-05-30 22:47:46 -04001257// If an edge's top and bottom points differ only by 1/2 machine epsilon in the primary
1258// sort criterion, it may not be possible to split correctly, since there is no point which is
1259// below the top and above the bottom. This function detects that case.
1260bool nearly_flat(Comparator& c, Edge* edge) {
1261 SkPoint diff = edge->fBottom->fPoint - edge->fTop->fPoint;
1262 float primaryDiff = c.fDirection == Comparator::Direction::kHorizontal ? diff.fX : diff.fY;
Stephen White13f3d8d2018-06-22 10:19:20 -04001263 return fabs(primaryDiff) < std::numeric_limits<float>::epsilon() && primaryDiff != 0.0f;
Stephen White53a02982018-05-30 22:47:46 -04001264}
1265
Stephen Whitee62999f2018-06-05 18:45:07 -04001266SkPoint clamp(SkPoint p, SkPoint min, SkPoint max, Comparator& c) {
1267 if (c.sweep_lt(p, min)) {
1268 return min;
1269 } else if (c.sweep_lt(max, p)) {
1270 return max;
1271 } else {
1272 return p;
1273 }
1274}
1275
Stephen Whitec4dbc372019-05-22 10:50:14 -04001276void compute_bisector(Edge* edge1, Edge* edge2, Vertex* v, SkArenaAlloc& alloc) {
1277 Line line1 = edge1->fLine;
1278 Line line2 = edge2->fLine;
1279 line1.normalize();
1280 line2.normalize();
1281 double cosAngle = line1.fA * line2.fA + line1.fB * line2.fB;
1282 if (cosAngle > 0.999) {
1283 return;
1284 }
1285 line1.fC += edge1->fWinding > 0 ? -1 : 1;
1286 line2.fC += edge2->fWinding > 0 ? -1 : 1;
1287 SkPoint p;
1288 if (line1.intersect(line2, &p)) {
1289 uint8_t alpha = edge1->fType == Edge::Type::kOuter ? 255 : 0;
1290 v->fPartner = alloc.make<Vertex>(p, alpha);
1291 LOG("computed bisector (%g,%g) alpha %d for vertex %g\n", p.fX, p.fY, alpha, v->fID);
1292 }
1293}
1294
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001295bool check_for_intersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Stephen White0cb31672017-06-08 14:41:01 -04001296 VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001297 if (!left || !right) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001298 return false;
ethannicholase9709e82016-01-07 13:34:16 -08001299 }
Stephen White56158ae2017-01-30 14:31:31 -05001300 SkPoint p;
1301 uint8_t alpha;
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001302 if (left->intersect(*right, &p, &alpha) && p.isFinite()) {
Ravi Mistrybfe95982018-05-29 18:19:07 +00001303 Vertex* v;
ethannicholase9709e82016-01-07 13:34:16 -08001304 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001305 Vertex* top = *current;
1306 // If the intersection point is above the current vertex, rewind to the vertex above the
1307 // intersection.
Stephen White0cb31672017-06-08 14:41:01 -04001308 while (top && c.sweep_lt(p, top->fPoint)) {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001309 top = top->fPrev;
1310 }
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001311 if (!nearly_flat(c, left)) {
1312 p = clamp(p, left->fTop->fPoint, left->fBottom->fPoint, c);
Stephen Whitee62999f2018-06-05 18:45:07 -04001313 }
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001314 if (!nearly_flat(c, right)) {
1315 p = clamp(p, right->fTop->fPoint, right->fBottom->fPoint, c);
Stephen Whitee62999f2018-06-05 18:45:07 -04001316 }
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001317 if (p == left->fTop->fPoint) {
1318 v = left->fTop;
1319 } else if (p == left->fBottom->fPoint) {
1320 v = left->fBottom;
1321 } else if (p == right->fTop->fPoint) {
1322 v = right->fTop;
1323 } else if (p == right->fBottom->fPoint) {
1324 v = right->fBottom;
Ravi Mistrybfe95982018-05-29 18:19:07 +00001325 } else {
Stephen White95152e12017-12-18 10:52:44 -05001326 v = create_sorted_vertex(p, alpha, mesh, top, c, alloc);
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001327 if (left->fTop->fPartner) {
Stephen Whitec4dbc372019-05-22 10:50:14 -04001328 v->fSynthetic = true;
1329 compute_bisector(left, right, v, alloc);
Stephen Whitee260c462017-12-19 18:09:54 -05001330 }
ethannicholase9709e82016-01-07 13:34:16 -08001331 }
Stephen White0cb31672017-06-08 14:41:01 -04001332 rewind(activeEdges, current, top ? top : v, c);
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001333 split_edge(left, v, activeEdges, current, c, alloc);
1334 split_edge(right, v, activeEdges, current, c, alloc);
Stephen White92eba8a2017-02-06 09:50:27 -05001335 v->fAlpha = SkTMax(v->fAlpha, alpha);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001336 return true;
ethannicholase9709e82016-01-07 13:34:16 -08001337 }
Stephen Whiteb141fcb2018-06-14 10:15:47 -04001338 return intersect_edge_pair(left, right, activeEdges, current, c, alloc);
ethannicholase9709e82016-01-07 13:34:16 -08001339}
1340
Stephen White3a9aab92017-03-07 14:07:18 -05001341void sanitize_contours(VertexList* contours, int contourCnt, bool approximate) {
1342 for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
1343 SkASSERT(contour->fHead);
1344 Vertex* prev = contour->fTail;
Stephen White5926f2d2017-02-13 13:55:42 -05001345 if (approximate) {
Stephen White3a9aab92017-03-07 14:07:18 -05001346 round(&prev->fPoint);
Stephen White5926f2d2017-02-13 13:55:42 -05001347 }
Stephen White3a9aab92017-03-07 14:07:18 -05001348 for (Vertex* v = contour->fHead; v;) {
senorblancof57372d2016-08-31 10:36:19 -07001349 if (approximate) {
1350 round(&v->fPoint);
1351 }
Stephen White3a9aab92017-03-07 14:07:18 -05001352 Vertex* next = v->fNext;
Stephen White3de40f82018-06-28 09:36:49 -04001353 Vertex* nextWrap = next ? next : contour->fHead;
Stephen White3a9aab92017-03-07 14:07:18 -05001354 if (coincident(prev->fPoint, v->fPoint)) {
ethannicholase9709e82016-01-07 13:34:16 -08001355 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY);
Stephen White3a9aab92017-03-07 14:07:18 -05001356 contour->remove(v);
Stephen White73e7f802017-08-23 13:56:07 -04001357 } else if (!v->fPoint.isFinite()) {
1358 LOG("vertex %g,%g non-finite; removing\n", v->fPoint.fX, v->fPoint.fY);
1359 contour->remove(v);
Stephen White3de40f82018-06-28 09:36:49 -04001360 } else if (Line(prev->fPoint, nextWrap->fPoint).dist(v->fPoint) == 0.0) {
Stephen White06768ca2018-05-25 14:50:56 -04001361 LOG("vertex %g,%g collinear; removing\n", v->fPoint.fX, v->fPoint.fY);
1362 contour->remove(v);
1363 } else {
1364 prev = v;
ethannicholase9709e82016-01-07 13:34:16 -08001365 }
Stephen White3a9aab92017-03-07 14:07:18 -05001366 v = next;
ethannicholase9709e82016-01-07 13:34:16 -08001367 }
1368 }
1369}
1370
Stephen Whitee260c462017-12-19 18:09:54 -05001371bool merge_coincident_vertices(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
Stephen Whitebda29c02017-03-13 15:10:13 -04001372 if (!mesh->fHead) {
Stephen Whitee260c462017-12-19 18:09:54 -05001373 return false;
Stephen Whitebda29c02017-03-13 15:10:13 -04001374 }
Stephen Whitee260c462017-12-19 18:09:54 -05001375 bool merged = false;
1376 for (Vertex* v = mesh->fHead->fNext; v;) {
1377 Vertex* next = v->fNext;
ethannicholase9709e82016-01-07 13:34:16 -08001378 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) {
1379 v->fPoint = v->fPrev->fPoint;
1380 }
1381 if (coincident(v->fPrev->fPoint, v->fPoint)) {
Stephen Whitee260c462017-12-19 18:09:54 -05001382 merge_vertices(v, v->fPrev, mesh, c, alloc);
1383 merged = true;
ethannicholase9709e82016-01-07 13:34:16 -08001384 }
Stephen Whitee260c462017-12-19 18:09:54 -05001385 v = next;
ethannicholase9709e82016-01-07 13:34:16 -08001386 }
Stephen Whitee260c462017-12-19 18:09:54 -05001387 return merged;
ethannicholase9709e82016-01-07 13:34:16 -08001388}
1389
1390// Stage 2: convert the contours to a mesh of edges connecting the vertices.
1391
Stephen White3a9aab92017-03-07 14:07:18 -05001392void build_edges(VertexList* contours, int contourCnt, VertexList* mesh, Comparator& c,
Herb Derby5cdc9dd2017-02-13 12:10:46 -05001393 SkArenaAlloc& alloc) {
Stephen White3a9aab92017-03-07 14:07:18 -05001394 for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
1395 Vertex* prev = contour->fTail;
1396 for (Vertex* v = contour->fHead; v;) {
1397 Vertex* next = v->fNext;
1398 connect(prev, v, Edge::Type::kInner, c, alloc);
1399 mesh->append(v);
ethannicholase9709e82016-01-07 13:34:16 -08001400 prev = v;
Stephen White3a9aab92017-03-07 14:07:18 -05001401 v = next;
ethannicholase9709e82016-01-07 13:34:16 -08001402 }
1403 }
ethannicholase9709e82016-01-07 13:34:16 -08001404}
1405
Stephen Whitee260c462017-12-19 18:09:54 -05001406void connect_partners(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
1407 for (Vertex* outer = mesh->fHead; outer; outer = outer->fNext) {
Stephen Whitebda29c02017-03-13 15:10:13 -04001408 if (Vertex* inner = outer->fPartner) {
Stephen Whitee260c462017-12-19 18:09:54 -05001409 if ((inner->fPrev || inner->fNext) && (outer->fPrev || outer->fNext)) {
1410 // Connector edges get zero winding, since they're only structural (i.e., to ensure
1411 // no 0-0-0 alpha triangles are produced), and shouldn't affect the poly winding
1412 // number.
1413 connect(outer, inner, Edge::Type::kConnector, c, alloc, 0);
1414 inner->fPartner = outer->fPartner = nullptr;
1415 }
Stephen Whitebda29c02017-03-13 15:10:13 -04001416 }
1417 }
1418}
1419
1420template <CompareFunc sweep_lt>
1421void sorted_merge(VertexList* front, VertexList* back, VertexList* result) {
1422 Vertex* a = front->fHead;
1423 Vertex* b = back->fHead;
1424 while (a && b) {
1425 if (sweep_lt(a->fPoint, b->fPoint)) {
1426 front->remove(a);
1427 result->append(a);
1428 a = front->fHead;
1429 } else {
1430 back->remove(b);
1431 result->append(b);
1432 b = back->fHead;
1433 }
1434 }
1435 result->append(*front);
1436 result->append(*back);
1437}
1438
1439void sorted_merge(VertexList* front, VertexList* back, VertexList* result, Comparator& c) {
1440 if (c.fDirection == Comparator::Direction::kHorizontal) {
1441 sorted_merge<sweep_lt_horiz>(front, back, result);
1442 } else {
1443 sorted_merge<sweep_lt_vert>(front, back, result);
1444 }
Stephen White3b5a3fa2017-06-06 14:51:19 -04001445#if LOGGING_ENABLED
1446 float id = 0.0f;
1447 for (Vertex* v = result->fHead; v; v = v->fNext) {
1448 v->fID = id++;
1449 }
1450#endif
Stephen Whitebda29c02017-03-13 15:10:13 -04001451}
1452
ethannicholase9709e82016-01-07 13:34:16 -08001453// Stage 3: sort the vertices by increasing sweep direction.
1454
Stephen White16a40cb2017-02-23 11:10:01 -05001455template <CompareFunc sweep_lt>
1456void merge_sort(VertexList* vertices) {
1457 Vertex* slow = vertices->fHead;
1458 if (!slow) {
ethannicholase9709e82016-01-07 13:34:16 -08001459 return;
1460 }
Stephen White16a40cb2017-02-23 11:10:01 -05001461 Vertex* fast = slow->fNext;
1462 if (!fast) {
1463 return;
1464 }
1465 do {
1466 fast = fast->fNext;
1467 if (fast) {
1468 fast = fast->fNext;
1469 slow = slow->fNext;
1470 }
1471 } while (fast);
1472 VertexList front(vertices->fHead, slow);
1473 VertexList back(slow->fNext, vertices->fTail);
1474 front.fTail->fNext = back.fHead->fPrev = nullptr;
ethannicholase9709e82016-01-07 13:34:16 -08001475
Stephen White16a40cb2017-02-23 11:10:01 -05001476 merge_sort<sweep_lt>(&front);
1477 merge_sort<sweep_lt>(&back);
ethannicholase9709e82016-01-07 13:34:16 -08001478
Stephen White16a40cb2017-02-23 11:10:01 -05001479 vertices->fHead = vertices->fTail = nullptr;
Stephen Whitebda29c02017-03-13 15:10:13 -04001480 sorted_merge<sweep_lt>(&front, &back, vertices);
ethannicholase9709e82016-01-07 13:34:16 -08001481}
1482
Stephen White95152e12017-12-18 10:52:44 -05001483void dump_mesh(const VertexList& mesh) {
1484#if LOGGING_ENABLED
1485 for (Vertex* v = mesh.fHead; v; v = v->fNext) {
1486 LOG("vertex %g (%g, %g) alpha %d", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
1487 if (Vertex* p = v->fPartner) {
1488 LOG(", partner %g (%g, %g) alpha %d\n", p->fID, p->fPoint.fX, p->fPoint.fY, p->fAlpha);
1489 } else {
1490 LOG(", null partner\n");
1491 }
1492 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1493 LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
1494 }
1495 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1496 LOG(" edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
1497 }
1498 }
1499#endif
1500}
1501
Stephen Whitec4dbc372019-05-22 10:50:14 -04001502void dump_skel(const SSEdgeList& ssEdges) {
1503#if LOGGING_ENABLED
1504 LOG("skeleton:\n");
1505 for (SSEdge* edge : ssEdges) {
1506 if (edge->fEdge) {
1507 LOG("skel edge %g -> %g (original %g -> %g)\n",
1508 edge->fPrev->fVertex->fID,
1509 edge->fNext->fVertex->fID,
1510 edge->fEdge->fTop->fID,
1511 edge->fEdge->fBottom->fID);
1512 }
1513 }
1514#endif
1515}
1516
Stephen White89042d52018-06-08 12:18:22 -04001517#ifdef SK_DEBUG
1518void validate_edge_pair(Edge* left, Edge* right, Comparator& c) {
1519 if (!left || !right) {
1520 return;
1521 }
1522 if (left->fTop == right->fTop) {
1523 SkASSERT(left->isLeftOf(right->fBottom));
1524 SkASSERT(right->isRightOf(left->fBottom));
1525 } else if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) {
1526 SkASSERT(left->isLeftOf(right->fTop));
1527 } else {
1528 SkASSERT(right->isRightOf(left->fTop));
1529 }
1530 if (left->fBottom == right->fBottom) {
1531 SkASSERT(left->isLeftOf(right->fTop));
1532 SkASSERT(right->isRightOf(left->fTop));
1533 } else if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) {
1534 SkASSERT(left->isLeftOf(right->fBottom));
1535 } else {
1536 SkASSERT(right->isRightOf(left->fBottom));
1537 }
1538}
1539
1540void validate_edge_list(EdgeList* edges, Comparator& c) {
1541 Edge* left = edges->fHead;
1542 if (!left) {
1543 return;
1544 }
1545 for (Edge* right = left->fRight; right; right = right->fRight) {
1546 validate_edge_pair(left, right, c);
1547 left = right;
1548 }
1549}
1550#endif
1551
ethannicholase9709e82016-01-07 13:34:16 -08001552// Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
1553
Stephen Whitec4dbc372019-05-22 10:50:14 -04001554bool connected(Vertex* v) {
1555 return v->fFirstEdgeAbove || v->fFirstEdgeBelow;
1556}
1557
Stephen Whitee260c462017-12-19 18:09:54 -05001558bool simplify(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
ethannicholase9709e82016-01-07 13:34:16 -08001559 LOG("simplifying complex polygons\n");
1560 EdgeList activeEdges;
Stephen Whitee260c462017-12-19 18:09:54 -05001561 bool found = false;
Stephen White0cb31672017-06-08 14:41:01 -04001562 for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) {
Stephen Whitec4dbc372019-05-22 10:50:14 -04001563 if (!connected(v)) {
ethannicholase9709e82016-01-07 13:34:16 -08001564 continue;
1565 }
Stephen White8a0bfc52017-02-21 15:24:13 -05001566 Edge* leftEnclosingEdge;
1567 Edge* rightEnclosingEdge;
ethannicholase9709e82016-01-07 13:34:16 -08001568 bool restartChecks;
1569 do {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001570 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
ethannicholase9709e82016-01-07 13:34:16 -08001571 restartChecks = false;
1572 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
Stephen White3b5a3fa2017-06-06 14:51:19 -04001573 v->fLeftEnclosingEdge = leftEnclosingEdge;
1574 v->fRightEnclosingEdge = rightEnclosingEdge;
ethannicholase9709e82016-01-07 13:34:16 -08001575 if (v->fFirstEdgeBelow) {
Stephen Whitebf6137e2017-01-04 15:43:26 -05001576 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
Stephen White89042d52018-06-08 12:18:22 -04001577 if (check_for_intersection(leftEnclosingEdge, edge, &activeEdges, &v, mesh, c,
Stephen White3b5a3fa2017-06-06 14:51:19 -04001578 alloc)) {
ethannicholase9709e82016-01-07 13:34:16 -08001579 restartChecks = true;
1580 break;
1581 }
Stephen White0cb31672017-06-08 14:41:01 -04001582 if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, &v, mesh, c,
Stephen White3b5a3fa2017-06-06 14:51:19 -04001583 alloc)) {
ethannicholase9709e82016-01-07 13:34:16 -08001584 restartChecks = true;
1585 break;
1586 }
1587 }
1588 } else {
Stephen White3b5a3fa2017-06-06 14:51:19 -04001589 if (check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
Stephen White0cb31672017-06-08 14:41:01 -04001590 &activeEdges, &v, mesh, c, alloc)) {
ethannicholase9709e82016-01-07 13:34:16 -08001591 restartChecks = true;
1592 }
1593
1594 }
Stephen Whitee260c462017-12-19 18:09:54 -05001595 found = found || restartChecks;
ethannicholase9709e82016-01-07 13:34:16 -08001596 } while (restartChecks);
Stephen White89042d52018-06-08 12:18:22 -04001597#ifdef SK_DEBUG
1598 validate_edge_list(&activeEdges, c);
1599#endif
ethannicholase9709e82016-01-07 13:34:16 -08001600 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1601 remove_edge(e, &activeEdges);
1602 }
1603 Edge* leftEdge = leftEnclosingEdge;
1604 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1605 insert_edge(e, leftEdge, &activeEdges);
1606 leftEdge = e;
1607 }
ethannicholase9709e82016-01-07 13:34:16 -08001608 }
Stephen Whitee260c462017-12-19 18:09:54 -05001609 SkASSERT(!activeEdges.fHead && !activeEdges.fTail);
1610 return found;
ethannicholase9709e82016-01-07 13:34:16 -08001611}
1612
1613// Stage 5: Tessellate the simplified mesh into monotone polygons.
1614
Herb Derby5cdc9dd2017-02-13 12:10:46 -05001615Poly* tessellate(const VertexList& vertices, SkArenaAlloc& alloc) {
Stephen White95152e12017-12-18 10:52:44 -05001616 LOG("\ntessellating simple polygons\n");
ethannicholase9709e82016-01-07 13:34:16 -08001617 EdgeList activeEdges;
1618 Poly* polys = nullptr;
Stephen Whitebf6137e2017-01-04 15:43:26 -05001619 for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) {
Stephen Whitec4dbc372019-05-22 10:50:14 -04001620 if (!connected(v)) {
ethannicholase9709e82016-01-07 13:34:16 -08001621 continue;
1622 }
1623#if LOGGING_ENABLED
senorblancof57372d2016-08-31 10:36:19 -07001624 LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
ethannicholase9709e82016-01-07 13:34:16 -08001625#endif
Stephen White8a0bfc52017-02-21 15:24:13 -05001626 Edge* leftEnclosingEdge;
1627 Edge* rightEnclosingEdge;
ethannicholase9709e82016-01-07 13:34:16 -08001628 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
Stephen White8a0bfc52017-02-21 15:24:13 -05001629 Poly* leftPoly;
1630 Poly* rightPoly;
ethannicholase9709e82016-01-07 13:34:16 -08001631 if (v->fFirstEdgeAbove) {
1632 leftPoly = v->fFirstEdgeAbove->fLeftPoly;
1633 rightPoly = v->fLastEdgeAbove->fRightPoly;
1634 } else {
1635 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullptr;
1636 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nullptr;
1637 }
1638#if LOGGING_ENABLED
1639 LOG("edges above:\n");
1640 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1641 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1642 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
1643 }
1644 LOG("edges below:\n");
1645 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1646 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1647 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
1648 }
1649#endif
1650 if (v->fFirstEdgeAbove) {
1651 if (leftPoly) {
senorblanco531237e2016-06-02 11:36:48 -07001652 leftPoly = leftPoly->addEdge(v->fFirstEdgeAbove, Poly::kRight_Side, alloc);
ethannicholase9709e82016-01-07 13:34:16 -08001653 }
1654 if (rightPoly) {
senorblanco531237e2016-06-02 11:36:48 -07001655 rightPoly = rightPoly->addEdge(v->fLastEdgeAbove, Poly::kLeft_Side, alloc);
ethannicholase9709e82016-01-07 13:34:16 -08001656 }
1657 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
ethannicholase9709e82016-01-07 13:34:16 -08001658 Edge* rightEdge = e->fNextEdgeAbove;
Stephen White8a0bfc52017-02-21 15:24:13 -05001659 remove_edge(e, &activeEdges);
1660 if (e->fRightPoly) {
1661 e->fRightPoly->addEdge(e, Poly::kLeft_Side, alloc);
ethannicholase9709e82016-01-07 13:34:16 -08001662 }
Stephen White8a0bfc52017-02-21 15:24:13 -05001663 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != e->fRightPoly) {
senorblanco531237e2016-06-02 11:36:48 -07001664 rightEdge->fLeftPoly->addEdge(e, Poly::kRight_Side, alloc);
ethannicholase9709e82016-01-07 13:34:16 -08001665 }
1666 }
1667 remove_edge(v->fLastEdgeAbove, &activeEdges);
1668 if (!v->fFirstEdgeBelow) {
1669 if (leftPoly && rightPoly && leftPoly != rightPoly) {
1670 SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartner == nullptr);
1671 rightPoly->fPartner = leftPoly;
1672 leftPoly->fPartner = rightPoly;
1673 }
1674 }
1675 }
1676 if (v->fFirstEdgeBelow) {
1677 if (!v->fFirstEdgeAbove) {
senorblanco93e3fff2016-06-07 12:36:00 -07001678 if (leftPoly && rightPoly) {
senorblanco531237e2016-06-02 11:36:48 -07001679 if (leftPoly == rightPoly) {
1680 if (leftPoly->fTail && leftPoly->fTail->fSide == Poly::kLeft_Side) {
1681 leftPoly = new_poly(&polys, leftPoly->lastVertex(),
1682 leftPoly->fWinding, alloc);
1683 leftEnclosingEdge->fRightPoly = leftPoly;
1684 } else {
1685 rightPoly = new_poly(&polys, rightPoly->lastVertex(),
1686 rightPoly->fWinding, alloc);
1687 rightEnclosingEdge->fLeftPoly = rightPoly;
1688 }
ethannicholase9709e82016-01-07 13:34:16 -08001689 }
Herb Derby5cdc9dd2017-02-13 12:10:46 -05001690 Edge* join = alloc.make<Edge>(leftPoly->lastVertex(), v, 1, Edge::Type::kInner);
senorblanco531237e2016-06-02 11:36:48 -07001691 leftPoly = leftPoly->addEdge(join, Poly::kRight_Side, alloc);
1692 rightPoly = rightPoly->addEdge(join, Poly::kLeft_Side, alloc);
ethannicholase9709e82016-01-07 13:34:16 -08001693 }
1694 }
1695 Edge* leftEdge = v->fFirstEdgeBelow;
1696 leftEdge->fLeftPoly = leftPoly;
1697 insert_edge(leftEdge, leftEnclosingEdge, &activeEdges);
1698 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
1699 rightEdge = rightEdge->fNextEdgeBelow) {
1700 insert_edge(rightEdge, leftEdge, &activeEdges);
1701 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWinding : 0;
1702 winding += leftEdge->fWinding;
1703 if (winding != 0) {
1704 Poly* poly = new_poly(&polys, v, winding, alloc);
1705 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
1706 }
1707 leftEdge = rightEdge;
1708 }
1709 v->fLastEdgeBelow->fRightPoly = rightPoly;
1710 }
1711#if LOGGING_ENABLED
1712 LOG("\nactive edges:\n");
1713 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
1714 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID,
1715 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRightPoly->fID : -1);
1716 }
1717#endif
1718 }
1719 return polys;
1720}
1721
Stephen Whitebf6137e2017-01-04 15:43:26 -05001722void remove_non_boundary_edges(const VertexList& mesh, SkPath::FillType fillType,
Herb Derby5cdc9dd2017-02-13 12:10:46 -05001723 SkArenaAlloc& alloc) {
Stephen White49789062017-02-21 10:35:49 -05001724 LOG("removing non-boundary edges\n");
1725 EdgeList activeEdges;
Stephen Whitebf6137e2017-01-04 15:43:26 -05001726 for (Vertex* v = mesh.fHead; v != nullptr; v = v->fNext) {
Stephen Whitec4dbc372019-05-22 10:50:14 -04001727 if (!connected(v)) {
Stephen White49789062017-02-21 10:35:49 -05001728 continue;
1729 }
1730 Edge* leftEnclosingEdge;
1731 Edge* rightEnclosingEdge;
1732 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
1733 bool prevFilled = leftEnclosingEdge &&
1734 apply_fill_type(fillType, leftEnclosingEdge->fWinding);
1735 for (Edge* e = v->fFirstEdgeAbove; e;) {
1736 Edge* next = e->fNextEdgeAbove;
1737 remove_edge(e, &activeEdges);
1738 bool filled = apply_fill_type(fillType, e->fWinding);
1739 if (filled == prevFilled) {
Stephen Whitee7a364d2017-01-11 16:19:26 -05001740 disconnect(e);
senorblancof57372d2016-08-31 10:36:19 -07001741 }
Stephen White49789062017-02-21 10:35:49 -05001742 prevFilled = filled;
senorblancof57372d2016-08-31 10:36:19 -07001743 e = next;
1744 }
Stephen White49789062017-02-21 10:35:49 -05001745 Edge* prev = leftEnclosingEdge;
1746 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1747 if (prev) {
1748 e->fWinding += prev->fWinding;
1749 }
1750 insert_edge(e, prev, &activeEdges);
1751 prev = e;
1752 }
senorblancof57372d2016-08-31 10:36:19 -07001753 }
senorblancof57372d2016-08-31 10:36:19 -07001754}
1755
Stephen White66412122017-03-01 11:48:27 -05001756// Note: this is the normal to the edge, but not necessarily unit length.
senorblancof57372d2016-08-31 10:36:19 -07001757void get_edge_normal(const Edge* e, SkVector* normal) {
Stephen Whitee260c462017-12-19 18:09:54 -05001758 normal->set(SkDoubleToScalar(e->fLine.fA),
1759 SkDoubleToScalar(e->fLine.fB));
senorblancof57372d2016-08-31 10:36:19 -07001760}
1761
1762// Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions
1763// and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to
1764// invert on stroking.
1765
Herb Derby5cdc9dd2017-02-13 12:10:46 -05001766void simplify_boundary(EdgeList* boundary, Comparator& c, SkArenaAlloc& alloc) {
senorblancof57372d2016-08-31 10:36:19 -07001767 Edge* prevEdge = boundary->fTail;
1768 SkVector prevNormal;
1769 get_edge_normal(prevEdge, &prevNormal);
1770 for (Edge* e = boundary->fHead; e != nullptr;) {
1771 Vertex* prev = prevEdge->fWinding == 1 ? prevEdge->fTop : prevEdge->fBottom;
1772 Vertex* next = e->fWinding == 1 ? e->fBottom : e->fTop;
Stephen Whitecfe12642018-09-26 17:25:59 -04001773 double distPrev = e->dist(prev->fPoint);
1774 double distNext = prevEdge->dist(next->fPoint);
senorblancof57372d2016-08-31 10:36:19 -07001775 SkVector normal;
1776 get_edge_normal(e, &normal);
Stephen Whitecfe12642018-09-26 17:25:59 -04001777 constexpr double kQuarterPixelSq = 0.25f * 0.25f;
Stephen Whitec4dbc372019-05-22 10:50:14 -04001778 if (prev == next) {
1779 remove_edge(prevEdge, boundary);
1780 remove_edge(e, boundary);
1781 prevEdge = boundary->fTail;
1782 e = boundary->fHead;
1783 if (prevEdge) {
1784 get_edge_normal(prevEdge, &prevNormal);
1785 }
1786 } else if (prevNormal.dot(normal) < 0.0 &&
Stephen Whitecfe12642018-09-26 17:25:59 -04001787 (distPrev * distPrev <= kQuarterPixelSq || distNext * distNext <= kQuarterPixelSq)) {
Stephen Whitebf6137e2017-01-04 15:43:26 -05001788 Edge* join = new_edge(prev, next, Edge::Type::kInner, c, alloc);
Stephen Whitee260c462017-12-19 18:09:54 -05001789 if (prev->fPoint != next->fPoint) {
1790 join->fLine.normalize();
1791 join->fLine = join->fLine * join->fWinding;
1792 }
senorblancof57372d2016-08-31 10:36:19 -07001793 insert_edge(join, e, boundary);
1794 remove_edge(prevEdge, boundary);
1795 remove_edge(e, boundary);
1796 if (join->fLeft && join->fRight) {
1797 prevEdge = join->fLeft;
1798 e = join;
1799 } else {
1800 prevEdge = boundary->fTail;
1801 e = boundary->fHead; // join->fLeft ? join->fLeft : join;
1802 }
1803 get_edge_normal(prevEdge, &prevNormal);
1804 } else {
1805 prevEdge = e;
1806 prevNormal = normal;
1807 e = e->fRight;
1808 }
1809 }
1810}
1811
Stephen Whitec4dbc372019-05-22 10:50:14 -04001812void ss_connect(Vertex* v, Vertex* dest, Comparator& c, SkArenaAlloc& alloc) {
1813 if (v == dest) {
1814 return;
Stephen Whitee260c462017-12-19 18:09:54 -05001815 }
Stephen Whitec4dbc372019-05-22 10:50:14 -04001816 LOG("ss_connecting vertex %g to vertex %g\n", v->fID, dest->fID);
1817 if (v->fSynthetic) {
1818 connect(v, dest, Edge::Type::kConnector, c, alloc, 0);
1819 } else if (v->fPartner) {
1820 LOG("setting %g's partner to %g ", v->fPartner->fID, dest->fID);
1821 LOG("and %g's partner to null\n", v->fID);
1822 v->fPartner->fPartner = dest;
1823 v->fPartner = nullptr;
Stephen Whitee260c462017-12-19 18:09:54 -05001824 }
1825}
1826
Stephen Whitec4dbc372019-05-22 10:50:14 -04001827void Event::apply(VertexList* mesh, Comparator& c, EventList* events, SkArenaAlloc& alloc) {
1828 if (!fEdge) {
Stephen Whitee260c462017-12-19 18:09:54 -05001829 return;
1830 }
Stephen Whitec4dbc372019-05-22 10:50:14 -04001831 Vertex* prev = fEdge->fPrev->fVertex;
1832 Vertex* next = fEdge->fNext->fVertex;
1833 SSEdge* prevEdge = fEdge->fPrev->fPrev;
1834 SSEdge* nextEdge = fEdge->fNext->fNext;
1835 if (!prevEdge || !nextEdge || !prevEdge->fEdge || !nextEdge->fEdge) {
1836 return;
Stephen White77169c82018-06-05 09:15:59 -04001837 }
Stephen Whitec4dbc372019-05-22 10:50:14 -04001838 Vertex* dest = create_sorted_vertex(fPoint, fAlpha, mesh, prev, c, alloc);
1839 dest->fSynthetic = true;
1840 SSVertex* ssv = alloc.make<SSVertex>(dest);
1841 LOG("collapsing %g, %g (original edge %g -> %g) to %g (%g, %g) alpha %d\n",
1842 prev->fID, next->fID, fEdge->fEdge->fTop->fID, fEdge->fEdge->fBottom->fID,
1843 dest->fID, fPoint.fX, fPoint.fY, fAlpha);
1844 fEdge->fEdge = nullptr;
Stephen Whitee260c462017-12-19 18:09:54 -05001845
Stephen Whitec4dbc372019-05-22 10:50:14 -04001846 ss_connect(prev, dest, c, alloc);
1847 ss_connect(next, dest, c, alloc);
Stephen Whitee260c462017-12-19 18:09:54 -05001848
Stephen Whitec4dbc372019-05-22 10:50:14 -04001849 prevEdge->fNext = nextEdge->fPrev = ssv;
1850 ssv->fPrev = prevEdge;
1851 ssv->fNext = nextEdge;
1852 if (!prevEdge->fEdge || !nextEdge->fEdge) {
1853 return;
1854 }
1855 if (prevEdge->fEvent) {
1856 prevEdge->fEvent->fEdge = nullptr;
1857 }
1858 if (nextEdge->fEvent) {
1859 nextEdge->fEvent->fEdge = nullptr;
1860 }
1861 if (prevEdge->fPrev == nextEdge->fNext) {
1862 ss_connect(prevEdge->fPrev->fVertex, dest, c, alloc);
1863 prevEdge->fEdge = nextEdge->fEdge = nullptr;
1864 } else {
1865 compute_bisector(prevEdge->fEdge, nextEdge->fEdge, dest, alloc);
1866 SkASSERT(prevEdge != fEdge && nextEdge != fEdge);
1867 if (dest->fPartner) {
1868 create_event(prevEdge, events, alloc);
1869 create_event(nextEdge, events, alloc);
1870 } else {
1871 create_event(prevEdge, prevEdge->fPrev->fVertex, nextEdge, dest, events, c, alloc);
1872 create_event(nextEdge, nextEdge->fNext->fVertex, prevEdge, dest, events, c, alloc);
1873 }
1874 }
Stephen Whitee260c462017-12-19 18:09:54 -05001875}
1876
1877bool is_overlap_edge(Edge* e) {
1878 if (e->fType == Edge::Type::kOuter) {
1879 return e->fWinding != 0 && e->fWinding != 1;
1880 } else if (e->fType == Edge::Type::kInner) {
1881 return e->fWinding != 0 && e->fWinding != -2;
1882 } else {
1883 return false;
1884 }
1885}
1886
1887// This is a stripped-down version of tessellate() which computes edges which
1888// join two filled regions, which represent overlap regions, and collapses them.
Stephen Whitec4dbc372019-05-22 10:50:14 -04001889bool collapse_overlap_regions(VertexList* mesh, Comparator& c, SkArenaAlloc& alloc,
1890 EventComparator comp) {
Stephen Whitee260c462017-12-19 18:09:54 -05001891 LOG("\nfinding overlap regions\n");
1892 EdgeList activeEdges;
Stephen Whitec4dbc372019-05-22 10:50:14 -04001893 EventList events(comp);
1894 SSVertexMap ssVertices;
1895 SSEdgeList ssEdges;
Stephen Whitee260c462017-12-19 18:09:54 -05001896 for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) {
Stephen Whitec4dbc372019-05-22 10:50:14 -04001897 if (!connected(v)) {
Stephen Whitee260c462017-12-19 18:09:54 -05001898 continue;
1899 }
1900 Edge* leftEnclosingEdge;
1901 Edge* rightEnclosingEdge;
1902 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
Stephen Whitec4dbc372019-05-22 10:50:14 -04001903 for (Edge* e = v->fLastEdgeAbove; e && e != leftEnclosingEdge;) {
Stephen Whitee260c462017-12-19 18:09:54 -05001904 Edge* prev = e->fPrevEdgeAbove ? e->fPrevEdgeAbove : leftEnclosingEdge;
1905 remove_edge(e, &activeEdges);
Stephen Whitec4dbc372019-05-22 10:50:14 -04001906 bool leftOverlap = prev && is_overlap_edge(prev);
1907 bool rightOverlap = is_overlap_edge(e);
1908 bool isOuterBoundary = e->fType == Edge::Type::kOuter &&
1909 (!prev || prev->fWinding == 0 || e->fWinding == 0);
Stephen Whitee260c462017-12-19 18:09:54 -05001910 if (prev) {
1911 e->fWinding -= prev->fWinding;
1912 }
Stephen Whitec4dbc372019-05-22 10:50:14 -04001913 if (leftOverlap && rightOverlap) {
1914 LOG("found interior overlap edge %g -> %g, disconnecting\n",
1915 e->fTop->fID, e->fBottom->fID);
1916 disconnect(e);
1917 } else if (leftOverlap || rightOverlap) {
1918 LOG("found overlap edge %g -> %g%s\n", e->fTop->fID, e->fBottom->fID,
1919 isOuterBoundary ? ", is outer boundary" : "");
1920 Vertex* prevVertex = e->fWinding < 0 ? e->fBottom : e->fTop;
1921 Vertex* nextVertex = e->fWinding < 0 ? e->fTop : e->fBottom;
1922 SSVertex* ssPrev = ssVertices[prevVertex];
1923 if (!ssPrev) {
1924 ssPrev = ssVertices[prevVertex] = alloc.make<SSVertex>(prevVertex);
1925 }
1926 SSVertex* ssNext = ssVertices[nextVertex];
1927 if (!ssNext) {
1928 ssNext = ssVertices[nextVertex] = alloc.make<SSVertex>(nextVertex);
1929 }
1930 SSEdge* ssEdge = alloc.make<SSEdge>(e, ssPrev, ssNext);
1931 ssEdges.push_back(ssEdge);
1932// SkASSERT(!ssPrev->fNext && !ssNext->fPrev);
1933 ssPrev->fNext = ssNext->fPrev = ssEdge;
1934 create_event(ssEdge, &events, alloc);
1935 if (!isOuterBoundary) {
1936 disconnect(e);
1937 }
1938 }
1939 e = prev;
Stephen Whitee260c462017-12-19 18:09:54 -05001940 }
1941 Edge* prev = leftEnclosingEdge;
1942 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1943 if (prev) {
1944 e->fWinding += prev->fWinding;
Stephen Whitee260c462017-12-19 18:09:54 -05001945 }
1946 insert_edge(e, prev, &activeEdges);
1947 prev = e;
1948 }
1949 }
Stephen Whitec4dbc372019-05-22 10:50:14 -04001950 bool complex = events.size() > 0;
1951
Stephen Whitee260c462017-12-19 18:09:54 -05001952 LOG("\ncollapsing overlap regions\n");
Stephen Whitec4dbc372019-05-22 10:50:14 -04001953 while (events.size() > 0) {
1954 Event* event = events.top();
Stephen Whitee260c462017-12-19 18:09:54 -05001955 events.pop();
Stephen Whitec4dbc372019-05-22 10:50:14 -04001956 event->apply(mesh, c, &events, alloc);
Stephen Whitee260c462017-12-19 18:09:54 -05001957 }
Stephen Whitec4dbc372019-05-22 10:50:14 -04001958 dump_skel(ssEdges);
1959 for (SSEdge* edge : ssEdges) {
1960 if (Edge* e = edge->fEdge) {
1961 connect(edge->fPrev->fVertex, edge->fNext->fVertex, e->fType, c, alloc, 0);
1962 }
1963 }
1964 return complex;
Stephen Whitee260c462017-12-19 18:09:54 -05001965}
1966
1967bool inversion(Vertex* prev, Vertex* next, Edge* origEdge, Comparator& c) {
1968 if (!prev || !next) {
1969 return true;
1970 }
1971 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
1972 return winding != origEdge->fWinding;
1973}
Stephen White92eba8a2017-02-06 09:50:27 -05001974
senorblancof57372d2016-08-31 10:36:19 -07001975// Stage 5d: Displace edges by half a pixel inward and outward along their normals. Intersect to
1976// find new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a
1977// new antialiased mesh from those vertices.
1978
Stephen Whitee260c462017-12-19 18:09:54 -05001979void stroke_boundary(EdgeList* boundary, VertexList* innerMesh, VertexList* outerMesh,
1980 Comparator& c, SkArenaAlloc& alloc) {
1981 LOG("\nstroking boundary\n");
1982 // A boundary with fewer than 3 edges is degenerate.
1983 if (!boundary->fHead || !boundary->fHead->fRight || !boundary->fHead->fRight->fRight) {
1984 return;
1985 }
1986 Edge* prevEdge = boundary->fTail;
1987 Vertex* prevV = prevEdge->fWinding > 0 ? prevEdge->fTop : prevEdge->fBottom;
1988 SkVector prevNormal;
1989 get_edge_normal(prevEdge, &prevNormal);
1990 double radius = 0.5;
1991 Line prevInner(prevEdge->fLine);
1992 prevInner.fC -= radius;
1993 Line prevOuter(prevEdge->fLine);
1994 prevOuter.fC += radius;
1995 VertexList innerVertices;
1996 VertexList outerVertices;
1997 bool innerInversion = true;
1998 bool outerInversion = true;
1999 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) {
2000 Vertex* v = e->fWinding > 0 ? e->fTop : e->fBottom;
2001 SkVector normal;
2002 get_edge_normal(e, &normal);
2003 Line inner(e->fLine);
2004 inner.fC -= radius;
2005 Line outer(e->fLine);
2006 outer.fC += radius;
2007 SkPoint innerPoint, outerPoint;
2008 LOG("stroking vertex %g (%g, %g)\n", v->fID, v->fPoint.fX, v->fPoint.fY);
2009 if (!prevEdge->fLine.nearParallel(e->fLine) && prevInner.intersect(inner, &innerPoint) &&
2010 prevOuter.intersect(outer, &outerPoint)) {
2011 float cosAngle = normal.dot(prevNormal);
2012 if (cosAngle < -kCosMiterAngle) {
2013 Vertex* nextV = e->fWinding > 0 ? e->fBottom : e->fTop;
2014
2015 // This is a pointy vertex whose angle is smaller than the threshold; miter it.
2016 Line bisector(innerPoint, outerPoint);
2017 Line tangent(v->fPoint, v->fPoint + SkPoint::Make(bisector.fA, bisector.fB));
2018 if (tangent.fA == 0 && tangent.fB == 0) {
2019 continue;
2020 }
2021 tangent.normalize();
2022 Line innerTangent(tangent);
2023 Line outerTangent(tangent);
2024 innerTangent.fC -= 0.5;
2025 outerTangent.fC += 0.5;
2026 SkPoint innerPoint1, innerPoint2, outerPoint1, outerPoint2;
2027 if (prevNormal.cross(normal) > 0) {
2028 // Miter inner points
2029 if (!innerTangent.intersect(prevInner, &innerPoint1) ||
2030 !innerTangent.intersect(inner, &innerPoint2) ||
2031 !outerTangent.intersect(bisector, &outerPoint)) {
Stephen Whitef470b7e2018-01-04 16:45:51 -05002032 continue;
Stephen Whitee260c462017-12-19 18:09:54 -05002033 }
2034 Line prevTangent(prevV->fPoint,
2035 prevV->fPoint + SkVector::Make(prevOuter.fA, prevOuter.fB));
2036 Line nextTangent(nextV->fPoint,
2037 nextV->fPoint + SkVector::Make(outer.fA, outer.fB));
Stephen Whitee260c462017-12-19 18:09:54 -05002038 if (prevTangent.dist(outerPoint) > 0) {
Stephen White4f34fca2018-01-11 16:14:04 -05002039 bisector.intersect(prevTangent, &outerPoint);
Stephen Whitee260c462017-12-19 18:09:54 -05002040 }
2041 if (nextTangent.dist(outerPoint) < 0) {
Stephen White4f34fca2018-01-11 16:14:04 -05002042 bisector.intersect(nextTangent, &outerPoint);
Stephen Whitee260c462017-12-19 18:09:54 -05002043 }
2044 outerPoint1 = outerPoint2 = outerPoint;
2045 } else {
2046 // Miter outer points
2047 if (!outerTangent.intersect(prevOuter, &outerPoint1) ||
2048 !outerTangent.intersect(outer, &outerPoint2)) {
Stephen Whitef470b7e2018-01-04 16:45:51 -05002049 continue;
Stephen Whitee260c462017-12-19 18:09:54 -05002050 }
2051 Line prevTangent(prevV->fPoint,
2052 prevV->fPoint + SkVector::Make(prevInner.fA, prevInner.fB));
2053 Line nextTangent(nextV->fPoint,
2054 nextV->fPoint + SkVector::Make(inner.fA, inner.fB));
Stephen Whitee260c462017-12-19 18:09:54 -05002055 if (prevTangent.dist(innerPoint) > 0) {
Stephen White4f34fca2018-01-11 16:14:04 -05002056 bisector.intersect(prevTangent, &innerPoint);
Stephen Whitee260c462017-12-19 18:09:54 -05002057 }
2058 if (nextTangent.dist(innerPoint) < 0) {
Stephen White4f34fca2018-01-11 16:14:04 -05002059 bisector.intersect(nextTangent, &innerPoint);
Stephen Whitee260c462017-12-19 18:09:54 -05002060 }
2061 innerPoint1 = innerPoint2 = innerPoint;
2062 }
Stephen Whiteea495232018-04-03 11:28:15 -04002063 if (!innerPoint1.isFinite() || !innerPoint2.isFinite() ||
2064 !outerPoint1.isFinite() || !outerPoint2.isFinite()) {
2065 continue;
2066 }
Stephen Whitee260c462017-12-19 18:09:54 -05002067 LOG("inner (%g, %g), (%g, %g), ",
2068 innerPoint1.fX, innerPoint1.fY, innerPoint2.fX, innerPoint2.fY);
2069 LOG("outer (%g, %g), (%g, %g)\n",
2070 outerPoint1.fX, outerPoint1.fY, outerPoint2.fX, outerPoint2.fY);
2071 Vertex* innerVertex1 = alloc.make<Vertex>(innerPoint1, 255);
2072 Vertex* innerVertex2 = alloc.make<Vertex>(innerPoint2, 255);
2073 Vertex* outerVertex1 = alloc.make<Vertex>(outerPoint1, 0);
2074 Vertex* outerVertex2 = alloc.make<Vertex>(outerPoint2, 0);
2075 innerVertex1->fPartner = outerVertex1;
2076 innerVertex2->fPartner = outerVertex2;
2077 outerVertex1->fPartner = innerVertex1;
2078 outerVertex2->fPartner = innerVertex2;
2079 if (!inversion(innerVertices.fTail, innerVertex1, prevEdge, c)) {
2080 innerInversion = false;
2081 }
2082 if (!inversion(outerVertices.fTail, outerVertex1, prevEdge, c)) {
2083 outerInversion = false;
2084 }
2085 innerVertices.append(innerVertex1);
2086 innerVertices.append(innerVertex2);
2087 outerVertices.append(outerVertex1);
2088 outerVertices.append(outerVertex2);
2089 } else {
2090 LOG("inner (%g, %g), ", innerPoint.fX, innerPoint.fY);
2091 LOG("outer (%g, %g)\n", outerPoint.fX, outerPoint.fY);
2092 Vertex* innerVertex = alloc.make<Vertex>(innerPoint, 255);
2093 Vertex* outerVertex = alloc.make<Vertex>(outerPoint, 0);
2094 innerVertex->fPartner = outerVertex;
2095 outerVertex->fPartner = innerVertex;
2096 if (!inversion(innerVertices.fTail, innerVertex, prevEdge, c)) {
2097 innerInversion = false;
2098 }
2099 if (!inversion(outerVertices.fTail, outerVertex, prevEdge, c)) {
2100 outerInversion = false;
2101 }
2102 innerVertices.append(innerVertex);
2103 outerVertices.append(outerVertex);
2104 }
2105 }
2106 prevInner = inner;
2107 prevOuter = outer;
2108 prevV = v;
2109 prevEdge = e;
2110 prevNormal = normal;
2111 }
2112 if (!inversion(innerVertices.fTail, innerVertices.fHead, prevEdge, c)) {
2113 innerInversion = false;
2114 }
2115 if (!inversion(outerVertices.fTail, outerVertices.fHead, prevEdge, c)) {
2116 outerInversion = false;
2117 }
2118 // Outer edges get 1 winding, and inner edges get -2 winding. This ensures that the interior
2119 // is always filled (1 + -2 = -1 for normal cases, 1 + 2 = 3 for thin features where the
2120 // interior inverts).
2121 // For total inversion cases, the shape has now reversed handedness, so invert the winding
2122 // so it will be detected during collapse_overlap_regions().
2123 int innerWinding = innerInversion ? 2 : -2;
2124 int outerWinding = outerInversion ? -1 : 1;
2125 for (Vertex* v = innerVertices.fHead; v && v->fNext; v = v->fNext) {
2126 connect(v, v->fNext, Edge::Type::kInner, c, alloc, innerWinding);
2127 }
2128 connect(innerVertices.fTail, innerVertices.fHead, Edge::Type::kInner, c, alloc, innerWinding);
2129 for (Vertex* v = outerVertices.fHead; v && v->fNext; v = v->fNext) {
2130 connect(v, v->fNext, Edge::Type::kOuter, c, alloc, outerWinding);
2131 }
2132 connect(outerVertices.fTail, outerVertices.fHead, Edge::Type::kOuter, c, alloc, outerWinding);
2133 innerMesh->append(innerVertices);
2134 outerMesh->append(outerVertices);
2135}
senorblancof57372d2016-08-31 10:36:19 -07002136
Herb Derby5cdc9dd2017-02-13 12:10:46 -05002137void extract_boundary(EdgeList* boundary, Edge* e, SkPath::FillType fillType, SkArenaAlloc& alloc) {
Stephen White95152e12017-12-18 10:52:44 -05002138 LOG("\nextracting boundary\n");
Stephen White49789062017-02-21 10:35:49 -05002139 bool down = apply_fill_type(fillType, e->fWinding);
senorblancof57372d2016-08-31 10:36:19 -07002140 while (e) {
2141 e->fWinding = down ? 1 : -1;
2142 Edge* next;
Stephen Whitee260c462017-12-19 18:09:54 -05002143 e->fLine.normalize();
2144 e->fLine = e->fLine * e->fWinding;
senorblancof57372d2016-08-31 10:36:19 -07002145 boundary->append(e);
2146 if (down) {
2147 // Find outgoing edge, in clockwise order.
2148 if ((next = e->fNextEdgeAbove)) {
2149 down = false;
2150 } else if ((next = e->fBottom->fLastEdgeBelow)) {
2151 down = true;
2152 } else if ((next = e->fPrevEdgeAbove)) {
2153 down = false;
2154 }
2155 } else {
2156 // Find outgoing edge, in counter-clockwise order.
2157 if ((next = e->fPrevEdgeBelow)) {
2158 down = true;
2159 } else if ((next = e->fTop->fFirstEdgeAbove)) {
2160 down = false;
2161 } else if ((next = e->fNextEdgeBelow)) {
2162 down = true;
2163 }
2164 }
Stephen Whitee7a364d2017-01-11 16:19:26 -05002165 disconnect(e);
senorblancof57372d2016-08-31 10:36:19 -07002166 e = next;
2167 }
2168}
2169
Stephen White5ad721e2017-02-23 16:50:47 -05002170// Stage 5b: Extract boundaries from mesh, simplify and stroke them into a new mesh.
senorblancof57372d2016-08-31 10:36:19 -07002171
Stephen Whitebda29c02017-03-13 15:10:13 -04002172void extract_boundaries(const VertexList& inMesh, VertexList* innerVertices,
2173 VertexList* outerVertices, SkPath::FillType fillType,
Stephen White5ad721e2017-02-23 16:50:47 -05002174 Comparator& c, SkArenaAlloc& alloc) {
2175 remove_non_boundary_edges(inMesh, fillType, alloc);
2176 for (Vertex* v = inMesh.fHead; v; v = v->fNext) {
senorblancof57372d2016-08-31 10:36:19 -07002177 while (v->fFirstEdgeBelow) {
Stephen White5ad721e2017-02-23 16:50:47 -05002178 EdgeList boundary;
2179 extract_boundary(&boundary, v->fFirstEdgeBelow, fillType, alloc);
2180 simplify_boundary(&boundary, c, alloc);
Stephen Whitebda29c02017-03-13 15:10:13 -04002181 stroke_boundary(&boundary, innerVertices, outerVertices, c, alloc);
senorblancof57372d2016-08-31 10:36:19 -07002182 }
2183 }
senorblancof57372d2016-08-31 10:36:19 -07002184}
2185
Stephen Whitebda29c02017-03-13 15:10:13 -04002186// This is a driver function that calls stages 2-5 in turn.
ethannicholase9709e82016-01-07 13:34:16 -08002187
Stephen White3a9aab92017-03-07 14:07:18 -05002188void contours_to_mesh(VertexList* contours, int contourCnt, bool antialias,
Herb Derby5cdc9dd2017-02-13 12:10:46 -05002189 VertexList* mesh, Comparator& c, SkArenaAlloc& alloc) {
ethannicholase9709e82016-01-07 13:34:16 -08002190#if LOGGING_ENABLED
2191 for (int i = 0; i < contourCnt; ++i) {
Stephen White3a9aab92017-03-07 14:07:18 -05002192 Vertex* v = contours[i].fHead;
ethannicholase9709e82016-01-07 13:34:16 -08002193 SkASSERT(v);
2194 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
Stephen White3a9aab92017-03-07 14:07:18 -05002195 for (v = v->fNext; v; v = v->fNext) {
ethannicholase9709e82016-01-07 13:34:16 -08002196 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
2197 }
2198 }
2199#endif
senorblancof57372d2016-08-31 10:36:19 -07002200 sanitize_contours(contours, contourCnt, antialias);
Stephen Whitebf6137e2017-01-04 15:43:26 -05002201 build_edges(contours, contourCnt, mesh, c, alloc);
senorblancof57372d2016-08-31 10:36:19 -07002202}
2203
Stephen Whitebda29c02017-03-13 15:10:13 -04002204void sort_mesh(VertexList* vertices, Comparator& c, SkArenaAlloc& alloc) {
Stephen Whitebf6137e2017-01-04 15:43:26 -05002205 if (!vertices || !vertices->fHead) {
Stephen White2f4686f2017-01-03 16:20:01 -05002206 return;
ethannicholase9709e82016-01-07 13:34:16 -08002207 }
2208
2209 // Sort vertices in Y (secondarily in X).
Stephen White16a40cb2017-02-23 11:10:01 -05002210 if (c.fDirection == Comparator::Direction::kHorizontal) {
2211 merge_sort<sweep_lt_horiz>(vertices);
2212 } else {
2213 merge_sort<sweep_lt_vert>(vertices);
2214 }
ethannicholase9709e82016-01-07 13:34:16 -08002215#if LOGGING_ENABLED
Stephen White2e2cb9b2017-01-09 13:11:18 -05002216 for (Vertex* v = vertices->fHead; v != nullptr; v = v->fNext) {
ethannicholase9709e82016-01-07 13:34:16 -08002217 static float gID = 0.0f;
2218 v->fID = gID++;
2219 }
2220#endif
Stephen White2f4686f2017-01-03 16:20:01 -05002221}
2222
Stephen White3a9aab92017-03-07 14:07:18 -05002223Poly* contours_to_polys(VertexList* contours, int contourCnt, SkPath::FillType fillType,
Stephen Whitebda29c02017-03-13 15:10:13 -04002224 const SkRect& pathBounds, bool antialias, VertexList* outerMesh,
Herb Derby5cdc9dd2017-02-13 12:10:46 -05002225 SkArenaAlloc& alloc) {
Stephen White16a40cb2017-02-23 11:10:01 -05002226 Comparator c(pathBounds.width() > pathBounds.height() ? Comparator::Direction::kHorizontal
2227 : Comparator::Direction::kVertical);
Stephen Whitebf6137e2017-01-04 15:43:26 -05002228 VertexList mesh;
2229 contours_to_mesh(contours, contourCnt, antialias, &mesh, c, alloc);
Stephen Whitebda29c02017-03-13 15:10:13 -04002230 sort_mesh(&mesh, c, alloc);
2231 merge_coincident_vertices(&mesh, c, alloc);
Stephen White0cb31672017-06-08 14:41:01 -04002232 simplify(&mesh, c, alloc);
Stephen Whitec4dbc372019-05-22 10:50:14 -04002233 LOG("\nsimplified mesh:\n");
2234 dump_mesh(mesh);
senorblancof57372d2016-08-31 10:36:19 -07002235 if (antialias) {
Stephen Whitebda29c02017-03-13 15:10:13 -04002236 VertexList innerMesh;
2237 extract_boundaries(mesh, &innerMesh, outerMesh, fillType, c, alloc);
2238 sort_mesh(&innerMesh, c, alloc);
2239 sort_mesh(outerMesh, c, alloc);
Stephen Whitee260c462017-12-19 18:09:54 -05002240 merge_coincident_vertices(&innerMesh, c, alloc);
2241 bool was_complex = merge_coincident_vertices(outerMesh, c, alloc);
2242 was_complex = simplify(&innerMesh, c, alloc) || was_complex;
2243 was_complex = simplify(outerMesh, c, alloc) || was_complex;
2244 LOG("\ninner mesh before:\n");
2245 dump_mesh(innerMesh);
2246 LOG("\nouter mesh before:\n");
2247 dump_mesh(*outerMesh);
Stephen Whitec4dbc372019-05-22 10:50:14 -04002248 EventComparator eventLT(EventComparator::Op::kLessThan);
2249 EventComparator eventGT(EventComparator::Op::kGreaterThan);
2250 was_complex = collapse_overlap_regions(&innerMesh, c, alloc, eventLT) || was_complex;
2251 was_complex = collapse_overlap_regions(outerMesh, c, alloc, eventGT) || was_complex;
Stephen Whitee260c462017-12-19 18:09:54 -05002252 if (was_complex) {
Stephen Whitebda29c02017-03-13 15:10:13 -04002253 LOG("found complex mesh; taking slow path\n");
2254 VertexList aaMesh;
Stephen White95152e12017-12-18 10:52:44 -05002255 LOG("\ninner mesh after:\n");
2256 dump_mesh(innerMesh);
2257 LOG("\nouter mesh after:\n");
2258 dump_mesh(*outerMesh);
Stephen Whitebda29c02017-03-13 15:10:13 -04002259 connect_partners(outerMesh, c, alloc);
Stephen Whitee260c462017-12-19 18:09:54 -05002260 connect_partners(&innerMesh, c, alloc);
Stephen Whitebda29c02017-03-13 15:10:13 -04002261 sorted_merge(&innerMesh, outerMesh, &aaMesh, c);
2262 merge_coincident_vertices(&aaMesh, c, alloc);
Stephen White0cb31672017-06-08 14:41:01 -04002263 simplify(&aaMesh, c, alloc);
Stephen Whitec4dbc372019-05-22 10:50:14 -04002264 LOG("combined and simplified mesh:\n");
Stephen White95152e12017-12-18 10:52:44 -05002265 dump_mesh(aaMesh);
Stephen Whitebda29c02017-03-13 15:10:13 -04002266 outerMesh->fHead = outerMesh->fTail = nullptr;
2267 return tessellate(aaMesh, alloc);
2268 } else {
2269 LOG("no complex polygons; taking fast path\n");
Stephen Whitebda29c02017-03-13 15:10:13 -04002270 return tessellate(innerMesh, alloc);
2271 }
Stephen White49789062017-02-21 10:35:49 -05002272 } else {
2273 return tessellate(mesh, alloc);
senorblancof57372d2016-08-31 10:36:19 -07002274 }
senorblancof57372d2016-08-31 10:36:19 -07002275}
2276
2277// Stage 6: Triangulate the monotone polygons into a vertex buffer.
Brian Osman0995fd52019-01-09 09:52:25 -05002278void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, bool emitCoverage, void* data) {
senorblancof57372d2016-08-31 10:36:19 -07002279 for (Poly* poly = polys; poly; poly = poly->fNext) {
2280 if (apply_fill_type(fillType, poly)) {
Brian Osman0995fd52019-01-09 09:52:25 -05002281 data = poly->emit(emitCoverage, data);
senorblancof57372d2016-08-31 10:36:19 -07002282 }
2283 }
2284 return data;
ethannicholase9709e82016-01-07 13:34:16 -08002285}
2286
halcanary9d524f22016-03-29 09:03:52 -07002287Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
Stephen Whitebda29c02017-03-13 15:10:13 -04002288 int contourCnt, SkArenaAlloc& alloc, bool antialias, bool* isLinear,
2289 VertexList* outerMesh) {
ethannicholase9709e82016-01-07 13:34:16 -08002290 SkPath::FillType fillType = path.getFillType();
2291 if (SkPath::IsInverseFillType(fillType)) {
2292 contourCnt++;
2293 }
Stephen White3a9aab92017-03-07 14:07:18 -05002294 std::unique_ptr<VertexList[]> contours(new VertexList[contourCnt]);
ethannicholase9709e82016-01-07 13:34:16 -08002295
2296 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinear);
senorblancof57372d2016-08-31 10:36:19 -07002297 return contours_to_polys(contours.get(), contourCnt, path.getFillType(), path.getBounds(),
Stephen Whitebda29c02017-03-13 15:10:13 -04002298 antialias, outerMesh, alloc);
ethannicholase9709e82016-01-07 13:34:16 -08002299}
2300
Stephen White11f65e02017-02-16 19:00:39 -05002301int get_contour_count(const SkPath& path, SkScalar tolerance) {
2302 int contourCnt;
2303 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tolerance);
ethannicholase9709e82016-01-07 13:34:16 -08002304 if (maxPts <= 0) {
Stephen White11f65e02017-02-16 19:00:39 -05002305 return 0;
ethannicholase9709e82016-01-07 13:34:16 -08002306 }
Stephen White11f65e02017-02-16 19:00:39 -05002307 return contourCnt;
ethannicholase9709e82016-01-07 13:34:16 -08002308}
2309
Greg Danield5b45932018-06-07 13:15:10 -04002310int64_t count_points(Poly* polys, SkPath::FillType fillType) {
2311 int64_t count = 0;
ethannicholase9709e82016-01-07 13:34:16 -08002312 for (Poly* poly = polys; poly; poly = poly->fNext) {
senorblancof57372d2016-08-31 10:36:19 -07002313 if (apply_fill_type(fillType, poly) && poly->fCount >= 3) {
ethannicholase9709e82016-01-07 13:34:16 -08002314 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3);
2315 }
2316 }
2317 return count;
2318}
2319
Greg Danield5b45932018-06-07 13:15:10 -04002320int64_t count_outer_mesh_points(const VertexList& outerMesh) {
2321 int64_t count = 0;
Stephen Whitebda29c02017-03-13 15:10:13 -04002322 for (Vertex* v = outerMesh.fHead; v; v = v->fNext) {
2323 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
2324 count += TESSELLATOR_WIREFRAME ? 12 : 6;
2325 }
2326 }
2327 return count;
2328}
2329
Brian Osman0995fd52019-01-09 09:52:25 -05002330void* outer_mesh_to_triangles(const VertexList& outerMesh, bool emitCoverage, void* data) {
Stephen Whitebda29c02017-03-13 15:10:13 -04002331 for (Vertex* v = outerMesh.fHead; v; v = v->fNext) {
2332 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
2333 Vertex* v0 = e->fTop;
2334 Vertex* v1 = e->fBottom;
2335 Vertex* v2 = e->fBottom->fPartner;
2336 Vertex* v3 = e->fTop->fPartner;
Brian Osman0995fd52019-01-09 09:52:25 -05002337 data = emit_triangle(v0, v1, v2, emitCoverage, data);
2338 data = emit_triangle(v0, v2, v3, emitCoverage, data);
Stephen Whitebda29c02017-03-13 15:10:13 -04002339 }
2340 }
2341 return data;
2342}
2343
ethannicholase9709e82016-01-07 13:34:16 -08002344} // namespace
2345
2346namespace GrTessellator {
2347
2348// Stage 6: Triangulate the monotone polygons into a vertex buffer.
2349
halcanary9d524f22016-03-29 09:03:52 -07002350int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
Brian Osman0995fd52019-01-09 09:52:25 -05002351 VertexAllocator* vertexAllocator, bool antialias, bool* isLinear) {
Stephen White11f65e02017-02-16 19:00:39 -05002352 int contourCnt = get_contour_count(path, tolerance);
ethannicholase9709e82016-01-07 13:34:16 -08002353 if (contourCnt <= 0) {
2354 *isLinear = true;
2355 return 0;
2356 }
Stephen White11f65e02017-02-16 19:00:39 -05002357 SkArenaAlloc alloc(kArenaChunkSize);
Stephen Whitebda29c02017-03-13 15:10:13 -04002358 VertexList outerMesh;
senorblancof57372d2016-08-31 10:36:19 -07002359 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, antialias,
Stephen Whitebda29c02017-03-13 15:10:13 -04002360 isLinear, &outerMesh);
senorblanco7ab96e92016-10-12 06:47:44 -07002361 SkPath::FillType fillType = antialias ? SkPath::kWinding_FillType : path.getFillType();
Greg Danield5b45932018-06-07 13:15:10 -04002362 int64_t count64 = count_points(polys, fillType);
Stephen Whitebda29c02017-03-13 15:10:13 -04002363 if (antialias) {
Greg Danield5b45932018-06-07 13:15:10 -04002364 count64 += count_outer_mesh_points(outerMesh);
Stephen Whitebda29c02017-03-13 15:10:13 -04002365 }
Greg Danield5b45932018-06-07 13:15:10 -04002366 if (0 == count64 || count64 > SK_MaxS32) {
Stephen Whiteff60b172017-05-05 15:54:52 -04002367 return 0;
2368 }
Greg Danield5b45932018-06-07 13:15:10 -04002369 int count = count64;
ethannicholase9709e82016-01-07 13:34:16 -08002370
senorblancof57372d2016-08-31 10:36:19 -07002371 void* verts = vertexAllocator->lock(count);
senorblanco6599eff2016-03-10 08:38:45 -08002372 if (!verts) {
ethannicholase9709e82016-01-07 13:34:16 -08002373 SkDebugf("Could not allocate vertices\n");
2374 return 0;
2375 }
senorblancof57372d2016-08-31 10:36:19 -07002376
2377 LOG("emitting %d verts\n", count);
Brian Osman80879d42019-01-07 16:15:27 -05002378 void* end = polys_to_triangles(polys, fillType, antialias, verts);
2379 end = outer_mesh_to_triangles(outerMesh, true, end);
Brian Osman80879d42019-01-07 16:15:27 -05002380
senorblancof57372d2016-08-31 10:36:19 -07002381 int actualCount = static_cast<int>((static_cast<uint8_t*>(end) - static_cast<uint8_t*>(verts))
2382 / vertexAllocator->stride());
ethannicholase9709e82016-01-07 13:34:16 -08002383 SkASSERT(actualCount <= count);
senorblanco6599eff2016-03-10 08:38:45 -08002384 vertexAllocator->unlock(actualCount);
ethannicholase9709e82016-01-07 13:34:16 -08002385 return actualCount;
2386}
2387
halcanary9d524f22016-03-29 09:03:52 -07002388int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
ethannicholase9709e82016-01-07 13:34:16 -08002389 GrTessellator::WindingVertex** verts) {
Stephen White11f65e02017-02-16 19:00:39 -05002390 int contourCnt = get_contour_count(path, tolerance);
ethannicholase9709e82016-01-07 13:34:16 -08002391 if (contourCnt <= 0) {
Chris Dalton84403d72018-02-13 21:46:17 -05002392 *verts = nullptr;
ethannicholase9709e82016-01-07 13:34:16 -08002393 return 0;
2394 }
Stephen White11f65e02017-02-16 19:00:39 -05002395 SkArenaAlloc alloc(kArenaChunkSize);
ethannicholase9709e82016-01-07 13:34:16 -08002396 bool isLinear;
Stephen Whitebda29c02017-03-13 15:10:13 -04002397 Poly* polys = path_to_polys(path, tolerance, clipBounds, contourCnt, alloc, false, &isLinear,
2398 nullptr);
ethannicholase9709e82016-01-07 13:34:16 -08002399 SkPath::FillType fillType = path.getFillType();
Greg Danield5b45932018-06-07 13:15:10 -04002400 int64_t count64 = count_points(polys, fillType);
2401 if (0 == count64 || count64 > SK_MaxS32) {
ethannicholase9709e82016-01-07 13:34:16 -08002402 *verts = nullptr;
2403 return 0;
2404 }
Greg Danield5b45932018-06-07 13:15:10 -04002405 int count = count64;
ethannicholase9709e82016-01-07 13:34:16 -08002406
2407 *verts = new GrTessellator::WindingVertex[count];
2408 GrTessellator::WindingVertex* vertsEnd = *verts;
2409 SkPoint* points = new SkPoint[count];
2410 SkPoint* pointsEnd = points;
2411 for (Poly* poly = polys; poly; poly = poly->fNext) {
senorblancof57372d2016-08-31 10:36:19 -07002412 if (apply_fill_type(fillType, poly)) {
ethannicholase9709e82016-01-07 13:34:16 -08002413 SkPoint* start = pointsEnd;
Brian Osman80879d42019-01-07 16:15:27 -05002414 pointsEnd = static_cast<SkPoint*>(poly->emit(false, pointsEnd));
ethannicholase9709e82016-01-07 13:34:16 -08002415 while (start != pointsEnd) {
2416 vertsEnd->fPos = *start;
2417 vertsEnd->fWinding = poly->fWinding;
2418 ++start;
2419 ++vertsEnd;
2420 }
2421 }
2422 }
2423 int actualCount = static_cast<int>(vertsEnd - *verts);
2424 SkASSERT(actualCount <= count);
2425 SkASSERT(pointsEnd - points == actualCount);
2426 delete[] points;
2427 return actualCount;
2428}
2429
2430} // namespace