qtriangulator.cpp File Reference

#include "qtriangulator_p.h"
#include <QtGui/qdialog.h>
#include <QtGui/qevent.h>
#include <QtGui/qpainter.h>
#include <QtGui/qpainterpath.h>
#include <QtGui/private/qbezier_p.h>
#include <QtGui/private/qdatabuffer_p.h>
#include <QtCore/qbitarray.h>
#include <QtCore/qvarlengtharray.h>
#include <QtCore/qqueue.h>
#include <QtCore/qglobal.h>
#include <QtCore/qpoint.h>
#include <QtCore/qalgorithms.h>
#include <QtDebug>
#include <math.h>
#include <private/qgl_p.h>

Go to the source code of this file.

Classes
struct	QFraction
class	QInt64Set
struct	QIntersectionPoint
class	QMaxHeap< T >
struct	QPodPoint
struct	QRBTree< T >
struct	QRBTree< T >::Node
class	QRingBuffer< T >
class	QTriangulator< T >
class	QTriangulator< T >::ComplexToSimple
class	QTriangulator< T >::ComplexToSimple::CompareEdges
struct	QTriangulator< T >::ComplexToSimple::Edge
struct	QTriangulator< T >::ComplexToSimple::Event
struct	QTriangulator< T >::ComplexToSimple::Intersection
struct	QTriangulator< T >::ComplexToSimple::Split
class	QTriangulator< T >::MonotoneToTriangles
class	QTriangulator< T >::SimpleToMonotone
class	QTriangulator< T >::SimpleToMonotone::CompareVertices
struct	QTriangulator< T >::SimpleToMonotone::Edge
struct	QVertexSet< T >

Macros
#define	Q_FIXED_POINT_SCALE   32

Typedefs
typedef QRBTree< int >::Node *	QRBTreeIntNodePointer

