/src/qtbase/src/gui/painting/qbezier.cpp

Source
// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
// Qt-Security score:significant reason:default

#include "qbezier_p.h"
#include <qdebug.h>
#include <qline.h>
#include <qmath.h>
#include <qpolygon.h>

#include <private/qnumeric_p.h>

#include <tuple> // for std::tie()

QT_BEGIN_NAMESPACE

//#define QDEBUG_BEZIER

/*!
  \internal
*/
QPolygonF QBezier::toPolygon(qreal bezier_flattening_threshold) const
{
    // flattening is done by splitting the bezier until we can replace the segment by a straight
    // line. We split further until the control points are close enough to the line connecting the
    // boundary points.
    //
    // the Distance of a point p from a line given by the points (a,b) is given by:
    //
    // d = abs( (bx - ax)(ay - py) - (by - ay)(ax - px) ) / line_length
    //
    // We can stop splitting if both control points are close enough to the line.
    // To make the algorithm faster we use the manhattan length of the line.

    QPolygonF polygon;
    polygon.append(QPointF(x1, y1));
    addToPolygon(&polygon, bezier_flattening_threshold);
    return polygon;
}

QBezier QBezier::mapBy(const QTransform &transform) const
{
    return QBezier::fromPoints(transform.map(pt1()), transform.map(pt2()), transform.map(pt3()), transform.map(pt4()));
}

QBezier QBezier::getSubRange(qreal t0, qreal t1) const
{
    QBezier result;
    QBezier temp;

    // cut at t1
    if (qFuzzyIsNull(t1 - qreal(1.))) {
        result = *this;
    } else {
        temp = *this;
        temp.parameterSplitLeft(t1, &result);
    }

    // cut at t0
    if (!qFuzzyIsNull(t0))
        result.parameterSplitLeft(t0 / t1, &temp);

    return result;
}

void QBezier::addToPolygon(QPolygonF *polygon, qreal bezier_flattening_threshold) const
{
    QBezier beziers[10];
    int levels[10];
    beziers[0] = *this;
    levels[0] = 9;
    int top = 0;

    while (top >= 0) {
        QBezier *b = &beziers[top];
        // check if we can pop the top bezier curve from the stack
        qreal y4y1 = b->y4 - b->y1;
        qreal x4x1 = b->x4 - b->x1;
        qreal l = qAbs(x4x1) + qAbs(y4y1);
        qreal d;
        if (l > 1.) {
            d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )
                + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );
        } else {
            d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
                qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
            l = 1.;
        }
        if (d < bezier_flattening_threshold * l || levels[top] == 0) {
            // good enough, we pop it off and add the endpoint
            polygon->append(QPointF(b->x4, b->y4));
            --top;
        } else {
            // split, second half of the polygon goes lower into the stack
            std::tie(b[1], b[0]) = b->split();
            levels[top + 1] = --levels[top];
            ++top;
        }
    }
}

void QBezier::addToPolygon(QDataBuffer<QPointF> &polygon, qreal bezier_flattening_threshold) const
{
    QBezier beziers[10];
    int levels[10];
    beziers[0] = *this;
    levels[0] = 9;
    int top = 0;

    while (top >= 0) {
        QBezier *b = &beziers[top];
        // check if we can pop the top bezier curve from the stack
        qreal y4y1 = b->y4 - b->y1;
        qreal x4x1 = b->x4 - b->x1;
        qreal l = qAbs(x4x1) + qAbs(y4y1);
        qreal d;
        if (l > 1.) {
            d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )
                + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );
        } else {
            d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
                qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
            l = 1.;
        }
        if (d < bezier_flattening_threshold * l || levels[top] == 0) {
            // good enough, we pop it off and add the endpoint
            polygon.add(QPointF(b->x4, b->y4));
            --top;
        } else {
            // split, second half of the polygon goes lower into the stack
            std::tie(b[1], b[0]) = b->split();
            levels[top + 1] = --levels[top];
            ++top;
        }
    }
}

QRectF QBezier::bounds() const
{
    qreal xmin = x1;
    qreal xmax = x1;
    if (x2 < xmin)
        xmin = x2;
    else if (x2 > xmax)
        xmax = x2;
    if (x3 < xmin)
        xmin = x3;
    else if (x3 > xmax)
        xmax = x3;
    if (x4 < xmin)
        xmin = x4;
    else if (x4 > xmax)
        xmax = x4;

    qreal ymin = y1;
    qreal ymax = y1;
    if (y2 < ymin)
        ymin = y2;
    else if (y2 > ymax)
        ymax = y2;
    if (y3 < ymin)
        ymin = y3;
    else if (y3 > ymax)
        ymax = y3;
    if (y4 < ymin)
        ymin = y4;
    else if (y4 > ymax)
        ymax = y4;
    return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
}


enum ShiftResult {
    Ok,
    Discard,
    Split,
    Circle
};

static ShiftResult good_offset(const QBezier *b1, const QBezier *b2, qreal offset, qreal threshold)
{
    const qreal o2 = offset*offset;
    const qreal max_dist_line = threshold*offset*offset;
    const qreal max_dist_normal = threshold*offset;
    const int divisions = 4;
    const qreal spacing = qreal(1.0) / divisions;
    qreal t = spacing;
    for (int i = 1; i < divisions; ++i, t += spacing) {
        QPointF p1 = b1->pointAt(t);
        QPointF p2 = b2->pointAt(t);
        qreal d = (p1.x() - p2.x())*(p1.x() - p2.x()) + (p1.y() - p2.y())*(p1.y() - p2.y());
        if (qAbs(d - o2) > max_dist_line)
            return Split;

        QPointF normalPoint = b1->normalVector(t);
        qreal l = qAbs(normalPoint.x()) + qAbs(normalPoint.y());
        if (l != qreal(0.0)) {
            d = qAbs( normalPoint.x()*(p1.y() - p2.y()) - normalPoint.y()*(p1.x() - p2.x()) ) / l;
            if (d > max_dist_normal)
                return Split;
        }
    }
    return Ok;
}

