blob: 6227b352b2e0bd11c28596eb2729dbbaf967bf50 [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);
31 int count = triangulator.pathToTriangles(tolerance, clipBounds, vertexAllocator,
32 path.getFillType());
33 *isLinear = triangulator.fIsLinear;
34 return count;
Chris Dalton57ea1fc2021-01-05 13:37:44 -070035 }
ethannicholase9709e82016-01-07 13:34:16 -080036
Chris Dalton854ee852021-01-05 15:12:59 -070037 static int PathToAATriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
38 GrEagerVertexAllocator* vertexAllocator, bool* isLinear) {
39 GrTriangulator triangulator(path);
40 triangulator.fRoundVerticesToQuarterPixel = true;
41 triangulator.fEmitCoverage = true;
42 int count = triangulator.pathToTriangles(tolerance, clipBounds, vertexAllocator,
43 SkPathFillType::kWinding);
44 *isLinear = triangulator.fIsLinear;
45 return count;
46 }
47
48 static int TriangulateSimpleInnerPolygons(const SkPath& path,
49 GrEagerVertexAllocator* vertexAllocator,
50 bool *isLinear) {
51 GrTriangulator triangulator(path);
52 triangulator.fCullCollinearVertices = false;
53 triangulator.fSimpleInnerPolygons = true;
54 int count = triangulator.pathToTriangles(0, SkRect::MakeEmpty(), vertexAllocator,
55 path.getFillType());
56 *isLinear = triangulator.fIsLinear;
57 return count;
58 }
ethannicholase9709e82016-01-07 13:34:16 -080059
Chris Dalton57ea1fc2021-01-05 13:37:44 -070060 struct WindingVertex {
61 SkPoint fPos;
62 int fWinding;
63 };
Chris Dalton6ccc0322020-01-29 11:38:16 -070064
Chris Dalton57ea1fc2021-01-05 13:37:44 -070065 // *DEPRECATED*: Once CCPR is removed this method will go away.
Chris Dalton6ccc0322020-01-29 11:38:16 -070066 //
Chris Dalton57ea1fc2021-01-05 13:37:44 -070067 // Triangulates a path to an array of vertices. Each triangle is represented as a set of three
68 // WindingVertex entries, each of which contains the position and winding count (which is the
69 // same for all three vertices of a triangle). The 'verts' out parameter is set to point to the
70 // resultant vertex array. CALLER IS RESPONSIBLE for deleting this buffer to avoid a memory
71 // leak!
72 static int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds,
73 WindingVertex** verts);
74
Chris Dalton17ce8c52021-01-07 18:08:46 -070075 // Enums used by GrTriangulator internals.
76 typedef enum { kLeft_Side, kRight_Side } Side;
77 enum class EdgeType { kInner, kOuter, kConnector };
78
Chris Dalton57ea1fc2021-01-05 13:37:44 -070079 // Structs used by GrTriangulator internals.
80 struct Vertex;
81 struct VertexList;
Chris Dalton17ce8c52021-01-07 18:08:46 -070082 struct Line;
Chris Dalton57ea1fc2021-01-05 13:37:44 -070083 struct Edge;
84 struct EdgeList;
Chris Dalton17ce8c52021-01-07 18:08:46 -070085 struct MonotonePoly;
Chris Dalton57ea1fc2021-01-05 13:37:44 -070086 struct Poly;
87 struct Comparator;
88
89private:
Chris Dalton854ee852021-01-05 15:12:59 -070090 GrTriangulator(const SkPath& path) : fPath(path) {}
Chris Dalton57ea1fc2021-01-05 13:37:44 -070091
92 // There are six stages to the basic algorithm:
93 //
94 // 1) Linearize the path contours into piecewise linear segments:
95 void pathToContours(float tolerance, const SkRect& clipBounds, VertexList* contours);
96
97 // 2) Build a mesh of edges connecting the vertices:
Chris Dalton811dc6a2021-01-07 16:40:32 -070098 void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -070099
100 // 3) Sort the vertices in Y (and secondarily in X) (merge_sort()).
101 static void SortMesh(VertexList* vertices, const Comparator&);
102
103 // 4) Simplify the mesh by inserting new vertices at intersecting edges:
104 enum class SimplifyResult {
105 kAlreadySimple,
106 kFoundSelfIntersection,
107 kAbort
108 };
109
Chris Dalton811dc6a2021-01-07 16:40:32 -0700110 SimplifyResult simplify(VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700111
112 // 5) Tessellate the simplified mesh into monotone polygons:
113 Poly* tessellate(const VertexList& vertices);
114
115 // 6) Triangulate the monotone polygons directly into a vertex buffer:
116 void* polysToTriangles(Poly* polys, void* data, SkPathFillType overrideFillType);
117
118 // For screenspace antialiasing, the algorithm is modified as follows:
119 //
120 // Run steps 1-5 above to produce polygons.
121 // 5b) Apply fill rules to extract boundary contours from the polygons (extract_boundaries()).
122 // 5c) Simplify boundaries to remove "pointy" vertices that cause inversions
123 // (simplify_boundary()).
124 // 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find
125 // new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a
126 // new antialiased mesh from those vertices (stroke_boundary()).
127 // Run steps 3-6 above on the new mesh, and produce antialiased triangles.
128 //
129 // The vertex sorting in step (3) is a merge sort, since it plays well with the linked list
130 // of vertices (and the necessity of inserting new vertices on intersection).
131 //
132 // Stages (4) and (5) use an active edge list -- a list of all edges for which the
133 // sweep line has crossed the top vertex, but not the bottom vertex. It's sorted
134 // left-to-right based on the point where both edges are active (when both top vertices
135 // have been seen, so the "lower" top vertex of the two). If the top vertices are equal
136 // (shared), it's sorted based on the last point where both edges are active, so the
137 // "upper" bottom vertex.
138 //
139 // The most complex step is the simplification (4). It's based on the Bentley-Ottman
140 // line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
141 // not exact and may violate the mesh topology or active edge list ordering. We
142 // accommodate this by adjusting the topology of the mesh and AEL to match the intersection
143 // points. This occurs in two ways:
144 //
145 // A) Intersections may cause a shortened edge to no longer be ordered with respect to its
146 // neighbouring edges at the top or bottom vertex. This is handled by merging the
147 // edges (merge_collinear_edges()).
148 // B) Intersections may cause an edge to violate the left-to-right ordering of the
149 // active edge list. This is handled by detecting potential violations and rewinding
150 // the active edge list to the vertex before they occur (rewind() during merging,
151 // rewind_if_necessary() during splitting).
152 //
153 // The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
154 // Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
155 // currently uses a linked list for the active edge list, rather than a 2-3 tree as the
156 // paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also
157 // become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N)
158 // insertions and removals was greater than the cost of infrequent O(N) lookups with the
159 // linked list implementation. With the latter, all removals are O(1), and most insertions
160 // are O(1), since we know the adjacent edge in the active edge list based on the topology.
161 // Only type 2 vertices (see paper) require the O(N) lookups, and these are much less
162 // frequent. There may be other data structures worth investigating, however.
163 //
164 // Note that the orientation of the line sweep algorithms is determined by the aspect ratio of
165 // the path bounds. When the path is taller than it is wide, we sort vertices based on
166 // increasing Y coordinate, and secondarily by increasing X coordinate. When the path is wider
167 // than it is tall, we sort by increasing X coordinate, but secondarily by *decreasing* Y
168 // coordinate. This is so that the "left" and "right" orientation in the code remains correct
169 // (edges to the left are increasing in Y; edges to the right are decreasing in Y). That is, the
170 // setting rotates 90 degrees counterclockwise, rather that transposing.
171
172 // Additional helpers and driver functions.
173 void appendPointToContour(const SkPoint& p, VertexList* contour);
174 void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd, VertexList* contour);
175 void generateCubicPoints(const SkPoint&, const SkPoint&, const SkPoint&, const SkPoint&,
176 SkScalar tolSqd, VertexList* contour, int pointsLeft);
Chris Dalton811dc6a2021-01-07 16:40:32 -0700177 bool splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
178 const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700179 bool intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton811dc6a2021-01-07 16:40:32 -0700180 const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700181 bool checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current,
Chris Dalton811dc6a2021-01-07 16:40:32 -0700182 VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700183 void sanitizeContours(VertexList* contours, int contourCnt);
Chris Dalton811dc6a2021-01-07 16:40:32 -0700184 bool mergeCoincidentVertices(VertexList* mesh, const Comparator&);
185 void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&);
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700186 Poly* contoursToPolys(VertexList* contours, int contourCnt, VertexList* outerMesh);
187 Poly* pathToPolys(float tolerance, const SkRect& clipBounds, int contourCnt,
188 VertexList* outerMesh);
189 int pathToTriangles(float tolerance, const SkRect& clipBounds, GrEagerVertexAllocator*,
190 SkPathFillType overrideFillType);
191
192 constexpr static int kArenaChunkSize = 16 * 1024;
193 SkArenaAlloc fAlloc{kArenaChunkSize};
194 const SkPath fPath;
Chris Dalton57ea1fc2021-01-05 13:37:44 -0700195 bool fIsLinear = false;
Chris Dalton854ee852021-01-05 15:12:59 -0700196
197 // Flags.
198 bool fRoundVerticesToQuarterPixel = false;
199 bool fEmitCoverage = false;
200 bool fCullCollinearVertices = true;
201 bool fSimpleInnerPolygons = false;
Chris Daltondcc8c542020-01-28 17:55:56 -0700202};
203
Chris Dalton5045de32021-01-07 19:09:01 -0700204/**
205 * Vertices are used in three ways: first, the path contours are converted into a
206 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
207 * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing
208 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid
209 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of
210 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since
211 * an individual Vertex from the path mesh may belong to multiple
212 * MonotonePolys, so the original Vertices cannot be re-used.
213 */
214
215struct GrTriangulator::Vertex {
216 Vertex(const SkPoint& point, uint8_t alpha)
217 : fPoint(point), fPrev(nullptr), fNext(nullptr)
218 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
219 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
220 , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
221 , fPartner(nullptr)
222 , fAlpha(alpha)
223 , fSynthetic(false)
224#if TRIANGULATOR_LOGGING
225 , fID (-1.0f)
226#endif
227 {}
228 SkPoint fPoint; // Vertex position
229 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
230 Vertex* fNext; // "
231 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
232 Edge* fLastEdgeAbove; // "
233 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
234 Edge* fLastEdgeBelow; // "
235 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
236 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
237 Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
238 uint8_t fAlpha;
239 bool fSynthetic; // Is this a synthetic vertex?
240#if TRIANGULATOR_LOGGING
241 float fID; // Identifier used for logging.
242#endif
243};
244
245struct GrTriangulator::VertexList {
246 VertexList() : fHead(nullptr), fTail(nullptr) {}
247 VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {}
248 Vertex* fHead;
249 Vertex* fTail;
250 void insert(Vertex* v, Vertex* prev, Vertex* next);
251 void append(Vertex* v) { insert(v, fTail, nullptr); }
252 void append(const VertexList& list) {
253 if (!list.fHead) {
254 return;
255 }
256 if (fTail) {
257 fTail->fNext = list.fHead;
258 list.fHead->fPrev = fTail;
259 } else {
260 fHead = list.fHead;
261 }
262 fTail = list.fTail;
263 }
264 void prepend(Vertex* v) { insert(v, nullptr, fHead); }
265 void remove(Vertex* v);
266 void close() {
267 if (fHead && fTail) {
268 fTail->fNext = fHead;
269 fHead->fPrev = fTail;
270 }
271 }
272};
273
274// A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line.
275struct GrTriangulator::Line {
276 Line(double a, double b, double c) : fA(a), fB(b), fC(c) {}
277 Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {}
278 Line(const SkPoint& p, const SkPoint& q)
279 : fA(static_cast<double>(q.fY) - p.fY) // a = dY
280 , fB(static_cast<double>(p.fX) - q.fX) // b = -dX
281 , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p)
282 static_cast<double>(p.fX) * q.fY) {}
283 double dist(const SkPoint& p) const { return fA * p.fX + fB * p.fY + fC; }
284 Line operator*(double v) const { return Line(fA * v, fB * v, fC * v); }
285 double magSq() const { return fA * fA + fB * fB; }
286 void normalize() {
287 double len = sqrt(this->magSq());
288 if (len == 0.0) {
289 return;
290 }
291 double scale = 1.0f / len;
292 fA *= scale;
293 fB *= scale;
294 fC *= scale;
295 }
296 bool nearParallel(const Line& o) const {
297 return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001;
298 }
299
300 // Compute the intersection of two (infinite) Lines.
301 bool intersect(const Line& other, SkPoint* point) const;
302 double fA, fB, fC;
303};
304
305/**
306 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
307 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
308 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
309 * point). For speed, that case is only tested by the callers that require it (e.g.,
310 * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
311 * Currently, this converts the edges to the parametric form, in order to avoid doing a division
312 * until an intersection has been confirmed. This is slightly slower in the "found" case, but
313 * a lot faster in the "not found" case.
314 *
315 * The coefficients of the line equation stored in double precision to avoid catastrophic
316 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is
317 * correct in float, since it's a polynomial of degree 2. The intersect() function, being
318 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its
319 * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of
320 * this file).
321 */
322
323struct GrTriangulator::Edge {
324 Edge(Vertex* top, Vertex* bottom, int winding, EdgeType type)
325 : fWinding(winding)
326 , fTop(top)
327 , fBottom(bottom)
328 , fType(type)
329 , fLeft(nullptr)
330 , fRight(nullptr)
331 , fPrevEdgeAbove(nullptr)
332 , fNextEdgeAbove(nullptr)
333 , fPrevEdgeBelow(nullptr)
334 , fNextEdgeBelow(nullptr)
335 , fLeftPoly(nullptr)
336 , fRightPoly(nullptr)
337 , fLeftPolyPrev(nullptr)
338 , fLeftPolyNext(nullptr)
339 , fRightPolyPrev(nullptr)
340 , fRightPolyNext(nullptr)
341 , fUsedInLeftPoly(false)
342 , fUsedInRightPoly(false)
343 , fLine(top, bottom) {
344 }
345 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
346 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt).
347 Vertex* fBottom; // The bottom vertex in vertex-sort-order.
348 EdgeType fType;
349 Edge* fLeft; // The linked list of edges in the active edge list.
350 Edge* fRight; // "
351 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
352 Edge* fNextEdgeAbove; // "
353 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
354 Edge* fNextEdgeBelow; // "
355 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
356 Poly* fRightPoly; // The Poly to the right of this edge, if any.
357 Edge* fLeftPolyPrev;
358 Edge* fLeftPolyNext;
359 Edge* fRightPolyPrev;
360 Edge* fRightPolyNext;
361 bool fUsedInLeftPoly;
362 bool fUsedInRightPoly;
363 Line fLine;
364 double dist(const SkPoint& p) const { return fLine.dist(p); }
365 bool isRightOf(Vertex* v) const { return fLine.dist(v->fPoint) < 0.0; }
366 bool isLeftOf(Vertex* v) const { return fLine.dist(v->fPoint) > 0.0; }
367 void recompute() { fLine = Line(fTop, fBottom); }
368 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const;
369};
370
371struct GrTriangulator::EdgeList {
372 EdgeList() : fHead(nullptr), fTail(nullptr) {}
373 Edge* fHead;
374 Edge* fTail;
375 void insert(Edge* edge, Edge* prev, Edge* next);
376 void append(Edge* e) { insert(e, fTail, nullptr); }
377 void remove(Edge* edge);
378 void removeAll() {
379 while (fHead) {
380 this->remove(fHead);
381 }
382 }
383 void close() {
384 if (fHead && fTail) {
385 fTail->fRight = fHead;
386 fHead->fLeft = fTail;
387 }
388 }
389 bool contains(Edge* edge) const { return edge->fLeft || edge->fRight || fHead == edge; }
390};
391
392struct GrTriangulator::MonotonePoly {
393 MonotonePoly(Edge* edge, Side side, int winding)
394 : fSide(side)
395 , fFirstEdge(nullptr)
396 , fLastEdge(nullptr)
397 , fPrev(nullptr)
398 , fNext(nullptr)
399 , fWinding(winding) {
400 this->addEdge(edge);
401 }
402 Side fSide;
403 Edge* fFirstEdge;
404 Edge* fLastEdge;
405 MonotonePoly* fPrev;
406 MonotonePoly* fNext;
407 int fWinding;
408 void addEdge(Edge*);
409 void* emit(bool emitCoverage, void* data);
410 void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, bool emitCoverage,
411 void* data) const;
412};
413
414struct GrTriangulator::Poly {
415 Poly(Vertex* v, int winding)
416 : fFirstVertex(v)
417 , fWinding(winding)
418 , fHead(nullptr)
419 , fTail(nullptr)
420 , fNext(nullptr)
421 , fPartner(nullptr)
422 , fCount(0)
423 {
424#if TRIANGULATOR_LOGGING
425 static int gID = 0;
426 fID = gID++;
427 TESS_LOG("*** created Poly %d\n", fID);
428#endif
429 }
430 Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc);
431 void* emit(bool emitCoverage, void *data);
432 Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; }
433 Vertex* fFirstVertex;
434 int fWinding;
435 MonotonePoly* fHead;
436 MonotonePoly* fTail;
437 Poly* fNext;
438 Poly* fPartner;
439 int fCount;
440#if TRIANGULATOR_LOGGING
441 int fID;
442#endif
443};
444
445struct GrTriangulator::Comparator {
446 enum class Direction { kVertical, kHorizontal };
447 Comparator(Direction direction) : fDirection(direction) {}
448 bool sweep_lt(const SkPoint& a, const SkPoint& b) const;
449 Direction fDirection;
450};
451
ethannicholase9709e82016-01-07 13:34:16 -0800452#endif