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

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