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

/*
 * line_clip.c: homogeneous 3-D line 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 = line_clip_to_halfspace(p, q, elem, sign, n ); \
    if ( nq==0 ) {  return 0; }                        \
    SWAP(p, q, r);                                     \
    SWAP(n, nq, i);                                    \
}


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

    int i,j,nq=0;

    /* start with u=vert[n-1], v=vert[0] */
    v  = &p[0];
    tv = sign*COORD(v,index) - v->CoordW;

    u  = &p[1];
    tu = sign*COORD(u,index) - u->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++;
    }

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

    return nq;
}

/*
 * Clip a line segment in homogenous coordinates.
 */
int clp_clip_line(ZBF_VERTEX *poly)
{
    int left = 0, right = 0, bottom = 0, top = 0, near = 0, far = 0;
    int i,nq,n=2;

    FLOAT w;

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

    /* count vertices "outside" with respect to each of the six planes */
    for (v=poly, i=n; i>0; 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 2;

    /* 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,
     * at each step toggling between polygons poly and poly2
     */
    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 poly2 then copy it to poly */
    if (p==poly2) { memcpy(poly, poly2, 2*sizeof(ZBF_VERTEX));  }

    return 2;
}
