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