5#include <QtGui/private/qbezier_p.h>
7#include <QtCore/QLoggingCategory>
8#include <QtCore/QVarLengthArray>
16 static bool init =
false;
17 const int numSteps = 21;
19 static qreal t2s[numSteps];
20 static qreal tmts[numSteps];
24 const qreal step = (1 - (2 *
t)) / (numSteps - 1);
25 for (
int i = 0;
i < numSteps;
i++) {
27 tmts[
i] = 2 *
t * (1 -
t);
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());
40 const int halfSteps = (numSteps - 1) / 2;
42 const qreal centerDist = distForIndex(halfSteps);
43 qreal minDist = centerDist;
45 for (
int i = 0;
i < halfSteps;
i++) {
46 qreal tDist = distForIndex(halfSteps + 1 +
i);
47 if (tDist < minDist) {
57 for (
int i = 0;
i < halfSteps;
i++) {
58 qreal tDist = distForIndex(halfSteps - 1 -
i);
59 if (tDist < minDist) {
67 return foundIt ? minDist : centerDist;
72 const QLineF st =
b.startTangent();
73 const QLineF et =
b.endTangent();
74 const QPointF midPoint =
b.midPoint();
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(cx1) == std::signbit(cx2));
88 return valid ? quadControlPoint : midPoint;
93 auto isValidRoot = [](
qreal r) {
101 xf.rotate(l.
angle());
102 xf.translate(-orig.
pt1().
x(), -orig.
pt1().
y());
106 const qreal x3 =
n.pt3().x();
107 const qreal x4 =
n.pt4().x();
109 const qreal y3 =
n.pt3().y();
116 const qreal a = 18 * ((-3 *
p) + (2 *
q) + (3 *
r) -
s);
118 if (std::signbit(
y2) != std::signbit(y3) &&
qFuzzyCompare(
float(x4 - x3),
float(
x2))) {
125 const qreal b = 18 * (((3 *
p) -
q) - (3 *
r));
131 const qreal root1 = (-
b + sqr) / (2 *
a);
132 const qreal root2 = (-
b - sqr) / (2 *
a);
135 if (isValidRoot(root1))
136 tpoints[
res++] = root1;
137 if (root2 != root1 && isValidRoot(root2))
138 tpoints[
res++] = root2;
140 if (
res == 2 && tpoints[0] > tpoints[1])
141 qSwap(tpoints[0], tpoints[1]);
164 out->append(
b.pt1());
168 const qreal f = 3.0 / 2.0;
169 const QPointF c1 =
b.pt1() +
f * (
b.pt2() -
b.pt1());
173 out->append(
b.pt4());
179 const QPointF dim = cpr.bottomRight() - cpr.topLeft();
184 const int maxSubSplits = numInfPoints > 0 ? 2 : 3;
187 for (
int i = 0;
i < numInfPoints + 1;
i++) {
188 qreal t1 = (
i < numInfPoints) ? infPoints[
i] : 1;
198 return sp +
t * (ep - sp);
200 const float r = 1 -
t;
201 return (
r *
r * sp) + (2 *
t *
r * cp) + (
t *
t * ep);
207 if (t0 <= 0 && t1 >= 1)
211 part.sp = pointAtFraction(
t0);
212 part.ep = pointAtFraction(
t1);
215 part.cp = 0.5f * (part.sp + part.ep);
216 part.m_isLine =
true;
219 const QVector2D rcp = (1 -
t0) * controlPoint() +
t0 * endPoint();
221 float segmentT = (
t1 -
t0) / (1 -
t0);
222 part.cp = (1 - segmentT) * part.sp + segmentT * rcp;
229 swappedElement.ep =
sp;
230 swappedElement.cp = cp;
231 swappedElement.sp = ep;
232 swappedElement.m_isLine = m_isLine;
233 return swappedElement;
245 return (max - min).length();
250int QQuadPath::Element::intersectionsAtY(
float y,
float *fractions,
bool swapXY)
const
254 auto getY = [=](
QVector2D p) ->
float {
return swapXY ? -
p.x() :
p.y(); };
256 const float y0 = getY(startPoint()) -
y;
257 const float y1 = getY(controlPoint()) -
y;
258 const float y2 = getY(endPoint()) -
y;
261 const float a =
y0 - (2 *
y1) +
y2;
265 const float sqr =
qSqrt(
b);
266 const float root1 = -(-
y0 +
y1 + sqr) /
a;
267 if (
qIsFinite(root1) && root1 >= 0 && root1 <= 1)
268 fractions[numRoots++] = root1;
269 const float root2 = (
y0 -
y1 + sqr) /
a;
270 if (
qIsFinite(root2) && root2 != root1 && root2 >= 0 && root2 <= 1)
271 fractions[numRoots++] = root2;
273 }
else if (
y1 !=
y2) {
274 const float root1 = (
y2 - (2 *
y1)) / (2 * (
y2 -
y1));
275 if (
qIsFinite(root1) && root1 >= 0 && root1 <= 1)
276 fractions[numRoots++] = root1;
286 return (
v2.x() *
v1.y()) - (
v2.y() *
v1.x());
305 constexpr float epsilon = 0.01f;
331 int winding_number = 0;
332 for (
int ei = fromIndex; ei <=
toIndex; ei++) {
342 if (point.
y() <
y1 || point.
y() >=
y2 ||
y1 ==
y2)
347 winding_number +=
dir;
351 if (point.
y() <
y1 || point.
y() >=
y2)
354 const int numRoots = e.intersectionsAtY(point.
y(), ts);
358 for (
int i = 0;
i < numRoots;
i++) {
366 winding_number +=
dir;
379 constexpr float toleranceT = 1e-3f;
380 const QVector2D point = m_elements.
at(elementIdx).pointAtFraction(elementT);
381 const QVector2D tangent = m_elements.
at(elementIdx).tangentAtFraction(elementT);
383 const bool swapXY =
qAbs(tangent.
x()) >
qAbs(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(); };
387 int winding_number = 0;
398 if (getY(point) <
y1 || getY(point) >=
y2 ||
y1 ==
y2)
402 if (
x <= getX(point) && (
i != elementIdx ||
qAbs(
t - elementT) > toleranceT))
403 winding_number +=
dir;
407 if (getY(point) <
y1 || getY(point) >=
y2)
410 const int numRoots = e.intersectionsAtY(getY(point), ts, swapXY);
414 for (
int j = 0;
j < numRoots;
j++) {
416 if (
x <= getX(point) && (
i != elementIdx ||
qAbs(ts[
j] - elementT) > toleranceT)) {
423 winding_number +=
dir;
428 int left_winding_number = winding_number;
429 int right_winding_number = winding_number;
431 int dir = getY(tangent) < 0 ? -1 : 1;
434 left_winding_number +=
dir;
436 right_winding_number +=
dir;
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));
441 if (leftInside && rightInside)
442 return QQuadPath::Element::FillSideBoth;
444 return QQuadPath::Element::FillSideLeft;
445 else if (rightInside)
446 return QQuadPath::Element::FillSideRight;
448 return QQuadPath::Element::FillSideUndetermined;
460 elem.sp = m_currentPoint;
461 elem.cp =
isLine ? (0.5f * (m_currentPoint + endPoint)) : control;
464 elem.m_isSubpathStart = m_subPathToStart;
465 m_subPathToStart =
false;
466 m_currentPoint = endPoint;
469void QQuadPath::addElement(
const Element &e)
471 m_subPathToStart =
false;
472 m_currentPoint = e.endPoint();
476#if !defined(QQUADPATH_CONVEX_CHECK_ERROR_MARGIN)
477# define QQUICKSHAPECURVERENDERER_CONVEX_CHECK_ERROR_MARGIN (1.0f / 32.0f)
480QQuadPath::Element::CurvatureFlags QQuadPath::coordinateOrderOfElement(
const QQuadPath::Element &element)
const
487 QVector2D justRightOfMid = midPoint + (normal * delta);
488 bool pathContainsPoint =
contains(justRightOfMid);
489 return pathContainsPoint ? Element::FillOnRight : Element::CurvatureFlags(0);
496 res.setFillRule(
path.fillRule());
502 for (
int i = 0;
i <
path.elementCount(); ++
i) {
506 switch (element.
type) {
516 ep =
path.elementAt(++
i);
518 const qreal f = 3.0 / 2.0;
524 for (
int i = 1;
i < quads.size();
i += 2) {
556 Element::CurvatureFlags
flags = Element::CurvatureUndetermined;
558 Q_ASSERT(element.childCount() == 0);
559 if (element.isSubpathStart()) {
560 if (pathHasFillOnRight && !checkAnomaly)
561 flags = Element::FillOnRight;
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);
574 if (element.isLine()) {
575 element.m_curvatureFlags =
flags;
577 bool controlPointOnLeft = element.isControlPointOnLeft();
578 bool isFillOnRight =
flags & Element::FillOnRight;
579 bool isConvex = controlPointOnLeft == isFillOnRight;
582 element.m_curvatureFlags = Element::CurvatureFlags(
flags | Element::Convex);
584 element.m_curvatureFlags =
flags;
597 min.setX(std::min({ min.x(), e.sp.
x(), e.cp.
x(), e.ep.
x() }));
598 min.setY(std::min({ min.y(), e.sp.
y(), e.cp.
y(), e.ep.
y() }));
599 max.
setX(std::max({ max.
x(), e.sp.
x(), e.cp.
x(), e.ep.
x() }));
600 max.
setY(std::max({ max.
y(), e.sp.
y(), e.cp.
y(), e.ep.
y() }));
621 for (
const Element &element : m_elements) {
622 if (element.m_isSubpathStart)
623 res.moveTo(element.startPoint().toPointF());
624 if (element.m_isLine)
625 res.lineTo(element.endPoint().toPointF());
627 res.quadTo(element.controlPoint().toPointF(), element.endPoint().toPointF());
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() <<
" ";
642 str <<
"Q " << element.controlPoint().x() <<
" " << element.controlPoint().y() <<
" "
643 << element.endPoint().x() <<
" " << element.endPoint().y() <<
" ";
657 res.m_subPathToStart =
false;
661 int prevElement = -1;
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(m_elements[subStart].
sp);
669 auto &endElement =
res.m_elements.
last();
670 endElement.m_isSubpathEnd =
true;
674 endElement.ep = m_elements[subStart].sp;
675 }
else if (prevElement >= 0) {
676 res.m_elements[prevElement].m_isSubpathEnd =
true;
681 prevElement =
res.m_elements.size() - 1;
684 if (subStart >= 0 && m_elements.
last().ep != m_elements[subStart].sp) {
685 res.m_currentPoint = m_elements.
last().ep;
686 res.lineTo(m_elements[subStart].
sp);
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;
716 m_currentPoint = m_element.startPoint();
717 if (m_element.isLine())
718 m_lineLength = (m_element.endPoint() - m_element.startPoint()).
length();
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(nextCut);
731 m_currentPoint = m_element.pointAtFraction(m_currentT);
732 m_consumed = nextCut;
736 m_currentPoint = m_element.endPoint();
743 return m_currentPoint;
750 QVector2D rcp = (1 - m_lastT) * m_element.controlPoint() + m_lastT * m_element.endPoint();
752 float segmentT = (m_currentT - m_lastT) / (1 - m_lastT);
753 QVector2D lcp = (1 - segmentT) * m_lastPoint + segmentT * rcp;
759 float elemLength = m_element.isLine() ? m_lineLength : m_lut.last();
760 return elemLength - m_consumed;
767 QVector2D ap = m_element.startPoint() - 2 * m_element.controlPoint() + m_element.endPoint();
768 QVector2D bp = 2 * m_element.controlPoint() - 2 * m_element.startPoint();
772 float b =
B / (2 *
A);
774 float k =
c - (
b *
b);
775 float l2 =
b * std::sqrt(
b *
b + k);
776 float lnom =
b + std::sqrt(
b *
b + k);
777 float l0 = 0.5f * std::sqrt(
A);
779 m_lut.resize(LUTSize, 0);
780 for (
int i = 1;
i < LUTSize;
i++) {
781 float t = float(
i) / (LUTSize - 1);
783 float w = std::sqrt(u * u + k);
786 float l3 = k * std::log(std::fabs(lden / lnom));
787 float res = l0 * (l1 - l2 + l3);
792 float tForLength(
float length)
798 auto it = std::upper_bound(m_lut.cbegin(), m_lut.cend(),
length);
800 float nextLength = *
it--;
801 float prevLength = *
it;
802 int prevIndex = std::distance(m_lut.cbegin(),
it);
803 float fraction = (
length - prevLength) / (nextLength - prevLength);
804 res = (prevIndex + fraction) / (LUTSize - 1);
811 float m_currentT = 0;
814 float m_consumed = 0;
818 static constexpr int LUTSize = 21;
819 QVarLengthArray<float, LUTSize> m_lut;
824 QVarLengthArray<float, 16>
pattern;
825 float patternLength = 0;
826 for (
int i = 0;
i < 2 * (dashPattern.length() / 2);
i++) {
827 float dashLength =
qMax(lineWidth * dashPattern[
i],
qreal(0));
829 patternLength += dashLength;
831 if (patternLength == 0)
835 float startOffset = std::fmod(lineWidth * dashOffset, patternLength);
837 startOffset += patternLength;
838 for (
float dashLength :
pattern) {
839 if (dashLength > startOffset)
841 startIndex = (startIndex + 1) %
pattern.size();
842 startOffset -= dashLength;
845 int dashIndex = startIndex;
846 float offset = startOffset;
852 dashIndex = startIndex;
857 bool gotAll = cutter.consume(
pattern.at(dashIndex) -
offset);
858 QVector2D nextPoint = cutter.currentCutPoint();
860 res.moveTo(nextPoint);
861 else if (element.
isLine())
862 res.lineTo(nextPoint);
864 res.quadTo(cutter.currentControlPoint(), nextPoint);
867 dashIndex = (dashIndex + 1) %
pattern.size();
869 offset += cutter.lastLength();
881 const int newChildIndex = m_childElements.
size();
882 m_childElements.
resize(newChildIndex + 2);
884 parent.m_numChildren = 2;
885 parent.m_firstChildIndex = newChildIndex;
887 Element &quad1 = m_childElements[newChildIndex];
889 quad1.sp = parent.sp;
890 quad1.cp = 0.5f * (parent.sp + parent.cp);
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;
897 Element &quad2 = m_childElements[newChildIndex + 1];
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;
908 qCDebug(lcSGCurveProcessor) <<
"Splitting has resulted in ~null quad";
914 auto printPoint = [&](
QVector2D p) {
stream <<
"(" <<
p.x() <<
", " <<
p.y() <<
") "; };
927 stream <<
"QuadPath::Element( ";
937 stream <<
"QuadPath(" <<
path.elementCount() <<
" main elements, "
938 <<
path.elementCountRecursive() <<
" leaf elements, "
bool consume(float length)
QVector2D currentControlPoint()
QVector2D currentCutPoint()
ElementCutter(const QQuadPath::Element &element)
static QBezier fromPoints(const QPointF &p1, const QPointF &p2, const QPointF &p3, const QPointF &p4)
void parameterSplitLeft(qreal t, QBezier *left)
QBezier bezierOnInterval(qreal t0, qreal t1) const
QBezier mapBy(const QTransform &transform) const
\inmodule QtCore\compares equality \compareswith equality QLine \endcompareswith
qsizetype size() const noexcept
bool isEmpty() const noexcept
const_reference at(qsizetype i) const noexcept
const T & constFirst() const noexcept
void resize(qsizetype size)
void append(parameter_type t)
void reserve(int size)
Reserves a given amount of elements in QPainterPath's internal memory.
\inmodule QtCore\reentrant
constexpr qreal x() const noexcept
Returns the x coordinate of this point.
static constexpr qreal dotProduct(const QPointF &p1, const QPointF &p2)
constexpr qreal y() const noexcept
Returns the y coordinate of this point.
The QPolygonF class provides a list of points using floating point precision.
bool isSubpathStart() const
Element segmentFromTo(float t0, float t1) const
QVector2D tangentAtFraction(float t) const
bool isSubpathEnd() const
QVector2D startPoint() const
QVector2D midPoint() const
QVector2D endPoint() const
QVector2D pointAtFraction(float t) const
QVector2D controlPoint() const
QQuadPath flattened() const
QPainterPath toPainterPath() const
static QVector2D closestPointOnLine(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
Element & elementAt(int i)
bool contains(const QVector2D &point) const
QString asSvgString() const
void iterateElements(Func &&lambda)
static bool isPointOnLine(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
void splitElementAt(int index)
QQuadPath subPathsClosed(bool *didClose=nullptr) const
static bool isPointOnLeft(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
static bool isPointNearLine(const QVector2D &p, const QVector2D &sp, const QVector2D &ep)
int elementCountRecursive() const
QQuadPath dashed(qreal lineWidth, const QList< qreal > &dashPattern, qreal dashOffset=0) const
PathHints pathHints() const
QRectF controlPointRect() const
Element::FillSide fillSideOf(int elementIdx, float elementT) const
Qt::FillRule fillRule() const
bool testHint(PathHint hint) const
static QQuadPath fromPainterPath(const QPainterPath &path, PathHints hints={})
friend Q_QUICK_EXPORT QDebug operator<<(QDebug, const QQuadPath &)
\inmodule QtCore\reentrant
const_iterator cend() const noexcept
\macro QT_RESTRICTED_CAST_FROM_ASCII
The QVector2D class represents a vector or vertex in 2D space.
constexpr float y() const noexcept
Returns the y coordinate of this point.
QVector2D normalized() const noexcept
Returns the normalized unit vector form of this vector.
constexpr float x() const noexcept
Returns the x coordinate of this point.
static constexpr float dotProduct(QVector2D v1, QVector2D v2) noexcept
Returns the dot product of v1 and v2.
constexpr void setY(float y) noexcept
Sets the y coordinate of this point to the given finite y coordinate.
constexpr QPointF toPointF() const noexcept
Returns the QPointF form of this 2D vector.
constexpr void setX(float x) noexcept
Sets the x coordinate of this point to the given finite x coordinate.
QSet< QString >::iterator it
Combined button and popup list for selecting options.
QTextStream & endl(QTextStream &stream)
Writes '\n' to the stream and flushes the stream.
#define Q_STATIC_ASSERT(Condition)
bool qIsFinite(qfloat16 f) noexcept
bool qFuzzyCompare(qfloat16 p1, qfloat16 p2) noexcept
bool qFuzzyIsNull(qfloat16 f) noexcept
qfloat16 qSqrt(qfloat16 f)
#define qCDebug(category,...)
#define Q_DECLARE_LOGGING_CATEGORY(name)
constexpr const T & qMin(const T &a, const T &b)
constexpr const T & qBound(const T &min, const T &val, const T &max)
constexpr const T & qMax(const T &a, const T &b)
constexpr T qAbs(const T &t)
GLint GLfloat GLfloat GLfloat v2
GLboolean GLboolean GLboolean b
GLint GLint GLint GLint GLint x
[0]
GLfloat GLfloat GLfloat w
[0]
GLboolean GLboolean GLboolean GLboolean a
[7]
GLuint GLfloat GLfloat GLfloat GLfloat y1
GLenum GLuint GLenum GLsizei length
GLenum GLenum GLsizei count
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t1
[4]
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat GLfloat t0
GLenum GLuint GLintptr offset
GLuint GLfloat GLfloat y0
GLfixed GLfixed GLfixed y2
GLdouble GLdouble GLdouble GLdouble q
GLsizei const GLchar *const * path
static bool isLine(const QBezier &bezier)
static qreal qt_scoreQuadratic(const QBezier &b, QPointF qcp)
static void qt_addToQuadratics(const QBezier &b, QPolygonF *p, int maxSplits, qreal maxDiff)
static QPointF qt_quadraticForCubic(const QBezier &b)
static float crossProduct(const QVector2D &sp, const QVector2D &p, const QVector2D &ep)
static void qt_toQuadratics(const QBezier &b, QPolygonF *out, qreal errorLimit=0.01)
static void printElement(QDebug stream, const QQuadPath::Element &element)
#define QQUICKSHAPECURVERENDERER_CONVEX_CHECK_ERROR_MARGIN
static int qt_getInflectionPoints(const QBezier &orig, qreal *tpoints)
static const qreal epsilon
QT_BEGIN_NAMESPACE constexpr void qSwap(T &value1, T &value2) noexcept(std::is_nothrow_swappable_v< T >)
Q_CORE_EXPORT int qEnvironmentVariableIntValue(const char *varName, bool *ok=nullptr) noexcept
static QT_BEGIN_NAMESPACE void init(QTextBoundaryFinder::BoundaryType type, QStringView str, QCharAttributes *attributes)
static uint toIndex(ExecutionEngine *e, const Value &v)
QTextStream out(stdout)
[7]