/*
			===== IDBSP - id Software's BSP builder for DOOM ====
	DOS port (c) 1994 Ron Rossbach (ej070@cleveland.freenet.edu)

	File BUILDBSP.C
		Implements the functions which build the BSP tree.  The tree is
		then split into its component resources (NODES, etc.) by functions
		in other modules.

	Revisions:

		1)	Credit goes to Antony Suter (antony@werple.apana.org.au) for fixing id's
				original bug which sometimes caused a column in a "far away" texture
				to be drawn out of order.  This caused the "column of slime" seen on
				E1M1 of id's original levels, when looking up at the imp in the
				"zigzag room". The bug is fixed by using a difference value for radius
        in the PointOnSide function; a value of 1.4143 fixes the bug, but will
        mess up sector references on some sidedefs in some PWADs.  If the
        default value (1.4143) gives you problems, run with -radius=2.0 (id's
        original value) or experiment to find the best setting.
*/

#include "idbsp.h"

int					cuts;					/* number of new lines generated by the BSP process */
float 			gray = 0; 		/* used for drawing the map in id's original code		*/
STORAGE 		*segstore_i;
bspnode_t   *startnode;		/* root of the BSP tree 														*/

/*
===============================================================================
=
= DivlineFromWorldline
=
=	Creates a dividing line from a "worldline"; i.e. a linedef as read from the
= input file.
===============================================================================
*/
void DivlineFromWorldline(divline_t *d, line_t *w)
{
	d->pt = w->p1;
	d->dx = w->p2.x - w->p1.x;
	d->dy = w->p2.y - w->p1.y;
}

/*
===============================================================================
=
= PointOnSide
=
=	This is Antony Suter's (antony@werple.apana.org.au) PointOnSide function,
= which fixes the bug mentioned above.
=
= Returns 0 if point is on "front" side of line ("right" side), 1 if on the
= "back" side, or -1 if colinear.  To account for floating point error, a
= point is considered on a line if it is within 8 pixels of it.
===============================================================================
*/
int     PointOnSide (NXPoint *p, divline_t *l)
{
	float   dx,dy;
	float   left, right;
	float   a,b,c,d;

	if (!l->dx)
		{
		if (p->x > (l->pt.x - pos_radius) && p->x < (l->pt.x + pos_radius))
			return -1;
		if (p->x < l->pt.x)
			return l->dy > 0;
		return l->dy < 0;
		}

	if (!l->dy)
		{
		if (p->y > (l->pt.y - pos_radius) && p->y < (l->pt.y + pos_radius))
			return -1;
		if (p->y < l->pt.y)
			return l->dx < 0;
		return l->dx > 0;
		}

	dx = l->pt.x - p->x;
	dy = l->pt.y - p->y;
	a = l->dx*l->dx + l->dy*l->dy;
	b = 2*(l->dx*dx + l->dy*dy);
	c = dx*dx+dy*dy - (pos_radius * pos_radius);      /* [2] unit radius */
	d = b*b - 4*a*c;
	if (d>0)
		return -1;               /* within [four] pixels of line */

	dx = p->x - l->pt.x;
	dy = p->y - l->pt.y;

	left = l->dy * dx;
	right = dy * l->dx;

	if ( fabs (left-right) < 0.5 )  /* allow slop */
		return -1;              			/* on line 		*/
	if (right < left)
		return 0;               			/* front side */

	return 1;                 			/* back side 	*/
}

/*
===============================================================================
=
= sign
=
= Returns 1, -1, or 0 based on the sign of the parameter.
=
================================================================================
*/
int sign (float i)
{
	if (i<0)
		return -1;
	else
		if (i>0)
			return 1;
	return 0;
}

