/******************************************************************************
	MODULE:		NODES.C
	WRITTEN BY:	Robert Fenske, Jr. (rfenske@swri.edu)
				Southwest Research Institute
				Electromagnetics Division
				6220 Culebra
				San Antonio, Texas 78238-5166
	CREATED:	Mar. 1994
	DESCRIPTION:	This module contains routines to generate the SEGS,
			SSECTORS, and NODES sections.  It needs only the
			LINEDEFS and VERTEXES as input.  These three sections
			combine to form a binary space partition tree.  This
			tree is built by recursively dividing the space into
			sections that balance (or at least try to) the number
			of segments and produce the least number of segment
			splits.  The nodes are kept in a binary tree.  The
			segments are kept in an ordered doubly-linked list.
			The created vertices are added to the end of the
			vertex list.  Once the divisions are complete, the
			SEGS, SSECTORS, and NODES structures are created from
			the binary tree and the segment and vertex lists.  Any
			memory allocated for the binary tree or the linked
			list is freed when no longer needed.

			This module does not do any error checking on any
			memory allocation.  If any allocation ever fails, this
			module will bomb.

			This module used to do some error checking while
			building the node tree, but now the tree is generated
			regardless of whether the input describes a correct,
			playable map.

			I wrote the code from the description of the binary
			space partition in the Unofficial DOOM Specs written
			by Matt Fell.  I found these references after I did
			the coding:

			1) Computer Graphics Principles and Practice,
			   2nd ed 1990
			   Foley J.D., van Dam A., Feiner S.K., Hughes J.F.
			   ISBN 0-201-12110-7

			2) "On Visible Surface Generation by a Priori Tree
			   Structures"
			   Fuchs H., Kedem Z.M., Naylor B.F.
			   Computer Graphics (SIGGRAPH '80 Proceedings)
			   v14 #3 July 1980 pp 124-133

			3) "Near Real-Time Shaded Display of Rigid Objects"
			   Fuchs H., Abram G.D., Grant E.D.
			   Computer Graphics (SIGGRAPH '83 Proceesings)
			   v17 #3 July 1983 pp 65-72

			DOOM is a trademark of id Software, Inc.
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "dmglobal.i"

#define tree_branch(c)	((c)=blockmem(NODE_TREE,1), \
			 (c)->left=NULL, (c)->right=NULL, (c))
#define two_sided(l)	(Lines[l].lsidndx != -1)
#define vdist2(v1,v2)	((long)((v1).x-(v2).x)*((v1).x-(v2).x)+\
			 (long)((v1).y-(v2).y)*((v1).y-(v2).y))

typedef struct SEGS_INFO {
	DOOM_SEGS seg;				/* a SEGment */
	struct SEGS_INFO *prev, *next;		/* to previous, next SEGment */
} SEGS_INFO;

typedef struct NODE_TREE {
	short ymin, ymax, xmin, xmax;		/* node rectangle limits */
	SEGS_INFO *pseg;			/* partition line SEG */
	SEGS_INFO *segs;			/* node's SEGS */
	short nsegs;				/* # initial SEGS in node */
	struct NODE_TREE *left, *right;		/* left, right children */
} NODE_TREE;

typedef struct NODE_INFO {
	DOOM_NODE *nodes;			/* all nodes */
	int nnodes;				/* total # NODES */
	DOOM_VERT *sverts;			/* all SEGS vertices */
	int nsverts;				/* total # SEGS vertices */
	DOOM_SEGS *segs;			/* all nodes' SEGS */
	int nsegs;				/* total # segs */
	DOOM_SSECTOR *ssecs;			/* all nodes' SSECTORs */
	int nssecs;				/* total # SSECTORs */
	SEGS_INFO *sinfo;			/* all SEGS lists */
} NODE_INFO;

NODE_INFO ninfo;				/* node information */


