makenode.c

/*- MAKENODE.C --------------------------------------------------------------*
 Recursively create nodes and return the pointers.
*---------------------------------------------------------------------------*/
#include "structs.h"
#include "bsp.h"

signed short node_x, node_y, node_dx, node_dy;

/*--------------------------------------------------------------------------*/

int SplitDist(struct Seg *ts)
{
	double t,dx,dy;

	if(ts->flip==0)
		{
		dx = (double)(vertices[linedefs[ts->linedef].start].x)-(vertices[ts->start].x);
		dy = (double)(vertices[linedefs[ts->linedef].start].y)-(vertices[ts->start].y);

		if(dx == 0 && dy == 0) 
			fprintf(stderr,"Trouble in SplitDist %f,%f\n",dx,dy);
		t = sqrt((dx*dx) + (dy*dy));
		return (int)t;
		}
	else
		{
		dx = (double)(vertices[linedefs[ts->linedef].end].x)-(vertices[ts->start].x);
		dy = (double)(vertices[linedefs[ts->linedef].end].y)-(vertices[ts->start].y);

		if(dx == 0 && dy == 0) 
			fprintf(stderr,"Trouble in SplitDist %f,%f\n",dx,dy);
		t = sqrt((dx*dx) + (dy*dy));
		return (int)t;
		}
}

/*---------------------------------------------------------------------------*
 Split a list of segs (ts) into two using the method described at bottom of
 file, this was taken from OBJECTS.C in the DEU5beta source.

 This is done by scanning all of the segs and finding the one that does
 the least splitting and has the least difference in numbers of segs on either
 side.
 If the ones on the left side make a SSector, then create another SSector
 else put the segs into lefts list.
 If the ones on the right side make a SSector, then create another SSector
 else put the segs into rights list.
*---------------------------------------------------------------------------*/

