// brush.c

#include "bsp5.h"

int			numbrushplanes;
plane_t		planes[max_map_planes];

int			numbrushfaces;
mface_t		faces[128];		// beveled clipping hull can generate many extra

//jim
	entity_t *currententity;

/*
=================
checkface

note: this will not catch 0 area polygons
=================
*/
void checkface (face_t *f)
{
	int		i, j;
	vec_t	*p1, *p2;
	vec_t	d, edgedist;
	vec3_t	dir, edgenormal, facenormal;

	if (f->numpoints < 3)
		error ("checkface: %i points",f->numpoints);

	vectorcopy (planes[f->planenum].normal, facenormal);
	if (f->planeside)
	{
		vectorsubtract (vec3_origin, facenormal, facenormal);
	}

	for (i=0 ; i<f->numpoints ; i++)
	{
		p1 = f->pts[i];

		for (j=0 ; j<3 ; j++)
			if (p1[j] > bogus_range || p1[j] < -bogus_range)
				error ("checkface: bugus_range: %f",p1[j]);

		j = i+1 == f->numpoints ? 0 : i+1;

	// check the point is on the face plane
		d = dotproduct (p1, planes[f->planenum].normal) - planes[f->planenum].dist;
//      if (d < -on_epsilon || d > on_epsilon)
//         error ("checkface: point off plane");
//med
      if (d < -1 || d > 1)
         error ("checkface: point off plane d=%f",d);

	// check the edge isn't degenerate
		p2 = f->pts[j];
		vectorsubtract (p2, p1, dir);

		if (vectorlength (dir) < on_epsilon)
			error ("checkface: degenerate edge");

		crossproduct (facenormal, dir, edgenormal);
		vectornormalize (edgenormal);
		edgedist = dotproduct (p1, edgenormal);
		edgedist += on_epsilon;

	// all other points must be on front side
		for (j=0 ; j<f->numpoints ; j++)
		{
			if (j == i)
				continue;
			d = dotproduct (f->pts[j], edgenormal);
			if (d > edgedist)
				error ("checkface: non-convex");
		}
	}
}


//===========================================================================

/*
=================
clearbounds
=================
*/
void clearbounds (brushset_t *bs)
{
	int		i, j;

	for (j=0 ; j<num_hulls ; j++)
		for (i=0 ; i<3 ; i++)
		{
			bs->mins[i] = 99999;
			bs->maxs[i] = -99999;
		}
}

/*
=================
addtobounds
=================
*/
void addtobounds (brushset_t *bs, vec3_t v)
{
	int		i;

	for (i=0 ; i<3 ; i++)
	{
		if (v[i] < bs->mins[i])
			bs->mins[i] = v[i];
		if (v[i] > bs->maxs[i])
			bs->maxs[i] = v[i];
	}
}

//===========================================================================

int	planetypefornormal (vec3_t normal)
{
	float	ax, ay, az;

// note: should these have an epsilon around 1.0?
	if (normal[0] == 1.0)
		return plane_x;
	if (normal[1] == 1.0)
		return plane_y;
	if (normal[2] == 1.0)
		return plane_z;
	if (normal[0] == -1.0 ||
		normal[1] == -1.0 ||
		normal[2] == -1.0)
		error ("planetypefornormal: not a canonical vector");

	ax = fabs(normal[0]);
	ay = fabs(normal[1]);
	az = fabs(normal[2]);

	if (ax >= ay && ax >= az)
		return plane_anyx;
	if (ay >= ax && ay >= az)
		return plane_anyy;
	return plane_anyz;
}

#define	distepsilon		0.01
#define	angleepsilon	0.00001

