summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/gui/painting/painting.pri6
-rw-r--r--src/gui/painting/qpathsimplifier.cpp1673
-rw-r--r--src/gui/painting/qpathsimplifier_p.h68
-rw-r--r--src/gui/text/qdistancefield.cpp762
-rw-r--r--src/gui/text/qdistancefield_p.h85
-rw-r--r--src/gui/text/text.pri6
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-01 16:38:57 +0000