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