Add distance field generation functions from Scenegraph

Since we may use distance field text rendering in raster, these
functions need to be moved from declarative to QtGui.

Change-Id: I158bc3bae02b5590ae812f06ad7a78a5914bcb9e
Reviewed-by: Eskil Abrahamsen Blomfeldt <eskil.abrahamsen-blomfeldt@nokia.com>

6 files changed, 2596 insertions, 4 deletions

diff --git a/src/gui/painting/painting.pri b/src/gui/painting/painting.pri
index 61a25e9ac8..4cd2351b23 100644
--- a/src/gui/painting/painting.pri
+++ b/src/gui/painting/painting.pri
@@ -34,7 +34,8 @@ HEADERS += \
         painting/qtextureglyphcache_p.h \
         painting/qtransform.h \
         painting/qplatformbackingstore_qpa.h \
-        painting/qpaintbuffer_p.h
+        painting/qpaintbuffer_p.h \
+        painting/qpathsimplifier_p.h
 
 
 SOURCES += \
@@ -68,7 +69,8 @@ SOURCES += \
         painting/qtextureglyphcache.cpp \
         painting/qtransform.cpp \
         painting/qplatformbackingstore_qpa.cpp \
-        painting/qpaintbuffer.cpp
+        painting/qpaintbuffer.cpp \
+        painting/qpathsimplifier.cpp
 
         SOURCES +=                                      \
                 painting/qpaintengine_raster.cpp        \