static inline void 
DivideSegs(struct Seg *ts, struct Seg **rs, struct Seg **ls, const bbox_t bbox)
{
	struct Seg *rights,*lefts;
	struct Seg *tmps,*best,*news,*prev;
	struct Seg *add_to_rs,*add_to_ls;
  	struct Seg *new_best=NULL,*new_rs,*new_ls;

	struct Seg *strights,*stlefts;
        int num_new=0;
	short int x,y,val;

	best = PickNode(ts,bbox);			/* Pick best node to use.*/

	if(best == NULL) ProgError("Couldn't pick nodeline!");

	node_x = vertices[best->start].x;
	node_y = vertices[best->start].y;
	node_dx = vertices[best->end].x-vertices[best->start].x;
	node_dy = vertices[best->end].y-vertices[best->start].y;

/* When we get to here, best is a pointer to the partition seg.
	Using this partition line, we must split any lines that are intersected
	into a left and right half, flagging them to be put their respective sides
	Ok, now we have the best line to use as a partitioning line, we must
   split all of the segs into two lists (rightside & leftside).				 */

	rights = NULL;									/* Start off with empty*/
	lefts = NULL;									/* lists.*/
	strights = NULL;								/* Start off with empty*/
	stlefts = NULL;								/* lists.*/

	psx = vertices[best->start].x;			/* Partition line coords*/
	psy = vertices[best->start].y;
	pex = vertices[best->end].x;
	pey = vertices[best->end].y;
	pdx = psx - pex;								/* Partition line DX,DY*/
	pdy = psy - pey;

	for(tmps=ts;tmps;tmps=tmps->next)
		{
		progress();									/* Something for the user to look at.*/
		add_to_rs = NULL;
		add_to_ls = NULL;
		if(tmps != best)
			{
			lsx = vertices[tmps->start].x;	/* Calculate this here, cos it doesn't*/
			lsy = vertices[tmps->start].y;	/* change for all the interations of*/
			lex = vertices[tmps->end].x;		/* the inner loop!*/
			ley = vertices[tmps->end].y;
			val = DoLinesIntersect();
			if((val&2 && val&64) || (val&4 && val&32))	/* If intersecting !!*/
				{
				ComputeIntersection(&x,&y);
/*				printf("Splitting Linedef %d at %d,%d\n",tmps->linedef,x,y);*/
 			        vertices = ResizeMemory(vertices, sizeof(struct Vertex) * (num_verts+1));
				vertices[num_verts].x = x;
				vertices[num_verts].y = y;

				news = GetMemory(sizeof( struct Seg));
				*news = *tmps;
				tmps->next = news;
				news->start = num_verts;
				tmps->end = num_verts;
				news->dist = SplitDist(news);
/*				printf("splitting dist = %d\n",news->dist);*/
/*				printf("splitting vertices = %d,%d,%d,%d\n",tmps->start,tmps->end,news->start,news->end);*/
				if(val&32) add_to_ls = tmps;
				if(val&64) add_to_rs = tmps;
				if(val&2) add_to_ls = news;
				if(val&4) add_to_rs = news;
				tmps = news;
				num_verts++;
				num_new++;
				}
			else
				{											/* Not split, which side ?*/
				if(val&34) add_to_ls = tmps;
				if(val&68) add_to_rs = tmps;
				if(val&1 && val&16)					/* On same line*/
					{
/* 06/01/97 Lee Killough: this fixes a bug ever since 1.2x,
   probably 1.0, of BSP: when partitioning a parallel seg,
   you must take its vertices' orientation into account, NOT the
   flip bits, to determine which side of the partitioning line a
   parallel seg should go on. If you simply flip the linedef in
   question, you will be flipping both its vertices and sidedefs,
   and the flip bits as well, even though the basic geometry has
   not changed. Thus you need to use the vertices' orientation
   (whether the seg is in the same direction or not, regardless
   of its original linedef's being flipped or not), into account.

   Originally, some segs were partitioned backwards, and if
   it happened that there were different sectors on either
   side of the seg being partitioned, it could leave holes
   in space, causing either invisible barriers or disappearing
   Things, because the ssector would be associated with the
   wrong sector.

   The old logic of tmps->flip != best->flip seems to rest on
   the assumption that if two segs are parallel, they came
   from the same linedef. This is clearly not always true.   */

              /*  if (tmps->flip != best->flip)   old logic -- wrong!!! */

              /* We know the segs are parallel or nearly so, so take their
                 dot product to determine their relative orientation. */

		if ( (lsx-lex)*pdx + (lsy-ley)*pdy < 0)
  	         add_to_ls = tmps;
	 	else
		 add_to_rs = tmps;
					}
				}
			}
		else add_to_rs = tmps;						/* This is the partition line*/

/*		printf("Val = %X\n",val);*/

		if(add_to_rs)							/* CHECK IF SHOULD ADD RIGHT ONE */
			{
			new_rs = GetMemory(sizeof(struct Seg));
			*new_rs = *add_to_rs;
			if(add_to_rs == best) new_best = new_rs;
			new_rs->next = NULL;
			if(!rights) strights = rights = new_rs;
			else
				{
				rights->next = new_rs;
				rights = new_rs;
				}
			}
				
		if(add_to_ls)							/* CHECK IF SHOULD ADD LEFT ONE */
			{
			new_ls = GetMemory(sizeof(struct Seg));
			*new_ls = *add_to_ls;
			if(add_to_ls == best) new_best = new_ls;
			new_ls->next = NULL;
			if(!lefts) stlefts = lefts = new_ls;
			else
				{
				lefts->next = new_ls;
				lefts = new_ls;
				}
			}
		}

	if(strights == NULL)
		{
/*		printf("No right side, moving partition into right side\n");*/
		strights = rights = new_best;
		prev = NULL;
		for(tmps=stlefts;tmps;tmps=tmps->next)
			{
			if(tmps == new_best)
				{
				if(prev != NULL) prev->next=tmps->next;
				else stlefts=tmps->next;
				}
			prev=tmps;
			}
		prev->next = NULL;
		}
	
	if(stlefts == NULL)
		{
/*		printf("No left side, moving partition into left side\n");*/
		stlefts = lefts = new_best;
		prev = NULL;
		for(tmps=strights;tmps;tmps=tmps->next)
			{
			if(tmps == new_best)
				{
				if(prev != NULL) prev->next=tmps->next;
				else strights=tmps->next;
				}
			prev=tmps;
			}
		stlefts->next = NULL;
		prev->next = NULL;								/* Make sure end of list = NULL*/
		}

	if(rights->next != NULL) rights->next = NULL;
	if(lefts->next != NULL) lefts->next = NULL;

	for(tmps=ts;tmps;tmps=best)
		{
		best=tmps->next;
		free(tmps);
		}

/*	printf("Made %d new Vertices and Segs\n",num_new);*/

	*rs = strights ; *ls = stlefts;
}