/******************************************************************************
	ROUTINE:	nodes_segs_init(lines,nlines)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine initializes the SEGS list by scanning the
			LINEDEFS list and creating the appropriate SEGS
			entries.  A seg is created for each side a LINEDEF has.
			It returns the number of SEGS created.
******************************************************************************/
int nodes_segs_init(lines,nlines)
register DOOM_LINE *lines;
int nlines;
{
  DOOM_VERT *vf, *vt;
  register SEGS_INFO *sinfo;
  register int nsegs;
  register int l;

  nsegs = 0;
  ninfo.sinfo = sinfo = blockmem(SEGS_INFO,1);
  sinfo->prev = NULL;
  for (l = 0; l < nlines; l++) {		/* scan all lines */
    sinfo->seg.fndx = lines[l].fndx;
    sinfo->seg.tndx = lines[l].tndx;
    vf = &ninfo.sverts[sinfo->seg.fndx], vt = &ninfo.sverts[sinfo->seg.tndx];
    sinfo->seg.angle = (bams)(vt->y==vf->y && vt->x<vf->x ? BAMS180 :
                              atan2((double)(vt->y-vf->y),
                                    (double)(vt->x-vf->x))*rad_to_bams+
                              0.5*sgn(vt->y-vf->y));
    sinfo->seg.sndx = 0;			/* right side */
    sinfo->seg.lndx = l;
    sinfo->seg.loffset = 0;
    nsegs++;
    sinfo->next = blockmem(SEGS_INFO,1);	/* set up for next one */
    sinfo->next->prev = sinfo;
    sinfo = sinfo->next;
    if (two_sided(l)) {				/* a left side also */
      sinfo->seg.fndx = lines[l].tndx;		/* switch vertices */
      sinfo->seg.tndx = lines[l].fndx;
      sinfo->seg.angle = sinfo->prev->seg.angle+BAMS180;
      sinfo->seg.sndx = 1;			/* left side */
      sinfo->seg.lndx = l;
      sinfo->seg.loffset = 0;
      nsegs++;
      sinfo->next = blockmem(SEGS_INFO,1);	/* set up for next one */
      sinfo->next->prev = sinfo;
      sinfo = sinfo->next;
    }
  }
  sinfo->prev->next = NULL;
  blockfree(sinfo);				/* don't need this one */
  return nsegs;					/* return # created SEGS */
}


/******************************************************************************
	ROUTINE:	nodes_split_seg(pseg,seg,right,left)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine splits the input segment into left and
			right segments based on the input partition line.  The
			intersection of the partition line (based on the input
			"from" and "to" coordinates) with the segment is found
			so that a new vertex can be added to the vertex list.
			The offset field of the left and right segments are
			computed from the distance to the new vertex along the
			segment.
******************************************************************************/
void nodes_split_seg(pseg,seg,right,left)
SEGS_INFO *pseg, *seg;
register SEGS_INFO **right, **left;
{
  DOOM_VERT *pf = &ninfo.sverts[pseg->seg.fndx],
            *pt = &ninfo.sverts[pseg->seg.tndx],
            *vf = &ninfo.sverts[seg->seg.fndx],
            *vt = &ninfo.sverts[seg->seg.tndx];
  long Ap = -((long)pt->y - pf->y),		/* partition line is */
       Bp = (long)pt->x - pf->x,		/* Ax + By + C = 0   */
       Cp = (long)pt->y*pf->x - (long)pt->x*pf->y;
  long As = -((long)vt->y - vf->y),		/* SEG line is     */
       Bs = (long)vt->x - vf->x,		/* Ax + By + C = 0 */
       Cs = (long)vt->y*vf->x - (long)vt->x*vf->y;
  double x, y;					/* intersection coords */
  DOOM_VERT iv;					/* intersection vertex */
  register int v;				/* intersection vertex index */

  *right = blockmem(SEGS_INFO,1);		/* new right side SEG */
  (*right)->seg = seg->seg;
  (*right)->next = NULL;
  *left = blockmem(SEGS_INFO,1);		/* new left side SEG */
  (*left)->seg = seg->seg;
  (*left)->next = NULL;
  x =  ((double)Bs*Cp - (double)Bp*Cs)/((double)Bp*As - (double)Bs*Ap);
  y = -((double)As*Cp - (double)Ap*Cs)/((double)Bp*As - (double)Bs*Ap);
  iv.x = x + sgn(x)*0.5;
  iv.y = y + sgn(y)*0.5;
  ninfo.sverts[v = ninfo.nsverts++] = iv;	/* add new vertex to list */
  if (seg->seg.sndx == 0) {			/* this is a right side SEG */
    if (Ap*vf->x + Bp*vf->y + Cp < 0) {
      (*right)->seg.tndx = v;
      (*left)->seg.fndx = v;
      (*left)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vf,iv));
    }else {
      (*right)->seg.fndx = v;
      (*right)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vt,iv));
      (*left)->seg.tndx = v;
    }
  }else {					/* this is a left side SEG */
    if (Ap*vt->x + Bp*vt->y + Cp < 0) {
      (*right)->seg.fndx = v;
      (*right)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vt,iv));
      (*left)->seg.tndx = v;
    }else {
      (*right)->seg.tndx = v;
      (*left)->seg.fndx = v;
      (*left)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vf,iv));
    }
  }
}


