diff options
Diffstat (limited to 'src/gui/painting/qpathclipper.cpp')
-rw-r--r-- | src/gui/painting/qpathclipper.cpp | 2149 |
1 files changed, 2149 insertions, 0 deletions
diff --git a/src/gui/painting/qpathclipper.cpp b/src/gui/painting/qpathclipper.cpp new file mode 100644 index 0000000000..d18fba2e7c --- /dev/null +++ b/src/gui/painting/qpathclipper.cpp @@ -0,0 +1,2149 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the Technology Preview License Agreement accompanying +** this package. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** If you have questions regarding the use of this file, please contact +** Nokia at qt-info@nokia.com. +** +** +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qpathclipper_p.h" + +#include <private/qbezier_p.h> +#include <private/qdatabuffer_p.h> +#include <private/qnumeric_p.h> +#include <qmath.h> + +/** + The algorithm is as follows: + + 1. Find all intersections between the two paths (including self-intersections), + and build a winged edge structure of non-intersecting parts. + 2. While there are more unhandled edges: + 3. Pick a y-coordinate from an unhandled edge. + 4. Intersect the horizontal line at y-coordinate with all edges. + 5. Traverse intersections left to right deciding whether each subpath should be added or not. + 6. If the subpath should be added, traverse the winged-edge structure and add the edges to + a separate winged edge structure. + 7. Mark all edges in subpaths crossing the horizontal line as handled. + 8. (Optional) Simplify the resulting winged edge structure by merging shared edges. + 9. Convert the resulting winged edge structure to a painter path. + */ + +#include <qdebug.h> + +QT_BEGIN_NAMESPACE + +static inline bool fuzzyIsNull(qreal d) +{ + if (sizeof(qreal) == sizeof(double)) + return qAbs(d) <= 1e-12; + else + return qAbs(d) <= 1e-5f; +} + +static inline bool comparePoints(const QPointF &a, const QPointF &b) +{ + return fuzzyIsNull(a.x() - b.x()) + && fuzzyIsNull(a.y() - b.y()); +} + +//#define QDEBUG_CLIPPER +static qreal dot(const QPointF &a, const QPointF &b) +{ + return a.x() * b.x() + a.y() * b.y(); +} + +static void normalize(double &x, double &y) +{ + double reciprocal = 1 / qSqrt(x * x + y * y); + x *= reciprocal; + y *= reciprocal; +} + +struct QIntersection +{ + qreal alphaA; + qreal alphaB; + + QPointF pos; +}; + +class QIntersectionFinder +{ +public: + void produceIntersections(QPathSegments &segments); + bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const; + +private: + bool linesIntersect(const QLineF &a, const QLineF &b) const; +}; + +bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const +{ + const QPointF p1 = a.p1(); + const QPointF p2 = a.p2(); + + const QPointF q1 = b.p1(); + const QPointF q2 = b.p2(); + + if (comparePoints(p1, p2) || comparePoints(q1, q2)) + return false; + + const bool p1_equals_q1 = comparePoints(p1, q1); + const bool p2_equals_q2 = comparePoints(p2, q2); + + if (p1_equals_q1 && p2_equals_q2) + return true; + + const bool p1_equals_q2 = comparePoints(p1, q2); + const bool p2_equals_q1 = comparePoints(p2, q1); + + if (p1_equals_q2 && p2_equals_q1) + return true; + + const QPointF pDelta = p2 - p1; + const QPointF qDelta = q2 - q1; + + const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x(); + + if (qFuzzyIsNull(par)) { + const QPointF normal(-pDelta.y(), pDelta.x()); + + // coinciding? + if (qFuzzyIsNull(dot(normal, q1 - p1))) { + const qreal dp = dot(pDelta, pDelta); + + const qreal tq1 = dot(pDelta, q1 - p1); + const qreal tq2 = dot(pDelta, q2 - p1); + + if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp)) + return true; + + const qreal dq = dot(qDelta, qDelta); + + const qreal tp1 = dot(qDelta, p1 - q1); + const qreal tp2 = dot(qDelta, p2 - q1); + + if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq)) + return true; + } + + return false; + } + + const qreal invPar = 1 / par; + + const qreal tp = (qDelta.y() * (q1.x() - p1.x()) - + qDelta.x() * (q1.y() - p1.y())) * invPar; + + if (tp < 0 || tp > 1) + return false; + + const qreal tq = (pDelta.y() * (q1.x() - p1.x()) - + pDelta.x() * (q1.y() - p1.y())) * invPar; + + return tq >= 0 && tq <= 1; +} + +bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const +{ + if (a.segments() == 0 || b.segments() == 0) + return false; + + const QRectF &rb0 = b.elementBounds(0); + + qreal minX = rb0.left(); + qreal minY = rb0.top(); + qreal maxX = rb0.right(); + qreal maxY = rb0.bottom(); + + for (int i = 1; i < b.segments(); ++i) { + const QRectF &r = b.elementBounds(i); + minX = qMin(minX, r.left()); + minY = qMin(minY, r.top()); + maxX = qMax(maxX, r.right()); + maxY = qMax(maxY, r.bottom()); + } + + QRectF rb(minX, minY, maxX - minX, maxY - minY); + + for (int i = 0; i < a.segments(); ++i) { + const QRectF &r1 = a.elementBounds(i); + + if (r1.left() > rb.right() || rb.left() > r1.right()) + continue; + if (r1.top() > rb.bottom() || rb.top() > r1.bottom()) + continue; + + for (int j = 0; j < b.segments(); ++j) { + const QRectF &r2 = b.elementBounds(j); + + if (r1.left() > r2.right() || r2.left() > r1.right()) + continue; + if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) + continue; + + if (linesIntersect(a.lineAt(i), b.lineAt(j))) + return true; + } + } + + return false; +} + +namespace { +struct TreeNode +{ + qreal splitLeft; + qreal splitRight; + bool leaf; + + int lowestLeftIndex; + int lowestRightIndex; + + union { + struct { + int first; + int last; + } interval; + struct { + int left; + int right; + } children; + } index; +}; + +struct RectF +{ + qreal x1; + qreal y1; + qreal x2; + qreal y2; +}; + +class SegmentTree +{ +public: + SegmentTree(QPathSegments &segments); + + QRectF boundingRect() const; + + void produceIntersections(int segment); + +private: + TreeNode buildTree(int first, int last, int depth, const RectF &bounds); + + void produceIntersectionsLeaf(const TreeNode &node, int segment); + void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis); + void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections); + + QPathSegments &m_segments; + QVector<int> m_index; + + RectF m_bounds; + + QVector<TreeNode> m_tree; + QDataBuffer<QIntersection> m_intersections; +}; + +SegmentTree::SegmentTree(QPathSegments &segments) + : m_segments(segments), + m_intersections(0) +{ + m_bounds.x1 = qt_inf(); + m_bounds.y1 = qt_inf(); + m_bounds.x2 = -qt_inf(); + m_bounds.y2 = -qt_inf(); + + m_index.resize(m_segments.segments()); + + for (int i = 0; i < m_index.size(); ++i) { + m_index[i] = i; + + const QRectF &segmentBounds = m_segments.elementBounds(i); + + if (segmentBounds.left() < m_bounds.x1) + m_bounds.x1 = segmentBounds.left(); + if (segmentBounds.top() < m_bounds.y1) + m_bounds.y1 = segmentBounds.top(); + if (segmentBounds.right() > m_bounds.x2) + m_bounds.x2 = segmentBounds.right(); + if (segmentBounds.bottom() > m_bounds.y2) + m_bounds.y2 = segmentBounds.bottom(); + } + + m_tree.resize(1); + + TreeNode root = buildTree(0, m_index.size(), 0, m_bounds); + m_tree[0] = root; +} + +QRectF SegmentTree::boundingRect() const +{ + return QRectF(QPointF(m_bounds.x1, m_bounds.y1), + QPointF(m_bounds.x2, m_bounds.y2)); +} + +static inline qreal coordinate(const QPointF &pos, int axis) +{ + return axis == 0 ? pos.x() : pos.y(); +} + +TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds) +{ + if (depth >= 24 || (last - first) <= 10) { + TreeNode node; + node.leaf = true; + node.index.interval.first = first; + node.index.interval.last = last; + + return node; + } + + int splitAxis = (depth & 1); + + TreeNode node; + node.leaf = false; + + qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]); + + node.splitLeft = (&bounds.x1)[splitAxis]; + node.splitRight = (&bounds.x2)[splitAxis]; + + node.lowestLeftIndex = INT_MAX; + node.lowestRightIndex = INT_MAX; + + const int treeSize = m_tree.size(); + + node.index.children.left = treeSize; + node.index.children.right = treeSize + 1; + + m_tree.resize(treeSize + 2); + + int l = first; + int r = last - 1; + + // partition into left and right sets + while (l <= r) { + const int index = m_index.at(l); + const QRectF &segmentBounds = m_segments.elementBounds(index); + + qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis); + + if (coordinate(segmentBounds.center(), splitAxis) < split) { + qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis); + if (highCoordinate > node.splitLeft) + node.splitLeft = highCoordinate; + if (index < node.lowestLeftIndex) + node.lowestLeftIndex = index; + ++l; + } else { + if (lowCoordinate < node.splitRight) + node.splitRight = lowCoordinate; + if (index < node.lowestRightIndex) + node.lowestRightIndex = index; + qSwap(m_index[l], m_index[r]); + --r; + } + } + + RectF lbounds = bounds; + (&lbounds.x2)[splitAxis] = node.splitLeft; + + RectF rbounds = bounds; + (&rbounds.x1)[splitAxis] = node.splitRight; + + TreeNode left = buildTree(first, l, depth + 1, lbounds); + m_tree[node.index.children.left] = left; + + TreeNode right = buildTree(l, last, depth + 1, rbounds); + m_tree[node.index.children.right] = right; + + return node; +} + +void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections) +{ + const QPointF p1 = a.p1(); + const QPointF p2 = a.p2(); + + const QPointF q1 = b.p1(); + const QPointF q2 = b.p2(); + + if (comparePoints(p1, p2) || comparePoints(q1, q2)) + return; + + const bool p1_equals_q1 = comparePoints(p1, q1); + const bool p2_equals_q2 = comparePoints(p2, q2); + + if (p1_equals_q1 && p2_equals_q2) + return; + + const bool p1_equals_q2 = comparePoints(p1, q2); + const bool p2_equals_q1 = comparePoints(p2, q1); + + if (p1_equals_q2 && p2_equals_q1) + return; + + const QPointF pDelta = p2 - p1; + const QPointF qDelta = q2 - q1; + + const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x(); + + if (qFuzzyIsNull(par)) { + const QPointF normal(-pDelta.y(), pDelta.x()); + + // coinciding? + if (qFuzzyIsNull(dot(normal, q1 - p1))) { + const qreal invDp = 1 / dot(pDelta, pDelta); + + const qreal tq1 = dot(pDelta, q1 - p1) * invDp; + const qreal tq2 = dot(pDelta, q2 - p1) * invDp; + + if (tq1 > 0 && tq1 < 1) { + QIntersection intersection; + intersection.alphaA = tq1; + intersection.alphaB = 0; + intersection.pos = q1; + intersections.add(intersection); + } + + if (tq2 > 0 && tq2 < 1) { + QIntersection intersection; + intersection.alphaA = tq2; + intersection.alphaB = 1; + intersection.pos = q2; + intersections.add(intersection); + } + + const qreal invDq = 1 / dot(qDelta, qDelta); + + const qreal tp1 = dot(qDelta, p1 - q1) * invDq; + const qreal tp2 = dot(qDelta, p2 - q1) * invDq; + + if (tp1 > 0 && tp1 < 1) { + QIntersection intersection; + intersection.alphaA = 0; + intersection.alphaB = tp1; + intersection.pos = p1; + intersections.add(intersection); + } + + if (tp2 > 0 && tp2 < 1) { + QIntersection intersection; + intersection.alphaA = 1; + intersection.alphaB = tp2; + intersection.pos = p2; + intersections.add(intersection); + } + } + + return; + } + + // if the lines are not parallel and share a common end point, then they + // don't intersect + if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2) + return; + + + const qreal tp = (qDelta.y() * (q1.x() - p1.x()) - + qDelta.x() * (q1.y() - p1.y())) / par; + const qreal tq = (pDelta.y() * (q1.x() - p1.x()) - + pDelta.x() * (q1.y() - p1.y())) / par; + + if (tp<0 || tp>1 || tq<0 || tq>1) + return; + + const bool p_zero = qFuzzyIsNull(tp); + const bool p_one = qFuzzyIsNull(tp - 1); + + const bool q_zero = qFuzzyIsNull(tq); + const bool q_one = qFuzzyIsNull(tq - 1); + + if ((q_zero || q_one) && (p_zero || p_one)) + return; + + QPointF pt; + if (p_zero) { + pt = p1; + } else if (p_one) { + pt = p2; + } else if (q_zero) { + pt = q1; + } else if (q_one) { + pt = q2; + } else { + pt = q1 + (q2 - q1) * tq; + } + + QIntersection intersection; + intersection.alphaA = tp; + intersection.alphaB = tq; + intersection.pos = pt; + intersections.add(intersection); +} + +void SegmentTree::produceIntersections(int segment) +{ + const QRectF &segmentBounds = m_segments.elementBounds(segment); + + RectF sbounds; + sbounds.x1 = segmentBounds.left(); + sbounds.y1 = segmentBounds.top(); + sbounds.x2 = segmentBounds.right(); + sbounds.y2 = segmentBounds.bottom(); + + produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0); +} + +void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment) +{ + const QRectF &r1 = m_segments.elementBounds(segment); + const QLineF lineA = m_segments.lineAt(segment); + + for (int i = node.index.interval.first; i < node.index.interval.last; ++i) { + const int other = m_index.at(i); + if (other >= segment) + continue; + + const QRectF &r2 = m_segments.elementBounds(other); + + if (r1.left() > r2.right() || r2.left() > r1.right()) + continue; + if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) + continue; + + m_intersections.reset(); + + const QLineF lineB = m_segments.lineAt(other); + + intersectLines(lineA, lineB, m_intersections); + + for (int k = 0; k < m_intersections.size(); ++k) { + QPathSegments::Intersection i_isect, j_isect; + i_isect.vertex = j_isect.vertex = m_segments.addPoint(m_intersections.at(k).pos); + + i_isect.t = m_intersections.at(k).alphaA; + j_isect.t = m_intersections.at(k).alphaB; + + i_isect.next = 0; + j_isect.next = 0; + + m_segments.addIntersection(segment, i_isect); + m_segments.addIntersection(other, j_isect); + } + } +} + +void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis) +{ + if (node.leaf) { + produceIntersectionsLeaf(node, segment); + return; + } + + RectF lbounds = nodeBounds; + (&lbounds.x2)[axis] = node.splitLeft; + + RectF rbounds = nodeBounds; + (&rbounds.x1)[axis] = node.splitRight; + + if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft) + produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis); + + if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight) + produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis); +} + +} + +void QIntersectionFinder::produceIntersections(QPathSegments &segments) +{ + SegmentTree tree(segments); + + for (int i = 0; i < segments.segments(); ++i) + tree.produceIntersections(i); +} + +class QKdPointTree +{ +public: + enum Traversal { + TraverseBoth, + TraverseLeft, + TraverseRight, + TraverseNone + }; + + struct Node { + int point; + int id; + + Node *left; + Node *right; + }; + + QKdPointTree(const QPathSegments &segments) + : m_segments(&segments) + , m_nodes(m_segments->points()) + , m_id(0) + { + m_nodes.resize(m_segments->points()); + + for (int i = 0; i < m_nodes.size(); ++i) { + m_nodes.at(i).point = i; + m_nodes.at(i).id = -1; + } + + m_rootNode = build(0, m_nodes.size()); + } + + int build(int begin, int end, int depth = 0); + + Node *rootNode() + { + return &m_nodes.at(m_rootNode); + } + + inline int nextId() + { + return m_id++; + } + +private: + const QPathSegments *m_segments; + QDataBuffer<Node> m_nodes; + + int m_rootNode; + int m_id; +}; + +template <typename T> +void qTraverseKdPointTree(QKdPointTree::Node &node, T &t, int depth = 0) +{ + QKdPointTree::Traversal status = t(node, depth); + + const bool traverseRight = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseRight); + const bool traverseLeft = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseLeft); + + if (traverseLeft && node.left) + QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.left, t, depth + 1); + + if (traverseRight && node.right) + QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.right, t, depth + 1); +} + +static inline qreal component(const QPointF &point, unsigned int i) +{ + Q_ASSERT(i < 2); + const qreal components[] = { point.x(), point.y() }; + return components[i]; +} + +int QKdPointTree::build(int begin, int end, int depth) +{ + Q_ASSERT(end > begin); + + const qreal pivot = component(m_segments->pointAt(m_nodes.at(begin).point), depth & 1); + + int first = begin + 1; + int last = end - 1; + + while (first <= last) { + const qreal value = component(m_segments->pointAt(m_nodes.at(first).point), depth & 1); + + if (value < pivot) + ++first; + else { + qSwap(m_nodes.at(first), m_nodes.at(last)); + --last; + } + } + + qSwap(m_nodes.at(last), m_nodes.at(begin)); + + if (last > begin) + m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1)); + else + m_nodes.at(last).left = 0; + + if (last + 1 < end) + m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1)); + else + m_nodes.at(last).right = 0; + + return last; +} + +class QKdPointFinder +{ +public: + QKdPointFinder(int point, const QPathSegments &segments, QKdPointTree &tree) + : m_point(point) + , m_result(-1) + , m_segments(&segments) + , m_tree(&tree) + { + pointComponents[0] = segments.pointAt(point).x(); + pointComponents[1] = segments.pointAt(point).y(); + } + + inline QKdPointTree::Traversal operator()(QKdPointTree::Node &node, int depth) + { + if (m_result != -1) + return QKdPointTree::TraverseNone; + + const QPointF &nodePoint = m_segments->pointAt(node.point); + + const qreal pivotComponents[] = { nodePoint.x(), nodePoint.y() }; + + const qreal pivot = pivotComponents[depth & 1]; + const qreal value = pointComponents[depth & 1]; + + if (fuzzyIsNull(pivot - value)) { + const qreal pivot2 = pivotComponents[(depth + 1) & 1]; + const qreal value2 = pointComponents[(depth + 1) & 1]; + + if (fuzzyIsNull(pivot2 - value2)) { + if (node.id < 0) + node.id = m_tree->nextId(); + + m_result = node.id; + return QKdPointTree::TraverseNone; + } else + return QKdPointTree::TraverseBoth; + } else if (value < pivot) { + return QKdPointTree::TraverseLeft; + } else { + return QKdPointTree::TraverseRight; + } + } + + int result() const + { + return m_result; + } + +private: + int m_point; + qreal pointComponents[2]; + int m_result; + const QPathSegments *m_segments; + QKdPointTree *m_tree; +}; + +// merge all points that are within qFuzzyCompare range of each other +void QPathSegments::mergePoints() +{ + QKdPointTree tree(*this); + + if (tree.rootNode()) { + QDataBuffer<QPointF> mergedPoints(points()); + QDataBuffer<int> pointIndices(points()); + + for (int i = 0; i < points(); ++i) { + QKdPointFinder finder(i, *this, tree); + QT_PREPEND_NAMESPACE(qTraverseKdPointTree<QKdPointFinder>)(*tree.rootNode(), finder); + + Q_ASSERT(finder.result() != -1); + + if (finder.result() >= mergedPoints.size()) + mergedPoints << m_points.at(i); + + pointIndices << finder.result(); + } + + for (int i = 0; i < m_segments.size(); ++i) { + m_segments.at(i).va = pointIndices.at(m_segments.at(i).va); + m_segments.at(i).vb = pointIndices.at(m_segments.at(i).vb); + } + + for (int i = 0; i < m_intersections.size(); ++i) + m_intersections.at(i).vertex = pointIndices.at(m_intersections.at(i).vertex); + + m_points.swap(mergedPoints); + } +} + +void QWingedEdge::intersectAndAdd() +{ + QIntersectionFinder finder; + finder.produceIntersections(m_segments); + + m_segments.mergePoints(); + + for (int i = 0; i < m_segments.points(); ++i) + addVertex(m_segments.pointAt(i)); + + QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments()); + for (int i = 0; i < m_segments.segments(); ++i) { + intersections.reset(); + + int pathId = m_segments.pathId(i); + + const QPathSegments::Intersection *isect = m_segments.intersectionAt(i); + while (isect) { + intersections << *isect; + + if (isect->next) { + isect += isect->next; + } else { + isect = 0; + } + } + + qSort(intersections.data(), intersections.data() + intersections.size()); + + int first = m_segments.segmentAt(i).va; + int second = m_segments.segmentAt(i).vb; + + int last = first; + for (int j = 0; j < intersections.size(); ++j) { + const QPathSegments::Intersection &isect = intersections.at(j); + + QPathEdge *ep = edge(addEdge(last, isect.vertex)); + + if (ep) { + const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1; + if (pathId == 0) + ep->windingA += dir; + else + ep->windingB += dir; + } + + last = isect.vertex; + } + + QPathEdge *ep = edge(addEdge(last, second)); + + if (ep) { + const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1; + if (pathId == 0) + ep->windingA += dir; + else + ep->windingB += dir; + } + } +} + +QWingedEdge::QWingedEdge() : + m_edges(0), + m_vertices(0), + m_segments(0) +{ +} + +QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) : + m_edges(subject.elementCount()), + m_vertices(subject.elementCount()), + m_segments(subject.elementCount()) +{ + m_segments.setPath(subject); + m_segments.addPath(clip); + + intersectAndAdd(); +} + +QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const +{ + const QPathEdge *sp = edge(status.edge); + Q_ASSERT(sp); + + TraversalStatus result; + result.edge = sp->next(status.traversal, status.direction); + result.traversal = status.traversal; + result.direction = status.direction; + + const QPathEdge *rp = edge(result.edge); + Q_ASSERT(rp); + + if (sp->vertex(status.direction) == rp->vertex(status.direction)) + result.flip(); + + return result; +} + +static bool isLine(const QBezier &bezier) +{ + const bool equal_1_2 = comparePoints(bezier.pt1(), bezier.pt2()); + const bool equal_2_3 = comparePoints(bezier.pt2(), bezier.pt3()); + const bool equal_3_4 = comparePoints(bezier.pt3(), bezier.pt4()); + + // point? + if (equal_1_2 && equal_2_3 && equal_3_4) + return true; + + if (comparePoints(bezier.pt1(), bezier.pt4())) + return equal_1_2 || equal_3_4; + + return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4); +} + +void QPathSegments::setPath(const QPainterPath &path) +{ + m_points.reset(); + m_intersections.reset(); + m_segments.reset(); + + m_pathId = 0; + + addPath(path); +} + +void QPathSegments::addPath(const QPainterPath &path) +{ + int firstSegment = m_segments.size(); + + bool hasMoveTo = false; + int lastMoveTo = 0; + int last = 0; + for (int i = 0; i < path.elementCount(); ++i) { + int current = m_points.size(); + + QPointF currentPoint; + if (path.elementAt(i).type == QPainterPath::CurveToElement) + currentPoint = path.elementAt(i+2); + else + currentPoint = path.elementAt(i); + + if (i > 0 && comparePoints(m_points.at(lastMoveTo), currentPoint)) + current = lastMoveTo; + else + m_points << currentPoint; + + switch (path.elementAt(i).type) { + case QPainterPath::MoveToElement: + if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo))) + m_segments << Segment(m_pathId, last, lastMoveTo); + hasMoveTo = true; + last = lastMoveTo = current; + break; + case QPainterPath::LineToElement: + m_segments << Segment(m_pathId, last, current); + last = current; + break; + case QPainterPath::CurveToElement: + { + QBezier bezier = QBezier::fromPoints(m_points.at(last), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2)); + if (isLine(bezier)) { + m_segments << Segment(m_pathId, last, current); + } else { + QRectF bounds = bezier.bounds(); + + // threshold based on similar algorithm as in qtriangulatingstroker.cpp + int threshold = qMin<float>(64, qMax(bounds.width(), bounds.height()) * (2 * qreal(3.14) / 6)); + + if (threshold < 3) threshold = 3; + qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1); + + for (int t = 1; t < threshold - 1; ++t) { + currentPoint = bezier.pointAt(t * one_over_threshold_minus_1); + + int index = m_points.size(); + m_segments << Segment(m_pathId, last, index); + last = index; + + m_points << currentPoint; + } + + m_segments << Segment(m_pathId, last, current); + } + } + last = current; + i += 2; + break; + default: + Q_ASSERT(false); + break; + } + } + + if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo))) + m_segments << Segment(m_pathId, last, lastMoveTo); + + for (int i = firstSegment; i < m_segments.size(); ++i) { + const QLineF line = lineAt(i); + + qreal x1 = line.p1().x(); + qreal y1 = line.p1().y(); + qreal x2 = line.p2().x(); + qreal y2 = line.p2().y(); + + if (x2 < x1) + qSwap(x1, x2); + if (y2 < y1) + qSwap(y1, y2); + + m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1); + } + + ++m_pathId; +} + +qreal QWingedEdge::delta(int vertex, int a, int b) const +{ + const QPathEdge *ap = edge(a); + const QPathEdge *bp = edge(b); + + double a_angle = ap->angle; + double b_angle = bp->angle; + + if (vertex == ap->second) + a_angle = ap->invAngle; + + if (vertex == bp->second) + b_angle = bp->invAngle; + + double result = b_angle - a_angle; + + if (result >= 128.) + return result - 128.; + else if (result < 0) + return result + 128.; + else + return result; +} + +static inline QPointF midPoint(const QWingedEdge &list, int ei) +{ + const QPathEdge *ep = list.edge(ei); + Q_ASSERT(ep); + + const QPointF a = *list.vertex(ep->first); + const QPointF b = *list.vertex(ep->second); + return a + 0.5 * (b - a); +} + +QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const +{ + const QPathVertex *vp = vertex(vi); + + Q_ASSERT(vp); + Q_ASSERT(ei >= 0); + Q_ASSERT(vp->edge >= 0); + + int position = vp->edge; + qreal d = 128.; + + TraversalStatus status; + status.direction = edge(vp->edge)->directionTo(vi); + status.traversal = QPathEdge::RightTraversal; + status.edge = vp->edge; + +#ifdef QDEBUG_CLIPPER + const QPathEdge *ep = edge(ei); + qDebug() << "Finding insert status for edge" << ei << "at vertex" << QPointF(*vp) << ", angles: " << ep->angle << ep->invAngle; +#endif + + do { + status = next(status); + status.flip(); + + Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi); + qreal d2 = delta(vi, ei, status.edge); + +#ifdef QDEBUG_CLIPPER + const QPathEdge *op = edge(status.edge); + qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle; +#endif + + if (d2 < d) { + position = status.edge; + d = d2; + } + } while (status.edge != vp->edge); + + status.traversal = QPathEdge::LeftTraversal; + status.direction = QPathEdge::Forward; + status.edge = position; + + if (edge(status.edge)->vertex(status.direction) != vi) + status.flip(); + +#ifdef QDEBUG_CLIPPER + qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge; +#endif + + Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi); + + return status; +} + +void QWingedEdge::removeEdge(int ei) +{ + QPathEdge *ep = edge(ei); + + TraversalStatus status; + status.direction = QPathEdge::Forward; + status.traversal = QPathEdge::RightTraversal; + status.edge = ei; + + TraversalStatus forwardRight = next(status); + forwardRight.flipDirection(); + + status.traversal = QPathEdge::LeftTraversal; + TraversalStatus forwardLeft = next(status); + forwardLeft.flipDirection(); + + status.direction = QPathEdge::Backward; + TraversalStatus backwardLeft = next(status); + backwardLeft.flipDirection(); + + status.traversal = QPathEdge::RightTraversal; + TraversalStatus backwardRight = next(status); + backwardRight.flipDirection(); + + edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge); + edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge); + + edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge); + edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge); + + ep->setNext(QPathEdge::Forward, ei); + ep->setNext(QPathEdge::Backward, ei); + + QPathVertex *a = vertex(ep->first); + QPathVertex *b = vertex(ep->second); + + a->edge = backwardRight.edge; + b->edge = forwardRight.edge; +} + +static int commonEdge(const QWingedEdge &list, int a, int b) +{ + const QPathVertex *ap = list.vertex(a); + Q_ASSERT(ap); + + const QPathVertex *bp = list.vertex(b); + Q_ASSERT(bp); + + if (ap->edge < 0 || bp->edge < 0) + return -1; + + QWingedEdge::TraversalStatus status; + status.edge = ap->edge; + status.direction = list.edge(status.edge)->directionTo(a); + status.traversal = QPathEdge::RightTraversal; + + do { + const QPathEdge *ep = list.edge(status.edge); + + if ((ep->first == a && ep->second == b) + || (ep->first == b && ep->second == a)) + return status.edge; + + status = list.next(status); + status.flip(); + } while (status.edge != ap->edge); + + return -1; +} + +static double computeAngle(const QPointF &v) +{ +#if 1 + if (v.x() == 0) { + return v.y() <= 0 ? 0 : 64.; + } else if (v.y() == 0) { + return v.x() <= 0 ? 32. : 96.; + } + + double vx = v.x(); + double vy = v.y(); + normalize(vx, vy); + if (vy < 0) { + if (vx < 0) { // 0 - 32 + return -32. * vx; + } else { // 96 - 128 + return 128. - 32. * vx; + } + } else { // 32 - 96 + return 64. + 32. * vx; + } +#else + // doesn't seem to be robust enough + return qAtan2(v.x(), v.y()) + Q_PI; +#endif +} + +int QWingedEdge::addEdge(const QPointF &a, const QPointF &b) +{ + int fi = insert(a); + int si = insert(b); + + return addEdge(fi, si); +} + +int QWingedEdge::addEdge(int fi, int si) +{ + if (fi == si) + return -1; + + int common = commonEdge(*this, fi, si); + if (common >= 0) + return common; + + m_edges << QPathEdge(fi, si); + + int ei = m_edges.size() - 1; + + QPathVertex *fp = vertex(fi); + QPathVertex *sp = vertex(si); + + QPathEdge *ep = edge(ei); + + const QPointF tangent = QPointF(*sp) - QPointF(*fp); + ep->angle = computeAngle(tangent); + ep->invAngle = ep->angle + 64; + if (ep->invAngle >= 128) + ep->invAngle -= 128; + + QPathVertex *vertices[2] = { fp, sp }; + QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward }; + +#ifdef QDEBUG_CLIPPER + printf("** Adding edge %d / vertices: %.07f %.07f, %.07f %.07f\n", ei, fp->x, fp->y, sp->x, sp->y); +#endif + + for (int i = 0; i < 2; ++i) { + QPathVertex *vp = vertices[i]; + if (vp->edge < 0) { + vp->edge = ei; + ep->setNext(dirs[i], ei); + } else { + int vi = ep->vertex(dirs[i]); + Q_ASSERT(vertex(vi) == vertices[i]); + + TraversalStatus os = findInsertStatus(vi, ei); + QPathEdge *op = edge(os.edge); + + Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]); + + TraversalStatus ns = next(os); + ns.flipDirection(); + QPathEdge *np = edge(ns.edge); + + op->setNext(os.traversal, os.direction, ei); + np->setNext(ns.traversal, ns.direction, ei); + + int oe = os.edge; + int ne = ns.edge; + + os = next(os); + ns = next(ns); + + os.flipDirection(); + ns.flipDirection(); + + Q_ASSERT(os.edge == ei); + Q_ASSERT(ns.edge == ei); + + ep->setNext(os.traversal, os.direction, oe); + ep->setNext(ns.traversal, ns.direction, ne); + } + } + + Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Forward) >= 0); + Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Backward) >= 0); + Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Forward) >= 0); + Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0); + + return ei; +} + +int QWingedEdge::insert(const QPathVertex &vertex) +{ + if (!m_vertices.isEmpty()) { + const QPathVertex &last = m_vertices.last(); + if (vertex.x == last.x && vertex.y == last.y) + return m_vertices.size() - 1; + + for (int i = 0; i < m_vertices.size(); ++i) { + const QPathVertex &v = m_vertices.at(i); + if (qFuzzyCompare(v.x, vertex.x) && qFuzzyCompare(v.y, vertex.y)) { + return i; + } + } + } + + m_vertices << vertex; + return m_vertices.size() - 1; +} + +static void addLineTo(QPainterPath &path, const QPointF &point) +{ + const int elementCount = path.elementCount(); + if (elementCount >= 2) { + const QPainterPath::Element &middle = path.elementAt(elementCount - 1); + if (middle.type == QPainterPath::LineToElement) { + const QPointF first = path.elementAt(elementCount - 2); + const QPointF d1 = point - first; + const QPointF d2 = middle - first; + + const QPointF p(-d1.y(), d1.x()); + + if (qFuzzyIsNull(dot(p, d2))) { + path.setElementPositionAt(elementCount - 1, point.x(), point.y()); + return; + } + } + } + + path.lineTo(point); +} + +static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal) +{ + QWingedEdge::TraversalStatus status; + status.edge = edge; + status.traversal = traversal; + status.direction = QPathEdge::Forward; + + path.moveTo(*list.vertex(list.edge(edge)->first)); + + do { + const QPathEdge *ep = list.edge(status.edge); + + addLineTo(path, *list.vertex(ep->vertex(status.direction))); + + if (status.traversal == QPathEdge::LeftTraversal) + ep->flag &= ~16; + else + ep->flag &= ~32; + + status = list.next(status); + } while (status.edge != edge); +} + +void QWingedEdge::simplify() +{ + for (int i = 0; i < edgeCount(); ++i) { + const QPathEdge *ep = edge(i); + + // if both sides are part of the inside then we can collapse the edge + int flag = 0x3 << 4; + if ((ep->flag & flag) == flag) { + removeEdge(i); + + ep->flag &= ~flag; + } + } +} + +QPainterPath QWingedEdge::toPath() const +{ + QPainterPath path; + + for (int i = 0; i < edgeCount(); ++i) { + const QPathEdge *ep = edge(i); + + if (ep->flag & 16) { + add(path, *this, i, QPathEdge::LeftTraversal); + } + + if (ep->flag & 32) + add(path, *this, i, QPathEdge::RightTraversal); + } + + return path; +} + +bool QPathClipper::intersect() +{ + if (subjectPath == clipPath) + return true; + + QRectF r1 = subjectPath.controlPointRect(); + QRectF r2 = clipPath.controlPointRect(); + if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) || + qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) { + // no way we could intersect + return false; + } + + bool subjectIsRect = pathToRect(subjectPath); + bool clipIsRect = pathToRect(clipPath); + + if (subjectIsRect && clipIsRect) + return true; + else if (subjectIsRect) + return clipPath.intersects(r1); + else if (clipIsRect) + return subjectPath.intersects(r2); + + QPathSegments a(subjectPath.elementCount()); + a.setPath(subjectPath); + QPathSegments b(clipPath.elementCount()); + b.setPath(clipPath); + + QIntersectionFinder finder; + if (finder.hasIntersections(a, b)) + return true; + + for (int i = 0; i < clipPath.elementCount(); ++i) { + if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) { + const QPointF point = clipPath.elementAt(i); + if (r1.contains(point) && subjectPath.contains(point)) + return true; + } + } + + for (int i = 0; i < subjectPath.elementCount(); ++i) { + if (subjectPath.elementAt(i).type == QPainterPath::MoveToElement) { + const QPointF point = subjectPath.elementAt(i); + if (r2.contains(point) && clipPath.contains(point)) + return true; + } + } + + return false; +} + +bool QPathClipper::contains() +{ + if (subjectPath == clipPath) + return false; + + QRectF r1 = subjectPath.controlPointRect(); + QRectF r2 = clipPath.controlPointRect(); + if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) || + qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) { + // no intersection -> not contained + return false; + } + + bool clipIsRect = pathToRect(clipPath); + if (clipIsRect) + return subjectPath.contains(r2); + + QPathSegments a(subjectPath.elementCount()); + a.setPath(subjectPath); + QPathSegments b(clipPath.elementCount()); + b.setPath(clipPath); + + QIntersectionFinder finder; + if (finder.hasIntersections(a, b)) + return false; + + for (int i = 0; i < clipPath.elementCount(); ++i) { + if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) { + const QPointF point = clipPath.elementAt(i); + if (!r1.contains(point) || !subjectPath.contains(point)) + return false; + } + } + + return true; +} + +QPathClipper::QPathClipper(const QPainterPath &subject, + const QPainterPath &clip) + : subjectPath(subject) + , clipPath(clip) +{ + aMask = subjectPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1; + bMask = clipPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1; +} + +template <typename Iterator, typename Equality> +Iterator qRemoveDuplicates(Iterator begin, Iterator end, Equality eq) +{ + if (begin == end) + return end; + + Iterator last = begin; + ++begin; + Iterator insert = begin; + for (Iterator it = begin; it != end; ++it) { + if (!eq(*it, *last)) { + *insert++ = *it; + last = it; + } + } + + return insert; +} + +static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal) +{ + QWingedEdge::TraversalStatus status; + status.edge = edge; + status.traversal = traversal; + status.direction = QPathEdge::Forward; + + do { + if (status.traversal == QPathEdge::LeftTraversal) + list.edge(status.edge)->flag |= 1; + else + list.edge(status.edge)->flag |= 2; + + status = list.next(status); + } while (status.edge != edge); +} + +template <typename InputIterator> +InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val) +{ + while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val))) + ++first; + return first; +} + +static bool fuzzyCompare(qreal a, qreal b) +{ + return qFuzzyCompare(a, b); +} + +bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect) +{ + if (path.elementCount() != 5) + return false; + + const bool mightBeRect = path.elementAt(0).isMoveTo() + && path.elementAt(1).isLineTo() + && path.elementAt(2).isLineTo() + && path.elementAt(3).isLineTo() + && path.elementAt(4).isLineTo(); + + if (!mightBeRect) + return false; + + const qreal x1 = path.elementAt(0).x; + const qreal y1 = path.elementAt(0).y; + + const qreal x2 = path.elementAt(1).x; + const qreal y2 = path.elementAt(2).y; + + if (path.elementAt(1).y != y1) + return false; + + if (path.elementAt(2).x != x2) + return false; + + if (path.elementAt(3).x != x1 || path.elementAt(3).y != y2) + return false; + + if (path.elementAt(4).x != x1 || path.elementAt(4).y != y1) + return false; + + if (rect) + rect->setCoords(x1, y1, x2, y2); + + return true; +} + + +QPainterPath QPathClipper::clip(Operation operation) +{ + op = operation; + + if (op != Simplify) { + if (subjectPath == clipPath) + return op == BoolSub ? QPainterPath() : subjectPath; + + bool subjectIsRect = pathToRect(subjectPath, 0); + bool clipIsRect = pathToRect(clipPath, 0); + + const QRectF clipBounds = clipPath.boundingRect(); + const QRectF subjectBounds = subjectPath.boundingRect(); + + if (!clipBounds.intersects(subjectBounds)) { + switch (op) { + case BoolSub: + return subjectPath; + case BoolAnd: + return QPainterPath(); + case BoolOr: { + QPainterPath result = subjectPath; + if (result.fillRule() == clipPath.fillRule()) { + result.addPath(clipPath); + } else if (result.fillRule() == Qt::WindingFill) { + result = result.simplified(); + result.addPath(clipPath); + } else { + result.addPath(clipPath.simplified()); + } + return result; + } + default: + break; + } + } + + if (clipBounds.contains(subjectBounds)) { + if (clipIsRect) { + switch (op) { + case BoolSub: + return QPainterPath(); + case BoolAnd: + return subjectPath; + case BoolOr: + return clipPath; + default: + break; + } + } + } else if (subjectBounds.contains(clipBounds)) { + if (subjectIsRect) { + switch (op) { + case BoolSub: + if (clipPath.fillRule() == Qt::OddEvenFill) { + QPainterPath result = clipPath; + result.addRect(subjectBounds); + return result; + } else { + QPainterPath result = clipPath.simplified(); + result.addRect(subjectBounds); + return result; + } + break; + case BoolAnd: + return clipPath; + case BoolOr: + return subjectPath; + default: + break; + } + } + } + + if (op == BoolAnd) { + if (subjectIsRect) + return intersect(clipPath, subjectBounds); + else if (clipIsRect) + return intersect(subjectPath, clipBounds); + } + } + + QWingedEdge list(subjectPath, clipPath); + + doClip(list, ClipMode); + + QPainterPath path = list.toPath(); + return path; +} + +bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode) +{ + QVector<qreal> y_coords; + y_coords.reserve(list.vertexCount()); + for (int i = 0; i < list.vertexCount(); ++i) + y_coords << list.vertex(i)->y; + + qSort(y_coords.begin(), y_coords.end()); + y_coords.resize(qRemoveDuplicates(y_coords.begin(), y_coords.end(), fuzzyCompare) - y_coords.begin()); + +#ifdef QDEBUG_CLIPPER + printf("sorted y coords:\n"); + for (int i = 0; i < y_coords.size(); ++i) { + printf("%.9f\n", y_coords[i]); + } +#endif + + bool found; + do { + found = false; + int index = 0; + qreal maxHeight = 0; + for (int i = 0; i < list.edgeCount(); ++i) { + QPathEdge *edge = list.edge(i); + + // have both sides of this edge already been handled? + if ((edge->flag & 0x3) == 0x3) + continue; + + QPathVertex *a = list.vertex(edge->first); + QPathVertex *b = list.vertex(edge->second); + + if (qFuzzyCompare(a->y, b->y)) + continue; + + found = true; + + qreal height = qAbs(a->y - b->y); + if (height > maxHeight) { + index = i; + maxHeight = height; + } + } + + if (found) { + QPathEdge *edge = list.edge(index); + + QPathVertex *a = list.vertex(edge->first); + QPathVertex *b = list.vertex(edge->second); + + // FIXME: this can be optimized by using binary search + const int first = qFuzzyFind(y_coords.begin(), y_coords.end(), qMin(a->y, b->y)) - y_coords.begin(); + const int last = qFuzzyFind(y_coords.begin() + first, y_coords.end(), qMax(a->y, b->y)) - y_coords.begin(); + + Q_ASSERT(first < y_coords.size() - 1); + Q_ASSERT(last < y_coords.size()); + + qreal bestY = 0.5 * (y_coords[first] + y_coords[first+1]); + qreal biggestGap = y_coords[first+1] - y_coords[first]; + + for (int i = first + 1; i < last; ++i) { + qreal gap = y_coords[i+1] - y_coords[i]; + + if (gap > biggestGap) { + bestY = 0.5 * (y_coords[i] + y_coords[i+1]); + biggestGap = gap; + } + } + +#ifdef QDEBUG_CLIPPER + printf("y: %.9f, gap: %.9f\n", bestY, biggestGap); +#endif + + if (handleCrossingEdges(list, bestY, mode) && mode == CheckMode) + return true; + + edge->flag |= 0x3; + } + } while (found); + + if (mode == ClipMode) + list.simplify(); + + return false; +} + +static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal) +{ + QWingedEdge::TraversalStatus status; + status.edge = edge; + status.traversal = traversal; + status.direction = QPathEdge::Forward; + + do { + int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2; + + QPathEdge *ep = list.edge(status.edge); + + ep->flag |= (flag | (flag << 4)); + +#ifdef QDEBUG_CLIPPER + qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag; +#endif + + status = list.next(status); + } while (status.edge != edge); +} + +struct QCrossingEdge +{ + int edge; + qreal x; + + bool operator<(const QCrossingEdge &edge) const + { + return x < edge.x; + } +}; + +static bool bool_op(bool a, bool b, QPathClipper::Operation op) +{ + switch (op) { + case QPathClipper::BoolAnd: + return a && b; + case QPathClipper::BoolOr: // fall-through + case QPathClipper::Simplify: + return a || b; + case QPathClipper::BoolSub: + return a && !b; + default: + Q_ASSERT(false); + return false; + } +} + +bool QWingedEdge::isInside(qreal x, qreal y) const +{ + int winding = 0; + for (int i = 0; i < edgeCount(); ++i) { + const QPathEdge *ep = edge(i); + + // left xor right + int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1; + + if (!w) + continue; + + QPointF a = *vertex(ep->first); + QPointF b = *vertex(ep->second); + + if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { + qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); + + if (intersectionX > x) + winding += w; + } + } + + return winding & 1; +} + +static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y) +{ + QVector<QCrossingEdge> crossings; + for (int i = 0; i < list.edgeCount(); ++i) { + const QPathEdge *edge = list.edge(i); + QPointF a = *list.vertex(edge->first); + QPointF b = *list.vertex(edge->second); + + if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { + const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); + const QCrossingEdge edge = { i, intersection }; + crossings << edge; + } + } + return crossings; +} + +bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode) +{ + QVector<QCrossingEdge> crossings = findCrossings(list, y); + + Q_ASSERT(!crossings.isEmpty()); + qSort(crossings.begin(), crossings.end()); + + int windingA = 0; + int windingB = 0; + + int windingD = 0; + +#ifdef QDEBUG_CLIPPER + qDebug() << "crossings:" << crossings.size(); +#endif + for (int i = 0; i < crossings.size() - 1; ++i) { + int ei = crossings.at(i).edge; + const QPathEdge *edge = list.edge(ei); + + windingA += edge->windingA; + windingB += edge->windingB; + + const bool hasLeft = (edge->flag >> 4) & 1; + const bool hasRight = (edge->flag >> 4) & 2; + + windingD += hasLeft ^ hasRight; + + const bool inA = (windingA & aMask) != 0; + const bool inB = (windingB & bMask) != 0; + const bool inD = (windingD & 0x1) != 0; + + const bool inside = bool_op(inA, inB, op); + const bool add = inD ^ inside; + +#ifdef QDEBUG_CLIPPER + printf("y %f, x %f, inA: %d, inB: %d, inD: %d, inside: %d, flag: %x, bezier: %p, edge: %d\n", y, crossings.at(i).x, inA, inB, inD, inside, edge->flag, edge->bezier, ei); +#endif + + if (add) { + if (mode == CheckMode) + return true; + + qreal y0 = list.vertex(edge->first)->y; + qreal y1 = list.vertex(edge->second)->y; + + if (y0 < y1) { + if (!(edge->flag & 1)) + traverse(list, ei, QPathEdge::LeftTraversal); + + if (!(edge->flag & 2)) + clear(list, ei, QPathEdge::RightTraversal); + } else { + if (!(edge->flag & 1)) + clear(list, ei, QPathEdge::LeftTraversal); + + if (!(edge->flag & 2)) + traverse(list, ei, QPathEdge::RightTraversal); + } + + ++windingD; + } else { + if (!(edge->flag & 1)) + clear(list, ei, QPathEdge::LeftTraversal); + + if (!(edge->flag & 2)) + clear(list, ei, QPathEdge::RightTraversal); + } + } + + return false; +} + +namespace { + +QList<QPainterPath> toSubpaths(const QPainterPath &path) +{ + + QList<QPainterPath> subpaths; + if (path.isEmpty()) + return subpaths; + + QPainterPath current; + for (int i = 0; i < path.elementCount(); ++i) { + const QPainterPath::Element &e = path.elementAt(i); + switch (e.type) { + case QPainterPath::MoveToElement: + if (current.elementCount() > 1) + subpaths += current; + current = QPainterPath(); + current.moveTo(e); + break; + case QPainterPath::LineToElement: + current.lineTo(e); + break; + case QPainterPath::CurveToElement: { + current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2)); + i+=2; + break; + } + case QPainterPath::CurveToDataElement: + Q_ASSERT(!"toSubpaths(), bad element type"); + break; + } + } + + if (current.elementCount() > 1) + subpaths << current; + + return subpaths; +} + +enum Edge +{ + Left, Top, Right, Bottom +}; + +static bool isVertical(Edge edge) +{ + return edge == Left || edge == Right; +} + +template <Edge edge> +bool compare(const QPointF &p, qreal t) +{ + switch (edge) + { + case Left: + return p.x() < t; + case Right: + return p.x() > t; + case Top: + return p.y() < t; + default: + return p.y() > t; + } +} + +template <Edge edge> +QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t) +{ + QLineF line(a, b); + switch (edge) { + case Left: // fall-through + case Right: + return line.pointAt((t - a.x()) / (b.x() - a.x())); + default: + return line.pointAt((t - a.y()) / (b.y() - a.y())); + } +} + +void addLine(QPainterPath &path, const QLineF &line) +{ + if (path.elementCount() > 0) + path.lineTo(line.p1()); + else + path.moveTo(line.p1()); + + path.lineTo(line.p2()); +} + +template <Edge edge> +void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result) +{ + bool outA = compare<edge>(a, t); + bool outB = compare<edge>(b, t); + if (outA && outB) + return; + + if (outA) + addLine(result, QLineF(intersectLine<edge>(a, b, t), b)); + else if(outB) + addLine(result, QLineF(a, intersectLine<edge>(a, b, t))); + else + addLine(result, QLineF(a, b)); +} + +void addBezier(QPainterPath &path, const QBezier &bezier) +{ + if (path.elementCount() > 0) + path.lineTo(bezier.pt1()); + else + path.moveTo(bezier.pt1()); + + path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4()); +} + +template <Edge edge> +void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result) +{ + QBezier bezier = QBezier::fromPoints(a, b, c, d); + + bool outA = compare<edge>(a, t); + bool outB = compare<edge>(b, t); + bool outC = compare<edge>(c, t); + bool outD = compare<edge>(d, t); + + int outCount = int(outA) + int(outB) + int(outC) + int(outD); + + if (outCount == 4) + return; + + if (outCount == 0) { + addBezier(result, bezier); + return; + } + + QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform(); + QBezier unflipped = bezier; + QBezier flipped = bezier.mapBy(flip); + + qreal t0 = 0, t1 = 1; + int stationary = flipped.stationaryYPoints(t0, t1); + + qreal segments[4]; + QPointF points[4]; + points[0] = unflipped.pt1(); + segments[0] = 0; + + int segmentCount = 0; + if (stationary > 0) { + ++segmentCount; + segments[segmentCount] = t0; + points[segmentCount] = unflipped.pointAt(t0); + } + if (stationary > 1) { + ++segmentCount; + segments[segmentCount] = t1; + points[segmentCount] = unflipped.pointAt(t1); + } + ++segmentCount; + segments[segmentCount] = 1; + points[segmentCount] = unflipped.pt4(); + + qreal lastIntersection = 0; + for (int i = 0; i < segmentCount; ++i) { + outA = compare<edge>(points[i], t); + outB = compare<edge>(points[i+1], t); + + if (outA != outB) { + qreal intersection = flipped.tForY(segments[i], segments[i+1], t); + + if (outB) + addBezier(result, unflipped.getSubRange(lastIntersection, intersection)); + + lastIntersection = intersection; + } + } + + if (!outB) + addBezier(result, unflipped.getSubRange(lastIntersection, 1)); +} + +// clips a single subpath against a single edge +template <Edge edge> +QPainterPath clip(const QPainterPath &path, qreal t) +{ + QPainterPath result; + for (int i = 1; i < path.elementCount(); ++i) { + const QPainterPath::Element &element = path.elementAt(i); + Q_ASSERT(!element.isMoveTo()); + if (element.isLineTo()) { + clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result); + } else { + clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result); + i += 2; + } + } + + int last = path.elementCount() - 1; + if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0))) + clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result); + + return result; +} + +QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect) +{ + QList<QPainterPath> subpaths = toSubpaths(path); + + QPainterPath result; + result.setFillRule(path.fillRule()); + for (int i = 0; i < subpaths.size(); ++i) { + QPainterPath subPath = subpaths.at(i); + QRectF bounds = subPath.boundingRect(); + if (bounds.intersects(rect)) { + if (bounds.left() < rect.left()) + subPath = clip<Left>(subPath, rect.left()); + if (bounds.right() > rect.right()) + subPath = clip<Right>(subPath, rect.right()); + + bounds = subPath.boundingRect(); + + if (bounds.top() < rect.top()) + subPath = clip<Top>(subPath, rect.top()); + if (bounds.bottom() > rect.bottom()) + subPath = clip<Bottom>(subPath, rect.bottom()); + + if (subPath.elementCount() > 1) + result.addPath(subPath); + } + } + return result; +} + +} + +QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect) +{ + return intersectPath(path, rect); +} + +QT_END_NAMESPACE |