void normalizeplane (plane_t *dp)
{
	vec_t	ax, ay, az;

	if (dp->normal[0] == -1.0)
	{
		dp->normal[0] = 1.0;
		dp->dist = -dp->dist;
	}
	if (dp->normal[1] == -1.0)
	{
		dp->normal[1] = 1.0;
		dp->dist = -dp->dist;
	}
	if (dp->normal[2] == -1.0)
	{
		dp->normal[2] = 1.0;
		dp->dist = -dp->dist;
	}

	if (dp->normal[0] == 1.0)
	{
		dp->type = plane_x;
		return;
	}
	if (dp->normal[1] == 1.0)
	{
		dp->type = plane_y;
		return;
	}
	if (dp->normal[2] == 1.0)
	{
		dp->type = plane_z;
		return;
	}

	ax = fabs(dp->normal[0]);
	ay = fabs(dp->normal[1]);
	az = fabs(dp->normal[2]);

	if (ax >= ay && ax >= az)
		dp->type = plane_anyx;
	else if (ay >= ax && ay >= az)
		dp->type = plane_anyy;
	else
		dp->type = plane_anyz;
	if (dp->normal[dp->type-plane_anyx] < 0)
	{
		vectorsubtract (vec3_origin, dp->normal, dp->normal);
		dp->dist = -dp->dist;
	}

}

/*
===============
findplane

returns a global plane number and the side that will be the front
===============
*/
int	findplane (plane_t *dplane, int *side)
{
	int			i;
	plane_t		*dp, pl;
	vec_t		dot;

	dot = vectorlength(dplane->normal);
	if (dot < 1.0 - angleepsilon || dot > 1.0 + angleepsilon)
		error ("findplane: normalization error");

	pl = *dplane;
	normalizeplane (&pl);
	if (dotproduct(pl.normal, dplane->normal) > 0)
		*side = 0;
	else
		*side = 1;

	dp = planes;
	for (i=0 ; i<numbrushplanes;i++, dp++)
	{
		dot = dotproduct (dp->normal, pl.normal);
		if (dot > 1.0 - angleepsilon
		&& fabs(dp->dist - pl.dist) < distepsilon )
		{	// regular match
			return i;
		}
	}

	if (numbrushplanes == max_map_planes)
		error ("numbrushplanes == max_map_planes");

	planes[numbrushplanes] = pl;

	numbrushplanes++;

	return numbrushplanes-1;
}


/*
===============
findplane_old

returns a global plane number and the side that will be the front
===============
*/
int	findplane_old (plane_t *dplane, int *side)
{
	int			i;
	plane_t		*dp;
	vec_t		dot, ax, ay, az;

	dot = vectorlength(dplane->normal);
	if (dot < 1.0 - angleepsilon || dot > 1.0 + angleepsilon)
		error ("findplane: normalization error");

	dp = planes;

	for (i=0 ; i<numbrushplanes;i++, dp++)
	{
		dot = dotproduct (dplane->normal, dp->normal);
		if (dot > 1.0 - angleepsilon
		&& fabs(dplane->dist - dp->dist) < distepsilon )
		{	// regular match
			*side = 0;
			return i;
		}
		if (dot < -1.0+angleepsilon
		&& fabs(dplane->dist + dp->dist) < distepsilon )
		{	// inverse of vector
			*side = 1;
			return i;
		}
	}

// allocate a new plane, flipping normal to a consistant direction
// if needed
	*dp = *dplane;

	if (numbrushplanes == max_map_planes)
		error ("numbrushplanes == max_map_planes");
	numbrushplanes++;

	*side = 0;

// note: should these have an epsilon around 1.0?
	if (dplane->normal[0] == 1.0)
		dp->type = plane_x;
	else if (dplane->normal[1] == 1.0)
		dp->type = plane_y;
	else if (dplane->normal[2] == 1.0)
		dp->type = plane_z;
	else if (dplane->normal[0] == -1.0)
	{
		dp->type = plane_x;
		dp->normal[0] = 1.0;
		dp->dist = -dp->dist;
		*side = 1;
	}
	else if (dplane->normal[1] == -1.0)
	{
		dp->type = plane_y;
		dp->normal[1] = 1.0;
		dp->dist = -dp->dist;
		*side = 1;
	}
	else if (dplane->normal[2] == -1.0)
	{
		dp->type = plane_z;
		dp->normal[2] = 1.0;
		dp->dist = -dp->dist;
		*side = 1;
	}
	else
	{
		ax = fabs(dplane->normal[0]);
		ay = fabs(dplane->normal[1]);
		az = fabs(dplane->normal[2]);

		if (ax >= ay && ax >= az)
			dp->type = plane_anyx;
		else if (ay >= ax && ay >= az)
			dp->type = plane_anyy;
		else
			dp->type = plane_anyz;
		if (dplane->normal[dp->type-plane_anyx] < 0)
		{
			vectorsubtract (vec3_origin, dp->normal, dp->normal);
			dp->dist = -dp->dist;
			*side = 1;
		}
	}

	return i;
}



