summaryrefslogtreecommitdiffstats
path: root/src/opengl/gl2paintengineex
diff options
context:
space:
mode:
Diffstat (limited to 'src/opengl/gl2paintengineex')
-rw-r--r--src/opengl/gl2paintengineex/qglengineshadermanager.cpp55
-rw-r--r--src/opengl/gl2paintengineex/qglengineshadermanager_p.h1
-rw-r--r--src/opengl/gl2paintengineex/qglgradientcache.cpp25
-rw-r--r--src/opengl/gl2paintengineex/qglgradientcache_p.h9
-rw-r--r--src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp36
-rw-r--r--src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h8
-rw-r--r--src/opengl/gl2paintengineex/qrbtree_p.h573
-rw-r--r--src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp74
-rw-r--r--src/opengl/gl2paintengineex/qtextureglyphcache_gl_p.h48
-rw-r--r--src/opengl/gl2paintengineex/qtriangulator.cpp2612
-rw-r--r--src/opengl/gl2paintengineex/qtriangulator_p.h148
11 files changed, 146 insertions, 3443 deletions
diff --git a/src/opengl/gl2paintengineex/qglengineshadermanager.cpp b/src/opengl/gl2paintengineex/qglengineshadermanager.cpp
index 4c50089f6d..aebdce6e01 100644
--- a/src/opengl/gl2paintengineex/qglengineshadermanager.cpp
+++ b/src/opengl/gl2paintengineex/qglengineshadermanager.cpp
@@ -44,6 +44,8 @@
#include "qpaintengineex_opengl2_p.h"
#include "qglshadercache_p.h"
+#include <QtGui/private/qopenglcontext_p.h>
+
#if defined(QT_DEBUG)
#include <QMetaEnum>
#endif
@@ -52,18 +54,50 @@
QT_BEGIN_NAMESPACE
+class QGLEngineSharedShadersResource : public QOpenGLSharedResource
+{
+public:
+ QGLEngineSharedShadersResource(QOpenGLContext *ctx)
+ : QOpenGLSharedResource(ctx->shareGroup())
+ , m_shaders(new QGLEngineSharedShaders(QGLContext::fromOpenGLContext(ctx)))
+ {
+ }
+
+ ~QGLEngineSharedShadersResource()
+ {
+ delete m_shaders;
+ }
+
+ void invalidateResource()
+ {
+ delete m_shaders;
+ m_shaders = 0;
+ }
+
+ void freeResource(QOpenGLContext *)
+ {
+ }
+
+ QGLEngineSharedShaders *shaders() const { return m_shaders; }
+
+private:
+ QGLEngineSharedShaders *m_shaders;
+};
+
class QGLShaderStorage
{
public:
QGLEngineSharedShaders *shadersForThread(const QGLContext *context) {
- QGLContextGroupResource<QGLEngineSharedShaders> *&shaders = m_storage.localData();
+ QOpenGLMultiGroupSharedResource *&shaders = m_storage.localData();
if (!shaders)
- shaders = new QGLContextGroupResource<QGLEngineSharedShaders>();
- return shaders->value(context);
+ shaders = new QOpenGLMultiGroupSharedResource;
+ QGLEngineSharedShadersResource *resource =
+ shaders->value<QGLEngineSharedShadersResource>(context->contextHandle());
+ return resource ? resource->shaders() : 0;
}
private:
- QThreadStorage<QGLContextGroupResource<QGLEngineSharedShaders> *> m_storage;
+ QThreadStorage<QOpenGLMultiGroupSharedResource *> m_storage;
};
Q_GLOBAL_STATIC(QGLShaderStorage, qt_shader_storage);
@@ -81,8 +115,7 @@ const char* QGLEngineSharedShaders::qShaderSnippets[] = {
};
QGLEngineSharedShaders::QGLEngineSharedShaders(const QGLContext* context)
- : ctxGuard(context)
- , blitShaderProg(0)
+ : blitShaderProg(0)
, simpleShaderProg(0)
{
@@ -327,14 +360,14 @@ QGLEngineShaderProg *QGLEngineSharedShaders::findProgramInCache(const QGLEngineS
vertexSource.append(qShaderSnippets[prog.mainVertexShader]);
vertexSource.append(qShaderSnippets[prog.positionVertexShader]);
- QScopedPointer<QGLShaderProgram> shaderProgram(new QGLShaderProgram(ctxGuard.context(), 0));
+ QScopedPointer<QGLShaderProgram> shaderProgram(new QGLShaderProgram);
CachedShader shaderCache(fragSource, vertexSource);
- bool inCache = shaderCache.load(shaderProgram.data(), ctxGuard.context());
+ bool inCache = shaderCache.load(shaderProgram.data(), QGLContext::currentContext());
if (!inCache) {
- QScopedPointer<QGLShader> fragShader(new QGLShader(QGLShader::Fragment, ctxGuard.context(), 0));
+ QScopedPointer<QGLShader> fragShader(new QGLShader(QGLShader::Fragment));
QByteArray description;
#if defined(QT_DEBUG)
// Name the shader for easier debugging
@@ -357,7 +390,7 @@ QGLEngineShaderProg *QGLEngineSharedShaders::findProgramInCache(const QGLEngineS
break;
}
- QScopedPointer<QGLShader> vertexShader(new QGLShader(QGLShader::Vertex, ctxGuard.context(), 0));
+ QScopedPointer<QGLShader> vertexShader(new QGLShader(QGLShader::Vertex));
#if defined(QT_DEBUG)
// Name the shader for easier debugging
description.clear();
@@ -396,7 +429,7 @@ QGLEngineShaderProg *QGLEngineSharedShaders::findProgramInCache(const QGLEngineS
newProg->program->link();
if (newProg->program->isLinked()) {
if (!inCache)
- shaderCache.store(newProg->program, ctxGuard.context());
+ shaderCache.store(newProg->program, QGLContext::currentContext());
} else {
QLatin1String none("none");
QLatin1String br("\n");
diff --git a/src/opengl/gl2paintengineex/qglengineshadermanager_p.h b/src/opengl/gl2paintengineex/qglengineshadermanager_p.h
index 921df369f4..58c761df43 100644
--- a/src/opengl/gl2paintengineex/qglengineshadermanager_p.h
+++ b/src/opengl/gl2paintengineex/qglengineshadermanager_p.h
@@ -365,7 +365,6 @@ public:
void cleanupCustomStage(QGLCustomShaderStage* stage);
private:
- QGLSharedResourceGuard ctxGuard;
QGLShaderProgram *blitShaderProg;
QGLShaderProgram *simpleShaderProg;
QList<QGLEngineShaderProg*> cachedPrograms;
diff --git a/src/opengl/gl2paintengineex/qglgradientcache.cpp b/src/opengl/gl2paintengineex/qglgradientcache.cpp
index 9e6b801c40..6ca09ba140 100644
--- a/src/opengl/gl2paintengineex/qglgradientcache.cpp
+++ b/src/opengl/gl2paintengineex/qglgradientcache.cpp
@@ -51,21 +51,42 @@ class QGL2GradientCacheWrapper
public:
QGL2GradientCache *cacheForContext(const QGLContext *context) {
QMutexLocker lock(&m_mutex);
- return m_resource.value(context);
+ return m_resource.value<QGL2GradientCache>(context->contextHandle());
}
private:
- QGLContextGroupResource<QGL2GradientCache> m_resource;
+ QOpenGLMultiGroupSharedResource m_resource;
QMutex m_mutex;
};
Q_GLOBAL_STATIC(QGL2GradientCacheWrapper, qt_gradient_caches)
+QGL2GradientCache::QGL2GradientCache(QOpenGLContext *ctx)
+ : QOpenGLSharedResource(ctx->shareGroup())
+{
+}
+
+QGL2GradientCache::~QGL2GradientCache()
+{
+ cache.clear();
+}
+
QGL2GradientCache *QGL2GradientCache::cacheForContext(const QGLContext *context)
{
return qt_gradient_caches()->cacheForContext(context);
}
+void QGL2GradientCache::invalidateResource()
+{
+ QMutexLocker lock(&m_mutex);
+ cache.clear();
+}
+
+void QGL2GradientCache::freeResource(QOpenGLContext *)
+{
+ cleanCache();
+}
+
void QGL2GradientCache::cleanCache()
{
QMutexLocker lock(&m_mutex);
diff --git a/src/opengl/gl2paintengineex/qglgradientcache_p.h b/src/opengl/gl2paintengineex/qglgradientcache_p.h
index 1c2d0a029a..600085a75f 100644
--- a/src/opengl/gl2paintengineex/qglgradientcache_p.h
+++ b/src/opengl/gl2paintengineex/qglgradientcache_p.h
@@ -58,7 +58,7 @@
QT_BEGIN_NAMESPACE
-class QGL2GradientCache
+class QGL2GradientCache : public QOpenGLSharedResource
{
struct CacheInfo
{
@@ -76,12 +76,15 @@ class QGL2GradientCache
public:
static QGL2GradientCache *cacheForContext(const QGLContext *context);
- QGL2GradientCache(const QGLContext *) {}
- ~QGL2GradientCache() { cleanCache(); }
+ QGL2GradientCache(QOpenGLContext *);
+ ~QGL2GradientCache();
GLuint getBuffer(const QGradient &gradient, qreal opacity);
inline int paletteSize() const { return 1024; }
+ void invalidateResource();
+ void freeResource(QOpenGLContext *ctx);
+
private:
inline int maxCacheSize() const { return 60; }
inline void generateGradientColorTable(const QGradient& gradient,
diff --git a/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp b/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp
index d2c63ddc10..e6a12cd40c 100644
--- a/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp
+++ b/src/opengl/gl2paintengineex/qpaintengineex_opengl2.cpp
@@ -76,10 +76,9 @@
#include <QPaintEngine>
#include <private/qpainter_p.h>
#include <private/qfontengine_p.h>
-#include <private/qpixmapdata_gl_p.h>
#include <private/qdatabuffer_p.h>
#include <private/qstatictext_p.h>
-#include <private/qtriangulator_p.h>
+#include <QtGui/private/qtriangulator_p.h>
#include "qglengineshadermanager_p.h"
#include "qgl2pexvertexarray_p.h"
@@ -668,6 +667,7 @@ struct QGL2PEVectorPathCache
int indexCount;
GLenum primitiveType;
qreal iscale;
+ QVertexIndexVector::Type indexType;
};
void QGL2PaintEngineExPrivate::cleanupVectorPath(QPaintEngineEx *engine, void *data)
@@ -825,13 +825,14 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
cache->indexCount = polys.indices.size();
cache->primitiveType = GL_TRIANGLES;
cache->iscale = inverseScale;
+ cache->indexType = polys.indices.type();
#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);
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint)
+ if (polys.indices.type() == QVertexIndexVector::UnsignedInt)
glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(quint32) * polys.indices.size(), polys.indices.data(), GL_STATIC_DRAW);
else
glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(quint16) * polys.indices.size(), polys.indices.data(), GL_STATIC_DRAW);
@@ -842,7 +843,7 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
glBufferData(GL_ARRAY_BUFFER, sizeof(float) * vertices.size(), vertices.data(), GL_STATIC_DRAW);
#else
cache->vertices = (float *) qMalloc(sizeof(float) * polys.vertices.size());
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
+ if (polys.indices.type() == QVertexIndexVector::UnsignedInt) {
cache->indices = (quint32 *) qMalloc(sizeof(quint32) * polys.indices.size());
memcpy(cache->indices, polys.indices.data(), sizeof(quint32) * polys.indices.size());
} else {
@@ -859,7 +860,7 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
glBindBuffer(GL_ARRAY_BUFFER, cache->vbo);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, cache->ibo);
setVertexAttributePointer(QT_VERTEX_COORDS_ATTR, 0);
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint)
+ if (cache->indexType == QVertexIndexVector::UnsignedInt)
glDrawElements(cache->primitiveType, cache->indexCount, GL_UNSIGNED_INT, 0);
else
glDrawElements(cache->primitiveType, cache->indexCount, GL_UNSIGNED_SHORT, 0);
@@ -867,7 +868,7 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
glBindBuffer(GL_ARRAY_BUFFER, 0);
#else
setVertexAttributePointer(QT_VERTEX_COORDS_ATTR, cache->vertices);
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint)
+ if (cache->indexType == QVertexIndexVector::UnsignedInt)
glDrawElements(cache->primitiveType, cache->indexCount, GL_UNSIGNED_INT, (qint32 *)cache->indices);
else
glDrawElements(cache->primitiveType, cache->indexCount, GL_UNSIGNED_SHORT, (qint16 *)cache->indices);
@@ -896,7 +897,7 @@ void QGL2PaintEngineExPrivate::fill(const QVectorPath& path)
prepareForDraw(currentBrush.isOpaque());
setVertexAttributePointer(QT_VERTEX_COORDS_ATTR, vertices.constData());
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint)
+ if (polys.indices.type() == QVertexIndexVector::UnsignedInt)
glDrawElements(GL_TRIANGLES, polys.indices.size(), GL_UNSIGNED_INT, polys.indices.data());
else
glDrawElements(GL_TRIANGLES, polys.indices.size(), GL_UNSIGNED_SHORT, polys.indices.data());
@@ -1581,10 +1582,9 @@ void QGL2PaintEngineExPrivate::drawCachedGlyphs(QFontEngineGlyphCache::Type glyp
QGLTextureGlyphCache *cache =
(QGLTextureGlyphCache *) staticTextItem->fontEngine()->glyphCache(cacheKey, glyphType, QTransform());
- if (!cache || cache->cacheType() != glyphType || cache->context() == 0) {
- cache = new QGLTextureGlyphCache(ctx, glyphType, QTransform());
+ if (!cache || cache->cacheType() != glyphType || cache->contextGroup() == 0) {
+ cache = new QGLTextureGlyphCache(glyphType, QTransform());
staticTextItem->fontEngine()->setGlyphCache(cacheKey, cache);
- cache->insert(ctx, cache);
recreateVertexArrays = true;
}
@@ -2048,21 +2048,13 @@ bool QGL2PaintEngineEx::begin(QPaintDevice *pdev)
bool QGL2PaintEngineEx::end()
{
Q_D(QGL2PaintEngineEx);
- QGLContext *ctx = d->ctx;
+ QGLContext *ctx = d->ctx;
glUseProgram(0);
d->transferMode(BrushDrawingMode);
d->device->endPaint();
-#if defined(Q_WS_X11)
- // On some (probably all) drivers, deleting an X pixmap which has been bound to a texture
- // before calling glFinish/swapBuffers renders garbage. Presumably this is because X deletes
- // the pixmap behind the driver's back before it's had a chance to use it. To fix this, we
- // reference all QPixmaps which have been bound to stop them being deleted and only deref
- // them here, after swapBuffers, where they can be safely deleted.
- ctx->d_func()->boundPixmaps.clear();
-#endif
- d->ctx->d_ptr->active_engine = 0;
+ ctx->d_ptr->active_engine = 0;
d->resetGLState();
@@ -2335,8 +2327,8 @@ void QGL2PaintEngineExPrivate::systemStateChanged()
if (systemClip.isEmpty()) {
useSystemClip = false;
} else {
- if (q->paintDevice()->devType() == QInternal::Widget && currentClipWidget) {
- QWidgetPrivate *widgetPrivate = qt_widget_private(currentClipWidget->window());
+ if (q->paintDevice()->devType() == QInternal::Widget && currentClipDevice) {
+ QWidgetPrivate *widgetPrivate = qt_widget_private(static_cast<QWidget *>(currentClipDevice)->window());
useSystemClip = widgetPrivate->extra && widgetPrivate->extra->inRenderWithPainter;
} else {
useSystemClip = true;
diff --git a/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h b/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h
index 2895d5a9b0..dbf760929c 100644
--- a/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h
+++ b/src/opengl/gl2paintengineex/qpaintengineex_opengl2_p.h
@@ -59,7 +59,6 @@
#include <private/qglengineshadermanager_p.h>
#include <private/qgl2pexvertexarray_p.h>
#include <private/qglpaintdevice_p.h>
-#include <private/qglpixmapfilter_p.h>
#include <private/qfontengine_p.h>
#include <private/qdatabuffer_p.h>
#include <private/qtriangulatingstroker_p.h>
@@ -153,8 +152,6 @@ public:
void invalidateState();
- QPixmapFilter *pixmapFilter(int type, const QPixmapFilter *prototype);
-
void setRenderTextActive(bool);
bool isNativePaintingActive() const;
@@ -302,11 +299,6 @@ public:
QTriangulatingStroker stroker;
QDashedStrokeProcessor dasher;
- QScopedPointer<QPixmapFilter> convolutionFilter;
- QScopedPointer<QPixmapFilter> colorizeFilter;
- QScopedPointer<QPixmapFilter> blurFilter;
- QScopedPointer<QPixmapFilter> dropShadowFilter;
-
QSet<QVectorPath::CacheEntry *> pathCaches;
QVector<GLuint> unusedVBOSToClean;
QVector<GLuint> unusedIBOSToClean;
diff --git a/src/opengl/gl2paintengineex/qrbtree_p.h b/src/opengl/gl2paintengineex/qrbtree_p.h
deleted file mode 100644
index 09ef81cdbb..0000000000
--- a/src/opengl/gl2paintengineex/qrbtree_p.h
+++ /dev/null
@@ -1,573 +0,0 @@
-/****************************************************************************
-**
-** Copyright (C) 2011 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$
-** GNU Lesser General Public License Usage
-** 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.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU General
-** Public License version 3.0 as published by the Free Software Foundation
-** and appearing in the file LICENSE.GPL included in the packaging of this
-** file. Please review the following information to ensure the GNU General
-** Public License version 3.0 requirements will be met:
-** http://www.gnu.org/copyleft/gpl.html.
-**
-** Other Usage
-** Alternatively, this file may be used in accordance with the terms and
-** conditions contained in a signed written agreement between you and Nokia.
-**
-**
-**
-**
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
-
-#ifndef QRBTREE_P_H
-#define QRBTREE_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/qglobal.h>
-
-QT_BEGIN_NAMESPACE
-
-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 validate() 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>::validate() 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;
-}
-
-QT_END_NAMESPACE
-
-#endif
diff --git a/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp b/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp
index dbed354dfb..af6cb53a3a 100644
--- a/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp
+++ b/src/opengl/gl2paintengineex/qtextureglyphcache_gl.cpp
@@ -43,10 +43,6 @@
#include "qpaintengineex_opengl2_p.h"
#include "private/qglengineshadersource_p.h"
-#if defined QT_OPENGL_ES_2 && !defined(QT_NO_EGL)
-#include "private/qeglcontext_p.h"
-#endif
-
QT_BEGIN_NAMESPACE
#ifdef Q_WS_WIN
@@ -55,19 +51,16 @@ extern Q_GUI_EXPORT bool qt_cleartype_enabled;
QBasicAtomicInt qgltextureglyphcache_serial_number = Q_BASIC_ATOMIC_INITIALIZER(1);
-QGLTextureGlyphCache::QGLTextureGlyphCache(const QGLContext *context, QFontEngineGlyphCache::Type type, const QTransform &matrix)
- : QImageTextureGlyphCache(type, matrix), QGLContextGroupResourceBase()
- , ctx(0)
+QGLTextureGlyphCache::QGLTextureGlyphCache(QFontEngineGlyphCache::Type type, const QTransform &matrix)
+ : QImageTextureGlyphCache(type, matrix)
, pex(0)
, m_blitProgram(0)
, m_filterMode(Nearest)
, m_serialNumber(qgltextureglyphcache_serial_number.fetchAndAddRelaxed(1))
{
#ifdef QT_GL_TEXTURE_GLYPH_CACHE_DEBUG
- qDebug(" -> QGLTextureGlyphCache() %p for context %p.", this, ctx);
+ qDebug(" -> QGLTextureGlyphCache() %p for context %p.", this, QOpenGLContext::currentContext());
#endif
- setContext(context);
-
m_vertexCoordinateArray[0] = -1.0f;
m_vertexCoordinateArray[1] = -1.0f;
m_vertexCoordinateArray[2] = 1.0f;
@@ -95,14 +88,9 @@ QGLTextureGlyphCache::~QGLTextureGlyphCache()
delete m_blitProgram;
}
-void QGLTextureGlyphCache::setContext(const QGLContext *context)
-{
- ctx = context;
- m_h = 0;
-}
-
void QGLTextureGlyphCache::createTextureData(int width, int height)
{
+ QGLContext *ctx = const_cast<QGLContext *>(QGLContext::currentContext());
if (ctx == 0) {
qWarning("QGLTextureGlyphCache::createTextureData: Called with no context");
return;
@@ -120,12 +108,17 @@ void QGLTextureGlyphCache::createTextureData(int width, int height)
if (height < 16)
height = 16;
- QGLGlyphTexture *glyphTexture = m_textureResource.value(ctx);
- glGenTextures(1, &glyphTexture->m_texture);
- glBindTexture(GL_TEXTURE_2D, glyphTexture->m_texture);
+ if (m_textureResource && !m_textureResource->m_texture)
+ delete m_textureResource;
+
+ if (!m_textureResource)
+ m_textureResource = new QGLGlyphTexture(ctx);
+
+ glGenTextures(1, &m_textureResource->m_texture);
+ glBindTexture(GL_TEXTURE_2D, m_textureResource->m_texture);
- glyphTexture->m_width = width;
- glyphTexture->m_height = height;
+ m_textureResource->m_width = width;
+ m_textureResource->m_height = height;
if (m_type == QFontEngineGlyphCache::Raster_RGBMask) {
QVarLengthArray<uchar> data(width * height * 4);
@@ -148,14 +141,14 @@ void QGLTextureGlyphCache::createTextureData(int width, int height)
void QGLTextureGlyphCache::resizeTextureData(int width, int height)
{
+ QGLContext *ctx = const_cast<QGLContext *>(QGLContext::currentContext());
if (ctx == 0) {
qWarning("QGLTextureGlyphCache::resizeTextureData: Called with no context");
return;
}
- QGLGlyphTexture *glyphTexture = m_textureResource.value(ctx);
- int oldWidth = glyphTexture->m_width;
- int oldHeight = glyphTexture->m_height;
+ int oldWidth = m_textureResource->m_width;
+ int oldHeight = m_textureResource->m_height;
// Make the lower glyph texture size 16 x 16.
if (width < 16)
@@ -163,7 +156,7 @@ void QGLTextureGlyphCache::resizeTextureData(int width, int height)
if (height < 16)
height = 16;
- GLuint oldTexture = glyphTexture->m_texture;
+ GLuint oldTexture = m_textureResource->m_texture;
createTextureData(width, height);
if (ctx->d_ptr->workaround_brokenFBOReadBack) {
@@ -177,7 +170,7 @@ void QGLTextureGlyphCache::resizeTextureData(int width, int height)
// ### the QTextureGlyphCache API needs to be reworked to allow
// ### resizeTextureData to fail
- glBindFramebuffer(GL_FRAMEBUFFER_EXT, glyphTexture->m_fbo);
+ glBindFramebuffer(GL_FRAMEBUFFER_EXT, m_textureResource->m_fbo);
GLuint tmp_texture;
glGenTextures(1, &tmp_texture);
@@ -261,7 +254,7 @@ void QGLTextureGlyphCache::resizeTextureData(int width, int height)
glDrawArrays(GL_TRIANGLE_FAN, 0, 4);
- glBindTexture(GL_TEXTURE_2D, glyphTexture->m_texture);
+ glBindTexture(GL_TEXTURE_2D, m_textureResource->m_texture);
glCopyTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, 0, 0, oldWidth, oldHeight);
@@ -280,16 +273,16 @@ void QGLTextureGlyphCache::resizeTextureData(int width, int height)
void QGLTextureGlyphCache::fillTexture(const Coord &c, glyph_t glyph, QFixed subPixelPosition)
{
+ QGLContext *ctx = const_cast<QGLContext *>(QGLContext::currentContext());
if (ctx == 0) {
qWarning("QGLTextureGlyphCache::fillTexture: Called with no context");
return;
}
- QGLGlyphTexture *glyphTexture = m_textureResource.value(ctx);
if (ctx->d_ptr->workaround_brokenFBOReadBack) {
QImageTextureGlyphCache::fillTexture(c, glyph, subPixelPosition);
- glBindTexture(GL_TEXTURE_2D, glyphTexture->m_texture);
+ glBindTexture(GL_TEXTURE_2D, m_textureResource->m_texture);
const QImage &texture = image();
const uchar *bits = texture.constBits();
bits += c.y * texture.bytesPerLine() + c.x;
@@ -326,7 +319,7 @@ void QGLTextureGlyphCache::fillTexture(const Coord &c, glyph_t glyph, QFixed sub
}
}
- glBindTexture(GL_TEXTURE_2D, glyphTexture->m_texture);
+ glBindTexture(GL_TEXTURE_2D, m_textureResource->m_texture);
if (mask.format() == QImage::Format_RGB32) {
glTexSubImage2D(GL_TEXTURE_2D, 0, c.x, c.y, maskWidth, maskHeight, GL_BGRA, GL_UNSIGNED_BYTE, mask.bits());
} else {
@@ -362,6 +355,7 @@ int QGLTextureGlyphCache::glyphPadding() const
int QGLTextureGlyphCache::maxTextureWidth() const
{
+ QGLContext *ctx = const_cast<QGLContext *>(QGLContext::currentContext());
if (ctx == 0)
return QImageTextureGlyphCache::maxTextureWidth();
else
@@ -370,6 +364,7 @@ int QGLTextureGlyphCache::maxTextureWidth() const
int QGLTextureGlyphCache::maxTextureHeight() const
{
+ QGLContext *ctx = const_cast<QGLContext *>(QGLContext::currentContext());
if (ctx == 0)
return QImageTextureGlyphCache::maxTextureHeight();
@@ -381,16 +376,15 @@ int QGLTextureGlyphCache::maxTextureHeight() const
void QGLTextureGlyphCache::clear()
{
- if (ctx != 0) {
- m_textureResource.cleanup(ctx);
-
- m_w = 0;
- m_h = 0;
- m_cx = 0;
- m_cy = 0;
- m_currentRowHeight = 0;
- coords.clear();
- }
+ m_textureResource->free();
+ m_textureResource = 0;
+
+ m_w = 0;
+ m_h = 0;
+ m_cx = 0;
+ m_cy = 0;
+ m_currentRowHeight = 0;
+ coords.clear();
}
QT_END_NAMESPACE
diff --git a/src/opengl/gl2paintengineex/qtextureglyphcache_gl_p.h b/src/opengl/gl2paintengineex/qtextureglyphcache_gl_p.h
index 83ca06d040..7b7da9d8e8 100644
--- a/src/opengl/gl2paintengineex/qtextureglyphcache_gl_p.h
+++ b/src/opengl/gl2paintengineex/qtextureglyphcache_gl_p.h
@@ -63,10 +63,11 @@ QT_BEGIN_NAMESPACE
class QGL2PaintEngineExPrivate;
-struct QGLGlyphTexture
+struct QGLGlyphTexture : public QOpenGLSharedResource
{
QGLGlyphTexture(const QGLContext *ctx)
- : m_width(0)
+ : QOpenGLSharedResource(ctx->contextHandle()->shareGroup())
+ , m_width(0)
, m_height(0)
{
if (ctx && !ctx->d_ptr->workaround_brokenFBOReadBack)
@@ -77,19 +78,24 @@ struct QGLGlyphTexture
#endif
}
- ~QGLGlyphTexture() {
- const QGLContext *ctx = QGLContext::currentContext();
+ void freeResource(QOpenGLContext *context)
+ {
+ const QGLContext *ctx = QGLContext::fromOpenGLContext(context);
#ifdef QT_GL_TEXTURE_GLYPH_CACHE_DEBUG
qDebug("~QGLGlyphTexture() %p for context %p.", this, ctx);
#endif
- // At this point, the context group is made current, so it's safe to
- // release resources without a makeCurrent() call
- if (ctx) {
- if (!ctx->d_ptr->workaround_brokenFBOReadBack)
- glDeleteFramebuffers(1, &m_fbo);
- if (m_width || m_height)
- glDeleteTextures(1, &m_texture);
- }
+ if (!ctx->d_ptr->workaround_brokenFBOReadBack)
+ glDeleteFramebuffers(1, &m_fbo);
+ if (m_width || m_height)
+ glDeleteTextures(1, &m_texture);
+ }
+
+ void invalidateResource()
+ {
+ m_texture = 0;
+ m_fbo = 0;
+ m_width = 0;
+ m_height = 0;
}
GLuint m_texture;
@@ -98,10 +104,10 @@ struct QGLGlyphTexture
int m_height;
};
-class Q_OPENGL_EXPORT QGLTextureGlyphCache : public QImageTextureGlyphCache, public QGLContextGroupResourceBase
+class Q_OPENGL_EXPORT QGLTextureGlyphCache : public QImageTextureGlyphCache
{
public:
- QGLTextureGlyphCache(const QGLContext *context, QFontEngineGlyphCache::Type type, const QTransform &matrix);
+ QGLTextureGlyphCache(QFontEngineGlyphCache::Type type, const QTransform &matrix);
~QGLTextureGlyphCache();
virtual void createTextureData(int width, int height);
@@ -113,25 +119,24 @@ public:
inline GLuint texture() const {
QGLTextureGlyphCache *that = const_cast<QGLTextureGlyphCache *>(this);
- QGLGlyphTexture *glyphTexture = that->m_textureResource.value(ctx);
+ QGLGlyphTexture *glyphTexture = that->m_textureResource;
return glyphTexture ? glyphTexture->m_texture : 0;
}
inline int width() const {
QGLTextureGlyphCache *that = const_cast<QGLTextureGlyphCache *>(this);
- QGLGlyphTexture *glyphTexture = that->m_textureResource.value(ctx);
+ QGLGlyphTexture *glyphTexture = that->m_textureResource;
return glyphTexture ? glyphTexture->m_width : 0;
}
inline int height() const {
QGLTextureGlyphCache *that = const_cast<QGLTextureGlyphCache *>(this);
- QGLGlyphTexture *glyphTexture = that->m_textureResource.value(ctx);
+ QGLGlyphTexture *glyphTexture = that->m_textureResource;
return glyphTexture ? glyphTexture->m_height : 0;
}
inline void setPaintEnginePrivate(QGL2PaintEngineExPrivate *p) { pex = p; }
- void setContext(const QGLContext *context);
- inline const QGLContext *context() const { return ctx; }
+ inline const QOpenGLContextGroup *contextGroup() const { return m_textureResource ? m_textureResource->group() : 0; }
inline int serialNumber() const { return m_serialNumber; }
@@ -144,12 +149,9 @@ public:
void clear();
- void freeResource(void *) { ctx = 0; }
-
private:
- QGLContextGroupResource<QGLGlyphTexture> m_textureResource;
+ QGLGlyphTexture *m_textureResource;
- const QGLContext *ctx;
QGL2PaintEngineExPrivate *pex;
QGLShaderProgram *m_blitProgram;
FilterMode m_filterMode;
diff --git a/src/opengl/gl2paintengineex/qtriangulator.cpp b/src/opengl/gl2paintengineex/qtriangulator.cpp
deleted file mode 100644
index d4b7131794..0000000000
--- a/src/opengl/gl2paintengineex/qtriangulator.cpp
+++ /dev/null
@@ -1,2612 +0,0 @@
-/****************************************************************************
-**
-** Copyright (C) 2011 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$
-** GNU Lesser General Public License Usage
-** 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.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU General
-** Public License version 3.0 as published by the Free Software Foundation
-** and appearing in the file LICENSE.GPL included in the packaging of this
-** file. Please review the following information to ensure the GNU General
-** Public License version 3.0 requirements will be met:
-** http://www.gnu.org/copyleft/gpl.html.
-**
-** Other Usage
-** Alternatively, this file may be used in accordance with the terms and
-** conditions contained in a signed written agreement between you and Nokia.
-**
-**
-**
-**
-**
-** $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 <private/qgl_p.h>
-#include <private/qrbtree_p.h>
-
-#include <math.h>
-
-QT_BEGIN_NAMESPACE
-
-//#define Q_TRIANGULATOR_DEBUG
-
-#define Q_FIXED_POINT_SCALE 32
-
-// Quick sort.
-template <class T, class LessThan>
-#ifdef Q_CC_RVCT // RVCT 2.2 doesn't see recursive _static_ template function
-void sort(T *array, int count, LessThan lessThan)
-#else
-static void sort(T *array, int count, LessThan lessThan)
-#endif
-{
- // 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>
-#ifdef Q_CC_RVCT
-void sort(T *array, int count) // RVCT 2.2 doesn't see recursive _static_ template function
-#else
-static void sort(T *array, int count)
-#endif
-{
- // 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);
-}
-
-template<typename T>
-struct QVertexSet
-{
- inline QVertexSet() { }
- inline QVertexSet(const QVertexSet<T> &other) : vertices(other.vertices), indices(other.indices) { }
- QVertexSet<T> &operator = (const QVertexSet<T> &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<T> indices; // [i[0], j[0], k[0], i[1], j[1], k[1], i[2], ...]
-};
-
-//============================================================================//
-// 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 QT_PREPEND_NAMESPACE(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:
- QMaxHeap() : m_data(0) {}
- 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;
-}
-
-//============================================================================//
-// 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 //
-//============================================================================//
-template<typename T>
-class QTriangulator
-{
-public:
- typedef QVarLengthArray<int, 6> ShortArray;
-
- //================================//
- // QTriangulator::ComplexToSimple //
- //================================//
- friend class ComplexToSimple;
- class ComplexToSimple
- {
- public:
- inline ComplexToSimple(QTriangulator<T> *parent) : m_parent(parent),
- m_edges(0), m_events(0), m_splits(0) { }
- 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<T> *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { }
- void decompose();
- private:
- enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex};
-
- struct Edge
- {
- QRBTree<int>::Node *node;
- int helper, twin, next, previous;
- T 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<T> *parent) : m_parent(parent) { }
- void decompose();
- private:
- inline T 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((qint32)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((qint32)indices(i)),
- m_parent->m_vertices.at((qint32)indices(j)), m_parent->m_vertices.at((qint32)indices(k)));
- }
-
- QTriangulator<T> *m_parent;
- int m_first;
- int m_length;
- };
-
- inline QTriangulator() : m_vertices(0) { }
-
- // 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.
- QVertexSet<T> triangulate();
- QVertexSet<T> polyline();
-private:
- QDataBuffer<QPodPoint> m_vertices;
- QVector<T> m_indices;
- uint m_hint;
-};
-
-//============================================================================//
-// QTriangulator //
-//============================================================================//
-
-template <typename T>
-QVertexSet<T> QTriangulator<T>::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();
-
- QVertexSet<T> 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;
-}
-
-template <typename T>
-QVertexSet<T> QTriangulator<T>::polyline()
-{
- 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();
- }
-
- QVertexSet<T> 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;
-}
-
-template <typename T>
-void QTriangulator<T>::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] = T(-1); //Q_TRIANGULATE_END_OF_POLYGON
-}
-
-template <typename T>
-void QTriangulator<T>::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(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
- // Fall through.
- case QPainterPath::LineToElement:
- m_indices.push_back(T(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(T(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(T(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(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
-}
-
-template <typename T>
-void QTriangulator<T>::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod)
-{
- initialize(qtVectorPathForPath(path), matrix, lod);
-}
-
-//============================================================================//
-// QTriangulator::ComplexToSimple //
-//============================================================================//
-template <typename T>
-void QTriangulator<T>::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(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
- }
-}
-
-template <typename T>
-void QTriangulator<T>::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) == T(-1)) { // 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
-template <typename T>
-bool QTriangulator<T>::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((qint32)e1.from);
- const QPodPoint &u2 = m_parent->m_vertices.at((qint32)e1.to);
- const QPodPoint &v1 = m_parent->m_vertices.at((qint32)e2.from);
- const QPodPoint &v2 = m_parent->m_vertices.at((qint32)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 = QT_PREPEND_NAMESPACE(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;
-}
-
-template <typename T>
-bool QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(upper, l, u);
- // d < 0: left, d > 0: right, d == 0: on top
- if (d == 0)
- d = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.lower()), l, u);
- return d < 0;
-}
-
-template <typename T>
-QRBTree<int>::Node *QTriangulator<T>::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;
-}
-
-template <typename T>
-QRBTree<int>::Node *QTriangulator<T>::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;
-}
-
-template <typename T>
-QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
- Q_ASSERT(d <= 0);
- if (d == 0) {
- result.second = current;
- current = current->right;
- } else {
- current = current->left;
- }
- }
-
- return result;
-}
-
-template <typename T>
-QPair<QRBTree<int>::Node *, QRBTree<int>::Node *> QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(point, v1, v2);
- Q_ASSERT(d <= 0);
- if (d == 0) {
- current = current->right;
- } else {
- result.second = current;
- current = current->left;
- }
- }
-
- return result;
-}
-
-template <typename T>
-void QTriangulator<T>::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);
- }
-}
-
-template <typename T>
-void QTriangulator<T>::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);
-}
-
-template <typename T>
-void QTriangulator<T>::ComplexToSimple::sortEdgeList(const QPodPoint eventPoint)
-{
- QIntersectionPoint eventPoint2 = QT_PREPEND_NAMESPACE(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((qint32)edge.from);
- const QPodPoint &v = m_parent->m_vertices.at((qint32)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((qint32)edge.from);
- const QPodPoint &v = m_parent->m_vertices.at((qint32)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
-
- }
-}
-
-template <typename T>
-void QTriangulator<T>::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());
-}
-
-template <typename T>
-void QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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'.
-template <typename T>
-int QTriangulator<T>::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;
- }
-}
-
-template <typename T>
-bool QTriangulator<T>::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;
-}
-
-template <typename T>
-void QTriangulator<T>::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);
-}
-
-template <typename T>
-void QTriangulator<T>::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(QT_PREPEND_NAMESPACE(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
-}
-
-template <typename T>
-void QTriangulator<T>::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);
- }
-}
-
-template <typename T>
-bool QTriangulator<T>::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;
-}
-
-template <typename T>
-inline bool QTriangulator<T>::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
-template <typename T>
-QTriangulator<T>::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));
-}
-
-template <typename T>
-void QTriangulator<T>::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);
- }
-}
-
-template <typename T>
-void QTriangulator<T>::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();
-}
-
-template <typename T>
-void QTriangulator<T>::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();
- }
-}
-
-template <typename T>
-void QTriangulator<T>::ComplexToSimple::DebugDialog::mousePressEvent(QMouseEvent *event)
-{
- if (event->button() == Qt::LeftButton)
- m_lastMousePos = event->pos();
- event->accept();
-}
-
-
-#endif
-
-//============================================================================//
-// QTriangulator::SimpleToMonotone //
-//============================================================================//
-template <typename T>
-void QTriangulator<T>::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() != T(-1)) // Q_TRIANGULATE_END_OF_POLYGON
- m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON
- }
-}
-
-template <typename T>
-void QTriangulator<T>::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) != T(-1)); // 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.
- }
-}
-
-template <typename T>
-void QTriangulator<T>::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);
- }
-}
-
-template <typename T>
-void QTriangulator<T>::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)));
- //}
-}
-
-template <typename T>
-bool QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(leftEdge.upper()), l, u);
- // d < 0: left, d > 0: right, d == 0: on top
- if (d == 0)
- d = QT_PREPEND_NAMESPACE(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.
-template <typename T>
-QRBTree<int>::Node *QTriangulator<T>::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.
-template <typename T>
-QRBTree<int>::Node *QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(m_parent->m_vertices.at(pointIndex), p1, p2);
- if (d <= 0) {
- current = current->left;
- } else {
- result = current;
- current = current->right;
- }
- }
- return result;
-}
-
-template <typename T>
-void QTriangulator<T>::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 = QT_PREPEND_NAMESPACE(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);
- }
-}
-
-template <typename T>
-void QTriangulator<T>::SimpleToMonotone::classifyVertices()
-{
- for (int i = 0; i < m_edges.size(); ++i)
- classifyVertex(i);
-}
-
-template <typename T>
-bool QTriangulator<T>::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;
-}
-
-template <typename T>
-bool QTriangulator<T>::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);
-}
-
-template <typename T>
-int QTriangulator<T>::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;
-}
-
-template <typename T>
-void QTriangulator<T>::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);
-}
-
-template <typename T>
-void QTriangulator<T>::SimpleToMonotone::monotoneDecomposition()
-{
- if (m_edges.isEmpty())
- return;
-
- Q_ASSERT(!m_edgeList.root);
- QDataBuffer<QPair<int, int> > diagonals(m_upperVertex.size());
-
- 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((quint32)m_edges.at(i).from),
- m_parent->m_vertices.at((quint32)m_edges.at(j).from), m_parent->m_vertices.at((quint32)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.validate());
- } 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.validate());
- }
- 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.validate());
- } 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.validate());
- } else {
- qWarning("Inconsistent polygon. (#6)");
- }
- }
- break;
- }
- }
-
- for (int i = 0; i < diagonals.size(); ++i)
- createDiagonal(diagonals.at(i).first, diagonals.at(i).second);
-}
-
-template <typename T>
-bool QTriangulator<T>::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 //
-//============================================================================//
-template <typename T>
-void QTriangulator<T>::MonotoneToTriangles::decompose()
-{
- QVector<T> result;
- QDataBuffer<int> stack(m_parent->m_indices.size());
- 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) != T(-1)) { // 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)
-{
- QTriangleSet triangleSet;
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
- QTriangulator<quint32> triangulator;
- triangulator.initialize(polygon, count, hint, matrix);
- QVertexSet<quint32> vertexSet = triangulator.triangulate();
- triangleSet.vertices = vertexSet.vertices;
- triangleSet.indices.setDataUint(vertexSet.indices);
-
- } else {
- QTriangulator<quint16> triangulator;
- triangulator.initialize(polygon, count, hint, matrix);
- QVertexSet<quint16> vertexSet = triangulator.triangulate();
- triangleSet.vertices = vertexSet.vertices;
- triangleSet.indices.setDataUshort(vertexSet.indices);
- }
- return triangleSet;
-}
-
-QTriangleSet qTriangulate(const QVectorPath &path,
- const QTransform &matrix, qreal lod)
-{
- QTriangleSet triangleSet;
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
- QTriangulator<quint32> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint32> vertexSet = triangulator.triangulate();
- triangleSet.vertices = vertexSet.vertices;
- triangleSet.indices.setDataUint(vertexSet.indices);
- } else {
- QTriangulator<quint16> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint16> vertexSet = triangulator.triangulate();
- triangleSet.vertices = vertexSet.vertices;
- triangleSet.indices.setDataUshort(vertexSet.indices);
- }
- return triangleSet;
-}
-
-QTriangleSet qTriangulate(const QPainterPath &path,
- const QTransform &matrix, qreal lod)
-{
- QTriangleSet triangleSet;
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
- QTriangulator<quint32> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint32> vertexSet = triangulator.triangulate();
- triangleSet.vertices = vertexSet.vertices;
- triangleSet.indices.setDataUint(vertexSet.indices);
- } else {
- QTriangulator<quint16> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint16> vertexSet = triangulator.triangulate();
- triangleSet.vertices = vertexSet.vertices;
- triangleSet.indices.setDataUshort(vertexSet.indices);
- }
- return triangleSet;
-}
-
-QPolylineSet qPolyline(const QVectorPath &path,
- const QTransform &matrix, qreal lod)
-{
- QPolylineSet polyLineSet;
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
- QTriangulator<quint32> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint32> vertexSet = triangulator.polyline();
- polyLineSet.vertices = vertexSet.vertices;
- polyLineSet.indices.setDataUint(vertexSet.indices);
- } else {
- QTriangulator<quint16> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint16> vertexSet = triangulator.polyline();
- polyLineSet.vertices = vertexSet.vertices;
- polyLineSet.indices.setDataUshort(vertexSet.indices);
- }
- return polyLineSet;
-}
-
-QPolylineSet qPolyline(const QPainterPath &path,
- const QTransform &matrix, qreal lod)
-{
- QPolylineSet polyLineSet;
- if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
- QTriangulator<quint32> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint32> vertexSet = triangulator.polyline();
- polyLineSet.vertices = vertexSet.vertices;
- polyLineSet.indices.setDataUint(vertexSet.indices);
- } else {
- QTriangulator<quint16> triangulator;
- triangulator.initialize(path, matrix, lod);
- QVertexSet<quint16> vertexSet = triangulator.polyline();
- polyLineSet.vertices = vertexSet.vertices;
- polyLineSet.indices.setDataUshort(vertexSet.indices);
- }
- return polyLineSet;
-}
-
-QT_END_NAMESPACE
diff --git a/src/opengl/gl2paintengineex/qtriangulator_p.h b/src/opengl/gl2paintengineex/qtriangulator_p.h
deleted file mode 100644
index 04a219c255..0000000000
--- a/src/opengl/gl2paintengineex/qtriangulator_p.h
+++ /dev/null
@@ -1,148 +0,0 @@
-/****************************************************************************
-**
-** Copyright (C) 2011 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$
-** GNU Lesser General Public License Usage
-** 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.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU General
-** Public License version 3.0 as published by the Free Software Foundation
-** and appearing in the file LICENSE.GPL included in the packaging of this
-** file. Please review the following information to ensure the GNU General
-** Public License version 3.0 requirements will be met:
-** http://www.gnu.org/copyleft/gpl.html.
-**
-** Other Usage
-** Alternatively, this file may be used in accordance with the terms and
-** conditions contained in a signed written agreement between you and Nokia.
-**
-**
-**
-**
-**
-** $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
-
-class Q_OPENGL_EXPORT QVertexIndexVector
-{
-public:
- enum Type {
- UnsignedInt,
- UnsignedShort
- };
-
- inline Type type() const { return t; }
-
- inline void setDataUint(const QVector<quint32> &data)
- {
- t = UnsignedInt;
- indices32 = data;
- }
-
- inline void setDataUshort(const QVector<quint16> &data)
- {
- t = UnsignedShort;
- indices16 = data;
- }
-
- inline const void* data() const
- {
- if (t == UnsignedInt)
- return indices32.data();
- return indices16.data();
- }
-
- inline int size() const
- {
- if (t == UnsignedInt)
- return indices32.size();
- return indices16.size();
- }
-
- inline QVertexIndexVector &operator = (const QVertexIndexVector &other)
- {
- if (t == UnsignedInt)
- indices32 = other.indices32;
- else
- indices16 = other.indices16;
-
- return *this;
- }
-
-private:
-
- Type t;
- QVector<quint32> indices32;
- QVector<quint16> indices16;
-};
-
-struct Q_OPENGL_EXPORT 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], ...]
- QVertexIndexVector indices; // [i[0], j[0], k[0], i[1], j[1], k[1], i[2], ...]
-};
-
-struct Q_OPENGL_EXPORT 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], ...]
- QVertexIndexVector indices; // End of polyline is marked with -1.
-};
-
-// 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 Q_OPENGL_EXPORT qTriangulate(const QPainterPath &path, const QTransform &matrix = QTransform(), qreal lod = 1);
-QPolylineSet qPolyline(const QVectorPath &path, const QTransform &matrix = QTransform(), qreal lod = 1);
-QPolylineSet Q_OPENGL_EXPORT qPolyline(const QPainterPath &path, const QTransform &matrix = QTransform(), qreal lod = 1);
-
-QT_END_NAMESPACE
-
-#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-01 23:37:30 +0000