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

source code of qtdeclarative/src/quickshapes/qquadpath.cpp