summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSamuel Rødal <sroedal@trolltech.com>2010-02-05 09:13:14 (GMT)
committerSamuel Rødal <sroedal@trolltech.com>2010-02-15 14:42:38 (GMT)
commit8d7046fbd798c6104eca6098b828c505ca32085c (patch)
tree6390afc523e578e30e2fbb87652c3a3d10fc4cdf
parentc77f37f8d9ed021c8a61f50a571b117588e9258f (diff)
downloadQt-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.cpp36
-rw-r--r--src/gui/painting/qbezier_p.h6
-rw-r--r--src/gui/painting/qpathclipper.cpp259
-rw-r--r--src/gui/painting/qpathclipper_p.h1
-rw-r--r--tests/auto/qpathclipper/tst_qpathclipper.cpp18
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;
}