diff --git a/src/gui/painting/qpathsimplifier.cpp b/src/gui/painting/qpathsimplifier.cpp
new file mode 100644
index 0000000000..fc3ce6361b
--- /dev/null
+++ b/src/gui/painting/qpathsimplifier.cpp
@@ -0,0 +1,1673 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtDeclarative module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qpathsimplifier_p.h"
+
+#include <QtCore/qvarlengtharray.h>
+#include <QtCore/qglobal.h>
+#include <QtCore/qpoint.h>
+#include <QtCore/qalgorithms.h>
+
+#include <math.h>
+
+#include <private/qopengl_p.h>
+#include <private/qrbtree_p.h>
+
+QT_BEGIN_NAMESPACE
+
+#define Q_FIXED_POINT_SCALE 256
+#define Q_TRIANGULATE_END_OF_POLYGON quint32(-1)
+
+
+namespace {
+
+//============================================================================//
+//                                   QPoint                                   //
+//============================================================================//
+
+inline bool operator < (const QPoint &a, const QPoint &b)
+{
+    return a.y() < b.y() || (a.y() == b.y() && a.x() < b.x());
+}
+
+inline bool operator > (const QPoint &a, const QPoint &b)
+{
+    return b < a;
+}
+
+inline bool operator <= (const QPoint &a, const QPoint &b)
+{
+    return !(a > b);
+}
+
+inline bool operator >= (const QPoint &a, const QPoint &b)
+{
+    return !(a < b);
+}
+
+inline int cross(const QPoint &u, const QPoint &v)
+{
+    return u.x() * v.y() - u.y() * v.x();
+}
+
+inline int dot(const QPoint &u, const QPoint &v)
+{
+    return u.x() * v.x() + u.y() * v.y();
+}
+
+//============================================================================//
+//                                  Fraction                                  //
+//============================================================================//
+
+// Fraction must be in the range [0, 1)
+struct Fraction
+{
+    bool isValid() const { return denominator != 0; }
+
+    // numerator and denominator must not have common denominators.
+    unsigned int numerator, denominator;
+};
+
+inline unsigned int gcd(unsigned int x, unsigned int y)
+{
+    while (y != 0) {
+        unsigned int z = y;
+        y = x % y;
+        x = z;
+    }
+    return x;
+}
+
+// Fraction must be in the range [0, 1)
+// Assume input is valid.
+Fraction fraction(unsigned int n, unsigned int d) {
+    Fraction result;
+    if (n == 0) {
+        result.numerator = 0;
+        result.denominator = 1;
+    } else {
+        unsigned int g = gcd(n, d);
+        result.numerator = n / g;
+        result.denominator = d / g;
+    }
+    return result;
+}
+
+//============================================================================//
+//                                  Rational                                  //
+//============================================================================//
+
+struct Rational
+{
+    bool isValid() const { return fraction.isValid(); }
+    int integer;
+    Fraction fraction;
+};
+
+//============================================================================//
+//                             IntersectionPoint                              //
+//============================================================================//
+
+struct IntersectionPoint
+{
+    bool isValid() const { return x.fraction.isValid() && y.fraction.isValid(); }
+    QPoint round() const;
+    bool isAccurate() const { return x.fraction.numerator == 0 && y.fraction.numerator == 0; }
+
+    Rational x; // 8:8 signed, 32/32
+    Rational y; // 8:8 signed, 32/32
+};
+
+QPoint IntersectionPoint::round() const
+{
+    QPoint result(x.integer, y.integer);
+    if (2 * x.fraction.numerator >= x.fraction.denominator)
+        ++result.rx();
+    if (2 * y.fraction.numerator >= y.fraction.denominator)
+        ++result.ry();
+    return result;
+}
+
+// Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the
+// line and zero if exactly on the line.
+// The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1',
+// which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order).
+inline int pointDistanceFromLine(const QPoint &p, const QPoint &v1, const QPoint &v2)
+{
+    return cross(v2 - v1, p - v1);
+}
+
+IntersectionPoint intersectionPoint(const QPoint &u1, const QPoint &u2,
+                                    const QPoint &v1, const QPoint &v2)
+{
+    IntersectionPoint result = {{0, {0, 0}}, {0, {0, 0}}};
+
+    QPoint u = u2 - u1;
+    QPoint v = v2 - v1;
+    int d1 = cross(u, v1 - u1);
+    int d2 = cross(u, v2 - u1);
+    int det = d2 - d1;
+    int d3 = cross(v, u1 - v1);
+    int d4 = d3 - det; //qCross(v, u2 - v1);
+
+    // Check that the math is correct.
+    Q_ASSERT(d4 == cross(v, u2 - v1));
+
+    // The intersection point can be expressed as:
+    // v1 - v * d1/det
+    // v2 - v * d2/det
+    // u1 + u * d3/det
+    // u2 + u * d4/det
+
+    // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap.
+    if (det == 0)
+        return result;
+
+    if (det < 0) {
+        det = -det;
+        d1 = -d1;
+        d2 = -d2;
+        d3 = -d3;
+        d4 = -d4;
+    }
+
+    // I'm only interested in lines intersecting at their interior, not at their end points.
+    // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'.
+    if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0)
+        return result;
+
+    // Calculate the intersection point as follows:
+    // v1 - v * d1/det | v1 <= v2 (component-wise)
+    // v2 - v * d2/det | v2 < v1 (component-wise)
+
+    // Assuming 16 bits per vector component.
+    if (v.x() >= 0) {
+        result.x.integer = v1.x() + int(qint64(-v.x()) * d1 / det);
+        result.x.fraction = fraction((unsigned int)(qint64(-v.x()) * d1 % det), (unsigned int)det);
+    } else {
+        result.x.integer = v2.x() + int(qint64(-v.x()) * d2 / det);
+        result.x.fraction = fraction((unsigned int)(qint64(-v.x()) * d2 % det), (unsigned int)det);
+    }
+
+    if (v.y() >= 0) {
+        result.y.integer = v1.y() + int(qint64(-v.y()) * d1 / det);
+        result.y.fraction = fraction((unsigned int)(qint64(-v.y()) * d1 % det), (unsigned int)det);
+    } else {
+        result.y.integer = v2.y() + int(qint64(-v.y()) * d2 / det);
+        result.y.fraction = fraction((unsigned int)(qint64(-v.y()) * d2 % det), (unsigned int)det);
+    }
+
+    Q_ASSERT(result.x.fraction.isValid());
+    Q_ASSERT(result.y.fraction.isValid());
+    return result;
+}
+
+//============================================================================//
+//                               PathSimplifier                               //
+//============================================================================//
+
+class PathSimplifier
+{
+public:
+    PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
+                   QDataBuffer<quint32> &indices, const QTransform &matrix);
+
+private:
+    struct Element;
+
+    class BoundingVolumeHierarchy
+    {
+    public:
+        struct Node
+        {
+            enum Type
+            {
+                Leaf,
+                Split
+            };
+            Type type;
+            QPoint minimum;
+            QPoint maximum;
+            union {
+                Element *element; // type == Leaf
+                Node *left; // type == Split
+            };
+            Node *right;
+        };
+
+        BoundingVolumeHierarchy();
+        ~BoundingVolumeHierarchy();
+        void allocate(int nodeCount);
+        void free();
+        Node *newNode();
+
+        Node *root;
+    private:
+        void freeNode(Node *n);
+
+        Node *nodeBlock;
+        int blockSize;
+        int firstFree;
+    };
+
+    struct Element
+    {
+        enum Degree
+        {
+            Line = 1,
+            Quadratic = 2,
+            Cubic = 3
+        };
+
+        quint32 &upperIndex() { return indices[pointingUp ? degree : 0]; }
+        quint32 &lowerIndex() { return indices[pointingUp ? 0 : degree]; }
+        quint32 upperIndex() const { return indices[pointingUp ? degree : 0]; }
+        quint32 lowerIndex() const { return indices[pointingUp ? 0 : degree]; }
+        void flip();
+
+        QPoint middle;
+        quint32 indices[4]; // index to points
+        Element *next, *previous; // used in connectElements()
+        int winding; // used in connectElements()
+        union {
+            QRBTree<Element *>::Node *edgeNode; // used in connectElements()
+            BoundingVolumeHierarchy::Node *bvhNode;
+        };
+        Degree degree : 8;
+        uint processed : 1; // initially false, true when the element has been checked for intersections.
+        uint pointingUp : 1; // used in connectElements()
+        uint originallyPointingUp : 1; // used in connectElements()
+    };
+
+    class ElementAllocator
+    {
+    public:
+        ElementAllocator();
+        ~ElementAllocator();
+        void allocate(int count);
+        Element *newElement();
+    private:
+        struct ElementBlock
+        {
+            ElementBlock *next;
+            int blockSize;
+            int firstFree;
+            Element elements[1];
+        } *blocks;
+    };
+
+    struct Event
+    {
+        enum Type { Upper, Lower };
+        bool operator < (const Event &other) const;
+
+        QPoint point;
+        Type type;
+        Element *element;
+    };
+
+    typedef QRBTree<Element *>::Node RBNode;
+    typedef BoundingVolumeHierarchy::Node BVHNode;
+
+    void initElements(const QVectorPath &path, const QTransform &matrix);
+    void removeIntersections();
+    void connectElements();
+    void fillIndices();
+    BVHNode *buildTree(Element **elements, int elementCount);
+    bool intersectNodes(QDataBuffer<Element *> &elements, BVHNode *elementNode, BVHNode *treeNode);
+    bool equalElements(const Element *e1, const Element *e2);
+    bool splitLineAt(QDataBuffer<Element *> &elements, BVHNode *node, quint32 pointIndex, bool processAgain);
+    void appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes, Element *element);
+    QPair<int, int> calculateSeparatingAxisRange(const QPoint &axis, Element *element);
+    void splitCurve(QDataBuffer<Element *> &elements, BVHNode *node);
+    bool setElementToQuadratic(Element *element, quint32 pointIndex1, const QPoint &ctrl, quint32 pointIndex2);
+    bool setElementToCubic(Element *element, quint32 pointIndex1, const QPoint &ctrl1, const QPoint &ctrl2, quint32 pointIndex2);
+    void setElementToCubicAndSimplify(Element *element, quint32 pointIndex1, const QPoint &ctrl1, const QPoint &ctrl2, quint32 pointIndex2);
+    RBNode *findElementLeftOf(const Element *element, const QPair<RBNode *, RBNode *> &bounds);
+    bool elementIsLeftOf(const Element *left, const Element *right);
+    QPair<RBNode *, RBNode *> outerBounds(const QPoint &point);
+    static bool flattenQuadratic(const QPoint &u, const QPoint &v, const QPoint &w);
+    static bool flattenCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q);
+    static bool splitQuadratic(const QPoint &u, const QPoint &v, const QPoint &w, QPoint *result);
+    static bool splitCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q, QPoint *result);
+    void subDivQuadratic(const QPoint &u, const QPoint &v, const QPoint &w);
+    void subDivCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q);
+    static void sortEvents(Event *events, int count);
+
+    ElementAllocator m_elementAllocator;
+    QDataBuffer<Element *> m_elements;
+    QDataBuffer<QPoint> *m_points;
+    BoundingVolumeHierarchy m_bvh;
+    QDataBuffer<quint32> *m_indices;
+    QRBTree<Element *> m_elementList;
+    uint m_hints;
+};
+
+inline PathSimplifier::BoundingVolumeHierarchy::BoundingVolumeHierarchy()
+    : root(0)
+    , nodeBlock(0)
+    , blockSize(0)
+    , firstFree(0)
+{
+}
+
+inline PathSimplifier::BoundingVolumeHierarchy::~BoundingVolumeHierarchy()
+{
+    free();
+}
+
+inline void PathSimplifier::BoundingVolumeHierarchy::allocate(int nodeCount)
+{
+    Q_ASSERT(nodeBlock == 0);
+    Q_ASSERT(firstFree == 0);
+    nodeBlock = new Node[blockSize = nodeCount];
+}
+
+inline void PathSimplifier::BoundingVolumeHierarchy::free()
+{
+    freeNode(root);
+    delete[] nodeBlock;
+    nodeBlock = 0;
+    firstFree = blockSize = 0;
+    root = 0;
+}
+
+inline PathSimplifier::BVHNode *PathSimplifier::BoundingVolumeHierarchy::newNode()
+{
+    if (firstFree < blockSize)
+        return &nodeBlock[firstFree++];
+    return new Node;
+}
+
+inline void PathSimplifier::BoundingVolumeHierarchy::freeNode(Node *n)
+{
+    if (!n)
+        return;
+    Q_ASSERT(n->type == Node::Split || n->type == Node::Leaf);
+    if (n->type == Node::Split) {
+        freeNode(n->left);
+        freeNode(n->right);
+    }
+    if (!(n >= nodeBlock && n < nodeBlock + blockSize))
+        delete n;
+}
+
+inline PathSimplifier::ElementAllocator::ElementAllocator()
+    : blocks(0)
+{
+}
+
+inline PathSimplifier::ElementAllocator::~ElementAllocator()
+{
+    while (blocks) {
+        ElementBlock *block = blocks;
+        blocks = blocks->next;
+        free(block);
+    }
+}
+
+inline void PathSimplifier::ElementAllocator::allocate(int count)
+{
+    Q_ASSERT(blocks == 0);
+    Q_ASSERT(count > 0);
+    blocks = (ElementBlock *)malloc(sizeof(ElementBlock) + (count - 1) * sizeof(Element));
+    blocks->blockSize = count;
+    blocks->next = 0;
+    blocks->firstFree = 0;
+}
+
+inline PathSimplifier::Element *PathSimplifier::ElementAllocator::newElement()
+{
+    Q_ASSERT(blocks);
+    if (blocks->firstFree < blocks->blockSize)
+        return &blocks->elements[blocks->firstFree++];
+    ElementBlock *oldBlock = blocks;
+    blocks = (ElementBlock *)malloc(sizeof(ElementBlock) + (oldBlock->blockSize - 1) * sizeof(Element));
+    blocks->blockSize = oldBlock->blockSize;
+    blocks->next = oldBlock;
+    blocks->firstFree = 0;
+    return &blocks->elements[blocks->firstFree++];
+}
+
+
+inline bool PathSimplifier::Event::operator < (const Event &other) const
+{
+    if (point == other.point)
+        return type < other.type;
+    return other.point < point;
+}
+
+inline void PathSimplifier::Element::flip()
+{
+    for (int i = 0; i < (degree + 1) >> 1; ++i) {
+        Q_ASSERT(degree >= Line && degree <= Cubic);
+        Q_ASSERT(i >= 0 && i < degree);
+        qSwap(indices[i], indices[degree - i]);
+    }
+    pointingUp = !pointingUp;
+    Q_ASSERT(next == 0 && previous == 0);
+}
+
+PathSimplifier::PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
+                               QDataBuffer<quint32> &indices, const QTransform &matrix)
+    : m_elements(0)
+    , m_points(&vertices)
+    , m_indices(&indices)
+{
+    m_points->reset();
+    m_indices->reset();
+    initElements(path, matrix);
+    if (!m_elements.isEmpty()) {
+        removeIntersections();
+        connectElements();
+        fillIndices();
+    }
+}
+
+void PathSimplifier::initElements(const QVectorPath &path, const QTransform &matrix)
+{
+    m_hints = path.hints();
+    int pathElementCount = path.elementCount();
+    if (pathElementCount == 0)
+        return;
+    m_elements.reserve(2 * pathElementCount);
+    m_elementAllocator.allocate(2 * pathElementCount);
+    m_points->reserve(2 * pathElementCount);
+    const QPainterPath::ElementType *e = path.elements();
+    const qreal *p = path.points();
+    if (e) {
+        qreal x, y;
+        quint32 moveToIndex = 0;
+        quint32 previousIndex = 0;
+        for (int i = 0; i < pathElementCount; ++i, ++e, p += 2) {
+            switch (*e) {
+            case QPainterPath::MoveToElement:
+                {
+                    if (!m_points->isEmpty()) {
+                        const QPoint &from = m_points->at(previousIndex);
+                        const QPoint &to = m_points->at(moveToIndex);
+                        if (from != to) {
+                            Element *element = m_elementAllocator.newElement();
+                            element->degree = Element::Line;
+                            element->indices[0] = previousIndex;
+                            element->indices[1] = moveToIndex;
+                            element->middle.rx() = (from.x() + to.x()) >> 1;
+                            element->middle.ry() = (from.y() + to.y()) >> 1;
+                            m_elements.add(element);
+                        }
+                    }
+                    previousIndex = moveToIndex = m_points->size();
+                    matrix.map(p[0], p[1], &x, &y);
+                    QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
+                    m_points->add(to);
+                }
+                break;
+            case QPainterPath::LineToElement:
+                Q_ASSERT(!m_points->isEmpty());
+                {
+                    matrix.map(p[0], p[1], &x, &y);
+                    QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
+                    const QPoint &from = m_points->last();
+                    if (to != from) {
+                        Element *element = m_elementAllocator.newElement();
+                        element->degree = Element::Line;
+                        element->indices[0] = previousIndex;
+                        element->indices[1] = quint32(m_points->size());
+                        element->middle.rx() = (from.x() + to.x()) >> 1;
+                        element->middle.ry() = (from.y() + to.y()) >> 1;
+                        m_elements.add(element);
+                        previousIndex = m_points->size();
+                        m_points->add(to);
+                    }
+                }
+                break;
+            case QPainterPath::CurveToElement:
+                Q_ASSERT(i + 2 < pathElementCount);
+                Q_ASSERT(!m_points->isEmpty());
+                Q_ASSERT(e[1] == QPainterPath::CurveToDataElement);
+                Q_ASSERT(e[2] == QPainterPath::CurveToDataElement);
+                {
+                    quint32 startPointIndex = previousIndex;
+                    matrix.map(p[4], p[5], &x, &y);
+                    QPoint end(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
+                    previousIndex = m_points->size();
+                    m_points->add(end);
+
+                    // See if this cubic bezier is really quadratic.
+                    qreal x1 = p[-2] + qreal(1.5) * (p[0] - p[-2]);
+                    qreal y1 = p[-1] + qreal(1.5) * (p[1] - p[-1]);
+                    qreal x2 = p[4] + qreal(1.5) * (p[2] - p[4]);
+                    qreal y2 = p[5] + qreal(1.5) * (p[3] - p[5]);
+
+                    Element *element = m_elementAllocator.newElement();
+                    if (qAbs(x1 - x2) < qreal(1e-3) && qAbs(y1 - y2) < qreal(1e-3)) {
+                        // The bezier curve is quadratic.
+                        matrix.map(x1, y1, &x, &y);
+                        QPoint ctrl(qRound(x * Q_FIXED_POINT_SCALE),
+                                    qRound(y * Q_FIXED_POINT_SCALE));
+                        setElementToQuadratic(element, startPointIndex, ctrl, previousIndex);
+                    } else {
+                        // The bezier curve is cubic.
+                        matrix.map(p[0], p[1], &x, &y);
+                        QPoint ctrl1(qRound(x * Q_FIXED_POINT_SCALE),
+                                     qRound(y * Q_FIXED_POINT_SCALE));
+                        matrix.map(p[2], p[3], &x, &y);
+                        QPoint ctrl2(qRound(x * Q_FIXED_POINT_SCALE),
+                                     qRound(y * Q_FIXED_POINT_SCALE));
+                        setElementToCubicAndSimplify(element, startPointIndex, ctrl1, ctrl2,
+                                                     previousIndex);
+                    }
+                    m_elements.add(element);
+                }
+                i += 2;
+                e += 2;
+                p += 4;
+
+                break;
+            default:
+                Q_ASSERT_X(0, "QSGPathSimplifier::initialize", "Unexpected element type.");
+                break;
+            }
+        }
+        if (!m_points->isEmpty()) {
+            const QPoint &from = m_points->at(previousIndex);
+            const QPoint &to = m_points->at(moveToIndex);
+            if (from != to) {
+                Element *element = m_elementAllocator.newElement();
+                element->degree = Element::Line;
+                element->indices[0] = previousIndex;
+                element->indices[1] = moveToIndex;
+                element->middle.rx() = (from.x() + to.x()) >> 1;
+                element->middle.ry() = (from.y() + to.y()) >> 1;
+                m_elements.add(element);
+            }
+        }
+    } else {
+        qreal x, y;
+
+        for (int i = 0; i < pathElementCount; ++i, p += 2) {
+            matrix.map(p[0], p[1], &x, &y);
+            QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE));
+            if (to != m_points->last())
+                m_points->add(to);
+        }
+
+        while (!m_points->isEmpty() && m_points->last() == m_points->first())
+            m_points->pop_back();
+
+        if (m_points->isEmpty())
+            return;
+
+        quint32 prev = quint32(m_points->size() - 1);
+        for (int i = 0; i < m_points->size(); ++i) {
+            QPoint &to = m_points->at(i);
+            QPoint &from = m_points->at(prev);
+            Element *element = m_elementAllocator.newElement();
+            element->degree = Element::Line;
+            element->indices[0] = prev;
+            element->indices[1] = quint32(i);
+            element->middle.rx() = (from.x() + to.x()) >> 1;
+            element->middle.ry() = (from.y() + to.y()) >> 1;
+            m_elements.add(element);
+            prev = i;
+        }
+    }
+
+    for (int i = 0; i < m_elements.size(); ++i)
+        m_elements.at(i)->processed = false;
+}
+
+void PathSimplifier::removeIntersections()
+{
+    Q_ASSERT(!m_elements.isEmpty());
+    QDataBuffer<Element *> elements(m_elements.size());
+    for (int i = 0; i < m_elements.size(); ++i)
+        elements.add(m_elements.at(i));
+    m_bvh.allocate(2 * m_elements.size());
+    m_bvh.root = buildTree(elements.data(), elements.size());
+
+    elements.reset();
+    for (int i = 0; i < m_elements.size(); ++i)
+        elements.add(m_elements.at(i));
+
+    while (!elements.isEmpty()) {
+        Element *element = elements.last();
+        elements.pop_back();
+        BVHNode *node = element->bvhNode;
+        Q_ASSERT(node->type == BVHNode::Leaf);
+        Q_ASSERT(node->element == element);
+        if (!element->processed) {
+            if (!intersectNodes(elements, node, m_bvh.root))
+                element->processed = true;
+        }
+    }
+
+    m_bvh.free(); // The bounding volume hierarchy is not needed anymore.
+}
+
+void PathSimplifier::connectElements()
+{
+    Q_ASSERT(!m_elements.isEmpty());
+    QDataBuffer<Event> events(m_elements.size() * 2);
+    for (int i = 0; i < m_elements.size(); ++i) {
+        Element *element = m_elements.at(i);
+        element->next = element->previous = 0;
+        element->winding = 0;
+        element->edgeNode = 0;
+        const QPoint &u = m_points->at(element->indices[0]);
+        const QPoint &v = m_points->at(element->indices[element->degree]);
+        if (u != v) {
+            element->pointingUp = element->originallyPointingUp = v < u;
+
+            Event event;
+            event.element = element;
+            event.point = u;
+            event.type = element->pointingUp ? Event::Lower : Event::Upper;
+            events.add(event);
+            event.point = v;
+            event.type = element->pointingUp ? Event::Upper : Event::Lower;
+            events.add(event);
+        }
+    }
+    QVarLengthArray<Element *, 8> orderedElements;
+    if (!events.isEmpty())
+        sortEvents(events.data(), events.size());
+    while (!events.isEmpty()) {
+        const Event *event = &events.last();
+        QPoint eventPoint = event->point;
+
+        // Find all elements passing through the event point.
+        QPair<RBNode *, RBNode *> bounds = outerBounds(eventPoint);
+
+        // Special case: single element above and single element below event point.
+        int eventCount = events.size();
+        if (event->type == Event::Lower && eventCount > 2) {
+            QPair<RBNode *, RBNode *> range;
+            range.first = bounds.first ? m_elementList.next(bounds.first)
+                                       : m_elementList.front(m_elementList.root);
+            range.second = bounds.second ? m_elementList.previous(bounds.second)
+                                         : m_elementList.back(m_elementList.root);
+
+            const Event *event2 = &events.at(eventCount - 2);
+            const Event *event3 = &events.at(eventCount - 3);
+            Q_ASSERT(event2->point == eventPoint); // There are always at least two events at a point.
+            if (range.first == range.second && event2->type == Event::Upper && event3->point != eventPoint) {
+                Element *element = event->element;
+                Element *element2 = event2->element;
+                element->edgeNode->data = event2->element;
+                element2->edgeNode = element->edgeNode;
+                element->edgeNode = 0;
+
+                events.pop_back();
+                events.pop_back();
+
+                if (element2->pointingUp != element->pointingUp)
+                    element2->flip();
+                element2->winding = element->winding;
+                int winding = element->winding;
+                if (element->originallyPointingUp)
+                    ++winding;
+                if (winding == 0 || winding == 1) {
+                    if (element->pointingUp) {
+                        element->previous = event2->element;
+                        element2->next = event->element;
+                    } else {
+                        element->next = event2->element;
+                        element2->previous = event->element;
+                    }
+                }
+                continue;
+            }
+        }
+        orderedElements.clear();
+
+        // First, find the ones above the event point.
+        if (m_elementList.root) {
+            RBNode *current = bounds.first ? m_elementList.next(bounds.first)
+                                           : m_elementList.front(m_elementList.root);
+            while (current != bounds.second) {
+                Element *element = current->data;
+                Q_ASSERT(element->edgeNode == current);
+                int winding = element->winding;
+                if (element->originallyPointingUp)
+                    ++winding;
+                const QPoint &lower = m_points->at(element->lowerIndex());
+                if (lower == eventPoint) {
+                    if (winding == 0 || winding == 1)
+                        orderedElements.append(current->data);
+                } else {
+                    // The element is passing through 'event.point'.
+                    Q_ASSERT(m_points->at(element->upperIndex()) != eventPoint);
+                    Q_ASSERT(element->degree == Element::Line);
+                    // Split the line.
+                    Element *eventElement = event->element;
+                    int indexIndex = (event->type == Event::Upper) == eventElement->pointingUp
+                                     ? eventElement->degree : 0;
+                    quint32 pointIndex = eventElement->indices[indexIndex];
+                    Q_ASSERT(eventPoint == m_points->at(pointIndex));
+
+                    Element *upperElement = m_elementAllocator.newElement();
+                    *upperElement = *element;
+                    upperElement->lowerIndex() = element->upperIndex() = pointIndex;
+                    upperElement->edgeNode = 0;
+                    element->next = element->previous = 0;
+                    if (upperElement->next)
+                        upperElement->next->previous = upperElement;
+                    else if (upperElement->previous)
+                        upperElement->previous->next = upperElement;
+                    if (element->pointingUp != element->originallyPointingUp)
+                        element->flip();
+                    if (winding == 0 || winding == 1)
+                        orderedElements.append(upperElement);
+                    m_elements.add(upperElement);
+                }
+                current = m_elementList.next(current);
+            }
+        }
+        while (!events.isEmpty() && events.last().point == eventPoint) {
+            event = &events.last();
+            if (event->type == Event::Upper) {
+                Q_ASSERT(event->point == m_points->at(event->element->upperIndex()));
+                RBNode *left = findElementLeftOf(event->element, bounds);
+                RBNode *node = m_elementList.newNode();
+                node->data = event->element;
+                Q_ASSERT(event->element->edgeNode == 0);
+                event->element->edgeNode = node;
+                m_elementList.attachAfter(left, node);
+            } else {
+                Q_ASSERT(event->type == Event::Lower);
+                Q_ASSERT(event->point == m_points->at(event->element->lowerIndex()));
+                Element *element = event->element;
+                Q_ASSERT(element->edgeNode);
+                m_elementList.deleteNode(element->edgeNode);
+                Q_ASSERT(element->edgeNode == 0);
+            }
+            events.pop_back();
+        }
+
+        if (m_elementList.root) {
+            RBNode *current = bounds.first ? m_elementList.next(bounds.first)
+                                           : m_elementList.front(m_elementList.root);
+            int winding = bounds.first ? bounds.first->data->winding : 0;
+
+            // Calculate winding numbers and flip elements if necessary.
+            while (current != bounds.second) {
+                Element *element = current->data;
+                Q_ASSERT(element->edgeNode == current);
+                int ccw = winding & 1;
+                Q_ASSERT(element->pointingUp == element->originallyPointingUp);
+                if (element->originallyPointingUp) {
+                    --winding;
+                } else {
+                    ++winding;
+                    ccw ^= 1;
+                }
+                element->winding = winding;
+                if (ccw == 0)
+                    element->flip();
+                current = m_elementList.next(current);
+            }
+
+            // Pick elements with correct winding number.
+            current = bounds.second ? m_elementList.previous(bounds.second)
+                                    : m_elementList.back(m_elementList.root);
+            while (current != bounds.first) {
+                Element *element = current->data;
+                Q_ASSERT(element->edgeNode == current);
+                Q_ASSERT(m_points->at(element->upperIndex()) == eventPoint);
+                int winding = element->winding;
+                if (element->originallyPointingUp)
+                    ++winding;
+                if (winding == 0 || winding == 1)
+                    orderedElements.append(current->data);
+                current = m_elementList.previous(current);
+            }
+        }
+
+        if (!orderedElements.isEmpty()) {
+            Q_ASSERT((orderedElements.size() & 1) == 0);
+            int i = 0;
+            Element *firstElement = orderedElements.at(0);
+            if (m_points->at(firstElement->indices[0]) != eventPoint) {
+                orderedElements.append(firstElement);
+                i = 1;
+            }
+            for (; i < orderedElements.size(); i += 2) {
+                Q_ASSERT(i + 1 < orderedElements.size());
+                Element *next = orderedElements.at(i);
+                Element *previous = orderedElements.at(i + 1);
+                Q_ASSERT(next->previous == 0);
+                Q_ASSERT(previous->next == 0);
+                next->previous = previous;
+                previous->next = next;
+            }
+        }
+    }
+#ifndef QT_NO_DEBUG
+    for (int i = 0; i < m_elements.size(); ++i) {
+        const Element *element = m_elements.at(i);
+        Q_ASSERT(element->next == 0 || element->next->previous == element);
+        Q_ASSERT(element->previous == 0 || element->previous->next == element);
+        Q_ASSERT((element->next == 0) == (element->previous == 0));
+    }
+#endif
+}
+
+void PathSimplifier::fillIndices()
+{
+    for (int i = 0; i < m_elements.size(); ++i)
+        m_elements.at(i)->processed = false;
+    for (int i = 0; i < m_elements.size(); ++i) {
+        Element *element = m_elements.at(i);
+        if (element->processed || element->next == 0)
+            continue;
+        do {
+            m_indices->add(element->indices[0]);
+            switch (element->degree) {
+            case Element::Quadratic:
+                {
+                    QPoint pts[] = {
+                        m_points->at(element->indices[0]),
+                        m_points->at(element->indices[1]),
+                        m_points->at(element->indices[2])
+                    };
+                    subDivQuadratic(pts[0], pts[1], pts[2]);
+                }
+                break;
+            case Element::Cubic:
+                {
+                    QPoint pts[] = {
+                        m_points->at(element->indices[0]),
+                        m_points->at(element->indices[1]),
+                        m_points->at(element->indices[2]),
+                        m_points->at(element->indices[3])
+                    };
+                    subDivCubic(pts[0], pts[1], pts[2], pts[3]);
+                }
+                break;
+            default:
+                break;
+            }
+            Q_ASSERT(element->next);
+            element->processed = true;
+            element = element->next;
+        } while (element != m_elements.at(i));
+        m_indices->add(Q_TRIANGULATE_END_OF_POLYGON);
+    }
+}
+
+PathSimplifier::BVHNode *PathSimplifier::buildTree(Element **elements, int elementCount)
+{
+    Q_ASSERT(elementCount > 0);
+    BVHNode *node = m_bvh.newNode();
+    if (elementCount == 1) {
+        Element *element = *elements;
+        element->bvhNode = node;
+        node->type = BVHNode::Leaf;
+        node->element = element;
+        node->minimum = node->maximum = m_points->at(element->indices[0]);
+        for (int i = 1; i <= element->degree; ++i) {
+            const QPoint &p = m_points->at(element->indices[i]);
+            node->minimum.rx() = qMin(node->minimum.x(), p.x());
+            node->minimum.ry() = qMin(node->minimum.y(), p.y());
+            node->maximum.rx() = qMax(node->maximum.x(), p.x());
+            node->maximum.ry() = qMax(node->maximum.y(), p.y());
+        }
+        return node;
+    }
+
+    node->type = BVHNode::Split;
+
+    QPoint minimum, maximum;
+    minimum = maximum = elements[0]->middle;
+
+    for (int i = 1; i < elementCount; ++i) {
+        const QPoint &p = elements[i]->middle;
+        minimum.rx() = qMin(minimum.x(), p.x());
+        minimum.ry() = qMin(minimum.y(), p.y());
+        maximum.rx() = qMax(maximum.x(), p.x());
+        maximum.ry() = qMax(maximum.y(), p.y());
+    }
+
+    int comp, pivot;
+    if (maximum.x() - minimum.x() > maximum.y() - minimum.y()) {
+        comp = 0;
+        pivot = (maximum.x() + minimum.x()) >> 1;
+    } else {
+        comp = 1;
+        pivot = (maximum.y() + minimum.y()) >> 1;
+    }
+
+    int lo = 0;
+    int hi = elementCount - 1;
+    while (lo < hi) {
+        while (lo < hi && (&elements[lo]->middle.rx())[comp] <= pivot)
+            ++lo;
+        while (lo < hi && (&elements[hi]->middle.rx())[comp] > pivot)
+            --hi;
+        if (lo < hi)
+            qSwap(elements[lo], elements[hi]);
+    }
+
+    if (lo == elementCount) {
+        // All points are the same.
+        Q_ASSERT(minimum.x() == maximum.x() && minimum.y() == maximum.y());
+        lo = elementCount >> 1;
+    }
+
+    node->left = buildTree(elements, lo);
+    node->right = buildTree(elements + lo, elementCount - lo);
+
+    const BVHNode *left = node->left;
+    const BVHNode *right = node->right;
+    node->minimum.rx() = qMin(left->minimum.x(), right->minimum.x());
+    node->minimum.ry() = qMin(left->minimum.y(), right->minimum.y());
+    node->maximum.rx() = qMax(left->maximum.x(), right->maximum.x());
+    node->maximum.ry() = qMax(left->maximum.y(), right->maximum.y());
+
+    return node;
+}
+
+bool PathSimplifier::intersectNodes(QDataBuffer<Element *> &elements, BVHNode *elementNode,
+                                    BVHNode *treeNode)
+{
+    if (elementNode->minimum.x() >= treeNode->maximum.x()
+        || elementNode->minimum.y() >= treeNode->maximum.y()
+        || elementNode->maximum.x() <= treeNode->minimum.x()
+        || elementNode->maximum.y() <= treeNode->minimum.y())
+    {
+        return false;
+    }
+
+    Q_ASSERT(elementNode->type == BVHNode::Leaf);
+    Element *element = elementNode->element;
+    Q_ASSERT(!element->processed);
+
+    if (treeNode->type == BVHNode::Leaf) {
+        Element *nodeElement = treeNode->element;
+        if (!nodeElement->processed)
+            return false;
+
+        if (treeNode->element == elementNode->element)
+            return false;
+
+        if (equalElements(treeNode->element, elementNode->element))
+            return false; // element doesn't split itself.
+
+        if (element->degree == Element::Line && nodeElement->degree == Element::Line) {
+            const QPoint &u1 = m_points->at(element->indices[0]);
+            const QPoint &u2 = m_points->at(element->indices[1]);
+            const QPoint &v1 = m_points->at(nodeElement->indices[0]);
+            const QPoint &v2 = m_points->at(nodeElement->indices[1]);
+            IntersectionPoint intersection = intersectionPoint(u1, u2, v1, v2);
+            if (!intersection.isValid())
+                return false;
+
+            Q_ASSERT(intersection.x.integer >= qMin(u1.x(), u2.x()));
+            Q_ASSERT(intersection.y.integer >= qMin(u1.y(), u2.y()));
+            Q_ASSERT(intersection.x.integer >= qMin(v1.x(), v2.x()));
+            Q_ASSERT(intersection.y.integer >= qMin(v1.y(), v2.y()));
+
+            Q_ASSERT(intersection.x.integer <= qMax(u1.x(), u2.x()));
+            Q_ASSERT(intersection.y.integer <= qMax(u1.y(), u2.y()));
+            Q_ASSERT(intersection.x.integer <= qMax(v1.x(), v2.x()));
+            Q_ASSERT(intersection.y.integer <= qMax(v1.y(), v2.y()));
+
+            m_points->add(intersection.round());
+            splitLineAt(elements, treeNode, m_points->size() - 1, !intersection.isAccurate());
+            return splitLineAt(elements, elementNode, m_points->size() - 1, false);
+        } else {
+            QVarLengthArray<QPoint, 12> axes;
+            appendSeparatingAxes(axes, elementNode->element);
+            appendSeparatingAxes(axes, treeNode->element);
+            for (int i = 0; i < axes.size(); ++i) {
+                QPair<int, int> range1 = calculateSeparatingAxisRange(axes.at(i), elementNode->element);
+                QPair<int, int> range2 = calculateSeparatingAxisRange(axes.at(i), treeNode->element);
+                if (range1.first >= range2.second || range1.second <= range2.first) {
+                    return false; // Separating axis found.
+                }
+            }
+            // Bounding areas overlap.
+            if (nodeElement->degree > Element::Line)
+                splitCurve(elements, treeNode);
+            if (element->degree > Element::Line) {
+                splitCurve(elements, elementNode);
+            } else {
+                // The element was not split, so it can be processed further.
+                if (intersectNodes(elements, elementNode, treeNode->left))
+                    return true;
+                if (intersectNodes(elements, elementNode, treeNode->right))
+                    return true;
+                return false;
+            }
+            return true;
+        }
+    } else {
+        if (intersectNodes(elements, elementNode, treeNode->left))
+            return true;
+        if (intersectNodes(elements, elementNode, treeNode->right))
+            return true;
+        return false;
+    }
+}
+
+bool PathSimplifier::equalElements(const Element *e1, const Element *e2)
+{
+    Q_ASSERT(e1 != e2);
+    if (e1->degree != e2->degree)
+        return false;
+
+    // Possibly equal and in the same direction.
+    bool equalSame = true;
+    for (int i = 0; i <= e1->degree; ++i)
+        equalSame &= m_points->at(e1->indices[i]) == m_points->at(e2->indices[i]);
+
+    // Possibly equal and in opposite directions.
+    bool equalOpposite = true;
+    for (int i = 0; i <= e1->degree; ++i)
+        equalOpposite &= m_points->at(e1->indices[e1->degree - i]) == m_points->at(e2->indices[i]);
+
+    return equalSame || equalOpposite;
+}
+
+bool PathSimplifier::splitLineAt(QDataBuffer<Element *> &elements, BVHNode *node,
+                                 quint32 pointIndex, bool processAgain)
+{
+    Q_ASSERT(node->type == BVHNode::Leaf);
+    Element *element = node->element;
+    Q_ASSERT(element->degree == Element::Line);
+    const QPoint &u = m_points->at(element->indices[0]);
+    const QPoint &v = m_points->at(element->indices[1]);
+    const QPoint &p = m_points->at(pointIndex);
+    if (u == p || v == p)
+        return false; // No split needed.
+
+    if (processAgain)
+        element->processed = false; // Needs to be processed again.
+
+    Element *first = node->element;
+    Element *second = m_elementAllocator.newElement();
+    *second = *first;
+    first->indices[1] = second->indices[0] = pointIndex;
+    first->middle.rx() = (u.x() + p.x()) >> 1;
+    first->middle.ry() = (u.y() + p.y()) >> 1;
+    second->middle.rx() = (v.x() + p.x()) >> 1;
+    second->middle.ry() = (v.y() + p.y()) >> 1;
+    m_elements.add(second);
+
+    BVHNode *left = m_bvh.newNode();
+    BVHNode *right = m_bvh.newNode();
+    left->type = right->type = BVHNode::Leaf;
+    left->element = first;
+    right->element = second;
+    left->minimum = right->minimum = node->minimum;
+    left->maximum = right->maximum = node->maximum;
+    if (u.x() < v.x())
+        left->maximum.rx() = right->minimum.rx() = p.x();
+    else
+        left->minimum.rx() = right->maximum.rx() = p.x();
+    if (u.y() < v.y())
+        left->maximum.ry() = right->minimum.ry() = p.y();
+    else
+        left->minimum.ry() = right->maximum.ry() = p.y();
+    left->element->bvhNode = left;
+    right->element->bvhNode = right;
+
+    node->type = BVHNode::Split;
+    node->left = left;
+    node->right = right;
+
+    if (!first->processed) {
+        elements.add(left->element);
+        elements.add(right->element);
+    }
+    return true;
+}
+
+void PathSimplifier::appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes, Element *element)
+{
+    switch (element->degree) {
+    case Element::Cubic:
+        {
+            const QPoint &u = m_points->at(element->indices[0]);
+            const QPoint &v = m_points->at(element->indices[1]);
+            const QPoint &w = m_points->at(element->indices[2]);
+            const QPoint &q = m_points->at(element->indices[3]);
+            QPoint ns[] = {
+                QPoint(u.y() - v.y(), v.x() - u.x()),
+                QPoint(v.y() - w.y(), w.x() - v.x()),
+                QPoint(w.y() - q.y(), q.x() - w.x()),
+                QPoint(q.y() - u.y(), u.x() - q.x()),
+                QPoint(u.y() - w.y(), w.x() - u.x()),
+                QPoint(v.y() - q.y(), q.x() - v.x())
+            };
+            for (int i = 0; i < 6; ++i) {
+                if (ns[i].x() || ns[i].y())
+                    axes.append(ns[i]);
+            }
+        }
+        break;
+    case Element::Quadratic:
+        {
+            const QPoint &u = m_points->at(element->indices[0]);
+            const QPoint &v = m_points->at(element->indices[1]);
+            const QPoint &w = m_points->at(element->indices[2]);
+            QPoint ns[] = {
+                QPoint(u.y() - v.y(), v.x() - u.x()),
+                QPoint(v.y() - w.y(), w.x() - v.x()),
+                QPoint(w.y() - u.y(), u.x() - w.x())
+            };
+            for (int i = 0; i < 3; ++i) {
+                if (ns[i].x() || ns[i].y())
+                    axes.append(ns[i]);
+            }
+        }
+        break;
+    case Element::Line:
+        {
+            const QPoint &u = m_points->at(element->indices[0]);
+            const QPoint &v = m_points->at(element->indices[1]);
+            QPoint n(u.y() - v.y(), v.x() - u.x());
+            if (n.x() || n.y())
+                axes.append(n);
+        }
+        break;
+    default:
+        Q_ASSERT_X(0, "QSGPathSimplifier::appendSeparatingAxes", "Unexpected element type.");
+        break;
+    }
+}
+
+QPair<int, int> PathSimplifier::calculateSeparatingAxisRange(const QPoint &axis, Element *element)
+{
+    QPair<int, int> range(0x7fffffff, -0x7fffffff);
+    for (int i = 0; i <= element->degree; ++i) {
+        const QPoint &p = m_points->at(element->indices[i]);
+        int dist = dot(axis, p);
+        range.first = qMin(range.first, dist);
+        range.second = qMax(range.second, dist);
+    }
+    return range;
+}
+
+void PathSimplifier::splitCurve(QDataBuffer<Element *> &elements, BVHNode *node)
+{
+    Q_ASSERT(node->type == BVHNode::Leaf);
+
+    Element *first = node->element;
+    Element *second = m_elementAllocator.newElement();
+    *second = *first;
+    m_elements.add(second);
+    Q_ASSERT(first->degree > Element::Line);
+
+    bool accurate = true;
+    const QPoint &u = m_points->at(first->indices[0]);
+    const QPoint &v = m_points->at(first->indices[1]);
+    const QPoint &w = m_points->at(first->indices[2]);
+
+    if (first->degree == Element::Quadratic) {
+        QPoint pts[3];
+        accurate = splitQuadratic(u, v, w, pts);
+        int pointIndex = m_points->size();
+        m_points->add(pts[1]);
+        accurate &= setElementToQuadratic(first, first->indices[0], pts[0], pointIndex);
+        accurate &= setElementToQuadratic(second, pointIndex, pts[2], second->indices[2]);
+    } else {
+        Q_ASSERT(first->degree == Element::Cubic);
+        const QPoint &q = m_points->at(first->indices[3]);
+        QPoint pts[5];
+        accurate = splitCubic(u, v, w, q, pts);
+        int pointIndex = m_points->size();
+        m_points->add(pts[2]);
+        accurate &= setElementToCubic(first, first->indices[0], pts[0], pts[1], pointIndex);
+        accurate &= setElementToCubic(second, pointIndex, pts[3], pts[4], second->indices[3]);
+    }
+
+    if (!accurate)
+        first->processed = second->processed = false; // Needs to be processed again.
+
+    BVHNode *left = m_bvh.newNode();
+    BVHNode *right = m_bvh.newNode();
+    left->type = right->type = BVHNode::Leaf;
+    left->element = first;
+    right->element = second;
+
+    left->minimum.rx() = left->minimum.ry() = right->minimum.rx() = right->minimum.ry() = INT_MAX;
+    left->maximum.rx() = left->maximum.ry() = right->maximum.rx() = right->maximum.ry() = INT_MIN;
+
+    for (int i = 0; i <= first->degree; ++i) {
+        QPoint &p = m_points->at(first->indices[i]);
+        left->minimum.rx() = qMin(left->minimum.x(), p.x());
+        left->minimum.ry() = qMin(left->minimum.y(), p.y());
+        left->maximum.rx() = qMax(left->maximum.x(), p.x());
+        left->maximum.ry() = qMax(left->maximum.y(), p.y());
+    }
+    for (int i = 0; i <= second->degree; ++i) {
+        QPoint &p = m_points->at(second->indices[i]);
+        right->minimum.rx() = qMin(right->minimum.x(), p.x());
+        right->minimum.ry() = qMin(right->minimum.y(), p.y());
+        right->maximum.rx() = qMax(right->maximum.x(), p.x());
+        right->maximum.ry() = qMax(right->maximum.y(), p.y());
+    }
+    left->element->bvhNode = left;
+    right->element->bvhNode = right;
+
+    node->type = BVHNode::Split;
+    node->left = left;
+    node->right = right;
+
+    if (!first->processed) {
+        elements.add(left->element);
+        elements.add(right->element);
+    }
+}
+
+bool PathSimplifier::setElementToQuadratic(Element *element, quint32 pointIndex1,
+                                           const QPoint &ctrl, quint32 pointIndex2)
+{
+    const QPoint &p1 = m_points->at(pointIndex1);
+    const QPoint &p2 = m_points->at(pointIndex2);
+    if (flattenQuadratic(p1, ctrl, p2)) {
+        // Insert line.
+        element->degree = Element::Line;
+        element->indices[0] = pointIndex1;
+        element->indices[1] = pointIndex2;
+        element->middle.rx() = (p1.x() + p2.x()) >> 1;
+        element->middle.ry() = (p1.y() + p2.y()) >> 1;
+        return false;
+    } else {
+        // Insert bezier.
+        element->degree = Element::Quadratic;
+        element->indices[0] = pointIndex1;
+        element->indices[1] = m_points->size();
+        element->indices[2] = pointIndex2;
+        element->middle.rx() = (p1.x() + ctrl.x() + p2.x()) / 3;
+        element->middle.ry() = (p1.y() + ctrl.y() + p2.y()) / 3;
+        m_points->add(ctrl);
+        return true;
+    }
+}
+
+bool PathSimplifier::setElementToCubic(Element *element, quint32 pointIndex1, const QPoint &v,
+                                       const QPoint &w, quint32 pointIndex2)
+{
+    const QPoint &u = m_points->at(pointIndex1);
+    const QPoint &q = m_points->at(pointIndex2);
+    if (flattenCubic(u, v, w, q)) {
+        // Insert line.
+        element->degree = Element::Line;
+        element->indices[0] = pointIndex1;
+        element->indices[1] = pointIndex2;
+        element->middle.rx() = (u.x() + q.x()) >> 1;
+        element->middle.ry() = (u.y() + q.y()) >> 1;
+        return false;
+    } else {
+        // Insert bezier.
+        element->degree = Element::Cubic;
+        element->indices[0] = pointIndex1;
+        element->indices[1] = m_points->size();
+        element->indices[2] = m_points->size() + 1;
+        element->indices[3] = pointIndex2;
+        element->middle.rx() = (u.x() + v.x() + w.x() + q.x()) >> 2;
+        element->middle.ry() = (u.y() + v.y() + w.y() + q.y()) >> 2;
+        m_points->add(v);
+        m_points->add(w);
+        return true;
+    }
+}
+
+void PathSimplifier::setElementToCubicAndSimplify(Element *element, quint32 pointIndex1,
+                                                  const QPoint &v, const QPoint &w,
+                                                  quint32 pointIndex2)
+{
+    const QPoint &u = m_points->at(pointIndex1);
+    const QPoint &q = m_points->at(pointIndex2);
+    if (flattenCubic(u, v, w, q)) {
+        // Insert line.
+        element->degree = Element::Line;
+        element->indices[0] = pointIndex1;
+        element->indices[1] = pointIndex2;
+        element->middle.rx() = (u.x() + q.x()) >> 1;
+        element->middle.ry() = (u.y() + q.y()) >> 1;
+        return;
+    }
+
+    bool intersecting = (u == q) || intersectionPoint(u, v, w, q).isValid();
+    if (!intersecting) {
+        // Insert bezier.
+        element->degree = Element::Cubic;
+        element->indices[0] = pointIndex1;
+        element->indices[1] = m_points->size();
+        element->indices[2] = m_points->size() + 1;
+        element->indices[3] = pointIndex2;
+        element->middle.rx() = (u.x() + v.x() + w.x() + q.x()) >> 2;
+        element->middle.ry() = (u.y() + v.y() + w.y() + q.y()) >> 2;
+        m_points->add(v);
+        m_points->add(w);
+        return;
+    }
+
+    QPoint pts[5];
+    splitCubic(u, v, w, q, pts);
+    int pointIndex = m_points->size();
+    m_points->add(pts[2]);
+    Element *element2 = m_elementAllocator.newElement();
+    m_elements.add(element2);
+    setElementToCubicAndSimplify(element, pointIndex1, pts[0], pts[1], pointIndex);
+    setElementToCubicAndSimplify(element2, pointIndex, pts[3], pts[4], pointIndex2);
+}
+
+PathSimplifier::RBNode *PathSimplifier::findElementLeftOf(const Element *element,
+                                                          const QPair<RBNode *, RBNode *> &bounds)
+{
+    if (!m_elementList.root)
+        return 0;
+    RBNode *current = bounds.first;
+    Q_ASSERT(!current || !elementIsLeftOf(element, current->data));
+    if (!current)
+        current = m_elementList.front(m_elementList.root);
+    Q_ASSERT(current);
+    RBNode *result = 0;
+    while (current != bounds.second && !elementIsLeftOf(element, current->data)) {
+        result = current;
+        current = m_elementList.next(current);
+    }
+    return result;
+}
+
+bool PathSimplifier::elementIsLeftOf(const Element *left, const Element *right)
+{
+    const QPoint &leftU = m_points->at(left->upperIndex());
+    const QPoint &leftL = m_points->at(left->lowerIndex());
+    const QPoint &rightU = m_points->at(right->upperIndex());
+    const QPoint &rightL = m_points->at(right->lowerIndex());
+    Q_ASSERT(leftL >= rightU && rightL >= leftU);
+    if (leftU.x() < qMin(rightL.x(), rightU.x()))
+        return true;
+    if (leftU.x() > qMax(rightL.x(), rightU.x()))
+        return false;
+    int d = pointDistanceFromLine(leftU, rightL, rightU);
+    // d < 0: left, d > 0: right, d == 0: on top
+    if (d == 0) {
+        d = pointDistanceFromLine(leftL, rightL, rightU);
+        if (d == 0) {
+            if (right->degree > Element::Line) {
+                d = pointDistanceFromLine(leftL, rightL, m_points->at(right->indices[1]));
+                if (d == 0)
+                    d = pointDistanceFromLine(leftL, rightL, m_points->at(right->indices[2]));
+            } else if (left->degree > Element::Line) {
+                d = pointDistanceFromLine(m_points->at(left->indices[1]), rightL, rightU);
+                if (d == 0)
+                    d = pointDistanceFromLine(m_points->at(left->indices[2]), rightL, rightU);
+            }
+        }
+    }
+    return d < 0;
+}
+
+QPair<PathSimplifier::RBNode *, PathSimplifier::RBNode *> PathSimplifier::outerBounds(const QPoint &point)
+{
+    RBNode *current = m_elementList.root;
+    QPair<RBNode *, RBNode *> result(0, 0);
+
+    while (current) {
+        const Element *element = current->data;
+        Q_ASSERT(element->edgeNode == current);
+        const QPoint &v1 = m_points->at(element->lowerIndex());
+        const QPoint &v2 = m_points->at(element->upperIndex());
+        Q_ASSERT(point >= v2 && point <= v1);
+        if (point == v1 || point == v2)
+            break;
+        int d = pointDistanceFromLine(point, v1, v2);
+        if (d == 0) {
+            if (element->degree == Element::Line)
+                break;
+            d = pointDistanceFromLine(point, v1, m_points->at(element->indices[1]));
+            if (d == 0)
+                d = pointDistanceFromLine(point, v1, m_points->at(element->indices[2]));
+            Q_ASSERT(d != 0);
+        }
+        if (d < 0) {
+            result.second = current;
+            current = current->left;
+        } else {
+            result.first = current;
+            current = current->right;
+        }
+    }
+
+    if (!current)
+        return result;
+
+    RBNode *mid = current;
+
+    current = mid->left;
+    while (current) {
+        const Element *element = current->data;
+        Q_ASSERT(element->edgeNode == current);
+        const QPoint &v1 = m_points->at(element->lowerIndex());
+        const QPoint &v2 = m_points->at(element->upperIndex());
+        Q_ASSERT(point >= v2 && point <= v1);
+        bool equal = (point == v1 || point == v2);
+        if (!equal) {
+            int d = pointDistanceFromLine(point, v1, v2);
+            Q_ASSERT(d >= 0);
+            equal = (d == 0 && element->degree == Element::Line);
+        }
+        if (equal) {
+            current = current->left;
+        } else {
+            result.first = current;
+            current = current->right;
+        }
+    }
+
+    current = mid->right;
+    while (current) {
+        const Element *element = current->data;
+        Q_ASSERT(element->edgeNode == current);
+        const QPoint &v1 = m_points->at(element->lowerIndex());
+        const QPoint &v2 = m_points->at(element->upperIndex());
+        Q_ASSERT(point >= v2 && point <= v1);
+        bool equal = (point == v1 || point == v2);
+        if (!equal) {
+            int d = pointDistanceFromLine(point, v1, v2);
+            Q_ASSERT(d <= 0);
+            equal = (d == 0 && element->degree == Element::Line);
+        }
+        if (equal) {
+            current = current->right;
+        } else {
+            result.second = current;
+            current = current->left;
+        }
+    }
+
+    return result;
+}
+
+inline bool PathSimplifier::flattenQuadratic(const QPoint &u, const QPoint &v, const QPoint &w)
+{
+    QPoint deltas[2] = { v - u, w - v };
+    int d = qAbs(cross(deltas[0], deltas[1]));
+    int l = qAbs(deltas[0].x()) + qAbs(deltas[0].y()) + qAbs(deltas[1].x()) + qAbs(deltas[1].y());
+    return d < (Q_FIXED_POINT_SCALE * Q_FIXED_POINT_SCALE * 3 / 2) || l <= Q_FIXED_POINT_SCALE * 2;
+}
+
+inline bool PathSimplifier::flattenCubic(const QPoint &u, const QPoint &v,
+                                         const QPoint &w, const QPoint &q)
+{
+    QPoint deltas[] = { v - u, w - v, q - w, q - u };
+    int d = qAbs(cross(deltas[0], deltas[1])) + qAbs(cross(deltas[1], deltas[2]))
+            + qAbs(cross(deltas[0], deltas[3])) + qAbs(cross(deltas[3], deltas[2]));
+    int l = qAbs(deltas[0].x()) + qAbs(deltas[0].y()) + qAbs(deltas[1].x()) + qAbs(deltas[1].y())
+            + qAbs(deltas[2].x()) + qAbs(deltas[2].y());
+    return d < (Q_FIXED_POINT_SCALE * Q_FIXED_POINT_SCALE * 3) || l <= Q_FIXED_POINT_SCALE * 2;
+}
+
+inline bool PathSimplifier::splitQuadratic(const QPoint &u, const QPoint &v,
+                                           const QPoint &w, QPoint *result)
+{
+    result[0] = u + v;
+    result[2] = v + w;
+    result[1] = result[0] + result[2];
+    bool accurate = ((result[0].x() | result[0].y() | result[2].x() | result[2].y()) & 1) == 0
+                    && ((result[1].x() | result[1].y()) & 3) == 0;
+    result[0].rx() >>= 1;
+    result[0].ry() >>= 1;
+    result[1].rx() >>= 2;
+    result[1].ry() >>= 2;
+    result[2].rx() >>= 1;
+    result[2].ry() >>= 1;
+    return accurate;
+}
+
+inline bool PathSimplifier::splitCubic(const QPoint &u, const QPoint &v,
+                                       const QPoint &w, const QPoint &q, QPoint *result)
+{
+    result[0] = u + v;
+    result[2] = v + w;
+    result[4] = w + q;
+    result[1] = result[0] + result[2];
+    result[3] = result[2] + result[4];
+    result[2] = result[1] + result[3];
+    bool accurate = ((result[0].x() | result[0].y() | result[4].x() | result[4].y()) & 1) == 0
+                    && ((result[1].x() | result[1].y() | result[3].x() | result[3].y()) & 3) == 0
+                    && ((result[2].x() | result[2].y()) & 7) == 0;
+    result[0].rx() >>= 1;
+    result[0].ry() >>= 1;
+    result[1].rx() >>= 2;
+    result[1].ry() >>= 2;
+    result[2].rx() >>= 3;
+    result[2].ry() >>= 3;
+    result[3].rx() >>= 2;
+    result[3].ry() >>= 2;
+    result[4].rx() >>= 1;
+    result[4].ry() >>= 1;
+    return accurate;
+}
+
+inline void PathSimplifier::subDivQuadratic(const QPoint &u, const QPoint &v, const QPoint &w)
+{
+    if (flattenQuadratic(u, v, w))
+        return;
+    QPoint pts[3];
+    splitQuadratic(u, v, w, pts);
+    subDivQuadratic(u, pts[0], pts[1]);
+    m_indices->add(m_points->size());
+    m_points->add(pts[1]);
+    subDivQuadratic(pts[1], pts[2], w);
+}
+
+inline void PathSimplifier::subDivCubic(const QPoint &u, const QPoint &v,
+                                        const QPoint &w, const QPoint &q)
+{
+    if (flattenCubic(u, v, w, q))
+        return;
+    QPoint pts[5];
+    splitCubic(u, v, w, q, pts);
+    subDivCubic(u, pts[0], pts[1], pts[2]);
+    m_indices->add(m_points->size());
+    m_points->add(pts[2]);
+    subDivCubic(pts[2], pts[3], pts[4], q);
+}
+
+void PathSimplifier::sortEvents(Event *events, int count)
+{
+    // Bucket sort + insertion sort.
+    Q_ASSERT(count > 0);
+    QDataBuffer<Event> buffer(count);
+    buffer.resize(count);
+    QScopedArrayPointer<int> bins(new int[count]);
+    int counts[0x101];
+    memset(counts, 0, sizeof(counts));
+
+    int minimum, maximum;
+    minimum = maximum = events[0].point.y();
+    for (int i = 1; i < count; ++i) {
+        minimum = qMin(minimum, events[i].point.y());
+        maximum = qMax(maximum, events[i].point.y());
+    }
+
+    for (int i = 0; i < count; ++i) {
+        bins[i] = ((maximum - events[i].point.y()) << 8) / (maximum - minimum + 1);
+        Q_ASSERT(bins[i] >= 0 && bins[i] < 0x100);
+        ++counts[bins[i]];
+    }
+
+    for (int i = 1; i < 0x100; ++i)
+        counts[i] += counts[i - 1];
+    counts[0x100] = counts[0xff];
+    Q_ASSERT(counts[0x100] == count);
+
+    for (int i = 0; i < count; ++i)
+        buffer.at(--counts[bins[i]]) = events[i];
+
+    int j = 0;
+    for (int i = 0; i < 0x100; ++i) {
+        for (; j < counts[i + 1]; ++j) {
+            int k = j;
+            while (k > 0 && (buffer.at(j) < events[k - 1])) {
+                events[k] = events[k - 1];
+                --k;
+            }
+            events[k] = buffer.at(j);
+        }
+    }
+}
+
+} // end anonymous namespace
+
+
+void qSimplifyPath(const QVectorPath &path, QDataBuffer<QPoint> &vertices,
+                   QDataBuffer<quint32> &indices, const QTransform &matrix)
+{
+    PathSimplifier(path, vertices, indices, matrix);
+}
+
+void qSimplifyPath(const QPainterPath &path, QDataBuffer<QPoint> &vertices,
+                   QDataBuffer<quint32> &indices, const QTransform &matrix)
+{
+    qSimplifyPath(qtVectorPathForPath(path), vertices, indices, matrix);
+}
+
+
+QT_END_NAMESPACE
diff --git a/src/gui/painting/qpathsimplifier_p.h b/src/gui/painting/qpathsimplifier_p.h
new file mode 100644
index 0000000000..9941bd21f2
--- /dev/null
+++ b/src/gui/painting/qpathsimplifier_p.h
@@ -0,0 +1,68 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtDeclarative module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QPATHSIMPLIFIER_P_H
+#define QPATHSIMPLIFIER_P_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <QtGui/qpainterpath.h>
+#include <QtGui/private/qdatabuffer_p.h>
+#include <QtGui/private/qvectorpath_p.h>
+
+QT_BEGIN_NAMESPACE
+
+// The returned vertices are in 8:8 fixed point format. The path is assumed to be in the range (-128, 128)x(-128, 128).
+void qSimplifyPath(const QVectorPath &path, QDataBuffer<QPoint> &vertices, QDataBuffer<quint32> &indices, const QTransform &matrix = QTransform());
+void qSimplifyPath(const QPainterPath &path, QDataBuffer<QPoint> &vertices, QDataBuffer<quint32> &indices, const QTransform &matrix = QTransform());
+
+QT_END_NAMESPACE
+
+#endif
diff --git a/src/gui/text/qdistancefield.cpp b/src/gui/text/qdistancefield.cpp
new file mode 100644
index 0000000000..fb06a26c8f
--- /dev/null
+++ b/src/gui/text/qdistancefield.cpp
@@ -0,0 +1,762 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtDeclarative module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qdistancefield_p.h"
+#include <qmath.h>
+#include <private/qdatabuffer_p.h>
+#include <private/qpathsimplifier_p.h>
+
+QT_BEGIN_NAMESPACE
+
+namespace
+{
+    enum FillHDir
+    {
+        LeftToRight,
+        RightToLeft
+    };
+
+    enum FillVDir
+    {
+        TopDown,
+        BottomUp
+    };
+
+    enum FillClip
+    {
+        NoClip,
+        Clip
+    };
+}
+
+template <FillClip clip, FillHDir dir>
+inline void fillLine(qint32 *, int, int, int, qint32, qint32)
+{
+}
+
+template <>
+inline void fillLine<Clip, LeftToRight>(qint32 *line, int width, int lx, int rx, qint32 d, qint32 dd)
+{
+    int fromX = qMax(0, lx >> 8);
+    int toX = qMin(width, rx >> 8);
+    int x = toX - fromX;
+    if (x <= 0)
+        return;
+    qint32 val = d + (((fromX << 8) + 0xff - lx) * dd >> 8);
+    line += fromX;
+    do {
+        *line = abs(val) < abs(*line) ? val : *line;
+        val += dd;
+        ++line;
+    } while (--x);
+}
+
+template <>
+inline void fillLine<Clip, RightToLeft>(qint32 *line, int width, int lx, int rx, qint32 d, qint32 dd)
+{
+    int fromX = qMax(0, lx >> 8);
+    int toX = qMin(width, rx >> 8);
+    int x = toX - fromX;
+    if (x <= 0)
+        return;
+    qint32 val = d + (((toX << 8) + 0xff - rx) * dd >> 8);
+    line += toX;
+    do {
+        val -= dd;
+        --line;
+        *line = abs(val) < abs(*line) ? val : *line;
+    } while (--x);
+}
+
+template <>
+inline void fillLine<NoClip, LeftToRight>(qint32 *line, int, int lx, int rx, qint32 d, qint32 dd)
+{
+    int fromX = lx >> 8;
+    int toX = rx >> 8;
+    int x = toX - fromX;
+    if (x <= 0)
+        return;
+    qint32 val = d + ((~lx & 0xff) * dd >> 8);
+    line += fromX;
+    do {
+        *line = abs(val) < abs(*line) ? val : *line;
+        val += dd;
+        ++line;
+    } while (--x);
+}
+
+template <>
+inline void fillLine<NoClip, RightToLeft>(qint32 *line, int, int lx, int rx, qint32 d, qint32 dd)
+{
+    int fromX = lx >> 8;
+    int toX = rx >> 8;
+    int x = toX - fromX;
+    if (x <= 0)
+        return;
+    qint32 val = d + ((~rx & 0xff) * dd >> 8);
+    line += toX;
+    do {
+        val -= dd;
+        --line;
+        *line = abs(val) < abs(*line) ? val : *line;
+    } while (--x);
+}
+
+template <FillClip clip, FillVDir vDir, FillHDir hDir>
+inline void fillLines(qint32 *bits, int width, int height, int upperY, int lowerY,
+                      int &lx, int ldx, int &rx, int rdx, qint32 &d, qint32 ddy, qint32 ddx)
+{
+    Q_UNUSED(height);
+    Q_ASSERT(upperY < lowerY);
+    int y = lowerY - upperY;
+    if (vDir == TopDown) {
+        qint32 *line = bits + upperY * width;
+        do {
+            fillLine<clip, hDir>(line, width, lx, rx, d, ddx);
+            lx += ldx;
+            d += ddy;
+            rx += rdx;
+            line += width;
+        } while (--y);
+    } else {
+        qint32 *line = bits + lowerY * width;
+        do {
+            lx -= ldx;
+            d -= ddy;
+            rx -= rdx;
+            line -= width;
+            fillLine<clip, hDir>(line, width, lx, rx, d, ddx);
+        } while (--y);
+    }
+}
+
+template <FillClip clip>
+void drawTriangle(qint32 *bits, int width, int height, const QPoint *center,
+                  const QPoint *v1, const QPoint *v2, qint32 value)
+{
+    const int y1 = clip == Clip ? qBound(0, v1->y() >> 8, height) : v1->y() >> 8;
+    const int y2 = clip == Clip ? qBound(0, v2->y() >> 8, height) : v2->y() >> 8;
+    const int yC = clip == Clip ? qBound(0, center->y() >> 8, height) : center->y() >> 8;
+
+    const int v1Frac = clip == Clip ? (y1 << 8) + 0xff - v1->y() : ~v2->y() & 0xff;
+    const int v2Frac = clip == Clip ? (y2 << 8) + 0xff - v2->y() : ~v1->y() & 0xff;
+    const int centerFrac = clip == Clip ? (yC << 8) + 0xff - center->y() : ~center->y() & 0xff;
+
+    int dx1 = 0, x1 = 0, dx2 = 0, x2 = 0;
+    qint32 dd1, d1, dd2, d2;
+    if (v1->y() != center->y()) {
+        dx1 = ((v1->x() - center->x()) << 8) / (v1->y() - center->y());
+        x1 = center->x() + centerFrac * (v1->x() - center->x()) / (v1->y() - center->y());
+    }
+    if (v2->y() != center->y()) {
+        dx2 = ((v2->x() - center->x()) << 8) / (v2->y() - center->y());
+        x2 = center->x() + centerFrac * (v2->x() - center->x()) / (v2->y() - center->y());
+    }
+
+    const qint32 div = (v2->x() - center->x()) * (v1->y() - center->y())
+                     - (v2->y() - center->y()) * (v1->x() - center->x());
+    const qint32 dd = div ? qint32((qint64(value * (v1->y() - v2->y())) << 8) / div) : 0;
+
+    if (y2 < yC) {
+        if (y1 < yC) {
+            // Center at the bottom.
+            if (y2 < y1) {
+                // y2 < y1 < yC
+                // Long right edge.
+                d1 = centerFrac * value / (v1->y() - center->y());
+                dd1 = ((value << 8) / (v1->y() - center->y()));
+                fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y1, yC, x1, dx1,
+                                                       x2, dx2, d1, dd1, dd);
+                dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
+                x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
+                fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, y1, x1, dx1,
+                                                       x2, dx2, value, 0, dd);
+            } else {
+                // y1 <= y2 < yC
+                // Long left edge.
+                d2 = centerFrac * value / (v2->y() - center->y());
+                dd2 = ((value << 8) / (v2->y() - center->y()));
+                fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y2, yC, x1, dx1,
+                                                       x2, dx2, d2, dd2, dd);
+                if (y1 != y2) {
+                    dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
+                    x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
+                    fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, y2, x1, dx1,
+                                                           x2, dx2, value, 0, dd);
+                }
+            }
+        } else {
+            // y2 < yC <= y1
+            // Center to the right.
+            int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
+            int xUp, xDn;
+            xUp = xDn = v2->x() + (clip == Clip ? (yC << 8) + 0xff - v2->y()
+                                                : (center->y() | 0xff) - v2->y())
+                        * (v1->x() - v2->x()) / (v1->y() - v2->y());
+            fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, yC, xUp, dx,
+                                                   x2, dx2, value, 0, dd);
+            if (yC != y1)
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y1, xDn, dx,
+                                                      x1, dx1, value, 0, dd);
+        }
+    } else {
+        if (y1 < yC) {
+            // y1 < yC <= y2
+            // Center to the left.
+            int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
+            int xUp, xDn;
+            xUp = xDn = v1->x() + (clip == Clip ? (yC << 8) + 0xff - v1->y()
+                                                : (center->y() | 0xff) - v1->y())
+                        * (v1->x() - v2->x()) / (v1->y() - v2->y());
+            fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, yC, x1, dx1,
+                                                   xUp, dx, value, 0, dd);
+            if (yC != y2)
+                fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y2, x2, dx2,
+                                                      xDn, dx, value, 0, dd);
+        } else {
+            // Center at the top.
+            if (y2 < y1) {
+                // yC <= y2 < y1
+                // Long right edge.
+                if (yC != y2) {
+                    d2 = centerFrac * value / (v2->y() - center->y());
+                    dd2 = ((value << 8) / (v2->y() - center->y()));
+                    fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y2, x2, dx2,
+                                                          x1, dx1, d2, dd2, dd);
+                }
+                dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
+                x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, y2, y1, x2, dx2,
+                                                      x1, dx1, value, 0, dd);
+            } else {
+                // Long left edge.
+                // yC <= y1 <= y2
+                if (yC != y1) {
+                    d1 = centerFrac * value / (v1->y() - center->y());
+                    dd1 = ((value << 8) / (v1->y() - center->y()));
+                    fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y1, x2, dx2,
+                                                          x1, dx1, d1, dd1, dd);
+                }
+                if (y1 != y2) {
+                    dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
+                    x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
+                    fillLines<clip, TopDown, RightToLeft>(bits, width, height, y1, y2, x2, dx2,
+                                                          x1, dx1, value, 0, dd);
+                }
+            }
+        }
+    }
+}
+
+template <FillClip clip>
+void drawRectangle(qint32 *bits, int width, int height,
+                   const QPoint *int1, const QPoint *center1, const QPoint *ext1,
+                   const QPoint *int2, const QPoint *center2, const QPoint *ext2,
+                   qint32 extValue)
+{
+    if (center1->y() > center2->y()) {
+        qSwap(center1, center2);
+        qSwap(int1, ext2);
+        qSwap(ext1, int2);
+        extValue = -extValue;
+    }
+
+    Q_ASSERT(ext1->x() - center1->x() == center1->x() - int1->x());
+    Q_ASSERT(ext1->y() - center1->y() == center1->y() - int1->y());
+    Q_ASSERT(ext2->x() - center2->x() == center2->x() - int2->x());
+    Q_ASSERT(ext2->y() - center2->y() == center2->y() - int2->y());
+
+    const int yc1 = clip == Clip ? qBound(0, center1->y() >> 8, height) : center1->y() >> 8;
+    const int yc2 = clip == Clip ? qBound(0, center2->y() >> 8, height) : center2->y() >> 8;
+    const int yi1 = clip == Clip ? qBound(0, int1->y() >> 8, height) : int1->y() >> 8;
+    const int yi2 = clip == Clip ? qBound(0, int2->y() >> 8, height) : int2->y() >> 8;
+    const int ye1 = clip == Clip ? qBound(0, ext1->y() >> 8, height) : ext1->y() >> 8;
+    const int ye2 = clip == Clip ? qBound(0, ext2->y() >> 8, height) : ext2->y() >> 8;
+
+    const int center1Frac = clip == Clip ? (yc1 << 8) + 0xff - center1->y() : ~center1->y() & 0xff;
+    const int center2Frac = clip == Clip ? (yc2 << 8) + 0xff - center2->y() : ~center2->y() & 0xff;
+    const int int1Frac = clip == Clip ? (yi1 << 8) + 0xff - int1->y() : ~int1->y() & 0xff;
+    const int ext1Frac = clip == Clip ? (ye1 << 8) + 0xff - ext1->y() : ~ext1->y() & 0xff;
+
+    int dxC = 0, dxE = 0; // cap slope, edge slope
+    qint32 ddC = 0;
+    if (ext1->y() != int1->y()) {
+        dxC = ((ext1->x() - int1->x()) << 8) / (ext1->y() - int1->y());
+        ddC = (extValue << 9) / (ext1->y() - int1->y());
+    }
+    if (ext1->y() != ext2->y())
+        dxE = ((ext1->x() - ext2->x()) << 8) / (ext1->y() - ext2->y());
+
+    const qint32 div = (ext1->x() - int1->x()) * (ext2->y() - int1->y())
+                     - (ext1->y() - int1->y()) * (ext2->x() - int1->x());
+    const qint32 dd = div ? qint32((qint64(extValue * (ext2->y() - ext1->y())) << 9) / div) : 0;
+
+    int xe1, xe2, xc1, xc2;
+    qint32 d;
+
+    qint32 intValue = -extValue;
+
+    if (center2->x() < center1->x()) {
+        // Leaning to the right. '/'
+        if (int1->y() < ext2->y()) {
+            // Mostly vertical.
+            Q_ASSERT(ext1->y() != ext2->y());
+            xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+            xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+            if (ye1 != yi1) {
+                xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+                xc2 += (ye1 - yc1) * dxC;
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, yi1, xe1, dxE,
+                                                      xc2, dxC, extValue, 0, dd);
+            }
+            if (yi1 != ye2)
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi1, ye2, xe1, dxE,
+                                                      xe2, dxE, extValue, 0, dd);
+            if (ye2 != yi2) {
+                xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+                xc1 += (ye2 - yc2) * dxC;
+                fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye2, yi2, xc1, dxC,
+                                                      xe2, dxE, intValue, 0, dd);
+            }
+        } else {
+            // Mostly horizontal.
+            Q_ASSERT(ext1->y() != int1->y());
+            xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+            xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+            xc1 += (ye2 - yc2) * dxC;
+            xc2 += (ye1 - yc1) * dxC;
+            if (ye1 != ye2) {
+                xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE,
+                                                      xc2, dxC, extValue, 0, dd);
+            }
+            if (ye2 != yi1) {
+                d = (clip == Clip ? (ye2 << 8) + 0xff - center2->y()
+                                  : (ext2->y() | 0xff) - center2->y())
+                    * 2 * extValue / (ext1->y() - int1->y());
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye2, yi1, xc1, dxC,
+                                                      xc2, dxC, d, ddC, dd);
+            }
+            if (yi1 != yi2) {
+                xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+                fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC,
+                                                      xe2, dxE, intValue, 0, dd);
+            }
+        }
+    } else {
+        // Leaning to the left. '\'
+        if (ext1->y() < int2->y()) {
+            // Mostly vertical.
+            Q_ASSERT(ext1->y() != ext2->y());
+            xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+            xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+            if (yi1 != ye1) {
+                xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+                xc1 += (yi1 - yc1) * dxC;
+                fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, ye1, xc1, dxC,
+                                                      xe2, dxE, intValue, 0, dd);
+            }
+            if (ye1 != yi2)
+                fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye1, yi2, xe1, dxE,
+                                                      xe2, dxE, intValue, 0, dd);
+            if (yi2 != ye2) {
+                xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+                xc2 += (yi2 - yc2) * dxC;
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi2, ye2, xe1, dxE,
+                                                      xc2, dxC, extValue, 0, dd);
+            }
+        } else {
+            // Mostly horizontal.
+            Q_ASSERT(ext1->y() != int1->y());
+            xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+            xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
+            xc1 += (yi1 - yc1) * dxC;
+            xc2 += (yi2 - yc2) * dxC;
+            if (yi1 != yi2) {
+                xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+                fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC,
+                                                      xe2, dxE, intValue, 0, dd);
+            }
+            if (yi2 != ye1) {
+                d = (clip == Clip ? (yi2 << 8) + 0xff - center2->y()
+                                  : (int2->y() | 0xff) - center2->y())
+                    * 2 * extValue / (ext1->y() - int1->y());
+                fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi2, ye1, xc1, dxC,
+                                                      xc2, dxC, d, ddC, dd);
+            }
+            if (ye1 != ye2) {
+                xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
+                fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE,
+                                                      xc2, dxC, extValue, 0, dd);
+            }
+        }
+    }
+}
+
+static void drawPolygons(qint32 *bits, int width, int height, const QPoint *vertices,
+                         const quint32 *indices, int indexCount, qint32 value)
+{
+    Q_ASSERT(indexCount != 0);
+    Q_ASSERT(height <= 128);
+    QVarLengthArray<quint8, 16> scans[128];
+    int first = 0;
+    for (int i = 1; i < indexCount; ++i) {
+        quint32 idx1 = indices[i - 1];
+        quint32 idx2 = indices[i];
+        Q_ASSERT(idx1 != quint32(-1));
+        if (idx2 == quint32(-1)) {
+            idx2 = indices[first];
+            Q_ASSERT(idx2 != quint32(-1));
+            first = ++i;
+        }
+        const QPoint *v1 = &vertices[idx1];
+        const QPoint *v2 = &vertices[idx2];
+        if (v2->y() < v1->y())
+            qSwap(v1, v2);
+        int fromY = qMax(0, v1->y() >> 8);
+        int toY = qMin(height, v2->y() >> 8);
+        if (fromY >= toY)
+            continue;
+        int dx = ((v2->x() - v1->x()) << 8) / (v2->y() - v1->y());
+        int x = v1->x() + ((fromY << 8) + 0xff - v1->y()) * (v2->x() - v1->x()) / (v2->y() - v1->y());
+        for (int y = fromY; y < toY; ++y) {
+            quint32 c = quint32(x >> 8);
+            if (c < quint32(width))
+                scans[y].append(quint8(c));
+            x += dx;
+        }
+    }
+    for (int i = 0; i < height; ++i) {
+        quint8 *scanline = scans[i].data();
+        int size = scans[i].size();
+        for (int j = 1; j < size; ++j) {
+            int k = j;
+            quint8 value = scanline[k];
+            for (; k != 0 && value < scanline[k - 1]; --k)
+                scanline[k] = scanline[k - 1];
+            scanline[k] = value;
+        }
+        qint32 *line = bits + i * width;
+        int j = 0;
+        for (; j + 1 < size; j += 2) {
+            for (quint8 x = scanline[j]; x < scanline[j + 1]; ++x)
+                line[x] = value;
+        }
+        if (j < size) {
+            for (int x = scanline[j]; x < width; ++x)
+                line[x] = value;
+        }
+    }
+}
+
+static QImage makeDistanceField(int imgSize, const QPainterPath &path, int dfScale, int offs)
+{
+    QImage image(imgSize, imgSize, QImage::Format_Indexed8);
+
+    if (path.isEmpty()) {
+        image.fill(0);
+        return image;
+    }
+
+    QTransform transform;
+    transform.translate(offs, offs);
+    transform.scale(qreal(1) / dfScale, qreal(1) / dfScale);
+
+    QDataBuffer<quint32> pathIndices(0);
+    QDataBuffer<QPoint> pathVertices(0);
+    qSimplifyPath(path, pathVertices, pathIndices, transform);
+
+    const qint32 interiorColor = -0x7f80; // 8:8 signed format, -127.5
+    const qint32 exteriorColor = 0x7f80; // 8:8 signed format, 127.5
+
+    QScopedArrayPointer<qint32> bits(new qint32[imgSize * imgSize]);
+    for (int i = 0; i < imgSize * imgSize; ++i)
+        bits[i] = exteriorColor;
+
+    const qreal angleStep = qreal(15 * 3.141592653589793238 / 180);
+    const QPoint rotation(qRound(cos(angleStep) * 0x4000),
+                          qRound(sin(angleStep) * 0x4000)); // 2:14 signed
+
+    const quint32 *indices = pathIndices.data();
+    QVarLengthArray<QPoint> normals;
+    QVarLengthArray<QPoint> vertices;
+    QVarLengthArray<bool> isConvex;
+    QVarLengthArray<bool> needsClipping;
+
+    drawPolygons(bits.data(), imgSize, imgSize, pathVertices.data(), indices, pathIndices.size(),
+                 interiorColor);
+
+    int index = 0;
+
+    while (index < pathIndices.size()) {
+        normals.clear();
+        vertices.clear();
+        needsClipping.clear();
+
+        // Find end of polygon.
+        int end = index;
+        while (indices[end] != quint32(-1))
+            ++end;
+
+        // Calculate vertex normals.
+        for (int next = index, prev = end - 1; next < end; prev = next++) {
+            quint32 fromVertexIndex = indices[prev];
+            quint32 toVertexIndex = indices[next];
+
+            const QPoint &from = pathVertices.at(fromVertexIndex);
+            const QPoint &to = pathVertices.at(toVertexIndex);
+
+            QPoint n(to.y() - from.y(), from.x() - to.x());
+            if (n.x() == 0 && n.y() == 0)
+                continue;
+            int scale = qRound((offs << 16) / sqrt(qreal(n.x() * n.x() + n.y() * n.y()))); // 8:16
+            n.rx() = n.x() * scale >> 8;
+            n.ry() = n.y() * scale >> 8;
+            normals.append(n);
+            QPoint v(to.x() + 0x7f, to.y() + 0x7f);
+            vertices.append(v);
+            needsClipping.append((to.x() < offs << 8) || (to.x() >= (imgSize - offs) << 8)
+                                 || (to.y() < offs << 8) || (to.y() >= (imgSize - offs) << 8));
+        }
+
+        isConvex.resize(normals.count());
+        for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) {
+            isConvex[prev] = normals.at(prev).x() * normals.at(next).y()
+                           - normals.at(prev).y() * normals.at(next).x() < 0;
+        }
+
+        // Draw quads.
+        for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) {
+            QPoint n = normals.at(next);
+            QPoint intPrev = vertices.at(prev);
+            QPoint extPrev = vertices.at(prev);
+            QPoint intNext = vertices.at(next);
+            QPoint extNext = vertices.at(next);
+
+            extPrev.rx() -= n.x();
+            extPrev.ry() -= n.y();
+            intPrev.rx() += n.x();
+            intPrev.ry() += n.y();
+            extNext.rx() -= n.x();
+            extNext.ry() -= n.y();
+            intNext.rx() += n.x();
+            intNext.ry() += n.y();
+
+            if (needsClipping[prev] || needsClipping[next]) {
+                drawRectangle<Clip>(bits.data(), imgSize, imgSize,
+                                    &intPrev, &vertices.at(prev), &extPrev,
+                                    &intNext, &vertices.at(next), &extNext,
+                                    exteriorColor);
+            } else {
+                drawRectangle<NoClip>(bits.data(), imgSize, imgSize,
+                                      &intPrev, &vertices.at(prev), &extPrev,
+                                      &intNext, &vertices.at(next), &extNext,
+                                      exteriorColor);
+            }
+
+            if (isConvex.at(prev)) {
+                QPoint p = extPrev;
+                if (needsClipping[prev]) {
+                    for (;;) {
+                        QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
+                                  (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
+                        n = rn;
+                        if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) {
+                            p.rx() = vertices.at(prev).x() - normals.at(prev).x();
+                            p.ry() = vertices.at(prev).y() - normals.at(prev).y();
+                            drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                               &extPrev, &p, exteriorColor);
+                            break;
+                        }
+
+                        p.rx() = vertices.at(prev).x() - n.x();
+                        p.ry() = vertices.at(prev).y() - n.y();
+                        drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                           &extPrev, &p, exteriorColor);
+                        extPrev = p;
+                    }
+                } else {
+                    for (;;) {
+                        QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
+                                  (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
+                        n = rn;
+                        if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) {
+                            p.rx() = vertices.at(prev).x() - normals.at(prev).x();
+                            p.ry() = vertices.at(prev).y() - normals.at(prev).y();
+                            drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                                 &extPrev, &p, exteriorColor);
+                            break;
+                        }
+
+                        p.rx() = vertices.at(prev).x() - n.x();
+                        p.ry() = vertices.at(prev).y() - n.y();
+                        drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                             &extPrev, &p, exteriorColor);
+                        extPrev = p;
+                    }
+                }
+            } else {
+                QPoint p = intPrev;
+                if (needsClipping[prev]) {
+                    for (;;) {
+                        QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
+                                  (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
+                        n = rn;
+                        if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) {
+                            p.rx() = vertices.at(prev).x() + normals.at(prev).x();
+                            p.ry() = vertices.at(prev).y() + normals.at(prev).y();
+                            drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                               &p, &intPrev, interiorColor);
+                            break;
+                        }
+
+                        p.rx() = vertices.at(prev).x() + n.x();
+                        p.ry() = vertices.at(prev).y() + n.y();
+                        drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                           &p, &intPrev, interiorColor);
+                        intPrev = p;
+                    }
+                } else {
+                    for (;;) {
+                        QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
+                                  (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
+                        n = rn;
+                        if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) {
+                            p.rx() = vertices.at(prev).x() + normals.at(prev).x();
+                            p.ry() = vertices.at(prev).y() + normals.at(prev).y();
+                            drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                                 &p, &intPrev, interiorColor);
+                            break;
+                        }
+
+                        p.rx() = vertices.at(prev).x() + n.x();
+                        p.ry() = vertices.at(prev).y() + n.y();
+                        drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
+                                             &p, &intPrev, interiorColor);
+                        intPrev = p;
+                    }
+                }
+            }
+        }
+
+        index = end + 1;
+    }
+
+    const qint32 *inLine = bits.data();
+    uchar *outLine = image.bits();
+    int padding = image.bytesPerLine() - image.width();
+    for (int y = 0; y < imgSize; ++y) {
+        for (int x = 0; x < imgSize; ++x, ++inLine, ++outLine)
+            *outLine = uchar((0x7f80 - *inLine) >> 8);
+        outLine += padding;
+    }
+
+    return image;
+}
+
+bool qt_fontHasNarrowOutlines(const QRawFont &f)
+{
+    QRawFont font = f;
+    font.setPixelSize(QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE);
+    Q_ASSERT(font.isValid());
+
+    QVector<quint32> glyphIndices = font.glyphIndexesForString(QLatin1String("O"));
+    if (glyphIndices.size() < 1)
+        return false;
+
+    QImage im = font.alphaMapForGlyph(glyphIndices.at(0), QRawFont::PixelAntialiasing);
+    if (im.isNull())
+        return false;
+
+    int minHThick = 999;
+    int minVThick = 999;
+
+    int thick = 0;
+    bool in = false;
+    int y = (im.height() + 1) / 2;
+    for (int x = 0; x < im.width(); ++x) {
+        int a = qAlpha(im.pixel(x, y));
+        if (a > 127) {
+            in = true;
+            ++thick;
+        } else if (in) {
+            in = false;
+            minHThick = qMin(minHThick, thick);
+            thick = 0;
+        }
+    }
+
+    thick = 0;
+    in = false;
+    int x = (im.width() + 1) / 2;
+    for (int y = 0; y < im.height(); ++y) {
+        int a = qAlpha(im.pixel(x, y));
+        if (a > 127) {
+            in = true;
+            ++thick;
+        } else if (in) {
+            in = false;
+            minVThick = qMin(minVThick, thick);
+            thick = 0;
+        }
+    }
+
+    return minHThick == 1 || minVThick == 1;
+}
+
+QImage qt_renderDistanceFieldGlyph(const QRawFont &font, glyph_t glyph, bool doubleResolution)
+{
+    QRawFont renderFont = font;
+    renderFont.setPixelSize(QT_DISTANCEFIELD_BASEFONTSIZE(doubleResolution) * QT_DISTANCEFIELD_SCALE(doubleResolution));
+
+    QPainterPath path = renderFont.pathForGlyph(glyph);
+    path.translate(-path.boundingRect().topLeft());
+    path.setFillRule(Qt::WindingFill);
+
+    QImage im = makeDistanceField(QT_DISTANCEFIELD_TILESIZE(doubleResolution),
+                                  path,
+                                  QT_DISTANCEFIELD_SCALE(doubleResolution),
+                                  QT_DISTANCEFIELD_RADIUS(doubleResolution) / QT_DISTANCEFIELD_SCALE(doubleResolution));
+    return im;
+}
+
+QT_END_NAMESPACE
+
diff --git a/src/gui/text/qdistancefield_p.h b/src/gui/text/qdistancefield_p.h
new file mode 100644
index 0000000000..486d291b78
--- /dev/null
+++ b/src/gui/text/qdistancefield_p.h
@@ -0,0 +1,85 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtDeclarative module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QDISTANCEFIELD_H
+#define QDISTANCEFIELD_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <qrawfont.h>
+#include <private/qfontengine_p.h>
+
+QT_BEGIN_NAMESPACE
+
+#define QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE 54
+#define QT_DISTANCEFIELD_DEFAULT_TILESIZE 64
+#define QT_DISTANCEFIELD_DEFAULT_SCALE 16
+#define QT_DISTANCEFIELD_DEFAULT_RADIUS 80
+#define QT_DISTANCEFIELD_HIGHGLYPHCOUNT 2000
+
+#define QT_DISTANCEFIELD_BASEFONTSIZE(NarrowOutlineFont) \
+    (NarrowOutlineFont ? QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE * 2 : \
+                         QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE)
+#define QT_DISTANCEFIELD_TILESIZE(NarrowOutlineFont) \
+    (NarrowOutlineFont ? QT_DISTANCEFIELD_DEFAULT_TILESIZE * 2 : \
+                         QT_DISTANCEFIELD_DEFAULT_TILESIZE)
+#define QT_DISTANCEFIELD_SCALE(NarrowOutlineFont) \
+    (NarrowOutlineFont ? QT_DISTANCEFIELD_DEFAULT_SCALE / 2 : \
+                         QT_DISTANCEFIELD_DEFAULT_SCALE)
+#define QT_DISTANCEFIELD_RADIUS(NarrowOutlineFont) \
+    (NarrowOutlineFont ? QT_DISTANCEFIELD_DEFAULT_RADIUS / 2 : \
+                         QT_DISTANCEFIELD_DEFAULT_RADIUS)
+
+bool Q_GUI_EXPORT qt_fontHasNarrowOutlines(const QRawFont &f);
+QImage Q_GUI_EXPORT qt_renderDistanceFieldGlyph(const QRawFont &font, glyph_t glyph, bool doubleResolution);
+
+QT_END_NAMESPACE
+
+#endif // QDISTANCEFIELD_H
diff --git a/src/gui/text/text.pri b/src/gui/text/text.pri
index 63a731f116..6587769712 100644
--- a/src/gui/text/text.pri
+++ b/src/gui/text/text.pri
@@ -42,7 +42,8 @@ HEADERS += \
         text/qrawfont_p.h \
     text/qglyphrun.h \
     text/qglyphrun_p.h \
-    text/qharfbuzz_copy_p.h
+    text/qharfbuzz_copy_p.h \
+    text/qdistancefield_p.h
 
 SOURCES += \
 	text/qfont.cpp \
@@ -73,7 +74,8 @@ SOURCES += \
 	text/qtextodfwriter.cpp \
 	text/qstatictext.cpp \
         text/qrawfont.cpp \
-    text/qglyphrun.cpp
+    text/qglyphrun.cpp \
+    text/qdistancefield.cpp
 
 contains(QT_CONFIG, directwrite) {
     LIBS_PRIVATE += -ldwrite