src/gui/painting/qbezier.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 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 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  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 /*!
  69   \internal
  70 */
  71 QBezier QBezier::fromPoints(const QPointF &p1, const QPointF &p2,
  72                             const QPointF &p3, const QPointF &p4)
  73 {
  74     QBezier b;
  75     b.x1 = p1.x();
  76     b.y1 = p1.y();
  77     b.x2 = p2.x();
  78     b.y2 = p2.y();
  79     b.x3 = p3.x();
  80     b.y3 = p3.y();
  81     b.x4 = p4.x();
  82     b.y4 = p4.y();
  83     return b;
  84 }
  85
  86 /*!
  87   \internal
  88 */
  89 QPolygonF QBezier::toPolygon(qreal bezier_flattening_threshold) const
  90 {
  91     // flattening is done by splitting the bezier until we can replace the segment by a straight
  92     // line. We split further until the control points are close enough to the line connecting the
  93     // boundary points.
  94     //
  95     // the Distance of a point p from a line given by the points (a,b) is given by:
  96     //
  97     // d = abs( (bx - ax)(ay - py) - (by - ay)(ax - px) ) / line_length
  98     //
  99     // We can stop splitting if both control points are close enough to the line.
 100     // To make the algorithm faster we use the manhattan length of the line.
 101
 102     QPolygonF polygon;
 103     polygon.append(QPointF(x1, y1));
 104     addToPolygon(&polygon, bezier_flattening_threshold);
 105     return polygon;
 106 }
 107
 108 QBezier QBezier::mapBy(const QTransform &transform) const
 109 {
 110     return QBezier::fromPoints(transform.map(pt1()), transform.map(pt2()), transform.map(pt3()), transform.map(pt4()));
 111 }
 112
 113 QBezier QBezier::getSubRange(qreal t0, qreal t1) const
 114 {
 115     QBezier result;
 116     QBezier temp;
 117
 118     // cut at t1
 119     if (qFuzzyIsNull(t1 - qreal(1.))) {
 120         result = *this;
 121     } else {
 122         temp = *this;
 123         temp.parameterSplitLeft(t1, &result);
 124     }
 125
 126     // cut at t0
 127     if (!qFuzzyIsNull(t0))
 128         result.parameterSplitLeft(t0 / t1, &temp);
 129
 130     return result;
 131 }
 132
 133 static inline int quadraticRoots(qreal a, qreal b, qreal c,
 134                                  qreal *x1, qreal *x2)
 135 {
 136     if (qFuzzyIsNull(a)) {
 137         if (qFuzzyIsNull(b))
 138             return 0;
 139         *x1 = *x2 = (-c / b);
 140         return 1;
 141     } else {
 142         const qreal det = b * b - 4 * a * c;
 143         if (qFuzzyIsNull(det)) {
 144             *x1 = *x2 = -b / (2 * a);
 145             return 1;
 146         }
 147         if (det > 0) {
 148             if (qFuzzyIsNull(b)) {
 149                 *x2 = qSqrt(-c / a);
 150                 *x1 = -(*x2);
 151                 return 2;
 152             }
 153             const qreal stableA = b / (2 * a);
 154             const qreal stableB = c / (a * stableA * stableA);
 155             const qreal stableC = -1 - qSqrt(1 - stableB);
 156             *x2 = stableA * stableC;
 157             *x1 = (stableA * stableB) / stableC;
 158             return 2;
 159         } else
 160             return 0;
 161     }
 162 }
 163
 164 static inline bool findInflections(qreal a, qreal b, qreal c,
 165                                    qreal *t1 , qreal *t2, qreal *tCups)
 166 {
 167     qreal r1 = 0, r2 = 0;
 168
 169     short rootsCount = quadraticRoots(a, b, c, &r1, &r2);
 170
 171     if (rootsCount >= 1) {
 172         if (r1 < r2) {
 173             *t1 = r1;
 174             *t2 = r2;
 175         } else {
 176             *t1 = r2;
 177             *t2 = r1;
 178         }
 179         if (!qFuzzyIsNull(a))
 180             *tCups = qreal(0.5) * (-b / a);
 181         else
 182             *tCups = 2;
 183
 184         return true;
 185     }
 186
 187     return false;
 188 }
 189
 190
 191 void QBezier::addToPolygon(QPolygonF *polygon, qreal bezier_flattening_threshold) const
 192 {
 193     QBezier beziers[32];
 194     beziers[0] = *this;
 195     QBezier *b = beziers;
 196
 197     while (b >= beziers) {
 198         // check if we can pop the top bezier curve from the stack
 199         qreal y4y1 = b->y4 - b->y1;
 200         qreal x4x1 = b->x4 - b->x1;
 201         qreal l = qAbs(x4x1) + qAbs(y4y1);
 202         qreal d;
 203         if (l > 1.) {
 204             d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )
 205                 + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );
 206         } else {
 207             d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
 208                 qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
 209             l = 1.;
 210         }
 211         if (d < bezier_flattening_threshold*l || b == beziers + 31) {
 212             // good enough, we pop it off and add the endpoint
 213             polygon->append(QPointF(b->x4, b->y4));
 214             --b;
 215         } else {
 216             // split, second half of the polygon goes lower into the stack
 217             b->split(b+1, b);
 218             ++b;
 219         }
 220     }
 221 }
 222
 223 QRectF QBezier::bounds() const
 224 {
 225     qreal xmin = x1;
 226     qreal xmax = x1;
 227     if (x2 < xmin)
 228         xmin = x2;
 229     else if (x2 > xmax)
 230         xmax = x2;
 231     if (x3 < xmin)
 232         xmin = x3;
 233     else if (x3 > xmax)
 234         xmax = x3;
 235     if (x4 < xmin)
 236         xmin = x4;
 237     else if (x4 > xmax)
 238         xmax = x4;
 239
 240     qreal ymin = y1;
 241     qreal ymax = y1;
 242     if (y2 < ymin)
 243         ymin = y2;
 244     else if (y2 > ymax)
 245         ymax = y2;
 246     if (y3 < ymin)
 247         ymin = y3;
 248     else if (y3 > ymax)
 249         ymax = y3;
 250     if (y4 < ymin)
 251         ymin = y4;
 252     else if (y4 > ymax)
 253         ymax = y4;
 254     return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
 255 }
 256
 257
 258 enum ShiftResult {
 259     Ok,
 260     Discard,
 261     Split,
 262     Circle
 263 };
 264
 265 static ShiftResult good_offset(const QBezier *b1, const QBezier *b2, qreal offset, qreal threshold)
 266 {
 267     const qreal o2 = offset*offset;
 268     const qreal max_dist_line = threshold*offset*offset;
 269     const qreal max_dist_normal = threshold*offset;
 270     const qreal spacing = qreal(0.25);
 271     for (qreal i = spacing; i < qreal(0.99); i += spacing) {
 272         QPointF p1 = b1->pointAt(i);
 273         QPointF p2 = b2->pointAt(i);
 274         qreal d = (p1.x() - p2.x())*(p1.x() - p2.x()) + (p1.y() - p2.y())*(p1.y() - p2.y());
 275         if (qAbs(d - o2) > max_dist_line)
 276             return Split;
 277
 278         QPointF normalPoint = b1->normalVector(i);
 279         qreal l = qAbs(normalPoint.x()) + qAbs(normalPoint.y());
 280         if (l != qreal(0.0)) {
 281             d = qAbs( normalPoint.x()*(p1.y() - p2.y()) - normalPoint.y()*(p1.x() - p2.x()) ) / l;
 282             if (d > max_dist_normal)
 283                 return Split;
 284         }
 285     }
 286     return Ok;
 287 }
 288
 289 static ShiftResult shift(const QBezier *orig, QBezier *shifted, qreal offset, qreal threshold)
 290 {
 291     int map[4];
 292     bool p1_p2_equal = (orig->x1 == orig->x2 && orig->y1 == orig->y2);
 293     bool p2_p3_equal = (orig->x2 == orig->x3 && orig->y2 == orig->y3);
 294     bool p3_p4_equal = (orig->x3 == orig->x4 && orig->y3 == orig->y4);
 295
 296     QPointF points[4];
 297     int np = 0;
 298     points[np] = QPointF(orig->x1, orig->y1);
 299     map[0] = 0;
 300     ++np;
 301     if (!p1_p2_equal) {
 302         points[np] = QPointF(orig->x2, orig->y2);
 303         ++np;
 304     }
 305     map[1] = np - 1;
 306     if (!p2_p3_equal) {
 307         points[np] = QPointF(orig->x3, orig->y3);
 308         ++np;
 309     }
 310     map[2] = np - 1;
 311     if (!p3_p4_equal) {
 312         points[np] = QPointF(orig->x4, orig->y4);
 313         ++np;
 314     }
 315     map[3] = np - 1;
 316     if (np == 1)
 317         return Discard;
 318
 319     QRectF b = orig->bounds();
 320     if (np == 4 && b.width() < .1*offset && b.height() < .1*offset) {
 321         qreal l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +
 322                   (orig->y1 - orig->y2)*(orig->y1 - orig->y1) *
 323                   (orig->x3 - orig->x4)*(orig->x3 - orig->x4) +
 324                   (orig->y3 - orig->y4)*(orig->y3 - orig->y4);
 325         qreal dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +
 326                     (orig->y1 - orig->y2)*(orig->y3 - orig->y4);
 327         if (dot < 0 && dot*dot < 0.8*l)
 328             // the points are close and reverse dirction. Approximate the whole
 329             // thing by a semi circle
 330             return Circle;
 331     }
 332
 333     QPointF points_shifted[4];
 334
 335     QLineF prev = QLineF(QPointF(), points[1] - points[0]);
 336     QPointF prev_normal = prev.normalVector().unitVector().p2();
 337
 338     points_shifted[0] = points[0] + offset * prev_normal;
 339
 340     for (int i = 1; i < np - 1; ++i) {
 341         QLineF next = QLineF(QPointF(), points[i + 1] - points[i]);
 342         QPointF next_normal = next.normalVector().unitVector().p2();
 343
 344         QPointF normal_sum = prev_normal + next_normal;
 345
 346         qreal r = qreal(1.0) + prev_normal.x() * next_normal.x()
 347                   + prev_normal.y() * next_normal.y();
 348
 349         if (qFuzzyIsNull(r)) {
 350             points_shifted[i] = points[i] + offset * prev_normal;
 351         } else {
 352             qreal k = offset / r;
 353             points_shifted[i] = points[i] + k * normal_sum;
 354         }
 355
 356         prev_normal = next_normal;
 357     }
 358
 359     points_shifted[np - 1] = points[np - 1] + offset * prev_normal;
 360
 361     *shifted = QBezier::fromPoints(points_shifted[map[0]], points_shifted[map[1]],
 362                                    points_shifted[map[2]], points_shifted[map[3]]);
 363
 364     return good_offset(orig, shifted, offset, threshold);
 365 }
 366
 367 // This value is used to determine the length of control point vectors
 368 // when approximating arc segments as curves. The factor is multiplied
 369 // with the radius of the circle.
 370 #define KAPPA qreal(0.5522847498)
 371
 372
 373 static bool addCircle(const QBezier *b, qreal offset, QBezier *o)
 374 {
 375     QPointF normals[3];
 376
 377     normals[0] = QPointF(b->y2 - b->y1, b->x1 - b->x2);
 378     qreal dist = qSqrt(normals[0].x()*normals[0].x() + normals[0].y()*normals[0].y());
 379     if (qFuzzyIsNull(dist))
 380         return false;
 381     normals[0] /= dist;
 382     normals[2] = QPointF(b->y4 - b->y3, b->x3 - b->x4);
 383     dist = qSqrt(normals[2].x()*normals[2].x() + normals[2].y()*normals[2].y());
 384     if (qFuzzyIsNull(dist))
 385         return false;
 386     normals[2] /= dist;
 387
 388     normals[1] = QPointF(b->x1 - b->x2 - b->x3 + b->x4, b->y1 - b->y2 - b->y3 + b->y4);
 389     normals[1] /= -1*qSqrt(normals[1].x()*normals[1].x() + normals[1].y()*normals[1].y());
 390
 391     qreal angles[2];
 392     qreal sign = 1.;
 393     for (int i = 0; i < 2; ++i) {
 394         qreal cos_a = normals[i].x()*normals[i+1].x() + normals[i].y()*normals[i+1].y();
 395         if (cos_a > 1.)
 396             cos_a = 1.;
 397         if (cos_a < -1.)
 398             cos_a = -1;
 399         angles[i] = qAcos(cos_a)/Q_PI;
 400     }
 401
 402     if (angles[0] + angles[1] > 1.) {
 403         // more than 180 degrees
 404         normals[1] = -normals[1];
 405         angles[0] = 1. - angles[0];
 406         angles[1] = 1. - angles[1];
 407         sign = -1.;
 408
 409     }
 410
 411     QPointF circle[3];
 412     circle[0] = QPointF(b->x1, b->y1) + normals[0]*offset;
 413     circle[1] = QPointF(qreal(0.5)*(b->x1 + b->x4), qreal(0.5)*(b->y1 + b->y4)) + normals[1]*offset;
 414     circle[2] = QPointF(b->x4, b->y4) + normals[2]*offset;
 415
 416     for (int i = 0; i < 2; ++i) {
 417         qreal kappa = qreal(2.0) * KAPPA * sign * offset * angles[i];
 418
 419         o->x1 = circle[i].x();
 420         o->y1 = circle[i].y();
 421         o->x2 = circle[i].x() - normals[i].y()*kappa;
 422         o->y2 = circle[i].y() + normals[i].x()*kappa;
 423         o->x3 = circle[i+1].x() + normals[i+1].y()*kappa;
 424         o->y3 = circle[i+1].y() - normals[i+1].x()*kappa;
 425         o->x4 = circle[i+1].x();
 426         o->y4 = circle[i+1].y();
 427
 428         ++o;
 429     }
 430     return true;
 431 }
 432
 433 int QBezier::shifted(QBezier *curveSegments, int maxSegments, qreal offset, float threshold) const
 434 {
 435     Q_ASSERT(curveSegments);
 436     Q_ASSERT(maxSegments > 0);
 437
 438     if (x1 == x2 && x1 == x3 && x1 == x4 &&
 439         y1 == y2 && y1 == y3 && y1 == y4)
 440         return 0;
 441
 442     --maxSegments;
 443     QBezier beziers[10];
 444 redo:
 445     beziers[0] = *this;
 446     QBezier *b = beziers;
 447     QBezier *o = curveSegments;
 448
 449     while (b >= beziers) {
 450         int stack_segments = b - beziers + 1;
 451         if ((stack_segments == 10) || (o - curveSegments == maxSegments - stack_segments)) {
 452             threshold *= qreal(1.5);
 453             if (threshold > qreal(2.0))
 454                 goto give_up;
 455             goto redo;
 456         }
 457         ShiftResult res = shift(b, o, offset, threshold);
 458         if (res == Discard) {
 459             --b;
 460         } else if (res == Ok) {
 461             ++o;
 462             --b;
 463             continue;
 464         } else if (res == Circle && maxSegments - (o - curveSegments) >= 2) {
 465             // add semi circle
 466             if (addCircle(b, offset, o))
 467                 o += 2;
 468             --b;
 469         } else {
 470             b->split(b+1, b);
 471             ++b;
 472         }
 473     }
 474
 475 give_up:
 476     while (b >= beziers) {
 477         ShiftResult res = shift(b, o, offset, threshold);
 478
 479         // if res isn't Ok or Split then *o is undefined
 480         if (res == Ok || res == Split)
 481             ++o;
 482
 483         --b;
 484     }
 485
 486     Q_ASSERT(o - curveSegments <= maxSegments);
 487     return o - curveSegments;
 488 }
 489
 490 #ifdef QDEBUG_BEZIER
 491 static QDebug operator<<(QDebug dbg, const QBezier &bz)
 492 {
 493     dbg << '[' << bz.x1<< ", " << bz.y1 << "], "
 494         << '[' << bz.x2 <<", " << bz.y2 << "], "
 495         << '[' << bz.x3 <<", " << bz.y3 << "], "
 496         << '[' << bz.x4 <<", " << bz.y4 << ']';
 497     return dbg;
 498 }
 499 #endif
 500
 501 static inline void splitBezierAt(const QBezier &bez, qreal t,
 502                                  QBezier *left, QBezier *right)
 503 {
 504     left->x1 = bez.x1;
 505     left->y1 = bez.y1;
 506
 507     left->x2 = bez.x1 + t * ( bez.x2 - bez.x1 );
 508     left->y2 = bez.y1 + t * ( bez.y2 - bez.y1 );
 509
 510     left->x3 = bez.x2 + t * ( bez.x3 - bez.x2 ); // temporary holding spot
 511     left->y3 = bez.y2 + t * ( bez.y3 - bez.y2 ); // temporary holding spot
 512
 513     right->x3 = bez.x3 + t * ( bez.x4 - bez.x3 );
 514     right->y3 = bez.y3 + t * ( bez.y4 - bez.y3 );
 515
 516     right->x2 = left->x3 + t * ( right->x3 - left->x3);
 517     right->y2 = left->y3 + t * ( right->y3 - left->y3);
 518
 519     left->x3 = left->x2 + t * ( left->x3 - left->x2 );
 520     left->y3 = left->y2 + t * ( left->y3 - left->y2 );
 521
 522     left->x4 = right->x1 = left->x3 + t * (right->x2 - left->x3);
 523     left->y4 = right->y1 = left->y3 + t * (right->y2 - left->y3);
 524
 525     right->x4 = bez.x4;
 526     right->y4 = bez.y4;
 527 }
 528
 529 qreal QBezier::length(qreal error) const
 530 {
 531     qreal length = qreal(0.0);
 532
 533     addIfClose(&length, error);
 534
 535     return length;
 536 }
 537
 538 void QBezier::addIfClose(qreal *length, qreal error) const
 539 {
 540     QBezier left, right;     /* bez poly splits */
 541
 542     qreal len = qreal(0.0);  /* arc length */
 543     qreal chord;             /* chord length */
 544
 545     len = len + QLineF(QPointF(x1, y1),QPointF(x2, y2)).length();
 546     len = len + QLineF(QPointF(x2, y2),QPointF(x3, y3)).length();
 547     len = len + QLineF(QPointF(x3, y3),QPointF(x4, y4)).length();
 548
 549     chord = QLineF(QPointF(x1, y1),QPointF(x4, y4)).length();
 550
 551     if((len-chord) > error) {
 552         split(&left, &right);                 /* split in two */
 553         left.addIfClose(length, error);       /* try left side */
 554         right.addIfClose(length, error);      /* try right side */
 555         return;
 556     }
 557
 558     *length = *length + len;
 559
 560     return;
 561 }
 562
 563 qreal QBezier::tForY(qreal t0, qreal t1, qreal y) const
 564 {
 565     qreal py0 = pointAt(t0).y();
 566     qreal py1 = pointAt(t1).y();
 567
 568     if (py0 > py1) {
 569         qSwap(py0, py1);
 570         qSwap(t0, t1);
 571     }
 572
 573     Q_ASSERT(py0 <= py1);
 574
 575     if (py0 >= y)
 576         return t0;
 577     else if (py1 <= y)
 578         return t1;
 579
 580     Q_ASSERT(py0 < y && y < py1);
 581
 582     qreal lt = t0;
 583     qreal dt;
 584     do {
 585         qreal t = qreal(0.5) * (t0 + t1);
 586
 587         qreal a, b, c, d;
 588         QBezier::coefficients(t, a, b, c, d);
 589         qreal yt = a * y1 + b * y2 + c * y3 + d * y4;
 590
 591         if (yt < y) {
 592             t0 = t;
 593             py0 = yt;
 594         } else {
 595             t1 = t;
 596             py1 = yt;
 597         }
 598         dt = lt - t;
 599         lt = t;
 600     } while (qAbs(dt) > qreal(1e-7));
 601
 602     return t0;
 603 }
 604
 605 int QBezier::stationaryYPoints(qreal &t0, qreal &t1) const
 606 {
 607     // y(t) = (1 - t)^3 * y1 + 3 * (1 - t)^2 * t * y2 + 3 * (1 - t) * t^2 * y3 + t^3 * y4
 608     // y'(t) = 3 * (-(1-2t+t^2) * y1 + (1 - 4 * t + 3 * t^2) * y2 + (2 * t - 3 * t^2) * y3 + t^2 * y4)
 609     // y'(t) = 3 * ((-y1 + 3 * y2 - 3 * y3 + y4)t^2 + (2 * y1 - 4 * y2 + 2 * y3)t + (-y1 + y2))
 610
 611     const qreal a = -y1 + 3 * y2 - 3 * y3 + y4;
 612     const qreal b = 2 * y1 - 4 * y2 + 2 * y3;
 613     const qreal c = -y1 + y2;
 614
 615     if (qFuzzyIsNull(a)) {
 616         if (qFuzzyIsNull(b))
 617             return 0;
 618
 619         t0 = -c / b;
 620         return t0 > 0 && t0 < 1;
 621     }
 622
 623     qreal reciprocal = b * b - 4 * a * c;
 624
 625     if (qFuzzyIsNull(reciprocal)) {
 626         t0 = -b / (2 * a);
 627         return t0 > 0 && t0 < 1;
 628     } else if (reciprocal > 0) {
 629         qreal temp = qSqrt(reciprocal);
 630
 631         t0 = (-b - temp)/(2*a);
 632         t1 = (-b + temp)/(2*a);
 633
 634         if (t1 < t0)
 635             qSwap(t0, t1);
 636
 637         int count = 0;
 638         qreal t[2] = { 0, 1 };
 639
 640         if (t0 > 0 && t0 < 1)
 641             t[count++] = t0;
 642         if (t1 > 0 && t1 < 1)
 643             t[count++] = t1;
 644
 645         t0 = t[0];
 646         t1 = t[1];
 647
 648         return count;
 649     }
 650
 651     return 0;
 652 }
 653
 654 qreal QBezier::tAtLength(qreal l) const
 655 {
 656     qreal len = length();
 657     qreal t   = qreal(1.0);
 658     const qreal error = qreal(0.01);
 659     if (l > len || qFuzzyCompare(l, len))
 660         return t;
 661
 662     t *= qreal(0.5);
 663     //int iters = 0;
 664     //qDebug()<<"LEN is "<<l<<len;
 665     qreal lastBigger = qreal(1.0);
 666     while (1) {
 667         //qDebug()<<"\tt is "<<t;
 668         QBezier right = *this;
 669         QBezier left;
 670         right.parameterSplitLeft(t, &left);
 671         qreal lLen = left.length();
 672         if (qAbs(lLen - l) < error)
 673             break;
 674
 675         if (lLen < l) {
 676             t += (lastBigger - t) * qreal(0.5);
 677         } else {
 678             lastBigger = t;
 679             t -= t * qreal(0.5);
 680         }
 681         //++iters;
 682     }
 683     //qDebug()<<"number of iters is "<<iters;
 684     return t;
 685 }
 686
 687 QBezier QBezier::bezierOnInterval(qreal t0, qreal t1) const
 688 {
 689     if (t0 == 0 && t1 == 1)
 690         return *this;
 691
 692     QBezier bezier = *this;
 693
 694     QBezier result;
 695     bezier.parameterSplitLeft(t0, &result);
 696     qreal trueT = (t1-t0)/(1-t0);
 697     bezier.parameterSplitLeft(trueT, &result);
 698
 699     return result;
 700 }
 701
 702 QT_END_NAMESPACE