Functions
static int	compare (quint64 a, quint64 b)
static int	comparePoints (const QPodPoint &u, const QPodPoint &v)
static quint64	gcd (quint64 x, quint64 y)
static int	primeForCount (int count)
static int	primeForNumBits (int numBits)
static int	qCompareFractions (quint64 a, quint64 b, quint64 c, quint64 d)
static qint64	qCross (const QPodPoint &u, const QPodPoint &v)
static qint64	qDot (const QPodPoint &u, const QPodPoint &v)
static QFraction	qFraction (quint64 n, quint64 d)
static QIntersectionPoint	qIntersectionPoint (const QPodPoint &point)
static QIntersectionPoint	qIntersectionPoint (int x, int y)
static QIntersectionPoint	qIntersectionPoint (const QPodPoint &u1, const QPodPoint &u2, const QPodPoint &v1, const QPodPoint &v2)
static qint64	qPointDistanceFromLine (const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
static bool	qPointIsLeftOfLine (const QPodPoint &p, const QPodPoint &v1, const QPodPoint &v2)
QPolylineSet	qPolyline (const QVectorPath &path, const QTransform &matrix, qreal lod)
QPolylineSet	qPolyline (const QPainterPath &path, const QTransform &matrix, qreal lod)
QTriangleSet	qTriangulate (const qreal *polygon, int count, uint hint, const QTransform &matrix)
QTriangleSet	qTriangulate (const QVectorPath &path, const QTransform &matrix, qreal lod)
QTriangleSet	qTriangulate (const QPainterPath &path, const QTransform &matrix, qreal lod)
template<class T , class LessThan >
static void	sort (T *array, int count, LessThan lessThan)
template<class T >
static void	sort (T *array, int count)

Variables
static const uchar	prime_deltas []

Macro Definition Documentation

Q_FIXED_POINT_SCALE

#define Q_FIXED_POINT_SCALE   32

Definition at line 66 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::initialize(), QTriangulator< T >::polyline(), and QTriangulator< T >::triangulate().

Typedef Documentation

QRBTreeIntNodePointer

typedef QRBTree<int>::Node* QRBTreeIntNodePointer

Definition at line 1313 of file qtriangulator.cpp.

Function Documentation

compare()

static int compare ( quint64  a, quint64  b  )

inlinestatic

Definition at line 233 of file qtriangulator.cpp.

Referenced by qCompareFractions().

{
    return (a > b) - (a < b);
}

comparePoints()

static int comparePoints ( const QPodPoint &  u, const QPodPoint &  v  )

static

Definition at line 349 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::CompareEdges::operator()().

{
    if (u.y < v.y)
        return -1;
    if (u.y > v.y)
        return 1;
    if (u.x < v.x)
        return -1;
    if (u.x > v.x)
        return 1;
    return 0;
}

gcd()

static quint64 gcd ( quint64  x, quint64  y  )

inlinestatic

Definition at line 223 of file qtriangulator.cpp.

Referenced by qFraction().

{
    while (y != 0) {
        quint64 z = y;
        y = x % y;
        x = z;
    }
    return x;
}

primeForCount()

static int primeForCount ( int  count )

inlinestatic

Definition at line 1121 of file qtriangulator.cpp.

Referenced by QInt64Set::insert(), and QInt64Set::QInt64Set().

{
    int low = 0;
    int high = 32;
    for (int i = 0; i < 5; ++i) {
        int mid = (high + low) / 2;
        if (count >= 1 << mid)
            low = mid;
        else
            high = mid;
    }
    return primeForNumBits(high);
}

primeForNumBits()

static int primeForNumBits ( int  numBits )

inlinestatic

Definition at line 1116 of file qtriangulator.cpp.

Referenced by primeForCount().

{
    return (1 << numBits) + prime_deltas[numBits];
}

qCompareFractions()

static int qCompareFractions ( quint64  a, quint64  b, quint64  c, quint64  d  )

static

Definition at line 241 of file qtriangulator.cpp.

Referenced by QFraction::operator<().

{
    const quint64 LIMIT = Q_UINT64_C(0x100000000);
    for (;;) {
        // If the products 'ad' and 'bc' fit into 64 bits, they can be directly compared.
        if (b < LIMIT && d < LIMIT)
            return compare(a * d, b * c);

        if (a == 0 || c == 0)
            return compare(a, c);

        // a/b < c/d  <=>  d/c < b/a
        quint64 b_div_a = b / a;
        quint64 d_div_c = d / c;
        if (b_div_a != d_div_c)
            return compare(d_div_c, b_div_a);

        // floor(d/c) == floor(b/a)
        // frac(d/c) < frac(b/a) ?
        // frac(x/y) = (x%y)/y
        d -= d_div_c * c; //d %= c;
        b -= b_div_a * a; //b %= a;
        qSwap(a, d);
        qSwap(b, c);
    }
}

qCross()

static qint64 qCross ( const QPodPoint &  u, const QPodPoint &  v  )

inlinestatic

Definition at line 321 of file qtriangulator.cpp.

Referenced by qIntersectionPoint(), qPointDistanceFromLine(), and QTriangulator< T >::ComplexToSimple::sortEdgeList().

{
    return qint64(u.x) * qint64(v.y) - qint64(u.y) * qint64(v.x);
}

qDot()

static qint64 qDot ( const QPodPoint &  u, const QPodPoint &  v  )

inlinestatic

Definition at line 326 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::Event::operator<().

{
    return qint64(u.x) * qint64(v.x) + qint64(u.y) * qint64(v.y);
}

qFraction()

static QFraction qFraction ( quint64  n, quint64  d  )

static

Definition at line 270 of file qtriangulator.cpp.

Referenced by QIntersectionPoint::isOnLine(), and qIntersectionPoint().

                                                 {
    QFraction result;
    if (n == 0) {
        result.numerator = 0;
        result.denominator = 1;
    } else {
        quint64 g = gcd(n, d);
        result.numerator = n / g;
        result.denominator = d / g;
    }
    return result;
}

qIntersectionPoint() [1/3]

static QIntersectionPoint qIntersectionPoint ( const QPodPoint &  point )

inlinestatic

Definition at line 384 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::calculateIntersection(), QTriangulator< T >::ComplexToSimple::calculateIntersections(), QTriangulator< T >::ComplexToSimple::removeUnwantedEdgesAndConnect(), and QTriangulator< T >::ComplexToSimple::sortEdgeList().

{
    // upperLeft = point, xOffset = 0/1, yOffset = 0/1.
    QIntersectionPoint p = {{point.x, point.y}, {0, 1}, {0, 1}};
    return p;
}

qIntersectionPoint() [2/3]

static QIntersectionPoint qIntersectionPoint ( int  x, int  y  )

inlinestatic

Definition at line 391 of file qtriangulator.cpp.

{
    // upperLeft = (x, y), xOffset = 0/1, yOffset = 0/1.
    QIntersectionPoint p = {{x, y}, {0, 1}, {0, 1}};
    return p;
}

qIntersectionPoint() [3/3]

static QIntersectionPoint qIntersectionPoint ( const QPodPoint &  u1, const QPodPoint &  u2, const QPodPoint &  v1, const QPodPoint &  v2  )

static

Definition at line 398 of file qtriangulator.cpp.

{
    QIntersectionPoint result = {{0, 0}, {0, 0}, {0, 0}};

    QPodPoint u = u2 - u1;
    QPodPoint v = v2 - v1;
    qint64 d1 = qCross(u, v1 - u1);
    qint64 d2 = qCross(u, v2 - u1);
    qint64 det = d2 - d1;
    qint64 d3 = qCross(v, u1 - v1);
    qint64 d4 = d3 - det; //qCross(v, u2 - v1);

    // Check that the math is correct.
    Q_ASSERT(d4 == qCross(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 21 bits per vector component.
    // TODO: Make code path for 31 bits per vector component.
    if (v.x >= 0) {
        result.upperLeft.x = v1.x + (-v.x * d1) / det;
        result.xOffset = qFraction(quint64(-v.x * d1) % quint64(det), quint64(det));
    } else {
        result.upperLeft.x = v2.x + (-v.x * d2) / det;
        result.xOffset = qFraction(quint64(-v.x * d2) % quint64(det), quint64(det));
    }

    if (v.y >= 0) {
        result.upperLeft.y = v1.y + (-v.y * d1) / det;
        result.yOffset = qFraction(quint64(-v.y * d1) % quint64(det), quint64(det));
    } else {
        result.upperLeft.y = v2.y + (-v.y * d2) / det;
        result.yOffset = qFraction(quint64(-v.y * d2) % quint64(det), quint64(det));
    }

    Q_ASSERT(result.xOffset.isValid());
    Q_ASSERT(result.yOffset.isValid());
    return result;
}

qPointDistanceFromLine()

static qint64 qPointDistanceFromLine ( const QPodPoint &  p, const QPodPoint &  v1, const QPodPoint &  v2  )

inlinestatic

Definition at line 335 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::ComplexToSimple::bounds(), QTriangulator< T >::SimpleToMonotone::classifyVertex(), QTriangulator< T >::ComplexToSimple::edgeIsLeftOfEdge(), QTriangulator< T >::SimpleToMonotone::edgeIsLeftOfEdge(), QTriangulator< T >::ComplexToSimple::outerBounds(), qPointIsLeftOfLine(), and QTriangulator< T >::SimpleToMonotone::searchEdgeLeftOfPoint().

{
    return qCross(v2 - v1, p - v1);
}

qPointIsLeftOfLine()

static bool qPointIsLeftOfLine ( const QPodPoint &  p, const QPodPoint &  v1, const QPodPoint &  v2  )

inlinestatic

Definition at line 340 of file qtriangulator.cpp.

Referenced by QTriangulator< T >::MonotoneToTriangles::leftOfEdge(), QTriangulator< T >::SimpleToMonotone::monotoneDecomposition(), and QTriangulator< T >::SimpleToMonotone::pointIsInSector().

{
    return QT_PREPEND_NAMESPACE(qPointDistanceFromLine)(p, v1, v2) < 0;
}

qPolyline() [1/2]

QPolylineSet qPolyline	(	const QVectorPath &	path,
		const QTransform &	matrix,
		qreal	lod
	)

Definition at line 3077 of file qtriangulator.cpp.

{
    QPolylineSet polyLineSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.polyline();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUshort(vertexSet.indices);
    }
    return polyLineSet;
}

qPolyline() [2/2]

QPolylineSet qPolyline	(	const QPainterPath &	path,
		const QTransform &	matrix,
		qreal	lod
	)

Definition at line 3097 of file qtriangulator.cpp.

{
    QPolylineSet polyLineSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.polyline();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        polyLineSet.vertices = vertexSet.vertices;
        polyLineSet.indices.setDataUshort(vertexSet.indices);
    }
    return polyLineSet;
}

qTriangulate() [1/3]

QTriangleSet qTriangulate	(	const qreal *	polygon,
		int	count,
		uint	hint,
		const QTransform &	matrix
	)

Definition at line 3016 of file qtriangulator.cpp.

Referenced by QGL2PaintEngineExPrivate::fill().

{
    QTriangleSet triangleSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(polygon, count, hint, matrix);
        QVertexSet<quint32> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUint(vertexSet.indices);

    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(polygon, count, hint, matrix);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUshort(vertexSet.indices);
    }
    return triangleSet;
}

