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 "qquadpath_p.h"
5
6#include <private/qsgcurveprocessor_p.h>
7
8#include <QtGui/private/qbezier_p.h>
9#include <QtMath>
10#include <QtCore/QLoggingCategory>
11#include <QtCore/QVarLengthArray>
12
13QT_BEGIN_NAMESPACE
14
15static qreal qt_scoreQuadratic(const QBezier &b, QPointF qcp)
16{
17 static bool init = false;
18 const int numSteps = 21;
19 Q_STATIC_ASSERT(numSteps % 2 == 1); // numTries must be odd
20 static qreal t2s[numSteps];
21 static qreal tmts[numSteps];
22 if (!init) {
23 // Precompute bezier factors
24 qreal t = 0.20;
25 const qreal step = (1 - (2 * t)) / (numSteps - 1);
26 for (int i = 0; i < numSteps; i++) {
27 t2s[i] = t * t;
28 tmts[i] = 2 * t * (1 - t);
29 t += step;
30 }
31 init = true;
32 }
33
34 const QPointF midPoint = b.midPoint();
35 auto distForIndex = [&](int i) -> qreal {
36 QPointF qp = (t2s[numSteps - 1 - i] * b.pt1()) + (tmts[i] * qcp) + (t2s[i] * b.pt4());
37 QPointF d = midPoint - qp;
38 return QPointF::dotProduct(p1: d, p2: d);
39 };
40
41 const int halfSteps = (numSteps - 1) / 2;
42 bool foundIt = false;
43 const qreal centerDist = distForIndex(halfSteps);
44 qreal minDist = centerDist;
45 // Search for the minimum in right half
46 for (int i = 0; i < halfSteps; i++) {
47 qreal tDist = distForIndex(halfSteps + 1 + i);
48 if (tDist < minDist) {
49 minDist = tDist;
50 } else {
51 foundIt = (i > 0);
52 break;
53 }
54 }
55 if (!foundIt) {
56 // Search in left half
57 minDist = centerDist;
58 for (int i = 0; i < halfSteps; i++) {
59 qreal tDist = distForIndex(halfSteps - 1 - i);
60 if (tDist < minDist) {
61 minDist = tDist;
62 } else {
63 foundIt = (i > 0);
64 break;
65 }
66 }
67 }
68 return foundIt ? minDist : centerDist;
69}
70
71static QPointF qt_quadraticForCubic(const QBezier &b)
72{
73 const QLineF st = b.startTangent();
74 const QLineF et = b.endTangent();
75 const QPointF midPoint = b.midPoint();
76 bool valid = true;
77 QPointF quadControlPoint;
78 if (st.intersects(l: et, intersectionPoint: &quadControlPoint) == QLineF::NoIntersection) {
79 valid = false;
80 } else {
81 // Check if intersection is on wrong side
82 const QPointF bl = b.pt4() - b.pt1();
83 const QPointF ml = midPoint - b.pt1();
84 const QPointF ql = quadControlPoint - b.pt1();
85 qreal cx1 = (ml.x() * bl.y()) - (ml.y() * bl.x());
86 qreal cx2 = (ql.x() * bl.y()) - (ql.y() * bl.x());
87 valid = (std::signbit(x: cx1) == std::signbit(x: cx2));
88 }
89 return valid ? quadControlPoint : midPoint;
90}
91
92static int qt_getInflectionPoints(const QBezier &orig, qreal *tpoints)
93{
94 auto isValidRoot = [](qreal r) {
95 return qIsFinite(d: r) && (r > 0) && (!qFuzzyIsNull(f: float(r))) && (r < 1)
96 && (!qFuzzyIsNull(f: float(r - 1)));
97 };
98
99 // normalize so pt1.x,pt1.y,pt4.y == 0
100 QTransform xf;
101 const QLineF l(orig.pt1(), orig.pt4());
102 xf.rotate(a: l.angle());
103 xf.translate(dx: -orig.pt1().x(), dy: -orig.pt1().y());
104 const QBezier n = orig.mapBy(transform: xf);
105
106 const qreal x2 = n.pt2().x();
107 const qreal x3 = n.pt3().x();
108 const qreal x4 = n.pt4().x();
109 const qreal y2 = n.pt2().y();
110 const qreal y3 = n.pt3().y();
111
112 const qreal p = x3 * y2;
113 const qreal q = x4 * y2;
114 const qreal r = x2 * y3;
115 const qreal s = x4 * y3;
116
117 const qreal a = 18 * ((-3 * p) + (2 * q) + (3 * r) - s);
118 if (qFuzzyIsNull(f: float(a))) {
119 if (std::signbit(x: y2) != std::signbit(x: y3) && qFuzzyCompare(p1: float(x4 - x3), p2: float(x2))) {
120 tpoints[0] = 0.5; // approx
121 return 1;
122 } else if (!a) {
123 return 0;
124 }
125 }
126 const qreal b = 18 * (((3 * p) - q) - (3 * r));
127 const qreal c = 18 * (r - p);
128 const qreal rad = (b * b) - (4 * a * c);
129 if (rad < 0)
130 return 0;
131 const qreal sqr = qSqrt(v: rad);
132 const qreal root1 = (-b + sqr) / (2 * a);
133 const qreal root2 = (-b - sqr) / (2 * a);
134
135 int res = 0;
136 if (isValidRoot(root1))
137 tpoints[res++] = root1;
138 if (root2 != root1 && isValidRoot(root2))
139 tpoints[res++] = root2;
140
141 if (res == 2 && tpoints[0] > tpoints[1])
142 qSwap(value1&: tpoints[0], value2&: tpoints[1]);
143
144 return res;
145}
146
147static void qt_addToQuadratics(const QBezier &b, QPolygonF *p, int maxSplits, qreal maxDiff)
148{
149 QPointF qcp = qt_quadraticForCubic(b);
150 if (maxSplits <= 0 || qt_scoreQuadratic(b, qcp) < maxDiff) {
151 p->append(t: qcp);
152 p->append(t: b.pt4());
153 } else {
154 QBezier rhs = b;
155 QBezier lhs;
156 rhs.parameterSplitLeft(t: 0.5, left: &lhs);
157 qt_addToQuadratics(b: lhs, p, maxSplits: maxSplits - 1, maxDiff);
158 qt_addToQuadratics(b: rhs, p, maxSplits: maxSplits - 1, maxDiff);
159 }
160}
161
162static void qt_toQuadratics(const QBezier &b, QPolygonF *out, qreal errorLimit = 0.01)
163{
164 out->resize(size: 0);
165 out->append(t: b.pt1());
166
167 {
168 // Shortcut if the cubic is really a quadratic
169 const qreal f = 3.0 / 2.0;
170 const QPointF c1 = b.pt1() + f * (b.pt2() - b.pt1());
171 const QPointF c2 = b.pt4() + f * (b.pt3() - b.pt4());
172 if (c1 == c2) {
173 out->append(t: c1);
174 out->append(t: b.pt4());
175 return;
176 }
177 }
178
179 const QRectF cpr = b.bounds();
180 const QPointF dim = cpr.bottomRight() - cpr.topLeft();
181 qreal maxDiff = QPointF::dotProduct(p1: dim, p2: dim) * errorLimit * errorLimit; // maxdistance^2
182
183 qreal infPoints[2];
184 int numInfPoints = qt_getInflectionPoints(orig: b, tpoints: infPoints);
185 const int maxSubSplits = numInfPoints > 0 ? 2 : 3;
186 qreal t0 = 0;
187 // number of main segments == #inflectionpoints + 1
188 for (int i = 0; i < numInfPoints + 1; i++) {
189 qreal t1 = (i < numInfPoints) ? infPoints[i] : 1;
190 QBezier segment = b.bezierOnInterval(t0, t1);
191 qt_addToQuadratics(b: segment, p: out, maxSplits: maxSubSplits, maxDiff);
192 t0 = t1;
193 }
194}
195
196QVector2D QQuadPath::Element::pointAtFraction(float t) const
197{
198 if (isLine()) {
199 return sp + t * (ep - sp);
200 } else {
201 const float r = 1 - t;
202 return (r * r * sp) + (2 * t * r * cp) + (t * t * ep);
203 }
204}
205
206QQuadPath::Element QQuadPath::Element::segmentFromTo(float t0, float t1) const
207{
208 if (t0 <= 0 && t1 >= 1)
209 return *this;
210
211 Element part;
212 part.sp = pointAtFraction(t: t0);
213 part.ep = pointAtFraction(t: t1);
214
215 if (isLine()) {
216 part.cp = 0.5f * (part.sp + part.ep);
217 part.m_isLine = true;
218 } else {
219 // Split curve right at t0, yields { t0, rcp, endPoint } quad segment
220 const QVector2D rcp = (1 - t0) * controlPoint() + t0 * endPoint();
221 // Split that left at t1, yields { t0, lcp, t1 } quad segment
222 float segmentT = (t1 - t0) / (1 - t0);
223 part.cp = (1 - segmentT) * part.sp + segmentT * rcp;
224 }
225 return part;
226}
227
228QQuadPath::Element QQuadPath::Element::reversed() const {
229 Element swappedElement;
230 swappedElement.ep = sp;
231 swappedElement.cp = cp;
232 swappedElement.sp = ep;
233 swappedElement.m_isLine = m_isLine;
234 return swappedElement;
235}
236
237float QQuadPath::Element::extent() const
238{
239 // TBD: cache this value if we start using it a lot
240 QVector2D min(qMin(a: sp.x(), b: ep.x()), qMin(a: sp.y(), b: ep.y()));
241 QVector2D max(qMax(a: sp.x(), b: ep.x()), qMax(a: sp.y(), b: ep.y()));
242 if (!isLine()) {
243 min = QVector2D(qMin(a: min.x(), b: cp.x()), qMin(a: min.y(), b: cp.y()));
244 max = QVector2D(qMax(a: max.x(), b: cp.x()), qMax(a: max.y(), b: cp.y()));
245 }
246 return (max - min).length();
247}
248
249// Returns the number of intersections between element and a horizontal line at y.
250// The t values of max 2 intersection(s) are stored in the fractions array
251int QQuadPath::Element::intersectionsAtY(float y, float *fractions, bool swapXY) const
252{
253 Q_ASSERT(!isLine());
254
255 auto getY = [=](QVector2D p) -> float { return swapXY ? -p.x() : p.y(); };
256
257 const float y0 = getY(startPoint()) - y;
258 const float y1 = getY(controlPoint()) - y;
259 const float y2 = getY(endPoint()) - y;
260
261 int numRoots = 0;
262 const float a = y0 - (2 * y1) + y2;
263 if (a) {
264 const float b = (y1 * y1) - (y0 * y2);
265 if (b >= 0) {
266 const float sqr = qSqrt(v: b);
267 const float root1 = -(-y0 + y1 + sqr) / a;
268 if (qIsFinite(f: root1) && root1 >= 0 && root1 <= 1)
269 fractions[numRoots++] = root1;
270 const float root2 = (y0 - y1 + sqr) / a;
271 if (qIsFinite(f: root2) && root2 != root1 && root2 >= 0 && root2 <= 1)
272 fractions[numRoots++] = root2;
273 }
274 } else if (y1 != y2) {
275 const float root1 = (y2 - (2 * y1)) / (2 * (y2 - y1));
276 if (qIsFinite(f: root1) && root1 >= 0 && root1 <= 1)
277 fractions[numRoots++] = root1;
278 }
279
280 return numRoots;
281}
282
283static float crossProduct(const QVector2D &sp, const QVector2D &p, const QVector2D &ep)
284{
285 QVector2D v1 = ep - sp;
286 QVector2D v2 = p - sp;
287 return (v2.x() * v1.y()) - (v2.y() * v1.x());
288}
289
290bool QQuadPath::isPointOnLeft(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
291{
292 // Use cross product to compare directions of base vector and vector from start to p
293 return crossProduct(sp, p, ep) >= 0.0f;
294}
295
296bool QQuadPath::isPointOnLine(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
297{
298 return qFuzzyIsNull(f: crossProduct(sp, p, ep));
299}
300
301// Assumes sp != ep
302bool QQuadPath::isPointNearLine(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
303{
304 // epsilon is max length of p-to-baseline relative to length of baseline. So 0.01 means that
305 // the distance from p to the baseline must be less than 1% of the length of the baseline.
306 constexpr float epsilon = 0.01f;
307 QVector2D bv = ep - sp;
308 float bl2 = QVector2D::dotProduct(v1: bv, v2: bv);
309 float t = QVector2D::dotProduct(v1: p - sp, v2: bv) / bl2;
310 QVector2D pv = p - (sp + t * bv);
311 return (QVector2D::dotProduct(v1: pv, v2: pv) / bl2) < (epsilon * epsilon);
312}
313
314QVector2D QQuadPath::closestPointOnLine(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
315{
316 QVector2D line = ep - sp;
317 float t = QVector2D::dotProduct(v1: p - sp, v2: line) / QVector2D::dotProduct(v1: line, v2: line);
318 return sp + qBound(min: 0.0f, val: t, max: 1.0f) * line;
319}
320
321// NOTE: it is assumed that subpaths are closed
322bool QQuadPath::contains(const QVector2D &point) const
323{
324 return contains(point, fromIndex: 0, toIndex: elementCount() - 1);
325}
326
327bool QQuadPath::contains(const QVector2D &point, int fromIndex, int toIndex) const
328{
329 // if (!controlPointRect().contains(pt) : good opt when we add cpr caching
330 // return false;
331
332 int winding_number = 0;
333 for (int ei = fromIndex; ei <= toIndex; ei++) {
334 const Element &e = m_elements.at(i: ei);
335 int dir = 1;
336 float y1 = e.startPoint().y();
337 float y2 = e.endPoint().y();
338 if (y2 < y1) {
339 qSwap(value1&: y1, value2&: y2);
340 dir = -1;
341 }
342 if (e.m_isLine) {
343 if (point.y() < y1 || point.y() >= y2 || y1 == y2)
344 continue;
345 const float t = (point.y() - e.startPoint().y()) / (e.endPoint().y() - e.startPoint().y());
346 const float x = e.startPoint().x() + t * (e.endPoint().x() - e.startPoint().x());
347 if (x <= point.x())
348 winding_number += dir;
349 } else {
350 y1 = qMin(a: y1, b: e.controlPoint().y());
351 y2 = qMax(a: y2, b: e.controlPoint().y());
352 if (point.y() < y1 || point.y() >= y2)
353 continue;
354 float ts[2];
355 const int numRoots = e.intersectionsAtY(y: point.y(), fractions: ts);
356 // Count if there is exactly one intersection to the left
357 bool oneHit = false;
358 float tForHit = -1;
359 for (int i = 0; i < numRoots; i++) {
360 if (e.pointAtFraction(t: ts[i]).x() <= point.x()) {
361 oneHit = !oneHit;
362 tForHit = ts[i];
363 }
364 }
365 if (oneHit) {
366 dir = e.tangentAtFraction(t: tForHit).y() < 0 ? -1 : 1;
367 winding_number += dir;
368 }
369 }
370 };
371
372 return (fillRule() == Qt::WindingFill ? (winding_number != 0) : ((winding_number % 2) != 0));
373}
374
375// similar as contains. But we treat the element with the index elementIdx in a special way
376// that should be numerically more stable. The result is a contains for a point on the left
377// and for the right side of the element.
378QQuadPath::Element::FillSide QQuadPath::fillSideOf(int elementIdx, float elementT) const
379{
380 constexpr float toleranceT = 1e-3f;
381 const QVector2D point = m_elements.at(i: elementIdx).pointAtFraction(t: elementT);
382 const QVector2D tangent = m_elements.at(i: elementIdx).tangentAtFraction(t: elementT);
383
384 const bool swapXY = qAbs(t: tangent.x()) > qAbs(t: tangent.y());
385 auto getX = [=](QVector2D p) -> float { return swapXY ? p.y() : p.x(); };
386 auto getY = [=](QVector2D p) -> float { return swapXY ? -p.x() : p.y(); };
387
388 int winding_number = 0;
389 for (int i = 0; i < elementCount(); i++) {
390 const Element &e = m_elements.at(i);
391 int dir = 1;
392 float y1 = getY(e.startPoint());
393 float y2 = getY(e.endPoint());
394 if (y2 < y1) {
395 qSwap(value1&: y1, value2&: y2);
396 dir = -1;
397 }
398 if (e.m_isLine) {
399 if (getY(point) < y1 || getY(point) >= y2 || y1 == y2)
400 continue;
401 const float t = (getY(point) - getY(e.startPoint())) / (getY(e.endPoint()) - getY(e.startPoint()));
402 const float x = getX(e.startPoint()) + t * (getX(e.endPoint()) - getX(e.startPoint()));
403 if (x <= getX(point) && (i != elementIdx || qAbs(t: t - elementT) > toleranceT))
404 winding_number += dir;
405 } else {
406 y1 = qMin(a: y1, b: getY(e.controlPoint()));
407 y2 = qMax(a: y2, b: getY(e.controlPoint()));
408 if (getY(point) < y1 || getY(point) >= y2)
409 continue;
410 float ts[2];
411 const int numRoots = e.intersectionsAtY(y: getY(point), fractions: ts, swapXY);
412 // Count if there is exactly one intersection to the left
413 bool oneHit = false;
414 float tForHit = -1;
415 for (int j = 0; j < numRoots; j++) {
416 const float x = getX(e.pointAtFraction(t: ts[j]));
417 if (x <= getX(point) && (i != elementIdx || qAbs(t: ts[j] - elementT) > toleranceT)) {
418 oneHit = !oneHit;
419 tForHit = ts[j];
420 }
421 }
422 if (oneHit) {
423 dir = getY(e.tangentAtFraction(t: tForHit)) < 0 ? -1 : 1;
424 winding_number += dir;
425 }
426 }
427 };
428
429 int left_winding_number = winding_number;
430 int right_winding_number = winding_number;
431
432 int dir = getY(tangent) < 0 ? -1 : 1;
433
434 if (dir > 0)
435 left_winding_number += dir;
436 else
437 right_winding_number += dir;
438
439 bool leftInside = (fillRule() == Qt::WindingFill ? (left_winding_number != 0) : ((left_winding_number % 2) != 0));
440 bool rightInside = (fillRule() == Qt::WindingFill ? (right_winding_number != 0) : ((right_winding_number % 2) != 0));
441
442 if (leftInside && rightInside)
443 return QQuadPath::Element::FillSideBoth;
444 else if (leftInside)
445 return QQuadPath::Element::FillSideLeft;
446 else if (rightInside)
447 return QQuadPath::Element::FillSideRight;
448 else
449 return QQuadPath::Element::FillSideUndetermined; //should not happen except for numerical error.
450}
451
452void QQuadPath::addElement(const QVector2D &control, const QVector2D &endPoint, bool isLine)
453{
454 if (qFuzzyCompare(v1: m_currentPoint, v2: endPoint))
455 return; // 0 length element, skip
456
457 isLine = isLine || isPointNearLine(p: control, sp: m_currentPoint, ep: endPoint); // Turn flat quad into line
458
459 if (!m_subPathToStart) {
460 Q_ASSERT(!m_elements.isEmpty());
461 m_elements.last().m_isSubpathEnd = false;
462 }
463 m_elements.resize(size: m_elements.size() + 1);
464 Element &elem = m_elements.last();
465 elem.sp = m_currentPoint;
466 elem.cp = isLine ? (0.5f * (m_currentPoint + endPoint)) : control;
467 elem.ep = endPoint;
468 elem.m_isLine = isLine;
469 elem.m_isSubpathStart = m_subPathToStart;
470 m_subPathToStart = false;
471 elem.m_isSubpathEnd = true;
472 m_currentPoint = endPoint;
473}
474
475void QQuadPath::addElement(const Element &e)
476{
477 m_subPathToStart = false;
478 m_currentPoint = e.endPoint();
479 m_elements.append(t: e);
480}
481
482#if !defined(QQUADPATH_CONVEX_CHECK_ERROR_MARGIN)
483# define QQUICKSHAPECURVERENDERER_CONVEX_CHECK_ERROR_MARGIN (1.0f / 32.0f)
484#endif
485
486QQuadPath::Element::FillSide QQuadPath::coordinateOrderOfElement(const QQuadPath::Element &element) const
487{
488 QVector2D baseLine = element.endPoint() - element.startPoint();
489 QVector2D midPoint = element.midPoint();
490 // At the midpoint, the tangent of a quad is parallel to the baseline
491 QVector2D normal = QVector2D(-baseLine.y(), baseLine.x()).normalized();
492 float delta = qMin(a: element.extent() / 100, QQUICKSHAPECURVERENDERER_CONVEX_CHECK_ERROR_MARGIN);
493 QVector2D offset = (normal * delta);
494 bool pathContainsPointToRight = contains(point: midPoint + offset);
495 bool pathContainsPointToLeft = contains(point: midPoint - offset);
496 Element::FillSide res = Element::FillSideUndetermined;
497 if (pathContainsPointToRight)
498 res = (pathContainsPointToLeft ? Element::FillSideBoth : Element::FillSideRight);
499 else if (pathContainsPointToLeft)
500 res = Element::FillSideLeft;
501 return res;
502}
503
504QQuadPath QQuadPath::fromPainterPath(const QPainterPath &path, PathHints hints)
505{
506 QQuadPath res;
507 res.reserve(size: path.elementCount());
508 res.setFillRule(path.fillRule());
509
510 const bool isQuadratic = hints & PathQuadratic;
511
512 QPolygonF quads;
513 QPointF sp;
514 for (int i = 0; i < path.elementCount(); ++i) {
515 QPainterPath::Element element = path.elementAt(i);
516
517 QPointF ep(element);
518 switch (element.type) {
519 case QPainterPath::MoveToElement:
520 res.moveTo(to: QVector2D(ep));
521 break;
522 case QPainterPath::LineToElement:
523 res.lineTo(to: QVector2D(ep));
524 break;
525 case QPainterPath::CurveToElement: {
526 QPointF cp1 = ep;
527 QPointF cp2(path.elementAt(i: ++i));
528 ep = path.elementAt(i: ++i);
529 if (isQuadratic) {
530 const qreal f = 3.0 / 2.0;
531 const QPointF cp = sp + f * (cp1 - sp);
532 res.quadTo(control: QVector2D(cp), to: QVector2D(ep));
533 } else {
534 QBezier b = QBezier::fromPoints(p1: sp, p2: cp1, p3: cp2, p4: ep);
535 qt_toQuadratics(b, out: &quads);
536 for (int i = 1; i < quads.size(); i += 2) {
537 QVector2D cp(quads[i]);
538 QVector2D ep(quads[i + 1]);
539 res.quadTo(control: cp, to: ep);
540 }
541 }
542 break;
543 }
544 default:
545 Q_UNREACHABLE();
546 break;
547 }
548 sp = ep;
549 }
550
551 res.setPathHints(hints | PathQuadratic);
552 return res;
553}
554
555void QQuadPath::addCurvatureData()
556{
557 // We use the convention that the inside of a curve is on the *right* side of the
558 // direction of the baseline.Thus, as long as this is true: if the control point is
559 // on the left side of the baseline, the curve is convex and otherwise it is
560 // concave. The paths we get can be arbitrary order, but each subpath will have a
561 // consistent order. Therefore, for the first curve element in a subpath, we can
562 // determine if the direction already follows the convention or not, and then we
563 // can easily detect curvature of all subsequent elements in the subpath.
564
565 auto isSingleSided = [](Element::FillSide fillSide) {
566 return fillSide == Element::FillSideLeft || fillSide == Element::FillSideRight;
567 };
568
569 auto flagFromFillSide = [](Element::FillSide fillSide) {
570 if (fillSide == Element::FillSideRight || fillSide == Element::FillSideBoth)
571 return Element::FillOnRight;
572 else
573 return Element::CurvatureUndetermined;
574 };
575
576 static bool checkAnomaly = qEnvironmentVariableIntValue(varName: "QT_QUICKSHAPES_CHECK_ALL_CURVATURE") != 0;
577 const bool pathHasFillOnRight = testHint(hint: PathFillOnRight);
578
579 Element::CurvatureFlags flags = Element::CurvatureUndetermined;
580 for (int i = 0; i < m_elements.size(); i++) {
581 QQuadPath::Element &element = m_elements[i];
582 Q_ASSERT(element.childCount() == 0);
583 if (element.isSubpathStart()) {
584 if (pathHasFillOnRight && !checkAnomaly) {
585 flags = Element::FillOnRight;
586 } else {
587 Element::FillSide fillSide = Element::FillSideUndetermined;
588 for (int j = i; !isSingleSided(fillSide) && j < m_elements.size(); j++) {
589 const QQuadPath::Element &subElem = m_elements.at(i: j);
590 if (j > i && subElem.isSubpathStart())
591 break;
592 fillSide = coordinateOrderOfElement(element: subElem);
593 }
594 flags = flagFromFillSide(fillSide);
595 }
596 } else if (checkAnomaly) {
597 Element::FillSide fillSide = coordinateOrderOfElement(element);
598 if (isSingleSided(fillSide)) {
599 Element::CurvatureFlags newFlags = flagFromFillSide(fillSide);
600 if (flags != newFlags) {
601 qCDebug(lcSGCurveProcessor)
602 << "Curvature anomaly detected:" << element
603 << "Subpath fill on right:" << (flags & Element::FillOnRight)
604 << "Element fill on right:" << (newFlags & Element::FillOnRight);
605 flags = newFlags;
606 }
607 }
608 }
609
610 if (element.isLine()) {
611 element.m_curvatureFlags = flags;
612 } else {
613 bool controlPointOnLeft = element.isControlPointOnLeft();
614 bool isFillOnRight = flags & Element::FillOnRight;
615 bool isConvex = controlPointOnLeft == isFillOnRight;
616
617 if (isConvex)
618 element.m_curvatureFlags = Element::CurvatureFlags(flags | Element::Convex);
619 else
620 element.m_curvatureFlags = flags;
621 }
622 }
623}
624
625QRectF QQuadPath::controlPointRect() const
626{
627 QRectF res;
628 if (elementCount()) {
629 QVector2D min, max;
630 min = max = m_elements.constFirst().sp;
631 // No need to recurse, as split curve's controlpoints are within the parent curve's
632 for (const QQuadPath::Element &e : std::as_const(t: m_elements)) {
633 min.setX(std::min(l: { min.x(), e.sp.x(), e.cp.x(), e.ep.x() }));
634 min.setY(std::min(l: { min.y(), e.sp.y(), e.cp.y(), e.ep.y() }));
635 max.setX(std::max(l: { max.x(), e.sp.x(), e.cp.x(), e.ep.x() }));
636 max.setY(std::max(l: { max.y(), e.sp.y(), e.cp.y(), e.ep.y() }));
637 }
638 res = QRectF(min.toPointF(), max.toPointF());
639 }
640 return res;
641}
642
643// Count leaf elements
644int QQuadPath::elementCountRecursive() const
645{
646 int count = 0;
647 iterateElements(lambda: [&](const QQuadPath::Element &, int) { count++; });
648 return count;
649}
650
651QPainterPath QQuadPath::toPainterPath() const
652{
653 // Currently only converts the main, unsplit path; no need for the split path identified
654 QPainterPath res;
655 res.reserve(size: elementCount());
656 res.setFillRule(fillRule());
657 for (const Element &element : m_elements) {
658 if (element.m_isSubpathStart)
659 res.moveTo(p: element.startPoint().toPointF());
660 if (element.m_isLine)
661 res.lineTo(p: element.endPoint().toPointF());
662 else
663 res.quadTo(ctrlPt: element.controlPoint().toPointF(), endPt: element.endPoint().toPointF());
664 };
665 return res;
666}
667
668QString QQuadPath::asSvgString() const
669{
670 QString res;
671 QTextStream str(&res);
672 for (const Element &element : m_elements) {
673 if (element.isSubpathStart())
674 str << "M " << element.startPoint().x() << " " << element.startPoint().y() << " ";
675 if (element.isLine())
676 str << "L " << element.endPoint().x() << " " << element.endPoint().y() << " ";
677 else
678 str << "Q " << element.controlPoint().x() << " " << element.controlPoint().y() << " "
679 << element.endPoint().x() << " " << element.endPoint().y() << " ";
680 }
681 return res;
682}
683
684// Returns a new path since doing it inline would probably be less efficient
685// (technically changing it from O(n) to O(n^2))
686// Note that this function should be called before splitting any elements,
687// so we can assume that the structure is a list and not a tree
688QQuadPath QQuadPath::subPathsClosed(bool *didClose) const
689{
690 Q_ASSERT(m_childElements.isEmpty());
691 bool closed = false;
692 QQuadPath res = *this;
693 res.m_subPathToStart = false;
694 res.m_elements = {};
695 res.m_elements.reserve(asize: elementCount());
696 int subStart = -1;
697 int prevElement = -1;
698 for (int i = 0; i < elementCount(); i++) {
699 const auto &element = m_elements.at(i);
700 if (element.m_isSubpathStart) {
701 if (subStart >= 0 && m_elements[i - 1].ep != m_elements[subStart].sp) {
702 res.m_currentPoint = m_elements[i - 1].ep;
703 res.lineTo(to: m_elements[subStart].sp);
704 closed = true;
705 auto &endElement = res.m_elements.last();
706 endElement.m_isSubpathEnd = true;
707 // lineTo() can bail out if the points are too close.
708 // In that case, just change the end point to be equal to the start
709 // (No need to test because the assignment is a no-op otherwise).
710 endElement.ep = m_elements[subStart].sp;
711 } else if (prevElement >= 0) {
712 res.m_elements[prevElement].m_isSubpathEnd = true;
713 }
714 subStart = i;
715 }
716 res.m_elements.append(t: element);
717 prevElement = res.m_elements.size() - 1;
718 }
719
720 if (subStart >= 0 && m_elements.last().ep != m_elements[subStart].sp) {
721 res.m_currentPoint = m_elements.last().ep;
722 res.lineTo(to: m_elements[subStart].sp);
723 closed = true;
724 }
725 if (!res.m_elements.isEmpty()) {
726 auto &endElement = res.m_elements.last();
727 endElement.m_isSubpathEnd = true;
728 endElement.ep = m_elements[subStart].sp;
729 }
730
731 if (didClose)
732 *didClose = closed;
733 return res;
734}
735
736QQuadPath QQuadPath::flattened() const
737{
738 QQuadPath res;
739 res.reserve(size: elementCountRecursive());
740 iterateElements(lambda: [&](const QQuadPath::Element &elem, int) { res.m_elements.append(t: elem); });
741 res.setPathHints(pathHints());
742 res.setFillRule(fillRule());
743 return res;
744}
745
746class ElementCutter
747{
748public:
749 ElementCutter(const QQuadPath::Element &element)
750 : m_element(element)
751 {
752 m_currentPoint = m_element.startPoint();
753 if (m_element.isLine())
754 m_lineLength = (m_element.endPoint() - m_element.startPoint()).length();
755 else
756 fillLUT();
757 }
758
759 bool consume(float length)
760 {
761 m_lastT = m_currentT;
762 m_lastPoint = m_currentPoint;
763 float nextCut = m_consumed + length;
764 float cutT = m_element.isLine() ? nextCut / m_lineLength : tForLength(length: nextCut);
765 if (cutT < 1) {
766 m_currentT = cutT;
767 m_currentPoint = m_element.pointAtFraction(t: m_currentT);
768 m_consumed = nextCut;
769 return true;
770 } else {
771 m_currentT = 1;
772 m_currentPoint = m_element.endPoint();
773 return false;
774 }
775 }
776
777 QVector2D currentCutPoint()
778 {
779 return m_currentPoint;
780 }
781
782 QVector2D currentControlPoint()
783 {
784 Q_ASSERT(!m_element.isLine());
785 // Split curve right at lastT, yields { lastPoint, rcp, endPoint } quad segment
786 QVector2D rcp = (1 - m_lastT) * m_element.controlPoint() + m_lastT * m_element.endPoint();
787 // Split that left at currentT, yields { lastPoint, lcp, currentPoint } quad segment
788 float segmentT = (m_currentT - m_lastT) / (1 - m_lastT);
789 QVector2D lcp = (1 - segmentT) * m_lastPoint + segmentT * rcp;
790 return lcp;
791 }
792
793 float lastLength()
794 {
795 float elemLength = m_element.isLine() ? m_lineLength : m_lut.last();
796 return elemLength - m_consumed;
797 }
798
799private:
800 void fillLUT()
801 {
802 Q_ASSERT(!m_element.isLine());
803 QVector2D ap = m_element.startPoint() - 2 * m_element.controlPoint() + m_element.endPoint();
804 QVector2D bp = 2 * m_element.controlPoint() - 2 * m_element.startPoint();
805 float A = 4 * QVector2D::dotProduct(v1: ap, v2: ap);
806 float B = 4 * QVector2D::dotProduct(v1: ap, v2: bp);
807 float C = QVector2D::dotProduct(v1: bp, v2: bp);
808 float b = B / (2 * A);
809 float c = C / A;
810 float k = c - (b * b);
811 float l2 = b * std::sqrt(x: b * b + k);
812 float lnom = b + std::sqrt(x: b * b + k);
813 float l0 = 0.5f * std::sqrt(x: A);
814
815 m_lut.resize(sz: LUTSize, v: 0);
816 for (int i = 1; i < LUTSize; i++) {
817 float t = float(i) / (LUTSize - 1);
818 float u = t + b;
819 float w = std::sqrt(x: u * u + k);
820 float l1 = u * w;
821 float lden = u + w;
822 float l3 = k * std::log(x: std::fabs(x: lden / lnom));
823 float res = l0 * (l1 - l2 + l3);
824 m_lut[i] = res;
825 }
826 }
827
828 float tForLength(float length)
829 {
830 Q_ASSERT(!m_element.isLine());
831 Q_ASSERT(!m_lut.isEmpty());
832
833 float res = 2; // I.e. invalid, outside [0, 1] range
834 auto it = std::upper_bound(first: m_lut.cbegin(), last: m_lut.cend(), val: length);
835 if (it != m_lut.cend()) {
836 float nextLength = *it--;
837 float prevLength = *it;
838 int prevIndex = std::distance(first: m_lut.cbegin(), last: it);
839 float fraction = (length - prevLength) / (nextLength - prevLength);
840 res = (prevIndex + fraction) / (LUTSize - 1);
841 }
842 return res;
843 }
844
845 const QQuadPath::Element &m_element;
846 float m_lastT = 0;
847 float m_currentT = 0;
848 QVector2D m_lastPoint;
849 QVector2D m_currentPoint;
850 float m_consumed = 0;
851 // For line elements:
852 float m_lineLength;
853 // For quadratic curve elements:
854 static constexpr int LUTSize = 21;
855 QVarLengthArray<float, LUTSize> m_lut;
856};
857
858QQuadPath QQuadPath::dashed(qreal lineWidth, const QList<qreal> &dashPattern, qreal dashOffset) const
859{
860 QVarLengthArray<float, 16> pattern;
861 float patternLength = 0;
862 for (int i = 0; i < 2 * (dashPattern.length() / 2); i++) {
863 float dashLength = qMax(a: lineWidth * dashPattern[i], b: qreal(0));
864 pattern.append(t: dashLength);
865 patternLength += dashLength;
866 }
867 if (patternLength == 0)
868 return {};
869
870 int startIndex = 0;
871 float startOffset = std::fmod(x: lineWidth * dashOffset, y: patternLength);
872 if (startOffset < 0)
873 startOffset += patternLength;
874 for (float dashLength : pattern) {
875 if (dashLength > startOffset)
876 break;
877 startIndex = (startIndex + 1) % pattern.size(); // The % guards against accuracy issues
878 startOffset -= dashLength;
879 }
880
881 int dashIndex = startIndex;
882 float offset = startOffset;
883 QQuadPath res;
884 for (int i = 0; i < elementCount(); i++) {
885 const Element &element = elementAt(i);
886 if (element.isSubpathStart()) {
887 res.moveTo(to: element.startPoint());
888 dashIndex = startIndex;
889 offset = startOffset;
890 }
891 ElementCutter cutter(element);
892 while (true) {
893 bool gotAll = cutter.consume(length: pattern.at(idx: dashIndex) - offset);
894 QVector2D nextPoint = cutter.currentCutPoint();
895 if (dashIndex & 1)
896 res.moveTo(to: nextPoint); // gap
897 else if (element.isLine())
898 res.lineTo(to: nextPoint); // dash in line
899 else
900 res.quadTo(control: cutter.currentControlPoint(), to: nextPoint); // dash in curve
901 if (gotAll) {
902 offset = 0;
903 dashIndex = (dashIndex + 1) % pattern.size();
904 } else {
905 offset += cutter.lastLength();
906 break;
907 }
908 }
909 }
910 res.setFillRule(fillRule());
911 res.setPathHints(pathHints());
912 return res;
913}
914
915void QQuadPath::splitElementAt(int index)
916{
917 const int newChildIndex = m_childElements.size();
918 m_childElements.resize(size: newChildIndex + 2);
919 Element &parent = elementAt(i: index);
920 parent.m_numChildren = 2;
921 parent.m_firstChildIndex = newChildIndex;
922
923 Element &quad1 = m_childElements[newChildIndex];
924 const QVector2D mp = parent.midPoint();
925 quad1.sp = parent.sp;
926 quad1.cp = 0.5f * (parent.sp + parent.cp);
927 quad1.ep = mp;
928 quad1.m_isSubpathStart = parent.m_isSubpathStart;
929 quad1.m_isSubpathEnd = false;
930 quad1.m_curvatureFlags = parent.m_curvatureFlags;
931 quad1.m_isLine = parent.m_isLine; //### || isPointNearLine(quad1.cp, quad1.sp, quad1.ep);
932
933 Element &quad2 = m_childElements[newChildIndex + 1];
934 quad2.sp = mp;
935 quad2.cp = 0.5f * (parent.ep + parent.cp);
936 quad2.ep = parent.ep;
937 quad2.m_isSubpathStart = false;
938 quad2.m_isSubpathEnd = parent.m_isSubpathEnd;
939 quad2.m_curvatureFlags = parent.m_curvatureFlags;
940 quad2.m_isLine = parent.m_isLine; //### || isPointNearLine(quad2.cp, quad2.sp, quad2.ep);
941
942#ifndef QT_NO_DEBUG
943 if (qFuzzyCompare(v1: quad1.sp, v2: quad1.ep) || qFuzzyCompare(v1: quad2.sp, v2: quad2.ep))
944 qCDebug(lcSGCurveProcessor) << "Splitting has resulted in ~null quad";
945#endif
946}
947
948static void printElement(QDebug stream, const QQuadPath::Element &element)
949{
950 auto printPoint = [&](QVector2D p) { stream << "(" << p.x() << ", " << p.y() << ") "; };
951 stream << "{ ";
952 printPoint(element.startPoint());
953 printPoint(element.controlPoint());
954 printPoint(element.endPoint());
955 stream << "} " << (element.isLine() ? "L " : "C ") << (element.isConvex() ? "X " : "O ")
956 << (element.isSubpathStart() ? "S" : element.isSubpathEnd() ? "E" : "");
957}
958
959QDebug operator<<(QDebug stream, const QQuadPath::Element &element)
960{
961 QDebugStateSaver saver(stream);
962 stream.nospace();
963 stream << "QuadPath::Element( ";
964 printElement(stream, element);
965 stream << " )";
966 return stream;
967}
968
969QDebug operator<<(QDebug stream, const QQuadPath &path)
970{
971 QDebugStateSaver saver(stream);
972 stream.nospace();
973 stream << "QuadPath(" << path.elementCount() << " main elements, "
974 << path.elementCountRecursive() << " leaf elements, "
975 << (path.fillRule() == Qt::OddEvenFill ? "OddEven" : "Winding") << Qt::endl;
976 int count = 0;
977 path.iterateElements(lambda: [&](const QQuadPath::Element &e, int) {
978 stream << " " << count++ << (e.isSubpathStart() ? " >" : " ");
979 printElement(stream, element: e);
980 stream << Qt::endl;
981 });
982 stream << ")";
983 return stream;
984}
985
986QT_END_NAMESPACE
987

source code of qtdeclarative/src/quick/scenegraph/util/qquadpath.cpp