Changeset 846 for trunk/src/gui/painting/qpathclipper.cpp

Timestamp:

May 5, 2011, 5:36:53 AM (14 years ago)

Author:

Dmitry A. Kuminov

Message:

trunk: Merged in qt 4.7.2 sources from branches/vendor/nokia/qt.

Location:

trunk

Files:

• . (modified) (1 prop)
• src/gui/painting/qpathclipper.cpp (modified) (35 diffs)

trunk/src/gui/painting/qpathclipper.cpp

@@ -1 +1 @@
 /****************************************************************************
 **
-** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 ** All rights reserved.
 ** Contact: Nokia Corporation (qt-info@nokia.com)
@@ -44 +44 @@
 #include <private/qbezier_p.h>
 #include <private/qdatabuffer_p.h>
+#include <private/qnumeric_p.h>
 #include <qmath.h>
 
@@ -86 +87 @@
 }
 
-static QPointF normalize(const QPointF &p)
-{
-    return p / qSqrt(p.x() * p.x() + p.y() * p.y());
+static void normalize(double &x, double &y)
+{
+    double reciprocal = 1 / qSqrt(x * x + y * y);
+    x *= reciprocal;
+    y *= reciprocal;
 }
 
@@ -106 +109 @@
 
 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
@@ -175 +165 @@
     }
 
-    // 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;
 
@@ -194 +179 @@
 }
 
-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();
+bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const
+{
+    if (a.segments() == 0 || b.segments() == 0)
+        return false;
+
+    const QRectF &rb0 = b.elementBounds(0);
+
+    qreal minX = rb0.left();
+    qreal minY = rb0.top();
+    qreal maxX = rb0.right();
+    qreal maxY = rb0.bottom();
+
+    for (int i = 1; i < b.segments(); ++i) {
+        const QRectF &r = b.elementBounds(i);
+        minX = qMin(minX, r.left());
+        minY = qMin(minY, r.top());
+        maxX = qMax(maxX, r.right());
+        maxY = qMax(maxY, r.bottom());
+    }
+
+    QRectF rb(minX, minY, maxX - minX, maxY - minY);
+
+    for (int i = 0; i < a.segments(); ++i) {
+        const QRectF &r1 = a.elementBounds(i);
+
+        if (r1.left() > rb.right() || rb.left() > r1.right())
+            continue;
+        if (r1.top() > rb.bottom() || rb.top() > r1.bottom())
+            continue;
+
+        for (int j = 0; j < b.segments(); ++j) {
+            const QRectF &r2 = b.elementBounds(j);
+
+            if (r1.left() > r2.right() || r2.left() > r1.right())
+                continue;
+            if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
+                continue;
+
+            if (linesIntersect(a.lineAt(i), b.lineAt(j)))
+                return true;
+        }
+    }
+
+    return false;
+}
+
+namespace {
+struct TreeNode
+{
+    qreal splitLeft;
+    qreal splitRight;
+    bool leaf;
+
+    int lowestLeftIndex;
+    int lowestRightIndex;
+
+    union {
+        struct {
+            int first;
+            int last;
+        } interval;
+        struct {
+            int left;
+            int right;
+        } children;
+    } index;
+};
+
+struct RectF
+{
+    qreal x1;
+    qreal y1;
+    qreal x2;
+    qreal y2;
+};
+
+class SegmentTree
+{
+public:
+    SegmentTree(QPathSegments &segments);
+
+    QRectF boundingRect() const;
+
+    void produceIntersections(int segment);
+
+private:
+    TreeNode buildTree(int first, int last, int depth, const RectF &bounds);
+
+    void produceIntersectionsLeaf(const TreeNode &node, int segment);
+    void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis);
+    void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections);
+
+    QPathSegments &m_segments;
+    QVector<int> m_index;
+
+    RectF m_bounds;
+
+    QVector<TreeNode> m_tree;
+    QDataBuffer<QIntersection> m_intersections;
+};
+
+SegmentTree::SegmentTree(QPathSegments &segments)
+    : m_segments(segments),
+      m_intersections(0)
+{
+    m_bounds.x1 = qt_inf();
+    m_bounds.y1 = qt_inf();
+    m_bounds.x2 = -qt_inf();
+    m_bounds.y2 = -qt_inf();
+
+    m_index.resize(m_segments.segments());
+
+    for (int i = 0; i < m_index.size(); ++i) {
+        m_index[i] = i;
+
+        const QRectF &segmentBounds = m_segments.elementBounds(i);
+
+        if (segmentBounds.left() < m_bounds.x1)
+            m_bounds.x1 = segmentBounds.left();
+        if (segmentBounds.top() < m_bounds.y1)
+            m_bounds.y1 = segmentBounds.top();
+        if (segmentBounds.right() > m_bounds.x2)
+            m_bounds.x2 = segmentBounds.right();
+        if (segmentBounds.bottom() > m_bounds.y2)
+            m_bounds.y2 = segmentBounds.bottom();
+    }
+
+    m_tree.resize(1);
+
+    TreeNode root = buildTree(0, m_index.size(), 0, m_bounds);
+    m_tree[0] = root;
+}
+
+QRectF SegmentTree::boundingRect() const
+{
+    return QRectF(QPointF(m_bounds.x1, m_bounds.y1),
+                  QPointF(m_bounds.x2, m_bounds.y2));
+}
+
+static inline qreal coordinate(const QPointF &pos, int axis)
+{
+    return axis == 0 ? pos.x() : pos.y();
+}
+
+TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds)
+{
+    if (depth >= 24 || (last - first) <= 10) {
+        TreeNode node;
+        node.leaf = true;
+        node.index.interval.first = first;
+        node.index.interval.last = last;
+
+        return node;
+    }
+
+    int splitAxis = (depth & 1);
+
+    TreeNode node;
+    node.leaf = false;
+
+    qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]);
+
+    node.splitLeft = (&bounds.x1)[splitAxis];
+    node.splitRight = (&bounds.x2)[splitAxis];
+
+    node.lowestLeftIndex = INT_MAX;
+    node.lowestRightIndex = INT_MAX;
+
+    const int treeSize = m_tree.size();
+
+    node.index.children.left = treeSize;
+    node.index.children.right = treeSize + 1;
+
+    m_tree.resize(treeSize + 2);
+
+    int l = first;
+    int r = last - 1;
+
+    // partition into left and right sets
+    while (l <= r) {
+        const int index = m_index.at(l);
+        const QRectF &segmentBounds = m_segments.elementBounds(index);
+
+        qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis);
+
+        if (coordinate(segmentBounds.center(), splitAxis) < split) {
+            qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis);
+            if (highCoordinate > node.splitLeft)
+                node.splitLeft = highCoordinate;
+            if (index < node.lowestLeftIndex)
+                node.lowestLeftIndex = index;
+            ++l;
         } else {
-            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)
+            if (lowCoordinate < node.splitRight)
+                node.splitRight = lowCoordinate;
+            if (index < node.lowestRightIndex)
+                node.lowestRightIndex = index;
+            qSwap(m_index[l], m_index[r]);
+            --r;
+        }
+    }
+
+    RectF lbounds = bounds;
+    (&lbounds.x2)[splitAxis] = node.splitLeft;
+
+    RectF rbounds = bounds;
+    (&rbounds.x1)[splitAxis] = node.splitRight;
+
+    TreeNode left = buildTree(first, l, depth + 1, lbounds);
+    m_tree[node.index.children.left] = left;
+
+    TreeNode right = buildTree(l, last, depth + 1, rbounds);
+    m_tree[node.index.children.right] = right;
+
+    return node;
+}
+
+void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections)
 {
     const QPointF p1 = a.p1();
@@ -358 +518 @@
 }
 
-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())
+void SegmentTree::produceIntersections(int segment)
+{
+    const QRectF &segmentBounds = m_segments.elementBounds(segment);
+
+    RectF sbounds;
+    sbounds.x1 = segmentBounds.left();
+    sbounds.y1 = segmentBounds.top();
+    sbounds.x2 = segmentBounds.right();
+    sbounds.y2 = segmentBounds.bottom();
+
+    produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0);
+}
+
+void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment)
+{
+    const QRectF &r1 = m_segments.elementBounds(segment);
+    const QLineF lineA = m_segments.lineAt(segment);
+
+    for (int i = node.index.interval.first; i < node.index.interval.last; ++i) {
+        const int other = m_index.at(i);
+        if (other >= segment)
             continue;
-        if (r1.top() > rb.bottom() || rb.top() > r1.bottom())
+
+        const QRectF &r2 = m_segments.elementBounds(other);
+
+        if (r1.left() > r2.right() || r2.left() > r1.right())
             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;
+        if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
+            continue;
+
+        m_intersections.reset();
+
+        const QLineF lineB = m_segments.lineAt(other);
+
+        intersectLines(lineA, lineB, m_intersections);
+
+        for (int k = 0; k < m_intersections.size(); ++k) {
+            QPathSegments::Intersection i_isect, j_isect;
+            i_isect.vertex = j_isect.vertex = m_segments.addPoint(m_intersections.at(k).pos);
+
+            i_isect.t = m_intersections.at(k).alphaA;
+            j_isect.t = m_intersections.at(k).alphaB;
+
+            i_isect.next = 0;
+            j_isect.next = 0;
+
+            m_segments.addIntersection(segment, i_isect);
+            m_segments.addIntersection(other, j_isect);
+        }
+    }
+}
+
+void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis)
+{
+    if (node.leaf) {
+        produceIntersectionsLeaf(node, segment);
+        return;
+    }
+
+    RectF lbounds = nodeBounds;
+    (&lbounds.x2)[axis] = node.splitLeft;
+
+    RectF rbounds = nodeBounds;
+    (&rbounds.x1)[axis] = node.splitRight;
+
+    if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft)
+        produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis);
+
+    if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight)
+        produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis);
+}
+
 }
 
 void QIntersectionFinder::produceIntersections(QPathSegments &segments)
 {
-    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);
-            }
-        }
-    }
+    SegmentTree tree(segments);
+
+    for (int i = 0; i < segments.segments(); ++i)
+        tree.produceIntersections(i);
 }
 
@@ -713 +810 @@
         addVertex(m_segments.pointAt(i));
 
-    QDataBuffer<QPathSegments::Intersection> intersections;
+    QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments());
     for (int i = 0; i < m_segments.segments(); ++i) {
         intersections.reset();
@@ -732 +829 @@
         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));
+        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(second).y() ? 1 : -1;
+                const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1;
                 if (pathId == 0)
                     ep->windingA += dir;
@@ -779 +845 @@
                     ep->windingB += dir;
             }
-        }
-    }
-}
-
-QWingedEdge::QWingedEdge()
-{
-}
-
-QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip)
+
+            last = isect.vertex;
+        }
+
+        QPathEdge *ep = edge(addEdge(last, second));
+
+        if (ep) {
+            const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1;
+            if (pathId == 0)
+                ep->windingA += dir;
+            else
+                ep->windingB += dir;
+        }
+    }
+}
+
+QWingedEdge::QWingedEdge() :
+    m_edges(0),
+    m_vertices(0),
+    m_segments(0)
+{
+}
+
+QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) :
+    m_edges(subject.elementCount()),
+    m_vertices(subject.elementCount()),
+    m_segments(subject.elementCount())
 {
     m_segments.setPath(subject);
@@ -833 +917 @@
 {
     m_points.reset();
-    m_beziers.reset();
     m_intersections.reset();
     m_segments.reset();
@@ -880 +963 @@
                     m_segments << Segment(m_pathId, last, current);
                 } else {
-                    m_segments << Segment(m_pathId, last, current, m_beziers.size());
-                    m_beziers << bezier;
+                    QRectF bounds = bezier.bounds();
+
+                    // threshold based on similar algorithm as in qtriangulatingstroker.cpp
+                    int threshold = qMin<float>(64, qMax(bounds.width(), bounds.height()) * (2 * qreal(3.14) / 6));
+
+                    if (threshold < 3) threshold = 3;
+                    qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1);
+
+                    for (int t = 1; t < threshold - 1; ++t) {
+                        currentPoint = bezier.pointAt(t * one_over_threshold_minus_1);
+
+                        int index = m_points.size();
+                        m_segments << Segment(m_pathId, last, index);
+                        last = index;
+
+                        m_points << currentPoint;
+                    }
+
+                    m_segments << Segment(m_pathId, last, current);
                 }
             }
@@ -897 +997 @@
 
     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);
-        }
+        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);
     }
 
@@ -925 +1020 @@
     const QPathEdge *bp = edge(b);
 
-    qreal a_angle = ap->angle;
-    qreal b_angle = bp->angle;
+    double a_angle = ap->angle;
+    double b_angle = bp->angle;
 
     if (vertex == ap->second)
@@ -934 +1029 @@
         b_angle = bp->invAngle;
 
-    qreal result = b_angle - a_angle;
-
-    if (qFuzzyIsNull(result) || qFuzzyCompare(result, 128))
-        return 0;
-
-    if (result < 0)
+    double result = b_angle - a_angle;
+
+    if (result >= 128.)
+        return result - 128.;
+    else if (result < 0)
         return result + 128.;
     else
@@ -945 +1039 @@
 }
 
-static inline QPointF tangentAt(const QWingedEdge &list, int vi, int ei)
+static inline QPointF midPoint(const QWingedEdge &list, 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;
+    const QPointF a = *list.vertex(ep->first);
+    const QPointF b = *list.vertex(ep->second);
+    return a + 0.5 * (b - a);
 }
 
@@ -1086 +1075 @@
 
         Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);
-
         qreal d2 = delta(vi, ei, status.edge);
 
@@ -1094 +1082 @@
 #endif
 
-        if (!(qFuzzyIsNull(d2) && isLeftOf(*this, vi, status.edge, ei))
-            && (d2 < d || (qFuzzyCompare(d2, d) && isLeftOf(*this, vi, status.edge, position)))) {
+        if (d2 < d) {
             position = status.edge;
             d = d2;
@@ -1187 +1174 @@
 }
 
-static qreal computeAngle(const QPointF &v)
+static double computeAngle(const QPointF &v)
 {
 #if 1
@@ -1196 +1183 @@
     }
 
-    QPointF nv = normalize(v);
-    if (nv.y() < 0) {
-        if (nv.x() < 0) { // 0 - 32
-            return -32. * nv.x();
+    double vx = v.x();
+    double vy = v.y();
+    normalize(vx, vy);
+    if (vy < 0) {
+        if (vx < 0) { // 0 - 32
+            return -32. * vx;
         } else { // 96 - 128
-            return 128. - 32. * nv.x();
+            return 128. - 32. * vx;
         }
     } else { // 32 - 96
-        return 64. + 32 * nv.x();
+        return 64. + 32. * vx;
     }
 #else
@@ -1212 +1201 @@
 }
 
-int QWingedEdge::addEdge(const QPointF &a, const QPointF &b, const QBezier *bezier, qreal t0, qreal t1)
+int QWingedEdge::addEdge(const QPointF &a, const QPointF &b)
 {
     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)
+    return addEdge(fi, si);
+}
+
+int QWingedEdge::addEdge(int fi, int si)
 {
     if (fi == si)
@@ -1238 +1227 @@
     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;
-    }
+    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 };
@@ -1315 +1286 @@
 }
 
-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)
 {
@@ -1431 +1334 @@
     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));
 
@@ -1441 +1339 @@
         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)));
+        addLineTo(path, *list.vertex(ep->vertex(status.direction)));
 
         if (status.traversal == QPathEdge::LeftTraversal)
@@ -1470 +1348 @@
         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());
-    }
 }
 
@@ -1536 +1406 @@
         return subjectPath.intersects(r2);
 
-    QPathSegments a;
+    QPathSegments a(subjectPath.elementCount());
     a.setPath(subjectPath);
-    QPathSegments b;
+    QPathSegments b(clipPath.elementCount());
     b.setPath(clipPath);
 
@@ -1581 +1451 @@
         return subjectPath.contains(r2);
 
-    QPathSegments a;
+    QPathSegments a(subjectPath.elementCount());
     a.setPath(subjectPath);
-    QPathSegments b;
+    QPathSegments b(clipPath.elementCount());
     b.setPath(clipPath);
 
@@ -1705 +1575 @@
         if (subjectPath == clipPath)
             return op == BoolSub ? QPainterPath() : subjectPath;
+
+        bool subjectIsRect = pathToRect(subjectPath, 0);
+        bool clipIsRect = pathToRect(clipPath, 0);
 
         const QRectF clipBounds = clipPath.boundingRect();
@@ -1733 +1606 @@
 
         if (clipBounds.contains(subjectBounds)) {
-            QRectF clipRect;
-            if (pathToRect(clipPath, &clipRect) && clipRect.contains(subjectBounds)) {
+            if (clipIsRect) {
                 switch (op) {
                 case BoolSub:
@@ -1747 +1619 @@
             }
         } else if (subjectBounds.contains(clipBounds)) {
-            QRectF subjectRect;
-            if (pathToRect(subjectPath, &subjectRect) && subjectRect.contains(clipBounds)) {
+            if (subjectIsRect) {
                 switch (op) {
                 case BoolSub:
                     if (clipPath.fillRule() == Qt::OddEvenFill) {
                         QPainterPath result = clipPath;
-                        result.addRect(subjectRect);
+                        result.addRect(subjectBounds);
                         return result;
                     } else {
                         QPainterPath result = clipPath.simplified();
-                        result.addRect(subjectRect);
+                        result.addRect(subjectBounds);
                         return result;
                     }
@@ -1770 +1641 @@
             }
         }
+
+        if (op == BoolAnd) {
+            if (subjectIsRect)
+                return intersect(clipPath, subjectBounds);
+            else if (clipIsRect)
+                return intersect(subjectPath, clipBounds);
+        }
     }
 
@@ -1931 +1809 @@
 
         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;
-            }
+            qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());
+
+            if (intersectionX > x)
+                winding += w;
         }
     }
@@ -1965 +1828 @@
 
         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;
-            }
+            const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());
+            const QCrossingEdge edge = { i, intersection };
+            crossings << edge;
         }
     }
@@ -2053 +1908 @@
 }
 
+namespace {
+
+QList<QPainterPath> toSubpaths(const QPainterPath &path)
+{
+
+    QList<QPainterPath> subpaths;
+    if (path.isEmpty())
+        return subpaths;
+
+    QPainterPath current;
+    for (int i = 0; i < path.elementCount(); ++i) {
+        const QPainterPath::Element &e = path.elementAt(i);
+        switch (e.type) {
+        case QPainterPath::MoveToElement:
+            if (current.elementCount() > 1)
+                subpaths += current;
+            current = QPainterPath();
+            current.moveTo(e);
+            break;
+        case QPainterPath::LineToElement:
+            current.lineTo(e);
+            break;
+        case QPainterPath::CurveToElement: {
+            current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2));
+            i+=2;
+            break;
+        }
+        case QPainterPath::CurveToDataElement:
+            Q_ASSERT(!"toSubpaths(), bad element type");
+            break;
+        }
+    }
+
+    if (current.elementCount() > 1)
+        subpaths << current;
+
+    return subpaths;
+}
+
+enum Edge
+{
+    Left, Top, Right, Bottom
+};
+
+static bool isVertical(Edge edge)
+{
+    return edge == Left || edge == Right;
+}
+
+template <Edge edge>
+bool compare(const QPointF &p, qreal t)
+{
+    switch (edge)
+    {
+    case Left:
+        return p.x() < t;
+    case Right:
+        return p.x() > t;
+    case Top:
+        return p.y() < t;
+    default:
+        return p.y() > t;
+    }
+}
+
+template <Edge edge>
+QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t)
+{
+    QLineF line(a, b);
+    switch (edge) {
+    case Left: // fall-through
+    case Right:
+        return line.pointAt((t - a.x()) / (b.x() - a.x()));
+    default:
+        return line.pointAt((t - a.y()) / (b.y() - a.y()));
+    }
+}
+
+void addLine(QPainterPath &path, const QLineF &line)
+{
+    if (path.elementCount() > 0)
+        path.lineTo(line.p1());
+    else
+        path.moveTo(line.p1());
+
+    path.lineTo(line.p2());
+}
+
+template <Edge edge>
+void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result)
+{
+    bool outA = compare<edge>(a, t);
+    bool outB = compare<edge>(b, t);
+    if (outA && outB)
+        return;
+
+    if (outA)
+        addLine(result, QLineF(intersectLine<edge>(a, b, t), b));
+    else if(outB)
+        addLine(result, QLineF(a, intersectLine<edge>(a, b, t)));
+    else
+        addLine(result, QLineF(a, b));
+}
+
+void addBezier(QPainterPath &path, const QBezier &bezier)
+{
+    if (path.elementCount() > 0)
+        path.lineTo(bezier.pt1());
+    else
+        path.moveTo(bezier.pt1());
+
+    path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4());
+}
+
+template <Edge edge>
+void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result)
+{
+    QBezier bezier = QBezier::fromPoints(a, b, c, d);
+
+    bool outA = compare<edge>(a, t);
+    bool outB = compare<edge>(b, t);
+    bool outC = compare<edge>(c, t);
+    bool outD = compare<edge>(d, t);
+
+    int outCount = int(outA) + int(outB) + int(outC) + int(outD);
+
+    if (outCount == 4)
+        return;
+
+    if (outCount == 0) {
+        addBezier(result, bezier);
+        return;
+    }
+
+    QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform();
+    QBezier unflipped = bezier;
+    QBezier flipped = bezier.mapBy(flip);
+
+    qreal t0 = 0, t1 = 1;
+    int stationary = flipped.stationaryYPoints(t0, t1);
+
+    qreal segments[4];
+    QPointF points[4];
+    points[0] = unflipped.pt1();
+    segments[0] = 0;
+
+    int segmentCount = 0;
+    if (stationary > 0) {
+        ++segmentCount;
+        segments[segmentCount] = t0;
+        points[segmentCount] = unflipped.pointAt(t0);
+    }
+    if (stationary > 1) {
+        ++segmentCount;
+        segments[segmentCount] = t1;
+        points[segmentCount] = unflipped.pointAt(t1);
+    }
+    ++segmentCount;
+    segments[segmentCount] = 1;
+    points[segmentCount] = unflipped.pt4();
+
+    qreal lastIntersection = 0;
+    for (int i = 0; i < segmentCount; ++i) {
+        outA = compare<edge>(points[i], t);
+        outB = compare<edge>(points[i+1], t);
+
+        if (outA != outB) {
+            qreal intersection = flipped.tForY(segments[i], segments[i+1], t);
+
+            if (outB)
+                addBezier(result, unflipped.getSubRange(lastIntersection, intersection));
+
+            lastIntersection = intersection;
+        }
+    }
+
+    if (!outB)
+        addBezier(result, unflipped.getSubRange(lastIntersection, 1));
+}
+
+// clips a single subpath against a single edge
+template <Edge edge>
+QPainterPath clip(const QPainterPath &path, qreal t)
+{
+    QPainterPath result;
+    for (int i = 1; i < path.elementCount(); ++i) {
+        const QPainterPath::Element &element = path.elementAt(i);
+        Q_ASSERT(!element.isMoveTo());
+        if (element.isLineTo()) {
+            clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result);
+        } else {
+            clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result);
+            i += 2;
+        }
+    }
+
+    int last = path.elementCount() - 1;
+    if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0)))
+        clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result);
+
+    return result;
+}
+
+QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect)
+{
+    QList<QPainterPath> subpaths = toSubpaths(path);
+
+    QPainterPath result;
+    result.setFillRule(path.fillRule());
+    for (int i = 0; i < subpaths.size(); ++i) {
+        QPainterPath subPath = subpaths.at(i);
+        QRectF bounds = subPath.boundingRect();
+        if (bounds.intersects(rect)) {
+            if (bounds.left() < rect.left())
+                subPath = clip<Left>(subPath, rect.left());
+            if (bounds.right() > rect.right())
+                subPath = clip<Right>(subPath, rect.right());
+
+            bounds = subPath.boundingRect();
+
+            if (bounds.top() < rect.top())
+                subPath = clip<Top>(subPath, rect.top());
+            if (bounds.bottom() > rect.bottom())
+                subPath = clip<Bottom>(subPath, rect.bottom());
+
+            if (subPath.elementCount() > 1)
+                result.addPath(subPath);
+        }
+    }
+    return result;
+}
+
+}
+
+QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect)
+{
+    return intersectPath(path, rect);
+}
+
 QT_END_NAMESPACE