QT_WARNING_DISABLE_FLOAT_COMPARE

static ShiftResult shift(const QBezier *orig, QBezier *shifted, qreal offset, qreal threshold)
{
    int map[4];
    bool p1_p2_equal = qFuzzyCompare(orig->x1, orig->x2) && qFuzzyCompare(orig->y1, orig->y2);
    bool p2_p3_equal = qFuzzyCompare(orig->x2, orig->x3) && qFuzzyCompare(orig->y2, orig->y3);
    bool p3_p4_equal = qFuzzyCompare(orig->x3, orig->x4) && qFuzzyCompare(orig->y3, orig->y4);

    QPointF points[4];
    int np = 0;
    points[np] = QPointF(orig->x1, orig->y1);
    map[0] = 0;
    ++np;
    if (!p1_p2_equal) {
        points[np] = QPointF(orig->x2, orig->y2);
        ++np;
    }
    map[1] = np - 1;
    if (!p2_p3_equal) {
        points[np] = QPointF(orig->x3, orig->y3);
        ++np;
    }
    map[2] = np - 1;
    if (!p3_p4_equal) {
        points[np] = QPointF(orig->x4, orig->y4);
        ++np;
    }
    map[3] = np - 1;
    if (np == 1)
        return Discard;

    QRectF b = orig->bounds();
    if (np == 4 && b.width() < .1*offset && b.height() < .1*offset) {
        qreal l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +
                  (orig->y1 - orig->y2)*(orig->y1 - orig->y2) *
                  (orig->x3 - orig->x4)*(orig->x3 - orig->x4) +
                  (orig->y3 - orig->y4)*(orig->y3 - orig->y4);
        qreal dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +
                    (orig->y1 - orig->y2)*(orig->y3 - orig->y4);
        if (dot < 0 && dot*dot < 0.8*l)
            // the points are close and reverse dirction. Approximate the whole
            // thing by a semi circle
            return Circle;
    }

    QPointF points_shifted[4];

    QLineF prev = QLineF(QPointF(), points[1] - points[0]);
    if (!prev.length())
        return Discard;
    QPointF prev_normal = prev.normalVector().unitVector().p2();

    points_shifted[0] = points[0] + offset * prev_normal;

    for (int i = 1; i < np - 1; ++i) {
        QLineF next = QLineF(QPointF(), points[i + 1] - points[i]);
        QPointF next_normal = next.normalVector().unitVector().p2();

        QPointF normal_sum = prev_normal + next_normal;

        qreal r = qreal(1.0) + prev_normal.x() * next_normal.x()
                  + prev_normal.y() * next_normal.y();

        if (qFuzzyIsNull(r)) {
            points_shifted[i] = points[i] + offset * prev_normal;
        } else {
            qreal k = offset / r;
            points_shifted[i] = points[i] + k * normal_sum;
        }

        prev_normal = next_normal;
    }

    points_shifted[np - 1] = points[np - 1] + offset * prev_normal;

    *shifted = QBezier::fromPoints(points_shifted[map[0]], points_shifted[map[1]],
                                   points_shifted[map[2]], points_shifted[map[3]]);

    if (np > 2)
        return good_offset(orig, shifted, offset, threshold);
    return Ok;
}

// This value is used to determine the length of control point vectors
// when approximating arc segments as curves. The factor is multiplied
// with the radius of the circle.
#define KAPPA qreal(0.5522847498)


static bool addCircle(const QBezier *b, qreal offset, QBezier *o)
{
    QPointF normals[3];

    normals[0] = QPointF(b->y2 - b->y1, b->x1 - b->x2);
    qreal dist = qSqrt(normals[0].x()*normals[0].x() + normals[0].y()*normals[0].y());
    if (qFuzzyIsNull(dist))
        return false;
    normals[0] /= dist;
    normals[2] = QPointF(b->y4 - b->y3, b->x3 - b->x4);
    dist = qSqrt(normals[2].x()*normals[2].x() + normals[2].y()*normals[2].y());
    if (qFuzzyIsNull(dist))
        return false;
    normals[2] /= dist;

    normals[1] = QPointF(b->x1 - b->x2 - b->x3 + b->x4, b->y1 - b->y2 - b->y3 + b->y4);
    normals[1] /= -1*qSqrt(normals[1].x()*normals[1].x() + normals[1].y()*normals[1].y());

    qreal angles[2];
    qreal sign = 1.;
    for (int i = 0; i < 2; ++i) {
        qreal cos_a = normals[i].x()*normals[i+1].x() + normals[i].y()*normals[i+1].y();
        if (cos_a > 1.)
            cos_a = 1.;
        if (cos_a < -1.)
            cos_a = -1;
        angles[i] = qAcos(cos_a) * qreal(M_1_PI);
    }

    if (angles[0] + angles[1] > 1.) {
        // more than 180 degrees
        normals[1] = -normals[1];
        angles[0] = 1. - angles[0];
        angles[1] = 1. - angles[1];
        sign = -1.;

    }

    QPointF circle[3];
    circle[0] = QPointF(b->x1, b->y1) + normals[0]*offset;
    circle[1] = QPointF(qreal(0.5)*(b->x1 + b->x4), qreal(0.5)*(b->y1 + b->y4)) + normals[1]*offset;
    circle[2] = QPointF(b->x4, b->y4) + normals[2]*offset;

    for (int i = 0; i < 2; ++i) {
        qreal kappa = qreal(2.0) * KAPPA * sign * offset * angles[i];

        o->x1 = circle[i].x();
        o->y1 = circle[i].y();
        o->x2 = circle[i].x() - normals[i].y()*kappa;
        o->y2 = circle[i].y() + normals[i].x()*kappa;
        o->x3 = circle[i+1].x() + normals[i+1].y()*kappa;
        o->y3 = circle[i+1].y() - normals[i+1].x()*kappa;
        o->x4 = circle[i+1].x();
        o->y4 = circle[i+1].y();

        ++o;
    }
    return true;
}

