/*

------------------------------------------------------------------

Black Nebula

File :				Clip.c
Programmer:		Colin Adams
Date:				23/4/91
Last Modified :	10/6/91

------------------------------------------------------------------

*/

#include "3d.h"
#include <proto/dos.h>

#define BOUNDARY_COUNT 4
#define MAX_LIMIT 500


extern short U_rot, W_rot, View_Angle;
extern short num_active[];

static point s[BOUNDARY_COUNT], first_point[BOUNDARY_COUNT];
static short new_edge[BOUNDARY_COUNT];
static polygon *clip_poly;
static object *sort_obj; /* global for sort */
static point clip_point;
static int Depth[TOTAL_MAX_OBJECTS]; /* array to sort in */

static int xp[3], yp[3], zp[3];

enum
{
	TOP,
	RIGHT,
	BOTTOM,
	LEFT
};

/*	------------------------------------------------------------------
		Fast Square Root Code for IEEE floating point numbers
		from Graphics Gems, Academic Press 1990
		
		Supplied by Peter Stephenson
		------------------------------------------------------------------
*/

static short sqrttab[0x100];

void build_table(void)
{
	unsigned short i;
	float f;
	unsigned int *fi = (int *) &f;
	
	for(i=0; i<= 0x7f; i++)
	{
		/* build a float with the bit pattern i as
		mantissa and an exponent of 0, stored as 127 */
		
		*fi = (i << 16) | ( 127 << 23);
		f = sqrt(f);
		
		/* take the square root then strip the first 7 bits of the
		mantissa into the table */
		
		sqrttab[i] = (*fi & 0x7fffff) >> 16;
		
		/* repeat the process, this time with an exponent of 1,
		stored as 128 */
		
		*fi = (i << 16) | (128 << 23);
		f = sqrt(f);
		
		sqrttab[i+0x80] = (*fi & 0x7fffff) >> 16;
	}
}

float fsqrt(float n)
{
	unsigned int *num = (int *) &n;
	short e;
	
	if(n==0) return 0;
	
	e = (*num >> 23) - 127;
	
	*num &= 0x7fffff;
	
	if(e & 0x01)
		*num |= 0x800000;
		
	e >>= 1;
	
	*num = ((sqrttab[*num >> 16]) << 16) | ((e + 127) << 23);
	return n;
}

/*	------------------------------------------------------------------
		Clipping Routines
		
		The clipping algorithm is Sutherland and Hodgeman's.  The
		description of the algorithm is in Computer Graphics by
		D. Hearn & M. Baker.
		------------------------------------------------------------------
*/

short inside(point *p, short edge)
/* returns true if the point is inside the given edge, false if not */
{
	switch(edge)
	{
		case TOP:	/* top line */
			if(p->y >= Y_MIN)
				return 1;
			return 0;
		case RIGHT:	/* right hand side */
			if(p->x <= X_MAX)
				return 1;
			return 0;
		case BOTTOM:	/* bottom line */
			if(p->y <= Y_MAX)
				return 1;
			return 0;
		case LEFT:	/* left hand side */
			if(p->x >= X_MIN)
				return 1;
			return 0;
	}	
}


short cross(point *p, point *p2, short edge)
/* returns true if the 2 points cross the given edge */
{
	/*
	
	This first bit is a slight hack to make points generated a mile
	apart when on the other side of the eye, not appear! May or may
	not be fixed.
	
	2/6/91
	
	It is now very unlikely to be fixed, as I don't think it
	can be!!  But it seems to work...
	
	*/

	if(abs(p->x) > MAX_LIMIT || abs(p2->x) > MAX_LIMIT ||
		abs(p->y) > MAX_LIMIT || abs(p2->y) > MAX_LIMIT)
		return 0;

	/* end of horrible speed reducing hack */
	
	switch(edge)
	{
		case TOP: /* top edge */
			if(p->y > Y_MIN)
			{
				if(p2->y <= Y_MIN)
					return 1;
			}
			else if(p2->y > Y_MIN)
				return 1;
			return 0;
			
		case RIGHT: /* right hand edge */
			if(p->x > X_MAX)
			{
				if(p2->x <= X_MAX)
					return 1;
			}
			else if(p2->x > X_MAX)
				return 1;
			return 0;
		
		case BOTTOM: /* bottom edge */
			if(p->y > Y_MAX)
			{
				if(p2->y <= Y_MAX)
					return 1;
			}
			else if(p2->y > Y_MAX)
				return 1;
			return 0;
	
		case LEFT: /* left hand edge */
			if(p->x > X_MIN)
			{
				if(p2->x <= X_MIN)
					return 1;
			}
			else if(p2->x > X_MIN)
				return 1;
			return 0;
	}
}

