qpathclipper.cpp File Reference

#include "qpathclipper_p.h"
#include <private/qbezier_p.h>
#include <private/qdatabuffer_p.h>
#include <private/qnumeric_p.h>
#include <qmath.h>
#include <qdebug.h>

Go to the source code of this file.

Classes
struct	QCrossingEdge
struct	QIntersection
class	QIntersectionFinder
class	QKdPointFinder
class	QKdPointTree
struct	QKdPointTree::Node

Enumerations
enum	Edge

Functions
static void	add (QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
static void	addLineTo (QPainterPath &path, const QPointF &point)
static bool	bool_op (bool a, bool b, QPathClipper::Operation op)
static void	clear (QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
static int	commonEdge (const QWingedEdge &list, int a, int b)
static bool	comparePoints (const QPointF &a, const QPointF &b)
static qreal	component (const QPointF &point, unsigned int i)
static double	computeAngle (const QPointF &v)
static qreal	dot (const QPointF &a, const QPointF &b)
static QVector< QCrossingEdge >	findCrossings (const QWingedEdge &list, qreal y)
static bool	fuzzyCompare (qreal a, qreal b)
static bool	fuzzyIsNull (qreal d)
static bool	isLine (const QBezier &bezier)
static QPointF	midPoint (const QWingedEdge &list, int ei)
static void	normalize (double &x, double &y)
template<typename InputIterator >
InputIterator	qFuzzyFind (InputIterator first, InputIterator last, qreal val)
template<typename Iterator , typename Equality >
Iterator	qRemoveDuplicates (Iterator begin, Iterator end, Equality eq)
template<typename T >
void	qTraverseKdPointTree (QKdPointTree::Node &node, T &t, int depth=0)
static void	traverse (QWingedEdge &list, int edge, QPathEdge::Traversal traversal)

Enumeration Type Documentation

Edge

enum Edge

Definition at line 1949 of file qpathclipper.cpp.

{
    Left, Top, Right, Bottom
};

Function Documentation

add()

static void add ( QPainterPath &  path, const QWingedEdge &  list, int  edge, QPathEdge::Traversal  traversal  )

static

Definition at line 1329 of file qpathclipper.cpp.

Referenced by QPathClipper::handleCrossingEdges(), and QWingedEdge::toPath().

{
    QWingedEdge::TraversalStatus status;
    status.edge = edge;
    status.traversal = traversal;
    status.direction = QPathEdge::Forward;

    path.moveTo(*list.vertex(list.edge(edge)->first));

    do {
        const QPathEdge *ep = list.edge(status.edge);

        addLineTo(path, *list.vertex(ep->vertex(status.direction)));

        if (status.traversal == QPathEdge::LeftTraversal)
            ep->flag &= ~16;
        else
            ep->flag &= ~32;

        status = list.next(status);
    } while (status.edge != edge);
}

addLineTo()

static void addLineTo ( QPainterPath &  path, const QPointF &  point  )

static

Definition at line 1307 of file qpathclipper.cpp.

Referenced by add().

{
    const int elementCount = path.elementCount();
    if (elementCount >= 2) {
        const QPainterPath::Element &middle = path.elementAt(elementCount - 1);
        if (middle.type == QPainterPath::LineToElement) {
            const QPointF first = path.elementAt(elementCount - 2);
            const QPointF d1 = point - first;
            const QPointF d2 = middle - first;

            const QPointF p(-d1.y(), d1.x());

            if (qFuzzyIsNull(dot(p, d2))) {
                path.setElementPositionAt(elementCount - 1, point.x(), point.y());
                return;
            }
        }
    }

    path.lineTo(point);
}

bool_op()

static bool bool_op ( bool  a, bool  b, QPathClipper::Operation  op  )

static

Definition at line 1779 of file qpathclipper.cpp.

Referenced by QPathClipper::handleCrossingEdges().

{
    switch (op) {
    case QPathClipper::BoolAnd:
        return a && b;
    case QPathClipper::BoolOr: // fall-through
    case QPathClipper::Simplify:
        return a || b;
    case QPathClipper::BoolSub:
        return a && !b;
    default:
        Q_ASSERT(false);
        return false;
    }
}

clear()

static void clear ( QWingedEdge &  list, int  edge, QPathEdge::Traversal  traversal  )

static

Definition at line 1501 of file qpathclipper.cpp.

Referenced by QPathClipper::handleCrossingEdges().

{
    QWingedEdge::TraversalStatus status;
    status.edge = edge;
    status.traversal = traversal;
    status.direction = QPathEdge::Forward;

    do {
        if (status.traversal == QPathEdge::LeftTraversal)
            list.edge(status.edge)->flag |= 1;
        else
            list.edge(status.edge)->flag |= 2;

        status = list.next(status);
    } while (status.edge != edge);
}

commonEdge()

static int commonEdge ( const QWingedEdge &  list, int  a, int  b  )

static

Definition at line 1146 of file qpathclipper.cpp.

Referenced by QWingedEdge::addEdge().

{
    const QPathVertex *ap = list.vertex(a);
    Q_ASSERT(ap);

    const QPathVertex *bp = list.vertex(b);
    Q_ASSERT(bp);

    if (ap->edge < 0 || bp->edge < 0)
        return -1;

    QWingedEdge::TraversalStatus status;
    status.edge = ap->edge;
    status.direction = list.edge(status.edge)->directionTo(a);
    status.traversal = QPathEdge::RightTraversal;

    do {
        const QPathEdge *ep = list.edge(status.edge);

        if ((ep->first == a && ep->second == b)
            || (ep->first == b && ep->second == a))
            return status.edge;

        status = list.next(status);
        status.flip();
    } while (status.edge != ap->edge);

    return -1;
}

comparePoints()

static bool comparePoints ( const QPointF &  a, const QPointF &  b  )

inlinestatic

Definition at line 77 of file qpathclipper.cpp.

Referenced by QPathSegments::addPath(), QIntersectionFinder::hasIntersections(), isLine(), and QIntersectionFinder::linesIntersect().

{
    return fuzzyIsNull(a.x() - b.x())
           && fuzzyIsNull(a.y() - b.y());
}

component()

static qreal component ( const QPointF &  point, unsigned int  i  )

inlinestatic

Definition at line 670 of file qpathclipper.cpp.

Referenced by QDeclarativeLoaderPrivate::_q_sourceLoaded(), QKdPointTree::build(), QDeclarativeCompiler::buildPropertyObjectAssignment(), convertARGB32_to_RGBA4444(), QDeclarativeCompiledData::TypeReference::createInstance(), QDeclarativeCompiledData::TypeReference::createPropertyCache(), QmlJSDebugger::AbstractViewInspector::createQmlObject(), QDeclarativeEnginePrivate::createQmlObject(), QCoreGraphicsPaintEngine::drawTiledPixmap(), QDeclarativeViewPrivate::execute(), QDeclarativeLoaderPrivate::load(), QDeclarativeCompiledData::TypeReference::metaObject(), QDeclarativeBindingCompilerPrivate::parseName(), QDeclarativeCompiledData::TypeReference::propertyCache(), QDeclarativeGridViewPrivate::QDeclarativeGridViewPrivate(), QDeclarativeListViewPrivate::QDeclarativeListViewPrivate(), QAbstractTextDocumentLayout::registerHandler(), and QPatternist::XsdComplexType::~XsdComplexType().

{
    Q_ASSERT(i < 2);
    const qreal components[] = { point.x(), point.y() };
    return components[i];
}

computeAngle()

static double computeAngle ( const QPointF &  v )

static

Definition at line 1176 of file qpathclipper.cpp.

Referenced by QWingedEdge::addEdge().

{
#if 1
    if (v.x() == 0) {
        return v.y() <= 0 ? 0 : 64.;
    } else if (v.y() == 0) {
        return v.x() <= 0 ? 32. : 96.;
    }

    double vx = v.x();
    double vy = v.y();
    normalize(vx, vy);
    if (vy < 0) {
        if (vx < 0) { // 0 - 32
            return -32. * vx;
        } else { // 96 - 128
            return 128. - 32. * vx;
        }
    } else { // 32 - 96
        return 64. + 32. * vx;
    }
#else
    // doesn't seem to be robust enough
    return qAtan2(v.x(), v.y()) + Q_PI;
#endif
}

dot()

static qreal dot ( const QPointF &  a, const QPointF &  b  )

static

Definition at line 84 of file qpathclipper.cpp.

Referenced by addLineTo(), QPen::dashPattern(), QDeclarativeCompiler::evaluateEnum(), QIntersectionFinder::hasIntersections(), QScriptEngine::importExtension(), QIntersectionFinder::linesIntersect(), QQuaternion::nlerp(), QDashStroker::patternForStyle(), qSplitTableName(), QDeclarativeTypeData::resolveTypes(), shift(), QQuaternion::slerp(), QTransform::type(), and QX11PaintEngine::updatePen().

{
    return a.x() * b.x() + a.y() * b.y();
}

findCrossings()

static QVector<QCrossingEdge> findCrossings ( const QWingedEdge &  list, qreal  y  )

static

Definition at line 1821 of file qpathclipper.cpp.

Referenced by QPathClipper::handleCrossingEdges().

{
    QVector<QCrossingEdge> crossings;
    for (int i = 0; i < list.edgeCount(); ++i) {
        const QPathEdge *edge = list.edge(i);
        QPointF a = *list.vertex(edge->first);
        QPointF b = *list.vertex(edge->second);

        if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) {
            const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y());
            const QCrossingEdge edge = { i, intersection };
            crossings << edge;
        }
    }
    return crossings;
}

