/*
 * $Id$
 *
 * $Date$
 * $Revision$
 *
 * (C) 1999 by Hyperion
 * All rights reserved
 *
 * This file is part of the MiniGL library project
 * See the file Licence.txt for more details
 *
 */

#include "sysinc.h"
#include <math.h>

static char rcsid[] UNUSED = "$Id$";

#define LERP(t,a,b) \
	({ float aa = a; float bb = b; (aa) + (float)t * ( (bb) - (aa) ); })

#define INTERPOLATE(res,t,a,b) \
	res->bx = LERP(t,a->bx, b->bx); \
	res->by = LERP(t,a->by, b->by); \
	res->bz = LERP(t,a->bz, b->bz); \
	res->bw = LERP(t,a->bw, b->bw); \
	res->q = LERP(t, a->q, b->q); \
	res->v.color.a = LERP(t,a->v.color.a, b->v.color.a); \
	res->v.color.r = LERP(t,a->v.color.r, b->v.color.r); \
	res->v.color.g = LERP(t,a->v.color.g, b->v.color.g); \
	res->v.color.b = LERP(t,a->v.color.b, b->v.color.b); \
	res->v.u = LERP(t,a->v.u, b->v.u); \
	res->v.v = LERP(t,a->v.v, b->v.v);

#define CLIP_EPS (1e-7)

void hc_CodePoint(MGLVertex *v)
{
	float w = v->bw;
	GLubyte outcode = 0;

	if (v->bw < CLIP_EPS )
	{
		outcode |= MGL_CLIP_NEGW;
	}

	if (-w > v->bx)
	{
		outcode |= MGL_CLIP_LEFT;
	}
	else
	if (v->bx > w)
	{
		outcode |= MGL_CLIP_RIGHT;
	}

	if (-w > v->by)
	{
		outcode |= MGL_CLIP_BOTTOM;
	}
	else
	if (v->by > w)
	{
		outcode |= MGL_CLIP_TOP;
	}

	if (-w > v->bz)
	{
		outcode |= MGL_CLIP_BACK;
	}
	else
	if (v->bz > w)
	{
		outcode |= MGL_CLIP_FRONT;
	}

	v->outcode = outcode;
}

#define _x1 (a->bx)
#define _y1 (a->by)
#define _z1 (a->bz)
#define _w1 (a->bw)

#define _x2 (b->bx)
#define _y2 (b->by)
#define _z2 (b->bz)
#define _w2 (b->bw)

static void hc_ClipWZero(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	float w1 = _w1, w2 = _w2;
	float t = (CLIP_EPS-w1)/(w2-w1);
	r->bx = LERP(t,a->bx, b->bx);
	r->by = LERP(t,a->by, b->by);
	r->bz = LERP(t,a->bz, b->bz);
	r->bw = CLIP_EPS;
	r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
	r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
	r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
	r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
	r->v.u = LERP(t,a->v.u, b->v.u);
	r->v.v = LERP(t,a->v.v, b->v.v);
	hc_CodePoint(r);

	if (a->q == 1.0 && b->q == 1.0)
		r->q = 1.0;
	else
		r->q = CLIP_EPS;
}

static void hc_ClipTop(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	float w1 = _w1, y1 = _y1, w2 = _w2, y2 = _y2;
	float t = (w1-y1)/((w1-y1)-(w2-y2));
	r->bx = LERP(t,a->bx, b->bx);
	r->bz = LERP(t,a->bz, b->bz);
	r->bw = LERP(t,a->bw, b->bw);
	r->by = r->bw;
	r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
	r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
	r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
	r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
	r->v.u = LERP(t,a->v.u, b->v.u);
	r->v.v = LERP(t,a->v.v, b->v.v);
	hc_CodePoint(r);

	if (a->q == 1.0 && b->q == 1.0)
		r->q = 1.0;
	else
		r->q = LERP(t, a->q, b->q);
}

