blob: ea343122c8bc2f4f8ec7f952ba3edc1ae80d0c02 [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 Dalton854ee852021-01-05 15:12:59 -070028 static int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
29 GrEagerVertexAllocator* vertexAllocator, bool* isLinear) {
30 GrTriangulator triangulator(path);
Chris Dalton37d16f12021-01-20 18:32:48 -070031 Poly* polys = triangulator.pathToPolys(tolerance, clipBounds, isLinear);
Chris Daltond5384792021-01-20 15:43:24 -070032 int count = triangulator.polysToTriangles(polys, vertexAllocator);
Chris Dalton854ee852021-01-05 15:12:59 -070033 return count;
Chris Dalton57ea1fc2021-01-05 13:37:44 -070034 }
ethannicholase9709e82016-01-07 13:34:16 -080035
Chris Dalton68b8bd52021-01-14 10:48:02 -070036 // The breadcrumb triangles serve as a glue that erases T-junctions between a path's outer
37 // curves and its inner polygon triangulation. Drawing a path's outer curves, breadcrumb
38 // triangles, and inner polygon triangulation all together into the stencil buffer has the same
39 // identical rasterized effect as stenciling a classic Redbook fan.
40 //
41 // The breadcrumb triangles track all the edge splits that led from the original inner polygon
42 // edges to the final triangulation. Every time an edge splits, we emit a razor-thin breadcrumb
43 // triangle consisting of the edge's original endpoints and the split point. (We also add
44 // supplemental breadcrumb triangles to areas where abs(winding) > 1.)
45 //
46 // a
47 // /
48 // /
49 // /
50 // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x].
51 // /
52 // /
53 // b
54 //
55 // The opposite-direction shared edges between the triangulation and breadcrumb triangles should
56 // all cancel out, leaving just the set of edges from the original polygon.
57 class BreadcrumbTriangleCollector { public:
58 void push(SkPoint a, SkPoint b, SkPoint c, int winding) {
59 if (a != b && a != c && b != c) {
60 if (winding > 0) {
61 this->onPush(a, b, c, winding);
62 } else if (winding < 0) {
63 this->onPush(b, a, c, -winding);
64 }
65 }
66 }
67 virtual ~BreadcrumbTriangleCollector() {}
68 private:
69 virtual void onPush(SkPoint a, SkPoint b, SkPoint c, int winding) = 0;
70 };
71
72 static int TriangulateInnerPolygons(const SkPath& path, GrEagerVertexAllocator* vertexAllocator,
73 BreadcrumbTriangleCollector* breadcrumbTriangles, bool
74 *isLinear) {
75 GrTriangulator triangulator(path);
76 triangulator.fCullCollinearVertices = false;
77 triangulator.fBreadcrumbTriangles = breadcrumbTriangles;
Chris Dalton37d16f12021-01-20 18:32:48 -070078 Poly* polys = triangulator.pathToPolys(0, SkRect::MakeEmpty(), isLinear);
Chris Daltond5384792021-01-20 15:43:24 -070079 int count = triangulator.polysToTriangles(polys, vertexAllocator);
Chris Dalton68b8bd52021-01-14 10:48:02 -070080 return count;
81 }
82
Chris Dalton854ee852021-01-05 15:12:59 -070083 static int TriangulateSimpleInnerPolygons(const SkPath& path,
84 GrEagerVertexAllocator* vertexAllocator,
85 bool *isLinear) {
86 GrTriangulator triangulator(path);
87 triangulator.fCullCollinearVertices = false;
Chris Dalton57115c02021-01-12 18:12:18 -070088 triangulator.fDisallowSelfIntersection = true;
Chris Dalton37d16f12021-01-20 18:32:48 -070089 Poly* polys = triangulator.pathToPolys(0, SkRect::MakeEmpty(), isLinear);
Chris Daltond5384792021-01-20 15:43:24 -070090 int count = triangulator.polysToTriangles(polys, vertexAllocator);
Chris Dalton854ee852021-01-05 15:12:59 -070091 return count;
92 }
ethannicholase9709e82016-01-07 13:34:16 -080093
Chris Dalton57ea1fc2021-01-05 13:37:44 -070094 struct WindingVertex {
95 SkPoint fPos;
96 int fWinding;
97 };
Chris Dalton6ccc0322020-01-29 11:38:16 -070098
Chris Dalton57ea1fc2021-01-05 13:37:44 -070099 // *DEPRECATED*: Once CCPR is removed this method will go away.
Chris Dalton6ccc0322020-01-29 11:38:16 -0700100 //
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700101 // Triangulates a path to an array of vertices. Each triangle is represented as a set of three
102 // WindingVertex entries, each of which contains the position and winding count (which is the
103 // same for all three vertices of a triangle). The 'verts' out parameter is set to point to the
104 // resultant vertex array. CALLER IS RESPONSIBLE for deleting this buffer to avoid a memory
105 // leak!
106 static int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
107 WindingVertex** verts);
108
Chris Dalton17ce8c52021-01-07 18:08:46 -0700109 // Enums used by GrTriangulator internals.
110 typedef enum { kLeft_Side, kRight_Side } Side;
111 enum class EdgeType { kInner, kOuter, kConnector };
112
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700113 // Structs used by GrTriangulator internals.
114 struct Vertex;
115 struct VertexList;
Chris Dalton17ce8c52021-01-07 18:08:46 -0700116 struct Line;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700117 struct Edge;
118 struct EdgeList;
Chris Dalton17ce8c52021-01-07 18:08:46 -0700119 struct MonotonePoly;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700120 struct Poly;
121 struct Comparator;
122
Chris Dalton7cf3add2021-01-11 18:33:28 -0700123protected:
Chris Dalton854ee852021-01-05 15:12:59 -0700124 GrTriangulator(const SkPath& path) : fPath(path) {}
Chris Dalton7cf3add2021-01-11 18:33:28 -0700125 virtual ~GrTriangulator() {}
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700126
127 // There are six stages to the basic algorithm:
128 //
129 // 1) Linearize the path contours into piecewise linear segments:
Chris Dalton37d16f12021-01-20 18:32:48 -0700130 void pathToContours(float tolerance, const SkRect& clipBounds, VertexList* contours,
131 bool* isLinear);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700132
133 // 2) Build a mesh of edges connecting the vertices:
Chris Dalton811dc6a2021-01-07 16:40:32 -0700134 void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700135
Chris Dalton68b8bd52021-01-14 10:48:02 -0700136 // 3) Sort the vertices in Y (and secondarily in X):
Chris Dalton47114db2021-01-06 00:35:20 -0700137 static void SortedMerge(VertexList* front, VertexList* back, VertexList* result,
138 const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700139 static void SortMesh(VertexList* vertices, const Comparator&);
140
141 // 4) Simplify the mesh by inserting new vertices at intersecting edges:
142 enum class SimplifyResult {
143 kAlreadySimple,
144 kFoundSelfIntersection,
145 kAbort
146 };
147
Chris Dalton811dc6a2021-01-07 16:40:32 -0700148 SimplifyResult simplify(VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700149
150 // 5) Tessellate the simplified mesh into monotone polygons:
Chris Dalton93c2d812021-01-11 19:51:59 -0700151 virtual Poly* tessellate(const VertexList& vertices, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700152
153 // 6) Triangulate the monotone polygons directly into a vertex buffer:
Chris Daltond5384792021-01-20 15:43:24 -0700154 void* polysToTriangles(Poly* polys, void* data, SkPathFillType overrideFillType);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700155
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700156 // The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
157 // of vertices (and the necessity of inserting new vertices on intersection).
158 //
159 // Stages (4) and (5) use an active edge list -- a list of all edges for which the
160 // sweep line has crossed the top vertex, but not the bottom vertex. It's sorted
161 // left-to-right based on the point where both edges are active (when both top vertices
162 // have been seen, so the "lower" top vertex of the two). If the top vertices are equal
163 // (shared), it's sorted based on the last point where both edges are active, so the
164 // "upper" bottom vertex.
165 //
166 // The most complex step is the simplification (4). It's based on the Bentley-Ottman
167 // line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
168 // not exact and may violate the mesh topology or active edge list ordering. We
169 // accommodate this by adjusting the topology of the mesh and AEL to match the intersection
170 // points. This occurs in two ways:
171 //
172 // A) Intersections may cause a shortened edge to no longer be ordered with respect to its
173 // neighbouring edges at the top or bottom vertex. This is handled by merging the
Chris Dalton68b8bd52021-01-14 10:48:02 -0700174 // edges (mergeCollinearVertices()).
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700175 // B) Intersections may cause an edge to violate the left-to-right ordering of the
176 // active edge list. This is handled by detecting potential violations and rewinding
177 // the active edge list to the vertex before they occur (rewind() during merging,
178 // rewind_if_necessary() during splitting).
179 //
180 // The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
181 // Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
182 // currently uses a linked list for the active edge list, rather than a 2-3 tree as the
183 // paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
184 // become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
185 // insertions and removals was greater than the cost of infrequent O(N) lookups with the
186 // linked list implementation. With the latter, all removals are O(1), and most insertions
187 // are O(1), since we know the adjacent edge in the active edge list based on the topology.
188 // Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
189 // frequent. There may be other data structures worth investigating, however.
190 //
191 // Note that the orientation of the line sweep algorithms is determined by the aspect ratio of
192 // the path bounds. When the path is taller than it is wide, we sort vertices based on
193 // increasing Y coordinate, and secondarily by increasing X coordinate. When the path is wider
194 // than it is tall, we sort by increasing X coordinate, but secondarily by *decreasing* Y
195 // coordinate. This is so that the "left" and "right" orientation in the code remains correct
196 // (edges to the left are increasing in Y; edges to the right are decreasing in Y). That is, the
197 // setting rotates 90 degrees counterclockwise, rather that transposing.
198
199 // Additional helpers and driver functions.
Chris Dalton9a4904f2021-01-07 19:10:14 -0700200 void* emitMonotonePoly(const MonotonePoly*, void* data);
201 void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, int winding, void* data) const;
202 void* emitPoly(const Poly*, void *data);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700203 Poly* makePoly(Poly** head, Vertex* v, int winding);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700204 void appendPointToContour(const SkPoint& p, VertexList* contour);
205 void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd, VertexList* contour);
206 void generateCubicPoints(const SkPoint&, const SkPoint&, const SkPoint&, const SkPoint&,
207 SkScalar tolSqd, VertexList* contour, int pointsLeft);
Chris Dalton47114db2021-01-06 00:35:20 -0700208 bool applyFillType(int winding);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700209 Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&);
Chris Dalton68b8bd52021-01-14 10:48:02 -0700210 void setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator&);
211 void setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
212 const Comparator&);
213 void mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
214 const Comparator&);
215 void mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
216 const Comparator&);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700217 Edge* makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType, const Comparator&,
218 int windingScale = 1);
Chris Dalton68b8bd52021-01-14 10:48:02 -0700219 void mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh, const Comparator&);
Chris Dalton47114db2021-01-06 00:35:20 -0700220 static void FindEnclosingEdges(Vertex* v, EdgeList* edges, Edge** left, Edge** right);
Chris Dalton68b8bd52021-01-14 10:48:02 -0700221 void mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
222 const Comparator&);
Chris Dalton811dc6a2021-01-07 16:40:32 -0700223 bool splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
224 const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700225 bool intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton811dc6a2021-01-07 16:40:32 -0700226 const Comparator&);
Chris Dalton7cf3add2021-01-11 18:33:28 -0700227 Vertex* makeSortedVertex(const SkPoint&, uint8_t alpha, VertexList* mesh, Vertex* reference,
228 const Comparator&);
229 void computeBisector(Edge* edge1, Edge* edge2, Vertex*);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700230 bool checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton811dc6a2021-01-07 16:40:32 -0700231 VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700232 void sanitizeContours(VertexList* contours, int contourCnt);
Chris Dalton811dc6a2021-01-07 16:40:32 -0700233 bool mergeCoincidentVertices(VertexList* mesh, const Comparator&);
234 void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
Chris Dalton93c2d812021-01-11 19:51:59 -0700235 Poly* contoursToPolys(VertexList* contours, int contourCnt);
Chris Dalton37d16f12021-01-20 18:32:48 -0700236 Poly* pathToPolys(float tolerance, const SkRect& clipBounds, bool* isLinear);
Chris Daltond5384792021-01-20 15:43:24 -0700237 static int64_t CountPoints(Poly* polys, SkPathFillType overrideFillType);
238 int polysToTriangles(Poly*, GrEagerVertexAllocator*);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700239
240 constexpr static int kArenaChunkSize = 16 * 1024;
241 SkArenaAlloc fAlloc{kArenaChunkSize};
242 const SkPath fPath;
Chris Dalton854ee852021-01-05 15:12:59 -0700243
Chris Dalton68b8bd52021-01-14 10:48:02 -0700244 // Internal control knobs.
Chris Dalton854ee852021-01-05 15:12:59 -0700245 bool fRoundVerticesToQuarterPixel = false;
246 bool fEmitCoverage = false;
247 bool fCullCollinearVertices = true;
Chris Dalton57115c02021-01-12 18:12:18 -0700248 bool fDisallowSelfIntersection = false;
Chris Dalton68b8bd52021-01-14 10:48:02 -0700249 BreadcrumbTriangleCollector* fBreadcrumbTriangles = nullptr;
Chris Daltondcc8c542020-01-28 17:55:56 -0700250};
251
Chris Dalton5045de32021-01-07 19:09:01 -0700252/**
253 * Vertices are used in three ways: first, the path contours are converted into a
254 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
255 * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
256 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
257 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
258 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
259 * an individual Vertex from the path mesh may belong to multiple
260 * MonotonePolys, so the original Vertices cannot be re-used.
261 */
262
263struct GrTriangulator::Vertex {
264 Vertex(const SkPoint& point, uint8_t alpha)
265 : fPoint(point), fPrev(nullptr), fNext(nullptr)
266 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
267 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
268 , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
269 , fPartner(nullptr)
270 , fAlpha(alpha)
271 , fSynthetic(false)
272#if TRIANGULATOR_LOGGING
273 , fID (-1.0f)
274#endif
275 {}
276 SkPoint fPoint; // Vertex position
277 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
278 Vertex* fNext; // "
279 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
280 Edge* fLastEdgeAbove; // "
281 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
282 Edge* fLastEdgeBelow; // "
283 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
284 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
285 Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
286 uint8_t fAlpha;
287 bool fSynthetic; // Is this a synthetic vertex?
288#if TRIANGULATOR_LOGGING
289 float fID; // Identifier used for logging.
290#endif
Chris Dalton24472af2021-01-11 20:05:00 -0700291 bool isConnected() const { return this->fFirstEdgeAbove || this->fFirstEdgeBelow; }
Chris Dalton5045de32021-01-07 19:09:01 -0700292};
293
294struct GrTriangulator::VertexList {
295 VertexList() : fHead(nullptr), fTail(nullptr) {}
296 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {}
297 Vertex* fHead;
298 Vertex* fTail;
299 void insert(Vertex* v, Vertex* prev, Vertex* next);
300 void append(Vertex* v) { insert(v, fTail, nullptr); }
301 void append(const VertexList& list) {
302 if (!list.fHead) {
303 return;
304 }
305 if (fTail) {
306 fTail->fNext = list.fHead;
307 list.fHead->fPrev = fTail;
308 } else {
309 fHead = list.fHead;
310 }
311 fTail = list.fTail;
312 }
313 void prepend(Vertex* v) { insert(v, nullptr, fHead); }
314 void remove(Vertex* v);
315 void close() {
316 if (fHead && fTail) {
317 fTail->fNext = fHead;
318 fHead->fPrev = fTail;
319 }
320 }
Chris Dalton24472af2021-01-11 20:05:00 -0700321#if TRIANGULATOR_LOGGING
322 void dump();
323#endif
Chris Dalton5045de32021-01-07 19:09:01 -0700324};
325
326// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
327struct GrTriangulator::Line {
328 Line(double a, double b, double c) : fA(a), fB(b), fC(c) {}
329 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
330 Line(const SkPoint& p, const SkPoint& q)
331 : fA(static_cast<double>(q.fY) - p.fY) // a = dY
332 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX
333 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p)
334 static_cast<double>(p.fX) * q.fY) {}
335 double dist(const SkPoint& p) const { return fA * p.fX + fB * p.fY + fC; }
336 Line operator*(double v) const { return Line(fA * v, fB * v, fC * v); }
337 double magSq() const { return fA * fA + fB * fB; }
338 void normalize() {
339 double len = sqrt(this->magSq());
340 if (len == 0.0) {
341 return;
342 }
343 double scale = 1.0f / len;
344 fA *= scale;
345 fB *= scale;
346 fC *= scale;
347 }
348 bool nearParallel(const Line& o) const {
349 return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001;
350 }
351
352 // Compute the intersection of two (infinite) Lines.
353 bool intersect(const Line& other, SkPoint* point) const;
354 double fA, fB, fC;
355};
356
357/**
358 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
359 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
360 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
361 * point). For speed, that case is only tested by the callers that require it (e.g.,
362 * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
363 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
364 * until an intersection has been confirmed. This is slightly slower in the "found" case, but
365 * a lot faster in the "not found" case.
366 *
367 * The coefficients of the line equation stored in double precision to avoid catastrophic
368 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
369 * correct in float, since it's a polynomial of degree 2. The intersect() function, being
370 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
371 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
372 * this file).
373 */
374
375struct GrTriangulator::Edge {
376 Edge(Vertex* top, Vertex* bottom, int winding, EdgeType type)
377 : fWinding(winding)
378 , fTop(top)
379 , fBottom(bottom)
380 , fType(type)
381 , fLeft(nullptr)
382 , fRight(nullptr)
383 , fPrevEdgeAbove(nullptr)
384 , fNextEdgeAbove(nullptr)
385 , fPrevEdgeBelow(nullptr)
386 , fNextEdgeBelow(nullptr)
387 , fLeftPoly(nullptr)
388 , fRightPoly(nullptr)
389 , fLeftPolyPrev(nullptr)
390 , fLeftPolyNext(nullptr)
391 , fRightPolyPrev(nullptr)
392 , fRightPolyNext(nullptr)
393 , fUsedInLeftPoly(false)
394 , fUsedInRightPoly(false)
395 , fLine(top, bottom) {
396 }
397 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
398 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt).
399 Vertex* fBottom; // The bottom vertex in vertex-sort-order.
400 EdgeType fType;
401 Edge* fLeft; // The linked list of edges in the active edge list.
402 Edge* fRight; // "
403 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
404 Edge* fNextEdgeAbove; // "
405 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
406 Edge* fNextEdgeBelow; // "
407 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
408 Poly* fRightPoly; // The Poly to the right of this edge, if any.
409 Edge* fLeftPolyPrev;
410 Edge* fLeftPolyNext;
411 Edge* fRightPolyPrev;
412 Edge* fRightPolyNext;
413 bool fUsedInLeftPoly;
414 bool fUsedInRightPoly;
415 Line fLine;
416 double dist(const SkPoint& p) const { return fLine.dist(p); }
417 bool isRightOf(Vertex* v) const { return fLine.dist(v->fPoint) < 0.0; }
418 bool isLeftOf(Vertex* v) const { return fLine.dist(v->fPoint) > 0.0; }
419 void recompute() { fLine = Line(fTop, fBottom); }
Chris Dalton24472af2021-01-11 20:05:00 -0700420 void insertAbove(Vertex*, const Comparator&);
421 void insertBelow(Vertex*, const Comparator&);
422 void disconnect();
Chris Dalton5045de32021-01-07 19:09:01 -0700423 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const;
424};
425
426struct GrTriangulator::EdgeList {
427 EdgeList() : fHead(nullptr), fTail(nullptr) {}
428 Edge* fHead;
429 Edge* fTail;
430 void insert(Edge* edge, Edge* prev, Edge* next);
Chris Dalton24472af2021-01-11 20:05:00 -0700431 void insert(Edge* edge, Edge* prev);
Chris Dalton5045de32021-01-07 19:09:01 -0700432 void append(Edge* e) { insert(e, fTail, nullptr); }
433 void remove(Edge* edge);
434 void removeAll() {
435 while (fHead) {
436 this->remove(fHead);
437 }
438 }
439 void close() {
440 if (fHead && fTail) {
441 fTail->fRight = fHead;
442 fHead->fLeft = fTail;
443 }
444 }
445 bool contains(Edge* edge) const { return edge->fLeft || edge->fRight || fHead == edge; }
446};
447
448struct GrTriangulator::MonotonePoly {
449 MonotonePoly(Edge* edge, Side side, int winding)
450 : fSide(side)
451 , fFirstEdge(nullptr)
452 , fLastEdge(nullptr)
453 , fPrev(nullptr)
454 , fNext(nullptr)
455 , fWinding(winding) {
456 this->addEdge(edge);
457 }
458 Side fSide;
459 Edge* fFirstEdge;
460 Edge* fLastEdge;
461 MonotonePoly* fPrev;
462 MonotonePoly* fNext;
463 int fWinding;
464 void addEdge(Edge*);
465 void* emit(bool emitCoverage, void* data);
466 void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, bool emitCoverage,
467 void* data) const;
468};
469
470struct GrTriangulator::Poly {
471 Poly(Vertex* v, int winding)
472 : fFirstVertex(v)
473 , fWinding(winding)
474 , fHead(nullptr)
475 , fTail(nullptr)
476 , fNext(nullptr)
477 , fPartner(nullptr)
478 , fCount(0)
479 {
480#if TRIANGULATOR_LOGGING
481 static int gID = 0;
482 fID = gID++;
483 TESS_LOG("*** created Poly %d\n", fID);
484#endif
485 }
486 Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc);
487 void* emit(bool emitCoverage, void *data);
488 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
489 Vertex* fFirstVertex;
490 int fWinding;
491 MonotonePoly* fHead;
492 MonotonePoly* fTail;
493 Poly* fNext;
494 Poly* fPartner;
495 int fCount;
496#if TRIANGULATOR_LOGGING
497 int fID;
498#endif
499};
500
501struct GrTriangulator::Comparator {
502 enum class Direction { kVertical, kHorizontal };
503 Comparator(Direction direction) : fDirection(direction) {}
504 bool sweep_lt(const SkPoint& a, const SkPoint& b) const;
505 Direction fDirection;
506};
507
ethannicholase9709e82016-01-07 13:34:16 -0800508#endif