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

source code of qtbase/src/gui/painting/qpathsimplifier.cpp