src/quick/scenegraph/qsgpathsimplifier.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtDeclarative module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qsgpathsimplifier_p.h"
  43
  44 #include <QtCore/qvarlengtharray.h>
  45 #include <QtCore/qglobal.h>
  46 #include <QtCore/qpoint.h>
  47 #include <QtCore/qalgorithms.h>
  48
  49 #include <math.h>
  50
  51 #include <private/qopengl_p.h>
  52 #include <private/qrbtree_p.h>
  53
  54 QT_BEGIN_NAMESPACE
  55
  56 #define Q_FIXED_POINT_SCALE 256
  57 #define Q_TRIANGULATE_END_OF_POLYGON quint32(-1)
  58
  59
  60 namespace {
  61
  62 //============================================================================//
  63 //                                   QPoint                                   //
  64 //============================================================================//
  65
  66 inline bool operator < (const QPoint &a, const QPoint &b)
  67 {
  68     return a.y() < b.y() || (a.y() == b.y() && a.x() < b.x());
  69 }
  70
  71 inline bool operator > (const QPoint &a, const QPoint &b)
  72 {
  73     return b < a;
  74 }
  75
  76 inline bool operator <= (const QPoint &a, const QPoint &b)
  77 {
  78     return !(a > b);
  79 }
  80
  81 inline bool operator >= (const QPoint &a, const QPoint &b)
  82 {
  83     return !(a < b);
  84 }
  85
  86 inline int cross(const QPoint &u, const QPoint &v)
  87 {
  88     return u.x() * v.y() - u.y() * v.x();
  89 }
  90
  91 inline int dot(const QPoint &u, const QPoint &v)
  92 {
  93     return u.x() * v.x() + u.y() * v.y();
  94 }
  95
  96 //============================================================================//
  97 //                                  Fraction                                  //
  98 //============================================================================//
  99
 100 // Fraction must be in the range [0, 1)
 101 struct Fraction
 102 {
 103     bool isValid() const { return denominator != 0; }
 104
 105     // numerator and denominator must not have common denominators.
 106     unsigned int numerator, denominator;
 107 };
 108
 109 inline unsigned int gcd(unsigned int x, unsigned int y)
 110 {
 111     while (y != 0) {
 112         unsigned int z = y;
 113         y = x % y;
 114         x = z;
 115     }
 116     return x;
 117 }
 118
 119 // Fraction must be in the range [0, 1)
 120 // Assume input is valid.
 121 Fraction fraction(unsigned int n, unsigned int d) {
 122     Fraction result;
 123     if (n == 0) {
 124         result.numerator = 0;
 125         result.denominator = 1;
 126     } else {
 127         unsigned int g = gcd(n, d);
 128         result.numerator = n / g;
 129         result.denominator = d / g;
 130     }
 131     return result;
 132 }
 133
 134 //============================================================================//
 135 //                                  Rational                                  //
 136 //============================================================================//
 137
 138 struct Rational
 139 {
 140     bool isValid() const { return fraction.isValid(); }
 141     int integer;
 142     Fraction fraction;
 143 };
 144
 145 //============================================================================//
 146 //                             IntersectionPoint                              //
 147 //============================================================================//
 148
 149 struct IntersectionPoint
 150 {
 151     bool isValid() const { return x.fraction.isValid() && y.fraction.isValid(); }
 152     QPoint round() const;
 153     bool isAccurate() const { return x.fraction.numerator == 0 && y.fraction.numerator == 0; }
 154
 155     Rational x; // 8:8 signed, 32/32
 156     Rational y; // 8:8 signed, 32/32
 157 };
 158
 159 QPoint IntersectionPoint::round() const
 160 {
 161     QPoint result(x.integer, y.integer);
 162     if (2 * x.fraction.numerator >= x.fraction.denominator)
 163         ++result.rx();
 164     if (2 * y.fraction.numerator >= y.fraction.denominator)
 165         ++result.ry();
 166     return result;
 167 }
 168
 169 // Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the
 170 // line and zero if exactly on the line.
 171 // The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1',
 172 // which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order).
 173 inline int pointDistanceFromLine(const QPoint &p, const QPoint &v1, const QPoint &v2)
 174 {
 175     return cross(v2 - v1, p - v1);
 176 }
 177
 178 IntersectionPoint intersectionPoint(const QPoint &u1, const QPoint &u2,
 179                                     const QPoint &v1, const QPoint &v2)
 180 {
 181     IntersectionPoint result = {{0, {0, 0}}, {0, {0, 0}}};
 182
 183     QPoint u = u2 - u1;
 184     QPoint v = v2 - v1;
 185     int d1 = cross(u, v1 - u1);
 186     int d2 = cross(u, v2 - u1);
 187     int det = d2 - d1;
 188     int d3 = cross(v, u1 - v1);
 189     int d4 = d3 - det; //qCross(v, u2 - v1);
 190
 191     // Check that the math is correct.
 192     Q_ASSERT(d4 == cross(v, u2 - v1));
 193
 194     // The intersection point can be expressed as:
 195     // v1 - v * d1/det
 196     // v2 - v * d2/det
 197     // u1 + u * d3/det
 198     // u2 + u * d4/det
 199
 200     // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.
 201     if (det == 0)
 202         return result;
 203
 204     if (det < 0) {
 205         det = -det;
 206         d1 = -d1;
 207         d2 = -d2;
 208         d3 = -d3;
 209         d4 = -d4;
 210     }
 211
 212     // I'm only interested in lines intersecting at their interior, not at their end points.
 213     // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'.
 214     if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
 215         return result;
 216
 217     // Calculate the intersection point as follows:
 218     // v1 - v * d1/det | v1 <= v2 (component-wise)
 219     // v2 - v * d2/det | v2 < v1 (component-wise)
 220
 221     // Assuming 16 bits per vector component.
 222     if (v.x() >= 0) {
 223         result.x.integer = v1.x() + int(qint64(-v.x()) * d1 / det);
 224         result.x.fraction = fraction((unsigned int)(qint64(-v.x()) * d1 % det), (unsigned int)det);
 225     } else {
 226         result.x.integer = v2.x() + int(qint64(-v.x()) * d2 / det);
 227         result.x.fraction = fraction((unsigned int)(qint64(-v.x()) * d2 % det), (unsigned int)det);
 228     }
 229
 230     if (v.y() >= 0) {
 231         result.y.integer = v1.y() + int(qint64(-v.y()) * d1 / det);
 232         result.y.fraction = fraction((unsigned int)(qint64(-v.y()) * d1 % det), (unsigned int)det);
 233     } else {
 234         result.y.integer = v2.y() + int(qint64(-v.y()) * d2 / det);
 235         result.y.fraction = fraction((unsigned int)(qint64(-v.y()) * d2 % det), (unsigned int)det);
 236     }
 237
 238     Q_ASSERT(result.x.fraction.isValid());
 239     Q_ASSERT(result.y.fraction.isValid());
 240     return result;
 241 }
 242
 243 //============================================================================//
 244 //                               PathSimplifier                               //
 245 //============================================================================//
 246
 247 class PathSimplifier
 248 {
 249 public:
 250     PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
 251                    QDataBuffer<quint32> &indices, const QTransform &matrix);
 252
 253 private:
 254     struct Element;
 255
 256     class BoundingVolumeHierarchy
 257     {
 258     public:
 259         struct Node
 260         {
 261             enum Type
 262             {
 263                 Leaf,
 264                 Split
 265             };
 266             Type type;
 267             QPoint minimum;
 268             QPoint maximum;
 269             union {
 270                 Element *element; // type == Leaf
 271                 Node *left; // type == Split
 272             };
 273             Node *right;
 274         };
 275
 276         BoundingVolumeHierarchy();
 277         ~BoundingVolumeHierarchy();
 278         void allocate(int nodeCount);
 279         void free();
 280         Node *newNode();
 281
 282         Node *root;
 283     private:
 284         void freeNode(Node *n);
 285
 286         Node *nodeBlock;
 287         int blockSize;
 288         int firstFree;
 289     };
 290
 291     struct Element
 292     {
 293         enum Degree
 294         {
 295             Line = 1,
 296             Quadratic = 2,
 297             Cubic = 3
 298         };
 299
 300         quint32 &upperIndex() { return indices[pointingUp ? degree : 0]; }
 301         quint32 &lowerIndex() { return indices[pointingUp ? 0 : degree]; }
 302         quint32 upperIndex() const { return indices[pointingUp ? degree : 0]; }
 303         quint32 lowerIndex() const { return indices[pointingUp ? 0 : degree]; }
 304         void flip();
 305
 306         QPoint middle;
 307         quint32 indices[4]; // index to points
 308         Element *next, *previous; // used in connectElements()
 309         int winding; // used in connectElements()
 310         union {
 311             QRBTree<Element *>::Node *edgeNode; // used in connectElements()
 312             BoundingVolumeHierarchy::Node *bvhNode;
 313         };
 314         Degree degree : 8;
 315         uint processed : 1; // initially false, true when the element has been checked for intersections.
 316         uint pointingUp : 1; // used in connectElements()
 317         uint originallyPointingUp : 1; // used in connectElements()
 318     };
 319
 320     class ElementAllocator
 321     {
 322     public:
 323         ElementAllocator();
 324         ~ElementAllocator();
 325         void allocate(int count);
 326         Element *newElement();
 327     private:
 328         struct ElementBlock
 329         {
 330             ElementBlock *next;
 331             int blockSize;
 332             int firstFree;
 333             Element elements[1];
 334         } *blocks;
 335     };
 336
 337     struct Event
 338     {
 339         enum Type { Upper, Lower };
 340         bool operator < (const Event &other) const;
 341
 342         QPoint point;
 343         Type type;
 344         Element *element;
 345     };
 346
 347     typedef QRBTree<Element *>::Node RBNode;
 348     typedef BoundingVolumeHierarchy::Node BVHNode;
 349
 350     void initElements(const QVectorPath &path, const QTransform &matrix);
 351     void removeIntersections();
 352     void connectElements();
 353     void fillIndices();
 354     BVHNode *buildTree(Element **elements, int elementCount);
 355     bool intersectNodes(QDataBuffer<Element *> &elements, BVHNode *elementNode, BVHNode *treeNode);
 356     bool equalElements(const Element *e1, const Element *e2);
 357     bool splitLineAt(QDataBuffer<Element *> &elements, BVHNode *node, quint32 pointIndex, bool processAgain);
 358     void appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes, Element *element);
 359     QPair<int, int> calculateSeparatingAxisRange(const QPoint &axis, Element *element);
 360     void splitCurve(QDataBuffer<Element *> &elements, BVHNode *node);
 361     bool setElementToQuadratic(Element *element, quint32 pointIndex1, const QPoint &ctrl, quint32 pointIndex2);
 362     bool setElementToCubic(Element *element, quint32 pointIndex1, const QPoint &ctrl1, const QPoint &ctrl2, quint32 pointIndex2);
 363     void setElementToCubicAndSimplify(Element *element, quint32 pointIndex1, const QPoint &ctrl1, const QPoint &ctrl2, quint32 pointIndex2);
 364     RBNode *findElementLeftOf(const Element *element, const QPair<RBNode *, RBNode *> &bounds);
 365     bool elementIsLeftOf(const Element *left, const Element *right);
 366     QPair<RBNode *, RBNode *> outerBounds(const QPoint &point);
 367     static bool flattenQuadratic(const QPoint &u, const QPoint &v, const QPoint &w);
 368     static bool flattenCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q);
 369     static bool splitQuadratic(const QPoint &u, const QPoint &v, const QPoint &w, QPoint *result);
 370     static bool splitCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q, QPoint *result);
 371     void subDivQuadratic(const QPoint &u, const QPoint &v, const QPoint &w);
 372     void subDivCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q);
 373     static void sortEvents(Event *events, int count);
 374
 375     ElementAllocator m_elementAllocator;
 376     QDataBuffer<Element *> m_elements;
 377     QDataBuffer<QPoint> *m_points;
 378     BoundingVolumeHierarchy m_bvh;
 379     QDataBuffer<quint32> *m_indices;
 380     QRBTree<Element *> m_elementList;
 381     uint m_hints;
 382 };
 383
 384 inline PathSimplifier::BoundingVolumeHierarchy::BoundingVolumeHierarchy()
 385     : root(0)
 386     , nodeBlock(0)
 387     , blockSize(0)
 388     , firstFree(0)
 389 {
 390 }
 391
 392 inline PathSimplifier::BoundingVolumeHierarchy::~BoundingVolumeHierarchy()
 393 {
 394     free();
 395 }
 396
 397 inline void PathSimplifier::BoundingVolumeHierarchy::allocate(int nodeCount)
 398 {
 399     Q_ASSERT(nodeBlock == 0);
 400     Q_ASSERT(firstFree == 0);
 401     nodeBlock = new Node[blockSize = nodeCount];
 402 }
 403
 404 inline void PathSimplifier::BoundingVolumeHierarchy::free()
 405 {
 406     freeNode(root);
 407     delete[] nodeBlock;
 408     nodeBlock = 0;
 409     firstFree = blockSize = 0;
 410     root = 0;
 411 }
 412
 413 inline PathSimplifier::BVHNode *PathSimplifier::BoundingVolumeHierarchy::newNode()
 414 {
 415     if (firstFree < blockSize)
 416         return &nodeBlock[firstFree++];
 417     return new Node;
 418 }
 419
 420 inline void PathSimplifier::BoundingVolumeHierarchy::freeNode(Node *n)
 421 {
 422     if (!n)
 423         return;
 424     Q_ASSERT(n->type == Node::Split || n->type == Node::Leaf);
 425     if (n->type == Node::Split) {
 426         freeNode(n->left);
 427         freeNode(n->right);
 428     }
 429     if (!(n >= nodeBlock && n < nodeBlock + blockSize))
 430         delete n;
 431 }
 432
 433 inline PathSimplifier::ElementAllocator::ElementAllocator()
 434     : blocks(0)
 435 {
 436 }
 437
 438 inline PathSimplifier::ElementAllocator::~ElementAllocator()
 439 {
 440     while (blocks) {
 441         ElementBlock *block = blocks;
 442         blocks = blocks->next;
 443         free(block);
 444     }
 445 }
 446
 447 inline void PathSimplifier::ElementAllocator::allocate(int count)
 448 {
 449     Q_ASSERT(blocks == 0);
 450     Q_ASSERT(count > 0);
 451     blocks = (ElementBlock *)malloc(sizeof(ElementBlock) + (count - 1) * sizeof(Element));
 452     blocks->blockSize = count;
 453     blocks->next = 0;
 454     blocks->firstFree = 0;
 455 }
 456
 457 inline PathSimplifier::Element *PathSimplifier::ElementAllocator::newElement()
 458 {
 459     Q_ASSERT(blocks);
 460     if (blocks->firstFree < blocks->blockSize)
 461         return &blocks->elements[blocks->firstFree++];
 462     ElementBlock *oldBlock = blocks;
 463     blocks = (ElementBlock *)malloc(sizeof(ElementBlock) + (oldBlock->blockSize - 1) * sizeof(Element));
 464     blocks->blockSize = oldBlock->blockSize;
 465     blocks->next = oldBlock;
 466     blocks->firstFree = 0;
 467     return &blocks->elements[blocks->firstFree++];
 468 }
 469
 470
 471 inline bool PathSimplifier::Event::operator < (const Event &other) const
 472 {
 473     if (point == other.point)
 474         return type < other.type;
 475     return other.point < point;
 476 }
 477
 478 inline void PathSimplifier::Element::flip()
 479 {
 480     for (int i = 0; i < (degree + 1) >> 1; ++i) {
 481         Q_ASSERT(degree >= Line && degree <= Cubic);
 482         Q_ASSERT(i >= 0 && i < degree);
 483         qSwap(indices[i], indices[degree - i]);
 484     }
 485     pointingUp = !pointingUp;
 486     Q_ASSERT(next == 0 && previous == 0);
 487 }
 488
 489 PathSimplifier::PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
 490                                QDataBuffer<quint32> &indices, const QTransform &matrix)
 491     : m_elements(0)
 492     , m_points(&vertices)
 493     , m_indices(&indices)
 494 {
 495     m_points->reset();
 496     m_indices->reset();
 497     initElements(path, matrix);
 498     if (!m_elements.isEmpty()) {
 499         removeIntersections();
 500         connectElements();
 501         fillIndices();
 502     }
 503 }
 504
 505 void PathSimplifier::initElements(const QVectorPath &path, const QTransform &matrix)
 506 {
 507     m_hints = path.hints();
 508     int pathElementCount = path.elementCount();
 509     if (pathElementCount == 0)
 510         return;
 511     m_elements.reserve(2 * pathElementCount);
 512     m_elementAllocator.allocate(2 * pathElementCount);
 513     m_points->reserve(2 * pathElementCount);
 514     const QPainterPath::ElementType *e = path.elements();
 515     const qreal *p = path.points();
 516     if (e) {
 517         qreal x, y;
 518         quint32 moveToIndex = 0;
 519         quint32 previousIndex = 0;
 520         for (int i = 0; i < pathElementCount; ++i, ++e, p += 2) {
 521             switch (*e) {
 522             case QPainterPath::MoveToElement:
 523                 {
 524                     if (!m_points->isEmpty()) {
 525                         const QPoint &from = m_points->at(previousIndex);
 526                         const QPoint &to = m_points->at(moveToIndex);
 527                         if (from != to) {
 528                             Element *element = m_elementAllocator.newElement();
 529                             element->degree = Element::Line;
 530                             element->indices[0] = previousIndex;
 531                             element->indices[1] = moveToIndex;
 532                             element->middle.rx() = (from.x() + to.x()) >> 1;
 533                             element->middle.ry() = (from.y() + to.y()) >> 1;
 534                             m_elements.add(element);
 535                         }
 536                     }
 537                     previousIndex = moveToIndex = m_points->size();
 538                     matrix.map(p[0], p[1], &x, &y);
 539                     QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
 540                     m_points->add(to);
 541                 }
 542                 break;
 543             case QPainterPath::LineToElement:
 544                 Q_ASSERT(!m_points->isEmpty());
 545                 {
 546                     matrix.map(p[0], p[1], &x, &y);
 547                     QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
 548                     const QPoint &from = m_points->last();
 549                     if (to != from) {
 550                         Element *element = m_elementAllocator.newElement();
 551                         element->degree = Element::Line;
 552                         element->indices[0] = previousIndex;
 553                         element->indices[1] = quint32(m_points->size());
 554                         element->middle.rx() = (from.x() + to.x()) >> 1;
 555                         element->middle.ry() = (from.y() + to.y()) >> 1;
 556                         m_elements.add(element);
 557                         previousIndex = m_points->size();
 558                         m_points->add(to);
 559                     }
 560                 }
 561                 break;
 562             case QPainterPath::CurveToElement:
 563                 Q_ASSERT(i + 2 < pathElementCount);
 564                 Q_ASSERT(!m_points->isEmpty());
 565                 Q_ASSERT(e[1] == QPainterPath::CurveToDataElement);
 566                 Q_ASSERT(e[2] == QPainterPath::CurveToDataElement);
 567                 {
 568                     quint32 startPointIndex = previousIndex;
 569                     matrix.map(p[4], p[5], &x, &y);
 570                     QPoint end(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
 571                     previousIndex = m_points->size();
 572                     m_points->add(end);
 573
 574                     // See if this cubic bezier is really quadratic.
 575                     qreal x1 = p[-2] + qreal(1.5) * (p[0] - p[-2]);
 576                     qreal y1 = p[-1] + qreal(1.5) * (p[1] - p[-1]);
 577                     qreal x2 = p[4] + qreal(1.5) * (p[2] - p[4]);
 578                     qreal y2 = p[5] + qreal(1.5) * (p[3] - p[5]);
 579
 580                     Element *element = m_elementAllocator.newElement();
 581                     if (qAbs(x1 - x2) < qreal(1e-3) && qAbs(y1 - y2) < qreal(1e-3)) {
 582                         // The bezier curve is quadratic.
 583                         matrix.map(x1, y1, &x, &y);
 584                         QPoint ctrl(qRound(x * Q_FIXED_POINT_SCALE),
 585                                     qRound(y * Q_FIXED_POINT_SCALE));
 586                         setElementToQuadratic(element, startPointIndex, ctrl, previousIndex);
 587                     } else {
 588                         // The bezier curve is cubic.
 589                         matrix.map(p[0], p[1], &x, &y);
 590                         QPoint ctrl1(qRound(x * Q_FIXED_POINT_SCALE),
 591                                      qRound(y * Q_FIXED_POINT_SCALE));
 592                         matrix.map(p[2], p[3], &x, &y);
 593                         QPoint ctrl2(qRound(x * Q_FIXED_POINT_SCALE),
 594                                      qRound(y * Q_FIXED_POINT_SCALE));
 595                         setElementToCubicAndSimplify(element, startPointIndex, ctrl1, ctrl2,
 596                                                      previousIndex);
 597                     }
 598                     m_elements.add(element);
 599                 }
 600                 i += 2;
 601                 e += 2;
 602                 p += 4;
 603
 604                 break;
 605             default:
 606                 Q_ASSERT_X(0, "QSGPathSimplifier::initialize", "Unexpected element type.");
 607                 break;
 608             }
 609         }
 610         if (!m_points->isEmpty()) {
 611             const QPoint &from = m_points->at(previousIndex);
 612             const QPoint &to = m_points->at(moveToIndex);
 613             if (from != to) {
 614                 Element *element = m_elementAllocator.newElement();
 615                 element->degree = Element::Line;
 616                 element->indices[0] = previousIndex;
 617                 element->indices[1] = moveToIndex;
 618                 element->middle.rx() = (from.x() + to.x()) >> 1;
 619                 element->middle.ry() = (from.y() + to.y()) >> 1;
 620                 m_elements.add(element);
 621             }
 622         }
 623     } else {
 624         qreal x, y;
 625
 626         for (int i = 0; i < pathElementCount; ++i, p += 2) {
 627             matrix.map(p[0], p[1], &x, &y);
 628             QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
 629             if (to != m_points->last())
 630                 m_points->add(to);
 631         }
 632
 633         while (!m_points->isEmpty() && m_points->last() == m_points->first())
 634             m_points->pop_back();
 635
 636         if (m_points->isEmpty())
 637             return;
 638
 639         quint32 prev = quint32(m_points->size() - 1);
 640         for (int i = 0; i < m_points->size(); ++i) {
 641             QPoint &to = m_points->at(i);
 642             QPoint &from = m_points->at(prev);
 643             Element *element = m_elementAllocator.newElement();
 644             element->degree = Element::Line;
 645             element->indices[0] = prev;
 646             element->indices[1] = quint32(i);
 647             element->middle.rx() = (from.x() + to.x()) >> 1;
 648             element->middle.ry() = (from.y() + to.y()) >> 1;
 649             m_elements.add(element);
 650             prev = i;
 651         }
 652     }
 653
 654     for (int i = 0; i < m_elements.size(); ++i)
 655         m_elements.at(i)->processed = false;
 656 }
 657
 658 void PathSimplifier::removeIntersections()
 659 {
 660     Q_ASSERT(!m_elements.isEmpty());
 661     QDataBuffer<Element *> elements(m_elements.size());
 662     for (int i = 0; i < m_elements.size(); ++i)
 663         elements.add(m_elements.at(i));
 664     m_bvh.allocate(2 * m_elements.size());
 665     m_bvh.root = buildTree(elements.data(), elements.size());
 666
 667     elements.reset();
 668     for (int i = 0; i < m_elements.size(); ++i)
 669         elements.add(m_elements.at(i));
 670
 671     while (!elements.isEmpty()) {
 672         Element *element = elements.last();
 673         elements.pop_back();
 674         BVHNode *node = element->bvhNode;
 675         Q_ASSERT(node->type == BVHNode::Leaf);
 676         Q_ASSERT(node->element == element);
 677         if (!element->processed) {
 678             if (!intersectNodes(elements, node, m_bvh.root))
 679                 element->processed = true;
 680         }
 681     }
 682
 683     m_bvh.free(); // The bounding volume hierarchy is not needed anymore.
 684 }
 685
 686 void PathSimplifier::connectElements()
 687 {
 688     Q_ASSERT(!m_elements.isEmpty());
 689     QDataBuffer<Event> events(m_elements.size() * 2);
 690     for (int i = 0; i < m_elements.size(); ++i) {
 691         Element *element = m_elements.at(i);
 692         element->next = element->previous = 0;
 693         element->winding = 0;
 694         element->edgeNode = 0;
 695         const QPoint &u = m_points->at(element->indices[0]);
 696         const QPoint &v = m_points->at(element->indices[element->degree]);
 697         if (u != v) {
 698             element->pointingUp = element->originallyPointingUp = v < u;
 699
 700             Event event;
 701             event.element = element;
 702             event.point = u;
 703             event.type = element->pointingUp ? Event::Lower : Event::Upper;
 704             events.add(event);
 705             event.point = v;
 706             event.type = element->pointingUp ? Event::Upper : Event::Lower;
 707             events.add(event);
 708         }
 709     }
 710     QVarLengthArray<Element *, 8> orderedElements;
 711     if (!events.isEmpty())
 712         sortEvents(events.data(), events.size());
 713     while (!events.isEmpty()) {
 714         const Event *event = &events.last();
 715         QPoint eventPoint = event->point;
 716
 717         // Find all elements passing through the event point.
 718         QPair<RBNode *, RBNode *> bounds = outerBounds(eventPoint);
 719
 720         // Special case: single element above and single element below event point.
 721         int eventCount = events.size();
 722         if (event->type == Event::Lower && eventCount > 2) {
 723             QPair<RBNode *, RBNode *> range;
 724             range.first = bounds.first ? m_elementList.next(bounds.first)
 725                                        : m_elementList.front(m_elementList.root);
 726             range.second = bounds.second ? m_elementList.previous(bounds.second)
 727                                          : m_elementList.back(m_elementList.root);
 728
 729             const Event *event2 = &events.at(eventCount - 2);
 730             const Event *event3 = &events.at(eventCount - 3);
 731             Q_ASSERT(event2->point == eventPoint); // There are always at least two events at a point.
 732             if (range.first == range.second && event2->type == Event::Upper && event3->point != eventPoint) {
 733                 Element *element = event->element;
 734                 Element *element2 = event2->element;
 735                 element->edgeNode->data = event2->element;
 736                 element2->edgeNode = element->edgeNode;
 737                 element->edgeNode = 0;
 738
 739                 events.pop_back();
 740                 events.pop_back();
 741
 742                 if (element2->pointingUp != element->pointingUp)
 743                     element2->flip();
 744                 element2->winding = element->winding;
 745                 int winding = element->winding;
 746                 if (element->originallyPointingUp)
 747                     ++winding;
 748                 if (winding == 0 || winding == 1) {
 749                     if (element->pointingUp) {
 750                         element->previous = event2->element;
 751                         element2->next = event->element;
 752                     } else {
 753                         element->next = event2->element;
 754                         element2->previous = event->element;
 755                     }
 756                 }
 757                 continue;
 758             }
 759         }
 760         orderedElements.clear();
 761
 762         // First, find the ones above the event point.
 763         if (m_elementList.root) {
 764             RBNode *current = bounds.first ? m_elementList.next(bounds.first)
 765                                            : m_elementList.front(m_elementList.root);
 766             while (current != bounds.second) {
 767                 Element *element = current->data;
 768                 Q_ASSERT(element->edgeNode == current);
 769                 int winding = element->winding;
 770                 if (element->originallyPointingUp)
 771                     ++winding;
 772                 const QPoint &lower = m_points->at(element->lowerIndex());
 773                 if (lower == eventPoint) {
 774                     if (winding == 0 || winding == 1)
 775                         orderedElements.append(current->data);
 776                 } else {
 777                     // The element is passing through 'event.point'.
 778                     Q_ASSERT(m_points->at(element->upperIndex()) != eventPoint);
 779                     Q_ASSERT(element->degree == Element::Line);
 780                     // Split the line.
 781                     Element *eventElement = event->element;
 782                     int indexIndex = (event->type == Event::Upper) == eventElement->pointingUp
 783                                      ? eventElement->degree : 0;
 784                     quint32 pointIndex = eventElement->indices[indexIndex];
 785                     Q_ASSERT(eventPoint == m_points->at(pointIndex));
 786
 787                     Element *upperElement = m_elementAllocator.newElement();
 788                     *upperElement = *element;
 789                     upperElement->lowerIndex() = element->upperIndex() = pointIndex;
 790                     upperElement->edgeNode = 0;
 791                     element->next = element->previous = 0;
 792                     if (upperElement->next)
 793                         upperElement->next->previous = upperElement;
 794                     else if (upperElement->previous)
 795                         upperElement->previous->next = upperElement;
 796                     if (element->pointingUp != element->originallyPointingUp)
 797                         element->flip();
 798                     if (winding == 0 || winding == 1)
 799                         orderedElements.append(upperElement);
 800                     m_elements.add(upperElement);
 801                 }
 802                 current = m_elementList.next(current);
 803             }
 804         }
 805         while (!events.isEmpty() && events.last().point == eventPoint) {
 806             event = &events.last();
 807             if (event->type == Event::Upper) {
 808                 Q_ASSERT(event->point == m_points->at(event->element->upperIndex()));
 809                 RBNode *left = findElementLeftOf(event->element, bounds);
 810                 RBNode *node = m_elementList.newNode();
 811                 node->data = event->element;
 812                 Q_ASSERT(event->element->edgeNode == 0);
 813                 event->element->edgeNode = node;
 814                 m_elementList.attachAfter(left, node);
 815             } else {
 816                 Q_ASSERT(event->type == Event::Lower);
 817                 Q_ASSERT(event->point == m_points->at(event->element->lowerIndex()));
 818                 Element *element = event->element;
 819                 Q_ASSERT(element->edgeNode);
 820                 m_elementList.deleteNode(element->edgeNode);
 821                 Q_ASSERT(element->edgeNode == 0);
 822             }
 823             events.pop_back();
 824         }
 825
 826         if (m_elementList.root) {
 827             RBNode *current = bounds.first ? m_elementList.next(bounds.first)
 828                                            : m_elementList.front(m_elementList.root);
 829             int winding = bounds.first ? bounds.first->data->winding : 0;
 830
 831             // Calculate winding numbers and flip elements if necessary.
 832             while (current != bounds.second) {
 833                 Element *element = current->data;
 834                 Q_ASSERT(element->edgeNode == current);
 835                 int ccw = winding & 1;
 836                 Q_ASSERT(element->pointingUp == element->originallyPointingUp);
 837                 if (element->originallyPointingUp) {
 838                     --winding;
 839                 } else {
 840                     ++winding;
 841                     ccw ^= 1;
 842                 }
 843                 element->winding = winding;
 844                 if (ccw == 0)
 845                     element->flip();
 846                 current = m_elementList.next(current);
 847             }
 848
 849             // Pick elements with correct winding number.
 850             current = bounds.second ? m_elementList.previous(bounds.second)
 851                                     : m_elementList.back(m_elementList.root);
 852             while (current != bounds.first) {
 853                 Element *element = current->data;
 854                 Q_ASSERT(element->edgeNode == current);
 855                 Q_ASSERT(m_points->at(element->upperIndex()) == eventPoint);
 856                 int winding = element->winding;
 857                 if (element->originallyPointingUp)
 858                     ++winding;
 859                 if (winding == 0 || winding == 1)
 860                     orderedElements.append(current->data);
 861                 current = m_elementList.previous(current);
 862             }
 863         }
 864
 865         if (!orderedElements.isEmpty()) {
 866             Q_ASSERT((orderedElements.size() & 1) == 0);
 867             int i = 0;
 868             Element *firstElement = orderedElements.at(0);
 869             if (m_points->at(firstElement->indices[0]) != eventPoint) {
 870                 orderedElements.append(firstElement);
 871                 i = 1;
 872             }
 873             for (; i < orderedElements.size(); i += 2) {
 874                 Q_ASSERT(i + 1 < orderedElements.size());
 875                 Element *next = orderedElements.at(i);
 876                 Element *previous = orderedElements.at(i + 1);
 877                 Q_ASSERT(next->previous == 0);
 878                 Q_ASSERT(previous->next == 0);
 879                 next->previous = previous;
 880                 previous->next = next;
 881             }
 882         }
 883     }
 884 #ifndef QT_NO_DEBUG
 885     for (int i = 0; i < m_elements.size(); ++i) {
 886         const Element *element = m_elements.at(i);
 887         Q_ASSERT(element->next == 0 || element->next->previous == element);
 888         Q_ASSERT(element->previous == 0 || element->previous->next == element);
 889         Q_ASSERT((element->next == 0) == (element->previous == 0));
 890     }
 891 #endif
 892 }
 893
 894 void PathSimplifier::fillIndices()
 895 {
 896     for (int i = 0; i < m_elements.size(); ++i)
 897         m_elements.at(i)->processed = false;
 898     for (int i = 0; i < m_elements.size(); ++i) {
 899         Element *element = m_elements.at(i);
 900         if (element->processed || element->next == 0)
 901             continue;
 902         do {
 903             m_indices->add(element->indices[0]);
 904             switch (element->degree) {
 905             case Element::Quadratic:
 906                 {
 907                     QPoint pts[] = {
 908                         m_points->at(element->indices[0]),
 909                         m_points->at(element->indices[1]),
 910                         m_points->at(element->indices[2])
 911                     };
 912                     subDivQuadratic(pts[0], pts[1], pts[2]);
 913                 }
 914                 break;
 915             case Element::Cubic:
 916                 {
 917                     QPoint pts[] = {
 918                         m_points->at(element->indices[0]),
 919                         m_points->at(element->indices[1]),
 920                         m_points->at(element->indices[2]),
 921                         m_points->at(element->indices[3])
 922                     };
 923                     subDivCubic(pts[0], pts[1], pts[2], pts[3]);
 924                 }
 925                 break;
 926             default:
 927                 break;
 928             }
 929             Q_ASSERT(element->next);
 930             element->processed = true;
 931             element = element->next;
 932         } while (element != m_elements.at(i));
 933         m_indices->add(Q_TRIANGULATE_END_OF_POLYGON);
 934     }
 935 }
 936
 937 PathSimplifier::BVHNode *PathSimplifier::buildTree(Element **elements, int elementCount)
 938 {
 939     Q_ASSERT(elementCount > 0);
 940     BVHNode *node = m_bvh.newNode();
 941     if (elementCount == 1) {
 942         Element *element = *elements;
 943         element->bvhNode = node;
 944         node->type = BVHNode::Leaf;
 945         node->element = element;
 946         node->minimum = node->maximum = m_points->at(element->indices[0]);
 947         for (int i = 1; i <= element->degree; ++i) {
 948             const QPoint &p = m_points->at(element->indices[i]);
 949             node->minimum.rx() = qMin(node->minimum.x(), p.x());
 950             node->minimum.ry() = qMin(node->minimum.y(), p.y());
 951             node->maximum.rx() = qMax(node->maximum.x(), p.x());
 952             node->maximum.ry() = qMax(node->maximum.y(), p.y());
 953         }
 954         return node;
 955     }
 956
 957     node->type = BVHNode::Split;
 958
 959     QPoint minimum, maximum;
 960     minimum = maximum = elements[0]->middle;
 961
 962     for (int i = 1; i < elementCount; ++i) {
 963         const QPoint &p = elements[i]->middle;
 964         minimum.rx() = qMin(minimum.x(), p.x());
 965         minimum.ry() = qMin(minimum.y(), p.y());
 966         maximum.rx() = qMax(maximum.x(), p.x());
 967         maximum.ry() = qMax(maximum.y(), p.y());
 968     }
 969
 970     int comp, pivot;
 971     if (maximum.x() - minimum.x() > maximum.y() - minimum.y()) {
 972         comp = 0;
 973         pivot = (maximum.x() + minimum.x()) >> 1;
 974     } else {
 975         comp = 1;
 976         pivot = (maximum.y() + minimum.y()) >> 1;
 977     }
 978
 979     int lo = 0;
 980     int hi = elementCount - 1;
 981     while (lo < hi) {
 982         while (lo < hi && (&elements[lo]->middle.rx())[comp] <= pivot)
 983             ++lo;
 984         while (lo < hi && (&elements[hi]->middle.rx())[comp] > pivot)
 985             --hi;
 986         if (lo < hi)
 987             qSwap(elements[lo], elements[hi]);
 988     }
 989
 990     if (lo == elementCount) {
 991         // All points are the same.
 992         Q_ASSERT(minimum.x() == maximum.x() && minimum.y() == maximum.y());
 993         lo = elementCount >> 1;
 994     }
 995
 996     node->left = buildTree(elements, lo);
 997     node->right = buildTree(elements + lo, elementCount - lo);
 998
 999     const BVHNode *left = node->left;
1000     const BVHNode *right = node->right;
1001     node->minimum.rx() = qMin(left->minimum.x(), right->minimum.x());
1002     node->minimum.ry() = qMin(left->minimum.y(), right->minimum.y());
1003     node->maximum.rx() = qMax(left->maximum.x(), right->maximum.x());
1004     node->maximum.ry() = qMax(left->maximum.y(), right->maximum.y());
1005
1006     return node;
1007 }
1008
1009 bool PathSimplifier::intersectNodes(QDataBuffer<Element *> &elements, BVHNode *elementNode,
1010                                     BVHNode *treeNode)
1011 {
1012     if (elementNode->minimum.x() >= treeNode->maximum.x()
1013         || elementNode->minimum.y() >= treeNode->maximum.y()
1014         || elementNode->maximum.x() <= treeNode->minimum.x()
1015         || elementNode->maximum.y() <= treeNode->minimum.y())
1016     {
1017         return false;
1018     }
1019
1020     Q_ASSERT(elementNode->type == BVHNode::Leaf);
1021     Element *element = elementNode->element;
1022     Q_ASSERT(!element->processed);
1023
1024     if (treeNode->type == BVHNode::Leaf) {
1025         Element *nodeElement = treeNode->element;
1026         if (!nodeElement->processed)
1027             return false;
1028
1029         if (treeNode->element == elementNode->element)
1030             return false;
1031
1032         if (equalElements(treeNode->element, elementNode->element))
1033             return false; // element doesn't split itself.
1034
1035         if (element->degree == Element::Line && nodeElement->degree == Element::Line) {
1036             const QPoint &u1 = m_points->at(element->indices[0]);
1037             const QPoint &u2 = m_points->at(element->indices[1]);
1038             const QPoint &v1 = m_points->at(nodeElement->indices[0]);
1039             const QPoint &v2 = m_points->at(nodeElement->indices[1]);
1040             IntersectionPoint intersection = intersectionPoint(u1, u2, v1, v2);
1041             if (!intersection.isValid())
1042                 return false;
1043
1044             Q_ASSERT(intersection.x.integer >= qMin(u1.x(), u2.x()));
1045             Q_ASSERT(intersection.y.integer >= qMin(u1.y(), u2.y()));
1046             Q_ASSERT(intersection.x.integer >= qMin(v1.x(), v2.x()));
1047             Q_ASSERT(intersection.y.integer >= qMin(v1.y(), v2.y()));
1048
1049             Q_ASSERT(intersection.x.integer <= qMax(u1.x(), u2.x()));
1050             Q_ASSERT(intersection.y.integer <= qMax(u1.y(), u2.y()));
1051             Q_ASSERT(intersection.x.integer <= qMax(v1.x(), v2.x()));
1052             Q_ASSERT(intersection.y.integer <= qMax(v1.y(), v2.y()));
1053
1054             m_points->add(intersection.round());
1055             splitLineAt(elements, treeNode, m_points->size() - 1, !intersection.isAccurate());
1056             return splitLineAt(elements, elementNode, m_points->size() - 1, false);
1057         } else {
1058             QVarLengthArray<QPoint, 12> axes;
1059             appendSeparatingAxes(axes, elementNode->element);
1060             appendSeparatingAxes(axes, treeNode->element);
1061             for (int i = 0; i < axes.size(); ++i) {
1062                 QPair<int, int> range1 = calculateSeparatingAxisRange(axes.at(i), elementNode->element);
1063                 QPair<int, int> range2 = calculateSeparatingAxisRange(axes.at(i), treeNode->element);
1064                 if (range1.first >= range2.second || range1.second <= range2.first) {
1065                     return false; // Separating axis found.
1066                 }
1067             }
1068             // Bounding areas overlap.
1069             if (nodeElement->degree > Element::Line)
1070                 splitCurve(elements, treeNode);
1071             if (element->degree > Element::Line) {
1072                 splitCurve(elements, elementNode);
1073             } else {
1074                 // The element was not split, so it can be processed further.
1075                 if (intersectNodes(elements, elementNode, treeNode->left))
1076                     return true;
1077                 if (intersectNodes(elements, elementNode, treeNode->right))
1078                     return true;
1079                 return false;
1080             }
1081             return true;
1082         }
1083     } else {
1084         if (intersectNodes(elements, elementNode, treeNode->left))
1085             return true;
1086         if (intersectNodes(elements, elementNode, treeNode->right))
1087             return true;
1088         return false;
1089     }
1090 }
1091
1092 bool PathSimplifier::equalElements(const Element *e1, const Element *e2)
1093 {
1094     Q_ASSERT(e1 != e2);
1095     if (e1->degree != e2->degree)
1096         return false;
1097
1098     // Possibly equal and in the same direction.
1099     bool equalSame = true;
1100     for (int i = 0; i <= e1->degree; ++i)
1101         equalSame &= m_points->at(e1->indices[i]) == m_points->at(e2->indices[i]);
1102
1103     // Possibly equal and in opposite directions.
1104     bool equalOpposite = true;
1105     for (int i = 0; i <= e1->degree; ++i)
1106         equalOpposite &= m_points->at(e1->indices[e1->degree - i]) == m_points->at(e2->indices[i]);
1107
1108     return equalSame || equalOpposite;
1109 }
1110
1111 bool PathSimplifier::splitLineAt(QDataBuffer<Element *> &elements, BVHNode *node,
1112                                  quint32 pointIndex, bool processAgain)
1113 {
1114     Q_ASSERT(node->type == BVHNode::Leaf);
1115     Element *element = node->element;
1116     Q_ASSERT(element->degree == Element::Line);
1117     const QPoint &u = m_points->at(element->indices[0]);
1118     const QPoint &v = m_points->at(element->indices[1]);
1119     const QPoint &p = m_points->at(pointIndex);
1120     if (u == p || v == p)
1121         return false; // No split needed.
1122
1123     if (processAgain)
1124         element->processed = false; // Needs to be processed again.
1125
1126     Element *first = node->element;
1127     Element *second = m_elementAllocator.newElement();
1128     *second = *first;
1129     first->indices[1] = second->indices[0] = pointIndex;
1130     first->middle.rx() = (u.x() + p.x()) >> 1;
1131     first->middle.ry() = (u.y() + p.y()) >> 1;
1132     second->middle.rx() = (v.x() + p.x()) >> 1;
1133     second->middle.ry() = (v.y() + p.y()) >> 1;
1134     m_elements.add(second);
1135
1136     BVHNode *left = m_bvh.newNode();
1137     BVHNode *right = m_bvh.newNode();
1138     left->type = right->type = BVHNode::Leaf;
1139     left->element = first;
1140     right->element = second;
1141     left->minimum = right->minimum = node->minimum;
1142     left->maximum = right->maximum = node->maximum;
1143     if (u.x() < v.x())
1144         left->maximum.rx() = right->minimum.rx() = p.x();
1145     else
1146         left->minimum.rx() = right->maximum.rx() = p.x();
1147     if (u.y() < v.y())
1148         left->maximum.ry() = right->minimum.ry() = p.y();
1149     else
1150         left->minimum.ry() = right->maximum.ry() = p.y();
1151     left->element->bvhNode = left;
1152     right->element->bvhNode = right;
1153
1154     node->type = BVHNode::Split;
1155     node->left = left;
1156     node->right = right;
1157
1158     if (!first->processed) {
1159         elements.add(left->element);
1160         elements.add(right->element);
1161     }
1162     return true;
1163 }
1164
1165 void PathSimplifier::appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes, Element *element)
1166 {
1167     switch (element->degree) {
1168     case Element::Cubic:
1169         {
1170             const QPoint &u = m_points->at(element->indices[0]);
1171             const QPoint &v = m_points->at(element->indices[1]);
1172             const QPoint &w = m_points->at(element->indices[2]);
1173             const QPoint &q = m_points->at(element->indices[3]);
1174             QPoint ns[] = {
1175                 QPoint(u.y() - v.y(), v.x() - u.x()),
1176                 QPoint(v.y() - w.y(), w.x() - v.x()),
1177                 QPoint(w.y() - q.y(), q.x() - w.x()),
1178                 QPoint(q.y() - u.y(), u.x() - q.x()),
1179                 QPoint(u.y() - w.y(), w.x() - u.x()),
1180                 QPoint(v.y() - q.y(), q.x() - v.x())
1181             };
1182             for (int i = 0; i < 6; ++i) {
1183                 if (ns[i].x() || ns[i].y())
1184                     axes.append(ns[i]);
1185             }
1186         }
1187         break;
1188     case Element::Quadratic:
1189         {
1190             const QPoint &u = m_points->at(element->indices[0]);
1191             const QPoint &v = m_points->at(element->indices[1]);
1192             const QPoint &w = m_points->at(element->indices[2]);
1193             QPoint ns[] = {
1194                 QPoint(u.y() - v.y(), v.x() - u.x()),
1195                 QPoint(v.y() - w.y(), w.x() - v.x()),
1196                 QPoint(w.y() - u.y(), u.x() - w.x())
1197             };
1198             for (int i = 0; i < 3; ++i) {
1199                 if (ns[i].x() || ns[i].y())
1200                     axes.append(ns[i]);
1201             }
1202         }
1203         break;
1204     case Element::Line:
1205         {
1206             const QPoint &u = m_points->at(element->indices[0]);
1207             const QPoint &v = m_points->at(element->indices[1]);
1208             QPoint n(u.y() - v.y(), v.x() - u.x());
1209             if (n.x() || n.y())
1210                 axes.append(n);
1211         }
1212         break;
1213     default:
1214         Q_ASSERT_X(0, "QSGPathSimplifier::appendSeparatingAxes", "Unexpected element type.");
1215         break;
1216     }
1217 }
1218
1219 QPair<int, int> PathSimplifier::calculateSeparatingAxisRange(const QPoint &axis, Element *element)
1220 {
1221     QPair<int, int> range(0x7fffffff, -0x7fffffff);
1222     for (int i = 0; i <= element->degree; ++i) {
1223         const QPoint &p = m_points->at(element->indices[i]);
1224         int dist = dot(axis, p);
1225         range.first = qMin(range.first, dist);
1226         range.second = qMax(range.second, dist);
1227     }
1228     return range;
1229 }
1230
1231 void PathSimplifier::splitCurve(QDataBuffer<Element *> &elements, BVHNode *node)
1232 {
1233     Q_ASSERT(node->type == BVHNode::Leaf);
1234
1235     Element *first = node->element;
1236     Element *second = m_elementAllocator.newElement();
1237     *second = *first;
1238     m_elements.add(second);
1239     Q_ASSERT(first->degree > Element::Line);
1240
1241     bool accurate = true;
1242     const QPoint &u = m_points->at(first->indices[0]);
1243     const QPoint &v = m_points->at(first->indices[1]);
1244     const QPoint &w = m_points->at(first->indices[2]);
1245
1246     if (first->degree == Element::Quadratic) {
1247         QPoint pts[3];
1248         accurate = splitQuadratic(u, v, w, pts);
1249         int pointIndex = m_points->size();
1250         m_points->add(pts[1]);
1251         accurate &= setElementToQuadratic(first, first->indices[0], pts[0], pointIndex);
1252         accurate &= setElementToQuadratic(second, pointIndex, pts[2], second->indices[2]);
1253     } else {
1254         Q_ASSERT(first->degree == Element::Cubic);
1255         const QPoint &q = m_points->at(first->indices[3]);
1256         QPoint pts[5];
1257         accurate = splitCubic(u, v, w, q, pts);
1258         int pointIndex = m_points->size();
1259         m_points->add(pts[2]);
1260         accurate &= setElementToCubic(first, first->indices[0], pts[0], pts[1], pointIndex);
1261         accurate &= setElementToCubic(second, pointIndex, pts[3], pts[4], second->indices[3]);
1262     }
1263
1264     if (!accurate)
1265         first->processed = second->processed = false; // Needs to be processed again.
1266
1267     BVHNode *left = m_bvh.newNode();
1268     BVHNode *right = m_bvh.newNode();
1269     left->type = right->type = BVHNode::Leaf;
1270     left->element = first;
1271     right->element = second;
1272
1273     left->minimum.rx() = left->minimum.ry() = right->minimum.rx() = right->minimum.ry() = INT_MAX;
1274     left->maximum.rx() = left->maximum.ry() = right->maximum.rx() = right->maximum.ry() = INT_MIN;
1275
1276     for (int i = 0; i <= first->degree; ++i) {
1277         QPoint &p = m_points->at(first->indices[i]);
1278         left->minimum.rx() = qMin(left->minimum.x(), p.x());
1279         left->minimum.ry() = qMin(left->minimum.y(), p.y());
1280         left->maximum.rx() = qMax(left->maximum.x(), p.x());
1281         left->maximum.ry() = qMax(left->maximum.y(), p.y());
1282     }
1283     for (int i = 0; i <= second->degree; ++i) {
1284         QPoint &p = m_points->at(second->indices[i]);
1285         right->minimum.rx() = qMin(right->minimum.x(), p.x());
1286         right->minimum.ry() = qMin(right->minimum.y(), p.y());
1287         right->maximum.rx() = qMax(right->maximum.x(), p.x());
1288         right->maximum.ry() = qMax(right->maximum.y(), p.y());
1289     }
1290     left->element->bvhNode = left;
1291     right->element->bvhNode = right;
1292
1293     node->type = BVHNode::Split;
1294     node->left = left;
1295     node->right = right;
1296
1297     if (!first->processed) {
1298         elements.add(left->element);
1299         elements.add(right->element);
1300     }
1301 }
1302
1303 bool PathSimplifier::setElementToQuadratic(Element *element, quint32 pointIndex1,
1304                                            const QPoint &ctrl, quint32 pointIndex2)
1305 {
1306     const QPoint &p1 = m_points->at(pointIndex1);
1307     const QPoint &p2 = m_points->at(pointIndex2);
1308     if (flattenQuadratic(p1, ctrl, p2)) {
1309         // Insert line.
1310         element->degree = Element::Line;
1311         element->indices[0] = pointIndex1;
1312         element->indices[1] = pointIndex2;
1313         element->middle.rx() = (p1.x() + p2.x()) >> 1;
1314         element->middle.ry() = (p1.y() + p2.y()) >> 1;
1315         return false;
1316     } else {
1317         // Insert bezier.
1318         element->degree = Element::Quadratic;
1319         element->indices[0] = pointIndex1;
1320         element->indices[1] = m_points->size();
1321         element->indices[2] = pointIndex2;
1322         element->middle.rx() = (p1.x() + ctrl.x() + p2.x()) / 3;
1323         element->middle.ry() = (p1.y() + ctrl.y() + p2.y()) / 3;
1324         m_points->add(ctrl);
1325         return true;
1326     }
1327 }
1328
1329 bool PathSimplifier::setElementToCubic(Element *element, quint32 pointIndex1, const QPoint &v,
1330                                        const QPoint &w, quint32 pointIndex2)
1331 {
1332     const QPoint &u = m_points->at(pointIndex1);
1333     const QPoint &q = m_points->at(pointIndex2);
1334     if (flattenCubic(u, v, w, q)) {
1335         // Insert line.
1336         element->degree = Element::Line;
1337         element->indices[0] = pointIndex1;
1338         element->indices[1] = pointIndex2;
1339         element->middle.rx() = (u.x() + q.x()) >> 1;
1340         element->middle.ry() = (u.y() + q.y()) >> 1;
1341         return false;
1342     } else {
1343         // Insert bezier.
1344         element->degree = Element::Cubic;
1345         element->indices[0] = pointIndex1;
1346         element->indices[1] = m_points->size();
1347         element->indices[2] = m_points->size() + 1;
1348         element->indices[3] = pointIndex2;
1349         element->middle.rx() = (u.x() + v.x() + w.x() + q.x()) >> 2;
1350         element->middle.ry() = (u.y() + v.y() + w.y() + q.y()) >> 2;
1351         m_points->add(v);
1352         m_points->add(w);
1353         return true;
1354     }
1355 }
1356
1357 void PathSimplifier::setElementToCubicAndSimplify(Element *element, quint32 pointIndex1,
1358                                                   const QPoint &v, const QPoint &w,
1359                                                   quint32 pointIndex2)
1360 {
1361     const QPoint &u = m_points->at(pointIndex1);
1362     const QPoint &q = m_points->at(pointIndex2);
1363     if (flattenCubic(u, v, w, q)) {
1364         // Insert line.
1365         element->degree = Element::Line;
1366         element->indices[0] = pointIndex1;
1367         element->indices[1] = pointIndex2;
1368         element->middle.rx() = (u.x() + q.x()) >> 1;
1369         element->middle.ry() = (u.y() + q.y()) >> 1;
1370         return;
1371     }
1372
1373     bool intersecting = (u == q) || intersectionPoint(u, v, w, q).isValid();
1374     if (!intersecting) {
1375         // Insert bezier.
1376         element->degree = Element::Cubic;
1377         element->indices[0] = pointIndex1;
1378         element->indices[1] = m_points->size();
1379         element->indices[2] = m_points->size() + 1;
1380         element->indices[3] = pointIndex2;
1381         element->middle.rx() = (u.x() + v.x() + w.x() + q.x()) >> 2;
1382         element->middle.ry() = (u.y() + v.y() + w.y() + q.y()) >> 2;
1383         m_points->add(v);
1384         m_points->add(w);
1385         return;
1386     }
1387
1388     QPoint pts[5];
1389     splitCubic(u, v, w, q, pts);
1390     int pointIndex = m_points->size();
1391     m_points->add(pts[2]);
1392     Element *element2 = m_elementAllocator.newElement();
1393     m_elements.add(element2);
1394     setElementToCubicAndSimplify(element, pointIndex1, pts[0], pts[1], pointIndex);
1395     setElementToCubicAndSimplify(element2, pointIndex, pts[3], pts[4], pointIndex2);
1396 }
1397
1398 PathSimplifier::RBNode *PathSimplifier::findElementLeftOf(const Element *element,
1399                                                           const QPair<RBNode *, RBNode *> &bounds)
1400 {
1401     if (!m_elementList.root)
1402         return 0;
1403     RBNode *current = bounds.first;
1404     Q_ASSERT(!current || !elementIsLeftOf(element, current->data));
1405     if (!current)
1406         current = m_elementList.front(m_elementList.root);
1407     Q_ASSERT(current);
1408     RBNode *result = 0;
1409     while (current != bounds.second && !elementIsLeftOf(element, current->data)) {
1410         result = current;
1411         current = m_elementList.next(current);
1412     }
1413     return result;
1414 }
1415
1416 bool PathSimplifier::elementIsLeftOf(const Element *left, const Element *right)
1417 {
1418     const QPoint &leftU = m_points->at(left->upperIndex());
1419     const QPoint &leftL = m_points->at(left->lowerIndex());
1420     const QPoint &rightU = m_points->at(right->upperIndex());
1421     const QPoint &rightL = m_points->at(right->lowerIndex());
1422     Q_ASSERT(leftL >= rightU && rightL >= leftU);
1423     if (leftU.x() < qMin(rightL.x(), rightU.x()))
1424         return true;
1425     if (leftU.x() > qMax(rightL.x(), rightU.x()))
1426         return false;
1427     int d = pointDistanceFromLine(leftU, rightL, rightU);
1428     // d < 0: left, d > 0: right, d == 0: on top
1429     if (d == 0) {
1430         d = pointDistanceFromLine(leftL, rightL, rightU);
1431         if (d == 0) {
1432             if (right->degree > Element::Line) {
1433                 d = pointDistanceFromLine(leftL, rightL, m_points->at(right->indices[1]));
1434                 if (d == 0)
1435                     d = pointDistanceFromLine(leftL, rightL, m_points->at(right->indices[2]));
1436             } else if (left->degree > Element::Line) {
1437                 d = pointDistanceFromLine(m_points->at(left->indices[1]), rightL, rightU);
1438                 if (d == 0)
1439                     d = pointDistanceFromLine(m_points->at(left->indices[2]), rightL, rightU);
1440             }
1441         }
1442     }
1443     return d < 0;
1444 }
1445
1446 QPair<PathSimplifier::RBNode *, PathSimplifier::RBNode *> PathSimplifier::outerBounds(const QPoint &point)
1447 {
1448     RBNode *current = m_elementList.root;
1449     QPair<RBNode *, RBNode *> result(0, 0);
1450
1451     while (current) {
1452         const Element *element = current->data;
1453         Q_ASSERT(element->edgeNode == current);
1454         const QPoint &v1 = m_points->at(element->lowerIndex());
1455         const QPoint &v2 = m_points->at(element->upperIndex());
1456         Q_ASSERT(point >= v2 && point <= v1);
1457         if (point == v1 || point == v2)
1458             break;
1459         int d = pointDistanceFromLine(point, v1, v2);
1460         if (d == 0) {
1461             if (element->degree == Element::Line)
1462                 break;
1463             d = pointDistanceFromLine(point, v1, m_points->at(element->indices[1]));
1464             if (d == 0)
1465                 d = pointDistanceFromLine(point, v1, m_points->at(element->indices[2]));
1466             Q_ASSERT(d != 0);
1467         }
1468         if (d < 0) {
1469             result.second = current;
1470             current = current->left;
1471         } else {
1472             result.first = current;
1473             current = current->right;
1474         }
1475     }
1476
1477     if (!current)
1478         return result;
1479
1480     RBNode *mid = current;
1481
1482     current = mid->left;
1483     while (current) {
1484         const Element *element = current->data;
1485         Q_ASSERT(element->edgeNode == current);
1486         const QPoint &v1 = m_points->at(element->lowerIndex());
1487         const QPoint &v2 = m_points->at(element->upperIndex());
1488         Q_ASSERT(point >= v2 && point <= v1);
1489         bool equal = (point == v1 || point == v2);
1490         if (!equal) {
1491             int d = pointDistanceFromLine(point, v1, v2);
1492             Q_ASSERT(d >= 0);
1493             equal = (d == 0 && element->degree == Element::Line);
1494         }
1495         if (equal) {
1496             current = current->left;
1497         } else {
1498             result.first = current;
1499             current = current->right;
1500         }
1501     }
1502
1503     current = mid->right;
1504     while (current) {
1505         const Element *element = current->data;
1506         Q_ASSERT(element->edgeNode == current);
1507         const QPoint &v1 = m_points->at(element->lowerIndex());
1508         const QPoint &v2 = m_points->at(element->upperIndex());
1509         Q_ASSERT(point >= v2 && point <= v1);
1510         bool equal = (point == v1 || point == v2);
1511         if (!equal) {
1512             int d = pointDistanceFromLine(point, v1, v2);
1513             Q_ASSERT(d <= 0);
1514             equal = (d == 0 && element->degree == Element::Line);
1515         }
1516         if (equal) {
1517             current = current->right;
1518         } else {
1519             result.second = current;
1520             current = current->left;
1521         }
1522     }
1523
1524     return result;
1525 }
1526
1527 inline bool PathSimplifier::flattenQuadratic(const QPoint &u, const QPoint &v, const QPoint &w)
1528 {
1529     QPoint deltas[2] = { v - u, w - v };
1530     int d = qAbs(cross(deltas[0], deltas[1]));
1531     int l = qAbs(deltas[0].x()) + qAbs(deltas[0].y()) + qAbs(deltas[1].x()) + qAbs(deltas[1].y());
1532     return d < (Q_FIXED_POINT_SCALE * Q_FIXED_POINT_SCALE * 3 / 2) || l <= Q_FIXED_POINT_SCALE * 2;
1533 }
1534
1535 inline bool PathSimplifier::flattenCubic(const QPoint &u, const QPoint &v,
1536                                          const QPoint &w, const QPoint &q)
1537 {
1538     QPoint deltas[] = { v - u, w - v, q - w, q - u };
1539     int d = qAbs(cross(deltas[0], deltas[1])) + qAbs(cross(deltas[1], deltas[2]))
1540             + qAbs(cross(deltas[0], deltas[3])) + qAbs(cross(deltas[3], deltas[2]));
1541     int l = qAbs(deltas[0].x()) + qAbs(deltas[0].y()) + qAbs(deltas[1].x()) + qAbs(deltas[1].y())
1542             + qAbs(deltas[2].x()) + qAbs(deltas[2].y());
1543     return d < (Q_FIXED_POINT_SCALE * Q_FIXED_POINT_SCALE * 3) || l <= Q_FIXED_POINT_SCALE * 2;
1544 }
1545
1546 inline bool PathSimplifier::splitQuadratic(const QPoint &u, const QPoint &v,
1547                                            const QPoint &w, QPoint *result)
1548 {
1549     result[0] = u + v;
1550     result[2] = v + w;
1551     result[1] = result[0] + result[2];
1552     bool accurate = ((result[0].x() | result[0].y() | result[2].x() | result[2].y()) & 1) == 0
1553                     && ((result[1].x() | result[1].y()) & 3) == 0;
1554     result[0].rx() >>= 1;
1555     result[0].ry() >>= 1;
1556     result[1].rx() >>= 2;
1557     result[1].ry() >>= 2;
1558     result[2].rx() >>= 1;
1559     result[2].ry() >>= 1;
1560     return accurate;
1561 }
1562
1563 inline bool PathSimplifier::splitCubic(const QPoint &u, const QPoint &v,
1564                                        const QPoint &w, const QPoint &q, QPoint *result)
1565 {
1566     result[0] = u + v;
1567     result[2] = v + w;
1568     result[4] = w + q;
1569     result[1] = result[0] + result[2];
1570     result[3] = result[2] + result[4];
1571     result[2] = result[1] + result[3];
1572     bool accurate = ((result[0].x() | result[0].y() | result[4].x() | result[4].y()) & 1) == 0
1573                     && ((result[1].x() | result[1].y() | result[3].x() | result[3].y()) & 3) == 0
1574                     && ((result[2].x() | result[2].y()) & 7) == 0;
1575     result[0].rx() >>= 1;
1576     result[0].ry() >>= 1;
1577     result[1].rx() >>= 2;
1578     result[1].ry() >>= 2;
1579     result[2].rx() >>= 3;
1580     result[2].ry() >>= 3;
1581     result[3].rx() >>= 2;
1582     result[3].ry() >>= 2;
1583     result[4].rx() >>= 1;
1584     result[4].ry() >>= 1;
1585     return accurate;
1586 }
1587
1588 inline void PathSimplifier::subDivQuadratic(const QPoint &u, const QPoint &v, const QPoint &w)
1589 {
1590     if (flattenQuadratic(u, v, w))
1591         return;
1592     QPoint pts[3];
1593     splitQuadratic(u, v, w, pts);
1594     subDivQuadratic(u, pts[0], pts[1]);
1595     m_indices->add(m_points->size());
1596     m_points->add(pts[1]);
1597     subDivQuadratic(pts[1], pts[2], w);
1598 }
1599
1600 inline void PathSimplifier::subDivCubic(const QPoint &u, const QPoint &v,
1601                                         const QPoint &w, const QPoint &q)
1602 {
1603     if (flattenCubic(u, v, w, q))
1604         return;
1605     QPoint pts[5];
1606     splitCubic(u, v, w, q, pts);
1607     subDivCubic(u, pts[0], pts[1], pts[2]);
1608     m_indices->add(m_points->size());
1609     m_points->add(pts[2]);
1610     subDivCubic(pts[2], pts[3], pts[4], q);
1611 }
1612
1613 void PathSimplifier::sortEvents(Event *events, int count)
1614 {
1615     // Bucket sort + insertion sort.
1616     Q_ASSERT(count > 0);
1617     QDataBuffer<Event> buffer(count);
1618     buffer.resize(count);
1619     QScopedArrayPointer<int> bins(new int[count]);
1620     int counts[0x101];
1621     memset(counts, 0, sizeof(counts));
1622
1623     int minimum, maximum;
1624     minimum = maximum = events[0].point.y();
1625     for (int i = 1; i < count; ++i) {
1626         minimum = qMin(minimum, events[i].point.y());
1627         maximum = qMax(maximum, events[i].point.y());
1628     }
1629
1630     for (int i = 0; i < count; ++i) {
1631         bins[i] = ((maximum - events[i].point.y()) << 8) / (maximum - minimum + 1);
1632         Q_ASSERT(bins[i] >= 0 && bins[i] < 0x100);
1633         ++counts[bins[i]];
1634     }
1635
1636     for (int i = 1; i < 0x100; ++i)
1637         counts[i] += counts[i - 1];
1638     counts[0x100] = counts[0xff];
1639     Q_ASSERT(counts[0x100] == count);
1640
1641     for (int i = 0; i < count; ++i)
1642         buffer.at(--counts[bins[i]]) = events[i];
1643
1644     int j = 0;
1645     for (int i = 0; i < 0x100; ++i) {
1646         for (; j < counts[i + 1]; ++j) {
1647             int k = j;
1648             while (k > 0 && (buffer.at(j) < events[k - 1])) {
1649                 events[k] = events[k - 1];
1650                 --k;
1651             }
1652             events[k] = buffer.at(j);
1653         }
1654     }
1655 }
1656
1657 } // end anonymous namespace
1658
1659
1660 void qSimplifyPath(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
1661                    QDataBuffer<quint32> &indices, const QTransform &matrix)
1662 {
1663     PathSimplifier(path, vertices, indices, matrix);
1664 }
1665
1666 void qSimplifyPath(const QPainterPath &path, QDataBuffer<QPoint> &vertices,
1667                    QDataBuffer<quint32> &indices, const QTransform &matrix)
1668 {
1669     qSimplifyPath(qtVectorPathForPath(path), vertices, indices, matrix);
1670 }
1671
1672
1673 QT_END_NAMESPACE