fuzzyCompare()

static bool fuzzyCompare ( qreal  a, qreal  b  )

static

Definition at line 1526 of file qpathclipper.cpp.

Referenced by QPathClipper::doClip().

{
    return qFuzzyCompare(a, b);
}

fuzzyIsNull()

static bool fuzzyIsNull ( qreal  d )

inlinestatic

The algorithm is as follows:

1. Find all intersections between the two paths (including self-intersections), and build a winged edge structure of non-intersecting parts.
2. While there are more unhandled edges:
   1. Pick a y-coordinate from an unhandled edge.
   2. Intersect the horizontal line at y-coordinate with all edges.
   3. Traverse intersections left to right deciding whether each subpath should be added or not.
   4. If the subpath should be added, traverse the winged-edge structure and add the edges to a separate winged edge structure.
   5. Mark all edges in subpaths crossing the horizontal line as handled.

(Optional) Simplify the resulting winged edge structure by merging shared edges.

1. Convert the resulting winged edge structure to a painter path.

Definition at line 69 of file qpathclipper.cpp.

Referenced by comparePoints(), and QKdPointFinder::operator()().

{
    if (sizeof(qreal) == sizeof(double))
        return qAbs(d) <= 1e-12;
    else
        return qAbs(d) <= 1e-5f;
}