/*
=============================================================================

			turn brushes into groups of faces

=============================================================================
*/

vec3_t		brush_mins, brush_maxs;
face_t		*brush_faces;

//jim
entity_t *findtargetentity( char *targetname )
	{
	int			entnum;
	entity_t	*ent;

	for (entnum = 0 ; entnum < num_entities ; entnum++)
		{
		ent = &entities[entnum];
		if ( !strcmp( targetname, valueforkey ( ent, "targetname" ) ) )
			{
			return ent;
			}
		}
	return null;
	}

/*
=================
createbrushfaces
=================
*/
#define	zero_epsilon	0.001
void createbrushfaces (void)
{
	int				i,j, k;
	vec_t			r;
	face_t			*f;
	winding_t		*w;
	plane_t			plane;
	mface_t			*mf;
//jim
   vec3_t         offset;
   char           *classname;
	vec3_t			point;
   vec_t          max;
   vec_t          min;

   //jim
	offset[ 0 ] = offset[ 1 ] = offset[ 2 ] = 0;
   brush_mins[0] = brush_mins[1] = brush_mins[2] = 99999;
	brush_maxs[0] = brush_maxs[1] = brush_maxs[2] = -99999;

	brush_faces = null;

   //jim
   classname = valueforkey ( currententity, "classname" );
	if ( !strncmp( classname, "rotate_", 7 ) )
		{
		entity_t	*foundentity;
		char 		*searchstring;
		char		 text[20];

		searchstring = valueforkey ( currententity, "target" );
		foundentity = findtargetentity( searchstring );
		if ( foundentity )
			{
			getvectorforkey( foundentity, "origin", offset );
			//printf( "**** shifting entity '%s' by %f, %f, %f\n",
			//	classname, offset[ 0 ], offset[ 1 ], offset[ 2 ] );
			}

		sprintf( text, "%d %d %d", (int)offset[ 0 ],
			(int)offset[ 1 ], (int)offset[ 2 ] );
		setkeyvalue( currententity, "origin", text );
		}

	for (i=0 ; i<numbrushfaces ; i++)
	{
		mf = &faces[i];

		w = basewindingforplane (&mf->plane);

		for (j=0 ; j<numbrushfaces && w ; j++)
		{
			if (j == i)
				continue;
		// flip the plane, because we want to keep the back side
			vectorsubtract (vec3_origin,faces[j].plane.normal, plane.normal);
			plane.dist = -faces[j].plane.dist;

			w = clipwinding (w, &plane, false);
		}

		if (!w)
			continue;	// overcontrained plane

	// this face is a keeper
		f = allocface ();
		f->numpoints = w->numpoints;
		if (f->numpoints > maxedges)
			error ("f->numpoints > maxedges");

		for (j=0 ; j<w->numpoints ; j++)
		{
			for (k=0 ; k<3 ; k++)
			{
            //jim
				point[k] = w->points[j][k] - offset[ k ];
            r = q_rint (point[k]);
            if ( fabs(point[k] - r) < zero_epsilon)
               f->pts[j][k] = r;
            else
               f->pts[j][k] = point[k];

				if (f->pts[j][k] < brush_mins[k])
					brush_mins[k] = f->pts[j][k];
				if (f->pts[j][k] > brush_maxs[k])
					brush_maxs[k] = f->pts[j][k];
            if (f->pts[j][k] < min)
					min = f->pts[j][k];
				if (f->pts[j][k] > max)
					max = f->pts[j][k];
         }

		}
      //jim
      vectorcopy( mf->plane.normal, plane.normal );
		vectorscale (mf->plane.normal, mf->plane.dist, point);
		vectorsubtract(point, offset, point);
		plane.dist = dotproduct (plane.normal, point);

      freewinding (w);
		f->texturenum = mf->texinfo;
      //jim
      f->planenum = findplane (&plane, &f->planeside);
//      f->planenum = findplane (&mf->plane, &f->planeside);
		f->next = brush_faces;
		brush_faces = f;
		checkface (f);
	}

   // rotatable objects have to have a bounding box big enough
	// to account for all its rotations.
	if ( !strncmp( classname, "rotate_", 7 ) )
		{
		vec_t delta;

		delta = fabs( max );
		if ( fabs( min ) > delta )
		   delta = fabs( min );

		for (k=0 ; k<3 ; k++)
			{
			brush_mins[k] = -delta;
			brush_maxs[k] = delta;
			}
		}
}



