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 "qquickshapecurverenderer_p.h"
5	#include "qquickshapecurverenderer_p_p.h"
6	#include "qquickshapecurvenode_p.h"
7	#include "qquickshapestrokenode_p.h"
8
9	#include <QtGui/qvector2d.h>
10	#include <QtGui/qvector4d.h>
11	#include <QtGui/private/qtriangulator_p.h>
12	#include <QtGui/private/qtriangulatingstroker_p.h>
13	#include <QtGui/private/qrhi_p.h>
14
15	#include <QtQuick/qsgmaterial.h>
16
17	#include <QThread>
18
19	QT_BEGIN_NAMESPACE
20
21	Q_LOGGING_CATEGORY(lcShapeCurveRenderer, "qt.shape.curverenderer");
22
23	namespace {
24
25	class QQuickShapeWireFrameMaterialShader : public QSGMaterialShader
26	{
27	public:
28	QQuickShapeWireFrameMaterialShader()
29	{
30	setShaderFileName(stage: VertexStage,
31	QStringLiteral(":/qt-project.org/shapes/shaders_ng/wireframe.vert.qsb"));
32	setShaderFileName(stage: FragmentStage,
33	QStringLiteral(":/qt-project.org/shapes/shaders_ng/wireframe.frag.qsb"));
34	}
35
36	bool updateUniformData(RenderState &state, QSGMaterial *, QSGMaterial *) override
37	{
38	bool changed = false;
39	QByteArray *buf = state.uniformData();
40	Q_ASSERT(buf->size() >= 64);
41
42	if (state.isMatrixDirty()) {
43	const QMatrix4x4 m = state.combinedMatrix();
44
45	memcpy(dest: buf->data(), src: m.constData(), n: 64);
46	changed = true;
47	}
48
49	return changed;
50	}
51	};
52
53	class QQuickShapeWireFrameMaterial : public QSGMaterial
54	{
55	public:
56	QQuickShapeWireFrameMaterial()
57	{
58	setFlag(flags: Blending, on: true);
59	}
60
61	int compare(const QSGMaterial *other) const override
62	{
63	return (type() - other->type());
64	}
65
66	protected:
67	QSGMaterialType *type() const override
68	{
69	static QSGMaterialType t;
70	return &t;
71	}
72	QSGMaterialShader *createShader(QSGRendererInterface::RenderMode) const override
73	{
74	return new QQuickShapeWireFrameMaterialShader;
75	}
76
77	};
78
79	class QQuickShapeWireFrameNode : public QSGGeometryNode
80	{
81	public:
82	struct WireFrameVertex
83	{
84	float x, y, u, v, w;
85	};
86
87	QQuickShapeWireFrameNode()
88	{
89	setFlag(OwnsGeometry, true);
90	setGeometry(new QSGGeometry(attributes(), 0, 0));
91	activateMaterial();
92	}
93
94	void activateMaterial()
95	{
96	m_material.reset(other: new QQuickShapeWireFrameMaterial);
97	setMaterial(m_material.data());
98	}
99
100	static const QSGGeometry::AttributeSet &attributes()
101	{
102	static QSGGeometry::Attribute data[] = {
103	QSGGeometry::Attribute::createWithAttributeType(pos: 0, tupleSize: 2, primitiveType: QSGGeometry::FloatType, attributeType: QSGGeometry::PositionAttribute),
104	QSGGeometry::Attribute::createWithAttributeType(pos: 1, tupleSize: 3, primitiveType: QSGGeometry::FloatType, attributeType: QSGGeometry::TexCoordAttribute),
105	};
106	static QSGGeometry::AttributeSet attrs = { .count: 2, .stride: sizeof(WireFrameVertex), .attributes: data };
107	return attrs;
108	}
109
110	protected:
111	QScopedPointer<QQuickShapeWireFrameMaterial> m_material;
112	};
113	}
114
115
116	QQuickShapeCurveRenderer::~QQuickShapeCurveRenderer() { }
117
118	void QQuickShapeCurveRenderer::beginSync(int totalCount, bool *countChanged)
119	{
120	if (countChanged != nullptr && totalCount != m_paths.size())
121	*countChanged = true;
122	m_paths.resize(size: totalCount);
123	}
124
125	void QQuickShapeCurveRenderer::setPath(int index, const QQuickPath *path)
126	{
127	auto &pathData = m_paths[index];
128	pathData.originalPath = path->path();
129	pathData.m_dirty |= PathDirty;
130	}
131
132	void QQuickShapeCurveRenderer::setStrokeColor(int index, const QColor &color)
133	{
134	auto &pathData = m_paths[index];
135	const bool wasVisible = pathData.isStrokeVisible();
136	pathData.pen.setColor(color);
137	if (pathData.isStrokeVisible() != wasVisible)
138	pathData.m_dirty |= StrokeDirty;
139	else
140	pathData.m_dirty |= UniformsDirty;
141	}
142
143	void QQuickShapeCurveRenderer::setStrokeWidth(int index, qreal w)
144	{
145	auto &pathData = m_paths[index];
146	if (w > 0) {
147	pathData.validPenWidth = true;
148	pathData.pen.setWidthF(w);
149	} else {
150	pathData.validPenWidth = false;
151	}
152	pathData.m_dirty |= StrokeDirty;
153	}
154
155	void QQuickShapeCurveRenderer::setFillColor(int index, const QColor &color)
156	{
157	auto &pathData = m_paths[index];
158	const bool wasVisible = pathData.isFillVisible();
159	pathData.fillColor = color;
160	if (pathData.isFillVisible() != wasVisible)
161	pathData.m_dirty |= FillDirty;
162	else
163	pathData.m_dirty |= UniformsDirty;
164	}
165
166	void QQuickShapeCurveRenderer::setFillRule(int index, QQuickShapePath::FillRule fillRule)
167	{
168	auto &pathData = m_paths[index];
169	pathData.fillRule = Qt::FillRule(fillRule);
170	pathData.m_dirty |= PathDirty;
171	}
172
173	void QQuickShapeCurveRenderer::setJoinStyle(int index,
174	QQuickShapePath::JoinStyle joinStyle,
175	int miterLimit)
176	{
177	auto &pathData = m_paths[index];
178	pathData.pen.setJoinStyle(Qt::PenJoinStyle(joinStyle));
179	pathData.pen.setMiterLimit(miterLimit);
180	pathData.m_dirty |= StrokeDirty;
181	}
182
183	void QQuickShapeCurveRenderer::setCapStyle(int index, QQuickShapePath::CapStyle capStyle)
184	{
185	auto &pathData = m_paths[index];
186	pathData.pen.setCapStyle(Qt::PenCapStyle(capStyle));
187	pathData.m_dirty |= StrokeDirty;
188	}
189
190	void QQuickShapeCurveRenderer::setStrokeStyle(int index,
191	QQuickShapePath::StrokeStyle strokeStyle,
192	qreal dashOffset,
193	const QVector<qreal> &dashPattern)
194	{
195	auto &pathData = m_paths[index];
196	pathData.pen.setStyle(Qt::PenStyle(strokeStyle));
197	if (strokeStyle == QQuickShapePath::DashLine) {
198	pathData.pen.setDashPattern(dashPattern);
199	pathData.pen.setDashOffset(dashOffset);
200	}
201	pathData.m_dirty |= StrokeDirty;
202	}
203
204	void QQuickShapeCurveRenderer::setFillGradient(int index, QQuickShapeGradient *gradient)
205	{
206	PathData &pd(m_paths[index]);
207	pd.gradientType = NoGradient;
208	if (QQuickShapeLinearGradient *g = qobject_cast<QQuickShapeLinearGradient *>(object: gradient)) {
209	pd.gradientType = LinearGradient;
210	pd.gradient.stops = gradient->gradientStops();
211	pd.gradient.spread = gradient->spread();
212	pd.gradient.a = QPointF(g->x1(), g->y1());
213	pd.gradient.b = QPointF(g->x2(), g->y2());
214	} else if (QQuickShapeRadialGradient *g = qobject_cast<QQuickShapeRadialGradient *>(object: gradient)) {
215	pd.gradientType = RadialGradient;
216	pd.gradient.a = QPointF(g->centerX(), g->centerY());
217	pd.gradient.b = QPointF(g->focalX(), g->focalY());
218	pd.gradient.v0 = g->centerRadius();
219	pd.gradient.v1 = g->focalRadius();
220	} else if (QQuickShapeConicalGradient *g = qobject_cast<QQuickShapeConicalGradient *>(object: gradient)) {
221	pd.gradientType = ConicalGradient;
222	pd.gradient.a = QPointF(g->centerX(), g->centerY());
223	pd.gradient.v0 = g->angle();
224	} else
225	if (gradient != nullptr) {
226	static bool warned = false;
227	if (!warned) {
228	warned = true;
229	qCWarning(lcShapeCurveRenderer) << "Unsupported gradient fill";
230	}
231	}
232
233	if (pd.gradientType != NoGradient) {
234	pd.gradient.stops = gradient->gradientStops();
235	pd.gradient.spread = gradient->spread();
236	}
237
238	pd.m_dirty |= FillDirty;
239	}
240
241	void QQuickShapeCurveRenderer::setAsyncCallback(void (*callback)(void *), void *data)
242	{
243	qCWarning(lcShapeCurveRenderer) << "Asynchronous creation not supported by CurveRenderer";
244	Q_UNUSED(callback);
245	Q_UNUSED(data);
246	}
247
248	void QQuickShapeCurveRenderer::endSync(bool async)
249	{
250	Q_UNUSED(async);
251	}
252
253	void QQuickShapeCurveRenderer::updateNode()
254	{
255	if (!m_rootNode)
256	return;
257	static const bool doOverlapSolving = !qEnvironmentVariableIntValue(varName: "QT_QUICKSHAPES_DISABLE_OVERLAP_SOLVER");
258	static const bool useTriangulatingStroker = qEnvironmentVariableIntValue(varName: "QT_QUICKSHAPES_TRIANGULATING_STROKER");
259	static const bool simplifyPath = qEnvironmentVariableIntValue(varName: "QT_QUICKSHAPES_SIMPLIFY_PATHS");
260
261	for (PathData &pathData : m_paths) {
262	int dirtyFlags = pathData.m_dirty;
263
264	if (dirtyFlags & PathDirty) {
265	if (simplifyPath)
266	pathData.path = QQuadPath::fromPainterPath(path: pathData.originalPath.simplified());
267	else
268	pathData.path = QQuadPath::fromPainterPath(path: pathData.originalPath);
269	pathData.path.setFillRule(pathData.fillRule);
270	pathData.fillPath = {};
271	dirtyFlags |= (FillDirty | StrokeDirty);
272	}
273
274	if (dirtyFlags & FillDirty) {
275	deleteAndClear(nodeList: &pathData.fillNodes);
276	deleteAndClear(nodeList: &pathData.fillDebugNodes);
277	if (pathData.isFillVisible()) {
278	if (pathData.fillPath.isEmpty()) {
279	pathData.fillPath = pathData.path.subPathsClosed();
280	pathData.fillPath.addCurvatureData();
281	if (doOverlapSolving)
282	solveOverlaps(path&: pathData.fillPath);
283	}
284	pathData.fillNodes = addFillNodes(pathData, debugNodes: &pathData.fillDebugNodes);
285	dirtyFlags |= StrokeDirty;
286	}
287	}
288
289	if (dirtyFlags & StrokeDirty) {
290	deleteAndClear(nodeList: &pathData.strokeNodes);
291	deleteAndClear(nodeList: &pathData.strokeDebugNodes);
292	if (pathData.isStrokeVisible()) {
293	const QPen &pen = pathData.pen;
294	if (pen.style() == Qt::SolidLine)
295	pathData.strokePath = pathData.path;
296	else
297	pathData.strokePath = pathData.path.dashed(lineWidth: pen.widthF(), dashPattern: pen.dashPattern(), dashOffset: pen.dashOffset());
298
299	if (useTriangulatingStroker)
300	pathData.strokeNodes = addTriangulatingStrokerNodes(pathData, debugNodes: &pathData.strokeDebugNodes);
301	else
302	pathData.strokeNodes = addCurveStrokeNodes(pathData, debugNodes: &pathData.strokeDebugNodes);
303	}
304	}
305
306	if (dirtyFlags & UniformsDirty) {
307	if (!(dirtyFlags & FillDirty)) {
308	for (auto &pathNode : std::as_const(t&: pathData.fillNodes))
309	static_cast<QQuickShapeCurveNode *>(pathNode)->setColor(pathData.fillColor);
310	}
311	if (!(dirtyFlags & StrokeDirty)) {
312	if (useTriangulatingStroker) {
313	for (auto &strokeNode : std::as_const(t&: pathData.strokeNodes))
314	static_cast<QQuickShapeCurveNode *>(strokeNode)->setColor(pathData.pen.color());
315	} else {
316	for (auto &strokeNode : std::as_const(t&: pathData.strokeNodes))
317	static_cast<QQuickShapeStrokeNode *>(strokeNode)->setColor(pathData.pen.color());
318	}
319	}
320	}
321
322	pathData.m_dirty &= ~(PathDirty | FillDirty | StrokeDirty | UniformsDirty);
323	}
324	}
325
326	namespace {
327	// Input coordinate space is pre-mapped so that (0, 0) maps to [0, 0] in uv space.
328	// 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)
329	static inline QVector2D uvForPoint(QVector2D v1, QVector2D v2, QVector2D p)
330	{
331	double divisor = v1.x() * v2.y() - v2.x() * v1.y();
332
333	float u = (p.x() * v2.y() - p.y() * v2.x()) / divisor;
334	float v = (p.y() * v1.x() - p.x() * v1.y()) / divisor;
335
336	return {u, v};
337	}
338
339	// Find uv coordinates for the point p, for a quadratic curve from p0 to p2 with control point p1
340	// also works for a line from p0 to p2, where p1 is on the inside of the path relative to the line
341	static inline QVector2D curveUv(QVector2D p0, QVector2D p1, QVector2D p2, QVector2D p)
342	{
343	QVector2D v1 = 2 * (p1 - p0);
344	QVector2D v2 = p2 - v1 - p0;
345	return uvForPoint(v1, v2, p: p - p0);
346	}
347
348	static QVector3D elementUvForPoint(const QQuadPath::Element& e, QVector2D p)
349	{
350	auto uv = curveUv(p0: e.startPoint(), p1: e.controlPoint(), p2: e.endPoint(), p);
351	if (e.isLine())
352	return { uv.x(), uv.y(), 0.0f };
353	else
354	return { uv.x(), uv.y(), e.isConvex() ? -1.0f : 1.0f };
355	}
356
357	static inline QVector2D calcNormalVector(QVector2D a, QVector2D b)
358	{
359	auto v = b - a;
360	return {v.y(), -v.x()};
361	}
362
363	// The sign of the return value indicates which side of the line defined by a and n the point p falls
364	static inline float testSideOfLineByNormal(QVector2D a, QVector2D n, QVector2D p)
365	{
366	float dot = QVector2D::dotProduct(v1: p - a, v2: n);
367	return dot;
368	};
369
370	template<typename Func>
371	void iteratePath(const QQuadPath &path, int index, Func &&lambda)
372	{
373	const auto &element = path.elementAt(i: index);
374	if (element.childCount() == 0) {
375	lambda(element, index);
376	} else {
377	for (int i = 0; i < element.childCount(); ++i)
378	iteratePath(path, element.indexOfChild(childNumber: i), lambda);
379	}
380	}
381
382	static inline float determinant(const QVector2D &p1, const QVector2D &p2, const QVector2D &p3)
383	{
384	return p1.x() * (p2.y() - p3.y())
385	+ p2.x() * (p3.y() - p1.y())
386	+ p3.x() * (p1.y() - p2.y());
387	}
388	}
389
390	QVector<QSGGeometryNode *> QQuickShapeCurveRenderer::addFillNodes(const PathData &pathData,
391	NodeList *debugNodes)
392	{
393	auto *node = new QQuickShapeCurveNode;
394	node->setGradientType(pathData.gradientType);
395
396	QVector<QSGGeometryNode *> ret;
397	const QColor &color = pathData.fillColor;
398	QPainterPath internalHull;
399	internalHull.setFillRule(pathData.fillPath.fillRule());
400
401	bool visualizeDebug = debugVisualization() & DebugCurves;
402	const float dbg = visualizeDebug ? 0.5f : 0.0f;
403	node->setDebug(dbg);
404	QVector<QQuickShapeWireFrameNode::WireFrameVertex> wfVertices;
405
406	QHash<QPair<float, float>, int> linePointHash;
407	QHash<QPair<float, float>, int> concaveControlPointHash;
408	QHash<QPair<float, float>, int> convexPointHash;
409
410	auto toRoundedPair = [](const QPointF &p) -> QPair<float, float> {
411	return qMakePair(value1: qRound(d: p.x() * 32.0f) / 32.0f, value2: qRound(d: p.y() * 32.0f) / 32.0f);
412	};
413
414	auto toRoundedVec2D = [](const QPointF &p) -> QVector2D {
415	return { qRound(d: p.x() * 32.0f) / 32.0f, qRound(d: p.y() * 32.0f) / 32.0f };
416	};
417
418	auto roundVec2D = [](const QVector2D &p) -> QVector2D {
419	return { qRound(f: p.x() * 32.0f) / 32.0f, qRound(f: p.y() * 32.0f) / 32.0f };
420	};
421
422	auto addCurveTriangle = [&](const QQuadPath::Element &element,
423	const QVector2D &sp,
424	const QVector2D &ep,
425	const QVector2D &cp) {
426	node->appendTriangle(v1: sp, v2: cp, v3: ep,
427	uvForPoint: [&element](QVector2D v) { return elementUvForPoint(e: element, p: v); });
428
429	wfVertices.append(t: {.x: sp.x(), .y: sp.y(), .u: 1.0f, .v: 0.0f, .w: 0.0f}); // 0
430	wfVertices.append(t: {.x: cp.x(), .y: cp.y(), .u: 0.0f, .v: 1.0f, .w: 0.0f}); // 1
431	wfVertices.append(t: {.x: ep.x(), .y: ep.y(), .u: 0.0f, .v: 0.0f, .w: 1.0f}); // 2
432	};
433
434	auto addCurveTriangleWithNormals = [&](const QQuadPath::Element &element,
435	const std::array<QVector2D, 3> &v,
436	const std::array<QVector2D, 3> &n) {
437	node->appendTriangle(v, n, uvForPoint: [&element](QVector2D v) { return elementUvForPoint(e: element, p: v); });
438	wfVertices.append(t: {.x: v[0].x(), .y: v[0].y(), .u: 1.0f, .v: 0.0f, .w: 0.0f}); // 0
439	wfVertices.append(t: {.x: v[1].x(), .y: v[1].y(), .u: 0.0f, .v: 1.0f, .w: 0.0f}); // 1
440	wfVertices.append(t: {.x: v[2].x(), .y: v[2].y(), .u: 0.0f, .v: 0.0f, .w: 1.0f}); // 2
441	};
442
443	auto outsideNormal = [](const QVector2D &startPoint,
444	const QVector2D &endPoint,
445	const QVector2D &insidePoint) {
446
447	QVector2D baseLine = endPoint - startPoint;
448	QVector2D insideVector = insidePoint - startPoint;
449	QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()).normalized();
450
451	bool swap = QVector2D::dotProduct(v1: insideVector, v2: normal) < 0;
452
453	return swap ? normal : -normal;
454	};
455
456	auto addTriangleForLine = [&](const QQuadPath::Element &element,
457	const QVector2D &sp,
458	const QVector2D &ep,
459	const QVector2D &cp) {
460	addCurveTriangle(element, sp, ep, cp);
461
462	// Add triangles on the outer side to make room for AA
463	const QVector2D normal = outsideNormal(sp, ep, cp);
464	constexpr QVector2D null;
465	addCurveTriangleWithNormals(element, {sp, sp, ep}, {null, normal, null});
466	addCurveTriangleWithNormals(element, {sp, ep, ep}, {normal, normal, null});
467	};
468
469	auto addTriangleForConcave = [&](const QQuadPath::Element &element,
470	const QVector2D &sp,
471	const QVector2D &ep,
472	const QVector2D &cp) {
473	addTriangleForLine(element, sp, ep, cp);
474	};
475
476	auto addTriangleForConvex = [&](const QQuadPath::Element &element,
477	const QVector2D &sp,
478	const QVector2D &ep,
479	const QVector2D &cp) {
480	addCurveTriangle(element, sp, ep, cp);
481	// Add two triangles on the outer side to get some more AA
482
483	constexpr QVector2D null;
484	// First triangle on the line sp-cp, replacing ep
485	{
486	const QVector2D normal = outsideNormal(sp, cp, ep);
487	addCurveTriangleWithNormals(element, {sp, sp, cp}, {null, normal, null});
488	}
489
490	// Second triangle on the line ep-cp, replacing sp
491	{
492	const QVector2D normal = outsideNormal(ep, cp, sp);
493	addCurveTriangleWithNormals(element, {ep, ep, cp}, {null, normal, null});
494	}
495	};
496
497	auto addFillTriangle = [&](const QVector2D &p1, const QVector2D &p2, const QVector2D &p3) {
498	constexpr QVector3D uv(0.0, 1.0, -1.0);
499	node->appendTriangle(v1: p1, v2: p2, v3: p3, uvForPoint: [&uv](QVector2D) { return uv; } );
500
501	wfVertices.append(t: {.x: p1.x(), .y: p1.y(), .u: 1.0f, .v: 0.0f, .w: 0.0f}); // 0
502	wfVertices.append(t: {.x: p3.x(), .y: p3.y(), .u: 0.0f, .v: 1.0f, .w: 0.0f}); // 1
503	wfVertices.append(t: {.x: p2.x(), .y: p2.y(), .u: 0.0f, .v: 0.0f, .w: 1.0f}); // 2
504	};
505
506	for (int i = 0; i < pathData.fillPath.elementCount(); ++i) {
507	iteratePath(path: pathData.fillPath, index: i, lambda: [&](const QQuadPath::Element &element, int index) {
508	QPointF sp(element.startPoint().toPointF()); //### to much conversion to and from pointF
509	QPointF cp(element.controlPoint().toPointF());
510	QPointF ep(element.endPoint().toPointF());
511	if (element.isSubpathStart())
512	internalHull.moveTo(p: sp);
513	if (element.isLine()) {
514	internalHull.lineTo(p: ep);
515	linePointHash.insert(key: toRoundedPair(sp), value: index);
516	} else {
517	if (element.isConvex()) {
518	internalHull.lineTo(p: ep);
519	addTriangleForConvex(element, toRoundedVec2D(sp), toRoundedVec2D(ep), toRoundedVec2D(cp));
520	convexPointHash.insert(key: toRoundedPair(sp), value: index);
521	} else {
522	internalHull.lineTo(p: cp);
523	internalHull.lineTo(p: ep);
524	addTriangleForConcave(element, toRoundedVec2D(sp), toRoundedVec2D(ep), toRoundedVec2D(cp));
525	concaveControlPointHash.insert(key: toRoundedPair(cp), value: index);
526	}
527	}
528	});
529	}
530
531	auto makeHashable = [](const QVector2D &p) -> QPair<float, float> {
532	return qMakePair(value1: qRound(f: p.x() * 32.0f) / 32.0f, value2: qRound(f: p.y() * 32.0f) / 32.0f);
533	};
534	// Points in p are already rounded do 1/32
535	// Returns false if the triangle needs to be split. Adds the triangle to the graphics buffers and returns true otherwise.
536	// (Does not handle ambiguous vertices that are on multiple unrelated lines/curves)
537	auto onSameSideOfLine = [](const QVector2D &p1,
538	const QVector2D &p2,
539	const QVector2D &linePoint,
540	const QVector2D &lineNormal) {
541	float side1 = testSideOfLineByNormal(a: linePoint, n: lineNormal, p: p1);
542	float side2 = testSideOfLineByNormal(a: linePoint, n: lineNormal, p: p2);
543	return side1 * side2 >= 0;
544	};
545
546	auto pointInSafeSpace = [&](const QVector2D &p, const QQuadPath::Element &element) -> bool {
547	const QVector2D a = element.startPoint();
548	const QVector2D b = element.endPoint();
549	const QVector2D c = element.controlPoint();
550	// There are "safe" areas of the curve also across the baseline: the curve can never cross:
551	// line1: the line through A and B'
552	// line2: the line through B and A'
553	// Where A' = A "mirrored" through C and B' = B "mirrored" through C
554	const QVector2D n1 = calcNormalVector(a, b: c + (c - b));
555	const QVector2D n2 = calcNormalVector(a: b, b: c + (c - a));
556	bool safeSideOf1 = onSameSideOfLine(p, c, a, n1);
557	bool safeSideOf2 = onSameSideOfLine(p, c, b, n2);
558	return safeSideOf1 && safeSideOf2;
559	};
560
561	auto handleTriangle = [&](const QVector2D (&p)[3]) -> bool {
562	int lineElementIndex = -1;
563	int concaveElementIndex = -1;
564	int convexElementIndex = -1;
565
566	bool foundElement = false;
567	int si = -1;
568	int ei = -1;
569	for (int i = 0; i < 3; ++i) {
570	if (auto found = linePointHash.constFind(key: makeHashable(p[i])); found != linePointHash.constEnd()) {
571	// check if this triangle is on a line, i.e. if one point is the sp and another is the ep of the same path element
572	const auto &element = pathData.fillPath.elementAt(i: *found);
573	for (int j = 0; j < 3; ++j) {
574	if (i != j && roundVec2D(element.endPoint()) == p[j]) {
575	if (foundElement)
576	return false; // More than one edge on path: must split
577	lineElementIndex = *found;
578	si = i;
579	ei = j;
580	foundElement = true;
581	}
582	}
583	} else if (auto found = concaveControlPointHash.constFind(key: makeHashable(p[i])); found != concaveControlPointHash.constEnd()) {
584	// check if this triangle is on the tangent line of a concave curve,
585	// i.e if one point is the cp, and the other is sp or ep
586	// TODO: clean up duplicated code (almost the same as the lineElement path above)
587	const auto &element = pathData.fillPath.elementAt(i: *found);
588	for (int j = 0; j < 3; ++j) {
589	if (i == j)
590	continue;
591	if (roundVec2D(element.startPoint()) == p[j] || roundVec2D(element.endPoint()) == p[j]) {
592	if (foundElement)
593	return false; // More than one edge on path: must split
594	concaveElementIndex = *found;
595	// The tangent line is p[i] - p[j]
596	si = i;
597	ei = j;
598	foundElement = true;
599	}
600	}
601	} else if (auto found = convexPointHash.constFind(key: makeHashable(p[i])); found != convexPointHash.constEnd()) {
602	// check if this triangle is on a curve, i.e. if one point is the sp and another is the ep of the same path element
603	const auto &element = pathData.fillPath.elementAt(i: *found);
604	for (int j = 0; j < 3; ++j) {
605	if (i != j && roundVec2D(element.endPoint()) == p[j]) {
606	if (foundElement)
607	return false; // More than one edge on path: must split
608	convexElementIndex = *found;
609	si = i;
610	ei = j;
611	foundElement = true;
612	}
613	}
614	}
615	}
616	if (lineElementIndex != -1) {
617	int ci = (6 - si - ei) % 3; // 1+2+3 is 6, so missing number is 6-n1-n2
618	addTriangleForLine(pathData.fillPath.elementAt(i: lineElementIndex), p[si], p[ei], p[ci]);
619	} else if (concaveElementIndex != -1) {
620	addCurveTriangle(pathData.fillPath.elementAt(i: concaveElementIndex), p[0], p[1], p[2]);
621	} else if (convexElementIndex != -1) {
622	int oi = (6 - si - ei) % 3;
623	const auto &otherPoint = p[oi];
624	const auto &element = pathData.fillPath.elementAt(i: convexElementIndex);
625	// We have to test whether the triangle can cross the line
626	// TODO: use the toplevel element's safe space
627	bool safeSpace = pointInSafeSpace(otherPoint, element);
628	if (safeSpace) {
629	addCurveTriangle(element, p[0], p[1], p[2]);
630	} else {
631	// Find a point inside the triangle that's also in the safe space
632	QVector2D newPoint = (p[0] + p[1] + p[2]) / 3;
633	// We should calculate the point directly, but just do a lazy implementation for now:
634	for (int i = 0; i < 7; ++i) {
635	safeSpace = pointInSafeSpace(newPoint, element);
636	if (safeSpace)
637	break;
638	newPoint = (p[si] + p[ei] + newPoint) / 3;
639	}
640	if (safeSpace) {
641	// Split triangle. We know the original triangle is only on one path element, so the other triangles are both fill.
642	// Curve triangle is (sp, ep, np)
643	addCurveTriangle(element, p[si], p[ei], newPoint);
644	// The other two are (sp, op, np) and (ep, op, np)
645	addFillTriangle(p[si], p[oi], newPoint);
646	addFillTriangle(p[ei], p[oi], newPoint);
647	} else {
648	// fallback to fill if we can't find a point in safe space
649	addFillTriangle(p[0], p[1], p[2]);
650	}
651	}
652
653	} else {
654	addFillTriangle(p[0], p[1], p[2]);
655	}
656	return true;
657	};
658
659	QTriangleSet triangles = qTriangulate(path: internalHull);
660
661	const quint32 *idxTable = static_cast<const quint32 *>(triangles.indices.data());
662	for (int triangle = 0; triangle < triangles.indices.size() / 3; ++triangle) {
663	const quint32 *idx = &idxTable[triangle * 3];
664
665	QVector2D p[3];
666	for (int i = 0; i < 3; ++i) {
667	p[i] = toRoundedVec2D(QPointF(triangles.vertices.at(i: idx[i] * 2),
668	triangles.vertices.at(i: idx[i] * 2 + 1)));
669	}
670	if (qFuzzyIsNull(f: determinant(p1: p[0], p2: p[1], p3: p[2])))
671	continue; // Skip degenerate triangles
672	bool needsSplit = !handleTriangle(p);
673	if (needsSplit) {
674	QVector2D c = (p[0] + p[1] + p[2]) / 3;
675	for (int i = 0; i < 3; ++i) {
676	qSwap(value1&: c, value2&: p[i]);
677	handleTriangle(p);
678	qSwap(value1&: c, value2&: p[i]);
679	}
680	}
681	}
682
683	QVector<quint32> indices = node->uncookedIndexes();
684	if (indices.size() > 0) {
685	node->setColor(color);
686	node->setFillGradient(pathData.gradient);
687
688	node->cookGeometry();
689	m_rootNode->appendChildNode(node);
690	ret.append(t: node);
691	}
692
693	const bool wireFrame = debugVisualization() & DebugWireframe;
694	if (wireFrame) {
695	QQuickShapeWireFrameNode *wfNode = new QQuickShapeWireFrameNode;
696	QSGGeometry *wfg = new QSGGeometry(QQuickShapeWireFrameNode::attributes(),
697	wfVertices.size(),
698	indices.size(),
699	QSGGeometry::UnsignedIntType);
700	wfNode->setGeometry(wfg);
701
702	wfg->setDrawingMode(QSGGeometry::DrawTriangles);
703	memcpy(dest: wfg->indexData(),
704	src: indices.data(),
705	n: indices.size() * wfg->sizeOfIndex());
706	memcpy(dest: wfg->vertexData(),
707	src: wfVertices.data(),
708	n: wfg->vertexCount() * wfg->sizeOfVertex());
709
710	m_rootNode->appendChildNode(node: wfNode);
711	debugNodes->append(t: wfNode);
712	}
713
714	return ret;
715	}
716
717	QVector<QSGGeometryNode *> QQuickShapeCurveRenderer::addTriangulatingStrokerNodes(const PathData &pathData, NodeList *debugNodes)
718	{
719	QVector<QSGGeometryNode *> ret;
720	const QColor &color = pathData.pen.color();
721
722	QVector<QQuickShapeWireFrameNode::WireFrameVertex> wfVertices;
723
724	QTriangulatingStroker stroker;
725	const auto painterPath = pathData.strokePath.toPainterPath();
726	const QVectorPath &vp = qtVectorPathForPath(path: painterPath);
727	QPen pen = pathData.pen;
728	stroker.process(path: vp, pen, clip: {}, hints: {});
729
730	auto *node = new QQuickShapeCurveNode;
731	node->setGradientType(pathData.gradientType);
732
733	auto findPointOtherSide = [](const QVector2D &startPoint, const QVector2D &endPoint, const QVector2D &referencePoint){
734
735	QVector2D baseLine = endPoint - startPoint;
736	QVector2D insideVector = referencePoint - startPoint;
737	QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()); // TODO: limit size of triangle
738
739	bool swap = QVector2D::dotProduct(v1: insideVector, v2: normal) < 0;
740
741	return swap ? startPoint + normal : startPoint - normal;
742	};
743
744	static bool disableExtraTriangles = qEnvironmentVariableIntValue(varName: "QT_QUICKSHAPES_WIP_DISABLE_EXTRA_STROKE_TRIANGLES");
745
746	auto addStrokeTriangle = [&](const QVector2D &p1, const QVector2D &p2, const QVector2D &p3, bool){
747	if (p1 == p2 || p2 == p3) {
748	return;
749	}
750
751	auto uvForPoint = [&p1, &p2, &p3](QVector2D p) {
752	auto uv = curveUv(p0: p1, p1: p2, p2: p3, p);
753	return QVector3D(uv.x(), uv.y(), 0.0f); // Line
754	};
755
756	node->appendTriangle(v1: p1, v2: p2, v3: p3, uvForPoint);
757
758
759	wfVertices.append(t: {.x: p1.x(), .y: p1.y(), .u: 1.0f, .v: 0.0f, .w: 0.0f}); // 0
760	wfVertices.append(t: {.x: p2.x(), .y: p2.y(), .u: 0.0f, .v: 0.1f, .w: 0.0f}); // 1
761	wfVertices.append(t: {.x: p3.x(), .y: p3.y(), .u: 0.0f, .v: 0.0f, .w: 1.0f}); // 2
762
763	if (!disableExtraTriangles) {
764	// Add a triangle on the outer side of the line to get some more AA
765	// The new point replaces p2 (currentVertex+1)
766	QVector2D op = findPointOtherSide(p1, p3, p2);
767	node->appendTriangle(v1: p1, v2: op, v3: p3, uvForPoint);
768
769	wfVertices.append(t: {.x: p1.x(), .y: p1.y(), .u: 1.0f, .v: 0.0f, .w: 0.0f});
770	wfVertices.append(t: {.x: op.x(), .y: op.y(), .u: 0.0f, .v: 1.0f, .w: 0.0f}); // replacing p2
771	wfVertices.append(t: {.x: p3.x(), .y: p3.y(), .u: 0.0f, .v: 0.0f, .w: 1.0f});
772	}
773	};
774
775	const int vertCount = stroker.vertexCount() / 2;
776	const float *verts = stroker.vertices();
777	for (int i = 0; i < vertCount - 2; ++i) {
778	QVector2D p[3];
779	for (int j = 0; j < 3; ++j) {
780	p[j] = QVector2D(verts[(i+j)*2], verts[(i+j)*2 + 1]);
781	}
782	bool isOdd = i % 2;
783	addStrokeTriangle(p[0], p[1], p[2], isOdd);
784	}
785
786	QVector<quint32> indices = node->uncookedIndexes();
787	if (indices.size() > 0) {
788	node->setColor(color);
789	node->setFillGradient(pathData.gradient);
790
791	node->cookGeometry();
792	m_rootNode->appendChildNode(node);
793	ret.append(t: node);
794	}
795	const bool wireFrame = debugVisualization() & DebugWireframe;
796	if (wireFrame) {
797	QQuickShapeWireFrameNode *wfNode = new QQuickShapeWireFrameNode;
798	QSGGeometry *wfg = new QSGGeometry(QQuickShapeWireFrameNode::attributes(),
799	wfVertices.size(),
800	indices.size(),
801	QSGGeometry::UnsignedIntType);
802	wfNode->setGeometry(wfg);
803
804	wfg->setDrawingMode(QSGGeometry::DrawTriangles);
805	memcpy(dest: wfg->indexData(),
806	src: indices.data(),
807	n: indices.size() * wfg->sizeOfIndex());
808	memcpy(dest: wfg->vertexData(),
809	src: wfVertices.data(),
810	n: wfg->vertexCount() * wfg->sizeOfVertex());
811
812	m_rootNode->appendChildNode(node: wfNode);
813	debugNodes->append(t: wfNode);
814	}
815
816	return ret;
817	}
818
819	void QQuickShapeCurveRenderer::setRootNode(QSGNode *node)
820	{
821	m_rootNode = node;
822	}
823
824	int QQuickShapeCurveRenderer::debugVisualizationFlags = QQuickShapeCurveRenderer::NoDebug;
825
826	int QQuickShapeCurveRenderer::debugVisualization()
827	{
828	static const int envFlags = qEnvironmentVariableIntValue(varName: "QT_QUICKSHAPES_DEBUG");
829	return debugVisualizationFlags | envFlags;
830	}
831
832	void QQuickShapeCurveRenderer::setDebugVisualization(int options)
833	{
834	if (debugVisualizationFlags == options)
835	return;
836	debugVisualizationFlags = options;
837	}
838
839	void QQuickShapeCurveRenderer::deleteAndClear(NodeList *nodeList)
840	{
841	for (QSGNode *node : std::as_const(t&: *nodeList))
842	delete node;
843	nodeList->clear();
844	}
845
846	namespace {
847
848	/*
849	Clever triangle overlap algorithm. Stack Overflow says:
850
851	You can prove that the two triangles do not collide by finding an edge (out of the total 6
852	edges that make up the two triangles) that acts as a separating line where all the vertices
853	of one triangle lie on one side and the vertices of the other triangle lie on the other side.
854	If you can find such an edge then it means that the triangles do not intersect otherwise the
855	triangles are colliding.
856	*/
857	using TrianglePoints = std::array<QVector2D, 3>;
858	using LinePoints = std::array<QVector2D, 2>;
859
860	// The sign of the determinant tells the winding order: positive means counter-clockwise
861
862	static inline double determinant(const TrianglePoints &p)
863	{
864	return determinant(p1: p[0], p2: p[1], p3: p[2]);
865	}
866
867	// Fix the triangle so that the determinant is positive
868	static void fixWinding(TrianglePoints &p)
869	{
870	double det = determinant(p);
871	if (det < 0.0) {
872	qSwap(value1&: p[0], value2&: p[1]);
873	}
874	}
875
876	// Return true if the determinant is negative, i.e. if the winding order is opposite of the triangle p1,p2,p3.
877	// This means that p is strictly on the other side of p1-p2 relative to p3 [where p1,p2,p3 is a triangle with
878	// a positive determinant].
879	bool checkEdge(QVector2D &p1, QVector2D &p2, QVector2D &p, float epsilon)
880	{
881	return determinant(p1, p2, p3: p) <= epsilon;
882	}
883
884
885	bool checkTriangleOverlap(TrianglePoints &triangle1, TrianglePoints &triangle2, float epsilon = 1.0/32)
886	{
887	// See if there is an edge of triangle1 such that all vertices in triangle2 are on the opposite side
888	fixWinding(p&: triangle1);
889	for (int i = 0; i < 3; i++) {
890	int ni = (i + 1) % 3;
891	if (checkEdge(p1&: triangle1[i], p2&: triangle1[ni], p&: triangle2[0], epsilon) &&
892	checkEdge(p1&: triangle1[i], p2&: triangle1[ni], p&: triangle2[1], epsilon) &&
893	checkEdge(p1&: triangle1[i], p2&: triangle1[ni], p&: triangle2[2], epsilon))
894	return false;
895	}
896
897	// See if there is an edge of triangle2 such that all vertices in triangle1 are on the opposite side
898	fixWinding(p&: triangle2);
899	for (int i = 0; i < 3; i++) {
900	int ni = (i + 1) % 3;
901
902	if (checkEdge(p1&: triangle2[i], p2&: triangle2[ni], p&: triangle1[0], epsilon) &&
903	checkEdge(p1&: triangle2[i], p2&: triangle2[ni], p&: triangle1[1], epsilon) &&
904	checkEdge(p1&: triangle2[i], p2&: triangle2[ni], p&: triangle1[2], epsilon))
905	return false;
906	}
907
908	return true;
909	}
910
911	bool checkLineTriangleOverlap(TrianglePoints &triangle, LinePoints &line, float epsilon = 1.0/32)
912	{
913	// See if all vertices of the triangle are on the same side of the line
914	bool s1 = determinant(p1: line[0], p2: line[1], p3: triangle[0]) < 0;
915	auto s2 = determinant(p1: line[0], p2: line[1], p3: triangle[1]) < 0;
916	auto s3 = determinant(p1: line[0], p2: line[1], p3: triangle[2]) < 0;
917	// If all determinants have the same sign, then there is no overlap
918	if (s1 == s2 && s2 == s3) {
919	return false;
920	}
921	// See if there is an edge of triangle1 such that both vertices in line are on the opposite side
922	fixWinding(p&: triangle);
923	for (int i = 0; i < 3; i++) {
924	int ni = (i + 1) % 3;
925	if (checkEdge(p1&: triangle[i], p2&: triangle[ni], p&: line[0], epsilon) &&
926	checkEdge(p1&: triangle[i], p2&: triangle[ni], p&: line[1], epsilon))
927	return false;
928	}
929
930	return true;
931	}
932
933	// We could slightly optimize this if we did fixWinding in advance
934	bool checkTriangleContains (QVector2D pt, QVector2D v1, QVector2D v2, QVector2D v3, float epsilon = 1.0/32)
935	{
936	float d1, d2, d3;
937	d1 = determinant(p1: pt, p2: v1, p3: v2);
938	d2 = determinant(p1: pt, p2: v2, p3: v3);
939	d3 = determinant(p1: pt, p2: v3, p3: v1);
940
941	bool allNegative = d1 < -epsilon && d2 < -epsilon && d3 < -epsilon;
942	bool allPositive = d1 > epsilon && d2 > epsilon && d3 > epsilon;
943
944	return allNegative || allPositive;
945	}
946
947	// e1 is always a concave curve. e2 can be curve or line
948	static bool isOverlap(const QQuadPath &path, int e1, int e2)
949	{
950	const QQuadPath::Element &element1 = path.elementAt(i: e1);
951	const QQuadPath::Element &element2 = path.elementAt(i: e2);
952
953	TrianglePoints t1{ element1.startPoint(), element1.controlPoint(), element1.endPoint() };
954
955	if (element2.isLine()) {
956	LinePoints line{ element2.startPoint(), element2.endPoint() };
957	return checkLineTriangleOverlap(triangle&: t1, line);
958	} else {
959	TrianglePoints t2{ element2.startPoint(), element2.controlPoint(), element2.endPoint() };
960	return checkTriangleOverlap(triangle1&: t1, triangle2&: t2);
961	}
962
963	return false;
964	}
965
966	static bool isOverlap(const QQuadPath &path, int index, const QVector2D &vertex)
967	{
968	const QQuadPath::Element &elem = path.elementAt(i: index);
969	return checkTriangleContains(pt: vertex, v1: elem.startPoint(), v2: elem.controlPoint(), v3: elem.endPoint());
970	}
971
972	struct TriangleData
973	{
974	TrianglePoints points;
975	int pathElementIndex;
976	TrianglePoints normals;
977	};
978
979	// Returns a vector that is normal to baseLine, pointing to the right
980	QVector2D normalVector(QVector2D baseLine)
981	{
982	QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()).normalized();
983	return normal;
984	}
985
986	// Returns a vector that is normal to the path and pointing to the right. If endSide is false
987	// the vector is normal to the start point, otherwise to the end point
988	QVector2D normalVector(const QQuadPath::Element &element, bool endSide = false)
989	{
990	if (element.isLine())
991	return normalVector(baseLine: element.endPoint() - element.startPoint());
992	else if (!endSide)
993	return normalVector(baseLine: element.controlPoint() - element.startPoint());
994	else
995	return normalVector(baseLine: element.endPoint() - element.controlPoint());
996	}
997
998	// Returns a vector that is parallel to the path. If endSide is false
999	// the vector starts at the start point and points forward,
1000	// otherwise it starts at the end point and points backward
1001	QVector2D tangentVector(const QQuadPath::Element &element, bool endSide = false)
1002	{
1003	if (element.isLine()) {
1004	if (!endSide)
1005	return element.endPoint() - element.startPoint();
1006	else
1007	return element.startPoint() - element.endPoint();
1008	} else {
1009	if (!endSide)
1010	return element.controlPoint() - element.startPoint();
1011	else
1012	return element.controlPoint() - element.endPoint();
1013	}
1014	}
1015
1016	// Really simplistic O(n^2) triangulator - only intended for five points
1017	QList<TriangleData> simplePointTriangulator(const QList<QVector2D> &pts, const QList<QVector2D> &normals, int elementIndex)
1018	{
1019	int count = pts.size();
1020	Q_ASSERT(count >= 3);
1021	Q_ASSERT(normals.size() == count);
1022
1023	// First we find the convex hull: it's always in positive determinant winding order
1024	QList<int> hull;
1025	float det1 = determinant(p1: pts[0], p2: pts[1], p3: pts[2]);
1026	if (det1 > 0)
1027	hull << 0 << 1 << 2;
1028	else
1029	hull << 2 << 1 << 0;
1030	auto connectableInHull = [&](int idx) -> QList<int> {
1031	QList<int> r;
1032	const int n = hull.size();
1033	const auto &pt = pts[idx];
1034	for (int i = 0; i < n; ++i) {
1035	const auto &i1 = hull.at(i);
1036	const auto &i2 = hull.at(i: (i+1) % n);
1037	if (determinant(p1: pts[i1], p2: pts[i2], p3: pt) < 0.0f)
1038	r << i;
1039	}
1040	return r;
1041	};
1042	for (int i = 3; i < count; ++i) {
1043	auto visible = connectableInHull(i);
1044	if (visible.isEmpty())
1045	continue;
1046	int visCount = visible.count();
1047	int hullCount = hull.count();
1048	// Find where the visible part of the hull starts. (This is the part we need to triangulate to,
1049	// and the part we're going to replace. "visible" contains the start point of the line segments that are visible from p.
1050	int boundaryStart = visible[0];
1051	for (int j = 0; j < visCount - 1; ++j) {
1052	if ((visible[j] + 1) % hullCount != visible[j+1]) {
1053	boundaryStart = visible[j + 1];
1054	break;
1055	}
1056	}
1057	// Finally replace the points that are now inside the hull
1058	// We insert the new point after boundaryStart, and before boundaryStart + visCount (modulo...)
1059	// and remove the points in between
1060	int pointsToKeep = hullCount - visCount + 1;
1061	QList<int> newHull;
1062	newHull << i;
1063	for (int j = 0; j < pointsToKeep; ++j) {
1064	newHull << hull.at(i: (j + boundaryStart + visCount) % hullCount);
1065	}
1066	hull = newHull;
1067	}
1068
1069	// Now that we have a convex hull, we can trivially triangulate it
1070	QList<TriangleData> ret;
1071	for (int i = 1; i < hull.size() - 1; ++i) {
1072	int i0 = hull[0];
1073	int i1 = hull[i];
1074	int i2 = hull[i+1];
1075	ret.append(t: {.points: {pts[i0], pts[i1], pts[i2]}, .pathElementIndex: elementIndex, .normals: {normals[i0], normals[i1], normals[i2]}});
1076	}
1077	return ret;
1078	}
1079
1080	static bool needsSplit(const QQuadPath::Element &el, float penWidth)
1081	{
1082	Q_UNUSED(penWidth)
1083	const auto v1 = el.controlPoint() - el.startPoint();
1084	const auto v2 = el.endPoint() - el.controlPoint();
1085	float cos = QVector2D::dotProduct(v1, v2) / (v1.length() * v2.length());
1086	return cos < 0.9;
1087	}
1088	static void splitElementIfNecessary(QQuadPath &path, int index, float penWidth)
1089	{
1090	auto &e = path.elementAt(i: index);
1091	if (e.isLine())
1092	return;
1093	if (e.childCount() == 0) {
1094	if (needsSplit(el: e, penWidth))
1095	path.splitElementAt(index);
1096	} else {
1097	for (int i = 0; i < e.childCount(); ++i)
1098	splitElementIfNecessary(path, index: e.indexOfChild(childNumber: i), penWidth);
1099	}
1100	}
1101
1102	static QQuadPath subdivide(const QQuadPath &path, int subdivisions, float penWidth)
1103	{
1104	QQuadPath newPath = path;
1105
1106	for (int i = 0; i < subdivisions; ++i)
1107	for (int j = 0; j < newPath.elementCount(); j++)
1108	splitElementIfNecessary(path&: newPath, index: j, penWidth);
1109	return newPath;
1110	}
1111
1112	static QList<TriangleData> customTriangulator2(const QQuadPath &path, float penWidth, Qt::PenJoinStyle joinStyle, Qt::PenCapStyle capStyle, float miterLimit)
1113	{
1114	const bool bevelJoin = joinStyle == Qt::BevelJoin;
1115	const bool roundJoin = joinStyle == Qt::RoundJoin;
1116	const bool miterJoin = !bevelJoin && !roundJoin;
1117
1118	const bool roundCap = capStyle == Qt::RoundCap;
1119	const bool squareCap = capStyle == Qt::SquareCap;
1120	// We can't use the simple miter for miter joins, since the shader currently only supports round joins
1121	const bool simpleMiter = joinStyle == Qt::RoundJoin;
1122
1123	Q_ASSERT(miterLimit > 0 || !miterJoin);
1124	float inverseMiterLimit = miterJoin ? 1.0f / miterLimit : 1.0;
1125
1126	const float penFactor = penWidth / 2;
1127
1128	// Returns {inner1, inner2, outer1, outer2, outerMiter}
1129	// where foo1 is for the end of element1 and foo2 is for the start of element2
1130	// and inner1 == inner2 unless we had to give up finding a decent point
1131	auto calculateJoin = [&](const QQuadPath::Element *element1, const QQuadPath::Element *element2,
1132	bool &outerBisectorWithinMiterLimit, bool &innerIsRight, bool &giveUp) -> std::array<QVector2D, 5>
1133	{
1134	outerBisectorWithinMiterLimit = true;
1135	innerIsRight = true;
1136	giveUp = false;
1137	if (!element1) {
1138	Q_ASSERT(element2);
1139	QVector2D n = normalVector(element: *element2).normalized();
1140	return {n, n, -n, -n, -n};
1141	}
1142	if (!element2) {
1143	Q_ASSERT(element1);
1144	QVector2D n = normalVector(element: *element1, endSide: true).normalized();
1145	return {n, n, -n, -n, -n};
1146	}
1147
1148	Q_ASSERT(element1->endPoint() == element2->startPoint());
1149
1150	const auto p1 = element1->isLine() ? element1->startPoint() : element1->controlPoint();
1151	const auto p2 = element1->endPoint();
1152	const auto p3 = element2->isLine() ? element2->endPoint() : element2->controlPoint();
1153
1154	const auto v1 = (p1 - p2).normalized();
1155	const auto v2 = (p3 - p2).normalized();
1156	const auto b = (v1 + v2);
1157
1158	constexpr float epsilon = 1.0f / 32.0f;
1159	bool smoothJoin = qAbs(t: b.x()) < epsilon && qAbs(t: b.y()) < epsilon;
1160
1161	if (smoothJoin) {
1162	// v1 and v2 are almost parallel and pointing in opposite directions
1163	// angle bisector formula will give an almost null vector: use normal of bisector of normals instead
1164	QVector2D n1(-v1.y(), v1.x());
1165	QVector2D n2(-v2.y(), v2.x());
1166	QVector2D n = (n2 - n1).normalized();
1167	return {n, n, -n, -n, -n};
1168	}
1169	// Calculate the length of the bisector, so it will cover the entire miter.
1170	// Using the identity sin(x/2) == sqrt((1 - cos(x)) / 2), and the fact that the
1171	// dot product of two unit vectors is the cosine of the angle between them
1172	// The length of the miter is w/sin(x/2) where x is the angle between the two elements
1173
1174	const auto bisector = b.normalized();
1175	float cos2x = QVector2D::dotProduct(v1, v2);
1176	cos2x = qMin(a: 1.0f, b: cos2x); // Allow for float inaccuracy
1177	float sine = sqrt(x: (1.0f - cos2x) / 2);
1178	innerIsRight = determinant(p1, p2, p3) > 0;
1179	sine = qMax(a: sine, b: 0.01f); // Avoid divide by zero
1180	float length = penFactor / sine;
1181
1182	// Check if bisector is longer than one of the lines it's trying to bisect
1183
1184	auto tooLong = [](QVector2D p1, QVector2D p2, QVector2D n, float length, float margin) -> bool {
1185	auto v = p2 - p1;
1186	// It's too long if the projection onto the bisector is longer than the bisector
1187	// and the projection onto the normal to the bisector is shorter
1188	// than the pen margin (that projection is just v - proj)
1189	// (we're adding a 10% safety margin to make room for AA -- not exact)
1190	auto projLen = QVector2D::dotProduct(v1: v, v2: n);
1191	return projLen * 0.9f < length && (v - n * projLen).length() * 0.9 < margin;
1192	};
1193
1194
1195	// The angle bisector of the tangent lines is not correct for curved lines. We could fix this by calculating
1196	// the exact intersection point, but for now just give up and use the normals.
1197
1198	giveUp = !element1->isLine() || !element2->isLine()
1199	|| tooLong(p1, p2, bisector, length, penFactor)
1200	|| tooLong(p3, p2, bisector, length, penFactor);
1201	outerBisectorWithinMiterLimit = sine >= inverseMiterLimit / 2.0f;
1202	bool simpleJoin = simpleMiter && outerBisectorWithinMiterLimit && !giveUp;
1203	const QVector2D bn = bisector / sine;
1204
1205	if (simpleJoin)
1206	return {bn, bn, -bn, -bn, -bn}; // We only have one inner and one outer point TODO: change inner point when conflict/curve
1207	const QVector2D n1 = normalVector(element: *element1, endSide: true).normalized();
1208	const QVector2D n2 = normalVector(element: *element2).normalized();
1209	if (giveUp) {
1210	if (innerIsRight)
1211	return {n1, n2, -n1, -n2, -bn};
1212	else
1213	return {-n1, -n2, n1, n2, -bn};
1214
1215	} else {
1216	if (innerIsRight)
1217	return {bn, bn, -n1, -n2, -bn};
1218	else
1219	return {bn, bn, n1, n2, -bn};
1220	}
1221	};
1222
1223	QList<TriangleData> ret;
1224
1225	auto triangulateCurve = [&](int idx, const QVector2D &p1, const QVector2D &p2, const QVector2D &p3, const QVector2D &p4,
1226	const QVector2D &n1, const QVector2D &n2, const QVector2D &n3, const QVector2D &n4)
1227	{
1228	const auto &element = path.elementAt(i: idx);
1229	const auto &s = element.startPoint();
1230	const auto &c = element.controlPoint();
1231	const auto &e = element.endPoint();
1232	// TODO: Don't flatten the path in addCurveStrokeNodes, but iterate over the children here instead
1233	bool controlPointOnRight = determinant(p1: s, p2: c, p3: e) > 0;
1234	QVector2D startNormal = normalVector(element).normalized();
1235	QVector2D endNormal = normalVector(element, endSide: true).normalized();
1236	QVector2D controlPointNormal = (startNormal + endNormal).normalized();
1237	if (controlPointOnRight)
1238	controlPointNormal = -controlPointNormal;
1239	QVector2D p5 = c + controlPointNormal * penFactor; // This is too simplistic
1240	TrianglePoints t1{p1, p2, p5};
1241	TrianglePoints t2{p3, p4, p5};
1242	bool simpleCase = !checkTriangleOverlap(triangle1&: t1, triangle2&: t2);
1243
1244	if (simpleCase) {
1245	ret.append(t: {.points: {p1, p2, p5}, .pathElementIndex: idx, .normals: {n1, n2, controlPointNormal}});
1246	ret.append(t: {.points: {p3, p4, p5}, .pathElementIndex: idx, .normals: {n3, n4, controlPointNormal}});
1247	if (controlPointOnRight) {
1248	ret.append(t: {.points: {p1, p3, p5}, .pathElementIndex: idx, .normals: {n1, n3, controlPointNormal}});
1249	} else {
1250	ret.append(t: {.points: {p2, p4, p5}, .pathElementIndex: idx, .normals: {n2, n4, controlPointNormal}});
1251	}
1252	} else {
1253	ret.append(other: simplePointTriangulator(pts: {p1, p2, p5, p3, p4}, normals: {n1, n2, controlPointNormal, n3, n4}, elementIndex: idx));
1254	}
1255	};
1256
1257	// Each element is calculated independently, so we don't have to special-case closed sub-paths.
1258	// Take care so the end points of one element are precisely equal to the start points of the next.
1259	// Any additional triangles needed for joining are added at the end of the current element.
1260
1261	int count = path.elementCount();
1262	int subStart = 0;
1263	while (subStart < count) {
1264	int subEnd = subStart;
1265	for (int i = subStart + 1; i < count; ++i) {
1266	const auto &e = path.elementAt(i);
1267	if (e.isSubpathStart()) {
1268	subEnd = i - 1;
1269	break;
1270	}
1271	if (i == count - 1) {
1272	subEnd = i;
1273	break;
1274	}
1275	}
1276	bool closed = path.elementAt(i: subStart).startPoint() == path.elementAt(i: subEnd).endPoint();
1277	const int subCount = subEnd - subStart + 1;
1278
1279	auto addIdx = [&](int idx, int delta) -> int {
1280	int subIdx = idx - subStart;
1281	if (closed)
1282	subIdx = (subIdx + subCount + delta) % subCount;
1283	else
1284	subIdx += delta;
1285	return subStart + subIdx;
1286	};
1287	auto elementAt = [&](int idx, int delta) -> const QQuadPath::Element * {
1288	int subIdx = idx - subStart;
1289	if (closed) {
1290	subIdx = (subIdx + subCount + delta) % subCount;
1291	return &path.elementAt(i: subStart + subIdx);
1292	}
1293	subIdx += delta;
1294	if (subIdx >= 0 && subIdx < subCount)
1295	return &path.elementAt(i: subStart + subIdx);
1296	return nullptr;
1297	};
1298
1299	for (int i = subStart; i <= subEnd; ++i) {
1300	const auto &element = path.elementAt(i);
1301	const auto *nextElement = elementAt(i, +1);
1302	const auto *prevElement = elementAt(i, -1);
1303
1304	const auto &s = element.startPoint();
1305	const auto &e = element.endPoint();
1306
1307	bool startInnerIsRight;
1308	bool startBisectorWithinMiterLimit; // Not used
1309	bool giveUpOnStartJoin; // Not used
1310	auto startJoin = calculateJoin(prevElement, &element,
1311	startBisectorWithinMiterLimit, startInnerIsRight,
1312	giveUpOnStartJoin);
1313	const QVector2D &startInner = startJoin[1];
1314	const QVector2D &startOuter = startJoin[3];
1315
1316	bool endInnerIsRight;
1317	bool endBisectorWithinMiterLimit;
1318	bool giveUpOnEndJoin;
1319	auto endJoin = calculateJoin(&element, nextElement,
1320	endBisectorWithinMiterLimit, endInnerIsRight,
1321	giveUpOnEndJoin);
1322	QVector2D endInner = endJoin[0];
1323	QVector2D endOuter = endJoin[2];
1324	QVector2D nextOuter = endJoin[3];
1325	QVector2D outerB = endJoin[4];
1326
1327	QVector2D p1, p2, p3, p4;
1328	QVector2D n1, n2, n3, n4;
1329
1330	if (startInnerIsRight) {
1331	n1 = startInner;
1332	n2 = startOuter;
1333	} else {
1334	n1 = startOuter;
1335	n2 = startInner;
1336	}
1337
1338	p1 = s + n1 * penFactor;
1339	p2 = s + n2 * penFactor;
1340
1341	// repeat logic above for the other end:
1342	if (endInnerIsRight) {
1343	n3 = endInner;
1344	n4 = endOuter;
1345	} else {
1346	n3 = endOuter;
1347	n4 = endInner;
1348	}
1349
1350	p3 = e + n3 * penFactor;
1351	p4 = e + n4 * penFactor;
1352
1353	// End caps
1354
1355	if (!prevElement) {
1356	QVector2D capSpace = tangentVector(element).normalized() * -penFactor;
1357	if (roundCap) {
1358	p1 += capSpace;
1359	p2 += capSpace;
1360	} else if (squareCap) {
1361	QVector2D c1 = p1 + capSpace;
1362	QVector2D c2 = p2 + capSpace;
1363	ret.append(t: {.points: {p1, s, c1}, .pathElementIndex: -1, .normals: {}});
1364	ret.append(t: {.points: {c1, s, c2}, .pathElementIndex: -1, .normals: {}});
1365	ret.append(t: {.points: {p2, s, c2}, .pathElementIndex: -1, .normals: {}});
1366	}
1367	}
1368	if (!nextElement) {
1369	QVector2D capSpace = tangentVector(element, endSide: true).normalized() * -penFactor;
1370	if (roundCap) {
1371	p3 += capSpace;
1372	p4 += capSpace;
1373	} else if (squareCap) {
1374	QVector2D c3 = p3 + capSpace;
1375	QVector2D c4 = p4 + capSpace;
1376	ret.append(t: {.points: {p3, e, c3}, .pathElementIndex: -1, .normals: {}});
1377	ret.append(t: {.points: {c3, e, c4}, .pathElementIndex: -1, .normals: {}});
1378	ret.append(t: {.points: {p4, e, c4}, .pathElementIndex: -1, .normals: {}});
1379	}
1380	}
1381
1382	if (element.isLine()) {
1383	ret.append(t: {.points: {p1, p2, p3}, .pathElementIndex: i, .normals: {n1, n2, n3}});
1384	ret.append(t: {.points: {p2, p3, p4}, .pathElementIndex: i, .normals: {n2, n3, n4}});
1385	} else {
1386	triangulateCurve(i, p1, p2, p3, p4, n1, n2, n3, n4);
1387	}
1388
1389	bool trivialJoin = simpleMiter && endBisectorWithinMiterLimit && !giveUpOnEndJoin;
1390	if (!trivialJoin && nextElement) {
1391	// inside of join (opposite of bevel) is defined by
1392	// triangle s, e, next.e
1393	bool innerOnRight = endInnerIsRight;
1394
1395	const auto outer1 = e + endOuter * penFactor;
1396	const auto outer2 = e + nextOuter * penFactor;
1397	//const auto inner = e + endInner * penFactor;
1398
1399	if (bevelJoin || (miterJoin && !endBisectorWithinMiterLimit)) {
1400	ret.append(t: {.points: {outer1, e, outer2}, .pathElementIndex: -1, .normals: {}});
1401	} else if (roundJoin) {
1402	ret.append(t: {.points: {outer1, e, outer2}, .pathElementIndex: i, .normals: {}});
1403	QVector2D nn = calcNormalVector(a: outer1, b: outer2).normalized() * penFactor;
1404	if (!innerOnRight)
1405	nn = -nn;
1406	ret.append(t: {.points: {outer1, outer1 + nn, outer2}, .pathElementIndex: i, .normals: {}});
1407	ret.append(t: {.points: {outer1 + nn, outer2, outer2 + nn}, .pathElementIndex: i, .normals: {}});
1408
1409	} else if (miterJoin) {
1410	QVector2D outer = e + outerB * penFactor;
1411	ret.append(t: {.points: {outer1, e, outer}, .pathElementIndex: -2, .normals: {}});
1412	ret.append(t: {.points: {outer, e, outer2}, .pathElementIndex: -2, .normals: {}});
1413	}
1414
1415	if (!giveUpOnEndJoin) {
1416	QVector2D inner = e + endInner * penFactor;
1417	ret.append(t: {.points: {inner, e, outer1}, .pathElementIndex: i, .normals: {endInner, {}, endOuter}});
1418	// The remaining triangle ought to be done by nextElement, but we don't have start join logic there (yet)
1419	int nextIdx = addIdx(i, +1);
1420	ret.append(t: {.points: {inner, e, outer2}, .pathElementIndex: nextIdx, .normals: {endInner, {}, nextOuter}});
1421	}
1422	}
1423	}
1424	subStart = subEnd + 1;
1425	}
1426	return ret;
1427	}
1428
1429	};
1430
1431	QVector<QSGGeometryNode *> QQuickShapeCurveRenderer::addCurveStrokeNodes(const PathData &pathData, NodeList *debugNodes)
1432	{
1433	QVector<QSGGeometryNode *> ret;
1434	const QColor &color = pathData.pen.color();
1435
1436	const bool debug = debugVisualization() & DebugCurves;
1437	auto *node = new QQuickShapeStrokeNode;
1438	node->setDebug(0.2f * debug);
1439	QVector<QQuickShapeWireFrameNode::WireFrameVertex> wfVertices;
1440
1441	float miterLimit = pathData.pen.miterLimit();
1442	float penWidth = pathData.pen.widthF();
1443
1444	static const int subdivisions = qEnvironmentVariable(varName: "QT_QUICKSHAPES_STROKE_SUBDIVISIONS", QStringLiteral("3")).toInt();
1445	auto thePath = subdivide(path: pathData.strokePath, subdivisions, penWidth).flattened(); // TODO: don't flatten, but handle it in the triangulator
1446	auto triangles = customTriangulator2(path: thePath, penWidth, joinStyle: pathData.pen.joinStyle(), capStyle: pathData.pen.capStyle(), miterLimit);
1447
1448	auto addCurveTriangle = [&](const QQuadPath::Element &element, const TriangleData &t){
1449	const QVector2D &p0 = t.points[0];
1450	const QVector2D &p1 = t.points[1];
1451	const QVector2D &p2 = t.points[2];
1452	if (element.isLine()) {
1453	node->appendTriangle(v: t.points,
1454	p: LinePoints{element.startPoint(), element.endPoint()},
1455	n: t.normals);
1456	} else {
1457	node->appendTriangle(v: t.points,
1458	p: { element.startPoint(), element.controlPoint(), element.endPoint()},
1459	n: t.normals);
1460	}
1461	wfVertices.append(t: {.x: p0.x(), .y: p0.y(), .u: 1.0f, .v: 0.0f, .w: 0.0f});
1462	wfVertices.append(t: {.x: p1.x(), .y: p1.y(), .u: 0.0f, .v: 1.0f, .w: 0.0f});
1463	wfVertices.append(t: {.x: p2.x(), .y: p2.y(), .u: 0.0f, .v: 0.0f, .w: 1.0f});
1464	};
1465
1466	auto addBevelTriangle = [&](const TrianglePoints &p)
1467	{
1468	QVector2D fp1 = p[0];
1469	QVector2D fp2 = p[2];
1470
1471	// That describes a path that passes through those points. We want the stroke
1472	// edge, so we need to shift everything down by the stroke offset
1473
1474	QVector2D nn = calcNormalVector(a: p[0], b: p[2]);
1475	if (determinant(p) < 0)
1476	nn = -nn;
1477	float delta = penWidth / 2;
1478
1479	QVector2D offset = nn.normalized() * delta;
1480	fp1 += offset;
1481	fp2 += offset;
1482
1483	TrianglePoints n;
1484	// p1 is inside, so n[1] is {0,0}
1485	n[0] = (p[0] - p[1]).normalized();
1486	n[2] = (p[2] - p[1]).normalized();
1487
1488	node->appendTriangle(v: p, p: LinePoints{fp1, fp2}, n);
1489
1490	wfVertices.append(t: {.x: p[0].x(), .y: p[0].y(), .u: 1.0f, .v: 0.0f, .w: 0.0f});
1491	wfVertices.append(t: {.x: p[1].x(), .y: p[1].y(), .u: 0.0f, .v: 1.0f, .w: 0.0f});
1492	wfVertices.append(t: {.x: p[2].x(), .y: p[2].y(), .u: 0.0f, .v: 0.0f, .w: 1.0f});
1493	};
1494
1495	for (const auto &triangle : triangles) {
1496	if (triangle.pathElementIndex < 0) {
1497	addBevelTriangle(triangle.points);
1498	continue;
1499	}
1500	const auto &element = thePath.elementAt(i: triangle.pathElementIndex);
1501	addCurveTriangle(element, triangle);
1502	}
1503
1504	auto indexCopy = node->uncookedIndexes(); // uncookedIndexes get delete on cooking
1505
1506	node->setColor(color);
1507	node->setStrokeWidth(pathData.pen.widthF());
1508	node->cookGeometry();
1509	m_rootNode->appendChildNode(node);
1510	ret.append(t: node);
1511
1512	const bool wireFrame = debugVisualization() & DebugWireframe;
1513	if (wireFrame) {
1514	QQuickShapeWireFrameNode *wfNode = new QQuickShapeWireFrameNode;
1515
1516	QSGGeometry *wfg = new QSGGeometry(QQuickShapeWireFrameNode::attributes(),
1517	wfVertices.size(),
1518	indexCopy.size(),
1519	QSGGeometry::UnsignedIntType);
1520	wfNode->setGeometry(wfg);
1521
1522	wfg->setDrawingMode(QSGGeometry::DrawTriangles);
1523	memcpy(dest: wfg->indexData(),
1524	src: indexCopy.data(),
1525	n: indexCopy.size() * wfg->sizeOfIndex());
1526	memcpy(dest: wfg->vertexData(),
1527	src: wfVertices.data(),
1528	n: wfg->vertexCount() * wfg->sizeOfVertex());
1529
1530	m_rootNode->appendChildNode(node: wfNode);
1531	debugNodes->append(t: wfNode);
1532	}
1533
1534	return ret;
1535	}
1536
1537	// TODO: we could optimize by preprocessing e1, since we call this function multiple times on the same
1538	// elements
1539	static void handleOverlap(QQuadPath &path, int e1, int e2, int recursionLevel = 0)
1540	{
1541	if (!isOverlap(path, e1, e2)) {
1542	return;
1543	}
1544
1545	if (recursionLevel > 8) {
1546	qCDebug(lcShapeCurveRenderer) << "Triangle overlap: recursion level" << recursionLevel << "aborting!";
1547	return;
1548	}
1549
1550	if (path.elementAt(i: e1).childCount() > 1) {
1551	auto e11 = path.indexOfChildAt(i: e1, childNumber: 0);
1552	auto e12 = path.indexOfChildAt(i: e1, childNumber: 1);
1553	handleOverlap(path, e1: e11, e2, recursionLevel: recursionLevel + 1);
1554	handleOverlap(path, e1: e12, e2, recursionLevel: recursionLevel + 1);
1555	} else if (path.elementAt(i: e2).childCount() > 1) {
1556	auto e21 = path.indexOfChildAt(i: e2, childNumber: 0);
1557	auto e22 = path.indexOfChildAt(i: e2, childNumber: 1);
1558	handleOverlap(path, e1, e2: e21, recursionLevel: recursionLevel + 1);
1559	handleOverlap(path, e1, e2: e22, recursionLevel: recursionLevel + 1);
1560	} else {
1561	path.splitElementAt(index: e1);
1562	auto e11 = path.indexOfChildAt(i: e1, childNumber: 0);
1563	auto e12 = path.indexOfChildAt(i: e1, childNumber: 1);
1564	bool overlap1 = isOverlap(path, e1: e11, e2);
1565	bool overlap2 = isOverlap(path, e1: e12, e2);
1566	if (!overlap1 && !overlap2)
1567	return; // no more overlap: success!
1568
1569	// We need to split more:
1570	if (path.elementAt(i: e2).isLine()) {
1571	// Splitting a line won't help, so we just split e1 further
1572	if (overlap1)
1573	handleOverlap(path, e1: e11, e2, recursionLevel: recursionLevel + 1);
1574	if (overlap2)
1575	handleOverlap(path, e1: e12, e2, recursionLevel: recursionLevel + 1);
1576	} else {
1577	// See if splitting e2 works:
1578	path.splitElementAt(index: e2);
1579	auto e21 = path.indexOfChildAt(i: e2, childNumber: 0);
1580	auto e22 = path.indexOfChildAt(i: e2, childNumber: 1);
1581	if (overlap1) {
1582	handleOverlap(path, e1: e11, e2: e21, recursionLevel: recursionLevel + 1);
1583	handleOverlap(path, e1: e11, e2: e22, recursionLevel: recursionLevel + 1);
1584	}
1585	if (overlap2) {
1586	handleOverlap(path, e1: e12, e2: e21, recursionLevel: recursionLevel + 1);
1587	handleOverlap(path, e1: e12, e2: e22, recursionLevel: recursionLevel + 1);
1588	}
1589	}
1590	}
1591	}
1592
1593	// Test if element contains a start point of another element
1594	static void handleOverlap(QQuadPath &path, int e1, const QVector2D vertex, int recursionLevel = 0)
1595	{
1596	// First of all: Ignore the next element: it trivially overlaps (maybe not necessary: we do check for strict containment)
1597	if (vertex == path.elementAt(i: e1).endPoint() || !isOverlap(path, index: e1, vertex))
1598	return;
1599	if (recursionLevel > 8) {
1600	qCDebug(lcShapeCurveRenderer) << "Vertex overlap: recursion level" << recursionLevel << "aborting!";
1601	return;
1602	}
1603
1604	// Don't split if we're already split
1605	if (path.elementAt(i: e1).childCount() == 0)
1606	path.splitElementAt(index: e1);
1607
1608	handleOverlap(path, e1: path.indexOfChildAt(i: e1, childNumber: 0), vertex, recursionLevel: recursionLevel + 1);
1609	handleOverlap(path, e1: path.indexOfChildAt(i: e1, childNumber: 1), vertex, recursionLevel: recursionLevel + 1);
1610	}
1611
1612	void QQuickShapeCurveRenderer::solveOverlaps(QQuadPath &path)
1613	{
1614	for (int i = 0; i < path.elementCount(); i++) {
1615	auto &element = path.elementAt(i);
1616	// only concave curve overlap is problematic, as long as we don't allow self-intersecting curves
1617	if (element.isLine() || element.isConvex())
1618	continue;
1619
1620	for (int j = 0; j < path.elementCount(); j++) {
1621	if (i == j)
1622	continue; // Would be silly to test overlap with self
1623	auto &other = path.elementAt(i: j);
1624	if (!other.isConvex() && !other.isLine() && j < i)
1625	continue; // We have already tested this combination, so no need to test again
1626	handleOverlap(path, e1: i, e2: j);
1627	}
1628	}
1629
1630	static const int handleConcaveJoint = qEnvironmentVariableIntValue(varName: "QT_QUICKSHAPES_WIP_CONCAVE_JOINT");
1631	if (handleConcaveJoint) {
1632	// Note that the joint between two non-concave elements can also be concave, so we have to
1633	// test all convex elements to see if there is a vertex in any of them. We could do it the other way
1634	// by identifying concave joints, but then we would have to know which side is the inside
1635	// TODO: optimization potential! Maybe do that at the same time as we identify concave curves?
1636
1637	// We do this in a separate loop, since the triangle/triangle test above is more expensive, and
1638	// if we did this first, there would be more triangles to test
1639	for (int i = 0; i < path.elementCount(); i++) {
1640	auto &element = path.elementAt(i);
1641	if (!element.isConvex())
1642	continue;
1643
1644	for (int j = 0; j < path.elementCount(); j++) {
1645	// We only need to check one point per element, since all subpaths are closed
1646	// Could do smartness to skip elements that cannot overlap, but let's do it the easy way first
1647	if (i == j)
1648	continue;
1649	const auto &other = path.elementAt(i: j);
1650	handleOverlap(path, e1: i, vertex: other.startPoint());
1651	}
1652	}
1653	}
1654	}
1655
1656	QT_END_NAMESPACE
1657