static void hc_ClipBottom(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	float w1 = _w1, y1 = _y1, w2 = _w2, y2 = _y2;
	float t = (w1+y1)/((w1+y1)-(w2+y2));
	r->bx = LERP(t,a->bx, b->bx);
	r->bz = LERP(t,a->bz, b->bz);
	r->bw = LERP(t,a->bw, b->bw);
	r->by = -r->bw;
	r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
	r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
	r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
	r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
	r->v.u = LERP(t,a->v.u, b->v.u);
	r->v.v = LERP(t,a->v.v, b->v.v);
	hc_CodePoint(r);

	if (a->q == 1.0 && b->q == 1.0)
		r->q = 1.0;
	else
		r->q = LERP(t, a->q, b->q);

}

static void hc_ClipLeft(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	float w1=_w1, x1=_x1, w2=_w2, x2=_x2;
	float t = (w1+x1)/((w1+x1)-(w2+x2));
	r->by = LERP(t,a->by, b->by);
	r->bz = LERP(t,a->bz, b->bz);
	r->bw = LERP(t,a->bw, b->bw);
	r->bx = -r->bw;
	r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
	r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
	r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
	r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
	r->v.u = LERP(t,a->v.u, b->v.u);
	r->v.v = LERP(t,a->v.v, b->v.v);
	hc_CodePoint(r);

	if (a->q == 1.0 && b->q == 1.0)
		r->q = 1.0;
	else
		r->q = LERP(t, a->q, b->q);

}

static void hc_ClipRight(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	float w1=_w1, x1=_x1, w2=_w2, x2=_x2;
	float t = (w1-x1)/((w1-x1)-(w2-x2));
	r->by = LERP(t,a->by, b->by);
	r->bz = LERP(t,a->bz, b->bz);
	r->bw = LERP(t,a->bw, b->bw);
	r->bx = r->bw;
	r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
	r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
	r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
	r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
	r->v.u = LERP(t,a->v.u, b->v.u);
	r->v.v = LERP(t,a->v.v, b->v.v);
	hc_CodePoint(r);

	if (a->q == 1.0 && b->q == 1.0)
		r->q = 1.0;
	else
		r->q = LERP(t, a->q, b->q);

}

static void hc_ClipFront(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	float w1=_w1, z1=_z1, w2=_w2, z2=_z2;
	float t = (w1-z1)/((w1-z1)-(w2-z2));
	r->bx = LERP(t,a->bx, b->bx);
	r->by = LERP(t,a->by, b->by);
	r->bw = LERP(t,a->bw, b->bw);
	r->bz = r->bw;
	r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
	r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
	r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
	r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
	r->v.u = LERP(t,a->v.u, b->v.u);
	r->v.v = LERP(t,a->v.v, b->v.v);
	hc_CodePoint(r);

	if (a->q == 1.0 && b->q == 1.0)
		r->q = 1.0;
	else
		r->q = LERP(t, a->q, b->q);

}

static void hc_ClipBack(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	float w1=_w1,z1=_z1,w2=_w2,z2=_z2;
	float t = (w1+z1)/((w1+z1)-(w2+z2));
	r->bx = LERP(t,a->bx, b->bx);
	r->by = LERP(t,a->by, b->by);
	r->bw = LERP(t,a->bw, b->bw);
	r->bz = -r->bw;
	r->v.color.a = LERP(t,a->v.color.a, b->v.color.a);
	r->v.color.r = LERP(t,a->v.color.r, b->v.color.r);
	r->v.color.g = LERP(t,a->v.color.g, b->v.color.g);
	r->v.color.b = LERP(t,a->v.color.b, b->v.color.b);
	r->v.u = LERP(t,a->v.u, b->v.u);
	r->v.v = LERP(t,a->v.v, b->v.v);
	hc_CodePoint(r);

	if (a->q == 1.0 && b->q == 1.0)
		r->q = 1.0;
	else
		r->q = LERP(t, a->q, b->q);

}

#undef x1
#undef y1
#undef z1
#undef w1
#undef x2
#undef y2
#undef z2
#undef w2