/******************************************************************************
	ROUTINE:	nodes_insert_seg(seglist,seg,preinsert)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine inserts the input SEG into the SEGS list
			either before or after the SEG that seglist references,
			depending on the preinsert flag.
******************************************************************************/
void nodes_insert_seg(seglist,seg,preinsert)
register SEGS_INFO *seglist, *seg;
int preinsert;
{
  if (preinsert) {				/* insert before */
    seg->prev = seglist->prev;
    seg->next = seglist;
  }else {					/* insert after */
    seg->prev = seglist;
    seg->next = seglist->next;
  }
  if (seg->prev != NULL) seg->prev->next = seg;
  if (seg->next != NULL) seg->next->prev = seg;
}


/******************************************************************************
	ROUTINE:	nodes_segs_bounds(node)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine scans all the SEGS contained in the input
			node to find the minimum and maximum coordinates for
			the node boundaries.
******************************************************************************/
void nodes_segs_bounds(node)
register NODE_TREE *node;
{
  register SEGS_INFO *sinfo;
  register DOOM_VERT *vf, *vt;
  register int s;

  node->xmin = node->ymin = 0x7FFF, node->xmax = node->ymax = 0x8000;
  for (sinfo = node->segs, s = 0; s < node->nsegs; s++) {
    vf = &ninfo.sverts[sinfo->seg.fndx], vt = &ninfo.sverts[sinfo->seg.tndx];
    if (vf->x < node->xmin) node->xmin = vf->x;
    if (vf->y < node->ymin) node->ymin = vf->y;
    if (vt->x < node->xmin) node->xmin = vt->x;
    if (vt->y < node->ymin) node->ymin = vt->y;
    if (node->xmax < vf->x) node->xmax = vf->x;
    if (node->ymax < vf->y) node->ymax = vf->y;
    if (node->xmax < vt->x) node->xmax = vt->x;
    if (node->ymax < vt->y) node->ymax = vt->y;
    sinfo = sinfo->next;
  }
}


/******************************************************************************
	ROUTINE:	nodes_select_side(pseg,seg,sideflag)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine returns whether the input segment is
			on the right side, left side, or both sides of the
			partition line of the input node.  This is done by
			determining on which side of the partition line each
			vertex of the seg lies.  Given that the partition line
			is Ax + By + C = 0 and a vertex is (Vx,Vy), the
			intersection of the partition line and the shortest-
			distance line from the vertex to the partition line
			is given by
				Xi = Vx - b * d
				Yi = Vy - a * d
			where a = B/(A^2+B^2)^.5, b = A/(A^2+B^2)^.5,
			c = C/(A^2+B^2)^.5, and d = a*Vx + b*Vy + c.  Since
			the directional information can be obtained from
			Xi - Vx = Vx - b*d - Vx = -b*d and
			Yi - Vx = Vy - a*d - Vy = -a*d, only d is needed to
			determine which side the vertex lies on.  Thus only
			the sign (-1, 0, or +1) of d = (A*Vx + B*Vx + C) /
			(A^2 + B^2)^.5 needs to be considered.  This simple
			matrix can be used to determine the side:
				"from"       "to" vertex
				vertex	left	on	right

				left	left	left	both
				on	left	?	right
				right	both	right	right	
			For the ? case, the side information in the seg must
			be used to determine the "sidedness".  Right is denoted
			with 0, left denoted by 1, and both denoted by -1.
			A, B, C, and d are calculated only when required to
			enhance the speed of the routine.
******************************************************************************/
int nodes_select_side(pseg,seg)
DOOM_SEGS *pseg, *seg;
{
  static int rightleft[3][3] = { {  1,  1, -1 },
                                 {  1, -2,  0 },
                                 { -1,  0,  0 } };
  static DOOM_VERT *lpf = NULL, *lpt = NULL;	/* last partition line verts */
  static long A, B, C;				/* describes partition line */
  static long pd;
  DOOM_VERT *pf = &ninfo.sverts[pseg->fndx],	/* partition line vertices */
            *pt = &ninfo.sverts[pseg->tndx],
            *vf = &ninfo.sverts[seg->fndx],	/* segment vertices */
            *vt = &ninfo.sverts[seg->tndx];
  long pfd, ptd;
  int sideflag;
  register int fside, tside;			/* "from"/"to" vertex side */

  if (lpf != pf || lpt != pt) {			/* update A,B,C if have to */
    A = -((long)pt->y - pf->y);			/* partition line is */
    B = (long)pt->x - pf->x;			/* Ax + By + C = 0   */
    C = (long)pt->y*pf->x - (long)pt->x*pf->y;
    pd = (long)sqrt((double)A*A+(double)B*B);
    lpf = pf;					/* save new vertices */
    lpt = pt;
  }
  pfd = A*vf->x + B*vf->y + C;
  fside = (pfd>=pd)-(pfd<=-pd);			/* "from" vertex side */
  ptd = A*vt->x + B*vt->y + C;
  tside = (ptd>=pd)-(ptd<=-pd);			/* "to" vertex side */
  sideflag = rightleft[1-fside][1-tside];
  if (sideflag == -2)				/* need to determine based */
    sideflag = pseg->angle != seg->angle;	/* on direction            */
  return sideflag;
}