qTriangulate() [2/3]

QTriangleSet qTriangulate	(	const QVectorPath &	path,
		const QTransform &	matrix,
		qreal	lod
	)

Definition at line 3037 of file qtriangulator.cpp.

{
    QTriangleSet triangleSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUshort(vertexSet.indices);
    }
    return triangleSet;
}

qTriangulate() [3/3]

QTriangleSet qTriangulate	(	const QPainterPath &	path,
		const QTransform &	matrix,
		qreal	lod
	)

Definition at line 3057 of file qtriangulator.cpp.

{
    QTriangleSet triangleSet;
    if (QGLExtensions::glExtensions() & QGLExtensions::ElementIndexUint) {
        QTriangulator<quint32> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint32> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUint(vertexSet.indices);
    } else {
        QTriangulator<quint16> triangulator;
        triangulator.initialize(path, matrix, lod);
        QVertexSet<quint16> vertexSet = triangulator.triangulate();
        triangleSet.vertices = vertexSet.vertices;
        triangleSet.indices.setDataUshort(vertexSet.indices);
    }
    return triangleSet;
}

sort() [1/2]

template<class T , class LessThan >

static void sort ( T *  array, int  count, LessThan  lessThan  )

static

Definition at line 73 of file qtriangulator.cpp.

