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

**

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

** All rights reserved.

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

**

** This file is part of the test suite 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 "oldtessellator.h"

#include <QPointF>

#include <QVector>

#include <QList>

#include <QVariant>

#include <QVarLengthArray>

#include <qdebug.h>

#include "limits.h"

#include "utils.h"

#include "qnum.h"

#include "XrenderFake.h"

/*

 * Polygon tesselator - can probably be optimized a bit more

 */

//#define QT_DEBUG_TESSELATOR

#define FloatToXFixed(i) (int)((i) * 65536)

#define IntToXFixed(i) ((i) << 16)

//inline int qrealToXFixed(qreal f)

//{ return f << 8; }

struct QEdge {

    inline QEdge()

    {}

    inline QEdge(const QPointF &pt1,

                 const QPointF &pt2)

    {

        p1.x = XDoubleToFixed(pt1.x());

        p1.y = XDoubleToFixed(pt1.y());

        p2.x = XDoubleToFixed(pt2.x());

        p2.y = XDoubleToFixed(pt2.y());

        m = (pt1.x() - pt2.x()) ? (pt1.y() - pt2.y()) / (pt1.x() - pt2.x()) : 0;

        im = m ? 1/m : 0;

        b = pt1.y() - m * pt1.x();

        vertical = p1.x == p2.x;

        horizontal = p1.y == p2.y;

    }

    inline qreal xAt(const qreal &y) const

    {

        Q_ASSERT(p1.y != p2.y);

        XFixed yf = XDoubleToFixed(y);

        if (yf == p1.y)

            return XFixedToDouble(p1.x);

        else if (yf == p2.y)

            return XFixedToDouble(p2.x);

        return (!vertical) ? (((y - b)*im)) : pf1.x();

    }

    QPointF     pf1, pf2;

    XPointFixed p1, p2;

    qreal m;

    qreal im;

    qreal b;

    qreal intersection;

    signed short winding;

    bool vertical;

    bool horizontal;

};

struct QVrtx {

    typedef QList<QEdge> Edges;

    XPointFixed coords;

    Edges startingEdges;

    Edges endingEdges;

    Edges intersectingEdges;

};

struct QIntersectionPoint {

    qreal x;

    const QEdge *edge;

};

QT_BEGIN_NAMESPACE

Q_DECLARE_TYPEINFO(QEdge, Q_PRIMITIVE_TYPE);

Q_DECLARE_TYPEINFO(QVrtx, Q_PRIMITIVE_TYPE);

Q_DECLARE_TYPEINFO(QIntersectionPoint, Q_PRIMITIVE_TYPE);

QT_END_NAMESPACE

// used by the edge point sort algorithm

static qreal currentY = 0.f;

static inline bool compareEdges(const QEdge *e1, const QEdge *e2)

{

    return e1->p1.y < e2->p1.y;

}

static inline bool isEqual(const XPointFixed &p1, const XPointFixed &p2)

{

    return ((p1.x == p2.x) && (p1.y == p2.y));

}

static inline bool compareIntersections(const QIntersectionPoint &i1, const QIntersectionPoint &i2)

{

    if (qAbs(i1.x - i2.x) > 0.01) { // x != other.x in 99% of the cases

        return i1.x < i2.x;

    } else {

        qreal x1 = (i1.edge->p1.x != i1.edge->p2.x) ?

                   ((currentY+1 - i1.edge->b)*i1.edge->m) : XFixedToDouble(i1.edge->p1.x);

        qreal x2 = (i2.edge->p1.x != i2.edge->p2.x) ?

                   ((currentY+1 - i2.edge->b)*i2.edge->m) : XFixedToDouble(i2.edge->p1.x);

//         qDebug() << ">>>" << currentY << i1.edge << i2.edge << x1 << x2;

        return x1 < x2;

    }

}

#ifdef QT_USE_FIXED_POINT

inline int qrealToXFixed(qreal f)