/******************************************************************************
	ROUTINE:	nodes_divide_node(node,left,right)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine divides the input node into left and
			right nodes based on the partition line of the input
			node.  This essentially means that the list of SEGS
			associated with the input node must be divided into
			left and right collections of SEGS.  This division is
			done by moving all the left side SEGS to the end of
			the SEGS list, leaving all right side SEGS at the front
			of the list.  Those SEGS that need to be split have
			their new right side SEG take the position of the old
			SEG and their new left side SEG put at the end of the
			list.  Once the list is divided, the right and left
			nodes are set the appropriate section of the list and
			their bounds are computed.
******************************************************************************/
void nodes_divide_node(node,right,left)
register NODE_TREE *node;
NODE_TREE *right, *left;
{
  int sideflag;
  int i;
  SEGS_INFO *next, *end;
  SEGS_INFO *lseg, *rseg;			/* for splitting seg in two */
  register SEGS_INFO *sinfo;

  sinfo = node->segs;
  right->nsegs = left->nsegs = 0;
  for (end = sinfo, i = 0; i < node->nsegs-1; i++) end = end->next;
  for (i = 0; i < node->nsegs; i++) {		/* scan all node's SEGS */
    sideflag = nodes_select_side(&node->pseg->seg,&sinfo->seg);
    next = sinfo->next;
    switch (sideflag) {
      bcase  0: right->nsegs++;			/* just add to right's total */
      bcase  1: if (sinfo->prev != NULL)	/* move to end of list */
                  sinfo->prev->next = sinfo->next;
                if (sinfo->next != NULL)
                  sinfo->next->prev = sinfo->prev;
                if (end == sinfo) end = sinfo->prev;
                if (node->segs == sinfo) node->segs = sinfo->next;
                nodes_insert_seg(end,sinfo,FALSE);
                end = sinfo;
                left->nsegs++;
      bcase -1: nodes_split_seg(node->pseg,sinfo,&rseg,&lseg);
                sinfo->seg = rseg->seg;		/* make this the right SEG */
                right->nsegs++;
                blockfree(rseg);		/* don't need this now */
                if (end == sinfo) node->segs = sinfo->prev;
                nodes_insert_seg(end,lseg,FALSE);/* add left SEG to end */
                end = lseg;
                left->nsegs++;
                ninfo.nsegs++;			/* one more for total */
    }
    sinfo = next;
  }
  for (sinfo = node->segs, i = 0; i < right->nsegs; i++)
    sinfo = sinfo->next;
  right->segs = node->segs;			/* SEGS on right side of   */
  nodes_segs_bounds(right);			/* partition line are here */
  left->segs = sinfo;				/* EGS on left side of     */
  nodes_segs_bounds(left);			/* partition line are here */
}