GLboolean hc_DecideFrontface(GLcontext context, MGLVertex *a, MGLVertex *b, MGLVertex *c, GLubyte outcode)
{
	GLboolean front;
	float a1,a2,b1,b2,r;
	float aw,bw,cw;

	if (context->CullFace_State == GL_FALSE) return GL_TRUE;
	if (context->CurrentCullFace == GL_FRONT_AND_BACK) return GL_FALSE;

	/*
	** The following line returns GL_TRUE if one or more of the vertices lie beyond the
	** camera plane. This is of course a wrong assumption, but those will be culled at
	** the clipping stage after the negative W coordinates have been removed.
	*/
	if (outcode&MGL_CLIP_NEGW) return GL_TRUE;

	aw = 1.0 / a->bw;
	bw = 1.0 / b->bw;
	cw = 1.0 / c->bw;

	#define EPSILON 1e-5

	a1 = a->bx*aw - b->bx*bw;
	a2 = a->by*aw - b->by*bw;
	b1 = c->bx*cw - b->bx*bw;
	b2 = c->by*cw - b->by*bw;
	r  = a1*b2-a2*b1;

	if (fabs(a1) < EPSILON && fabs(a2) < EPSILON)
	{
		return GL_TRUE;
	}

	if (fabs(b1) < EPSILON && fabs(b2) < EPSILON)
	{
		return GL_TRUE;
	}


	if ((r < 0.0 && context->CurrentFrontFace == GL_CCW) ||
		(r > 0.0 && context->CurrentFrontFace == GL_CW))
	{
		front = GL_TRUE;
	}
	else
	{
		front = GL_FALSE;
	}

	if (context->CurrentCullFace == GL_BACK)
	{
		return front;
	}
	else
	{
		return !front;
	}
}

void GLFrontFace(GLcontext context, GLenum mode)
{
	if (mode == GL_CW || mode == GL_CCW)
	{
		context->CurrentFrontFace = mode;
	}
	else
	{
		GLFlagError(context, 1, GL_INVALID_ENUM);
	}
}

void GLCullFace(GLcontext context, GLenum mode)
{
	if (mode == GL_FRONT || mode == GL_FRONT_AND_BACK || mode == GL_BACK)
	{
		context->CurrentCullFace = mode;
	}
	else
	{
		GLFlagError(context, 1, GL_INVALID_ENUM);
	}
}

/*
** Complicated clipping macro stuff.
*/

#define VERTP(i) &(context->VertexBuffer[a->verts[i]])
#define VERT(i) context->VertexBuffer[a->verts[i]]
#define POLYSWAP \
	if (b->numverts == 0) return; \
	temp=a; a=b; b=temp; \

#define DOCLIP(edge, routine)                                           \
	if (or_codes & edge)                                                 \
	{                                                                     \
		b->numverts = 0;                                                   \
		prev = a->numverts-1;                                               \
		for (i=0; i<a->numverts; i++)                                        \
		{                                                                     \
			/* Case 1 and 4*/                                                  \
			if (!(VERT(prev).outcode & edge))                                   \
			{                                                                    \
				b->verts[b->numverts] = a->verts[prev];                           \
				b->numverts++;                                                     \
			}                                                                       \
			/* Case 3 and 4 */                                                       \
			if ((VERT(prev).outcode ^ VERT(i).outcode) & edge)                        \
			{                                                                          \
				hc_##routine (VERTP(prev), VERTP(i), &(context->VertexBuffer[free]));   \
				b->verts[b->numverts]=free++;                                            \
				b->numverts++;                                                            \
			}                                                                              \
			prev = i;                                                                       \
		}                                                                                    \
		POLYSWAP                                                                              \
	}                                                                                          \


extern void dh_DrawPoly(GLcontext context, MGLPolygon *poly);
extern void dh_DrawPolyFF(GLcontext context, MGLPolygon *poly);


