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