summaryrefslogtreecommitdiffstats
path: root/src/opengl
diff options
context:
space:
mode:
Diffstat (limited to 'src/opengl')
-rw-r--r--src/opengl/gl2paintengineex/qgl2pexvertexarray.cpp2
-rw-r--r--src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp155
-rw-r--r--src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h1
-rw-r--r--src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp4
-rw-r--r--src/opengl/gl2paintengineex/qtriangulator.cpp2983
-rw-r--r--src/opengl/gl2paintengineex/qtriangulator_p.h98
-rw-r--r--src/opengl/opengl.pro2
-rw-r--r--src/opengl/qgl.cpp155
-rw-r--r--src/opengl/qgl.h23
-rw-r--r--src/opengl/qgl_p.h18
-rw-r--r--src/opengl/qgl_win.cpp158
-rw-r--r--src/opengl/qglextensions_p.h14
12 files changed, 3537 insertions, 76 deletions
diff --git a/src/opengl/gl2paintengineex/qgl2pexvertexarray.cpp b/src/opengl/gl2paintengineex/qgl2pexvertexarray.cpp
index 516b847..03b1bf0 100644
--- a/src/opengl/gl2paintengineex/qgl2pexvertexarray.cpp
+++ b/src/opengl/gl2paintengineex/qgl2pexvertexarray.cpp
@@ -145,7 +145,7 @@ void QGL2PEXVertexArray::addPath(const QVectorPath &path, GLfloat curveInverseSc
// threshold based on same algorithm as in qtriangulatingstroker.cpp
int threshold = qMin<float>(64, qMax(bounds.width(), bounds.height()) * 3.14f / (curveInverseScale * 6));
if (threshold < 3) threshold = 3;
- qreal one_over_threshold_minus_1 = 1.f / (threshold - 1);
+ qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1);
for (int t=0; t<threshold; ++t) {
QPointF pt = b.pointAt(t * one_over_threshold_minus_1);
lineToArray(pt.x(), pt.y());
diff --git a/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp b/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp
index caa679b..5e41cc1 100644
--- a/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp
+++ b/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp
@@ -77,6 +77,7 @@
#include <private/qfontengine_p.h>
#include <private/qpixmapdata_gl_p.h>
#include <private/qdatabuffer_p.h>
+#include <private/qtriangulator_p.h>
#include "qglgradientcache_p.h"
#include "qglengineshadermanager_p.h"
@@ -606,10 +607,13 @@ struct QGL2PEVectorPathCache
{
#ifdef QT_OPENGL_CACHE_AS_VBOS
GLuint vbo;
+ GLuint ibo;
#else
float *vertices;
+ quint32 *indices;
#endif
int vertexCount;
+ int indexCount;
GLenum primitiveType;
qreal iscale;
};
@@ -620,9 +624,12 @@ void QGL2PaintEngineExPrivate::cleanupVectorPath(QPaintEngineEx *engine, void *d
#ifdef QT_OPENGL_CACHE_AS_VBOS
Q_ASSERT(engine->type() == QPaintEngine::OpenGL2);
static_cast<QGL2PaintEngineEx *>(engine)->d_func()->unusedVBOSToClean << c->vbo;
+ if (c->ibo)
+ d->unusedIBOSToClean << c->ibo;
#else
Q_UNUSED(engine);
qFree(c->vertices);
+ qFree(c->indices);
#endif
delete c;
}
@@ -653,6 +660,9 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
const QPointF* const points = reinterpret_cast<const QPointF*>(path.points());
+ // ### Remove before release...
+ static bool do_vectorpath_cache = qgetenv("QT_OPENGL_NO_PATH_CACHE").isEmpty();
+
// Check to see if there's any hints
if (path.shape() == QVectorPath::RectangleHint) {
QGLRect rect(points[0].x(), points[0].y(), points[2].x(), points[2].y());
@@ -664,6 +674,8 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
QVectorPath::CacheEntry *data = path.lookupCacheData(q);
QGL2PEVectorPathCache *cache;
+ bool updateCache = false;
+
if (data) {
cache = (QGL2PEVectorPathCache *) data->data;
// Check if scale factor is exceeded for curved paths and generate curves if so...
@@ -673,34 +685,39 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
#ifdef QT_OPENGL_CACHE_AS_VBOS
glDeleteBuffers(1, &cache->vbo);
cache->vbo = 0;
+ Q_ASSERT(cache->ibo == 0);
#else
qFree(cache->vertices);
+ Q_ASSERT(cache->indices == 0);
#endif
- cache->vertexCount = 0;
+ updateCache = true;
}
}
} else {
cache = new QGL2PEVectorPathCache;
- cache->vertexCount = 0;
data = const_cast<QVectorPath &>(path).addCacheData(q, cache, cleanupVectorPath);
+ updateCache = true;
}
// Flatten the path at the current scale factor and fill it into the cache struct.
- if (!cache->vertexCount) {
+ if (updateCache) {
vertexCoordinateArray.clear();
vertexCoordinateArray.addPath(path, inverseScale, false);
int vertexCount = vertexCoordinateArray.vertexCount();
int floatSizeInBytes = vertexCount * 2 * sizeof(float);
cache->vertexCount = vertexCount;
+ cache->indexCount = 0;
cache->primitiveType = GL_TRIANGLE_FAN;
cache->iscale = inverseScale;
#ifdef QT_OPENGL_CACHE_AS_VBOS
glGenBuffers(1, &cache->vbo);
glBindBuffer(GL_ARRAY_BUFFER, cache->vbo);
glBufferData(GL_ARRAY_BUFFER, floatSizeInBytes, vertexCoordinateArray.data(), GL_STATIC_DRAW);
+ cache->ibo = 0;
#else
cache->vertices = (float *) qMalloc(floatSizeInBytes);
memcpy(cache->vertices, vertexCoordinateArray.data(), floatSizeInBytes);
+ cache->indices = 0;
#endif
}
@@ -716,8 +733,6 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
} else {
// printf(" - Marking path as cachable...\n");
// Tag it for later so that if the same path is drawn twice, it is assumed to be static and thus cachable
- // ### Remove before release...
- static bool do_vectorpath_cache = qgetenv("QT_OPENGL_NO_PATH_CACHE").isEmpty();
if (do_vectorpath_cache)
path.makeCacheable();
vertexCoordinateArray.clear();
@@ -727,31 +742,117 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
}
} else {
- // The path is too complicated & needs the stencil technique
- vertexCoordinateArray.clear();
- vertexCoordinateArray.addPath(path, inverseScale, false);
+ bool useCache = path.isCacheable();
+ if (useCache) {
+ QRectF bbox = path.controlPointRect();
+ // If the path doesn't fit within these limits, it is possible that the triangulation will fail.
+ useCache &= (bbox.left() > -0x8000 * inverseScale)
+ && (bbox.right() < 0x8000 * inverseScale)
+ && (bbox.top() > -0x8000 * inverseScale)
+ && (bbox.bottom() < 0x8000 * inverseScale);
+ }
- fillStencilWithVertexArray(vertexCoordinateArray, path.hasWindingFill());
+ if (useCache) {
+ QVectorPath::CacheEntry *data = path.lookupCacheData(q);
+ QGL2PEVectorPathCache *cache;
- glStencilMask(0xff);
- glStencilOp(GL_KEEP, GL_REPLACE, GL_REPLACE);
+ bool updateCache = false;
+
+ if (data) {
+ cache = (QGL2PEVectorPathCache *) data->data;
+ // Check if scale factor is exceeded for curved paths and generate curves if so...
+ if (path.isCurved()) {
+ qreal scaleFactor = cache->iscale / inverseScale;
+ if (scaleFactor < 0.5 || scaleFactor > 2.0) {
+#ifdef QT_OPENGL_CACHE_AS_VBOS
+ glDeleteBuffers(1, &cache->vbo);
+ glDeleteBuffers(1, &cache->ibo);
+#else
+ qFree(cache->vertices);
+ qFree(cache->indices);
+#endif
+ updateCache = true;
+ }
+ }
+ } else {
+ cache = new QGL2PEVectorPathCache;
+ data = const_cast<QVectorPath &>(path).addCacheData(q, cache, cleanupVectorPath);
+ updateCache = true;
+ }
+
+ // Flatten the path at the current scale factor and fill it into the cache struct.
+ if (updateCache) {
+ QTriangleSet polys = qTriangulate(path, QTransform().scale(1 / inverseScale, 1 / inverseScale));
+ cache->vertexCount = polys.vertices.size() / 2;
+ cache->indexCount = polys.indices.size();
+ cache->primitiveType = GL_TRIANGLES;
+ cache->iscale = inverseScale;
+
+#ifdef QT_OPENGL_CACHE_AS_VBOS
+ glGenBuffers(1, &cache->vbo);
+ glGenBuffers(1, &cache->ibo);
+ glBindBuffer(GL_ARRAY_BUFFER, cache->vbo);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cache->ibo);
+ glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(quint32) * polys.indices.size(), polys.indices.data(), GL_STATIC_DRAW);
+
+ QVarLengthArray<float> vertices(polys.vertices.size());
+ for (int i = 0; i < polys.vertices.size(); ++i)
+ vertices[i] = float(inverseScale * polys.vertices.at(i));
+ glBufferData(GL_ARRAY_BUFFER, sizeof(float) * vertices.size(), vertices.data(), GL_STATIC_DRAW);
+#else
+ cache->vertices = (float *) qMalloc(sizeof(float) * polys.vertices.size());
+ cache->indices = (quint32 *) qMalloc(sizeof(quint32) * polys.indices.size());
+ memcpy(cache->indices, polys.indices.data(), sizeof(quint32) * polys.indices.size());
+ for (int i = 0; i < polys.vertices.size(); ++i)
+ cache->vertices[i] = float(inverseScale * polys.vertices.at(i));
+#endif
+ }
+
+ prepareForDraw(currentBrush.isOpaque());
+#ifdef QT_OPENGL_CACHE_AS_VBOS
+ glBindBuffer(GL_ARRAY_BUFFER, cache->vbo);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cache->ibo);
+ setVertexAttributePointer(QT_VERTEX_COORDS_ATTR, 0);
+ glDrawElements(cache->primitiveType, cache->indexCount, GL_UNSIGNED_INT, 0);
+ glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
+ glBindBuffer(GL_ARRAY_BUFFER, 0);
+#else
+ setVertexAttributePointer(QT_VERTEX_COORDS_ATTR, cache->vertices);
+ glDrawElements(cache->primitiveType, cache->indexCount, GL_UNSIGNED_INT, cache->indices);
+#endif
- if (q->state()->clipTestEnabled) {
- // Pass when high bit is set, replace stencil value with current clip
- glStencilFunc(GL_NOTEQUAL, q->state()->currentClip, GL_STENCIL_HIGH_BIT);
- } else if (path.hasWindingFill()) {
- // Pass when any bit is set, replace stencil value with 0
- glStencilFunc(GL_NOTEQUAL, 0, 0xff);
} else {
- // Pass when high bit is set, replace stencil value with 0
- glStencilFunc(GL_NOTEQUAL, 0, GL_STENCIL_HIGH_BIT);
- }
- prepareForDraw(currentBrush.isOpaque());
+ // printf(" - Marking path as cachable...\n");
+ // Tag it for later so that if the same path is drawn twice, it is assumed to be static and thus cachable
+ if (do_vectorpath_cache)
+ path.makeCacheable();
- // Stencil the brush onto the dest buffer
- composite(vertexCoordinateArray.boundingRect());
- glStencilMask(0);
- updateClipScissorTest();
+ // The path is too complicated & needs the stencil technique
+ vertexCoordinateArray.clear();
+ vertexCoordinateArray.addPath(path, inverseScale, false);
+
+ fillStencilWithVertexArray(vertexCoordinateArray, path.hasWindingFill());
+
+ glStencilMask(0xff);
+ glStencilOp(GL_KEEP, GL_REPLACE, GL_REPLACE);
+
+ if (q->state()->clipTestEnabled) {
+ // Pass when high bit is set, replace stencil value with current clip
+ glStencilFunc(GL_NOTEQUAL, q->state()->currentClip, GL_STENCIL_HIGH_BIT);
+ } else if (path.hasWindingFill()) {
+ // Pass when any bit is set, replace stencil value with 0
+ glStencilFunc(GL_NOTEQUAL, 0, 0xff);
+ } else {
+ // Pass when high bit is set, replace stencil value with 0
+ glStencilFunc(GL_NOTEQUAL, 0, GL_STENCIL_HIGH_BIT);
+ }
+ prepareForDraw(currentBrush.isOpaque());
+
+ // Stencil the brush onto the dest buffer
+ composite(vertexCoordinateArray.boundingRect());
+ glStencilMask(0);
+ updateClipScissorTest();
+ }
}
}
@@ -1605,6 +1706,10 @@ bool QGL2PaintEngineEx::end()
glDeleteBuffers(d->unusedVBOSToClean.size(), d->unusedVBOSToClean.constData());
d->unusedVBOSToClean.clear();
}
+ if (!d->unusedIBOSToClean.isEmpty()) {
+ glDeleteBuffers(d->unusedIBOSToClean.size(), d->unusedIBOSToClean.constData());
+ d->unusedIBOSToClean.clear();
+ }
#endif
return false;
diff --git a/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h b/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h
index ce1b538..e3d0bfc 100644
--- a/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h
+++ b/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h
@@ -295,6 +295,7 @@ public:
QSet<QVectorPath::CacheEntry *> pathCaches;
QVector<GLuint> unusedVBOSToClean;
+ QVector<GLuint> unusedIBOSToClean;
const GLfloat *vertexAttribPointers[3];
};
diff --git a/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp b/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp
index fed1658..6cb76ee 100644
--- a/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp
+++ b/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp
@@ -42,6 +42,8 @@
#include "qtextureglyphcache_gl_p.h"
#include "qpaintengineex_opengl2_p.h"
+QT_BEGIN_NAMESPACE
+
#ifdef Q_WS_WIN
extern Q_GUI_EXPORT bool qt_cleartype_enabled;
#endif
@@ -243,3 +245,5 @@ int QGLTextureGlyphCache::glyphMargin() const
return m_type == QFontEngineGlyphCache::Raster_RGBMask ? 2 : 0;
#endif
}
+
+QT_END_NAMESPACE
diff --git a/src/opengl/gl2paintengineex/qtriangulator.cpp b/src/opengl/gl2paintengineex/qtriangulator.cpp
new file mode 100644
index 0000000..115f31b
--- /dev/null
+++ b/src/opengl/gl2paintengineex/qtriangulator.cpp
@@ -0,0 +1,2983 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtOpenGL module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qtriangulator_p.h"
+
+#include <QtGui/qdialog.h>
+#include <QtGui/qevent.h>
+#include <QtGui/qpainter.h>
+#include <QtGui/qpainterpath.h>
+#include <QtGui/private/qbezier_p.h>
+#include <QtGui/private/qdatabuffer_p.h>
+#include <QtCore/qbitarray.h>
+#include <QtCore/qvarlengtharray.h>
+#include <QtCore/qqueue.h>
+#include <QtCore/qglobal.h>
+#include <QtCore/qpoint.h>
+#include <QtCore/qalgorithms.h>
+#include <QtDebug>
+
+#include <math.h>
+
+QT_BEGIN_NAMESPACE
+
+//#define Q_TRIANGULATOR_DEBUG
+
+#define Q_FIXED_POINT_SCALE 32
+
+// Quick sort.
+template <class T, class LessThan>
+static void sort(T *array, int count, LessThan lessThan)
+{
+ // If the number of elements fall below some threshold, use insertion sort.
+ const int INSERTION_SORT_LIMIT = 7; // About 7 is fastest on my computer...
+ if (count <= INSERTION_SORT_LIMIT) {
+ for (int i = 1; i < count; ++i) {
+ T temp = array[i];
+ int j = i;
+ while (j > 0 && lessThan(temp, array[j - 1])) {
+ array[j] = array[j - 1];
+ --j;
+ }
+ array[j] = temp;
+ }
+ return;
+ }
+
+ int high = count - 1;
+ int low = 0;
+ int mid = high / 2;
+ if (lessThan(array[mid], array[low]))
+ qSwap(array[mid], array[low]);
+ if (lessThan(array[high], array[mid]))
+ qSwap(array[high], array[mid]);
+ if (lessThan(array[mid], array[low]))
+ qSwap(array[mid], array[low]);
+
+ --high;
+ ++low;
+ qSwap(array[mid], array[high]);
+ int pivot = high;
+ --high;
+
+ while (low <= high) {
+ while (!lessThan(array[pivot], array[low])) {
+ ++low;
+ if (low > high)
+ goto sort_loop_end;
+ }
+ while (!lessThan(array[high], array[pivot])) {
+ --high;
+ if (low > high)
+ goto sort_loop_end;
+ }
+ qSwap(array[low], array[high]);
+ ++low;
+ --high;
+ }
+sort_loop_end:
+ if (low != pivot)
+ qSwap(array[pivot], array[low]);
+ sort(array, low, lessThan);
+ sort(array + low + 1, count - low - 1, lessThan);
+}
+
+// Quick sort.
+template <class T>
+static void sort(T *array, int count)
+{
+ // If the number of elements fall below some threshold, use insertion sort.
+ const int INSERTION_SORT_LIMIT = 25; // About 25 is fastest on my computer...
+ if (count <= INSERTION_SORT_LIMIT) {
+ for (int i = 1; i < count; ++i) {
+ T temp = array[i];
+ int j = i;
+ while (j > 0 && (temp < array[j - 1])) {
+ array[j] = array[j - 1];
+ --j;
+ }
+ array[j] = temp;
+ }
+ return;
+ }
+
+ int high = count - 1;
+ int low = 0;
+ int mid = high / 2;
+ if ((array[mid] < array[low]))
+ qSwap(array[mid], array[low]);
+ if ((array[high] < array[mid]))
+ qSwap(array[high], array[mid]);
+ if ((array[mid] < array[low]))
+ qSwap(array[mid], array[low]);
+
+ --high;
+ ++low;
+ qSwap(array[mid], array[high]);
+ int pivot = high;
+ --high;
+
+ while (low <= high) {
+ while (!(array[pivot] < array[low])) {
+ ++low;
+ if (low > high)
+ goto sort_loop_end;
+ }
+ while (!(array[high] < array[pivot])) {
+ --high;
+ if (low > high)
+ goto sort_loop_end;
+ }
+ qSwap(array[low], array[high]);
+ ++low;
+ --high;
+ }
+sort_loop_end:
+ if (low != pivot)
+ qSwap(array[pivot], array[low]);
+ sort(array, low);
+ sort(array + low + 1, count - low - 1);
+}
+
+//============================================================================//
+// QFraction //
+//============================================================================//
+
+// Fraction must be in the range [0, 1)
+struct QFraction
+{
+ // Comparison operators must not be called on invalid fractions.
+ inline bool operator < (const QFraction &other) const;
+ inline bool operator == (const QFraction &other) const;
+ inline bool operator != (const QFraction &other) const {return !(*this == other);}
+ inline bool operator > (const QFraction &other) const {return other < *this;}
+ inline bool operator >= (const QFraction &other) const {return !(*this < other);}
+ inline bool operator <= (const QFraction &other) const {return !(*this > other);}
+
+ inline bool isValid() const {return denominator != 0;}
+
+ // numerator and denominator must not have common denominators.
+ quint64 numerator, denominator;
+};
+
+static inline quint64 gcd(quint64 x, quint64 y)
+{
+ while (y != 0) {
+ quint64 z = y;
+ y = x % y;
+ x = z;
+ }
+ return x;
+}
+
+static inline int compare(quint64 a, quint64 b)
+{
+ return (a > b) - (a < b);
+}
+
+// Compare a/b with c/d.
+// Return negative if less, 0 if equal, positive if greater.
+// a < b, c < d
+static int qCompareFractions(quint64 a, quint64 b, quint64 c, quint64 d)
+{
+ const quint64 LIMIT = Q_UINT64_C(0x100000000);
+ for (;;) {
+ // If the products 'ad' and 'bc' fit into 64 bits, they can be directly compared.
+ if (b < LIMIT && d < LIMIT)
+ return compare(a * d, b * c);
+
+ if (a == 0 || c == 0)
+ return compare(a, c);
+
+ // a/b < c/d <=> d/c < b/a
+ quint64 b_div_a = b / a;
+ quint64 d_div_c = d / c;
+ if (b_div_a != d_div_c)
+ return compare(d_div_c, b_div_a);
+
+ // floor(d/c) == floor(b/a)
+ // frac(d/c) < frac(b/a) ?
+ // frac(x/y) = (x%y)/y
+ d -= d_div_c * c; //d %= c;
+ b -= b_div_a * a; //b %= a;
+ qSwap(a, d);
+ qSwap(b, c);
+ }
+}
+
+// Fraction must be in the range [0, 1)
+// Assume input is valid.
+static QFraction qFraction(quint64 n, quint64 d) {
+ QFraction result;
+ if (n == 0) {
+ result.numerator = 0;
+ result.denominator = 1;
+ } else {
+ quint64 g = gcd(n, d);
+ result.numerator = n / g;
+ result.denominator = d / g;
+ }
+ return result;
+}
+
+inline bool QFraction::operator < (const QFraction &other) const
+{
+ return qCompareFractions(numerator, denominator, other.numerator, other.denominator) < 0;
+}
+
+inline bool QFraction::operator == (const QFraction &other) const
+{
+ return numerator == other.numerator && denominator == other.denominator;
+}
+
+//============================================================================//
+// QPodPoint //
+//============================================================================//
+
+struct QPodPoint
+{
+ inline bool operator < (const QPodPoint &other) const
+ {
+ if (y != other.y)
+ return y < other.y;
+ return x < other.x;
+ }
+
+ inline bool operator > (const QPodPoint &other) const {return other < *this;}
+ inline bool operator <= (const QPodPoint &other) const {return !(*this > other);}
+ inline bool operator >= (const QPodPoint &other) const {return !(*this < other);}
+ inline bool operator == (const QPodPoint &other) const {return x == other.x && y == other.y;}
+ inline bool operator != (const QPodPoint &other) const {return x != other.x || y != other.y;}
+
+ inline QPodPoint &operator += (const QPodPoint &other) {x += other.x; y += other.y; return *this;}
+ inline QPodPoint &operator -= (const QPodPoint &other) {x -= other.x; y -= other.y; return *this;}
+ inline QPodPoint operator + (const QPodPoint &other) const {QPodPoint result = {x + other.x, y + other.y}; return result;}
+ inline QPodPoint operator - (const QPodPoint &other) const {QPodPoint result = {x - other.x, y - other.y}; return result;}
+
+ int x;
+ int y;
+};
+
+static inline qint64 qCross(const QPodPoint &u, const QPodPoint &v)
+{
+ return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
+}
+
+static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v)
+{
+ return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
+}
+
+// Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the
+// line and zero if exactly on the line.
+// The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1',
+// which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order).
+static inline qint64 qPointDistanceFromLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
+{
+ return qCross(v2 - v1, p - v1);
+}
+
+static inline bool qPointIsLeftOfLine(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
+{
+ return qPointDistanceFromLine(p, v1, v2) < 0;
+}
+
+// Return:
+// -1 if u < v
+// 0 if u == v
+// 1 if u > v
+static int comparePoints(const QPodPoint &u, const QPodPoint &v)
+{
+ if (u.y < v.y)
+ return -1;
+ if (u.y > v.y)
+ return 1;
+ if (u.x < v.x)
+ return -1;
+ if (u.x > v.x)
+ return 1;
+ return 0;
+}
+
+//============================================================================//
+// QIntersectionPoint //
+//============================================================================//
+
+struct QIntersectionPoint
+{
+ inline bool isValid() const {return xOffset.isValid() && yOffset.isValid();}
+ QPodPoint round() const;
+ inline bool isAccurate() const {return xOffset.numerator == 0 && yOffset.numerator == 0;}
+ bool operator < (const QIntersectionPoint &other) const;
+ bool operator == (const QIntersectionPoint &other) const;
+ inline bool operator != (const QIntersectionPoint &other) const {return !(*this == other);}
+ inline bool operator > (const QIntersectionPoint &other) const {return other < *this;}
+ inline bool operator >= (const QIntersectionPoint &other) const {return !(*this < other);}
+ inline bool operator <= (const QIntersectionPoint &other) const {return !(*this > other);}
+ bool isOnLine(const QPodPoint &u, const QPodPoint &v) const;
+
+ QPodPoint upperLeft;
+ QFraction xOffset;
+ QFraction yOffset;
+};
+
+static inline QIntersectionPoint qIntersectionPoint(const QPodPoint &point)
+{
+ // upperLeft = point, xOffset = 0/1, yOffset = 0/1.
+ QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};
+ return p;
+}
+
+static inline QIntersectionPoint qIntersectionPoint(int x, int y)
+{
+ // upperLeft = (x, y), xOffset = 0/1, yOffset = 0/1.
+ QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};
+ return p;
+}
+
+static QIntersectionPoint qIntersectionPoint(const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2)
+{
+ QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};
+
+ QPodPoint u = u2 - u1;
+ QPodPoint v = v2 - v1;
+ qint64 d1 = qCross(u, v1 - u1);
+ qint64 d2 = qCross(u, v2 - u1);
+ qint64 det = d2 - d1;
+ qint64 d3 = qCross(v, u1 - v1);
+ qint64 d4 = d3 - det; //qCross(v, u2 - v1);
+
+ // Check that the math is correct.
+ Q_ASSERT(d4 == qCross(v, u2 - v1));
+
+ // The intersection point can be expressed as:
+ // v1 - v * d1/det
+ // v2 - v * d2/det
+ // u1 + u * d3/det
+ // u2 + u * d4/det
+
+ // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.
+ if (det == 0)
+ return result;
+
+ if (det < 0) {
+ det = -det;
+ d1 = -d1;
+ d2 = -d2;
+ d3 = -d3;
+ d4 = -d4;
+ }
+
+ // I'm only interested in lines intersecting at their interior, not at their end points.
+ // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'.
+ if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
+ return result;
+
+ // Calculate the intersection point as follows:
+ // v1 - v * d1/det | v1 <= v2 (component-wise)
+ // v2 - v * d2/det | v2 < v1 (component-wise)
+
+ // Assuming 21 bits per vector component.
+ // TODO: Make code path for 31 bits per vector component.
+ if (v.x >= 0) {
+ result.upperLeft.x = v1.x + (-v.x * d1) / det;
+ result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));
+ } else {
+ result.upperLeft.x = v2.x + (-v.x * d2) / det;
+ result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));
+ }
+
+ if (v.y >= 0) {
+ result.upperLeft.y = v1.y + (-v.y * d1) / det;
+ result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));
+ } else {
+ result.upperLeft.y = v2.y + (-v.y * d2) / det;
+ result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));
+ }
+
+ Q_ASSERT(result.xOffset.isValid());
+ Q_ASSERT(result.yOffset.isValid());
+ return result;
+}
+
+QPodPoint QIntersectionPoint::round() const
+{
+ QPodPoint result = upperLeft;
+ if (2 * xOffset.numerator >= xOffset.denominator)
+ ++result.x;
+ if (2 * yOffset.numerator >= yOffset.denominator)
+ ++result.y;
+ return result;
+}
+
+bool QIntersectionPoint::operator < (const QIntersectionPoint &other) const
+{
+ if (upperLeft.y != other.upperLeft.y)
+ return upperLeft.y < other.upperLeft.y;
+ if (yOffset != other.yOffset)
+ return yOffset < other.yOffset;
+ if (upperLeft.x != other.upperLeft.x)
+ return upperLeft.x < other.upperLeft.x;
+ return xOffset < other.xOffset;
+}
+
+bool QIntersectionPoint::operator == (const QIntersectionPoint &other) const
+{
+ return upperLeft == other.upperLeft && xOffset == other.xOffset && yOffset == other.yOffset;
+}
+
+// Returns true if this point is on the infinite line passing through 'u' and 'v'.
+bool QIntersectionPoint::isOnLine(const QPodPoint &u, const QPodPoint &v) const
+{
+ // TODO: Make code path for coordinates with more than 21 bits.
+ const QPodPoint p = upperLeft - u;
+ const QPodPoint q = v - u;
+ bool isHorizontal = p.y == 0 && yOffset.numerator == 0;
+ bool isVertical = p.x == 0 && xOffset.numerator == 0;
+ if (isHorizontal && isVertical)
+ return true;
+ if (isHorizontal)
+ return q.y == 0;
+ if (q.y == 0)
+ return false;
+ if (isVertical)
+ return q.x == 0;
+ if (q.x == 0)
+ return false;
+
+ // At this point, 'p+offset' and 'q' cannot lie on the x or y axis.
+
+ if (((q.x < 0) == (q.y < 0)) != ((p.x < 0) == (p.y < 0)))
+ return false; // 'p + offset' and 'q' pass through different quadrants.
+
+ // Move all coordinates into the first quadrant.
+ quint64 nx, ny;
+ if (p.x < 0)
+ nx = quint64(-p.x) * xOffset.denominator - xOffset.numerator;
+ else
+ nx = quint64(p.x) * xOffset.denominator + xOffset.numerator;
+ if (p.y < 0)
+ ny = quint64(-p.y) * yOffset.denominator - yOffset.numerator;
+ else
+ ny = quint64(p.y) * yOffset.denominator + yOffset.numerator;
+
+ return qFraction(quint64(qAbs(q.x)) * xOffset.denominator, quint64(qAbs(q.y)) * yOffset.denominator) == qFraction(nx, ny);
+}
+
+//============================================================================//
+// QMaxHeap //
+//============================================================================//
+
+template <class T>
+class QMaxHeap
+{
+public:
+ inline int size() const {return m_data.size();}
+ inline bool empty() const {return m_data.isEmpty();}
+ inline bool isEmpty() const {return m_data.isEmpty();}
+ void push(const T &x);
+ T pop();
+ inline const T &top() const {return m_data.first();}
+private:
+ static inline int parent(int i) {return (i - 1) / 2;}
+ static inline int left(int i) {return 2 * i + 1;}
+ static inline int right(int i) {return 2 * i + 2;}
+
+ QDataBuffer<T> m_data;
+};
+
+template <class T>
+void QMaxHeap<T>::push(const T &x)
+{
+ int current = m_data.size();
+ int parent = QMaxHeap::parent(current);
+ m_data.add(x);
+ while (current != 0 && m_data.at(parent) < x) {
+ m_data.at(current) = m_data.at(parent);
+ current = parent;
+ parent = QMaxHeap::parent(current);
+ }
+ m_data.at(current) = x;
+}
+
+template <class T>
+T QMaxHeap<T>::pop()
+{
+ T result = m_data.first();
+ T back = m_data.last();
+ m_data.pop_back();
+ if (!m_data.isEmpty()) {
+ int current = 0;
+ for (;;) {
+ int left = QMaxHeap::left(current);
+ int right = QMaxHeap::right(current);
+ if (left >= m_data.size())
+ break;
+ int greater = left;
+ if (right < m_data.size() && m_data.at(left) < m_data.at(right))
+ greater = right;
+ if (m_data.at(greater) < back)
+ break;
+ m_data.at(current) = m_data.at(greater);
+ current = greater;
+ }
+ m_data.at(current) = back;
+ }
+ return result;
+}
+
+//============================================================================//
+// QRBTree //
+//============================================================================//
+
+template <class T>
+struct QRBTree
+{
+ struct Node
+ {
+ inline Node() : parent(0), left(0), right(0), red(true) { }
+ inline ~Node() {if (left) delete left; if (right) delete right;}
+ T data;
+ Node *parent;
+ Node *left;
+ Node *right;
+ bool red;
+ };
+
+ inline QRBTree() : root(0), freeList(0) { }
+ inline ~QRBTree();
+
+ inline void clear();
+
+ void attachBefore(Node *parent, Node *child);
+ void attachAfter(Node *parent, Node *child);
+
+ inline Node *front(Node *node) const;
+ inline Node *back(Node *node) const;
+ Node *next(Node *node) const;
+ Node *previous(Node *node) const;
+
+ inline void deleteNode(Node *&node);
+ inline Node *newNode();
+
+ // Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
+ // 'left' and 'right' cannot be null.
+ int order(Node *left, Node *right);
+ inline bool verify() const;
+
+private:
+ void rotateLeft(Node *node);
+ void rotateRight(Node *node);
+ void update(Node *node);
+
+ inline void attachLeft(Node *parent, Node *child);
+ inline void attachRight(Node *parent, Node *child);
+
+ int blackDepth(Node *top) const;
+ bool checkRedBlackProperty(Node *top) const;
+
+ void swapNodes(Node *n1, Node *n2);
+ void detach(Node *node);
+
+ // 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
+ void rebalance(Node *node);
+
+public:
+ Node *root;
+private:
+ Node *freeList;
+};
+
+template <class T>
+inline QRBTree<T>::~QRBTree()
+{
+ clear();
+ while (freeList) {
+ // Avoid recursively calling the destructor, as this list may become large.
+ Node *next = freeList->right;
+ freeList->right = 0;
+ delete freeList;
+ freeList = next;
+ }
+}
+
+template <class T>
+inline void QRBTree<T>::clear()
+{
+ if (root)
+ delete root;
+ root = 0;
+}
+
+template <class T>
+void QRBTree<T>::rotateLeft(Node *node)
+{
+ // | | //
+ // N B //
+ // / \ / \ //
+ // A B ---> N D //
+ // / \ / \ //
+ // C D A C //
+
+ Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
+ ref = node->right;
+ node->right->parent = node->parent;
+
+ // : //
+ // N //
+ // / :| //
+ // A B //
+ // / \ //
+ // C D //
+
+ node->right = ref->left;
+ if (ref->left)
+ ref->left->parent = node;
+
+ // : | //
+ // N B //
+ // / \ : \ //
+ // A C D //
+
+ ref->left = node;
+ node->parent = ref;
+
+ // | //
+ // B //
+ // / \ //
+ // N D //
+ // / \ //
+ // A C //
+}
+
+template <class T>
+void QRBTree<T>::rotateRight(Node *node)
+{
+ // | | //
+ // N A //
+ // / \ / \ //
+ // A B ---> C N //
+ // / \ / \ //
+ // C D D B //
+
+ Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
+ ref = node->left;
+ node->left->parent = node->parent;
+
+ node->left = ref->right;
+ if (ref->right)
+ ref->right->parent = node;
+
+ ref->right = node;
+ node->parent = ref;
+}
+
+template <class T>
+void QRBTree<T>::update(Node *node) // call this after inserting a node
+{
+ for (;;) {
+ Node *parent = node->parent;
+
+ // if the node is the root, color it black
+ if (!parent) {
+ node->red = false;
+ return;
+ }
+
+ // if the parent is black, the node can be left red
+ if (!parent->red)
+ return;
+
+ // at this point, the parent is red and cannot be the root
+ Node *grandpa = parent->parent;
+ Q_ASSERT(grandpa);
+
+ Node *uncle = (parent == grandpa->left ? grandpa->right : grandpa->left);
+ if (uncle && uncle->red) {
+ // grandpa's black, parent and uncle are red.
+ // let parent and uncle be black, grandpa red and recursively update grandpa.
+ Q_ASSERT(!grandpa->red);
+ parent->red = false;
+ uncle->red = false;
+ grandpa->red = true;
+ node = grandpa;
+ continue;
+ }
+
+ // at this point, uncle is black
+ if (node == parent->right && parent == grandpa->left)
+ rotateLeft(node = parent);
+ else if (node == parent->left && parent == grandpa->right)
+ rotateRight(node = parent);
+ parent = node->parent;
+
+ if (parent == grandpa->left) {
+ rotateRight(grandpa);
+ parent->red = false;
+ grandpa->red = true;
+ } else {
+ rotateLeft(grandpa);
+ parent->red = false;
+ grandpa->red = true;
+ }
+ return;
+ }
+}
+
+template <class T>
+inline void QRBTree<T>::attachLeft(Node *parent, Node *child)
+{
+ Q_ASSERT(!parent->left);
+ parent->left = child;
+ child->parent = parent;
+ update(child);
+}
+
+template <class T>
+inline void QRBTree<T>::attachRight(Node *parent, Node *child)
+{
+ Q_ASSERT(!parent->right);
+ parent->right = child;
+ child->parent = parent;
+ update(child);
+}
+
+template <class T>
+void QRBTree<T>::attachBefore(Node *parent, Node *child)
+{
+ if (!root)
+ update(root = child);
+ else if (!parent)
+ attachRight(back(root), child);
+ else if (parent->left)
+ attachRight(back(parent->left), child);
+ else
+ attachLeft(parent, child);
+}
+
+template <class T>
+void QRBTree<T>::attachAfter(Node *parent, Node *child)
+{
+ if (!root)
+ update(root = child);
+ else if (!parent)
+ attachLeft(front(root), child);
+ else if (parent->right)
+ attachLeft(front(parent->right), child);
+ else
+ attachRight(parent, child);
+}
+
+template <class T>
+void QRBTree<T>::swapNodes(Node *n1, Node *n2)
+{
+ // Since iterators must not be invalidated, it is not sufficient to only swap the data.
+ if (n1->parent == n2) {
+ n1->parent = n2->parent;
+ n2->parent = n1;
+ } else if (n2->parent == n1) {
+ n2->parent = n1->parent;
+ n1->parent = n2;
+ } else {
+ qSwap(n1->parent, n2->parent);
+ }
+
+ qSwap(n1->left, n2->left);
+ qSwap(n1->right, n2->right);
+ qSwap(n1->red, n2->red);
+
+ if (n1->parent) {
+ if (n1->parent->left == n2)
+ n1->parent->left = n1;
+ else
+ n1->parent->right = n1;
+ } else {
+ root = n1;
+ }
+
+ if (n2->parent) {
+ if (n2->parent->left == n1)
+ n2->parent->left = n2;
+ else
+ n2->parent->right = n2;
+ } else {
+ root = n2;
+ }
+
+ if (n1->left)
+ n1->left->parent = n1;
+ if (n1->right)
+ n1->right->parent = n1;
+
+ if (n2->left)
+ n2->left->parent = n2;
+ if (n2->right)
+ n2->right->parent = n2;
+}
+
+template <class T>
+void QRBTree<T>::detach(Node *node) // call this before removing a node.
+{
+ if (node->right)
+ swapNodes(node, front(node->right));
+
+ Node *child = (node->left ? node->left : node->right);
+
+ if (!node->red) {
+ if (child && child->red)
+ child->red = false;
+ else
+ rebalance(node);
+ }
+
+ Node *&ref = (node->parent ? (node == node->parent->left ? node->parent->left : node->parent->right) : root);
+ ref = child;
+ if (child)
+ child->parent = node->parent;
+ node->left = node->right = node->parent = 0;
+}
+
+// 'node' must be black. rebalance will reduce the depth of black nodes by one in the sibling tree.
+template <class T>
+void QRBTree<T>::rebalance(Node *node)
+{
+ Q_ASSERT(!node->red);
+ for (;;) {
+ if (!node->parent)
+ return;
+
+ // at this point, node is not a parent, it is black, thus it must have a sibling.
+ Node *sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
+ Q_ASSERT(sibling);
+
+ if (sibling->red) {
+ sibling->red = false;
+ node->parent->red = true;
+ if (node == node->parent->left)
+ rotateLeft(node->parent);
+ else
+ rotateRight(node->parent);
+ sibling = (node == node->parent->left ? node->parent->right : node->parent->left);
+ Q_ASSERT(sibling);
+ }
+
+ // at this point, the sibling is black.
+ Q_ASSERT(!sibling->red);
+
+ if ((!sibling->left || !sibling->left->red) && (!sibling->right || !sibling->right->red)) {
+ bool parentWasRed = node->parent->red;
+ sibling->red = true;
+ node->parent->red = false;
+ if (parentWasRed)
+ return;
+ node = node->parent;
+ continue;
+ }
+
+ // at this point, at least one of the sibling's children is red.
+
+ if (node == node->parent->left) {
+ if (!sibling->right || !sibling->right->red) {
+ Q_ASSERT(sibling->left);
+ sibling->red = true;
+ sibling->left->red = false;
+ rotateRight(sibling);
+
+ sibling = sibling->parent;
+ Q_ASSERT(sibling);
+ }
+ sibling->red = node->parent->red;
+ node->parent->red = false;
+
+ Q_ASSERT(sibling->right->red);
+ sibling->right->red = false;
+ rotateLeft(node->parent);
+ } else {
+ if (!sibling->left || !sibling->left->red) {
+ Q_ASSERT(sibling->right);
+ sibling->red = true;
+ sibling->right->red = false;
+ rotateLeft(sibling);
+
+ sibling = sibling->parent;
+ Q_ASSERT(sibling);
+ }
+ sibling->red = node->parent->red;
+ node->parent->red = false;
+
+ Q_ASSERT(sibling->left->red);
+ sibling->left->red = false;
+ rotateRight(node->parent);
+ }
+ return;
+ }
+}
+
+template <class T>
+inline typename QRBTree<T>::Node *QRBTree<T>::front(Node *node) const
+{
+ while (node->left)
+ node = node->left;
+ return node;
+}
+
+template <class T>
+inline typename QRBTree<T>::Node *QRBTree<T>::back(Node *node) const
+{
+ while (node->right)
+ node = node->right;
+ return node;
+}
+
+template <class T>
+typename QRBTree<T>::Node *QRBTree<T>::next(Node *node) const
+{
+ if (node->right)
+ return front(node->right);
+ while (node->parent && node == node->parent->right)
+ node = node->parent;
+ return node->parent;
+}
+
+template <class T>
+typename QRBTree<T>::Node *QRBTree<T>::previous(Node *node) const
+{
+ if (node->left)
+ return back(node->left);
+ while (node->parent && node == node->parent->left)
+ node = node->parent;
+ return node->parent;
+}
+
+template <class T>
+int QRBTree<T>::blackDepth(Node *top) const
+{
+ if (!top)
+ return 0;
+ int leftDepth = blackDepth(top->left);
+ int rightDepth = blackDepth(top->right);
+ if (leftDepth != rightDepth)
+ return -1;
+ if (!top->red)
+ ++leftDepth;
+ return leftDepth;
+}
+
+template <class T>
+bool QRBTree<T>::checkRedBlackProperty(Node *top) const
+{
+ if (!top)
+ return true;
+ if (top->left && !checkRedBlackProperty(top->left))
+ return false;
+ if (top->right && !checkRedBlackProperty(top->right))
+ return false;
+ return !(top->red && ((top->left && top->left->red) || (top->right && top->right->red)));
+}
+
+template <class T>
+inline bool QRBTree<T>::verify() const
+{
+ return checkRedBlackProperty(root) && blackDepth(root) != -1;
+}
+
+template <class T>
+inline void QRBTree<T>::deleteNode(Node *&node)
+{
+ Q_ASSERT(node);
+ detach(node);
+ node->right = freeList;
+ freeList = node;
+ node = 0;
+}
+
+template <class T>
+inline typename QRBTree<T>::Node *QRBTree<T>::newNode()
+{
+ if (freeList) {
+ Node *node = freeList;
+ freeList = freeList->right;
+ node->parent = node->left = node->right = 0;
+ node->red = true;
+ return node;
+ }
+ return new Node;
+}
+
+// Return 1 if 'left' comes after 'right', 0 if equal, and -1 otherwise.
+// 'left' and 'right' cannot be null.
+template <class T>
+int QRBTree<T>::order(Node *left, Node *right)
+{
+ Q_ASSERT(left && right);
+ if (left == right)
+ return 0;
+
+ QVector<Node *> leftAncestors;
+ QVector<Node *> rightAncestors;
+ while (left) {
+ leftAncestors.push_back(left);
+ left = left->parent;
+ }
+ while (right) {
+ rightAncestors.push_back(right);
+ right = right->parent;
+ }
+ Q_ASSERT(leftAncestors.back() == root && rightAncestors.back() == root);
+
+ while (!leftAncestors.empty() && !rightAncestors.empty() && leftAncestors.back() == rightAncestors.back()) {
+ leftAncestors.pop_back();
+ rightAncestors.pop_back();
+ }
+
+ if (!leftAncestors.empty())
+ return (leftAncestors.back() == leftAncestors.back()->parent->left ? -1 : 1);
+
+ if (!rightAncestors.empty())
+ return (rightAncestors.back() == rightAncestors.back()->parent->right ? -1 : 1);
+
+ // The code should never reach this point.
+ Q_ASSERT(!leftAncestors.empty() || !rightAncestors.empty());
+ return 0;
+}
+
+//============================================================================//
+// QInt64Hash //
+//============================================================================//
+
+// Copied from qhash.cpp
+static const uchar prime_deltas[] = {
+ 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
+ 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
+};
+
+// Copied from qhash.cpp
+static inline int primeForNumBits(int numBits)
+{
+ return (1 << numBits) + prime_deltas[numBits];
+}
+
+static inline int primeForCount(int count)
+{
+ int low = 0;
+ int high = 32;
+ for (int i = 0; i < 5; ++i) {
+ int mid = (high + low) / 2;
+ if (count >= 1 << mid)
+ low = mid;
+ else
+ high = mid;
+ }
+ return primeForNumBits(high);
+}
+
+// Hash set of quint64s. Elements cannot be removed without clearing the
+// entire set. A value of -1 is used to mark unused entries.
+class QInt64Set
+{
+public:
+ inline QInt64Set(int capacity = 64);
+ inline ~QInt64Set() {if (m_array) delete[] m_array;}
+ inline bool isValid() const {return m_array;}
+ void insert(quint64 key);
+ bool contains(quint64 key) const;
+ inline void clear();
+private:
+ bool rehash(int capacity);
+
+ static const quint64 UNUSED;
+
+ quint64 *m_array;
+ int m_capacity;
+ int m_count;
+};
+
+const quint64 QInt64Set::UNUSED = quint64(-1);
+
+inline QInt64Set::QInt64Set(int capacity)
+{
+ m_capacity = primeForCount(capacity);
+ m_array = new quint64[m_capacity];
+ if (m_array)
+ clear();
+ else
+ m_capacity = 0;
+}
+
+bool QInt64Set::rehash(int capacity)
+{
+ quint64 *oldArray = m_array;
+ int oldCapacity = m_capacity;
+
+ m_capacity = capacity;
+ m_array = new quint64[m_capacity];
+ if (m_array) {
+ clear();
+ if (oldArray) {
+ for (int i = 0; i < oldCapacity; ++i) {
+ if (oldArray[i] != UNUSED)
+ insert(oldArray[i]);
+ }
+ delete[] oldArray;
+ }
+ return true;
+ } else {
+ m_capacity = oldCapacity;
+ m_array = oldArray;
+ return false;
+ }
+}
+
+void QInt64Set::insert(quint64 key)
+{
+ if (m_count > 3 * m_capacity / 4)
+ rehash(primeForCount(2 * m_capacity));
+ Q_ASSERT_X(m_array, "QInt64Hash<T>::insert", "Hash set not allocated.");
+ int index = int(key % m_capacity);
+ for (int i = 0; i < m_capacity; ++i) {
+ index += i;
+ if (index >= m_capacity)
+ index -= m_capacity;
+ if (m_array[index] == key)
+ return;
+ if (m_array[index] == UNUSED) {
+ ++m_count;
+ m_array[index] = key;
+ return;
+ }
+ }
+ Q_ASSERT_X(0, "QInt64Hash<T>::insert", "Hash set full.");
+}
+
+bool QInt64Set::contains(quint64 key) const
+{
+ Q_ASSERT_X(m_array, "QInt64Hash<T>::contains", "Hash set not allocated.");
+ int index = int(key % m_capacity);
+ for (int i = 0; i < m_capacity; ++i) {
+ index += i;
+ if (index >= m_capacity)
+ index -= m_capacity;
+ if (m_array[index] == key)
+ return true;
+ if (m_array[index] == UNUSED)
+ return false;
+ }
+ return false;
+}
+
+inline void QInt64Set::clear()
+{
+ Q_ASSERT_X(m_array, "QInt64Hash<T>::clear", "Hash set not allocated.");
+ for (int i = 0; i < m_capacity; ++i)
+ m_array[i] = UNUSED;
+ m_count = 0;
+}
+
+//============================================================================//
+// QRingBuffer //
+//============================================================================//
+
+// T must be POD.
+template <class T>
+class QRingBuffer
+{
+public:
+ inline QRingBuffer() : m_array(0), m_head(0), m_size(0), m_capacity(0) { }
+ inline ~QRingBuffer() {if (m_array) delete[] m_array;}
+ bool reallocate(int capacity);
+ inline const T &head() const {Q_ASSERT(m_size > 0); return m_array[m_head];}
+ inline const T &dequeue();
+ inline void enqueue(const T &x);
+ inline bool isEmpty() const {return m_size == 0;}
+private:
+ T *m_array;
+ int m_head;
+ int m_size;
+ int m_capacity;
+};
+
+template <class T>
+bool QRingBuffer<T>::reallocate(int capacity)
+{
+ T *oldArray = m_array;
+ m_array = new T[capacity];
+ if (m_array) {
+ if (oldArray) {
+ if (m_head + m_size > m_capacity) {
+ memcpy(m_array, oldArray + m_head, (m_capacity - m_head) * sizeof(T));
+ memcpy(m_array + (m_capacity - m_head), oldArray, (m_head + m_size - m_capacity) * sizeof(T));
+ } else {
+ memcpy(m_array, oldArray + m_head, m_size * sizeof(T));
+ }
+ delete[] oldArray;
+ }
+ m_capacity = capacity;
+ m_head = 0;
+ return true;
+ } else {
+ m_array = oldArray;
+ return false;
+ }
+}
+
+template <class T>
+inline const T &QRingBuffer<T>::dequeue()
+{
+ Q_ASSERT(m_size > 0);
+ Q_ASSERT(m_array);
+ Q_ASSERT(m_capacity >= m_size);
+ int index = m_head;
+ if (++m_head >= m_capacity)
+ m_head -= m_capacity;
+ --m_size;
+ return m_array[index];
+}
+
+template <class T>
+inline void QRingBuffer<T>::enqueue(const T &x)
+{
+ if (m_size == m_capacity)
+ reallocate(qMax(2 * m_capacity, 64));
+ int index = m_head + m_size;
+ if (index >= m_capacity)
+ index -= m_capacity;
+ m_array[index] = x;
+ ++m_size;
+}
+
+//============================================================================//
+// QTriangulator //
+//============================================================================//
+
+class QTriangulator
+{
+public:
+ typedef QVarLengthArray<int, 6> ShortArray;
+
+ //================================//
+ // QTriangulator::ComplexToSimple //
+ //================================//
+ friend class ComplexToSimple;
+ class ComplexToSimple
+ {
+ public:
+ inline ComplexToSimple(QTriangulator *parent) : m_parent(parent) { }
+ void decompose();
+ private:
+ struct Edge
+ {
+ inline int &upper() {return pointingUp ? to : from;}
+ inline int &lower() {return pointingUp ? from : to;}
+ inline int upper() const {return pointingUp ? to : from;}
+ inline int lower() const {return pointingUp ? from : to;}
+
+ QRBTree<int>::Node *node;
+ int from, to; // vertex
+ int next, previous; // edge
+ int winding;
+ bool mayIntersect;
+ bool pointingUp, originallyPointingUp;
+ };
+
+ friend class CompareEdges;
+ class CompareEdges
+ {
+ public:
+ inline CompareEdges(ComplexToSimple *parent) : m_parent(parent) { }
+ bool operator () (int i, int j) const;
+ private:
+ ComplexToSimple *m_parent;
+ };
+
+ struct Intersection
+ {
+ bool operator < (const Intersection &other) const {return other.intersectionPoint < intersectionPoint;}
+
+ QIntersectionPoint intersectionPoint;
+ int vertex;
+ int leftEdge;
+ int rightEdge;
+ };
+
+ struct Split
+ {
+ int vertex;
+ int edge;
+ bool accurate;
+ };
+
+ struct Event
+ {
+ enum Type {Upper, Lower};
+ inline bool operator < (const Event &other) const;
+
+ QPodPoint point;
+ Type type;
+ int edge;
+ };
+
+#ifdef Q_TRIANGULATOR_DEBUG
+ friend class DebugDialog;
+ friend class QTriangulator;
+ class DebugDialog : public QDialog
+ {
+ public:
+ DebugDialog(ComplexToSimple *parent, int currentVertex);
+ protected:
+ void paintEvent(QPaintEvent *);
+ void wheelEvent(QWheelEvent *);
+ void mouseMoveEvent(QMouseEvent *);
+ void mousePressEvent(QMouseEvent *);
+ private:
+ ComplexToSimple *m_parent;
+ QRectF m_window;
+ QPoint m_lastMousePos;
+ int m_vertex;
+ };
+#endif
+
+ void initEdges();
+ bool calculateIntersection(int left, int right);
+ bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
+ QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex) const;
+ QRBTree<int>::Node *searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const;
+ QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> bounds(const QPodPoint &point) const;
+ QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> outerBounds(const QPodPoint &point) const;
+ void splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint);
+ void reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost);
+ void sortEdgeList(const QPodPoint eventPoint);
+ void fillPriorityQueue();
+ void calculateIntersections();
+ int splitEdge(int splitIndex);
+ bool splitEdgesAtIntersections();
+ void insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i);
+ void removeUnwantedEdgesAndConnect();
+ void removeUnusedPoints();
+
+ QTriangulator *m_parent;
+ QDataBuffer<Edge> m_edges;
+ QRBTree<int> m_edgeList;
+ QDataBuffer<Event> m_events;
+ QDataBuffer<Split> m_splits;
+ QMaxHeap<Intersection> m_topIntersection;
+ QInt64Set m_processedEdgePairs;
+ int m_initialPointCount;
+ };
+#ifdef Q_TRIANGULATOR_DEBUG
+ friend class ComplexToSimple::DebugDialog;
+#endif
+
+ //=================================//
+ // QTriangulator::SimpleToMonotone //
+ //=================================//
+ friend class SimpleToMonotone;
+ class SimpleToMonotone
+ {
+ public:
+ inline SimpleToMonotone(QTriangulator *parent) : m_parent(parent) { }
+ void decompose();
+ private:
+ enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};
+
+ struct Edge
+ {
+ QRBTree<int>::Node *node;
+ int helper, twin, next, previous;
+ quint32 from, to;
+ VertexType type;
+ bool pointingUp;
+ int upper() const {return (pointingUp ? to : from);}
+ int lower() const {return (pointingUp ? from : to);}
+ };
+
+ friend class CompareVertices;
+ class CompareVertices
+ {
+ public:
+ CompareVertices(SimpleToMonotone *parent) : m_parent(parent) { }
+ bool operator () (int i, int j) const;
+ private:
+ SimpleToMonotone *m_parent;
+ };
+
+ void setupDataStructures();
+ void removeZeroLengthEdges();
+ void fillPriorityQueue();
+ bool edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const;
+ // Returns the rightmost edge not to the right of the given edge.
+ QRBTree<int>::Node *searchEdgeLeftOfEdge(int edgeIndex) const;
+ // Returns the rightmost edge left of the given point.
+ QRBTree<int>::Node *searchEdgeLeftOfPoint(int pointIndex) const;
+ void classifyVertex(int i);
+ void classifyVertices();
+ bool pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3);
+ bool pointIsInSector(int vertex, int sector);
+ int findSector(int edge, int vertex);
+ void createDiagonal(int lower, int upper);
+ void monotoneDecomposition();
+
+ QTriangulator *m_parent;
+ QRBTree<int> m_edgeList;
+ QDataBuffer<Edge> m_edges;
+ QDataBuffer<int> m_upperVertex;
+ bool m_clockwiseOrder;
+ };
+
+ //====================================//
+ // QTriangulator::MonotoneToTriangles //
+ //====================================//
+ friend class MonotoneToTriangles;
+ class MonotoneToTriangles
+ {
+ public:
+ inline MonotoneToTriangles(QTriangulator *parent) : m_parent(parent) { }
+ void decompose();
+ private:
+ inline quint32 indices(int index) const {return m_parent->m_indices.at(index + m_first);}
+ inline int next(int index) const {return (index + 1) % m_length;}
+ inline int previous(int index) const {return (index + m_length - 1) % m_length;}
+ inline bool less(int i, int j) const {return m_parent->m_vertices.at(indices(i)) < m_parent->m_vertices.at(indices(j));}
+ inline bool leftOfEdge(int i, int j, int k) const
+ {
+ return qPointIsLeftOfLine(m_parent->m_vertices.at(indices(i)),
+ m_parent->m_vertices.at(indices(j)), m_parent->m_vertices.at(indices(k)));
+ }
+
+ QTriangulator *m_parent;
+ int m_first;
+ int m_length;
+ };
+
+ inline QTriangulator() { }
+
+ // Call this only once.
+ void initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix);
+ // Call this only once.
+ void initialize(const QVectorPath &path, const QTransform &matrix, qreal lod);
+ // Call this only once.
+ void initialize(const QPainterPath &path, const QTransform &matrix, qreal lod);
+ // Call either triangulate() or polyline() only once.
+ QTriangleSet triangulate();
+ QPolylineSet polyline();
+private:
+ QDataBuffer<QPodPoint> m_vertices;
+ QVector<quint32> m_indices;
+ uint m_hint;
+};
+
+//============================================================================//
+// QTriangulator //
+//============================================================================//
+
+QTriangleSet QTriangulator::triangulate()
+{
+ for (int i = 0; i < m_vertices.size(); ++i) {
+ Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21));
+ Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21));
+ }
+
+ if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill)))
+ m_hint |= QVectorPath::OddEvenFill;
+
+ if (m_hint & QVectorPath::NonConvexShapeMask) {
+ ComplexToSimple c2s(this);
+ c2s.decompose();
+ SimpleToMonotone s2m(this);
+ s2m.decompose();
+ }
+ MonotoneToTriangles m2t(this);
+ m2t.decompose();
+
+ QTriangleSet result;
+ result.indices = m_indices;
+ result.vertices.resize(2 * m_vertices.size());
+ for (int i = 0; i < m_vertices.size(); ++i) {
+ result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
+ result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
+ }
+ return result;
+}
+
+QPolylineSet QTriangulator::polyline()
+{
+ QPolylineSet result;
+ result.indices = m_indices;
+ result.vertices.resize(2 * m_vertices.size());
+ for (int i = 0; i < m_vertices.size(); ++i) {
+ result.vertices[2 * i + 0] = qreal(m_vertices.at(i).x) / Q_FIXED_POINT_SCALE;
+ result.vertices[2 * i + 1] = qreal(m_vertices.at(i).y) / Q_FIXED_POINT_SCALE;
+ }
+ return result;
+}
+
+void QTriangulator::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix)
+{
+ m_hint = hint;
+ m_vertices.resize(count);
+ m_indices.resize(count + 1);
+ for (int i = 0; i < count; ++i) {
+ qreal x, y;
+ matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y);
+ m_vertices.at(i).x = qRound(x * Q_FIXED_POINT_SCALE);
+ m_vertices.at(i).y = qRound(y * Q_FIXED_POINT_SCALE);
+ m_indices[i] = i;
+ }
+ m_indices[count] = Q_TRIANGULATE_END_OF_POLYGON;
+}
+
+void QTriangulator::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod)
+{
+ m_hint = path.hints();
+ // Curved paths will be converted to complex polygons.
+ m_hint &= ~QVectorPath::CurvedShapeMask;
+
+ const qreal *p = path.points();
+ const QPainterPath::ElementType *e = path.elements();
+ if (e) {
+ for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) {
+ switch (*e) {
+ case QPainterPath::MoveToElement:
+ if (!m_indices.isEmpty())
+ m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+ // Fall through.
+ case QPainterPath::LineToElement:
+ m_indices.push_back(quint32(m_vertices.size()));
+ m_vertices.resize(m_vertices.size() + 1);
+ qreal x, y;
+ matrix.map(p[0], p[1], &x, &y);
+ m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
+ m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
+ break;
+ case QPainterPath::CurveToElement:
+ {
+ qreal pts[8];
+ for (int i = 0; i < 4; ++i)
+ matrix.map(p[2 * i - 2], p[2 * i - 1], &pts[2 * i + 0], &pts[2 * i + 1]);
+ for (int i = 0; i < 8; ++i)
+ pts[i] *= lod;
+ QBezier bezier = QBezier::fromPoints(QPointF(pts[0], pts[1]), QPointF(pts[2], pts[3]), QPointF(pts[4], pts[5]), QPointF(pts[6], pts[7]));
+ QPolygonF poly = bezier.toPolygon();
+ // Skip first point, it already exists in 'm_vertices'.
+ for (int j = 1; j < poly.size(); ++j) {
+ m_indices.push_back(quint32(m_vertices.size()));
+ m_vertices.resize(m_vertices.size() + 1);
+ m_vertices.last().x = qRound(poly.at(j).x() * Q_FIXED_POINT_SCALE / lod);
+ m_vertices.last().y = qRound(poly.at(j).y() * Q_FIXED_POINT_SCALE / lod);
+ }
+ }
+ i += 2;
+ e += 2;
+ p += 4;
+ break;
+ default:
+ Q_ASSERT_X(0, "QTriangulator::triangulate", "Unexpected element type.");
+ break;
+ }
+ }
+ } else {
+ for (int i = 0; i < path.elementCount(); ++i, p += 2) {
+ m_indices.push_back(quint32(m_vertices.size()));
+ m_vertices.resize(m_vertices.size() + 1);
+ qreal x, y;
+ matrix.map(p[0], p[1], &x, &y);
+ m_vertices.last().x = qRound(x * Q_FIXED_POINT_SCALE);
+ m_vertices.last().y = qRound(y * Q_FIXED_POINT_SCALE);
+ }
+ }
+ m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+}
+
+void QTriangulator::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod)
+{
+ initialize(qtVectorPathForPath(path), matrix, lod);
+}
+
+//============================================================================//
+// QTriangulator::ComplexToSimple //
+//============================================================================//
+
+void QTriangulator::ComplexToSimple::decompose()
+{
+ m_initialPointCount = m_parent->m_vertices.size();
+ initEdges();
+ do {
+ calculateIntersections();
+ } while (splitEdgesAtIntersections());
+
+ removeUnwantedEdgesAndConnect();
+ removeUnusedPoints();
+
+ m_parent->m_indices.clear();
+ QBitArray processed(m_edges.size(), false);
+ for (int first = 0; first < m_edges.size(); ++first) {
+ // If already processed, or if unused path, skip.
+ if (processed.at(first) || m_edges.at(first).next == -1)
+ continue;
+
+ int i = first;
+ do {
+ Q_ASSERT(!processed.at(i));
+ Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
+ m_parent->m_indices.push_back(m_edges.at(i).from);
+ processed.setBit(i);
+ i = m_edges.at(i).next; // CCW order
+ } while (i != first);
+ m_parent->m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+ }
+}
+
+void QTriangulator::ComplexToSimple::initEdges()
+{
+ // Initialize edge structure.
+ // 'next' and 'previous' are not being initialized at this point.
+ int first = 0;
+ for (int i = 0; i < m_parent->m_indices.size(); ++i) {
+ if (m_parent->m_indices.at(i) == Q_TRIANGULATE_END_OF_POLYGON) {
+ if (m_edges.size() != first)
+ m_edges.last().to = m_edges.at(first).from;
+ first = m_edges.size();
+ } else {
+ Q_ASSERT(i + 1 < m_parent->m_indices.size());
+ // {node, from, to, next, previous, winding, mayIntersect, pointingUp, originallyPointingUp}
+ Edge edge = {0, m_parent->m_indices.at(i), m_parent->m_indices.at(i + 1), -1, -1, 0, true, false, false};
+ m_edges.add(edge);
+ }
+ }
+ if (first != m_edges.size())
+ m_edges.last().to = m_edges.at(first).from;
+ for (int i = 0; i < m_edges.size(); ++i) {
+ m_edges.at(i).originallyPointingUp = 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);
+ }
+}
+
+// Return true if new intersection was found
+bool QTriangulator::ComplexToSimple::calculateIntersection(int left, int right)
+{
+ const Edge &e1 = m_edges.at(left);
+ const Edge &e2 = m_edges.at(right);
+
+ const QPodPoint &u1 = m_parent->m_vertices.at(e1.from);
+ const QPodPoint &u2 = m_parent->m_vertices.at(e1.to);
+ const QPodPoint &v1 = m_parent->m_vertices.at(e2.from);
+ const QPodPoint &v2 = m_parent->m_vertices.at(e2.to);
+ if (qMax(u1.x, u2.x) <= qMin(v1.x, v2.x))
+ return false;
+
+ quint64 key = (left > right ? (quint64(right) << 32) | quint64(left) : (quint64(left) << 32) | quint64(right));
+ if (m_processedEdgePairs.contains(key))
+ return false;
+ m_processedEdgePairs.insert(key);
+
+ Intersection intersection;
+ intersection.leftEdge = left;
+ intersection.rightEdge = right;
+ intersection.intersectionPoint = qIntersectionPoint(u1, u2, v1, v2);
+
+ if (!intersection.intersectionPoint.isValid())
+ return false;
+
+ Q_ASSERT(intersection.intersectionPoint.isOnLine(u1, u2));
+ Q_ASSERT(intersection.intersectionPoint.isOnLine(v1, v2));
+
+ intersection.vertex = m_parent->m_vertices.size();
+ m_topIntersection.push(intersection);
+ m_parent->m_vertices.add(intersection.intersectionPoint.round());
+ return true;
+}
+
+bool QTriangulator::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
+{
+ const Edge &leftEdge = m_edges.at(leftEdgeIndex);
+ const Edge &rightEdge = m_edges.at(rightEdgeIndex);
+ const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
+ const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
+ const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper());
+ if (upper.x < qMin(l.x, u.x))
+ return true;
+ if (upper.x > qMax(l.x, u.x))
+ return false;
+ qint64 d = qPointDistanceFromLine(upper, l, u);
+ // d < 0: left, d > 0: right, d == 0: on top
+ if (d == 0)
+ d = qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
+ return d < 0;
+}
+
+QRBTree<int>::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const
+{
+ QRBTree<int>::Node *current = m_edgeList.root;
+ QRBTree<int>::Node *result = 0;
+ while (current) {
+ if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
+ current = current->left;
+ } else {
+ result = current;
+ current = current->right;
+ }
+ }
+ return result;
+}
+
+QRBTree<int>::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree<int>::Node *after) const
+{
+ if (!m_edgeList.root)
+ return after;
+ QRBTree<int>::Node *result = after;
+ QRBTree<int>::Node *current = (after ? m_edgeList.next(after) : m_edgeList.front(m_edgeList.root));
+ while (current) {
+ if (edgeIsLeftOfEdge(edgeIndex, current->data))
+ return result;
+ result = current;
+ current = m_edgeList.next(current);
+ }
+ return result;
+}
+
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator::ComplexToSimple::bounds(const QPodPoint &point) const
+{
+ QRBTree<int>::Node *current = m_edgeList.root;
+ QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
+ while (current) {
+ const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+ const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+ qint64 d = qPointDistanceFromLine(point, v1, v2);
+ if (d == 0) {
+ result.first = result.second = current;
+ break;
+ }
+ current = (d < 0 ? current->left : current->right);
+ }
+ if (current == 0)
+ return result;
+
+ current = result.first->left;
+ while (current) {
+ const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+ const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+ qint64 d = qPointDistanceFromLine(point, v1, v2);
+ Q_ASSERT(d >= 0);
+ if (d == 0) {
+ result.first = current;
+ current = current->left;
+ } else {
+ current = current->right;
+ }
+ }
+
+ current = result.second->right;
+ while (current) {
+ const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+ const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+ qint64 d = qPointDistanceFromLine(point, v1, v2);
+ Q_ASSERT(d <= 0);
+ if (d == 0) {
+ result.second = current;
+ current = current->right;
+ } else {
+ current = current->left;
+ }
+ }
+
+ return result;
+}
+
+QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator::ComplexToSimple::outerBounds(const QPodPoint &point) const
+{
+ QRBTree<int>::Node *current = m_edgeList.root;
+ QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> result(0, 0);
+
+ while (current) {
+ const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+ const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+ qint64 d = qPointDistanceFromLine(point, v1, v2);
+ if (d == 0)
+ break;
+ if (d < 0) {
+ result.second = current;
+ current = current->left;
+ } else {
+ result.first = current;
+ current = current->right;
+ }
+ }
+
+ if (!current)
+ return result;
+
+ QRBTree<int>::Node *mid = current;
+
+ current = mid->left;
+ while (current) {
+ const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+ const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+ qint64 d = qPointDistanceFromLine(point, v1, v2);
+ Q_ASSERT(d >= 0);
+ if (d == 0) {
+ current = current->left;
+ } else {
+ result.first = current;
+ current = current->right;
+ }
+ }
+
+ current = mid->right;
+ while (current) {
+ const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+ const QPodPoint &v2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+ qint64 d = qPointDistanceFromLine(point, v1, v2);
+ Q_ASSERT(d <= 0);
+ if (d == 0) {
+ current = current->right;
+ } else {
+ result.second = current;
+ current = current->left;
+ }
+ }
+
+ return result;
+}
+
+void QTriangulator::ComplexToSimple::splitEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint)
+{
+ Q_ASSERT(leftmost && rightmost);
+
+ // Split.
+ for (;;) {
+ const QPodPoint &u = m_parent->m_vertices.at(m_edges.at(leftmost->data).from);
+ const QPodPoint &v = m_parent->m_vertices.at(m_edges.at(leftmost->data).to);
+ Q_ASSERT(intersectionPoint.isOnLine(u, v));
+ const Split split = {vertex, leftmost->data, intersectionPoint.isAccurate()};
+ if (intersectionPoint.xOffset.numerator != 0 || intersectionPoint.yOffset.numerator != 0 || (intersectionPoint.upperLeft != u && intersectionPoint.upperLeft != v))
+ m_splits.add(split);
+ if (leftmost == rightmost)
+ break;
+ leftmost = m_edgeList.next(leftmost);
+ }
+}
+
+
+void QTriangulator::ComplexToSimple::reorderEdgeListRange(QRBTree<int>::Node *leftmost, QRBTree<int>::Node *rightmost)
+{
+ Q_ASSERT(leftmost && rightmost);
+
+ QRBTree<int>::Node *storeLeftmost = leftmost;
+ QRBTree<int>::Node *storeRightmost = rightmost;
+
+ // Reorder.
+ while (leftmost != rightmost) {
+ Edge &left = m_edges.at(leftmost->data);
+ Edge &right = m_edges.at(rightmost->data);
+ qSwap(left.node, right.node);
+ qSwap(leftmost->data, rightmost->data);
+ leftmost = m_edgeList.next(leftmost);
+ if (leftmost == rightmost)
+ break;
+ rightmost = m_edgeList.previous(rightmost);
+ }
+
+ rightmost = m_edgeList.next(storeRightmost);
+ leftmost = m_edgeList.previous(storeLeftmost);
+ if (leftmost)
+ calculateIntersection(leftmost->data, storeLeftmost->data);
+ if (rightmost)
+ calculateIntersection(storeRightmost->data, rightmost->data);
+}
+
+void QTriangulator::ComplexToSimple::sortEdgeList(const QPodPoint eventPoint)
+{
+ QIntersectionPoint eventPoint2 = qIntersectionPoint(eventPoint);
+ while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint < eventPoint2) {
+ Intersection intersection = m_topIntersection.pop();
+
+ QIntersectionPoint currentIntersectionPoint = intersection.intersectionPoint;
+ int currentVertex = intersection.vertex;
+
+ QRBTree<int>::Node *leftmost = m_edges.at(intersection.leftEdge).node;
+ QRBTree<int>::Node *rightmost = m_edges.at(intersection.rightEdge).node;
+
+ for (;;) {
+ QRBTree<int>::Node *previous = m_edgeList.previous(leftmost);
+ if (!previous)
+ break;
+ const Edge &edge = m_edges.at(previous->data);
+ const QPodPoint &u = m_parent->m_vertices.at(edge.from);
+ const QPodPoint &v = m_parent->m_vertices.at(edge.to);
+ if (!currentIntersectionPoint.isOnLine(u, v)) {
+ Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
+ break;
+ }
+ leftmost = previous;
+ }
+
+ for (;;) {
+ QRBTree<int>::Node *next = m_edgeList.next(rightmost);
+ if (!next)
+ break;
+ const Edge &edge = m_edges.at(next->data);
+ const QPodPoint &u = m_parent->m_vertices.at(edge.from);
+ const QPodPoint &v = m_parent->m_vertices.at(edge.to);
+ if (!currentIntersectionPoint.isOnLine(u, v)) {
+ Q_ASSERT(!currentIntersectionPoint.isAccurate() || qCross(currentIntersectionPoint.upperLeft - u, v - u) != 0);
+ break;
+ }
+ rightmost = next;
+ }
+
+ Q_ASSERT(leftmost && rightmost);
+ splitEdgeListRange(leftmost, rightmost, currentVertex, currentIntersectionPoint);
+ reorderEdgeListRange(leftmost, rightmost);
+
+ while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= currentIntersectionPoint)
+ m_topIntersection.pop();
+
+#ifdef Q_TRIANGULATOR_DEBUG
+ DebugDialog dialog(this, intersection.vertex);
+ dialog.exec();
+#endif
+
+ }
+}
+
+void QTriangulator::ComplexToSimple::fillPriorityQueue()
+{
+ m_events.reset();
+ m_events.reserve(m_edges.size() * 2);
+ for (int i = 0; i < m_edges.size(); ++i) {
+ Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
+ Q_ASSERT(m_edges.at(i).node == 0);
+ Q_ASSERT(m_edges.at(i).pointingUp == m_edges.at(i).originallyPointingUp);
+ Q_ASSERT(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)));
+ // Ignore zero-length edges.
+ if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) {
+ QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper());
+ QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower());
+ Event upperEvent = {{upper.x, upper.y}, Event::Upper, i};
+ Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i};
+ m_events.add(upperEvent);
+ m_events.add(lowerEvent);
+ }
+ }
+ //qSort(m_events.data(), m_events.data() + m_events.size());
+ sort(m_events.data(), m_events.size());
+}
+
+void QTriangulator::ComplexToSimple::calculateIntersections()
+{
+ fillPriorityQueue();
+
+ Q_ASSERT(m_topIntersection.empty());
+ Q_ASSERT(m_edgeList.root == 0);
+
+ // Find all intersection points.
+ while (!m_events.isEmpty()) {
+ Event event = m_events.last();
+ sortEdgeList(event.point);
+
+ // Find all edges in the edge list that contain the current vertex and mark them to be split later.
+ QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> range = bounds(event.point);
+ QRBTree<int>::Node *leftNode = range.first ? m_edgeList.previous(range.first) : 0;
+ int vertex = (event.type == Event::Upper ? m_edges.at(event.edge).upper() : m_edges.at(event.edge).lower());
+ QIntersectionPoint eventPoint = qIntersectionPoint(event.point);
+
+ if (range.first != 0) {
+ splitEdgeListRange(range.first, range.second, vertex, eventPoint);
+ reorderEdgeListRange(range.first, range.second);
+ }
+
+ // Handle the edges with start or end point in the current vertex.
+ while (!m_events.isEmpty() && m_events.last().point == event.point) {
+ event = m_events.last();
+ m_events.pop_back();
+ int i = event.edge;
+
+ if (m_edges.at(i).node) {
+ // Remove edge from edge list.
+ Q_ASSERT(event.type == Event::Lower);
+ QRBTree<int>::Node *left = m_edgeList.previous(m_edges.at(i).node);
+ QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
+ m_edgeList.deleteNode(m_edges.at(i).node);
+ if (!left || !right)
+ continue;
+ calculateIntersection(left->data, right->data);
+ } else {
+ // Insert edge into edge list.
+ Q_ASSERT(event.type == Event::Upper);
+ QRBTree<int>::Node *left = searchEdgeLeftOf(i, leftNode);
+ m_edgeList.attachAfter(left, m_edges.at(i).node = m_edgeList.newNode());
+ m_edges.at(i).node->data = i;
+ QRBTree<int>::Node *right = m_edgeList.next(m_edges.at(i).node);
+ if (left)
+ calculateIntersection(left->data, i);
+ if (right)
+ calculateIntersection(i, right->data);
+ }
+ }
+ while (!m_topIntersection.isEmpty() && m_topIntersection.top().intersectionPoint <= eventPoint)
+ m_topIntersection.pop();
+#ifdef Q_TRIANGULATOR_DEBUG
+ DebugDialog dialog(this, vertex);
+ dialog.exec();
+#endif
+ }
+ m_processedEdgePairs.clear();
+}
+
+// Split an edge into two pieces at the given point.
+// The upper piece is pushed to the end of the 'm_edges' vector.
+// The lower piece replaces the old edge.
+// Return the edge whose 'from' is 'pointIndex'.
+int QTriangulator::ComplexToSimple::splitEdge(int splitIndex)
+{
+ const Split &split = m_splits.at(splitIndex);
+ Edge &lowerEdge = m_edges.at(split.edge);
+ Q_ASSERT(lowerEdge.node == 0);
+ Q_ASSERT(lowerEdge.previous == -1 && lowerEdge.next == -1);
+
+ if (lowerEdge.from == split.vertex)
+ return split.edge;
+ if (lowerEdge.to == split.vertex)
+ return lowerEdge.next;
+
+ // Check that angle >= 90 degrees.
+ //Q_ASSERT(qDot(m_points.at(m_edges.at(edgeIndex).from) - m_points.at(pointIndex),
+ // m_points.at(m_edges.at(edgeIndex).to) - m_points.at(pointIndex)) <= 0);
+
+ Edge upperEdge = lowerEdge;
+ upperEdge.mayIntersect |= !split.accurate; // The edge may have been split before at an inaccurate split point.
+ lowerEdge.mayIntersect = !split.accurate;
+ if (lowerEdge.pointingUp) {
+ lowerEdge.to = upperEdge.from = split.vertex;
+ m_edges.add(upperEdge);
+ return m_edges.size() - 1;
+ } else {
+ lowerEdge.from = upperEdge.to = split.vertex;
+ m_edges.add(upperEdge);
+ return split.edge;
+ }
+}
+
+bool QTriangulator::ComplexToSimple::splitEdgesAtIntersections()
+{
+ for (int i = 0; i < m_edges.size(); ++i)
+ m_edges.at(i).mayIntersect = false;
+ bool checkForNewIntersections = false;
+ for (int i = 0; i < m_splits.size(); ++i) {
+ splitEdge(i);
+ checkForNewIntersections |= !m_splits.at(i).accurate;
+ }
+ for (int i = 0; i < m_edges.size(); ++i) {
+ m_edges.at(i).originallyPointingUp = 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);
+ }
+ m_splits.reset();
+ return checkForNewIntersections;
+}
+
+void QTriangulator::ComplexToSimple::insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i)
+{
+ // Edges with zero length should not reach this part.
+ Q_ASSERT(m_parent->m_vertices.at(m_edges.at(i).from) != m_parent->m_vertices.at(m_edges.at(i).to));
+
+ // Skip edges with unwanted winding number.
+ int windingNumber = m_edges.at(i).winding;
+ if (m_edges.at(i).originallyPointingUp)
+ ++windingNumber;
+
+ // Make sure exactly one fill rule is specified.
+ Q_ASSERT(((m_parent->m_hint & QVectorPath::WindingFill) != 0) != ((m_parent->m_hint & QVectorPath::OddEvenFill) != 0));
+
+ if ((m_parent->m_hint & QVectorPath::WindingFill) && windingNumber != 0 && windingNumber != 1)
+ return;
+
+ // Skip cancelling edges.
+ if (!orderedEdges.isEmpty()) {
+ int j = orderedEdges[orderedEdges.size() - 1];
+ // If the last edge is already connected in one end, it should not be cancelled.
+ if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1
+ && (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to))
+ && (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) {
+ orderedEdges.removeLast();
+ return;
+ }
+ }
+ orderedEdges.append(i);
+}
+
+void QTriangulator::ComplexToSimple::removeUnwantedEdgesAndConnect()
+{
+ Q_ASSERT(m_edgeList.root == 0);
+ // Initialize priority queue.
+ fillPriorityQueue();
+
+ ShortArray orderedEdges;
+
+ while (!m_events.isEmpty()) {
+ Event event = m_events.last();
+ int edgeIndex = event.edge;
+
+ // Check that all the edges in the list crosses the current scanline
+ //if (m_edgeList.root) {
+ // for (QRBTree<int>::Node *node = m_edgeList.front(m_edgeList.root); node; node = m_edgeList.next(node)) {
+ // Q_ASSERT(event.point <= m_points.at(m_edges.at(node->data).lower()));
+ // }
+ //}
+
+ orderedEdges.clear();
+ QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> b = outerBounds(event.point);
+ if (m_edgeList.root) {
+ QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
+ // Process edges that are going to be removed from the edge list at the current event point.
+ while (current != b.second) {
+ Q_ASSERT(current);
+ Q_ASSERT(m_edges.at(current->data).node == current);
+ Q_ASSERT(qIntersectionPoint(event.point).isOnLine(m_parent->m_vertices.at(m_edges.at(current->data).from), m_parent->m_vertices.at(m_edges.at(current->data).to)));
+ Q_ASSERT(m_parent->m_vertices.at(m_edges.at(current->data).from) == event.point || m_parent->m_vertices.at(m_edges.at(current->data).to) == event.point);
+ insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
+ current = m_edgeList.next(current);
+ }
+ }
+
+ // Remove edges above the event point, insert edges below the event point.
+ do {
+ event = m_events.last();
+ m_events.pop_back();
+ edgeIndex = event.edge;
+
+ // Edges with zero length should not reach this part.
+ Q_ASSERT(m_parent->m_vertices.at(m_edges.at(edgeIndex).from) != m_parent->m_vertices.at(m_edges.at(edgeIndex).to));
+
+ if (m_edges.at(edgeIndex).node) {
+ Q_ASSERT(event.type == Event::Lower);
+ Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).lower()));
+ m_edgeList.deleteNode(m_edges.at(edgeIndex).node);
+ } else {
+ Q_ASSERT(event.type == Event::Upper);
+ Q_ASSERT(event.point == m_parent->m_vertices.at(m_edges.at(event.edge).upper()));
+ QRBTree<int>::Node *left = searchEdgeLeftOf(edgeIndex, b.first);
+ m_edgeList.attachAfter(left, m_edges.at(edgeIndex).node = m_edgeList.newNode());
+ m_edges.at(edgeIndex).node->data = edgeIndex;
+ }
+ } while (!m_events.isEmpty() && m_events.last().point == event.point);
+
+ if (m_edgeList.root) {
+ QRBTree<int>::Node *current = (b.first ? m_edgeList.next(b.first) : m_edgeList.front(m_edgeList.root));
+
+ // Calculate winding number and turn counter-clockwise.
+ int currentWindingNumber = (b.first ? m_edges.at(b.first->data).winding : 0);
+ while (current != b.second) {
+ Q_ASSERT(current);
+ //Q_ASSERT(b.second == 0 || m_edgeList.order(current, b.second) < 0);
+ int i = current->data;
+ Q_ASSERT(m_edges.at(i).node == current);
+
+ // Winding number.
+ int ccwWindingNumber = m_edges.at(i).winding = currentWindingNumber;
+ if (m_edges.at(i).originallyPointingUp) {
+ --m_edges.at(i).winding;
+ } else {
+ ++m_edges.at(i).winding;
+ ++ccwWindingNumber;
+ }
+ currentWindingNumber = m_edges.at(i).winding;
+
+ // Turn counter-clockwise.
+ if ((ccwWindingNumber & 1) == 0) {
+ Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1);
+ qSwap(m_edges.at(i).from, m_edges.at(i).to);
+ m_edges.at(i).pointingUp = !m_edges.at(i).pointingUp;
+ }
+
+ current = m_edgeList.next(current);
+ }
+
+ // Process edges that were inserted into the edge list at the current event point.
+ current = (b.second ? m_edgeList.previous(b.second) : m_edgeList.back(m_edgeList.root));
+ while (current != b.first) {
+ Q_ASSERT(current);
+ Q_ASSERT(m_edges.at(current->data).node == current);
+ insertEdgeIntoVectorIfWanted(orderedEdges, current->data);
+ current = m_edgeList.previous(current);
+ }
+ }
+ if (orderedEdges.isEmpty())
+ continue;
+
+ Q_ASSERT((orderedEdges.size() & 1) == 0);
+
+ // Connect edges.
+ // First make sure the first edge point towards the current point.
+ int i;
+ if (m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).from) == event.point) {
+ i = 1;
+ int copy = orderedEdges[0]; // Make copy in case the append() will cause a reallocation.
+ orderedEdges.append(copy);
+ } else {
+ Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[0]).to) == event.point);
+ i = 0;
+ }
+
+ // Remove references to duplicate points. First find the point with lowest index.
+ int pointIndex = INT_MAX;
+ for (int j = i; j < orderedEdges.size(); j += 2) {
+ Q_ASSERT(j + 1 < orderedEdges.size());
+ Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j]).to) == event.point);
+ Q_ASSERT(m_parent->m_vertices.at(m_edges.at(orderedEdges[j + 1]).from) == event.point);
+ if (m_edges.at(orderedEdges[j]).to < pointIndex)
+ pointIndex = m_edges.at(orderedEdges[j]).to;
+ if (m_edges.at(orderedEdges[j + 1]).from < pointIndex)
+ pointIndex = m_edges.at(orderedEdges[j + 1]).from;
+ }
+
+ for (; i < orderedEdges.size(); i += 2) {
+ // Remove references to duplicate points by making all edges reference one common point.
+ m_edges.at(orderedEdges[i]).to = m_edges.at(orderedEdges[i + 1]).from = pointIndex;
+
+ Q_ASSERT(m_edges.at(orderedEdges[i]).pointingUp || m_edges.at(orderedEdges[i]).previous != -1);
+ Q_ASSERT(!m_edges.at(orderedEdges[i + 1]).pointingUp || m_edges.at(orderedEdges[i + 1]).next != -1);
+
+ m_edges.at(orderedEdges[i]).next = orderedEdges[i + 1];
+ m_edges.at(orderedEdges[i + 1]).previous = orderedEdges[i];
+ }
+ } // end while
+}
+
+void QTriangulator::ComplexToSimple::removeUnusedPoints() {
+ QBitArray used(m_parent->m_vertices.size(), false);
+ for (int i = 0; i < m_edges.size(); ++i) {
+ Q_ASSERT((m_edges.at(i).previous == -1) == (m_edges.at(i).next == -1));
+ if (m_edges.at(i).next != -1)
+ used.setBit(m_edges.at(i).from);
+ }
+ QDataBuffer<quint32> newMapping(m_parent->m_vertices.size());
+ newMapping.resize(m_parent->m_vertices.size());
+ int count = 0;
+ for (int i = 0; i < m_parent->m_vertices.size(); ++i) {
+ if (used.at(i)) {
+ m_parent->m_vertices.at(count) = m_parent->m_vertices.at(i);
+ newMapping.at(i) = count;
+ ++count;
+ }
+ }
+ m_parent->m_vertices.resize(count);
+ for (int i = 0; i < m_edges.size(); ++i) {
+ m_edges.at(i).from = newMapping.at(m_edges.at(i).from);
+ m_edges.at(i).to = newMapping.at(m_edges.at(i).to);
+ }
+}
+
+bool QTriangulator::ComplexToSimple::CompareEdges::operator () (int i, int j) const
+{
+ int cmp = comparePoints(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));
+ if (cmp == 0) {
+ cmp = comparePoints(m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).to),
+ m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).to));
+ }
+ return cmp > 0;
+}
+
+inline bool QTriangulator::ComplexToSimple::Event::operator < (const Event &other) const
+{
+ if (point == other.point)
+ return type < other.type; // 'Lower' has higher priority than 'Upper'.
+ return other.point < point;
+}
+
+//============================================================================//
+// QTriangulator::ComplexToSimple::DebugDialog //
+//============================================================================//
+
+#ifdef Q_TRIANGULATOR_DEBUG
+
+QTriangulator::ComplexToSimple::DebugDialog::DebugDialog(ComplexToSimple *parent, int currentVertex)
+ : m_parent(parent), m_vertex(currentVertex)
+{
+ QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
+ if (vertices.isEmpty())
+ return;
+
+ int minX, maxX, minY, maxY;
+ minX = maxX = vertices.at(0).x;
+ minY = maxY = vertices.at(0).y;
+ for (int i = 1; i < vertices.size(); ++i) {
+ minX = qMin(minX, vertices.at(i).x);
+ maxX = qMax(maxX, vertices.at(i).x);
+ minY = qMin(minY, vertices.at(i).y);
+ maxY = qMax(maxY, vertices.at(i).y);
+ }
+ int w = maxX - minX;
+ int h = maxY - minY;
+ qreal border = qMin(w, h) / 10.0;
+ m_window = QRectF(minX - border, minY - border, (maxX - minX + 2 * border), (maxY - minY + 2 * border));
+}
+
+void QTriangulator::ComplexToSimple::DebugDialog::paintEvent(QPaintEvent *)
+{
+ QPainter p(this);
+ p.setRenderHint(QPainter::Antialiasing, true);
+ p.fillRect(rect(), Qt::black);
+ QDataBuffer<QPodPoint> &vertices = m_parent->m_parent->m_vertices;
+ if (vertices.isEmpty())
+ return;
+
+ qreal halfPointSize = qMin(m_window.width(), m_window.height()) / 300.0;
+ p.setWindow(m_window.toRect());
+
+ p.setPen(Qt::white);
+
+ QDataBuffer<Edge> &edges = m_parent->m_edges;
+ for (int i = 0; i < edges.size(); ++i) {
+ QPodPoint u = vertices.at(edges.at(i).from);
+ QPodPoint v = vertices.at(edges.at(i).to);
+ p.drawLine(u.x, u.y, v.x, v.y);
+ }
+
+ for (int i = 0; i < vertices.size(); ++i) {
+ QPodPoint q = vertices.at(i);
+ p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::red);
+ }
+
+ Qt::GlobalColor colors[6] = {Qt::red, Qt::green, Qt::blue, Qt::cyan, Qt::magenta, Qt::yellow};
+ p.setOpacity(0.5);
+ int count = 0;
+ if (m_parent->m_edgeList.root) {
+ QRBTree<int>::Node *current = m_parent->m_edgeList.front(m_parent->m_edgeList.root);
+ while (current) {
+ p.setPen(colors[count++ % 6]);
+ QPodPoint u = vertices.at(edges.at(current->data).from);
+ QPodPoint v = vertices.at(edges.at(current->data).to);
+ p.drawLine(u.x, u.y, v.x, v.y);
+ current = m_parent->m_edgeList.next(current);
+ }
+ }
+
+ p.setOpacity(1.0);
+ QPodPoint q = vertices.at(m_vertex);
+ p.fillRect(QRectF(q.x - halfPointSize, q.y - halfPointSize, 2 * halfPointSize, 2 * halfPointSize), Qt::green);
+
+ p.setPen(Qt::gray);
+ QDataBuffer<Split> &splits = m_parent->m_splits;
+ for (int i = 0; i < splits.size(); ++i) {
+ QPodPoint q = vertices.at(splits.at(i).vertex);
+ QPodPoint u = vertices.at(edges.at(splits.at(i).edge).from) - q;
+ QPodPoint v = vertices.at(edges.at(splits.at(i).edge).to) - q;
+ qreal uLen = sqrt(qreal(qDot(u, u)));
+ qreal vLen = sqrt(qreal(qDot(v, v)));
+ if (uLen) {
+ u.x *= 2 * halfPointSize / uLen;
+ u.y *= 2 * halfPointSize / uLen;
+ }
+ if (vLen) {
+ v.x *= 2 * halfPointSize / vLen;
+ v.y *= 2 * halfPointSize / vLen;
+ }
+ u += q;
+ v += q;
+ p.drawLine(u.x, u.y, v.x, v.y);
+ }
+}
+
+void QTriangulator::ComplexToSimple::DebugDialog::wheelEvent(QWheelEvent *event)
+{
+ qreal scale = exp(-0.001 * event->delta());
+ QPointF center = m_window.center();
+ QPointF delta = scale * (m_window.bottomRight() - center);
+ m_window = QRectF(center - delta, center + delta);
+ event->accept();
+ update();
+}
+
+void QTriangulator::ComplexToSimple::DebugDialog::mouseMoveEvent(QMouseEvent *event)
+{
+ if (event->buttons() & Qt::LeftButton) {
+ QPointF delta = event->pos() - m_lastMousePos;
+ delta.setX(delta.x() * m_window.width() / width());
+ delta.setY(delta.y() * m_window.height() / height());
+ m_window.translate(-delta.x(), -delta.y());
+ m_lastMousePos = event->pos();
+ event->accept();
+ update();
+ }
+}
+
+void QTriangulator::ComplexToSimple::DebugDialog::mousePressEvent(QMouseEvent *event)
+{
+ if (event->button() == Qt::LeftButton)
+ m_lastMousePos = event->pos();
+ event->accept();
+}
+
+
+#endif
+
+//============================================================================//
+// QTriangulator::SimpleToMonotone //
+//============================================================================//
+
+void QTriangulator::SimpleToMonotone::decompose()
+{
+ setupDataStructures();
+ removeZeroLengthEdges();
+ monotoneDecomposition();
+
+ m_parent->m_indices.clear();
+ QBitArray processed(m_edges.size(), false);
+ for (int first = 0; first < m_edges.size(); ++first) {
+ if (processed.at(first))
+ continue;
+ int i = first;
+ do {
+ Q_ASSERT(!processed.at(i));
+ Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i);
+ m_parent->m_indices.push_back(m_edges.at(i).from);
+ processed.setBit(i);
+ i = m_edges.at(i).next;
+ } while (i != first);
+ if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != Q_TRIANGULATE_END_OF_POLYGON)
+ m_parent->m_indices.push_back(Q_TRIANGULATE_END_OF_POLYGON);
+ }
+}
+
+void QTriangulator::SimpleToMonotone::setupDataStructures()
+{
+ int i = 0;
+ Edge e;
+ e.node = 0;
+ e.twin = -1;
+
+ while (i + 3 <= m_parent->m_indices.size()) {
+ int start = m_edges.size();
+
+ do {
+ e.from = m_parent->m_indices.at(i);
+ e.type = RegularVertex;
+ e.next = m_edges.size() + 1;
+ e.previous = m_edges.size() - 1;
+ m_edges.add(e);
+ ++i;
+ Q_ASSERT(i < m_parent->m_indices.size());
+ } while (m_parent->m_indices.at(i) != Q_TRIANGULATE_END_OF_POLYGON);
+
+ m_edges.last().next = start;
+ m_edges.at(start).previous = m_edges.size() - 1;
+ ++i; // Skip Q_TRIANGULATE_END_OF_POLYGON.
+ }
+
+ for (i = 0; i < m_edges.size(); ++i) {
+ m_edges.at(i).to = m_edges.at(m_edges.at(i).next).from;
+ 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);
+ m_edges.at(i).helper = -1; // Not initialized here.
+ }
+}
+
+void QTriangulator::SimpleToMonotone::removeZeroLengthEdges()
+{
+ for (int i = 0; i < m_edges.size(); ++i) {
+ if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) {
+ m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next;
+ m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous;
+ m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from;
+ m_edges.at(i).next = -1; // Mark as removed.
+ }
+ }
+
+ QDataBuffer<int> newMapping(m_edges.size());
+ newMapping.resize(m_edges.size());
+ int count = 0;
+ for (int i = 0; i < m_edges.size(); ++i) {
+ if (m_edges.at(i).next != -1) {
+ m_edges.at(count) = m_edges.at(i);
+ newMapping.at(i) = count;
+ ++count;
+ }
+ }
+ m_edges.resize(count);
+ for (int i = 0; i < m_edges.size(); ++i) {
+ m_edges.at(i).next = newMapping.at(m_edges.at(i).next);
+ m_edges.at(i).previous = newMapping.at(m_edges.at(i).previous);
+ }
+}
+
+void QTriangulator::SimpleToMonotone::fillPriorityQueue()
+{
+ m_upperVertex.reset();
+ m_upperVertex.reserve(m_edges.size());
+ for (int i = 0; i < m_edges.size(); ++i)
+ m_upperVertex.add(i);
+ CompareVertices cmp(this);
+ //qSort(m_upperVertex.data(), m_upperVertex.data() + m_upperVertex.size(), cmp);
+ sort(m_upperVertex.data(), m_upperVertex.size(), cmp);
+ //for (int i = 1; i < m_upperVertex.size(); ++i) {
+ // Q_ASSERT(!cmp(m_upperVertex.at(i), m_upperVertex.at(i - 1)));
+ //}
+}
+
+bool QTriangulator::SimpleToMonotone::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const
+{
+ const Edge &leftEdge = m_edges.at(leftEdgeIndex);
+ const Edge &rightEdge = m_edges.at(rightEdgeIndex);
+ const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper());
+ const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower());
+ qint64 d = qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.upper()), l, u);
+ // d < 0: left, d > 0: right, d == 0: on top
+ if (d == 0)
+ d = qPointDistanceFromLine(m_parent->m_vertices.at(leftEdge.lower()), l, u);
+ return d < 0;
+}
+
+// Returns the rightmost edge not to the right of the given edge.
+QRBTree<int>::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfEdge(int edgeIndex) const
+{
+ QRBTree<int>::Node *current = m_edgeList.root;
+ QRBTree<int>::Node *result = 0;
+ while (current) {
+ if (edgeIsLeftOfEdge(edgeIndex, current->data)) {
+ current = current->left;
+ } else {
+ result = current;
+ current = current->right;
+ }
+ }
+ return result;
+}
+
+// Returns the rightmost edge left of the given point.
+QRBTree<int>::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfPoint(int pointIndex) const
+{
+ QRBTree<int>::Node *current = m_edgeList.root;
+ QRBTree<int>::Node *result = 0;
+ while (current) {
+ const QPodPoint &p1 = m_parent->m_vertices.at(m_edges.at(current->data).lower());
+ const QPodPoint &p2 = m_parent->m_vertices.at(m_edges.at(current->data).upper());
+ qint64 d = qPointDistanceFromLine(m_parent->m_vertices.at(pointIndex), p1, p2);
+ if (d <= 0) {
+ current = current->left;
+ } else {
+ result = current;
+ current = current->right;
+ }
+ }
+ return result;
+}
+
+void QTriangulator::SimpleToMonotone::classifyVertex(int i)
+{
+ Edge &e2 = m_edges.at(i);
+ const Edge &e1 = m_edges.at(e2.previous);
+
+ bool startOrSplit = (e1.pointingUp && !e2.pointingUp);
+ bool endOrMerge = (!e1.pointingUp && e2.pointingUp);
+
+ const QPodPoint &p1 = m_parent->m_vertices.at(e1.from);
+ const QPodPoint &p2 = m_parent->m_vertices.at(e2.from);
+ const QPodPoint &p3 = m_parent->m_vertices.at(e2.to);
+ qint64 d = qPointDistanceFromLine(p1, p2, p3);
+ Q_ASSERT(d != 0 || (!startOrSplit && !endOrMerge));
+
+ e2.type = RegularVertex;
+
+ if (m_clockwiseOrder) {
+ if (startOrSplit)
+ e2.type = (d < 0 ? SplitVertex : StartVertex);
+ else if (endOrMerge)
+ e2.type = (d < 0 ? MergeVertex : EndVertex);
+ } else {
+ if (startOrSplit)
+ e2.type = (d > 0 ? SplitVertex : StartVertex);
+ else if (endOrMerge)
+ e2.type = (d > 0 ? MergeVertex : EndVertex);
+ }
+}
+
+void QTriangulator::SimpleToMonotone::classifyVertices()
+{
+ for (int i = 0; i < m_edges.size(); ++i)
+ classifyVertex(i);
+}
+
+bool QTriangulator::SimpleToMonotone::pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3)
+{
+ bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1);
+ bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2);
+
+ if (qPointIsLeftOfLine(v1, v2, v3))
+ return leftOfPreviousEdge && leftOfNextEdge;
+ else
+ return leftOfPreviousEdge || leftOfNextEdge;
+}
+
+bool QTriangulator::SimpleToMonotone::pointIsInSector(int vertex, int sector)
+{
+ const QPodPoint &center = m_parent->m_vertices.at(m_edges.at(sector).from);
+ // Handle degenerate edges.
+ while (m_parent->m_vertices.at(m_edges.at(vertex).from) == center)
+ vertex = m_edges.at(vertex).next;
+ int next = m_edges.at(sector).next;
+ while (m_parent->m_vertices.at(m_edges.at(next).from) == center)
+ next = m_edges.at(next).next;
+ int previous = m_edges.at(sector).previous;
+ while (m_parent->m_vertices.at(m_edges.at(previous).from) == center)
+ previous = m_edges.at(previous).previous;
+
+ const QPodPoint &p = m_parent->m_vertices.at(m_edges.at(vertex).from);
+ const QPodPoint &v1 = m_parent->m_vertices.at(m_edges.at(previous).from);
+ const QPodPoint &v3 = m_parent->m_vertices.at(m_edges.at(next).from);
+ if (m_clockwiseOrder)
+ return pointIsInSector(p, v3, center, v1);
+ else
+ return pointIsInSector(p, v1, center, v3);
+}
+
+int QTriangulator::SimpleToMonotone::findSector(int edge, int vertex)
+{
+ while (!pointIsInSector(vertex, edge)) {
+ edge = m_edges.at(m_edges.at(edge).previous).twin;
+ Q_ASSERT(edge != -1);
+ }
+ return edge;
+}
+
+void QTriangulator::SimpleToMonotone::createDiagonal(int lower, int upper)
+{
+ lower = findSector(lower, upper);
+ upper = findSector(upper, lower);
+
+ int prevLower = m_edges.at(lower).previous;
+ int prevUpper = m_edges.at(upper).previous;
+
+ Edge e;
+
+ e.twin = m_edges.size() + 1;
+ e.next = upper;
+ e.previous = prevLower;
+ e.from = m_edges.at(lower).from;
+ e.to = m_edges.at(upper).from;
+ m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size());
+ m_edges.add(e);
+
+ e.twin = m_edges.size() - 1;
+ e.next = lower;
+ e.previous = prevUpper;
+ e.from = m_edges.at(upper).from;
+ e.to = m_edges.at(lower).from;
+ m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size());
+ m_edges.add(e);
+}
+
+void QTriangulator::SimpleToMonotone::monotoneDecomposition()
+{
+ if (m_edges.isEmpty())
+ return;
+
+ Q_ASSERT(!m_edgeList.root);
+ QDataBuffer<QPair<int, int> > diagonals;
+
+ int i = 0;
+ for (int index = 1; index < m_edges.size(); ++index) {
+ if (m_parent->m_vertices.at(m_edges.at(index).from) < m_parent->m_vertices.at(m_edges.at(i).from))
+ i = index;
+ }
+ Q_ASSERT(i < m_edges.size());
+ int j = m_edges.at(i).previous;
+ Q_ASSERT(j < m_edges.size());
+ m_clockwiseOrder = qPointIsLeftOfLine(m_parent->m_vertices.at(m_edges.at(i).from),
+ m_parent->m_vertices.at(m_edges.at(j).from), m_parent->m_vertices.at(m_edges.at(i).to));
+
+ classifyVertices();
+ fillPriorityQueue();
+
+ // debug: set helpers explicitly (shouldn't be necessary)
+ //for (int i = 0; i < m_edges.size(); ++i)
+ // m_edges.at(i).helper = m_edges.at(i).upper();
+
+ while (!m_upperVertex.isEmpty()) {
+ i = m_upperVertex.last();
+ Q_ASSERT(i < m_edges.size());
+ m_upperVertex.pop_back();
+ j = m_edges.at(i).previous;
+ Q_ASSERT(j < m_edges.size());
+
+ QRBTree<int>::Node *leftEdgeNode = 0;
+
+ switch (m_edges.at(i).type) {
+ case RegularVertex:
+ // If polygon interior is to the right of the vertex...
+ if (m_edges.at(i).pointingUp == m_clockwiseOrder) {
+ if (m_edges.at(i).node) {
+ Q_ASSERT(!m_edges.at(j).node);
+ if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
+ diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
+ m_edges.at(j).node = m_edges.at(i).node;
+ m_edges.at(i).node = 0;
+ m_edges.at(j).node->data = j;
+ m_edges.at(j).helper = i;
+ } else if (m_edges.at(j).node) {
+ Q_ASSERT(!m_edges.at(i).node);
+ if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
+ diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
+ m_edges.at(i).node = m_edges.at(j).node;
+ m_edges.at(j).node = 0;
+ m_edges.at(i).node->data = i;
+ m_edges.at(i).helper = i;
+ } else {
+ qWarning("Inconsistent polygon. (#1)");
+ }
+ } else {
+ leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
+ if (leftEdgeNode) {
+ if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
+ diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
+ m_edges.at(leftEdgeNode->data).helper = i;
+ } else {
+ qWarning("Inconsistent polygon. (#2)");
+ }
+ }
+ break;
+ case SplitVertex:
+ leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
+ if (leftEdgeNode) {
+ diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
+ m_edges.at(leftEdgeNode->data).helper = i;
+ } else {
+ qWarning("Inconsistent polygon. (#3)");
+ }
+ // Fall through.
+ case StartVertex:
+ if (m_clockwiseOrder) {
+ leftEdgeNode = searchEdgeLeftOfEdge(j);
+ QRBTree<int>::Node *node = m_edgeList.newNode();
+ node->data = j;
+ m_edges.at(j).node = node;
+ m_edges.at(j).helper = i;
+ m_edgeList.attachAfter(leftEdgeNode, node);
+ Q_ASSERT(m_edgeList.verify());
+ } else {
+ leftEdgeNode = searchEdgeLeftOfEdge(i);
+ QRBTree<int>::Node *node = m_edgeList.newNode();
+ node->data = i;
+ m_edges.at(i).node = node;
+ m_edges.at(i).helper = i;
+ m_edgeList.attachAfter(leftEdgeNode, node);
+ Q_ASSERT(m_edgeList.verify());
+ }
+ break;
+ case MergeVertex:
+ leftEdgeNode = searchEdgeLeftOfPoint(m_edges.at(i).from);
+ if (leftEdgeNode) {
+ if (m_edges.at(m_edges.at(leftEdgeNode->data).helper).type == MergeVertex)
+ diagonals.add(QPair<int, int>(i, m_edges.at(leftEdgeNode->data).helper));
+ m_edges.at(leftEdgeNode->data).helper = i;
+ } else {
+ qWarning("Inconsistent polygon. (#4)");
+ }
+ // Fall through.
+ case EndVertex:
+ if (m_clockwiseOrder) {
+ if (m_edges.at(m_edges.at(i).helper).type == MergeVertex)
+ diagonals.add(QPair<int, int>(i, m_edges.at(i).helper));
+ if (m_edges.at(i).node) {
+ m_edgeList.deleteNode(m_edges.at(i).node);
+ Q_ASSERT(m_edgeList.verify());
+ } else {
+ qWarning("Inconsistent polygon. (#5)");
+ }
+ } else {
+ if (m_edges.at(m_edges.at(j).helper).type == MergeVertex)
+ diagonals.add(QPair<int, int>(i, m_edges.at(j).helper));
+ if (m_edges.at(j).node) {
+ m_edgeList.deleteNode(m_edges.at(j).node);
+ Q_ASSERT(m_edgeList.verify());
+ } else {
+ qWarning("Inconsistent polygon. (#6)");
+ }
+ }
+ break;
+ }
+ }
+
+ for (int i = 0; i < diagonals.size(); ++i)
+ createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
+}
+
+bool QTriangulator::SimpleToMonotone::CompareVertices::operator () (int i, int j) const
+{
+ if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from)
+ return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type;
+ 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);
+}
+
+//============================================================================//
+// QTriangulator::MonotoneToTriangles //
+//============================================================================//
+
+void QTriangulator::MonotoneToTriangles::decompose()
+{
+ QVector<quint32> result;
+ QDataBuffer<int> stack;
+ m_first = 0;
+ // Require at least three more indices.
+ while (m_first + 3 <= m_parent->m_indices.size()) {
+ m_length = 0;
+ while (m_parent->m_indices.at(m_first + m_length) != Q_TRIANGULATE_END_OF_POLYGON) {
+ ++m_length;
+ Q_ASSERT(m_first + m_length < m_parent->m_indices.size());
+ }
+ if (m_length < 3) {
+ m_first += m_length + 1;
+ continue;
+ }
+
+ int minimum = 0;
+ while (less(next(minimum), minimum))
+ minimum = next(minimum);
+ while (less(previous(minimum), minimum))
+ minimum = previous(minimum);
+
+ stack.reset();
+ stack.add(minimum);
+ int left = previous(minimum);
+ int right = next(minimum);
+ bool stackIsOnLeftSide;
+ bool clockwiseOrder = leftOfEdge(minimum, left, right);
+
+ if (less(left, right)) {
+ stack.add(left);
+ left = previous(left);
+ stackIsOnLeftSide = true;
+ } else {
+ stack.add(right);
+ right = next(right);
+ stackIsOnLeftSide = false;
+ }
+
+ for (int count = 0; count + 2 < m_length; ++count)
+ {
+ Q_ASSERT(stack.size() >= 2);
+ if (less(left, right)) {
+ if (stackIsOnLeftSide == false) {
+ for (int i = 0; i + 1 < stack.size(); ++i) {
+ result.push_back(indices(stack.at(i + 1)));
+ result.push_back(indices(left));
+ result.push_back(indices(stack.at(i)));
+ }
+ stack.first() = stack.last();
+ stack.resize(1);
+ } else {
+ while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(left, stack.at(stack.size() - 2), stack.last()))) {
+ result.push_back(indices(stack.at(stack.size() - 2)));
+ result.push_back(indices(left));
+ result.push_back(indices(stack.last()));
+ stack.pop_back();
+ }
+ }
+ stack.add(left);
+ left = previous(left);
+ stackIsOnLeftSide = true;
+ } else {
+ if (stackIsOnLeftSide == true) {
+ for (int i = 0; i + 1 < stack.size(); ++i) {
+ result.push_back(indices(stack.at(i)));
+ result.push_back(indices(right));
+ result.push_back(indices(stack.at(i + 1)));
+ }
+ stack.first() = stack.last();
+ stack.resize(1);
+ } else {
+ while (stack.size() >= 2 && (clockwiseOrder ^ !leftOfEdge(right, stack.last(), stack.at(stack.size() - 2)))) {
+ result.push_back(indices(stack.last()));
+ result.push_back(indices(right));
+ result.push_back(indices(stack.at(stack.size() - 2)));
+ stack.pop_back();
+ }
+ }
+ stack.add(right);
+ right = next(right);
+ stackIsOnLeftSide = false;
+ }
+ }
+
+ m_first += m_length + 1;
+ }
+ m_parent->m_indices = result;
+}
+
+//============================================================================//
+// qTriangulate //
+//============================================================================//
+
+QTriangleSet qTriangulate(const qreal *polygon, int count, uint hint, const QTransform &matrix)
+{
+ QTriangulator triangulator;
+ triangulator.initialize(polygon, count, hint, matrix);
+ return triangulator.triangulate();
+}
+
+QTriangleSet qTriangulate(const QVectorPath &path, const QTransform &matrix, qreal lod)
+{
+ QTriangulator triangulator;
+ triangulator.initialize(path, matrix, lod);
+ return triangulator.triangulate();
+}
+
+QTriangleSet qTriangulate(const QPainterPath &path, const QTransform &matrix, qreal lod)
+{
+ QTriangulator triangulator;
+ triangulator.initialize(path, matrix, lod);
+ return triangulator.triangulate();
+}
+
+QPolylineSet qPolyline(const QVectorPath &path, const QTransform &matrix, qreal lod)
+{
+ QTriangulator triangulator;
+ triangulator.initialize(path, matrix, lod);
+ return triangulator.polyline();
+}
+
+QPolylineSet qPolyline(const QPainterPath &path, const QTransform &matrix, qreal lod)
+{
+ QTriangulator triangulator;
+ triangulator.initialize(path, matrix, lod);
+ return triangulator.polyline();
+}
+
+QT_END_NAMESPACE
diff --git a/src/opengl/gl2paintengineex/qtriangulator_p.h b/src/opengl/gl2paintengineex/qtriangulator_p.h
new file mode 100644
index 0000000..da47666
--- /dev/null
+++ b/src/opengl/gl2paintengineex/qtriangulator_p.h
@@ -0,0 +1,98 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtOpenGL module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QTRIANGULATOR_P_H
+#define QTRIANGULATOR_P_H
+
+//
+// W A R N I N G
+// -------------
+//
+// This file is not part of the Qt API. It exists purely as an
+// implementation detail. This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <QtCore/qvector.h>
+#include <QtGui/private/qvectorpath_p.h>
+
+QT_BEGIN_NAMESPACE
+
+#define Q_TRIANGULATE_END_OF_POLYGON quint32(-1)
+
+struct QTriangleSet
+{
+ inline QTriangleSet() { }
+ inline QTriangleSet(const QTriangleSet &other) : vertices(other.vertices), indices(other.indices) { }
+ QTriangleSet &operator = (const QTriangleSet &other) {vertices = other.vertices; indices = other.indices; return *this;}
+
+ // 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, ...
+ QVector<qreal> vertices; // [x[0], y[0], x[1], y[1], x[2], ...]
+ QVector<quint32> indices; // [i[0], j[0], k[0], i[1], j[1], k[1], i[2], ...]
+};
+
+struct QPolylineSet
+{
+ inline QPolylineSet() { }
+ inline QPolylineSet(const QPolylineSet &other) : vertices(other.vertices), indices(other.indices) { }
+ QPolylineSet &operator = (const QPolylineSet &other) {vertices = other.vertices; indices = other.indices; return *this;}
+
+ QVector<qreal> vertices; // [x[0], y[0], x[1], y[1], x[2], ...]
+ QVector<quint32> indices;
+
+};
+
+// The vertex coordinates of the returned triangle set will be rounded to a grid with a mesh size
+// of 1/32. The polygon is first transformed, then scaled by 32, the coordinates are rounded to
+// integers, the polygon is triangulated, and then scaled back by 1/32.
+// 'hint' should be a combination of QVectorPath::Hints.
+// 'lod' is the level of detail. Default is 1. Curves are split into more lines when 'lod' is higher.
+QTriangleSet qTriangulate(const qreal *polygon, int count, uint hint = QVectorPath::PolygonHint | QVectorPath::OddEvenFill, const QTransform &matrix = QTransform());
+QTriangleSet qTriangulate(const QVectorPath &path, const QTransform &matrix = QTransform(), qreal lod = 1);
+QTriangleSet qTriangulate(const QPainterPath &path, const QTransform &matrix = QTransform(), qreal lod = 1);
+QPolylineSet qPolyline(const QVectorPath &path, const QTransform &matrix = QTransform(), qreal lod = 1);
+QPolylineSet qPolyline(const QPainterPath &path, const QTransform &matrix = QTransform(), qreal lod = 1);
+
+QT_END_NAMESPACE
+
+#endif
diff --git a/src/opengl/opengl.pro b/src/opengl/opengl.pro
index 6076891..69cfd30 100644
--- a/src/opengl/opengl.pro
+++ b/src/opengl/opengl.pro
@@ -55,6 +55,7 @@ SOURCES += qgl.cpp \
gl2paintengineex/qglengineshadersource_p.h \
gl2paintengineex/qglcustomshaderstage_p.h \
gl2paintengineex/qtriangulatingstroker_p.h \
+ gl2paintengineex/qtriangulator_p.h \
gl2paintengineex/qtextureglyphcache_gl_p.h
SOURCES += qglshaderprogram.cpp \
@@ -69,6 +70,7 @@ SOURCES += qgl.cpp \
gl2paintengineex/qpaintengineex_opengl2.cpp \
gl2paintengineex/qglcustomshaderstage.cpp \
gl2paintengineex/qtriangulatingstroker.cpp \
+ gl2paintengineex/qtriangulator.cpp \
gl2paintengineex/qtextureglyphcache_gl.cpp
}
diff --git a/src/opengl/qgl.cpp b/src/opengl/qgl.cpp
index 3f32cf3..b7139a2 100644
--- a/src/opengl/qgl.cpp
+++ b/src/opengl/qgl.cpp
@@ -222,6 +222,9 @@ bool qt_gl_preferGL2Engine()
\value DirectRendering Specifies that the context is used for direct rendering to a display.
\value HasOverlay Enables the use of an overlay.
\value SampleBuffers Enables the use of sample buffers.
+ \value DeprecatedFunctions Enables the use of deprecated functionality for OpenGL 3.x
+ contexts. A context with deprecated functionality enabled is
+ called a full context in the OpenGL specification.
\value SingleBuffer Specifies the use of a single buffer, as opposed to double buffers.
\value NoDepthBuffer Disables the use of a depth buffer.
\value ColorIndex Specifies that the context should use a color index as its pixel format.
@@ -232,6 +235,9 @@ bool qt_gl_preferGL2Engine()
\value IndirectRendering Specifies that the context is used for indirect rendering to a buffer.
\value NoOverlay Disables the use of an overlay.
\value NoSampleBuffers Disables the use of sample buffers.
+ \value NoDeprecatedFunctions Disables the use of deprecated functionality for OpenGL 3.x
+ contexts. A context with deprecated functionality disabled is
+ called a forward compatible context in the OpenGL specification.
\sa {Sample Buffers Example}
*/
@@ -1077,6 +1083,88 @@ int QGLFormat::stencilBufferSize() const
}
/*!
+ \since 4.7
+
+ Set the OpenGL version. If a context compatible with the requested OpenGL version
+ cannot be created, a context compatible with version 1.x is created instead.
+
+ \sa majorVersion(), minorVersion()
+*/
+void QGLFormat::setVersion(int major, int minor)
+{
+ if (major < 1 || minor < 0) {
+ qWarning("QGLFormat::setVersion: Cannot set zero or negative version number %d.%d", major, minor);
+ return;
+ }
+ detach();
+ d->majorVersion = major;
+ d->minorVersion = minor;
+}
+
+/*!
+ \since 4.7
+
+ Returns the OpenGL major version.
+
+ \sa setVersion(), minorVersion()
+*/
+int QGLFormat::majorVersion() const
+{
+ return d->majorVersion;
+}
+
+/*!
+ \since 4.7
+
+ Returns the OpenGL minor version.
+
+ \sa setVersion(), majorVersion()
+*/
+int QGLFormat::minorVersion() const
+{
+ return d->minorVersion;
+}
+
+/*!
+ \enum QGLFormat::OpenGLContextProfile
+ \since 4.7
+
+ This enum describes the OpenGL context profiles that can be specified for contexts implementing
+ OpenGL version 3.2 or higher. These profiles are different from OpenGL ES profiles.
+
+ \value NoProfile OpenGL version is lower than 3.2.
+ \value CoreProfile Functionality deprecated in OpenGL version 3.0 is not available.
+ \value CompatibilityProfile Functionality from earlier OpenGL versions is available.
+*/
+
+/*!
+ \since 4.7
+
+ Set the OpenGL context profile. The profile is ignored if the requested OpenGL
+ version is less than 3.2.
+
+ \sa profile()
+*/
+void QGLFormat::setProfile(OpenGLContextProfile profile)
+{
+ detach();
+ d->profile = profile;
+}
+
+/*!
+ \since 4.7
+
+ Returns the OpenGL context profile.
+
+ \sa setProfile()
+*/
+QGLFormat::OpenGLContextProfile QGLFormat::profile() const
+{
+ return d->profile;
+}
+
+
+/*!
\fn bool QGLFormat::hasOpenGL()
Returns true if the window system has any OpenGL support;
@@ -1112,25 +1200,21 @@ QGLFormat::OpenGLVersionFlags Q_AUTOTEST_EXPORT qOpenGLVersionFlagsFromString(co
if (parts[2].startsWith(QLatin1String("1.1")))
versionFlags |= QGLFormat::OpenGL_ES_Common_Version_1_1 |
QGLFormat::OpenGL_ES_CommonLite_Version_1_1;
- }
- else {
+ } else {
// Not -CM, must be CL, CommonLite
versionFlags |= QGLFormat::OpenGL_ES_CommonLite_Version_1_0;
if (parts[2].startsWith(QLatin1String("1.1")))
versionFlags |= QGLFormat::OpenGL_ES_CommonLite_Version_1_1;
}
- }
- else {
+ } else {
// OpenGL ES version 2.0 or higher
versionFlags |= QGLFormat::OpenGL_ES_Version_2_0;
}
- }
- else {
+ } else {
// if < 3 parts to the name, it is an unrecognised OpenGL ES
qWarning("Unrecognised OpenGL ES version");
}
- }
- else {
+ } else {
// not ES, regular OpenGL, the version numbers are first in the string
if (versionString.startsWith(QLatin1String("1."))) {
switch (versionString[2].toAscii()) {
@@ -1147,30 +1231,35 @@ QGLFormat::OpenGLVersionFlags Q_AUTOTEST_EXPORT qOpenGLVersionFlagsFromString(co
default:
break;
}
- }
- else if (versionString.startsWith(QLatin1String("2."))) {
+ } else if (versionString.startsWith(QLatin1String("2."))) {
versionFlags |= QGLFormat::OpenGL_Version_1_1 |
QGLFormat::OpenGL_Version_1_2 |
QGLFormat::OpenGL_Version_1_3 |
QGLFormat::OpenGL_Version_1_4 |
QGLFormat::OpenGL_Version_1_5 |
QGLFormat::OpenGL_Version_2_0;
- QString minorVersion = versionString.section(QLatin1Char(' '), 0, 0).section(QLatin1Char('.'), 1, 1);
- if (minorVersion == QChar(QLatin1Char('1')))
+ if (versionString[2].toAscii() == '1')
versionFlags |= QGLFormat::OpenGL_Version_2_1;
- }
- else if (versionString.startsWith(QLatin1String("3."))) {
- versionFlags |= QGLFormat::OpenGL_Version_1_1 |
- QGLFormat::OpenGL_Version_1_2 |
- QGLFormat::OpenGL_Version_1_3 |
- QGLFormat::OpenGL_Version_1_4 |
- QGLFormat::OpenGL_Version_1_5 |
- QGLFormat::OpenGL_Version_2_0 |
- QGLFormat::OpenGL_Version_2_1 |
- QGLFormat::OpenGL_Version_3_0;
- }
- else
+ } else if (versionString.startsWith(QLatin1String("3."))) {
+ versionFlags |= QGLFormat::OpenGL_Version_1_1 |
+ QGLFormat::OpenGL_Version_1_2 |
+ QGLFormat::OpenGL_Version_1_3 |
+ QGLFormat::OpenGL_Version_1_4 |
+ QGLFormat::OpenGL_Version_1_5 |
+ QGLFormat::OpenGL_Version_2_0 |
+ QGLFormat::OpenGL_Version_2_1 |
+ QGLFormat::OpenGL_Version_3_0;
+ switch (versionString[2].toAscii()) {
+ case '2':
+ versionFlags |= QGLFormat::OpenGL_Version_3_2;
+ case '1':
+ versionFlags |= QGLFormat::OpenGL_Version_3_1;
+ default:
+ break;
+ }
+ } else {
qWarning("Unrecognised OpenGL version");
+ }
}
return versionFlags;
}
@@ -1202,6 +1291,12 @@ QGLFormat::OpenGLVersionFlags Q_AUTOTEST_EXPORT qOpenGLVersionFlagsFromString(co
\value OpenGL_Version_3_0 OpenGL version 3.0 or higher is present.
+ \value OpenGL_Version_3_1 OpenGL version 3.1 or higher is present.
+ Note that OpenGL version 3.1 or higher does not necessarily support all the features of
+ version 3.0 and lower.
+
+ \value OpenGL_Version_3_2 OpenGL version 3.2 or higher is present.
+
\value OpenGL_ES_CommonLite_Version_1_0 OpenGL ES version 1.0 Common Lite or higher is present.
\value OpenGL_ES_Common_Version_1_0 OpenGL ES version 1.0 Common or higher is present.
@@ -1373,14 +1468,20 @@ void QGLFormat::setDefaultOverlayFormat(const QGLFormat &f)
bool operator==(const QGLFormat& a, const QGLFormat& b)
{
- return (int) a.d->opts == (int) b.d->opts && a.d->pln == b.d->pln && a.d->alphaSize == b.d->alphaSize
- && a.d->accumSize == b.d->accumSize && a.d->stencilSize == b.d->stencilSize
+ return (a.d == b.d) || ((int) a.d->opts == (int) b.d->opts
+ && a.d->pln == b.d->pln
+ && a.d->alphaSize == b.d->alphaSize
+ && a.d->accumSize == b.d->accumSize
+ && a.d->stencilSize == b.d->stencilSize
&& a.d->depthSize == b.d->depthSize
&& a.d->redSize == b.d->redSize
&& a.d->greenSize == b.d->greenSize
&& a.d->blueSize == b.d->blueSize
&& a.d->numSamples == b.d->numSamples
- && a.d->swapInterval == b.d->swapInterval;
+ && a.d->swapInterval == b.d->swapInterval
+ && a.d->majorVersion == b.d->majorVersion
+ && a.d->minorVersion == b.d->minorVersion
+ && a.d->profile == b.d->profile);
}
diff --git a/src/opengl/qgl.h b/src/opengl/qgl.h
index 1a04ff9..8ada8ce 100644
--- a/src/opengl/qgl.h
+++ b/src/opengl/qgl.h
@@ -144,6 +144,7 @@ namespace QGL
DirectRendering = 0x0080,
HasOverlay = 0x0100,
SampleBuffers = 0x0200,
+ DeprecatedFunctions = 0x0400,
SingleBuffer = DoubleBuffer << 16,
NoDepthBuffer = DepthBuffer << 16,
ColorIndex = Rgba << 16,
@@ -153,7 +154,8 @@ namespace QGL
NoStereoBuffers = StereoBuffers << 16,
IndirectRendering = DirectRendering << 16,
NoOverlay = HasOverlay << 16,
- NoSampleBuffers = SampleBuffers << 16
+ NoSampleBuffers = SampleBuffers << 16,
+ NoDeprecatedFunctions = DeprecatedFunctions << 16
};
Q_DECLARE_FLAGS(FormatOptions, FormatOption)
}
@@ -235,7 +237,20 @@ public:
static bool hasOpenGL();
static bool hasOpenGLOverlays();
- enum OpenGLVersionFlag {
+ void setVersion(int major, int minor);
+ int majorVersion() const;
+ int minorVersion() const;
+
+ enum OpenGLContextProfile {
+ NoProfile,
+ CoreProfile,
+ CompatibilityProfile
+ };
+
+ void setProfile(OpenGLContextProfile profile);
+ OpenGLContextProfile profile() const;
+
+ enum OpenGLVersionFlag {
OpenGL_Version_None = 0x00000000,
OpenGL_Version_1_1 = 0x00000001,
OpenGL_Version_1_2 = 0x00000002,
@@ -249,7 +264,9 @@ public:
OpenGL_ES_Common_Version_1_1 = 0x00000200,
OpenGL_ES_CommonLite_Version_1_1 = 0x00000400,
OpenGL_ES_Version_2_0 = 0x00000800,
- OpenGL_Version_3_0 = 0x00001000
+ OpenGL_Version_3_0 = 0x00001000,
+ OpenGL_Version_3_1 = 0x00002000,
+ OpenGL_Version_3_2 = 0x00004000
};
Q_DECLARE_FLAGS(OpenGLVersionFlags, OpenGLVersionFlag)
diff --git a/src/opengl/qgl_p.h b/src/opengl/qgl_p.h
index 0104f07..9e8e335 100644
--- a/src/opengl/qgl_p.h
+++ b/src/opengl/qgl_p.h
@@ -132,11 +132,15 @@ public:
QGLFormatPrivate()
: ref(1)
{
- opts = QGL::DoubleBuffer | QGL::DepthBuffer | QGL::Rgba | QGL::DirectRendering | QGL::StencilBuffer;
+ opts = QGL::DoubleBuffer | QGL::DepthBuffer | QGL::Rgba | QGL::DirectRendering
+ | QGL::StencilBuffer | QGL::DeprecatedFunctions;
pln = 0;
depthSize = accumSize = stencilSize = redSize = greenSize = blueSize = alphaSize = -1;
numSamples = -1;
swapInterval = -1;
+ majorVersion = 1;
+ minorVersion = 0;
+ profile = QGLFormat::NoProfile;
}
QGLFormatPrivate(const QGLFormatPrivate *other)
: ref(1),
@@ -150,7 +154,10 @@ public:
blueSize(other->blueSize),
alphaSize(other->alphaSize),
numSamples(other->numSamples),
- swapInterval(other->swapInterval)
+ swapInterval(other->swapInterval),
+ majorVersion(other->majorVersion),
+ minorVersion(other->minorVersion),
+ profile(other->profile)
{
}
QAtomicInt ref;
@@ -165,6 +172,9 @@ public:
int alphaSize;
int numSamples;
int swapInterval;
+ int majorVersion;
+ int minorVersion;
+ QGLFormat::OpenGLContextProfile profile;
};
class QGLWidgetPrivate : public QWidgetPrivate
@@ -344,6 +354,10 @@ public:
void syncGlState(); // Makes sure the GL context's state is what we think it is
#if defined(Q_WS_WIN)
+ void updateFormatVersion();
+#endif
+
+#if defined(Q_WS_WIN)
HGLRC rc;
HDC dc;
WId win;
diff --git a/src/opengl/qgl_win.cpp b/src/opengl/qgl_win.cpp
index ed4814f..b5f952e 100644
--- a/src/opengl/qgl_win.cpp
+++ b/src/opengl/qgl_win.cpp
@@ -122,6 +122,30 @@ typedef bool (APIENTRY *PFNWGLCHOOSEPIXELFORMATARB)(HDC hdc,
#define WGL_TYPE_COLORINDEX_ARB 0x202C
#endif
+#ifndef WGL_ARB_create_context
+#define WGL_CONTEXT_MAJOR_VERSION_ARB 0x2091
+#define WGL_CONTEXT_MINOR_VERSION_ARB 0x2092
+#define WGL_CONTEXT_LAYER_PLANE_ARB 0x2093
+#define WGL_CONTEXT_FLAGS_ARB 0x2094
+#define WGL_CONTEXT_PROFILE_MASK_ARB 0x9126
+#define WGL_CONTEXT_DEBUG_BIT_ARB 0x0001
+#define WGL_CONTEXT_FORWARD_COMPATIBLE_BIT_ARB 0x0002
+#define WGL_CONTEXT_CORE_PROFILE_BIT_ARB 0x0001
+#define WGL_CONTEXT_COMPATIBILITY_PROFILE_BIT_ARB 0x0002
+// Error codes returned by GetLastError().
+#define ERROR_INVALID_VERSION_ARB 0x2095
+#define ERROR_INVALID_PROFILE_ARB 0x2096
+#endif
+
+#ifndef GL_VERSION_3_2
+#define GL_CONTEXT_PROFILE_MASK 0x9126
+#define GL_MAJOR_VERSION 0x821B
+#define GL_MINOR_VERSION 0x821C
+#define GL_NUM_EXTENSIONS 0x821D
+#define GL_CONTEXT_FLAGS 0x821E
+#define GL_CONTEXT_FLAG_FORWARD_COMPATIBLE_BIT 0x0001
+#endif
+
QT_BEGIN_NAMESPACE
class QGLCmapPrivate
@@ -682,8 +706,118 @@ QGLTemporaryContext::~QGLTemporaryContext()
wglMakeCurrent(d->old_dc, d->old_context);
}
+static bool qgl_create_context(HDC hdc, QGLContextPrivate *d, QGLContextPrivate *shareContext)
+{
+ d->rc = 0;
+
+ typedef HGLRC (APIENTRYP PFNWGLCREATECONTEXTATTRIBSARB)(HDC, HGLRC, const int *);
+ PFNWGLCREATECONTEXTATTRIBSARB wglCreateContextAttribsARB =
+ (PFNWGLCREATECONTEXTATTRIBSARB) wglGetProcAddress("wglCreateContextAttribsARB");
+ if (wglCreateContextAttribsARB) {
+ int attributes[11];
+ int attribIndex = 0;
+ const int major = d->reqFormat.majorVersion();
+ const int minor = d->reqFormat.minorVersion();
+ attributes[attribIndex++] = WGL_CONTEXT_MAJOR_VERSION_ARB;
+ attributes[attribIndex++] = major;
+ attributes[attribIndex++] = WGL_CONTEXT_MINOR_VERSION_ARB;
+ attributes[attribIndex++] = minor;
+
+ if (major >= 3 && !d->reqFormat.testOption(QGL::DeprecatedFunctions)) {
+ attributes[attribIndex++] = WGL_CONTEXT_FLAGS_ARB;
+ attributes[attribIndex++] = WGL_CONTEXT_FORWARD_COMPATIBLE_BIT_ARB;
+ }
+
+ if ((major == 3 && minor >= 2) || major > 3) {
+ switch (d->reqFormat.profile()) {
+ case QGLFormat::NoProfile:
+ break;
+ case QGLFormat::CoreProfile:
+ attributes[attribIndex++] = WGL_CONTEXT_PROFILE_MASK_ARB;
+ attributes[attribIndex++] = WGL_CONTEXT_CORE_PROFILE_BIT_ARB;
+ break;
+ case QGLFormat::CompatibilityProfile:
+ attributes[attribIndex++] = WGL_CONTEXT_PROFILE_MASK_ARB;
+ attributes[attribIndex++] = WGL_CONTEXT_COMPATIBILITY_PROFILE_BIT_ARB;
+ break;
+ default:
+ qWarning("QGLContext::chooseContext(): Context profile not supported.");
+ return false;
+ }
+ }
+
+ if (d->reqFormat.plane() != 0) {
+ attributes[attribIndex++] = WGL_CONTEXT_LAYER_PLANE_ARB;
+ attributes[attribIndex++] = d->reqFormat.plane();
+ }
+
+ attributes[attribIndex++] = 0; // Terminate list.
+ d->rc = wglCreateContextAttribsARB(hdc, shareContext && shareContext->valid
+ ? shareContext->rc : 0, attributes);
+ if (d->rc) {
+ if (shareContext)
+ shareContext->sharing = d->sharing = true;
+ return true;
+ }
+ }
+
+ d->rc = wglCreateLayerContext(hdc, d->reqFormat.plane());
+ if (d->rc && shareContext && shareContext->valid)
+ shareContext->sharing = d->sharing = wglShareLists(shareContext->rc, d->rc);
+ return d->rc != 0;
+}
+
+void QGLContextPrivate::updateFormatVersion()
+{
+ const GLubyte *s = glGetString(GL_VERSION);
+
+ if (!(s && s[0] >= '0' && s[0] <= '9' && s[1] == '.' && s[2] >= '0' && s[2] <= '9')) {
+ if (!s)
+ qWarning("QGLContext::chooseContext(): OpenGL version string is null.");
+ else
+ qWarning("QGLContext::chooseContext(): Unexpected OpenGL version string format.");
+ glFormat.setVersion(0, 0);
+ glFormat.setProfile(QGLFormat::NoProfile);
+ glFormat.setOption(QGL::DeprecatedFunctions);
+ return;
+ }
+
+ int major = s[0] - '0';
+ int minor = s[2] - '0';
+ glFormat.setVersion(major, minor);
+
+ if (major < 3) {
+ glFormat.setProfile(QGLFormat::NoProfile);
+ glFormat.setOption(QGL::DeprecatedFunctions);
+ } else {
+ GLint value = 0;
+ if (major > 3 || minor >= 2)
+ glGetIntegerv(GL_CONTEXT_PROFILE_MASK, &value);
+
+ switch (value) {
+ case WGL_CONTEXT_CORE_PROFILE_BIT_ARB:
+ glFormat.setProfile(QGLFormat::CoreProfile);
+ break;
+ case WGL_CONTEXT_COMPATIBILITY_PROFILE_BIT_ARB:
+ glFormat.setProfile(QGLFormat::CompatibilityProfile);
+ break;
+ default:
+ glFormat.setProfile(QGLFormat::NoProfile);
+ break;
+ }
+
+ glGetIntegerv(GL_CONTEXT_FLAGS, &value);
+ if (value & GL_CONTEXT_FLAG_FORWARD_COMPATIBLE_BIT)
+ glFormat.setOption(QGL::NoDeprecatedFunctions);
+ else
+ glFormat.setOption(QGL::DeprecatedFunctions);
+ }
+}
+
bool QGLContext::chooseContext(const QGLContext* shareContext)
{
+ QGLContextPrivate *share = shareContext ? const_cast<QGLContext *>(shareContext)->d_func() : 0;
+
Q_D(QGLContext);
// workaround for matrox driver:
// make a cheap call to opengl to force loading of DLL
@@ -741,8 +875,7 @@ bool QGLContext::chooseContext(const QGLContext* shareContext)
goto end;
}
- d->rc = wglCreateLayerContext(myDc, d->glFormat.plane());
- if (!d->rc) {
+ if (!qgl_create_context(myDc, d, share)) {
qwglError("QGLContext::chooseContext()", "CreateLayerContext");
result = false;
goto end;
@@ -792,16 +925,7 @@ bool QGLContext::chooseContext(const QGLContext* shareContext)
d->cmap = new QGLCmap(1 << lpfd.cColorBits);
d->cmap->setEntry(lpfd.crTransparent, qRgb(1, 2, 3));//, QGLCmap::Reserved);
}
-
- if (shareContext && shareContext->isValid()) {
- QGLContext *share = const_cast<QGLContext *>(shareContext);
- d->sharing = (wglShareLists(shareContext->d_func()->rc, d->rc) != 0);
- share->d_func()->sharing = d->sharing;
- }
-
- goto end;
- }
- {
+ } else {
PIXELFORMATDESCRIPTOR pfd;
PIXELFORMATDESCRIPTOR realPfd;
d->pixelFormatId = choosePixelFormat(&pfd, myDc);
@@ -840,17 +964,12 @@ bool QGLContext::chooseContext(const QGLContext* shareContext)
goto end;
}
- if (!(d->rc = wglCreateLayerContext(myDc, 0))) {
+ if (!qgl_create_context(myDc, d, share)) {
qwglError("QGLContext::chooseContext()", "wglCreateContext");
result = false;
goto end;
}
- if (shareContext && shareContext->isValid()) {
- d->sharing = (wglShareLists(shareContext->d_func()->rc, d->rc) != 0);
- const_cast<QGLContext *>(shareContext)->d_func()->sharing = d->sharing;
- }
-
if(!deviceIsPixmap()) {
QRgb* pal = qgl_create_rgb_palette(&realPfd);
if (pal) {
@@ -865,6 +984,9 @@ bool QGLContext::chooseContext(const QGLContext* shareContext)
end:
// vblanking
wglMakeCurrent(myDc, d->rc);
+ if (d->rc)
+ d->updateFormatVersion();
+
typedef BOOL (APIENTRYP PFNWGLSWAPINTERVALEXT) (int interval);
typedef int (APIENTRYP PFNWGLGETSWAPINTERVALEXT) (void);
PFNWGLSWAPINTERVALEXT wglSwapIntervalEXT = (PFNWGLSWAPINTERVALEXT) wglGetProcAddress("wglSwapIntervalEXT");
diff --git a/src/opengl/qglextensions_p.h b/src/opengl/qglextensions_p.h
index b0cb429..86096d2 100644
--- a/src/opengl/qglextensions_p.h
+++ b/src/opengl/qglextensions_p.h
@@ -599,6 +599,20 @@ struct QGLExtensionFuncs
#define GL_DECR_WRAP 0x8508
#endif
+#ifndef GL_VERSION_1_5
+#define GL_ARRAY_BUFFER 0x8892
+#define GL_ELEMENT_ARRAY_BUFFER 0x8893
+#define GL_STREAM_DRAW 0x88E0
+#define GL_STREAM_READ 0x88E1
+#define GL_STREAM_COPY 0x88E2
+#define GL_STATIC_DRAW 0x88E4
+#define GL_STATIC_READ 0x88E5
+#define GL_STATIC_COPY 0x88E6
+#define GL_DYNAMIC_DRAW 0x88E8
+#define GL_DYNAMIC_READ 0x88E9
+#define GL_DYNAMIC_COPY 0x88EA
+#endif
+
#ifndef GL_VERSION_2_0
#define GL_FRAGMENT_SHADER 0x8B30
#define GL_VERTEX_SHADER 0x8B31
generated by cgit v0.12 at 2024-11-13 01:36:37 (GMT)