/****************************************************************************

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, 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.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qtessellator_p.h"

#include <QRect>

#include <QList>

#include <QDebug>

#include <qmath.h>

#include <limits.h>

QT_BEGIN_NAMESPACE

//#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 = q_check_ptr((Edge **)realloc(edges, s*sizeof(Edge *)));

        edge_table = q_check_ptr((Edge *)realloc(edge_table, s*sizeof(Edge)));

        old = q_check_ptr((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;

    }

    old_size = size;

}

void QTessellatorPrivate::Scanline::lineDone()

{

    Edge **end = old + old_size;

    Edge **e = old;

    while (e < end) {

        if ((*e)->free) {

            (*e)->edge = first_unused;

            first_unused = (*e - edge_table);

        }

        ++e;

    }

}

void QTessellatorPrivate::Scanline::insert(int pos, const Edge &e)

{

    Edge *edge = edge_table + first_unused;

    first_unused = edge->edge;

    Q_ASSERT(first_unused != -1);

    *edge = e;

    memmove(edges + pos + 1, edges + pos, (size - pos)*sizeof(Edge *));

    edges[pos] = edge;

    ++size;