/*
 * $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
 *
 */

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

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

#define DUMP_VERTEX(vert) \
 mykprintf("x:%6.3f y:%6.3f z:%6.3f w:%6.3f\nR:%6.3f G:%6.3f B:%6.3f A:%6.3f\nU:%6.3f V:%6.3f\noutcode=0x%X\n",\
		 (vert).bx, (vert).by, (vert).bz, (vert).bw,                                                                                      \
		 (vert).v.color.r, (vert).v.color.g, (vert).v.color.b, (vert).v.color.a,                                                          \
		 (vert).v.u, (vert).v.v, (vert).outcode)


#define LERP(t,a,b) \
	(a) + (float)t * ( (b) - (a) )

#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->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;
	v->outcode = 0;

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

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

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

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

#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)

#ifdef GLNDEBUG
#define DEBUG_CLIP(name,code) code
#else
#define DEBUG_CLIP(name,code) \
	mykprintf("%s: t=%f\n", #name, t);\
	DUMP_VERTEX(*a); \
	DUMP_VERTEX(*b); \
	code             \
	DUMP_VERTEX(*r);
#endif

static void hc_ClipWZero(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	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);
}

static void hc_ClipTop(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	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);
}

static void hc_ClipBottom(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	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);
}

static void hc_ClipLeft(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	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);
}

static void hc_ClipRight(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	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);
}

static void hc_ClipFront(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	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);
}

static void hc_ClipBack(MGLVertex *a, MGLVertex *b, MGLVertex *r)
{
	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);
}

#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);

#ifndef GLNDEBUG
void hc_DumpPolygon(GLcontext context, MGLPolygon *poly, char *string, int clipcode)
{
	int i;
	mykprintf("--- %s (0x%X) -- (%d vertices)\n", string,clipcode, poly->numverts);
	for (i=0; i<poly->numverts; i++)
	{
		DUMP_VERTEX(context->VertexBuffer[poly->verts[i]]);
	}
	mykprintf("-------------------------\n");
}

#define CLIPDBG(string,code) \
	hc_DumpPolygon(context,a,#string,code);

#else

#define CLIPDBG(string,code)

#endif


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;

	CLIPDBG(ClipWZero, MGL_CLIP_NEGW)
	DOCLIP(MGL_CLIP_NEGW, ClipWZero);

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

	CLIPDBG(ClipLeft, MGL_CLIP_LEFT)
	DOCLIP(MGL_CLIP_LEFT, ClipLeft)

	CLIPDBG(ClipRight, MGL_CLIP_RIGHT)
	DOCLIP(MGL_CLIP_RIGHT, ClipRight)

	CLIPDBG(ClipFront, MGL_CLIP_FRONT)
	DOCLIP(MGL_CLIP_FRONT, ClipFront)

	CLIPDBG(ClipBack, MGL_CLIP_BACK)
	DOCLIP(MGL_CLIP_BACK, ClipBack)

	CLIPDBG(ClipTop, MGL_CLIP_TOP)
	DOCLIP(MGL_CLIP_TOP, ClipTop)

	CLIPDBG(ClipBottom, MGL_CLIP_BOTTOM)
	DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)

	CLIPDBG(Final,0)
	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;

	CLIPDBG(ClipWZero, MGL_CLIP_NEGW)
	DOCLIP(MGL_CLIP_NEGW, ClipWZero);

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

	CLIPDBG(ClipLeft, MGL_CLIP_LEFT)
	DOCLIP(MGL_CLIP_LEFT, ClipLeft)

	CLIPDBG(ClipRight, MGL_CLIP_RIGHT)
	DOCLIP(MGL_CLIP_RIGHT, ClipRight)

	CLIPDBG(ClipFront, MGL_CLIP_FRONT)
	DOCLIP(MGL_CLIP_FRONT, ClipFront)

	CLIPDBG(ClipBack, MGL_CLIP_BACK)
	DOCLIP(MGL_CLIP_BACK, ClipBack)

	CLIPDBG(ClipTop, MGL_CLIP_TOP)
	DOCLIP(MGL_CLIP_TOP, ClipTop)

	CLIPDBG(ClipBottom, MGL_CLIP_BOTTOM)
	DOCLIP(MGL_CLIP_BOTTOM, ClipBottom)

	CLIPDBG(Final,0)

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