--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/gui/painting/qpathclipper.cpp Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,2057 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 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 <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 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 (comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2())
+ && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4()))
+ || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3())
+ && comparePoints(one.pt3(), two.pt2()) && comparePoints(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 (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;
+ }
+
+ // 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 ((comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2())
+ && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4()))
+ || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3())
+ && comparePoints(one.pt3(), two.pt2()) && comparePoints(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 (qFuzzyIsNull(alpha_p)) {
+ pt = one.pt1();
+ } else if (qFuzzyIsNull(alpha_p - 1)) {
+ pt = one.pt4();
+ } else if (qFuzzyIsNull(alpha_q)) {
+ pt = two.pt1();
+ } else if (qFuzzyIsNull(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 (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);
+}
+
+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 (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;
+ 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 = 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_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 && 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 {
+ 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 && !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 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 (qFuzzyIsNull(result) || 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 (qFuzzyIsNull(normal.x()) && qFuzzyIsNull(normal.y()))
+ 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 (!(qFuzzyIsNull(d2) && 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 (qFuzzyIsNull(aTangent.x()) && qFuzzyIsNull(aTangent.y()))
+ aTangent = bezier->secondDerivedAt(t0);
+
+ if (qFuzzyIsNull(bTangent.x()) && qFuzzyIsNull(bTangent.y()))
+ 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 (comparePoints(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 (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;
+
+ 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