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

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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