void find_intersection(point *p1, point *p2, short edge, point *i)
/*
Find intersection point of line, uses fixed point maths.  This routine
is heavily optimized, requiring only 1 integer division and 1 integer
multiplication to find the intersection!!!  If you know a faster
method please tell me!
*/
{
	register int mnumer, mdenom;
	
	/* get gradient */
	
	mnumer = (p2->y - p1->y);
	mdenom = (p2->x - p1->x);
	
	switch(edge)
	{
		case TOP:
		{
			register int j = Y_MIN - p1->y;
			i->y = Y_MIN;
			i->x = p1->x + (mnumer ? (j * mdenom) / mnumer : 0);
			return;
		}		
		case RIGHT:
		{
			register int j = (X_MAX - p1->x);
			i->x = X_MAX;
			i->y = p1->y + (mdenom ? (mnumer*j)/mdenom : 0);
			return;
		}
		case BOTTOM:
		{
			register int j = Y_MAX - p1->y;
			i->y = Y_MAX;
			i->x = p1->x + (mnumer ? (j * mdenom) / mnumer : 0);
			return;
		}		
		case LEFT:
		{
			register int j = (X_MIN - p1->x);
			i->x = X_MIN;
			i->y = p1->y + (mdenom ? (mnumer*j)/mdenom : 0);
			return;
		}
	}
}

void clip_this(point *p, short edge)
/* recursively checks a point against all the boundary edges */
{
	point i;
	
	if(new_edge[edge])
	{
		first_point[edge].x = p->x;
		first_point[edge].y = p->y;
		new_edge[edge] = 0;
	}
	else if(cross(p, &s[edge], edge))
	{
		find_intersection(p, &s[edge], edge, &i);
		
		if(edge < 3)
			clip_this(&i, edge+1);
		else
		{
			clip_poly->clip_num++;
			clip_poly->clip_x[clip_poly->clip_num] = i.x;
			clip_poly->clip_y[clip_poly->clip_num] = i.y;
		}	
	}
	
	s[edge].x = p->x;
	s[edge].y = p->y;
	
	if(inside(p, edge))
	{
		if(edge < 3)
			clip_this(p, edge+1);
		else
		{
			clip_poly->clip_num++;
			clip_poly->clip_x[clip_poly->clip_num] = p->x;
			clip_poly->clip_y[clip_poly->clip_num] = p->y;
		}
	}
}

void clip_closer(void)
/*
Closing routine. For each window edge, clips the line connecting
the last saved vertex and the first_point processed against the
edge
*/
{
	point i;
	register short edge;
	
	for(edge=0; edge<BOUNDARY_COUNT; edge++)
	{
		if(cross(&s[edge], &first_point[edge], edge))
		{
			find_intersection(&s[edge], &first_point[edge],edge,&i);
			
			if(edge<3)
				clip_this(&i, edge+1);
			else
			{
				clip_poly->clip_num++;
				clip_poly->clip_x[clip_poly->clip_num] = i.x;
				clip_poly->clip_y[clip_poly->clip_num] = i.y;
			}
		}
	}
}

void polygon_clip(polygon *poly)
/* clips the polygon sent against the boundaries */
{
	register int k;

	clip_poly = poly;			/* use a global for speed */
	clip_poly->clip_num = -1; /* no points in output yet */
		
	for(k=0; k<4; k++)
		new_edge[k] = 1;

	for(k=0; k<clip_poly->numpoints; k++)
	{
		clip_point.x = clip_poly->x[k];
		clip_point.y = clip_poly->y[k];
		clip_this(&clip_point, 0);
	}
	clip_closer(); /* close polygon */
	clip_poly->clip_num++;
}
	
/*	------------------------------------------------------------------
		Hidden Surface Routines
		
		Determines the order to draw objects, and polygons within
		an object
		------------------------------------------------------------------
*/


int SpinPolyCentre(object *obj, polygon *poly)
/*
Spin a point and calculate it's depth from the eye.  The point
is the centre point of a polygon, and is used for hidden surface
removal.  This routine should be pretty quick, but if you know a
faster algorithm, I'd love to know it!
*/
{
	register int x,y,z;
	register int xrot, yrot, zrot;
		
	xrot = obj->rot_x;
	yrot = obj->rot_y;
	zrot = obj->rot_z;
		
	x = poly->centre.x;
	y = poly->centre.y;
	z = poly->centre.z;

	/* rotate a point around the z axis */
		
	if(zrot)
	{
		register int temp, temp2, temp3;
		temp = x;
		temp2 = costable[zrot];
		temp3 = sintable[zrot];
			
		x = ((temp2*temp)>>16) - ((temp3*y)>>16);
		y = ((temp3*temp)>>16) + ((temp2*y)>>16);
	}
		
	/* rotate a point around the x axis */
		
	if(xrot)
	{
		register int temp, temp2, temp3;
		temp = y;
		temp2 = costable[xrot];
		temp3 = sintable[xrot];
			
		y = ((temp2*temp)>>16) - ((temp3*z)>>16);
		z = ((temp3*temp)>>16) + ((temp2*z)>>16);
	}
		
	/* rotate a point around the y axis */
		
	if(yrot)
	{
		register int temp, temp2, temp3;
		temp = z;
		temp2 = costable[yrot];
		temp3 = sintable[yrot];
			
		z = ((temp2*temp)>>16) - ((temp3*x)>>16);
		x = ((temp3*temp)>>16) + ((temp2*x)>>16);
	}
		
	/* calculate depths */
		
	x = ex - (x + obj->trans_x);
	y = ey - (y + obj->trans_y);
	z = ez - (z + obj->trans_z);
	
	return (x*x + y*y + z*z);
}	

