painting/qpathsimplifier.cpp

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