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#ifndef GrTriangulator_DEFINED
9#define GrTriangulator_DEFINED
10
11#if !defined(SK_ENABLE_OPTIMIZE_SIZE)
12
13#include "include/core/SkPath.h"
14#include "include/core/SkPoint.h"
15#include "include/private/SkColorData.h"
16#include "src/base/SkArenaAlloc.h"
17#include "src/gpu/ganesh/GrColor.h"
18
19class GrEagerVertexAllocator;
20struct SkRect;
21
22#define TRIANGULATOR_LOGGING 0
23#define TRIANGULATOR_WIREFRAME 0
24
25/**
26 * Provides utility functions for converting paths to a collection of triangles.
27 */
28class GrTriangulator {
29public:
30 constexpr static int kArenaDefaultChunkSize = 16 * 1024;
31
32 static int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
33 GrEagerVertexAllocator* vertexAllocator, bool* isLinear) {
34 if (!path.isFinite()) {
35 return 0;
36 }
37 SkArenaAlloc alloc(kArenaDefaultChunkSize);
38 GrTriangulator triangulator(path, &alloc);
39 auto [ polys, success ] = triangulator.pathToPolys(tolerance, clipBounds, isLinear);
40 if (!success) {
41 return 0;
42 }
43 int count = triangulator.polysToTriangles(polys, vertexAllocator);
44 return count;
45 }
46
47 // Enums used by GrTriangulator internals.
48 typedef enum { kLeft_Side, kRight_Side } Side;
49 enum class EdgeType { kInner, kOuter, kConnector };
50
51 // Structs used by GrTriangulator internals.
52 struct Vertex;
53 struct VertexList;
54 struct Line;
55 struct Edge;
56 struct EdgeList;
57 struct MonotonePoly;
58 struct Poly;
59 struct Comparator;
60
61protected:
62 GrTriangulator(const SkPath& path, SkArenaAlloc* alloc) : fPath(path), fAlloc(alloc) {}
63 virtual ~GrTriangulator() {}
64
65 // There are six stages to the basic algorithm:
66 //
67 // 1) Linearize the path contours into piecewise linear segments:
68 void pathToContours(float tolerance, const SkRect& clipBounds, VertexList* contours,
69 bool* isLinear) const;
70
71 // 2) Build a mesh of edges connecting the vertices:
72 void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh,
73 const Comparator&);
74
75 // 3) Sort the vertices in Y (and secondarily in X):
76 static void SortedMerge(VertexList* front, VertexList* back, VertexList* result,
77 const Comparator&);
78 static void SortMesh(VertexList* vertices, const Comparator&);
79
80 // 4) Simplify the mesh by inserting new vertices at intersecting edges:
81 enum class SimplifyResult {
82 kFailed,
83 kAlreadySimple,
84 kFoundSelfIntersection
85 };
86
87 enum class BoolFail {
88 kFalse,
89 kTrue,
90 kFail
91 };
92
93 [[nodiscard]] SimplifyResult simplify(VertexList* mesh, const Comparator&);
94
95 // 5) Tessellate the simplified mesh into monotone polygons:
96 virtual std::tuple<Poly*, bool> tessellate(const VertexList& vertices, const Comparator&);
97
98 // 6) Triangulate the monotone polygons directly into a vertex buffer:
99 skgpu::VertexWriter polysToTriangles(Poly* polys,
100 SkPathFillType overrideFillType,
101 skgpu::VertexWriter data) const;
102
103 // The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
104 // of vertices (and the necessity of inserting new vertices on intersection).
105 //
106 // Stages (4) and (5) use an active edge list -- a list of all edges for which the
107 // sweep line has crossed the top vertex, but not the bottom vertex. It's sorted
108 // left-to-right based on the point where both edges are active (when both top vertices
109 // have been seen, so the "lower" top vertex of the two). If the top vertices are equal
110 // (shared), it's sorted based on the last point where both edges are active, so the
111 // "upper" bottom vertex.
112 //
113 // The most complex step is the simplification (4). It's based on the Bentley-Ottman
114 // line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
115 // not exact and may violate the mesh topology or active edge list ordering. We
116 // accommodate this by adjusting the topology of the mesh and AEL to match the intersection
117 // points. This occurs in two ways:
118 //
119 // A) Intersections may cause a shortened edge to no longer be ordered with respect to its
120 // neighbouring edges at the top or bottom vertex. This is handled by merging the
121 // edges (mergeCollinearVertices()).
122 // B) Intersections may cause an edge to violate the left-to-right ordering of the
123 // active edge list. This is handled by detecting potential violations and rewinding
124 // the active edge list to the vertex before they occur (rewind() during merging,
125 // rewind_if_necessary() during splitting).
126 //
127 // The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
128 // Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
129 // currently uses a linked list for the active edge list, rather than a 2-3 tree as the
130 // paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
131 // become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
132 // insertions and removals was greater than the cost of infrequent O(N) lookups with the
133 // linked list implementation. With the latter, all removals are O(1), and most insertions
134 // are O(1), since we know the adjacent edge in the active edge list based on the topology.
135 // Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
136 // frequent. There may be other data structures worth investigating, however.
137 //
138 // Note that the orientation of the line sweep algorithms is determined by the aspect ratio of
139 // the path bounds. When the path is taller than it is wide, we sort vertices based on
140 // increasing Y coordinate, and secondarily by increasing X coordinate. When the path is wider
141 // than it is tall, we sort by increasing X coordinate, but secondarily by *decreasing* Y
142 // coordinate. This is so that the "left" and "right" orientation in the code remains correct
143 // (edges to the left are increasing in Y; edges to the right are decreasing in Y). That is, the
144 // setting rotates 90 degrees counterclockwise, rather that transposing.
145
146 // Additional helpers and driver functions.
147 skgpu::VertexWriter emitMonotonePoly(const MonotonePoly*, skgpu::VertexWriter data) const;
148 skgpu::VertexWriter emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, int winding,
149 skgpu::VertexWriter data) const;
150 skgpu::VertexWriter emitPoly(const Poly*, skgpu::VertexWriter data) const;
151
152 Poly* makePoly(Poly** head, Vertex* v, int winding) const;
153 void appendPointToContour(const SkPoint& p, VertexList* contour) const;
154 void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd,
155 VertexList* contour) const;
156 void generateCubicPoints(const SkPoint&, const SkPoint&, const SkPoint&, const SkPoint&,
157 SkScalar tolSqd, VertexList* contour, int pointsLeft) const;
158 bool applyFillType(int winding) const;
159 MonotonePoly* allocateMonotonePoly(Edge* edge, Side side, int winding);
160 Edge* allocateEdge(Vertex* top, Vertex* bottom, int winding, EdgeType type);
161 Edge* makeEdge(Vertex* prev, Vertex* next, EdgeType type, const Comparator&);
162 [[nodiscard]] bool setTop(
163 Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator&) const;
164 [[nodiscard]] bool setBottom(
165 Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator&) const;
166 [[nodiscard]] bool mergeEdgesAbove(
167 Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, const Comparator&) const;
168 [[nodiscard]] bool mergeEdgesBelow(
169 Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current, const Comparator&) const;
170 Edge* makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType, const Comparator&,
171 int windingScale = 1);
172 void mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh, const Comparator&) const;
173 static void FindEnclosingEdges(const Vertex& v, const EdgeList& edges,
174 Edge** left, Edge** right);
175 bool mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
176 const Comparator&) const;
177 BoolFail splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
178 const Comparator&);
179 BoolFail intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
180 const Comparator&);
181 Vertex* makeSortedVertex(const SkPoint&, uint8_t alpha, VertexList* mesh, Vertex* reference,
182 const Comparator&) const;
183 void computeBisector(Edge* edge1, Edge* edge2, Vertex*) const;
184 BoolFail checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
185 VertexList* mesh, const Comparator&);
186 void sanitizeContours(VertexList* contours, int contourCnt) const;
187 bool mergeCoincidentVertices(VertexList* mesh, const Comparator&) const;
188 void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh,
189 const Comparator&);
190 std::tuple<Poly*, bool> contoursToPolys(VertexList* contours, int contourCnt);
191 std::tuple<Poly*, bool> pathToPolys(float tolerance, const SkRect& clipBounds,
192 bool* isLinear);
193 static int64_t CountPoints(Poly* polys, SkPathFillType overrideFillType);
194 int polysToTriangles(Poly*, GrEagerVertexAllocator*) const;
195
196 // FIXME: fPath should be plumbed through function parameters instead.
197 const SkPath fPath;
198 SkArenaAlloc* const fAlloc;
199 int fNumMonotonePolys = 0;
200 int fNumEdges = 0;
201
202 // Internal control knobs.
203 bool fRoundVerticesToQuarterPixel = false;
204 bool fEmitCoverage = false;
205 bool fPreserveCollinearVertices = false;
206 bool fCollectBreadcrumbTriangles = false;
207
208 // The breadcrumb triangles serve as a glue that erases T-junctions between a path's outer
209 // curves and its inner polygon triangulation. Drawing a path's outer curves, breadcrumb
210 // triangles, and inner polygon triangulation all together into the stencil buffer has the same
211 // identical rasterized effect as stenciling a classic Redbook fan.
212 //
213 // The breadcrumb triangles track all the edge splits that led from the original inner polygon
214 // edges to the final triangulation. Every time an edge splits, we emit a razor-thin breadcrumb
215 // triangle consisting of the edge's original endpoints and the split point. (We also add
216 // supplemental breadcrumb triangles to areas where abs(winding) > 1.)
217 //
218 // a
219 // /
220 // /
221 // /
222 // x <- Edge splits at x. New breadcrumb triangle is: [a, b, x].
223 // /
224 // /
225 // b
226 //
227 // The opposite-direction shared edges between the triangulation and breadcrumb triangles should
228 // all cancel out, leaving just the set of edges from the original polygon.
229 class BreadcrumbTriangleList {
230 public:
231 struct Node {
232 Node(SkPoint a, SkPoint b, SkPoint c) : fPts{a, b, c} {}
233 SkPoint fPts[3];
234 Node* fNext = nullptr;
235 };
236 const Node* head() const { return fHead; }
237 int count() const { return fCount; }
238
239 void append(SkArenaAlloc* alloc, SkPoint a, SkPoint b, SkPoint c, int winding) {
240 if (a == b || a == c || b == c || winding == 0) {
241 return;
242 }
243 if (winding < 0) {
244 std::swap(x&: a, y&: b);
245 winding = -winding;
246 }
247 for (int i = 0; i < winding; ++i) {
248 SkASSERT(fTail && !(*fTail));
249 *fTail = alloc->make<Node>(args&: a, args&: b, args&: c);
250 fTail = &(*fTail)->fNext;
251 }
252 fCount += winding;
253 }
254
255 void concat(BreadcrumbTriangleList&& list) {
256 SkASSERT(fTail && !(*fTail));
257 if (list.fHead) {
258 *fTail = list.fHead;
259 fTail = list.fTail;
260 fCount += list.fCount;
261 list.fHead = nullptr;
262 list.fTail = &list.fHead;
263 list.fCount = 0;
264 }
265 }
266
267 private:
268 Node* fHead = nullptr;
269 Node** fTail = &fHead;
270 int fCount = 0;
271 };
272
273 mutable BreadcrumbTriangleList fBreadcrumbList;
274};
275
276/**
277 * Vertices are used in three ways: first, the path contours are converted into a
278 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
279 * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
280 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
281 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
282 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
283 * an individual Vertex from the path mesh may belong to multiple
284 * MonotonePolys, so the original Vertices cannot be re-used.
285 */
286
287struct GrTriangulator::Vertex {
288 Vertex(const SkPoint& point, uint8_t alpha)
289 : fPoint(point), fPrev(nullptr), fNext(nullptr)
290 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
291 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
292 , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
293 , fPartner(nullptr)
294 , fAlpha(alpha)
295 , fSynthetic(false)
296#if TRIANGULATOR_LOGGING
297 , fID (-1.0f)
298#endif
299 {}
300 SkPoint fPoint; // Vertex position
301 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
302 Vertex* fNext; // "
303 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
304 Edge* fLastEdgeAbove; // "
305 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
306 Edge* fLastEdgeBelow; // "
307 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
308 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
309 Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
310 uint8_t fAlpha;
311 bool fSynthetic; // Is this a synthetic vertex?
312#if TRIANGULATOR_LOGGING
313 float fID; // Identifier used for logging.
314#endif
315 bool isConnected() const { return this->fFirstEdgeAbove || this->fFirstEdgeBelow; }
316};
317
318struct GrTriangulator::VertexList {
319 VertexList() : fHead(nullptr), fTail(nullptr) {}
320 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {}
321 Vertex* fHead;
322 Vertex* fTail;
323 void insert(Vertex* v, Vertex* prev, Vertex* next);
324 void append(Vertex* v) { insert(v, prev: fTail, next: nullptr); }
325 void append(const VertexList& list) {
326 if (!list.fHead) {
327 return;
328 }
329 if (fTail) {
330 fTail->fNext = list.fHead;
331 list.fHead->fPrev = fTail;
332 } else {
333 fHead = list.fHead;
334 }
335 fTail = list.fTail;
336 }
337 void prepend(Vertex* v) { insert(v, prev: nullptr, next: fHead); }
338 void remove(Vertex* v);
339 void close() {
340 if (fHead && fTail) {
341 fTail->fNext = fHead;
342 fHead->fPrev = fTail;
343 }
344 }
345#if TRIANGULATOR_LOGGING
346 void dump() const;
347#endif
348};
349
350// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
351struct GrTriangulator::Line {
352 Line(double a, double b, double c) : fA(a), fB(b), fC(c) {}
353 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
354 Line(const SkPoint& p, const SkPoint& q)
355 : fA(static_cast<double>(q.fY) - p.fY) // a = dY
356 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX
357 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p)
358 static_cast<double>(p.fX) * q.fY) {}
359 double dist(const SkPoint& p) const { return fA * p.fX + fB * p.fY + fC; }
360 Line operator*(double v) const { return Line(fA * v, fB * v, fC * v); }
361 double magSq() const { return fA * fA + fB * fB; }
362 void normalize() {
363 double len = sqrt(x: this->magSq());
364 if (len == 0.0) {
365 return;
366 }
367 double scale = 1.0f / len;
368 fA *= scale;
369 fB *= scale;
370 fC *= scale;
371 }
372 bool nearParallel(const Line& o) const {
373 return fabs(x: o.fA - fA) < 0.00001 && fabs(x: o.fB - fB) < 0.00001;
374 }
375
376 // Compute the intersection of two (infinite) Lines.
377 bool intersect(const Line& other, SkPoint* point) const;
378 double fA, fB, fC;
379};
380
381/**
382 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
383 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
384 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
385 * point). For speed, that case is only tested by the callers that require it (e.g.,
386 * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
387 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
388 * until an intersection has been confirmed. This is slightly slower in the "found" case, but
389 * a lot faster in the "not found" case.
390 *
391 * The coefficients of the line equation stored in double precision to avoid catastrophic
392 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
393 * correct in float, since it's a polynomial of degree 2. The intersect() function, being
394 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
395 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
396 * this file).
397 */
398
399struct GrTriangulator::Edge {
400 Edge(Vertex* top, Vertex* bottom, int winding, EdgeType type)
401 : fWinding(winding)
402 , fTop(top)
403 , fBottom(bottom)
404 , fType(type)
405 , fLeft(nullptr)
406 , fRight(nullptr)
407 , fPrevEdgeAbove(nullptr)
408 , fNextEdgeAbove(nullptr)
409 , fPrevEdgeBelow(nullptr)
410 , fNextEdgeBelow(nullptr)
411 , fLeftPoly(nullptr)
412 , fRightPoly(nullptr)
413 , fLeftPolyPrev(nullptr)
414 , fLeftPolyNext(nullptr)
415 , fRightPolyPrev(nullptr)
416 , fRightPolyNext(nullptr)
417 , fUsedInLeftPoly(false)
418 , fUsedInRightPoly(false)
419 , fLine(top, bottom) {
420 }
421 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
422 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt).
423 Vertex* fBottom; // The bottom vertex in vertex-sort-order.
424 EdgeType fType;
425 Edge* fLeft; // The linked list of edges in the active edge list.
426 Edge* fRight; // "
427 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
428 Edge* fNextEdgeAbove; // "
429 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
430 Edge* fNextEdgeBelow; // "
431 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
432 Poly* fRightPoly; // The Poly to the right of this edge, if any.
433 Edge* fLeftPolyPrev;
434 Edge* fLeftPolyNext;
435 Edge* fRightPolyPrev;
436 Edge* fRightPolyNext;
437 bool fUsedInLeftPoly;
438 bool fUsedInRightPoly;
439 Line fLine;
440
441 double dist(const SkPoint& p) const {
442 // Coerce points coincident with the vertices to have dist = 0, since converting from
443 // a double intersection point back to float storage might construct a point that's no
444 // longer on the ideal line.
445 return (p == fTop->fPoint || p == fBottom->fPoint) ? 0.0 : fLine.dist(p);
446 }
447 bool isRightOf(const Vertex& v) const { return this->dist(p: v.fPoint) < 0.0; }
448 bool isLeftOf(const Vertex& v) const { return this->dist(p: v.fPoint) > 0.0; }
449 void recompute() { fLine = Line(fTop, fBottom); }
450 void insertAbove(Vertex*, const Comparator&);
451 void insertBelow(Vertex*, const Comparator&);
452 void disconnect();
453 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const;
454};
455
456struct GrTriangulator::EdgeList {
457 EdgeList() : fHead(nullptr), fTail(nullptr) {}
458 Edge* fHead;
459 Edge* fTail;
460 void insert(Edge* edge, Edge* prev, Edge* next);
461 bool insert(Edge* edge, Edge* prev);
462 void append(Edge* e) { insert(edge: e, prev: fTail, next: nullptr); }
463 bool remove(Edge* edge);
464 void removeAll() {
465 while (fHead) {
466 this->remove(edge: fHead);
467 }
468 }
469 void close() {
470 if (fHead && fTail) {
471 fTail->fRight = fHead;
472 fHead->fLeft = fTail;
473 }
474 }
475 bool contains(Edge* edge) const { return edge->fLeft || edge->fRight || fHead == edge; }
476};
477
478struct GrTriangulator::MonotonePoly {
479 MonotonePoly(Edge* edge, Side side, int winding)
480 : fSide(side)
481 , fFirstEdge(nullptr)
482 , fLastEdge(nullptr)
483 , fPrev(nullptr)
484 , fNext(nullptr)
485 , fWinding(winding) {
486 this->addEdge(edge);
487 }
488 Side fSide;
489 Edge* fFirstEdge;
490 Edge* fLastEdge;
491 MonotonePoly* fPrev;
492 MonotonePoly* fNext;
493 int fWinding;
494 void addEdge(Edge*);
495};
496
497struct GrTriangulator::Poly {
498 Poly(Vertex* v, int winding);
499
500 Poly* addEdge(Edge* e, Side side, GrTriangulator*);
501 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
502 Vertex* fFirstVertex;
503 int fWinding;
504 MonotonePoly* fHead;
505 MonotonePoly* fTail;
506 Poly* fNext;
507 Poly* fPartner;
508 int fCount;
509#if TRIANGULATOR_LOGGING
510 int fID;
511#endif
512};
513
514struct GrTriangulator::Comparator {
515 enum class Direction { kVertical, kHorizontal };
516 Comparator(Direction direction) : fDirection(direction) {}
517 bool sweep_lt(const SkPoint& a, const SkPoint& b) const;
518 Direction fDirection;
519};
520
521#endif // SK_ENABLE_OPTIMIZE_SIZE
522
523#endif // GrTriangulator_DEFINED
524

source code of flutter_engine/third_party/skia/src/gpu/ganesh/geometry/GrTriangulator.h