Referenced by QSortFilterProxyModelPrivate::_q_sourceColumnsInserted(), QSortFilterProxyModelPrivate::_q_sourceReset(), QSortFilterProxyModelPrivate::_q_sourceRowsInserted(), QSortFilterProxyModelPrivate::create_index(), QTriangulator< T >::ComplexToSimple::fillPriorityQueue(), QTriangulator< T >::SimpleToMonotone::fillPriorityQueue(), QTableModel::index(), QStandardItemModelPrivate::itemFromIndex(), QStringList::QStringList(), QDir::setSorting(), QAbstractItemModel::sibling(), sort(), QDir::temp(), and QPatternist::NodeSortExpression::wrapAround().

{
    // If the number of elements fall below some threshold, use insertion sort.
    const int INSERTION_SORT_LIMIT = 7; // About 7 is fastest on my computer...
    if (count <= INSERTION_SORT_LIMIT) {
        for (int i = 1; i < count; ++i) {
            T temp = array[i];
            int j = i;
            while (j > 0 && lessThan(temp, array[j - 1])) {
                array[j] = array[j - 1];
                --j;
            }
            array[j] = temp;
        }
        return;
    }

    int high = count - 1;
    int low = 0;
    int mid = high / 2;
    if (lessThan(array[mid], array[low]))
        qSwap(array[mid], array[low]);
    if (lessThan(array[high], array[mid]))
        qSwap(array[high], array[mid]);
    if (lessThan(array[mid], array[low]))
        qSwap(array[mid], array[low]);

    --high;
    ++low;
    qSwap(array[mid], array[high]);
    int pivot = high;
    --high;

    while (low <= high) {
        while (!lessThan(array[pivot], array[low])) {
            ++low;
            if (low > high)
                goto sort_loop_end;
        }
        while (!lessThan(array[high], array[pivot])) {
            --high;
            if (low > high)
                goto sort_loop_end;
        }
        qSwap(array[low], array[high]);
        ++low;
        --high;
    }
sort_loop_end:
    if (low != pivot)
        qSwap(array[pivot], array[low]);
    sort(array, low, lessThan);
    sort(array + low + 1, count - low - 1, lessThan);
}

sort() [2/2]

template<class T >

static void sort ( T *  array, int  count  )

static

Definition at line 134 of file qtriangulator.cpp.

{
    // If the number of elements fall below some threshold, use insertion sort.
    const int INSERTION_SORT_LIMIT = 25; // About 25 is fastest on my computer...
    if (count <= INSERTION_SORT_LIMIT) {
        for (int i = 1; i < count; ++i) {
            T temp = array[i];
            int j = i;
            while (j > 0 && (temp < array[j - 1])) {
                array[j] = array[j - 1];
                --j;
            }
            array[j] = temp;
        }
        return;
    }

    int high = count - 1;
    int low = 0;
    int mid = high / 2;
    if ((array[mid] < array[low]))
        qSwap(array[mid], array[low]);
    if ((array[high] < array[mid]))
        qSwap(array[high], array[mid]);
    if ((array[mid] < array[low]))
        qSwap(array[mid], array[low]);

    --high;
    ++low;
    qSwap(array[mid], array[high]);
    int pivot = high;
    --high;

    while (low <= high) {
        while (!(array[pivot] < array[low])) {
            ++low;
            if (low > high)
                goto sort_loop_end;
        }
        while (!(array[high] < array[pivot])) {
            --high;
            if (low > high)
                goto sort_loop_end;
        }
        qSwap(array[low], array[high]);
        ++low;
        --high;
    }
sort_loop_end:
    if (low != pivot)
        qSwap(array[pivot], array[low]);
    sort(array, low);
    sort(array + low + 1, count - low - 1);
}

Variable Documentation

prime_deltas

const uchar prime_deltas[]

static

Initial value:

= {
    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
}

Definition at line 1110 of file qtriangulator.cpp.