/******************************************************************************
	ROUTINE:	nodes_partition_line(node)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine searches for a suitable SEG to use as a
			partition line (which will divide the input node).
			Suitable is taken to mean the SEG that most equalizes
			the number of SEGS on each side of the partition line
			and mimimizes the number of SEG splits that need to be
			done.  Ideally, the partition line should also do
			this for all the node's children as well, but the
			calculations would be far too time consuming; therefore
			only the input node is considered.  The most suitable
			partition is found by selecting the SEG that maximizes
			the (geometric mean)^2 of the right and left side
			counts and the number of splits.  The geometric means
			are computed via A*Rc*Lc/(B*Sc+1) where Rc, Lc, Sc
			are the right side, left side, and split counts
			respectively and A, B are empirical constants (the
			+1 is for the split count zero case).  The geometric
			mean variables are initialized to -1 so that at least
			one SEG will qualify (even if the maximum mean is
			zero).  Two means are computed: interior-only SEGS,
			and all SEGS.  The interior-only SEGS mean is computed
			by noting that a border SEG will put the SEGS all on
			one side or the other so that the right or left number
			of SEGS will equal the number of SEGS in the node.
			The interior-only mean is chosen if is >= zero, and
			then the all mean.  This routine sets the partition
			line fields of the input node with the indices of the
			appropriate VERTEXES.
******************************************************************************/
void nodes_partition_line(node)
register NODE_TREE *node;
{
  long agm=-1, igm=-1;				/* max geometric mean counts */
  long gm;					/* geometric mean count */
  int apndx, ipndx;				/* partition line indices */
  int rcnt, lcnt, splits;
  register int sideflag;
  register SEGS_INFO *sinfo, *iseg;
  register int s, i;

  sinfo = node->segs;
  for (s = 0; s < node->nsegs; s++) {		/* scan SEGS in node */
    printf(s&1?"/\010":"\\\010");
    node->pseg = sinfo;				/* try as partition line */
    rcnt = lcnt = splits = 0;
    iseg = node->segs;
    for (i = 0; i < node->nsegs; i++) {
      sideflag = nodes_select_side(&node->pseg->seg,&iseg->seg);
      if (sideflag == 0)       rcnt++;		/* count SEGS on both sides */
      else if (sideflag == 1)  lcnt++;		/* of the partition line    */
      else if (sideflag == -1) splits++;
      iseg = iseg->next;
    }
    gm = 200*rcnt*lcnt/(16*splits/3+1);		/* 200, 16/3 are empirical */
    if (agm < gm) agm = gm, apndx = s;
    if (rcnt != node->nsegs && lcnt != node->nsegs)
      if (igm < gm) igm = gm, ipndx = s;
    sinfo = sinfo->next;
  }
  if (igm >= 0) s = ipndx;
  else          s = apndx;
	/* assign partition line; note that this SEG may be split   */
	/* later and so won't represent the SEG as it currently is, */
	/* but I don't think it really matters since it will still  */
	/* represent the partition line                             */
  node->pseg = node->segs;
  for (i = 0; i < s; i++) node->pseg = node->pseg->next;
}


/******************************************************************************
	ROUTINE:	nodes_subsector_test(node)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine checks whether the input node can be
			an SSECTOR or not.  To be a subsector, the SEGS in
			the node must describe a convex polygon (no interior
			angles > 180 degrees).
******************************************************************************/
int nodes_subsector_test(node)
register NODE_TREE *node;
{
  int subsector = TRUE;
  register SEGS_INFO *sinfo, *iseg;
  register int s, i;

  sinfo = node->segs;
  for (s = 0; subsector && s < node->nsegs; s++) {/* scan all SEGS */
    for (iseg = node->segs, i = 0; i < node->nsegs; i++) {
      if (i != s) {
        if (nodes_select_side(&sinfo->seg,&iseg->seg) != 0) {
          subsector = FALSE;			/* interior angle > 180 degs */
          break;				/* so not an SSECTOR         */
        }
      }
      iseg = iseg->next;
    }
    sinfo = sinfo->next;
  }
  return subsector;
}


