diff options
Diffstat (limited to 'src/gui/painting/qpathclipper.cpp')
| -rw-r--r-- | src/gui/painting/qpathclipper.cpp | 2042 |
1 files changed, 2042 insertions, 0 deletions
diff --git a/src/gui/painting/qpathclipper.cpp b/src/gui/painting/qpathclipper.cpp new file mode 100644 index 0000000..297cdd3 --- /dev/null +++ b/src/gui/painting/qpathclipper.cpp @@ -0,0 +1,2042 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (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 either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** 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.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qpathclipper_p.h" + +#include <private/qbezier_p.h> +#include <private/qdatabuffer_p.h> +#include <qmath.h> + +#include <QImage> +#include <QPainter> + +/** + 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 + +//#define QDEBUG_CLIPPER +static qreal dot(const QPointF &a, const QPointF &b) +{ + return a.x() * b.x() + a.y() * b.y(); +} + +static QPointF normalize(const QPointF &p) +{ + return p / qSqrt(p.x() * p.x() + p.y() * p.y()); +} + +static bool pathToRect(const QPainterPath &path, QRectF *rect = 0); + +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: + void intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections); + void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections); + + bool beziersIntersect(const QBezier &one, const QBezier &two) const; + bool linesIntersect(const QLineF &a, const QLineF &b) const; +}; + +bool QIntersectionFinder::beziersIntersect(const QBezier &one, const QBezier &two) const +{ + return (one.pt1() == two.pt1() && one.pt2() == two.pt2() && one.pt3() == two.pt3() && one.pt4() == two.pt4()) + || (one.pt1() == two.pt4() && one.pt2() == two.pt3() && one.pt3() == two.pt2() && one.pt4() == two.pt1()) + || QBezier::findIntersections(one, two, 0); +} + +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 (p1 == p2 || q1 == q2) + return false; + + const bool p1_equals_q1 = (p1 == q1); + const bool p2_equals_q2 = (p2 == q2); + + if (p1_equals_q1 && p2_equals_q2) + return true; + + const bool p1_equals_q2 = (p1 == q2); + const bool p2_equals_q1 = (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 (qFuzzyCompare(par + 1, 1)) { + const QPointF normal(-pDelta.y(), pDelta.x()); + + // coinciding? + if (qFuzzyCompare(dot(normal, q1 - p1) + 1, 1)) { + 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; + } + + // 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 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; +} + +void QIntersectionFinder::intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections) +{ + if ((one.pt1() == two.pt1() && one.pt2() == two.pt2() && one.pt3() == two.pt3() && one.pt4() == two.pt4()) + || (one.pt1() == two.pt4() && one.pt2() == two.pt3() && one.pt3() == two.pt2() && one.pt4() == two.pt1())) { + + return; + } + + t.clear(); + + if (!QBezier::findIntersections(one, two, &t)) + return; + + int count = t.size(); + + for (int i = 0; i < count; ++i) { + qreal alpha_p = t.at(i).first; + qreal alpha_q = t.at(i).second; + + QPointF pt; + if (qFuzzyCompare(alpha_p + 1, 1)) { + pt = one.pt1(); + } else if (qFuzzyCompare(alpha_p, 1)) { + pt = one.pt4(); + } else if (qFuzzyCompare(alpha_q + 1, 1)) { + pt = two.pt1(); + } else if (qFuzzyCompare(alpha_q, 1)) { + pt = two.pt4(); + } else { + pt = one.pointAt(alpha_p); + } + + QIntersection intersection; + intersection.alphaA = alpha_p; + intersection.alphaB = alpha_q; + intersection.pos = pt; + intersections.add(intersection); + } +} + +void QIntersectionFinder::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 (p1 == p2 || q1 == q2) + return; + + const bool p1_equals_q1 = (p1 == q1); + const bool p2_equals_q2 = (p2 == q2); + + if (p1_equals_q1 && p2_equals_q2) + return; + + const bool p1_equals_q2 = (p1 == q2); + const bool p2_equals_q1 = (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 (qFuzzyCompare(par + 1, 1)) { + const QPointF normal(-pDelta.y(), pDelta.x()); + + // coinciding? + if (qFuzzyCompare(dot(normal, q1 - p1) + 1, 1)) { + 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 = qFuzzyCompare(tp + 1, 1); + const bool p_one = qFuzzyCompare(tp, 1); + + const bool q_zero = qFuzzyCompare(tq + 1, 1); + const bool q_one = qFuzzyCompare(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); +} + +static const QBezier bezierFromLine(const QLineF &line) +{ + const QPointF p1 = line.p1(); + const QPointF p2 = line.p2(); + const QPointF delta = (p2 - p1) / 3; + return QBezier::fromPoints(p1, p1 + delta, p1 + 2 * delta, p2); +} + +bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const +{ + QBezier tempA; + QBezier tempB; + + 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 QBezier *bezierA = a.bezierAt(i); + bool isBezierA = bezierA != 0; + + 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; + + bool isBezierB = b.bezierAt(j) != 0; + + if (isBezierA || isBezierB) { + const QBezier *bezierB; + if (isBezierB) { + bezierB = b.bezierAt(j); + } else { + tempB = bezierFromLine(b.lineAt(j)); + bezierB = &tempB; + } + + if (!bezierA) { + tempA = bezierFromLine(a.lineAt(i)); + bezierA = &tempA; + } + + if (beziersIntersect(*bezierA, *bezierB)) + return true; + } else { + if (linesIntersect(a.lineAt(i), b.lineAt(j))) + return true; + } + } + } + + return false; +} + +void QIntersectionFinder::produceIntersections(QPathSegments &segments) +{ + QBezier tempA; + QBezier tempB; + + QVector<QPair<qreal, qreal> > t; + QDataBuffer<QIntersection> intersections; + + for (int i = 0; i < segments.segments(); ++i) { + const QBezier *bezierA = segments.bezierAt(i); + bool isBezierA = bezierA != 0; + + const QRectF &r1 = segments.elementBounds(i); + + for (int j = 0; j < i; ++j) { + const QRectF &r2 = segments.elementBounds(j); + + if (r1.left() > r2.right() || r2.left() > r1.right()) + continue; + if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) + continue; + + intersections.reset(); + + bool isBezierB = segments.bezierAt(j) != 0; + + if (isBezierA || isBezierB) { + const QBezier *bezierB; + if (isBezierB) { + bezierB = segments.bezierAt(j); + } else { + tempB = bezierFromLine(segments.lineAt(j)); + bezierB = &tempB; + } + + if (!bezierA) { + tempA = bezierFromLine(segments.lineAt(i)); + bezierA = &tempA; + } + + intersectBeziers(*bezierA, *bezierB, t, intersections); + } else { + const QLineF lineA = segments.lineAt(i); + const QLineF lineB = segments.lineAt(j); + + intersectLines(lineA, lineB, intersections); + } + + for (int k = 0; k < intersections.size(); ++k) { + QPathSegments::Intersection i_isect, j_isect; + i_isect.vertex = j_isect.vertex = segments.addPoint(intersections.at(k).pos); + + i_isect.t = intersections.at(k).alphaA; + j_isect.t = intersections.at(k).alphaB; + + i_isect.next = 0; + j_isect.next = 0; + + segments.addIntersection(i, i_isect); + segments.addIntersection(j, j_isect); + } + } + } +} + +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 (qFuzzyCompare(pivot, value)) { + const qreal pivot2 = pivotComponents[(depth + 1) & 1]; + const qreal value2 = pointComponents[(depth + 1) & 1]; + + if (qFuzzyCompare(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; + 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()); + + const QBezier *bezier = m_segments.bezierAt(i); + if (bezier) { + int first = m_segments.segmentAt(i).va; + int second = m_segments.segmentAt(i).vb; + + qreal alpha = 0.0; + int last = first; + for (int j = 0; j < intersections.size(); ++j) { + const QPathSegments::Intersection &isect = intersections.at(j); + + addBezierEdge(bezier, last, isect.vertex, alpha, isect.t, pathId); + + alpha = isect.t; + last = isect.vertex; + } + + addBezierEdge(bezier, last, second, alpha, 1.0, pathId); + } else { + 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() +{ +} + +QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) +{ + 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 = bezier.pt1() == bezier.pt2(); + const bool equal_2_3 = bezier.pt2() == bezier.pt3(); + const bool equal_3_4 = bezier.pt3() == bezier.pt4(); + + // point? + if (equal_1_2 && equal_2_3 && equal_3_4) + return true; + + if (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_beziers.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 && m_points.at(lastMoveTo) == currentPoint) + current = lastMoveTo; + else + m_points << currentPoint; + + switch (path.elementAt(i).type) { + case QPainterPath::MoveToElement: + if (hasMoveTo && last != lastMoveTo && 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 { + m_segments << Segment(m_pathId, last, current, m_beziers.size()); + m_beziers << bezier; + } + } + last = current; + i += 2; + break; + default: + Q_ASSERT(false); + break; + } + } + + if (hasMoveTo && last != lastMoveTo && 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 QBezier *bezier = bezierAt(i); + if (bezier) { + m_segments.at(i).bounds = bezier->bounds(); + } else { + 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); + + qreal a_angle = ap->angle; + qreal b_angle = bp->angle; + + if (vertex == ap->second) + a_angle = ap->invAngle; + + if (vertex == bp->second) + b_angle = bp->invAngle; + + qreal result = b_angle - a_angle; + + if (qFuzzyCompare(result + 1, 1) || qFuzzyCompare(result, 128)) + return 0; + + if (result < 0) + return result + 128.; + else + return result; +} + +static inline QPointF tangentAt(const QWingedEdge &list, int vi, int ei) +{ + const QPathEdge *ep = list.edge(ei); + Q_ASSERT(ep); + + qreal t; + qreal sign; + + if (ep->first == vi) { + t = ep->t0; + sign = 1; + } else { + t = ep->t1; + sign = -1; + } + + QPointF normal; + if (ep->bezier) { + normal = ep->bezier->derivedAt(t); + + if (qFuzzyCompare(normal.x() + 1, 1) && qFuzzyCompare(normal.y() + 1, 1)) + normal = ep->bezier->secondDerivedAt(t); + } else { + const QPointF a = *list.vertex(ep->first); + const QPointF b = *list.vertex(ep->second); + normal = b - a; + } + + return normalize(sign * normal); +} + +static inline QPointF midPoint(const QWingedEdge &list, int ei) +{ + const QPathEdge *ep = list.edge(ei); + Q_ASSERT(ep); + + if (ep->bezier) { + return ep->bezier->pointAt(0.5 * (ep->t0 + ep->t1)); + } else { + const QPointF a = *list.vertex(ep->first); + const QPointF b = *list.vertex(ep->second); + return a + 0.5 * (b - a); + } +} + +static QBezier transform(const QBezier &bezier, const QPointF &xAxis, const QPointF &yAxis, const QPointF &origin) +{ + QPointF points[4] = { + bezier.pt1(), + bezier.pt2(), + bezier.pt3(), + bezier.pt4() + }; + + for (int i = 0; i < 4; ++i) { + const QPointF p = points[i] - origin; + + points[i].rx() = dot(xAxis, p); + points[i].ry() = dot(yAxis, p); + } + + return QBezier::fromPoints(points[0], points[1], points[2], points[3]); +} + +static bool isLeftOf(const QWingedEdge &list, int vi, int ai, int bi) +{ + const QPathEdge *ap = list.edge(ai); + const QPathEdge *bp = list.edge(bi); + + Q_ASSERT(ap); + Q_ASSERT(bp); + + if (!(ap->bezier || bp->bezier)) + return false; + + const QPointF tangent = tangentAt(list, vi, ai); + const QPointF normal(tangent.y(), -tangent.x()); + + const QPointF origin = *list.vertex(vi); + + const QPointF dpA = midPoint(list, ai) - origin; + const QPointF dpB = midPoint(list, bi) - origin; + + qreal xA = dot(normal, dpA); + qreal xB = dot(normal, dpB); + + if (xA <= 0 && xB >= 0) + return true; + + if (xA >= 0 && xB <= 0) + return false; + + if (!ap->bezier) + return xB > 0; + + if (!bp->bezier) + return xA < 0; + + // both are beziers on the same side of the tangent + + // transform the beziers into the local coordinate system + // such that positive y is along the tangent, and positive x is along the normal + + QBezier bezierA = transform(*ap->bezier, normal, tangent, origin); + QBezier bezierB = transform(*bp->bezier, normal, tangent, origin); + + qreal y = qMin(bezierA.pointAt(0.5 * (ap->t0 + ap->t1)).y(), + bezierB.pointAt(0.5 * (bp->t0 + bp->t1)).y()); + + xA = bezierA.pointAt(bezierA.tForY(ap->t0, ap->t1, y)).x(); + xB = bezierB.pointAt(bezierB.tForY(bp->t0, bp->t1, y)).x(); + + return xA < xB; +} + +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 (!(qFuzzyCompare(d2 + 1, 1) && isLeftOf(*this, vi, status.edge, ei)) + && (d2 < d || (qFuzzyCompare(d2, d) && isLeftOf(*this, vi, status.edge, position)))) { + 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 qreal 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.; + } + + QPointF nv = normalize(v); + if (nv.y() < 0) { + if (nv.x() < 0) { // 0 - 32 + return -32. * nv.x(); + } else { // 96 - 128 + return 128. - 32. * nv.x(); + } + } else { // 32 - 96 + return 64. + 32 * nv.x(); + } +#else + // doesn't seem to be robust enough + return atan2(v.x(), v.y()) + Q_PI; +#endif +} + +int QWingedEdge::addEdge(const QPointF &a, const QPointF &b, const QBezier *bezier, qreal t0, qreal t1) +{ + int fi = insert(a); + int si = insert(b); + + return addEdge(fi, si, bezier, t0, t1); +} + +int QWingedEdge::addEdge(int fi, int si, const QBezier *bezier, qreal t0, qreal t1) +{ + 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); + + ep->bezier = bezier; + ep->t0 = t0; + ep->t1 = t1; + + if (bezier) { + QPointF aTangent = bezier->derivedAt(t0); + QPointF bTangent = -bezier->derivedAt(t1); + + if (qFuzzyCompare(aTangent.x() + 1, 1) && qFuzzyCompare(aTangent.y() + 1, 1)) + aTangent = bezier->secondDerivedAt(t0); + + if (qFuzzyCompare(bTangent.x() + 1, 1) && qFuzzyCompare(bTangent.y() + 1, 1)) + bTangent = bezier->secondDerivedAt(t1); + + ep->angle = computeAngle(aTangent); + ep->invAngle = computeAngle(bTangent); + } else { + 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; +} + +void QWingedEdge::addBezierEdge(const QBezier *bezier, int vertexA, int vertexB, qreal alphaA, qreal alphaB, int path) +{ + if (qFuzzyCompare(alphaA, alphaB)) + return; + + qreal alphaMid = (alphaA + alphaB) * 0.5; + + qreal s0 = 0; + qreal s1 = 1; + int count = bezier->stationaryYPoints(s0, s1); + + m_splitPoints.clear(); + m_splitPoints << alphaA; + m_splitPoints << alphaMid; + m_splitPoints << alphaB; + + if (count > 0 && !qFuzzyCompare(s0, alphaA) && !qFuzzyCompare(s0, alphaMid) && !qFuzzyCompare(s0, alphaB) && s0 > alphaA && s0 < alphaB) + m_splitPoints << s0; + + if (count > 1 && !qFuzzyCompare(s1, alphaA) && !qFuzzyCompare(s1, alphaMid) && !qFuzzyCompare(s1, alphaB) && s1 > alphaA && s1 < alphaB) + m_splitPoints << s1; + + if (count > 0) + qSort(m_splitPoints.begin(), m_splitPoints.end()); + + int last = vertexA; + for (int i = 0; i < m_splitPoints.size() - 1; ++i) { + const qreal t0 = m_splitPoints[i]; + const qreal t1 = m_splitPoints[i+1]; + + int current; + if ((i + 1) == (m_splitPoints.size() - 1)) { + current = vertexB; + } else { + current = insert(bezier->pointAt(t1)); + } + + QPathEdge *ep = edge(addEdge(last, current, bezier, t0, t1)); + + if (ep) { + const int dir = m_vertices.at(last).y < m_vertices.at(current).y ? 1 : -1; + if (path == 0) + ep->windingA += dir; + else + ep->windingB += dir; + } + + last = current; + } +} + +void QWingedEdge::addBezierEdge(const QBezier *bezier, const QPointF &a, const QPointF &b, qreal alphaA, qreal alphaB, int path) +{ + if (qFuzzyCompare(alphaA, alphaB)) + return; + + if (a == b) { + int v = insert(a); + + addBezierEdge(bezier, v, v, alphaA, alphaB, path); + } else { + int va = insert(a); + int vb = insert(b); + + addBezierEdge(bezier, va, vb, alphaA, alphaB, path); + } +} + +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 (qFuzzyCompare(dot(p, d2) + 1, 1)) { + 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; + + const QBezier *bezier = 0; + qreal t0 = 1; + qreal t1 = 0; + bool forward = true; + + path.moveTo(*list.vertex(list.edge(edge)->first)); + + do { + const QPathEdge *ep = list.edge(status.edge); + + if (ep->bezier != bezier || (bezier && t0 != ep->t1 && t1 != ep->t0)) { + if (bezier) { + QBezier sub = bezier->bezierOnInterval(t0, t1); + + if (forward) + path.cubicTo(sub.pt2(), sub.pt3(), sub.pt4()); + else + path.cubicTo(sub.pt3(), sub.pt2(), sub.pt1()); + } + + bezier = ep->bezier; + t0 = 1; + t1 = 0; + forward = status.direction == QPathEdge::Forward; + } + + if (ep->bezier) { + t0 = qMin(t0, ep->t0); + t1 = qMax(t1, ep->t1); + } else + 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); + + if (bezier) { + QBezier sub = bezier->bezierOnInterval(t0, t1); + if (forward) + path.cubicTo(sub.pt2(), sub.pt3(), sub.pt4()); + else + path.cubicTo(sub.pt3(), sub.pt2(), sub.pt1()); + } +} + +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; + a.setPath(subjectPath); + QPathSegments b; + 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; + a.setPath(subjectPath); + QPathSegments b; + 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 && !qFuzzyCompare(qreal(*first), qreal(val))) + ++first; + return first; +} + +static bool fuzzyCompare(qreal a, qreal b) +{ + return qFuzzyCompare(a, b); +} + +static bool 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 = QRectF(QPointF(x1, y1), QPointF(x2, y2)); + + return true; +} + + +QPainterPath QPathClipper::clip(Operation operation) +{ + op = operation; + + if (op != Simplify) { + if (subjectPath == clipPath) + return op == BoolSub ? QPainterPath() : subjectPath; + + 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)) { + QRectF clipRect; + if (pathToRect(clipPath, &clipRect) && clipRect.contains(subjectBounds)) { + switch (op) { + case BoolSub: + return QPainterPath(); + case BoolAnd: + return subjectPath; + case BoolOr: + return clipPath; + default: + break; + } + } + } else if (subjectBounds.contains(clipBounds)) { + QRectF subjectRect; + if (pathToRect(subjectPath, &subjectRect) && subjectRect.contains(clipBounds)) { + switch (op) { + case BoolSub: + if (clipPath.fillRule() == Qt::OddEvenFill) { + QPainterPath result = clipPath; + result.addRect(subjectRect); + return result; + } else { + QPainterPath result = clipPath.simplified(); + result.addRect(subjectRect); + return result; + } + break; + case BoolAnd: + return clipPath; + case BoolOr: + return subjectPath; + default: + break; + } + } + } + } + + 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)) { + if (ep->bezier) { + qreal maxX = qMax(a.x(), qMax(b.x(), qMax(ep->bezier->x2, ep->bezier->x3))); + qreal minX = qMin(a.x(), qMin(b.x(), qMin(ep->bezier->x2, ep->bezier->x3))); + + if (minX > x) { + winding += w; + } else if (maxX > x) { + const qreal t = ep->bezier->tForY(ep->t0, ep->t1, y); + const qreal intersection = ep->bezier->pointAt(t).x(); + + if (intersection > x) + winding += w; + } + } else { + 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)) { + if (edge->bezier) { + const qreal t = edge->bezier->tForY(edge->t0, edge->t1, y); + const qreal intersection = edge->bezier->pointAt(t).x(); + + const QCrossingEdge edge = { i, intersection }; + crossings << edge; + } else { + 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; +} + +QT_END_NAMESPACE |