isLine()

static bool isLine ( const QBezier &  bezier )

static

Definition at line 900 of file qpathclipper.cpp.

Referenced by QPathSegments::addPath().

{
    const bool equal_1_2 = comparePoints(bezier.pt1(), bezier.pt2());
    const bool equal_2_3 = comparePoints(bezier.pt2(), bezier.pt3());
    const bool equal_3_4 = comparePoints(bezier.pt3(), bezier.pt4());

    // point?
    if (equal_1_2 && equal_2_3 && equal_3_4)
        return true;

    if (comparePoints(bezier.pt1(), bezier.pt4()))
        return equal_1_2 || equal_3_4;

    return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4);
}

midPoint()

static QPointF midPoint ( const QWingedEdge &  list, int  ei  )

inlinestatic

Definition at line 1041 of file qpathclipper.cpp.

Referenced by QBezier::midTangent(), and QBezier::pt4().

{
    const QPathEdge *ep = list.edge(ei);
    Q_ASSERT(ep);

    const QPointF a = *list.vertex(ep->first);
    const QPointF b = *list.vertex(ep->second);
    return a + 0.5 * (b - a);
}

normalize()

static void normalize ( double &  x, double &  y  )

static

Definition at line 89 of file qpathclipper.cpp.

Referenced by ShaderEffectItem::bindGeometry(), computeAngle(), QXmlStreamReaderPrivate::parse(), QGridLayoutBox::QGridLayoutBox(), QRect::QRect(), and QDomNodePrivate::setNodeValue().

{
    double reciprocal = 1 / qSqrt(x * x + y * y);
    x *= reciprocal;
    y *= reciprocal;
}

qFuzzyFind()

template<typename InputIterator >

InputIterator qFuzzyFind	(	InputIterator	first,
		InputIterator	last,
		qreal	val
	)

Definition at line 1519 of file qpathclipper.cpp.

Referenced by QPathClipper::doClip().

{
    while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val)))
        ++first;
    return first;
}

qRemoveDuplicates()

template<typename Iterator , typename Equality >

Iterator qRemoveDuplicates	(	Iterator	begin,
		Iterator	end,
		Equality	eq
	)

Definition at line 1483 of file qpathclipper.cpp.

Referenced by QPathClipper::doClip().

{
    if (begin == end)
        return end;

    Iterator last = begin;
    ++begin;
    Iterator insert = begin;
    for (Iterator it = begin; it != end; ++it) {
        if (!eq(*it, *last)) {
            *insert++ = *it;
            last = it;
        }
    }

    return insert;
}

qTraverseKdPointTree()

template<typename T >

void qTraverseKdPointTree	(	QKdPointTree::Node &	node,
		T &	t,
		int	depth = 0
	)

Definition at line 656 of file qpathclipper.cpp.

{
    QKdPointTree::Traversal status = t(node, depth);

    const bool traverseRight = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseRight);
    const bool traverseLeft = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseLeft);

    if (traverseLeft && node.left)
        QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.left, t, depth + 1);

    if (traverseRight && node.right)
        QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.right, t, depth + 1);
}

traverse()

static void traverse ( QWingedEdge &  list, int  edge, QPathEdge::Traversal  traversal  )

static

Definition at line 1746 of file qpathclipper.cpp.

Referenced by QPathClipper::handleCrossingEdges().

{
    QWingedEdge::TraversalStatus status;
    status.edge = edge;
    status.traversal = traversal;
    status.direction = QPathEdge::Forward;

    do {
        int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2;

        QPathEdge *ep = list.edge(status.edge);

        ep->flag |= (flag | (flag << 4));

#ifdef QDEBUG_CLIPPER
        qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag;
#endif

        status = list.next(status);
    } while (status.edge != edge);
}