1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
6 ** This file is part of the QtQml module of the Qt Toolkit.
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.
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.
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.
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.
40 ****************************************************************************/
42 #include "qsgpathsimplifier_p.h"
44 #include <QtCore/qvarlengtharray.h>
45 #include <QtCore/qglobal.h>
46 #include <QtCore/qpoint.h>
47 #include <QtCore/qalgorithms.h>
51 #include <private/qopengl_p.h>
52 #include <private/qrbtree_p.h>
56 #define Q_FIXED_POINT_SCALE 256
57 #define Q_TRIANGULATE_END_OF_POLYGON quint32(-1)
62 //============================================================================//
64 //============================================================================//
66 inline bool operator < (const QPoint &a, const QPoint &b)
68 return a.y() < b.y() || (a.y() == b.y() && a.x() < b.x());
71 inline bool operator > (const QPoint &a, const QPoint &b)
76 inline bool operator <= (const QPoint &a, const QPoint &b)
81 inline bool operator >= (const QPoint &a, const QPoint &b)
86 inline int cross(const QPoint &u, const QPoint &v)
88 return u.x() * v.y() - u.y() * v.x();
91 inline int dot(const QPoint &u, const QPoint &v)
93 return u.x() * v.x() + u.y() * v.y();
96 //============================================================================//
98 //============================================================================//
100 // Fraction must be in the range [0, 1)
103 bool isValid() const { return denominator != 0; }
105 // numerator and denominator must not have common denominators.
106 unsigned int numerator, denominator;
109 inline unsigned int gcd(unsigned int x, unsigned int y)
119 // Fraction must be in the range [0, 1)
120 // Assume input is valid.
121 Fraction fraction(unsigned int n, unsigned int d) {
124 result.numerator = 0;
125 result.denominator = 1;
127 unsigned int g = gcd(n, d);
128 result.numerator = n / g;
129 result.denominator = d / g;
134 //============================================================================//
136 //============================================================================//
140 bool isValid() const { return fraction.isValid(); }
145 //============================================================================//
146 // IntersectionPoint //
147 //============================================================================//
149 struct IntersectionPoint
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; }
155 Rational x; // 8:8 signed, 32/32
156 Rational y; // 8:8 signed, 32/32
159 QPoint IntersectionPoint::round() const
161 QPoint result(x.integer, y.integer);
162 if (2 * x.fraction.numerator >= x.fraction.denominator)
164 if (2 * y.fraction.numerator >= y.fraction.denominator)
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)
175 return cross(v2 - v1, p - v1);
178 IntersectionPoint intersectionPoint(const QPoint &u1, const QPoint &u2,
179 const QPoint &v1, const QPoint &v2)
181 IntersectionPoint result = {{0, {0, 0}}, {0, {0, 0}}};
185 int d1 = cross(u, v1 - u1);
186 int d2 = cross(u, v2 - u1);
188 int d3 = cross(v, u1 - v1);
189 int d4 = d3 - det; //qCross(v, u2 - v1);
191 // Check that the math is correct.
192 Q_ASSERT(d4 == cross(v, u2 - v1));
194 // The intersection point can be expressed as:
200 // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.
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)
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)
221 // Assuming 16 bits per vector component.
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);
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);
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);
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);
238 Q_ASSERT(result.x.fraction.isValid());
239 Q_ASSERT(result.y.fraction.isValid());
243 //============================================================================//
245 //============================================================================//
250 PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
251 QDataBuffer<quint32> &indices, const QTransform &matrix);
256 class BoundingVolumeHierarchy
270 Element *element; // type == Leaf
271 Node *left; // type == Split
276 BoundingVolumeHierarchy();
277 ~BoundingVolumeHierarchy();
278 void allocate(int nodeCount);
284 void freeNode(Node *n);
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]; }
307 quint32 indices[4]; // index to points
308 Element *next, *previous; // used in connectElements()
309 int winding; // used in connectElements()
311 QRBTree<Element *>::Node *edgeNode; // used in connectElements()
312 BoundingVolumeHierarchy::Node *bvhNode;
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()
320 class ElementAllocator
325 void allocate(int count);
326 Element *newElement();
339 enum Type { Upper, Lower };
340 bool operator < (const Event &other) const;
347 typedef QRBTree<Element *>::Node RBNode;
348 typedef BoundingVolumeHierarchy::Node BVHNode;
350 void initElements(const QVectorPath &path, const QTransform &matrix);
351 void removeIntersections();
352 void connectElements();
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);
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;
384 inline PathSimplifier::BoundingVolumeHierarchy::BoundingVolumeHierarchy()
392 inline PathSimplifier::BoundingVolumeHierarchy::~BoundingVolumeHierarchy()
397 inline void PathSimplifier::BoundingVolumeHierarchy::allocate(int nodeCount)
399 Q_ASSERT(nodeBlock == 0);
400 Q_ASSERT(firstFree == 0);
401 nodeBlock = new Node[blockSize = nodeCount];
404 inline void PathSimplifier::BoundingVolumeHierarchy::free()
409 firstFree = blockSize = 0;
413 inline PathSimplifier::BVHNode *PathSimplifier::BoundingVolumeHierarchy::newNode()
415 if (firstFree < blockSize)
416 return &nodeBlock[firstFree++];
420 inline void PathSimplifier::BoundingVolumeHierarchy::freeNode(Node *n)
424 Q_ASSERT(n->type == Node::Split || n->type == Node::Leaf);
425 if (n->type == Node::Split) {
429 if (!(n >= nodeBlock && n < nodeBlock + blockSize))
433 inline PathSimplifier::ElementAllocator::ElementAllocator()
438 inline PathSimplifier::ElementAllocator::~ElementAllocator()
441 ElementBlock *block = blocks;
442 blocks = blocks->next;
447 inline void PathSimplifier::ElementAllocator::allocate(int count)
449 Q_ASSERT(blocks == 0);
451 blocks = (ElementBlock *)malloc(sizeof(ElementBlock) + (count - 1) * sizeof(Element));
452 blocks->blockSize = count;
454 blocks->firstFree = 0;
457 inline PathSimplifier::Element *PathSimplifier::ElementAllocator::newElement()
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++];
471 inline bool PathSimplifier::Event::operator < (const Event &other) const
473 if (point == other.point)
474 return type < other.type;
475 return other.point < point;
478 inline void PathSimplifier::Element::flip()
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]);
485 pointingUp = !pointingUp;
486 Q_ASSERT(next == 0 && previous == 0);
489 PathSimplifier::PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
490 QDataBuffer<quint32> &indices, const QTransform &matrix)
492 , m_points(&vertices)
493 , m_indices(&indices)
497 initElements(path, matrix);
498 if (!m_elements.isEmpty()) {
499 removeIntersections();
505 void PathSimplifier::initElements(const QVectorPath &path, const QTransform &matrix)
507 m_hints = path.hints();
508 int pathElementCount = path.elementCount();
509 if (pathElementCount == 0)
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();
518 quint32 moveToIndex = 0;
519 quint32 previousIndex = 0;
520 for (int i = 0; i < pathElementCount; ++i, ++e, p += 2) {
522 case QPainterPath::MoveToElement:
524 if (!m_points->isEmpty()) {
525 const QPoint &from = m_points->at(previousIndex);
526 const QPoint &to = m_points->at(moveToIndex);
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);
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));
543 case QPainterPath::LineToElement:
544 Q_ASSERT(!m_points->isEmpty());
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();
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();
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);
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();
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]);
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);
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,
598 m_elements.add(element);
606 Q_ASSERT_X(0, "QSGPathSimplifier::initialize", "Unexpected element type.");
610 if (!m_points->isEmpty()) {
611 const QPoint &from = m_points->at(previousIndex);
612 const QPoint &to = m_points->at(moveToIndex);
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);
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())
633 while (!m_points->isEmpty() && m_points->last() == m_points->first())
634 m_points->pop_back();
636 if (m_points->isEmpty())
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);
654 for (int i = 0; i < m_elements.size(); ++i)
655 m_elements.at(i)->processed = false;
658 void PathSimplifier::removeIntersections()
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());
668 for (int i = 0; i < m_elements.size(); ++i)
669 elements.add(m_elements.at(i));
671 while (!elements.isEmpty()) {
672 Element *element = elements.last();
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;
683 m_bvh.free(); // The bounding volume hierarchy is not needed anymore.
686 void PathSimplifier::connectElements()
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]);
698 element->pointingUp = element->originallyPointingUp = v < u;
701 event.element = element;
703 event.type = element->pointingUp ? Event::Lower : Event::Upper;
706 event.type = element->pointingUp ? Event::Upper : Event::Lower;
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;
717 // Find all elements passing through the event point.
718 QPair<RBNode *, RBNode *> bounds = outerBounds(eventPoint);
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);
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;
742 if (element2->pointingUp != element->pointingUp)
744 element2->winding = element->winding;
745 int winding = element->winding;
746 if (element->originallyPointingUp)
748 if (winding == 0 || winding == 1) {
749 if (element->pointingUp) {
750 element->previous = event2->element;
751 element2->next = event->element;
753 element->next = event2->element;
754 element2->previous = event->element;
760 orderedElements.clear();
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)
772 const QPoint &lower = m_points->at(element->lowerIndex());
773 if (lower == eventPoint) {
774 if (winding == 0 || winding == 1)
775 orderedElements.append(current->data);
777 // The element is passing through 'event.point'.
778 Q_ASSERT(m_points->at(element->upperIndex()) != eventPoint);
779 Q_ASSERT(element->degree == Element::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));
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)
798 if (winding == 0 || winding == 1)
799 orderedElements.append(upperElement);
800 m_elements.add(upperElement);
802 current = m_elementList.next(current);
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);
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);
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;
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) {
843 element->winding = winding;
846 current = m_elementList.next(current);
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)
859 if (winding == 0 || winding == 1)
860 orderedElements.append(current->data);
861 current = m_elementList.previous(current);
865 if (!orderedElements.isEmpty()) {
866 Q_ASSERT((orderedElements.size() & 1) == 0);
868 Element *firstElement = orderedElements.at(0);
869 if (m_points->at(firstElement->indices[0]) != eventPoint) {
870 orderedElements.append(firstElement);
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;
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));
894 void PathSimplifier::fillIndices()
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)
903 m_indices->add(element->indices[0]);
904 switch (element->degree) {
905 case Element::Quadratic:
908 m_points->at(element->indices[0]),
909 m_points->at(element->indices[1]),
910 m_points->at(element->indices[2])
912 subDivQuadratic(pts[0], pts[1], pts[2]);
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])
923 subDivCubic(pts[0], pts[1], pts[2], pts[3]);
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);
937 PathSimplifier::BVHNode *PathSimplifier::buildTree(Element **elements, int elementCount)
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());
957 node->type = BVHNode::Split;
959 QPoint minimum, maximum;
960 minimum = maximum = elements[0]->middle;
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());
971 if (maximum.x() - minimum.x() > maximum.y() - minimum.y()) {
973 pivot = (maximum.x() + minimum.x()) >> 1;
976 pivot = (maximum.y() + minimum.y()) >> 1;
980 int hi = elementCount - 1;
982 while (lo < hi && (&elements[lo]->middle.rx())[comp] <= pivot)
984 while (lo < hi && (&elements[hi]->middle.rx())[comp] > pivot)
987 qSwap(elements[lo], elements[hi]);
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;
996 node->left = buildTree(elements, lo);
997 node->right = buildTree(elements + lo, elementCount - lo);
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());
1009 bool PathSimplifier::intersectNodes(QDataBuffer<Element *> &elements, BVHNode *elementNode,
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())
1020 Q_ASSERT(elementNode->type == BVHNode::Leaf);
1021 Element *element = elementNode->element;
1022 Q_ASSERT(!element->processed);
1024 if (treeNode->type == BVHNode::Leaf) {
1025 Element *nodeElement = treeNode->element;
1026 if (!nodeElement->processed)
1029 if (treeNode->element == elementNode->element)
1032 if (equalElements(treeNode->element, elementNode->element))
1033 return false; // element doesn't split itself.
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())
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()));
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()));
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);
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.
1068 // Bounding areas overlap.
1069 if (nodeElement->degree > Element::Line)
1070 splitCurve(elements, treeNode);
1071 if (element->degree > Element::Line) {
1072 splitCurve(elements, elementNode);
1074 // The element was not split, so it can be processed further.
1075 if (intersectNodes(elements, elementNode, treeNode->left))
1077 if (intersectNodes(elements, elementNode, treeNode->right))
1084 if (intersectNodes(elements, elementNode, treeNode->left))
1086 if (intersectNodes(elements, elementNode, treeNode->right))
1092 bool PathSimplifier::equalElements(const Element *e1, const Element *e2)
1095 if (e1->degree != e2->degree)
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]);
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]);
1108 return equalSame || equalOpposite;
1111 bool PathSimplifier::splitLineAt(QDataBuffer<Element *> &elements, BVHNode *node,
1112 quint32 pointIndex, bool processAgain)
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.
1124 element->processed = false; // Needs to be processed again.
1126 Element *first = node->element;
1127 Element *second = m_elementAllocator.newElement();
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);
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;
1144 left->maximum.rx() = right->minimum.rx() = p.x();
1146 left->minimum.rx() = right->maximum.rx() = p.x();
1148 left->maximum.ry() = right->minimum.ry() = p.y();
1150 left->minimum.ry() = right->maximum.ry() = p.y();
1151 left->element->bvhNode = left;
1152 right->element->bvhNode = right;
1154 node->type = BVHNode::Split;
1156 node->right = right;
1158 if (!first->processed) {
1159 elements.add(left->element);
1160 elements.add(right->element);
1165 void PathSimplifier::appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes, Element *element)
1167 switch (element->degree) {
1168 case Element::Cubic:
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]);
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())
1182 for (int i = 0; i < 6; ++i) {
1183 if (ns[i].x() || ns[i].y())
1188 case Element::Quadratic:
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]);
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())
1198 for (int i = 0; i < 3; ++i) {
1199 if (ns[i].x() || ns[i].y())
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());
1214 Q_ASSERT_X(0, "QSGPathSimplifier::appendSeparatingAxes", "Unexpected element type.");
1219 QPair<int, int> PathSimplifier::calculateSeparatingAxisRange(const QPoint &axis, Element *element)
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);
1231 void PathSimplifier::splitCurve(QDataBuffer<Element *> &elements, BVHNode *node)
1233 Q_ASSERT(node->type == BVHNode::Leaf);
1235 Element *first = node->element;
1236 Element *second = m_elementAllocator.newElement();
1238 m_elements.add(second);
1239 Q_ASSERT(first->degree > Element::Line);
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]);
1246 if (first->degree == Element::Quadratic) {
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]);
1254 Q_ASSERT(first->degree == Element::Cubic);
1255 const QPoint &q = m_points->at(first->indices[3]);
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]);
1265 first->processed = second->processed = false; // Needs to be processed again.
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;
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;
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());
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());
1290 left->element->bvhNode = left;
1291 right->element->bvhNode = right;
1293 node->type = BVHNode::Split;
1295 node->right = right;
1297 if (!first->processed) {
1298 elements.add(left->element);
1299 elements.add(right->element);
1303 bool PathSimplifier::setElementToQuadratic(Element *element, quint32 pointIndex1,
1304 const QPoint &ctrl, quint32 pointIndex2)
1306 const QPoint &p1 = m_points->at(pointIndex1);
1307 const QPoint &p2 = m_points->at(pointIndex2);
1308 if (flattenQuadratic(p1, ctrl, p2)) {
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;
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);
1329 bool PathSimplifier::setElementToCubic(Element *element, quint32 pointIndex1, const QPoint &v,
1330 const QPoint &w, quint32 pointIndex2)
1332 const QPoint &u = m_points->at(pointIndex1);
1333 const QPoint &q = m_points->at(pointIndex2);
1334 if (flattenCubic(u, v, w, q)) {
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;
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;
1357 void PathSimplifier::setElementToCubicAndSimplify(Element *element, quint32 pointIndex1,
1358 const QPoint &v, const QPoint &w,
1359 quint32 pointIndex2)
1361 const QPoint &u = m_points->at(pointIndex1);
1362 const QPoint &q = m_points->at(pointIndex2);
1363 if (flattenCubic(u, v, w, q)) {
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;
1373 bool intersecting = (u == q) || intersectionPoint(u, v, w, q).isValid();
1374 if (!intersecting) {
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;
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);
1398 PathSimplifier::RBNode *PathSimplifier::findElementLeftOf(const Element *element,
1399 const QPair<RBNode *, RBNode *> &bounds)
1401 if (!m_elementList.root)
1403 RBNode *current = bounds.first;
1404 Q_ASSERT(!current || !elementIsLeftOf(element, current->data));
1406 current = m_elementList.front(m_elementList.root);
1409 while (current != bounds.second && !elementIsLeftOf(element, current->data)) {
1411 current = m_elementList.next(current);
1416 bool PathSimplifier::elementIsLeftOf(const Element *left, const Element *right)
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()))
1425 if (leftU.x() > qMax(rightL.x(), rightU.x()))
1427 int d = pointDistanceFromLine(leftU, rightL, rightU);
1428 // d < 0: left, d > 0: right, d == 0: on top
1430 d = pointDistanceFromLine(leftL, rightL, rightU);
1432 if (right->degree > Element::Line) {
1433 d = pointDistanceFromLine(leftL, rightL, m_points->at(right->indices[1]));
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);
1439 d = pointDistanceFromLine(m_points->at(left->indices[2]), rightL, rightU);
1446 QPair<PathSimplifier::RBNode *, PathSimplifier::RBNode *> PathSimplifier::outerBounds(const QPoint &point)
1448 RBNode *current = m_elementList.root;
1449 QPair<RBNode *, RBNode *> result(0, 0);
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)
1459 int d = pointDistanceFromLine(point, v1, v2);
1461 if (element->degree == Element::Line)
1463 d = pointDistanceFromLine(point, v1, m_points->at(element->indices[1]));
1465 d = pointDistanceFromLine(point, v1, m_points->at(element->indices[2]));
1469 result.second = current;
1470 current = current->left;
1472 result.first = current;
1473 current = current->right;
1480 RBNode *mid = current;
1482 current = mid->left;
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);
1491 int d = pointDistanceFromLine(point, v1, v2);
1493 equal = (d == 0 && element->degree == Element::Line);
1496 current = current->left;
1498 result.first = current;
1499 current = current->right;
1503 current = mid->right;
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);
1512 int d = pointDistanceFromLine(point, v1, v2);
1514 equal = (d == 0 && element->degree == Element::Line);
1517 current = current->right;
1519 result.second = current;
1520 current = current->left;
1527 inline bool PathSimplifier::flattenQuadratic(const QPoint &u, const QPoint &v, const QPoint &w)
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;
1535 inline bool PathSimplifier::flattenCubic(const QPoint &u, const QPoint &v,
1536 const QPoint &w, const QPoint &q)
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;
1546 inline bool PathSimplifier::splitQuadratic(const QPoint &u, const QPoint &v,
1547 const QPoint &w, QPoint *result)
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;
1563 inline bool PathSimplifier::splitCubic(const QPoint &u, const QPoint &v,
1564 const QPoint &w, const QPoint &q, QPoint *result)
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;
1588 inline void PathSimplifier::subDivQuadratic(const QPoint &u, const QPoint &v, const QPoint &w)
1590 if (flattenQuadratic(u, v, w))
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);
1600 inline void PathSimplifier::subDivCubic(const QPoint &u, const QPoint &v,
1601 const QPoint &w, const QPoint &q)
1603 if (flattenCubic(u, v, w, q))
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);
1613 void PathSimplifier::sortEvents(Event *events, int count)
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]);
1621 memset(counts, 0, sizeof(counts));
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());
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);
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);
1641 for (int i = 0; i < count; ++i)
1642 buffer.at(--counts[bins[i]]) = events[i];
1645 for (int i = 0; i < 0x100; ++i) {
1646 for (; j < counts[i + 1]; ++j) {
1648 while (k > 0 && (buffer.at(j) < events[k - 1])) {
1649 events[k] = events[k - 1];
1652 events[k] = buffer.at(j);
1657 } // end anonymous namespace
1660 void qSimplifyPath(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
1661 QDataBuffer<quint32> &indices, const QTransform &matrix)
1663 PathSimplifier(path, vertices, indices, matrix);
1666 void qSimplifyPath(const QPainterPath &path, QDataBuffer<QPoint> &vertices,
1667 QDataBuffer<quint32> &indices, const QTransform &matrix)
1669 qSimplifyPath(qtVectorPathForPath(path), vertices, indices, matrix);