Line | Source Code | Coverage |
---|
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 | | - |
54 | QT_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 | | - |
65 | inline 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 | | - |
70 | inline bool operator > (const QPoint &a, const QPoint &b) | - |
71 | { | - |
72 | return b < a; never executed: return b < a; | 0 |
73 | } | - |
74 | | - |
75 | inline bool operator <= (const QPoint &a, const QPoint &b) | - |
76 | { | - |
77 | return !(a > b); never executed: return !(a > b); | 0 |
78 | } | - |
79 | | - |
80 | inline bool operator >= (const QPoint &a, const QPoint &b) | - |
81 | { | - |
82 | return !(a < b); never executed: return !(a < b); | 0 |
83 | } | - |
84 | | - |
85 | namespace { | - |
86 | | - |
87 | inline 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 | | - |
92 | inline 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) | - |
102 | struct 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 | | - |
110 | inline unsigned int gcd(unsigned int x, unsigned int y) | - |
111 | { | - |
112 | while (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 | } | 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. | - |
122 | Fraction 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) { | 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 { | 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 | } | 0 |
132 | return result; never executed: return result; | 0 |
133 | } | - |
134 | | - |
135 | //============================================================================// | - |
136 | // Rational // | - |
137 | //============================================================================// | - |
138 | | - |
139 | struct 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 | | - |
150 | struct 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 | | - |
160 | QPoint 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). | - |
174 | inline 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 | | - |
179 | IntersectionPoint 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) { | 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 | } | 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 { | 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 | } | 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 { | 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 | } | 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 | | - |
248 | class PathSimplifier | - |
249 | { | - |
250 | public: | - |
251 | PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices, | - |
252 | QDataBuffer<quint32> &indices, const QTransform &matrix); | - |
253 | | - |
254 | private: | - |
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 | | - |
385 | inline PathSimplifier::BoundingVolumeHierarchy::BoundingVolumeHierarchy() | - |
386 | : root(0) | - |
387 | , nodeBlock(0) | - |
388 | , blockSize(0) | - |
389 | , firstFree(0) | - |
390 | { | - |
391 | } | 0 |
392 | | - |
393 | inline PathSimplifier::BoundingVolumeHierarchy::~BoundingVolumeHierarchy() | - |
394 | { | - |
395 | free(); never executed (the execution status of this line is deduced): free(); | - |
396 | } | 0 |
397 | | - |
398 | inline 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 | } | 0 |
404 | | - |
405 | inline 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 | } | 0 |
413 | | - |
414 | inline 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 | | - |
421 | inline void PathSimplifier::BoundingVolumeHierarchy::freeNode(Node *n) | - |
422 | { | - |
423 | if (!n) | 0 |
424 | 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 | } | 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 | } | 0 |
433 | | - |
434 | inline PathSimplifier::ElementAllocator::ElementAllocator() | - |
435 | : blocks(0) | - |
436 | { | - |
437 | } | 0 |
438 | | - |
439 | inline PathSimplifier::ElementAllocator::~ElementAllocator() | - |
440 | { | - |
441 | while (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 | } | 0 |
446 | } | 0 |
447 | | - |
448 | inline 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 | } | 0 |
457 | | - |
458 | inline 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 | | - |
472 | inline 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 | | - |
479 | inline 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 | } | 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 | } | 0 |
489 | | - |
490 | PathSimplifier::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 | } | 0 |
504 | } | 0 |
505 | | - |
506 | void 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; | 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) { | 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 | } | 0 |
537 | } | 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; | 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 | } | 0 |
561 | } | - |
562 | 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 { | 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 | } | 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; | 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; | 0 |
609 | } | - |
610 | } | 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 | } | 0 |
623 | } | 0 |
624 | } else { | 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 | } | 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; | 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 | } | 0 |
653 | } | 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 | } | 0 |
658 | | - |
659 | void 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 | } | 0 |
682 | } | 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 | } | 0 |
686 | | - |
687 | void 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) { | 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 | } | 0 |
710 | } | 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 { | 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 | } | 0 |
757 | } | - |
758 | continue; never executed: continue; | 0 |
759 | } | - |
760 | } | 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 { | 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 | } | 0 |
803 | current = m_elementList.next(current); never executed (the execution status of this line is deduced): current = m_elementList.next(current); | - |
804 | } | 0 |
805 | } | 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 { | 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 | } | 0 |
824 | events.pop_back(); never executed (the execution status of this line is deduced): events.pop_back(); | - |
825 | } | 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 { | 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 | } | 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 | } | 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 | } | 0 |
864 | } | 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 | } | 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 | } | 0 |
883 | } | 0 |
884 | } | 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 | } | 0 |
894 | | - |
895 | void 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; | 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; | 0 |
927 | default: | - |
928 | 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 | } | 0 |
936 | } | 0 |
937 | | - |
938 | PathSimplifier::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 | } | 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 | } | 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 { | 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 | } | 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) { | 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; | 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; | 0 |
987 | if (lo < hi) | 0 |
988 | qSwap(elements[lo], elements[hi]); never executed: qSwap(elements[lo], elements[hi]); | 0 |
989 | } | 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 | } | 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 | | - |
1010 | bool 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 | } | 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 { | 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 | | - |
1093 | bool 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 | | - |
1112 | bool 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 | } | 0 |
1163 | return true; never executed: return true; | 0 |
1164 | } | - |
1165 | | - |
1166 | void 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) { | 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 | } | 0 |
1187 | } | - |
1188 | 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) { | 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 | } | 0 |
1203 | } | - |
1204 | 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; | 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; | 0 |
1217 | } | - |
1218 | } | 0 |
1219 | | - |
1220 | QPair<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 | } | 0 |
1229 | return range; never executed: return range; | 0 |
1230 | } | - |
1231 | | - |
1232 | void 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 { | 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 | } | 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 | } | 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 | } | 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 | } | 0 |
1302 | } | 0 |
1303 | | - |
1304 | bool 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 | | - |
1330 | bool 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 | | - |
1358 | void 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; | 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; | 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 | } | 0 |
1398 | | - |
1399 | PathSimplifier::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 | } | 0 |
1414 | return result; never executed: return result; | 0 |
1415 | } | - |
1416 | | - |
1417 | bool 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) { | 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) { | 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) | 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) | 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 | } | 0 |
1442 | } | - |
1443 | } | 0 |
1444 | return d < 0; never executed: return d < 0; | 0 |
1445 | } | - |
1446 | | - |
1447 | QPair<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) { | 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; | 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) { | 0 |
1462 | if (element->degree == Element::Line) never evaluated: element->degree == Element::Line | 0 |
1463 | 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) | 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 | } | 0 |
1469 | if (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 { | 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 | } | 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) { | 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) { | 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 | } | 0 |
1496 | if (equal) { | 0 |
1497 | current = current->left; never executed (the execution status of this line is deduced): current = current->left; | - |
1498 | } else { | 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 | } | 0 |
1502 | } | - |
1503 | | - |
1504 | current = mid->right; never executed (the execution status of this line is deduced): current = mid->right; | - |
1505 | while (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) { | 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 | } | 0 |
1517 | if (equal) { | 0 |
1518 | current = current->right; never executed (the execution status of this line is deduced): current = current->right; | - |
1519 | } else { | 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 | } | 0 |
1523 | } | - |
1524 | | - |
1525 | return result; never executed: return result; | 0 |
1526 | } | - |
1527 | | - |
1528 | inline 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 | | - |
1536 | inline 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 | | - |
1547 | inline 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 | | - |
1564 | inline 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 | | - |
1589 | inline 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; | 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 | } | 0 |
1600 | | - |
1601 | inline 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; | 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 | } | 0 |
1613 | | - |
1614 | void 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 | } | 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 | } | 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 | } | 0 |
1653 | events[k] = buffer.at(j); never executed (the execution status of this line is deduced): events[k] = buffer.at(j); | - |
1654 | } | 0 |
1655 | } | 0 |
1656 | } | 0 |
1657 | | - |
1658 | } // end anonymous namespace | - |
1659 | | - |
1660 | | - |
1661 | void 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 | } | 0 |
1666 | | - |
1667 | void 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 | } | 0 |
1672 | | - |
1673 | | - |
1674 | QT_END_NAMESPACE | - |
1675 | | - |
| | |