opengl/qtriangulator.cpp

Switch to Source codePreprocessed file
LineSource CodeCoverage
1 -
2 -
3 -
4 -
5 -
6 -
7 -
8 -
9 -
10 -
11template<typename T> -
12struct QVertexSet -
13{ -
14 inline QVertexSet() { } -
15 inline QVertexSet(const QVertexSet<T> &other) : vertices(other.vertices), indices(other.indices) { }
never executed: }
0
16 QVertexSet<T> &operator = (const QVertexSet<T> &other) {vertices = other.vertices; indices = other.indices; return *this;}
never executed: return *this;
0
17 -
18 -
19 QVector<qreal> vertices; -
20 QVector<T> indices; -
21}; -
22 -
23 -
24 -
25 -
26 -
27 -
28struct QFraction -
29{ -
30 -
31 inline bool operator < (const QFraction &other) const; -
32 inline bool operator == (const QFraction &other) const; -
33 inline bool operator != (const QFraction &other) const {return !(*this == other);}
never executed: return !(*this == other);
0
34 inline bool operator > (const QFraction &other) const {return other < *this;}
never executed: return other < *this;
0
35 inline bool operator >= (const QFraction &other) const {return !(*this < other);}
never executed: return !(*this < other);
0
36 inline bool operator <= (const QFraction &other) const {return !(*this > other);}
never executed: return !(*this > other);
0
37 -
38 inline bool isValid() const {return denominator != 0;}
never executed: return denominator != 0;
0
39 -
40 -
41 quint64 numerator, denominator; -
42}; -
43 -
44static inline quint64 gcd(quint64 x, quint64 y) -
45{ -
46 while (y != 0) {
never evaluated: y != 0
0
47 quint64 z = y; -
48 y = x % y; -
49 x = z; -
50 }
never executed: }
0
51 return x;
never executed: return x;
0
52} -
53 -
54static inline int compare(quint64 a, quint64 b) -
55{ -
56 return (a > b) - (a < b);
never executed: return (a > b) - (a < b);
0
57} -
58 -
59 -
60 -
61 -
62static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d) -
63{ -
64 const quint64 LIMIT = static_cast<unsigned long long>(0x100000000ULL); -
65 for (;;) { -
66 -
67 if (b < LIMIT && d < LIMIT)
never evaluated: b < LIMIT
never evaluated: d < LIMIT
0
68 return compare(a * d, b * c);
never executed: return compare(a * d, b * c);
0
69 -
70 if (a == 0 || c == 0)
never evaluated: a == 0
never evaluated: c == 0
0
71 return compare(a, c);
never executed: return compare(a, c);
0
72 -
73 -
74 quint64 b_div_a = b / a; -
75 quint64 d_div_c = d / c; -
76 if (b_div_a != d_div_c)
never evaluated: b_div_a != d_div_c
0
77 return compare(d_div_c, b_div_a);
never executed: return compare(d_div_c, b_div_a);
0
78 -
79 -
80 -
81 -
82 d -= d_div_c * c; -
83 b -= b_div_a * a; -
84 qSwap(a, d); -
85 qSwap(b, c); -
86 }
never executed: }
0
87}
never executed: }
0
88 -
89 -
90 -
91static QFraction qFraction(quint64 n, quint64 d) { -
92 QFraction result; -
93 if (n == 0) {
never evaluated: n == 0
0
94 result.numerator = 0; -
95 result.denominator = 1; -
96 } else {
never executed: }
0
97 quint64 g = gcd(n, d); -
98 result.numerator = n / g; -
99 result.denominator = d / g; -
100 }
never executed: }
0
101 return result;
never executed: return result;
0
102} -
103 -
104inline bool QFraction::operator < (const QFraction &other) const -
105{ -
106 return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
never executed: return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
0
107} -
108 -
109inline bool QFraction::operator == (const QFraction &other) const -
110{ -
111 return numerator == other.numerator && denominator == other.denominator;
never executed: return numerator == other.numerator && denominator == other.denominator;
0
112} -
113 -
114 -
115 -
116 -
117 -
118struct QPodPoint -
119{ -
120 inline bool operator < (const QPodPoint &other) const -
121 { -
122 if (y != other.y)
never evaluated: y != other.y
0
123 return y < other.y;
never executed: return y < other.y;
0
124 return x < other.x;
never executed: return x < other.x;
0
125 } -
126 -
127 inline bool operator > (const QPodPoint &other) const {return other < *this;}
never executed: return other < *this;
0
128 inline bool operator <= (const QPodPoint &other) const {return !(*this > other);}
never executed: return !(*this > other);
0
129 inline bool operator >= (const QPodPoint &other) const {return !(*this < other);}
never executed: return !(*this < other);
0
130 inline bool operator == (const QPodPoint &other) const {return x == other.x && y == other.y;}
never executed: return x == other.x && y == other.y;
0
131 inline bool operator != (const QPodPoint &other) const {return x != other.x || y != other.y;}
never executed: return x != other.x || y != other.y;
0
132 -
133 inline QPodPoint &operator += (const QPodPoint &other) {x += other.x; y += other.y; return *this;}
never executed: return *this;
0
134 inline QPodPoint &operator -= (const QPodPoint &other) {x -= other.x; y -= other.y; return *this;}
never executed: return *this;
0
135 inline QPodPoint operator + (const QPodPoint &other) const {QPodPoint result = {x + other.x, y + other.y}; return result;}
never executed: return result;
0
136 inline QPodPoint operator - (const QPodPoint &other) const {QPodPoint result = {x - other.x, y - other.y}; return result;}
never executed: return result;
0
137 -
138 int x; -
139 int y; -
140}; -
141 -
142static inline qint64 qCross(const QPodPoint &u, const QPodPoint &v) -
143{ -
144 return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
never executed: return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
0
145} -
146 -
147static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v) -
148{ -
149 return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
never executed: return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
0
150} -
151 -
152 -
153 -
154 -
155 -
156static inline qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2) -
157{ -
158 return qCross(v2 - v1, p - v1);
never executed: return qCross(v2 - v1, p - v1);
0
159} -
160 -
161static inline bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2) -
162{ -
163 return ::qPointDistanceFromLine(p, v1, v2) < 0;
never executed: return ::qPointDistanceFromLine(p, v1, v2) < 0;
0
164} -
165 -
166 -
167 -
168 -
169 -
170struct QIntersectionPoint -
171{ -
172 inline bool isValid() const {return xOffset.isValid() && yOffset.isValid();}
never executed: return xOffset.isValid() && yOffset.isValid();
0
173 QPodPoint round() const; -
174 inline bool isAccurate() const {return xOffset.numerator == 0 && yOffset.numerator == 0;}
never executed: return xOffset.numerator == 0 && yOffset.numerator == 0;
0
175 bool operator < (const QIntersectionPoint &other) const; -
176 bool operator == (const QIntersectionPoint &other) const; -
177 inline bool operator != (const QIntersectionPoint &other) const {return !(*this == other);}
never executed: return !(*this == other);
0
178 inline bool operator > (const QIntersectionPoint &other) const {return other < *this;}
never executed: return other < *this;
0
179 inline bool operator >= (const QIntersectionPoint &other) const {return !(*this < other);}
never executed: return !(*this < other);
0
180 inline bool operator <= (const QIntersectionPoint &other) const {return !(*this > other);}
never executed: return !(*this > other);
0
181 bool isOnLine(const QPodPoint &u, const QPodPoint &v) const; -
182 -
183 QPodPoint upperLeft; -
184 QFraction xOffset; -
185 QFraction yOffset; -
186}; -
187 -
188static inline QIntersectionPoint qIntersectionPoint(const QPodPoint &point) -
189{ -
190 -
191 QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}}; -
192 return p;
never executed: return p;
0
193} -
194 -
195static inline QIntersectionPoint qIntersectionPoint(int x, int y) -
196{ -
197 -
198 QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}}; -
199 return p;
never executed: return p;
0
200} -
201 -
202static QIntersectionPoint qIntersectionPoint(const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2) -
203{ -
204 QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}}; -
205 -
206 QPodPoint u = u2 - u1; -
207 QPodPoint v = v2 - v1; -
208 qint64 d1 = qCross(u, v1 - u1); -
209 qint64 d2 = qCross(u, v2 - u1); -
210 qint64 det = d2 - d1; -
211 qint64 d3 = qCross(v, u1 - v1); -
212 qint64 d4 = d3 - det; -
213 -
214 -
215 qt_noop(); -
216 if (det == 0)
never evaluated: det == 0
0
217 return result;
never executed: return result;
0
218 -
219 if (det < 0) {
never evaluated: det < 0
0
220 det = -det; -
221 d1 = -d1; -
222 d2 = -d2; -
223 d3 = -d3; -
224 d4 = -d4; -
225 }
never executed: }
0
226 -
227 -
228 -
229 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
230 return result;
never executed: return result;
0
231 -
232 -
233 -
234 -
235 -
236 -
237 -
238 if (v.x >= 0) {
never evaluated: v.x >= 0
0
239 result.upperLeft.x = v1.x + (-v.x * d1) / det; -
240 result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det)); -
241 } else {
never executed: }
0
242 result.upperLeft.x = v2.x + (-v.x * d2) / det; -
243 result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det)); -
244 }
never executed: }
0
245 -
246 if (v.y >= 0) {
never evaluated: v.y >= 0
0
247 result.upperLeft.y = v1.y + (-v.y * d1) / det; -
248 result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det)); -
249 } else {
never executed: }
0
250 result.upperLeft.y = v2.y + (-v.y * d2) / det; -
251 result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det)); -
252 }
never executed: }
0
253 -
254 qt_noop(); -
255 qt_noop(); -
256 return result;
never executed: return result;
0
257} -
258 -
259QPodPoint QIntersectionPoint::round() const -
260{ -
261 QPodPoint result = upperLeft; -
262 if (2 * xOffset.numerator >= xOffset.denominator)
never evaluated: 2 * xOffset.numerator >= xOffset.denominator
0
263 ++result.x;
never executed: ++result.x;
0
264 if (2 * yOffset.numerator >= yOffset.denominator)
never evaluated: 2 * yOffset.numerator >= yOffset.denominator
0
265 ++result.y;
never executed: ++result.y;
0
266 return result;
never executed: return result;
0
267} -
268 -
269bool QIntersectionPoint::operator < (const QIntersectionPoint &other) const -
270{ -
271 if (upperLeft.y != other.upperLeft.y)
never evaluated: upperLeft.y != other.upperLeft.y
0
272 return upperLeft.y < other.upperLeft.y;
never executed: return upperLeft.y < other.upperLeft.y;
0
273 if (yOffset != other.yOffset)
never evaluated: yOffset != other.yOffset
0
274 return yOffset < other.yOffset;
never executed: return yOffset < other.yOffset;
0
275 if (upperLeft.x != other.upperLeft.x)
never evaluated: upperLeft.x != other.upperLeft.x
0
276 return upperLeft.x < other.upperLeft.x;
never executed: return upperLeft.x < other.upperLeft.x;
0
277 return xOffset < other.xOffset;
never executed: return xOffset < other.xOffset;
0
278} -
279 -
280bool QIntersectionPoint::operator == (const QIntersectionPoint &other) const -
281{ -
282 return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
never executed: return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
0
283} -
284 -
285 -
286bool QIntersectionPoint::isOnLine(const QPodPoint &u, const QPodPoint &v) const -
287{ -
288 -
289 const QPodPoint p = upperLeft - u; -
290 const QPodPoint q = v - u; -
291 bool isHorizontal = p.y == 0 && yOffset.numerator == 0;
never evaluated: p.y == 0
never evaluated: yOffset.numerator == 0
0
292 bool isVertical = p.x == 0 && xOffset.numerator == 0;
never evaluated: p.x == 0
never evaluated: xOffset.numerator == 0
0
293 if (isHorizontal && isVertical)
never evaluated: isHorizontal
never evaluated: isVertical
0
294 return true;
never executed: return true;
0
295 if (isHorizontal)
never evaluated: isHorizontal
0
296 return q.y == 0;
never executed: return q.y == 0;
0
297 if (q.y == 0)
never evaluated: q.y == 0
0
298 return false;
never executed: return false;
0
299 if (isVertical)
never evaluated: isVertical
0
300 return q.x == 0;
never executed: return q.x == 0;
0
301 if (q.x == 0)
never evaluated: q.x == 0
0
302 return false;
never executed: return false;
0
303 -
304 -
305 -
306 if (((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0)))
never evaluated: ((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0))
0
307 return false;
never executed: return false;
0
308 -
309 -
310 quint64 nx, ny; -
311 if (p.x < 0)
never evaluated: p.x < 0
0
312 nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
never executed: nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
0
313 else -
314 nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
never executed: nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
0
315 if (p.y < 0)
never evaluated: p.y < 0
0
316 ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
never executed: ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
0
317 else -
318 ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
never executed: ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
0
319 -
320 return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
never executed: return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
0
321} -
322 -
323 -
324 -
325 -
326 -
327template <class T> -
328class QMaxHeap -
329{ -
330public: -
331 QMaxHeap() : m_data(0) {}
never executed: }
0
332 inline int size() const {return m_data.size();}
never executed: return m_data.size();
0
333 inline bool empty() const {return m_data.isEmpty();}
never executed: return m_data.isEmpty();
0
334 inline bool isEmpty() const {return m_data.isEmpty();}
never executed: return m_data.isEmpty();
0
335 void push(const T &x); -
336 T pop(); -
337 inline const T &top() const {return m_data.first();}
never executed: return m_data.first();
0
338private: -
339 static inline int parent(int i) {return (i - 1) / 2;}
never executed: return (i - 1) / 2;
0
340 static inline int left(int i) {return 2 * i + 1;}
never executed: return 2 * i + 1;
0
341 static inline int right(int i) {return 2 * i + 2;}
never executed: return 2 * i + 2;
0
342 -
343 QDataBuffer<T> m_data; -
344}; -
345 -
346template <class T> -
347void QMaxHeap<T>::push(const T &x) -
348{ -
349 int current = m_data.size(); -
350 int parent = QMaxHeap::parent(current); -
351 m_data.add(x); -
352 while (current != 0 && m_data.at(parent) < x) {
never evaluated: current != 0
never evaluated: m_data.at(parent) < x
0
353 m_data.at(current) = m_data.at(parent); -
354 current = parent; -
355 parent = QMaxHeap::parent(current); -
356 }
never executed: }
0
357 m_data.at(current) = x; -
358}
never executed: }
0
359 -
360template <class T> -
361T QMaxHeap<T>::pop() -
362{ -
363 T result = m_data.first(); -
364 T back = m_data.last(); -
365 m_data.pop_back(); -
366 if (!m_data.isEmpty()) {
never evaluated: !m_data.isEmpty()
0
367 int current = 0; -
368 for (;;) { -
369 int left = QMaxHeap::left(current); -
370 int right = QMaxHeap::right(current); -
371 if (left >= m_data.size())
never evaluated: left >= m_data.size()
0
372 break;
never executed: break;
0
373 int greater = left; -
374 if (right < m_data.size() && m_data.at(left) < m_data.at(right))
never evaluated: right < m_data.size()
never evaluated: m_data.at(left) < m_data.at(right)
0
375 greater = right;
never executed: greater = right;
0
376 if (m_data.at(greater) < back)
never evaluated: m_data.at(greater) < back
0
377 break;
never executed: break;
0
378 m_data.at(current) = m_data.at(greater); -
379 current = greater; -
380 }
never executed: }
0
381 m_data.at(current) = back; -
382 }
never executed: }
0
383 return result;
never executed: return result;
0
384} -
385 -
386 -
387 -
388 -
389 -
390 -
391static const uchar prime_deltas[] = { -
392 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, -
393 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 -
394}; -
395 -
396 -
397static inline int primeForNumBits(int numBits) -
398{ -
399 return (1 << numBits) + prime_deltas[numBits];
never executed: return (1 << numBits) + prime_deltas[numBits];
0
400} -
401 -
402static inline int primeForCount(int count) -
403{ -
404 int low = 0; -
405 int high = 32; -
406 for (int i = 0; i < 5; ++i) {
never evaluated: i < 5
0
407 int mid = (high + low) / 2; -
408 if (count >= 1 << mid)
never evaluated: count >= 1 << mid
0
409 low = mid;
never executed: low = mid;
0
410 else -
411 high = mid;
never executed: high = mid;
0
412 } -
413 return primeForNumBits(high);
never executed: return primeForNumBits(high);
0
414} -
415 -
416 -
417 -
418class QInt64Set -
419{ -
420public: -
421 inline QInt64Set(int capacity = 64); -
422 inline ~QInt64Set() {if (m_array) delete[] m_array;}
never evaluated: m_array
never executed: delete[] m_array;
never executed: }
0
423 inline bool isValid() const {return m_array;}
never executed: return m_array;
0
424 void insert(quint64 key); -
425 bool contains(quint64 key) const; -
426 inline void clear(); -
427private: -
428 bool rehash(int capacity); -
429 -
430 static const quint64 UNUSED; -
431 -
432 quint64 *m_array; -
433 int m_capacity; -
434 int m_count; -
435}; -
436 -
437const quint64 QInt64Set::UNUSED = quint64(-1); -
438 -
439inline QInt64Set::QInt64Set(int capacity) -
440{ -
441 m_capacity = primeForCount(capacity); -
442 m_array = new quint64[m_capacity]; -
443 if (m_array)
never evaluated: m_array
0
444 clear();
never executed: clear();
0
445 else -
446 m_capacity = 0;
never executed: m_capacity = 0;
0
447} -
448 -
449bool QInt64Set::rehash(int capacity) -
450{ -
451 quint64 *oldArray = m_array; -
452 int oldCapacity = m_capacity; -
453 -
454 m_capacity = capacity; -
455 m_array = new quint64[m_capacity]; -
456 if (m_array) {
never evaluated: m_array
0
457 clear(); -
458 if (oldArray) {
never evaluated: oldArray
0
459 for (int i = 0; i < oldCapacity; ++i) {
never evaluated: i < oldCapacity
0
460 if (oldArray[i] != UNUSED)
never evaluated: oldArray[i] != UNUSED
0
461 insert(oldArray[i]);
never executed: insert(oldArray[i]);
0
462 }
never executed: }
0
463 delete[] oldArray; -
464 }
never executed: }
0
465 return true;
never executed: return true;
0
466 } else { -
467 m_capacity = oldCapacity; -
468 m_array = oldArray; -
469 return false;
never executed: return false;
0
470 } -
471} -
472 -
473void QInt64Set::insert(quint64 key) -
474{ -
475 if (m_count > 3 * m_capacity / 4)
never evaluated: m_count > 3 * m_capacity / 4
0
476 rehash(primeForCount(2 * m_capacity));
never executed: rehash(primeForCount(2 * m_capacity));
0
477 qt_noop(); -
478 int index = int(key % m_capacity); -
479 for (int i = 0; i < m_capacity; ++i) {
never evaluated: i < m_capacity
0
480 index += i; -
481 if (index >= m_capacity)
never evaluated: index >= m_capacity
0
482 index -= m_capacity;
never executed: index -= m_capacity;
0
483 if (m_array[index] == key)
never evaluated: m_array[index] == key
0
484 return;
never executed: return;
0
485 if (m_array[index] == UNUSED) {
never evaluated: m_array[index] == UNUSED
0
486 ++m_count; -
487 m_array[index] = key; -
488 return;
never executed: return;
0
489 } -
490 }
never executed: }
0
491 qt_noop(); -
492}
never executed: }
0
493 -
494bool QInt64Set::contains(quint64 key) const -
495{ -
496 qt_noop(); -
497 int index = int(key % m_capacity); -
498 for (int i = 0; i < m_capacity; ++i) {
never evaluated: i < m_capacity
0
499 index += i; -
500 if (index >= m_capacity)
never evaluated: index >= m_capacity
0
501 index -= m_capacity;
never executed: index -= m_capacity;
0
502 if (m_array[index] == key)
never evaluated: m_array[index] == key
0
503 return true;
never executed: return true;
0
504 if (m_array[index] == UNUSED)
never evaluated: m_array[index] == UNUSED
0
505 return false;
never executed: return false;
0
506 }
never executed: }
0
507 return false;
never executed: return false;
0
508} -
509 -
510inline void QInt64Set::clear() -
511{ -
512 qt_noop(); -
513 for (int i = 0; i < m_capacity; ++i)
never evaluated: i < m_capacity
0
514 m_array[i] = UNUSED;
never executed: m_array[i] = UNUSED;
0
515 m_count = 0; -
516}
never executed: }
0
517 -
518 -
519 -
520 -
521template<typename T> -
522class QTriangulator -
523{ -
524public: -
525 typedef QVarLengthArray<int, 6> ShortArray; -
526 -
527 -
528 -
529 -
530 friend class ComplexToSimple; -
531 class ComplexToSimple -
532 { -
533 public: -
534 inline ComplexToSimple(QTriangulator<T> *parent) : m_parent(parent), -
535 m_edges(0), m_events(0), m_splits(0) { }
never executed: }
0
536 void decompose(); -
537 private: -
538 struct Edge -
539 { -
540 inline int &upper() {return pointingUp ? to : from;}
never executed: return pointingUp ? to : from;
0
541 inline int &lower() {return pointingUp ? from : to;}
never executed: return pointingUp ? from : to;
0
542 inline int upper() const {return pointingUp ? to : from;}
never executed: return pointingUp ? to : from;
0
543 inline int lower() const {return pointingUp ? from : to;}
never executed: return pointingUp ? from : to;
0
544 -
545 QRBTree<int>::Node *node; -
546 int from, to; -
547 int next, previous; -
548 int winding; -
549 bool mayIntersect; -
550 bool pointingUp, originallyPointingUp; -
551 }; -
552 -
553 struct Intersection -
554 { -
555 bool operator < (const Intersection &other) const {return other.intersectionPoint < intersectionPoint;}
never executed: return other.intersectionPoint < intersectionPoint;
0
556 -
557 QIntersectionPoint intersectionPoint; -
558 int vertex; -
559 int leftEdge; -
560 int rightEdge; -
561 }; -
562 -
563 struct Split -
564 { -
565 int vertex; -
566 int edge; -
567 bool accurate; -
568 }; -
569 -
570 struct Event -
571 { -
572 enum Type {Upper, Lower}; -
573 inline bool operator < (const Event &other) const; -
574 -
575 QPodPoint point; -
576 Type type; -
577 int edge; -
578 }; -
579 void initEdges(); -
580 bool calculateIntersection(int left, int right); -
581 bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const; -
582 QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex) const; -
583 QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const; -
584 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> bounds(const QPodPoint &point) const; -
585 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> outerBounds(const QPodPoint &point) const; -
586 void splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint); -
587 void reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost); -
588 void sortEdgeList(const QPodPoint eventPoint); -
589 void fillPriorityQueue(); -
590 void calculateIntersections(); -
591 int splitEdge(int splitIndex); -
592 bool splitEdgesAtIntersections(); -
593 void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i); -
594 void removeUnwantedEdgesAndConnect(); -
595 void removeUnusedPoints(); -
596 -
597 QTriangulator *m_parent; -
598 QDataBuffer<Edge> m_edges; -
599 QRBTree<int> m_edgeList; -
600 QDataBuffer<Event> m_events; -
601 QDataBuffer<Split> m_splits; -
602 QMaxHeap<Intersection> m_topIntersection; -
603 QInt64Set m_processedEdgePairs; -
604 int m_initialPointCount; -
605 }; -
606 -
607 -
608 -
609 -
610 -
611 -
612 -
613 friend class SimpleToMonotone; -
614 class SimpleToMonotone -
615 { -
616 public: -
617 inline SimpleToMonotone(QTriangulator<T> *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { }
never executed: }
0
618 void decompose(); -
619 private: -
620 enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex}; -
621 -
622 struct Edge -
623 { -
624 QRBTree<int>::Node *node; -
625 int helper, twin, next, previous; -
626 T from, to; -
627 VertexType type; -
628 bool pointingUp; -
629 int upper() const {return (pointingUp ? to : from);}
never executed: return (pointingUp ? to : from);
0
630 int lower() const {return (pointingUp ? from : to);}
never executed: return (pointingUp ? from : to);
0
631 }; -
632 -
633 friend class CompareVertices; -
634 class CompareVertices -
635 { -
636 public: -
637 CompareVertices(SimpleToMonotone *parent) : m_parent(parent) { }
never executed: }
0
638 bool operator () (int i, int j) const; -
639 private: -
640 SimpleToMonotone *m_parent; -
641 }; -
642 -
643 void setupDataStructures(); -
644 void removeZeroLengthEdges(); -
645 void fillPriorityQueue(); -
646 bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const; -
647 -
648 QRBTree<int>::Node *searchEdgeLeftOfEdge(int edgeIndex) const; -
649 -
650 QRBTree<int>::Node *searchEdgeLeftOfPoint(int pointIndex) const; -
651 void classifyVertex(int i); -
652 void classifyVertices(); -
653 bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3); -
654 bool pointIsInSector(int vertex, int sector); -
655 int findSector(int edge, int vertex); -
656 void createDiagonal(int lower, int upper); -
657 void monotoneDecomposition(); -
658 -
659 QTriangulator *m_parent; -
660 QRBTree<int> m_edgeList; -
661 QDataBuffer<Edge> m_edges; -
662 QDataBuffer<int> m_upperVertex; -
663 bool m_clockwiseOrder; -
664 }; -
665 -
666 -
667 -
668 -
669 friend class MonotoneToTriangles; -
670 class MonotoneToTriangles -
671 { -
672 public: -
673 inline MonotoneToTriangles(QTriangulator<T> *parent) : m_parent(parent) { }
never executed: }
0
674 void decompose(); -
675 private: -
676 inline T indices(int index) const {return m_parent->m_indices.at(index + m_first);}
never executed: return m_parent->m_indices.at(index + m_first);
0
677 inline int next(int index) const {return (index + 1) % m_length;}
never executed: return (index + 1) % m_length;
0
678 inline int previous(int index) const {return (index + m_length - 1) % m_length;}
never executed: return (index + m_length - 1) % m_length;
0
679 inline bool less(int i, int j) const {return m_parent->m_vertices.at((qint32)indices(i)) < m_parent->m_vertices.at(indices(j));}
never executed: return m_parent->m_vertices.at((qint32)indices(i)) < m_parent->m_vertices.at(indices(j));
0
680 inline bool leftOfEdge(int i, int j, int k) const -
681 { -
682 return qPointIsLeftOfLine(m_parent->m_vertices.at((qint32)indices(i)), 0
683 m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
never executed: return qPointIsLeftOfLine(m_parent->m_vertices.at((qint32)indices(i)), m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
0
684 } -
685 -
686 QTriangulator<T> *m_parent; -
687 int m_first; -
688 int m_length; -
689 }; -
690 -
691 inline QTriangulator() : m_vertices(0) { }
never executed: }
0
692 -
693 -
694 void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix); -
695 -
696 void initialize(const QVectorPath &path, const QTransform &matrix, qreal lod); -
697 -
698 void initialize(const QPainterPath &path, const QTransform &matrix, qreal lod); -
699 -
700 QVertexSet<T> triangulate(); -
701 QVertexSet<T> polyline(); -
702private: -
703 QDataBuffer<QPodPoint> m_vertices; -
704 QVector<T> m_indices; -
705 uint m_hint; -
706}; -
707 -
708 -
709 -
710 -
711 -
712template <typename T> -
713QVertexSet<T> QTriangulator<T>::triangulate() -
714{ -
715 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
716 qt_noop(); -
717 qt_noop(); -
718 }
never executed: }
0
719 -
720 if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill)))
never evaluated: !(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill))
0
721 m_hint |= QVectorPath::OddEvenFill;
never executed: m_hint |= QVectorPath::OddEvenFill;
0
722 -
723 if (m_hint & QVectorPath::NonConvexShapeMask) {
never evaluated: m_hint & QVectorPath::NonConvexShapeMask
0
724 ComplexToSimple c2s(this); -
725 c2s.decompose(); -
726 SimpleToMonotone s2m(this); -
727 s2m.decompose(); -
728 }
never executed: }
0
729 MonotoneToTriangles m2t(this); -
730 m2t.decompose(); -
731 -
732 QVertexSet<T> result; -
733 result.indices = m_indices; -
734 result.vertices.resize(2 * m_vertices.size()); -
735 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
736 result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / 32; -
737 result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / 32; -
738 }
never executed: }
0
739 return result;
never executed: return result;
0
740} -
741 -
742template <typename T> -
743QVertexSet<T> QTriangulator<T>::polyline() -
744{ -
745 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
746 qt_noop(); -
747 qt_noop(); -
748 }
never executed: }
0
749 -
750 if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill)))
never evaluated: !(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill))
0
751 m_hint |= QVectorPath::OddEvenFill;
never executed: m_hint |= QVectorPath::OddEvenFill;
0
752 -
753 if (m_hint & QVectorPath::NonConvexShapeMask) {
never evaluated: m_hint & QVectorPath::NonConvexShapeMask
0
754 ComplexToSimple c2s(this); -
755 c2s.decompose(); -
756 }
never executed: }
0
757 -
758 QVertexSet<T> result; -
759 result.indices = m_indices; -
760 result.vertices.resize(2 * m_vertices.size()); -
761 for (int i = 0; i < m_vertices.size(); ++i) {
never evaluated: i < m_vertices.size()
0
762 result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / 32; -
763 result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / 32; -
764 }
never executed: }
0
765 return result;
never executed: return result;
0
766} -
767 -
768template <typename T> -
769void QTriangulator<T>::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix) -
770{ -
771 m_hint = hint; -
772 m_vertices.resize(count); -
773 m_indices.resize(count + 1); -
774 for (int i = 0; i < count; ++i) {
never evaluated: i < count
0
775 qreal x, y; -
776 matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y); -
777 m_vertices.at(i).x = qRound(x * 32); -
778 m_vertices.at(i).y = qRound(y * 32); -
779 m_indices[i] = i; -
780 }
never executed: }
0
781 m_indices[count] = T(-1); -
782}
never executed: }
0
783 -
784template <typename T> -
785void QTriangulator<T>::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod) -
786{ -
787 m_hint = path.hints(); -
788 -
789 m_hint &= ~QVectorPath::CurvedShapeMask; -
790 -
791 const qreal *p = path.points(); -
792 const QPainterPath::ElementType *e = path.elements(); -
793 if (e) {
never evaluated: e
0
794 for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) {
never evaluated: i < path.elementCount()
0
795 switch (*e) { -
796 case QPainterPath::MoveToElement: -
797 if (!m_indices.isEmpty())
never evaluated: !m_indices.isEmpty()
0
798 m_indices.push_back(T(-1));
never executed: m_indices.push_back(T(-1));
0
799 -
800 case QPainterPath::LineToElement:
code before this statement never executed: case QPainterPath::LineToElement:
0
801 m_indices.push_back(T(m_vertices.size())); -
802 m_vertices.resize(m_vertices.size() + 1); -
803 qreal x, y; -
804 matrix.map(p[0], p[1], &x, &y); -
805 m_vertices.last().x = qRound(x * 32); -
806 m_vertices.last().y = qRound(y * 32); -
807 break;
never executed: break;
0
808 case QPainterPath::CurveToElement: -
809 { -
810 qreal pts[8]; -
811 for (int i = 0; i < 4; ++i)
never evaluated: i < 4
0
812 matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
never executed: matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
0
813 for (int i = 0; i < 8; ++i)
never evaluated: i < 8
0
814 pts[i] *= lod;
never executed: pts[i] *= lod;
0
815 QBezier bezier = QBezier::fromPoints(QPointF(pts[0], pts[1]), QPointF(pts[2], pts[3]), QPointF(pts[4], pts[5]), QPointF(pts[6], pts[7])); -
816 QPolygonF poly = bezier.toPolygon(); -
817 -
818 for (int j = 1; j < poly.size(); ++j) {
never evaluated: j < poly.size()
0
819 m_indices.push_back(T(m_vertices.size())); -
820 m_vertices.resize(m_vertices.size() + 1); -
821 m_vertices.last().x = qRound(poly.at(j).x() * 32 / lod); -
822 m_vertices.last().y = qRound(poly.at(j).y() * 32 / lod); -
823 }
never executed: }
0
824 } -
825 i += 2; -
826 e += 2; -
827 p += 4; -
828 break;
never executed: break;
0
829 default: -
830 qt_noop(); -
831 break;
never executed: break;
0
832 } -
833 }
never executed: }
0
834 } else {
never executed: }
0
835 for (int i = 0; i < path.elementCount(); ++i, p += 2) {
never evaluated: i < path.elementCount()
0
836 m_indices.push_back(T(m_vertices.size())); -
837 m_vertices.resize(m_vertices.size() + 1); -
838 qreal x, y; -
839 matrix.map(p[0], p[1], &x, &y); -
840 m_vertices.last().x = qRound(x * 32); -
841 m_vertices.last().y = qRound(y * 32); -
842 }
never executed: }
0
843 }
never executed: }
0
844 m_indices.push_back(T(-1)); -
845}
never executed: }
0
846 -
847template <typename T> -
848void QTriangulator<T>::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod) -
849{ -
850 initialize(qtVectorPathForPath(path), matrix, lod); -
851}
never executed: }
0
852 -
853 -
854 -
855 -
856template <typename T> -
857void QTriangulator<T>::ComplexToSimple::decompose() -
858{ -
859 m_initialPointCount = m_parent->m_vertices.size(); -
860 initEdges(); -
861 do { -
862 calculateIntersections(); -
863 } while (splitEdgesAtIntersections());
never executed: }
never evaluated: splitEdgesAtIntersections()
0
864 -
865 removeUnwantedEdgesAndConnect(); -
866 removeUnusedPoints(); -
867 -
868 m_parent->m_indices.clear(); -
869 QBitArray processed(m_edges.size(), false); -
870 for (int first = 0; first < m_edges.size(); ++first) {
never evaluated: first < m_edges.size()
0
871 -
872 if (processed.at(first) || m_edges.at(first).next == -1)
never evaluated: processed.at(first)
never evaluated: m_edges.at(first).next == -1
0
873 continue;
never executed: continue;
0
874 -
875 int i = first; -
876 do { -
877 qt_noop(); -
878 qt_noop(); -
879 m_parent->m_indices.push_back(m_edges.at(i).from); -
880 processed.setBit(i); -
881 i = m_edges.at(i).next; -
882 } while (i != first);
never executed: }
never evaluated: i != first
0
883 m_parent->m_indices.push_back(T(-1)); -
884 }
never executed: }
0
885}
never executed: }
0
886 -
887template <typename T> -
888void QTriangulator<T>::ComplexToSimple::initEdges() -
889{ -
890 -
891 -
892 int first = 0; -
893 for (int i = 0; i < m_parent->m_indices.size(); ++i) {
never evaluated: i < m_parent->m_indices.size()
0
894 if (m_parent->m_indices.at(i) == T(-1)) {
never evaluated: m_parent->m_indices.at(i) == T(-1)
0
895 if (m_edges.size() != first)
never evaluated: m_edges.size() != first
0
896 m_edges.last().to = m_edges.at(first).from;
never executed: m_edges.last().to = m_edges.at(first).from;
0
897 first = m_edges.size(); -
898 } else {
never executed: }
0
899 qt_noop(); -
900 -
901 Edge edge = {0, int(m_parent->m_indices.at(i)), int(m_parent->m_indices.at(i + 1)), -1, -1, 0, true, false, false}; -
902 m_edges.add(edge); -
903 }
never executed: }
0
904 } -
905 if (first != m_edges.size())
never evaluated: first != m_edges.size()
0
906 m_edges.last().to = m_edges.at(first).from;
never executed: m_edges.last().to = m_edges.at(first).from;
0
907 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
908 m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp = -
909 m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from); -
910 }
never executed: }
0
911}
never executed: }
0
912 -
913 -
914template <typename T> -
915bool QTriangulator<T>::ComplexToSimple::calculateIntersection(int left, int right) -
916{ -
917 const Edge &e1 = m_edges.at(left); -
918 const Edge &e2 = m_edges.at(right); -
919 -
920 const QPodPoint &u1 = m_parent->m_vertices.at((qint32)e1.from); -
921 const QPodPoint &u2 = m_parent->m_vertices.at((qint32)e1.to); -
922 const QPodPoint &v1 = m_parent->m_vertices.at((qint32)e2.from); -
923 const QPodPoint &v2 = m_parent->m_vertices.at((qint32)e2.to); -
924 if (qMax(u1.x, u2.x) <= qMin(v1.x, v2.x))
never evaluated: qMax(u1.x, u2.x) <= qMin(v1.x, v2.x)
0
925 return false;
never executed: return false;
0
926 -
927 quint64 key = (left > right ? (quint64(right) << 32) | quint64(left) : (quint64(left) << 32) | quint64(right));
never evaluated: left > right
0
928 if (m_processedEdgePairs.contains(key))
never evaluated: m_processedEdgePairs.contains(key)
0
929 return false;
never executed: return false;
0
930 m_processedEdgePairs.insert(key); -
931 -
932 Intersection intersection; -
933 intersection.leftEdge = left; -
934 intersection.rightEdge = right; -
935 intersection.intersectionPoint = ::qIntersectionPoint(u1, u2, v1, v2); -
936 -
937 if (!intersection.intersectionPoint.isValid())
never evaluated: !intersection.intersectionPoint.isValid()
0
938 return false;
never executed: return false;
0
939 -
940 qt_noop(); -
941 qt_noop(); -
942 -
943 intersection.vertex = m_parent->m_vertices.size(); -
944 m_topIntersection.push(intersection); -
945 m_parent->m_vertices.add(intersection.intersectionPoint.round()); -
946 return true;
never executed: return true;
0
947} -
948 -
949template <typename T> -
950bool QTriangulator<T>::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const -
951{ -
952 const Edge &leftEdge = m_edges.at(leftEdgeIndex); -
953 const Edge &rightEdge = m_edges.at(rightEdgeIndex); -
954 const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper()); -
955 const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower()); -
956 const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper()); -
957 if (upper.x < qMin(l.x, u.x))
never evaluated: upper.x < qMin(l.x, u.x)
0
958 return true;
never executed: return true;
0
959 if (upper.x > qMax(l.x, u.x))
never evaluated: upper.x > qMax(l.x, u.x)
0
960 return false;
never executed: return false;
0
961 qint64 d = ::qPointDistanceFromLine(upper, l, u); -
962 -
963 if (d == 0)
never evaluated: d == 0
0
964 d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
never executed: d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
0
965 return d < 0;
never executed: return d < 0;
0
966} -
967 -
968template <typename T> -
969QRBTree<int>::Node *QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const -
970{ -
971 QRBTree<int>::Node *current = m_edgeList.root; -
972 QRBTree<int>::Node *result = 0; -
973 while (current) {
never evaluated: current
0
974 if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
never evaluated: edgeIsLeftOfEdge(edgeIndex, current->data)
0
975 current = current->left; -
976 } else {
never executed: }
0
977 result = current; -
978 current = current->right; -
979 }
never executed: }
0
980 } -
981 return result;
never executed: return result;
0
982} -
983 -
984template <typename T> -
985QRBTree<int>::Node *QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const -
986{ -
987 if (!m_edgeList.root)
never evaluated: !m_edgeList.root
0
988 return after;
never executed: return after;
0
989 QRBTree<int>::Node *result = after; -
990 QRBTree<int>::Node *current = (after ? m_edgeList.next(after) : m_edgeList.front(m_edgeList.root));
never evaluated: after
0
991 while (current) {
never evaluated: current
0
992 if (edgeIsLeftOfEdge(edgeIndex, current->data))
never evaluated: edgeIsLeftOfEdge(edgeIndex, current->data)
0
993 return result;
never executed: return result;
0
994 result = current; -
995 current = m_edgeList.next(current); -
996 }
never executed: }
0
997 return result;
never executed: return result;
0
998} -
999 -
1000template <typename T> -
1001QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::ComplexToSimple::bounds(const QPodPoint &point) const -
1002{ -
1003 QRBTree<int>::Node *current = m_edgeList.root; -
1004 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0); -
1005 while (current) {
never evaluated: current
0
1006 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower()); -
1007 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper()); -
1008 qint64 d = ::qPointDistanceFromLine(point, v1, v2); -
1009 if (d == 0) {
never evaluated: d == 0
0
1010 result.first = result.second = current; -
1011 break;
never executed: break;
0
1012 } -
1013 current = (d < 0 ? current->left : current->right);
never evaluated: d < 0
0
1014 }
never executed: }
0
1015 if (current == 0)
never evaluated: current == 0
0
1016 return result;
never executed: return result;
0
1017 -
1018 current = result.first->left; -
1019 while (current) {
never evaluated: current
0
1020 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower()); -
1021 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper()); -
1022 qint64 d = ::qPointDistanceFromLine(point, v1, v2); -
1023 qt_noop(); -
1024 if (d == 0) {
never evaluated: d == 0
0
1025 result.first = current; -
1026 current = current->left; -
1027 } else {
never executed: }
0
1028 current = current->right; -
1029 }
never executed: }
0
1030 } -
1031 -
1032 current = result.second->right; -
1033 while (current) {
never evaluated: current
0
1034 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower()); -
1035 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper()); -
1036 qint64 d = ::qPointDistanceFromLine(point, v1, v2); -
1037 qt_noop(); -
1038 if (d == 0) {
never evaluated: d == 0
0
1039 result.second = current; -
1040 current = current->right; -
1041 } else {
never executed: }
0
1042 current = current->left; -
1043 }
never executed: }
0
1044 } -
1045 -
1046 return result;
never executed: return result;
0
1047} -
1048 -
1049template <typename T> -
1050QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::ComplexToSimple::outerBounds(const QPodPoint &point) const -
1051{ -
1052 QRBTree<int>::Node *current = m_edgeList.root; -
1053 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0); -
1054 -
1055 while (current) {
never evaluated: current
0
1056 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower()); -
1057 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper()); -
1058 qint64 d = ::qPointDistanceFromLine(point, v1, v2); -
1059 if (d == 0)
never evaluated: d == 0
0
1060 break;
never executed: break;
0
1061 if (d < 0) {
never evaluated: d < 0
0
1062 result.second = current; -
1063 current = current->left; -
1064 } else {
never executed: }
0
1065 result.first = current; -
1066 current = current->right; -
1067 }
never executed: }
0
1068 } -
1069 -
1070 if (!current)
never evaluated: !current
0
1071 return result;
never executed: return result;
0
1072 -
1073 QRBTree<int>::Node *mid = current; -
1074 -
1075 current = mid->left; -
1076 while (current) {
never evaluated: current
0
1077 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower()); -
1078 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper()); -
1079 qint64 d = ::qPointDistanceFromLine(point, v1, v2); -
1080 qt_noop(); -
1081 if (d == 0) {
never evaluated: d == 0
0
1082 current = current->left; -
1083 } else {
never executed: }
0
1084 result.first = current; -
1085 current = current->right; -
1086 }
never executed: }
0
1087 } -
1088 -
1089 current = mid->right; -
1090 while (current) {
never evaluated: current
0
1091 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower()); -
1092 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper()); -
1093 qint64 d = ::qPointDistanceFromLine(point, v1, v2); -
1094 qt_noop(); -
1095 if (d == 0) {
never evaluated: d == 0
0
1096 current = current->right; -
1097 } else {
never executed: }
0
1098 result.second = current; -
1099 current = current->left; -
1100 }
never executed: }
0
1101 } -
1102 -
1103 return result;
never executed: return result;
0
1104} -
1105 -
1106template <typename T> -
1107void QTriangulator<T>::ComplexToSimple::splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint) -
1108{ -
1109 qt_noop(); -
1110 -
1111 -
1112 for (;;) { -
1113 const QPodPoint &u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from); -
1114 const QPodPoint &v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to); -
1115 qt_noop(); -
1116 const Split split = {vertex, leftmost->data, intersectionPoint.isAccurate()}; -
1117 if (intersectionPoint.xOffset.numerator != 0 || intersectionPoint.yOffset.numerator != 0 || (intersectionPoint.upperLeft != u && intersectionPoint.upperLeft != v))
never evaluated: intersectionPoint.xOffset.numerator != 0
never evaluated: intersectionPoint.yOffset.numerator != 0
never evaluated: intersectionPoint.upperLeft != u
never evaluated: intersectionPoint.upperLeft != v
0
1118 m_splits.add(split);
never executed: m_splits.add(split);
0
1119 if (leftmost == rightmost)
never evaluated: leftmost == rightmost
0
1120 break;
never executed: break;
0
1121 leftmost = m_edgeList.next(leftmost); -
1122 }
never executed: }
0
1123}
never executed: }
0
1124 -
1125template <typename T> -
1126void QTriangulator<T>::ComplexToSimple::reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost) -
1127{ -
1128 qt_noop(); -
1129 -
1130 QRBTree<int>::Node *storeLeftmost = leftmost; -
1131 QRBTree<int>::Node *storeRightmost = rightmost; -
1132 -
1133 -
1134 while (leftmost != rightmost) {
never evaluated: leftmost != rightmost
0
1135 Edge &left = m_edges.at(leftmost->data); -
1136 Edge &right = m_edges.at(rightmost->data); -
1137 qSwap(left.node, right.node); -
1138 qSwap(leftmost->data, rightmost->data); -
1139 leftmost = m_edgeList.next(leftmost); -
1140 if (leftmost == rightmost)
never evaluated: leftmost == rightmost
0
1141 break;
never executed: break;
0
1142 rightmost = m_edgeList.previous(rightmost); -
1143 }
never executed: }
0
1144 -
1145 rightmost = m_edgeList.next(storeRightmost); -
1146 leftmost = m_edgeList.previous(storeLeftmost); -
1147 if (leftmost)
never evaluated: leftmost
0
1148 calculateIntersection(leftmost->data, storeLeftmost->data);
never executed: calculateIntersection(leftmost->data, storeLeftmost->data);
0
1149 if (rightmost)
never evaluated: rightmost
0
1150 calculateIntersection(storeRightmost->data, rightmost->data);
never executed: calculateIntersection(storeRightmost->data, rightmost->data);
0
1151}
never executed: }
0
1152 -
1153template <typename T> -
1154void QTriangulator<T>::ComplexToSimple::sortEdgeList(const QPodPoint eventPoint) -
1155{ -
1156 QIntersectionPoint eventPoint2 = ::qIntersectionPoint(eventPoint); -
1157 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint < eventPoint2) {
never evaluated: !m_topIntersection.isEmpty()
never evaluated: m_topIntersection.top().intersectionPoint < eventPoint2
0
1158 Intersection intersection = m_topIntersection.pop(); -
1159 -
1160 QIntersectionPoint currentIntersectionPoint = intersection.intersectionPoint; -
1161 int currentVertex = intersection.vertex; -
1162 -
1163 QRBTree<int>::Node *leftmost = m_edges.at(intersection.leftEdge).node; -
1164 QRBTree<int>::Node *rightmost = m_edges.at(intersection.rightEdge).node; -
1165 -
1166 for (;;) { -
1167 QRBTree<int>::Node *previous = m_edgeList.previous(leftmost); -
1168 if (!previous)
never evaluated: !previous
0
1169 break;
never executed: break;
0
1170 const Edge &edge = m_edges.at(previous->data); -
1171 const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from); -
1172 const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to); -
1173 if (!currentIntersectionPoint.isOnLine(u, v)) {
never evaluated: !currentIntersectionPoint.isOnLine(u, v)
0
1174 qt_noop(); -
1175 break;
never executed: break;
0
1176 } -
1177 leftmost = previous; -
1178 }
never executed: }
0
1179 -
1180 for (;;) { -
1181 QRBTree<int>::Node *next = m_edgeList.next(rightmost); -
1182 if (!next)
never evaluated: !next
0
1183 break;
never executed: break;
0
1184 const Edge &edge = m_edges.at(next->data); -
1185 const QPodPoint &u = m_parent->m_vertices.at((qint32)edge.from); -
1186 const QPodPoint &v = m_parent->m_vertices.at((qint32)edge.to); -
1187 if (!currentIntersectionPoint.isOnLine(u, v)) {
never evaluated: !currentIntersectionPoint.isOnLine(u, v)
0
1188 qt_noop(); -
1189 break;
never executed: break;
0
1190 } -
1191 rightmost = next; -
1192 }
never executed: }
0
1193 -
1194 qt_noop(); -
1195 splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint); -
1196 reorderEdgeListRange(leftmost, rightmost); -
1197 -
1198 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= currentIntersectionPoint)
never evaluated: !m_topIntersection.isEmpty()
never evaluated: m_topIntersection.top().intersectionPoint <= currentIntersectionPoint
0
1199 m_topIntersection.pop();
never executed: m_topIntersection.pop();
0
1200 -
1201 -
1202 -
1203 -
1204 -
1205 -
1206 }
never executed: }
0
1207}
never executed: }
0
1208 -
1209template <typename T> -
1210void QTriangulator<T>::ComplexToSimple::fillPriorityQueue() -
1211{ -
1212 m_events.reset(); -
1213 m_events.reserve(m_edges.size() * 2); -
1214 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1215 qt_noop(); -
1216 qt_noop(); -
1217 qt_noop(); -
1218 qt_noop(); -
1219 -
1220 if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) {
never evaluated: m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)
0
1221 QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper()); -
1222 QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower()); -
1223 Event upperEvent = {{upper.x, upper.y}, Event::Upper, i}; -
1224 Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i}; -
1225 m_events.add(upperEvent); -
1226 m_events.add(lowerEvent); -
1227 }
never executed: }
0
1228 }
never executed: }
0
1229 -
1230 std::sort(m_events.data(), m_events.data() + m_events.size()); -
1231}
never executed: }
0
1232 -
1233template <typename T> -
1234void QTriangulator<T>::ComplexToSimple::calculateIntersections() -
1235{ -
1236 fillPriorityQueue(); -
1237 -
1238 qt_noop(); -
1239 qt_noop(); -
1240 -
1241 -
1242 while (!m_events.isEmpty()) {
never evaluated: !m_events.isEmpty()
0
1243 Event event = m_events.last(); -
1244 sortEdgeList(event.point); -
1245 -
1246 -
1247 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> range = bounds(event.point); -
1248 QRBTree<int>::Node *leftNode = range.first ? m_edgeList.previous(range.first) : 0;
never evaluated: range.first
0
1249 int vertex = (event.type == Event::Upper ? m_edges.at(event.edge).upper() : m_edges.at(event.edge).lower());
never evaluated: event.type == Event::Upper
0
1250 QIntersectionPoint eventPoint = ::qIntersectionPoint(event.point); -
1251 -
1252 if (range.first != 0) {
never evaluated: range.first != 0
0
1253 splitEdgeListRange(range.first, range.second, vertex, eventPoint); -
1254 reorderEdgeListRange(range.first, range.second); -
1255 }
never executed: }
0
1256 -
1257 -
1258 while (!m_events.isEmpty() && m_events.last().point == event.point) {
never evaluated: !m_events.isEmpty()
never evaluated: m_events.last().point == event.point
0
1259 event = m_events.last(); -
1260 m_events.pop_back(); -
1261 int i = event.edge; -
1262 -
1263 if (m_edges.at(i).node) {
never evaluated: m_edges.at(i).node
0
1264 -
1265 qt_noop(); -
1266 QRBTree<int>::Node *left = m_edgeList.previous(m_edges.at(i).node); -
1267 QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node); -
1268 m_edgeList.deleteNode(m_edges.at(i).node); -
1269 if (!left || !right)
never evaluated: !left
never evaluated: !right
0
1270 continue;
never executed: continue;
0
1271 calculateIntersection(left->data, right->data); -
1272 } else {
never executed: }
0
1273 -
1274 qt_noop(); -
1275 QRBTree<int>::Node *left = searchEdgeLeftOf(i, leftNode); -
1276 m_edgeList.attachAfter(left, m_edges.at(i).node = m_edgeList.newNode()); -
1277 m_edges.at(i).node->data = i; -
1278 QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node); -
1279 if (left)
never evaluated: left
0
1280 calculateIntersection(left->data, i);
never executed: calculateIntersection(left->data, i);
0
1281 if (right)
never evaluated: right
0
1282 calculateIntersection(i, right->data);
never executed: calculateIntersection(i, right->data);
0
1283 }
never executed: }
0
1284 } -
1285 while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= eventPoint)
never evaluated: !m_topIntersection.isEmpty()
never evaluated: m_topIntersection.top().intersectionPoint <= eventPoint
0
1286 m_topIntersection.pop();
never executed: m_topIntersection.pop();
0
1287 -
1288 -
1289 -
1290 -
1291 }
never executed: }
0
1292 m_processedEdgePairs.clear(); -
1293}
never executed: }
0
1294 -
1295 -
1296 -
1297 -
1298 -
1299template <typename T> -
1300int QTriangulator<T>::ComplexToSimple::splitEdge(int splitIndex) -
1301{ -
1302 const Split &split = m_splits.at(splitIndex); -
1303 Edge &lowerEdge = m_edges.at(split.edge); -
1304 qt_noop(); -
1305 qt_noop(); -
1306 -
1307 if (lowerEdge.from == split.vertex)
never evaluated: lowerEdge.from == split.vertex
0
1308 return split.edge;
never executed: return split.edge;
0
1309 if (lowerEdge.to == split.vertex)
never evaluated: lowerEdge.to == split.vertex
0
1310 return lowerEdge.next;
never executed: return lowerEdge.next;
0
1311 -
1312 -
1313 -
1314 -
1315 -
1316 Edge upperEdge = lowerEdge; -
1317 upperEdge.mayIntersect |= !split.accurate; -
1318 lowerEdge.mayIntersect = !split.accurate; -
1319 if (lowerEdge.pointingUp) {
never evaluated: lowerEdge.pointingUp
0
1320 lowerEdge.to = upperEdge.from = split.vertex; -
1321 m_edges.add(upperEdge); -
1322 return m_edges.size() - 1;
never executed: return m_edges.size() - 1;
0
1323 } else { -
1324 lowerEdge.from = upperEdge.to = split.vertex; -
1325 m_edges.add(upperEdge); -
1326 return split.edge;
never executed: return split.edge;
0
1327 } -
1328} -
1329 -
1330template <typename T> -
1331bool QTriangulator<T>::ComplexToSimple::splitEdgesAtIntersections() -
1332{ -
1333 for (int i = 0; i < m_edges.size(); ++i)
never evaluated: i < m_edges.size()
0
1334 m_edges.at(i).mayIntersect = false;
never executed: m_edges.at(i).mayIntersect = false;
0
1335 bool checkForNewIntersections = false; -
1336 for (int i = 0; i < m_splits.size(); ++i) {
never evaluated: i < m_splits.size()
0
1337 splitEdge(i); -
1338 checkForNewIntersections |= !m_splits.at(i).accurate; -
1339 }
never executed: }
0
1340 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1341 m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp = -
1342 m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from); -
1343 }
never executed: }
0
1344 m_splits.reset(); -
1345 return checkForNewIntersections;
never executed: return checkForNewIntersections;
0
1346} -
1347 -
1348template <typename T> -
1349void QTriangulator<T>::ComplexToSimple::insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i) -
1350{ -
1351 -
1352 qt_noop(); -
1353 -
1354 -
1355 int windingNumber = m_edges.at(i).winding; -
1356 if (m_edges.at(i).originallyPointingUp)
never evaluated: m_edges.at(i).originallyPointingUp
0
1357 ++windingNumber;
never executed: ++windingNumber;
0
1358 -
1359 -
1360 qt_noop(); -
1361 -
1362 if ((m_parent->m_hint & QVectorPath::WindingFill) && windingNumber != 0 && windingNumber != 1)
never evaluated: (m_parent->m_hint & QVectorPath::WindingFill)
never evaluated: windingNumber != 0
never evaluated: windingNumber != 1
0
1363 return;
never executed: return;
0
1364 -
1365 -
1366 if (!orderedEdges.isEmpty()) {
never evaluated: !orderedEdges.isEmpty()
0
1367 int j = orderedEdges[orderedEdges.size() - 1]; -
1368 -
1369 if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1
never evaluated: m_edges.at(j).next == -1
never evaluated: m_edges.at(j).previous == -1
0
1370 && (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
never evaluated: (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
0
1371 && (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) {
never evaluated: (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))
0
1372 orderedEdges.removeLast(); -
1373 return;
never executed: return;
0
1374 } -
1375 }
never executed: }
0
1376 orderedEdges.append(i); -
1377}
never executed: }
0
1378 -
1379template <typename T> -
1380void QTriangulator<T>::ComplexToSimple::removeUnwantedEdgesAndConnect() -
1381{ -
1382 qt_noop(); -
1383 -
1384 fillPriorityQueue(); -
1385 -
1386 ShortArray orderedEdges; -
1387 -
1388 while (!m_events.isEmpty()) {
never evaluated: !m_events.isEmpty()
0
1389 Event event = m_events.last(); -
1390 int edgeIndex = event.edge; -
1391 orderedEdges.clear(); -
1392 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> b = outerBounds(event.point); -
1393 if (m_edgeList.root) {
never evaluated: m_edgeList.root
0
1394 QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
never evaluated: b.first
0
1395 -
1396 while (current != b.second) {
never evaluated: current != b.second
0
1397 qt_noop(); -
1398 qt_noop(); -
1399 qt_noop(); -
1400 qt_noop(); -
1401 insertEdgeIntoVectorIfWanted(orderedEdges, current->data); -
1402 current = m_edgeList.next(current); -
1403 }
never executed: }
0
1404 }
never executed: }
0
1405 -
1406 -
1407 do { -
1408 event = m_events.last(); -
1409 m_events.pop_back(); -
1410 edgeIndex = event.edge; -
1411 -
1412 -
1413 qt_noop(); -
1414 -
1415 if (m_edges.at(edgeIndex).node) {
never evaluated: m_edges.at(edgeIndex).node
0
1416 qt_noop(); -
1417 qt_noop(); -
1418 m_edgeList.deleteNode(m_edges.at(edgeIndex).node); -
1419 } else {
never executed: }
0
1420 qt_noop(); -
1421 qt_noop(); -
1422 QRBTree<int>::Node *left = searchEdgeLeftOf(edgeIndex, b.first); -
1423 m_edgeList.attachAfter(left, m_edges.at(edgeIndex).node = m_edgeList.newNode()); -
1424 m_edges.at(edgeIndex).node->data = edgeIndex; -
1425 }
never executed: }
0
1426 } while (!m_events.isEmpty() && m_events.last().point == event.point);
never evaluated: !m_events.isEmpty()
never evaluated: m_events.last().point == event.point
0
1427 -
1428 if (m_edgeList.root) {
never evaluated: m_edgeList.root
0
1429 QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
never evaluated: b.first
0
1430 -
1431 -
1432 int currentWindingNumber = (b.first ? m_edges.at(b.first->data).winding : 0);
never evaluated: b.first
0
1433 while (current != b.second) {
never evaluated: current != b.second
0
1434 qt_noop(); -
1435 -
1436 int i = current->data; -
1437 qt_noop(); -
1438 -
1439 -
1440 int ccwWindingNumber = m_edges.at(i).winding = currentWindingNumber; -
1441 if (m_edges.at(i).originallyPointingUp) {
never evaluated: m_edges.at(i).originallyPointingUp
0
1442 --m_edges.at(i).winding; -
1443 } else {
never executed: }
0
1444 ++m_edges.at(i).winding; -
1445 ++ccwWindingNumber; -
1446 }
never executed: }
0
1447 currentWindingNumber = m_edges.at(i).winding; -
1448 -
1449 -
1450 if ((ccwWindingNumber & 1) == 0) {
never evaluated: (ccwWindingNumber & 1) == 0
0
1451 qt_noop(); -
1452 qSwap(m_edges.at(i).from, m_edges.at(i).to); -
1453 m_edges.at(i).pointingUp = !m_edges.at(i).pointingUp; -
1454 }
never executed: }
0
1455 -
1456 current = m_edgeList.next(current); -
1457 }
never executed: }
0
1458 -
1459 -
1460 current = (b.second ? m_edgeList.previous(b.second) : m_edgeList.back(m_edgeList.root));
never evaluated: b.second
0
1461 while (current != b.first) {
never evaluated: current != b.first
0
1462 qt_noop(); -
1463 qt_noop(); -
1464 insertEdgeIntoVectorIfWanted(orderedEdges, current->data); -
1465 current = m_edgeList.previous(current); -
1466 }
never executed: }
0
1467 }
never executed: }
0
1468 if (orderedEdges.isEmpty())
never evaluated: orderedEdges.isEmpty()
0
1469 continue;
never executed: continue;
0
1470 -
1471 qt_noop(); -
1472 -
1473 -
1474 -
1475 int i; -
1476 if (m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) == event.point) {
never evaluated: m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) == event.point
0
1477 i = 1; -
1478 int copy = orderedEdges[0]; -
1479 orderedEdges.append(copy); -
1480 } else {
never executed: }
0
1481 qt_noop(); -
1482 i = 0; -
1483 }
never executed: }
0
1484 -
1485 -
1486 int pointIndex = 2147483647; -
1487 for (int j = i; j < orderedEdges.size(); j += 2) {
never evaluated: j < orderedEdges.size()
0
1488 qt_noop(); -
1489 qt_noop(); -
1490 qt_noop(); -
1491 if (m_edges.at(orderedEdges[j]).to < pointIndex)
never evaluated: m_edges.at(orderedEdges[j]).to < pointIndex
0
1492 pointIndex = m_edges.at(orderedEdges[j]).to;
never executed: pointIndex = m_edges.at(orderedEdges[j]).to;
0
1493 if (m_edges.at(orderedEdges[j + 1]).from < pointIndex)
never evaluated: m_edges.at(orderedEdges[j + 1]).from < pointIndex
0
1494 pointIndex = m_edges.at(orderedEdges[j + 1]).from;
never executed: pointIndex = m_edges.at(orderedEdges[j + 1]).from;
0
1495 }
never executed: }
0
1496 -
1497 for (; i < orderedEdges.size(); i += 2) {
never evaluated: i < orderedEdges.size()
0
1498 -
1499 m_edges.at(orderedEdges[i]).to = m_edges.at(orderedEdges[i + 1]).from = pointIndex; -
1500 -
1501 qt_noop(); -
1502 qt_noop(); -
1503 -
1504 m_edges.at(orderedEdges[i]).next = orderedEdges[i + 1]; -
1505 m_edges.at(orderedEdges[i + 1]).previous = orderedEdges[i]; -
1506 }
never executed: }
0
1507 }
never executed: }
0
1508}
never executed: }
0
1509 -
1510template <typename T> -
1511void QTriangulator<T>::ComplexToSimple::removeUnusedPoints() { -
1512 QBitArray used(m_parent->m_vertices.size(), false); -
1513 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1514 qt_noop(); -
1515 if (m_edges.at(i).next != -1)
never evaluated: m_edges.at(i).next != -1
0
1516 used.setBit(m_edges.at(i).from);
never executed: used.setBit(m_edges.at(i).from);
0
1517 }
never executed: }
0
1518 QDataBuffer<quint32> newMapping(m_parent->m_vertices.size()); -
1519 newMapping.resize(m_parent->m_vertices.size()); -
1520 int count = 0; -
1521 for (int i = 0; i < m_parent->m_vertices.size(); ++i) {
never evaluated: i < m_parent->m_vertices.size()
0
1522 if (used.at(i)) {
never evaluated: used.at(i)
0
1523 m_parent->m_vertices.at(count) = m_parent->m_vertices.at(i); -
1524 newMapping.at(i) = count; -
1525 ++count; -
1526 }
never executed: }
0
1527 }
never executed: }
0
1528 m_parent->m_vertices.resize(count); -
1529 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1530 m_edges.at(i).from = newMapping.at(m_edges.at(i).from); -
1531 m_edges.at(i).to = newMapping.at(m_edges.at(i).to); -
1532 }
never executed: }
0
1533}
never executed: }
0
1534 -
1535template <typename T> -
1536inline bool QTriangulator<T>::ComplexToSimple::Event::operator < (const Event &other) const -
1537{ -
1538 if (point == other.point)
never evaluated: point == other.point
0
1539 return type < other.type;
never executed: return type < other.type;
0
1540 return other.point < point;
never executed: return other.point < point;
0
1541} -
1542template <typename T> -
1543void QTriangulator<T>::SimpleToMonotone::decompose() -
1544{ -
1545 setupDataStructures(); -
1546 removeZeroLengthEdges(); -
1547 monotoneDecomposition(); -
1548 -
1549 m_parent->m_indices.clear(); -
1550 QBitArray processed(m_edges.size(), false); -
1551 for (int first = 0; first < m_edges.size(); ++first) {
never evaluated: first < m_edges.size()
0
1552 if (processed.at(first))
never evaluated: processed.at(first)
0
1553 continue;
never executed: continue;
0
1554 int i = first; -
1555 do { -
1556 qt_noop(); -
1557 qt_noop(); -
1558 m_parent->m_indices.push_back(m_edges.at(i).from); -
1559 processed.setBit(i); -
1560 i = m_edges.at(i).next; -
1561 } while (i != first);
never executed: }
never evaluated: i != first
0
1562 if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != T(-1))
never evaluated: m_parent->m_indices.size() > 0
never evaluated: m_parent->m_indices.back() != T(-1)
0
1563 m_parent->m_indices.push_back(T(-1));
never executed: m_parent->m_indices.push_back(T(-1));
0
1564 }
never executed: }
0
1565}
never executed: }
0
1566 -
1567template <typename T> -
1568void QTriangulator<T>::SimpleToMonotone::setupDataStructures() -
1569{ -
1570 int i = 0; -
1571 Edge e; -
1572 e.node = 0; -
1573 e.twin = -1; -
1574 -
1575 while (i + 3 <= m_parent->m_indices.size()) {
never evaluated: i + 3 <= m_parent->m_indices.size()
0
1576 int start = m_edges.size(); -
1577 -
1578 do { -
1579 e.from = m_parent->m_indices.at(i); -
1580 e.type = RegularVertex; -
1581 e.next = m_edges.size() + 1; -
1582 e.previous = m_edges.size() - 1; -
1583 m_edges.add(e); -
1584 ++i; -
1585 qt_noop(); -
1586 } while (m_parent->m_indices.at(i) != T(-1));
never executed: }
never evaluated: m_parent->m_indices.at(i) != T(-1)
0
1587 -
1588 m_edges.last().next = start; -
1589 m_edges.at(start).previous = m_edges.size() - 1; -
1590 ++i; -
1591 }
never executed: }
0
1592 -
1593 for (i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1594 m_edges.at(i).to = m_edges.at(m_edges.at(i).next).from; -
1595 m_edges.at(i).pointingUp = m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from); -
1596 m_edges.at(i).helper = -1; -
1597 }
never executed: }
0
1598}
never executed: }
0
1599 -
1600template <typename T> -
1601void QTriangulator<T>::SimpleToMonotone::removeZeroLengthEdges() -
1602{ -
1603 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1604 if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) {
never evaluated: m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)
0
1605 m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next; -
1606 m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous; -
1607 m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from; -
1608 m_edges.at(i).next = -1; -
1609 }
never executed: }
0
1610 }
never executed: }
0
1611 -
1612 QDataBuffer<int> newMapping(m_edges.size()); -
1613 newMapping.resize(m_edges.size()); -
1614 int count = 0; -
1615 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1616 if (m_edges.at(i).next != -1) {
never evaluated: m_edges.at(i).next != -1
0
1617 m_edges.at(count) = m_edges.at(i); -
1618 newMapping.at(i) = count; -
1619 ++count; -
1620 }
never executed: }
0
1621 }
never executed: }
0
1622 m_edges.resize(count); -
1623 for (int i = 0; i < m_edges.size(); ++i) {
never evaluated: i < m_edges.size()
0
1624 m_edges.at(i).next = newMapping.at(m_edges.at(i).next); -
1625 m_edges.at(i).previous = newMapping.at(m_edges.at(i).previous); -
1626 }
never executed: }
0
1627}
never executed: }
0
1628 -
1629template <typename T> -
1630void QTriangulator<T>::SimpleToMonotone::fillPriorityQueue() -
1631{ -
1632 m_upperVertex.reset(); -
1633 m_upperVertex.reserve(m_edges.size()); -
1634 for (int i = 0; i < m_edges.size(); ++i)
never evaluated: i < m_edges.size()
0
1635 m_upperVertex.add(i);
never executed: m_upperVertex.add(i);
0
1636 CompareVertices cmp(this); -
1637 std::sort(m_upperVertex.data(), m_upperVertex.data() + m_upperVertex.size(), cmp); -
1638 -
1639 -
1640 -
1641}
never executed: }
0
1642 -
1643template <typename T> -
1644bool QTriangulator<T>::SimpleToMonotone::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const -
1645{ -
1646 const Edge &leftEdge = m_edges.at(leftEdgeIndex); -
1647 const Edge &rightEdge = m_edges.at(rightEdgeIndex); -
1648 const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper()); -
1649 const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower()); -
1650 qint64 d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.upper()), l, u); -
1651 -
1652 if (d == 0)
never evaluated: d == 0
0
1653 d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
never executed: d = ::qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
0
1654 return d < 0;
never executed: return d < 0;
0
1655} -
1656 -
1657 -
1658template <typename T> -
1659QRBTree<int>::Node *QTriangulator<T>::SimpleToMonotone::searchEdgeLeftOfEdge(int edgeIndex) const -
1660{ -
1661 QRBTree<int>::Node *current = m_edgeList.root; -
1662 QRBTree<int>::Node *result = 0; -
1663 while (current) {
never evaluated: current
0
1664 if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
never evaluated: edgeIsLeftOfEdge(edgeIndex, current->data)
0
1665 current = current->left; -
1666 } else {
never executed: }
0
1667 result = current; -
1668 current = current->right; -
1669 }
never executed: }
0
1670 } -
1671 return result;
never executed: return result;
0
1672} -
1673 -
1674 -
1675template <typename T> -
1676QRBTree<int>::Node *QTriangulator<T>::SimpleToMonotone::searchEdgeLeftOfPoint(int pointIndex) const -
1677{ -
1678 QRBTree<int>::Node *current = m_edgeList.root; -
1679 QRBTree<int>::Node *result = 0; -
1680 while (current) {
never evaluated: current
0
1681 const QPodPoint &p1 = m_parent->m_vertices.at(m_edges.at(current->data).lower()); -
1682 const QPodPoint &p2 = m_parent->m_vertices.at(m_edges.at(current->data).upper()); -
1683 qint64 d = ::qPointDistanceFromLine(m_parent->m_vertices.at(pointIndex), p1, p2); -
1684 if (d <= 0) {
never evaluated: d <= 0
0
1685 current = current->left; -
1686 } else {
never executed: }
0
1687 result = current; -
1688 current = current->right; -
1689 }
never executed: }
0
1690 } -
1691 return result;
never executed: return result;
0
1692} -
1693 -
1694template <typename T> -
1695void QTriangulator<T>::SimpleToMonotone::classifyVertex(int i) -
1696{ -
1697 Edge &e2 = m_edges.at(i); -
1698 const Edge &e1 = m_edges.at(e2.previous); -
1699 -
1700 bool startOrSplit = (e1.pointingUp && !e2.pointingUp);
never evaluated: e1.pointingUp
never evaluated: !e2.pointingUp
0
1701 bool endOrMerge = (!e1.pointingUp && e2.pointingUp);
never evaluated: !e1.pointingUp
never evaluated: e2.pointingUp
0
1702 -
1703 const QPodPoint &p1 = m_parent->m_vertices.at(e1.from); -
1704 const QPodPoint &p2 = m_parent->m_vertices.at(e2.from); -
1705 const QPodPoint &p3 = m_parent->m_vertices.at(e2.to); -
1706 qint64 d = ::qPointDistanceFromLine(p1, p2, p3); -
1707 qt_noop(); -
1708 -
1709 e2.type = RegularVertex; -
1710 -
1711 if (m_clockwiseOrder) {
never evaluated: m_clockwiseOrder
0
1712 if (startOrSplit)
never evaluated: startOrSplit
0
1713 e2.type = (d < 0 ? SplitVertex : StartVertex);
never executed: e2.type = (d < 0 ? SplitVertex : StartVertex);
never evaluated: d < 0
0
1714 else if (endOrMerge)
never evaluated: endOrMerge
0
1715 e2.type = (d < 0 ? MergeVertex : EndVertex);
never executed: e2.type = (d < 0 ? MergeVertex : EndVertex);
never evaluated: d < 0
0
1716 } else { -
1717 if (startOrSplit)
never evaluated: startOrSplit
0
1718 e2.type = (d > 0 ? SplitVertex : StartVertex);
never executed: e2.type = (d > 0 ? SplitVertex : StartVertex);
never evaluated: d > 0
0
1719 else if (endOrMerge)
never evaluated: endOrMerge
0
1720 e2.type = (d > 0 ? MergeVertex : EndVertex);
never executed: e2.type = (d > 0 ? MergeVertex : EndVertex);
never evaluated: d > 0
0
1721 } -
1722} -
1723 -
1724template <typename T> -
1725void QTriangulator<T>::SimpleToMonotone::classifyVertices() -
1726{ -
1727 for (int i = 0; i < m_edges.size(); ++i)
never evaluated: i < m_edges.size()
0
1728 classifyVertex(i);
never executed: classifyVertex(i);
0
1729}
never executed: }
0
1730 -
1731template <typename T> -
1732bool QTriangulator<T>::SimpleToMonotone::pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3) -
1733{ -
1734 bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1); -
1735 bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2); -
1736 -
1737 if (qPointIsLeftOfLine(v1, v2, v3))
never evaluated: qPointIsLeftOfLine(v1, v2, v3)
0
1738 return leftOfPreviousEdge && leftOfNextEdge;
never executed: return leftOfPreviousEdge && leftOfNextEdge;
0
1739 else -
1740 return leftOfPreviousEdge || leftOfNextEdge;
never executed: return leftOfPreviousEdge || leftOfNextEdge;
0
1741} -
1742 -
1743template <typename T> -
1744bool QTriangulator<T>::SimpleToMonotone::pointIsInSector(int vertex, int sector) -
1745{ -
1746 const QPodPoint &center = m_parent->m_vertices.at(m_edges.at(sector).from); -
1747 -
1748 while (m_parent->m_vertices.at(m_edges.at(vertex).from) == center)
never evaluated: m_parent->m_vertices.at(m_edges.at(vertex).from) == center
0
1749 vertex = m_edges.at(vertex).next;
never executed: vertex = m_edges.at(vertex).next;
0
1750 int next = m_edges.at(sector).next; -
1751 while (m_parent->m_vertices.at(m_edges.at(next).from) == center)
never evaluated: m_parent->m_vertices.at(m_edges.at(next).from) == center
0
1752 next = m_edges.at(next).next;
never executed: next = m_edges.at(next).next;
0
1753 int previous = m_edges.at(sector).previous; -
1754 while (m_parent->m_vertices.at(m_edges.at(previous).from) == center)
never evaluated: m_parent->m_vertices.at(m_edges.at(previous).from) == center
0
1755 previous = m_edges.at(previous).previous;
never executed: previous = m_edges.at(previous).previous;
0
1756 -
1757 const QPodPoint &p = m_parent->m_vertices.at(m_edges.at(vertex).from); -
1758 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(previous).from); -
1759 const QPodPoint &v3 = m_parent->m_vertices.at(m_edges.at(next).from); -
1760 if (m_clockwiseOrder)
never evaluated: m_clockwiseOrder
0
1761 return pointIsInSector(p, v3, center, v1);
never executed: return pointIsInSector(p, v3, center, v1);
0
1762 else -
1763 return pointIsInSector(p, v1, center, v3);
never executed: return pointIsInSector(p, v1, center, v3);
0
1764} -
1765 -
1766template <typename T> -
1767int QTriangulator<T>::SimpleToMonotone::findSector(int edge, int vertex) -
1768{ -
1769 while (!pointIsInSector(vertex, edge)) {
never evaluated: !pointIsInSector(vertex, edge)
0
1770 edge = m_edges.at(m_edges.at(edge).previous).twin; -
1771 qt_noop(); -
1772 }
never executed: }
0
1773 return edge;
never executed: return edge;
0
1774} -
1775 -
1776template <typename T> -
1777void QTriangulator<T>::SimpleToMonotone::createDiagonal(int lower, int upper) -
1778{ -
1779 lower = findSector(lower, upper); -
1780 upper = findSector(upper, lower); -
1781 -
1782 int prevLower = m_edges.at(lower).previous; -
1783 int prevUpper = m_edges.at(upper).previous; -
1784 -
1785 Edge e; -
1786 -
1787 e.twin = m_edges.size() + 1; -
1788 e.next = upper; -
1789 e.previous = prevLower; -
1790 e.from = m_edges.at(lower).from; -
1791 e.to = m_edges.at(upper).from; -
1792 m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size()); -
1793 m_edges.add(e); -
1794 -
1795 e.twin = m_edges.size() - 1; -
1796 e.next = lower; -
1797 e.previous = prevUpper; -
1798 e.from = m_edges.at(upper).from; -
1799 e.to = m_edges.at(lower).from; -
1800 m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size()); -
1801 m_edges.add(e); -
1802}
never executed: }
0
1803 -
1804template <typename T> -
1805void QTriangulator<T>::SimpleToMonotone::monotoneDecomposition() -
1806{ -
1807 if (m_edges.isEmpty())
never evaluated: m_edges.isEmpty()
0
1808 return;
never executed: return;
0
1809 -
1810 qt_noop(); -
1811 QDataBuffer<QPair<int, int> > diagonals(m_upperVertex.size()); -
1812 -
1813 int i = 0; -
1814 for (int index = 1; index < m_edges.size(); ++index) {
never evaluated: index < m_edges.size()
0
1815 if (m_parent->m_vertices.at(m_edges.at(index).from) < m_parent->m_vertices.at(m_edges.at(i).from))
never evaluated: m_parent->m_vertices.at(m_edges.at(index).from) < m_parent->m_vertices.at(m_edges.at(i).from)
0
1816 i = index;
never executed: i = index;
0
1817 }
never executed: }
0
1818 qt_noop(); -
1819 int j = m_edges.at(i).previous; -
1820 qt_noop(); -
1821 m_clockwiseOrder = qPointIsLeftOfLine(m_parent->m_vertices.at((quint32)m_edges.at(i).from), -
1822 m_parent->m_vertices.at((quint32)m_edges.at(j).from), m_parent->m_vertices.at((quint32)m_edges.at(i).to)); -
1823 -
1824 classifyVertices(); -
1825 fillPriorityQueue(); -
1826 -
1827 -
1828 -
1829 -
1830 -
1831 while (!m_upperVertex.isEmpty()) {
never evaluated: !m_upperVertex.isEmpty()
0
1832 i = m_upperVertex.last(); -
1833 qt_noop(); -
1834 m_upperVertex.pop_back(); -
1835 j = m_edges.at(i).previous; -
1836 qt_noop(); -
1837 -
1838 QRBTree<int>::Node *leftEdgeNode = 0; -
1839 -
1840 switch (m_edges.at(i).type) { -
1841 case RegularVertex: -
1842 -
1843 if (m_edges.at(i).pointingUp == m_clockwiseOrder) {
never evaluated: m_edges.at(i).pointingUp == m_clockwiseOrder
0
1844 if (m_edges.at(i).node) {
never evaluated: m_edges.at(i).node
0
1845 qt_noop(); -
1846 if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(i).helper).type == MergeVertex
0
1847 diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
0
1848 m_edges.at(j).node = m_edges.at(i).node; -
1849 m_edges.at(i).node = 0; -
1850 m_edges.at(j).node->data = j; -
1851 m_edges.at(j).helper = i; -
1852 } else if (m_edges.at(j).node) {
never executed: }
never evaluated: m_edges.at(j).node
0
1853 qt_noop(); -
1854 if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(j).helper).type == MergeVertex
0
1855 diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
0
1856 m_edges.at(i).node = m_edges.at(j).node; -
1857 m_edges.at(j).node = 0; -
1858 m_edges.at(i).node->data = i; -
1859 m_edges.at(i).helper = i; -
1860 } else {
never executed: }
0
1861 QMessageLogger("opengl/qtriangulator.cpp", 2090, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#1)"); -
1862 }
never executed: }
0
1863 } else { -
1864 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from); -
1865 if (leftEdgeNode) {
never evaluated: leftEdgeNode
0
1866 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex
0
1867 diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
0
1868 m_edges.at(leftEdgeNode->data).helper = i; -
1869 } else {
never executed: }
0
1870 QMessageLogger("opengl/qtriangulator.cpp", 2099, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#2)"); -
1871 }
never executed: }
0
1872 } -
1873 break;
never executed: break;
0
1874 case SplitVertex: -
1875 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from); -
1876 if (leftEdgeNode) {
never evaluated: leftEdgeNode
0
1877 diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper)); -
1878 m_edges.at(leftEdgeNode->data).helper = i; -
1879 } else {
never executed: }
0
1880 QMessageLogger("opengl/qtriangulator.cpp", 2109, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#3)"); -
1881 }
never executed: }
0
1882 -
1883 case StartVertex:
code before this statement never executed: case StartVertex:
0
1884 if (m_clockwiseOrder) {
never evaluated: m_clockwiseOrder
0
1885 leftEdgeNode = searchEdgeLeftOfEdge(j); -
1886 QRBTree<int>::Node *node = m_edgeList.newNode(); -
1887 node->data = j; -
1888 m_edges.at(j).node = node; -
1889 m_edges.at(j).helper = i; -
1890 m_edgeList.attachAfter(leftEdgeNode, node); -
1891 qt_noop(); -
1892 } else {
never executed: }
0
1893 leftEdgeNode = searchEdgeLeftOfEdge(i); -
1894 QRBTree<int>::Node *node = m_edgeList.newNode(); -
1895 node->data = i; -
1896 m_edges.at(i).node = node; -
1897 m_edges.at(i).helper = i; -
1898 m_edgeList.attachAfter(leftEdgeNode, node); -
1899 qt_noop(); -
1900 }
never executed: }
0
1901 break;
never executed: break;
0
1902 case MergeVertex: -
1903 leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from); -
1904 if (leftEdgeNode) {
never evaluated: leftEdgeNode
0
1905 if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex
0
1906 diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
0
1907 m_edges.at(leftEdgeNode->data).helper = i; -
1908 } else {
never executed: }
0
1909 QMessageLogger("opengl/qtriangulator.cpp", 2138, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#4)"); -
1910 }
never executed: }
0
1911 -
1912 case EndVertex:
code before this statement never executed: case EndVertex:
0
1913 if (m_clockwiseOrder) {
never evaluated: m_clockwiseOrder
0
1914 if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(i).helper).type == MergeVertex
0
1915 diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
0
1916 if (m_edges.at(i).node) {
never evaluated: m_edges.at(i).node
0
1917 m_edgeList.deleteNode(m_edges.at(i).node); -
1918 qt_noop(); -
1919 } else {
never executed: }
0
1920 QMessageLogger("opengl/qtriangulator.cpp", 2149, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#5)"); -
1921 }
never executed: }
0
1922 } else { -
1923 if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
never evaluated: m_edges.at(m_edges.at(j).helper).type == MergeVertex
0
1924 diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
never executed: diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
0
1925 if (m_edges.at(j).node) {
never evaluated: m_edges.at(j).node
0
1926 m_edgeList.deleteNode(m_edges.at(j).node); -
1927 qt_noop(); -
1928 } else {
never executed: }
0
1929 QMessageLogger("opengl/qtriangulator.cpp", 2158, __PRETTY_FUNCTION__).warning("Inconsistent polygon. (#6)"); -
1930 }
never executed: }
0
1931 } -
1932 break;
never executed: break;
0
1933 } -
1934 }
never executed: }
0
1935 -
1936 for (int i = 0; i < diagonals.size(); ++i)
never evaluated: i < diagonals.size()
0
1937 createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
never executed: createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
0
1938}
never executed: }
0
1939 -
1940template <typename T> -
1941bool QTriangulator<T>::SimpleToMonotone::CompareVertices::operator () (int i, int j) const -
1942{ -
1943 if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from)
never evaluated: m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from
0
1944 return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
never executed: return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
0
1945 return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) > 0
1946 m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
never executed: return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) > m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from);
0
1947} -
1948 -
1949 -
1950 -
1951 -
1952template <typename T> -
1953void QTriangulator<T>::MonotoneToTriangles::decompose() -
1954{ -
1955 QVector<T> result; -
1956 QDataBuffer<int> stack(m_parent->m_indices.size()); -
1957 m_first = 0; -
1958 -
1959 while (m_first + 3 <= m_parent->m_indices.size()) {
never evaluated: m_first + 3 <= m_parent->m_indices.size()
0
1960 m_length = 0; -
1961 while (m_parent->m_indices.at(m_first + m_length) != T(-1)) {
never evaluated: m_parent->m_indices.at(m_first + m_length) != T(-1)
0
1962 ++m_length; -
1963 qt_noop(); -
1964 }
never executed: }
0
1965 if (m_length < 3) {
never evaluated: m_length < 3
0
1966 m_first += m_length + 1; -
1967 continue;
never executed: continue;
0
1968 } -
1969 -
1970 int minimum = 0; -
1971 while (less(next(minimum), minimum))
never evaluated: less(next(minimum), minimum)
0
1972 minimum = next(minimum);
never executed: minimum = next(minimum);
0
1973 while (less(previous(minimum), minimum))
never evaluated: less(previous(minimum), minimum)
0
1974 minimum = previous(minimum);
never executed: minimum = previous(minimum);
0
1975 -
1976 stack.reset(); -
1977 stack.add(minimum); -
1978 int left = previous(minimum); -
1979 int right = next(minimum); -
1980 bool stackIsOnLeftSide; -
1981 bool clockwiseOrder = leftOfEdge(minimum, left, right); -
1982 -
1983 if (less(left, right)) {
never evaluated: less(left, right)
0
1984 stack.add(left); -
1985 left = previous(left); -
1986 stackIsOnLeftSide = true; -
1987 } else {
never executed: }
0
1988 stack.add(right); -
1989 right = next(right); -
1990 stackIsOnLeftSide = false; -
1991 }
never executed: }
0
1992 -
1993 for (int count = 0; count + 2 < m_length; ++count)
never evaluated: count + 2 < m_length
0
1994 { -
1995 qt_noop(); -
1996 if (less(left, right)) {
never evaluated: less(left, right)
0
1997 if (stackIsOnLeftSide == false) {
never evaluated: stackIsOnLeftSide == false
0
1998 for (int i = 0; i + 1 < stack.size(); ++i) {
never evaluated: i + 1 < stack.size()
0
1999 result.push_back(indices(stack.at(i + 1))); -
2000 result.push_back(indices(left)); -
2001 result.push_back(indices(stack.at(i))); -
2002 }
never executed: }
0
2003 stack.first() = stack.last(); -
2004 stack.resize(1); -
2005 } else {
never executed: }
0
2006 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))) {
never evaluated: stack.size() >= 2
never evaluated: (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))
0
2007 result.push_back(indices(stack.at(stack.size() - 2))); -
2008 result.push_back(indices(left)); -
2009 result.push_back(indices(stack.last())); -
2010 stack.pop_back(); -
2011 }
never executed: }
0
2012 }
never executed: }
0
2013 stack.add(left); -
2014 left = previous(left); -
2015 stackIsOnLeftSide = true; -
2016 } else {
never executed: }
0
2017 if (stackIsOnLeftSide == true) {
never evaluated: stackIsOnLeftSide == true
0
2018 for (int i = 0; i + 1 < stack.size(); ++i) {
never evaluated: i + 1 < stack.size()
0
2019 result.push_back(indices(stack.at(i))); -
2020 result.push_back(indices(right)); -
2021 result.push_back(indices(stack.at(i + 1))); -
2022 }
never executed: }
0
2023 stack.first() = stack.last(); -
2024 stack.resize(1); -
2025 } else {
never executed: }
0
2026 while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))) {
never evaluated: stack.size() >= 2
never evaluated: (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))
0
2027 result.push_back(indices(stack.last())); -
2028 result.push_back(indices(right)); -
2029 result.push_back(indices(stack.at(stack.size() - 2))); -
2030 stack.pop_back(); -
2031 }
never executed: }
0
2032 }
never executed: }
0
2033 stack.add(right); -
2034 right = next(right); -
2035 stackIsOnLeftSide = false; -
2036 }
never executed: }
0
2037 } -
2038 -
2039 m_first += m_length + 1; -
2040 }
never executed: }
0
2041 m_parent->m_indices = result; -
2042}
never executed: }
0
2043 -
2044 -
2045 -
2046 -
2047 -
2048static bool hasElementIndexUint() -
2049{ -
2050 QOpenGLContext *context = QOpenGLContext::currentContext(); -
2051 if (!context)
never evaluated: !context
0
2052 return false;
never executed: return false;
0
2053 return static_cast<QOpenGLExtensions *>(context->functions())->hasOpenGLExtension(QOpenGLExtensions::ElementIndexUint);
never executed: return static_cast<QOpenGLExtensions *>(context->functions())->hasOpenGLExtension(QOpenGLExtensions::ElementIndexUint);
0
2054} -
2055 -
2056__attribute__((visibility("default"))) QTriangleSet qTriangulate(const qreal *polygon, -
2057 int count, uint hint, const QTransform &matrix) -
2058{ -
2059 QTriangleSet triangleSet; -
2060 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2061 QTriangulator<quint32> triangulator; -
2062 triangulator.initialize(polygon, count, hint, matrix); -
2063 QVertexSet<quint32> vertexSet = triangulator.triangulate(); -
2064 triangleSet.vertices = vertexSet.vertices; -
2065 triangleSet.indices.setDataUint(vertexSet.indices); -
2066 -
2067 } else {
never executed: }
0
2068 QTriangulator<quint16> triangulator; -
2069 triangulator.initialize(polygon, count, hint, matrix); -
2070 QVertexSet<quint16> vertexSet = triangulator.triangulate(); -
2071 triangleSet.vertices = vertexSet.vertices; -
2072 triangleSet.indices.setDataUshort(vertexSet.indices); -
2073 }
never executed: }
0
2074 return triangleSet;
never executed: return triangleSet;
0
2075} -
2076 -
2077__attribute__((visibility("default"))) QTriangleSet qTriangulate(const QVectorPath &path, -
2078 const QTransform &matrix, qreal lod) -
2079{ -
2080 QTriangleSet triangleSet; -
2081 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2082 QTriangulator<quint32> triangulator; -
2083 triangulator.initialize(path, matrix, lod); -
2084 QVertexSet<quint32> vertexSet = triangulator.triangulate(); -
2085 triangleSet.vertices = vertexSet.vertices; -
2086 triangleSet.indices.setDataUint(vertexSet.indices); -
2087 } else {
never executed: }
0
2088 QTriangulator<quint16> triangulator; -
2089 triangulator.initialize(path, matrix, lod); -
2090 QVertexSet<quint16> vertexSet = triangulator.triangulate(); -
2091 triangleSet.vertices = vertexSet.vertices; -
2092 triangleSet.indices.setDataUshort(vertexSet.indices); -
2093 }
never executed: }
0
2094 return triangleSet;
never executed: return triangleSet;
0
2095} -
2096 -
2097QTriangleSet qTriangulate(const QPainterPath &path, -
2098 const QTransform &matrix, qreal lod) -
2099{ -
2100 QTriangleSet triangleSet; -
2101 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2102 QTriangulator<quint32> triangulator; -
2103 triangulator.initialize(path, matrix, lod); -
2104 QVertexSet<quint32> vertexSet = triangulator.triangulate(); -
2105 triangleSet.vertices = vertexSet.vertices; -
2106 triangleSet.indices.setDataUint(vertexSet.indices); -
2107 } else {
never executed: }
0
2108 QTriangulator<quint16> triangulator; -
2109 triangulator.initialize(path, matrix, lod); -
2110 QVertexSet<quint16> vertexSet = triangulator.triangulate(); -
2111 triangleSet.vertices = vertexSet.vertices; -
2112 triangleSet.indices.setDataUshort(vertexSet.indices); -
2113 }
never executed: }
0
2114 return triangleSet;
never executed: return triangleSet;
0
2115} -
2116 -
2117QPolylineSet qPolyline(const QVectorPath &path, -
2118 const QTransform &matrix, qreal lod) -
2119{ -
2120 QPolylineSet polyLineSet; -
2121 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2122 QTriangulator<quint32> triangulator; -
2123 triangulator.initialize(path, matrix, lod); -
2124 QVertexSet<quint32> vertexSet = triangulator.polyline(); -
2125 polyLineSet.vertices = vertexSet.vertices; -
2126 polyLineSet.indices.setDataUint(vertexSet.indices); -
2127 } else {
never executed: }
0
2128 QTriangulator<quint16> triangulator; -
2129 triangulator.initialize(path, matrix, lod); -
2130 QVertexSet<quint16> vertexSet = triangulator.polyline(); -
2131 polyLineSet.vertices = vertexSet.vertices; -
2132 polyLineSet.indices.setDataUshort(vertexSet.indices); -
2133 }
never executed: }
0
2134 return polyLineSet;
never executed: return polyLineSet;
0
2135} -
2136 -
2137QPolylineSet qPolyline(const QPainterPath &path, -
2138 const QTransform &matrix, qreal lod) -
2139{ -
2140 QPolylineSet polyLineSet; -
2141 if (hasElementIndexUint()) {
never evaluated: hasElementIndexUint()
0
2142 QTriangulator<quint32> triangulator; -
2143 triangulator.initialize(path, matrix, lod); -
2144 QVertexSet<quint32> vertexSet = triangulator.polyline(); -
2145 polyLineSet.vertices = vertexSet.vertices; -
2146 polyLineSet.indices.setDataUint(vertexSet.indices); -
2147 } else {
never executed: }
0
2148 QTriangulator<quint16> triangulator; -
2149 triangulator.initialize(path, matrix, lod); -
2150 QVertexSet<quint16> vertexSet = triangulator.polyline(); -
2151 polyLineSet.vertices = vertexSet.vertices; -
2152 polyLineSet.indices.setDataUshort(vertexSet.indices); -
2153 }
never executed: }
0
2154 return polyLineSet;
never executed: return polyLineSet;
0
2155} -
2156 -
2157 -
2158 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial