qtessellator.cpp

奇趣公司比较新的qt/emd版本

/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the QtGui module of the Qt Toolkit.
**
** This file may be used under the terms of the GNU General Public
** License version 2.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 GNU
** General Public Licensing requirements will be met:
** http://trolltech.com/products/qt/licenses/licensing/opensource/
**
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
** or contact the sales department at [e-mail].
**
** In addition, as a special exception, Trolltech gives you certain
** additional rights. These rights are described in the Trolltech GPL
** Exception version 1.0, which can be found at
** http://www.trolltech.com/products/qt/gplexception/ and in the file
** GPL_EXCEPTION.txt in this package.
**
** In addition, as a special exception, Trolltech, as the sole copyright
** holder for Qt Designer, grants users of the Qt/Eclipse Integration
** plug-in the right for the Qt/Eclipse Integration to link to
** functionality provided by Qt Designer and its related libraries.
**
** Trolltech reserves all rights not expressly granted herein.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/

#include "qtessellator_p.h"

#include <QRect>
#include <QList>
#include <QDebug>

#include <limits.h>
#include <private/qmath_p.h>

//#define DEBUG
#ifdef DEBUG
#define QDEBUG qDebug
#else
#define QDEBUG if (1); else qDebug
#endif

static const bool emit_clever = true;
static const bool mark_clever = false;

enum VertexFlags {
    LineBeforeStarts = 0x1,
    LineBeforeEnds = 0x2,
    LineBeforeHorizontal = 0x4,
    LineAfterStarts = 0x8,
    LineAfterEnds = 0x10,
    LineAfterHorizontal = 0x20
};



class QTessellatorPrivate {
public:
    struct Vertices;

    QTessellatorPrivate() {}

    QRectF collectAndSortVertices(const QPointF *points, int *maxActiveEdges);
    void cancelCoincidingEdges();

    void emitEdges(QTessellator *tessellator);
    void processIntersections();
    void removeEdges();
    void addEdges();
    void addIntersections();

    struct Vertex : public QTessellator::Vertex
    {
        int flags;
    };

    struct Intersection
    {
        Q27Dot5 y;
        int edge;
        bool operator <(const Intersection &other) const {
            if (y != other.y)
                return y < other.y;
            return edge < other.edge;
        }
    };
    struct IntersectionLink
    {
        int next;
        int prev;
    };
    typedef QMap<Intersection, IntersectionLink> Intersections;

    struct Edge {
        Edge(const Vertices &v, int _edge);
        int edge;
        const Vertex *v0;
        const Vertex *v1;
        Q27Dot5 y_left;
        Q27Dot5 y_right;
        signed int winding : 8;
        bool mark;
        bool free;
        bool intersect_left;
        bool intersect_right;
        bool isLeftOf(const Edge &other, Q27Dot5 y) const;
        Q27Dot5 positionAt(Q27Dot5 y) const;
        bool intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const;

    };

    class EdgeSorter
    {
    public:
        EdgeSorter(int _y) : y(_y) {}
        bool operator() (const Edge *e1, const Edge *e2);
        int y;
    };

    class Scanline {
    public:
        Scanline();
        ~Scanline();

        void init(int maxActiveEdges);
        void done();

        int findEdgePosition(Q27Dot5 x, Q27Dot5 y) const;
        int findEdgePosition(const Edge &e) const;
        int findEdge(int edge) const;
        void clearMarks();

        void swap(int p1, int p2) {
            Edge *tmp = edges[p1];
            edges[p1] = edges[p2];
            edges[p2] = tmp;
        }
        void insert(int pos, const Edge &e);
        void removeAt(int pos);
        void markEdges(int pos1, int pos2);

        void prepareLine();
        void lineDone();

        Edge **old;
        int old_size;

        Edge **edges;
        int size;

    private:
        Edge *edge_table;
        int first_unused;
        int max_edges;
        enum { default_alloc = 32 };
    };

    struct Vertices {
        enum { default_alloc = 128 };
        Vertices();
        ~Vertices();
        void init(int maxVertices);
        void done();
        Vertex *storage;
        Vertex **sorted;

        Vertex *operator[] (int i) { return storage + i; }
        const Vertex *operator[] (int i) const { return storage + i; }
        int position(const Vertex *v) const {
            return v - storage;
        }
        Vertex *next(Vertex *v) {
            ++v;
            if (v == storage + nPoints)
                v = storage;
            return v;
        }
        const Vertex *next(const Vertex *v) const {
            ++v;
            if (v == storage + nPoints)
                v = storage;
            return v;
        }
        int nextPos(const Vertex *v) const {
            ++v;
            if (v == storage + nPoints)
                return 0;
            return v - storage;
        }
        Vertex *prev(Vertex *v) {
            if (v == storage)
                v = storage + nPoints;
            --v;
            return v;
        }
        const Vertex *prev(const Vertex *v) const {
            if (v == storage)
                v = storage + nPoints;
            --v;
            return v;
        }
        int prevPos(const Vertex *v) const {
            if (v == storage)
                v = storage + nPoints;
            --v;
            return v - storage;
        }
        int nPoints;
        int allocated;
    };
    Vertices vertices;
    Intersections intersections;
    Scanline scanline;
    bool winding;
    Q27Dot5 y;
    int currentVertex;

private:
    void addIntersection(const Edge *e1, const Edge *e2);
    bool edgeInChain(Intersection i, int edge);
};


QTessellatorPrivate::Edge::Edge(const QTessellatorPrivate::Vertices &vertices, int edge)
{
    this->edge = edge;
    intersect_left = intersect_right = true;
    mark = false;
    free = false;

    v0 = vertices[edge];
    v1 = vertices.next(v0);

    Q_ASSERT(v0->y != v1->y);

    if (v0->y > v1->y) {
        qSwap(v0, v1);
        winding = -1;
    } else {
        winding = 1;
    }
    y_left = y_right = v0->y;
}

// This is basically the algorithm from graphics gems. The algorithm
// is cubic in the coordinates at one place.  Since we use 64bit
// integers, this implies, that the allowed range for our coordinates
// is limited to 21 bits.  With 5 bits behind the decimal, this
// implies that differences in coordaintes can range from 2*SHORT_MIN
// to 2*SHORT_MAX, giving us efficiently a coordinate system from
// SHORT_MIN to SHORT_MAX.
//

// WARNING: It's absolutely critical that the intersect() and isLeftOf() methods use
// exactly the same algorithm to calulate yi. It's also important to be sure the algorithms
// are transitive (ie. the conditions below are true for all input data):
//
// a.intersect(b) == b.intersect(a)
// a.isLeftOf(b) != b.isLeftOf(a)
//
// This is tricky to get right, so be very careful when changing anything in here!

static inline bool sameSign(qint64 a, qint64 b) {
    return (((qint64) ((quint64) a ^ (quint64) b)) >= 0 );
}

bool QTessellatorPrivate::Edge::intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const
{
    qint64 a1 = v1->y - v0->y;
    qint64 b1 = v0->x - v1->x;

    qint64 a2 = other.v1->y - other.v0->y;
    qint64 b2 = other.v0->x - other.v1->x;

    qint64 det = a1 * b2 - a2 * b1;
    if (det == 0)
        return false;

    qint64 c1 = qint64(v1->x) * v0->y - qint64(v0->x) * v1->y;

    qint64 r3 = a1 * other.v0->x + b1 * other.v0->y + c1;
    qint64 r4 = a1 * other.v1->x + b1 * other.v1->y + c1;

    // Check signs of r3 and r4.  If both point 3 and point 4 lie on
    // same side of line 1, the line segments do not intersect.
    QDEBUG() << "        " << r3 << r4;
    if (r3 != 0 && r4 != 0 && sameSign( r3, r4 ))
        return false;

    qint64 c2 = qint64(other.v1->x) * other.v0->y - qint64(other.v0->x) * other.v1->y;

    qint64 r1 = a2 * v0->x + b2 * v0->y + c2;
    qint64 r2 = a2 * v1->x + b2 * v1->y + c2;

    // Check signs of r1 and r2.  If both point 1 and point 2 lie
    // on same side of second line segment, the line segments do not intersect.
    QDEBUG() << "        " << r1 << r2;
    if (r1 != 0 && r2 != 0 && sameSign( r1, r2 ))
        return false;

    // The det/2 is to get rounding instead of truncating.  It
    // is added or subtracted to the numerator, depending upon the
    // sign of the numerator.
    qint64 offset = det < 0 ? -det : det;
    offset >>= 1;

    qint64 num = a2 * c1 - a1 * c2;
    *y = ( num < 0 ? num - offset : num + offset ) / det;

    *det_positive = (det > 0);

    return true;
}

#undef SAME_SIGNS

bool QTessellatorPrivate::Edge::isLeftOf(const Edge &other, Q27Dot5 y) const
{
//     QDEBUG() << "isLeftOf" << edge << other.edge << y;
    qint64 a1 = v1->y - v0->y;
    qint64 b1 = v0->x - v1->x;
    qint64 a2 = other.v1->y - other.v0->y;
    qint64 b2 = other.v0->x - other.v1->x;

    qint64 c2 = qint64(other.v1->x) * other.v0->y - qint64(other.v0->x) * other.v1->y;

    qint64 det = a1 * b2 - a2 * b1;
    if (det == 0) {
        // lines are parallel. Only need to check side of one point
        // fixed ordering for coincident edges
        qint64 r1 = a2 * v0->x + b2 * v0->y + c2;
//         QDEBUG() << "det = 0" << r1;
        if (r1 == 0)
            return edge < other.edge;
        return (r1 < 0);
    }

    // not parallel, need to find the y coordinate of the intersection point
    qint64 c1 = qint64(v1->x) * v0->y - qint64(v0->x) * v1->y;

    qint64 offset = det < 0 ? -det : det;
    offset >>= 1;

    qint64 num = a2 * c1 - a1 * c2;
    qint64 yi = ( num < 0 ? num - offset : num + offset ) / det;
//     QDEBUG() << "    num=" << num << "offset=" << offset << "det=" << det;

    return ((yi > y) ^ (det < 0));
}

static inline bool compareVertex(const QTessellatorPrivate::Vertex *p1,
                                 const QTessellatorPrivate::Vertex *p2)
{
    if (p1->y == p2->y) {
        if (p1->x == p2->x)
            return p1 < p2;
        return p1->x < p2->x;
    }
    return p1->y < p2->y;
}

Q27Dot5 QTessellatorPrivate::Edge::positionAt(Q27Dot5 y) const
{
    if (y == v0->y)
        return v0->x;
    else if (y == v1->y)
        return v1->x;

    qint64 d = v1->x - v0->x;
    return (v0->x + d*(y - v0->y)/(v1->y-v0->y));
}

bool QTessellatorPrivate::EdgeSorter::operator() (const Edge *e1, const Edge *e2)
{
    return e1->isLeftOf(*e2, y);
}


QTessellatorPrivate::Scanline::Scanline()
{
    edges = 0;
    edge_table = 0;
    old = 0;
}

void QTessellatorPrivate::Scanline::init(int maxActiveEdges)
{
    maxActiveEdges *= 2;
    if (!edges || maxActiveEdges > default_alloc) {
        max_edges = maxActiveEdges;
        int s = qMax(maxActiveEdges + 1, default_alloc + 1);
        edges = (Edge **)realloc(edges, s*sizeof(Edge *));
        edge_table = (Edge *)realloc(edge_table, s*sizeof(Edge));
        old = (Edge **)realloc(old, s*sizeof(Edge *));
    }
    size = 0;
    old_size = 0;
    first_unused = 0;
    for (int i = 0; i < maxActiveEdges; ++i)
        edge_table[i].edge = i+1;
    edge_table[maxActiveEdges].edge = -1;
}

void QTessellatorPrivate::Scanline::done()
{
    if (max_edges > default_alloc) {
        free(edges);
        free(old);
        free(edge_table);
        edges = 0;
        old = 0;
        edge_table = 0;
    }
}

QTessellatorPrivate::Scanline::~Scanline()
{
    free(edges);
    free(old);
    free(edge_table);
}

int QTessellatorPrivate::Scanline::findEdgePosition(Q27Dot5 x, Q27Dot5 y) const
{
    int min = 0;
    int max = size - 1;
    while (min < max) {
        int pos = min + ((max - min + 1) >> 1);
        Q27Dot5 ax = edges[pos]->positionAt(y);
        if (ax > x) {
            max = pos - 1;
        } else {
            min = pos;
        }
    }
    return min;
}

int QTessellatorPrivate::Scanline::findEdgePosition(const Edge &e) const
{
//     qDebug() << ">>      findEdgePosition";
    int min = 0;
    int max = size;
    while (min < max) {
        int pos = min + ((max - min) >> 1);
//         qDebug() << "        " << min << max << pos << edges[pos]->isLeftOf(e, e.y0);
        if (edges[pos]->isLeftOf(e, e.v0->y)) {
            min = pos + 1;
        } else {
            max = pos;
        }
    }
//     qDebug() << "<<      findEdgePosition got" << min;
    return min;
}

int QTessellatorPrivate::Scanline::findEdge(int edge) const
{
    for (int i = 0; i < size; ++i) {
        int item_edge = edges[i]->edge;
        if (item_edge == edge)
            return i;
    }
    //Q_ASSERT(false);
    return -1;
}

void QTessellatorPrivate::Scanline::clearMarks()
{
    for (int i = 0; i < size; ++i) {
        edges[i]->mark = false;
        edges[i]->intersect_left = false;
        edges[i]->intersect_right = false;
    }
}

void QTessellatorPrivate::Scanline::prepareLine()
{
    Edge **end = edges + size;
    Edge **e = edges;
    Edge **o = old;
    while (e < end) {
        *o = *e;
        ++o;
        ++e;