/*
==============================================================================

beveled clipping hull generation

this is done by brute force, and could easily get a lot faster if anyone cares.
==============================================================================
*/

vec3_t	hull_size[3][2] = {
{ {0, 0, 0}, {0, 0, 0} },
{ {-16,-16,-32}, {16,16,24} },
{ {-32,-32,-64}, {32,32,24} }

};

#define	max_hull_points	32
#define	max_hull_edges	64

int		num_hull_points;
vec3_t	hull_points[max_hull_points];
vec3_t	hull_corners[max_hull_points*8];
int		num_hull_edges;
int		hull_edges[max_hull_edges][2];

/*
============
addbrushplane
=============
*/
void addbrushplane (plane_t *plane)
{
	int		i;
	plane_t	*pl;
	float	l;

	if (numbrushfaces == max_faces)
		error ("addbrushplane: numbrushfaces == max_faces");
	l = vectorlength (plane->normal);
	if (l < 0.999 || l > 1.001)
		error ("addbrushplane: bad normal");

	for (i=0 ; i<numbrushfaces ; i++)
	{
		pl = &faces[i].plane;
		if (vectorcompare (pl->normal, plane->normal)
		&& fabs(pl->dist - plane->dist) < on_epsilon )
			return;
	}
	faces[i].plane = *plane;
	faces[i].texinfo = faces[0].texinfo;
	numbrushfaces++;
}


/*
============
testaddplane

adds the given plane to the brush description if all of the original brush
vertexes can be put on the front side
=============
*/
void testaddplane (plane_t *plane)
{
	int		i, c;
	vec_t	d;
	vec_t	*corner;
	plane_t	flip;
	vec3_t	inv;
	int		counts[3];
	plane_t	*pl;

// see if the plane has allready been added
	for (i=0 ; i<numbrushfaces ; i++)
	{
		pl = &faces[i].plane;
		if (vectorcompare (plane->normal, pl->normal) && fabs(plane->dist - pl->dist) < on_epsilon)
			return;
		vectorsubtract (vec3_origin, plane->normal, inv);
		if (vectorcompare (inv, pl->normal) && fabs(plane->dist + pl->dist) < on_epsilon)
			return;
	}

// check all the corner points
	counts[0] = counts[1] = counts[2] = 0;
	c = num_hull_points * 8;

	corner = hull_corners[0];
	for (i=0 ; i<c ; i++, corner += 3)
	{
		d = dotproduct (corner, plane->normal) - plane->dist;
		if (d < -on_epsilon)
		{
			if (counts[0])
				return;
			counts[1]++;
		}
		else if (d > on_epsilon)
		{
			if (counts[1])
				return;
			counts[0]++;
		}
		else
			counts[2]++;
	}

// the plane is a seperator

	if (counts[0])
	{
		vectorsubtract (vec3_origin, plane->normal, flip.normal);
		flip.dist = -plane->dist;
		plane = &flip;
	}

	addbrushplane (plane);
}

