painting/qpathsimplifier.cpp

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