blob: 1cc31e2000dbfd76fe2c2ced9229a30d55f815af [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 Dalton330cfa42021-01-27 18:24:48 -070034 Poly* polys = triangulator.pathToPolys(tolerance, clipBounds, nullptr, isLinear);
35 int count = triangulator.polysToTriangles(polys, vertexAllocator, nullptr);
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
Chris Dalton330cfa42021-01-27 18:24:48 -070072 // The breadcrumb triangles serve as a glue that erases T-junctions between a path's outer
73 // curves and its inner polygon triangulation. Drawing a path's outer curves, breadcrumb
74 // triangles, and inner polygon triangulation all together into the stencil buffer has the same
75 // identical rasterized effect as stenciling a classic Redbook fan.
76 //
77 // The breadcrumb triangles track all the edge splits that led from the original inner polygon
78 // edges to the final triangulation. Every time an edge splits, we emit a razor-thin breadcrumb
79 // triangle consisting of the edge's original endpoints and the split point. (We also add
80 // supplemental breadcrumb triangles to areas where abs(winding) > 1.)
81 //
82 // a
83 // /
84 // /
85 // /
86 // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x].
87 // /
88 // /
89 // b
90 //
91 // The opposite-direction shared edges between the triangulation and breadcrumb triangles should
92 // all cancel out, leaving just the set of edges from the original polygon.
93 class BreadcrumbTriangleList {
94 public:
95 void prepend(SkArenaAlloc* alloc, SkPoint a, SkPoint b, SkPoint c, int winding) {
96 if (a == b || a == c || b == c || winding == 0) {
97 return;
98 }
99 if (winding < 0) {
100 std::swap(a, b);
101 winding = -winding;
102 }
103 for (int i = 0; i < winding; ++i) {
104 fHead = alloc->make<Node>(a, b, c, fHead);
105 }
106 fCount += winding;
107 }
108
109 struct Node {
110 Node(SkPoint a, SkPoint b, SkPoint c, const Node* next) : fPts{a, b, c}, fNext(next) {}
111 SkPoint fPts[3];
112 const Node* fNext;
113 };
114 const Node* head() const { return fHead; }
115 int count() const { return fCount; }
116
117 private:
118 const Node* fHead = nullptr;
119 int fCount = 0;
120 };
121
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700122 // There are six stages to the basic algorithm:
123 //
124 // 1) Linearize the path contours into piecewise linear segments:
Chris Dalton37d16f12021-01-20 18:32:48 -0700125 void pathToContours(float tolerance, const SkRect& clipBounds, VertexList* contours,
Chris Dalton330cfa42021-01-27 18:24:48 -0700126 bool* isLinear) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700127
128 // 2) Build a mesh of edges connecting the vertices:
Chris Dalton330cfa42021-01-27 18:24:48 -0700129 void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&,
130 BreadcrumbTriangleList*) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700131
Chris Dalton68b8bd52021-01-14 10:48:02 -0700132 // 3) Sort the vertices in Y (and secondarily in X):
Chris Dalton47114db2021-01-06 00:35:20 -0700133 static void SortedMerge(VertexList* front, VertexList* back, VertexList* result,
134 const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700135 static void SortMesh(VertexList* vertices, const Comparator&);
136
137 // 4) Simplify the mesh by inserting new vertices at intersecting edges:
Chris Daltonebb37e72021-01-27 17:59:45 -0700138 enum class SimplifyResult : bool {
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700139 kAlreadySimple,
Chris Daltonebb37e72021-01-27 17:59:45 -0700140 kFoundSelfIntersection
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700141 };
142
Chris Dalton330cfa42021-01-27 18:24:48 -0700143 SimplifyResult simplify(VertexList* mesh, const Comparator&, BreadcrumbTriangleList*) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700144
145 // 5) Tessellate the simplified mesh into monotone polygons:
Chris Dalton330cfa42021-01-27 18:24:48 -0700146 virtual Poly* tessellate(const VertexList& vertices, const Comparator&) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700147
148 // 6) Triangulate the monotone polygons directly into a vertex buffer:
Chris Dalton330cfa42021-01-27 18:24:48 -0700149 void* polysToTriangles(Poly* polys, void* data, BreadcrumbTriangleList*,
150 SkPathFillType overrideFillType) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700151
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700152 // The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
153 // of vertices (and the necessity of inserting new vertices on intersection).
154 //
155 // Stages (4) and (5) use an active edge list -- a list of all edges for which the
156 // sweep line has crossed the top vertex, but not the bottom vertex. It's sorted
157 // left-to-right based on the point where both edges are active (when both top vertices
158 // have been seen, so the "lower" top vertex of the two). If the top vertices are equal
159 // (shared), it's sorted based on the last point where both edges are active, so the
160 // "upper" bottom vertex.
161 //
162 // The most complex step is the simplification (4). It's based on the Bentley-Ottman
163 // line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
164 // not exact and may violate the mesh topology or active edge list ordering. We
165 // accommodate this by adjusting the topology of the mesh and AEL to match the intersection
166 // points. This occurs in two ways:
167 //
168 // A) Intersections may cause a shortened edge to no longer be ordered with respect to its
169 // neighbouring edges at the top or bottom vertex. This is handled by merging the
Chris Dalton68b8bd52021-01-14 10:48:02 -0700170 // edges (mergeCollinearVertices()).
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700171 // B) Intersections may cause an edge to violate the left-to-right ordering of the
172 // active edge list. This is handled by detecting potential violations and rewinding
173 // the active edge list to the vertex before they occur (rewind() during merging,
174 // rewind_if_necessary() during splitting).
175 //
176 // The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
177 // Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
178 // currently uses a linked list for the active edge list, rather than a 2-3 tree as the
179 // paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
180 // become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
181 // insertions and removals was greater than the cost of infrequent O(N) lookups with the
182 // linked list implementation. With the latter, all removals are O(1), and most insertions
183 // are O(1), since we know the adjacent edge in the active edge list based on the topology.
184 // Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
185 // frequent. There may be other data structures worth investigating, however.
186 //
187 // Note that the orientation of the line sweep algorithms is determined by the aspect ratio of
188 // the path bounds. When the path is taller than it is wide, we sort vertices based on
189 // increasing Y coordinate, and secondarily by increasing X coordinate. When the path is wider
190 // than it is tall, we sort by increasing X coordinate, but secondarily by *decreasing* Y
191 // coordinate. This is so that the "left" and "right" orientation in the code remains correct
192 // (edges to the left are increasing in Y; edges to the right are decreasing in Y). That is, the
193 // setting rotates 90 degrees counterclockwise, rather that transposing.
194
195 // Additional helpers and driver functions.
Chris Dalton330cfa42021-01-27 18:24:48 -0700196 void* emitMonotonePoly(const MonotonePoly*, void* data, BreadcrumbTriangleList*) const;
197 void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, int winding, void* data,
198 BreadcrumbTriangleList*) const;
199 void* emitPoly(const Poly*, void *data, BreadcrumbTriangleList*) const;
200 Poly* makePoly(Poly** head, Vertex* v, int winding) const;
201 void appendPointToContour(const SkPoint& p, VertexList* contour) const;
202 void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd,
203 VertexList* contour) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700204 void generateCubicPoints(const SkPoint&, const SkPoint&, const SkPoint&, const SkPoint&,
Chris Dalton330cfa42021-01-27 18:24:48 -0700205 SkScalar tolSqd, VertexList* contour, int pointsLeft) const;
206 bool applyFillType(int winding) const;
207 Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&) const;
208 void setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator&,
209 BreadcrumbTriangleList*) const;
Chris Dalton68b8bd52021-01-14 10:48:02 -0700210 void setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
Chris Dalton330cfa42021-01-27 18:24:48 -0700211 const Comparator&, BreadcrumbTriangleList*) const;
Chris Dalton68b8bd52021-01-14 10:48:02 -0700212 void mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
Chris Dalton330cfa42021-01-27 18:24:48 -0700213 const Comparator&, BreadcrumbTriangleList*) const;
Chris Dalton68b8bd52021-01-14 10:48:02 -0700214 void mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
Chris Dalton330cfa42021-01-27 18:24:48 -0700215 const Comparator&, BreadcrumbTriangleList*) const;
Chris Dalton7cf3add2021-01-11 18:33:28 -0700216 Edge* makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType, const Comparator&,
Chris Dalton330cfa42021-01-27 18:24:48 -0700217 BreadcrumbTriangleList*, int windingScale = 1) const;
218 void mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh, const Comparator&,
219 BreadcrumbTriangleList*) const;
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,
Chris Dalton330cfa42021-01-27 18:24:48 -0700222 const Comparator&, BreadcrumbTriangleList*) const;
Chris Dalton811dc6a2021-01-07 16:40:32 -0700223 bool splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
Chris Dalton330cfa42021-01-27 18:24:48 -0700224 const Comparator&, BreadcrumbTriangleList*) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700225 bool intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton330cfa42021-01-27 18:24:48 -0700226 const Comparator&, BreadcrumbTriangleList*) const;
Chris Dalton7cf3add2021-01-11 18:33:28 -0700227 Vertex* makeSortedVertex(const SkPoint&, uint8_t alpha, VertexList* mesh, Vertex* reference,
Chris Dalton330cfa42021-01-27 18:24:48 -0700228 const Comparator&) const;
229 void computeBisector(Edge* edge1, Edge* edge2, Vertex*) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700230 bool checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton330cfa42021-01-27 18:24:48 -0700231 VertexList* mesh, const Comparator&, BreadcrumbTriangleList*) const;
232 void sanitizeContours(VertexList* contours, int contourCnt) const;
233 bool mergeCoincidentVertices(VertexList* mesh, const Comparator&,
234 BreadcrumbTriangleList*) const;
235 void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&,
236 BreadcrumbTriangleList*) const;
237 Poly* contoursToPolys(VertexList* contours, int contourCnt, BreadcrumbTriangleList*) const;
238 Poly* pathToPolys(float tolerance, const SkRect& clipBounds, BreadcrumbTriangleList*,
239 bool* isLinear) const;
Chris Daltond5384792021-01-20 15:43:24 -0700240 static int64_t CountPoints(Poly* polys, SkPathFillType overrideFillType);
Chris Dalton330cfa42021-01-27 18:24:48 -0700241 int polysToTriangles(Poly*, GrEagerVertexAllocator*, BreadcrumbTriangleList*) const;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700242
Chris Dalton330cfa42021-01-27 18:24:48 -0700243 // FIXME: fPath should be plumbed through function parameters instead.
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700244 const SkPath fPath;
Chris Dalton8a42b092021-01-21 22:09:26 -0700245 SkArenaAlloc* const fAlloc;
Chris Dalton854ee852021-01-05 15:12:59 -0700246
Chris Dalton68b8bd52021-01-14 10:48:02 -0700247 // Internal control knobs.
Chris Dalton854ee852021-01-05 15:12:59 -0700248 bool fRoundVerticesToQuarterPixel = false;
249 bool fEmitCoverage = false;
250 bool fCullCollinearVertices = true;
Chris Daltondcc8c542020-01-28 17:55:56 -0700251};
252
Chris Dalton5045de32021-01-07 19:09:01 -0700253/**
254 * Vertices are used in three ways: first, the path contours are converted into a
255 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
256 * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
257 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
258 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
259 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
260 * an individual Vertex from the path mesh may belong to multiple
261 * MonotonePolys, so the original Vertices cannot be re-used.
262 */
263
264struct GrTriangulator::Vertex {
265 Vertex(const SkPoint& point, uint8_t alpha)
266 : fPoint(point), fPrev(nullptr), fNext(nullptr)
267 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
268 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
269 , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
270 , fPartner(nullptr)
271 , fAlpha(alpha)
272 , fSynthetic(false)
273#if TRIANGULATOR_LOGGING
274 , fID (-1.0f)
275#endif
276 {}
277 SkPoint fPoint; // Vertex position
278 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
279 Vertex* fNext; // "
280 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
281 Edge* fLastEdgeAbove; // "
282 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
283 Edge* fLastEdgeBelow; // "
284 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
285 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
286 Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
287 uint8_t fAlpha;
288 bool fSynthetic; // Is this a synthetic vertex?
289#if TRIANGULATOR_LOGGING
290 float fID; // Identifier used for logging.
291#endif
Chris Dalton24472af2021-01-11 20:05:00 -0700292 bool isConnected() const { return this->fFirstEdgeAbove || this->fFirstEdgeBelow; }
Chris Dalton5045de32021-01-07 19:09:01 -0700293};
294
295struct GrTriangulator::VertexList {
296 VertexList() : fHead(nullptr), fTail(nullptr) {}
297 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {}
298 Vertex* fHead;
299 Vertex* fTail;
300 void insert(Vertex* v, Vertex* prev, Vertex* next);
301 void append(Vertex* v) { insert(v, fTail, nullptr); }
302 void append(const VertexList& list) {
303 if (!list.fHead) {
304 return;
305 }
306 if (fTail) {
307 fTail->fNext = list.fHead;
308 list.fHead->fPrev = fTail;
309 } else {
310 fHead = list.fHead;
311 }
312 fTail = list.fTail;
313 }
314 void prepend(Vertex* v) { insert(v, nullptr, fHead); }
315 void remove(Vertex* v);
316 void close() {
317 if (fHead && fTail) {
318 fTail->fNext = fHead;
319 fHead->fPrev = fTail;
320 }
321 }
Chris Dalton24472af2021-01-11 20:05:00 -0700322#if TRIANGULATOR_LOGGING
Chris Dalton330cfa42021-01-27 18:24:48 -0700323 void dump() const;
Chris Dalton24472af2021-01-11 20:05:00 -0700324#endif
Chris Dalton5045de32021-01-07 19:09:01 -0700325};
326
327// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
328struct GrTriangulator::Line {
329 Line(double a, double b, double c) : fA(a), fB(b), fC(c) {}
330 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
331 Line(const SkPoint& p, const SkPoint& q)
332 : fA(static_cast<double>(q.fY) - p.fY) // a = dY
333 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX
334 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p)
335 static_cast<double>(p.fX) * q.fY) {}
336 double dist(const SkPoint& p) const { return fA * p.fX + fB * p.fY + fC; }
337 Line operator*(double v) const { return Line(fA * v, fB * v, fC * v); }
338 double magSq() const { return fA * fA + fB * fB; }
339 void normalize() {
340 double len = sqrt(this->magSq());
341 if (len == 0.0) {
342 return;
343 }
344 double scale = 1.0f / len;
345 fA *= scale;
346 fB *= scale;
347 fC *= scale;
348 }
349 bool nearParallel(const Line& o) const {
350 return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001;
351 }
352
353 // Compute the intersection of two (infinite) Lines.
354 bool intersect(const Line& other, SkPoint* point) const;
355 double fA, fB, fC;
356};
357
358/**
359 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
360 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
361 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
362 * point). For speed, that case is only tested by the callers that require it (e.g.,
363 * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
364 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
365 * until an intersection has been confirmed. This is slightly slower in the "found" case, but
366 * a lot faster in the "not found" case.
367 *
368 * The coefficients of the line equation stored in double precision to avoid catastrophic
369 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
370 * correct in float, since it's a polynomial of degree 2. The intersect() function, being
371 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
372 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
373 * this file).
374 */
375
376struct GrTriangulator::Edge {
377 Edge(Vertex* top, Vertex* bottom, int winding, EdgeType type)
378 : fWinding(winding)
379 , fTop(top)
380 , fBottom(bottom)
381 , fType(type)
382 , fLeft(nullptr)
383 , fRight(nullptr)
384 , fPrevEdgeAbove(nullptr)
385 , fNextEdgeAbove(nullptr)
386 , fPrevEdgeBelow(nullptr)
387 , fNextEdgeBelow(nullptr)
388 , fLeftPoly(nullptr)
389 , fRightPoly(nullptr)
390 , fLeftPolyPrev(nullptr)
391 , fLeftPolyNext(nullptr)
392 , fRightPolyPrev(nullptr)
393 , fRightPolyNext(nullptr)
394 , fUsedInLeftPoly(false)
395 , fUsedInRightPoly(false)
396 , fLine(top, bottom) {
397 }
398 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
399 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt).
400 Vertex* fBottom; // The bottom vertex in vertex-sort-order.
401 EdgeType fType;
402 Edge* fLeft; // The linked list of edges in the active edge list.
403 Edge* fRight; // "
404 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
405 Edge* fNextEdgeAbove; // "
406 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
407 Edge* fNextEdgeBelow; // "
408 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
409 Poly* fRightPoly; // The Poly to the right of this edge, if any.
410 Edge* fLeftPolyPrev;
411 Edge* fLeftPolyNext;
412 Edge* fRightPolyPrev;
413 Edge* fRightPolyNext;
414 bool fUsedInLeftPoly;
415 bool fUsedInRightPoly;
416 Line fLine;
417 double dist(const SkPoint& p) const { return fLine.dist(p); }
418 bool isRightOf(Vertex* v) const { return fLine.dist(v->fPoint) < 0.0; }
419 bool isLeftOf(Vertex* v) const { return fLine.dist(v->fPoint) > 0.0; }
420 void recompute() { fLine = Line(fTop, fBottom); }
Chris Dalton24472af2021-01-11 20:05:00 -0700421 void insertAbove(Vertex*, const Comparator&);
422 void insertBelow(Vertex*, const Comparator&);
423 void disconnect();
Chris Dalton5045de32021-01-07 19:09:01 -0700424 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const;
425};
426
427struct GrTriangulator::EdgeList {
428 EdgeList() : fHead(nullptr), fTail(nullptr) {}
429 Edge* fHead;
430 Edge* fTail;
431 void insert(Edge* edge, Edge* prev, Edge* next);
Chris Dalton24472af2021-01-11 20:05:00 -0700432 void insert(Edge* edge, Edge* prev);
Chris Dalton5045de32021-01-07 19:09:01 -0700433 void append(Edge* e) { insert(e, fTail, nullptr); }
434 void remove(Edge* edge);
435 void removeAll() {
436 while (fHead) {
437 this->remove(fHead);
438 }
439 }
440 void close() {
441 if (fHead && fTail) {
442 fTail->fRight = fHead;
443 fHead->fLeft = fTail;
444 }
445 }
446 bool contains(Edge* edge) const { return edge->fLeft || edge->fRight || fHead == edge; }
447};
448
449struct GrTriangulator::MonotonePoly {
450 MonotonePoly(Edge* edge, Side side, int winding)
451 : fSide(side)
452 , fFirstEdge(nullptr)
453 , fLastEdge(nullptr)
454 , fPrev(nullptr)
455 , fNext(nullptr)
456 , fWinding(winding) {
457 this->addEdge(edge);
458 }
459 Side fSide;
460 Edge* fFirstEdge;
461 Edge* fLastEdge;
462 MonotonePoly* fPrev;
463 MonotonePoly* fNext;
464 int fWinding;
465 void addEdge(Edge*);
Chris Dalton5045de32021-01-07 19:09:01 -0700466};
467
468struct GrTriangulator::Poly {
469 Poly(Vertex* v, int winding)
470 : fFirstVertex(v)
471 , fWinding(winding)
472 , fHead(nullptr)
473 , fTail(nullptr)
474 , fNext(nullptr)
475 , fPartner(nullptr)
476 , fCount(0)
477 {
478#if TRIANGULATOR_LOGGING
479 static int gID = 0;
480 fID = gID++;
481 TESS_LOG("*** created Poly %d\n", fID);
482#endif
483 }
Chris Dalton8a42b092021-01-21 22:09:26 -0700484 Poly* addEdge(Edge* e, Side side, SkArenaAlloc* alloc);
Chris Dalton5045de32021-01-07 19:09:01 -0700485 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
486 Vertex* fFirstVertex;
487 int fWinding;
488 MonotonePoly* fHead;
489 MonotonePoly* fTail;
490 Poly* fNext;
491 Poly* fPartner;
492 int fCount;
493#if TRIANGULATOR_LOGGING
494 int fID;
495#endif
496};
497
498struct GrTriangulator::Comparator {
499 enum class Direction { kVertical, kHorizontal };
500 Comparator(Direction direction) : fDirection(direction) {}
501 bool sweep_lt(const SkPoint& a, const SkPoint& b) const;
502 Direction fDirection;
503};
504
ethannicholase9709e82016-01-07 13:34:16 -0800505#endif