• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #include "src/gpu/ganesh/geometry/GrTriangulator.h"
9 
10 #include "include/core/SkPathTypes.h"
11 #include "include/core/SkRect.h"
12 #include "include/private/base/SkDebug.h"
13 #include "include/private/base/SkFloatingPoint.h"
14 #include "include/private/base/SkMath.h"
15 #include "include/private/base/SkTPin.h"
16 #include "src/base/SkVx.h"
17 #include "src/core/SkGeometry.h"
18 #include "src/core/SkPointPriv.h"
19 #include "src/gpu/BufferWriter.h"
20 #include "src/gpu/ganesh/GrColor.h"
21 #include "src/gpu/ganesh/GrEagerVertexAllocator.h"
22 #include "src/gpu/ganesh/geometry/GrPathUtils.h"
23 
24 #include <algorithm>
25 #include <cstddef>
26 #include <limits>
27 #include <memory>
28 #include <tuple>
29 #include <utility>
30 
31 #if !defined(SK_ENABLE_OPTIMIZE_SIZE)
32 
33 #if TRIANGULATOR_LOGGING
34 #define TESS_LOG printf
35 #define DUMP_MESH(M) (M).dump()
36 #else
37 #define TESS_LOG(...)
38 #define DUMP_MESH(M)
39 #endif
40 
41 using EdgeType = GrTriangulator::EdgeType;
42 using Vertex = GrTriangulator::Vertex;
43 using VertexList = GrTriangulator::VertexList;
44 using Line = GrTriangulator::Line;
45 using Edge = GrTriangulator::Edge;
46 using EdgeList = GrTriangulator::EdgeList;
47 using Poly = GrTriangulator::Poly;
48 using MonotonePoly = GrTriangulator::MonotonePoly;
49 using Comparator = GrTriangulator::Comparator;
50 
51 template <class T, T* T::*Prev, T* T::*Next>
list_insert(T * t,T * prev,T * next,T ** head,T ** tail)52 static void list_insert(T* t, T* prev, T* next, T** head, T** tail) {
53     t->*Prev = prev;
54     t->*Next = next;
55     if (prev) {
56         prev->*Next = t;
57     } else if (head) {
58         *head = t;
59     }
60     if (next) {
61         next->*Prev = t;
62     } else if (tail) {
63         *tail = t;
64     }
65 }
66 
67 template <class T, T* T::*Prev, T* T::*Next>
list_remove(T * t,T ** head,T ** tail)68 static void list_remove(T* t, T** head, T** tail) {
69     if (t->*Prev) {
70         t->*Prev->*Next = t->*Next;
71     } else if (head) {
72         *head = t->*Next;
73     }
74     if (t->*Next) {
75         t->*Next->*Prev = t->*Prev;
76     } else if (tail) {
77         *tail = t->*Prev;
78     }
79     t->*Prev = t->*Next = nullptr;
80 }
81 
82 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b);
83 
sweep_lt_horiz(const SkPoint & a,const SkPoint & b)84 static bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) {
85     return a.fX < b.fX || (a.fX == b.fX && a.fY > b.fY);
86 }
87 
sweep_lt_vert(const SkPoint & a,const SkPoint & b)88 static bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) {
89     return a.fY < b.fY || (a.fY == b.fY && a.fX < b.fX);
90 }
91 
sweep_lt(const SkPoint & a,const SkPoint & b) const92 bool GrTriangulator::Comparator::sweep_lt(const SkPoint& a, const SkPoint& b) const {
93     return fDirection == Direction::kHorizontal ? sweep_lt_horiz(a, b) : sweep_lt_vert(a, b);
94 }
95 
emit_vertex(Vertex * v,bool emitCoverage,skgpu::VertexWriter data)96 static inline skgpu::VertexWriter emit_vertex(Vertex* v,
97                                               bool emitCoverage,
98                                               skgpu::VertexWriter data) {
99     data << v->fPoint;
100 
101     if (emitCoverage) {
102         data << GrNormalizeByteToFloat(v->fAlpha);
103     }
104 
105     return data;
106 }
107 
emit_triangle(Vertex * v0,Vertex * v1,Vertex * v2,bool emitCoverage,skgpu::VertexWriter data)108 static skgpu::VertexWriter emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2,
109                                          bool emitCoverage, skgpu::VertexWriter data) {
110     TESS_LOG("emit_triangle %g (%g, %g) %d\n", v0->fID, v0->fPoint.fX, v0->fPoint.fY, v0->fAlpha);
111     TESS_LOG("              %g (%g, %g) %d\n", v1->fID, v1->fPoint.fX, v1->fPoint.fY, v1->fAlpha);
112     TESS_LOG("              %g (%g, %g) %d\n", v2->fID, v2->fPoint.fX, v2->fPoint.fY, v2->fAlpha);
113 #if TRIANGULATOR_WIREFRAME
114     data = emit_vertex(v0, emitCoverage, std::move(data));
115     data = emit_vertex(v1, emitCoverage, std::move(data));
116     data = emit_vertex(v1, emitCoverage, std::move(data));
117     data = emit_vertex(v2, emitCoverage, std::move(data));
118     data = emit_vertex(v2, emitCoverage, std::move(data));
119     data = emit_vertex(v0, emitCoverage, std::move(data));
120 #else
121     data = emit_vertex(v0, emitCoverage, std::move(data));
122     data = emit_vertex(v1, emitCoverage, std::move(data));
123     data = emit_vertex(v2, emitCoverage, std::move(data));
124 #endif
125     return data;
126 }
127 
insert(Vertex * v,Vertex * prev,Vertex * next)128 void GrTriangulator::VertexList::insert(Vertex* v, Vertex* prev, Vertex* next) {
129     list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail);
130 }
131 
remove(Vertex * v)132 void GrTriangulator::VertexList::remove(Vertex* v) {
133     list_remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, &fHead, &fTail);
134 }
135 
136 // Round to nearest quarter-pixel. This is used for screenspace tessellation.
137 
round(SkPoint * p)138 static inline void round(SkPoint* p) {
139     p->fX = SkScalarRoundToScalar(p->fX * 4.0f) * 0.25f;
140     p->fY = SkScalarRoundToScalar(p->fY * 4.0f) * 0.25f;
141 }
142 
double_to_clamped_scalar(double d)143 static inline SkScalar double_to_clamped_scalar(double d) {
144     // Clamps large values to what's finitely representable when cast back to a float.
145     static const double kMaxLimit = (double) SK_ScalarMax;
146     // It's not perfect, but a using a value larger than float_min helps protect from denormalized
147     // values and ill-conditions in intermediate calculations on coordinates.
148     static const double kNearZeroLimit = 16 * (double) std::numeric_limits<float>::min();
149     if (std::abs(d) < kNearZeroLimit) {
150         d = 0.f;
151     }
152     return SkDoubleToScalar(std::max(-kMaxLimit, std::min(d, kMaxLimit)));
153 }
154 
intersect(const Line & other,SkPoint * point) const155 bool GrTriangulator::Line::intersect(const Line& other, SkPoint* point) const {
156     double denom = fA * other.fB - fB * other.fA;
157     if (denom == 0.0) {
158         return false;
159     }
160     double scale = 1.0 / denom;
161     point->fX = double_to_clamped_scalar((fB * other.fC - other.fB * fC) * scale);
162     point->fY = double_to_clamped_scalar((other.fA * fC - fA * other.fC) * scale);
163      round(point);
164     return point->isFinite();
165 }
166 
167 // If the edge's vertices differ by many orders of magnitude, the computed line equation can have
168 // significant error in its distance and intersection tests. To avoid this, we recursively subdivide
169 // long edges and effectively perform a binary search to perform a more accurate intersection test.
edge_line_needs_recursion(const SkPoint & p0,const SkPoint & p1)170 static bool edge_line_needs_recursion(const SkPoint& p0, const SkPoint& p1) {
171     // ilogbf(0) returns an implementation-defined constant, but we are choosing to saturate
172     // negative exponents to 0 for comparisons sake. We're only trying to recurse on lines with
173     // very large coordinates.
174     int expDiffX = std::abs((std::abs(p0.fX) < 1.f ? 0 : std::ilogbf(p0.fX)) -
175                             (std::abs(p1.fX) < 1.f ? 0 : std::ilogbf(p1.fX)));
176     int expDiffY = std::abs((std::abs(p0.fY) < 1.f ? 0 : std::ilogbf(p0.fY)) -
177                             (std::abs(p1.fY) < 1.f ? 0 : std::ilogbf(p1.fY)));
178     // Differ by more than 2^20, or roughly a factor of one million.
179     return expDiffX > 20 || expDiffY > 20;
180 }
181 
recursive_edge_intersect(const Line & u,SkPoint u0,SkPoint u1,const Line & v,SkPoint v0,SkPoint v1,SkPoint * p,double * s,double * t)182 static bool recursive_edge_intersect(const Line& u, SkPoint u0, SkPoint u1,
183                                      const Line& v, SkPoint v0, SkPoint v1,
184                                      SkPoint* p, double* s, double* t) {
185     // First check if the bounding boxes of [u0,u1] intersects [v0,v1]. If they do not, then the
186     // two line segments cannot intersect in their domain (even if the lines themselves might).
187     // - don't use SkRect::intersect since the vertices aren't sorted and horiz/vertical lines
188     //   appear as empty rects, which then never "intersect" according to SkRect.
189     if (std::min(u0.fX, u1.fX) > std::max(v0.fX, v1.fX) ||
190         std::max(u0.fX, u1.fX) < std::min(v0.fX, v1.fX) ||
191         std::min(u0.fY, u1.fY) > std::max(v0.fY, v1.fY) ||
192         std::max(u0.fY, u1.fY) < std::min(v0.fY, v1.fY)) {
193         return false;
194     }
195 
196     // Compute intersection based on current segment vertices; if an intersection is found but the
197     // vertices differ too much in magnitude, we recurse using the midpoint of the segment to
198     // reject false positives. We don't currently try to avoid false negatives (e.g. large magnitude
199     // line reports no intersection but there is one).
200     double denom = u.fA * v.fB - u.fB * v.fA;
201     if (denom == 0.0) {
202         return false;
203     }
204     double dx = static_cast<double>(v0.fX) - u0.fX;
205     double dy = static_cast<double>(v0.fY) - u0.fY;
206     double sNumer = dy * v.fB + dx * v.fA;
207     double tNumer = dy * u.fB + dx * u.fA;
208     // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early.
209     // This saves us doing the divide below unless absolutely necessary.
210     if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom)
211                     : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) {
212         return false;
213     }
214 
215     *s = sNumer / denom;
216     *t = tNumer / denom;
217     SkASSERT(*s >= 0.0 && *s <= 1.0 && *t >= 0.0 && *t <= 1.0);
218 
219     const bool uNeedsSplit = edge_line_needs_recursion(u0, u1);
220     const bool vNeedsSplit = edge_line_needs_recursion(v0, v1);
221     if (!uNeedsSplit && !vNeedsSplit) {
222         p->fX = double_to_clamped_scalar(u0.fX - (*s) * u.fB);
223         p->fY = double_to_clamped_scalar(u0.fY + (*s) * u.fA);
224         return true;
225     } else {
226         double sScale = 1.0, sShift = 0.0;
227         double tScale = 1.0, tShift = 0.0;
228 
229         if (uNeedsSplit) {
230             SkPoint uM = {(float) (0.5 * u0.fX + 0.5 * u1.fX),
231                           (float) (0.5 * u0.fY + 0.5 * u1.fY)};
232             sScale = 0.5;
233             if (*s >= 0.5) {
234                 u0 = uM;
235                 sShift = 0.5;
236             } else {
237                 u1 = uM;
238             }
239         }
240         if (vNeedsSplit) {
241             SkPoint vM = {(float) (0.5 * v0.fX + 0.5 * v1.fX),
242                           (float) (0.5 * v0.fY + 0.5 * v1.fY)};
243             tScale = 0.5;
244             if (*t >= 0.5) {
245                 v0 = vM;
246                 tShift = 0.5;
247             } else {
248                 v1 = vM;
249             }
250         }
251 
252         // Just recompute both lines, even if only one was split; we're already in a slow path.
253         if (recursive_edge_intersect(Line(u0, u1), u0, u1, Line(v0, v1), v0, v1, p, s, t)) {
254             // Adjust s and t back to full range
255             *s = sScale * (*s) + sShift;
256             *t = tScale * (*t) + tShift;
257             return true;
258         } else {
259             // False positive
260             return false;
261         }
262     }
263 }
264 
intersect(const Edge & other,SkPoint * p,uint8_t * alpha) const265 bool GrTriangulator::Edge::intersect(const Edge& other, SkPoint* p, uint8_t* alpha) const {
266     TESS_LOG("intersecting %g -> %g with %g -> %g\n",
267              fTop->fID, fBottom->fID, other.fTop->fID, other.fBottom->fID);
268     if (fTop == other.fTop || fBottom == other.fBottom ||
269         fTop == other.fBottom || fBottom == other.fTop) {
270         // If the two edges share a vertex by construction, they have already been split and
271         // shouldn't be considered "intersecting" anymore.
272         return false;
273     }
274 
275     double s, t; // needed to interpolate vertex alpha
276     const bool intersects = recursive_edge_intersect(
277             fLine, fTop->fPoint, fBottom->fPoint,
278             other.fLine, other.fTop->fPoint, other.fBottom->fPoint,
279             p, &s, &t);
280     if (!intersects) {
281         return false;
282     }
283 
284     if (alpha) {
285         if (fType == EdgeType::kInner || other.fType == EdgeType::kInner) {
286             // If the intersection is on any interior edge, it needs to stay fully opaque or later
287             // triangulation could leech transparency into the inner fill region.
288             *alpha = 255;
289         } else if (fType == EdgeType::kOuter && other.fType == EdgeType::kOuter) {
290             // Trivially, the intersection will be fully transparent since since it is by
291             // construction on the outer edge.
292             *alpha = 0;
293         } else {
294             // Could be two connectors crossing, or a connector crossing an outer edge.
295             // Take the max interpolated alpha
296             SkASSERT(fType == EdgeType::kConnector || other.fType == EdgeType::kConnector);
297             *alpha = std::max((1.0 - s) * fTop->fAlpha + s * fBottom->fAlpha,
298                               (1.0 - t) * other.fTop->fAlpha + t * other.fBottom->fAlpha);
299         }
300     }
301     return true;
302 }
303 
insert(Edge * edge,Edge * prev,Edge * next)304 void GrTriangulator::EdgeList::insert(Edge* edge, Edge* prev, Edge* next) {
305     list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail);
306 }
307 
remove(Edge * edge)308 bool GrTriangulator::EdgeList::remove(Edge* edge) {
309     TESS_LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
310     // SkASSERT(this->contains(edge));  // Leave this here for future debugging.
311     if (!this->contains(edge)) {
312         return false;
313     }
314     list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
315     return true;
316 }
317 
addEdge(Edge * edge)318 void GrTriangulator::MonotonePoly::addEdge(Edge* edge) {
319     if (fSide == Side::kRight) {
320         SkASSERT(!edge->fUsedInRightPoly);
321         list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>(
322             edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
323         edge->fUsedInRightPoly = true;
324     } else {
325         SkASSERT(!edge->fUsedInLeftPoly);
326         list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
327             edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
328         edge->fUsedInLeftPoly = true;
329     }
330 }
331 
emitMonotonePoly(const MonotonePoly * monotonePoly,skgpu::VertexWriter data) const332 skgpu::VertexWriter GrTriangulator::emitMonotonePoly(const MonotonePoly* monotonePoly,
333                                                      skgpu::VertexWriter data) const {
334     SkASSERT(monotonePoly->fWinding != 0);
335     Edge* e = monotonePoly->fFirstEdge;
336     VertexList vertices;
337     vertices.append(e->fTop);
338     int count = 1;
339     while (e != nullptr) {
340         if (Side::kRight == monotonePoly->fSide) {
341             vertices.append(e->fBottom);
342             e = e->fRightPolyNext;
343         } else {
344             vertices.prepend(e->fBottom);
345             e = e->fLeftPolyNext;
346         }
347         count++;
348     }
349     Vertex* first = vertices.fHead;
350     Vertex* v = first->fNext;
351     while (v != vertices.fTail) {
352         SkASSERT(v && v->fPrev && v->fNext);
353         Vertex* prev = v->fPrev;
354         Vertex* curr = v;
355         Vertex* next = v->fNext;
356         if (count == 3) {
357             return this->emitTriangle(prev, curr, next, monotonePoly->fWinding, std::move(data));
358         }
359         double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.fX;
360         double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.fY;
361         double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.fX;
362         double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.fY;
363         if (ax * by - ay * bx >= 0.0) {
364             data = this->emitTriangle(prev, curr, next, monotonePoly->fWinding, std::move(data));
365             v->fPrev->fNext = v->fNext;
366             v->fNext->fPrev = v->fPrev;
367             count--;
368             if (v->fPrev == first) {
369                 v = v->fNext;
370             } else {
371                 v = v->fPrev;
372             }
373         } else {
374             v = v->fNext;
375         }
376     }
377     return data;
378 }
379 
emitTriangle(Vertex * prev,Vertex * curr,Vertex * next,int winding,skgpu::VertexWriter data) const380 skgpu::VertexWriter GrTriangulator::emitTriangle(
381         Vertex* prev, Vertex* curr, Vertex* next, int winding, skgpu::VertexWriter data) const {
382     if (winding > 0) {
383         // Ensure our triangles always wind in the same direction as if the path had been
384         // triangulated as a simple fan (a la red book).
385         std::swap(prev, next);
386     }
387     if (fCollectBreadcrumbTriangles && abs(winding) > 1 &&
388         fPath.getFillType() == SkPathFillType::kWinding) {
389         // The first winding count will come from the actual triangle we emit. The remaining counts
390         // come from the breadcrumb triangle.
391         fBreadcrumbList.append(fAlloc, prev->fPoint, curr->fPoint, next->fPoint, abs(winding) - 1);
392     }
393     return emit_triangle(prev, curr, next, fEmitCoverage, std::move(data));
394 }
395 
Poly(Vertex * v,int winding)396 GrTriangulator::Poly::Poly(Vertex* v, int winding)
397         : fFirstVertex(v)
398         , fWinding(winding)
399         , fHead(nullptr)
400         , fTail(nullptr)
401         , fNext(nullptr)
402         , fPartner(nullptr)
403         , fCount(0)
404 {
405 #if TRIANGULATOR_LOGGING
406     static int gID = 0;
407     fID = gID++;
408     TESS_LOG("*** created Poly %d\n", fID);
409 #endif
410 }
411 
addEdge(Edge * e,Side side,GrTriangulator * tri)412 Poly* GrTriangulator::Poly::addEdge(Edge* e, Side side, GrTriangulator* tri) {
413     TESS_LOG("addEdge (%g -> %g) to poly %d, %s side\n",
414              e->fTop->fID,
415              e->fBottom->fID,
416              fID,
417              side == Side::kLeft ? "left" : "right");
418     Poly* partner = fPartner;
419     Poly* poly = this;
420     if (side == Side::kRight) {
421         if (e->fUsedInRightPoly) {
422             return this;
423         }
424     } else {
425         if (e->fUsedInLeftPoly) {
426             return this;
427         }
428     }
429     if (partner) {
430         fPartner = partner->fPartner = nullptr;
431     }
432     if (!fTail) {
433         fHead = fTail = tri->allocateMonotonePoly(e, side, fWinding);
434         fCount += 2;
435     } else if (e->fBottom == fTail->fLastEdge->fBottom) {
436         return poly;
437     } else if (side == fTail->fSide) {
438         fTail->addEdge(e);
439         fCount++;
440     } else {
441         e = tri->allocateEdge(fTail->fLastEdge->fBottom, e->fBottom, 1, EdgeType::kInner);
442         fTail->addEdge(e);
443         fCount++;
444         if (partner) {
445             partner->addEdge(e, side, tri);
446             poly = partner;
447         } else {
448             MonotonePoly* m = tri->allocateMonotonePoly(e, side, fWinding);
449             m->fPrev = fTail;
450             fTail->fNext = m;
451             fTail = m;
452         }
453     }
454     return poly;
455 }
emitPoly(const Poly * poly,skgpu::VertexWriter data) const456 skgpu::VertexWriter GrTriangulator::emitPoly(const Poly* poly, skgpu::VertexWriter data) const {
457     if (poly->fCount < 3) {
458         return data;
459     }
460     TESS_LOG("emit() %d, size %d\n", poly->fID, poly->fCount);
461     for (MonotonePoly* m = poly->fHead; m != nullptr; m = m->fNext) {
462         data = this->emitMonotonePoly(m, std::move(data));
463     }
464     return data;
465 }
466 
coincident(const SkPoint & a,const SkPoint & b)467 static bool coincident(const SkPoint& a, const SkPoint& b) {
468     return a == b;
469 }
470 
makePoly(Poly ** head,Vertex * v,int winding) const471 Poly* GrTriangulator::makePoly(Poly** head, Vertex* v, int winding) const {
472     Poly* poly = fAlloc->make<Poly>(v, winding);
473     poly->fNext = *head;
474     *head = poly;
475     return poly;
476 }
477 
appendPointToContour(const SkPoint & p,VertexList * contour) const478 void GrTriangulator::appendPointToContour(const SkPoint& p, VertexList* contour) const {
479     Vertex* v = fAlloc->make<Vertex>(p, 255);
480 #if TRIANGULATOR_LOGGING
481     static float gID = 0.0f;
482     v->fID = gID++;
483 #endif
484     contour->append(v);
485 }
486 
quad_error_at(const SkPoint pts[3],SkScalar t,SkScalar u)487 static SkScalar quad_error_at(const SkPoint pts[3], SkScalar t, SkScalar u) {
488     SkQuadCoeff quad(pts);
489     SkPoint p0 = to_point(quad.eval(t - 0.5f * u));
490     SkPoint mid = to_point(quad.eval(t));
491     SkPoint p1 = to_point(quad.eval(t + 0.5f * u));
492     if (!p0.isFinite() || !mid.isFinite() || !p1.isFinite()) {
493         return 0;
494     }
495     return SkPointPriv::DistanceToLineSegmentBetweenSqd(mid, p0, p1);
496 }
497 
appendQuadraticToContour(const SkPoint pts[3],SkScalar toleranceSqd,VertexList * contour) const498 void GrTriangulator::appendQuadraticToContour(const SkPoint pts[3], SkScalar toleranceSqd,
499                                               VertexList* contour) const {
500     SkQuadCoeff quad(pts);
501     skvx::float2 aa = quad.fA * quad.fA;
502     SkScalar denom = 2.0f * (aa[0] + aa[1]);
503     skvx::float2 ab = quad.fA * quad.fB;
504     SkScalar t = denom ? (-ab[0] - ab[1]) / denom : 0.0f;
505     int nPoints = 1;
506     SkScalar u = 1.0f;
507     // Test possible subdivision values only at the point of maximum curvature.
508     // If it passes the flatness metric there, it'll pass everywhere.
509     while (nPoints < GrPathUtils::kMaxPointsPerCurve) {
510         u = 1.0f / nPoints;
511         if (quad_error_at(pts, t, u) < toleranceSqd) {
512             break;
513         }
514         nPoints++;
515     }
516     for (int j = 1; j <= nPoints; j++) {
517         this->appendPointToContour(to_point(quad.eval(j * u)), contour);
518     }
519 }
520 
generateCubicPoints(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2,const SkPoint & p3,SkScalar tolSqd,VertexList * contour,int pointsLeft) const521 void GrTriangulator::generateCubicPoints(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
522                                          const SkPoint& p3, SkScalar tolSqd, VertexList* contour,
523                                          int pointsLeft) const {
524     SkScalar d1 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3);
525     SkScalar d2 = SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3);
526     if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || !SkIsFinite(d1, d2)) {
527         this->appendPointToContour(p3, contour);
528         return;
529     }
530     const SkPoint q[] = {
531         { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
532         { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
533         { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
534     };
535     const SkPoint r[] = {
536         { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
537         { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
538     };
539     const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
540     pointsLeft >>= 1;
541     this->generateCubicPoints(p0, q[0], r[0], s, tolSqd, contour, pointsLeft);
542     this->generateCubicPoints(s, r[1], q[2], p3, tolSqd, contour, pointsLeft);
543 }
544 
545 // Stage 1: convert the input path to a set of linear contours (linked list of Vertices).
546 
pathToContours(float tolerance,const SkRect & clipBounds,VertexList * contours,bool * isLinear) const547 void GrTriangulator::pathToContours(float tolerance, const SkRect& clipBounds,
548                                     VertexList* contours, bool* isLinear) const {
549     SkScalar toleranceSqd = tolerance * tolerance;
550     SkPoint pts[4];
551     *isLinear = true;
552     VertexList* contour = contours;
553     SkPath::Iter iter(fPath, false);
554     if (fPath.isInverseFillType()) {
555         SkPoint quad[4];
556         clipBounds.toQuad(quad);
557         for (int i = 3; i >= 0; i--) {
558             this->appendPointToContour(quad[i], contours);
559         }
560         contour++;
561     }
562     SkAutoConicToQuads converter;
563     SkPath::Verb verb;
564     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
565         switch (verb) {
566             case SkPath::kConic_Verb: {
567                 *isLinear = false;
568                 if (toleranceSqd == 0) {
569                     this->appendPointToContour(pts[2], contour);
570                     break;
571                 }
572                 SkScalar weight = iter.conicWeight();
573                 const SkPoint* quadPts = converter.computeQuads(pts, weight, toleranceSqd);
574                 for (int i = 0; i < converter.countQuads(); ++i) {
575                     this->appendQuadraticToContour(quadPts, toleranceSqd, contour);
576                     quadPts += 2;
577                 }
578                 break;
579             }
580             case SkPath::kMove_Verb:
581                 if (contour->fHead) {
582                     contour++;
583                 }
584                 this->appendPointToContour(pts[0], contour);
585                 break;
586             case SkPath::kLine_Verb: {
587                 this->appendPointToContour(pts[1], contour);
588                 break;
589             }
590             case SkPath::kQuad_Verb: {
591                 *isLinear = false;
592                 if (toleranceSqd == 0) {
593                     this->appendPointToContour(pts[2], contour);
594                     break;
595                 }
596                 this->appendQuadraticToContour(pts, toleranceSqd, contour);
597                 break;
598             }
599             case SkPath::kCubic_Verb: {
600                 *isLinear = false;
601                 if (toleranceSqd == 0) {
602                     this->appendPointToContour(pts[3], contour);
603                     break;
604                 }
605                 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance);
606                 this->generateCubicPoints(pts[0], pts[1], pts[2], pts[3], toleranceSqd, contour,
607                                           pointsLeft);
608                 break;
609             }
610             case SkPath::kClose_Verb:
611             case SkPath::kDone_Verb:
612                 break;
613         }
614     }
615 }
616 
apply_fill_type(SkPathFillType fillType,int winding)617 static inline bool apply_fill_type(SkPathFillType fillType, int winding) {
618     switch (fillType) {
619         case SkPathFillType::kWinding:
620             return winding != 0;
621         case SkPathFillType::kEvenOdd:
622             return (winding & 1) != 0;
623         case SkPathFillType::kInverseWinding:
624             return winding == 1;
625         case SkPathFillType::kInverseEvenOdd:
626             return (winding & 1) == 1;
627         default:
628             SkASSERT(false);
629             return false;
630     }
631 }
632 
applyFillType(int winding) const633 bool GrTriangulator::applyFillType(int winding) const {
634     return apply_fill_type(fPath.getFillType(), winding);
635 }
636 
apply_fill_type(SkPathFillType fillType,Poly * poly)637 static inline bool apply_fill_type(SkPathFillType fillType, Poly* poly) {
638     return poly && apply_fill_type(fillType, poly->fWinding);
639 }
640 
allocateMonotonePoly(Edge * edge,Side side,int winding)641 MonotonePoly* GrTriangulator::allocateMonotonePoly(Edge* edge, Side side, int winding) {
642     ++fNumMonotonePolys;
643     return fAlloc->make<MonotonePoly>(edge, side, winding);
644 }
645 
allocateEdge(Vertex * top,Vertex * bottom,int winding,EdgeType type)646 Edge* GrTriangulator::allocateEdge(Vertex* top, Vertex* bottom, int winding, EdgeType type) {
647     ++fNumEdges;
648     return fAlloc->make<Edge>(top, bottom, winding, type);
649 }
650 
makeEdge(Vertex * prev,Vertex * next,EdgeType type,const Comparator & c)651 Edge* GrTriangulator::makeEdge(Vertex* prev, Vertex* next, EdgeType type,
652                                const Comparator& c) {
653     SkASSERT(prev->fPoint != next->fPoint);
654     int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1;
655     Vertex* top = winding < 0 ? next : prev;
656     Vertex* bottom = winding < 0 ? prev : next;
657     return this->allocateEdge(top, bottom, winding, type);
658 }
659 
insert(Edge * edge,Edge * prev)660 bool EdgeList::insert(Edge* edge, Edge* prev) {
661     TESS_LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
662     // SkASSERT(!this->contains(edge));  // Leave this here for debugging.
663     if (this->contains(edge)) {
664         return false;
665     }
666     Edge* next = prev ? prev->fRight : fHead;
667     this->insert(edge, prev, next);
668     return true;
669 }
670 
FindEnclosingEdges(const Vertex & v,const EdgeList & edges,Edge ** left,Edge ** right)671 void GrTriangulator::FindEnclosingEdges(const Vertex& v,
672                                         const EdgeList& edges,
673                                         Edge** left, Edge**right) {
674     if (v.fFirstEdgeAbove && v.fLastEdgeAbove) {
675         *left = v.fFirstEdgeAbove->fLeft;
676         *right = v.fLastEdgeAbove->fRight;
677         return;
678     }
679     Edge* next = nullptr;
680     Edge* prev;
681     for (prev = edges.fTail; prev != nullptr; prev = prev->fLeft) {
682         if (prev->isLeftOf(v)) {
683             break;
684         }
685         next = prev;
686     }
687     *left = prev;
688     *right = next;
689 }
690 
insertAbove(Vertex * v,const Comparator & c)691 void GrTriangulator::Edge::insertAbove(Vertex* v, const Comparator& c) {
692     if (fTop->fPoint == fBottom->fPoint ||
693         c.sweep_lt(fBottom->fPoint, fTop->fPoint)) {
694         return;
695     }
696     TESS_LOG("insert edge (%g -> %g) above vertex %g\n", fTop->fID, fBottom->fID, v->fID);
697     Edge* prev = nullptr;
698     Edge* next;
699     for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) {
700         if (next->isRightOf(*fTop)) {
701             break;
702         }
703         prev = next;
704     }
705     list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
706         this, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
707 }
708 
insertBelow(Vertex * v,const Comparator & c)709 void GrTriangulator::Edge::insertBelow(Vertex* v, const Comparator& c) {
710     if (fTop->fPoint == fBottom->fPoint ||
711         c.sweep_lt(fBottom->fPoint, fTop->fPoint)) {
712         return;
713     }
714     TESS_LOG("insert edge (%g -> %g) below vertex %g\n", fTop->fID, fBottom->fID, v->fID);
715     Edge* prev = nullptr;
716     Edge* next;
717     for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) {
718         if (next->isRightOf(*fBottom)) {
719             break;
720         }
721         prev = next;
722     }
723     list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
724         this, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
725 }
726 
remove_edge_above(Edge * edge)727 static void remove_edge_above(Edge* edge) {
728     SkASSERT(edge->fTop && edge->fBottom);
729     TESS_LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
730              edge->fBottom->fID);
731     list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
732         edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
733 }
734 
remove_edge_below(Edge * edge)735 static void remove_edge_below(Edge* edge) {
736     SkASSERT(edge->fTop && edge->fBottom);
737     TESS_LOG("removing edge (%g -> %g) below vertex %g\n",
738              edge->fTop->fID, edge->fBottom->fID, edge->fTop->fID);
739     list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
740         edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
741 }
742 
disconnect()743 void GrTriangulator::Edge::disconnect() {
744     remove_edge_above(this);
745     remove_edge_below(this);
746 }
747 
rewind(EdgeList * activeEdges,Vertex ** current,Vertex * dst,const Comparator & c)748 static bool rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, const Comparator& c) {
749     if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) {
750         return true;
751     }
752     Vertex* v = *current;
753     TESS_LOG("rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID);
754     while (v != dst) {
755         v = v->fPrev;
756         for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
757             if (!activeEdges->remove(e)) {
758                 return false;
759             }
760         }
761         Edge* leftEdge = v->fLeftEnclosingEdge;
762         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
763             if (!activeEdges->insert(e, leftEdge)) {
764                 return false;
765             }
766             leftEdge = e;
767             Vertex* top = e->fTop;
768             if (c.sweep_lt(top->fPoint, dst->fPoint) &&
769                 ((top->fLeftEnclosingEdge && !top->fLeftEnclosingEdge->isLeftOf(*e->fTop)) ||
770                  (top->fRightEnclosingEdge && !top->fRightEnclosingEdge->isRightOf(*e->fTop)))) {
771                 dst = top;
772             }
773         }
774     }
775     *current = v;
776     return true;
777 }
778 
rewind_if_necessary(Edge * edge,EdgeList * activeEdges,Vertex ** current,const Comparator & c)779 static bool rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current,
780                                 const Comparator& c) {
781     if (!activeEdges || !current) {
782         return true;
783     }
784     if (!edge) {
785         return false;
786     }
787     Vertex* top = edge->fTop;
788     Vertex* bottom = edge->fBottom;
789     if (edge->fLeft) {
790         Vertex* leftTop = edge->fLeft->fTop;
791         Vertex* leftBottom = edge->fLeft->fBottom;
792         if (leftTop && leftBottom) {
793             if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(*top)) {
794                 if (!rewind(activeEdges, current, leftTop, c)) {
795                     return false;
796                 }
797             } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(*leftTop)) {
798                 if (!rewind(activeEdges, current, top, c)) {
799                     return false;
800                 }
801             } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
802                        !edge->fLeft->isLeftOf(*bottom)) {
803                 if (!rewind(activeEdges, current, leftTop, c)) {
804                     return false;
805                 }
806             } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) &&
807                        !edge->isRightOf(*leftBottom)) {
808                 if (!rewind(activeEdges, current, top, c)) {
809                     return false;
810                 }
811             }
812         }
813     }
814     if (edge->fRight) {
815         Vertex* rightTop = edge->fRight->fTop;
816         Vertex* rightBottom = edge->fRight->fBottom;
817         if (rightTop && rightBottom) {
818             if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(*top)) {
819                 if (!rewind(activeEdges, current, rightTop, c)) {
820                     return false;
821                 }
822             } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(*rightTop)) {
823                 if (!rewind(activeEdges, current, top, c)) {
824                     return false;
825                 }
826             } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
827                        !edge->fRight->isRightOf(*bottom)) {
828                 if (!rewind(activeEdges, current, rightTop, c)) {
829                     return false;
830                 }
831             } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
832                        !edge->isLeftOf(*rightBottom)) {
833                 if (!rewind(activeEdges, current, top, c)) {
834                     return false;
835                 }
836             }
837         }
838     }
839     return true;
840 }
841 
setTop(Edge * edge,Vertex * v,EdgeList * activeEdges,Vertex ** current,const Comparator & c) const842 bool GrTriangulator::setTop(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
843                             const Comparator& c) const {
844     remove_edge_below(edge);
845     if (fCollectBreadcrumbTriangles) {
846         fBreadcrumbList.append(fAlloc, edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
847                                edge->fWinding);
848     }
849     edge->fTop = v;
850     edge->recompute();
851     edge->insertBelow(v, c);
852     if (!rewind_if_necessary(edge, activeEdges, current, c)) {
853         return false;
854     }
855     return this->mergeCollinearEdges(edge, activeEdges, current, c);
856 }
857 
setBottom(Edge * edge,Vertex * v,EdgeList * activeEdges,Vertex ** current,const Comparator & c) const858 bool GrTriangulator::setBottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current,
859                                const Comparator& c) const {
860     remove_edge_above(edge);
861     if (fCollectBreadcrumbTriangles) {
862         fBreadcrumbList.append(fAlloc, edge->fTop->fPoint, edge->fBottom->fPoint, v->fPoint,
863                                edge->fWinding);
864     }
865     edge->fBottom = v;
866     edge->recompute();
867     edge->insertAbove(v, c);
868     if (!rewind_if_necessary(edge, activeEdges, current, c)) {
869         return false;
870     }
871     return this->mergeCollinearEdges(edge, activeEdges, current, c);
872 }
873 
mergeEdgesAbove(Edge * edge,Edge * other,EdgeList * activeEdges,Vertex ** current,const Comparator & c) const874 bool GrTriangulator::mergeEdgesAbove(Edge* edge, Edge* other, EdgeList* activeEdges,
875                                      Vertex** current, const Comparator& c) const {
876     if (!edge || !other) {
877         return false;
878     }
879     if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
880         TESS_LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
881                  edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
882                  edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
883         if (!rewind(activeEdges, current, edge->fTop, c)) {
884             return false;
885         }
886         other->fWinding += edge->fWinding;
887         edge->disconnect();
888         edge->fTop = edge->fBottom = nullptr;
889     } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
890         if (!rewind(activeEdges, current, edge->fTop, c)) {
891             return false;
892         }
893         other->fWinding += edge->fWinding;
894         if (!this->setBottom(edge, other->fTop, activeEdges, current, c)) {
895             return false;
896         }
897     } else {
898         if (!rewind(activeEdges, current, other->fTop, c)) {
899             return false;
900         }
901         edge->fWinding += other->fWinding;
902         if (!this->setBottom(other, edge->fTop, activeEdges, current, c)) {
903             return false;
904         }
905     }
906     return true;
907 }
908 
mergeEdgesBelow(Edge * edge,Edge * other,EdgeList * activeEdges,Vertex ** current,const Comparator & c) const909 bool GrTriangulator::mergeEdgesBelow(Edge* edge, Edge* other, EdgeList* activeEdges,
910                                      Vertex** current, const Comparator& c) const {
911     if (!edge || !other) {
912         return false;
913     }
914     if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
915         TESS_LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
916                  edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
917                  edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
918         if (!rewind(activeEdges, current, edge->fTop, c)) {
919             return false;
920         }
921         other->fWinding += edge->fWinding;
922         edge->disconnect();
923         edge->fTop = edge->fBottom = nullptr;
924     } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
925         if (!rewind(activeEdges, current, other->fTop, c)) {
926             return false;
927         }
928         edge->fWinding += other->fWinding;
929         if (!this->setTop(other, edge->fBottom, activeEdges, current, c)) {
930             return false;
931         }
932     } else {
933         if (!rewind(activeEdges, current, edge->fTop, c)) {
934             return false;
935         }
936         other->fWinding += edge->fWinding;
937         if (!this->setTop(edge, other->fBottom, activeEdges, current, c)) {
938             return false;
939         }
940     }
941     return true;
942 }
943 
top_collinear(Edge * left,Edge * right)944 static bool top_collinear(Edge* left, Edge* right) {
945     if (!left || !right) {
946         return false;
947     }
948     return left->fTop->fPoint == right->fTop->fPoint ||
949            !left->isLeftOf(*right->fTop) || !right->isRightOf(*left->fTop);
950 }
951 
bottom_collinear(Edge * left,Edge * right)952 static bool bottom_collinear(Edge* left, Edge* right) {
953     if (!left || !right) {
954         return false;
955     }
956     return left->fBottom->fPoint == right->fBottom->fPoint ||
957            !left->isLeftOf(*right->fBottom) || !right->isRightOf(*left->fBottom);
958 }
959 
960 // How deep of a stack of mergeCollinearEdges() we'll accept
961 static constexpr int kMaxMergeCollinearCalls = 64;
962 
mergeCollinearEdges(Edge * edge,EdgeList * activeEdges,Vertex ** current,const Comparator & c) const963 bool GrTriangulator::mergeCollinearEdges(Edge* edge, EdgeList* activeEdges, Vertex** current,
964                                          const Comparator& c) const {
965     // Stack is unreasonably deep
966     if (++fMergeCollinearStackCount > kMaxMergeCollinearCalls) {
967         return false;
968     }
969     for (;;) {
970         if (top_collinear(edge->fPrevEdgeAbove, edge)) {
971             if (!this->mergeEdgesAbove(edge->fPrevEdgeAbove, edge, activeEdges, current, c)) {
972                 return false;
973             }
974         } else if (top_collinear(edge, edge->fNextEdgeAbove)) {
975             if (!this->mergeEdgesAbove(edge->fNextEdgeAbove, edge, activeEdges, current, c)) {
976                 return false;
977             }
978         } else if (bottom_collinear(edge->fPrevEdgeBelow, edge)) {
979             if (!this->mergeEdgesBelow(edge->fPrevEdgeBelow, edge, activeEdges, current, c)) {
980                 return false;
981             }
982         } else if (bottom_collinear(edge, edge->fNextEdgeBelow)) {
983             if (!this->mergeEdgesBelow(edge->fNextEdgeBelow, edge, activeEdges, current, c)) {
984                 return false;
985             }
986         } else {
987             break;
988         }
989     }
990     SkASSERT(!top_collinear(edge->fPrevEdgeAbove, edge));
991     SkASSERT(!top_collinear(edge, edge->fNextEdgeAbove));
992     SkASSERT(!bottom_collinear(edge->fPrevEdgeBelow, edge));
993     SkASSERT(!bottom_collinear(edge, edge->fNextEdgeBelow));
994     return true;
995 }
996 
splitEdge(Edge * edge,Vertex * v,EdgeList * activeEdges,Vertex ** current,const Comparator & c)997 GrTriangulator::BoolFail GrTriangulator::splitEdge(
998         Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, const Comparator& c) {
999     if (!edge->fTop || !edge->fBottom || v == edge->fTop || v == edge->fBottom) {
1000         return BoolFail::kFalse;
1001     }
1002     TESS_LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
1003              edge->fTop->fID, edge->fBottom->fID, v->fID, v->fPoint.fX, v->fPoint.fY);
1004     Vertex* top;
1005     Vertex* bottom;
1006     int winding = edge->fWinding;
1007     // Theoretically, and ideally, the edge betwee p0 and p1 is being split by v, and v is "between"
1008     // the segment end points according to c. This is equivalent to p0 < v < p1.  Unfortunately, if
1009     // v was clamped/rounded this relation doesn't always hold.
1010     if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
1011         // Actually "v < p0 < p1": update 'edge' to be v->p1 and add v->p0. We flip the winding on
1012         // the new edge so that it winds as if it were p0->v.
1013         top = v;
1014         bottom = edge->fTop;
1015         winding *= -1;
1016         if (!this->setTop(edge, v, activeEdges, current, c)) {
1017             return BoolFail::kFail;
1018         }
1019     } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
1020         // Actually "p0 < p1 < v": update 'edge' to be p0->v and add p1->v. We flip the winding on
1021         // the new edge so that it winds as if it were v->p1.
1022         top = edge->fBottom;
1023         bottom = v;
1024         winding *= -1;
1025         if (!this->setBottom(edge, v, activeEdges, current, c)) {
1026             return BoolFail::kFail;
1027         }
1028     } else {
1029         // The ideal case, "p0 < v < p1": update 'edge' to be p0->v and add v->p1. Original winding
1030         // is valid for both edges.
1031         top = v;
1032         bottom = edge->fBottom;
1033         if (!this->setBottom(edge, v, activeEdges, current, c)) {
1034             return BoolFail::kFail;
1035         }
1036     }
1037     Edge* newEdge = this->allocateEdge(top, bottom, winding, edge->fType);
1038     newEdge->insertBelow(top, c);
1039     newEdge->insertAbove(bottom, c);
1040     fMergeCollinearStackCount = 0;
1041     if (!this->mergeCollinearEdges(newEdge, activeEdges, current, c)) {
1042         return BoolFail::kFail;
1043     }
1044     return BoolFail::kTrue;
1045 }
1046 
intersectEdgePair(Edge * left,Edge * right,EdgeList * activeEdges,Vertex ** current,const Comparator & c)1047 GrTriangulator::BoolFail GrTriangulator::intersectEdgePair(
1048         Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current, const Comparator& c) {
1049     if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) {
1050         return BoolFail::kFalse;
1051     }
1052     if (left->fTop == right->fTop || left->fBottom == right->fBottom) {
1053         return BoolFail::kFalse;
1054     }
1055 
1056     // Check if the lines intersect as determined by isLeftOf and isRightOf, since that is the
1057     // source of ground truth. It may suggest an intersection even if Edge::intersect() did not have
1058     // the precision to check it. In this case we are explicitly correcting the edge topology to
1059     // match the sided-ness checks.
1060     Edge* split = nullptr;
1061     Vertex* splitAt = nullptr;
1062     if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) {
1063         if (!left->isLeftOf(*right->fTop)) {
1064             split = left;
1065             splitAt = right->fTop;
1066         }
1067     } else {
1068         if (!right->isRightOf(*left->fTop)) {
1069             split = right;
1070             splitAt = left->fTop;
1071         }
1072     }
1073     if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) {
1074         if (!left->isLeftOf(*right->fBottom)) {
1075             split = left;
1076             splitAt = right->fBottom;
1077         }
1078     } else {
1079         if (!right->isRightOf(*left->fBottom)) {
1080             split = right;
1081             splitAt = left->fBottom;
1082         }
1083     }
1084 
1085     if (!split) {
1086         return BoolFail::kFalse;
1087     }
1088 
1089     // Rewind to the top of the edge that is "moving" since this topology correction can change the
1090     // geometry of the split edge.
1091     if (!rewind(activeEdges, current, split->fTop, c)) {
1092         return BoolFail::kFail;
1093     }
1094     return this->splitEdge(split, splitAt, activeEdges, current, c);
1095 }
1096 
makeConnectingEdge(Vertex * prev,Vertex * next,EdgeType type,const Comparator & c,int windingScale)1097 Edge* GrTriangulator::makeConnectingEdge(Vertex* prev, Vertex* next, EdgeType type,
1098                                          const Comparator& c, int windingScale) {
1099     if (!prev || !next || prev->fPoint == next->fPoint) {
1100         return nullptr;
1101     }
1102     Edge* edge = this->makeEdge(prev, next, type, c);
1103     edge->insertBelow(edge->fTop, c);
1104     edge->insertAbove(edge->fBottom, c);
1105     edge->fWinding *= windingScale;
1106     fMergeCollinearStackCount = 0;
1107     this->mergeCollinearEdges(edge, nullptr, nullptr, c);
1108     return edge;
1109 }
1110 
mergeVertices(Vertex * src,Vertex * dst,VertexList * mesh,const Comparator & c) const1111 void GrTriangulator::mergeVertices(Vertex* src, Vertex* dst, VertexList* mesh,
1112                                    const Comparator& c) const {
1113     TESS_LOG("found coincident verts at %g, %g; merging %g into %g\n",
1114              src->fPoint.fX, src->fPoint.fY, src->fID, dst->fID);
1115     dst->fAlpha = std::max(src->fAlpha, dst->fAlpha);
1116     if (src->fPartner) {
1117         src->fPartner->fPartner = dst;
1118     }
1119     // setBottom()/setTop() will call mergeCollinearEdges() but this can recurse,
1120     // so we need to clear the stack count here.
1121     while (Edge* edge = src->fFirstEdgeAbove) {
1122         fMergeCollinearStackCount = 0;
1123         std::ignore = this->setBottom(edge, dst, nullptr, nullptr, c);
1124     }
1125     while (Edge* edge = src->fFirstEdgeBelow) {
1126         fMergeCollinearStackCount = 0;
1127         std::ignore = this->setTop(edge, dst, nullptr, nullptr, c);
1128     }
1129     mesh->remove(src);
1130     dst->fSynthetic = true;
1131 }
1132 
makeSortedVertex(const SkPoint & p,uint8_t alpha,VertexList * mesh,Vertex * reference,const Comparator & c) const1133 Vertex* GrTriangulator::makeSortedVertex(const SkPoint& p, uint8_t alpha, VertexList* mesh,
1134                                          Vertex* reference, const Comparator& c) const {
1135     Vertex* prevV = reference;
1136     while (prevV && c.sweep_lt(p, prevV->fPoint)) {
1137         prevV = prevV->fPrev;
1138     }
1139     Vertex* nextV = prevV ? prevV->fNext : mesh->fHead;
1140     while (nextV && c.sweep_lt(nextV->fPoint, p)) {
1141         prevV = nextV;
1142         nextV = nextV->fNext;
1143     }
1144     Vertex* v;
1145     if (prevV && coincident(prevV->fPoint, p)) {
1146         v = prevV;
1147     } else if (nextV && coincident(nextV->fPoint, p)) {
1148         v = nextV;
1149     } else {
1150         v = fAlloc->make<Vertex>(p, alpha);
1151 #if TRIANGULATOR_LOGGING
1152         if (!prevV) {
1153             v->fID = mesh->fHead->fID - 1.0f;
1154         } else if (!nextV) {
1155             v->fID = mesh->fTail->fID + 1.0f;
1156         } else {
1157             v->fID = (prevV->fID + nextV->fID) * 0.5f;
1158         }
1159 #endif
1160         mesh->insert(v, prevV, nextV);
1161     }
1162     return v;
1163 }
1164 
1165 // Clamps x and y coordinates independently, so the returned point will lie within the bounding
1166 // box formed by the corners of 'min' and 'max' (although min/max here refer to the ordering
1167 // imposed by 'c').
clamp(SkPoint p,SkPoint min,SkPoint max,const Comparator & c)1168 static SkPoint clamp(SkPoint p, SkPoint min, SkPoint max, const Comparator& c) {
1169     if (c.fDirection == Comparator::Direction::kHorizontal) {
1170         // With horizontal sorting, we know min.x <= max.x, but there's no relation between
1171         // Y components unless min.x == max.x.
1172         return {SkTPin(p.fX, min.fX, max.fX),
1173                 min.fY < max.fY ? SkTPin(p.fY, min.fY, max.fY)
1174                                 : SkTPin(p.fY, max.fY, min.fY)};
1175     } else {
1176         // And with vertical sorting, we know Y's relation but not necessarily X's.
1177         return {min.fX < max.fX ? SkTPin(p.fX, min.fX, max.fX)
1178                                 : SkTPin(p.fX, max.fX, min.fX),
1179                 SkTPin(p.fY, min.fY, max.fY)};
1180     }
1181 }
1182 
computeBisector(Edge * edge1,Edge * edge2,Vertex * v) const1183 void GrTriangulator::computeBisector(Edge* edge1, Edge* edge2, Vertex* v) const {
1184     SkASSERT(fEmitCoverage);  // Edge-AA only!
1185     Line line1 = edge1->fLine;
1186     Line line2 = edge2->fLine;
1187     line1.normalize();
1188     line2.normalize();
1189     double cosAngle = line1.fA * line2.fA + line1.fB * line2.fB;
1190     if (cosAngle > 0.999) {
1191         return;
1192     }
1193     line1.fC += edge1->fWinding > 0 ? -1 : 1;
1194     line2.fC += edge2->fWinding > 0 ? -1 : 1;
1195     SkPoint p;
1196     if (line1.intersect(line2, &p)) {
1197         uint8_t alpha = edge1->fType == EdgeType::kOuter ? 255 : 0;
1198         v->fPartner = fAlloc->make<Vertex>(p, alpha);
1199         TESS_LOG("computed bisector (%g,%g) alpha %d for vertex %g\n", p.fX, p.fY, alpha, v->fID);
1200     }
1201 }
1202 
checkForIntersection(Edge * left,Edge * right,EdgeList * activeEdges,Vertex ** current,VertexList * mesh,const Comparator & c)1203 GrTriangulator::BoolFail GrTriangulator::checkForIntersection(
1204         Edge* left, Edge* right, EdgeList* activeEdges,
1205         Vertex** current, VertexList* mesh,
1206         const Comparator& c) {
1207     if (!left || !right) {
1208         return BoolFail::kFalse;
1209     }
1210     SkPoint p;
1211     uint8_t alpha;
1212     // If we are going to call intersect, then there must be tops and bottoms.
1213     if (!left->fTop || !left->fBottom || !right->fTop || !right->fBottom) {
1214         return BoolFail::kFail;
1215     }
1216     if (left->intersect(*right, &p, &alpha) && p.isFinite()) {
1217         Vertex* v;
1218         TESS_LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
1219         Vertex* top = *current;
1220         // If the intersection point is above the current vertex, rewind to the vertex above the
1221         // intersection.
1222         while (top && c.sweep_lt(p, top->fPoint)) {
1223             top = top->fPrev;
1224         }
1225 
1226         // Always clamp the intersection to lie between the vertices of each segment, since
1227         // in theory that's where the intersection is, but in reality, floating point error may
1228         // have computed an intersection beyond a vertex's component(s).
1229         p = clamp(p, left->fTop->fPoint, left->fBottom->fPoint, c);
1230         p = clamp(p, right->fTop->fPoint, right->fBottom->fPoint, c);
1231 
1232         if (coincident(p, left->fTop->fPoint)) {
1233             v = left->fTop;
1234         } else if (coincident(p, left->fBottom->fPoint)) {
1235             v = left->fBottom;
1236         } else if (coincident(p, right->fTop->fPoint)) {
1237             v = right->fTop;
1238         } else if (coincident(p, right->fBottom->fPoint)) {
1239             v = right->fBottom;
1240         } else {
1241             v = this->makeSortedVertex(p, alpha, mesh, top, c);
1242             if (left->fTop->fPartner) {
1243                 SkASSERT(fEmitCoverage);  // Edge-AA only!
1244                 v->fSynthetic = true;
1245                 this->computeBisector(left, right, v);
1246             }
1247         }
1248         if (!rewind(activeEdges, current, top ? top : v, c)) {
1249             return BoolFail::kFail;
1250         }
1251         if (this->splitEdge(left, v, activeEdges, current, c) == BoolFail::kFail) {
1252             return BoolFail::kFail;
1253         }
1254         if (this->splitEdge(right, v, activeEdges, current, c) == BoolFail::kFail) {
1255             return BoolFail::kFail;
1256         }
1257         v->fAlpha = std::max(v->fAlpha, alpha);
1258         return BoolFail::kTrue;
1259     }
1260     return this->intersectEdgePair(left, right, activeEdges, current, c);
1261 }
1262 
sanitizeContours(VertexList * contours,int contourCnt) const1263 void GrTriangulator::sanitizeContours(VertexList* contours, int contourCnt) const {
1264     for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
1265         SkASSERT(contour->fHead);
1266         Vertex* prev = contour->fTail;
1267         prev->fPoint.fX = double_to_clamped_scalar((double) prev->fPoint.fX);
1268         prev->fPoint.fY = double_to_clamped_scalar((double) prev->fPoint.fY);
1269         if (fRoundVerticesToQuarterPixel) {
1270             round(&prev->fPoint);
1271         }
1272         for (Vertex* v = contour->fHead; v;) {
1273             v->fPoint.fX = double_to_clamped_scalar((double) v->fPoint.fX);
1274             v->fPoint.fY = double_to_clamped_scalar((double) v->fPoint.fY);
1275             if (fRoundVerticesToQuarterPixel) {
1276                 round(&v->fPoint);
1277             }
1278             Vertex* next = v->fNext;
1279             Vertex* nextWrap = next ? next : contour->fHead;
1280             if (coincident(prev->fPoint, v->fPoint)) {
1281                 TESS_LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoint.fY);
1282                 contour->remove(v);
1283             } else if (!v->fPoint.isFinite()) {
1284                 TESS_LOG("vertex %g,%g non-finite; removing\n", v->fPoint.fX, v->fPoint.fY);
1285                 contour->remove(v);
1286             } else if (!fPreserveCollinearVertices &&
1287                        Line(prev->fPoint, nextWrap->fPoint).dist(v->fPoint) == 0.0) {
1288                 TESS_LOG("vertex %g,%g collinear; removing\n", v->fPoint.fX, v->fPoint.fY);
1289                 contour->remove(v);
1290             } else {
1291                 prev = v;
1292             }
1293             v = next;
1294         }
1295     }
1296 }
1297 
mergeCoincidentVertices(VertexList * mesh,const Comparator & c) const1298 bool GrTriangulator::mergeCoincidentVertices(VertexList* mesh, const Comparator& c) const {
1299     if (!mesh->fHead) {
1300         return false;
1301     }
1302     bool merged = false;
1303     for (Vertex* v = mesh->fHead->fNext; v;) {
1304         Vertex* next = v->fNext;
1305         if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) {
1306             v->fPoint = v->fPrev->fPoint;
1307         }
1308         if (coincident(v->fPrev->fPoint, v->fPoint)) {
1309             this->mergeVertices(v, v->fPrev, mesh, c);
1310             merged = true;
1311         }
1312         v = next;
1313     }
1314     return merged;
1315 }
1316 
1317 // Stage 2: convert the contours to a mesh of edges connecting the vertices.
1318 
buildEdges(VertexList * contours,int contourCnt,VertexList * mesh,const Comparator & c)1319 void GrTriangulator::buildEdges(VertexList* contours, int contourCnt, VertexList* mesh,
1320                                 const Comparator& c) {
1321     for (VertexList* contour = contours; contourCnt > 0; --contourCnt, ++contour) {
1322         Vertex* prev = contour->fTail;
1323         for (Vertex* v = contour->fHead; v;) {
1324             Vertex* next = v->fNext;
1325             this->makeConnectingEdge(prev, v, EdgeType::kInner, c);
1326             mesh->append(v);
1327             prev = v;
1328             v = next;
1329         }
1330     }
1331 }
1332 
1333 template <CompareFunc sweep_lt>
sorted_merge(VertexList * front,VertexList * back,VertexList * result)1334 static void sorted_merge(VertexList* front, VertexList* back, VertexList* result) {
1335     Vertex* a = front->fHead;
1336     Vertex* b = back->fHead;
1337     while (a && b) {
1338         if (sweep_lt(a->fPoint, b->fPoint)) {
1339             front->remove(a);
1340             result->append(a);
1341             a = front->fHead;
1342         } else {
1343             back->remove(b);
1344             result->append(b);
1345             b = back->fHead;
1346         }
1347     }
1348     result->append(*front);
1349     result->append(*back);
1350 }
1351 
SortedMerge(VertexList * front,VertexList * back,VertexList * result,const Comparator & c)1352 void GrTriangulator::SortedMerge(VertexList* front, VertexList* back, VertexList* result,
1353                                  const Comparator& c) {
1354     if (c.fDirection == Comparator::Direction::kHorizontal) {
1355         sorted_merge<sweep_lt_horiz>(front, back, result);
1356     } else {
1357         sorted_merge<sweep_lt_vert>(front, back, result);
1358     }
1359 #if TRIANGULATOR_LOGGING
1360     float id = 0.0f;
1361     for (Vertex* v = result->fHead; v; v = v->fNext) {
1362         v->fID = id++;
1363     }
1364 #endif
1365 }
1366 
1367 // Stage 3: sort the vertices by increasing sweep direction.
1368 
1369 template <CompareFunc sweep_lt>
merge_sort(VertexList * vertices)1370 static void merge_sort(VertexList* vertices) {
1371     Vertex* slow = vertices->fHead;
1372     if (!slow) {
1373         return;
1374     }
1375     Vertex* fast = slow->fNext;
1376     if (!fast) {
1377         return;
1378     }
1379     do {
1380         fast = fast->fNext;
1381         if (fast) {
1382             fast = fast->fNext;
1383             slow = slow->fNext;
1384         }
1385     } while (fast);
1386     VertexList front(vertices->fHead, slow);
1387     VertexList back(slow->fNext, vertices->fTail);
1388     front.fTail->fNext = back.fHead->fPrev = nullptr;
1389 
1390     merge_sort<sweep_lt>(&front);
1391     merge_sort<sweep_lt>(&back);
1392 
1393     vertices->fHead = vertices->fTail = nullptr;
1394     sorted_merge<sweep_lt>(&front, &back, vertices);
1395 }
1396 
1397 #if TRIANGULATOR_LOGGING
dump() const1398 void VertexList::dump() const {
1399     for (Vertex* v = fHead; v; v = v->fNext) {
1400         TESS_LOG("vertex %g (%g, %g) alpha %d", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
1401         if (Vertex* p = v->fPartner) {
1402             TESS_LOG(", partner %g (%g, %g) alpha %d\n",
1403                     p->fID, p->fPoint.fX, p->fPoint.fY, p->fAlpha);
1404         } else {
1405             TESS_LOG(", null partner\n");
1406         }
1407         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1408             TESS_LOG("  edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
1409         }
1410         for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1411             TESS_LOG("  edge %g -> %g, winding %d\n", e->fTop->fID, e->fBottom->fID, e->fWinding);
1412         }
1413     }
1414 }
1415 #endif
1416 
1417 #ifdef SK_DEBUG
validate_edge_pair(Edge * left,Edge * right,const Comparator & c)1418 static void validate_edge_pair(Edge* left, Edge* right, const Comparator& c) {
1419     if (!left || !right) {
1420         return;
1421     }
1422     if (left->fTop == right->fTop) {
1423         SkASSERT(left->isLeftOf(*right->fBottom));
1424         SkASSERT(right->isRightOf(*left->fBottom));
1425     } else if (c.sweep_lt(left->fTop->fPoint, right->fTop->fPoint)) {
1426         SkASSERT(left->isLeftOf(*right->fTop));
1427     } else {
1428         SkASSERT(right->isRightOf(*left->fTop));
1429     }
1430     if (left->fBottom == right->fBottom) {
1431         SkASSERT(left->isLeftOf(*right->fTop));
1432         SkASSERT(right->isRightOf(*left->fTop));
1433     } else if (c.sweep_lt(right->fBottom->fPoint, left->fBottom->fPoint)) {
1434         SkASSERT(left->isLeftOf(*right->fBottom));
1435     } else {
1436         SkASSERT(right->isRightOf(*left->fBottom));
1437     }
1438 }
1439 
validate_edge_list(EdgeList * edges,const Comparator & c)1440 static void validate_edge_list(EdgeList* edges, const Comparator& c) {
1441     Edge* left = edges->fHead;
1442     if (!left) {
1443         return;
1444     }
1445     for (Edge* right = left->fRight; right; right = right->fRight) {
1446         validate_edge_pair(left, right, c);
1447         left = right;
1448     }
1449 }
1450 #endif
1451 
1452 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges.
1453 
simplify(VertexList * mesh,const Comparator & c)1454 GrTriangulator::SimplifyResult GrTriangulator::simplify(VertexList* mesh,
1455                                                         const Comparator& c) {
1456     TESS_LOG("simplifying complex polygons\n");
1457 
1458     int initialNumEdges = fNumEdges;
1459     int initialNumVertices = 0;
1460     for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) {
1461         ++initialNumVertices;
1462     }
1463     int numSelfIntersections = 0;
1464 
1465     EdgeList activeEdges;
1466     auto result = SimplifyResult::kAlreadySimple;
1467     int numVisitedVertices = 0;
1468     for (Vertex* v = mesh->fHead; v != nullptr; v = v->fNext) {
1469         ++numVisitedVertices;
1470         if (!v->isConnected()) {
1471             continue;
1472         }
1473 
1474         // The max increase across all skps, svgs and gms with only the triangulating and SW path
1475         // renderers enabled and with the triangulator's maxVerbCount set to the Chrome value is
1476         // 17x.
1477         if (fNumEdges > 170*initialNumEdges) {
1478             return SimplifyResult::kFailed;
1479         }
1480 
1481         if (numVisitedVertices > 170*initialNumVertices) {
1482             return SimplifyResult::kFailed;
1483         }
1484 
1485         Edge* leftEnclosingEdge;
1486         Edge* rightEnclosingEdge;
1487         bool restartChecks;
1488         do {
1489             TESS_LOG("\nvertex %g: (%g,%g), alpha %d\n",
1490                      v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
1491             restartChecks = false;
1492             FindEnclosingEdges(*v, activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
1493             v->fLeftEnclosingEdge = leftEnclosingEdge;
1494             v->fRightEnclosingEdge = rightEnclosingEdge;
1495             if (v->fFirstEdgeBelow) {
1496                 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
1497                     BoolFail l = this->checkForIntersection(
1498                             leftEnclosingEdge, edge, &activeEdges, &v, mesh, c);
1499                     if (l == BoolFail::kFail) {
1500                         return SimplifyResult::kFailed;
1501                     }
1502                     if (l == BoolFail::kFalse) {
1503                         BoolFail r = this->checkForIntersection(
1504                                 edge, rightEnclosingEdge, &activeEdges, &v, mesh, c);
1505                         if (r == BoolFail::kFail) {
1506                             return SimplifyResult::kFailed;
1507                         }
1508                         if (r == BoolFail::kFalse) {
1509                             // Neither l and r are both false.
1510                             continue;
1511                         }
1512                     }
1513 
1514                     // Either l or r are true.
1515                     result = SimplifyResult::kFoundSelfIntersection;
1516                     restartChecks = true;
1517                     ++numSelfIntersections;
1518                     break;
1519                 }  // for
1520             } else {
1521                 BoolFail bf = this->checkForIntersection(
1522                         leftEnclosingEdge, rightEnclosingEdge, &activeEdges, &v, mesh, c);
1523                 if (bf == BoolFail::kFail) {
1524                     return SimplifyResult::kFailed;
1525                 }
1526                 if (bf == BoolFail::kTrue) {
1527                     result = SimplifyResult::kFoundSelfIntersection;
1528                     restartChecks = true;
1529                     ++numSelfIntersections;
1530                 }
1531             }
1532 
1533             // In pathological cases, a path can intersect itself millions of times. After 500,000
1534             // self-intersections are found, reject the path.
1535             if (numSelfIntersections > 500000) {
1536                 return SimplifyResult::kFailed;
1537             }
1538         } while (restartChecks);
1539 #ifdef SK_DEBUG
1540         validate_edge_list(&activeEdges, c);
1541 #endif
1542         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1543             if (!activeEdges.remove(e)) {
1544                 return SimplifyResult::kFailed;
1545             }
1546         }
1547         Edge* leftEdge = leftEnclosingEdge;
1548         for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1549             activeEdges.insert(e, leftEdge);
1550             leftEdge = e;
1551         }
1552     }
1553     SkASSERT(!activeEdges.fHead && !activeEdges.fTail);
1554     return result;
1555 }
1556 
1557 // Stage 5: Tessellate the simplified mesh into monotone polygons.
1558 
tessellate(const VertexList & vertices,const Comparator &)1559 std::tuple<Poly*, bool> GrTriangulator::tessellate(const VertexList& vertices, const Comparator&) {
1560     TESS_LOG("\ntessellating simple polygons\n");
1561     EdgeList activeEdges;
1562     Poly* polys = nullptr;
1563     for (Vertex* v = vertices.fHead; v != nullptr; v = v->fNext) {
1564         if (!v->isConnected()) {
1565             continue;
1566         }
1567 #if TRIANGULATOR_LOGGING
1568         TESS_LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
1569 #endif
1570         Edge* leftEnclosingEdge;
1571         Edge* rightEnclosingEdge;
1572         FindEnclosingEdges(*v, activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
1573         Poly* leftPoly;
1574         Poly* rightPoly;
1575         if (v->fFirstEdgeAbove) {
1576             leftPoly = v->fFirstEdgeAbove->fLeftPoly;
1577             rightPoly = v->fLastEdgeAbove->fRightPoly;
1578         } else {
1579             leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullptr;
1580             rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nullptr;
1581         }
1582 #if TRIANGULATOR_LOGGING
1583         TESS_LOG("edges above:\n");
1584         for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1585             TESS_LOG("%g -> %g, lpoly %d, rpoly %d\n",
1586                      e->fTop->fID, e->fBottom->fID,
1587                      e->fLeftPoly ? e->fLeftPoly->fID : -1,
1588                      e->fRightPoly ? e->fRightPoly->fID : -1);
1589         }
1590         TESS_LOG("edges below:\n");
1591         for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1592             TESS_LOG("%g -> %g, lpoly %d, rpoly %d\n",
1593                      e->fTop->fID, e->fBottom->fID,
1594                      e->fLeftPoly ? e->fLeftPoly->fID : -1,
1595                      e->fRightPoly ? e->fRightPoly->fID : -1);
1596         }
1597 #endif
1598         if (v->fFirstEdgeAbove) {
1599             if (leftPoly) {
1600                 leftPoly = leftPoly->addEdge(v->fFirstEdgeAbove, Side::kRight, this);
1601             }
1602             if (rightPoly) {
1603                 rightPoly = rightPoly->addEdge(v->fLastEdgeAbove, Side::kLeft, this);
1604             }
1605             for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
1606                 Edge* rightEdge = e->fNextEdgeAbove;
1607                 activeEdges.remove(e);
1608                 if (e->fRightPoly) {
1609                     e->fRightPoly->addEdge(e, Side::kLeft, this);
1610                 }
1611                 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != e->fRightPoly) {
1612                     rightEdge->fLeftPoly->addEdge(e, Side::kRight, this);
1613                 }
1614             }
1615             activeEdges.remove(v->fLastEdgeAbove);
1616             if (!v->fFirstEdgeBelow) {
1617                 if (leftPoly && rightPoly && leftPoly != rightPoly) {
1618                     SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartner == nullptr);
1619                     rightPoly->fPartner = leftPoly;
1620                     leftPoly->fPartner = rightPoly;
1621                 }
1622             }
1623         }
1624         if (v->fFirstEdgeBelow) {
1625             if (!v->fFirstEdgeAbove) {
1626                 if (leftPoly && rightPoly) {
1627                     if (leftPoly == rightPoly) {
1628                         if (leftPoly->fTail && leftPoly->fTail->fSide == Side::kLeft) {
1629                             leftPoly = this->makePoly(&polys, leftPoly->lastVertex(),
1630                                                       leftPoly->fWinding);
1631                             leftEnclosingEdge->fRightPoly = leftPoly;
1632                         } else {
1633                             rightPoly = this->makePoly(&polys, rightPoly->lastVertex(),
1634                                                        rightPoly->fWinding);
1635                             rightEnclosingEdge->fLeftPoly = rightPoly;
1636                         }
1637                     }
1638                     Edge* join = this->allocateEdge(leftPoly->lastVertex(), v, 1, EdgeType::kInner);
1639                     leftPoly = leftPoly->addEdge(join, Side::kRight, this);
1640                     rightPoly = rightPoly->addEdge(join, Side::kLeft, this);
1641                 }
1642             }
1643             Edge* leftEdge = v->fFirstEdgeBelow;
1644             leftEdge->fLeftPoly = leftPoly;
1645             activeEdges.insert(leftEdge, leftEnclosingEdge);
1646             for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
1647                  rightEdge = rightEdge->fNextEdgeBelow) {
1648                 activeEdges.insert(rightEdge, leftEdge);
1649                 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWinding : 0;
1650                 winding += leftEdge->fWinding;
1651                 if (winding != 0) {
1652                     Poly* poly = this->makePoly(&polys, v, winding);
1653                     leftEdge->fRightPoly = rightEdge->fLeftPoly = poly;
1654                 }
1655                 leftEdge = rightEdge;
1656             }
1657             v->fLastEdgeBelow->fRightPoly = rightPoly;
1658         }
1659 #if TRIANGULATOR_LOGGING
1660         TESS_LOG("\nactive edges:\n");
1661         for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
1662             TESS_LOG("%g -> %g, lpoly %d, rpoly %d\n",
1663                      e->fTop->fID, e->fBottom->fID,
1664                      e->fLeftPoly ? e->fLeftPoly->fID : -1,
1665                      e->fRightPoly ? e->fRightPoly->fID : -1);
1666         }
1667 #endif
1668     }
1669     return { polys, true };
1670 }
1671 
1672 // This is a driver function that calls stages 2-5 in turn.
1673 
contoursToMesh(VertexList * contours,int contourCnt,VertexList * mesh,const Comparator & c)1674 void GrTriangulator::contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh,
1675                                     const Comparator& c) {
1676 #if TRIANGULATOR_LOGGING
1677     for (int i = 0; i < contourCnt; ++i) {
1678         Vertex* v = contours[i].fHead;
1679         SkASSERT(v);
1680         TESS_LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1681         for (v = v->fNext; v; v = v->fNext) {
1682             TESS_LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY);
1683         }
1684     }
1685 #endif
1686     this->sanitizeContours(contours, contourCnt);
1687     this->buildEdges(contours, contourCnt, mesh, c);
1688 }
1689 
SortMesh(VertexList * vertices,const Comparator & c)1690 void GrTriangulator::SortMesh(VertexList* vertices, const Comparator& c) {
1691     if (!vertices || !vertices->fHead) {
1692         return;
1693     }
1694 
1695     // Sort vertices in Y (secondarily in X).
1696     if (c.fDirection == Comparator::Direction::kHorizontal) {
1697         merge_sort<sweep_lt_horiz>(vertices);
1698     } else {
1699         merge_sort<sweep_lt_vert>(vertices);
1700     }
1701 #if TRIANGULATOR_LOGGING
1702     for (Vertex* v = vertices->fHead; v != nullptr; v = v->fNext) {
1703         static float gID = 0.0f;
1704         v->fID = gID++;
1705     }
1706 #endif
1707 }
1708 
contoursToPolys(VertexList * contours,int contourCnt)1709 std::tuple<Poly*, bool> GrTriangulator::contoursToPolys(VertexList* contours, int contourCnt) {
1710     const SkRect& pathBounds = fPath.getBounds();
1711     Comparator c(pathBounds.width() > pathBounds.height() ? Comparator::Direction::kHorizontal
1712                                                           : Comparator::Direction::kVertical);
1713     VertexList mesh;
1714     this->contoursToMesh(contours, contourCnt, &mesh, c);
1715     TESS_LOG("\ninitial mesh:\n");
1716     DUMP_MESH(mesh);
1717     SortMesh(&mesh, c);
1718     TESS_LOG("\nsorted mesh:\n");
1719     DUMP_MESH(mesh);
1720     this->mergeCoincidentVertices(&mesh, c);
1721     TESS_LOG("\nsorted+merged mesh:\n");
1722     DUMP_MESH(mesh);
1723     auto result = this->simplify(&mesh, c);
1724     if (result == SimplifyResult::kFailed) {
1725         return { nullptr, false };
1726     }
1727     TESS_LOG("\nsimplified mesh:\n");
1728     DUMP_MESH(mesh);
1729     return this->tessellate(mesh, c);
1730 }
1731 
1732 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
polysToTriangles(Poly * polys,SkPathFillType overrideFillType,skgpu::VertexWriter data) const1733 skgpu::VertexWriter GrTriangulator::polysToTriangles(Poly* polys,
1734                                                      SkPathFillType overrideFillType,
1735                                                      skgpu::VertexWriter data) const {
1736     for (Poly* poly = polys; poly; poly = poly->fNext) {
1737         if (apply_fill_type(overrideFillType, poly)) {
1738             data = this->emitPoly(poly, std::move(data));
1739         }
1740     }
1741     return data;
1742 }
1743 
get_contour_count(const SkPath & path,SkScalar tolerance)1744 static int get_contour_count(const SkPath& path, SkScalar tolerance) {
1745     // We could theoretically be more aggressive about not counting empty contours, but we need to
1746     // actually match the exact number of contour linked lists the tessellator will create later on.
1747     int contourCnt = 1;
1748     bool hasPoints = false;
1749 
1750     SkPath::Iter iter(path, false);
1751     SkPath::Verb verb;
1752     SkPoint pts[4];
1753     bool first = true;
1754     while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1755         switch (verb) {
1756             case SkPath::kMove_Verb:
1757                 if (!first) {
1758                     ++contourCnt;
1759                 }
1760                 [[fallthrough]];
1761             case SkPath::kLine_Verb:
1762             case SkPath::kConic_Verb:
1763             case SkPath::kQuad_Verb:
1764             case SkPath::kCubic_Verb:
1765                 hasPoints = true;
1766                 break;
1767             default:
1768                 break;
1769         }
1770         first = false;
1771     }
1772     if (!hasPoints) {
1773         return 0;
1774     }
1775     return contourCnt;
1776 }
1777 
pathToPolys(float tolerance,const SkRect & clipBounds,bool * isLinear)1778 std::tuple<Poly*, bool> GrTriangulator::pathToPolys(float tolerance, const SkRect& clipBounds, bool* isLinear) {
1779     int contourCnt = get_contour_count(fPath, tolerance);
1780     if (contourCnt <= 0) {
1781         *isLinear = true;
1782         return { nullptr, true };
1783     }
1784 
1785     if (SkPathFillType_IsInverse(fPath.getFillType())) {
1786         contourCnt++;
1787     }
1788     std::unique_ptr<VertexList[]> contours(new VertexList[contourCnt]);
1789 
1790     this->pathToContours(tolerance, clipBounds, contours.get(), isLinear);
1791     return this->contoursToPolys(contours.get(), contourCnt);
1792 }
1793 
CountPoints(Poly * polys,SkPathFillType overrideFillType)1794 int64_t GrTriangulator::CountPoints(Poly* polys, SkPathFillType overrideFillType) {
1795     int64_t count = 0;
1796     for (Poly* poly = polys; poly; poly = poly->fNext) {
1797         if (apply_fill_type(overrideFillType, poly) && poly->fCount >= 3) {
1798             count += (poly->fCount - 2) * (TRIANGULATOR_WIREFRAME ? 6 : 3);
1799         }
1800     }
1801     return count;
1802 }
1803 
1804 // Stage 6: Triangulate the monotone polygons into a vertex buffer.
1805 
polysToTriangles(Poly * polys,GrEagerVertexAllocator * vertexAllocator) const1806 int GrTriangulator::polysToTriangles(Poly* polys, GrEagerVertexAllocator* vertexAllocator) const {
1807     int64_t count64 = CountPoints(polys, fPath.getFillType());
1808     if (0 == count64 || count64 > SK_MaxS32) {
1809         return 0;
1810     }
1811     int count = count64;
1812 
1813     size_t vertexStride = sizeof(SkPoint);
1814     if (fEmitCoverage) {
1815         vertexStride += sizeof(float);
1816     }
1817     skgpu::VertexWriter verts = vertexAllocator->lockWriter(vertexStride, count);
1818     if (!verts) {
1819         SkDebugf("Could not allocate vertices\n");
1820         return 0;
1821     }
1822 
1823     TESS_LOG("emitting %d verts\n", count);
1824 
1825     skgpu::BufferWriter::Mark start = verts.mark();
1826     verts = this->polysToTriangles(polys, fPath.getFillType(), std::move(verts));
1827 
1828     int actualCount = static_cast<int>((verts.mark() - start) / vertexStride);
1829     SkASSERT(actualCount <= count);
1830     vertexAllocator->unlock(actualCount);
1831     return actualCount;
1832 }
1833 
1834 #endif // SK_ENABLE_OPTIMIZE_SIZE
1835