/*
 * Generic Convex Polygon Scan Conversion and Clipping
 * by Paul Heckbert
 * from "Graphics Gems", Academic Press, 1990
 */

/*
 * poly_clip.c: homogeneous 3-D convex polygon clipper
 *
 * original by Paul Heckbert    1985, Dec 1989
 * slightly modified by  Juha Ruokolainen/CSC, Sep 1994
 */

#include "graf.h"

#define SWAP(a,b,temp) {temp = a; a = b; b = temp;}
#define COORD(vert,i) ((FLOAT *)(vert))[i]

#define CLIP_AND_SWAP(elem, sign, p, q)                 \
{                                                       \
    nq = poly_clip_to_halfspace(p, q, elem, sign, n );  \
    if ( nq==0 ) { return 0; }                          \
    SWAP(p,  q, r);                                     \
    SWAP(n, nq, i);                                     \
}

/*
 * poly_clip_to_halfspace: clip convex polygon p against a plane.
 */
static int poly_clip_to_halfspace(ZBF_VERTEX *p, ZBF_VERTEX *q, int index, FLOAT sign, int np )
{
    FLOAT *up, *vp, *wp;
    FLOAT t, tu, tv;
    ZBF_VERTEX *u,*v;

    int i,j;

    int nq = 0;

    /* start with u=vert[n-1], v=vert[0] */
    u = &p[np-1];

    tu = sign*COORD(u,index) - u->CoordW;

    for (v = p, i=np; i>0; i--, u=v, tu=tv, v++)
    {
        /* on old polygon (p), u is previous vertex, v is current vertex */
        /* tv is negative if vertex v is in */

        tv = sign*COORD(v, index)-v->CoordW;
        if (tu <= 0.0 ^ tv <= 0.0)
        {
            /* edge crosses plane; add intersection point to q */
            t = tu / (tu-tv);
            up = (FLOAT *)u;
            vp = (FLOAT *)v;
            wp = (FLOAT *)&q[nq];

            for( j=0; j<VERTEX_NCOMP; j++ ) wp[j] = up[j] + t*(vp[j]-up[j]);

            nq++;
        }

        /* vertex v is in, copy it to q */
        if ( tv <= 0.0 ) q[nq++] = *v;
    }

    return nq;
}

/*
 * clp_clip_polygon: Clip the convex polygon to the screen space box.
 * output number of vertices is returned.
 */
int clp_clip_polygon(int n,ZBF_VERTEX *poly)
{
    int left = 0, right = 0, bottom = 0, top = 0, near = 0, far = 0;
    int i,nq;

    FLOAT w;

    ZBF_VERTEX *v;
    ZBF_VERTEX poly2[USR_MAX_VERTICES], *p, *q, *r;

    /* count vertices "outside" with respect to each of the six planes */
    for ( v=poly, i=0; i<n; i++, v++ )
    {
        w = v->CoordW;

        if (v->CoordX < -w) left++;
        else if (v->CoordX > w) right++;

        if (v->CoordY < -w) bottom++;
        else if (v->CoordY > w) top++;

        if (v->CoordZ < -w) near++;
        else if (v->CoordZ > w) far++;
    }

    /* check if all vertices inside */
    if ( !(left||right||bottom||top||near||far) ) return n;

    /* check if all vertices are "outside" any of the six planes */
    if ( left == n || right == n || bottom == n ||
         top  == n || near  == n || far == n ) return  0;

    /*
     * now clip against each of the planes that might cut the polygon
     */
    p = poly;
    q = poly2;

    if (left)   CLIP_AND_SWAP( VERTEX_COORD_X,-1.0,p,q );
    if (right)  CLIP_AND_SWAP( VERTEX_COORD_X, 1.0,p,q );
    if (bottom) CLIP_AND_SWAP( VERTEX_COORD_Y,-1.0,p,q );
    if (top)    CLIP_AND_SWAP( VERTEX_COORD_Y, 1.0,p,q );
    if (near)   CLIP_AND_SWAP( VERTEX_COORD_Z,-1.0,p,q );
    if (far)    CLIP_AND_SWAP( VERTEX_COORD_Z, 1.0,p,q );
 
    /* if result ended up in store then copy it to original */
    if ( p==poly2 ) { memcpy(poly, poly2, n*sizeof(ZBF_VERTEX));  }

    return n;
}