int QBezier::shifted(QBezier *curveSegments, int maxSegments, qreal offset, float threshold) const
{
    Q_ASSERT(curveSegments);
    Q_ASSERT(maxSegments > 0);

    if (qFuzzyCompare(x1, x2) && qFuzzyCompare(x1, x3) && qFuzzyCompare(x1, x4) &&
        qFuzzyCompare(y1, y2) && qFuzzyCompare(y1, y3) && qFuzzyCompare(y1, y4))
        return 0;

    --maxSegments;
    QBezier beziers[10];
redo:
    beziers[0] = *this;
    QBezier *b = beziers;
    QBezier *o = curveSegments;

    while (b >= beziers) {
        int stack_segments = b - beziers + 1;
        if ((stack_segments == 10) || (o - curveSegments == maxSegments - stack_segments)) {
            threshold *= qreal(1.5);
            if (threshold > qreal(2.0))
                goto give_up;
            goto redo;
        }
        ShiftResult res = shift(b, o, offset, threshold);
        if (res == Discard) {
            --b;
        } else if (res == Ok) {
            ++o;
            --b;
        } else if (res == Circle && maxSegments - (o - curveSegments) >= 2) {
            // add semi circle
            if (addCircle(b, offset, o))
                o += 2;
            --b;
        } else {
            std::tie(b[1], b[0]) = b->split();
            ++b;
        }
    }

give_up:
    while (b >= beziers) {
        ShiftResult res = shift(b, o, offset, threshold);

        // if res isn't Ok or Split then *o is undefined
        if (res == Ok || res == Split)
            ++o;

        --b;
    }

    Q_ASSERT(o - curveSegments <= maxSegments);
    return o - curveSegments;
}

#ifdef QDEBUG_BEZIER
static QDebug operator<<(QDebug dbg, const QBezier &bz)
{
    dbg << '[' << bz.x1<< ", " << bz.y1 << "], "
        << '[' << bz.x2 <<", " << bz.y2 << "], "
        << '[' << bz.x3 <<", " << bz.y3 << "], "
        << '[' << bz.x4 <<", " << bz.y4 << ']';
    return dbg;
}
#endif

qreal QBezier::length(qreal error) const
{
    qreal length = qreal(0.0);

    addIfClose(&length, error);

    return length;
}

void QBezier::addIfClose(qreal *length, qreal error) const
{
    qreal len = qreal(0.0);  /* arc length */
    qreal chord;             /* chord length */

    len = len + QLineF(QPointF(x1, y1),QPointF(x2, y2)).length();
    len = len + QLineF(QPointF(x2, y2),QPointF(x3, y3)).length();
    len = len + QLineF(QPointF(x3, y3),QPointF(x4, y4)).length();

    chord = QLineF(QPointF(x1, y1),QPointF(x4, y4)).length();

    if ((len-chord) > error) {
        const auto halves = split();                  /* split in two */
        halves.first.addIfClose(length, error);       /* try left side */
        halves.second.addIfClose(length, error);      /* try right side */
        return;
    }

    *length = *length + len;

    return;
}

qreal QBezier::tForY(qreal t0, qreal t1, qreal y) const
{
    qreal py0 = pointAt(t0).y();
    qreal py1 = pointAt(t1).y();

    if (py0 > py1) {
        qSwap(py0, py1);
        qSwap(t0, t1);
    }

    Q_ASSERT(py0 <= py1);

    if (py0 >= y)
        return t0;
    else if (py1 <= y)
        return t1;

    Q_ASSERT(py0 < y && y < py1);

    qreal lt = t0;
    qreal dt;
    do {
        qreal t = qreal(0.5) * (t0 + t1);

        qreal a, b, c, d;
        QBezier::coefficients(t, a, b, c, d);
        qreal yt = a * y1 + b * y2 + c * y3 + d * y4;

        if (yt < y) {
            t0 = t;
            py0 = yt;
        } else {
            t1 = t;
            py1 = yt;
        }
        dt = lt - t;
        lt = t;
    } while (qAbs(dt) > qreal(1e-7));

    return t0;
}

