source: trunk/src/opengl/gl2paintengineex/qtriangulator.cpp@ 944

Last change on this file since 944 was 846, checked in by Dmitry A. Kuminov, 15 years ago

trunk: Merged in qt 4.7.2 sources from branches/vendor/nokia/qt.
File size: 106.7 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
4** All rights reserved.
5** Contact: Nokia Corporation ([email protected])
6**
7** This file is part of the QtOpenGL module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial Usage
11** Licensees holding valid Qt Commercial licenses may use this file in
12** accordance with the Qt Commercial License Agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and Nokia.
15**
16** GNU Lesser General Public License Usage
17** Alternatively, this file may be used under the terms of the GNU Lesser
18** General Public License version 2.1 as published by the Free Software
19** Foundation and appearing in the file LICENSE.LGPL included in the
20** packaging of this file. Please review the following information to
21** ensure the GNU Lesser General Public License version 2.1 requirements
22** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
23**
24** In addition, as a special exception, Nokia gives you certain additional
25** rights. These rights are described in the Nokia Qt LGPL Exception
26** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you have questions regarding the use of this file, please contact
37** Nokia at [email protected].
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42#include "qtriangulator_p.h"
43
44#include <QtGui/qdialog.h>
45#include <QtGui/qevent.h>
46#include <QtGui/qpainter.h>
47#include <QtGui/qpainterpath.h>
48#include <QtGui/private/qbezier_p.h>
49#include <QtGui/private/qdatabuffer_p.h>
50#include <QtCore/qbitarray.h>
51#include <QtCore/qvarlengtharray.h>
52#include <QtCore/qqueue.h>
53#include <QtCore/qglobal.h>
54#include <QtCore/qpoint.h>
55#include <QtCore/qalgorithms.h>
56#include <QtDebug>
57
58#include <math.h>
59
60#include <private/qgl_p.h>
61
62QT_BEGIN_NAMESPACE
63
64//#define Q_TRIANGULATOR_DEBUG
65
66#define Q_FIXED_POINT_SCALE 32
67
68// Quick sort.
69template <class T, class LessThan>
70#ifdef Q_CC_RVCT // RVCT 2.2 doesn't see recursive _static_ template function
71void sort(T *array, int count, LessThan lessThan)
72#else
73static void sort(T *array, int count, LessThan lessThan)
74#endif
75{
76 // If the number of elements fall below some threshold, use insertion sort.
77 const int INSERTION_SORT_LIMIT = 7; // About 7 is fastest on my computer...
78 if (count <= INSERTION_SORT_LIMIT) {
79 for (int i = 1; i < count; ++i) {
80 T temp = array[i];
81 int j = i;
82 while (j > 0 && lessThan(temp, array[j - 1])) {
83 array[j] = array[j - 1];
84 --j;
85 }
86 array[j] = temp;
87 }
88 return;
89 }
90
91 int high = count - 1;
92 int low = 0;
93 int mid = high / 2;
94 if (lessThan(array[mid], array[low]))
95 qSwap(array[mid], array[low]);
96 if (lessThan(array[high], array[mid]))
97 qSwap(array[high], array[mid]);
98 if (lessThan(array[mid], array[low]))
99 qSwap(array[mid], array[low]);
100
101 --high;
102 ++low;
103 qSwap(array[mid], array[high]);
104 int pivot = high;
105 --high;
106
107 while (low <= high) {
108 while (!lessThan(array[pivot], array[low])) {
109 ++low;
110 if (low > high)
111 goto sort_loop_end;
112 }
113 while (!lessThan(array[high], array[pivot])) {
114 --high;
115 if (low > high)
116 goto sort_loop_end;
117 }
118 qSwap(array[low], array[high]);
119 ++low;
120 --high;
121 }
122sort_loop_end:
123 if (low != pivot)
124 qSwap(array[pivot], array[low]);
125 sort(array, low, lessThan);
126 sort(array + low + 1, count - low - 1, lessThan);
127}
128
129// Quick sort.
130template <class T>
131#ifdef Q_CC_RVCT
132void sort(T *array, int count) // RVCT 2.2 doesn't see recursive _static_ template function
133#else
134static void sort(T *array, int count)
135#endif
136{
137 // If the number of elements fall below some threshold, use insertion sort.
138 const int INSERTION_SORT_LIMIT = 25; // About 25 is fastest on my computer...
139 if (count <= INSERTION_SORT_LIMIT) {
140 for (int i = 1; i < count; ++i) {
141 T temp = array[i];
142 int j = i;
143 while (j > 0 && (temp < array[j - 1])) {
144 array[j] = array[j - 1];
145 --j;
146 }
147 array[j] = temp;
148 }
149 return;
150 }
151
152 int high = count - 1;
153 int low = 0;
154 int mid = high / 2;
155 if ((array[mid] < array[low]))
156 qSwap(array[mid], array[low]);
157 if ((array[high] < array[mid]))
158 qSwap(array[high], array[mid]);
159 if ((array[mid] < array[low]))
160 qSwap(array[mid], array[low]);
161
162 --high;
163 ++low;
164 qSwap(array[mid], array[high]);
165 int pivot = high;
166 --high;
167
168 while (low <= high) {
169 while (!(array[pivot] < array[low])) {
170 ++low;
171 if (low > high)
172 goto sort_loop_end;
173 }
174 while (!(array[high] < array[pivot])) {
175 --high;
176 if (low > high)
177 goto sort_loop_end;
178 }
179 qSwap(array[low], array[high]);
180 ++low;
181 --high;
182 }
183sort_loop_end:
184 if (low != pivot)
185 qSwap(array[pivot], array[low]);
186 sort(array, low);
187 sort(array + low + 1, count - low - 1);
188}
189
190template<typename T>
191struct QVertexSet
192{
193 inline QVertexSet() { }
194 inline QVertexSet(const QVertexSet<T> &other) : vertices(other.vertices), indices(other.indices) { }
195 QVertexSet<T> &operator = (const QVertexSet<T> &other) {vertices = other.vertices; indices = other.indices; return *this;}
196
197 // The vertices of a triangle are given by: (x[i[n]], y[i[n]]), (x[j[n]], y[j[n]]), (x[k[n]], y[k[n]]), n = 0, 1, ...
198 QVector<qreal> vertices; // [x[0], y[0], x[1], y[1], x[2], ...]
199 QVector<T> indices; // [i[0], j[0], k[0], i[1], j[1], k[1], i[2], ...]
200};
201
202//============================================================================//
203// QFraction //
204//============================================================================//
205
206// Fraction must be in the range [0, 1)
207struct QFraction
208{
209 // Comparison operators must not be called on invalid fractions.
210 inline bool operator < (const QFraction &other) const;
211 inline bool operator == (const QFraction &other) const;
212 inline bool operator != (const QFraction &other) const {return !(*this == other);}
213 inline bool operator > (const QFraction &other) const {return other < *this;}
214 inline bool operator >= (const QFraction &other) const {return !(*this < other);}
215 inline bool operator <= (const QFraction &other) const {return !(*this > other);}
216
217 inline bool isValid() const {return denominator != 0;}
218
219 // numerator and denominator must not have common denominators.
220 quint64 numerator, denominator;
221};
222
223static inline quint64 gcd(quint64 x, quint64 y)
224{
225 while (y != 0) {
226 quint64 z = y;
227 y = x % y;
228 x = z;
229 }
230 return x;
231}
232
233static inline int compare(quint64 a, quint64 b)
234{
235 return (a > b) - (a < b);
236}
237
238// Compare a/b with c/d.
239// Return negative if less, 0 if equal, positive if greater.
240// a < b, c < d
241static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d)
242{
243 const quint64 LIMIT = Q_UINT64_C(0x100000000);
244 for (;;) {
245 // If the products 'ad' and 'bc' fit into 64 bits, they can be directly compared.
246 if (b < LIMIT && d < LIMIT)
247 return compare(a * d, b * c);
248
249 if (a == 0 || c == 0)
250 return compare(a, c);
251
252 // a/b < c/d <=> d/c < b/a
253 quint64 b_div_a = b / a;
254 quint64 d_div_c = d / c;
255 if (b_div_a != d_div_c)
256 return compare(d_div_c, b_div_a);
257
258 // floor(d/c) == floor(b/a)
259 // frac(d/c) < frac(b/a) ?
260 // frac(x/y) = (x%y)/y
261 d -= d_div_c * c; //d %= c;
262 b -= b_div_a * a; //b %= a;
263 qSwap(a, d);
264 qSwap(b, c);
265 }
266}
267
268// Fraction must be in the range [0, 1)
269// Assume input is valid.
270static QFraction qFraction(quint64 n, quint64 d) {
271 QFraction result;
272 if (n == 0) {
273 result.numerator = 0;
274 result.denominator = 1;
275 } else {
276 quint64 g = gcd(n, d);
277 result.numerator = n / g;
278 result.denominator = d / g;
279 }
280 return result;
281}
282
283inline bool QFraction::operator < (const QFraction &other) const
284{
285 return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
286}
287
288inline bool QFraction::operator == (const QFraction &other) const
289{
290 return numerator == other.numerator && denominator == other.denominator;
291}
292
293//============================================================================//
294// QPodPoint //
295//============================================================================//
296
297struct QPodPoint
298{
299 inline bool operator < (const QPodPoint &other) const
300 {
301 if (y != other.y)
302 return y < other.y;
303 return x < other.x;
304 }
305
306 inline bool operator > (const QPodPoint &other) const {return other < *this;}
307 inline bool operator <= (const QPodPoint &other) const {return !(*this > other);}
308 inline bool operator >= (const QPodPoint &other) const {return !(*this < other);}
309 inline bool operator == (const QPodPoint &other) const {return x == other.x && y == other.y;}
310 inline bool operator != (const QPodPoint &other) const {return x != other.x || y != other.y;}
311
312 inline QPodPoint &operator += (const QPodPoint &other) {x += other.x; y += other.y; return *this;}
313 inline QPodPoint &operator -= (const QPodPoint &other) {x -= other.x; y -= other.y; return *this;}
314 inline QPodPoint operator + (const QPodPoint &other) const {QPodPoint result = {x + other.x, y + other.y}; return result;}
315 inline QPodPoint operator - (const QPodPoint &other) const {QPodPoint result = {x - other.x, y - other.y}; return result;}
316
317 int x;
318 int y;
319};
320
321static inline qint64 qCross(const QPodPoint &u, const QPodPoint &v)
322{
323 return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
324}
325
326static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v)
327{
328 return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
329}
330
331// Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the
332// line and zero if exactly on the line.
333// The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1',
334// which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order).
335static inline qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
336{
337 return qCross(v2 - v1, p - v1);
338}
339
340static inline bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
341{
342 return QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(p, v1, v2) < 0;
343}
344
345// Return:
346// -1 if u < v
347// 0 if u == v
348// 1 if u > v
349static int comparePoints(const QPodPoint &u, const QPodPoint &v)
350{
351 if (u.y < v.y)
352 return -1;
353 if (u.y > v.y)
354 return 1;
355 if (u.x < v.x)
356 return -1;
357 if (u.x > v.x)
358 return 1;
359 return 0;
360}
361
362//============================================================================//
363// QIntersectionPoint //
364//============================================================================//
365
366struct QIntersectionPoint
367{
368 inline bool isValid() const {return xOffset.isValid() && yOffset.isValid();}
369 QPodPoint round() const;
370 inline bool isAccurate() const {return xOffset.numerator == 0 && yOffset.numerator == 0;}
371 bool operator < (const QIntersectionPoint &other) const;
372 bool operator == (const QIntersectionPoint &other) const;
373 inline bool operator != (const QIntersectionPoint &other) const {return !(*this == other);}
374 inline bool operator > (const QIntersectionPoint &other) const {return other < *this;}
375 inline bool operator >= (const QIntersectionPoint &other) const {return !(*this < other);}
376 inline bool operator <= (const QIntersectionPoint &other) const {return !(*this > other);}
377 bool isOnLine(const QPodPoint &u, const QPodPoint &v) const;
378
379 QPodPoint upperLeft;
380 QFraction xOffset;
381 QFraction yOffset;
382};
383
384static inline QIntersectionPoint qIntersectionPoint(const QPodPoint &point)
385{
386 // upperLeft = point, xOffset = 0/1, yOffset = 0/1.
387 QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};
388 return p;
389}
390
391static inline QIntersectionPoint qIntersectionPoint(int x, int y)
392{
393 // upperLeft = (x, y), xOffset = 0/1, yOffset = 0/1.
394 QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};
395 return p;
396}
397
398static QIntersectionPoint qIntersectionPoint(const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2)
399{
400 QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};
401
402 QPodPoint u = u2 - u1;
403 QPodPoint v = v2 - v1;
404 qint64 d1 = qCross(u, v1 - u1);
405 qint64 d2 = qCross(u, v2 - u1);
406 qint64 det = d2 - d1;
407 qint64 d3 = qCross(v, u1 - v1);
408 qint64 d4 = d3 - det; //qCross(v, u2 - v1);
409
410 // Check that the math is correct.
411 Q_ASSERT(d4 == qCross(v, u2 - v1));
412
413 // The intersection point can be expressed as:
414 // v1 - v * d1/det
415 // v2 - v * d2/det
416 // u1 + u * d3/det
417 // u2 + u * d4/det
418
419 // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.
420 if (det == 0)
421 return result;
422
423 if (det < 0) {
424 det = -det;
425 d1 = -d1;
426 d2 = -d2;
427 d3 = -d3;
428 d4 = -d4;
429 }
430
431 // I'm only interested in lines intersecting at their interior, not at their end points.
432 // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'.
433 if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
434 return result;
435
436 // Calculate the intersection point as follows:
437 // v1 - v * d1/det | v1 <= v2 (component-wise)
438 // v2 - v * d2/det | v2 < v1 (component-wise)
439
440 // Assuming 21 bits per vector component.
441 // TODO: Make code path for 31 bits per vector component.
442 if (v.x >= 0) {
443 result.upperLeft.x = v1.x + (-v.x * d1) / det;
444 result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));
445 } else {
446 result.upperLeft.x = v2.x + (-v.x * d2) / det;
447 result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));
448 }
449
450 if (v.y >= 0) {
451 result.upperLeft.y = v1.y + (-v.y * d1) / det;
452 result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));
453 } else {
454 result.upperLeft.y = v2.y + (-v.y * d2) / det;
455 result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));
456 }
457
458 Q_ASSERT(result.xOffset.isValid());
459 Q_ASSERT(result.yOffset.isValid());
460 return result;
461}
462
463QPodPoint QIntersectionPoint::round() const
464{
465 QPodPoint result = upperLeft;
466 if (2 * xOffset.numerator >= xOffset.denominator)
467 ++result.x;
468 if (2 * yOffset.numerator >= yOffset.denominator)
469 ++result.y;
470 return result;
471}
472
473bool QIntersectionPoint::operator < (const QIntersectionPoint &other) const
474{
475 if (upperLeft.y != other.upperLeft.y)
476 return upperLeft.y < other.upperLeft.y;
477 if (yOffset != other.yOffset)
478 return yOffset < other.yOffset;
479 if (upperLeft.x != other.upperLeft.x)
480 return upperLeft.x < other.upperLeft.x;
481 return xOffset < other.xOffset;
482}
483
484bool QIntersectionPoint::operator == (const QIntersectionPoint &other) const
485{
486 return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
487}
488
489// Returns true if this point is on the infinite line passing through 'u' and 'v'.
490bool QIntersectionPoint::isOnLine(const QPodPoint &u, const QPodPoint &v) const
491{
492 // TODO: Make code path for coordinates with more than 21 bits.
493 const QPodPoint p = upperLeft - u;
494 const QPodPoint q = v - u;
495 bool isHorizontal = p.y == 0 && yOffset.numerator == 0;
496 bool isVertical = p.x == 0 && xOffset.numerator == 0;
497 if (isHorizontal && isVertical)
498 return true;
499 if (isHorizontal)
500 return q.y == 0;
501 if (q.y == 0)
502 return false;
503 if (isVertical)
504 return q.x == 0;
505 if (q.x == 0)
506 return false;
507
508 // At this point, 'p+offset' and 'q' cannot lie on the x or y axis.
509
510 if (((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0)))
511 return false; // 'p + offset' and 'q' pass through different quadrants.
512
513 // Move all coordinates into the first quadrant.
514 quint64 nx, ny;
515 if (p.x < 0)
516 nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
517 else
518 nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
519 if (p.y < 0)
520 ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
521 else
522 ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
523
524 return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
525}
526
527//============================================================================//
528// QMaxHeap //
529//============================================================================//
530
531template <class T>
532class QMaxHeap
533{
534public:
535 QMaxHeap() : m_data(0) {}
536 inline int size() const {return m_data.size();}
537 inline bool empty() const {return m_data.isEmpty();}
538 inline bool isEmpty() const {return m_data.isEmpty();}
539 void push(const T &x);
540 T pop();
541 inline const T &top() const {return m_data.first();}
542private:
543 static inline int parent(int i) {return (i - 1) / 2;}
544 static inline int left(int i) {return 2 * i + 1;}
545 static inline int right(int i) {return 2 * i + 2;}
546
547 QDataBuffer<T> m_data;
548};
549
550template <class T>
551void QMaxHeap<T>::push(const T &x)
552{
553 int current = m_data.size();
554 int parent = QMaxHeap::parent(current);
555 m_data.add(x);
556 while (current != 0 && m_data.at(parent) < x) {
557 m_data.at(current) = m_data.at(parent);
558 current = parent;
559 parent = QMaxHeap::parent(current);
560 }
561 m_data.at(current) = x;
562}
563
564template <class T>
565T QMaxHeap<T>::pop()
566{
567 T result = m_data.first();
568 T back = m_data.last();
569 m_data.pop_back();
570 if (!m_data.isEmpty()) {
571 int current = 0;
572 for (;;) {
573 int left = QMaxHeap::left(current);
574 int right = QMaxHeap::right(current);
575 if (left >= m_data.size())
576 break;
577 int greater = left;
578 if (right < m_data.size() && m_data.at(left) < m_data.at(right))
579 greater = right;
580 if (m_data.at(greater) < back)
581 break;
582 m_data.at(current) = m_data.at(greater);
583 current = greater;
584 }
585 m_data.at(current) = back;
586 }
587 return result;
588}
589
590//============================================================================//
591// QRBTree //
592//============================================================================//
593
594template <class T>
595struct QRBTree
596{
597 struct Node
598 {
599 inline Node() : parent(0), left(0), right(0), red(true) { }
600 inline ~Node() {if (left) delete left; if (right) delete right;}
601 T data;
602 Node *parent;
603 Node *left;
604 Node *right;
605 bool red;
606 };
607
608 inline QRBTree() : root(0), freeList(0) { }
609 inline ~QRBTree();
610
611 inline void clear();
612
613 void attachBefore(Node *parent, Node *child);
614 void attachAfter(Node *parent, Node *child);
615
616 inline Node *front(Node *node) const;
617 inline Node *back(Node *node) const;
618 Node *next(Node *node) const;
619 Node *previous(Node *node) const;
620
621 inline void deleteNode(Node *&node);
622 inline Node *newNode();
623
624 // Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
625 // 'left' and 'right' cannot be null.
626 int order(Node *left, Node *right);
627 inline bool validate() const;
628
629private:
630 void rotateLeft(Node *node);
631 void rotateRight(Node *node);
632 void update(Node *node);
633
634 inline void attachLeft(Node *parent, Node *child);
635 inline void attachRight(Node *parent, Node *child);
636
637 int blackDepth(Node *top) const;
638 bool checkRedBlackProperty(Node *top) const;
639
640 void swapNodes(Node *n1, Node *n2);
641 void detach(Node *node);
642
643 // 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
644 void rebalance(Node *node);
645
646public:
647 Node *root;
648private:
649 Node *freeList;
650};
651
652template <class T>
653inline QRBTree<T>::~QRBTree()
654{
655 clear();
656 while (freeList) {
657 // Avoid recursively calling the destructor, as this list may become large.
658 Node *next = freeList->right;
659 freeList->right = 0;
660 delete freeList;
661 freeList = next;
662 }
663}
664
665template <class T>
666inline void QRBTree<T>::clear()
667{
668 if (root)
669 delete root;
670 root = 0;
671}
672
673template <class T>
674void QRBTree<T>::rotateLeft(Node *node)
675{
676 // | | //
677 // N B //
678 // / \ / \ //
679 // A B ---> N D //
680 // / \ / \ //
681 // C D A C //
682
683 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
684 ref = node->right;
685 node->right->parent = node->parent;
686
687 // : //
688 // N //
689 // / :| //
690 // A B //
691 // / \ //
692 // C D //
693
694 node->right = ref->left;
695 if (ref->left)
696 ref->left->parent = node;
697
698 // : | //
699 // N B //
700 // / \ : \ //
701 // A C D //
702
703 ref->left = node;
704 node->parent = ref;
705
706 // | //
707 // B //
708 // / \ //
709 // N D //
710 // / \ //
711 // A C //
712}
713
714template <class T>
715void QRBTree<T>::rotateRight(Node *node)
716{
717 // | | //
718 // N A //
719 // / \ / \ //
720 // A B ---> C N //
721 // / \ / \ //
722 // C D D B //
723
724 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
725 ref = node->left;
726 node->left->parent = node->parent;
727
728 node->left = ref->right;
729 if (ref->right)
730 ref->right->parent = node;
731
732 ref->right = node;
733 node->parent = ref;
734}
735
736template <class T>
737void QRBTree<T>::update(Node *node) // call this after inserting a node
738{
739 for (;;) {
740 Node *parent = node->parent;
741
742 // if the node is the root, color it black
743 if (!parent) {
744 node->red = false;
745 return;
746 }
747
748 // if the parent is black, the node can be left red
749 if (!parent->red)
750 return;
751
752 // at this point, the parent is red and cannot be the root
753 Node *grandpa = parent->parent;
754 Q_ASSERT(grandpa);
755
756 Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
757 if (uncle && uncle->red) {
758 // grandpa's black, parent and uncle are red.
759 // let parent and uncle be black, grandpa red and recursively update grandpa.
760 Q_ASSERT(!grandpa->red);
761 parent->red = false;
762 uncle->red = false;
763 grandpa->red = true;
764 node = grandpa;
765 continue;
766 }
767
768 // at this point, uncle is black
769 if (node == parent->right && parent == grandpa->left)
770 rotateLeft(node = parent);
771 else if (node == parent->left && parent == grandpa->right)
772 rotateRight(node = parent);
773 parent = node->parent;
774
775 if (parent == grandpa->left) {
776 rotateRight(grandpa);
777 parent->red = false;
778 grandpa->red = true;
779 } else {
780 rotateLeft(grandpa);
781 parent->red = false;
782 grandpa->red = true;
783 }
784 return;
785 }
786}
787
788template <class T>
789inline void QRBTree<T>::attachLeft(Node *parent, Node *child)
790{
791 Q_ASSERT(!parent->left);
792 parent->left = child;
793 child->parent = parent;
794 update(child);
795}
796
797template <class T>
798inline void QRBTree<T>::attachRight(Node *parent, Node *child)
799{
800 Q_ASSERT(!parent->right);
801 parent->right = child;
802 child->parent = parent;
803 update(child);
804}
805
806template <class T>
807void QRBTree<T>::attachBefore(Node *parent, Node *child)
808{
809 if (!root)
810 update(root = child);
811 else if (!parent)
812 attachRight(back(root), child);
813 else if (parent->left)
814 attachRight(back(parent->left), child);
815 else
816 attachLeft(parent, child);
817}
818
819template <class T>
820void QRBTree<T>::attachAfter(Node *parent, Node *child)
821{
822 if (!root)
823 update(root = child);
824 else if (!parent)
825 attachLeft(front(root), child);
826 else if (parent->right)
827 attachLeft(front(parent->right), child);
828 else
829 attachRight(parent, child);
830}
831
832template <class T>
833void QRBTree<T>::swapNodes(Node *n1, Node *n2)
834{
835 // Since iterators must not be invalidated, it is not sufficient to only swap the data.
836 if (n1->parent == n2) {
837 n1->parent = n2->parent;
838 n2->parent = n1;
839 } else if (n2->parent == n1) {
840 n2->parent = n1->parent;
841 n1->parent = n2;
842 } else {
843 qSwap(n1->parent, n2->parent);
844 }
845
846 qSwap(n1->left, n2->left);
847 qSwap(n1->right, n2->right);
848 qSwap(n1->red, n2->red);
849
850 if (n1->parent) {
851 if (n1->parent->left == n2)
852 n1->parent->left = n1;
853 else
854 n1->parent->right = n1;
855 } else {
856 root = n1;
857 }
858
859 if (n2->parent) {
860 if (n2->parent->left == n1)
861 n2->parent->left = n2;
862 else
863 n2->parent->right = n2;
864 } else {
865 root = n2;
866 }
867
868 if (n1->left)
869 n1->left->parent = n1;
870 if (n1->right)
871 n1->right->parent = n1;
872
873 if (n2->left)
874 n2->left->parent = n2;
875 if (n2->right)
876 n2->right->parent = n2;
877}
878
879template <class T>
880void QRBTree<T>::detach(Node *node) // call this before removing a node.
881{
882 if (node->right)
883 swapNodes(node, front(node->right));
884
885 Node *child = (node->left ? node->left : node->right);
886
887 if (!node->red) {
888 if (child && child->red)
889 child->red = false;
890 else
891 rebalance(node);
892 }
893
894 Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
895 ref = child;
896 if (child)
897 child->parent = node->parent;
898 node->left = node->right = node->parent = 0;
899}
900
901// 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
902template <class T>
903void QRBTree<T>::rebalance(Node *node)
904{
905 Q_ASSERT(!node->red);
906 for (;;) {
907 if (!node->parent)
908 return;
909
910 // at this point, node is not a parent, it is black, thus it must have a sibling.
911 Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
912 Q_ASSERT(sibling);
913
914 if (sibling->red) {
915 sibling->red = false;
916 node->parent->red = true;
917 if (node == node->parent->left)
918 rotateLeft(node->parent);
919 else
920 rotateRight(node->parent);
921 sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
922 Q_ASSERT(sibling);
923 }
924
925 // at this point, the sibling is black.
926 Q_ASSERT(!sibling->red);
927
928 if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
929 bool parentWasRed = node->parent->red;
930 sibling->red = true;
931 node->parent->red = false;
932 if (parentWasRed)
933 return;
934 node = node->parent;
935 continue;
936 }
937
938 // at this point, at least one of the sibling's children is red.
939
940 if (node == node->parent->left) {
941 if (!sibling->right || !sibling->right->red) {
942 Q_ASSERT(sibling->left);
943 sibling->red = true;
944 sibling->left->red = false;
945 rotateRight(sibling);
946
947 sibling = sibling->parent;
948 Q_ASSERT(sibling);
949 }
950 sibling->red = node->parent->red;
951 node->parent->red = false;
952
953 Q_ASSERT(sibling->right->red);
954 sibling->right->red = false;
955 rotateLeft(node->parent);
956 } else {
957 if (!sibling->left || !sibling->left->red) {
958 Q_ASSERT(sibling->right);
959 sibling->red = true;
960 sibling->right->red = false;
961 rotateLeft(sibling);
962
963 sibling = sibling->parent;
964 Q_ASSERT(sibling);
965 }
966 sibling->red = node->parent->red;
967 node->parent->red = false;
968
969 Q_ASSERT(sibling->left->red);
970 sibling->left->red = false;
971 rotateRight(node->parent);
972 }
973 return;
974 }
975}
976
977template <class T>
978inline typename QRBTree<T>::Node *QRBTree<T>::front(Node *node) const
979{
980 while (node->left)
981 node = node->left;
982 return node;
983}
984
985template <class T>
986inline typename QRBTree<T>::Node *QRBTree<T>::back(Node *node) const
987{
988 while (node->right)
989 node = node->right;
990 return node;
991}
992
993template <class T>
994typename QRBTree<T>::Node *QRBTree<T>::next(Node *node) const
995{
996 if (node->right)
997 return front(node->right);
998 while (node->parent && node == node->parent->right)
999 node = node->parent;
1000 return node->parent;
1001}
1002
1003template <class T>
1004typename QRBTree<T>::Node *QRBTree<T>::previous(Node *node) const
1005{
1006 if (node->left)
1007 return back(node->left);
1008 while (node->parent && node == node->parent->left)
1009 node = node->parent;
1010 return node->parent;
1011}
1012
1013template <class T>
1014int QRBTree<T>::blackDepth(Node *top) const
1015{
1016 if (!top)
1017 return 0;
1018 int leftDepth = blackDepth(top->left);
1019 int rightDepth = blackDepth(top->right);
1020 if (leftDepth != rightDepth)
1021 return -1;
1022 if (!top->red)
1023 ++leftDepth;
1024 return leftDepth;
1025}
1026
1027template <class T>
1028bool QRBTree<T>::checkRedBlackProperty(Node *top) const
1029{
1030 if (!top)
1031 return true;
1032 if (top->left && !checkRedBlackProperty(top->left))
1033 return false;
1034 if (top->right && !checkRedBlackProperty(top->right))
1035 return false;
1036 return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red)));
1037}
1038
1039template <class T>
1040inline bool QRBTree<T>::validate() const
1041{
1042 return checkRedBlackProperty(root) && blackDepth(root) != -1;
1043}
1044
1045template <class T>
1046inline void QRBTree<T>::deleteNode(Node *&node)
1047{
1048 Q_ASSERT(node);
1049 detach(node);
1050 node->right = freeList;
1051 freeList = node;
1052 node = 0;
1053}
1054
1055template <class T>
1056inline typename QRBTree<T>::Node *QRBTree<T>::newNode()
1057{
1058 if (freeList) {
1059 Node *node = freeList;
1060 freeList = freeList->right;
1061 node->parent = node->left = node->right = 0;
1062 node->red = true;
1063 return node;
1064 }
1065 return new Node;
1066}
1067
1068// Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
1069// 'left' and 'right' cannot be null.
1070template <class T>
1071int QRBTree<T>::order(Node *left, Node *right)
1072{
1073 Q_ASSERT(left && right);
1074 if (left == right)
1075 return 0;
1076
1077 QVector<Node *> leftAncestors;
1078 QVector<Node *> rightAncestors;
1079 while (left) {
1080 leftAncestors.push_back(left);
1081 left = left->parent;
1082 }
1083 while (right) {
1084 rightAncestors.push_back(right);
1085 right = right->parent;
1086 }
1087 Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root);
1088
1089 while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) {
1090 leftAncestors.pop_back();
1091 rightAncestors.pop_back();
1092 }
1093
1094 if (!leftAncestors.empty())
1095 return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1);
1096
1097 if (!rightAncestors.empty())
1098 return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1);
1099
1100 // The code should never reach this point.
1101 Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty());
1102 return 0;
1103}
1104
1105//============================================================================//
1106// QInt64Hash //
1107//============================================================================//
1108
1109// Copied from qhash.cpp
1110static const uchar prime_deltas[] = {
1111 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
1112 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
1113};
1114
1115// Copied from qhash.cpp
1116static inline int primeForNumBits(int numBits)
1117{
1118 return (1 << numBits) + prime_deltas[numBits];
1119}
1120
1121static inline int primeForCount(int count)
1122{
1123 int low = 0;
1124 int high = 32;
1125 for (int i = 0; i < 5; ++i) {
1126 int mid = (high + low) / 2;
1127 if (count >= 1 << mid)
1128 low = mid;
1129 else
1130 high = mid;
1131 }
1132 return primeForNumBits(high);
1133}
1134
1135// Hash set of quint64s. Elements cannot be removed without clearing the
1136// entire set. A value of -1 is used to mark unused entries.
1137class QInt64Set
1138{
1139public:
1140 inline QInt64Set(int capacity = 64);
1141 inline ~QInt64Set() {if (m_array) delete[] m_array;}
1142 inline bool isValid() const {return m_array;}
1143 void insert(quint64 key);
1144 bool contains(quint64 key) const;
1145 inline void clear();
1146private:
1147 bool rehash(int capacity);
1148
1149 static const quint64 UNUSED;
1150
1151 quint64 *m_array;
1152 int m_capacity;
1153 int m_count;
1154};
1155
1156const quint64 QInt64Set::UNUSED = quint64(-1);
1157
1158inline QInt64Set::QInt64Set(int capacity)
1159{
1160 m_capacity = primeForCount(capacity);
1161 m_array = new quint64[m_capacity];
1162 if (m_array)
1163 clear();
1164 else
1165 m_capacity = 0;
1166}
1167
1168bool QInt64Set::rehash(int capacity)
1169{
1170 quint64 *oldArray = m_array;
1171 int oldCapacity = m_capacity;
1172
1173 m_capacity = capacity;
1174 m_array = new quint64[m_capacity];
1175 if (m_array) {
1176 clear();
1177 if (oldArray) {
1178 for (int i = 0; i < oldCapacity; ++i) {
1179 if (oldArray[i] != UNUSED)
1180 insert(oldArray[i]);
1181 }
1182 delete[] oldArray;
1183 }
1184 return true;
1185 } else {
1186 m_capacity = oldCapacity;
1187 m_array = oldArray;
1188 return false;
1189 }
1190}
1191
1192void QInt64Set::insert(quint64 key)
1193{
1194 if (m_count > 3 * m_capacity / 4)
1195 rehash(primeForCount(2 * m_capacity));
1196 Q_ASSERT_X(m_array, "QInt64Hash<T>::insert", "Hash set not allocated.");
1197 int index = int(key % m_capacity);
1198 for (int i = 0; i < m_capacity; ++i) {
1199 index += i;
1200 if (index >= m_capacity)
1201 index -= m_capacity;
1202 if (m_array[index] == key)
1203 return;
1204 if (m_array[index] == UNUSED) {
1205 ++m_count;
1206 m_array[index] = key;
1207 return;
1208 }
1209 }
1210 Q_ASSERT_X(0, "QInt64Hash<T>::insert", "Hash set full.");
1211}
1212
1213bool QInt64Set::contains(quint64 key) const
1214{
1215 Q_ASSERT_X(m_array, "QInt64Hash<T>::contains", "Hash set not allocated.");
1216 int index = int(key % m_capacity);
1217 for (int i = 0; i < m_capacity; ++i) {
1218 index += i;
1219 if (index >= m_capacity)
1220 index -= m_capacity;
1221 if (m_array[index] == key)
1222 return true;
1223 if (m_array[index] == UNUSED)
1224 return false;
1225 }
1226 return false;
1227}
1228
1229inline void QInt64Set::clear()
1230{
1231 Q_ASSERT_X(m_array, "QInt64Hash<T>::clear", "Hash set not allocated.");
1232 for (int i = 0; i < m_capacity; ++i)
1233 m_array[i] = UNUSED;
1234 m_count = 0;
1235}
1236
1237//============================================================================//
1238// QRingBuffer //
1239//============================================================================//
1240
1241// T must be POD.
1242template <class T>
1243class QRingBuffer
1244{
1245public:
1246 inline QRingBuffer() : m_array(0), m_head(0), m_size(0), m_capacity(0) { }
1247 inline ~QRingBuffer() {if (m_array) delete[] m_array;}
1248 bool reallocate(int capacity);
1249 inline const T &head() const {Q_ASSERT(m_size > 0); return m_array[m_head];}
1250 inline const T &dequeue();
1251 inline void enqueue(const T &x);
1252 inline bool isEmpty() const {return m_size == 0;}
1253private:
1254 T *m_array;
1255 int m_head;
1256 int m_size;
1257 int m_capacity;
1258};
1259
1260template <class T>
1261bool QRingBuffer<T>::reallocate(int capacity)
1262{
1263 T *oldArray = m_array;
1264 m_array = new T[capacity];
1265 if (m_array) {
1266 if (oldArray) {
1267 if (m_head + m_size > m_capacity) {
1268 memcpy(m_array, oldArray + m_head, (m_capacity - m_head) * sizeof(T));
1269 memcpy(m_array + (m_capacity - m_head), oldArray, (m_head + m_size - m_capacity) * sizeof(T));
1270 } else {
1271 memcpy(m_array, oldArray + m_head, m_size * sizeof(T));
1272 }
1273 delete[] oldArray;
1274 }
1275 m_capacity = capacity;
1276 m_head = 0;
1277 return true;
1278 } else {
1279 m_array = oldArray;
1280 return false;
1281 }
1282}
1283
1284template <class T>
1285inline const T &QRingBuffer<T>::dequeue()
1286{
1287 Q_ASSERT(m_size > 0);
1288 Q_ASSERT(m_array);
1289 Q_ASSERT(m_capacity >= m_size);
1290 int index = m_head;
1291 if (++m_head >= m_capacity)
1292 m_head -= m_capacity;
1293 --m_size;
1294 return m_array[index];
1295}
1296
1297template <class T>
1298inline void QRingBuffer<T>::enqueue(const T &x)
1299{
1300 if (m_size == m_capacity)
1301 reallocate(qMax(2 * m_capacity, 64));
1302 int index = m_head + m_size;
1303 if (index >= m_capacity)
1304 index -= m_capacity;
1305 m_array[index] = x;
1306 ++m_size;
1307}
1308
1309//============================================================================//
1310// QTriangulator //
1311//============================================================================//
1312template<typename T>
1313class QTriangulator
1314{
1315public:
1316 typedef QVarLengthArray<int, 6> ShortArray;
1317
1318 //================================//
1319 // QTriangulator::ComplexToSimple //
1320 //================================//
1321 friend class ComplexToSimple;
1322 class ComplexToSimple
1323 {
1324 public:
1325 inline ComplexToSimple(QTriangulator<T> *parent) : m_parent(parent),
1326 m_edges(0), m_events(0), m_splits(0) { }
1327 void decompose();
1328 private:
1329 struct Edge
1330 {
1331 inline int &upper() {return pointingUp ? to : from;}
1332 inline int &lower() {return pointingUp ? from : to;}
1333 inline int upper() const {return pointingUp ? to : from;}
1334 inline int lower() const {return pointingUp ? from : to;}
1335
1336 QRBTree<int>::Node *node;
1337 int from, to; // vertex
1338 int next, previous; // edge
1339 int winding;
1340 bool mayIntersect;
1341 bool pointingUp, originallyPointingUp;
1342 };
1343
1344 friend class CompareEdges;
1345 class CompareEdges
1346 {
1347 public:
1348 inline CompareEdges(ComplexToSimple *parent) : m_parent(parent) { }
1349 bool operator () (int i, int j) const;
1350 private:
1351 ComplexToSimple *m_parent;
1352 };
1353
1354 struct Intersection
1355 {
1356 bool operator < (const Intersection &other) const {return other.intersectionPoint < intersectionPoint;}
1357
1358 QIntersectionPoint intersectionPoint;
1359 int vertex;
1360 int leftEdge;
1361 int rightEdge;
1362 };
1363
1364 struct Split
1365 {
1366 int vertex;
1367 int edge;
1368 bool accurate;
1369 };
1370
1371 struct Event
1372 {
1373 enum Type {Upper, Lower};
1374 inline bool operator < (const Event &other) const;
1375
1376 QPodPoint point;
1377 Type type;
1378 int edge;
1379 };
1380
1381#ifdef Q_TRIANGULATOR_DEBUG
1382 friend class DebugDialog;
1383 friend class QTriangulator;
1384 class DebugDialog : public QDialog
1385 {
1386 public:
1387 DebugDialog(ComplexToSimple *parent, int currentVertex);
1388 protected:
1389 void paintEvent(QPaintEvent *);
1390 void wheelEvent(QWheelEvent *);
1391 void mouseMoveEvent(QMouseEvent *);
1392 void mousePressEvent(QMouseEvent *);
1393 private:
1394 ComplexToSimple *m_parent;
1395 QRectF m_window;
1396 QPoint m_lastMousePos;
1397 int m_vertex;
1398 };
1399#endif
1400
1401 void initEdges();
1402 bool calculateIntersection(int left, int right);
1403 bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
1404 QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex) const;
1405 QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const;
1406 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> bounds(const QPodPoint &point) const;
1407 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> outerBounds(const QPodPoint &point) const;
1408 void splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint);
1409 void reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost);
1410 void sortEdgeList(const QPodPoint eventPoint);
1411 void fillPriorityQueue();
1412 void calculateIntersections();
1413 int splitEdge(int splitIndex);
1414 bool splitEdgesAtIntersections();
1415 void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i);
1416 void removeUnwantedEdgesAndConnect();
1417 void removeUnusedPoints();
1418
1419 QTriangulator *m_parent;
1420 QDataBuffer<Edge> m_edges;
1421 QRBTree<int> m_edgeList;
1422 QDataBuffer<Event> m_events;
1423 QDataBuffer<Split> m_splits;
1424 QMaxHeap<Intersection> m_topIntersection;
1425 QInt64Set m_processedEdgePairs;
1426 int m_initialPointCount;
1427 };
1428#ifdef Q_TRIANGULATOR_DEBUG
1429 friend class ComplexToSimple::DebugDialog;
1430#endif
1431
1432 //=================================//
1433 // QTriangulator::SimpleToMonotone //
1434 //=================================//
1435 friend class SimpleToMonotone;
1436 class SimpleToMonotone
1437 {
1438 public:
1439 inline SimpleToMonotone(QTriangulator<T> *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { }
1440 void decompose();
1441 private:
1442 enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};
1443
1444 struct Edge
1445 {
1446 QRBTree<int>::Node *node;
1447 int helper, twin, next, previous;
1448 T from, to;
1449 VertexType type;
1450 bool pointingUp;
1451 int upper() const {return (pointingUp ? to : from);}
1452 int lower() const {return (pointingUp ? from : to);}
1453 };
1454
1455 friend class CompareVertices;
1456 class CompareVertices
1457 {
1458 public:
1459 CompareVertices(SimpleToMonotone *parent) : m_parent(parent) { }
1460 bool operator () (int i, int j) const;
1461 private:
1462 SimpleToMonotone *m_parent;
1463 };
1464
1465 void setupDataStructures();
1466 void removeZeroLengthEdges();
1467 void fillPriorityQueue();
1468 bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
1469 // Returns the rightmost edge not to the right of the given edge.
1470 QRBTree<int>::Node *searchEdgeLeftOfEdge(int edgeIndex) const;
1471 // Returns the rightmost edge left of the given point.
1472 QRBTree<int>::Node *searchEdgeLeftOfPoint(int pointIndex) const;
1473 void classifyVertex(int i);
1474 void classifyVertices();
1475 bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3);
1476 bool pointIsInSector(int vertex, int sector);
1477 int findSector(int edge, int vertex);
1478 void createDiagonal(int lower, int upper);
1479 void monotoneDecomposition();
1480
1481 QTriangulator *m_parent;
1482 QRBTree<int> m_edgeList;
1483 QDataBuffer<Edge> m_edges;
1484 QDataBuffer<int> m_upperVertex;
1485 bool m_clockwiseOrder;
1486 };
1487
1488 //====================================//
1489 // QTriangulator::MonotoneToTriangles //
1490 //====================================//
1491 friend class MonotoneToTriangles;
1492 class MonotoneToTriangles
1493 {
1494 public:
1495 inline MonotoneToTriangles(QTriangulator<T> *parent) : m_parent(parent) { }
1496 void decompose();
1497 private:
1498 inline T indices(int index) const {return m_parent->m_indices.at(index + m_first);}
1499 inline int next(int index) const {return (index + 1) % m_length;}
1500 inline int previous(int index) const {return (index + m_length - 1) % m_length;}
1501 inline bool less(int i, int j) const {return m_parent->m_vertices.at((qint32)indices(i)) < m_parent->m_vertices.at(indices(j));}
1502 inline bool leftOfEdge(int i, int j, int k) const
1503 {
1504 return qPointIsLeftOfLine(m_parent->m_vertices.at((qint32)indices(i)),
1505 m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
1506 }
1507
1508 QTriangulator<T> *m_parent;
1509 int m_first;
1510 int m_length;
1511 };
1512
1513 inline QTriangulator() : m_vertices(0) { }
1514
1515 // Call this only once.
1516 void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix);
1517 // Call this only once.
1518 void initialize(const QVectorPath &path, const QTransform &matrix, qreal lod);
1519 // Call this only once.
1520 void initialize(const QPainterPath &path, const QTransform &matrix, qreal lod);
1521 // Call either triangulate() or polyline() only once.
1522 QVertexSet<T> triangulate();
1523 QVertexSet<T> polyline();
1524private:
1525 QDataBuffer<QPodPoint> m_vertices;
1526 QVector<T> m_indices;
1527 uint m_hint;
1528};
1529
1530//============================================================================//
1531// QTriangulator //
1532//============================================================================//
1533
1534template <typename T>
1535QVertexSet<T> QTriangulator<T>::triangulate()
1536{
1537 for (int i = 0; i < m_vertices.size(); ++i) {
1538 Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21));
1539 Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21));
1540 }
1541
1542 if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill)))
1543 m_hint |= QVectorPath::OddEvenFill;
1544
1545 if (m_hint & QVectorPath::NonConvexShapeMask) {
1546 ComplexToSimple c2s(this);
1547 c2s.decompose();
1548 SimpleToMonotone s2m(this);
1549 s2m.decompose();
1550 }
1551 MonotoneToTriangles m2t(this);
1552 m2t.decompose();
1553
1554 QVertexSet<T> result;
1555 result.indices = m_indices;
1556 result.vertices.resize(2 * m_vertices.size());
1557 for (int i = 0; i < m_vertices.size(); ++i) {
1558 result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
1559 result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
1560 }
1561 return result;
1562}
1563
1564template <typename T>
1565QVertexSet<T> QTriangulator<T>::polyline()
1566{
1567 QVertexSet<T> result;
1568 result.indices = m_indices;
1569 result.vertices.resize(2 * m_vertices.size());
1570 for (int i = 0; i < m_vertices.size(); ++i) {
1571 result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
1572 result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
1573 }
1574 return result;
1575}
1576
1577template <typename T>
1578void QTriangulator<T>::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix)
1579{
1580 m_hint = hint;
1581 m_vertices.resize(count);
1582 m_indices.resize(count + 1);
1583 for (int i = 0; i < count; ++i) {
1584 qreal x, y;
1585 matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y);
1586 m_vertices.at(i).x = qRound(x * Q_FIXED_POINT_SCALE);
1587 m_vertices.at(i).y = qRound(y * Q_FIXED_POINT_SCALE);
1588 m_indices[i] = i;
1589 }
1590 m_indices[count] = T(-1); //Q_TRIANGULATE_END_OF_POLYGON
1591}
1592
1593template <typename T>
1594void QTriangulator<T>::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod)
1595{
1596 m_hint = path.hints();
1597 // Curved paths will be converted to complex polygons.
1598 m_hint &= ~QVectorPath::CurvedShapeMask;
1599
1600 const qreal *p = path.points();
1601 const QPainterPath::ElementType *e = path.elements();
1602 if (e) {
1603 for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) {
1604 switch (*e) {
1605 case QPainterPath::MoveToElement:
1606 if (!m_indices.isEmpty())
1607 m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
1608 // Fall through.
1609 case QPainterPath::LineToElement:
1610 m_indices.push_back(T(m_vertices.size()));
1611 m_vertices.resize(m_vertices.size() + 1);
1612 qreal x, y;
1613 matrix.map(p[0], p[1], &x, &y);
1614 m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
1615 m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
1616 break;
1617 case QPainterPath::CurveToElement:
1618 {
1619 qreal pts[8];
1620 for (int i = 0; i < 4; ++i)
1621 matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
1622 for (int i = 0; i < 8; ++i)
1623 pts[i] *= lod;
1624 QBezier bezier = QBezier::fromPoints(QPointF(pts[0], pts[1]), QPointF(pts[2], pts[3]), QPointF(pts[4], pts[5]), QPointF(pts[6], pts[7]));
1625 QPolygonF poly = bezier.toPolygon();
1626 // Skip first point, it already exists in 'm_vertices'.
1627 for (int j = 1; j < poly.size(); ++j) {
1628 m_indices.push_back(T(m_vertices.size()));
1629 m_vertices.resize(m_vertices.size() + 1);
1630 m_vertices.last().x = qRound(poly.at(j).x() * Q_FIXED_POINT_SCALE / lod);
1631 m_vertices.last().y = qRound(poly.at(j).y() * Q_FIXED_POINT_SCALE / lod);
1632 }
1633 }
1634 i += 2;
1635 e += 2;
1636 p += 4;
1637 break;
1638 default:
1639 Q_ASSERT_X(0, "QTriangulator::triangulate", "Unexpected element type.");
1640 break;
1641 }
1642 }
1643 } else {
1644 for (int i = 0; i < path.elementCount(); ++i, p += 2) {
1645 m_indices.push_back(T(m_vertices.size()));
1646 m_vertices.resize(m_vertices.size() + 1);
1647 qreal x, y;
1648 matrix.map(p[0], p[1], &x, &y);
1649 m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
1650 m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
1651 }
1652 }
1653 m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
1654}
1655
1656template <typename T>
1657void QTriangulator<T>::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod)
1658{
1659 initialize(qtVectorPathForPath(path), matrix, lod);
1660}
1661
1662//============================================================================//
1663// QTriangulator::ComplexToSimple //
1664//============================================================================//
1665template <typename T>
1666void QTriangulator<T>::ComplexToSimple::decompose()
1667{
1668 m_initialPointCount = m_parent->m_vertices.size();
1669 initEdges();
1670 do {
1671 calculateIntersections();
1672 } while (splitEdgesAtIntersections());
1673
1674 removeUnwantedEdgesAndConnect();
1675 removeUnusedPoints();
1676
1677 m_parent->m_indices.clear();
1678 QBitArray processed(m_edges.size(), false);
1679 for (int first = 0; first < m_edges.size(); ++first) {
1680 // If already processed, or if unused path, skip.
1681 if (processed.at(first) || m_edges.at(first).next == -1)
1682 continue;
1683
1684 int i = first;
1685 do {
1686 Q_ASSERT(!processed.at(i));
1687 Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
1688 m_parent->m_indices.push_back(m_edges.at(i).from);
1689 processed.setBit(i);
1690 i = m_edges.at(i).next; // CCW order
1691 } while (i != first);
1692 m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
1693 }
1694}
1695
1696template <typename T>
1697void QTriangulator<T>::ComplexToSimple::initEdges()
1698{
1699 // Initialize edge structure.
1700 // 'next' and 'previous' are not being initialized at this point.
1701 int first = 0;
1702 for (int i = 0; i < m_parent->m_indices.size(); ++i) {
1703 if (m_parent->m_indices.at(i) == T(-1)) { // Q_TRIANGULATE_END_OF_POLYGON
1704 if (m_edges.size() != first)
1705 m_edges.last().to = m_edges.at(first).from;
1706 first = m_edges.size();
1707 } else {
1708 Q_ASSERT(i + 1 < m_parent->m_indices.size());
1709 // {node, from, to, next, previous, winding, mayIntersect, pointingUp, originallyPointingUp}
1710 Edge edge = {0, m_parent->m_indices.at(i), m_parent->m_indices.at(i + 1), -1, -1, 0, true, false, false};
1711 m_edges.add(edge);
1712 }
1713 }
1714 if (first != m_edges.size())
1715 m_edges.last().to = m_edges.at(first).from;
1716 for (int i = 0; i < m_edges.size(); ++i) {
1717 m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp =
1718 m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from);
1719 }
1720}
1721
1722// Return true if new intersection was found
1723template <typename T>
1724bool QTriangulator<T>::ComplexToSimple::calculateIntersection(int left, int right)
1725{
1726 const Edge &e1 = m_edges.at(left);
1727 const Edge &e2 = m_edges.at(right);
1728
1729 const QPodPoint &u1 = m_parent->m_vertices.at((qint32)e1.from);
1730 const QPodPoint &u2 = m_parent->m_vertices.at((qint32)e1.to);
1731 const QPodPoint &v1 = m_parent->m_vertices.at((qint32)e2.from);
1732 const QPodPoint &v2 = m_parent->m_vertices.at((qint32)e2.to);
1733 if (qMax(u1.x, u2.x) <= qMin(v1.x, v2.x))
1734 return false;
1735
1736 quint64 key = (left > right ? (quint64(right) << 32) | quint64(left) : (quint64(left) << 32) | quint64(right));
1737 if (m_processedEdgePairs.contains(key))
1738 return false;
1739 m_processedEdgePairs.insert(key);
1740
1741 Intersection intersection;
1742 intersection.leftEdge = left;
1743 intersection.rightEdge = right;
1744 intersection.intersectionPoint = QT_PREPEND_NAMESPACE(qIntersectionPoint)(u1, u2, v1, v2);
1745
1746 if (!intersection.intersectionPoint.isValid())
1747 return false;
1748
1749 Q_ASSERT(intersection.intersectionPoint.isOnLine(u1, u2));
1750 Q_ASSERT(intersection.intersectionPoint.isOnLine(v1, v2));
1751
1752 intersection.vertex = m_parent->m_vertices.size();
1753 m_topIntersection.push(intersection);
1754 m_parent->m_vertices.add(intersection.intersectionPoint.round());
1755 return true;
1756}
1757
1758template <typename T>
1759bool QTriangulator<T>::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
1760{
1761 const Edge &leftEdge = m_edges.at(leftEdgeIndex);
1762 const Edge &rightEdge = m_edges.at(rightEdgeIndex);
1763 const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
1764 const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
1765 const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper());
1766 if (upper.x < qMin(l.x, u.x))
1767 return true;
1768 if (upper.x > qMax(l.x, u.x))
1769 return false;
1770 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(upper, l, u);
1771 // d < 0: left, d > 0: right, d == 0: on top
1772 if (d == 0)
1773 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.lower()), l, u);
1774 return d < 0;
1775}
1776
1777template <typename T>
1778QRBTree<int>::Node *QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const
1779{
1780 QRBTree<int>::Node *current = m_edgeList.root;
1781 QRBTree<int>::Node *result = 0;
1782 while (current) {
1783 if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
1784 current = current->left;
1785 } else {
1786 result = current;
1787 current = current->right;
1788 }
1789 }
1790 return result;
1791}
1792
1793template <typename T>
1794QRBTree<int>::Node *QTriangulator<T>::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const
1795{
1796 if (!m_edgeList.root)
1797 return after;
1798 QRBTree<int>::Node *result = after;
1799 QRBTree<int>::Node *current = (after ? m_edgeList.next(after) : m_edgeList.front(m_edgeList.root));
1800 while (current) {
1801 if (edgeIsLeftOfEdge(edgeIndex, current->data))
1802 return result;
1803 result = current;
1804 current = m_edgeList.next(current);
1805 }
1806 return result;
1807}
1808
1809template <typename T>
1810QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::ComplexToSimple::bounds(const QPodPoint &point) const
1811{
1812 QRBTree<int>::Node *current = m_edgeList.root;
1813 QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
1814 while (current) {
1815 const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
1816 const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
1817 qint64 d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
1818 if (d == 0) {
1819 result.first = result.second = current;
1820 break;
1821 }
1822 current = (d < 0 ? current->left : current->right);
1823 }