diff options
| -rw-r--r-- | src/quick/scenegraph/qsgadaptationlayer.cpp | 1 | ||||
| -rw-r--r-- | src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp | 1 | ||||
| -rw-r--r-- | src/quick/scenegraph/qsgpathsimplifier.cpp | 1673 | ||||
| -rw-r--r-- | src/quick/scenegraph/qsgpathsimplifier_p.h | 68 | ||||
| -rw-r--r-- | src/quick/scenegraph/scenegraph.pri | 2 | ||||
| -rw-r--r-- | src/quick/scenegraph/util/qsgdistancefieldutil.cpp | 714 | ||||
| -rw-r--r-- | src/quick/scenegraph/util/qsgdistancefieldutil_p.h | 24 |
7 files changed, 2 insertions, 2481 deletions
diff --git a/src/quick/scenegraph/qsgadaptationlayer.cpp b/src/quick/scenegraph/qsgadaptationlayer.cpp index 08e85ab8cb..2795d4d9a8 100644 --- a/src/quick/scenegraph/qsgadaptationlayer.cpp +++ b/src/quick/scenegraph/qsgadaptationlayer.cpp @@ -45,6 +45,7 @@ #include <QtQuick/private/qsgdistancefieldutil_p.h> #include <QtQuick/private/qsgdistancefieldglyphnode_p.h> #include <private/qrawfont_p.h> +#include <private/qdistancefield_p.h> #include <QtGui/qguiapplication.h> #include <qdir.h> diff --git a/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp b/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp index ef5b24d1fd..08f05075da 100644 --- a/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp +++ b/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp @@ -41,6 +41,7 @@ #include "qsgdefaultdistancefieldglyphcache_p.h" +#include <QtGui/private/qdistancefield_p.h> #include <QtQuick/private/qsgdistancefieldutil_p.h> #include <qopenglfunctions.h> diff --git a/src/quick/scenegraph/qsgpathsimplifier.cpp b/src/quick/scenegraph/qsgpathsimplifier.cpp deleted file mode 100644 index 21e5d473f0..0000000000 --- a/src/quick/scenegraph/qsgpathsimplifier.cpp +++ /dev/null @@ -1,1673 +0,0 @@ -/**************************************************************************** -** -** 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 "qsgpathsimplifier_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/quick/scenegraph/qsgpathsimplifier_p.h b/src/quick/scenegraph/qsgpathsimplifier_p.h deleted file mode 100644 index e60dc4fe37..0000000000 --- a/src/quick/scenegraph/qsgpathsimplifier_p.h +++ /dev/null @@ -1,68 +0,0 @@ -/**************************************************************************** -** -** 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 QSGPATHSIMPLIFIER_P_H -#define QSGPATHSIMPLIFIER_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/quick/scenegraph/scenegraph.pri b/src/quick/scenegraph/scenegraph.pri index dae4a3b8a8..f5fa18f87a 100644 --- a/src/quick/scenegraph/scenegraph.pri +++ b/src/quick/scenegraph/scenegraph.pri @@ -64,7 +64,6 @@ HEADERS += \ $$PWD/qsgdefaultimagenode_p.h \ $$PWD/qsgdefaultrectanglenode_p.h \ $$PWD/qsgflashnode_p.h \ - $$PWD/qsgpathsimplifier_p.h \ $$PWD/qsgshareddistancefieldglyphcache_p.h SOURCES += \ @@ -79,7 +78,6 @@ SOURCES += \ $$PWD/qsgdefaultimagenode.cpp \ $$PWD/qsgdefaultrectanglenode.cpp \ $$PWD/qsgflashnode.cpp \ - $$PWD/qsgpathsimplifier.cpp \ $$PWD/qsgshareddistancefieldglyphcache.cpp diff --git a/src/quick/scenegraph/util/qsgdistancefieldutil.cpp b/src/quick/scenegraph/util/qsgdistancefieldutil.cpp index be4673bdca..a8d73ed7d1 100644 --- a/src/quick/scenegraph/util/qsgdistancefieldutil.cpp +++ b/src/quick/scenegraph/util/qsgdistancefieldutil.cpp @@ -41,8 +41,6 @@ #include "qsgdistancefieldutil_p.h" -#include <qmath.h> -#include <private/qsgpathsimplifier_p.h> #include <private/qsgadaptationlayer_p.h> #include <QtGui/private/qopenglengineshadersource_p.h> #include <QtQuick/private/qsgcontext_p.h> @@ -64,718 +62,6 @@ static float defaultAntialiasingSpreadFunc(float glyphScale) return range / glyphScale; } -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; -} - QSGDistanceFieldGlyphCacheManager::QSGDistanceFieldGlyphCacheManager(QSGContext *c) : sgCtx(c) , m_threshold_func(defaultThresholdFunc) diff --git a/src/quick/scenegraph/util/qsgdistancefieldutil_p.h b/src/quick/scenegraph/util/qsgdistancefieldutil_p.h index 23da1d121f..bc1dbc2c72 100644 --- a/src/quick/scenegraph/util/qsgdistancefieldutil_p.h +++ b/src/quick/scenegraph/util/qsgdistancefieldutil_p.h @@ -48,33 +48,9 @@ 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) - - typedef float (*ThresholdFunc)(float glyphScale); typedef float (*AntialiasingSpreadFunc)(float glyphScale); -bool qt_fontHasNarrowOutlines(const QRawFont &f); -QImage qt_renderDistanceFieldGlyph(const QRawFont &font, glyph_t glyph, bool doubleResolution); - - class QOpenGLShaderProgram; class QSGDistanceFieldGlyphCache; class QSGContext; |