Improved path filling performance in the raster paint engine.

Convert bezier curves to polylines before rasterizing with gray
raster.

Change-Id: I353debd4338f2a3ce2fa1cfa1bff9dd2e36f05ab
Reviewed-by: Gunnar Sletta <gunnar.sletta@nokia.com>

4 files changed, 93 insertions, 55 deletions

diff --git a/src/gui/painting/qbezier.cpp b/src/gui/painting/qbezier.cpp
index 9d204f9a39..bdba3f21ef 100644
--- a/src/gui/painting/qbezier.cpp
+++ b/src/gui/painting/qbezier.cpp
@@ -220,6 +220,38 @@ void QBezier::addToPolygon(QPolygonF *polygon, qreal bezier_flattening_threshold
     }
 }
 
+void QBezier::addToPolygon(QDataBuffer<QPointF> &polygon, qreal bezier_flattening_threshold) const
+{
+    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 < bezier_flattening_threshold*l || b == beziers + 31) {
+            // good enough, we pop it off and add the endpoint
+            polygon.add(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;
diff --git a/src/gui/painting/qbezier_p.h b/src/gui/painting/qbezier_p.h
index f1f7eb155a..e8594ffa5a 100644
--- a/src/gui/painting/qbezier_p.h
+++ b/src/gui/painting/qbezier_p.h
@@ -60,6 +60,7 @@
 #include "QtCore/qlist.h"
 #include "QtCore/qpair.h"
 #include "QtGui/qtransform.h"
+#include <private/qdatabuffer_p.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -81,6 +82,7 @@ public:
 
     QPolygonF toPolygon(qreal bezier_flattening_threshold = 0.5) const;
     void addToPolygon(QPolygonF *p, qreal bezier_flattening_threshold = 0.5) const;
+    void addToPolygon(QDataBuffer<QPointF> &polygon, qreal bezier_flattening_threshold) const;
 
     QRectF bounds() const;
     qreal length(qreal error = 0.01) const;
diff --git a/src/gui/painting/qoutlinemapper.cpp b/src/gui/painting/qoutlinemapper.cpp
index 8b607b28b8..1aa77592ae 100644
--- a/src/gui/painting/qoutlinemapper.cpp
+++ b/src/gui/painting/qoutlinemapper.cpp
@@ -42,6 +42,7 @@
 #include "qoutlinemapper_p.h"
 #include <private/qpainterpath_p.h>
 #include "qmath.h"
+#include <private/qbezier_p.h>
 
 #include <stdlib.h>
 
@@ -74,6 +75,19 @@ static const QRectF boundingRect(const QPointF *points, int pointCount)
     return QRectF(QPointF(minx, miny), QPointF(maxx, maxy));
 }
 
+void QOutlineMapper::curveTo(const QPointF &cp1, const QPointF &cp2, const QPointF &ep) {
+#ifdef QT_DEBUG_CONVERT
+    printf("QOutlineMapper::curveTo() (%f, %f)\n", ep.x(), ep.y());
+#endif
+
+    QBezier bezier = QBezier::fromPoints(m_elements.last(), cp1, cp2, ep);
+    bezier.addToPolygon(m_elements, m_curve_threshold);
+    m_element_types.reserve(m_elements.size());
+    for (int i = m_elements.size() - m_element_types.size(); i; --i)
+        m_element_types << QPainterPath::LineToElement;
+    Q_ASSERT(m_elements.size() == m_element_types.size());
+}
+
 
 QT_FT_Outline *QOutlineMapper::convertPath(const QPainterPath &path)
 {
@@ -169,51 +183,47 @@ void QOutlineMapper::endOutline()
 {
     closeSubpath();
 
-    int element_count = m_elements.size();
-
-    if (element_count == 0) {
+    if (m_elements.isEmpty()) {
         memset(&m_outline, 0, sizeof(m_outline));
         return;
     }
 
-    QPointF *elements;
+    QPointF *elements = m_elements.data();
 
     // Transform the outline
     if (m_txop == QTransform::TxNone) {
-        elements = m_elements.data();
-    } else {
-        if (m_txop == QTransform::TxTranslate) {
-            for (int i=0; i<m_elements.size(); ++i) {
-                const QPointF &e = m_elements.at(i);
-                m_elements_dev << QPointF(e.x() + m_dx, e.y() + m_dy);
-            }
-        } else if (m_txop == QTransform::TxScale) {
-            for (int i=0; i<m_elements.size(); ++i) {
-                const QPointF &e = m_elements.at(i);
-                m_elements_dev << QPointF(m_m11 * e.x() + m_dx, m_m22 * e.y() + m_dy);
-            }
-        } else if (m_txop < QTransform::TxProject) {
-            for (int i=0; i<m_elements.size(); ++i) {
-                const QPointF &e = m_elements.at(i);
-                m_elements_dev << QPointF(m_m11 * e.x() + m_m21 * e.y() + m_dx,
-                                          m_m22 * e.y() + m_m12 * e.x() + m_dy);
-            }
-        } else {
-            const QVectorPath vp((qreal *)m_elements.data(), m_elements.size(), m_element_types.size() ? m_element_types.data() : 0);
-            QPainterPath path = vp.convertToPainterPath();
-            path = QTransform(m_m11, m_m12, m_m13, m_m21, m_m22, m_m23, m_dx, m_dy, m_m33).map(path);
-            if (!(m_outline.flags & QT_FT_OUTLINE_EVEN_ODD_FILL))
-                path.setFillRule(Qt::WindingFill);
-            uint old_txop = m_txop;
-            m_txop = QTransform::TxNone;
-            if (path.isEmpty())
-                m_valid = false;
-            else
-                convertPath(path);
-            m_txop = old_txop;
-            return;
+        // Nothing to do.
+    } else if (m_txop == QTransform::TxTranslate) {
+        for (int i = 0; i < m_elements.size(); ++i) {
+            QPointF &e = elements[i];
+            e = QPointF(e.x() + m_dx, e.y() + m_dy);
+        }
+    } else if (m_txop == QTransform::TxScale) {
+        for (int i = 0; i < m_elements.size(); ++i) {
+            QPointF &e = elements[i];
+            e = QPointF(m_m11 * e.x() + m_dx, m_m22 * e.y() + m_dy);
         }
-        elements = m_elements_dev.data();
+    } else if (m_txop < QTransform::TxProject) {
+        for (int i = 0; i < m_elements.size(); ++i) {
+            QPointF &e = elements[i];
+            e = QPointF(m_m11 * e.x() + m_m21 * e.y() + m_dx,
+                        m_m22 * e.y() + m_m12 * e.x() + m_dy);
+        }
+    } else {
+        const QVectorPath vp((qreal *)elements, m_elements.size(),
+                             m_element_types.size() ? m_element_types.data() : 0);
+        QPainterPath path = vp.convertToPainterPath();
+        path = QTransform(m_m11, m_m12, m_m13, m_m21, m_m22, m_m23, m_dx, m_dy, m_m33).map(path);
+        if (!(m_outline.flags & QT_FT_OUTLINE_EVEN_ODD_FILL))
+            path.setFillRule(Qt::WindingFill);
+        uint old_txop = m_txop;
+        m_txop = QTransform::TxNone;
+        if (path.isEmpty())
+            m_valid = false;
+        else
+            convertPath(path);
+        m_txop = old_txop;
+        return;
     }
 
     if (m_round_coords) {
@@ -223,7 +233,7 @@ void QOutlineMapper::endOutline()
                                   qFloor(elements[i].y() + aliasedCoordinateDelta));
     }
 
-    controlPointRect = boundingRect(elements, element_count);
+    controlPointRect = boundingRect(elements, m_elements.size());
 
 #ifdef QT_DEBUG_CONVERT
     printf(" - control point rect (%.2f, %.2f) %.2f x %.2f, clip=(%d,%d, %dx%d)\n",
@@ -242,9 +252,9 @@ void QOutlineMapper::endOutline()
                           || controlPointRect.height() > QT_RASTER_COORD_LIMIT));
 
     if (do_clip) {
-        clipElements(elements, elementTypes(), element_count);
+        clipElements(elements, elementTypes(), m_elements.size());
     } else {
-        convertElements(elements, elementTypes(), element_count);
+        convertElements(elements, elementTypes(), m_elements.size());
     }
 }
 
diff --git a/src/gui/painting/qoutlinemapper_p.h b/src/gui/painting/qoutlinemapper_p.h
index 388858ca44..7bcf3166ca 100644
--- a/src/gui/painting/qoutlinemapper_p.h
+++ b/src/gui/painting/qoutlinemapper_p.h
@@ -73,6 +73,8 @@ const int QT_RASTER_COORD_LIMIT = 32767;
 
 //#define QT_DEBUG_CONVERT
 
+Q_GUI_EXPORT bool qt_scaleForTransform(const QTransform &transform, qreal *scale);
+
 /********************************************************************************
  * class QOutlineMapper
  *
@@ -90,11 +92,9 @@ public:
     QOutlineMapper() :
         m_element_types(0),
         m_elements(0),
-        m_elements_dev(0),
         m_points(0),
         m_tags(0),
         m_contours(0),
-        m_polygon_dev(0),
         m_in_clip_elements(false),
         m_round_coords(false)
     {
@@ -117,6 +117,10 @@ public:
         m_dx = m.dx();
         m_dy = m.dy();
         m_txop = m.type();
+
+        qreal scale;
+        qt_scaleForTransform(m, &scale);
+        m_curve_threshold = scale == 0 ? qreal(0.25) : (qreal(0.25) / scale);
     }
 
     void beginOutline(Qt::FillRule fillRule)
@@ -126,7 +130,6 @@ public:
 #endif
         m_valid = true;
         m_elements.reset();
-        m_elements_dev.reset();
         m_element_types.reset();
         m_points.reset();
         m_tags.reset();
@@ -161,15 +164,7 @@ public:
         m_element_types << QPainterPath::LineToElement;
     }
 
-    inline void curveTo(const QPointF &cp1, const QPointF &cp2, const QPointF &ep) {
-#ifdef QT_DEBUG_CONVERT
-        printf("QOutlineMapper::curveTo() (%f, %f)\n", ep.x(), ep.y());
-#endif
-        m_elements << cp1 << cp2 << ep;
-        m_element_types << QPainterPath::CurveToElement
-                        << QPainterPath::CurveToDataElement
-                        << QPainterPath::CurveToDataElement;
-    }
+    void curveTo(const QPointF &cp1, const QPointF &cp2, const QPointF &ep);
 
     inline void closeSubpath() {
         int element_count = m_elements.size();
@@ -209,14 +204,11 @@ public:
 public:
     QDataBuffer<QPainterPath::ElementType> m_element_types;
     QDataBuffer<QPointF> m_elements;
-    QDataBuffer<QPointF> m_elements_dev;
     QDataBuffer<QT_FT_Vector> m_points;
     QDataBuffer<char> m_tags;
     QDataBuffer<int> m_contours;
 
     QRect m_clip_rect;
-    QDataBuffer<QPointF> m_polygon_dev;
-
     QRectF controlPointRect; // only valid after endOutline()
 
     QT_FT_Outline m_outline;
@@ -235,6 +227,8 @@ public:
     qreal m_dx;
     qreal m_dy;
 
+    qreal m_curve_threshold;
+
     bool m_valid;
     bool m_in_clip_elements;