/*--------------------------------------------------------------------------*/

static inline int IsItConvex( struct Seg *ts)
{
   struct Seg *line=ts,*check;
   int   sector,val;

/* All ssectors must come from same sector unless it's marked
   "special" with sector tag >= 900. Original idea, Lee Killough */

   sector = sidedefs[ts->flip ? linedefs[ts->linedef].sidedef2 :
                                linedefs[ts->linedef].sidedef1].sector;
   if (sectors[sector].tag < 900)
     while ((line=line->next)!=0)
      {
       int ts=sidedefs[line->flip ? linedefs[line->linedef].sidedef2 :
                                    linedefs[line->linedef].sidedef1].sector;
       if (ts != sector && sectors[ts].tag < 900)
           return TRUE;
      }

   /* all of the segs must be on the same side all the other segs */

	for(line=ts;line;line=line->next)
		{
		psx = vertices[line->start].x;
		psy = vertices[line->start].y;
		pex = vertices[line->end].x;
		pey = vertices[line->end].y;
		pdx = (psx - pex);									/* Partition line DX,DY*/
		pdy = (psy - pey);
		for(check=ts;check;check=check->next)
			{
			if(line!=check)
				{
				lsx = vertices[check->start].x;	/* Calculate this here, cos it doesn't*/
				lsy = vertices[check->start].y;	/* change for all the interations of*/
				lex = vertices[check->end].x;		/* the inner loop!*/
				ley = vertices[check->end].y;
				val = DoLinesIntersect();
				if(val&34) return TRUE;
				}
			}
		}

	/* no need to split the list: these Segs can be put in a SSector */
   return FALSE;
}

/*--------------------------------------------------------------------------*/

static inline int CreateSSector(struct Seg *tmps)
{
	struct Seg *next;
	int n;

	if(num_ssectors == 0)
		{
		ssectors = GetMemory(sizeof(struct SSector));
		}
	else
		{
		ssectors = ResizeMemory(ssectors,sizeof(struct SSector)*(num_ssectors+1));
		}
	
	ssectors[num_ssectors].first = num_psegs;

	n = num_psegs;
	
/*	printf("\n");*/

	for(;tmps;tmps=next)
		{
		if(num_psegs == 0)
			{
			psegs = GetMemory(sizeof(struct Pseg));
			}
		else
			{
			psegs = ResizeMemory(psegs,sizeof(struct Pseg)*(num_psegs+1));
			}

		psegs[num_psegs].start = tmps->start;
		psegs[num_psegs].end = tmps->end;
		psegs[num_psegs].angle = tmps->angle;
		psegs[num_psegs].linedef = tmps->linedef;
		psegs[num_psegs].flip = tmps->flip;
		psegs[num_psegs].dist = tmps->dist;
/*
		printf("%d,%d,%u,%d,%d,%u\n",
			psegs[num_psegs].start,
			psegs[num_psegs].end,
			psegs[num_psegs].angle,
			psegs[num_psegs].linedef,
			psegs[num_psegs].flip,
			psegs[num_psegs].dist);
*/
		num_psegs++;
		next = tmps->next;
		free(tmps); /* This seg is done */
		}

	ssectors[num_ssectors].num = num_psegs-n;

	num_ssectors++;

	return num_ssectors-1;
}

/*- translate (dx, dy) into an integer angle value (0-65535) ---------------*/

inline unsigned int ComputeAngle(int dx, int dy) {
   double w;

	w = (atan2( (double) dy , (double) dx) * (double)(65536/(M_PI*2)));

	if(w<0) w = (double)65536+w;

	return (unsigned) w;
}

struct Node *CreateNode(struct Seg *ts, const bbox_t bbox)
{
	struct Node *tn;
	struct Seg *rights = NULL;
	struct Seg *lefts = NULL;