/*
============
addhullpoint

doesn't add if duplicated
=============
*/
int addhullpoint (vec3_t p, int hullnum)
{
	int		i;
	vec_t	*c;
	int		x,y,z;

	for (i=0 ; i<num_hull_points ; i++)
		if (vectorcompare (p, hull_points[i]))
			return i;

	vectorcopy (p, hull_points[num_hull_points]);

	c = hull_corners[i*8];

	for (x=0 ; x<2 ; x++)
		for (y=0 ; y<2 ; y++)
			for (z=0; z<2 ; z++)
			{
				c[0] = p[0] + hull_size[hullnum][x][0];
				c[1] = p[1] + hull_size[hullnum][y][1];
				c[2] = p[2] + hull_size[hullnum][z][2];
				c += 3;
			}

	if (num_hull_points == max_hull_points)
		error ("max_hull_points");

	num_hull_points++;

	return i;
}


/*
============
addhulledge

creates all of the hull planes around the given edge, if not done allready
=============
*/
void addhulledge (vec3_t p1, vec3_t p2, int hullnum)
{
	int		pt1, pt2;
	int		i;
	int		a, b, c, d, e;
	vec3_t	edgevec, planeorg, planevec;
	plane_t	plane;
	vec_t	l;

	pt1 = addhullpoint (p1, hullnum);
	pt2 = addhullpoint (p2, hullnum);

	for (i=0 ; i<num_hull_edges ; i++)
		if ( (hull_edges[i][0] == pt1 && hull_edges[i][1] == pt2)
		|| (hull_edges[i][0] == pt2 && hull_edges[i][1] == pt1) )
			return;	// allread added

	if (num_hull_edges == max_hull_edges)
		error ("max_hull_edges");

	hull_edges[i][0] = pt1;
	hull_edges[i][1] = pt2;
	num_hull_edges++;

	vectorsubtract (p1, p2, edgevec);
	vectornormalize (edgevec);

	for (a=0 ; a<3 ; a++)
	{
		b = (a+1)%3;
		c = (a+2)%3;
		for (d=0 ; d<=1 ; d++)
			for (e=0 ; e<=1 ; e++)
			{
				vectorcopy (p1, planeorg);
				planeorg[b] += hull_size[hullnum][d][b];
				planeorg[c] += hull_size[hullnum][e][c];

				vectorcopy (vec3_origin, planevec);
				planevec[a] = 1;

				crossproduct (planevec, edgevec, plane.normal);
				l = vectorlength (plane.normal);
				if (l < 1-angleepsilon || l > 1+angleepsilon)
					continue;
				plane.dist = dotproduct (planeorg, plane.normal);
				testaddplane (&plane);
			}
	}


}

/*
============
expandbrush
=============
*/
void expandbrush (int hullnum)
{
	int		i, x, s;
	vec3_t	corner;
	face_t	*f;
	plane_t	plane, *p;

	num_hull_points = 0;
	num_hull_edges = 0;

// create all the hull points
	for (f=brush_faces ; f ; f=f->next)
		for (i=0 ; i<f->numpoints ; i++)
			addhullpoint (f->pts[i], hullnum);

// expand all of the planes
	for (i=0 ; i<numbrushfaces ; i++)
	{
		p = &faces[i].plane;
		vectorcopy (vec3_origin, corner);
		for (x=0 ; x<3 ; x++)
		{
			if (p->normal[x] > 0)
				corner[x] = hull_size[hullnum][1][x];
			else if (p->normal[x] < 0)
				corner[x] = hull_size[hullnum][0][x];
		}
		p->dist += dotproduct (corner, p->normal);
	}

// add any axis planes not contained in the brush to bevel off corners
	for (x=0 ; x<3 ; x++)
		for (s=-1 ; s<=1 ; s+=2)
		{
		// add the plane
			vectorcopy (vec3_origin, plane.normal);
			plane.normal[x] = s;
			if (s == -1)
				plane.dist = -brush_mins[x] + -hull_size[hullnum][0][x];
			else
				plane.dist = brush_maxs[x] + hull_size[hullnum][1][x];
			addbrushplane (&plane);
		}

// add all of the edge bevels
	for (f=brush_faces ; f ; f=f->next)
		for (i=0 ; i<f->numpoints ; i++)
			addhulledge (f->pts[i], f->pts[(i+1)%f->numpoints], hullnum);
}