{ return f.value() << 8; }

#else

#define qrealToXFixed FloatToXFixed

#endif

static XTrapezoid QT_FASTCALL toXTrapezoid(XFixed y1, XFixed y2, const QEdge &left, const QEdge &right)

{

    XTrapezoid trap;

    trap.top = y1;

    trap.bottom = y2;

    trap.left.p1.y = left.p1.y;

    trap.left.p2.y = left.p2.y;

    trap.right.p1.y = right.p1.y;

    trap.right.p2.y = right.p2.y;

    trap.left.p1.x = left.p1.x;

    trap.left.p2.x = left.p2.x;

    trap.right.p1.x = right.p1.x;

    trap.right.p2.x = right.p2.x;

    return trap;

}

#ifdef QT_DEBUG_TESSELATOR

static void dump_edges(const QList<const QEdge *> &et)

{

    for (int x = 0; x < et.size(); ++x) {

        qDebug() << "edge#" << x << et.at(x) << "("

                 << XFixedToDouble(et.at(x)->p1.x)

                 << XFixedToDouble(et.at(x)->p1.y)

                 << ") ("

                 << XFixedToDouble(et.at(x)->p2.x)

                 << XFixedToDouble(et.at(x)->p2.y)

                 << ") b: " << et.at(x)->b << "m:" << et.at(x)->m;

    }

}

static void dump_trap(const XTrapezoid &t)

{

    qDebug() << "trap# t=" << t.top/65536.0 << "b=" << t.bottom/65536.0  << "h="

             << XFixedToDouble(t.bottom - t.top) << "\tleft p1: ("

             << XFixedToDouble(t.left.p1.x) << ","<< XFixedToDouble(t.left.p1.y)

             << ")" << "\tleft p2: (" << XFixedToDouble(t.left.p2.x) << ","

             << XFixedToDouble(t.left.p2.y) << ")" << "\n\t\t\t\tright p1:("

             << XFixedToDouble(t.right.p1.x) << "," << XFixedToDouble(t.right.p1.y) << ")"

             << "\tright p2:(" << XFixedToDouble(t.right.p2.x) << ","

             << XFixedToDouble(t.right.p2.y) << ")";

}

#endif

typedef int Q27Dot5;

#define Q27Dot5ToDouble(i) (i/32.)

#define FloatToQ27Dot5(i) (int)((i) * 32)

#define IntToQ27Dot5(i) ((i) << 5)

#define Q27Dot5ToXFixed(i) ((i) << 11)

#define Q27Dot5Factor 32

void old_tesselate_polygon(QVector<XTrapezoid> *traps, const QPointF *pg, int pgSize,

                           bool winding)