void qsort_poly(int *left, int *right, int al, int ar)
/*
Quicksort for polygon depths within an object.  This can be written 
faster.
*/
{
	register int *p = left, *q = right, x = *(left+(right-left)/2), w;
	register int tar = ar, tal = al;
	
	do
	{
		while(*p>x)
		{
			p++; tal++;
		}
		
		while(*q<x)
		{
			q--; tar--;
		}
			
		if(p>q) break;

		w = *p;
		*p = *q;
		*q = w;
		
		{
			register polygon *temp;
			temp = sort_obj->draworder[tar];
			sort_obj->draworder[tar] = sort_obj->draworder[tal];
			sort_obj->draworder[tal] = temp;
		}
		
		p++; q--;
		tal++; tar--;
		
	} while (p<=q);

	if(left<q) qsort_poly(left, q, al, tar);
	if(p<right) qsort_poly(p, right, tal, ar);
}

void DepthSort(object *obj)
/* sorts an object's polygons into depths from the eye to determine
the order in which they are to be drawn */
{
	register polygon *pg = obj->poly;
	register short count = 0;
	register char oneobj = 0;
	
	if(!obj->poly->next)
		oneobj = 1;
	
	while(pg)
	{
		obj->draworder[count] = pg;
		
		/* NB. as an optimization, the actual distance from the eye is
		not stored but the square of it is, so the magnitude is
		relevant! */

		/*
		
		Check for back faces, this is the only way to make my
		hidden surface code work properly... I really didn't want to
		add this, but doesn't seem to slow down the code much as
		it doesn't draw/erase polygons which are back faces.
		
		Unfortunately it still sorts faces which aren't visible,
		should be fixed!
		
		*/
		
		if(pg->numpoints>2  && !oneobj)
		{
			register int i, A, B, C, D;
			
			for(i=0; i<3; i++)
			{
				xp[i] = manipulate_x[pg->p[i]];
				yp[i] = manipulate_y[pg->p[i]];
				zp[i] = manipulate_z[pg->p[i]];
			}
			
			/* horrible plane equation calculations */
			
			A = yp[0]*(zp[1]-zp[2]) + yp[1]*(zp[2]-zp[0]) + yp[2]*(zp[0]-zp[1]);
			B = zp[0]*(xp[1]-xp[2]) + zp[1]*(xp[2]-xp[0]) + zp[2]*(xp[0]-xp[1]);
			C = xp[0]*(yp[1]-yp[2]) + xp[1]*(yp[2]-yp[0]) + xp[2]*(yp[0]-yp[1]);
			D = - xp[0]*(yp[1]*zp[2] - yp[2]*zp[1]) - xp[1]*(yp[2]*zp[0] - yp[0]*zp[2])
				- xp[2]*(yp[0]*zp[1] - yp[1]*zp[0]);
				
			if((ex*A + ey*B + ez*C + D)<0)
			{
				pg->back_face = 1;
				pg->clip_num = 0;
			}
			else
			{
				pg->back_face = 0;
			}
				
		}
		else
			pg->back_face = 0;
		
		Depth[count++] = pg->back_face ? 0 : SpinPolyCentre(obj, pg);
		pg = (polygon *) pg->next;
	}

	obj->draworder[count] = NULL; /* terminate list */

	sort_obj = obj;
	if(count)
		qsort_poly(Depth, &Depth[count-1], 0, count-1);
		
}

/* Object sorting routines */

double rad(double degrees)
/* converts degrees to radians */
{
	double one8 = 180;
	return 3.141592654/(one8/degrees);
}

