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