1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qbezier_p.h"

    43 #include <qdebug.h>

    44 #include <qline.h>

    45 #include <qpolygon.h>

    46 #include <qvector.h>

    47 #include <qlist.h>

    48 #include <qmath.h>

    49 

    50 #include <private/qnumeric_p.h>

    51 #include <private/qmath_p.h>

    52 

    53 QT_BEGIN_NAMESPACE

    54 

    55 //#define QDEBUG_BEZIER

    56 

    57 #ifdef FLOAT_ACCURACY

    58 #define INV_EPS (1L<<23)

    59 #else

    60 /* The value of 1.0 / (1L<<14) is enough for most applications */

    61 #define INV_EPS (1L<<14)

    62 #endif

    63 

    64 #ifndef M_SQRT2

    65 #define M_SQRT2	1.41421356237309504880

    66 #endif

    67 

    68 #define log2(x) (qLn(x)/qLn(2.))

    69 

    70 static inline qreal log4(qreal x)

    71 {

    72     return qreal(0.5) * log2(x);

    73 }

    74 

    75 /*!

    76   \internal

    77 */

    78 QBezier QBezier::fromPoints(const QPointF &p1, const QPointF &p2,

    79                             const QPointF &p3, const QPointF &p4)

    80 {

    81     QBezier b;

    82     b.x1 = p1.x();

    83     b.y1 = p1.y();

    84     b.x2 = p2.x();

    85     b.y2 = p2.y();

    86     b.x3 = p3.x();

    87     b.y3 = p3.y();

    88     b.x4 = p4.x();

    89     b.y4 = p4.y();

    90     return b;

    91 }

    92 

    93 /*!

    94   \internal

    95 */

    96 QPolygonF QBezier::toPolygon() const

    97 {

    98     // flattening is done by splitting the bezier until we can replace the segment by a straight

    99     // line. We split further until the control points are close enough to the line connecting the

   100     // boundary points.

   101     //

   102     // the Distance of a point p from a line given by the points (a,b) is given by:

   103     //

   104     // d = abs( (bx - ax)(ay - py) - (by - ay)(ax - px) ) / line_length

   105     //

   106     // We can stop splitting if both control points are close enough to the line.

   107     // To make the algorithm faster we use the manhattan length of the line.

   108 

   109     QPolygonF polygon;

   110     polygon.append(QPointF(x1, y1));

   111     addToPolygon(&polygon);

   112     return polygon;

   113 }

   114 

   115 //0.5 is really low

   116 static const qreal flatness = 0.5;

   117 

   118 //based on "Fast, precise flattening of cubic Bezier path and offset curves"

   119 //      by T. F. Hain, A. L. Ahmad, S. V. R. Racherla and D. D. Langan

   120 static inline void flattenBezierWithoutInflections(QBezier &bez,

   121                                                    QPolygonF *&p)

   122 {

   123     QBezier left;

   124 

   125     while (1) {

   126         qreal dx = bez.x2 - bez.x1;

   127         qreal dy = bez.y2 - bez.y1;

   128 

   129         qreal normalized = qSqrt(dx * dx + dy * dy);

   130         if (qFuzzyIsNull(normalized))

   131            break;

   132 

   133         qreal d = qAbs(dx * (bez.y3 - bez.y2) - dy * (bez.x3 - bez.x2));

   134 

   135         qreal t = qSqrt(4. / 3. * normalized * flatness / d);

   136         if (t > 1 || qFuzzyIsNull(t - (qreal)1.))

   137             break;

   138         bez.parameterSplitLeft(t, &left);

   139         p->append(bez.pt1());

   140     }

   141 }

   142 

   143 

   144 static inline int quadraticRoots(qreal a, qreal b, qreal c,

   145                                  qreal *x1, qreal *x2)

   146 {

   147     if (qFuzzyIsNull(a)) {

   148         if (qFuzzyIsNull(b))

   149             return 0;

   150         *x1 = *x2 = (-c / b);

   151         return 1;

   152     } else {

   153         const qreal det = b * b - 4 * a * c;

   154         if (qFuzzyIsNull(det)) {

   155             *x1 = *x2 = -b / (2 * a);

   156             return 1;

   157         }

   158         if (det > 0) {

   159             if (qFuzzyIsNull(b)) {

   160                 *x2 = qSqrt(-c / a);

   161                 *x1 = -(*x2);

   162                 return 2;

   163             }

   164             const qreal stableA = b / (2 * a);

   165             const qreal stableB = c / (a * stableA * stableA);

   166             const qreal stableC = -1 - qSqrt(1 - stableB);

   167             *x2 = stableA * stableC;

   168             *x1 = (stableA * stableB) / stableC;

   169             return 2;

   170         } else

   171             return 0;

   172     }

   173 }

   174 

   175 static inline bool findInflections(qreal a, qreal b, qreal c,

   176                                    qreal *t1 , qreal *t2, qreal *tCups)

   177 {

   178     qreal r1 = 0, r2 = 0;

   179 

   180     short rootsCount = quadraticRoots(a, b, c, &r1, &r2);

   181 

   182     if (rootsCount >= 1) {

   183         if (r1 < r2) {

   184             *t1 = r1;

   185             *t2 = r2;

   186         } else {

   187             *t1 = r2;

   188             *t2 = r1;

   189         }

   190         if (!qFuzzyIsNull(a))

   191             *tCups = 0.5 * (-b / a);

   192         else

   193             *tCups = 2;

   194 

   195         return true;

   196     }

   197 

   198     return false;

   199 }

   200 

   201 

   202 void QBezier::addToPolygon(QPolygonF *polygon) const

   203 {

   204     QBezier beziers[32];

   205     beziers[0] = *this;

   206     QBezier *b = beziers;

   207 

   208     while (b >= beziers) {

   209         // check if we can pop the top bezier curve from the stack

   210         qreal y4y1 = b->y4 - b->y1;

   211         qreal x4x1 = b->x4 - b->x1;

   212         qreal l = qAbs(x4x1) + qAbs(y4y1);

   213         qreal d;

   214         if (l > 1.) {

   215             d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )

   216                 + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );

   217         } else {

   218             d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +

   219                 qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);

   220             l = 1.;

   221         }

   222         if (d < flatness*l || b == beziers + 31) {

   223             // good enough, we pop it off and add the endpoint

   224             polygon->append(QPointF(b->x4, b->y4));

   225             --b;

   226         } else {

   227             // split, second half of the polygon goes lower into the stack

   228             b->split(b+1, b);

   229             ++b;

   230         }

   231     }

   232 }

   233 

   234 void QBezier::addToPolygonMixed(QPolygonF *polygon) const

   235 {

   236     qreal ax = -x1 + 3*x2 - 3*x3 + x4;

   237     qreal ay = -y1 + 3*y2 - 3*y3 + y4;

   238     qreal bx = 3*x1 - 6*x2 + 3*x3;

   239     qreal by = 3*y1 - 6*y2 + 3*y3;

   240     qreal cx = -3*x1 + 3*x2;

   241     qreal cy = -3*y1 + 2*y2;

   242     qreal a = 6 * (ay * bx - ax * by);

   243     qreal b = 6 * (ay * cx - ax * cy);

   244     qreal c = 2 * (by * cx - bx * cy);

   245 

   246     if ((qFuzzyIsNull(a) && qFuzzyIsNull(b)) ||

   247         (b * b - 4 * a *c) < 0) {

   248         QBezier bez(*this);

   249         flattenBezierWithoutInflections(bez, polygon);

   250         polygon->append(QPointF(x4, y4));

   251     } else {

   252         QBezier beziers[32];

   253         beziers[0] = *this;

   254         QBezier *b = beziers;

   255 

   256         while (b >= beziers) {

   257             // check if we can pop the top bezier curve from the stack

   258             qreal y4y1 = b->y4 - b->y1;

   259             qreal x4x1 = b->x4 - b->x1;

   260             qreal l = qAbs(x4x1) + qAbs(y4y1);

   261             qreal d;

   262             if (l > 1.) {

   263                 d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )

   264                     + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );

   265             } else {

   266                 d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +

   267                     qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);

   268                 l = 1.;

   269             }

   270             if (d < .5*l || b == beziers + 31) {

   271                 // good enough, we pop it off and add the endpoint

   272                 polygon->append(QPointF(b->x4, b->y4));

   273                 --b;

   274             } else {

   275                 // split, second half of the polygon goes lower into the stack

   276                 b->split(b+1, b);

   277                 ++b;

   278             }

   279         }

   280     }

   281 }

   282 

   283 QRectF QBezier::bounds() const

   284 {

   285     qreal xmin = x1;

   286     qreal xmax = x1;

   287     if (x2 < xmin)

   288         xmin = x2;

   289     else if (x2 > xmax)

   290         xmax = x2;

   291     if (x3 < xmin)

   292         xmin = x3;

   293     else if (x3 > xmax)

   294         xmax = x3;

   295     if (x4 < xmin)

   296         xmin = x4;

   297     else if (x4 > xmax)

   298         xmax = x4;

   299 

   300     qreal ymin = y1;

   301     qreal ymax = y1;

   302     if (y2 < ymin)

   303         ymin = y2;

   304     else if (y2 > ymax)

   305         ymax = y2;

   306     if (y3 < ymin)

   307         ymin = y3;

   308     else if (y3 > ymax)

   309         ymax = y3;

   310     if (y4 < ymin)

   311         ymin = y4;

   312     else if (y4 > ymax)

   313         ymax = y4;

   314     return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);

   315 }

   316 

   317 

   318 enum ShiftResult {

   319     Ok,

   320     Discard,

   321     Split,

   322     Circle

   323 };

   324 

   325 static ShiftResult good_offset(const QBezier *b1, const QBezier *b2, qreal offset, qreal threshold)

   326 {

   327     const qreal o2 = offset*offset;

   328     const qreal max_dist_line = threshold*offset*offset;

   329     const qreal max_dist_normal = threshold*offset;

   330     const qreal spacing = 0.25;

   331     for (qreal i = spacing; i < 0.99; i += spacing) {

   332         QPointF p1 = b1->pointAt(i);

   333         QPointF p2 = b2->pointAt(i);

   334         qreal d = (p1.x() - p2.x())*(p1.x() - p2.x()) + (p1.y() - p2.y())*(p1.y() - p2.y());

   335         if (qAbs(d - o2) > max_dist_line)

   336             return Split;

   337 

   338         QPointF normalPoint = b1->normalVector(i);

   339         qreal l = qAbs(normalPoint.x()) + qAbs(normalPoint.y());

   340         if (l != 0.) {

   341             d = qAbs( normalPoint.x()*(p1.y() - p2.y()) - normalPoint.y()*(p1.x() - p2.x()) ) / l;

   342             if (d > max_dist_normal)

   343                 return Split;

   344         }

   345     }

   346     return Ok;

   347 }

   348 

   349 static inline QLineF qline_shifted(const QPointF &p1, const QPointF &p2, qreal offset)

   350 {

   351     QLineF l(p1, p2);

   352     QLineF ln = l.normalVector().unitVector();

   353     l.translate(ln.dx() * offset, ln.dy() * offset);

   354     return l;

   355 }

   356 

   357 static bool qbezier_is_line(QPointF *points, int pointCount)

   358 {

   359     Q_ASSERT(pointCount > 2);

   360 

   361     qreal dx13 = points[2].x() - points[0].x();

   362     qreal dy13 = points[2].y() - points[0].y();

   363 

   364     qreal dx12 = points[1].x() - points[0].x();

   365     qreal dy12 = points[1].y() - points[0].y();

   366 

   367     if (pointCount == 3) {

   368         return qFuzzyCompare(dx12 * dy13, dx13 * dy12);

   369     } else if (pointCount == 4) {

   370         qreal dx14 = points[3].x() - points[0].x();

   371         qreal dy14 = points[3].y() - points[0].y();

   372 

   373         return (qFuzzyCompare(dx12 * dy13, dx13 * dy12) && qFuzzyCompare(dx12 * dy14, dx14 * dy12));

   374     }

   375 

   376     return false;

   377 }

   378 

   379 static ShiftResult shift(const QBezier *orig, QBezier *shifted, qreal offset, qreal threshold)

   380 {

   381     int map[4];

   382     bool p1_p2_equal = (orig->x1 == orig->x2 && orig->y1 == orig->y2);

   383     bool p2_p3_equal = (orig->x2 == orig->x3 && orig->y2 == orig->y3);

   384     bool p3_p4_equal = (orig->x3 == orig->x4 && orig->y3 == orig->y4);

   385 

   386     QPointF points[4];

   387     int np = 0;

   388     points[np] = QPointF(orig->x1, orig->y1);

   389     map[0] = 0;

   390     ++np;

   391     if (!p1_p2_equal) {

   392         points[np] = QPointF(orig->x2, orig->y2);

   393         ++np;

   394     }

   395     map[1] = np - 1;

   396     if (!p2_p3_equal) {

   397         points[np] = QPointF(orig->x3, orig->y3);

   398         ++np;

   399     }

   400     map[2] = np - 1;

   401     if (!p3_p4_equal) {

   402         points[np] = QPointF(orig->x4, orig->y4);

   403         ++np;

   404     }

   405     map[3] = np - 1;

   406     if (np == 1)

   407         return Discard;

   408 

   409     // We need to specialcase lines of 3 or 4 points due to numerical

   410     // instability in intersections below

   411     if (np > 2 && qbezier_is_line(points, np)) {

   412         if (points[0] == points[np-1])

   413             return Discard;

   414 

   415         QLineF l = qline_shifted(points[0], points[np-1], offset);

   416         *shifted = QBezier::fromPoints(l.p1(), l.pointAt(qreal(0.33)), l.pointAt(qreal(0.66)), l.p2());

   417         return Ok;

   418     }

   419 

   420     QRectF b = orig->bounds();

   421     if (np == 4 && b.width() < .1*offset && b.height() < .1*offset) {

   422         qreal l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +

   423                   (orig->y1 - orig->y2)*(orig->y1 - orig->y1) *

   424                   (orig->x3 - orig->x4)*(orig->x3 - orig->x4) +

   425                   (orig->y3 - orig->y4)*(orig->y3 - orig->y4);

   426         qreal dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +

   427                     (orig->y1 - orig->y2)*(orig->y3 - orig->y4);

   428         if (dot < 0 && dot*dot < 0.8*l)

   429             // the points are close and reverse dirction. Approximate the whole

   430             // thing by a semi circle

   431             return Circle;

   432     }

   433 

   434     QPointF points_shifted[4];

   435 

   436     QLineF prev = QLineF(QPointF(), points[1] - points[0]);

   437     QPointF prev_normal = prev.normalVector().unitVector().p2();

   438 

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

   440 

   441     for (int i = 1; i < np - 1; ++i) {

   442         QLineF next = QLineF(QPointF(), points[i + 1] - points[i]);

   443         QPointF next_normal = next.normalVector().unitVector().p2();

   444 

   445         QPointF normal_sum = prev_normal + next_normal;

   446 

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

   448                   + prev_normal.y() * next_normal.y();

   449 

   450         if (qFuzzyIsNull(r)) {

   451             points_shifted[i] = points[i] + offset * prev_normal;

   452         } else {

   453             qreal k = offset / r;

   454             points_shifted[i] = points[i] + k * normal_sum;

   455         }

   456 

   457         prev_normal = next_normal;

   458     }

   459 

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

   461 

   462     *shifted = QBezier::fromPoints(points_shifted[map[0]], points_shifted[map[1]],

   463                                    points_shifted[map[2]], points_shifted[map[3]]);

   464 

   465     return good_offset(orig, shifted, offset, threshold);

   466 }

   467 

   468 // This value is used to determine the length of control point vectors

   469 // when approximating arc segments as curves. The factor is multiplied

   470 // with the radius of the circle.

   471 #define KAPPA 0.5522847498

   472 

   473 

   474 static bool addCircle(const QBezier *b, qreal offset, QBezier *o)

   475 {

   476     QPointF normals[3];

   477 

   478     normals[0] = QPointF(b->y2 - b->y1, b->x1 - b->x2);

   479     qreal dist = qSqrt(normals[0].x()*normals[0].x() + normals[0].y()*normals[0].y());

   480     if (qFuzzyIsNull(dist))

   481         return false;

   482     normals[0] /= dist;

   483     normals[2] = QPointF(b->y4 - b->y3, b->x3 - b->x4);

   484     dist = qSqrt(normals[2].x()*normals[2].x() + normals[2].y()*normals[2].y());

   485     if (qFuzzyIsNull(dist))

   486         return false;

   487     normals[2] /= dist;

   488 

   489     normals[1] = QPointF(b->x1 - b->x2 - b->x3 + b->x4, b->y1 - b->y2 - b->y3 + b->y4);

   490     normals[1] /= -1*qSqrt(normals[1].x()*normals[1].x() + normals[1].y()*normals[1].y());

   491 

   492     qreal angles[2];

   493     qreal sign = 1.;

   494     for (int i = 0; i < 2; ++i) {

   495         qreal cos_a = normals[i].x()*normals[i+1].x() + normals[i].y()*normals[i+1].y();

   496         if (cos_a > 1.)

   497             cos_a = 1.;

   498         if (cos_a < -1.)

   499             cos_a = -1;

   500         angles[i] = acos(cos_a)/Q_PI;

   501     }

   502 

   503     if (angles[0] + angles[1] > 1.) {

   504         // more than 180 degrees

   505         normals[1] = -normals[1];

   506         angles[0] = 1. - angles[0];

   507         angles[1] = 1. - angles[1];

   508         sign = -1.;

   509 

   510     }

   511 

   512     QPointF circle[3];

   513     circle[0] = QPointF(b->x1, b->y1) + normals[0]*offset;

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

   515     circle[2] = QPointF(b->x4, b->y4) + normals[2]*offset;

   516 

   517     for (int i = 0; i < 2; ++i) {

   518         qreal kappa = 2.*KAPPA * sign * offset * angles[i];

   519 

   520         o->x1 = circle[i].x();

   521         o->y1 = circle[i].y();

   522         o->x2 = circle[i].x() - normals[i].y()*kappa;

   523         o->y2 = circle[i].y() + normals[i].x()*kappa;

   524         o->x3 = circle[i+1].x() + normals[i+1].y()*kappa;

   525         o->y3 = circle[i+1].y() - normals[i+1].x()*kappa;

   526         o->x4 = circle[i+1].x();

   527         o->y4 = circle[i+1].y();

   528 

   529         ++o;

   530     }

   531     return true;

   532 }

   533 

   534 int QBezier::shifted(QBezier *curveSegments, int maxSegments, qreal offset, float threshold) const

   535 {

   536     Q_ASSERT(curveSegments);

   537     Q_ASSERT(maxSegments > 0);

   538 

   539     if (x1 == x2 && x1 == x3 && x1 == x4 &&

   540         y1 == y2 && y1 == y3 && y1 == y4)

   541         return 0;

   542 

   543     --maxSegments;

   544     QBezier beziers[10];

   545 redo:

   546     beziers[0] = *this;

   547     QBezier *b = beziers;

   548     QBezier *o = curveSegments;

   549 

   550     while (b >= beziers) {

   551         int stack_segments = b - beziers + 1;

   552         if ((stack_segments == 10) || (o - curveSegments == maxSegments - stack_segments)) {

   553             threshold *= 1.5;

   554             if (threshold > 2.)

   555                 goto give_up;

   556             goto redo;

   557         }

   558         ShiftResult res = shift(b, o, offset, threshold);

   559         if (res == Discard) {

   560             --b;

   561         } else if (res == Ok) {

   562             ++o;

   563             --b;

   564             continue;

   565         } else if (res == Circle && maxSegments - (o - curveSegments) >= 2) {

   566             // add semi circle

   567             if (addCircle(b, offset, o))

   568                 o += 2;

   569             --b;

   570         } else {

   571             b->split(b+1, b);

   572             ++b;

   573         }

   574     }

   575 

   576 give_up:

   577     while (b >= beziers) {

   578         ShiftResult res = shift(b, o, offset, threshold);

   579 

   580         // if res isn't Ok or Split then *o is undefined

   581         if (res == Ok || res == Split)

   582             ++o;

   583 

   584         --b;

   585     }

   586 

   587     Q_ASSERT(o - curveSegments <= maxSegments);

   588     return o - curveSegments;

   589 }

   590 

   591 #if 0

   592 static inline bool IntersectBB(const QBezier &a, const QBezier &b)

   593 {

   594     return a.bounds().intersects(b.bounds());

   595 }

   596 #else

   597 static int IntersectBB(const QBezier &a, const QBezier &b)

   598 {

   599     // Compute bounding box for a

   600     qreal minax, maxax, minay, maxay;

   601     if (a.x1 > a.x4)	 // These are the most likely to be extremal

   602 	minax = a.x4, maxax = a.x1;

   603     else

   604 	minax = a.x1, maxax = a.x4;

   605 

   606     if (a.x3 < minax)

   607 	minax = a.x3;

   608     else if (a.x3 > maxax)

   609 	maxax = a.x3;

   610 

   611     if (a.x2 < minax)

   612 	minax = a.x2;

   613     else if (a.x2 > maxax)

   614 	maxax = a.x2;

   615 

   616     if (a.y1 > a.y4)

   617 	minay = a.y4, maxay = a.y1;

   618     else

   619 	minay = a.y1, maxay = a.y4;

   620 

   621     if (a.y3 < minay)

   622 	minay = a.y3;

   623     else if (a.y3 > maxay)

   624 	maxay = a.y3;

   625 

   626     if (a.y2 < minay)

   627 	minay = a.y2;

   628     else if (a.y2 > maxay)

   629 	maxay = a.y2;

   630 

   631     // Compute bounding box for b

   632     qreal minbx, maxbx, minby, maxby;

   633     if (b.x1 > b.x4)

   634 	minbx = b.x4, maxbx = b.x1;

   635     else

   636 	minbx = b.x1, maxbx = b.x4;

   637 

   638     if (b.x3 < minbx)

   639 	minbx = b.x3;

   640     else if (b.x3 > maxbx)

   641 	maxbx = b.x3;

   642 

   643     if (b.x2 < minbx)

   644 	minbx = b.x2;

   645     else if (b.x2 > maxbx)

   646 	maxbx = b.x2;

   647 

   648     if (b.y1 > b.y4)

   649 	minby = b.y4, maxby = b.y1;

   650     else

   651 	minby = b.y1, maxby = b.y4;

   652 

   653     if (b.y3 < minby)

   654 	minby = b.y3;

   655     else if (b.y3 > maxby)

   656 	maxby = b.y3;

   657 

   658     if (b.y2 < minby)

   659 	minby = b.y2;

   660     else if (b.y2 > maxby)

   661 	maxby = b.y2;

   662 

   663     // Test bounding box of b against bounding box of a

   664     if ((minax > maxbx) || (minay > maxby)  // Not >= : need boundary case

   665 	|| (minbx > maxax) || (minby > maxay))

   666 	return 0; // they don't intersect

   667     else

   668 	return 1; // they intersect

   669 }

   670 #endif

   671 

   672 

   673 #ifdef QDEBUG_BEZIER

   674 static QDebug operator<<(QDebug dbg, const QBezier &bz)

   675 {

   676     dbg << '[' << bz.x1<< ", " << bz.y1 << "], "

   677         << '[' << bz.x2 <<", " << bz.y2 << "], "

   678         << '[' << bz.x3 <<", " << bz.y3 << "], "

   679         << '[' << bz.x4 <<", " << bz.y4 << ']';

   680     return dbg;

   681 }

   682 #endif

   683 

   684 static bool RecursivelyIntersect(const QBezier &a, qreal t0, qreal t1, int deptha,

   685                                  const QBezier &b, qreal u0, qreal u1, int depthb,

   686                                  QVector<QPair<qreal, qreal> > *t)

   687 {

   688 #ifdef QDEBUG_BEZIER

   689     static int I = 0;

   690     int currentD = I;

   691     fprintf(stderr, "%d) t0 = %lf, t1 = %lf, deptha = %d\n"

   692             "u0 = %lf, u1 = %lf, depthb = %d\n", I++, t0, t1, deptha,

   693             u0, u1, depthb);

   694 #endif

   695     if (deptha > 0) {

   696 	QBezier A[2];

   697         a.split(&A[0], &A[1]);

   698 	qreal tmid = (t0+t1)*0.5;

   699         //qDebug()<<"\t1)"<<A[0];

   700         //qDebug()<<"\t2)"<<A[1];

   701 	deptha--;

   702 	if (depthb > 0) {

   703 	    QBezier B[2];

   704             b.split(&B[0], &B[1]);

   705             //qDebug()<<"\t3)"<<B[0];

   706             //qDebug()<<"\t4)"<<B[1];

   707 	    qreal umid = (u0+u1)*0.5;

   708 	    depthb--;

   709 	    if (IntersectBB(A[0], B[0])) {

   710                 //fprintf(stderr, "\t 1 from %d\n", currentD);

   711 		if (RecursivelyIntersect(A[0], t0, tmid, deptha,

   712 				     B[0], u0, umid, depthb,

   713 				     t) && !t)

   714                     return true;

   715             }

   716 	    if (IntersectBB(A[1], B[0])) {

   717                 //fprintf(stderr, "\t 2 from %d\n", currentD);

   718 		if (RecursivelyIntersect(A[1], tmid, t1, deptha,

   719                                      B[0], u0, umid, depthb,

   720                                      t) && !t)

   721                     return true;

   722             }

   723 	    if (IntersectBB(A[0], B[1])) {

   724                 //fprintf(stderr, "\t 3 from %d\n", currentD);

   725 		if (RecursivelyIntersect(A[0], t0, tmid, deptha,

   726                                      B[1], umid, u1, depthb,

   727                                      t) && !t)

   728                     return true;

   729             }

   730 	    if (IntersectBB(A[1], B[1])) {

   731                 //fprintf(stderr, "\t 4 from %d\n", currentD);

   732 		if (RecursivelyIntersect(A[1], tmid, t1, deptha,

   733 				     B[1], umid, u1, depthb,

   734 				     t) && !t)

   735                     return true;

   736             }

   737             return t ? !t->isEmpty() : false;

   738         } else {

   739 	    if (IntersectBB(A[0], b)) {

   740                 //fprintf(stderr, "\t 5 from %d\n", currentD);

   741 		if (RecursivelyIntersect(A[0], t0, tmid, deptha,

   742 				     b, u0, u1, depthb,

   743 				     t) && !t)

   744                     return true;

   745             }

   746 	    if (IntersectBB(A[1], b)) {

   747                 //fprintf(stderr, "\t 6 from %d\n", currentD);

   748 		if (RecursivelyIntersect(A[1], tmid, t1, deptha,

   749                                      b, u0, u1, depthb,

   750                                      t) && !t)

   751                     return true;

   752             }

   753             return t ? !t->isEmpty() : false;

   754         }

   755     } else {

   756 	if (depthb > 0) {

   757 	    QBezier B[2];

   758             b.split(&B[0], &B[1]);

   759 	    qreal umid = (u0 + u1)*0.5;

   760 	    depthb--;

   761 	    if (IntersectBB(a, B[0])) {

   762                 //fprintf(stderr, "\t 7 from %d\n", currentD);

   763 		if (RecursivelyIntersect(a, t0, t1, deptha,

   764                                      B[0], u0, umid, depthb,

   765                                      t) && !t)

   766                     return true;

   767             }

   768 	    if (IntersectBB(a, B[1])) {

   769                 //fprintf(stderr, "\t 8 from %d\n", currentD);

   770 		if (RecursivelyIntersect(a, t0, t1, deptha,

   771                                      B[1], umid, u1, depthb,

   772                                      t) && !t)

   773                     return true;

   774             }

   775             return t ? !t->isEmpty() : false;

   776         }

   777 	else {

   778             // Both segments are fully subdivided; now do line segments

   779 	    qreal xlk = a.x4 - a.x1;

   780 	    qreal ylk = a.y4 - a.y1;

   781 	    qreal xnm = b.x4 - b.x1;

   782 	    qreal ynm = b.y4 - b.y1;

   783 	    qreal xmk = b.x1 - a.x1;

   784 	    qreal ymk = b.y1 - a.y1;

   785 	    qreal det = xnm * ylk - ynm * xlk;

   786 	    if (1.0 + det == 1.0) {

   787 		return false;

   788             } else {

   789                 qreal detinv = 1.0 / det;

   790                 qreal rs = (xnm * ymk - ynm *xmk) * detinv;

   791                 qreal rt = (xlk * ymk - ylk * xmk) * detinv;

   792                 if ((rs < 0.0) || (rs > 1.0) || (rt < 0.0) || (rt > 1.0))

   793                     return false;

   794 

   795                 if (t) {

   796                     const qreal alpha_a = t0 + rs * (t1 - t0);

   797                     const qreal alpha_b = u0 + rt * (u1 - u0);

   798 

   799                     *t << qMakePair(alpha_a, alpha_b);

   800                 }

   801 

   802                 return true;

   803             }

   804         }

   805     }

   806 }

   807 

   808 QVector< QPair<qreal, qreal> > QBezier::findIntersections(const QBezier &a, const QBezier &b)

   809 {

   810     QVector< QPair<qreal, qreal> > v(2);

   811     findIntersections(a, b, &v);

   812     return v;

   813 }

   814 

   815 bool QBezier::findIntersections(const QBezier &a, const QBezier &b,

   816                                 QVector<QPair<qreal, qreal> > *t)

   817 {

   818     if (IntersectBB(a, b)) {

   819         QPointF la1(fabs((a.x3 - a.x2) - (a.x2 - a.x1)),

   820                     fabs((a.y3 - a.y2) - (a.y2 - a.y1)));

   821 	QPointF la2(fabs((a.x4 - a.x3) - (a.x3 - a.x2)),

   822                     fabs((a.y4 - a.y3) - (a.y3 - a.y2)));

   823 	QPointF la;

   824 	if (la1.x() > la2.x()) la.setX(la1.x()); else la.setX(la2.x());

   825 	if (la1.y() > la2.y()) la.setY(la1.y()); else la.setY(la2.y());

   826 	QPointF lb1(fabs((b.x3 - b.x2) - (b.x2 - b.x1)),

   827                     fabs((b.y3 - b.y2) - (b.y2 - b.y1)));

   828 	QPointF lb2(fabs((b.x4 - b.x3) - (b.x3 - b.x2)),

   829                     fabs((b.y4 - b.y3) - (b.y3 - b.y2)));

   830 	QPointF lb;

   831 	if (lb1.x() > lb2.x()) lb.setX(lb1.x()); else lb.setX(lb2.x());

   832 	if (lb1.y() > lb2.y()) lb.setY(lb1.y()); else lb.setY(lb2.y());

   833 	qreal l0;

   834 	if (la.x() > la.y())

   835 	    l0 = la.x();

   836 	else

   837 	    l0 = la.y();

   838 	int ra;

   839 	if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0)

   840 	    ra = 0;

   841 	else

   842 	    ra = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0));

   843 	if (lb.x() > lb.y())

   844 	    l0 = lb.x();

   845 	else

   846 	    l0 = lb.y();

   847 	int rb;

   848 	if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0)

   849 	    rb = 0;

   850 	else

   851 	    rb = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0));

   852 

   853         // if qreal is float then halve the number of subdivisions

   854         if (sizeof(qreal) == 4) {

   855             ra /= 2;

   856             rb /= 2;

   857         }

   858 

   859 	return RecursivelyIntersect(a, 0., 1., ra, b, 0., 1., rb, t);

   860     }

   861 

   862     //Don't sort here because it breaks the orders of corresponding

   863     //  intersections points. this way t's at the same locations correspond

   864     //  to the same intersection point.

   865     //qSort(parameters[0].begin(), parameters[0].end(), qLess<qreal>());

   866     //qSort(parameters[1].begin(), parameters[1].end(), qLess<qreal>());

   867 

   868     return false;

   869 }

   870 

   871 static inline void splitBezierAt(const QBezier &bez, qreal t,

   872                                  QBezier *left, QBezier *right)

   873 {

   874     left->x1 = bez.x1;

   875     left->y1 = bez.y1;

   876 

   877     left->x2 = bez.x1 + t * ( bez.x2 - bez.x1 );

   878     left->y2 = bez.y1 + t * ( bez.y2 - bez.y1 );

   879 

   880     left->x3 = bez.x2 + t * ( bez.x3 - bez.x2 ); // temporary holding spot

   881     left->y3 = bez.y2 + t * ( bez.y3 - bez.y2 ); // temporary holding spot

   882 

   883     right->x3 = bez.x3 + t * ( bez.x4 - bez.x3 );

   884     right->y3 = bez.y3 + t * ( bez.y4 - bez.y3 );

   885 

   886     right->x2 = left->x3 + t * ( right->x3 - left->x3);

   887     right->y2 = left->y3 + t * ( right->y3 - left->y3);

   888 

   889     left->x3 = left->x2 + t * ( left->x3 - left->x2 );

   890     left->y3 = left->y2 + t * ( left->y3 - left->y2 );

   891 

   892     left->x4 = right->x1 = left->x3 + t * (right->x2 - left->x3);

   893     left->y4 = right->y1 = left->y3 + t * (right->y2 - left->y3);

   894 

   895     right->x4 = bez.x4;

   896     right->y4 = bez.y4;

   897 }

   898 

   899 QVector< QList<QBezier> > QBezier::splitAtIntersections(QBezier &b)

   900 {

   901     QVector< QList<QBezier> > curves(2);

   902 

   903     QVector< QPair<qreal, qreal> > allInters = findIntersections(*this, b);

   904 

   905     QList<qreal> inters1;

   906     QList<qreal> inters2;

   907 

   908     for (int i = 0; i < allInters.size(); ++i) {

   909         inters1 << allInters[i].first;

   910         inters2 << allInters[i].second;

   911     }

   912 

   913     qSort(inters1.begin(), inters1.end(), qLess<qreal>());

   914     qSort(inters2.begin(), inters2.end(), qLess<qreal>());

   915 

   916     Q_ASSERT(inters1.count() == inters2.count());

   917 

   918     int i;

   919     for (i = 0; i < inters1.count(); ++i) {

   920         qreal t1 = inters1.at(i);

   921         qreal t2 = inters2.at(i);

   922 

   923         QBezier curve1, curve2;

   924         parameterSplitLeft(t1, &curve1);

   925 	b.parameterSplitLeft(t2, &curve2);

   926         curves[0].append(curve1);

   927         curves[0].append(curve2);

   928     }

   929     curves[0].append(*this);

   930     curves[1].append(b);

   931 

   932     return curves;

   933 }

   934 

   935 qreal QBezier::length(qreal error) const

   936 {

   937     qreal length = 0.0;

   938 

   939     addIfClose(&length, error);

   940 

   941     return length;

   942 }

   943 

   944 void QBezier::addIfClose(qreal *length, qreal error) const

   945 {

   946     QBezier left, right;     /* bez poly splits */

   947 

   948     qreal len = 0.0;        /* arc length */

   949     qreal chord;            /* chord length */

   950 

   951     len = len + QLineF(QPointF(x1, y1),QPointF(x2, y2)).length();

   952     len = len + QLineF(QPointF(x2, y2),QPointF(x3, y3)).length();

   953     len = len + QLineF(QPointF(x3, y3),QPointF(x4, y4)).length();

   954 

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

   956 

   957     if((len-chord) > error) {

   958         split(&left, &right);                 /* split in two */

   959         left.addIfClose(length, error);       /* try left side */

   960         right.addIfClose(length, error);      /* try right side */

   961         return;

   962     }

   963 

   964     *length = *length + len;

   965 

   966     return;

   967 }

   968 

   969 qreal QBezier::tForY(qreal t0, qreal t1, qreal y) const

   970 {

   971     qreal py0 = pointAt(t0).y();

   972     qreal py1 = pointAt(t1).y();

   973 

   974     if (py0 > py1) {

   975         qSwap(py0, py1);

   976         qSwap(t0, t1);

   977     }

   978 

   979     Q_ASSERT(py0 <= py1);

   980 

   981     if (py0 >= y)

   982         return t0;

   983     else if (py1 <= y)

   984         return t1;

   985 

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

   987 

   988     qreal lt = t0;

   989     qreal dt;

   990     do {

   991         qreal t = 0.5 * (t0 + t1);

   992 

   993         qreal a, b, c, d;

   994         QBezier::coefficients(t, a, b, c, d);

   995         qreal yt = a * y1 + b * y2 + c * y3 + d * y4;

   996 

   997         if (yt < y) {

   998             t0 = t;

   999             py0 = yt;

  1000         } else {

  1001             t1 = t;

  1002             py1 = yt;

  1003         }

  1004         dt = lt - t;

  1005         lt = t;

  1006     } while (qAbs(dt) > 1e-7);

  1007 

  1008     return t0;

  1009 }

  1010 

  1011 int QBezier::stationaryYPoints(qreal &t0, qreal &t1) const

  1012 {

  1013     // y(t) = (1 - t)^3 * y1 + 3 * (1 - t)^2 * t * y2 + 3 * (1 - t) * t^2 * y3 + t^3 * y4

  1014     // y'(t) = 3 * (-(1-2t+t^2) * y1 + (1 - 4 * t + 3 * t^2) * y2 + (2 * t - 3 * t^2) * y3 + t^2 * y4)

  1015     // y'(t) = 3 * ((-y1 + 3 * y2 - 3 * y3 + y4)t^2 + (2 * y1 - 4 * y2 + 2 * y3)t + (-y1 + y2))

  1016 

  1017     const qreal a = -y1 + 3 * y2 - 3 * y3 + y4;

  1018     const qreal b = 2 * y1 - 4 * y2 + 2 * y3;

  1019     const qreal c = -y1 + y2;

  1020 

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

  1022 

  1023     QList<qreal> result;

  1024 

  1025     if (qFuzzyIsNull(reciprocal)) {

  1026         t0 = -b / (2 * a);

  1027         return 1;

  1028     } else if (reciprocal > 0) {

  1029         qreal temp = qSqrt(reciprocal);

  1030 

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

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

  1033 

  1034         if (t1 < t0)

  1035             qSwap(t0, t1);

  1036 

  1037         int count = 0;

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

  1039 

  1040         if (t0 > 0 && t0 < 1)

  1041             t[count++] = t0;

  1042         if (t1 > 0 && t1 < 1)

  1043             t[count++] = t1;

  1044 

  1045         t0 = t[0];

  1046         t1 = t[1];

  1047 

  1048         return count;

  1049     }

  1050 

  1051     return 0;

  1052 }

  1053 

  1054 qreal QBezier::tAtLength(qreal l) const

  1055 {

  1056     qreal len = length();

  1057     qreal t   = 1.0;

  1058     const qreal error = (qreal)0.01;

  1059     if (l > len || qFuzzyCompare(l, len))

  1060         return t;

  1061 

  1062     t *= 0.5;

  1063     //int iters = 0;

  1064     //qDebug()<<"LEN is "<<l<<len;

  1065     qreal lastBigger = 1.;

  1066     while (1) {

  1067         //qDebug()<<"\tt is "<<t;

  1068         QBezier right = *this;

  1069         QBezier left;

  1070         right.parameterSplitLeft(t, &left);

  1071         qreal lLen = left.length();

  1072         if (qAbs(lLen - l) < error)

  1073             break;

  1074 

  1075         if (lLen < l) {

  1076             t += (lastBigger - t)*.5;

  1077         } else {

  1078             lastBigger = t;

  1079             t -= t*.5;

  1080         }

  1081         //++iters;

  1082     }

  1083     //qDebug()<<"number of iters is "<<iters;

  1084     return t;

  1085 }

  1086 

  1087 QBezier QBezier::bezierOnInterval(qreal t0, qreal t1) const

  1088 {

  1089     if (t0 == 0 && t1 == 1)

  1090         return *this;

  1091 

  1092     QBezier bezier = *this;

  1093 

  1094     QBezier result;

  1095     bezier.parameterSplitLeft(t0, &result);

  1096     qreal trueT = (t1-t0)/(1-t0);

  1097     bezier.parameterSplitLeft(trueT, &result);

  1098 

  1099     return result;

  1100 }

  1101 

  1102 

  1103 static inline void bindInflectionPoint(const QBezier &bez, const qreal t,

  1104                                        qreal *tMinus , qreal *tPlus)

  1105 {

  1106     if (t <= 0) {

  1107         *tMinus = *tPlus = -1;

  1108         return;

  1109     } else if (t >= 1) {

  1110         *tMinus = *tPlus = 2;

  1111         return;

  1112     }

  1113 

  1114     QBezier left, right;

  1115     splitBezierAt(bez, t, &left, &right);

  1116 

  1117     qreal ax = -right.x1 + 3*right.x2 - 3*right.x3 + right.x4;

  1118     qreal ay = -right.y1 + 3*right.y2 - 3*right.y3 + right.y4;

  1119     qreal ex = 3 * (right.x2 - right.x3);

  1120     qreal ey = 3 * (right.y2 - right.y3);

  1121 

  1122     qreal s4 = qAbs(6 * (ey * ax - ex * ay) / qSqrt(ex * ex + ey * ey)) + 0.00001f;

  1123     qreal tf = pow(qreal(9 * flatness / s4), qreal(1./3.));

  1124     *tMinus = t - (1 - t) * tf;

  1125     *tPlus  = t + (1 - t) * tf;

  1126 }

  1127 

  1128 void QBezier::addToPolygonIterative(QPolygonF *p) const

  1129 {

  1130     qreal t1, t2, tcusp;

  1131     qreal t1min, t1plus, t2min, t2plus;

  1132 

  1133     qreal ax = -x1 + 3*x2 - 3*x3 + x4;

  1134     qreal ay = -y1 + 3*y2 - 3*y3 + y4;