int QBezier::stationaryYPoints(qreal &t0, qreal &t1) const
{
    // y(t) = (1 - t)^3 * y1 + 3 * (1 - t)^2 * t * y2 + 3 * (1 - t) * t^2 * y3 + t^3 * y4
    // y'(t) = 3 * (-(1-2t+t^2) * y1 + (1 - 4 * t + 3 * t^2) * y2 + (2 * t - 3 * t^2) * y3 + t^2 * y4)
    // y'(t) = 3 * ((-y1 + 3 * y2 - 3 * y3 + y4)t^2 + (2 * y1 - 4 * y2 + 2 * y3)t + (-y1 + y2))

    const qreal a = -y1 + 3 * y2 - 3 * y3 + y4;
    const qreal b = 2 * y1 - 4 * y2 + 2 * y3;
    const qreal c = -y1 + y2;

    if (qFuzzyIsNull(a)) {
        if (qFuzzyIsNull(b))
            return 0;

        t0 = -c / b;
        return t0 > 0 && t0 < 1;
    }

    qreal reciprocal = b * b - 4 * a * c;

    if (qFuzzyIsNull(reciprocal)) {
        t0 = -b / (2 * a);
        return t0 > 0 && t0 < 1;
    } else if (reciprocal > 0) {
        qreal temp = qSqrt(reciprocal);

        t0 = (-b - temp)/(2*a);
        t1 = (-b + temp)/(2*a);

        if (t1 < t0)
            qSwap(t0, t1);

        int count = 0;
        qreal t[2] = { 0, 1 };

        if (t0 > 0 && t0 < 1)
            t[count++] = t0;
        if (t1 > 0 && t1 < 1)
            t[count++] = t1;

        t0 = t[0];
        t1 = t[1];

        return count;
    }

    return 0;
}

qreal QBezier::tAtLength(qreal l) const
{
    qreal len = length();
    qreal t   = qreal(1.0);
    const qreal error = qreal(0.01);
    if (l > len || qFuzzyCompare(l, len))
        return t;

    t *= qreal(0.5);
    //int iters = 0;
    //qDebug()<<"LEN is "<<l<<len;
    qreal lastBigger = qreal(1.0);
    while (1) {
        //qDebug()<<"\tt is "<<t;
        QBezier right = *this;
        QBezier left;
        right.parameterSplitLeft(t, &left);
        qreal lLen = left.length();
        if (qAbs(lLen - l) < error)
            break;

        if (lLen < l) {
            t += (lastBigger - t) * qreal(0.5);
        } else {
            lastBigger = t;
            t -= t * qreal(0.5);
        }
        //++iters;
    }
    //qDebug()<<"number of iters is "<<iters;
    return t;
}

QBezier QBezier::bezierOnInterval(qreal t0, qreal t1) const
{
    if (t0 == 0 && t1 == 1)
        return *this;

    QBezier bezier = *this;

    QBezier result;
    bezier.parameterSplitLeft(t0, &result);
    qreal trueT = (t1-t0)/(1-t0);
    bezier.parameterSplitLeft(trueT, &result);

    return result;
}

QT_END_NAMESPACE

Coverage Report

Created: 2026-02-26 07:48

