diff options
author | Samuel Rødal <sroedal@trolltech.com> | 2010-02-05 09:13:14 (GMT) |
---|---|---|
committer | Samuel Rødal <sroedal@trolltech.com> | 2010-02-15 14:42:38 (GMT) |
commit | 8d7046fbd798c6104eca6098b828c505ca32085c (patch) | |
tree | 6390afc523e578e30e2fbb87652c3a3d10fc4cdf | |
parent | c77f37f8d9ed021c8a61f50a571b117588e9258f (diff) | |
download | Qt-8d7046fbd798c6104eca6098b828c505ca32085c.zip Qt-8d7046fbd798c6104eca6098b828c505ca32085c.tar.gz Qt-8d7046fbd798c6104eca6098b828c505ca32085c.tar.bz2 |
Improved performance of path vs path intersection where one is a rect.
By special-casing path vs rect intersections we can get much better
performance and more robust clipping.
Task-number: QTBUG-7396
Reviewed-by: Gunnar Sletta
-rw-r--r-- | src/gui/painting/qbezier.cpp | 36 | ||||
-rw-r--r-- | src/gui/painting/qbezier_p.h | 6 | ||||
-rw-r--r-- | src/gui/painting/qpathclipper.cpp | 259 | ||||
-rw-r--r-- | src/gui/painting/qpathclipper_p.h | 1 | ||||
-rw-r--r-- | tests/auto/qpathclipper/tst_qpathclipper.cpp | 18 |
5 files changed, 304 insertions, 16 deletions
diff --git a/src/gui/painting/qbezier.cpp b/src/gui/painting/qbezier.cpp index bbffda1..ea7fe4f 100644 --- a/src/gui/painting/qbezier.cpp +++ b/src/gui/painting/qbezier.cpp @@ -112,6 +112,11 @@ QPolygonF QBezier::toPolygon() const return polygon; } +QBezier QBezier::mapBy(const QTransform &transform) const +{ + return QBezier::fromPoints(transform.map(pt1()), transform.map(pt2()), transform.map(pt3()), transform.map(pt4())); +} + //0.5 is really low static const qreal flatness = 0.5; @@ -140,6 +145,25 @@ static inline void flattenBezierWithoutInflections(QBezier &bez, } } +QBezier QBezier::getSubRange(qreal t0, qreal t1) const +{ + QBezier result; + QBezier temp; + + // cut at t1 + if (qFuzzyIsNull(t1 - qreal(1.))) { + result = *this; + } else { + temp = *this; + temp.parameterSplitLeft(t1, &result); + } + + // cut at t0 + if (!qFuzzyIsNull(t0)) + result.parameterSplitLeft(t0 / t1, &temp); + + return result; +} static inline int quadraticRoots(qreal a, qreal b, qreal c, qreal *x1, qreal *x2) @@ -1018,13 +1042,19 @@ int QBezier::stationaryYPoints(qreal &t0, qreal &t1) const const qreal b = 2 * y1 - 4 * y2 + 2 * y3; const qreal c = -y1 + y2; - qreal reciprocal = b * b - 4 * a * c; + if (qFuzzyIsNull(a)) { + if (qFuzzyIsNull(b)) + return 0; - QList<qreal> result; + t0 = -c / b; + return t0 > 0 && t0 < 1; + } + + qreal reciprocal = b * b - 4 * a * c; if (qFuzzyIsNull(reciprocal)) { t0 = -b / (2 * a); - return 1; + return t0 > 0 && t0 < 1; } else if (reciprocal > 0) { qreal temp = qSqrt(reciprocal); diff --git a/src/gui/painting/qbezier_p.h b/src/gui/painting/qbezier_p.h index 3409bc7..f015ea8 100644 --- a/src/gui/painting/qbezier_p.h +++ b/src/gui/painting/qbezier_p.h @@ -59,6 +59,7 @@ #include "QtCore/qvector.h" #include "QtCore/qlist.h" #include "QtCore/qpair.h" +#include "QtGui/qtransform.h" QT_BEGIN_NAMESPACE @@ -96,6 +97,8 @@ public: QPointF pt3() const { return QPointF(x3, y3); } QPointF pt4() const { return QPointF(x4, y4); } + QBezier mapBy(const QTransform &transform) const; + inline QPointF midPoint() const; inline QLineF midTangent() const; @@ -104,6 +107,7 @@ public: inline void parameterSplitLeft(qreal t, QBezier *left); inline void split(QBezier *firstHalf, QBezier *secondHalf) const; + int shifted(QBezier *curveSegments, int maxSegmets, qreal offset, float threshold) const; @@ -117,6 +121,8 @@ public: static bool findIntersections(const QBezier &a, const QBezier &b, QVector<QPair<qreal, qreal> > *t); + QBezier getSubRange(qreal t0, qreal t1) const; + qreal x1, y1, x2, y2, x3, y3, x4, y4; }; diff --git a/src/gui/painting/qpathclipper.cpp b/src/gui/painting/qpathclipper.cpp index bc81514..949a820 100644 --- a/src/gui/painting/qpathclipper.cpp +++ b/src/gui/painting/qpathclipper.cpp @@ -1705,6 +1705,9 @@ QPainterPath QPathClipper::clip(Operation operation) if (subjectPath == clipPath) return op == BoolSub ? QPainterPath() : subjectPath; + bool subjectIsRect = pathToRect(subjectPath, 0); + bool clipIsRect = pathToRect(clipPath, 0); + const QRectF clipBounds = clipPath.boundingRect(); const QRectF subjectBounds = subjectPath.boundingRect(); @@ -1732,8 +1735,7 @@ QPainterPath QPathClipper::clip(Operation operation) } if (clipBounds.contains(subjectBounds)) { - QRectF clipRect; - if (pathToRect(clipPath, &clipRect) && clipRect.contains(subjectBounds)) { + if (clipIsRect) { switch (op) { case BoolSub: return QPainterPath(); @@ -1746,17 +1748,16 @@ QPainterPath QPathClipper::clip(Operation operation) } } } 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; } break; @@ -1769,6 +1770,13 @@ QPainterPath QPathClipper::clip(Operation operation) } } } + + if (op == BoolAnd) { + if (subjectIsRect) + return intersect(clipPath, subjectBounds); + else if (clipIsRect) + return intersect(subjectPath, clipBounds); + } } QWingedEdge list(subjectPath, clipPath); @@ -2052,4 +2060,243 @@ bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode m return false; } +namespace { + +QList<QPainterPath> toSubpaths(const QPainterPath &path) +{ + + QList<QPainterPath> subpaths; + if (path.isEmpty()) + return subpaths; + + QPainterPath current; + for (int i = 0; i < path.elementCount(); ++i) { + const QPainterPath::Element &e = path.elementAt(i); + switch (e.type) { + case QPainterPath::MoveToElement: + if (current.elementCount() > 1) + subpaths += current; + current = QPainterPath(); + current.moveTo(e); + break; + case QPainterPath::LineToElement: + current.lineTo(e); + break; + case QPainterPath::CurveToElement: { + current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2)); + i+=2; + break; + } + case QPainterPath::CurveToDataElement: + Q_ASSERT(!"toSubpaths(), bad element type"); + break; + } + } + + if (current.elementCount() > 1) + subpaths << current; + + return subpaths; +} + +enum Edge +{ + Left, Top, Right, Bottom +}; + +static bool isVertical(Edge edge) +{ + return edge == Left || edge == Right; +} + +template <Edge edge> +bool compare(const QPointF &p, qreal t) +{ + switch (edge) + { + case Left: + return p.x() < t; + case Right: + return p.x() > t; + case Top: + return p.y() < t; + default: + return p.y() > t; + } +} + +template <Edge edge> +QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t) +{ + QLineF line(a, b); + switch (edge) { + case Left: // fall-through + case Right: + return line.pointAt((t - a.x()) / (b.x() - a.x())); + default: + return line.pointAt((t - a.y()) / (b.y() - a.y())); + } +} + +void addLine(QPainterPath &path, const QLineF &line) +{ + if (path.elementCount() > 0) + path.lineTo(line.p1()); + else + path.moveTo(line.p1()); + + path.lineTo(line.p2()); +} + +template <Edge edge> +void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result) +{ + bool outA = compare<edge>(a, t); + bool outB = compare<edge>(b, t); + if (outA && outB) + return; + + if (outA) + addLine(result, QLineF(intersectLine<edge>(a, b, t), b)); + else if(outB) + addLine(result, QLineF(a, intersectLine<edge>(a, b, t))); + else + addLine(result, QLineF(a, b)); +} + +void addBezier(QPainterPath &path, const QBezier &bezier) +{ + if (path.elementCount() > 0) + path.lineTo(bezier.pt1()); + else + path.moveTo(bezier.pt1()); + + path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4()); +} + +template <Edge edge> +void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result) +{ + QBezier bezier = QBezier::fromPoints(a, b, c, d); + + bool outA = compare<edge>(a, t); + bool outB = compare<edge>(b, t); + bool outC = compare<edge>(c, t); + bool outD = compare<edge>(d, t); + + int outCount = int(outA) + int(outB) + int(outC) + int(outD); + + if (outCount == 4) + return; + + if (outCount == 0) { + addBezier(result, bezier); + return; + } + + QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform(); + QBezier unflipped = bezier; + QBezier flipped = bezier.mapBy(flip); + + qreal t0 = 0, t1 = 1; + int stationary = flipped.stationaryYPoints(t0, t1); + + qreal segments[4]; + QPointF points[4]; + points[0] = unflipped.pt1(); + segments[0] = 0; + + int segmentCount = 0; + if (stationary > 0) { + ++segmentCount; + segments[segmentCount] = t0; + points[segmentCount] = unflipped.pointAt(t0); + } + if (stationary > 1) { + ++segmentCount; + segments[segmentCount] = t1; + points[segmentCount] = unflipped.pointAt(t1); + } + ++segmentCount; + segments[segmentCount] = 1; + points[segmentCount] = unflipped.pt4(); + + qreal lastIntersection = 0; + for (int i = 0; i < segmentCount; ++i) { + outA = compare<edge>(points[i], t); + outB = compare<edge>(points[i+1], t); + + if (outA != outB) { + qreal intersection = flipped.tForY(segments[i], segments[i+1], t); + + if (outB) + addBezier(result, unflipped.getSubRange(lastIntersection, intersection)); + + lastIntersection = intersection; + } + } + + if (!outB) + addBezier(result, unflipped.getSubRange(lastIntersection, 1)); +} + +// clips a single subpath against a single edge +template <Edge edge> +QPainterPath clip(const QPainterPath &path, qreal t) +{ + QPainterPath result; + for (int i = 1; i < path.elementCount(); ++i) { + const QPainterPath::Element &element = path.elementAt(i); + Q_ASSERT(!element.isMoveTo()); + if (element.isLineTo()) { + clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result); + } else { + clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result); + i += 2; + } + } + + int last = path.elementCount() - 1; + if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0))) + clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result); + + return result; +} + +QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect) +{ + QList<QPainterPath> subpaths = toSubpaths(path); + + QPainterPath result; + result.setFillRule(path.fillRule()); + for (int i = 0; i < subpaths.size(); ++i) { + QPainterPath subPath = subpaths.at(i); + QRectF bounds = subPath.boundingRect(); + if (bounds.intersects(rect)) { + if (bounds.left() < rect.left()) + subPath = clip<Left>(subPath, rect.left()); + if (bounds.right() > rect.right()) + subPath = clip<Right>(subPath, rect.right()); + + bounds = subPath.boundingRect(); + + if (bounds.top() < rect.top()) + subPath = clip<Top>(subPath, rect.top()); + if (bounds.bottom() > rect.bottom()) + subPath = clip<Bottom>(subPath, rect.bottom()); + + if (subPath.elementCount() > 1) + result.addPath(subPath); + } + } + return result; +} + +} + +QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect) +{ + return intersectPath(path, rect); +} + QT_END_NAMESPACE diff --git a/src/gui/painting/qpathclipper_p.h b/src/gui/painting/qpathclipper_p.h index b900862..b42dc1d 100644 --- a/src/gui/painting/qpathclipper_p.h +++ b/src/gui/painting/qpathclipper_p.h @@ -87,6 +87,7 @@ public: bool contains(); static bool pathToRect(const QPainterPath &path, QRectF *rect = 0); + static QPainterPath intersect(const QPainterPath &path, const QRectF &rect); private: Q_DISABLE_COPY(QPathClipper) diff --git a/tests/auto/qpathclipper/tst_qpathclipper.cpp b/tests/auto/qpathclipper/tst_qpathclipper.cpp index 5b49545..9e37988 100644 --- a/tests/auto/qpathclipper/tst_qpathclipper.cpp +++ b/tests/auto/qpathclipper/tst_qpathclipper.cpp @@ -336,13 +336,17 @@ static QPainterPath samplePath13() static QPainterPath samplePath14() { QPainterPath path; - path.moveTo(QPointF(100, 180)); - path.lineTo(QPointF(100, 80)); - path.lineTo(QPointF(120, 80)); - path.lineTo(QPointF(120, 100)); - path.lineTo(QPointF(160, 100)); - path.lineTo(QPointF(160, 180)); - path.lineTo(QPointF(100, 180)); + + path.moveTo(160, 80); + path.lineTo(160, 180); + path.lineTo(100, 180); + path.lineTo(100, 80); + path.lineTo(160, 80); + path.moveTo(160, 80); + path.lineTo(160, 100); + path.lineTo(120, 100); + path.lineTo(120, 80); + return path; } |