diff options
Diffstat (limited to 'src/gui/opengl')
| -rw-r--r-- | src/gui/opengl/opengl.pri | 5 | ||||
| -rw-r--r-- | src/gui/opengl/qrbtree_p.h | 571 | ||||
| -rw-r--r-- | src/gui/opengl/qtriangulatingstroker.cpp | 613 | ||||
| -rw-r--r-- | src/gui/opengl/qtriangulatingstroker_p.h | 171 | ||||
| -rw-r--r-- | src/gui/opengl/qtriangulator.cpp | 2377 | ||||
| -rw-r--r-- | src/gui/opengl/qtriangulator_p.h | 148 |
6 files changed, 0 insertions, 3885 deletions
diff --git a/src/gui/opengl/opengl.pri b/src/gui/opengl/opengl.pri index dfaf3042bc..bdda5381ce 100644 --- a/src/gui/opengl/opengl.pri +++ b/src/gui/opengl/opengl.pri @@ -22,12 +22,9 @@ contains(QT_CONFIG, opengl)|contains(QT_CONFIG, opengles2) { opengl/qopenglpaintengine_p.h \ opengl/qopenglengineshadersource_p.h \ opengl/qopenglcustomshaderstage_p.h \ - opengl/qtriangulatingstroker_p.h \ opengl/qopengltextureglyphcache_p.h \ opengl/qopenglshadercache_p.h \ opengl/qopenglshadercache_meego_p.h \ - opengl/qtriangulator_p.h \ - opengl/qrbtree_p.h \ opengl/qopenglversionfunctions.h \ opengl/qopenglversionfunctionsfactory_p.h \ opengl/qopenglvertexarrayobject.h \ @@ -51,9 +48,7 @@ contains(QT_CONFIG, opengl)|contains(QT_CONFIG, opengles2) { opengl/qopengl2pexvertexarray.cpp \ opengl/qopenglpaintengine.cpp \ opengl/qopenglcustomshaderstage.cpp \ - opengl/qtriangulatingstroker.cpp \ opengl/qopengltextureglyphcache.cpp \ - opengl/qtriangulator.cpp \ opengl/qopenglversionfunctions.cpp \ opengl/qopenglversionfunctionsfactory.cpp \ opengl/qopenglvertexarrayobject.cpp \ diff --git a/src/gui/opengl/qrbtree_p.h b/src/gui/opengl/qrbtree_p.h deleted file mode 100644 index d3ee23a91c..0000000000 --- a/src/gui/opengl/qrbtree_p.h +++ /dev/null @@ -1,571 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $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 <QtGui/private/qtguiglobal_p.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/gui/opengl/qtriangulatingstroker.cpp b/src/gui/opengl/qtriangulatingstroker.cpp deleted file mode 100644 index d9a3231165..0000000000 --- a/src/gui/opengl/qtriangulatingstroker.cpp +++ /dev/null @@ -1,613 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#include "qtriangulatingstroker_p.h" -#include <qmath.h> - -QT_BEGIN_NAMESPACE - -#define CURVE_FLATNESS Q_PI / 8 - - - - -void QTriangulatingStroker::endCapOrJoinClosed(const qreal *start, const qreal *cur, - bool implicitClose, bool endsAtStart) -{ - if (endsAtStart) { - join(start + 2); - } else if (implicitClose) { - join(start); - lineTo(start); - join(start+2); - } else { - endCap(cur); - } - int count = m_vertices.size(); - - // Copy the (x, y) values because QDataBuffer::add(const float& t) - // may resize the buffer, which will leave t pointing at the - // previous buffer's memory region if we don't copy first. - float x = m_vertices.at(count-2); - float y = m_vertices.at(count-1); - m_vertices.add(x); - m_vertices.add(y); -} - -static inline void skipDuplicatePoints(const qreal **pts, const qreal *endPts) -{ - while ((*pts + 2) < endPts && float((*pts)[0]) == float((*pts)[2]) - && float((*pts)[1]) == float((*pts)[3])) - { - *pts += 2; - } -} - -void QTriangulatingStroker::process(const QVectorPath &path, const QPen &pen, const QRectF &, QPainter::RenderHints hints) -{ - const qreal *pts = path.points(); - const QPainterPath::ElementType *types = path.elements(); - int count = path.elementCount(); - if (count < 2) - return; - - float realWidth = qpen_widthf(pen); - if (realWidth == 0) - realWidth = 1; - - m_width = realWidth / 2; - - bool cosmetic = qt_pen_is_cosmetic(pen, hints); - if (cosmetic) { - m_width = m_width * m_inv_scale; - } - - m_join_style = qpen_joinStyle(pen); - m_cap_style = qpen_capStyle(pen); - m_vertices.reset(); - m_miter_limit = pen.miterLimit() * qpen_widthf(pen); - - // The curvyness is based on the notion that I originally wanted - // roughly one line segment pr 4 pixels. This may seem little, but - // because we sample at constantly incrementing B(t) E [0<t<1], we - // will get longer segments where the curvature is small and smaller - // segments when the curvature is high. - // - // To get a rough idea of the length of each curve, I pretend that - // the curve is a 90 degree arc, whose radius is - // qMax(curveBounds.width, curveBounds.height). Based on this - // logic we can estimate the length of the outline edges based on - // the radius + a pen width and adjusting for scale factors - // depending on if the pen is cosmetic or not. - // - // The curvyness value of PI/14 was based on, - // arcLength = 2*PI*r/4 = PI*r/2 and splitting length into somewhere - // between 3 and 8 where 5 seemed to be give pretty good results - // hence: Q_PI/14. Lower divisors will give more detail at the - // direct cost of performance. - - // simplfy pens that are thin in device size (2px wide or less) - if (realWidth < 2.5 && (cosmetic || m_inv_scale == 1)) { - if (m_cap_style == Qt::RoundCap) - m_cap_style = Qt::SquareCap; - if (m_join_style == Qt::RoundJoin) - m_join_style = Qt::MiterJoin; - m_curvyness_add = 0.5; - m_curvyness_mul = CURVE_FLATNESS / m_inv_scale; - m_roundness = 1; - } else if (cosmetic) { - m_curvyness_add = realWidth / 2; - m_curvyness_mul = float(CURVE_FLATNESS); - m_roundness = qMax<int>(4, realWidth * CURVE_FLATNESS); - } else { - m_curvyness_add = m_width; - m_curvyness_mul = CURVE_FLATNESS / m_inv_scale; - m_roundness = qMax<int>(4, realWidth * m_curvyness_mul); - } - - // Over this level of segmentation, there doesn't seem to be any - // benefit, even for huge penWidth - if (m_roundness > 24) - m_roundness = 24; - - m_sin_theta = qFastSin(Q_PI / m_roundness); - m_cos_theta = qFastCos(Q_PI / m_roundness); - - const qreal *endPts = pts + (count<<1); - const qreal *startPts = 0; - - Qt::PenCapStyle cap = m_cap_style; - - if (!types) { - skipDuplicatePoints(&pts, endPts); - if ((pts + 2) == endPts) - return; - - startPts = pts; - - bool endsAtStart = float(startPts[0]) == float(endPts[-2]) - && float(startPts[1]) == float(endPts[-1]); - - if (endsAtStart || path.hasImplicitClose()) - m_cap_style = Qt::FlatCap; - moveTo(pts); - m_cap_style = cap; - pts += 2; - skipDuplicatePoints(&pts, endPts); - lineTo(pts); - pts += 2; - skipDuplicatePoints(&pts, endPts); - while (pts < endPts) { - join(pts); - lineTo(pts); - pts += 2; - skipDuplicatePoints(&pts, endPts); - } - endCapOrJoinClosed(startPts, pts-2, path.hasImplicitClose(), endsAtStart); - - } else { - bool endsAtStart = false; - QPainterPath::ElementType previousType = QPainterPath::MoveToElement; - const qreal *previousPts = pts; - while (pts < endPts) { - switch (*types) { - case QPainterPath::MoveToElement: { - if (previousType != QPainterPath::MoveToElement) - endCapOrJoinClosed(startPts, previousPts, path.hasImplicitClose(), endsAtStart); - - startPts = pts; - skipDuplicatePoints(&startPts, endPts); // Skip duplicates to find correct normal. - if (startPts + 2 >= endPts) - return; // Nothing to see here... - - int end = (endPts - pts) / 2; - int i = 2; // Start looking to ahead since we never have two moveto's in a row - while (i<end && types[i] != QPainterPath::MoveToElement) { - ++i; - } - endsAtStart = float(startPts[0]) == float(pts[i*2 - 2]) - && float(startPts[1]) == float(pts[i*2 - 1]); - if (endsAtStart || path.hasImplicitClose()) - m_cap_style = Qt::FlatCap; - - moveTo(startPts); - m_cap_style = cap; - previousType = QPainterPath::MoveToElement; - previousPts = pts; - pts+=2; - ++types; - break; } - case QPainterPath::LineToElement: - if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])) { - if (previousType != QPainterPath::MoveToElement) - join(pts); - lineTo(pts); - previousType = QPainterPath::LineToElement; - previousPts = pts; - } - pts+=2; - ++types; - break; - case QPainterPath::CurveToElement: - if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1]) - || float(pts[0]) != float(pts[2]) || float(pts[1]) != float(pts[3]) - || float(pts[2]) != float(pts[4]) || float(pts[3]) != float(pts[5])) - { - if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])) { - if (previousType != QPainterPath::MoveToElement) - join(pts); - } - cubicTo(pts); - previousType = QPainterPath::CurveToElement; - previousPts = pts + 4; - } - pts+=6; - types+=3; - break; - default: - Q_ASSERT(false); - break; - } - } - - if (previousType != QPainterPath::MoveToElement) - endCapOrJoinClosed(startPts, previousPts, path.hasImplicitClose(), endsAtStart); - } -} - -void QTriangulatingStroker::moveTo(const qreal *pts) -{ - m_cx = pts[0]; - m_cy = pts[1]; - - float x2 = pts[2]; - float y2 = pts[3]; - normalVector(m_cx, m_cy, x2, y2, &m_nvx, &m_nvy); - - - // To acheive jumps we insert zero-area tringles. This is done by - // adding two identical points in both the end of previous strip - // and beginning of next strip - bool invisibleJump = m_vertices.size(); - - switch (m_cap_style) { - case Qt::FlatCap: - if (invisibleJump) { - m_vertices.add(m_cx + m_nvx); - m_vertices.add(m_cy + m_nvy); - } - break; - case Qt::SquareCap: { - float sx = m_cx - m_nvy; - float sy = m_cy + m_nvx; - if (invisibleJump) { - m_vertices.add(sx + m_nvx); - m_vertices.add(sy + m_nvy); - } - emitLineSegment(sx, sy, m_nvx, m_nvy); - break; } - case Qt::RoundCap: { - QVarLengthArray<float> points; - arcPoints(m_cx, m_cy, m_cx + m_nvx, m_cy + m_nvy, m_cx - m_nvx, m_cy - m_nvy, points); - m_vertices.resize(m_vertices.size() + points.size() + 2 * int(invisibleJump)); - int count = m_vertices.size(); - int front = 0; - int end = points.size() / 2; - while (front != end) { - m_vertices.at(--count) = points[2 * end - 1]; - m_vertices.at(--count) = points[2 * end - 2]; - --end; - if (front == end) - break; - m_vertices.at(--count) = points[2 * front + 1]; - m_vertices.at(--count) = points[2 * front + 0]; - ++front; - } - - if (invisibleJump) { - m_vertices.at(count - 1) = m_vertices.at(count + 1); - m_vertices.at(count - 2) = m_vertices.at(count + 0); - } - break; } - default: break; // ssssh gcc... - } - emitLineSegment(m_cx, m_cy, m_nvx, m_nvy); -} - -void QTriangulatingStroker::cubicTo(const qreal *pts) -{ - const QPointF *p = (const QPointF *) pts; - QBezier bezier = QBezier::fromPoints(*(p - 1), p[0], p[1], p[2]); - - QRectF bounds = bezier.bounds(); - float rad = qMax(bounds.width(), bounds.height()); - int threshold = qMin<float>(64, (rad + m_curvyness_add) * m_curvyness_mul); - if (threshold < 4) - threshold = 4; - qreal threshold_minus_1 = threshold - 1; - float vx, vy; - - float cx = m_cx, cy = m_cy; - float x, y; - - for (int i=1; i<threshold; ++i) { - qreal t = qreal(i) / threshold_minus_1; - QPointF p = bezier.pointAt(t); - x = p.x(); - y = p.y(); - - normalVector(cx, cy, x, y, &vx, &vy); - - emitLineSegment(x, y, vx, vy); - - cx = x; - cy = y; - } - - m_cx = cx; - m_cy = cy; - - m_nvx = vx; - m_nvy = vy; -} - -void QTriangulatingStroker::join(const qreal *pts) -{ - // Creates a join to the next segment (m_cx, m_cy) -> (pts[0], pts[1]) - normalVector(m_cx, m_cy, pts[0], pts[1], &m_nvx, &m_nvy); - - switch (m_join_style) { - case Qt::BevelJoin: - break; - case Qt::SvgMiterJoin: - case Qt::MiterJoin: { - // Find out on which side the join should be. - int count = m_vertices.size(); - float prevNvx = m_vertices.at(count - 2) - m_cx; - float prevNvy = m_vertices.at(count - 1) - m_cy; - float xprod = prevNvx * m_nvy - prevNvy * m_nvx; - float px, py, qx, qy; - - // If the segments are parallel, use bevel join. - if (qFuzzyIsNull(xprod)) - break; - - // Find the corners of the previous and next segment to join. - if (xprod < 0) { - px = m_vertices.at(count - 2); - py = m_vertices.at(count - 1); - qx = m_cx - m_nvx; - qy = m_cy - m_nvy; - } else { - px = m_vertices.at(count - 4); - py = m_vertices.at(count - 3); - qx = m_cx + m_nvx; - qy = m_cy + m_nvy; - } - - // Find intersection point. - float pu = px * prevNvx + py * prevNvy; - float qv = qx * m_nvx + qy * m_nvy; - float ix = (m_nvy * pu - prevNvy * qv) / xprod; - float iy = (prevNvx * qv - m_nvx * pu) / xprod; - - // Check that the distance to the intersection point is less than the miter limit. - if ((ix - px) * (ix - px) + (iy - py) * (iy - py) <= m_miter_limit * m_miter_limit) { - m_vertices.add(ix); - m_vertices.add(iy); - m_vertices.add(ix); - m_vertices.add(iy); - } - // else - // Do a plain bevel join if the miter limit is exceeded or if - // the lines are parallel. This is not what the raster - // engine's stroker does, but it is both faster and similar to - // what some other graphics API's do. - - break; } - case Qt::RoundJoin: { - QVarLengthArray<float> points; - int count = m_vertices.size(); - float prevNvx = m_vertices.at(count - 2) - m_cx; - float prevNvy = m_vertices.at(count - 1) - m_cy; - if (m_nvx * prevNvy - m_nvy * prevNvx < 0) { - arcPoints(0, 0, m_nvx, m_nvy, -prevNvx, -prevNvy, points); - for (int i = points.size() / 2; i > 0; --i) - emitLineSegment(m_cx, m_cy, points[2 * i - 2], points[2 * i - 1]); - } else { - arcPoints(0, 0, -prevNvx, -prevNvy, m_nvx, m_nvy, points); - for (int i = 0; i < points.size() / 2; ++i) - emitLineSegment(m_cx, m_cy, points[2 * i + 0], points[2 * i + 1]); - } - break; } - default: break; // gcc warn-- - } - - emitLineSegment(m_cx, m_cy, m_nvx, m_nvy); -} - -void QTriangulatingStroker::endCap(const qreal *) -{ - switch (m_cap_style) { - case Qt::FlatCap: - break; - case Qt::SquareCap: - emitLineSegment(m_cx + m_nvy, m_cy - m_nvx, m_nvx, m_nvy); - break; - case Qt::RoundCap: { - QVarLengthArray<float> points; - int count = m_vertices.size(); - arcPoints(m_cx, m_cy, m_vertices.at(count - 2), m_vertices.at(count - 1), m_vertices.at(count - 4), m_vertices.at(count - 3), points); - int front = 0; - int end = points.size() / 2; - while (front != end) { - m_vertices.add(points[2 * end - 2]); - m_vertices.add(points[2 * end - 1]); - --end; - if (front == end) - break; - m_vertices.add(points[2 * front + 0]); - m_vertices.add(points[2 * front + 1]); - ++front; - } - break; } - default: break; // to shut gcc up... - } -} - -void QTriangulatingStroker::arcPoints(float cx, float cy, float fromX, float fromY, float toX, float toY, QVarLengthArray<float> &points) -{ - float dx1 = fromX - cx; - float dy1 = fromY - cy; - float dx2 = toX - cx; - float dy2 = toY - cy; - - // while more than 180 degrees left: - while (dx1 * dy2 - dx2 * dy1 < 0) { - float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta; - float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta; - dx1 = tmpx; - dy1 = tmpy; - points.append(cx + dx1); - points.append(cy + dy1); - } - - // while more than 90 degrees left: - while (dx1 * dx2 + dy1 * dy2 < 0) { - float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta; - float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta; - dx1 = tmpx; - dy1 = tmpy; - points.append(cx + dx1); - points.append(cy + dy1); - } - - // while more than 0 degrees left: - while (dx1 * dy2 - dx2 * dy1 > 0) { - float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta; - float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta; - dx1 = tmpx; - dy1 = tmpy; - points.append(cx + dx1); - points.append(cy + dy1); - } - - // remove last point which was rotated beyond [toX, toY]. - if (!points.isEmpty()) - points.resize(points.size() - 2); -} - -static void qdashprocessor_moveTo(qreal x, qreal y, void *data) -{ - ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::MoveToElement, x, y); -} - -static void qdashprocessor_lineTo(qreal x, qreal y, void *data) -{ - ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::LineToElement, x, y); -} - -static void qdashprocessor_cubicTo(qreal, qreal, qreal, qreal, qreal, qreal, void *) -{ - Q_ASSERT(0); // The dasher should not produce curves... -} - -QDashedStrokeProcessor::QDashedStrokeProcessor() - : m_points(0), m_types(0), - m_dash_stroker(0), m_inv_scale(1) -{ - m_dash_stroker.setMoveToHook(qdashprocessor_moveTo); - m_dash_stroker.setLineToHook(qdashprocessor_lineTo); - m_dash_stroker.setCubicToHook(qdashprocessor_cubicTo); -} - -void QDashedStrokeProcessor::process(const QVectorPath &path, const QPen &pen, const QRectF &clip, QPainter::RenderHints hints) -{ - - const qreal *pts = path.points(); - const QPainterPath::ElementType *types = path.elements(); - int count = path.elementCount(); - - bool cosmetic = qt_pen_is_cosmetic(pen, hints); - - m_points.reset(); - m_types.reset(); - m_points.reserve(path.elementCount()); - m_types.reserve(path.elementCount()); - - qreal width = qpen_widthf(pen); - if (width == 0) - width = 1; - - m_dash_stroker.setDashPattern(pen.dashPattern()); - m_dash_stroker.setStrokeWidth(cosmetic ? width * m_inv_scale : width); - m_dash_stroker.setDashOffset(pen.dashOffset()); - m_dash_stroker.setMiterLimit(pen.miterLimit()); - m_dash_stroker.setClipRect(clip); - - float curvynessAdd, curvynessMul; - - // simplify pens that are thin in device size (2px wide or less) - if (width < 2.5 && (cosmetic || m_inv_scale == 1)) { - curvynessAdd = 0.5; - curvynessMul = CURVE_FLATNESS / m_inv_scale; - } else if (cosmetic) { - curvynessAdd= width / 2; - curvynessMul= float(CURVE_FLATNESS); - } else { - curvynessAdd = width * m_inv_scale; - curvynessMul = CURVE_FLATNESS / m_inv_scale; - } - - if (count < 2) - return; - - const qreal *endPts = pts + (count<<1); - - m_dash_stroker.begin(this); - - if (!types) { - m_dash_stroker.moveTo(pts[0], pts[1]); - pts += 2; - while (pts < endPts) { - m_dash_stroker.lineTo(pts[0], pts[1]); - pts += 2; - } - } else { - while (pts < endPts) { - switch (*types) { - case QPainterPath::MoveToElement: - m_dash_stroker.moveTo(pts[0], pts[1]); - pts += 2; - ++types; - break; - case QPainterPath::LineToElement: - m_dash_stroker.lineTo(pts[0], pts[1]); - pts += 2; - ++types; - break; - case QPainterPath::CurveToElement: { - QBezier b = QBezier::fromPoints(*(((const QPointF *) pts) - 1), - *(((const QPointF *) pts)), - *(((const QPointF *) pts) + 1), - *(((const QPointF *) pts) + 2)); - QRectF bounds = b.bounds(); - float rad = qMax(bounds.width(), bounds.height()); - int threshold = qMin<float>(64, (rad + curvynessAdd) * curvynessMul); - if (threshold < 4) - threshold = 4; - - qreal threshold_minus_1 = threshold - 1; - for (int i=0; i<threshold; ++i) { - QPointF pt = b.pointAt(i / threshold_minus_1); - m_dash_stroker.lineTo(pt.x(), pt.y()); - } - pts += 6; - types += 3; - break; } - default: break; - } - } - } - - m_dash_stroker.end(); -} - -QT_END_NAMESPACE - diff --git a/src/gui/opengl/qtriangulatingstroker_p.h b/src/gui/opengl/qtriangulatingstroker_p.h deleted file mode 100644 index 2b0f08972b..0000000000 --- a/src/gui/opengl/qtriangulatingstroker_p.h +++ /dev/null @@ -1,171 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#ifndef QTRIANGULATINGSTROKER_P_H -#define QTRIANGULATINGSTROKER_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 <QtGui/private/qtguiglobal_p.h> -#include <private/qdatabuffer_p.h> -#include <qvarlengtharray.h> -#include <private/qvectorpath_p.h> -#include <private/qbezier_p.h> -#include <private/qnumeric_p.h> -#include <private/qmath_p.h> - -QT_BEGIN_NAMESPACE - -class Q_GUI_EXPORT QTriangulatingStroker -{ -public: - QTriangulatingStroker() : m_vertices(0), m_cx(0), m_cy(0), m_nvx(0), m_nvy(0), m_width(1), m_miter_limit(2), - m_roundness(0), m_sin_theta(0), m_cos_theta(0), m_inv_scale(1), m_curvyness_mul(1), m_curvyness_add(0), - m_join_style(Qt::BevelJoin), m_cap_style(Qt::SquareCap) {} - - void process(const QVectorPath &path, const QPen &pen, const QRectF &clip, QPainter::RenderHints hints); - - inline int vertexCount() const { return m_vertices.size(); } - inline const float *vertices() const { return m_vertices.data(); } - - inline void setInvScale(qreal invScale) { m_inv_scale = invScale; } - -private: - inline void emitLineSegment(float x, float y, float nx, float ny); - void moveTo(const qreal *pts); - inline void lineTo(const qreal *pts); - void cubicTo(const qreal *pts); - void join(const qreal *pts); - inline void normalVector(float x1, float y1, float x2, float y2, float *nx, float *ny); - void endCap(const qreal *pts); - void arcPoints(float cx, float cy, float fromX, float fromY, float toX, float toY, QVarLengthArray<float> &points); - void endCapOrJoinClosed(const qreal *start, const qreal *cur, bool implicitClose, bool endsAtStart); - - - QDataBuffer<float> m_vertices; - - float m_cx, m_cy; // current points - float m_nvx, m_nvy; // normal vector... - float m_width; - qreal m_miter_limit; - - int m_roundness; // Number of line segments in a round join - qreal m_sin_theta; // sin(m_roundness / 360); - qreal m_cos_theta; // cos(m_roundness / 360); - qreal m_inv_scale; - float m_curvyness_mul; - float m_curvyness_add; - - Qt::PenJoinStyle m_join_style; - Qt::PenCapStyle m_cap_style; -}; - -class Q_GUI_EXPORT QDashedStrokeProcessor -{ -public: - QDashedStrokeProcessor(); - - void process(const QVectorPath &path, const QPen &pen, const QRectF &clip, QPainter::RenderHints hints); - - inline void addElement(QPainterPath::ElementType type, qreal x, qreal y) { - m_points.add(x); - m_points.add(y); - m_types.add(type); - } - - inline int elementCount() const { return m_types.size(); } - inline qreal *points() const { return m_points.data(); } - inline QPainterPath::ElementType *elementTypes() const { return m_types.data(); } - - inline void setInvScale(qreal invScale) { m_inv_scale = invScale; } - -private: - QDataBuffer<qreal> m_points; - QDataBuffer<QPainterPath::ElementType> m_types; - QDashStroker m_dash_stroker; - qreal m_inv_scale; -}; - -inline void QTriangulatingStroker::normalVector(float x1, float y1, float x2, float y2, - float *nx, float *ny) -{ - float dx = x2 - x1; - float dy = y2 - y1; - Q_ASSERT(dx != 0 || dy != 0); - - float pw; - - if (dx == 0) - pw = m_width / std::abs(dy); - else if (dy == 0) - pw = m_width / std::abs(dx); - else - pw = m_width / std::sqrt(dx*dx + dy*dy); - - *nx = -dy * pw; - *ny = dx * pw; -} - -inline void QTriangulatingStroker::emitLineSegment(float x, float y, float vx, float vy) -{ - m_vertices.add(x + vx); - m_vertices.add(y + vy); - m_vertices.add(x - vx); - m_vertices.add(y - vy); -} - -void QTriangulatingStroker::lineTo(const qreal *pts) -{ - emitLineSegment(pts[0], pts[1], m_nvx, m_nvy); - m_cx = pts[0]; - m_cy = pts[1]; -} - -QT_END_NAMESPACE - -#endif diff --git a/src/gui/opengl/qtriangulator.cpp b/src/gui/opengl/qtriangulator.cpp deleted file mode 100644 index 601b51a5fb..0000000000 --- a/src/gui/opengl/qtriangulator.cpp +++ /dev/null @@ -1,2377 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#include "qtriangulator_p.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/qopenglcontext_p.h> -#include <private/qopenglextensions_p.h> -#include <private/qrbtree_p.h> - -QT_BEGIN_NAMESPACE - -//#define Q_TRIANGULATOR_DEBUG - -#define Q_FIXED_POINT_SCALE 32 - -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); -} - -#ifdef Q_TRIANGULATOR_DEBUG -static inline qint64 qDot(const QPodPoint &u, const QPodPoint &v) -{ - return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y); -} -#endif - -// 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; -} - -//============================================================================// -// 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 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 \c 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, 17, 27, 3, - 1, 29, 3, 21, 7, 17, 15, 9, 43, 35, 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 (uint(count) >= (1u << 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; -} - -//============================================================================// -// 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; - }; - - 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, int(m_parent->m_indices.at(i)), int(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); - } - } - - std::sort(m_events.data(), 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> -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 = qSqrt(qDot(u, u)); - qreal vLen = qSqrt(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 = qExp(-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); - std::sort(m_upperVertex.data(), 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 ¢er = 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 // -//============================================================================// - -static bool hasElementIndexUint() -{ - QOpenGLContext *context = QOpenGLContext::currentContext(); - if (!context) - return false; - return static_cast<QOpenGLExtensions *>(context->functions())->hasOpenGLExtension(QOpenGLExtensions::ElementIndexUint); -} - -Q_GUI_EXPORT QTriangleSet qTriangulate(const qreal *polygon, - int count, uint hint, const QTransform &matrix) -{ - QTriangleSet triangleSet; - if (hasElementIndexUint()) { - 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; -} - -Q_GUI_EXPORT QTriangleSet qTriangulate(const QVectorPath &path, - const QTransform &matrix, qreal lod) -{ - QTriangleSet triangleSet; - if (hasElementIndexUint()) { - 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 (hasElementIndexUint()) { - 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 (hasElementIndexUint()) { - 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 (hasElementIndexUint()) { - 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/gui/opengl/qtriangulator_p.h b/src/gui/opengl/qtriangulator_p.h deleted file mode 100644 index 4d1aba099c..0000000000 --- a/src/gui/opengl/qtriangulator_p.h +++ /dev/null @@ -1,148 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $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 <QtGui/private/qtguiglobal_p.h> -#include <QtCore/qvector.h> -#include <QtGui/private/qvectorpath_p.h> - -QT_BEGIN_NAMESPACE - -class Q_GUI_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; - - t = other.t; - return *this; - } - -private: - - Type t; - QVector<quint32> indices32; - QVector<quint16> indices16; -}; - -struct Q_GUI_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_GUI_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 Q_GUI_EXPORT qTriangulate(const qreal *polygon, int count, uint hint = QVectorPath::PolygonHint | QVectorPath::OddEvenFill, const QTransform &matrix = QTransform()); -QTriangleSet Q_GUI_EXPORT qTriangulate(const QVectorPath &path, const QTransform &matrix = QTransform(), qreal lod = 1); -QTriangleSet Q_GUI_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_GUI_EXPORT qPolyline(const QPainterPath &path, const QTransform &matrix = QTransform(), qreal lod = 1); - -QT_END_NAMESPACE - -#endif |