//============================================================================


/*
===============
loadbrush

converts a mapbrush to a bsp brush
===============
*/
brush_t *loadbrush (mbrush_t *mb, int hullnum)
{
	brush_t		*b;
	int			contents;
	char		*name;
	mface_t		*f;

//
// check texture name for attributes
//
	name = miptex[texinfo[mb->faces->texinfo].miptex];

	if (!q_strcasecmp(name, "clip") && hullnum == 0)
		return null;		// "clip" brushes don't show up in the draw hull

	if (name[0] == '*' && worldmodel)		// entities never use water merging
	{
		if (!q_strncasecmp(name+1,"lava",4))
			contents = contents_lava;
		else if (!q_strncasecmp(name+1,"slime",5))
			contents = contents_slime;
		else
			contents = contents_water;
	}
	else if (!q_strncasecmp (name, "sky",3) && worldmodel && hullnum == 0)
		contents = contents_sky;
	else
		contents = contents_solid;

	if (hullnum && contents != contents_solid && contents != contents_sky)
		return null;		// water brushes don't show up in clipping hulls

// no seperate textures on clip hull

//
// create the faces
//
	brush_faces = null;

	numbrushfaces = 0;
	for (f=mb->faces ; f ; f=f->next)
	{
		faces[numbrushfaces] = *f;
		if (hullnum)
			faces[numbrushfaces].texinfo = 0;
		numbrushfaces++;
	}

	createbrushfaces ();

	if (!brush_faces)
	{
		printf ("warning: couldn't create brush faces\n");
		return null;
	}

	if (hullnum)
	{
		expandbrush (hullnum);
		createbrushfaces ();
	}

//
// create the brush
//
	b = allocbrush ();

	b->contents = contents;
	b->faces = brush_faces;
	vectorcopy (brush_mins, b->mins);
	vectorcopy (brush_maxs, b->maxs);

	return b;
}

//=============================================================================


/*
============
brush_drawall

============
*/
void brush_drawall (brushset_t *bs)
{
	brush_t	*b;
	face_t	*f;

	for (b=bs->brushes ; b ; b=b->next)
		for (f=b->faces ; f ; f=f->next)
			draw_drawface (f);
}


/*
============
brush_loadentity
============
*/
brushset_t *brush_loadentity (entity_t *ent, int hullnum)
{
	brush_t		*b, *next, *water, *other;
	mbrush_t	*mbr;
	int			numbrushes;
	brushset_t	*bset;

	bset = malloc (sizeof(brushset_t));
	memset (bset, 0, sizeof(brushset_t));
	clearbounds (bset);

	numbrushes = 0;
	other = water = null;

	qprintf ("--- brush_loadentity ---\n");

   currententity = ent;

   for (mbr = ent->brushes ; mbr ; mbr=mbr->next)
	{
		b = loadbrush (mbr, hullnum);
		if (!b)
			continue;

		numbrushes++;

		if (b->contents != contents_solid)
		{
			b->next = water;
			water = b;
		}
		else
		{
			b->next = other;
			other = b;
		}

		addtobounds (bset, b->mins);
		addtobounds (bset, b->maxs);
	}

// add all of the water textures at the start
	for (b=water ; b ; b=next)
	{
		next = b->next;
		b->next = other;
		other = b;
	}

	bset->brushes = other;

	brushset = bset;
	brush_drawall (bset);

	qprintf ("%i brushes read\n",numbrushes);

	return bset;
}