int GetAngle(int *h, short px, short py, short pz)
{
	register int o, angle, tempint;
	register char quad;
	int temp;
	float depth, temp2;
	int d;
	
	tempint = ex-px;
	depth = tempint * tempint;
	tempint = ez - pz;
	depth += tempint * tempint;
	tempint = ey - py;
	*h = depth + tempint * tempint;

	if(px>ex)
	{
		o = px - ex;
		if(pz>ez)
			quad = 4;
		else
		{
			if(pz==ez) return 0;
			quad = 1;
		}
	}
	else
	{
		if(px==ex)
		{
			if(pz<ez)
				return 90;
			else
				return 270;
		}
		
		o = ex - px;
		
		if(pz>ez)
			quad = 3;
		else
		{
			if(pz==ez) return 180;
			quad = 2;
		}
	}
	
	temp = o * 4096;
	temp2 = fsqrt(depth);
	
	d = temp/temp2;
	
	if(d>4096) d = 4096; /* to fix small errors which make d > 4096 */
	
	angle = anti_sin[d];
	
	switch(quad)
	{
		case 1: angle = 90 - angle; break;
		case 2: angle = 90 + angle; break;
		case 3: angle = 180 + (90-angle); break;
		case 4: angle += 270; break;
	}
	return angle;
}


int SpinObjCentre(object *obj)
{
	register int x,y,z;
	register short angle;
	int distance;
	
	x = obj->trans_x + obj->centre_x;
	y = obj->trans_y + obj->centre_y;
	z = obj->trans_z + obj->centre_z;
	
	angle = GetAngle(&distance, x, y, z);

	/* tries to eliminate objects which aren't in the field of view */
	
	if(View_Angle>=45)
	{
		if(View_Angle<=315)
		{
			if(angle>View_Angle+45 || angle<View_Angle-45)
				obj->drawme = 0;
		}
		else
		{
			if(angle<View_Angle-45 && angle>View_Angle-315)
				obj->drawme = 0;
		}
	}
	else
	{
		if(angle>View_Angle+45 && angle<View_Angle+315)
			obj->drawme = 0;
	}

	/* check if I hit something */
	
	if(distance<(obj->radius*5+500) && obj->type<MYMISSILE)
	{
		obj->i_am_dying = 1; /* kill enemy too! */
		obj->explode = 1;
		am_i_dead = 1;
	}
		
	return distance;
}

void qsort_depth(int *left, int *right, int al, int ar)
/* quicksort objects into drawing order */
{
	register int *p = left, *q = right, x = *(left+(right-left)/2), w;
	register int tar = ar, tal = al;
	
	do
	{
		while(*p>x)
		{
			p++; tal++;
		}
		
		while(*q<x)
		{
			q--; tar--;
		}
			
		if(p>q) break;

		w = *p;
		*p = *q;
		*q = w;
		
		{
			register object *temp;
			temp = active_list[tar];
			active_list[tar] = active_list[tal];
			active_list[tal] = temp;
		}
		
		p++; q--;
		tal++; tar--;
		
		
	} while (p<=q);

	if(left<q) qsort_depth(left, q, al, tar);
	if(p<right) qsort_depth(p, right, tal, ar);
}

void CalculateObjects(void)
/* sorts the objects into depths from the eye to determine
the order in which they are to be drawn
*/
{
	register short i,j;
	
	/*
	kills off objects which are floating around in a dead state but
	aren't totally removed from the system yet
	*/
	
	for(i=0; i<no_objects; i++)
	{
		while(i<no_objects && active_list[i]->i_am_dying)
		{
			if(active_list[i]->explode &&	active_list[i]->i_am_dying==1)
				CreateExplosion(active_list[i]);
			
			if(active_list[i]->i_am_dying++>2)
			{
				if(active_list[i]->type==EXPLOSION)
				{
					for(j=0; j<MAX_EXPLOSIONS; j++)
					{
						if(active_list[i] == &explosions[j])
						{
							exp_free[j] = 0;
							break;
						}
					}
				}
				else
				{
					for(j=0; j<MAX_OBJECTS; j++)
					{
						if(active_list[i] == &obj_types[active_list[i]->type][j])
						{
							obj_free[active_list[i]->type][j] = 0;
							break;
						}
					}
				}
				
				num_active[active_list[i]->type]--;
				
				for(j=i; j<no_objects-1; j++)
					active_list[j] = active_list[j+1];
			
				no_objects--;
			}
			else
			{
				active_list[i]->drawme = 0;
				break;
			}
		}
		
		if(i<no_objects)
		{
			if(active_list[i]->drawme)
				PrepareObject(active_list[i]);
		}
	}
	
	for(i=0; i<no_objects; i++)
		Depth[i] = SpinObjCentre(active_list[i]);

	qsort_depth(Depth, &Depth[no_objects-1], 0, no_objects-1);
	
}

void ClearObjects(void)
/* destroys the old image */
{
	register int i;
	
	for(i=0; i<no_objects; i++)
			EraseObject(active_list[i]);
}

void DisplayObjects(void)
{
	register int i;
	for(i=0; i<no_objects; i++)
		DrawObject(active_list[i]);
}
		
/* end of module clip.c */