/******************************************************************************
	ROUTINE:	nodes_partition_node(node)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine performs the binary space partitioning.
			It recursively divides (partitions) the input node
			until each leaf of the subtree defined by the input
			node is an SSECTOR.  A partition line is obtained and
			the left and right subtrees are allocated.  The left
			subtree is always checked first.  If it is not an
			SSECTOR, a recursive call is made to further divide
			the left subtree.  The same procedure is then performed
			on the right subtree.  The number of left and right
			children plus one for the current node is returned.
******************************************************************************/
int nodes_partition_node(node)
register NODE_TREE *node;
{
  int nl, nr;					/* # left, right nodes */
  register NODE_TREE *left, *right;		/* left, right children */

  nodes_partition_line(node);			/* obtain partition line */
  node->right = tree_branch(right);
  node->left = tree_branch(left);
  nodes_divide_node(node,right,left);
  if (right->nsegs == 0 ||
      nodes_subsector_test(left)) {		/* found an SSECTOR */
    if (right->nsegs == 0)
      printf("\n<<error, going on with Partition Line %d==>%d>>\n",
             node->pseg->seg.fndx,node->pseg->seg.tndx);
    printf("*\010\010");
    nl = 1;
  }else {					/* need further subdivision */
    printf("L");
    nl = nodes_partition_node(left);
  }
  if (left->nsegs == 0 ||
      nodes_subsector_test(right)) {		/* found an SSECTOR */
    if (left->nsegs == 0)
      printf("\n<<error, going on with Partition Line %d==>%d>>\n",
              node->pseg->seg.fndx,node->pseg->seg.tndx);
    printf("*\010\010");
    nr = 1;
  }else {					/* need further subdivision */
    printf("R");
    nr = nodes_partition_node(right);
  }
  return nl + nr + 1;				/* # left + # right + this 1 */
}


/******************************************************************************
	ROUTINE:	nodes_place_node(nodes,nndx,sndx,nodetree)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine builds the NODES structure from the
			input node tree.  It traverses the node tree in a
			post-order fashion, left side first.  As the tree is
			scanned, the NODES, SSECTORS, and SEGS lists are filled
			in as appropriate.  The SSECTORS and SEGS lists are
			referenced through the ninfo block.  The node tree
			entries are deleted after they are used.  The node
			number (or index) is returned, unless an SSECTOR is
			found, then a -(SSECTOR number) is returned.
******************************************************************************/
int nodes_place_node(nodes,nndx,sndx,nodetree)
register DOOM_NODE *nodes;
int *nndx, *sndx;
register NODE_TREE *nodetree;
{
  int nnum;					/* node number to return */
  int lnum, rnum;
  SEGS_INFO *sinfo, *next;
  register DOOM_NODE *node;
  register int s;

  if (nodetree->left != NULL) {			/* traverse node subtree */
    lnum = nodes_place_node(nodes,nndx,sndx,nodetree->left);
    rnum = nodes_place_node(nodes,nndx,sndx,nodetree->right);
    node = &nodes[nnum = (*nndx)++];
    node->x = ninfo.sverts[nodetree->pseg->seg.fndx].x;/* these 4 describe   */
    node->y = ninfo.sverts[nodetree->pseg->seg.fndx].y;/* the partition line */
    node->xdel = ninfo.sverts[nodetree->pseg->seg.tndx].x - node->x;
    node->ydel = ninfo.sverts[nodetree->pseg->seg.tndx].y - node->y;
    node->lymax = nodetree->left->ymax;
    node->lymin = nodetree->left->ymin;
    node->lxmin = nodetree->left->xmin;
    node->lxmax = nodetree->left->xmax;
    if (lnum < 0) node->nndx[1] = 0x8000 | (-lnum-1);/* mark as SSECTOR */
    else          node->nndx[1] = lnum;		/* mark as NODE */
    blockfree(nodetree->left);			/* done with left subtree */
    node->rymax = nodetree->right->ymax;
    node->rymin = nodetree->right->ymin;
    node->rxmin = nodetree->right->xmin;
    node->rxmax = nodetree->right->xmax;
    if (rnum < 0) node->nndx[0] = 0x8000 | (-rnum-1);/* mark as SSECTOR */
    else          node->nndx[0] = rnum;		/* mark as NODE */
    blockfree(nodetree->right);			/* done with right subtree */
  }else {					/* SSECTOR (tree leaf) */
    ninfo.ssecs[*sndx].count = nodetree->nsegs;
    if (*sndx == 0) ninfo.ssecs[*sndx].sndx = 0;
    else            ninfo.ssecs[*sndx].sndx = ninfo.ssecs[*sndx-1].sndx+
                                              ninfo.ssecs[*sndx-1].count;
    sinfo = nodetree->segs;
    for (s = 0; s < nodetree->nsegs; s++) {	/* copy node's SEGS to full */
      ninfo.segs[ninfo.nsegs++] = sinfo->seg;	/* SEGS array               */
      next = sinfo->next;
      blockfree(sinfo);
      sinfo = next;
    }
    nnum = -++(*sndx);				/* mark as leaf */
  }
  return nnum;					/* ret node # or <0 if leaf */
}