	tn = GetMemory( sizeof( struct Node));				/* Create a node*/
 
	DivideSegs(ts,&rights,&lefts,bbox);						/* Divide node in two*/

	num_nodes++;

	tn->x = node_x;											/* store node line info*/
	tn->y = node_y;
	tn->dx = node_dx;
	tn->dy = node_dy;

	FindLimits(lefts,tn->leftbox);				/* Find limits of vertices	*/

	if(IsItConvex(lefts))	  								/* Check lefthand side*/
		{
	        if (verbosity > 1) Verbose("L");
		tn->nextl = CreateNode(lefts,tn->leftbox);	/* still segs remaining*/
		tn->chleft = 0;
	        if (verbosity > 1) Verbose("\b");
		}
	else
		{
		tn->nextl = NULL;
		tn->chleft = CreateSSector(lefts) | 0x8000;
		}

	FindLimits(rights, tn->rightbox);										/* Find limits of vertices*/
	
	if(IsItConvex(rights))									/* Check righthand side*/
		{
	        if (verbosity > 1) Verbose("R");
		tn->nextr = CreateNode(rights, tn->rightbox);	/* still segs remaining*/
		tn->chright = 0;
	        if (verbosity > 1) Verbose("\b");
		}
	else
		{
		tn->nextr = NULL;
		tn->chright =  CreateSSector(rights) | 0x8000;
		}

	return tn;
}

/*---------------------------------------------------------------------------*
   
	This message has been taken, complete, from OBJECTS.C in DEU5beta source.
	It outlines the method used here to pick the nodelines.

	IF YOU ARE WRITING A DOOM EDITOR, PLEASE READ THIS:

   I spent a lot of time writing the Nodes builder.  There are some bugs in
   it, but most of the code is OK.  If you steal any ideas from this program,
   put a prominent message in your own editor to make it CLEAR that some
   original ideas were taken from DEU.  Thanks.

   While everyone was talking about LineDefs, I had the idea of taking only
   the Segs into account, and creating the Segs directly from the SideDefs.
   Also, dividing the list of Segs in two after each call to CreateNodes makes
   the algorithm faster.  I use several other tricks, such as looking at the
   two ends of a Seg to see on which side of the nodeline it lies or if it
   should be split in two.  I took me a lot of time and efforts to do this.

   I give this algorithm to whoever wants to use it, but with this condition:
   if your program uses some of the ideas from DEU or the whole algorithm, you
   MUST tell it to the user.  And if you post a message with all or parts of
   this algorithm in it, please post this notice also.  I don't want to speak
   legalese; I hope that you understand me...  I kindly give the sources of my
   program to you: please be kind with me...

   If you need more information about this, here is my E-mail address:
   Raphael.Quinet@eed.ericsson.se (Rapha‰l Quinet).

   Short description of the algorithm:
     1 - Create one Seg for each SideDef: pick each LineDef in turn.  If it
	 has a "first" SideDef, then create a normal Seg.  If it has a
	 "second" SideDef, then create a flipped Seg.
     2 - Call CreateNodes with the current list of Segs.  The list of Segs is
	 the only argument to CreateNodes.
     3 - Save the Nodes, Segs and SSectors to disk.  Start with the leaves of
	 the Nodes tree and continue up to the root (last Node).

   CreateNodes does the following:
     1 - Pick a nodeline amongst the Segs (minimize the number of splits and
	 keep the tree as balanced as possible).
     2 - Move all Segs on the right of the nodeline in a list (segs1) and do
	 the same for all Segs on the left of the nodeline (in segs2).
     3 - If the first list (segs1) contains references to more than one
	 Sector or if the angle between two adjacent Segs is greater than
	 180ø, then call CreateNodes with this (smaller) list.  Else, create
	 a SubSector with all these Segs.
     4 - Do the same for the second list (segs2).
     5 - Return the new node (its two children are already OK).

   Each time CreateSSector is called, the Segs are put in a global list.
   When there is no more Seg in CreateNodes' list, then they are all in the
   global list and ready to be saved to disk.

*---------------------------------------------------------------------------*/