From a3566649d1c22df0639efde0987edfc0596e99d9 Mon Sep 17 00:00:00 2001 From: Jiang Jiang Date: Mon, 6 Feb 2012 14:07:35 +0100 Subject: Add distance field generation functions from Scenegraph Since we may use distance field text rendering in raster, these functions need to be moved from declarative to QtGui. Change-Id: I158bc3bae02b5590ae812f06ad7a78a5914bcb9e Reviewed-by: Eskil Abrahamsen Blomfeldt --- src/gui/painting/qpathsimplifier.cpp | 1673 ++++++++++++++++++++++++++++++++++ 1 file changed, 1673 insertions(+) create mode 100644 src/gui/painting/qpathsimplifier.cpp (limited to 'src/gui/painting/qpathsimplifier.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 +#include +#include +#include + +#include + +#include +#include + +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 &vertices, + QDataBuffer &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::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::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 &elements, BVHNode *elementNode, BVHNode *treeNode); + bool equalElements(const Element *e1, const Element *e2); + bool splitLineAt(QDataBuffer &elements, BVHNode *node, quint32 pointIndex, bool processAgain); + void appendSeparatingAxes(QVarLengthArray &axes, Element *element); + QPair calculateSeparatingAxisRange(const QPoint &axis, Element *element); + void splitCurve(QDataBuffer &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 &bounds); + bool elementIsLeftOf(const Element *left, const Element *right); + QPair 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 m_elements; + QDataBuffer *m_points; + BoundingVolumeHierarchy m_bvh; + QDataBuffer *m_indices; + QRBTree 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 &vertices, + QDataBuffer &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 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 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 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 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 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 &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 axes; + appendSeparatingAxes(axes, elementNode->element); + appendSeparatingAxes(axes, treeNode->element); + for (int i = 0; i < axes.size(); ++i) { + QPair range1 = calculateSeparatingAxisRange(axes.at(i), elementNode->element); + QPair 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 &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 &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 PathSimplifier::calculateSeparatingAxisRange(const QPoint &axis, Element *element) +{ + QPair 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 &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 &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::outerBounds(const QPoint &point) +{ + RBNode *current = m_elementList.root; + QPair 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 buffer(count); + buffer.resize(count); + QScopedArrayPointer 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 &vertices, + QDataBuffer &indices, const QTransform &matrix) +{ + PathSimplifier(path, vertices, indices, matrix); +} + +void qSimplifyPath(const QPainterPath &path, QDataBuffer &vertices, + QDataBuffer &indices, const QTransform &matrix) +{ + qSimplifyPath(qtVectorPathForPath(path), vertices, indices, matrix); +} + + +QT_END_NAMESPACE -- cgit v1.2.3