/*
===============================================================================
=
= LineOnSide
=
= Returns side 0 / 1, or -2 if line must be split
= If the line is colinear, it will be placed on the front side if
= it is going the same direction as the dividing line
================================================================================
*/
boolean LineOnSide (line_t *wl, divline_t *bl)
{
	int     s1,s2;
	float		dx, dy;

	s1 = PointOnSide (&wl->p1, bl);
	s2 = PointOnSide (&wl->p2, bl);

	if (s1 == s2)
		{
		if (s1 == -1)
			{       /* colinear, so see if the directions are the same */
			dx = wl->p2.x - wl->p1.x;
			dy = wl->p2.y - wl->p1.y;
			if (sign(dx) == sign (bl->dx) && sign(dy) == sign(bl->dy) )
				return 0;
			return 1;
			}
		return s1;
		}
	if (s1 == -1)
		return s2;
	if (s2 == -1)
		return s1;

	return -2;
}

/*
===============================================================================
=
= InterceptVector
=
= Returns the fractional intercept point along first vector
================================================================================
*/
float InterceptVector (divline_t *v2, divline_t *v1)
{
#if 0

v1.x + f1*v1.xs = v2.x + f2*v2.xs       (parametric x coordinates)
f1*v1.xs = v2.x - v1.x + f2*v2.xs
f1 = (v2.x - v1.x +f2*v2.xs) / v1.xs

v1.y + f1*v1.ys = v2.y + f2*v2.ys       (parametric y coordinates)
f1 = (v2.y - v1.y + f2*v2.ys) / v1.ys

f1 = (v2.x - v1.x +f2*v2.xs) / v1.xs = (v2.y - v1.y + f2*v2.ys) / v1.ys
v1.ys*v2.x - v1.ys*v1.x + v1.ys*v2.xs*f2 = v1.xs*v2.y - v1.xs*v1.y + v1.xs*v2.ys*f2
(v1.ys*v2.xs - v1.xs*v2.ys)*f2 = -v1.ys*v2.x + v1.ys*v1.x + v1.xs*v2.y - v1.xs*v1.y
																												= v1.ys*(v1.x-v2.x) + v1.xs*(v2.y-v1.y)

f2 = (v1.ys*(v1.x-v2.x) + v1.xs*(v2.y-v1.y)) / (v1.ys*v2.xs - v1.xs*v2.ys)
#endif


	float   frac, num, den;

	den = v1->dy*v2->dx - v1->dx*v2->dy;
	if (den == 0)
		Error ("InterceptVector: parallel");

	num = (v1->pt.x - v2->pt.x)*v1->dy + (v2->pt.y - v1->pt.y)*v1->dx;
	frac = num / den;

	if (frac <= 0.0 || frac >= 1.0)
		Error ("InterceptVector: intersection outside line");

	return frac;
}

/*
===============================================================================
=
= round
=
================================================================================
*/
float round (float x)
{
	if (x>0)
		{
		if (x - (int)x < 0.1)
			return (int)x;
		else
			if (x - (int)x > 0.9)
				return (int)x+1;
			else
				return x;
		}

	if ((int)x - x < 0.1)
		return (int)x;
	else
		if ((int)x - x > 0.9)
			return  (int)x - 1;

	return x;
}

/*
===============================================================================
=
= CutLine
=
= Truncates the given worldline to the front side of the divline
= and returns the cut off back side in a newly allocated worldline
================================================================================
*/
line_t  *CutLine(line_t *wl, divline_t *bl)
{
	int         side;
	line_t      *new_p;
	divline_t		wld;
	float       frac;
	NXPoint     intr;
	int         offset;

	cuts++;
	DivlineFromWorldline (&wld, wl);
	new_p = (line_t *)SafeMalloc(sizeof(line_t));
	memset (new_p,0,sizeof(*new_p));
	*new_p = *wl;

	frac = InterceptVector (&wld, bl);
	intr.x = wld.pt.x + round(wld.dx*frac);
	intr.y = wld.pt.y + round(wld.dy*frac);
	offset = wl->offset + round(frac*sqrt(wld.dx*wld.dx+wld.dy*wld.dy));
	side = PointOnSide (&wl->p1, bl);
	if (side == 0)
		{       /* line starts on front side */
		wl->p2 = intr;
		new_p->p1 = intr;
		new_p->offset = offset;
		}
	else
		{       /* line starts on back side */
		wl->p1 = intr;
		wl->offset = offset;
		new_p->p2 = intr;
		}

	return new_p;
}

