From c46688b8a88da02028405604ab633b27d3fefa68 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Samuel=20R=C3=B8dal?= Date: Tue, 11 May 2010 12:46:46 +0200 Subject: Made curve tesselation be dynamically adjusted based on transform. This lets us avoid having to use a very low curve threshold value for all scales, and thus avoids the performance regression from change c41dbbb5e6495e26cd32. Task-number: QTBUG-9218 Reviewed-by: Gunnar Sletta --- src/gui/painting/qbezier.cpp | 228 +----------------------------------- src/gui/painting/qbezier_p.h | 7 +- src/gui/painting/qpaintengineex.cpp | 2 + src/gui/painting/qstroker.cpp | 23 ++-- src/gui/painting/qstroker_p.h | 18 ++- src/gui/painting/qtransform.cpp | 9 +- src/s60installs/bwins/QtGuiu.def | 4 +- src/s60installs/eabi/QtGuiu.def | 4 +- 8 files changed, 50 insertions(+), 245 deletions(-) diff --git a/src/gui/painting/qbezier.cpp b/src/gui/painting/qbezier.cpp index 7ff2a37..2a9b31a 100644 --- a/src/gui/painting/qbezier.cpp +++ b/src/gui/painting/qbezier.cpp @@ -93,7 +93,7 @@ QBezier QBezier::fromPoints(const QPointF &p1, const QPointF &p2, /*! \internal */ -QPolygonF QBezier::toPolygon() const +QPolygonF QBezier::toPolygon(qreal bezier_flattening_threshold) const { // flattening is done by splitting the bezier until we can replace the segment by a straight // line. We split further until the control points are close enough to the line connecting the @@ -108,7 +108,7 @@ QPolygonF QBezier::toPolygon() const QPolygonF polygon; polygon.append(QPointF(x1, y1)); - addToPolygon(&polygon); + addToPolygon(&polygon, bezier_flattening_threshold); return polygon; } @@ -117,34 +117,6 @@ QBezier QBezier::mapBy(const QTransform &transform) const return QBezier::fromPoints(transform.map(pt1()), transform.map(pt2()), transform.map(pt3()), transform.map(pt4())); } -//0.05 is really low, but required for scaled-up beziers... -static const qreal flatness = 0.05; - -//based on "Fast, precise flattening of cubic Bezier path and offset curves" -// by T. F. Hain, A. L. Ahmad, S. V. R. Racherla and D. D. Langan -static inline void flattenBezierWithoutInflections(QBezier &bez, - QPolygonF *&p) -{ - QBezier left; - - while (1) { - qreal dx = bez.x2 - bez.x1; - qreal dy = bez.y2 - bez.y1; - - qreal normalized = qSqrt(dx * dx + dy * dy); - if (qFuzzyIsNull(normalized)) - break; - - qreal d = qAbs(dx * (bez.y3 - bez.y2) - dy * (bez.x3 - bez.x2)); - - qreal t = qSqrt(4. / 3. * normalized * flatness / d); - if (t > 1 || qFuzzyIsNull(t - (qreal)1.)) - break; - bez.parameterSplitLeft(t, &left); - p->append(bez.pt1()); - } -} - QBezier QBezier::getSubRange(qreal t0, qreal t1) const { QBezier result; @@ -223,7 +195,7 @@ static inline bool findInflections(qreal a, qreal b, qreal c, } -void QBezier::addToPolygon(QPolygonF *polygon) const +void QBezier::addToPolygon(QPolygonF *polygon, qreal bezier_flattening_threshold) const { QBezier beziers[32]; beziers[0] = *this; @@ -243,7 +215,7 @@ void QBezier::addToPolygon(QPolygonF *polygon) const qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3); l = 1.; } - if (d < flatness*l || b == beziers + 31) { + if (d < bezier_flattening_threshold*l || b == beziers + 31) { // good enough, we pop it off and add the endpoint polygon->append(QPointF(b->x4, b->y4)); --b; @@ -255,55 +227,6 @@ void QBezier::addToPolygon(QPolygonF *polygon) const } } -void QBezier::addToPolygonMixed(QPolygonF *polygon) const -{ - qreal ax = -x1 + 3*x2 - 3*x3 + x4; - qreal ay = -y1 + 3*y2 - 3*y3 + y4; - qreal bx = 3*x1 - 6*x2 + 3*x3; - qreal by = 3*y1 - 6*y2 + 3*y3; - qreal cx = -3*x1 + 3*x2; - qreal cy = -3*y1 + 2*y2; - qreal a = 6 * (ay * bx - ax * by); - qreal b = 6 * (ay * cx - ax * cy); - qreal c = 2 * (by * cx - bx * cy); - - if ((qFuzzyIsNull(a) && qFuzzyIsNull(b)) || - (b * b - 4 * a *c) < 0) { - QBezier bez(*this); - flattenBezierWithoutInflections(bez, polygon); - polygon->append(QPointF(x4, y4)); - } else { - QBezier beziers[32]; - beziers[0] = *this; - QBezier *b = beziers; - - while (b >= beziers) { - // check if we can pop the top bezier curve from the stack - qreal y4y1 = b->y4 - b->y1; - qreal x4x1 = b->x4 - b->x1; - qreal l = qAbs(x4x1) + qAbs(y4y1); - qreal d; - if (l > 1.) { - d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) ) - + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) ); - } else { - d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) + - qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3); - l = 1.; - } - if (d < .5*l || b == beziers + 31) { - // good enough, we pop it off and add the endpoint - polygon->append(QPointF(b->x4, b->y4)); - --b; - } else { - // split, second half of the polygon goes lower into the stack - b->split(b+1, b); - ++b; - } - } - } -} - QRectF QBezier::bounds() const { qreal xmin = x1; @@ -824,147 +747,4 @@ QBezier QBezier::bezierOnInterval(qreal t0, qreal t1) const return result; } - -static inline void bindInflectionPoint(const QBezier &bez, const qreal t, - qreal *tMinus , qreal *tPlus) -{ - if (t <= 0) { - *tMinus = *tPlus = -1; - return; - } else if (t >= 1) { - *tMinus = *tPlus = 2; - return; - } - - QBezier left, right; - splitBezierAt(bez, t, &left, &right); - - qreal ax = -right.x1 + 3*right.x2 - 3*right.x3 + right.x4; - qreal ay = -right.y1 + 3*right.y2 - 3*right.y3 + right.y4; - qreal ex = 3 * (right.x2 - right.x3); - qreal ey = 3 * (right.y2 - right.y3); - - qreal s4 = qAbs(6 * (ey * ax - ex * ay) / qSqrt(ex * ex + ey * ey)) + 0.00001f; - qreal tf = qPow(qreal(9 * flatness / s4), qreal(1./3.)); - *tMinus = t - (1 - t) * tf; - *tPlus = t + (1 - t) * tf; -} - -void QBezier::addToPolygonIterative(QPolygonF *p) const -{ - qreal t1, t2, tcusp; - qreal t1min, t1plus, t2min, t2plus; - - qreal ax = -x1 + 3*x2 - 3*x3 + x4; - qreal ay = -y1 + 3*y2 - 3*y3 + y4; - qreal bx = 3*x1 - 6*x2 + 3*x3; - qreal by = 3*y1 - 6*y2 + 3*y3; - qreal cx = -3*x1 + 3*x2; - qreal cy = -3*y1 + 2*y2; - - if (findInflections(6 * (ay * bx - ax * by), - 6 * (ay * cx - ax * cy), - 2 * (by * cx - bx * cy), - &t1, &t2, &tcusp)) { - bindInflectionPoint(*this, t1, &t1min, &t1plus); - bindInflectionPoint(*this, t2, &t2min, &t2plus); - - QBezier tmpBez = *this; - QBezier left, right, bez1, bez2, bez3; - if (t1min > 0) { - if (t1min >= 1) { - flattenBezierWithoutInflections(tmpBez, p); - } else { - splitBezierAt(tmpBez, t1min, &left, &right); - flattenBezierWithoutInflections(left, p); - p->append(tmpBez.pointAt(t1min)); - - if (t2min < t1plus) { - if (tcusp < 1) { - p->append(tmpBez.pointAt(tcusp)); - } - if (t2plus < 1) { - splitBezierAt(tmpBez, t2plus, &left, &right); - flattenBezierWithoutInflections(right, p); - } - } else if (t1plus < 1) { - if (t2min < 1) { - splitBezierAt(tmpBez, t2min, &bez3, &right); - splitBezierAt(bez3, t1plus, &left, &bez2); - - flattenBezierWithoutInflections(bez2, p); - p->append(tmpBez.pointAt(t2min)); - - if (t2plus < 1) { - splitBezierAt(tmpBez, t2plus, &left, &bez2); - flattenBezierWithoutInflections(bez2, p); - } - } else { - splitBezierAt(tmpBez, t1plus, &left, &bez2); - flattenBezierWithoutInflections(bez2, p); - } - } - } - } else if (t1plus > 0) { - p->append(QPointF(x1, y1)); - if (t2min < t1plus) { - if (tcusp < 1) { - p->append(tmpBez.pointAt(tcusp)); - } - if (t2plus < 1) { - splitBezierAt(tmpBez, t2plus, &left, &bez2); - flattenBezierWithoutInflections(bez2, p); - } - } else if (t1plus < 1) { - if (t2min < 1) { - splitBezierAt(tmpBez, t2min, &bez3, &right); - splitBezierAt(bez3, t1plus, &left, &bez2); - - flattenBezierWithoutInflections(bez2, p); - - p->append(tmpBez.pointAt(t2min)); - if (t2plus < 1) { - splitBezierAt(tmpBez, t2plus, &left, &bez2); - flattenBezierWithoutInflections(bez2, p); - } - } else { - splitBezierAt(tmpBez, t1plus, &left, &bez2); - flattenBezierWithoutInflections(bez2, p); - } - } - } else if (t2min > 0) { - if (t2min < 1) { - splitBezierAt(tmpBez, t2min, &bez1, &right); - flattenBezierWithoutInflections(bez1, p); - p->append(tmpBez.pointAt(t2min)); - - if (t2plus < 1) { - splitBezierAt(tmpBez, t2plus, &left, &bez2); - flattenBezierWithoutInflections(bez2, p); - } - } else { - //### in here we should check whether the area of the - // triangle formed between pt1/pt2/pt3 is smaller - // or equal to 0 and then do iterative flattening - // if not we should fallback and do the recursive - // flattening. - flattenBezierWithoutInflections(tmpBez, p); - } - } else if (t2plus > 0) { - p->append(QPointF(x1, y1)); - if (t2plus < 1) { - splitBezierAt(tmpBez, t2plus, &left, &bez2); - flattenBezierWithoutInflections(bez2, p); - } - } else { - flattenBezierWithoutInflections(tmpBez, p); - } - } else { - QBezier bez = *this; - flattenBezierWithoutInflections(bez, p); - } - - p->append(QPointF(x4, y4)); -} - QT_END_NAMESPACE diff --git a/src/gui/painting/qbezier_p.h b/src/gui/painting/qbezier_p.h index 846635f..18ec116 100644 --- a/src/gui/painting/qbezier_p.h +++ b/src/gui/painting/qbezier_p.h @@ -79,10 +79,9 @@ public: inline QPointF derivedAt(qreal t) const; inline QPointF secondDerivedAt(qreal t) const; - QPolygonF toPolygon() const; - void addToPolygon(QPolygonF *p) const; - void addToPolygonIterative(QPolygonF *p) const; - void addToPolygonMixed(QPolygonF *p) const; + QPolygonF toPolygon(qreal bezier_flattening_threshold = 0.5) const; + void addToPolygon(QPolygonF *p, qreal bezier_flattening_threshold = 0.5) const; + QRectF bounds() const; qreal length(qreal error = 0.01) const; void addIfClose(qreal *length, qreal error) const; diff --git a/src/gui/painting/qpaintengineex.cpp b/src/gui/painting/qpaintengineex.cpp index fda937e..ff82d59 100644 --- a/src/gui/painting/qpaintengineex.cpp +++ b/src/gui/painting/qpaintengineex.cpp @@ -461,6 +461,7 @@ void QPaintEngineEx::stroke(const QVectorPath &path, const QPen &pen) // change the current transform. Normal transformed, // non-cosmetic pens will be transformed as part of fill // later, so they are also covered here.. + d->activeStroker->setCurveThresholdFromTransform(state()->matrix); d->activeStroker->begin(d->strokeHandler); if (types) { while (points < lastPoint) { @@ -518,6 +519,7 @@ void QPaintEngineEx::stroke(const QVectorPath &path, const QPen &pen) QPainterPath painterPath = state()->matrix.map(path.convertToPainterPath()); d->activeStroker->strokePath(painterPath, d->strokeHandler, QTransform()); } else { + d->activeStroker->setCurveThresholdFromTransform(state()->matrix); d->activeStroker->begin(d->strokeHandler); if (types) { while (points < lastPoint) { diff --git a/src/gui/painting/qstroker.cpp b/src/gui/painting/qstroker.cpp index 9b8e099..eabbd8a 100644 --- a/src/gui/painting/qstroker.cpp +++ b/src/gui/painting/qstroker.cpp @@ -120,8 +120,8 @@ private: class QSubpathFlatIterator { public: - QSubpathFlatIterator(const QDataBuffer *path) - : m_path(path), m_pos(0), m_curve_index(-1) { } + QSubpathFlatIterator(const QDataBuffer *path, qreal threshold) + : m_path(path), m_pos(0), m_curve_index(-1), m_curve_threshold(threshold) { } inline bool hasNext() const { return m_curve_index >= 0 || m_pos < m_path->size(); } @@ -152,7 +152,7 @@ public: QPointF(qt_fixed_to_real(m_path->at(m_pos+1).x), qt_fixed_to_real(m_path->at(m_pos+1).y)), QPointF(qt_fixed_to_real(m_path->at(m_pos+2).x), - qt_fixed_to_real(m_path->at(m_pos+2).y))).toPolygon(); + qt_fixed_to_real(m_path->at(m_pos+2).y))).toPolygon(m_curve_threshold); m_curve_index = 1; e.type = QPainterPath::LineToElement; e.x = m_curve.at(0).x(); @@ -169,6 +169,7 @@ private: int m_pos; QPolygonF m_curve; int m_curve_index; + qreal m_curve_threshold; }; template bool qt_stroke_side(Iterator *it, QStroker *stroker, @@ -187,7 +188,12 @@ static inline qreal adapted_angle_on_x(const QLineF &line) } QStrokerOps::QStrokerOps() - : m_elements(0), m_customData(0), m_moveTo(0), m_lineTo(0), m_cubicTo(0) + : m_elements(0) + , m_curveThreshold(qt_real_to_fixed(0.25)) + , m_customData(0) + , m_moveTo(0) + , m_lineTo(0) + , m_cubicTo(0) { } @@ -195,7 +201,6 @@ QStrokerOps::~QStrokerOps() { } - /*! Prepares the stroker. Call this function once before starting a stroke by calling moveTo, lineTo or cubicTo. @@ -238,6 +243,7 @@ void QStrokerOps::strokePath(const QPainterPath &path, void *customData, const Q if (path.isEmpty()) return; + setCurveThresholdFromTransform(matrix); begin(customData); int count = path.elementCount(); if (matrix.isIdentity()) { @@ -308,6 +314,8 @@ void QStrokerOps::strokePolygon(const QPointF *points, int pointCount, bool impl { if (!pointCount) return; + + setCurveThresholdFromTransform(matrix); begin(data); if (matrix.isIdentity()) { moveTo(qt_real_to_fixed(points[0].x()), qt_real_to_fixed(points[0].y())); @@ -348,6 +356,7 @@ void QStrokerOps::strokeEllipse(const QRectF &rect, void *data, const QTransform } } + setCurveThresholdFromTransform(matrix); begin(data); moveTo(qt_real_to_fixed(start.x()), qt_real_to_fixed(start.y())); for (int i=0; i<12; i+=3) { @@ -366,12 +375,10 @@ QStroker::QStroker() { m_strokeWidth = qt_real_to_fixed(1); m_miterLimit = qt_real_to_fixed(2); - m_curveThreshold = qt_real_to_fixed(0.25); } QStroker::~QStroker() { - } Qt::PenCapStyle QStroker::capForJoinMode(LineJoinMode mode) @@ -1135,7 +1142,7 @@ void QDashStroker::processCurrentSubpath() QPainterPath dashPath; - QSubpathFlatIterator it(&m_elements); + QSubpathFlatIterator it(&m_elements, m_curveThreshold); qfixed2d prev = it.next(); bool clipping = !m_clip_rect.isEmpty(); diff --git a/src/gui/painting/qstroker_p.h b/src/gui/painting/qstroker_p.h index 3e622a8..0f133ef 100644 --- a/src/gui/painting/qstroker_p.h +++ b/src/gui/painting/qstroker_p.h @@ -124,6 +124,9 @@ typedef void (*qStrokerCubicToHook)(qfixed c1x, qfixed c1y, qfixed ex, qfixed ey, void *data); +// qtransform.cpp +extern bool qt_scaleForTransform(const QTransform &transform, qreal *scale); + class Q_GUI_EXPORT QStrokerOps { public: @@ -161,6 +164,16 @@ public: QRectF clipRect() const { return m_clip_rect; } void setClipRect(const QRectF &clip) { m_clip_rect = clip; } + void setCurveThresholdFromTransform(const QTransform &transform) + { + qreal scale; + qt_scaleForTransform(transform, &scale); + setCurveThreshold(scale == 0 ? qreal(0.5) : (qreal(0.5) / scale)); + } + + void setCurveThreshold(qfixed threshold) { m_curveThreshold = threshold; } + qfixed curveThreshold() const { return m_curveThreshold; } + protected: inline void emitMoveTo(qfixed x, qfixed y); inline void emitLineTo(qfixed x, qfixed y); @@ -170,6 +183,7 @@ protected: QDataBuffer m_elements; QRectF m_clip_rect; + qfixed m_curveThreshold; void *m_customData; qStrokerMoveToHook m_moveTo; @@ -208,9 +222,6 @@ public: void setMiterLimit(qfixed length) { m_miterLimit = length; } qfixed miterLimit() const { return m_miterLimit; } - void setCurveThreshold(qfixed threshold) { m_curveThreshold = threshold; } - qfixed curveThreshold() const { return m_curveThreshold; } - void joinPoints(qfixed x, qfixed y, const QLineF &nextLine, LineJoinMode join); inline void emitMoveTo(qfixed x, qfixed y); inline void emitLineTo(qfixed x, qfixed y); @@ -227,7 +238,6 @@ protected: qfixed m_strokeWidth; qfixed m_miterLimit; - qfixed m_curveThreshold; LineJoinMode m_capStyle; LineJoinMode m_joinStyle; diff --git a/src/gui/painting/qtransform.cpp b/src/gui/painting/qtransform.cpp index 80b7520..c72a08e 100644 --- a/src/gui/painting/qtransform.cpp +++ b/src/gui/painting/qtransform.cpp @@ -1545,12 +1545,19 @@ static inline bool lineTo_clipped(QPainterPath &path, const QTransform &transfor return true; } +bool qt_scaleForTransform(const QTransform &transform, qreal *scale); static inline bool cubicTo_clipped(QPainterPath &path, const QTransform &transform, const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, bool needsMoveTo) { // Convert projective xformed curves to line // segments so they can be transformed more accurately - QPolygonF segment = QBezier::fromPoints(a, b, c, d).toPolygon(); + + qreal scale; + qt_scaleForTransform(transform, &scale); + + qreal curveThreshold = scale == 0 ? qreal(0.25) : (qreal(0.25) / scale); + + QPolygonF segment = QBezier::fromPoints(a, b, c, d).toPolygon(curveThreshold); for (int i = 0; i < segment.size() - 1; ++i) if (lineTo_clipped(path, transform, segment.at(i), segment.at(i+1), needsMoveTo)) diff --git a/src/s60installs/bwins/QtGuiu.def b/src/s60installs/bwins/QtGuiu.def index c3a3a08..8957c34 100644 --- a/src/s60installs/bwins/QtGuiu.def +++ b/src/s60installs/bwins/QtGuiu.def @@ -2126,8 +2126,8 @@ EXPORTS ?addToGroup@QGraphicsItemGroup@@QAEXPAVQGraphicsItem@@@Z @ 2125 NONAME ; void QGraphicsItemGroup::addToGroup(class QGraphicsItem *) ?addToIndex@QGraphicsItem@@IAEXXZ @ 2126 NONAME ; void QGraphicsItem::addToIndex(void) ?addToPolygon@QBezier@@QBEXPAVQPolygonF@@@Z @ 2127 NONAME ; void QBezier::addToPolygon(class QPolygonF *) const - ?addToPolygonIterative@QBezier@@QBEXPAVQPolygonF@@@Z @ 2128 NONAME ; void QBezier::addToPolygonIterative(class QPolygonF *) const - ?addToPolygonMixed@QBezier@@QBEXPAVQPolygonF@@@Z @ 2129 NONAME ; void QBezier::addToPolygonMixed(class QPolygonF *) const + ?addToPolygonIterative@QBezier@@QBEXPAVQPolygonF@@@Z @ 2128 NONAME ABSENT ; void QBezier::addToPolygonIterative(class QPolygonF *) const + ?addToPolygonMixed@QBezier@@QBEXPAVQPolygonF@@@Z @ 2129 NONAME ABSENT ; void QBezier::addToPolygonMixed(class QPolygonF *) const ?addToolBar@QMainWindow@@QAEPAVQToolBar@@ABVQString@@@Z @ 2130 NONAME ; class QToolBar * QMainWindow::addToolBar(class QString const &) ?addToolBar@QMainWindow@@QAEXPAVQToolBar@@@Z @ 2131 NONAME ; void QMainWindow::addToolBar(class QToolBar *) ?addToolBar@QMainWindow@@QAEXW4ToolBarArea@Qt@@PAVQToolBar@@@Z @ 2132 NONAME ; void QMainWindow::addToolBar(enum Qt::ToolBarArea, class QToolBar *) diff --git a/src/s60installs/eabi/QtGuiu.def b/src/s60installs/eabi/QtGuiu.def index b1166c5..d127b41 100644 --- a/src/s60installs/eabi/QtGuiu.def +++ b/src/s60installs/eabi/QtGuiu.def @@ -9901,9 +9901,9 @@ EXPORTS _ZNK7QBezier10addIfCloseEPff @ 9900 NONAME _ZNK7QBezier12addToPolygonEP9QPolygonF @ 9901 NONAME _ZNK7QBezier16bezierOnIntervalEff @ 9902 NONAME - _ZNK7QBezier17addToPolygonMixedEP9QPolygonF @ 9903 NONAME + _ZNK7QBezier17addToPolygonMixedEP9QPolygonF @ 9903 NONAME ABSENT _ZNK7QBezier17stationaryYPointsERfS0_ @ 9904 NONAME - _ZNK7QBezier21addToPolygonIterativeEP9QPolygonF @ 9905 NONAME + _ZNK7QBezier21addToPolygonIterativeEP9QPolygonF @ 9905 NONAME ABSENT _ZNK7QBezier5tForYEfff @ 9906 NONAME _ZNK7QBezier6boundsEv @ 9907 NONAME _ZNK7QBezier6lengthEf @ 9908 NONAME -- cgit v0.12