qpathsimplifier.cpp

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