From ff57203b57751a38c814419495123d23bb7c3f1e Mon Sep 17 00:00:00 2001 From: Andy Nichols Date: Fri, 12 Aug 2016 10:16:46 +0200 Subject: Move QTriangulator and QTriangulatingStroker classes to painting Previously the private APIs for QTriangulator and QTriangulatingStroker were located in src/gui/opengl because they were used by the OpenGL paint engine. These API's are not actually specific to OpenGL however, and were not being built when QT_NO_OPENGL was defined. It makes more sense for these classes to belong in the painting subgroup. Aside from the OpenGL paint engine, these private APIs are used by QtLocation to triangulate polylines to be rendered by QtQuick. Change-Id: Idb4d1e5b2a51394d4c6bcdf9ab1ece99de23d4de Reviewed-by: Laszlo Agocs --- src/gui/opengl/opengl.pri | 5 - src/gui/opengl/qrbtree_p.h | 571 ------- src/gui/opengl/qtriangulatingstroker.cpp | 613 ------- src/gui/opengl/qtriangulatingstroker_p.h | 171 -- src/gui/opengl/qtriangulator.cpp | 2377 --------------------------- src/gui/opengl/qtriangulator_p.h | 148 -- src/gui/painting/painting.pri | 5 + src/gui/painting/qrbtree_p.h | 571 +++++++ src/gui/painting/qtriangulatingstroker.cpp | 613 +++++++ src/gui/painting/qtriangulatingstroker_p.h | 171 ++ src/gui/painting/qtriangulator.cpp | 2382 ++++++++++++++++++++++++++++ src/gui/painting/qtriangulator_p.h | 148 ++ 12 files changed, 3890 insertions(+), 3885 deletions(-) delete mode 100644 src/gui/opengl/qrbtree_p.h delete mode 100644 src/gui/opengl/qtriangulatingstroker.cpp delete mode 100644 src/gui/opengl/qtriangulatingstroker_p.h delete mode 100644 src/gui/opengl/qtriangulator.cpp delete mode 100644 src/gui/opengl/qtriangulator_p.h create mode 100644 src/gui/painting/qrbtree_p.h create mode 100644 src/gui/painting/qtriangulatingstroker.cpp create mode 100644 src/gui/painting/qtriangulatingstroker_p.h create mode 100644 src/gui/painting/qtriangulator.cpp create mode 100644 src/gui/painting/qtriangulator_p.h (limited to 'src/gui') 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 - -QT_BEGIN_NAMESPACE - -template -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 -inline QRBTree::~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 -inline void QRBTree::clear() -{ - if (root) - delete root; - root = 0; -} - -template -void QRBTree::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 -void QRBTree::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 -void QRBTree::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 -inline void QRBTree::attachLeft(Node *parent, Node *child) -{ - Q_ASSERT(!parent->left); - parent->left = child; - child->parent = parent; - update(child); -} - -template -inline void QRBTree::attachRight(Node *parent, Node *child) -{ - Q_ASSERT(!parent->right); - parent->right = child; - child->parent = parent; - update(child); -} - -template -void QRBTree::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 -void QRBTree::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 -void QRBTree::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 -void QRBTree::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 -void QRBTree::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 -inline typename QRBTree::Node *QRBTree::front(Node *node) const -{ - while (node->left) - node = node->left; - return node; -} - -template -inline typename QRBTree::Node *QRBTree::back(Node *node) const -{ - while (node->right) - node = node->right; - return node; -} - -template -typename QRBTree::Node *QRBTree::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 -typename QRBTree::Node *QRBTree::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 -int QRBTree::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 -bool QRBTree::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 -inline bool QRBTree::validate() const -{ - return checkRedBlackProperty(root) && blackDepth(root) != -1; -} - -template -inline void QRBTree::deleteNode(Node *&node) -{ - Q_ASSERT(node); - detach(node); - node->right = freeList; - freeList = node; - node = 0; -} - -template -inline typename QRBTree::Node *QRBTree::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 -int QRBTree::order(Node *left, Node *right) -{ - Q_ASSERT(left && right); - if (left == right) - return 0; - - QVector leftAncestors; - QVector 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 - -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(4, realWidth * CURVE_FLATNESS); - } else { - m_curvyness_add = m_width; - m_curvyness_mul = CURVE_FLATNESS / m_inv_scale; - m_roundness = qMax(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 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(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 (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 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 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 &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(64, (rad + curvynessAdd) * curvynessMul); - if (threshold < 4) - threshold = 4; - - qreal threshold_minus_1 = threshold - 1; - for (int i=0; i -#include -#include -#include -#include -#include -#include - -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 &points); - void endCapOrJoinClosed(const qreal *start, const qreal *cur, bool implicitClose, bool endsAtStart); - - - QDataBuffer 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 m_points; - QDataBuffer 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 -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include -#include -#include - -QT_BEGIN_NAMESPACE - -//#define Q_TRIANGULATOR_DEBUG - -#define Q_FIXED_POINT_SCALE 32 - -template -struct QVertexSet -{ - inline QVertexSet() { } - inline QVertexSet(const QVertexSet &other) : vertices(other.vertices), indices(other.indices) { } - QVertexSet &operator = (const QVertexSet &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 vertices; // [x[0], y[0], x[1], y[1], x[2], ...] - QVector 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 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 m_data; -}; - -template -void QMaxHeap::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 -T QMaxHeap::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::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::insert", "Hash set full."); -} - -bool QInt64Set::contains(quint64 key) const -{ - Q_ASSERT_X(m_array, "QInt64Hash::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::clear", "Hash set not allocated."); - for (int i = 0; i < m_capacity; ++i) - m_array[i] = UNUSED; - m_count = 0; -} - -//============================================================================// -// QTriangulator // -//============================================================================// -template -class QTriangulator -{ -public: - typedef QVarLengthArray ShortArray; - - //================================// - // QTriangulator::ComplexToSimple // - //================================// - friend class ComplexToSimple; - class ComplexToSimple - { - public: - inline ComplexToSimple(QTriangulator *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::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::Node *searchEdgeLeftOf(int edgeIndex) const; - QRBTree::Node *searchEdgeLeftOf(int edgeIndex, QRBTree::Node *after) const; - QPair::Node *, QRBTree::Node *> bounds(const QPodPoint &point) const; - QPair::Node *, QRBTree::Node *> outerBounds(const QPodPoint &point) const; - void splitEdgeListRange(QRBTree::Node *leftmost, QRBTree::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint); - void reorderEdgeListRange(QRBTree::Node *leftmost, QRBTree::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 m_edges; - QRBTree m_edgeList; - QDataBuffer m_events; - QDataBuffer m_splits; - QMaxHeap m_topIntersection; - QInt64Set m_processedEdgePairs; - int m_initialPointCount; - }; -#ifdef Q_TRIANGULATOR_DEBUG - friend class ComplexToSimple::DebugDialog; -#endif - - //=================================// - // QTriangulator::SimpleToMonotone // - //=================================// - friend class SimpleToMonotone; - class SimpleToMonotone - { - public: - inline SimpleToMonotone(QTriangulator *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { } - void decompose(); - private: - enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex}; - - struct Edge - { - QRBTree::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::Node *searchEdgeLeftOfEdge(int edgeIndex) const; - // Returns the rightmost edge left of the given point. - QRBTree::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 m_edgeList; - QDataBuffer m_edges; - QDataBuffer m_upperVertex; - bool m_clockwiseOrder; - }; - - //====================================// - // QTriangulator::MonotoneToTriangles // - //====================================// - friend class MonotoneToTriangles; - class MonotoneToTriangles - { - public: - inline MonotoneToTriangles(QTriangulator *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 *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 triangulate(); - QVertexSet polyline(); -private: - QDataBuffer m_vertices; - QVector m_indices; - uint m_hint; -}; - -//============================================================================// -// QTriangulator // -//============================================================================// - -template -QVertexSet QTriangulator::triangulate() -{ - for (int i = 0; i < m_vertices.size(); ++i) { - Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21)); - Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21)); - } - - if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill))) - m_hint |= QVectorPath::OddEvenFill; - - if (m_hint & QVectorPath::NonConvexShapeMask) { - ComplexToSimple c2s(this); - c2s.decompose(); - SimpleToMonotone s2m(this); - s2m.decompose(); - } - MonotoneToTriangles m2t(this); - m2t.decompose(); - - QVertexSet 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 -QVertexSet QTriangulator::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 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 -void QTriangulator::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix) -{ - m_hint = hint; - m_vertices.resize(count); - m_indices.resize(count + 1); - for (int i = 0; i < count; ++i) { - qreal x, y; - matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y); - m_vertices.at(i).x = qRound(x * Q_FIXED_POINT_SCALE); - m_vertices.at(i).y = qRound(y * Q_FIXED_POINT_SCALE); - m_indices[i] = i; - } - m_indices[count] = T(-1); //Q_TRIANGULATE_END_OF_POLYGON -} - -template -void QTriangulator::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod) -{ - m_hint = path.hints(); - // Curved paths will be converted to complex polygons. - m_hint &= ~QVectorPath::CurvedShapeMask; - - const qreal *p = path.points(); - const QPainterPath::ElementType *e = path.elements(); - if (e) { - for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) { - switch (*e) { - case QPainterPath::MoveToElement: - if (!m_indices.isEmpty()) - m_indices.push_back(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 -void QTriangulator::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod) -{ - initialize(qtVectorPathForPath(path), matrix, lod); -} - -//============================================================================// -// QTriangulator::ComplexToSimple // -//============================================================================// -template -void QTriangulator::ComplexToSimple::decompose() -{ - m_initialPointCount = m_parent->m_vertices.size(); - initEdges(); - do { - calculateIntersections(); - } while (splitEdgesAtIntersections()); - - removeUnwantedEdgesAndConnect(); - removeUnusedPoints(); - - m_parent->m_indices.clear(); - QBitArray processed(m_edges.size(), false); - for (int first = 0; first < m_edges.size(); ++first) { - // If already processed, or if unused path, skip. - if (processed.at(first) || m_edges.at(first).next == -1) - continue; - - int i = first; - do { - Q_ASSERT(!processed.at(i)); - Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i); - m_parent->m_indices.push_back(m_edges.at(i).from); - processed.setBit(i); - i = m_edges.at(i).next; // CCW order - } while (i != first); - m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON - } -} - -template -void QTriangulator::ComplexToSimple::initEdges() -{ - // Initialize edge structure. - // 'next' and 'previous' are not being initialized at this point. - int first = 0; - for (int i = 0; i < m_parent->m_indices.size(); ++i) { - if (m_parent->m_indices.at(i) == 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 -bool QTriangulator::ComplexToSimple::calculateIntersection(int left, int right) -{ - const Edge &e1 = m_edges.at(left); - const Edge &e2 = m_edges.at(right); - - const QPodPoint &u1 = m_parent->m_vertices.at((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 -bool QTriangulator::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const -{ - const Edge &leftEdge = m_edges.at(leftEdgeIndex); - const Edge &rightEdge = m_edges.at(rightEdgeIndex); - const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper()); - const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower()); - const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper()); - if (upper.x < qMin(l.x, u.x)) - return true; - if (upper.x > qMax(l.x, u.x)) - return false; - qint64 d = 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 -QRBTree::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const -{ - QRBTree::Node *current = m_edgeList.root; - QRBTree::Node *result = 0; - while (current) { - if (edgeIsLeftOfEdge(edgeIndex, current->data)) { - current = current->left; - } else { - result = current; - current = current->right; - } - } - return result; -} - -template -QRBTree::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree::Node *after) const -{ - if (!m_edgeList.root) - return after; - QRBTree::Node *result = after; - QRBTree::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 -QPair::Node *, QRBTree::Node *> QTriangulator::ComplexToSimple::bounds(const QPodPoint &point) const -{ - QRBTree::Node *current = m_edgeList.root; - QPair::Node *, QRBTree::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 -QPair::Node *, QRBTree::Node *> QTriangulator::ComplexToSimple::outerBounds(const QPodPoint &point) const -{ - QRBTree::Node *current = m_edgeList.root; - QPair::Node *, QRBTree::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::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 -void QTriangulator::ComplexToSimple::splitEdgeListRange(QRBTree::Node *leftmost, QRBTree::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 -void QTriangulator::ComplexToSimple::reorderEdgeListRange(QRBTree::Node *leftmost, QRBTree::Node *rightmost) -{ - Q_ASSERT(leftmost && rightmost); - - QRBTree::Node *storeLeftmost = leftmost; - QRBTree::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 -void QTriangulator::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::Node *leftmost = m_edges.at(intersection.leftEdge).node; - QRBTree::Node *rightmost = m_edges.at(intersection.rightEdge).node; - - for (;;) { - QRBTree::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::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 -void QTriangulator::ComplexToSimple::fillPriorityQueue() -{ - m_events.reset(); - m_events.reserve(m_edges.size() * 2); - for (int i = 0; i < m_edges.size(); ++i) { - Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1); - Q_ASSERT(m_edges.at(i).node == 0); - Q_ASSERT(m_edges.at(i).pointingUp == m_edges.at(i).originallyPointingUp); - Q_ASSERT(m_edges.at(i).pointingUp == (m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from))); - // Ignore zero-length edges. - if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) { - QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper()); - QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower()); - Event upperEvent = {{upper.x, upper.y}, Event::Upper, i}; - Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i}; - m_events.add(upperEvent); - m_events.add(lowerEvent); - } - } - - std::sort(m_events.data(), m_events.data() + m_events.size()); -} - -template -void QTriangulator::ComplexToSimple::calculateIntersections() -{ - fillPriorityQueue(); - - Q_ASSERT(m_topIntersection.empty()); - Q_ASSERT(m_edgeList.root == 0); - - // Find all intersection points. - while (!m_events.isEmpty()) { - Event event = m_events.last(); - sortEdgeList(event.point); - - // Find all edges in the edge list that contain the current vertex and mark them to be split later. - QPair::Node *, QRBTree::Node *> range = bounds(event.point); - QRBTree::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::Node *left = m_edgeList.previous(m_edges.at(i).node); - QRBTree::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::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::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 -int QTriangulator::ComplexToSimple::splitEdge(int splitIndex) -{ - const Split &split = m_splits.at(splitIndex); - Edge &lowerEdge = m_edges.at(split.edge); - Q_ASSERT(lowerEdge.node == 0); - Q_ASSERT(lowerEdge.previous == -1 && lowerEdge.next == -1); - - if (lowerEdge.from == split.vertex) - return split.edge; - if (lowerEdge.to == split.vertex) - return lowerEdge.next; - - // Check that angle >= 90 degrees. - //Q_ASSERT(qDot(m_points.at(m_edges.at(edgeIndex).from) - m_points.at(pointIndex), - // m_points.at(m_edges.at(edgeIndex).to) - m_points.at(pointIndex)) <= 0); - - Edge upperEdge = lowerEdge; - upperEdge.mayIntersect |= !split.accurate; // The edge may have been split before at an inaccurate split point. - lowerEdge.mayIntersect = !split.accurate; - if (lowerEdge.pointingUp) { - lowerEdge.to = upperEdge.from = split.vertex; - m_edges.add(upperEdge); - return m_edges.size() - 1; - } else { - lowerEdge.from = upperEdge.to = split.vertex; - m_edges.add(upperEdge); - return split.edge; - } -} - -template -bool QTriangulator::ComplexToSimple::splitEdgesAtIntersections() -{ - for (int i = 0; i < m_edges.size(); ++i) - m_edges.at(i).mayIntersect = false; - bool checkForNewIntersections = false; - for (int i = 0; i < m_splits.size(); ++i) { - splitEdge(i); - checkForNewIntersections |= !m_splits.at(i).accurate; - } - for (int i = 0; i < m_edges.size(); ++i) { - m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp = - m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from); - } - m_splits.reset(); - return checkForNewIntersections; -} - -template -void QTriangulator::ComplexToSimple::insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i) -{ - // Edges with zero length should not reach this part. - Q_ASSERT(m_parent->m_vertices.at(m_edges.at(i).from) != m_parent->m_vertices.at(m_edges.at(i).to)); - - // Skip edges with unwanted winding number. - int windingNumber = m_edges.at(i).winding; - if (m_edges.at(i).originallyPointingUp) - ++windingNumber; - - // Make sure exactly one fill rule is specified. - Q_ASSERT(((m_parent->m_hint & QVectorPath::WindingFill) != 0) != ((m_parent->m_hint & QVectorPath::OddEvenFill) != 0)); - - if ((m_parent->m_hint & QVectorPath::WindingFill) && windingNumber != 0 && windingNumber != 1) - return; - - // Skip cancelling edges. - if (!orderedEdges.isEmpty()) { - int j = orderedEdges[orderedEdges.size() - 1]; - // If the last edge is already connected in one end, it should not be cancelled. - if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1 - && (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to)) - && (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) { - orderedEdges.removeLast(); - return; - } - } - orderedEdges.append(i); -} - -template -void QTriangulator::ComplexToSimple::removeUnwantedEdgesAndConnect() -{ - Q_ASSERT(m_edgeList.root == 0); - // Initialize priority queue. - fillPriorityQueue(); - - ShortArray orderedEdges; - - while (!m_events.isEmpty()) { - Event event = m_events.last(); - int edgeIndex = event.edge; - - // Check that all the edges in the list crosses the current scanline - //if (m_edgeList.root) { - // for (QRBTree::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::Node *, QRBTree::Node *> b = outerBounds(event.point); - if (m_edgeList.root) { - QRBTree::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::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::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 -void QTriangulator::ComplexToSimple::removeUnusedPoints() { - QBitArray used(m_parent->m_vertices.size(), false); - for (int i = 0; i < m_edges.size(); ++i) { - Q_ASSERT((m_edges.at(i).previous == -1) == (m_edges.at(i).next == -1)); - if (m_edges.at(i).next != -1) - used.setBit(m_edges.at(i).from); - } - QDataBuffer 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 -inline bool QTriangulator::ComplexToSimple::Event::operator < (const Event &other) const -{ - if (point == other.point) - return type < other.type; // 'Lower' has higher priority than 'Upper'. - return other.point < point; -} - -//============================================================================// -// QTriangulator::ComplexToSimple::DebugDialog // -//============================================================================// - -#ifdef Q_TRIANGULATOR_DEBUG -template -QTriangulator::ComplexToSimple::DebugDialog::DebugDialog(ComplexToSimple *parent, int currentVertex) - : m_parent(parent), m_vertex(currentVertex) -{ - QDataBuffer &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 -void QTriangulator::ComplexToSimple::DebugDialog::paintEvent(QPaintEvent *) -{ - QPainter p(this); - p.setRenderHint(QPainter::Antialiasing, true); - p.fillRect(rect(), Qt::black); - QDataBuffer &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 &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::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 &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 -void QTriangulator::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 -void QTriangulator::ComplexToSimple::DebugDialog::mouseMoveEvent(QMouseEvent *event) -{ - if (event->buttons() & Qt::LeftButton) { - QPointF delta = event->pos() - m_lastMousePos; - delta.setX(delta.x() * m_window.width() / width()); - delta.setY(delta.y() * m_window.height() / height()); - m_window.translate(-delta.x(), -delta.y()); - m_lastMousePos = event->pos(); - event->accept(); - update(); - } -} - -template -void QTriangulator::ComplexToSimple::DebugDialog::mousePressEvent(QMouseEvent *event) -{ - if (event->button() == Qt::LeftButton) - m_lastMousePos = event->pos(); - event->accept(); -} - - -#endif - -//============================================================================// -// QTriangulator::SimpleToMonotone // -//============================================================================// -template -void QTriangulator::SimpleToMonotone::decompose() -{ - setupDataStructures(); - removeZeroLengthEdges(); - monotoneDecomposition(); - - m_parent->m_indices.clear(); - QBitArray processed(m_edges.size(), false); - for (int first = 0; first < m_edges.size(); ++first) { - if (processed.at(first)) - continue; - int i = first; - do { - Q_ASSERT(!processed.at(i)); - Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i); - m_parent->m_indices.push_back(m_edges.at(i).from); - processed.setBit(i); - i = m_edges.at(i).next; - } while (i != first); - if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != T(-1)) // Q_TRIANGULATE_END_OF_POLYGON - m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON - } -} - -template -void QTriangulator::SimpleToMonotone::setupDataStructures() -{ - int i = 0; - Edge e; - e.node = 0; - e.twin = -1; - - while (i + 3 <= m_parent->m_indices.size()) { - int start = m_edges.size(); - - do { - e.from = m_parent->m_indices.at(i); - e.type = RegularVertex; - e.next = m_edges.size() + 1; - e.previous = m_edges.size() - 1; - m_edges.add(e); - ++i; - Q_ASSERT(i < m_parent->m_indices.size()); - } while (m_parent->m_indices.at(i) != 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 -void QTriangulator::SimpleToMonotone::removeZeroLengthEdges() -{ - for (int i = 0; i < m_edges.size(); ++i) { - if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) { - m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next; - m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous; - m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from; - m_edges.at(i).next = -1; // Mark as removed. - } - } - - QDataBuffer 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 -void QTriangulator::SimpleToMonotone::fillPriorityQueue() -{ - m_upperVertex.reset(); - m_upperVertex.reserve(m_edges.size()); - for (int i = 0; i < m_edges.size(); ++i) - m_upperVertex.add(i); - CompareVertices cmp(this); - 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 -bool QTriangulator::SimpleToMonotone::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const -{ - const Edge &leftEdge = m_edges.at(leftEdgeIndex); - const Edge &rightEdge = m_edges.at(rightEdgeIndex); - const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper()); - const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower()); - qint64 d = 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 -QRBTree::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfEdge(int edgeIndex) const -{ - QRBTree::Node *current = m_edgeList.root; - QRBTree::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 -QRBTree::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfPoint(int pointIndex) const -{ - QRBTree::Node *current = m_edgeList.root; - QRBTree::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 -void QTriangulator::SimpleToMonotone::classifyVertex(int i) -{ - Edge &e2 = m_edges.at(i); - const Edge &e1 = m_edges.at(e2.previous); - - bool startOrSplit = (e1.pointingUp && !e2.pointingUp); - bool endOrMerge = (!e1.pointingUp && e2.pointingUp); - - const QPodPoint &p1 = m_parent->m_vertices.at(e1.from); - const QPodPoint &p2 = m_parent->m_vertices.at(e2.from); - const QPodPoint &p3 = m_parent->m_vertices.at(e2.to); - qint64 d = 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 -void QTriangulator::SimpleToMonotone::classifyVertices() -{ - for (int i = 0; i < m_edges.size(); ++i) - classifyVertex(i); -} - -template -bool QTriangulator::SimpleToMonotone::pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3) -{ - bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1); - bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2); - - if (qPointIsLeftOfLine(v1, v2, v3)) - return leftOfPreviousEdge && leftOfNextEdge; - else - return leftOfPreviousEdge || leftOfNextEdge; -} - -template -bool QTriangulator::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 -int QTriangulator::SimpleToMonotone::findSector(int edge, int vertex) -{ - while (!pointIsInSector(vertex, edge)) { - edge = m_edges.at(m_edges.at(edge).previous).twin; - Q_ASSERT(edge != -1); - } - return edge; -} - -template -void QTriangulator::SimpleToMonotone::createDiagonal(int lower, int upper) -{ - lower = findSector(lower, upper); - upper = findSector(upper, lower); - - int prevLower = m_edges.at(lower).previous; - int prevUpper = m_edges.at(upper).previous; - - Edge e; - - e.twin = m_edges.size() + 1; - e.next = upper; - e.previous = prevLower; - e.from = m_edges.at(lower).from; - e.to = m_edges.at(upper).from; - m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size()); - m_edges.add(e); - - e.twin = m_edges.size() - 1; - e.next = lower; - e.previous = prevUpper; - e.from = m_edges.at(upper).from; - e.to = m_edges.at(lower).from; - m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size()); - m_edges.add(e); -} - -template -void QTriangulator::SimpleToMonotone::monotoneDecomposition() -{ - if (m_edges.isEmpty()) - return; - - Q_ASSERT(!m_edgeList.root); - QDataBuffer > 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::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(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(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(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(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::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::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(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(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(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 -bool QTriangulator::SimpleToMonotone::CompareVertices::operator () (int i, int j) const -{ - if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from) - return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type; - return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) > - m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from); -} - -//============================================================================// -// QTriangulator::MonotoneToTriangles // -//============================================================================// -template -void QTriangulator::MonotoneToTriangles::decompose() -{ - QVector result; - QDataBuffer 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(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 triangulator; - triangulator.initialize(polygon, count, hint, matrix); - QVertexSet vertexSet = triangulator.triangulate(); - triangleSet.vertices = vertexSet.vertices; - triangleSet.indices.setDataUint(vertexSet.indices); - - } else { - QTriangulator triangulator; - triangulator.initialize(polygon, count, hint, matrix); - QVertexSet 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 triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet vertexSet = triangulator.triangulate(); - triangleSet.vertices = vertexSet.vertices; - triangleSet.indices.setDataUint(vertexSet.indices); - } else { - QTriangulator triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet 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 triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet vertexSet = triangulator.triangulate(); - triangleSet.vertices = vertexSet.vertices; - triangleSet.indices.setDataUint(vertexSet.indices); - } else { - QTriangulator triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet 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 triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet vertexSet = triangulator.polyline(); - polyLineSet.vertices = vertexSet.vertices; - polyLineSet.indices.setDataUint(vertexSet.indices); - } else { - QTriangulator triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet 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 triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet vertexSet = triangulator.polyline(); - polyLineSet.vertices = vertexSet.vertices; - polyLineSet.indices.setDataUint(vertexSet.indices); - } else { - QTriangulator triangulator; - triangulator.initialize(path, matrix, lod); - QVertexSet 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 -#include -#include - -QT_BEGIN_NAMESPACE - -class Q_GUI_EXPORT QVertexIndexVector -{ -public: - enum Type { - UnsignedInt, - UnsignedShort - }; - - inline Type type() const { return t; } - - inline void setDataUint(const QVector &data) - { - t = UnsignedInt; - indices32 = data; - } - - inline void setDataUshort(const QVector &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 indices32; - QVector 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 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 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 diff --git a/src/gui/painting/painting.pri b/src/gui/painting/painting.pri index 2f927aeddb..00f2375923 100644 --- a/src/gui/painting/painting.pri +++ b/src/gui/painting/painting.pri @@ -42,6 +42,7 @@ HEADERS += \ painting/qpolygonclipper_p.h \ painting/qrasterdefs_p.h \ painting/qrasterizer_p.h \ + painting/qrbtree_p.h \ painting/qregion.h \ painting/qrgb.h \ painting/qrgba64.h \ @@ -49,6 +50,8 @@ HEADERS += \ painting/qstroker_p.h \ painting/qtextureglyphcache_p.h \ painting/qtransform.h \ + painting/qtriangulatingstroker_p.h \ + painting/qtriangulator_p.h \ painting/qplatformbackingstore.h \ painting/qpathsimplifier_p.h @@ -92,6 +95,8 @@ SOURCES += \ painting/qstroker.cpp \ painting/qtextureglyphcache.cpp \ painting/qtransform.cpp \ + painting/qtriangulatingstroker.cpp \ + painting/qtriangulator.cpp \ painting/qplatformbackingstore.cpp \ painting/qpathsimplifier.cpp diff --git a/src/gui/painting/qrbtree_p.h b/src/gui/painting/qrbtree_p.h new file mode 100644 index 0000000000..d3ee23a91c --- /dev/null +++ b/src/gui/painting/qrbtree_p.h @@ -0,0 +1,571 @@ +/**************************************************************************** +** +** 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 + +QT_BEGIN_NAMESPACE + +template +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 +inline QRBTree::~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 +inline void QRBTree::clear() +{ + if (root) + delete root; + root = 0; +} + +template +void QRBTree::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 +void QRBTree::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 +void QRBTree::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 +inline void QRBTree::attachLeft(Node *parent, Node *child) +{ + Q_ASSERT(!parent->left); + parent->left = child; + child->parent = parent; + update(child); +} + +template +inline void QRBTree::attachRight(Node *parent, Node *child) +{ + Q_ASSERT(!parent->right); + parent->right = child; + child->parent = parent; + update(child); +} + +template +void QRBTree::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 +void QRBTree::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 +void QRBTree::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 +void QRBTree::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 +void QRBTree::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 +inline typename QRBTree::Node *QRBTree::front(Node *node) const +{ + while (node->left) + node = node->left; + return node; +} + +template +inline typename QRBTree::Node *QRBTree::back(Node *node) const +{ + while (node->right) + node = node->right; + return node; +} + +template +typename QRBTree::Node *QRBTree::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 +typename QRBTree::Node *QRBTree::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 +int QRBTree::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 +bool QRBTree::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 +inline bool QRBTree::validate() const +{ + return checkRedBlackProperty(root) && blackDepth(root) != -1; +} + +template +inline void QRBTree::deleteNode(Node *&node) +{ + Q_ASSERT(node); + detach(node); + node->right = freeList; + freeList = node; + node = 0; +} + +template +inline typename QRBTree::Node *QRBTree::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 +int QRBTree::order(Node *left, Node *right) +{ + Q_ASSERT(left && right); + if (left == right) + return 0; + + QVector leftAncestors; + QVector 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/painting/qtriangulatingstroker.cpp b/src/gui/painting/qtriangulatingstroker.cpp new file mode 100644 index 0000000000..d9a3231165 --- /dev/null +++ b/src/gui/painting/qtriangulatingstroker.cpp @@ -0,0 +1,613 @@ +/**************************************************************************** +** +** 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 + +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(4, realWidth * CURVE_FLATNESS); + } else { + m_curvyness_add = m_width; + m_curvyness_mul = CURVE_FLATNESS / m_inv_scale; + m_roundness = qMax(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 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(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 (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 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 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 &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(64, (rad + curvynessAdd) * curvynessMul); + if (threshold < 4) + threshold = 4; + + qreal threshold_minus_1 = threshold - 1; + for (int i=0; i +#include +#include +#include +#include +#include +#include + +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 &points); + void endCapOrJoinClosed(const qreal *start, const qreal *cur, bool implicitClose, bool endsAtStart); + + + QDataBuffer 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 m_points; + QDataBuffer 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/painting/qtriangulator.cpp b/src/gui/painting/qtriangulator.cpp new file mode 100644 index 0000000000..7906011cd2 --- /dev/null +++ b/src/gui/painting/qtriangulator.cpp @@ -0,0 +1,2382 @@ +/**************************************************************************** +** +** 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifndef QT_NO_OPENGL +# include +# include +#endif +#include + +QT_BEGIN_NAMESPACE + +//#define Q_TRIANGULATOR_DEBUG + +#define Q_FIXED_POINT_SCALE 32 + +template +struct QVertexSet +{ + inline QVertexSet() { } + inline QVertexSet(const QVertexSet &other) : vertices(other.vertices), indices(other.indices) { } + QVertexSet &operator = (const QVertexSet &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 vertices; // [x[0], y[0], x[1], y[1], x[2], ...] + QVector 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 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 m_data; +}; + +template +void QMaxHeap::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 +T QMaxHeap::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::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::insert", "Hash set full."); +} + +bool QInt64Set::contains(quint64 key) const +{ + Q_ASSERT_X(m_array, "QInt64Hash::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::clear", "Hash set not allocated."); + for (int i = 0; i < m_capacity; ++i) + m_array[i] = UNUSED; + m_count = 0; +} + +//============================================================================// +// QTriangulator // +//============================================================================// +template +class QTriangulator +{ +public: + typedef QVarLengthArray ShortArray; + + //================================// + // QTriangulator::ComplexToSimple // + //================================// + friend class ComplexToSimple; + class ComplexToSimple + { + public: + inline ComplexToSimple(QTriangulator *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::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::Node *searchEdgeLeftOf(int edgeIndex) const; + QRBTree::Node *searchEdgeLeftOf(int edgeIndex, QRBTree::Node *after) const; + QPair::Node *, QRBTree::Node *> bounds(const QPodPoint &point) const; + QPair::Node *, QRBTree::Node *> outerBounds(const QPodPoint &point) const; + void splitEdgeListRange(QRBTree::Node *leftmost, QRBTree::Node *rightmost, int vertex, const QIntersectionPoint &intersectionPoint); + void reorderEdgeListRange(QRBTree::Node *leftmost, QRBTree::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 m_edges; + QRBTree m_edgeList; + QDataBuffer m_events; + QDataBuffer m_splits; + QMaxHeap m_topIntersection; + QInt64Set m_processedEdgePairs; + int m_initialPointCount; + }; +#ifdef Q_TRIANGULATOR_DEBUG + friend class ComplexToSimple::DebugDialog; +#endif + + //=================================// + // QTriangulator::SimpleToMonotone // + //=================================// + friend class SimpleToMonotone; + class SimpleToMonotone + { + public: + inline SimpleToMonotone(QTriangulator *parent) : m_parent(parent), m_edges(0), m_upperVertex(0) { } + void decompose(); + private: + enum VertexType {MergeVertex, EndVertex, RegularVertex, StartVertex, SplitVertex}; + + struct Edge + { + QRBTree::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::Node *searchEdgeLeftOfEdge(int edgeIndex) const; + // Returns the rightmost edge left of the given point. + QRBTree::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 m_edgeList; + QDataBuffer m_edges; + QDataBuffer m_upperVertex; + bool m_clockwiseOrder; + }; + + //====================================// + // QTriangulator::MonotoneToTriangles // + //====================================// + friend class MonotoneToTriangles; + class MonotoneToTriangles + { + public: + inline MonotoneToTriangles(QTriangulator *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 *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 triangulate(); + QVertexSet polyline(); +private: + QDataBuffer m_vertices; + QVector m_indices; + uint m_hint; +}; + +//============================================================================// +// QTriangulator // +//============================================================================// + +template +QVertexSet QTriangulator::triangulate() +{ + for (int i = 0; i < m_vertices.size(); ++i) { + Q_ASSERT(qAbs(m_vertices.at(i).x) < (1 << 21)); + Q_ASSERT(qAbs(m_vertices.at(i).y) < (1 << 21)); + } + + if (!(m_hint & (QVectorPath::OddEvenFill | QVectorPath::WindingFill))) + m_hint |= QVectorPath::OddEvenFill; + + if (m_hint & QVectorPath::NonConvexShapeMask) { + ComplexToSimple c2s(this); + c2s.decompose(); + SimpleToMonotone s2m(this); + s2m.decompose(); + } + MonotoneToTriangles m2t(this); + m2t.decompose(); + + QVertexSet 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 +QVertexSet QTriangulator::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 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 +void QTriangulator::initialize(const qreal *polygon, int count, uint hint, const QTransform &matrix) +{ + m_hint = hint; + m_vertices.resize(count); + m_indices.resize(count + 1); + for (int i = 0; i < count; ++i) { + qreal x, y; + matrix.map(polygon[2 * i + 0], polygon[2 * i + 1], &x, &y); + m_vertices.at(i).x = qRound(x * Q_FIXED_POINT_SCALE); + m_vertices.at(i).y = qRound(y * Q_FIXED_POINT_SCALE); + m_indices[i] = i; + } + m_indices[count] = T(-1); //Q_TRIANGULATE_END_OF_POLYGON +} + +template +void QTriangulator::initialize(const QVectorPath &path, const QTransform &matrix, qreal lod) +{ + m_hint = path.hints(); + // Curved paths will be converted to complex polygons. + m_hint &= ~QVectorPath::CurvedShapeMask; + + const qreal *p = path.points(); + const QPainterPath::ElementType *e = path.elements(); + if (e) { + for (int i = 0; i < path.elementCount(); ++i, ++e, p += 2) { + switch (*e) { + case QPainterPath::MoveToElement: + if (!m_indices.isEmpty()) + m_indices.push_back(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 +void QTriangulator::initialize(const QPainterPath &path, const QTransform &matrix, qreal lod) +{ + initialize(qtVectorPathForPath(path), matrix, lod); +} + +//============================================================================// +// QTriangulator::ComplexToSimple // +//============================================================================// +template +void QTriangulator::ComplexToSimple::decompose() +{ + m_initialPointCount = m_parent->m_vertices.size(); + initEdges(); + do { + calculateIntersections(); + } while (splitEdgesAtIntersections()); + + removeUnwantedEdgesAndConnect(); + removeUnusedPoints(); + + m_parent->m_indices.clear(); + QBitArray processed(m_edges.size(), false); + for (int first = 0; first < m_edges.size(); ++first) { + // If already processed, or if unused path, skip. + if (processed.at(first) || m_edges.at(first).next == -1) + continue; + + int i = first; + do { + Q_ASSERT(!processed.at(i)); + Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i); + m_parent->m_indices.push_back(m_edges.at(i).from); + processed.setBit(i); + i = m_edges.at(i).next; // CCW order + } while (i != first); + m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON + } +} + +template +void QTriangulator::ComplexToSimple::initEdges() +{ + // Initialize edge structure. + // 'next' and 'previous' are not being initialized at this point. + int first = 0; + for (int i = 0; i < m_parent->m_indices.size(); ++i) { + if (m_parent->m_indices.at(i) == 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 +bool QTriangulator::ComplexToSimple::calculateIntersection(int left, int right) +{ + const Edge &e1 = m_edges.at(left); + const Edge &e2 = m_edges.at(right); + + const QPodPoint &u1 = m_parent->m_vertices.at((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 +bool QTriangulator::ComplexToSimple::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const +{ + const Edge &leftEdge = m_edges.at(leftEdgeIndex); + const Edge &rightEdge = m_edges.at(rightEdgeIndex); + const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper()); + const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower()); + const QPodPoint &upper = m_parent->m_vertices.at(leftEdge.upper()); + if (upper.x < qMin(l.x, u.x)) + return true; + if (upper.x > qMax(l.x, u.x)) + return false; + qint64 d = 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 +QRBTree::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex) const +{ + QRBTree::Node *current = m_edgeList.root; + QRBTree::Node *result = 0; + while (current) { + if (edgeIsLeftOfEdge(edgeIndex, current->data)) { + current = current->left; + } else { + result = current; + current = current->right; + } + } + return result; +} + +template +QRBTree::Node *QTriangulator::ComplexToSimple::searchEdgeLeftOf(int edgeIndex, QRBTree::Node *after) const +{ + if (!m_edgeList.root) + return after; + QRBTree::Node *result = after; + QRBTree::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 +QPair::Node *, QRBTree::Node *> QTriangulator::ComplexToSimple::bounds(const QPodPoint &point) const +{ + QRBTree::Node *current = m_edgeList.root; + QPair::Node *, QRBTree::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 +QPair::Node *, QRBTree::Node *> QTriangulator::ComplexToSimple::outerBounds(const QPodPoint &point) const +{ + QRBTree::Node *current = m_edgeList.root; + QPair::Node *, QRBTree::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::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 +void QTriangulator::ComplexToSimple::splitEdgeListRange(QRBTree::Node *leftmost, QRBTree::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 +void QTriangulator::ComplexToSimple::reorderEdgeListRange(QRBTree::Node *leftmost, QRBTree::Node *rightmost) +{ + Q_ASSERT(leftmost && rightmost); + + QRBTree::Node *storeLeftmost = leftmost; + QRBTree::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 +void QTriangulator::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::Node *leftmost = m_edges.at(intersection.leftEdge).node; + QRBTree::Node *rightmost = m_edges.at(intersection.rightEdge).node; + + for (;;) { + QRBTree::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::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 +void QTriangulator::ComplexToSimple::fillPriorityQueue() +{ + m_events.reset(); + m_events.reserve(m_edges.size() * 2); + for (int i = 0; i < m_edges.size(); ++i) { + Q_ASSERT(m_edges.at(i).previous == -1 && m_edges.at(i).next == -1); + Q_ASSERT(m_edges.at(i).node == 0); + Q_ASSERT(m_edges.at(i).pointingUp == m_edges.at(i).originallyPointingUp); + Q_ASSERT(m_edges.at(i).pointingUp == (m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from))); + // Ignore zero-length edges. + if (m_parent->m_vertices.at(m_edges.at(i).to) != m_parent->m_vertices.at(m_edges.at(i).from)) { + QPodPoint upper = m_parent->m_vertices.at(m_edges.at(i).upper()); + QPodPoint lower = m_parent->m_vertices.at(m_edges.at(i).lower()); + Event upperEvent = {{upper.x, upper.y}, Event::Upper, i}; + Event lowerEvent = {{lower.x, lower.y}, Event::Lower, i}; + m_events.add(upperEvent); + m_events.add(lowerEvent); + } + } + + std::sort(m_events.data(), m_events.data() + m_events.size()); +} + +template +void QTriangulator::ComplexToSimple::calculateIntersections() +{ + fillPriorityQueue(); + + Q_ASSERT(m_topIntersection.empty()); + Q_ASSERT(m_edgeList.root == 0); + + // Find all intersection points. + while (!m_events.isEmpty()) { + Event event = m_events.last(); + sortEdgeList(event.point); + + // Find all edges in the edge list that contain the current vertex and mark them to be split later. + QPair::Node *, QRBTree::Node *> range = bounds(event.point); + QRBTree::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::Node *left = m_edgeList.previous(m_edges.at(i).node); + QRBTree::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::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::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 +int QTriangulator::ComplexToSimple::splitEdge(int splitIndex) +{ + const Split &split = m_splits.at(splitIndex); + Edge &lowerEdge = m_edges.at(split.edge); + Q_ASSERT(lowerEdge.node == 0); + Q_ASSERT(lowerEdge.previous == -1 && lowerEdge.next == -1); + + if (lowerEdge.from == split.vertex) + return split.edge; + if (lowerEdge.to == split.vertex) + return lowerEdge.next; + + // Check that angle >= 90 degrees. + //Q_ASSERT(qDot(m_points.at(m_edges.at(edgeIndex).from) - m_points.at(pointIndex), + // m_points.at(m_edges.at(edgeIndex).to) - m_points.at(pointIndex)) <= 0); + + Edge upperEdge = lowerEdge; + upperEdge.mayIntersect |= !split.accurate; // The edge may have been split before at an inaccurate split point. + lowerEdge.mayIntersect = !split.accurate; + if (lowerEdge.pointingUp) { + lowerEdge.to = upperEdge.from = split.vertex; + m_edges.add(upperEdge); + return m_edges.size() - 1; + } else { + lowerEdge.from = upperEdge.to = split.vertex; + m_edges.add(upperEdge); + return split.edge; + } +} + +template +bool QTriangulator::ComplexToSimple::splitEdgesAtIntersections() +{ + for (int i = 0; i < m_edges.size(); ++i) + m_edges.at(i).mayIntersect = false; + bool checkForNewIntersections = false; + for (int i = 0; i < m_splits.size(); ++i) { + splitEdge(i); + checkForNewIntersections |= !m_splits.at(i).accurate; + } + for (int i = 0; i < m_edges.size(); ++i) { + m_edges.at(i).originallyPointingUp = m_edges.at(i).pointingUp = + m_parent->m_vertices.at(m_edges.at(i).to) < m_parent->m_vertices.at(m_edges.at(i).from); + } + m_splits.reset(); + return checkForNewIntersections; +} + +template +void QTriangulator::ComplexToSimple::insertEdgeIntoVectorIfWanted(ShortArray &orderedEdges, int i) +{ + // Edges with zero length should not reach this part. + Q_ASSERT(m_parent->m_vertices.at(m_edges.at(i).from) != m_parent->m_vertices.at(m_edges.at(i).to)); + + // Skip edges with unwanted winding number. + int windingNumber = m_edges.at(i).winding; + if (m_edges.at(i).originallyPointingUp) + ++windingNumber; + + // Make sure exactly one fill rule is specified. + Q_ASSERT(((m_parent->m_hint & QVectorPath::WindingFill) != 0) != ((m_parent->m_hint & QVectorPath::OddEvenFill) != 0)); + + if ((m_parent->m_hint & QVectorPath::WindingFill) && windingNumber != 0 && windingNumber != 1) + return; + + // Skip cancelling edges. + if (!orderedEdges.isEmpty()) { + int j = orderedEdges[orderedEdges.size() - 1]; + // If the last edge is already connected in one end, it should not be cancelled. + if (m_edges.at(j).next == -1 && m_edges.at(j).previous == -1 + && (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(j).to)) + && (m_parent->m_vertices.at(m_edges.at(i).to) == m_parent->m_vertices.at(m_edges.at(j).from))) { + orderedEdges.removeLast(); + return; + } + } + orderedEdges.append(i); +} + +template +void QTriangulator::ComplexToSimple::removeUnwantedEdgesAndConnect() +{ + Q_ASSERT(m_edgeList.root == 0); + // Initialize priority queue. + fillPriorityQueue(); + + ShortArray orderedEdges; + + while (!m_events.isEmpty()) { + Event event = m_events.last(); + int edgeIndex = event.edge; + + // Check that all the edges in the list crosses the current scanline + //if (m_edgeList.root) { + // for (QRBTree::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::Node *, QRBTree::Node *> b = outerBounds(event.point); + if (m_edgeList.root) { + QRBTree::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::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::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 +void QTriangulator::ComplexToSimple::removeUnusedPoints() { + QBitArray used(m_parent->m_vertices.size(), false); + for (int i = 0; i < m_edges.size(); ++i) { + Q_ASSERT((m_edges.at(i).previous == -1) == (m_edges.at(i).next == -1)); + if (m_edges.at(i).next != -1) + used.setBit(m_edges.at(i).from); + } + QDataBuffer 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 +inline bool QTriangulator::ComplexToSimple::Event::operator < (const Event &other) const +{ + if (point == other.point) + return type < other.type; // 'Lower' has higher priority than 'Upper'. + return other.point < point; +} + +//============================================================================// +// QTriangulator::ComplexToSimple::DebugDialog // +//============================================================================// + +#ifdef Q_TRIANGULATOR_DEBUG +template +QTriangulator::ComplexToSimple::DebugDialog::DebugDialog(ComplexToSimple *parent, int currentVertex) + : m_parent(parent), m_vertex(currentVertex) +{ + QDataBuffer &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 +void QTriangulator::ComplexToSimple::DebugDialog::paintEvent(QPaintEvent *) +{ + QPainter p(this); + p.setRenderHint(QPainter::Antialiasing, true); + p.fillRect(rect(), Qt::black); + QDataBuffer &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 &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::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 &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 +void QTriangulator::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 +void QTriangulator::ComplexToSimple::DebugDialog::mouseMoveEvent(QMouseEvent *event) +{ + if (event->buttons() & Qt::LeftButton) { + QPointF delta = event->pos() - m_lastMousePos; + delta.setX(delta.x() * m_window.width() / width()); + delta.setY(delta.y() * m_window.height() / height()); + m_window.translate(-delta.x(), -delta.y()); + m_lastMousePos = event->pos(); + event->accept(); + update(); + } +} + +template +void QTriangulator::ComplexToSimple::DebugDialog::mousePressEvent(QMouseEvent *event) +{ + if (event->button() == Qt::LeftButton) + m_lastMousePos = event->pos(); + event->accept(); +} + + +#endif + +//============================================================================// +// QTriangulator::SimpleToMonotone // +//============================================================================// +template +void QTriangulator::SimpleToMonotone::decompose() +{ + setupDataStructures(); + removeZeroLengthEdges(); + monotoneDecomposition(); + + m_parent->m_indices.clear(); + QBitArray processed(m_edges.size(), false); + for (int first = 0; first < m_edges.size(); ++first) { + if (processed.at(first)) + continue; + int i = first; + do { + Q_ASSERT(!processed.at(i)); + Q_ASSERT(m_edges.at(m_edges.at(i).next).previous == i); + m_parent->m_indices.push_back(m_edges.at(i).from); + processed.setBit(i); + i = m_edges.at(i).next; + } while (i != first); + if (m_parent->m_indices.size() > 0 && m_parent->m_indices.back() != T(-1)) // Q_TRIANGULATE_END_OF_POLYGON + m_parent->m_indices.push_back(T(-1)); // Q_TRIANGULATE_END_OF_POLYGON + } +} + +template +void QTriangulator::SimpleToMonotone::setupDataStructures() +{ + int i = 0; + Edge e; + e.node = 0; + e.twin = -1; + + while (i + 3 <= m_parent->m_indices.size()) { + int start = m_edges.size(); + + do { + e.from = m_parent->m_indices.at(i); + e.type = RegularVertex; + e.next = m_edges.size() + 1; + e.previous = m_edges.size() - 1; + m_edges.add(e); + ++i; + Q_ASSERT(i < m_parent->m_indices.size()); + } while (m_parent->m_indices.at(i) != 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 +void QTriangulator::SimpleToMonotone::removeZeroLengthEdges() +{ + for (int i = 0; i < m_edges.size(); ++i) { + if (m_parent->m_vertices.at(m_edges.at(i).from) == m_parent->m_vertices.at(m_edges.at(i).to)) { + m_edges.at(m_edges.at(i).previous).next = m_edges.at(i).next; + m_edges.at(m_edges.at(i).next).previous = m_edges.at(i).previous; + m_edges.at(m_edges.at(i).next).from = m_edges.at(i).from; + m_edges.at(i).next = -1; // Mark as removed. + } + } + + QDataBuffer 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 +void QTriangulator::SimpleToMonotone::fillPriorityQueue() +{ + m_upperVertex.reset(); + m_upperVertex.reserve(m_edges.size()); + for (int i = 0; i < m_edges.size(); ++i) + m_upperVertex.add(i); + CompareVertices cmp(this); + 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 +bool QTriangulator::SimpleToMonotone::edgeIsLeftOfEdge(int leftEdgeIndex, int rightEdgeIndex) const +{ + const Edge &leftEdge = m_edges.at(leftEdgeIndex); + const Edge &rightEdge = m_edges.at(rightEdgeIndex); + const QPodPoint &u = m_parent->m_vertices.at(rightEdge.upper()); + const QPodPoint &l = m_parent->m_vertices.at(rightEdge.lower()); + qint64 d = 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 +QRBTree::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfEdge(int edgeIndex) const +{ + QRBTree::Node *current = m_edgeList.root; + QRBTree::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 +QRBTree::Node *QTriangulator::SimpleToMonotone::searchEdgeLeftOfPoint(int pointIndex) const +{ + QRBTree::Node *current = m_edgeList.root; + QRBTree::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 +void QTriangulator::SimpleToMonotone::classifyVertex(int i) +{ + Edge &e2 = m_edges.at(i); + const Edge &e1 = m_edges.at(e2.previous); + + bool startOrSplit = (e1.pointingUp && !e2.pointingUp); + bool endOrMerge = (!e1.pointingUp && e2.pointingUp); + + const QPodPoint &p1 = m_parent->m_vertices.at(e1.from); + const QPodPoint &p2 = m_parent->m_vertices.at(e2.from); + const QPodPoint &p3 = m_parent->m_vertices.at(e2.to); + qint64 d = 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 +void QTriangulator::SimpleToMonotone::classifyVertices() +{ + for (int i = 0; i < m_edges.size(); ++i) + classifyVertex(i); +} + +template +bool QTriangulator::SimpleToMonotone::pointIsInSector(const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2, const QPodPoint &v3) +{ + bool leftOfPreviousEdge = !qPointIsLeftOfLine(p, v2, v1); + bool leftOfNextEdge = !qPointIsLeftOfLine(p, v3, v2); + + if (qPointIsLeftOfLine(v1, v2, v3)) + return leftOfPreviousEdge && leftOfNextEdge; + else + return leftOfPreviousEdge || leftOfNextEdge; +} + +template +bool QTriangulator::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 +int QTriangulator::SimpleToMonotone::findSector(int edge, int vertex) +{ + while (!pointIsInSector(vertex, edge)) { + edge = m_edges.at(m_edges.at(edge).previous).twin; + Q_ASSERT(edge != -1); + } + return edge; +} + +template +void QTriangulator::SimpleToMonotone::createDiagonal(int lower, int upper) +{ + lower = findSector(lower, upper); + upper = findSector(upper, lower); + + int prevLower = m_edges.at(lower).previous; + int prevUpper = m_edges.at(upper).previous; + + Edge e; + + e.twin = m_edges.size() + 1; + e.next = upper; + e.previous = prevLower; + e.from = m_edges.at(lower).from; + e.to = m_edges.at(upper).from; + m_edges.at(upper).previous = m_edges.at(prevLower).next = int(m_edges.size()); + m_edges.add(e); + + e.twin = m_edges.size() - 1; + e.next = lower; + e.previous = prevUpper; + e.from = m_edges.at(upper).from; + e.to = m_edges.at(lower).from; + m_edges.at(lower).previous = m_edges.at(prevUpper).next = int(m_edges.size()); + m_edges.add(e); +} + +template +void QTriangulator::SimpleToMonotone::monotoneDecomposition() +{ + if (m_edges.isEmpty()) + return; + + Q_ASSERT(!m_edgeList.root); + QDataBuffer > 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::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(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(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(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(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::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::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(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(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(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 +bool QTriangulator::SimpleToMonotone::CompareVertices::operator () (int i, int j) const +{ + if (m_parent->m_edges.at(i).from == m_parent->m_edges.at(j).from) + return m_parent->m_edges.at(i).type > m_parent->m_edges.at(j).type; + return m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(i).from) > + m_parent->m_parent->m_vertices.at(m_parent->m_edges.at(j).from); +} + +//============================================================================// +// QTriangulator::MonotoneToTriangles // +//============================================================================// +template +void QTriangulator::MonotoneToTriangles::decompose() +{ + QVector result; + QDataBuffer 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() +{ +#ifndef QT_NO_OPENGL + QOpenGLContext *context = QOpenGLContext::currentContext(); + if (!context) + return false; + return static_cast(context->functions())->hasOpenGLExtension(QOpenGLExtensions::ElementIndexUint); +#else + return false; +#endif +} + +Q_GUI_EXPORT QTriangleSet qTriangulate(const qreal *polygon, + int count, uint hint, const QTransform &matrix) +{ + QTriangleSet triangleSet; + if (hasElementIndexUint()) { + QTriangulator triangulator; + triangulator.initialize(polygon, count, hint, matrix); + QVertexSet vertexSet = triangulator.triangulate(); + triangleSet.vertices = vertexSet.vertices; + triangleSet.indices.setDataUint(vertexSet.indices); + + } else { + QTriangulator triangulator; + triangulator.initialize(polygon, count, hint, matrix); + QVertexSet 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 triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet vertexSet = triangulator.triangulate(); + triangleSet.vertices = vertexSet.vertices; + triangleSet.indices.setDataUint(vertexSet.indices); + } else { + QTriangulator triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet 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 triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet vertexSet = triangulator.triangulate(); + triangleSet.vertices = vertexSet.vertices; + triangleSet.indices.setDataUint(vertexSet.indices); + } else { + QTriangulator triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet 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 triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet vertexSet = triangulator.polyline(); + polyLineSet.vertices = vertexSet.vertices; + polyLineSet.indices.setDataUint(vertexSet.indices); + } else { + QTriangulator triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet 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 triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet vertexSet = triangulator.polyline(); + polyLineSet.vertices = vertexSet.vertices; + polyLineSet.indices.setDataUint(vertexSet.indices); + } else { + QTriangulator triangulator; + triangulator.initialize(path, matrix, lod); + QVertexSet vertexSet = triangulator.polyline(); + polyLineSet.vertices = vertexSet.vertices; + polyLineSet.indices.setDataUshort(vertexSet.indices); + } + return polyLineSet; +} + +QT_END_NAMESPACE diff --git a/src/gui/painting/qtriangulator_p.h b/src/gui/painting/qtriangulator_p.h new file mode 100644 index 0000000000..4d1aba099c --- /dev/null +++ b/src/gui/painting/qtriangulator_p.h @@ -0,0 +1,148 @@ +/**************************************************************************** +** +** 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 +#include +#include + +QT_BEGIN_NAMESPACE + +class Q_GUI_EXPORT QVertexIndexVector +{ +public: + enum Type { + UnsignedInt, + UnsignedShort + }; + + inline Type type() const { return t; } + + inline void setDataUint(const QVector &data) + { + t = UnsignedInt; + indices32 = data; + } + + inline void setDataUshort(const QVector &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 indices32; + QVector 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 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 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 -- cgit v1.2.3