/*
===============================================================================
=
= EvaluateSplit
=
= Returns a number grading the quality of a split along the givent line
= for the current list of lines.  Evaluation is halted as soon as it is
= determined that a better split already exists
=
= A split is good if it divides the lines evenly without cutting many lines
= A horizontal or vertical split is better than a sloping split
=
= The LOWER the returned value, the better.  If the split line does not divide
= any of the lines at all, MAXINT will be returned
================================================================================
*/
int EvaluateSplit(STORAGE *lines_i, line_t *spliton, int bestgrade)
{
	int						i, c, side;
	line_t        *line_p;
	divline_t     divline;
	int           frontcount, backcount, max, new;
	int           grade;
	worldline_t   *wl;

	wl = (worldline_t *)linestore_i->data + spliton->linedef;

#if 0
	if (wl->special == BSPSLIDEENDSPECIAL)
		return MAXINT;  /* NEVER split on this, because it moves */
#endif
	DivlineFromWorldline (&divline, spliton);

	frontcount = backcount = 0;
	c = lines_i->count;
	grade = 0;

	for (i=0 ; i<c ; i++)
		{
		line_p = (line_t *)lines_i->data + i;
		if (line_p == spliton)
			side = 0;
		else
			side = LineOnSide (line_p, &divline);
		switch (side)
			{
			case 0:
					 frontcount++;
					 break;
			case 1:
					 backcount++;
					 break;
			case -2:
					 wl = (worldline_t *)linestore_i->data + line_p->linedef;
#if 0
					if (wl->special == BSPSLIDESIDESPECIAL)
						return MAXINT;  /* NEVER split this line, because it slides */
#endif
					frontcount++;
					backcount++;
					break;
			 }

		max = MAX(frontcount,backcount);
		new = (frontcount+backcount) - c;
		grade = max+new*8;
		if (grade > bestgrade)
			return grade;           /* might as well stop now */
		}

	if (frontcount == 0 || backcount == 0)
		return INT_MAX;                 /* line does not partition at all */

	return grade;
}


/*
===============================================================================
=
= ExecuteSplit
=
= Actually splits the line list as EvaluateLines predicted
================================================================================
*/
void ExecuteSplit(STORAGE *lines_i, line_t *spliton, STORAGE *frontlist_i,
									STORAGE *backlist_i)
{
	int            i, c, side;
	line_t         *line_p, *newline_p;
	divline_t      divline;

	DivlineFromWorldline(&divline, spliton);
	DrawDivLine(&divline);

	c = lines_i->count;

	for (i=0 ; i<c ; i++)
		{
		line_p = (line_t *)lines_i->data + i;
		if (line_p == spliton)
			side = 0;
		else
			side = LineOnSide (line_p, &divline);
		switch (side)
			{
			case 0:
							memcpy((line_t *)frontlist_i->data + frontlist_i->count,
											line_p, sizeof(line_t));
							frontlist_i->count += 1;
							frontlist_i->data = (line_t *)SafeRealloc(frontlist_i->data,
																sizeof(line_t) * (frontlist_i->count + 1));
							break;
			case 1:
							memcpy((line_t *)backlist_i->data + backlist_i->count, line_p,
											sizeof(line_t));
							backlist_i->count += 1;
							backlist_i->data = (line_t *)SafeRealloc(backlist_i->data,
																sizeof(line_t) * (backlist_i->count + 1));
							break;
			case -2:
							newline_p = CutLine (line_p, &divline);
							memcpy((line_t *)frontlist_i->data + frontlist_i->count,
											 line_p, sizeof(line_t));
							frontlist_i->count += 1;
							frontlist_i->data = (line_t *)SafeRealloc(frontlist_i->data,
																 sizeof(line_t) * (frontlist_i->count + 1));
							memcpy((line_t *)backlist_i->data + backlist_i->count,
											newline_p, sizeof(line_t));
							backlist_i->count += 1;
							backlist_i->data = (line_t *)SafeRealloc(backlist_i->data,
																sizeof(line_t) * (backlist_i->count + 1));
							break;
			default:
							Error ("ExecuteSplit: bad side");
			}
		}
}

