summaryrefslogtreecommitdiffstats
path: root/src/gui/painting/qbezier.cpp
diff options
context:
space:
mode:
authorLars Knoll <lars.knoll@nokia.com>2009-03-23 09:18:55 (GMT)
committerSimon Hausmann <simon.hausmann@nokia.com>2009-03-23 09:18:55 (GMT)
commite5fcad302d86d316390c6b0f62759a067313e8a9 (patch)
treec2afbf6f1066b6ce261f14341cf6d310e5595bc1 /src/gui/painting/qbezier.cpp
downloadQt-e5fcad302d86d316390c6b0f62759a067313e8a9.zip
Qt-e5fcad302d86d316390c6b0f62759a067313e8a9.tar.gz
Qt-e5fcad302d86d316390c6b0f62759a067313e8a9.tar.bz2
Long live Qt 4.5!
Diffstat (limited to 'src/gui/painting/qbezier.cpp')
-rw-r--r--src/gui/painting/qbezier.cpp1245
1 files changed, 1245 insertions, 0 deletions
diff --git a/src/gui/painting/qbezier.cpp b/src/gui/painting/qbezier.cpp
new file mode 100644
index 0000000..8317dd8
--- /dev/null
+++ b/src/gui/painting/qbezier.cpp
@@ -0,0 +1,1245 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QtGui module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain
+** additional rights. These rights are described in the Nokia Qt LGPL
+** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qbezier_p.h"
+#include <qdebug.h>
+#include <qline.h>
+#include <qpolygon.h>
+#include <qvector.h>
+#include <qlist.h>
+#include <qmath.h>
+
+#include <private/qnumeric_p.h>
+#include <private/qmath_p.h>
+
+QT_BEGIN_NAMESPACE
+
+//#define QDEBUG_BEZIER
+
+#ifdef FLOAT_ACCURACY
+#define INV_EPS (1L<<23)
+#else
+/* The value of 1.0 / (1L<<14) is enough for most applications */
+#define INV_EPS (1L<<14)
+#endif
+
+#ifndef M_SQRT2
+#define M_SQRT2 1.41421356237309504880
+#endif
+
+#define log2(x) (qLn(x)/qLn(2.))
+
+static inline qreal log4(qreal x)
+{
+ return qreal(0.5) * log2(x);
+}
+
+/*!
+ \internal
+*/
+QBezier QBezier::fromPoints(const QPointF &p1, const QPointF &p2,
+ const QPointF &p3, const QPointF &p4)
+{
+ QBezier b;
+ b.x1 = p1.x();
+ b.y1 = p1.y();
+ b.x2 = p2.x();
+ b.y2 = p2.y();
+ b.x3 = p3.x();
+ b.y3 = p3.y();
+ b.x4 = p4.x();
+ b.y4 = p4.y();
+ return b;
+}
+
+/*!
+ \internal
+*/
+QPolygonF QBezier::toPolygon() 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);
+ return polygon;
+}
+
+//0.5 is really low
+static const qreal flatness = 0.5;
+
+//based on "Fast, precise flattening of cubic Bezier path and offset curves"
+// by T. F. Hain, A. L. Ahmad, S. V. R. Racherla and D. D. Langan
+static inline void flattenBezierWithoutInflections(QBezier &bez,
+ QPolygonF *&p)
+{
+ QBezier left;
+
+ while (1) {
+ qreal dx = bez.x2 - bez.x1;
+ qreal dy = bez.y2 - bez.y1;
+
+ qreal normalized = qSqrt(dx * dx + dy * dy);
+ if (qFuzzyCompare(normalized + 1, 1))
+ break;
+
+ qreal d = qAbs(dx * (bez.y3 - bez.y2) - dy * (bez.x3 - bez.x2));
+
+ qreal t = qSqrt(4. / 3. * normalized * flatness / d);
+ if (t > 1 || qFuzzyCompare(t, (qreal)1.))
+ break;
+ bez.parameterSplitLeft(t, &left);
+ p->append(bez.pt1());
+ }
+}
+
+
+static inline int quadraticRoots(qreal a, qreal b, qreal c,
+ qreal *x1, qreal *x2)
+{
+ if (qFuzzyCompare(a + 1, 1)) {
+ if (qFuzzyCompare(b + 1, 1))
+ return 0;
+ *x1 = *x2 = (-c / b);
+ return 1;
+ } else {
+ const qreal det = b * b - 4 * a * c;
+ if (qFuzzyCompare(det + 1, 1)) {
+ *x1 = *x2 = -b / (2 * a);
+ return 1;
+ }
+ if (det > 0) {
+ if (qFuzzyCompare(b + 1, 1)) {
+ *x2 = qSqrt(-c / a);
+ *x1 = -(*x2);
+ return 2;
+ }
+ const qreal stableA = b / (2 * a);
+ const qreal stableB = c / (a * stableA * stableA);
+ const qreal stableC = -1 - qSqrt(1 - stableB);
+ *x2 = stableA * stableC;
+ *x1 = (stableA * stableB) / stableC;
+ return 2;
+ } else
+ return 0;
+ }
+}
+
+static inline bool findInflections(qreal a, qreal b, qreal c,
+ qreal *t1 , qreal *t2, qreal *tCups)
+{
+ qreal r1 = 0, r2 = 0;
+
+ short rootsCount = quadraticRoots(a, b, c, &r1, &r2);
+
+ if (rootsCount >= 1) {
+ if (r1 < r2) {
+ *t1 = r1;
+ *t2 = r2;
+ } else {
+ *t1 = r2;
+ *t2 = r1;
+ }
+ if (!qFuzzyCompare(a + 1, 1))
+ *tCups = 0.5 * (-b / a);
+ else
+ *tCups = 2;
+
+ return true;
+ }
+
+ return false;
+}
+
+
+void QBezier::addToPolygon(QPolygonF *polygon) const
+{
+ QBezier beziers[32];
+ beziers[0] = *this;
+ QBezier *b = beziers;
+
+ while (b >= beziers) {
+ // 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 < flatness*l || b == beziers + 31) {
+ // good enough, we pop it off and add the endpoint
+ polygon->append(QPointF(b->x4, b->y4));
+ --b;
+ } else {
+ // split, second half of the polygon goes lower into the stack
+ b->split(b+1, b);
+ ++b;
+ }
+ }
+}
+
+void QBezier::addToPolygonMixed(QPolygonF *polygon) const
+{
+ qreal ax = -x1 + 3*x2 - 3*x3 + x4;
+ qreal ay = -y1 + 3*y2 - 3*y3 + y4;
+ qreal bx = 3*x1 - 6*x2 + 3*x3;
+ qreal by = 3*y1 - 6*y2 + 3*y3;
+ qreal cx = -3*x1 + 3*x2;
+ qreal cy = -3*y1 + 2*y2;
+ qreal a = 6 * (ay * bx - ax * by);
+ qreal b = 6 * (ay * cx - ax * cy);
+ qreal c = 2 * (by * cx - bx * cy);
+
+ if ((qFuzzyCompare(a + 1, 1) && qFuzzyCompare(b + 1, 1)) ||
+ (b * b - 4 * a *c) < 0) {
+ QBezier bez(*this);
+ flattenBezierWithoutInflections(bez, polygon);
+ polygon->append(QPointF(x4, y4));
+ } else {
+ QBezier beziers[32];
+ beziers[0] = *this;
+ QBezier *b = beziers;
+
+ while (b >= beziers) {
+ // 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 < .5*l || b == beziers + 31) {
+ // good enough, we pop it off and add the endpoint
+ polygon->append(QPointF(b->x4, b->y4));
+ --b;
+ } else {
+ // split, second half of the polygon goes lower into the stack
+ b->split(b+1, b);
+ ++b;
+ }
+ }
+ }
+}
+
+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 qreal spacing = 0.25;
+ for (qreal i = spacing; i < 0.99; i += spacing) {
+ QPointF p1 = b1->pointAt(i);
+ QPointF p2 = b2->pointAt(i);
+ 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(i);
+ qreal l = qAbs(normalPoint.x()) + qAbs(normalPoint.y());
+ if (l != 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;
+}
+
+static inline QLineF qline_shifted(const QPointF &p1, const QPointF &p2, qreal offset)
+{
+ QLineF l(p1, p2);
+ QLineF ln = l.normalVector().unitVector();
+ l.translate(ln.dx() * offset, ln.dy() * offset);
+ return l;
+}
+
+static bool qbezier_is_line(QPointF *points, int pointCount)
+{
+ Q_ASSERT(pointCount > 2);
+
+ qreal dx13 = points[2].x() - points[0].x();
+ qreal dy13 = points[2].y() - points[0].y();
+
+ qreal dx12 = points[1].x() - points[0].x();
+ qreal dy12 = points[1].y() - points[0].y();
+
+ if (pointCount == 3) {
+ return qFuzzyCompare(dx12 * dy13, dx13 * dy12);
+ } else if (pointCount == 4) {
+ qreal dx14 = points[3].x() - points[0].x();
+ qreal dy14 = points[3].y() - points[0].y();
+
+ return (qFuzzyCompare(dx12 * dy13, dx13 * dy12) && qFuzzyCompare(dx12 * dy14, dx14 * dy12));
+ }
+
+ return false;
+}
+
+static ShiftResult shift(const QBezier *orig, QBezier *shifted, qreal offset, qreal threshold)
+{
+ int map[4];
+ bool p1_p2_equal = (orig->x1 == orig->x2 && orig->y1 == orig->y2);
+ bool p2_p3_equal = (orig->x2 == orig->x3 && orig->y2 == orig->y3);
+ bool p3_p4_equal = (orig->x3 == orig->x4 && 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;
+
+ // We need to specialcase lines of 3 or 4 points due to numerical
+ // instability in intersections below
+ if (np > 2 && qbezier_is_line(points, np)) {
+ if (points[0] == points[np-1])
+ return Discard;
+
+ QLineF l = qline_shifted(points[0], points[np-1], offset);
+ *shifted = QBezier::fromPoints(l.p1(), l.pointAt(qreal(0.33)), l.pointAt(qreal(0.66)), l.p2());
+ return Ok;
+ }
+
+ 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->y1) *
+ (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]);
+ 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 = 1.0 + prev_normal.x() * next_normal.x()
+ + prev_normal.y() * next_normal.y();
+
+ if (qFuzzyCompare(r + 1, 1)) {
+ 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]]);
+
+ return good_offset(orig, shifted, offset, threshold);
+}
+
+// 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 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 (qFuzzyCompare(dist + 1, 1))
+ 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 (qFuzzyCompare(dist + 1, 1))
+ 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] = acos(cos_a)/Q_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(0.5*(b->x1 + b->x4), 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 = 2.*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 (x1 == x2 && x1 == x3 && x1 == x4 &&
+ y1 == y2 && y1 == y3 && 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 *= 1.5;
+ if (threshold > 2.)
+ goto give_up;
+ goto redo;
+ }
+ ShiftResult res = shift(b, o, offset, threshold);
+ if (res == Discard) {
+ --b;
+ } else if (res == Ok) {
+ ++o;
+ --b;
+ continue;
+ } else if (res == Circle && maxSegments - (o - curveSegments) >= 2) {
+ // add semi circle
+ if (addCircle(b, offset, o))
+ o += 2;
+ --b;
+ } else {
+ b->split(b+1, b);
+ ++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;
+}
+
+#if 0
+static inline bool IntersectBB(const QBezier &a, const QBezier &b)
+{
+ return a.bounds().intersects(b.bounds());
+}
+#else
+static int IntersectBB(const QBezier &a, const QBezier &b)
+{
+ // Compute bounding box for a
+ qreal minax, maxax, minay, maxay;
+ if (a.x1 > a.x4) // These are the most likely to be extremal
+ minax = a.x4, maxax = a.x1;
+ else
+ minax = a.x1, maxax = a.x4;
+
+ if (a.x3 < minax)
+ minax = a.x3;
+ else if (a.x3 > maxax)
+ maxax = a.x3;
+
+ if (a.x2 < minax)
+ minax = a.x2;
+ else if (a.x2 > maxax)
+ maxax = a.x2;
+
+ if (a.y1 > a.y4)
+ minay = a.y4, maxay = a.y1;
+ else
+ minay = a.y1, maxay = a.y4;
+
+ if (a.y3 < minay)
+ minay = a.y3;
+ else if (a.y3 > maxay)
+ maxay = a.y3;
+
+ if (a.y2 < minay)
+ minay = a.y2;
+ else if (a.y2 > maxay)
+ maxay = a.y2;
+
+ // Compute bounding box for b
+ qreal minbx, maxbx, minby, maxby;
+ if (b.x1 > b.x4)
+ minbx = b.x4, maxbx = b.x1;
+ else
+ minbx = b.x1, maxbx = b.x4;
+
+ if (b.x3 < minbx)
+ minbx = b.x3;
+ else if (b.x3 > maxbx)
+ maxbx = b.x3;
+
+ if (b.x2 < minbx)
+ minbx = b.x2;
+ else if (b.x2 > maxbx)
+ maxbx = b.x2;
+
+ if (b.y1 > b.y4)
+ minby = b.y4, maxby = b.y1;
+ else
+ minby = b.y1, maxby = b.y4;
+
+ if (b.y3 < minby)
+ minby = b.y3;
+ else if (b.y3 > maxby)
+ maxby = b.y3;
+
+ if (b.y2 < minby)
+ minby = b.y2;
+ else if (b.y2 > maxby)
+ maxby = b.y2;
+
+ // Test bounding box of b against bounding box of a
+ if ((minax > maxbx) || (minay > maxby) // Not >= : need boundary case
+ || (minbx > maxax) || (minby > maxay))
+ return 0; // they don't intersect
+ else
+ return 1; // they intersect
+}
+#endif
+
+
+#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
+
+static bool RecursivelyIntersect(const QBezier &a, qreal t0, qreal t1, int deptha,
+ const QBezier &b, qreal u0, qreal u1, int depthb,
+ QVector<QPair<qreal, qreal> > *t)
+{
+#ifdef QDEBUG_BEZIER
+ static int I = 0;
+ int currentD = I;
+ fprintf(stderr, "%d) t0 = %lf, t1 = %lf, deptha = %d\n"
+ "u0 = %lf, u1 = %lf, depthb = %d\n", I++, t0, t1, deptha,
+ u0, u1, depthb);
+#endif
+ if (deptha > 0) {
+ QBezier A[2];
+ a.split(&A[0], &A[1]);
+ qreal tmid = (t0+t1)*0.5;
+ //qDebug()<<"\t1)"<<A[0];
+ //qDebug()<<"\t2)"<<A[1];
+ deptha--;
+ if (depthb > 0) {
+ QBezier B[2];
+ b.split(&B[0], &B[1]);
+ //qDebug()<<"\t3)"<<B[0];
+ //qDebug()<<"\t4)"<<B[1];
+ qreal umid = (u0+u1)*0.5;
+ depthb--;
+ if (IntersectBB(A[0], B[0])) {
+ //fprintf(stderr, "\t 1 from %d\n", currentD);
+ if (RecursivelyIntersect(A[0], t0, tmid, deptha,
+ B[0], u0, umid, depthb,
+ t) && !t)
+ return true;
+ }
+ if (IntersectBB(A[1], B[0])) {
+ //fprintf(stderr, "\t 2 from %d\n", currentD);
+ if (RecursivelyIntersect(A[1], tmid, t1, deptha,
+ B[0], u0, umid, depthb,
+ t) && !t)
+ return true;
+ }
+ if (IntersectBB(A[0], B[1])) {
+ //fprintf(stderr, "\t 3 from %d\n", currentD);
+ if (RecursivelyIntersect(A[0], t0, tmid, deptha,
+ B[1], umid, u1, depthb,
+ t) && !t)
+ return true;
+ }
+ if (IntersectBB(A[1], B[1])) {
+ //fprintf(stderr, "\t 4 from %d\n", currentD);
+ if (RecursivelyIntersect(A[1], tmid, t1, deptha,
+ B[1], umid, u1, depthb,
+ t) && !t)
+ return true;
+ }
+ return t ? !t->isEmpty() : false;
+ } else {
+ if (IntersectBB(A[0], b)) {
+ //fprintf(stderr, "\t 5 from %d\n", currentD);
+ if (RecursivelyIntersect(A[0], t0, tmid, deptha,
+ b, u0, u1, depthb,
+ t) && !t)
+ return true;
+ }
+ if (IntersectBB(A[1], b)) {
+ //fprintf(stderr, "\t 6 from %d\n", currentD);
+ if (RecursivelyIntersect(A[1], tmid, t1, deptha,
+ b, u0, u1, depthb,
+ t) && !t)
+ return true;
+ }
+ return t ? !t->isEmpty() : false;
+ }
+ } else {
+ if (depthb > 0) {
+ QBezier B[2];
+ b.split(&B[0], &B[1]);
+ qreal umid = (u0 + u1)*0.5;
+ depthb--;
+ if (IntersectBB(a, B[0])) {
+ //fprintf(stderr, "\t 7 from %d\n", currentD);
+ if (RecursivelyIntersect(a, t0, t1, deptha,
+ B[0], u0, umid, depthb,
+ t) && !t)
+ return true;
+ }
+ if (IntersectBB(a, B[1])) {
+ //fprintf(stderr, "\t 8 from %d\n", currentD);
+ if (RecursivelyIntersect(a, t0, t1, deptha,
+ B[1], umid, u1, depthb,
+ t) && !t)
+ return true;
+ }
+ return t ? !t->isEmpty() : false;
+ }
+ else {
+ // Both segments are fully subdivided; now do line segments
+ qreal xlk = a.x4 - a.x1;
+ qreal ylk = a.y4 - a.y1;
+ qreal xnm = b.x4 - b.x1;
+ qreal ynm = b.y4 - b.y1;
+ qreal xmk = b.x1 - a.x1;
+ qreal ymk = b.y1 - a.y1;
+ qreal det = xnm * ylk - ynm * xlk;
+ if (1.0 + det == 1.0) {
+ return false;
+ } else {
+ qreal detinv = 1.0 / det;
+ qreal rs = (xnm * ymk - ynm *xmk) * detinv;
+ qreal rt = (xlk * ymk - ylk * xmk) * detinv;
+ if ((rs < 0.0) || (rs > 1.0) || (rt < 0.0) || (rt > 1.0))
+ return false;
+
+ if (t) {
+ const qreal alpha_a = t0 + rs * (t1 - t0);
+ const qreal alpha_b = u0 + rt * (u1 - u0);
+
+ *t << qMakePair(alpha_a, alpha_b);
+ }
+
+ return true;
+ }
+ }
+ }
+}
+
+QVector< QPair<qreal, qreal> > QBezier::findIntersections(const QBezier &a, const QBezier &b)
+{
+ QVector< QPair<qreal, qreal> > v(2);
+ findIntersections(a, b, &v);
+ return v;
+}
+
+bool QBezier::findIntersections(const QBezier &a, const QBezier &b,
+ QVector<QPair<qreal, qreal> > *t)
+{
+ if (IntersectBB(a, b)) {
+ QPointF la1(fabs((a.x3 - a.x2) - (a.x2 - a.x1)),
+ fabs((a.y3 - a.y2) - (a.y2 - a.y1)));
+ QPointF la2(fabs((a.x4 - a.x3) - (a.x3 - a.x2)),
+ fabs((a.y4 - a.y3) - (a.y3 - a.y2)));
+ QPointF la;
+ if (la1.x() > la2.x()) la.setX(la1.x()); else la.setX(la2.x());
+ if (la1.y() > la2.y()) la.setY(la1.y()); else la.setY(la2.y());
+ QPointF lb1(fabs((b.x3 - b.x2) - (b.x2 - b.x1)),
+ fabs((b.y3 - b.y2) - (b.y2 - b.y1)));
+ QPointF lb2(fabs((b.x4 - b.x3) - (b.x3 - b.x2)),
+ fabs((b.y4 - b.y3) - (b.y3 - b.y2)));
+ QPointF lb;
+ if (lb1.x() > lb2.x()) lb.setX(lb1.x()); else lb.setX(lb2.x());
+ if (lb1.y() > lb2.y()) lb.setY(lb1.y()); else lb.setY(lb2.y());
+ qreal l0;
+ if (la.x() > la.y())
+ l0 = la.x();
+ else
+ l0 = la.y();
+ int ra;
+ if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0)
+ ra = 0;
+ else
+ ra = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0));
+ if (lb.x() > lb.y())
+ l0 = lb.x();
+ else
+ l0 = lb.y();
+ int rb;
+ if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0)
+ rb = 0;
+ else
+ rb = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0));
+
+ // if qreal is float then halve the number of subdivisions
+ if (sizeof(qreal) == 4) {
+ ra /= 2;
+ rb /= 2;
+ }
+
+ return RecursivelyIntersect(a, 0., 1., ra, b, 0., 1., rb, t);
+ }
+
+ //Don't sort here because it breaks the orders of corresponding
+ // intersections points. this way t's at the same locations correspond
+ // to the same intersection point.
+ //qSort(parameters[0].begin(), parameters[0].end(), qLess<qreal>());
+ //qSort(parameters[1].begin(), parameters[1].end(), qLess<qreal>());
+
+ return false;
+}
+
+static inline void splitBezierAt(const QBezier &bez, qreal t,
+ QBezier *left, QBezier *right)
+{
+ left->x1 = bez.x1;
+ left->y1 = bez.y1;
+
+ left->x2 = bez.x1 + t * ( bez.x2 - bez.x1 );
+ left->y2 = bez.y1 + t * ( bez.y2 - bez.y1 );
+
+ left->x3 = bez.x2 + t * ( bez.x3 - bez.x2 ); // temporary holding spot
+ left->y3 = bez.y2 + t * ( bez.y3 - bez.y2 ); // temporary holding spot
+
+ right->x3 = bez.x3 + t * ( bez.x4 - bez.x3 );
+ right->y3 = bez.y3 + t * ( bez.y4 - bez.y3 );
+
+ right->x2 = left->x3 + t * ( right->x3 - left->x3);
+ right->y2 = left->y3 + t * ( right->y3 - left->y3);
+
+ left->x3 = left->x2 + t * ( left->x3 - left->x2 );
+ left->y3 = left->y2 + t * ( left->y3 - left->y2 );
+
+ left->x4 = right->x1 = left->x3 + t * (right->x2 - left->x3);
+ left->y4 = right->y1 = left->y3 + t * (right->y2 - left->y3);
+
+ right->x4 = bez.x4;
+ right->y4 = bez.y4;
+}
+
+QVector< QList<QBezier> > QBezier::splitAtIntersections(QBezier &b)
+{
+ QVector< QList<QBezier> > curves(2);
+
+ QVector< QPair<qreal, qreal> > allInters = findIntersections(*this, b);
+
+ QList<qreal> inters1;
+ QList<qreal> inters2;
+
+ for (int i = 0; i < allInters.size(); ++i) {
+ inters1 << allInters[i].first;
+ inters2 << allInters[i].second;
+ }
+
+ qSort(inters1.begin(), inters1.end(), qLess<qreal>());
+ qSort(inters2.begin(), inters2.end(), qLess<qreal>());
+
+ Q_ASSERT(inters1.count() == inters2.count());
+
+ int i;
+ for (i = 0; i < inters1.count(); ++i) {
+ qreal t1 = inters1.at(i);
+ qreal t2 = inters2.at(i);
+
+ QBezier curve1, curve2;
+ parameterSplitLeft(t1, &curve1);
+ b.parameterSplitLeft(t2, &curve2);
+ curves[0].append(curve1);
+ curves[0].append(curve2);
+ }
+ curves[0].append(*this);
+ curves[1].append(b);
+
+ return curves;
+}
+
+qreal QBezier::length(qreal error) const
+{
+ qreal length = 0.0;
+
+ addIfClose(&length, error);
+
+ return length;
+}
+
+void QBezier::addIfClose(qreal *length, qreal error) const
+{
+ QBezier left, right; /* bez poly splits */
+
+ qreal len = 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) {
+ split(&left, &right); /* split in two */
+ left.addIfClose(length, error); /* try left side */
+ right.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 = 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) > 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;
+
+ qreal reciprocal = b * b - 4 * a * c;
+
+ QList<qreal> result;
+
+ if (qFuzzyCompare(reciprocal + 1, 1)) {
+ t0 = -b / (2 * a);
+ return 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 = 1.0;
+ const qreal error = (qreal)0.01;
+ if (l > len || qFuzzyCompare(l, len))
+ return t;
+
+ t *= 0.5;
+ //int iters = 0;
+ //qDebug()<<"LEN is "<<l<<len;
+ qreal lastBigger = 1.;
+ 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)*.5;
+ } else {
+ lastBigger = t;
+ t -= t*.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;
+}
+
+
+static inline void bindInflectionPoint(const QBezier &bez, const qreal t,
+ qreal *tMinus , qreal *tPlus)
+{
+ if (t <= 0) {
+ *tMinus = *tPlus = -1;
+ return;
+ } else if (t >= 1) {
+ *tMinus = *tPlus = 2;
+ return;
+ }
+
+ QBezier left, right;
+ splitBezierAt(bez, t, &left, &right);
+
+ qreal ax = -right.x1 + 3*right.x2 - 3*right.x3 + right.x4;
+ qreal ay = -right.y1 + 3*right.y2 - 3*right.y3 + right.y4;
+ qreal ex = 3 * (right.x2 - right.x3);
+ qreal ey = 3 * (right.y2 - right.y3);
+
+ qreal s4 = qAbs(6 * (ey * ax - ex * ay) / qSqrt(ex * ex + ey * ey)) + 0.00001f;
+ qreal tf = pow(qreal(9 * flatness / s4), qreal(1./3.));
+ *tMinus = t - (1 - t) * tf;
+ *tPlus = t + (1 - t) * tf;
+}
+
+void QBezier::addToPolygonIterative(QPolygonF *p) const
+{
+ qreal t1, t2, tcusp;
+ qreal t1min, t1plus, t2min, t2plus;
+
+ qreal ax = -x1 + 3*x2 - 3*x3 + x4;
+ qreal ay = -y1 + 3*y2 - 3*y3 + y4;
+ qreal bx = 3*x1 - 6*x2 + 3*x3;
+ qreal by = 3*y1 - 6*y2 + 3*y3;
+ qreal cx = -3*x1 + 3*x2;
+ qreal cy = -3*y1 + 2*y2;
+
+ if (findInflections(6 * (ay * bx - ax * by),
+ 6 * (ay * cx - ax * cy),
+ 2 * (by * cx - bx * cy),
+ &t1, &t2, &tcusp)) {
+ bindInflectionPoint(*this, t1, &t1min, &t1plus);
+ bindInflectionPoint(*this, t2, &t2min, &t2plus);
+
+ QBezier tmpBez = *this;
+ QBezier left, right, bez1, bez2, bez3;
+ if (t1min > 0) {
+ if (t1min >= 1) {
+ flattenBezierWithoutInflections(tmpBez, p);
+ } else {
+ splitBezierAt(tmpBez, t1min, &left, &right);
+ flattenBezierWithoutInflections(left, p);
+ p->append(tmpBez.pointAt(t1min));
+
+ if (t2min < t1plus) {
+ if (tcusp < 1) {
+ p->append(tmpBez.pointAt(tcusp));
+ }
+ if (t2plus < 1) {
+ splitBezierAt(tmpBez, t2plus, &left, &right);
+ flattenBezierWithoutInflections(right, p);
+ }
+ } else if (t1plus < 1) {
+ if (t2min < 1) {
+ splitBezierAt(tmpBez, t2min, &bez3, &right);
+ splitBezierAt(bez3, t1plus, &left, &bez2);
+
+ flattenBezierWithoutInflections(bez2, p);
+ p->append(tmpBez.pointAt(t2min));
+
+ if (t2plus < 1) {
+ splitBezierAt(tmpBez, t2plus, &left, &bez2);
+ flattenBezierWithoutInflections(bez2, p);
+ }
+ } else {
+ splitBezierAt(tmpBez, t1plus, &left, &bez2);
+ flattenBezierWithoutInflections(bez2, p);
+ }
+ }
+ }
+ } else if (t1plus > 0) {
+ p->append(QPointF(x1, y1));
+ if (t2min < t1plus) {
+ if (tcusp < 1) {
+ p->append(tmpBez.pointAt(tcusp));
+ }
+ if (t2plus < 1) {
+ splitBezierAt(tmpBez, t2plus, &left, &bez2);
+ flattenBezierWithoutInflections(bez2, p);
+ }
+ } else if (t1plus < 1) {
+ if (t2min < 1) {
+ splitBezierAt(tmpBez, t2min, &bez3, &right);
+ splitBezierAt(bez3, t1plus, &left, &bez2);
+
+ flattenBezierWithoutInflections(bez2, p);
+
+ p->append(tmpBez.pointAt(t2min));
+ if (t2plus < 1) {
+ splitBezierAt(tmpBez, t2plus, &left, &bez2);
+ flattenBezierWithoutInflections(bez2, p);
+ }
+ } else {
+ splitBezierAt(tmpBez, t1plus, &left, &bez2);
+ flattenBezierWithoutInflections(bez2, p);
+ }
+ }
+ } else if (t2min > 0) {
+ if (t2min < 1) {
+ splitBezierAt(tmpBez, t2min, &bez1, &right);
+ flattenBezierWithoutInflections(bez1, p);
+ p->append(tmpBez.pointAt(t2min));
+
+ if (t2plus < 1) {
+ splitBezierAt(tmpBez, t2plus, &left, &bez2);
+ flattenBezierWithoutInflections(bez2, p);
+ }
+ } else {
+ //### in here we should check whether the area of the
+ // triangle formed between pt1/pt2/pt3 is smaller
+ // or equal to 0 and then do iterative flattening
+ // if not we should fallback and do the recursive
+ // flattening.
+ flattenBezierWithoutInflections(tmpBez, p);
+ }
+ } else if (t2plus > 0) {
+ p->append(QPointF(x1, y1));
+ if (t2plus < 1) {
+ splitBezierAt(tmpBez, t2plus, &left, &bez2);
+ flattenBezierWithoutInflections(bez2, p);
+ }
+ } else {
+ flattenBezierWithoutInflections(tmpBez, p);
+ }
+ } else {
+ QBezier bez = *this;
+ flattenBezierWithoutInflections(bez, p);
+ }
+
+ p->append(QPointF(x4, y4));
+}
+
+QT_END_NAMESPACE