void hc_ClipAndDrawPoly(GLcontext context, MGLPolygon *poly, GLubyte or_codes)
{
	/*
	** Sutherland-Hodgeman clipping algorithm (almost)
	**
	** This clipping algorithm sucessively clips against each of the six
	** clipping planes (additional client-defined clipping planes would
	** be possible, those would be added to the back of this).
	** Vertices are copied from a to b and swapped at the end.
	** Output occurs within the clipping region:
	**
	**                | b
	**               i|/|
	**               /| |
	**              / | |c
	**            a/  |/
	**             | /|j
	**             |/ |
	**            d/  |
	**                |clip plane
	**
	** In the above figure, the algorithm first consideres edge d-a. Since it
	** does not cross the clipping plane, it outputs d and proceeds to edge
	** a-b. Since it crosses, it outputs a, calculates intersection i and outputs it.
	** No output occurs while b-c is considered, since it lies outside the frustum
	** and does not cross it. Finally, edge c-d yields output j.
	**
	** The result is d-a-i-j
	**
	** Classification of edges are divided into four cases:
	** Case 1: Edge is completely inside -> two vertices
	** Case 2: Edge is completely outside -> no output
	** Case 3: Edge enters the frustum -> one output
	** Case 4: Edge leaves frustum -> two outputs
	**
	** At any stage, if the output polygon has zero vertices, return immediately.
	*/

	MGLPolygon output;
	MGLPolygon *a, *b, *temp;
	int i,j;
	int prev;
	int free = context->VertexBufferPointer;
	GLboolean flag;
	GLubyte original_or_codes = or_codes;

	a = poly; b=&output;

	DOCLIP(MGL_CLIP_NEGW, ClipWZero);

	for (j=0;j<a->numverts; j++) or_codes |= context->VertexBuffer[a->verts[j]].outcode;

	DOCLIP(MGL_CLIP_LEFT, ClipLeft)
	DOCLIP(MGL_CLIP_RIGHT, ClipRight)
	DOCLIP(MGL_CLIP_FRONT, ClipFront)
	DOCLIP(MGL_CLIP_BACK, ClipBack)
	DOCLIP(MGL_CLIP_TOP, ClipTop)
	DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)

	if ((original_or_codes & MGL_CLIP_NEGW) && a->numverts>2)
	{
		flag = hc_DecideFrontface(context,
			&(context->VertexBuffer[a->verts[0]]),
			&(context->VertexBuffer[a->verts[1]]),
			&(context->VertexBuffer[a->verts[2]]), 0);
		if (flag == GL_FALSE)
			return;
	}

	// If we get here, there are vertices left...
	dh_DrawPoly(context, a);
}

void hc_ClipAndDrawPolyFF(GLcontext context, MGLPolygon *poly, GLubyte or_codes)
{
	MGLPolygon output;
	MGLPolygon *a, *b, *temp;
	int i,j;
	int prev;
	int free = context->VertexBufferPointer;

	a = poly; b=&output;

	DOCLIP(MGL_CLIP_NEGW, ClipWZero);

	for (j=0;j<a->numverts; j++) or_codes |= context->VertexBuffer[a->verts[j]].outcode;

	DOCLIP(MGL_CLIP_LEFT, ClipLeft)
	DOCLIP(MGL_CLIP_RIGHT, ClipRight)
	DOCLIP(MGL_CLIP_FRONT, ClipFront)
	DOCLIP(MGL_CLIP_BACK, ClipBack)
	DOCLIP(MGL_CLIP_TOP, ClipTop)
	DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)


	// If we get here, there are vertices left...
	dh_DrawPolyFF(context, a);
}

extern void dh_DrawLine(GLcontext context, MGLPolygon *poly);

void hc_ClipAndDrawLine(GLcontext context, MGLPolygon *poly, GLubyte or_codes)
{
    MGLPolygon output;
    MGLPolygon *a, *b, *temp;
    int i,j;
    int prev;
    int free = context->VertexBufferPointer;

    a = poly; b=&output;

    DOCLIP(MGL_CLIP_NEGW, ClipWZero);

    for (j = 0; j < a->numverts; j++)
	or_codes |= context->VertexBuffer[a->verts[j]].outcode;

    DOCLIP(MGL_CLIP_LEFT, ClipLeft)
    DOCLIP(MGL_CLIP_RIGHT, ClipRight)
    DOCLIP(MGL_CLIP_FRONT, ClipFront)
    DOCLIP(MGL_CLIP_BACK, ClipBack)
    DOCLIP(MGL_CLIP_TOP, ClipTop)
    DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)

    dh_DrawLine(context,a);
}