/****************************************************************************** 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 #include #include #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->xx ? 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<%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<%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 */ }