#include "idbsp.h"

/*
   I assume that a grid 8 is used for the maps, so a point will be considered
   on a line if it is within 8 pixels of it.  The accounts for floating error.
 */

int                 cuts;		/* number of new lines generated by BSP process */

/*
   ==================
   =
   = DivlineFromWorldline
   =
   ==================
 */

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
   =
   = Returns side 0 (front), 1 (back), or -1 (colinear)
   ==================
 */

/*
	#define POS_RADIUS   2.0         // original

	sometimes a radius of 1.5 has produced better results.
*/

#define POS_RADIUS	2.0
#define NEWPOS

int                 PointOnSideTol(NXPoint * p, divline_t * l, double Tol)
{
	int                 retval;

#ifdef NEWPOS
	float               y;
#else
	float               dx,
	                    dy;
	float               left,
	                    right;
	float               a,
	                    b,
	                    c,
	                    d;

#endif



#ifdef NEWPOS
	y = ((p -> y - l -> pt.y) * l -> dx - (p -> x - l -> pt.x) * l -> dy) /
		sqrt(l -> dx * l -> dx + l -> dy * l -> dy);

	if (fabs(y) < Tol)
		retval = -1;
	else
		retval = (y < 0.0) ? 0 : 1;
#else
	if (!l -> dx)
		{
		if (p -> x > (l -> pt.x - Tol) && p -> x < (l -> pt.x + Tol))
			retval = -1;
		else
			{
			if (p -> x < l -> pt.x)
				retval = l -> dy > 0;
			else
				retval = l -> dy < 0;
			}
		}
	else if (!l -> dy)
		{
		if (p -> y > (l -> pt.y - Tol) && p -> y < (l -> pt.y + Tol))
			retval = -1;
		else
			{
			if (p -> y < l -> pt.y)
				retval = l -> dx < 0;
			else
				retval = l -> dx > 0;
			}
		}
	else
		{

		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);
		d = b * b - 4 * a * c;

		if (d > 0)
			retval = -1;
		else
			{
			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)
				retval = -1;		   /* on line */
			else
				{
				if (right < left)
					retval = 0;		   /* front side */
				else
					retval = 1;		   /* back side */
				}
			}
		}
#endif

/*if (myval != retval)
   {
   printf("\nPOS: line (% 5g, % 5g) - % 5g, % 5g: pt (% 5g, % 5g): me % d: JC % d:\n",
   l->pt.x, l->pt.y, l->dx, l->dy, p->x, p->y, myval, retval);
   } */
/*return myval; */
	return retval;
}

int                 PointOnSide(NXPoint * p, divline_t * l)
{
	return PointOnSideTol(p, l, POS_RADIUS);
}

/*
   =============
   =
   = sign
   =
   = Returns -1, 0, or 1, based on the input sign
   =
   ==============
 */

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

#define NEWLOS

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;

#ifdef NEWLOS
			if (((bl -> dx * dx + bl -> dy * dy) / sqrt(dx * dx + dy * dy)) > 0.0)
#else
			if (sign(dx) == sign(bl -> dx) && sign(dy) == sign(bl -> dy))
#endif

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

double              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;
}


/*
   ==================
   =
   = CutLine
   =
   = Truncates the given worldline to the front side of the divline
   = and returns the cut off back side in a newly allocated worldline
   ==================
 */

double              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;
}

line_t             *CutLine(line_t * wl, divline_t * bl)
{
	int                 side;
	line_t             *new_p;
	divline_t           wld;
	float               frac;
	NXPoint             intr;
	int                 offset;
	double              ndx,
	                    ndy;

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

	frac = InterceptVector(&wld, bl);
	ndx = floor((wld.dx * frac) + 0.5);
	ndy = floor((wld.dy * frac) + 0.5);
	intr.x = wld.pt.x + (int)ndx;
	intr.y = wld.pt.y + (int)ndy;
	offset = wl -> offset + (int)floor(sqrt(ndx * ndx + ndy * ndy) + 0.5);
	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 (id lines_i, line_t *spliton, int bestgrade)
 */
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 = [linestore_i elementAt: spliton->linedef];
 */
	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];
 */
	c = lines_i -> count;
	grade = 0;

	for (i = 0; i < c; i++)
		{
/*              line_p = [lines_i elementAt: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 = [linestore_i elementAt: line_p->linedef];
 */
			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 (id lines_i, line_t *spliton
   , id frontlist_i, id backlist_i)
 */
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];
 */
	c = lines_i -> count;

	for (i = 0; i < c; i++)
		{
/*              line_p = [lines_i elementAt: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:
/*                      [frontlist_i addElement: line_p];
 */
			memcpy((line_t *) frontlist_i -> data + frontlist_i -> count, line_p, sizeof(line_t));
			frontlist_i -> count += 1;
			frontlist_i -> data = (line_t *) realloc(frontlist_i -> data,
				sizeof(line_t) * (frontlist_i -> count + 1));
			break;
			case 1:
/*                      [backlist_i addElement: line_p];
 */
			memcpy((line_t *) backlist_i -> data + backlist_i -> count, line_p, sizeof(line_t));
			backlist_i -> count += 1;
			backlist_i -> data = (line_t *) realloc(backlist_i -> data,
				sizeof(line_t) * (backlist_i -> count + 1));
			break;
			case -2:
			newline_p = CutLine(line_p, &divline);
/*                      [frontlist_i addElement: line_p];
   [backlist_i addElement: newline_p];
 */
			memcpy((line_t *) frontlist_i -> data + frontlist_i -> count, line_p, sizeof(line_t));
			frontlist_i -> count += 1;
			frontlist_i -> data = (line_t *) realloc(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 *) realloc(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
   ================
 */

/* float        gray = NX_WHITE; */
float               gray = 0;

/* bspnode_t *BSPList (id lines_i)
 */
bspnode_t          *BSPList(STORAGE * lines_i)
{
/*      id                              frontlist_i, backlist_i;
 */
	STORAGE            *frontlist_i,
	                   *backlist_i;
	int                 i,
	                    c,
	                    step;
	line_t             *line_p,
	                   *bestline_p;
	int                 v,
	                    bestv;
	bspnode_t          *node_p;

/*
   if (draw)
   PSsetgray (gray);
   gray = 1.0 - gray;
 */
	DrawLineStore(lines_i);

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

/*
   find the best line to partition on
 */

/*      c = [lines_i count];
 */

	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 = [lines_i elementAt:i];
 */
		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 alloc]
   initCount:              0
   elementSize:    sizeof(line_t)
   description:    NULL];
   backlist_i =
   [[Storage alloc]
   initCount:              0
   elementSize:    sizeof(line_t)
   description:    NULL];
 */
	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
   =
   =====================
 */

/* id segstore_i;
 */
STORAGE            *segstore_i;

void                MakeSegs(void)
{
	int                 i,
	                    count;
	worldline_t        *wl;

/* line_t   li;
 */
	line_t             *li;

/*
   segstore_i =
   [[Storage alloc]
   initCount:              0
   elementSize:    sizeof(line_t)
   description:    NULL];
 */
	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 elementAt:0];
 */
	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 addElement: &li];
 */
		segstore_i -> count += 1;
		segstore_i -> data = (line_t *) realloc(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 addElement: &li];
 */
			segstore_i -> count += 1;
			segstore_i -> data = (line_t *) realloc(segstore_i -> data,
				sizeof(line_t) * (segstore_i -> count + 1));
			li = (line_t *) segstore_i -> data + segstore_i -> count;
			}
		}
}


/*
   =====================
   =
   = BuildBSP
   =
   =====================
 */

bspnode_t          *startnode;

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