/*
===============================================================================
=
= BSPList
=
= Takes a storage of lines and recursively partitions the list
= Returns a bspnode_t
================================================================================
*/
bspnode_t *BSPList(STORAGE *lines_i)
{
	STORAGE			*frontlist_i, *backlist_i;
	int       	i, c, step;
	line_t    	*line_p, *bestline_p;
	int       	v, bestv;
	bspnode_t		*node_p;

	DrawLineStore(lines_i);

	node_p = (bspnode_t *)SafeMalloc (sizeof(*node_p));
	memset (node_p, 0, sizeof(*node_p));

/*
 find the best line to partition on
*/

	c = lines_i->count;
	bestv = INT_MAX;
	bestline_p = NULL;
	step = (c/40)+1;          /* set this to 1 for an exhaustive search */

research:
	for (i=0 ; i<c ; i+=step)
		{
		line_p = (line_t *)lines_i->data + i;
		v = EvaluateSplit (lines_i, line_p, bestv);
		if (v<bestv)
			{
			bestv = v;
			bestline_p = line_p;
			}
		}

/*
 if none of the lines should be split, the remaining lines
 are convex, and form a terminal node
*/

/*
	printf ("bestv:%i\n",bestv);
*/
	if (bestv == INT_MAX)
		{
		if (step > 1)
			{       /* possible to get here with non convex area if BSPSLIDE    */
							/* specials caused rejections 															*/
			step = 1;
			goto research;
			}
		node_p->lines_i = lines_i;
		return node_p;
		}

/*
 divide the line list into two nodes along the best split line
*/
	DivlineFromWorldline (&node_p->divline, bestline_p);

	frontlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	frontlist_i->count = 0;
	frontlist_i->size = sizeof(line_t);
	frontlist_i->data = (line_t *)SafeMalloc(sizeof(line_t));

	backlist_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	backlist_i->count = 0;
	backlist_i->size = sizeof(line_t);
	backlist_i->data = (line_t *)SafeMalloc(sizeof(line_t));

	ExecuteSplit (lines_i, bestline_p, frontlist_i, backlist_i);

/*
 recursively divide the lists
*/
	node_p->side[0] = BSPList (frontlist_i);
	node_p->side[1] = BSPList (backlist_i);

	return node_p;
}

/*
===============================================================================
=
= MakeSegs
=
===============================================================================
*/
void MakeSegs (void)
{
	int           i, count;
	worldline_t   *wl;
	line_t        *li;

	segstore_i = (STORAGE *)SafeMalloc(sizeof(STORAGE));
	segstore_i->data = (line_t *)SafeMalloc(sizeof(line_t));
	segstore_i->count = 0;
	segstore_i->size = sizeof(line_t);

	count = linestore_i->count;
	wl = linestore_i->data;

	li = segstore_i->data;

	for (i= 0 ; i<count ; i++, wl++)
		{
		li->p1 = wl->p1;
		li->p2 = wl->p2;
		li->linedef = i;
		li->side = 0;
		li->offset = 0;
		li->grouped = false;

		segstore_i->count += 1;
		segstore_i->data = (line_t *)SafeRealloc(segstore_i->data,
												sizeof(line_t) * (segstore_i->count + 1));
		li = (line_t *)segstore_i->data + segstore_i->count;

		if (wl->flags & ML_TWOSIDED)
			{
			li->p1 = wl->p2;
			li->p2 = wl->p1;
			li->linedef = i;
			li->side = 1;
			li->offset = 0;
			li->grouped = false;
			segstore_i->count += 1;
			segstore_i->data = (line_t *)SafeRealloc(segstore_i->data,
													sizeof(line_t) * (segstore_i->count + 1));
			li = (line_t *)segstore_i->data + segstore_i->count;
			}
		}
}

/*
===============================================================================
=
= BuildBSP
=
===============================================================================
*/
void BuildBSP(void)
{
	MakeSegs();
	cuts = 0;
	startnode = BSPList (segstore_i);
}