Line	Count	Source
1		// Copyright (C) 2016 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		// Qt-Security score:significant reason:default
4
5		#include "qbezier_p.h"
6		#include <qdebug.h>
7		#include <qline.h>
8		#include <qmath.h>
9		#include <qpolygon.h>
10
11		#include <private/qnumeric_p.h>
12
13		#include <tuple> // for std::tie()
14
15		QT_BEGIN_NAMESPACE
16
17		//#define QDEBUG_BEZIER
18
19		/*!
20		\internal
21		*/
22		QPolygonF QBezier::toPolygon(qreal bezier_flattening_threshold) const
23	0	{
24		// flattening is done by splitting the bezier until we can replace the segment by a straight
25		// line. We split further until the control points are close enough to the line connecting the
26		// boundary points.
27		//
28		// the Distance of a point p from a line given by the points (a,b) is given by:
29		//
30		// d = abs( (bx - ax)(ay - py) - (by - ay)(ax - px) ) / line_length
31		//
32		// We can stop splitting if both control points are close enough to the line.
33		// To make the algorithm faster we use the manhattan length of the line.
34
35	0	QPolygonF polygon;
36	0	polygon.append(QPointF(x1, y1));
37	0	addToPolygon(&polygon, bezier_flattening_threshold);
38	0	return polygon;
39	0	}
40
41		QBezier QBezier::mapBy(const QTransform &transform) const
42	0	{
43	0	return QBezier::fromPoints(transform.map(pt1()), transform.map(pt2()), transform.map(pt3()), transform.map(pt4()));
44	0	}
45
46		QBezier QBezier::getSubRange(qreal t0, qreal t1) const
47	0	{
48	0	QBezier result;
49	0	QBezier temp;
50
51		// cut at t1
52	0	if (qFuzzyIsNull(t1 - qreal(1.))) {
53	0	result = *this;
54	0	} else {
55	0	temp = *this;
56	0	temp.parameterSplitLeft(t1, &result);
57	0	}
58
59		// cut at t0
60	0	if (!qFuzzyIsNull(t0))
61	0	result.parameterSplitLeft(t0 / t1, &temp);
62
63	0	return result;
64	0	}
65
66		void QBezier::addToPolygon(QPolygonF *polygon, qreal bezier_flattening_threshold) const
67	0	{
68	0	QBezier beziers[10];
69	0	int levels[10];
70	0	beziers[0] = *this;
71	0	levels[0] = 9;
72	0	int top = 0;
73
74	0	while (top >= 0) {
75	0	QBezier *b = &beziers[top];
76		// check if we can pop the top bezier curve from the stack
77	0	qreal y4y1 = b->y4 - b->y1;
78	0	qreal x4x1 = b->x4 - b->x1;
79	0	qreal l = qAbs(x4x1) + qAbs(y4y1);
80	0	qreal d;
81	0	if (l > 1.) {
82	0	d = qAbs( (x4x1)(b->y1 - b->y2) - (y4y1)(b->x1 - b->x2) )
83	0	+ qAbs( (x4x1)(b->y1 - b->y3) - (y4y1)(b->x1 - b->x3) );
84	0	} else {
85	0	d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
86	0	qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
87	0	l = 1.;
88	0	}
89	0	if (d < bezier_flattening_threshold * l \|\| levels[top] == 0) {
90		// good enough, we pop it off and add the endpoint
91	0	polygon->append(QPointF(b->x4, b->y4));
92	0	--top;
93	0	} else {
94		// split, second half of the polygon goes lower into the stack
95	0	std::tie(b[1], b[0]) = b->split();
96	0	levels[top + 1] = --levels[top];
97	0	++top;
98	0	}
99	0	}
100	0	}
101
102		void QBezier::addToPolygon(QDataBuffer<QPointF> &polygon, qreal bezier_flattening_threshold) const
103	734k	{
104	734k	QBezier beziers[10];
105	734k	int levels[10];
106	734k	beziers[0] = *this;
107	734k	levels[0] = 9;
108	734k	int top = 0;
109
110	30.1M	while (top >= 0) {
111	29.4M	QBezier *b = &beziers[top];
112		// check if we can pop the top bezier curve from the stack
113	29.4M	qreal y4y1 = b->y4 - b->y1;
114	29.4M	qreal x4x1 = b->x4 - b->x1;
115	29.4M	qreal l = qAbs(x4x1) + qAbs(y4y1);
116	29.4M	qreal d;
117	29.4M	if (l > 1.) {
118	4.39M	d = qAbs( (x4x1)(b->y1 - b->y2) - (y4y1)(b->x1 - b->x2) )
119	4.39M	+ qAbs( (x4x1)(b->y1 - b->y3) - (y4y1)(b->x1 - b->x3) );
120	25.0M	} else {
121	25.0M	d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
122	25.0M	qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
123	25.0M	l = 1.;
124	25.0M	}
125	29.4M	if (d < bezier_flattening_threshold * l \|\| levels[top] == 0) {
126		// good enough, we pop it off and add the endpoint
127	15.0M	polygon.add(QPointF(b->x4, b->y4));
128	15.0M	--top;
129	15.0M	} else {
130		// split, second half of the polygon goes lower into the stack
131	14.3M	std::tie(b[1], b[0]) = b->split();
132	14.3M	levels[top + 1] = --levels[top];
133	14.3M	++top;
134	14.3M	}
135	29.4M	}
136	734k	}
137
138		QRectF QBezier::bounds() const
139	4.06M	{
140	4.06M	qreal xmin = x1;
141	4.06M	qreal xmax = x1;
142	4.06M	if (x2 < xmin)
143	1.10M	xmin = x2;
144	2.96M	else if (x2 > xmax)
145	985k	xmax = x2;
146	4.06M	if (x3 < xmin)
147	1.18M	xmin = x3;
148	2.88M	else if (x3 > xmax)
149	1.09M	xmax = x3;
150	4.06M	if (x4 < xmin)
151	1.02M	xmin = x4;
152	3.04M	else if (x4 > xmax)
153	901k	xmax = x4;
154
155	4.06M	qreal ymin = y1;
156	4.06M	qreal ymax = y1;
157	4.06M	if (y2 < ymin)
158	1.70M	ymin = y2;
159	2.36M	else if (y2 > ymax)
160	1.64M	ymax = y2;
161	4.06M	if (y3 < ymin)
162	2.04M	ymin = y3;
163	2.02M	else if (y3 > ymax)
164	1.76M	ymax = y3;
165	4.06M	if (y4 < ymin)
166	1.81M	ymin = y4;
167	2.25M	else if (y4 > ymax)
168	1.44M	ymax = y4;
169	4.06M	return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
170	4.06M	}
171
172
173		enum ShiftResult {
174		Ok,
175		Discard,
176		Split,
177		Circle
178		};
179
180		static ShiftResult good_offset(const QBezier b1, const QBezier b2, qreal offset, qreal threshold)
181	3.80M	{
182	3.80M	const qreal o2 = offset*offset;
183	3.80M	const qreal max_dist_line = thresholdoffsetoffset;
184	3.80M	const qreal max_dist_normal = threshold*offset;
185	3.80M	const int divisions = 4;
186	3.80M	const qreal spacing = qreal(1.0) / divisions;
187	3.80M	qreal t = spacing;
188	8.28M	for (int i = 1; i < divisions; ++i, t += spacing) {
189	7.00M	QPointF p1 = b1->pointAt(t);
190	7.00M	QPointF p2 = b2->pointAt(t);
191	7.00M	qreal d = (p1.x() - p2.x())(p1.x() - p2.x()) + (p1.y() - p2.y())(p1.y() - p2.y());
192	7.00M	if (qAbs(d - o2) > max_dist_line)
193	2.13M	return Split;
194
195	4.86M	QPointF normalPoint = b1->normalVector(t);
196	4.86M	qreal l = qAbs(normalPoint.x()) + qAbs(normalPoint.y());
197	4.86M	if (l != qreal(0.0)) {
198	4.86M	d = qAbs( normalPoint.x()(p1.y() - p2.y()) - normalPoint.y()(p1.x() - p2.x()) ) / l;
199	4.86M	if (d > max_dist_normal)
200	383k	return Split;
201	4.86M	}
202	4.86M	}
203	1.28M	return Ok;
204	3.80M	}
205
206		QT_WARNING_DISABLE_FLOAT_COMPARE
207
208		static ShiftResult shift(const QBezier orig, QBezier shifted, qreal offset, qreal threshold)
209	4.05M	{
210	4.05M	int map[4];
211	4.05M	bool p1_p2_equal = qFuzzyCompare(orig->x1, orig->x2) && qFuzzyCompare(orig->y1, orig->y2);
212	4.05M	bool p2_p3_equal = qFuzzyCompare(orig->x2, orig->x3) && qFuzzyCompare(orig->y2, orig->y3);
213	4.05M	bool p3_p4_equal = qFuzzyCompare(orig->x3, orig->x4) && qFuzzyCompare(orig->y3, orig->y4);
214
215	4.05M	QPointF points[4];
216	4.05M	int np = 0;
217	4.05M	points[np] = QPointF(orig->x1, orig->y1);
218	4.05M	map[0] = 0;
219	4.05M	++np;
220	4.05M	if (!p1_p2_equal) {
221	3.42M	points[np] = QPointF(orig->x2, orig->y2);
222	3.42M	++np;
223	3.42M	}
224	4.05M	map[1] = np - 1;
225	4.05M	if (!p2_p3_equal) {
226	3.80M	points[np] = QPointF(orig->x3, orig->y3);
227	3.80M	++np;
228	3.80M	}
229	4.05M	map[2] = np - 1;
230	4.05M	if (!p3_p4_equal) {
231	3.72M	points[np] = QPointF(orig->x4, orig->y4);
232	3.72M	++np;
233	3.72M	}
234	4.05M	map[3] = np - 1;
235	4.05M	if (np == 1)
236	231k	return Discard;
237
238	3.82M	QRectF b = orig->bounds();
239	3.82M	if (np == 4 && b.width() < .1offset && b.height() < .1offset) {
240	550k	qreal l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +
241	550k	(orig->y1 - orig->y2)(orig->y1 - orig->y2)
242	550k	(orig->x3 - orig->x4)*(orig->x3 - orig->x4) +
243	550k	(orig->y3 - orig->y4)*(orig->y3 - orig->y4);
244	550k	qreal dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +
245	550k	(orig->y1 - orig->y2)*(orig->y3 - orig->y4);
246	550k	if (dot < 0 && dotdot < 0.8l)
247		// the points are close and reverse dirction. Approximate the whole
248		// thing by a semi circle
249	20.2k	return Circle;
250	550k	}
251
252	3.80M	QPointF points_shifted[4];
253
254	3.80M	QLineF prev = QLineF(QPointF(), points[1] - points[0]);
255	3.80M	if (!prev.length())
256	0	return Discard;
257	3.80M	QPointF prev_normal = prev.normalVector().unitVector().p2();
258
259	3.80M	points_shifted[0] = points[0] + offset * prev_normal;
260
261	10.8M	for (int i = 1; i < np - 1; ++i) {
262	7.09M	QLineF next = QLineF(QPointF(), points[i + 1] - points[i]);
263	7.09M	QPointF next_normal = next.normalVector().unitVector().p2();
264
265	7.09M	QPointF normal_sum = prev_normal + next_normal;
266
267	7.09M	qreal r = qreal(1.0) + prev_normal.x() * next_normal.x()
268	7.09M	+ prev_normal.y() * next_normal.y();
269
270	7.09M	if (qFuzzyIsNull(r)) {
271	193k	points_shifted[i] = points[i] + offset * prev_normal;
272	6.89M	} else {
273	6.89M	qreal k = offset / r;
274	6.89M	points_shifted[i] = points[i] + k * normal_sum;
275	6.89M	}
276
277	7.09M	prev_normal = next_normal;
278	7.09M	}
279
280	3.80M	points_shifted[np - 1] = points[np - 1] + offset * prev_normal;
281
282	3.80M	*shifted = QBezier::fromPoints(points_shifted[map[0]], points_shifted[map[1]],
283	3.80M	points_shifted[map[2]], points_shifted[map[3]]);
284
285	3.80M	if (np > 2)
286	3.80M	return good_offset(orig, shifted, offset, threshold);
287	784	return Ok;
288	3.80M	}
289
290		// This value is used to determine the length of control point vectors
291		// when approximating arc segments as curves. The factor is multiplied
292		// with the radius of the circle.
293	38.5k	#define KAPPA qreal(0.5522847498)
294
295
296		static bool addCircle(const QBezier b, qreal offset, QBezier o)
297	20.2k	{
298	20.2k	QPointF normals[3];
299
300	20.2k	normals[0] = QPointF(b->y2 - b->y1, b->x1 - b->x2);
301	20.2k	qreal dist = qSqrt(normals[0].x()normals[0].x() + normals[0].y()normals[0].y());
302	20.2k	if (qFuzzyIsNull(dist))
303	471	return false;
304	19.7k	normals[0] /= dist;
305	19.7k	normals[2] = QPointF(b->y4 - b->y3, b->x3 - b->x4);
306	19.7k	dist = qSqrt(normals[2].x()normals[2].x() + normals[2].y()normals[2].y());
307	19.7k	if (qFuzzyIsNull(dist))
308	475	return false;
309	19.2k	normals[2] /= dist;
310
311	19.2k	normals[1] = QPointF(b->x1 - b->x2 - b->x3 + b->x4, b->y1 - b->y2 - b->y3 + b->y4);
312	19.2k	normals[1] /= -1qSqrt(normals[1].x()normals[1].x() + normals[1].y()*normals[1].y());
313
314	19.2k	qreal angles[2];
315	19.2k	qreal sign = 1.;
316	57.8k	for (int i = 0; i < 2; ++i) {
317	38.5k	qreal cos_a = normals[i].x()normals[i+1].x() + normals[i].y()normals[i+1].y();
318	38.5k	if (cos_a > 1.)
319	0	cos_a = 1.;
320	38.5k	if (cos_a < -1.)
321	0	cos_a = -1;
322	38.5k	angles[i] = qAcos(cos_a) * qreal(M_1_PI);
323	38.5k	}
324
325	19.2k	if (angles[0] + angles[1] > 1.) {
326		// more than 180 degrees
327	5.52k	normals[1] = -normals[1];
328	5.52k	angles[0] = 1. - angles[0];
329	5.52k	angles[1] = 1. - angles[1];
330	5.52k	sign = -1.;
331
332	5.52k	}
333
334	19.2k	QPointF circle[3];
335	19.2k	circle[0] = QPointF(b->x1, b->y1) + normals[0]*offset;
336	19.2k	circle[1] = QPointF(qreal(0.5)(b->x1 + b->x4), qreal(0.5)(b->y1 + b->y4)) + normals[1]*offset;
337	19.2k	circle[2] = QPointF(b->x4, b->y4) + normals[2]*offset;
338
339	57.8k	for (int i = 0; i < 2; ++i) {
340	38.5k	qreal kappa = qreal(2.0) * KAPPA * sign * offset * angles[i];
341
342	38.5k	o->x1 = circle[i].x();
343	38.5k	o->y1 = circle[i].y();
344	38.5k	o->x2 = circle[i].x() - normals[i].y()*kappa;
345	38.5k	o->y2 = circle[i].y() + normals[i].x()*kappa;
346	38.5k	o->x3 = circle[i+1].x() + normals[i+1].y()*kappa;
347	38.5k	o->y3 = circle[i+1].y() - normals[i+1].x()*kappa;
348	38.5k	o->x4 = circle[i+1].x();
349	38.5k	o->y4 = circle[i+1].y();
350
351	38.5k	++o;
352	38.5k	}
353	19.2k	return true;
354	19.7k	}
355
356		int QBezier::shifted(QBezier *curveSegments, int maxSegments, qreal offset, float threshold) const
357	613k	{
358	613k	Q_ASSERT(curveSegments);
359	613k	Q_ASSERT(maxSegments > 0);
360
361	613k	if (qFuzzyCompare(x1, x2) && qFuzzyCompare(x1, x3) && qFuzzyCompare(x1, x4) &&
362	51.1k	qFuzzyCompare(y1, y2) && qFuzzyCompare(y1, y3) && qFuzzyCompare(y1, y4))
363	0	return 0;
364
365	613k	--maxSegments;
366	613k	QBezier beziers[10];
367	806k	redo:
368	806k	beziers[0] = *this;
369	806k	QBezier *b = beziers;
370	806k	QBezier *o = curveSegments;
371
372	4.86M	while (b >= beziers) {
373	4.25M	int stack_segments = b - beziers + 1;
374	4.25M	if ((stack_segments == 10) \|\| (o - curveSegments == maxSegments - stack_segments)) {
375	193k	threshold *= qreal(1.5);
376	193k	if (threshold > qreal(2.0))
377	257	goto give_up;
378	193k	goto redo;
379	193k	}
380	4.05M	ShiftResult res = shift(b, o, offset, threshold);
381	4.05M	if (res == Discard) {
382	231k	--b;
383	3.82M	} else if (res == Ok) {
384	1.28M	++o;
385	1.28M	--b;
386	2.53M	} else if (res == Circle && maxSegments - (o - curveSegments) >= 2) {
387		// add semi circle
388	20.2k	if (addCircle(b, offset, o))
389	19.2k	o += 2;
390	20.2k	--b;
391	2.51M	} else {
392	2.51M	std::tie(b[1], b[0]) = b->split();
393	2.51M	++b;
394	2.51M	}
395	4.05M	}
396
397	613k	give_up:
398	614k	while (b >= beziers) {
399	1.83k	ShiftResult res = shift(b, o, offset, threshold);
400
401		// if res isn't Ok or Split then *o is undefined
402	1.83k	if (res == Ok \|\| res == Split)
403	1.80k	++o;
404
405	1.83k	--b;
406	1.83k	}
407
408	613k	Q_ASSERT(o - curveSegments <= maxSegments);
409	613k	return o - curveSegments;
410	806k	}
411
412		#ifdef QDEBUG_BEZIER
413		static QDebug operator<<(QDebug dbg, const QBezier &bz)
414		{
415		dbg << '[' << bz.x1<< ", " << bz.y1 << "], "
416		<< '[' << bz.x2 <<", " << bz.y2 << "], "
417		<< '[' << bz.x3 <<", " << bz.y3 << "], "
418		<< '[' << bz.x4 <<", " << bz.y4 << ']';
419		return dbg;
420		}
421		#endif
422
423		qreal QBezier::length(qreal error) const
424	0	{
425	0	qreal length = qreal(0.0);
426
427	0	addIfClose(&length, error);
428
429	0	return length;
430	0	}
431
432		void QBezier::addIfClose(qreal *length, qreal error) const
433	0	{
434	0	qreal len = qreal(0.0); /* arc length */
435	0	qreal chord; /* chord length */
436
437	0	len = len + QLineF(QPointF(x1, y1),QPointF(x2, y2)).length();
438	0	len = len + QLineF(QPointF(x2, y2),QPointF(x3, y3)).length();
439	0	len = len + QLineF(QPointF(x3, y3),QPointF(x4, y4)).length();
440
441	0	chord = QLineF(QPointF(x1, y1),QPointF(x4, y4)).length();
442
443	0	if ((len-chord) > error) {
444	0	const auto halves = split(); /* split in two */
445	0	halves.first.addIfClose(length, error); /* try left side */
446	0	halves.second.addIfClose(length, error); /* try right side */
447	0	return;
448	0	}
449
450	0	length = length + len;
451
452	0	return;
453	0	}
454
455		qreal QBezier::tForY(qreal t0, qreal t1, qreal y) const
456	0	{
457	0	qreal py0 = pointAt(t0).y();
458	0	qreal py1 = pointAt(t1).y();
459
460	0	if (py0 > py1) {
461	0	qSwap(py0, py1);
462	0	qSwap(t0, t1);
463	0	}
464
465	0	Q_ASSERT(py0 <= py1);
466
467	0	if (py0 >= y)
468	0	return t0;
469	0	else if (py1 <= y)
470	0	return t1;
471
472	0	Q_ASSERT(py0 < y && y < py1);
473
474	0	qreal lt = t0;
475	0	qreal dt;
476	0	do {
477	0	qreal t = qreal(0.5) * (t0 + t1);
478
479	0	qreal a, b, c, d;
480	0	QBezier::coefficients(t, a, b, c, d);
481	0	qreal yt = a * y1 + b * y2 + c * y3 + d * y4;
482
483	0	if (yt < y) {
484	0	t0 = t;
485	0	py0 = yt;
486	0	} else {
487	0	t1 = t;
488	0	py1 = yt;
489	0	}
490	0	dt = lt - t;
491	0	lt = t;
492	0	} while (qAbs(dt) > qreal(1e-7));
493
494	0	return t0;
495	0	}
496
497		int QBezier::stationaryYPoints(qreal &t0, qreal &t1) const
498	0	{
499		// y(t) = (1 - t)^3 * y1 + 3 * (1 - t)^2 * t * y2 + 3 * (1 - t) * t^2 * y3 + t^3 * y4
500		// y'(t) = 3 * (-(1-2t+t^2) * y1 + (1 - 4 * t + 3 * t^2) * y2 + (2 * t - 3 * t^2) * y3 + t^2 * y4)
501		// y'(t) = 3 * ((-y1 + 3 * y2 - 3 * y3 + y4)t^2 + (2 * y1 - 4 * y2 + 2 * y3)t + (-y1 + y2))
502
503	0	const qreal a = -y1 + 3 * y2 - 3 * y3 + y4;
504	0	const qreal b = 2 * y1 - 4 * y2 + 2 * y3;
505	0	const qreal c = -y1 + y2;
506
507	0	if (qFuzzyIsNull(a)) {
508	0	if (qFuzzyIsNull(b))
509	0	return 0;
510
511	0	t0 = -c / b;
512	0	return t0 > 0 && t0 < 1;
513	0	}
514
515	0	qreal reciprocal = b * b - 4 * a * c;
516
517	0	if (qFuzzyIsNull(reciprocal)) {
518	0	t0 = -b / (2 * a);
519	0	return t0 > 0 && t0 < 1;
520	0	} else if (reciprocal > 0) {
521	0	qreal temp = qSqrt(reciprocal);
522
523	0	t0 = (-b - temp)/(2*a);
524	0	t1 = (-b + temp)/(2*a);
525
526	0	if (t1 < t0)
527	0	qSwap(t0, t1);
528
529	0	int count = 0;
530	0	qreal t[2] = { 0, 1 };
531
532	0	if (t0 > 0 && t0 < 1)
533	0	t[count++] = t0;
534	0	if (t1 > 0 && t1 < 1)
535	0	t[count++] = t1;
536
537	0	t0 = t[0];
538	0	t1 = t[1];
539
540	0	return count;
541	0	}
542
543	0	return 0;
544	0	}
545
546		qreal QBezier::tAtLength(qreal l) const
547	0	{
548	0	qreal len = length();
549	0	qreal t = qreal(1.0);
550	0	const qreal error = qreal(0.01);
551	0	if (l > len \|\| qFuzzyCompare(l, len))
552	0	return t;
553
554	0	t *= qreal(0.5);
555		//int iters = 0;
556		//qDebug()<<"LEN is "<<l<<len;
557	0	qreal lastBigger = qreal(1.0);
558	0	while (1) {
559		//qDebug()<<"\tt is "<<t;
560	0	QBezier right = *this;
561	0	QBezier left;
562	0	right.parameterSplitLeft(t, &left);
563	0	qreal lLen = left.length();
564	0	if (qAbs(lLen - l) < error)
565	0	break;
566
567	0	if (lLen < l) {
568	0	t += (lastBigger - t) * qreal(0.5);
569	0	} else {
570	0	lastBigger = t;
571	0	t -= t * qreal(0.5);
572	0	}
573		//++iters;
574	0	}
575		//qDebug()<<"number of iters is "<<iters;
576	0	return t;
577	0	}
578
579		QBezier QBezier::bezierOnInterval(qreal t0, qreal t1) const
580	0	{
581	0	if (t0 == 0 && t1 == 1)
582	0	return *this;
583
584	0	QBezier bezier = *this;
585
586	0	QBezier result;
587	0	bezier.parameterSplitLeft(t0, &result);
588	0	qreal trueT = (t1-t0)/(1-t0);
589	0	bezier.parameterSplitLeft(trueT, &result);
590
591	0	return result;
592	0	}
593
594		QT_END_NAMESPACE