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