{

    QVector<QEdge> edges;

    edges.reserve(128);

    qreal ymin(INT_MAX/256);

    qreal ymax(INT_MIN/256);

    //painter.begin(pg, pgSize);

    Q_ASSERT(pg[0] == pg[pgSize-1]);

    // generate edge table

//     qDebug() << "POINTS:";

    for (int x = 0; x < pgSize-1; ++x) {

	QEdge edge;

        QPointF p1(Q27Dot5ToDouble(FloatToQ27Dot5(pg[x].x())),

                   Q27Dot5ToDouble(FloatToQ27Dot5(pg[x].y())));

        QPointF p2(Q27Dot5ToDouble(FloatToQ27Dot5(pg[x+1].x())),

                   Q27Dot5ToDouble(FloatToQ27Dot5(pg[x+1].y())));

//         qDebug() << "    "

//                  << p1;

	edge.winding = p1.y() > p2.y() ? 1 : -1;

	if (edge.winding > 0)

            qSwap(p1, p2);

        edge.p1.x = XDoubleToFixed(p1.x());

        edge.p1.y = XDoubleToFixed(p1.y());

        edge.p2.x = XDoubleToFixed(p2.x());

        edge.p2.y = XDoubleToFixed(p2.y());

	edge.m = (p1.y() - p2.y()) / (p1.x() - p2.x()); // line derivative

	edge.b = p1.y() - edge.m * p1.x(); // intersection with y axis

	edge.m = edge.m != 0.0 ? 1.0 / edge.m : 0.0; // inverted derivative

	edges.append(edge);

        ymin = qMin(ymin, qreal(XFixedToDouble(edge.p1.y)));

        ymax = qMax(ymax, qreal(XFixedToDouble(edge.p2.y)));

    }

    QList<const QEdge *> et; 	    // edge list

    for (int i = 0; i < edges.size(); ++i)

        et.append(&edges.at(i));

    // sort edge table by min y value

    qSort(et.begin(), et.end(), compareEdges);

    // eliminate shared edges

    for (int i = 0; i < et.size(); ++i) {

	for (int k = i+1; k < et.size(); ++k) {

            const QEdge *edgeI = et.at(i);

            const QEdge *edgeK = et.at(k);

            if (edgeK->p1.y > edgeI->p1.y)

                break;

   	    if (edgeI->winding != edgeK->winding &&

                isEqual(edgeI->p1, edgeK->p1) && isEqual(edgeI->p2, edgeK->p2)

		) {

 		et.removeAt(k);

		et.removeAt(i);

		--i;

		break;

	    }

	}

    }

    if (ymax <= ymin)

	return;

    QList<const QEdge *> aet; 	    // edges that intersects the current scanline

//     if (ymin < 0)

// 	ymin = 0;

//     if (paintEventClipRegion) // don't scan more lines than we have to

// 	ymax = paintEventClipRegion->boundingRect().height();

#ifdef QT_DEBUG_TESSELATOR

    qDebug("==> ymin = %f, ymax = %f", ymin, ymax);

#endif // QT_DEBUG_TESSELATOR

    currentY = ymin; // used by the less than op

    for (qreal y = ymin; y < ymax;) {

	// fill active edge table with edges that intersect the current line

	for (int i = 0; i < et.size(); ++i) {

            const QEdge *edge = et.at(i);

            if (edge->p1.y > XDoubleToFixed(y))

                break;

            aet.append(edge);

            et.removeAt(i);

            --i;

	}

	// remove processed edges from active edge table

	for (int i = 0; i < aet.size(); ++i) {

	    if (aet.at(i)->p2.y <= XDoubleToFixed(y)) {

		aet.removeAt(i);

 		--i;

	    }

	}

        if (aet.size()%2 != 0) {

#ifndef QT_NO_DEBUG

            qWarning("QX11PaintEngine: aet out of sync - this should not happen.");

#endif

            return;

        }

	// done?

	if (!aet.size()) {

            if (!et.size()) {

                break;

	    } else {

 		y = currentY = XFixedToDouble(et.at(0)->p1.y);

                continue;

	    }

        }

        // calculate the next y where we have to start a new set of trapezoids

	qreal next_y(INT_MAX/256);

 	for (int i = 0; i < aet.size(); ++i) {

            const QEdge *edge = aet.at(i);

 	    if (XFixedToDouble(edge->p2.y) < next_y)

 		next_y = XFixedToDouble(edge->p2.y);

        }

	if (et.size() && next_y > XFixedToDouble(et.at(0)->p1.y))

	    next_y = XFixedToDouble(et.at(0)->p1.y);

        int aetSize = aet.size();

	for (int i = 0; i < aetSize; ++i) {

	    for (int k = i+1; k < aetSize; ++k) {

                const QEdge *edgeI = aet.at(i);

                const QEdge *edgeK = aet.at(k);

		qreal m1 = edgeI->m;

		qreal b1 = edgeI->b;

		qreal m2 = edgeK->m;

		qreal b2 = edgeK->b;

		if (qAbs(m1 - m2) < 0.001)

                    continue;

                // ### intersect is not calculated correctly when optimized with -O2 (gcc)

                volatile qreal intersect = 0;

                if (!qIsFinite(b1))

                    intersect = (1.f / m2) * XFixedToDouble(edgeI->p1.x) + b2;

                else if (!qIsFinite(b2))

                    intersect = (1.f / m1) * XFixedToDouble(edgeK->p1.x) + b1;

                else

                    intersect = (b1*m1 - b2*m2) / (m1 - m2);

 		if (intersect > y && intersect < next_y)

		    next_y = intersect;

	    }

	}

        XFixed yf, next_yf;

        yf = qrealToXFixed(y);

        next_yf = qrealToXFixed(next_y);

        if (yf == next_yf) {

            y = currentY = next_y;

            continue;

        }

#ifdef QT_DEBUG_TESSELATOR

        qDebug("###> y = %f, next_y = %f, %d active edges", y, next_y, aet.size());

        qDebug("===> edges");

        dump_edges(et);

        qDebug("===> active edges");

        dump_edges(aet);

#endif

	// calc intersection points

 	QVarLengthArray<QIntersectionPoint> isects(aet.size()+1);

 	for (int i = 0; i < isects.size()-1; ++i) {

            const QEdge *edge = aet.at(i);

 	    isects[i].x = (edge->p1.x != edge->p2.x) ?

			  ((y - edge->b)*edge->m) : XFixedToDouble(edge->p1.x);

	    isects[i].edge = edge;

	}

	Q_ASSERT(isects.size()%2 == 1);

	// sort intersection points

 	qSort(&isects[0], &isects[isects.size()-1], compareIntersections);

//         qDebug() << "INTERSECTION_POINTS:";

//  	for (int i = 0; i < isects.size(); ++i)

//             qDebug() << isects[i].edge << isects[i].x;

        if (winding) {

            // winding fill rule

            for (int i = 0; i < isects.size()-1;) {

                int winding = 0;

                const QEdge *left = isects[i].edge;

                const QEdge *right = 0;

                winding += isects[i].edge->winding;

                for (++i; i < isects.size()-1 && winding != 0; ++i) {

                    winding += isects[i].edge->winding;

                    right = isects[i].edge;

                }

                if (!left || !right)

                    break;

                //painter.addTrapezoid(&toXTrapezoid(yf, next_yf, *left, *right));

                traps->append(toXTrapezoid(yf, next_yf, *left, *right));

            }

        } else {

            // odd-even fill rule

            for (int i = 0; i < isects.size()-2; i += 2) {

                //painter.addTrapezoid(&toXTrapezoid(yf, next_yf, *isects[i].edge, *isects[i+1].edge));

                traps->append(toXTrapezoid(yf, next_yf, *isects[i].edge, *isects[i+1].edge));

            }

        }

	y = currentY = next_y;

    }

#ifdef QT_DEBUG_TESSELATOR

    qDebug("==> number of trapezoids: %d - edge table size: %d\n", traps->size(), et.size());

    for (int i = 0; i < traps->size(); ++i)

        dump_trap(traps->at(i));

#endif

    // optimize by unifying trapezoids that share left/right lines

    // and have a common top/bottom edge

//     for (int i = 0; i < tps.size(); ++i) {

// 	for (int k = i+1; k < tps.size(); ++k) {

// 	    if (i != k && tps.at(i).right == tps.at(k).right

// 		&& tps.at(i).left == tps.at(k).left

// 		&& (tps.at(i).top == tps.at(k).bottom

// 		    || tps.at(i).bottom == tps.at(k).top))

// 	    {

// 		tps[i].bottom = tps.at(k).bottom;

// 		tps.removeAt(k);

//                 i = 0;

// 		break;

// 	    }

// 	}

//     }

    //static int i = 0;

    //QImage img = painter.end();

    //img.save(QString("res%1.png").arg(i++), "PNG");

}