diff options
Diffstat (limited to 'src/gui/painting/qbezier.cpp')
| -rw-r--r-- | src/gui/painting/qbezier.cpp | 1245 |
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 |