blob: 9704246fa67ab24634895860feb927c7b6087e41 [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
Chris Dalton17dc4182020-03-25 16:18:16 -06008#ifndef GrTriangulator_DEFINED
9#define GrTriangulator_DEFINED
ethannicholase9709e82016-01-07 13:34:16 -080010
Chris Dalton57ea1fc2021-01-05 13:37:44 -070011#include "include/core/SkPath.h"
Mike Kleinc0bd9f92019-04-23 12:05:21 -050012#include "include/core/SkPoint.h"
Mike Kleinc0bd9f92019-04-23 12:05:21 -050013#include "include/private/SkColorData.h"
Chris Dalton57ea1fc2021-01-05 13:37:44 -070014#include "src/core/SkArenaAlloc.h"
Greg Danielf91aeb22019-06-18 09:58:02 -040015#include "src/gpu/GrColor.h"
senorblanco6599eff2016-03-10 08:38:45 -080016
Chris Daltond081dce2020-01-23 12:09:04 -070017class GrEagerVertexAllocator;
senorblanco6599eff2016-03-10 08:38:45 -080018struct SkRect;
ethannicholase9709e82016-01-07 13:34:16 -080019
Chris Dalton5045de32021-01-07 19:09:01 -070020#define TRIANGULATOR_LOGGING 0
Chris Dalton57ea1fc2021-01-05 13:37:44 -070021#define TRIANGULATOR_WIREFRAME 0
22
ethannicholase9709e82016-01-07 13:34:16 -080023/**
24 * Provides utility functions for converting paths to a collection of triangles.
25 */
Chris Dalton57ea1fc2021-01-05 13:37:44 -070026class GrTriangulator {
27public:
Chris Dalton8a42b092021-01-21 22:09:26 -070028 constexpr static int kArenaDefaultChunkSize = 16 * 1024;
29
Chris Dalton854ee852021-01-05 15:12:59 -070030 static int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
31 GrEagerVertexAllocator* vertexAllocator, bool* isLinear) {
Chris Dalton8a42b092021-01-21 22:09:26 -070032 SkArenaAlloc alloc(kArenaDefaultChunkSize);
33 GrTriangulator triangulator(path, &alloc);
Chris Dalton37d16f12021-01-20 18:32:48 -070034 Poly* polys = triangulator.pathToPolys(tolerance, clipBounds, isLinear);
Chris Daltond5384792021-01-20 15:43:24 -070035 int count = triangulator.polysToTriangles(polys, vertexAllocator);
Chris Dalton854ee852021-01-05 15:12:59 -070036 return count;
Chris Dalton57ea1fc2021-01-05 13:37:44 -070037 }
ethannicholase9709e82016-01-07 13:34:16 -080038
Chris Dalton57ea1fc2021-01-05 13:37:44 -070039 struct WindingVertex {
40 SkPoint fPos;
41 int fWinding;
42 };
Chris Dalton6ccc0322020-01-29 11:38:16 -070043
Chris Dalton57ea1fc2021-01-05 13:37:44 -070044 // *DEPRECATED*: Once CCPR is removed this method will go away.
Chris Dalton6ccc0322020-01-29 11:38:16 -070045 //
Chris Dalton57ea1fc2021-01-05 13:37:44 -070046 // Triangulates a path to an array of vertices. Each triangle is represented as a set of three
47 // WindingVertex entries, each of which contains the position and winding count (which is the
48 // same for all three vertices of a triangle). The 'verts' out parameter is set to point to the
49 // resultant vertex array. CALLER IS RESPONSIBLE for deleting this buffer to avoid a memory
50 // leak!
51 static int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
52 WindingVertex** verts);
53
Chris Dalton17ce8c52021-01-07 18:08:46 -070054 // Enums used by GrTriangulator internals.
55 typedef enum { kLeft_Side, kRight_Side } Side;
56 enum class EdgeType { kInner, kOuter, kConnector };
57
Chris Dalton57ea1fc2021-01-05 13:37:44 -070058 // Structs used by GrTriangulator internals.
59 struct Vertex;
60 struct VertexList;
Chris Dalton17ce8c52021-01-07 18:08:46 -070061 struct Line;
Chris Dalton57ea1fc2021-01-05 13:37:44 -070062 struct Edge;
63 struct EdgeList;
Chris Dalton17ce8c52021-01-07 18:08:46 -070064 struct MonotonePoly;
Chris Dalton57ea1fc2021-01-05 13:37:44 -070065 struct Poly;
66 struct Comparator;
67
Chris Dalton7cf3add2021-01-11 18:33:28 -070068protected:
Chris Dalton8a42b092021-01-21 22:09:26 -070069 GrTriangulator(const SkPath& path, SkArenaAlloc* alloc) : fPath(path), fAlloc(alloc) {}
Chris Dalton7cf3add2021-01-11 18:33:28 -070070 virtual ~GrTriangulator() {}
Chris Dalton57ea1fc2021-01-05 13:37:44 -070071
72 // There are six stages to the basic algorithm:
73 //
74 // 1) Linearize the path contours into piecewise linear segments:
Chris Dalton37d16f12021-01-20 18:32:48 -070075 void pathToContours(float tolerance, const SkRect& clipBounds, VertexList* contours,
76 bool* isLinear);
Chris Dalton57ea1fc2021-01-05 13:37:44 -070077
78 // 2) Build a mesh of edges connecting the vertices:
Chris Dalton811dc6a2021-01-07 16:40:32 -070079 void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -070080
Chris Dalton68b8bd52021-01-14 10:48:02 -070081 // 3) Sort the vertices in Y (and secondarily in X):
Chris Dalton47114db2021-01-06 00:35:20 -070082 static void SortedMerge(VertexList* front, VertexList* back, VertexList* result,
83 const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -070084 static void SortMesh(VertexList* vertices, const Comparator&);
85
86 // 4) Simplify the mesh by inserting new vertices at intersecting edges:
87 enum class SimplifyResult {
88 kAlreadySimple,
89 kFoundSelfIntersection,
90 kAbort
91 };
92
Chris Dalton811dc6a2021-01-07 16:40:32 -070093 SimplifyResult simplify(VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -070094
95 // 5) Tessellate the simplified mesh into monotone polygons:
Chris Dalton93c2d812021-01-11 19:51:59 -070096 virtual Poly* tessellate(const VertexList& vertices, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -070097
98 // 6) Triangulate the monotone polygons directly into a vertex buffer:
Chris Daltond5384792021-01-20 15:43:24 -070099 void* polysToTriangles(Poly* polys, void* data, SkPathFillType overrideFillType);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700100
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700101 // The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
102 // of vertices (and the necessity of inserting new vertices on intersection).
103 //
104 // Stages (4) and (5) use an active edge list -- a list of all edges for which the
105 // sweep line has crossed the top vertex, but not the bottom vertex. It's sorted
106 // left-to-right based on the point where both edges are active (when both top vertices
107 // have been seen, so the "lower" top vertex of the two). If the top vertices are equal
108 // (shared), it's sorted based on the last point where both edges are active, so the
109 // "upper" bottom vertex.
110 //
111 // The most complex step is the simplification (4). It's based on the Bentley-Ottman
112 // line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
113 // not exact and may violate the mesh topology or active edge list ordering. We
114 // accommodate this by adjusting the topology of the mesh and AEL to match the intersection
115 // points. This occurs in two ways:
116 //
117 // A) Intersections may cause a shortened edge to no longer be ordered with respect to its
118 // neighbouring edges at the top or bottom vertex. This is handled by merging the
Chris Dalton68b8bd52021-01-14 10:48:02 -0700119 // edges (mergeCollinearVertices()).
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700120 // B) Intersections may cause an edge to violate the left-to-right ordering of the
121 // active edge list. This is handled by detecting potential violations and rewinding
122 // the active edge list to the vertex before they occur (rewind() during merging,
123 // rewind_if_necessary() during splitting).
124 //
125 // The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
126 // Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
127 // currently uses a linked list for the active edge list, rather than a 2-3 tree as the
128 // paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
129 // become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
130 // insertions and removals was greater than the cost of infrequent O(N) lookups with the
131 // linked list implementation. With the latter, all removals are O(1), and most insertions
132 // are O(1), since we know the adjacent edge in the active edge list based on the topology.
133 // Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
134 // frequent. There may be other data structures worth investigating, however.
135 //
136 // Note that the orientation of the line sweep algorithms is determined by the aspect ratio of
137 // the path bounds. When the path is taller than it is wide, we sort vertices based on
138 // increasing Y coordinate, and secondarily by increasing X coordinate. When the path is wider
139 // than it is tall, we sort by increasing X coordinate, but secondarily by *decreasing* Y
140 // coordinate. This is so that the "left" and "right" orientation in the code remains correct
141 // (edges to the left are increasing in Y; edges to the right are decreasing in Y). That is, the
142 // setting rotates 90 degrees counterclockwise, rather that transposing.
143
144 // Additional helpers and driver functions.
Chris Dalton9a4904f2021-01-07 19:10:14 -0700145 void* emitMonotonePoly(const MonotonePoly*, void* data);
146 void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, int winding, void* data) const;
147 void* emitPoly(const Poly*, void *data);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700148 Poly* makePoly(Poly** head, Vertex* v, int winding);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700149 void appendPointToContour(const SkPoint& p, VertexList* contour);
150 void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd, VertexList* contour);
151 void generateCubicPoints(const SkPoint&, const SkPoint&, const SkPoint&, const SkPoint&,
152 SkScalar tolSqd, VertexList* contour, int pointsLeft);
Chris Dalton47114db2021-01-06 00:35:20 -0700153 bool applyFillType(int winding);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700154 Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&);
Chris Dalton68b8bd52021-01-14 10:48:02 -0700155 void setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator&);
156 void setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
157 const Comparator&);
158 void mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
159 const Comparator&);
160 void mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
161 const Comparator&);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700162 Edge* makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType, const Comparator&,
163 int windingScale = 1);
Chris Dalton68b8bd52021-01-14 10:48:02 -0700164 void mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh, const Comparator&);
Chris Dalton47114db2021-01-06 00:35:20 -0700165 static void FindEnclosingEdges(Vertex* v, EdgeList* edges, Edge** left, Edge** right);
Chris Dalton68b8bd52021-01-14 10:48:02 -0700166 void mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
167 const Comparator&);
Chris Dalton811dc6a2021-01-07 16:40:32 -0700168 bool splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
169 const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700170 bool intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton811dc6a2021-01-07 16:40:32 -0700171 const Comparator&);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700172 Vertex* makeSortedVertex(const SkPoint&, uint8_t alpha, VertexList* mesh, Vertex* reference,
173 const Comparator&);
174 void computeBisector(Edge* edge1, Edge* edge2, Vertex*);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700175 bool checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton811dc6a2021-01-07 16:40:32 -0700176 VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700177 void sanitizeContours(VertexList* contours, int contourCnt);
Chris Dalton811dc6a2021-01-07 16:40:32 -0700178 bool mergeCoincidentVertices(VertexList* mesh, const Comparator&);
179 void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
Chris Dalton93c2d812021-01-11 19:51:59 -0700180 Poly* contoursToPolys(VertexList* contours, int contourCnt);
Chris Dalton37d16f12021-01-20 18:32:48 -0700181 Poly* pathToPolys(float tolerance, const SkRect& clipBounds, bool* isLinear);
Chris Daltond5384792021-01-20 15:43:24 -0700182 static int64_t CountPoints(Poly* polys, SkPathFillType overrideFillType);
183 int polysToTriangles(Poly*, GrEagerVertexAllocator*);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700184
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700185 const SkPath fPath;
Chris Dalton8a42b092021-01-21 22:09:26 -0700186 SkArenaAlloc* const fAlloc;
Chris Dalton854ee852021-01-05 15:12:59 -0700187
Chris Dalton68b8bd52021-01-14 10:48:02 -0700188 // Internal control knobs.
Chris Dalton854ee852021-01-05 15:12:59 -0700189 bool fRoundVerticesToQuarterPixel = false;
190 bool fEmitCoverage = false;
191 bool fCullCollinearVertices = true;
Chris Dalton57115c02021-01-12 18:12:18 -0700192 bool fDisallowSelfIntersection = false;
Chris Daltone4652052021-01-21 18:31:28 -0700193
194 // The breadcrumb triangles serve as a glue that erases T-junctions between a path's outer
195 // curves and its inner polygon triangulation. Drawing a path's outer curves, breadcrumb
196 // triangles, and inner polygon triangulation all together into the stencil buffer has the same
197 // identical rasterized effect as stenciling a classic Redbook fan.
198 //
199 // The breadcrumb triangles track all the edge splits that led from the original inner polygon
200 // edges to the final triangulation. Every time an edge splits, we emit a razor-thin breadcrumb
201 // triangle consisting of the edge's original endpoints and the split point. (We also add
202 // supplemental breadcrumb triangles to areas where abs(winding) > 1.)
203 //
204 // a
205 // /
206 // /
207 // /
208 // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x].
209 // /
210 // /
211 // b
212 //
213 // The opposite-direction shared edges between the triangulation and breadcrumb triangles should
214 // all cancel out, leaving just the set of edges from the original polygon.
215 class BreadcrumbTriangleCollector {
216 public:
217 void push(SkPoint a, SkPoint b, SkPoint c, int winding) {
218 if (a != b && a != c && b != c) {
219 if (winding > 0) {
220 this->onPush(a, b, c, winding);
221 } else if (winding < 0) {
222 this->onPush(b, a, c, -winding);
223 }
224 }
225 }
226 virtual ~BreadcrumbTriangleCollector() {}
227 private:
228 virtual void onPush(SkPoint, SkPoint, SkPoint, int winding) = 0;
229 };
230
Chris Dalton68b8bd52021-01-14 10:48:02 -0700231 BreadcrumbTriangleCollector* fBreadcrumbTriangles = nullptr;
Chris Daltondcc8c542020-01-28 17:55:56 -0700232};
233
Chris Dalton5045de32021-01-07 19:09:01 -0700234/**
235 * Vertices are used in three ways: first, the path contours are converted into a
236 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
237 * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
238 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
239 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
240 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
241 * an individual Vertex from the path mesh may belong to multiple
242 * MonotonePolys, so the original Vertices cannot be re-used.
243 */
244
245struct GrTriangulator::Vertex {
246 Vertex(const SkPoint& point, uint8_t alpha)
247 : fPoint(point), fPrev(nullptr), fNext(nullptr)
248 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
249 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
250 , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
251 , fPartner(nullptr)
252 , fAlpha(alpha)
253 , fSynthetic(false)
254#if TRIANGULATOR_LOGGING
255 , fID (-1.0f)
256#endif
257 {}
258 SkPoint fPoint; // Vertex position
259 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
260 Vertex* fNext; // "
261 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
262 Edge* fLastEdgeAbove; // "
263 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
264 Edge* fLastEdgeBelow; // "
265 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
266 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
267 Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
268 uint8_t fAlpha;
269 bool fSynthetic; // Is this a synthetic vertex?
270#if TRIANGULATOR_LOGGING
271 float fID; // Identifier used for logging.
272#endif
Chris Dalton24472af2021-01-11 20:05:00 -0700273 bool isConnected() const { return this->fFirstEdgeAbove || this->fFirstEdgeBelow; }
Chris Dalton5045de32021-01-07 19:09:01 -0700274};
275
276struct GrTriangulator::VertexList {
277 VertexList() : fHead(nullptr), fTail(nullptr) {}
278 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {}
279 Vertex* fHead;
280 Vertex* fTail;
281 void insert(Vertex* v, Vertex* prev, Vertex* next);
282 void append(Vertex* v) { insert(v, fTail, nullptr); }
283 void append(const VertexList& list) {
284 if (!list.fHead) {
285 return;
286 }
287 if (fTail) {
288 fTail->fNext = list.fHead;
289 list.fHead->fPrev = fTail;
290 } else {
291 fHead = list.fHead;
292 }
293 fTail = list.fTail;
294 }
295 void prepend(Vertex* v) { insert(v, nullptr, fHead); }
296 void remove(Vertex* v);
297 void close() {
298 if (fHead && fTail) {
299 fTail->fNext = fHead;
300 fHead->fPrev = fTail;
301 }
302 }
Chris Dalton24472af2021-01-11 20:05:00 -0700303#if TRIANGULATOR_LOGGING
304 void dump();
305#endif
Chris Dalton5045de32021-01-07 19:09:01 -0700306};
307
308// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
309struct GrTriangulator::Line {
310 Line(double a, double b, double c) : fA(a), fB(b), fC(c) {}
311 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
312 Line(const SkPoint& p, const SkPoint& q)
313 : fA(static_cast<double>(q.fY) - p.fY) // a = dY
314 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX
315 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p)
316 static_cast<double>(p.fX) * q.fY) {}
317 double dist(const SkPoint& p) const { return fA * p.fX + fB * p.fY + fC; }
318 Line operator*(double v) const { return Line(fA * v, fB * v, fC * v); }
319 double magSq() const { return fA * fA + fB * fB; }
320 void normalize() {
321 double len = sqrt(this->magSq());
322 if (len == 0.0) {
323 return;
324 }
325 double scale = 1.0f / len;
326 fA *= scale;
327 fB *= scale;
328 fC *= scale;
329 }
330 bool nearParallel(const Line& o) const {
331 return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001;
332 }
333
334 // Compute the intersection of two (infinite) Lines.
335 bool intersect(const Line& other, SkPoint* point) const;
336 double fA, fB, fC;
337};
338
339/**
340 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
341 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
342 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
343 * point). For speed, that case is only tested by the callers that require it (e.g.,
344 * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
345 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
346 * until an intersection has been confirmed. This is slightly slower in the "found" case, but
347 * a lot faster in the "not found" case.
348 *
349 * The coefficients of the line equation stored in double precision to avoid catastrophic
350 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
351 * correct in float, since it's a polynomial of degree 2. The intersect() function, being
352 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
353 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
354 * this file).
355 */
356
357struct GrTriangulator::Edge {
358 Edge(Vertex* top, Vertex* bottom, int winding, EdgeType type)
359 : fWinding(winding)
360 , fTop(top)
361 , fBottom(bottom)
362 , fType(type)
363 , fLeft(nullptr)
364 , fRight(nullptr)
365 , fPrevEdgeAbove(nullptr)
366 , fNextEdgeAbove(nullptr)
367 , fPrevEdgeBelow(nullptr)
368 , fNextEdgeBelow(nullptr)
369 , fLeftPoly(nullptr)
370 , fRightPoly(nullptr)
371 , fLeftPolyPrev(nullptr)
372 , fLeftPolyNext(nullptr)
373 , fRightPolyPrev(nullptr)
374 , fRightPolyNext(nullptr)
375 , fUsedInLeftPoly(false)
376 , fUsedInRightPoly(false)
377 , fLine(top, bottom) {
378 }
379 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
380 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt).
381 Vertex* fBottom; // The bottom vertex in vertex-sort-order.
382 EdgeType fType;
383 Edge* fLeft; // The linked list of edges in the active edge list.
384 Edge* fRight; // "
385 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
386 Edge* fNextEdgeAbove; // "
387 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
388 Edge* fNextEdgeBelow; // "
389 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
390 Poly* fRightPoly; // The Poly to the right of this edge, if any.
391 Edge* fLeftPolyPrev;
392 Edge* fLeftPolyNext;
393 Edge* fRightPolyPrev;
394 Edge* fRightPolyNext;
395 bool fUsedInLeftPoly;
396 bool fUsedInRightPoly;
397 Line fLine;
398 double dist(const SkPoint& p) const { return fLine.dist(p); }
399 bool isRightOf(Vertex* v) const { return fLine.dist(v->fPoint) < 0.0; }
400 bool isLeftOf(Vertex* v) const { return fLine.dist(v->fPoint) > 0.0; }
401 void recompute() { fLine = Line(fTop, fBottom); }
Chris Dalton24472af2021-01-11 20:05:00 -0700402 void insertAbove(Vertex*, const Comparator&);
403 void insertBelow(Vertex*, const Comparator&);
404 void disconnect();
Chris Dalton5045de32021-01-07 19:09:01 -0700405 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const;
406};
407
408struct GrTriangulator::EdgeList {
409 EdgeList() : fHead(nullptr), fTail(nullptr) {}
410 Edge* fHead;
411 Edge* fTail;
412 void insert(Edge* edge, Edge* prev, Edge* next);
Chris Dalton24472af2021-01-11 20:05:00 -0700413 void insert(Edge* edge, Edge* prev);
Chris Dalton5045de32021-01-07 19:09:01 -0700414 void append(Edge* e) { insert(e, fTail, nullptr); }
415 void remove(Edge* edge);
416 void removeAll() {
417 while (fHead) {
418 this->remove(fHead);
419 }
420 }
421 void close() {
422 if (fHead && fTail) {
423 fTail->fRight = fHead;
424 fHead->fLeft = fTail;
425 }
426 }
427 bool contains(Edge* edge) const { return edge->fLeft || edge->fRight || fHead == edge; }
428};
429
430struct GrTriangulator::MonotonePoly {
431 MonotonePoly(Edge* edge, Side side, int winding)
432 : fSide(side)
433 , fFirstEdge(nullptr)
434 , fLastEdge(nullptr)
435 , fPrev(nullptr)
436 , fNext(nullptr)
437 , fWinding(winding) {
438 this->addEdge(edge);
439 }
440 Side fSide;
441 Edge* fFirstEdge;
442 Edge* fLastEdge;
443 MonotonePoly* fPrev;
444 MonotonePoly* fNext;
445 int fWinding;
446 void addEdge(Edge*);
447 void* emit(bool emitCoverage, void* data);
448 void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, bool emitCoverage,
449 void* data) const;
450};
451
452struct GrTriangulator::Poly {
453 Poly(Vertex* v, int winding)
454 : fFirstVertex(v)
455 , fWinding(winding)
456 , fHead(nullptr)
457 , fTail(nullptr)
458 , fNext(nullptr)
459 , fPartner(nullptr)
460 , fCount(0)
461 {
462#if TRIANGULATOR_LOGGING
463 static int gID = 0;
464 fID = gID++;
465 TESS_LOG("*** created Poly %d\n", fID);
466#endif
467 }
Chris Dalton8a42b092021-01-21 22:09:26 -0700468 Poly* addEdge(Edge* e, Side side, SkArenaAlloc* alloc);
Chris Dalton5045de32021-01-07 19:09:01 -0700469 void* emit(bool emitCoverage, void *data);
470 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
471 Vertex* fFirstVertex;
472 int fWinding;
473 MonotonePoly* fHead;
474 MonotonePoly* fTail;
475 Poly* fNext;
476 Poly* fPartner;
477 int fCount;
478#if TRIANGULATOR_LOGGING
479 int fID;
480#endif
481};
482
483struct GrTriangulator::Comparator {
484 enum class Direction { kVertical, kHorizontal };
485 Comparator(Direction direction) : fDirection(direction) {}
486 bool sweep_lt(const SkPoint& a, const SkPoint& b) const;
487 Direction fDirection;
488};
489
ethannicholase9709e82016-01-07 13:34:16 -0800490#endif