/******************************************************************************
	ROUTINE:	nodes_make(nodes,nnodes,ssecs,nssecs,segs,nsegs,
			           verts,nverts,lines,nlines)
	WRITTEN BY:	Robert Fenske, Jr.
	CREATED:	Mar. 1994
	DESCRIPTION:	This routine generates the NODES, SSECTORS, and SEGS
			sections.  It first finds the minimum and maximum x,y
			coordinates of the map to use in the root of the node
			tree.  Then the node tree root is created.  The
			necessary counters in the ninfo block are zeroed and
			the SEGS vertices list is allocated.  Then
			nodes_partition_node() is called to build the node
			tree.  Next, the NODES, SSECTORS, and SEGS lists are
			allocated based on the values calculated during the
			construction of the node tree.  The necessary counters
			are zeroed and nodes_place_node() is called to fill
			the NODES, SSECTORS, and SEGS lists with the correct
			information.  All the appropriate values are placed
			into the return variables and the number of computed
			node entries is returned.
******************************************************************************/
int nodes_make(nodes,nnodes,ssecs,nssecs,segs,nsegs,verts,nverts,lines,nlines)
DOOM_NODE **nodes;
int *nnodes;
DOOM_SSECTOR **ssecs;
int *nssecs;
DOOM_SEGS **segs;
int *nsegs;
DOOM_VERT **verts;
int *nverts;
DOOM_LINE **lines;
int *nlines;
{
  NODE_TREE *nodetree;				/* BSP node tree */
  register int i;

  ninfo.nsverts = -1;
  for (i = 0; i < *nlines; i++) {		/* find maximum used vertex */
    if (ninfo.nsverts < (*lines)[i].fndx) ninfo.nsverts = (*lines)[i].fndx;
    if (ninfo.nsverts < (*lines)[i].tndx) ninfo.nsverts = (*lines)[i].tndx;
  }
  ninfo.nsverts++;
  ninfo.sverts = blockmem(DOOM_VERT,2*ninfo.nsverts);/* assume no more than  */
  for (i = 0; i < ninfo.nsverts; i++)		/* nsverts new verts created */
    ninfo.sverts[i] = (*verts)[i];
  ninfo.nsegs = nodes_segs_init(*lines,*nlines);/* initialize SEGS list */
  nodetree = tree_branch(nodetree);		/* node tree root */
  nodetree->nsegs = ninfo.nsegs;
  nodetree->segs = ninfo.sinfo;
  nodes_segs_bounds(nodetree);
  printf("%d sides ==>  ",ninfo.nsegs);
  ninfo.nnodes = nodes_partition_node(nodetree)/2;/* BSP it */
  ninfo.nodes = blockmem(DOOM_NODE,ninfo.nnodes);
  ninfo.nssecs = ninfo.nnodes+1;		/* always 1 more SSECTOR */
  ninfo.ssecs = blockmem(DOOM_SSECTOR,ninfo.nssecs);
  ninfo.segs = blockmem(DOOM_SEGS,ninfo.nsegs);
  ninfo.nsegs = ninfo.nssecs = ninfo.nnodes = 0;
  (void)nodes_place_node(ninfo.nodes,&ninfo.nnodes,&ninfo.nssecs,nodetree);
  if (nodes != NULL)  *nodes = ninfo.nodes;
  if (nnodes != NULL) *nnodes = ninfo.nnodes;
  if (ssecs != NULL)  *ssecs = ninfo.ssecs;
  if (nssecs != NULL) *nssecs = ninfo.nssecs;
  if (segs != NULL)   *segs = ninfo.segs;
  if (nsegs != NULL)  *nsegs = ninfo.nsegs;
  if (verts != NULL)  *verts = ninfo.sverts;
  if (nverts != NULL) *nverts = ninfo.nsverts;
  blockfree(nodetree);				/* done with the node tree */
  return *nnodes;				/* return number of nodes */
}
