1	// Copyright (C) 2023 The Qt Company Ltd.
2	// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4	#include "qsgcurveprocessor_p.h"
5
6	#include <QtGui/private/qtriangulator_p.h>
7	#include <QtCore/qloggingcategory.h>
8	#include <QtCore/qhash.h>
9
10	QT_BEGIN_NAMESPACE
11
12	Q_LOGGING_CATEGORY(lcSGCurveProcessor, "qt.quick.curveprocessor");
13	Q_LOGGING_CATEGORY(lcSGCurveIntersectionSolver, "qt.quick.curveprocessor.intersections");
14
15	namespace {
16	// Input coordinate space is pre-mapped so that (0, 0) maps to [0, 0] in uv space.
17	// v1 maps to [1,0], v2 maps to [0,1]. p is the point to be mapped to uv in this space (i.e. vector from p0)
18	static inline QVector2D uvForPoint(QVector2D v1, QVector2D v2, QVector2D p)
19	{
20	double divisor = v1.x() * v2.y() - v2.x() * v1.y();
21
22	float u = (p.x() * v2.y() - p.y() * v2.x()) / divisor;
23	float v = (p.y() * v1.x() - p.x() * v1.y()) / divisor;
24
25	return {u, v};
26	}
27
28	// Find uv coordinates for the point p, for a quadratic curve from p0 to p2 with control point p1
29	// also works for a line from p0 to p2, where p1 is on the inside of the path relative to the line
30	static inline QVector2D curveUv(QVector2D p0, QVector2D p1, QVector2D p2, QVector2D p)
31	{
32	QVector2D v1 = 2 * (p1 - p0);
33	QVector2D v2 = p2 - v1 - p0;
34	return uvForPoint(v1, v2, p: p - p0);
35	}
36
37	static QVector3D elementUvForPoint(const QQuadPath::Element& e, QVector2D p)
38	{
39	auto uv = curveUv(p0: e.startPoint(), p1: e.referencePoint(), p2: e.endPoint(), p);
40	if (e.isLine())
41	return { uv.x(), uv.y(), 0.0f };
42	else
43	return { uv.x(), uv.y(), e.isConvex() ? -1.0f : 1.0f };
44	}
45
46	static inline QVector2D calcNormalVector(QVector2D a, QVector2D b)
47	{
48	auto v = b - a;
49	return {v.y(), -v.x()};
50	}
51
52	// The sign of the return value indicates which side of the line defined by a and n the point p falls
53	static inline float testSideOfLineByNormal(QVector2D a, QVector2D n, QVector2D p)
54	{
55	float dot = QVector2D::dotProduct(v1: p - a, v2: n);
56	return dot;
57	};
58
59	static inline float determinant(const QVector2D &p1, const QVector2D &p2, const QVector2D &p3)
60	{
61	return p1.x() * (p2.y() - p3.y())
62	+ p2.x() * (p3.y() - p1.y())
63	+ p3.x() * (p1.y() - p2.y());
64	}
65
66	/*
67	Clever triangle overlap algorithm. Stack Overflow says:
68
69	You can prove that the two triangles do not collide by finding an edge (out of the total 6
70	edges that make up the two triangles) that acts as a separating line where all the vertices
71	of one triangle lie on one side and the vertices of the other triangle lie on the other side.
72	If you can find such an edge then it means that the triangles do not intersect otherwise the
73	triangles are colliding.
74	*/
75	using TrianglePoints = std::array<QVector2D, 3>;
76	using LinePoints = std::array<QVector2D, 2>;
77
78	// The sign of the determinant tells the winding order: positive means counter-clockwise
79
80	static inline double determinant(const TrianglePoints &p)
81	{
82	return determinant(p1: p[0], p2: p[1], p3: p[2]);
83	}
84
85	// Fix the triangle so that the determinant is positive
86	static void fixWinding(TrianglePoints &p)
87	{
88	double det = determinant(p);
89	if (det < 0.0) {
90	qSwap(value1&: p[0], value2&: p[1]);
91	}
92	}
93
94	// Return true if the determinant is negative, i.e. if the winding order is opposite of the triangle p1,p2,p3.
95	// This means that p is strictly on the other side of p1-p2 relative to p3 [where p1,p2,p3 is a triangle with
96	// a positive determinant].
97	bool checkEdge(const QVector2D &p1, const QVector2D &p2, const QVector2D &p, float epsilon)
98	{
99	return determinant(p1, p2, p3: p) <= epsilon;
100	}
101
102	// Check if lines l1 and l2 are intersecting and return the respective value. Solutions are stored to
103	// the optional pointer solution.
104	bool lineIntersection(const LinePoints &l1, const LinePoints &l2, QList<QPair<float, float>> *solution = nullptr)
105	{
106	constexpr double eps2 = 1e-5; // Epsilon for parameter space t1-t2
107
108	// see https://www.wolframalpha.com/input?i=solve%28A+%2B+t+*+B+%3D+C+%2B+s*D%3B+E+%2B+t+*+F+%3D+G+%2B+s+*+H+for+s+and+t%29
109	const float A = l1[0].x();
110	const float B = l1[1].x() - l1[0].x();
111	const float C = l2[0].x();
112	const float D = l2[1].x() - l2[0].x();
113	const float E = l1[0].y();
114	const float F = l1[1].y() - l1[0].y();
115	const float G = l2[0].y();
116	const float H = l2[1].y() - l2[0].y();
117
118	float det = D * F - B * H;
119
120	if (det == 0)
121	return false;
122
123	float s = (F * (A - C) - B * (E - G)) / det;
124	float t = (H * (A - C) - D * (E - G)) / det;
125
126	// Intersections at 0 count. Intersections at 1 do not.
127	bool intersecting = (s >= 0 && s <= 1. - eps2 && t >= 0 && t <= 1. - eps2);
128
129	if (solution && intersecting)
130	solution->append(t: QPair<float, float>(t, s));
131
132	return intersecting;
133	}
134
135
136	bool checkTriangleOverlap(TrianglePoints &triangle1, TrianglePoints &triangle2, float epsilon = 1.0/32)
137	{
138	// See if there is an edge of triangle1 such that all vertices in triangle2 are on the opposite side
139	fixWinding(p&: triangle1);
140	for (int i = 0; i < 3; i++) {
141	int ni = (i + 1) % 3;
142	if (checkEdge(p1: triangle1[i], p2: triangle1[ni], p: triangle2[0], epsilon) &&
143	checkEdge(p1: triangle1[i], p2: triangle1[ni], p: triangle2[1], epsilon) &&
144	checkEdge(p1: triangle1[i], p2: triangle1[ni], p: triangle2[2], epsilon))
145	return false;
146	}
147
148	// See if there is an edge of triangle2 such that all vertices in triangle1 are on the opposite side
149	fixWinding(p&: triangle2);
150	for (int i = 0; i < 3; i++) {
151	int ni = (i + 1) % 3;
152
153	if (checkEdge(p1: triangle2[i], p2: triangle2[ni], p: triangle1[0], epsilon) &&
154	checkEdge(p1: triangle2[i], p2: triangle2[ni], p: triangle1[1], epsilon) &&
155	checkEdge(p1: triangle2[i], p2: triangle2[ni], p: triangle1[2], epsilon))
156	return false;
157	}
158
159	return true;
160	}
161
162	bool checkLineTriangleOverlap(TrianglePoints &triangle, LinePoints &line, float epsilon = 1.0/32)
163	{
164	// See if all vertices of the triangle are on the same side of the line
165	bool s1 = determinant(p1: line[0], p2: line[1], p3: triangle[0]) < 0;
166	bool s2 = determinant(p1: line[0], p2: line[1], p3: triangle[1]) < 0;
167	bool s3 = determinant(p1: line[0], p2: line[1], p3: triangle[2]) < 0;
168	// If all determinants have the same sign, then there is no overlap
169	if (s1 == s2 && s2 == s3) {
170	return false;
171	}
172	// See if there is an edge of triangle1 such that both vertices in line are on the opposite side
173	fixWinding(p&: triangle);
174	for (int i = 0; i < 3; i++) {
175	int ni = (i + 1) % 3;
176	if (checkEdge(p1: triangle[i], p2: triangle[ni], p: line[0], epsilon) &&
177	checkEdge(p1: triangle[i], p2: triangle[ni], p: line[1], epsilon))
178	return false;
179	}
180
181	return true;
182	}
183
184	static bool isOverlap(const QQuadPath &path, int e1, int e2)
185	{
186	const QQuadPath::Element &element1 = path.elementAt(i: e1);
187	const QQuadPath::Element &element2 = path.elementAt(i: e2);
188
189	if (element1.isLine()) {
190	LinePoints line1{ element1.startPoint(), element1.endPoint() };
191	if (element2.isLine()) {
192	LinePoints line2{ element2.startPoint(), element2.endPoint() };
193	return lineIntersection(l1: line1, l2: line2);
194	} else {
195	TrianglePoints t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
196	return checkLineTriangleOverlap(triangle&: t2, line&: line1);
197	}
198	} else {
199	TrianglePoints t1{ element1.startPoint(), element1.controlPoint(), element1.endPoint() };
200	if (element2.isLine()) {
201	LinePoints line{ element2.startPoint(), element2.endPoint() };
202	return checkLineTriangleOverlap(triangle&: t1, line);
203	} else {
204	TrianglePoints t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
205	return checkTriangleOverlap(triangle1&: t1, triangle2&: t2);
206	}
207	}
208
209	return false;
210	}
211
212	static float angleBetween(const QVector2D v1, const QVector2D v2)
213	{
214	float dot = v1.x() * v2.x() + v1.y() * v2.y();
215	float cross = v1.x() * v2.y() - v1.y() * v2.x();
216	//TODO: Optimization: Maybe we don't need the atan2 here.
217	return atan2(y: cross, x: dot);
218	}
219
220	static bool isIntersecting(const TrianglePoints &t1, const TrianglePoints &t2, QList<QPair<float, float>> *solutions = nullptr)
221	{
222	constexpr double eps = 1e-5; // Epsilon for coordinate space x-y
223	constexpr double eps2 = 1e-5; // Epsilon for parameter space t1-t2
224	constexpr int maxIterations = 7; // Maximum iterations allowed for Newton
225
226	// Convert to double to get better accuracy.
227	QPointF td1[3] = { t1[0].toPointF(), t1[1].toPointF(), t1[2].toPointF() };
228	QPointF td2[3] = { t2[0].toPointF(), t2[1].toPointF(), t2[2].toPointF() };
229
230	// F = P1(t1) - P2(t2) where P1 and P2 are bezier curve functions.
231	// F = (0, 0) at the intersection.
232	// t is the vector of bezier curve parameters for curves P1 and P2
233	auto F = [=](QPointF t) { return
234	td1[0] * (1 - t.x()) * (1. - t.x()) + 2 * td1[1] * (1. - t.x()) * t.x() + td1[2] * t.x() * t.x() -
235	td2[0] * (1 - t.y()) * (1. - t.y()) - 2 * td2[1] * (1. - t.y()) * t.y() - td2[2] * t.y() * t.y();};
236
237	// J is the Jacobi Matrix dF/dt where F and t are both vectors of dimension 2.
238	// Storing in a QLineF for simplicity.
239	auto J = [=](QPointF t) { return QLineF(
240	td1[0].x() * (-2 * (1-t.x())) + 2 * td1[1].x() * (1 - 2 * t.x()) + td1[2].x() * 2 * t.x(),
241	-td2[0].x() * (-2 * (1-t.y())) - 2 * td2[1].x() * (1 - 2 * t.y()) - td2[2].x() * 2 * t.y(),
242	td1[0].y() * (-2 * (1-t.x())) + 2 * td1[1].y() * (1 - 2 * t.x()) + td1[2].y() * 2 * t.x(),
243	-td2[0].y() * (-2 * (1-t.y())) - 2 * td2[1].y() * (1 - 2 * t.y()) - td2[2].y() * 2 * t.y());};
244
245	// solve the equation A(as 2x2 matrix)*x = b. Returns x.
246	auto solve = [](QLineF A, QPointF b) {
247	// invert A
248	const double det = A.x1() * A.y2() - A.y1() * A.x2();
249	QLineF Ainv(A.y2() / det, -A.y1() / det, -A.x2() / det, A.x1() / det);
250	// return A^-1 * b
251	return QPointF(Ainv.x1() * b.x() + Ainv.y1() * b.y(),
252	Ainv.x2() * b.x() + Ainv.y2() * b.y());
253	};
254
255	#ifdef INTERSECTION_EXTRA_DEBUG
256	qCDebug(lcSGCurveIntersectionSolver) << "Checking" << t1[0] << t1[1] << t1[2];
257	qCDebug(lcSGCurveIntersectionSolver) << " vs" << t2[0] << t2[1] << t2[2];
258	#endif
259
260	// TODO: Try to figure out reasonable starting points to reach all 4 possible intersections.
261	// This works but is kinda brute forcing it.
262	constexpr std::array tref = { QPointF{0.0, 0.0}, QPointF{0.5, 0.0}, QPointF{1.0, 0.0},
263	QPointF{0.0, 0.5}, QPointF{0.5, 0.5}, QPointF{1.0, 0.5},
264	QPointF{0.0, 1.0}, QPointF{0.5, 1.0}, QPointF{1.0, 1.0} };
265
266	for (auto t : tref) {
267	double err = 1;
268	QPointF fval = F(t);
269	int i = 0;
270
271	// TODO: Try to abort sooner, e.g. when falling out of the interval [0-1]?
272	while (err > eps && i < maxIterations) { // && t.x() >= 0 && t.x() <= 1 && t.y() >= 0 && t.y() <= 1) {
273	t = t - solve(J(t), fval);
274	fval = F(t);
275	err = qAbs(t: fval.x()) + qAbs(t: fval.y()); // Using the Manhatten length as an error indicator.
276	i++;
277	#ifdef INTERSECTION_EXTRA_DEBUG
278	qCDebug(lcSGCurveIntersectionSolver) << " Newton iteration" << i << "t =" << t << "F =" << fval << "Error =" << err;
279	#endif
280	}
281	// Intersections at 0 count. Intersections at 1 do not.
282	if (err < eps && t.x() >=0 && t.x() <= 1. - 10 * eps2 && t.y() >= 0 && t.y() <= 1. - 10 * eps2) {
283	#ifdef INTERSECTION_EXTRA_DEBUG
284	qCDebug(lcSGCurveIntersectionSolver) << " Newton solution (after" << i << ")=" << t << "(" << F(t) << ")";
285	#endif
286	if (solutions) {
287	bool append = true;
288	for (auto solution : *solutions) {
289	if (qAbs(t: solution.first - t.x()) < 10 * eps2 && qAbs(t: solution.second - t.y()) < 10 * eps2) {
290	append = false;
291	break;
292	}
293	}
294	if (append)
295	solutions->append(t: {t.x(), t.y()});
296	}
297	else
298	return true;
299	}
300	}
301	if (solutions)
302	return solutions->size() > 0;
303	else
304	return false;
305	}
306
307	static bool isIntersecting(const QQuadPath &path, int e1, int e2, QList<QPair<float, float>> *solutions = nullptr)
308	{
309
310	const QQuadPath::Element &elem1 = path.elementAt(i: e1);
311	const QQuadPath::Element &elem2 = path.elementAt(i: e2);
312
313	if (elem1.isLine() && elem2.isLine()) {
314	return lineIntersection(l1: LinePoints {elem1.startPoint(), elem1.endPoint() },
315	l2: LinePoints {elem2.startPoint(), elem2.endPoint() },
316	solution: solutions);
317	} else {
318	return isIntersecting(t1: TrianglePoints { elem1.startPoint(), elem1.controlPoint(), elem1.endPoint() },
319	t2: TrianglePoints { elem2.startPoint(), elem2.controlPoint(), elem2.endPoint() },
320	solutions);
321	}
322	}
323
324	struct TriangleData
325	{
326	TrianglePoints points;
327	int pathElementIndex;
328	TrianglePoints normals;
329	};
330
331	// Returns a normalized vector that is perpendicular to baseLine, pointing to the right
332	inline QVector2D normalVector(QVector2D baseLine)
333	{
334	QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()).normalized();
335	return normal;
336	}
337
338	// Returns a vector that is normal to the path and pointing to the right. If endSide is false
339	// the vector is normal to the start point, otherwise to the end point
340	QVector2D normalVector(const QQuadPath::Element &element, bool endSide = false)
341	{
342	if (element.isLine())
343	return normalVector(baseLine: element.endPoint() - element.startPoint());
344	else if (!endSide)
345	return normalVector(baseLine: element.controlPoint() - element.startPoint());
346	else
347	return normalVector(baseLine: element.endPoint() - element.controlPoint());
348	}
349
350	// Returns a vector that is parallel to the path. If endSide is false
351	// the vector starts at the start point and points forward,
352	// otherwise it starts at the end point and points backward
353	QVector2D tangentVector(const QQuadPath::Element &element, bool endSide = false)
354	{
355	if (element.isLine()) {
356	if (!endSide)
357	return element.endPoint() - element.startPoint();
358	else
359	return element.startPoint() - element.endPoint();
360	} else {
361	if (!endSide)
362	return element.controlPoint() - element.startPoint();
363	else
364	return element.controlPoint() - element.endPoint();
365	}
366	}
367
368	// Really simplistic O(n^2) triangulator - only intended for five points
369	QList<TriangleData> simplePointTriangulator(const QList<QVector2D> &pts, const QList<QVector2D> &normals, int elementIndex)
370	{
371	int count = pts.size();
372	Q_ASSERT(count >= 3);
373	Q_ASSERT(normals.size() == count);
374
375	// First we find the convex hull: it's always in positive determinant winding order
376	QList<int> hull;
377	float det1 = determinant(p1: pts[0], p2: pts[1], p3: pts[2]);
378	if (det1 > 0)
379	hull << 0 << 1 << 2;
380	else
381	hull << 2 << 1 << 0;
382	auto connectableInHull = [&](int idx) -> QList<int> {
383	QList<int> r;
384	const int n = hull.size();
385	const auto &pt = pts[idx];
386	for (int i = 0; i < n; ++i) {
387	const auto &i1 = hull.at(i);
388	const auto &i2 = hull.at(i: (i+1) % n);
389	if (determinant(p1: pts[i1], p2: pts[i2], p3: pt) < 0.0f)
390	r << i;
391	}
392	return r;
393	};
394	for (int i = 3; i < count; ++i) {
395	auto visible = connectableInHull(i);
396	if (visible.isEmpty())
397	continue;
398	int visCount = visible.count();
399	int hullCount = hull.count();
400	// Find where the visible part of the hull starts. (This is the part we need to triangulate to,
401	// and the part we're going to replace. "visible" contains the start point of the line segments that are visible from p.
402	int boundaryStart = visible[0];
403	for (int j = 0; j < visCount - 1; ++j) {
404	if ((visible[j] + 1) % hullCount != visible[j+1]) {
405	boundaryStart = visible[j + 1];
406	break;
407	}
408	}
409	// Finally replace the points that are now inside the hull
410	// We insert the new point after boundaryStart, and before boundaryStart + visCount (modulo...)
411	// and remove the points in between
412	int pointsToKeep = hullCount - visCount + 1;
413	QList<int> newHull;
414	newHull << i;
415	for (int j = 0; j < pointsToKeep; ++j) {
416	newHull << hull.at(i: (j + boundaryStart + visCount) % hullCount);
417	}
418	hull = newHull;
419	}
420
421	// Now that we have a convex hull, we can trivially triangulate it
422	QList<TriangleData> ret;
423	for (int i = 1; i < hull.size() - 1; ++i) {
424	int i0 = hull[0];
425	int i1 = hull[i];
426	int i2 = hull[i+1];
427	ret.append(t: {.points: {pts[i0], pts[i1], pts[i2]}, .pathElementIndex: elementIndex, .normals: {normals[i0], normals[i1], normals[i2]}});
428	}
429	return ret;
430	}
431
432
433	inline bool needsSplit(const QQuadPath::Element &el)
434	{
435	Q_ASSERT(!el.isLine());
436	const auto v1 = el.controlPoint() - el.startPoint();
437	const auto v2 = el.endPoint() - el.controlPoint();
438	float cos = QVector2D::dotProduct(v1, v2) / (v1.length() * v2.length());
439	return cos < 0.9;
440	}
441
442
443	inline void splitElementIfNecessary(QQuadPath *path, int index, int level) {
444	if (level > 0 && needsSplit(el: path->elementAt(i: index))) {
445	path->splitElementAt(index);
446	splitElementIfNecessary(path, index: path->indexOfChildAt(i: index, childNumber: 0), level: level - 1);
447	splitElementIfNecessary(path, index: path->indexOfChildAt(i: index, childNumber: 1), level: level - 1);
448	}
449	}
450
451	static QQuadPath subdivide(const QQuadPath &path, int subdivisions)
452	{
453	QQuadPath newPath = path;
454	newPath.iterateElements(lambda: [&](QQuadPath::Element &e, int index) {
455	if (!e.isLine())
456	splitElementIfNecessary(path: &newPath, index, level: subdivisions);
457	});
458
459	return newPath;
460	}
461
462	static QList<TriangleData> customTriangulator2(const QQuadPath &path, float penWidth, Qt::PenJoinStyle joinStyle, Qt::PenCapStyle capStyle, float miterLimit)
463	{
464	const bool bevelJoin = joinStyle == Qt::BevelJoin;
465	const bool roundJoin = joinStyle == Qt::RoundJoin;
466	const bool miterJoin = !bevelJoin && !roundJoin;
467
468	const bool roundCap = capStyle == Qt::RoundCap;
469	const bool squareCap = capStyle == Qt::SquareCap;
470	// We can't use the simple miter for miter joins, since the shader currently only supports round joins
471	const bool simpleMiter = joinStyle == Qt::RoundJoin;
472
473	Q_ASSERT(miterLimit > 0 || !miterJoin);
474	float inverseMiterLimit = miterJoin ? 1.0f / miterLimit : 1.0;
475
476	const float penFactor = penWidth / 2;
477
478	// Returns {inner1, inner2, outer1, outer2, outerMiter}
479	// where foo1 is for the end of element1 and foo2 is for the start of element2
480	// and inner1 == inner2 unless we had to give up finding a decent point
481	auto calculateJoin = [&](const QQuadPath::Element *element1, const QQuadPath::Element *element2,
482	bool &outerBisectorWithinMiterLimit, bool &innerIsRight, bool &giveUp) -> std::array<QVector2D, 5>
483	{
484	outerBisectorWithinMiterLimit = true;
485	innerIsRight = true;
486	giveUp = false;
487	if (!element1) {
488	Q_ASSERT(element2);
489	QVector2D n = normalVector(element: *element2);
490	return {n, n, -n, -n, -n};
491	}
492	if (!element2) {
493	Q_ASSERT(element1);
494	QVector2D n = normalVector(element: *element1, endSide: true);
495	return {n, n, -n, -n, -n};
496	}
497
498	Q_ASSERT(element1->endPoint() == element2->startPoint());
499
500	const auto p1 = element1->isLine() ? element1->startPoint() : element1->controlPoint();
501	const auto p2 = element1->endPoint();
502	const auto p3 = element2->isLine() ? element2->endPoint() : element2->controlPoint();
503
504	const auto v1 = (p1 - p2).normalized();
505	const auto v2 = (p3 - p2).normalized();
506	const auto b = (v1 + v2);
507
508	constexpr float epsilon = 1.0f / 32.0f;
509	bool smoothJoin = qAbs(t: b.x()) < epsilon && qAbs(t: b.y()) < epsilon;
510
511	if (smoothJoin) {
512	// v1 and v2 are almost parallel and pointing in opposite directions
513	// angle bisector formula will give an almost null vector: use normal of bisector of normals instead
514	QVector2D n1(-v1.y(), v1.x());
515	QVector2D n2(-v2.y(), v2.x());
516	QVector2D n = (n2 - n1).normalized();
517	return {n, n, -n, -n, -n};
518	}
519	// Calculate the length of the bisector, so it will cover the entire miter.
520	// Using the identity sin(x/2) == sqrt((1 - cos(x)) / 2), and the fact that the
521	// dot product of two unit vectors is the cosine of the angle between them
522	// The length of the miter is w/sin(x/2) where x is the angle between the two elements
523
524	const auto bisector = b.normalized();
525	float cos2x = QVector2D::dotProduct(v1, v2);
526	cos2x = qMin(a: 1.0f, b: cos2x); // Allow for float inaccuracy
527	float sine = sqrt(x: (1.0f - cos2x) / 2);
528	innerIsRight = determinant(p1, p2, p3) > 0;
529	sine = qMax(a: sine, b: 0.01f); // Avoid divide by zero
530	float length = penFactor / sine;
531
532	// Check if bisector is longer than one of the lines it's trying to bisect
533
534	auto tooLong = [](QVector2D p1, QVector2D p2, QVector2D n, float length, float margin) -> bool {
535	auto v = p2 - p1;
536	// It's too long if the projection onto the bisector is longer than the bisector
537	// and the projection onto the normal to the bisector is shorter
538	// than the pen margin (that projection is just v - proj)
539	// (we're adding a 10% safety margin to make room for AA -- not exact)
540	auto projLen = QVector2D::dotProduct(v1: v, v2: n);
541	return projLen * 0.9f < length && (v - n * projLen).length() * 0.9 < margin;
542	};
543
544
545	// The angle bisector of the tangent lines is not correct for curved lines. We could fix this by calculating
546	// the exact intersection point, but for now just give up and use the normals.
547
548	giveUp = !element1->isLine() || !element2->isLine()
549	|| tooLong(p1, p2, bisector, length, penFactor)
550	|| tooLong(p3, p2, bisector, length, penFactor);
551	outerBisectorWithinMiterLimit = sine >= inverseMiterLimit / 2.0f;
552	bool simpleJoin = simpleMiter && outerBisectorWithinMiterLimit && !giveUp;
553	const QVector2D bn = bisector / sine;
554
555	if (simpleJoin)
556	return {bn, bn, -bn, -bn, -bn}; // We only have one inner and one outer point TODO: change inner point when conflict/curve
557	const QVector2D n1 = normalVector(element: *element1, endSide: true);
558	const QVector2D n2 = normalVector(element: *element2);
559	if (giveUp) {
560	if (innerIsRight)
561	return {n1, n2, -n1, -n2, -bn};
562	else
563	return {-n1, -n2, n1, n2, -bn};
564
565	} else {
566	if (innerIsRight)
567	return {bn, bn, -n1, -n2, -bn};
568	else
569	return {bn, bn, n1, n2, -bn};
570	}
571	};
572
573	QList<TriangleData> ret;
574
575	auto triangulateCurve = [&](int idx, const QVector2D &p1, const QVector2D &p2, const QVector2D &p3, const QVector2D &p4,
576	const QVector2D &n1, const QVector2D &n2, const QVector2D &n3, const QVector2D &n4)
577	{
578	const auto &element = path.elementAt(i: idx);
579	Q_ASSERT(!element.isLine());
580	const auto &s = element.startPoint();
581	const auto &c = element.controlPoint();
582	const auto &e = element.endPoint();
583	// TODO: Don't flatten the path in addCurveStrokeNodes, but iterate over the children here instead
584	bool controlPointOnRight = determinant(p1: s, p2: c, p3: e) > 0;
585	QVector2D startNormal = normalVector(element);
586	QVector2D endNormal = normalVector(element, endSide: true);
587	QVector2D controlPointNormal = (startNormal + endNormal).normalized();
588	if (controlPointOnRight)
589	controlPointNormal = -controlPointNormal;
590	QVector2D p5 = c + controlPointNormal * penFactor; // This is too simplistic
591	TrianglePoints t1{p1, p2, p5};
592	TrianglePoints t2{p3, p4, p5};
593	bool simpleCase = !checkTriangleOverlap(triangle1&: t1, triangle2&: t2);
594
595	if (simpleCase) {
596	ret.append(t: {.points: {p1, p2, p5}, .pathElementIndex: idx, .normals: {n1, n2, controlPointNormal}});
597	ret.append(t: {.points: {p3, p4, p5}, .pathElementIndex: idx, .normals: {n3, n4, controlPointNormal}});
598	if (controlPointOnRight) {
599	ret.append(t: {.points: {p1, p3, p5}, .pathElementIndex: idx, .normals: {n1, n3, controlPointNormal}});
600	} else {
601	ret.append(t: {.points: {p2, p4, p5}, .pathElementIndex: idx, .normals: {n2, n4, controlPointNormal}});
602	}
603	} else {
604	ret.append(other: simplePointTriangulator(pts: {p1, p2, p5, p3, p4}, normals: {n1, n2, controlPointNormal, n3, n4}, elementIndex: idx));
605	}
606	};
607
608	// Each element is calculated independently, so we don't have to special-case closed sub-paths.
609	// Take care so the end points of one element are precisely equal to the start points of the next.
610	// Any additional triangles needed for joining are added at the end of the current element.
611
612	int count = path.elementCount();
613	int subStart = 0;
614	while (subStart < count) {
615	int subEnd = subStart;
616	for (int i = subStart + 1; i < count; ++i) {
617	const auto &e = path.elementAt(i);
618	if (e.isSubpathStart()) {
619	subEnd = i - 1;
620	break;
621	}
622	if (i == count - 1) {
623	subEnd = i;
624	break;
625	}
626	}
627	bool closed = path.elementAt(i: subStart).startPoint() == path.elementAt(i: subEnd).endPoint();
628	const int subCount = subEnd - subStart + 1;
629
630	auto addIdx = [&](int idx, int delta) -> int {
631	int subIdx = idx - subStart;
632	if (closed)
633	subIdx = (subIdx + subCount + delta) % subCount;
634	else
635	subIdx += delta;
636	return subStart + subIdx;
637	};
638	auto elementAt = [&](int idx, int delta) -> const QQuadPath::Element * {
639	int subIdx = idx - subStart;
640	if (closed) {
641	subIdx = (subIdx + subCount + delta) % subCount;
642	return &path.elementAt(i: subStart + subIdx);
643	}
644	subIdx += delta;
645	if (subIdx >= 0 && subIdx < subCount)
646	return &path.elementAt(i: subStart + subIdx);
647	return nullptr;
648	};
649
650	for (int i = subStart; i <= subEnd; ++i) {
651	const auto &element = path.elementAt(i);
652	const auto *nextElement = elementAt(i, +1);
653	const auto *prevElement = elementAt(i, -1);
654
655	const auto &s = element.startPoint();
656	const auto &e = element.endPoint();
657
658	bool startInnerIsRight;
659	bool startBisectorWithinMiterLimit; // Not used
660	bool giveUpOnStartJoin; // Not used
661	auto startJoin = calculateJoin(prevElement, &element,
662	startBisectorWithinMiterLimit, startInnerIsRight,
663	giveUpOnStartJoin);
664	const QVector2D &startInner = startJoin[1];
665	const QVector2D &startOuter = startJoin[3];
666
667	bool endInnerIsRight;
668	bool endBisectorWithinMiterLimit;
669	bool giveUpOnEndJoin;
670	auto endJoin = calculateJoin(&element, nextElement,
671	endBisectorWithinMiterLimit, endInnerIsRight,
672	giveUpOnEndJoin);
673	QVector2D endInner = endJoin[0];
674	QVector2D endOuter = endJoin[2];
675	QVector2D nextOuter = endJoin[3];
676	QVector2D outerB = endJoin[4];
677
678	QVector2D p1, p2, p3, p4;
679	QVector2D n1, n2, n3, n4;
680
681	if (startInnerIsRight) {
682	n1 = startInner;
683	n2 = startOuter;
684	} else {
685	n1 = startOuter;
686	n2 = startInner;
687	}
688
689	p1 = s + n1 * penFactor;
690	p2 = s + n2 * penFactor;
691
692	// repeat logic above for the other end:
693	if (endInnerIsRight) {
694	n3 = endInner;
695	n4 = endOuter;
696	} else {
697	n3 = endOuter;
698	n4 = endInner;
699	}
700
701	p3 = e + n3 * penFactor;
702	p4 = e + n4 * penFactor;
703
704	// End caps
705
706	if (!prevElement) {
707	QVector2D capSpace = tangentVector(element).normalized() * -penFactor;
708	if (roundCap) {
709	p1 += capSpace;
710	p2 += capSpace;
711	} else if (squareCap) {
712	QVector2D c1 = p1 + capSpace;
713	QVector2D c2 = p2 + capSpace;
714	ret.append(t: {.points: {p1, s, c1}, .pathElementIndex: -1, .normals: {}});
715	ret.append(t: {.points: {c1, s, c2}, .pathElementIndex: -1, .normals: {}});
716	ret.append(t: {.points: {p2, s, c2}, .pathElementIndex: -1, .normals: {}});
717	}
718	}
719	if (!nextElement) {
720	QVector2D capSpace = tangentVector(element, endSide: true).normalized() * -penFactor;
721	if (roundCap) {
722	p3 += capSpace;
723	p4 += capSpace;
724	} else if (squareCap) {
725	QVector2D c3 = p3 + capSpace;
726	QVector2D c4 = p4 + capSpace;
727	ret.append(t: {.points: {p3, e, c3}, .pathElementIndex: -1, .normals: {}});
728	ret.append(t: {.points: {c3, e, c4}, .pathElementIndex: -1, .normals: {}});
729	ret.append(t: {.points: {p4, e, c4}, .pathElementIndex: -1, .normals: {}});
730	}
731	}
732
733	if (element.isLine()) {
734	ret.append(t: {.points: {p1, p2, p3}, .pathElementIndex: i, .normals: {n1, n2, n3}});
735	ret.append(t: {.points: {p2, p3, p4}, .pathElementIndex: i, .normals: {n2, n3, n4}});
736	} else {
737	triangulateCurve(i, p1, p2, p3, p4, n1, n2, n3, n4);
738	}
739
740	bool trivialJoin = simpleMiter && endBisectorWithinMiterLimit && !giveUpOnEndJoin;
741	if (!trivialJoin && nextElement) {
742	// inside of join (opposite of bevel) is defined by
743	// triangle s, e, next.e
744	bool innerOnRight = endInnerIsRight;
745
746	const auto outer1 = e + endOuter * penFactor;
747	const auto outer2 = e + nextOuter * penFactor;
748	//const auto inner = e + endInner * penFactor;
749
750	if (bevelJoin || (miterJoin && !endBisectorWithinMiterLimit)) {
751	ret.append(t: {.points: {outer1, e, outer2}, .pathElementIndex: -1, .normals: {}});
752	} else if (roundJoin) {
753	ret.append(t: {.points: {outer1, e, outer2}, .pathElementIndex: i, .normals: {}});
754	QVector2D nn = calcNormalVector(a: outer1, b: outer2).normalized() * penFactor;
755	if (!innerOnRight)
756	nn = -nn;
757	ret.append(t: {.points: {outer1, outer1 + nn, outer2}, .pathElementIndex: i, .normals: {}});
758	ret.append(t: {.points: {outer1 + nn, outer2, outer2 + nn}, .pathElementIndex: i, .normals: {}});
759
760	} else if (miterJoin) {
761	QVector2D outer = e + outerB * penFactor;
762	ret.append(t: {.points: {outer1, e, outer}, .pathElementIndex: -2, .normals: {}});
763	ret.append(t: {.points: {outer, e, outer2}, .pathElementIndex: -2, .normals: {}});
764	}
765
766	if (!giveUpOnEndJoin) {
767	QVector2D inner = e + endInner * penFactor;
768	ret.append(t: {.points: {inner, e, outer1}, .pathElementIndex: i, .normals: {endInner, {}, endOuter}});
769	// The remaining triangle ought to be done by nextElement, but we don't have start join logic there (yet)
770	int nextIdx = addIdx(i, +1);
771	ret.append(t: {.points: {inner, e, outer2}, .pathElementIndex: nextIdx, .normals: {endInner, {}, nextOuter}});
772	}
773	}
774	}
775	subStart = subEnd + 1;
776	}
777	return ret;
778	}
779
780	// TODO: we could optimize by preprocessing e1, since we call this function multiple times on the same
781	// elements
782	// Returns true if a change was made
783	static bool handleOverlap(QQuadPath &path, int e1, int e2, int recursionLevel = 0)
784	{
785	// Splitting lines is not going to help with overlap, since we assume that lines don't intersect
786	if (path.elementAt(i: e1).isLine() && path.elementAt(i: e1).isLine())
787	return false;
788
789	if (!isOverlap(path, e1, e2)) {
790	return false;
791	}
792
793	if (recursionLevel > 8) {
794	qCDebug(lcSGCurveProcessor) << "Triangle overlap: recursion level" << recursionLevel << "aborting!";
795	return false;
796	}
797
798	if (path.elementAt(i: e1).childCount() > 1) {
799	auto e11 = path.indexOfChildAt(i: e1, childNumber: 0);
800	auto e12 = path.indexOfChildAt(i: e1, childNumber: 1);
801	handleOverlap(path, e1: e11, e2, recursionLevel: recursionLevel + 1);
802	handleOverlap(path, e1: e12, e2, recursionLevel: recursionLevel + 1);
803	} else if (path.elementAt(i: e2).childCount() > 1) {
804	auto e21 = path.indexOfChildAt(i: e2, childNumber: 0);
805	auto e22 = path.indexOfChildAt(i: e2, childNumber: 1);
806	handleOverlap(path, e1, e2: e21, recursionLevel: recursionLevel + 1);
807	handleOverlap(path, e1, e2: e22, recursionLevel: recursionLevel + 1);
808	} else {
809	path.splitElementAt(index: e1);
810	auto e11 = path.indexOfChildAt(i: e1, childNumber: 0);
811	auto e12 = path.indexOfChildAt(i: e1, childNumber: 1);
812	bool overlap1 = isOverlap(path, e1: e11, e2);
813	bool overlap2 = isOverlap(path, e1: e12, e2);
814	if (!overlap1 && !overlap2)
815	return true; // no more overlap: success!
816
817	// We need to split more:
818	if (path.elementAt(i: e2).isLine()) {
819	// Splitting a line won't help, so we just split e1 further
820	if (overlap1)
821	handleOverlap(path, e1: e11, e2, recursionLevel: recursionLevel + 1);
822	if (overlap2)
823	handleOverlap(path, e1: e12, e2, recursionLevel: recursionLevel + 1);
824	} else {
825	// See if splitting e2 works:
826	path.splitElementAt(index: e2);
827	auto e21 = path.indexOfChildAt(i: e2, childNumber: 0);
828	auto e22 = path.indexOfChildAt(i: e2, childNumber: 1);
829	if (overlap1) {
830	handleOverlap(path, e1: e11, e2: e21, recursionLevel: recursionLevel + 1);
831	handleOverlap(path, e1: e11, e2: e22, recursionLevel: recursionLevel + 1);
832	}
833	if (overlap2) {
834	handleOverlap(path, e1: e12, e2: e21, recursionLevel: recursionLevel + 1);
835	handleOverlap(path, e1: e12, e2: e22, recursionLevel: recursionLevel + 1);
836	}
837	}
838	}
839	return true;
840	}
841	}
842
843	// Returns true if the path was changed
844	bool QSGCurveProcessor::solveOverlaps(QQuadPath &path)
845	{
846	bool changed = false;
847	if (path.testHint(hint: QQuadPath::PathNonOverlappingControlPointTriangles))
848	return false;
849
850	const auto candidates = findOverlappingCandidates(path);
851	for (auto candidate : candidates)
852	changed = handleOverlap(path, e1: candidate.first, e2: candidate.second) || changed;
853
854	path.setHint(hint: QQuadPath::PathNonOverlappingControlPointTriangles);
855	return changed;
856	}
857
858	// A fast algorithm to find path elements that might overlap. We will only check the overlap of the
859	// triangles that define the elements.
860	// We will order the elements first and then pool them depending on their x-values. This should
861	// reduce the complexity to O(n log n), where n is the number of elements in the path.
862	QList<QPair<int, int>> QSGCurveProcessor::findOverlappingCandidates(const QQuadPath &path)
863	{
864	struct BRect { float xmin; float xmax; float ymin; float ymax; };
865
866	// Calculate all bounding rectangles
867	QVarLengthArray<int, 64> elementStarts, elementEnds;
868	QVarLengthArray<BRect, 64> boundingRects;
869	elementStarts.reserve(sz: path.elementCount());
870	boundingRects.reserve(sz: path.elementCount());
871	for (int i = 0; i < path.elementCount(); i++) {
872	QQuadPath::Element e = path.elementAt(i);
873
874	BRect bR{.xmin: qMin(a: qMin(a: e.startPoint().x(), b: e.controlPoint().x()), b: e.endPoint().x()),
875	.xmax: qMax(a: qMax(a: e.startPoint().x(), b: e.controlPoint().x()), b: e.endPoint().x()),
876	.ymin: qMin(a: qMin(a: e.startPoint().y(), b: e.controlPoint().y()), b: e.endPoint().y()),
877	.ymax: qMax(a: qMax(a: e.startPoint().y(), b: e.controlPoint().y()), b: e.endPoint().y())};
878	boundingRects.append(t: bR);
879	elementStarts.append(t: i);
880	}
881
882	// Sort the bounding rectangles by x-startpoint and x-endpoint
883	auto compareXmin = [&](int i, int j){return boundingRects.at(idx: i).xmin < boundingRects.at(idx: j).xmin;};
884	auto compareXmax = [&](int i, int j){return boundingRects.at(idx: i).xmax < boundingRects.at(idx: j).xmax;};
885	std::sort(first: elementStarts.begin(), last: elementStarts.end(), comp: compareXmin);
886	elementEnds = elementStarts;
887	std::sort(first: elementEnds.begin(), last: elementEnds.end(), comp: compareXmax);
888
889	QList<int> bRpool;
890	QList<QPair<int, int>> overlappingBB;
891
892	// Start from x = xmin and move towards xmax. Add a rectangle to the pool and check for
893	// intersections with all other rectangles in the pool. If a rectangles xmax is smaller
894	// than the new xmin, it can be removed from the pool.
895	int firstElementEnd = 0;
896	for (const int addIndex : std::as_const(t&: elementStarts)) {
897	const BRect &newR = boundingRects.at(idx: addIndex);
898	// First remove elements from the pool that cannot touch the new one
899	// because xmax is too small
900	while (bRpool.size() && firstElementEnd < elementEnds.size()) {
901	int removeIndex = elementEnds.at(idx: firstElementEnd);
902	if (bRpool.contains(t: removeIndex) && newR.xmin > boundingRects.at(idx: removeIndex).xmax) {
903	bRpool.removeOne(t: removeIndex);
904	firstElementEnd++;
905	} else {
906	break;
907	}
908	}
909
910	// Now compare the new element with all elements in the pool.
911	for (int j = 0; j < bRpool.size(); j++) {
912	int i = bRpool.at(i: j);
913	const BRect &r1 = boundingRects.at(idx: i);
914	// We don't have to check for x because the pooling takes care of it.
915	//if (r1.xmax <= newR.xmin || newR.xmax <= r1.xmin)
916	// continue;
917
918	bool isNeighbor = false;
919	if (i - addIndex == 1) {
920	if (!path.elementAt(i: addIndex).isSubpathEnd())
921	isNeighbor = true;
922	} else if (addIndex - i == 1) {
923	if (!path.elementAt(i).isSubpathEnd())
924	isNeighbor = true;
925	}
926	// Neighbors need to be completely different (otherwise they just share a point)
927	if (isNeighbor && (r1.ymax <= newR.ymin || newR.ymax <= r1.ymin))
928	continue;
929	// Non-neighbors can also just touch
930	if (!isNeighbor && (r1.ymax < newR.ymin || newR.ymax < r1.ymin))
931	continue;
932	// If the bounding boxes are overlapping it is a candidate for an intersection.
933	overlappingBB.append(t: QPair<int, int>(i, addIndex));
934	}
935	bRpool.append(t: addIndex); //Add the new element to the pool.
936	}
937	return overlappingBB;
938	}
939
940	// Remove paths that are nested inside another path and not required to fill the path correctly
941	bool QSGCurveProcessor::removeNestedSubpaths(QQuadPath &path)
942	{
943	// Ensure that the path is not intersecting first
944	Q_ASSERT(path.testHint(QQuadPath::PathNonIntersecting));
945
946	if (path.fillRule() != Qt::WindingFill) {
947	// If the fillingRule is odd-even, all internal subpaths matter
948	return false;
949	}
950
951	// Store the starting and end elements of the subpaths to be able
952	// to jump quickly between them.
953	QList<int> subPathStartPoints;
954	QList<int> subPathEndPoints;
955	for (int i = 0; i < path.elementCount(); i++) {
956	if (path.elementAt(i).isSubpathStart())
957	subPathStartPoints.append(t: i);
958	if (path.elementAt(i).isSubpathEnd()) {
959	subPathEndPoints.append(t: i);
960	}
961	}
962	const int subPathCount = subPathStartPoints.size();
963
964	// If there is only one subpath, none have to be removed
965	if (subPathStartPoints.size() < 2)
966	return false;
967
968	// We set up a matrix that tells us which path is nested in which other path.
969	QList<bool> isInside;
970	bool isAnyInside = false;
971	isInside.reserve(asize: subPathStartPoints.size() * subPathStartPoints.size());
972	for (int i = 0; i < subPathCount; i++) {
973	for (int j = 0; j < subPathCount; j++) {
974	if (i == j) {
975	isInside.append(t: false);
976	} else {
977	isInside.append(t: path.contains(point: path.elementAt(i: subPathStartPoints.at(i)).startPoint(),
978	fromIndex: subPathStartPoints.at(i: j), toIndex: subPathEndPoints.at(i: j)));
979	if (isInside.last())
980	isAnyInside = true;
981	}
982	}
983	}
984
985	// If no nested subpaths are present we can return early.
986	if (!isAnyInside)
987	return false;
988
989	// To find out which paths are filled and which not, we first calculate the
990	// rotation direction (clockwise - counterclockwise).
991	QList<bool> clockwise;
992	clockwise.reserve(asize: subPathCount);
993	for (int i = 0; i < subPathCount; i++) {
994	float sumProduct = 0;
995	for (int j = subPathStartPoints.at(i); j <= subPathEndPoints.at(i); j++) {
996	const QVector2D startPoint = path.elementAt(i: j).startPoint();
997	const QVector2D endPoint = path.elementAt(i: j).endPoint();
998	sumProduct += (endPoint.x() - startPoint.x()) * (endPoint.y() + startPoint.y());
999	}
1000	clockwise.append(t: sumProduct > 0);
1001	}
1002
1003	// Set up a list that tells us which paths create filling and which path create holes.
1004	// Holes in Holes and fillings in fillings can then be removed.
1005	QList<bool> isFilled;
1006	isFilled.reserve(asize: subPathStartPoints.size() );
1007	for (int i = 0; i < subPathCount; i++) {
1008	int crossings = clockwise.at(i) ? 1 : -1;
1009	for (int j = 0; j < subPathStartPoints.size(); j++) {
1010	if (isInside.at(i: i * subPathCount + j))
1011	crossings += clockwise.at(i: j) ? 1 : -1;
1012	}
1013	isFilled.append(t: crossings != 0);
1014	}
1015
1016	// A helper function to find the most inner subpath that is around a subpath.
1017	// Returns -1 if the subpath is a toplevel subpath.
1018	auto findClosestOuterSubpath = [&](int subPath) {
1019	// All paths that contain the current subPath are candidates.
1020	QList<int> candidates;
1021	for (int i = 0; i < subPathStartPoints.size(); i++) {
1022	if (isInside.at(i: subPath * subPathCount + i))
1023	candidates.append(t: i);
1024	}
1025	int maxNestingLevel = -1;
1026	int maxNestingLevelIndex = -1;
1027	for (int i = 0; i < candidates.size(); i++) {
1028	int nestingLevel = 0;
1029	for (int j = 0; j < candidates.size(); j++) {
1030	if (isInside.at(i: candidates.at(i) * subPathCount + candidates.at(i: j))) {
1031	nestingLevel++;
1032	}
1033	}
1034	if (nestingLevel > maxNestingLevel) {
1035	maxNestingLevel = nestingLevel;
1036	maxNestingLevelIndex = candidates.at(i);
1037	}
1038	}
1039	return maxNestingLevelIndex;
1040	};
1041
1042	bool pathChanged = false;
1043	QQuadPath fixedPath;
1044	fixedPath.setPathHints(path.pathHints());
1045
1046	// Go through all subpaths and find the closest surrounding subpath.
1047	// If it is doing the same (create filling or create hole) we can remove it.
1048	for (int i = 0; i < subPathCount; i++) {
1049	int j = findClosestOuterSubpath(i);
1050	if (j >= 0 && isFilled.at(i) == isFilled.at(i: j)) {
1051	pathChanged = true;
1052	} else {
1053	for (int k = subPathStartPoints.at(i); k <= subPathEndPoints.at(i); k++)
1054	fixedPath.addElement(e: path.elementAt(i: k));
1055	}
1056	}
1057
1058	if (pathChanged)
1059	path = fixedPath;
1060	return pathChanged;
1061	}
1062
1063	// Returns true if the path was changed
1064	bool QSGCurveProcessor::solveIntersections(QQuadPath &path, bool removeNestedPaths)
1065	{
1066	if (path.testHint(hint: QQuadPath::PathNonIntersecting)) {
1067	if (removeNestedPaths)
1068	return removeNestedSubpaths(path);
1069	else
1070	return false;
1071	}
1072
1073	if (path.elementCount() < 2) {
1074	path.setHint(hint: QQuadPath::PathNonIntersecting);
1075	return false;
1076	}
1077
1078	struct IntersectionData { int e1; int e2; float t1; float t2; bool in1 = false, in2 = false, out1 = false, out2 = false; };
1079	QList<IntersectionData> intersections;
1080
1081	// Helper function to mark an intersection as handled when the
1082	// path i is processed moving forward/backward
1083	auto markIntersectionAsHandled = [=](IntersectionData *data, int i, bool forward) {
1084	if (data->e1 == i) {
1085	if (forward)
1086	data->out1 = true;
1087	else
1088	data->in1 = true;
1089	} else if (data->e2 == i){
1090	if (forward)
1091	data->out2 = true;
1092	else
1093	data->in2 = true;
1094	} else {
1095	Q_UNREACHABLE();
1096	}
1097	};
1098
1099	// First make a O(n log n) search for candidates.
1100	const QList<QPair<int, int>> candidates = findOverlappingCandidates(path);
1101	// Then check the candidates for actual intersections.
1102	for (const auto &candidate : candidates) {
1103	QList<QPair<float,float>> res;
1104	int e1 = candidate.first;
1105	int e2 = candidate.second;
1106	if (isIntersecting(path, e1, e2, solutions: &res)) {
1107	for (const auto &r : res)
1108	intersections.append(t: {.e1: e1, .e2: e2, .t1: r.first, .t2: r.second});
1109	}
1110	}
1111
1112	qCDebug(lcSGCurveIntersectionSolver) << "----- Checking for Intersections -----";
1113	qCDebug(lcSGCurveIntersectionSolver) << "Found" << intersections.length() << "intersections";
1114	if (lcSGCurveIntersectionSolver().isDebugEnabled()) {
1115	for (const auto &i : intersections) {
1116	auto p1 = path.elementAt(i: i.e1).pointAtFraction(t: i.t1);
1117	auto p2 = path.elementAt(i: i.e2).pointAtFraction(t: i.t2);
1118	qCDebug(lcSGCurveIntersectionSolver) << " between" << i.e1 << "and" << i.e2 << "at" << i.t1 << "/" << i.t2 << "->" << p1 << "/" << p2;
1119	}
1120	}
1121
1122	if (intersections.isEmpty()) {
1123	path.setHint(hint: QQuadPath::PathNonIntersecting);
1124	if (removeNestedPaths) {
1125	qCDebug(lcSGCurveIntersectionSolver) << "No Intersections found. Looking for enclosed subpaths.";
1126	return removeNestedSubpaths(path);
1127	} else {
1128	qCDebug(lcSGCurveIntersectionSolver) << "Returning the path unchanged.";
1129	return false;
1130	}
1131	}
1132
1133
1134	// Store the starting and end elements of the subpaths to be able
1135	// to jump quickly between them. Also keep a list of handled paths,
1136	// so we know if we need to come back to a subpath or if it
1137	// was already united with another subpath due to an intersection.
1138	QList<int> subPathStartPoints;
1139	QList<int> subPathEndPoints;
1140	QList<bool> subPathHandled;
1141	for (int i = 0; i < path.elementCount(); i++) {
1142	if (path.elementAt(i).isSubpathStart())
1143	subPathStartPoints.append(t: i);
1144	if (path.elementAt(i).isSubpathEnd()) {
1145	subPathEndPoints.append(t: i);
1146	subPathHandled.append(t: false);
1147	}
1148	}
1149
1150	// A small helper to find the subPath of an element with index
1151	auto subPathIndex = [&](int index) {
1152	for (int i = 0; i < subPathStartPoints.size(); i++) {
1153	if (index >= subPathStartPoints.at(i) && index <= subPathEndPoints.at(i))
1154	return i;
1155	}
1156	return -1;
1157	};
1158
1159	// Helper to ensure that index i and position t are valid:
1160	auto ensureInBounds = [&](int *i, float *t, float deltaT) {
1161	if (*t <= 0.f) {
1162	if (path.elementAt(i: *i).isSubpathStart())
1163	*i = subPathEndPoints.at(i: subPathIndex(*i));
1164	else
1165	*i = *i - 1;
1166	*t = 1.f - deltaT;
1167	} else if (*t >= 1.f) {
1168	if (path.elementAt(i: *i).isSubpathEnd())
1169	*i = subPathStartPoints.at(i: subPathIndex(*i));
1170	else
1171	*i = *i + 1;
1172	*t = deltaT;
1173	}
1174	};
1175
1176	// Helper function to find a siutable starting point between start and end.
1177	// A suitable starting point is where right is inside and left is outside
1178	// If left is inside and right is outside it works too, just move in the
1179	// other direction (forward = false).
1180	auto findStart = [=](QQuadPath &path, int start, int end, int *result, bool *forward) {
1181	for (int i = start; i < end; i++) {
1182	int adjecent;
1183	if (subPathStartPoints.contains(t: i))
1184	adjecent = subPathEndPoints.at(i: subPathStartPoints.indexOf(t: i));
1185	else
1186	adjecent = i - 1;
1187
1188	QQuadPath::Element::FillSide fillSide = path.fillSideOf(elementIdx: i, elementT: 1e-4f);
1189	const bool leftInside = fillSide == QQuadPath::Element::FillSideLeft;
1190	const bool rightInside = fillSide == QQuadPath::Element::FillSideRight;
1191	qCDebug(lcSGCurveIntersectionSolver) << "Element" << i << "/" << adjecent << "meeting point is left/right inside:" << leftInside << "/" << rightInside;
1192	if (rightInside) {
1193	*result = i;
1194	*forward = true;
1195	return true;
1196	} else if (leftInside) {
1197	*result = adjecent;
1198	*forward = false;
1199	return true;
1200	}
1201	}
1202	return false;
1203	};
1204
1205	// Also store handledElements (handled is when we touch the start point).
1206	// This is used to identify and abort on errors.
1207	QVarLengthArray<bool> handledElements(path.elementCount(), false);
1208	// Only store handledElements when it is not touched due to an intersection.
1209	bool regularVisit = true;
1210
1211	QQuadPath fixedPath;
1212	fixedPath.setFillRule(path.fillRule());
1213
1214	int i1 = 0;
1215	float t1 = 0;
1216
1217	int i2 = 0;
1218	float t2 = 0;
1219
1220	float t = 0;
1221	bool forward = true;
1222
1223	int startedAtIndex = -1;
1224	float startedAtT = -1;
1225
1226	if (!findStart(path, 0, path.elementCount(), &i1, &forward)) {
1227	qCDebug(lcSGCurveIntersectionSolver) << "No suitable start found. This should not happen. Returning the path unchanged.";
1228	return false;
1229	}
1230
1231	// Helper function to start a new subpath and update temporary variables.
1232	auto startNewSubPath = [&](int i, bool forward) {
1233	if (forward) {
1234	fixedPath.moveTo(to: path.elementAt(i).startPoint());
1235	t = startedAtT = 0;
1236	} else {
1237	fixedPath.moveTo(to: path.elementAt(i).endPoint());
1238	t = startedAtT = 1;
1239	}
1240	startedAtIndex = i;
1241	subPathHandled[subPathIndex(i)] = true;
1242	};
1243	startNewSubPath(i1, forward);
1244
1245	// If not all interactions where found correctly, we might end up in an infinite loop.
1246	// Therefore we count the total number of iterations and bail out at some point.
1247	int totalIterations = 0;
1248
1249	// We need to store the last intersection so we don't jump back and forward immediately.
1250	int prevIntersection = -1;
1251
1252	do {
1253	// Sanity check: Make sure that we do not process the same corner point more than once.
1254	if (regularVisit && (t == 0 || t == 1)) {
1255	int nextIndex = i1;
1256	if (t == 1 && path.elementAt(i: i1).isSubpathEnd()) {
1257	nextIndex = subPathStartPoints.at(i: subPathIndex(i1));
1258	} else if (t == 1) {
1259	nextIndex = nextIndex + 1;
1260	}
1261	if (handledElements[nextIndex]) {
1262	qCDebug(lcSGCurveIntersectionSolver) << "Revisiting an element when trying to solve intersections. This should not happen. Returning the path unchanged.";
1263	return false;
1264	}
1265	handledElements[nextIndex] = true;
1266	}
1267	// Sanity check: Keep an eye on total iterations
1268	totalIterations++;
1269
1270	qCDebug(lcSGCurveIntersectionSolver) << "Checking section" << i1 << "from" << t << "going" << (forward ? "forward" : "backward");
1271
1272	// Find the next intersection that is as close as possible to t but in direction of processing (forward or !forward).
1273	int iC = -1; //intersection candidate
1274	t1 = forward? 1 : -1; //intersection candidate t-value
1275	for (int j = 0; j < intersections.size(); j++) {
1276	if (j == prevIntersection)
1277	continue;
1278	if (i1 == intersections[j].e1 &&
1279	intersections[j].t1 * (forward ? 1 : -1) >= t * (forward ? 1 : -1) &&
1280	intersections[j].t1 * (forward ? 1 : -1) < t1 * (forward ? 1 : -1)) {
1281	iC = j;
1282	t1 = intersections[j].t1;
1283	i2 = intersections[j].e2;
1284	t2 = intersections[j].t2;
1285	}
1286	if (i1 == intersections[j].e2 &&
1287	intersections[j].t2 * (forward ? 1 : -1) >= t * (forward ? 1 : -1) &&
1288	intersections[j].t2 * (forward ? 1 : -1) < t1 * (forward ? 1 : -1)) {
1289	iC = j;
1290	t1 = intersections[j].t2;
1291	i2 = intersections[j].e1;
1292	t2 = intersections[j].t1;
1293	}
1294	}
1295	prevIntersection = iC;
1296
1297	if (iC < 0) {
1298	qCDebug(lcSGCurveIntersectionSolver) << " No intersection found on my way. Adding the rest of the segment " << i1;
1299	regularVisit = true;
1300	// If no intersection with the current element was found, just add the rest of the element
1301	// to the fixed path and go on.
1302	// If we reached the end (going forward) or start (going backward) of a subpath, we have
1303	// to wrap aroud. Abort condition for the loop comes separately later.
1304	if (forward) {
1305	if (path.elementAt(i: i1).isLine()) {
1306	fixedPath.lineTo(to: path.elementAt(i: i1).endPoint());
1307	} else {
1308	const QQuadPath::Element rest = path.elementAt(i: i1).segmentFromTo(t0: t, t1: 1);
1309	fixedPath.quadTo(control: rest.controlPoint(), to: rest.endPoint());
1310	}
1311	if (path.elementAt(i: i1).isSubpathEnd()) {
1312	int index = subPathEndPoints.indexOf(t: i1);
1313	qCDebug(lcSGCurveIntersectionSolver) << " Going back to the start of subPath" << index;
1314	i1 = subPathStartPoints.at(i: index);
1315	} else {
1316	i1++;
1317	}
1318	t = 0;
1319	} else {
1320	if (path.elementAt(i: i1).isLine()) {
1321	fixedPath.lineTo(to: path.elementAt(i: i1).startPoint());
1322	} else {
1323	const QQuadPath::Element rest = path.elementAt(i: i1).segmentFromTo(t0: 0, t1: t).reversed();
1324	fixedPath.quadTo(control: rest.controlPoint(), to: rest.endPoint());
1325	}
1326	if (path.elementAt(i: i1).isSubpathStart()) {
1327	int index = subPathStartPoints.indexOf(t: i1);
1328	qCDebug(lcSGCurveIntersectionSolver) << " Going back to the end of subPath" << index;
1329	i1 = subPathEndPoints.at(i: index);
1330	} else {
1331	i1--;
1332	}
1333	t = 1;
1334	}
1335	} else { // Here comes the part where we actually handle intersections.
1336	qCDebug(lcSGCurveIntersectionSolver) << " Found an intersection at" << t1 << "with" << i2 << "at" << t2;
1337
1338	// Mark the subpath we intersected with as visisted. We do not have to come here explicitly again.
1339	subPathHandled[subPathIndex(i2)] = true;
1340
1341	// Mark the path that lead us to this intersection as handled on the intersection level.
1342	// Note the ! in front of forward. This is required because we move towards the intersection.
1343	markIntersectionAsHandled(&intersections[iC], i1, !forward);
1344
1345	// Split the path from the last point to the newly found intersection.
1346	// Add the part of the current segment to the fixedPath.
1347	const QQuadPath::Element &elem1 = path.elementAt(i: i1);
1348	if (elem1.isLine()) {
1349	fixedPath.lineTo(to: elem1.pointAtFraction(t: t1));
1350	} else {
1351	QQuadPath::Element partUntilIntersection;
1352	if (forward) {
1353	partUntilIntersection = elem1.segmentFromTo(t0: t, t1);
1354	} else {
1355	partUntilIntersection = elem1.segmentFromTo(t0: t1, t1: t).reversed();
1356	}
1357	fixedPath.quadTo(control: partUntilIntersection.controlPoint(), to: partUntilIntersection.endPoint());
1358	}
1359
1360	// If only one unhandled path is left the decision how to proceed is trivial
1361	if (intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && !intersections[iC].out2) {
1362	i1 = intersections[iC].e2;
1363	t = intersections[iC].t2;
1364	forward = true;
1365	} else if (intersections[iC].in1 && intersections[iC].in2 && !intersections[iC].out1 && intersections[iC].out2) {
1366	i1 = intersections[iC].e1;
1367	t = intersections[iC].t1;
1368	forward = true;
1369	} else if (intersections[iC].in1 && !intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
1370	i1 = intersections[iC].e2;
1371	t = intersections[iC].t2;
1372	forward = false;
1373	} else if (!intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
1374	i1 = intersections[iC].e1;
1375	t = intersections[iC].t1;
1376	forward = false;
1377	} else {
1378	// If no trivial path is left, calculate the intersection angle to decide which path to move forward.
1379	// For winding fill we take the left most path forward, so the inside stays on the right side
1380	// For odd even fill we take the right most path forward so we cut of the smallest area.
1381	// We come back at the intersection and add the missing pieces as subpaths later on.
1382	if (t1 !=0 && t1 != 1 && t2 != 0 && t2 != 1) {
1383	QVector2D tangent1 = elem1.tangentAtFraction(t: t1);
1384	if (!forward)
1385	tangent1 = -tangent1;
1386	const QQuadPath::Element &elem2 = path.elementAt(i: i2);
1387	const QVector2D tangent2 = elem2.tangentAtFraction(t: t2);
1388	const float angle = angleBetween(v1: -tangent1, v2: tangent2);
1389	qCDebug(lcSGCurveIntersectionSolver) << " Angle at intersection is" << angle;
1390	// A small angle. Everything smaller is interpreted as tangent
1391	constexpr float deltaAngle = 1e-3f;
1392	if ((angle > deltaAngle && path.fillRule() == Qt::WindingFill) || (angle < -deltaAngle && path.fillRule() == Qt::OddEvenFill)) {
1393	forward = true;
1394	i1 = i2;
1395	t = t2;
1396	qCDebug(lcSGCurveIntersectionSolver) << " Next going forward from" << t << "on" << i1;
1397	} else if ((angle < -deltaAngle && path.fillRule() == Qt::WindingFill) || (angle > deltaAngle && path.fillRule() == Qt::OddEvenFill)) {
1398	forward = false;
1399	i1 = i2;
1400	t = t2;
1401	qCDebug(lcSGCurveIntersectionSolver) << " Next going backward from" << t << "on" << i1;
1402	} else { // this is basically a tangential touch and and no crossing. So stay on the current path, keep direction
1403	qCDebug(lcSGCurveIntersectionSolver) << " Found tangent. Staying on element";
1404	}
1405	} else {
1406	// If we are intersecting exactly at a corner, the trick with the angle does not help.
1407	// Therefore we have to rely on finding the next path by looking forward and see if the
1408	// path there is valid. This is more expensive than the method above and is therefore
1409	// just used as a fallback for corner cases.
1410	constexpr float deltaT = 1e-4f;
1411	int i2after = i2;
1412	float t2after = t2 + deltaT;
1413	ensureInBounds(&i2after, &t2after, deltaT);
1414	QQuadPath::Element::FillSide fillSideForwardNew = path.fillSideOf(elementIdx: i2after, elementT: t2after);
1415	if (fillSideForwardNew == QQuadPath::Element::FillSideRight) {
1416	forward = true;
1417	i1 = i2;
1418	t = t2;
1419	qCDebug(lcSGCurveIntersectionSolver) << " Next going forward from" << t << "on" << i1;
1420	} else {
1421	int i2before = i2;
1422	float t2before = t2 - deltaT;
1423	ensureInBounds(&i2before, &t2before, deltaT);
1424	QQuadPath::Element::FillSide fillSideBackwardNew = path.fillSideOf(elementIdx: i2before, elementT: t2before);
1425	if (fillSideBackwardNew == QQuadPath::Element::FillSideLeft) {
1426	forward = false;
1427	i1 = i2;
1428	t = t2;
1429	qCDebug(lcSGCurveIntersectionSolver) << " Next going backward from" << t << "on" << i1;
1430	} else {
1431	qCDebug(lcSGCurveIntersectionSolver) << " Staying on element.";
1432	}
1433	}
1434	}
1435	}
1436
1437	// Mark the path that takes us away from this intersection as handled on the intersection level.
1438	if (!(i1 == startedAtIndex && t == startedAtT))
1439	markIntersectionAsHandled(&intersections[iC], i1, forward);
1440
1441	// If we took all paths from an intersection it can be deleted.
1442	if (intersections[iC].in1 && intersections[iC].in2 && intersections[iC].out1 && intersections[iC].out2) {
1443	qCDebug(lcSGCurveIntersectionSolver) << " This intersection was processed completely and will be removed";
1444	intersections.removeAt(i: iC);
1445	prevIntersection = -1;
1446	}
1447	regularVisit = false;
1448	}
1449
1450	if (i1 == startedAtIndex && t == startedAtT) {
1451	// We reached the point on the subpath where we started. This subpath is done.
1452	// We have to find an unhandled subpath or a new subpath that was generated by cuts/intersections.
1453	qCDebug(lcSGCurveIntersectionSolver) << "Reached my starting point and try to find a new subpath.";
1454
1455	// Search for the next subpath to handle.
1456	int nextUnhandled = -1;
1457	for (int i = 0; i < subPathHandled.size(); i++) {
1458	if (!subPathHandled.at(i)) {
1459
1460	// Not nesesarrily handled (if findStart return false) but if we find no starting
1461	// point, we cannot/don't need to handle it anyway. So just mark it as handled.
1462	subPathHandled[i] = true;
1463
1464	if (findStart(path, subPathStartPoints.at(i), subPathEndPoints.at(i), &i1, &forward)) {
1465	nextUnhandled = i;
1466	qCDebug(lcSGCurveIntersectionSolver) << "Found a new subpath" << i << "to be processed.";
1467	startNewSubPath(i1, forward);
1468	regularVisit = true;
1469	break;
1470	}
1471	}
1472	}
1473
1474	// If no valid subpath is left, we have to go back to the unhandled intersections.
1475	while (nextUnhandled < 0) {
1476	qCDebug(lcSGCurveIntersectionSolver) << "All subpaths handled. Looking for unhandled intersections.";
1477	if (intersections.isEmpty()) {
1478	qCDebug(lcSGCurveIntersectionSolver) << "All intersections handled. I am done.";
1479	fixedPath.setHint(hint: QQuadPath::PathNonIntersecting);
1480	path = fixedPath;
1481	return true;
1482	}
1483
1484	IntersectionData &unhandledIntersec = intersections[0];
1485	prevIntersection = 0;
1486	regularVisit = false;
1487	qCDebug(lcSGCurveIntersectionSolver) << "Revisiting intersection of" << unhandledIntersec.e1 << "with" << unhandledIntersec.e2;
1488	qCDebug(lcSGCurveIntersectionSolver) << "Handled are" << unhandledIntersec.e1 << "in:" << unhandledIntersec.in1 << "out:" << unhandledIntersec.out1
1489	<< "/" << unhandledIntersec.e2 << "in:" << unhandledIntersec.in2 << "out:" << unhandledIntersec.out2;
1490
1491	// Searching for the correct direction to go forward.
1492	// That requires that the intersection + small delta (here 1e-4)
1493	// is a valid starting point (filling only on one side)
1494	auto lookForwardOnIntersection = [&](bool *handledPath, int nextE, float nextT, bool nextForward) {
1495	if (*handledPath)
1496	return false;
1497	constexpr float deltaT = 1e-4f;
1498	int eForward = nextE;
1499	float tForward = nextT + (nextForward ? deltaT : -deltaT);
1500	ensureInBounds(&eForward, &tForward, deltaT);
1501	QQuadPath::Element::FillSide fillSide = path.fillSideOf(elementIdx: eForward, elementT: tForward);
1502	if ((nextForward && fillSide == QQuadPath::Element::FillSideRight) ||
1503	(!nextForward && fillSide == QQuadPath::Element::FillSideLeft)) {
1504	fixedPath.moveTo(to: path.elementAt(i: nextE).pointAtFraction(t: nextT));
1505	i1 = startedAtIndex = nextE;
1506	t = startedAtT = nextT;
1507	forward = nextForward;
1508	*handledPath = true;
1509	return true;
1510	}
1511	return false;
1512	};
1513
1514	if (lookForwardOnIntersection(&unhandledIntersec.in1, unhandledIntersec.e1, unhandledIntersec.t1, false))
1515	break;
1516	if (lookForwardOnIntersection(&unhandledIntersec.in2, unhandledIntersec.e2, unhandledIntersec.t2, false))
1517	break;
1518	if (lookForwardOnIntersection(&unhandledIntersec.out1, unhandledIntersec.e1, unhandledIntersec.t1, true))
1519	break;
1520	if (lookForwardOnIntersection(&unhandledIntersec.out2, unhandledIntersec.e2, unhandledIntersec.t2, true))
1521	break;
1522
1523	intersections.removeFirst();
1524	qCDebug(lcSGCurveIntersectionSolver) << "Found no way to move forward at this intersection and removed it.";
1525	}
1526	}
1527
1528	} while (totalIterations < path.elementCount() * 50);
1529	// Check the totalIterations as a sanity check. Should never be triggered.
1530
1531	qCDebug(lcSGCurveIntersectionSolver) << "Could not solve intersections of path. This should not happen. Returning the path unchanged.";
1532
1533	return false;
1534	}
1535
1536
1537	void QSGCurveProcessor::processStroke(const QQuadPath &strokePath,
1538	float miterLimit,
1539	float penWidth,
1540	Qt::PenJoinStyle joinStyle,
1541	Qt::PenCapStyle capStyle,
1542	addStrokeTriangleCallback addTriangle,
1543	int subdivisions)
1544	{
1545	auto thePath = subdivide(path: strokePath, subdivisions).flattened(); // TODO: don't flatten, but handle it in the triangulator
1546	auto triangles = customTriangulator2(path: thePath, penWidth, joinStyle, capStyle, miterLimit);
1547
1548	auto addCurveTriangle = [&](const QQuadPath::Element &element, const TriangleData &t) {
1549	addTriangle(t.points,
1550	{ element.startPoint(), element.controlPoint(), element.endPoint() },
1551	t.normals,
1552	element.isLine());
1553	};
1554
1555	auto addBevelTriangle = [&](const TrianglePoints &p)
1556	{
1557	QVector2D fp1 = p[0];
1558	QVector2D fp2 = p[2];
1559
1560	// That describes a path that passes through those points. We want the stroke
1561	// edge, so we need to shift everything down by the stroke offset
1562
1563	QVector2D nn = calcNormalVector(a: p[0], b: p[2]);
1564	if (determinant(p) < 0)
1565	nn = -nn;
1566	float delta = penWidth / 2;
1567
1568	QVector2D offset = nn.normalized() * delta;
1569	fp1 += offset;
1570	fp2 += offset;
1571
1572	TrianglePoints n;
1573	// p1 is inside, so n[1] is {0,0}
1574	n[0] = (p[0] - p[1]).normalized();
1575	n[2] = (p[2] - p[1]).normalized();
1576
1577	addTriangle(p, { fp1, QVector2D(0.0f, 0.0f), fp2 }, n, true);
1578	};
1579
1580	for (const auto &triangle : triangles) {
1581	if (triangle.pathElementIndex < 0) {
1582	addBevelTriangle(triangle.points);
1583	continue;
1584	}
1585	const auto &element = thePath.elementAt(i: triangle.pathElementIndex);
1586	addCurveTriangle(element, triangle);
1587	}
1588	}
1589
1590	// 2x variant of qHash(float)
1591	inline size_t qHash(QVector2D key, size_t seed = 0) noexcept
1592	{
1593	Q_STATIC_ASSERT(sizeof(QVector2D) == sizeof(quint64));
1594	// ensure -0 gets mapped to 0
1595	key[0] += 0.0f;
1596	key[1] += 0.0f;
1597	quint64 k;
1598	memcpy(dest: &k, src: &key, n: sizeof(QVector2D));
1599	return QHashPrivate::hash(key: k, seed);
1600	}
1601
1602	void QSGCurveProcessor::processFill(const QQuadPath &fillPath,
1603	Qt::FillRule fillRule,
1604	addTriangleCallback addTriangle)
1605	{
1606	QPainterPath internalHull;
1607	internalHull.setFillRule(fillRule);
1608
1609	QMultiHash<QVector2D, int> pointHash;
1610
1611	auto roundVec2D = [](const QVector2D &p) -> QVector2D {
1612	return { qRound64(f: p.x() * 32.0f) / 32.0f, qRound64(f: p.y() * 32.0f) / 32.0f };
1613	};
1614
1615	auto addCurveTriangle = [&](const QQuadPath::Element &element,
1616	const QVector2D &sp,
1617	const QVector2D &ep,
1618	const QVector2D &cp) {
1619	addTriangle({ sp, cp, ep },
1620	{},
1621	[&element](QVector2D v) { return elementUvForPoint(e: element, p: v); });
1622	};
1623
1624	auto addCurveTriangleWithNormals = [&](const QQuadPath::Element &element,
1625	const std::array<QVector2D, 3> &v,
1626	const std::array<QVector2D, 3> &n) {
1627	addTriangle(v, n, [&element](QVector2D v) { return elementUvForPoint(e: element, p: v); });
1628	};
1629
1630	auto outsideNormal = [](const QVector2D &startPoint,
1631	const QVector2D &endPoint,
1632	const QVector2D &insidePoint) {
1633
1634	QVector2D baseLine = endPoint - startPoint;
1635	QVector2D insideVector = insidePoint - startPoint;
1636	QVector2D normal = normalVector(baseLine);
1637
1638	bool swap = QVector2D::dotProduct(v1: insideVector, v2: normal) < 0;
1639
1640	return swap ? normal : -normal;
1641	};
1642
1643	auto addTriangleForLine = [&](const QQuadPath::Element &element,
1644	const QVector2D &sp,
1645	const QVector2D &ep,
1646	const QVector2D &cp) {
1647	addCurveTriangle(element, sp, ep, cp);
1648
1649	// Add triangles on the outer side to make room for AA
1650	const QVector2D normal = outsideNormal(sp, ep, cp);
1651	constexpr QVector2D null;
1652	addCurveTriangleWithNormals(element, {sp, sp, ep}, {null, normal, null});
1653	addCurveTriangleWithNormals(element, {sp, ep, ep}, {normal, normal, null});
1654	};
1655
1656	auto addTriangleForConcave = [&](const QQuadPath::Element &element,
1657	const QVector2D &sp,
1658	const QVector2D &ep,
1659	const QVector2D &cp) {
1660	addTriangleForLine(element, sp, ep, cp);
1661	};
1662
1663	auto addTriangleForConvex = [&](const QQuadPath::Element &element,
1664	const QVector2D &sp,
1665	const QVector2D &ep,
1666	const QVector2D &cp) {
1667	addCurveTriangle(element, sp, ep, cp);
1668	// Add two triangles on the outer side to get some more AA
1669
1670	constexpr QVector2D null;
1671	// First triangle on the line sp-cp, replacing ep
1672	{
1673	const QVector2D normal = outsideNormal(sp, cp, ep);
1674	addCurveTriangleWithNormals(element, {sp, sp, cp}, {null, normal, null});
1675	}
1676
1677	// Second triangle on the line ep-cp, replacing sp
1678	{
1679	const QVector2D normal = outsideNormal(ep, cp, sp);
1680	addCurveTriangleWithNormals(element, {ep, ep, cp}, {null, normal, null});
1681	}
1682	};
1683
1684	auto addFillTriangle = [&](const QVector2D &p1, const QVector2D &p2, const QVector2D &p3) {
1685	constexpr QVector3D uv(0.0, 1.0, -1.0);
1686	addTriangle({ p1, p2, p3 },
1687	{},
1688	[&uv](QVector2D) { return uv; });
1689	};
1690
1691	fillPath.iterateElements(lambda: [&](const QQuadPath::Element &element, int index) {
1692	QVector2D sp(element.startPoint());
1693	QVector2D cp(element.controlPoint());
1694	QVector2D ep(element.endPoint());
1695	QVector2D rsp = roundVec2D(sp);
1696
1697	if (element.isSubpathStart())
1698	internalHull.moveTo(p: sp.toPointF());
1699	if (element.isLine()) {
1700	internalHull.lineTo(p: ep.toPointF());
1701	pointHash.insert(key: rsp, value: index);
1702	} else {
1703	QVector2D rep = roundVec2D(ep);
1704	QVector2D rcp = roundVec2D(cp);
1705	if (element.isConvex()) {
1706	internalHull.lineTo(p: ep.toPointF());
1707	addTriangleForConvex(element, rsp, rep, rcp);
1708	pointHash.insert(key: rsp, value: index);
1709	} else {
1710	internalHull.lineTo(p: cp.toPointF());
1711	internalHull.lineTo(p: ep.toPointF());
1712	addTriangleForConcave(element, rsp, rep, rcp);
1713	pointHash.insert(key: rcp, value: index);
1714	}
1715	}
1716	});
1717
1718	// Points in p are already rounded do 1/32
1719	// Returns false if the triangle needs to be split. Adds the triangle to the graphics buffers and returns true otherwise.
1720	// (Does not handle ambiguous vertices that are on multiple unrelated lines/curves)
1721	auto onSameSideOfLine = [](const QVector2D &p1,
1722	const QVector2D &p2,
1723	const QVector2D &linePoint,
1724	const QVector2D &lineNormal) {
1725	float side1 = testSideOfLineByNormal(a: linePoint, n: lineNormal, p: p1);
1726	float side2 = testSideOfLineByNormal(a: linePoint, n: lineNormal, p: p2);
1727	return side1 * side2 >= 0;
1728	};
1729
1730	auto pointInSafeSpace = [&](const QVector2D &p, const QQuadPath::Element &element) -> bool {
1731	const QVector2D a = element.startPoint();
1732	const QVector2D b = element.endPoint();
1733	const QVector2D c = element.controlPoint();
1734	// There are "safe" areas of the curve also across the baseline: the curve can never cross:
1735	// line1: the line through A and B'
1736	// line2: the line through B and A'
1737	// Where A' = A "mirrored" through C and B' = B "mirrored" through C
1738	const QVector2D n1 = calcNormalVector(a, b: c + (c - b));
1739	const QVector2D n2 = calcNormalVector(a: b, b: c + (c - a));
1740	bool safeSideOf1 = onSameSideOfLine(p, c, a, n1);
1741	bool safeSideOf2 = onSameSideOfLine(p, c, b, n2);
1742	return safeSideOf1 && safeSideOf2;
1743	};
1744
1745	// Returns false if the triangle belongs to multiple elements and need to be split.
1746	// Otherwise adds the triangle, optionally splitting it to avoid "unsafe space"
1747	auto handleTriangle = [&](const QVector2D (&p)[3]) -> bool {
1748	bool isLine = false;
1749	bool isConcave = false;
1750	bool isConvex = false;
1751	int elementIndex = -1;
1752
1753	bool foundElement = false;
1754	int si = -1;
1755	int ei = -1;
1756
1757	for (int i = 0; i < 3; ++i) {
1758	auto pointFoundRange = std::as_const(t&: pointHash).equal_range(key: roundVec2D(p[i]));
1759
1760	if (pointFoundRange.first == pointHash.constEnd())
1761	continue;
1762
1763	// This point is on some element, now find the element
1764	int testIndex = *pointFoundRange.first;
1765	bool ambiguous = std::next(x: pointFoundRange.first) != pointFoundRange.second;
1766	if (ambiguous) {
1767	// The triangle should be on the inside of exactly one of the elements
1768	// We're doing the test for each of the points, which maybe duplicates some effort,
1769	// but optimize for simplicity for now.
1770	for (auto it = pointFoundRange.first; it != pointFoundRange.second; ++it) {
1771	auto &el = fillPath.elementAt(i: *it);
1772	bool fillOnLeft = !el.isFillOnRight();
1773	auto sp = roundVec2D(el.startPoint());
1774	auto ep = roundVec2D(el.endPoint());
1775	// Check if the triangle is on the inside of el; i.e. each point is either sp, ep, or on the inside.
1776	auto pointInside = [&](const QVector2D &p) {
1777	return p == sp || p == ep
1778	|| QQuadPath::isPointOnLeft(p, sp: el.startPoint(), ep: el.endPoint()) == fillOnLeft;
1779	};
1780	if (pointInside(p[0]) && pointInside(p[1]) && pointInside(p[2])) {
1781	testIndex = *it;
1782	break;
1783	}
1784	}
1785	}
1786
1787	const auto &element = fillPath.elementAt(i: testIndex);
1788	// Now we check if p[i] -> p[j] is on the element for some j
1789	// For a line, the relevant line is sp-ep
1790	// For concave it's cp-sp/ep
1791	// For convex it's sp-ep again
1792	bool onElement = false;
1793	for (int j = 0; j < 3; ++j) {
1794	if (i == j)
1795	continue;
1796	if (element.isConvex() || element.isLine())
1797	onElement = roundVec2D(element.endPoint()) == p[j];
1798	else // concave
1799	onElement = roundVec2D(element.startPoint()) == p[j] || roundVec2D(element.endPoint()) == p[j];
1800	if (onElement) {
1801	if (foundElement)
1802	return false; // Triangle already on some other element: must split
1803	si = i;
1804	ei = j;
1805	foundElement = true;
1806	elementIndex = testIndex;
1807	isConvex = element.isConvex();
1808	isLine = element.isLine();
1809	isConcave = !isLine && !isConvex;
1810	break;
1811	}
1812	}
1813	}
1814
1815	if (isLine) {
1816	int ci = (6 - si - ei) % 3; // 1+2+3 is 6, so missing number is 6-n1-n2
1817	addTriangleForLine(fillPath.elementAt(i: elementIndex), p[si], p[ei], p[ci]);
1818	} else if (isConcave) {
1819	addCurveTriangle(fillPath.elementAt(i: elementIndex), p[0], p[1], p[2]);
1820	} else if (isConvex) {
1821	int oi = (6 - si - ei) % 3;
1822	const auto &otherPoint = p[oi];
1823	const auto &element = fillPath.elementAt(i: elementIndex);
1824	// We have to test whether the triangle can cross the line
1825	// TODO: use the toplevel element's safe space
1826	bool safeSpace = pointInSafeSpace(otherPoint, element);
1827	if (safeSpace) {
1828	addCurveTriangle(element, p[0], p[1], p[2]);
1829	} else {
1830	// Find a point inside the triangle that's also in the safe space
1831	QVector2D newPoint = (p[0] + p[1] + p[2]) / 3;
1832	// We should calculate the point directly, but just do a lazy implementation for now:
1833	for (int i = 0; i < 7; ++i) {
1834	safeSpace = pointInSafeSpace(newPoint, element);
1835	if (safeSpace)
1836	break;
1837	newPoint = (p[si] + p[ei] + newPoint) / 3;
1838	}
1839	if (safeSpace) {
1840	// Split triangle. We know the original triangle is only on one path element, so the other triangles are both fill.
1841	// Curve triangle is (sp, ep, np)
1842	addCurveTriangle(element, p[si], p[ei], newPoint);
1843	// The other two are (sp, op, np) and (ep, op, np)
1844	addFillTriangle(p[si], p[oi], newPoint);
1845	addFillTriangle(p[ei], p[oi], newPoint);
1846	} else {
1847	// fallback to fill if we can't find a point in safe space
1848	addFillTriangle(p[0], p[1], p[2]);
1849	}
1850	}
1851
1852	} else {
1853	addFillTriangle(p[0], p[1], p[2]);
1854	}
1855	return true;
1856	};
1857
1858	QTriangleSet triangles = qTriangulate(path: internalHull);
1859	// Workaround issue in qTriangulate() for single-triangle path
1860	if (triangles.indices.size() == 3)
1861	triangles.indices.setDataUint({ 0, 1, 2 });
1862
1863	const quint32 *idxTable = static_cast<const quint32 *>(triangles.indices.data());
1864	for (int triangle = 0; triangle < triangles.indices.size() / 3; ++triangle) {
1865	const quint32 *idx = &idxTable[triangle * 3];
1866
1867	QVector2D p[3];
1868	for (int i = 0; i < 3; ++i) {
1869	p[i] = roundVec2D(QVector2D(float(triangles.vertices.at(i: idx[i] * 2)),
1870	float(triangles.vertices.at(i: idx[i] * 2 + 1))));
1871	}
1872	if (qFuzzyIsNull(f: determinant(p1: p[0], p2: p[1], p3: p[2])))
1873	continue; // Skip degenerate triangles
1874	bool needsSplit = !handleTriangle(p);
1875	if (needsSplit) {
1876	QVector2D c = (p[0] + p[1] + p[2]) / 3;
1877	for (int i = 0; i < 3; ++i) {
1878	qSwap(value1&: c, value2&: p[i]);
1879	handleTriangle(p);
1880	qSwap(value1&: c, value2&: p[i]);
1881	}
1882	}
1883	}
1884	}
1885
1886
1887	QT_END_NAMESPACE
1888