home *** CD-ROM | disk | FTP | other *** search
/ Doom I/II Collection / DM12.ISO / edit / vnb / nodes.c < prev    next >
C/C++ Source or Header  |  1994-05-24  |  29KB  |  701 lines
  1. /******************************************************************************
  2.     MODULE:        NODES.C
  3.     WRITTEN BY:    Robert Fenske, Jr. (rfenske@swri.edu)
  4.                 Southwest Research Institute
  5.                 Electromagnetics Division
  6.                 6220 Culebra
  7.                 San Antonio, Texas 78238-5166
  8.     CREATED:    Mar. 1994
  9.     DESCRIPTION:    This module contains routines to generate the SEGS,
  10.             SSECTORS, and NODES sections.  It needs only the
  11.             LINEDEFS and VERTEXES as input.  These three sections
  12.             combine to form a binary space partition tree.  This
  13.             tree is built by recursively dividing the space into
  14.             sections that balance (or at least try to) the number
  15.             of segments and produce the least number of segment
  16.             splits.  The nodes are kept in a binary tree.  The
  17.             segments are kept in an ordered doubly-linked list.
  18.             The created vertices are added to the end of the
  19.             vertex list.  Once the divisions are complete, the
  20.             SEGS, SSECTORS, and NODES structures are created from
  21.             the binary tree and the segment and vertex lists.  Any
  22.             memory allocated for the binary tree or the linked
  23.             list is freed when no longer needed.
  24.  
  25.             This module does not do any error checking on any
  26.             memory allocation.  If any allocation ever fails, this
  27.             module will bomb.
  28.  
  29.             This module used to do some error checking while
  30.             building the node tree, but now the tree is generated
  31.             regardless of whether the input describes a correct,
  32.             playable map.
  33.  
  34.             I wrote the code from the description of the binary
  35.             space partition in the Unofficial DOOM Specs written
  36.             by Matt Fell.  I found these references after I did
  37.             the coding:
  38.  
  39.             1) Computer Graphics Principles and Practice,
  40.                2nd ed 1990
  41.                Foley J.D., van Dam A., Feiner S.K., Hughes J.F.
  42.                ISBN 0-201-12110-7
  43.  
  44.             2) "On Visible Surface Generation by a Priori Tree
  45.                Structures"
  46.                Fuchs H., Kedem Z.M., Naylor B.F.
  47.                Computer Graphics (SIGGRAPH '80 Proceedings)
  48.                v14 #3 July 1980 pp 124-133
  49.  
  50.             3) "Near Real-Time Shaded Display of Rigid Objects"
  51.                Fuchs H., Abram G.D., Grant E.D.
  52.                Computer Graphics (SIGGRAPH '83 Proceesings)
  53.                v17 #3 July 1983 pp 65-72
  54.  
  55.             DOOM is a trademark of id Software, Inc.
  56. ******************************************************************************/
  57. #include <stdio.h>
  58. #include <stdlib.h>
  59. #include <math.h>
  60. #include "dmglobal.i"
  61.  
  62. #define tree_branch(c)    ((c)=blockmem(NODE_TREE,1), \
  63.              (c)->left=NULL, (c)->right=NULL, (c))
  64. #define two_sided(l)    (Lines[l].lsidndx != -1)
  65. #define vdist2(v1,v2)    ((long)((v1).x-(v2).x)*((v1).x-(v2).x)+\
  66.              (long)((v1).y-(v2).y)*((v1).y-(v2).y))
  67.  
  68. typedef struct SEGS_INFO {
  69.     DOOM_SEGS seg;                /* a SEGment */
  70.     struct SEGS_INFO *prev, *next;        /* to previous, next SEGment */
  71. } SEGS_INFO;
  72.  
  73. typedef struct NODE_TREE {
  74.     short ymin, ymax, xmin, xmax;        /* node rectangle limits */
  75.     SEGS_INFO *pseg;            /* partition line SEG */
  76.     SEGS_INFO *segs;            /* node's SEGS */
  77.     short nsegs;                /* # initial SEGS in node */
  78.     struct NODE_TREE *left, *right;        /* left, right children */
  79. } NODE_TREE;
  80.  
  81. typedef struct NODE_INFO {
  82.     DOOM_NODE *nodes;            /* all nodes */
  83.     int nnodes;                /* total # NODES */
  84.     DOOM_VERT *sverts;            /* all SEGS vertices */
  85.     int nsverts;                /* total # SEGS vertices */
  86.     DOOM_SEGS *segs;            /* all nodes' SEGS */
  87.     int nsegs;                /* total # segs */
  88.     DOOM_SSECTOR *ssecs;            /* all nodes' SSECTORs */
  89.     int nssecs;                /* total # SSECTORs */
  90.     SEGS_INFO *sinfo;            /* all SEGS lists */
  91. } NODE_INFO;
  92.  
  93. NODE_INFO ninfo;                /* node information */
  94.  
  95.  
  96. /******************************************************************************
  97.     ROUTINE:    nodes_segs_init(lines,nlines)
  98.     WRITTEN BY:    Robert Fenske, Jr.
  99.     CREATED:    Mar. 1994
  100.     DESCRIPTION:    This routine initializes the SEGS list by scanning the
  101.             LINEDEFS list and creating the appropriate SEGS
  102.             entries.  A seg is created for each side a LINEDEF has.
  103.             It returns the number of SEGS created.
  104. ******************************************************************************/
  105. int nodes_segs_init(lines,nlines)
  106. register DOOM_LINE *lines;
  107. int nlines;
  108. {
  109.   DOOM_VERT *vf, *vt;
  110.   register SEGS_INFO *sinfo;
  111.   register int nsegs;
  112.   register int l;
  113.  
  114.   nsegs = 0;
  115.   ninfo.sinfo = sinfo = blockmem(SEGS_INFO,1);
  116.   sinfo->prev = NULL;
  117.   for (l = 0; l < nlines; l++) {        /* scan all lines */
  118.     sinfo->seg.fndx = lines[l].fndx;
  119.     sinfo->seg.tndx = lines[l].tndx;
  120.     vf = &ninfo.sverts[sinfo->seg.fndx], vt = &ninfo.sverts[sinfo->seg.tndx];
  121.     sinfo->seg.angle = (bams)(vt->y==vf->y && vt->x<vf->x ? BAMS180 :
  122.                               atan2((double)(vt->y-vf->y),
  123.                                     (double)(vt->x-vf->x))*rad_to_bams+
  124.                               0.5*sgn(vt->y-vf->y));
  125.     sinfo->seg.sndx = 0;            /* right side */
  126.     sinfo->seg.lndx = l;
  127.     sinfo->seg.loffset = 0;
  128.     nsegs++;
  129.     sinfo->next = blockmem(SEGS_INFO,1);    /* set up for next one */
  130.     sinfo->next->prev = sinfo;
  131.     sinfo = sinfo->next;
  132.     if (two_sided(l)) {                /* a left side also */
  133.       sinfo->seg.fndx = lines[l].tndx;        /* switch vertices */
  134.       sinfo->seg.tndx = lines[l].fndx;
  135.       sinfo->seg.angle = sinfo->prev->seg.angle+BAMS180;
  136.       sinfo->seg.sndx = 1;            /* left side */
  137.       sinfo->seg.lndx = l;
  138.       sinfo->seg.loffset = 0;
  139.       nsegs++;
  140.       sinfo->next = blockmem(SEGS_INFO,1);    /* set up for next one */
  141.       sinfo->next->prev = sinfo;
  142.       sinfo = sinfo->next;
  143.     }
  144.   }
  145.   sinfo->prev->next = NULL;
  146.   blockfree(sinfo);                /* don't need this one */
  147.   return nsegs;                    /* return # created SEGS */
  148. }
  149.  
  150.  
  151. /******************************************************************************
  152.     ROUTINE:    nodes_split_seg(pseg,seg,right,left)
  153.     WRITTEN BY:    Robert Fenske, Jr.
  154.     CREATED:    Mar. 1994
  155.     DESCRIPTION:    This routine splits the input segment into left and
  156.             right segments based on the input partition line.  The
  157.             intersection of the partition line (based on the input
  158.             "from" and "to" coordinates) with the segment is found
  159.             so that a new vertex can be added to the vertex list.
  160.             The offset field of the left and right segments are
  161.             computed from the distance to the new vertex along the
  162.             segment.
  163. ******************************************************************************/
  164. void nodes_split_seg(pseg,seg,right,left)
  165. SEGS_INFO *pseg, *seg;
  166. register SEGS_INFO **right, **left;
  167. {
  168.   DOOM_VERT *pf = &ninfo.sverts[pseg->seg.fndx],
  169.             *pt = &ninfo.sverts[pseg->seg.tndx],
  170.             *vf = &ninfo.sverts[seg->seg.fndx],
  171.             *vt = &ninfo.sverts[seg->seg.tndx];
  172.   long Ap = -((long)pt->y - pf->y),        /* partition line is */
  173.        Bp = (long)pt->x - pf->x,        /* Ax + By + C = 0   */
  174.        Cp = (long)pt->y*pf->x - (long)pt->x*pf->y;
  175.   long As = -((long)vt->y - vf->y),        /* SEG line is     */
  176.        Bs = (long)vt->x - vf->x,        /* Ax + By + C = 0 */
  177.        Cs = (long)vt->y*vf->x - (long)vt->x*vf->y;
  178.   double x, y;                    /* intersection coords */
  179.   DOOM_VERT iv;                    /* intersection vertex */
  180.   register int v;                /* intersection vertex index */
  181.  
  182.   *right = blockmem(SEGS_INFO,1);        /* new right side SEG */
  183.   (*right)->seg = seg->seg;
  184.   (*right)->next = NULL;
  185.   *left = blockmem(SEGS_INFO,1);        /* new left side SEG */
  186.   (*left)->seg = seg->seg;
  187.   (*left)->next = NULL;
  188.   x =  ((double)Bs*Cp - (double)Bp*Cs)/((double)Bp*As - (double)Bs*Ap);
  189.   y = -((double)As*Cp - (double)Ap*Cs)/((double)Bp*As - (double)Bs*Ap);
  190.   iv.x = x + sgn(x)*0.5;
  191.   iv.y = y + sgn(y)*0.5;
  192.   ninfo.sverts[v = ninfo.nsverts++] = iv;    /* add new vertex to list */
  193.   if (seg->seg.sndx == 0) {            /* this is a right side SEG */
  194.     if (Ap*vf->x + Bp*vf->y + Cp < 0) {
  195.       (*right)->seg.tndx = v;
  196.       (*left)->seg.fndx = v;
  197.       (*left)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vf,iv));
  198.     }else {
  199.       (*right)->seg.fndx = v;
  200.       (*right)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vt,iv));
  201.       (*left)->seg.tndx = v;
  202.     }
  203.   }else {                    /* this is a left side SEG */
  204.     if (Ap*vt->x + Bp*vt->y + Cp < 0) {
  205.       (*right)->seg.fndx = v;
  206.       (*right)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vt,iv));
  207.       (*left)->seg.tndx = v;
  208.     }else {
  209.       (*right)->seg.tndx = v;
  210.       (*left)->seg.fndx = v;
  211.       (*left)->seg.loffset = seg->seg.loffset + sqrt((double)vdist2(*vf,iv));
  212.     }
  213.   }
  214. }
  215.  
  216.  
  217. /******************************************************************************
  218.     ROUTINE:    nodes_insert_seg(seglist,seg,preinsert)
  219.     WRITTEN BY:    Robert Fenske, Jr.
  220.     CREATED:    Mar. 1994
  221.     DESCRIPTION:    This routine inserts the input SEG into the SEGS list
  222.             either before or after the SEG that seglist references,
  223.             depending on the preinsert flag.
  224. ******************************************************************************/
  225. void nodes_insert_seg(seglist,seg,preinsert)
  226. register SEGS_INFO *seglist, *seg;
  227. int preinsert;
  228. {
  229.   if (preinsert) {                /* insert before */
  230.     seg->prev = seglist->prev;
  231.     seg->next = seglist;
  232.   }else {                    /* insert after */
  233.     seg->prev = seglist;
  234.     seg->next = seglist->next;
  235.   }
  236.   if (seg->prev != NULL) seg->prev->next = seg;
  237.   if (seg->next != NULL) seg->next->prev = seg;
  238. }
  239.  
  240.  
  241. /******************************************************************************
  242.     ROUTINE:    nodes_segs_bounds(node)
  243.     WRITTEN BY:    Robert Fenske, Jr.
  244.     CREATED:    Mar. 1994
  245.     DESCRIPTION:    This routine scans all the SEGS contained in the input
  246.             node to find the minimum and maximum coordinates for
  247.             the node boundaries.
  248. ******************************************************************************/
  249. void nodes_segs_bounds(node)
  250. register NODE_TREE *node;
  251. {
  252.   register SEGS_INFO *sinfo;
  253.   register DOOM_VERT *vf, *vt;
  254.   register int s;
  255.  
  256.   node->xmin = node->ymin = 0x7FFF, node->xmax = node->ymax = 0x8000;
  257.   for (sinfo = node->segs, s = 0; s < node->nsegs; s++) {
  258.     vf = &ninfo.sverts[sinfo->seg.fndx], vt = &ninfo.sverts[sinfo->seg.tndx];
  259.     if (vf->x < node->xmin) node->xmin = vf->x;
  260.     if (vf->y < node->ymin) node->ymin = vf->y;
  261.     if (vt->x < node->xmin) node->xmin = vt->x;
  262.     if (vt->y < node->ymin) node->ymin = vt->y;
  263.     if (node->xmax < vf->x) node->xmax = vf->x;
  264.     if (node->ymax < vf->y) node->ymax = vf->y;
  265.     if (node->xmax < vt->x) node->xmax = vt->x;
  266.     if (node->ymax < vt->y) node->ymax = vt->y;
  267.     sinfo = sinfo->next;
  268.   }
  269. }
  270.  
  271.  
  272. /******************************************************************************
  273.     ROUTINE:    nodes_select_side(pseg,seg,sideflag)
  274.     WRITTEN BY:    Robert Fenske, Jr.
  275.     CREATED:    Mar. 1994
  276.     DESCRIPTION:    This routine returns whether the input segment is
  277.             on the right side, left side, or both sides of the
  278.             partition line of the input node.  This is done by
  279.             determining on which side of the partition line each
  280.             vertex of the seg lies.  Given that the partition line
  281.             is Ax + By + C = 0 and a vertex is (Vx,Vy), the
  282.             intersection of the partition line and the shortest-
  283.             distance line from the vertex to the partition line
  284.             is given by
  285.                 Xi = Vx - b * d
  286.                 Yi = Vy - a * d
  287.             where a = B/(A^2+B^2)^.5, b = A/(A^2+B^2)^.5,
  288.             c = C/(A^2+B^2)^.5, and d = a*Vx + b*Vy + c.  Since
  289.             the directional information can be obtained from
  290.             Xi - Vx = Vx - b*d - Vx = -b*d and
  291.             Yi - Vx = Vy - a*d - Vy = -a*d, only d is needed to
  292.             determine which side the vertex lies on.  Thus only
  293.             the sign (-1, 0, or +1) of d = (A*Vx + B*Vx + C) /
  294.             (A^2 + B^2)^.5 needs to be considered.  This simple
  295.             matrix can be used to determine the side:
  296.                 "from"       "to" vertex
  297.                 vertex    left    on    right
  298.  
  299.                 left    left    left    both
  300.                 on    left    ?    right
  301.                 right    both    right    right    
  302.             For the ? case, the side information in the seg must
  303.             be used to determine the "sidedness".  Right is denoted
  304.             with 0, left denoted by 1, and both denoted by -1.
  305.             A, B, C, and d are calculated only when required to
  306.             enhance the speed of the routine.
  307. ******************************************************************************/
  308. int nodes_select_side(pseg,seg)
  309. DOOM_SEGS *pseg, *seg;
  310. {
  311.   static int rightleft[3][3] = { {  1,  1, -1 },
  312.                                  {  1, -2,  0 },
  313.                                  { -1,  0,  0 } };
  314.   static DOOM_VERT *lpf = NULL, *lpt = NULL;    /* last partition line verts */
  315.   static long A, B, C;                /* describes partition line */
  316.   static long pd;
  317.   DOOM_VERT *pf = &ninfo.sverts[pseg->fndx],    /* partition line vertices */
  318.             *pt = &ninfo.sverts[pseg->tndx],
  319.             *vf = &ninfo.sverts[seg->fndx],    /* segment vertices */
  320.             *vt = &ninfo.sverts[seg->tndx];
  321.   long pfd, ptd;
  322.   int sideflag;
  323.   register int fside, tside;            /* "from"/"to" vertex side */
  324.  
  325.   if (lpf != pf || lpt != pt) {            /* update A,B,C if have to */
  326.     A = -((long)pt->y - pf->y);            /* partition line is */
  327.     B = (long)pt->x - pf->x;            /* Ax + By + C = 0   */
  328.     C = (long)pt->y*pf->x - (long)pt->x*pf->y;
  329.     pd = (long)sqrt((double)A*A+(double)B*B);
  330.     lpf = pf;                    /* save new vertices */
  331.     lpt = pt;
  332.   }
  333.   pfd = A*vf->x + B*vf->y + C;
  334.   fside = (pfd>=pd)-(pfd<=-pd);            /* "from" vertex side */
  335.   ptd = A*vt->x + B*vt->y + C;
  336.   tside = (ptd>=pd)-(ptd<=-pd);            /* "to" vertex side */
  337.   sideflag = rightleft[1-fside][1-tside];
  338.   if (sideflag == -2)                /* need to determine based */
  339.     sideflag = pseg->angle != seg->angle;    /* on direction            */
  340.   return sideflag;
  341. }
  342.  
  343.  
  344. /******************************************************************************
  345.     ROUTINE:    nodes_divide_node(node,left,right)
  346.     WRITTEN BY:    Robert Fenske, Jr.
  347.     CREATED:    Mar. 1994
  348.     DESCRIPTION:    This routine divides the input node into left and
  349.             right nodes based on the partition line of the input
  350.             node.  This essentially means that the list of SEGS
  351.             associated with the input node must be divided into
  352.             left and right collections of SEGS.  This division is
  353.             done by moving all the left side SEGS to the end of
  354.             the SEGS list, leaving all right side SEGS at the front
  355.             of the list.  Those SEGS that need to be split have
  356.             their new right side SEG take the position of the old
  357.             SEG and their new left side SEG put at the end of the
  358.             list.  Once the list is divided, the right and left
  359.             nodes are set the appropriate section of the list and
  360.             their bounds are computed.
  361. ******************************************************************************/
  362. void nodes_divide_node(node,right,left)
  363. register NODE_TREE *node;
  364. NODE_TREE *right, *left;
  365. {
  366.   int sideflag;
  367.   int i;
  368.   SEGS_INFO *next, *end;
  369.   SEGS_INFO *lseg, *rseg;            /* for splitting seg in two */
  370.   register SEGS_INFO *sinfo;
  371.  
  372.   sinfo = node->segs;
  373.   right->nsegs = left->nsegs = 0;
  374.   for (end = sinfo, i = 0; i < node->nsegs-1; i++) end = end->next;
  375.   for (i = 0; i < node->nsegs; i++) {        /* scan all node's SEGS */
  376.     sideflag = nodes_select_side(&node->pseg->seg,&sinfo->seg);
  377.     next = sinfo->next;
  378.     switch (sideflag) {
  379.       bcase  0: right->nsegs++;            /* just add to right's total */
  380.       bcase  1: if (sinfo->prev != NULL)    /* move to end of list */
  381.                   sinfo->prev->next = sinfo->next;
  382.                 if (sinfo->next != NULL)
  383.                   sinfo->next->prev = sinfo->prev;
  384.                 if (end == sinfo) end = sinfo->prev;
  385.                 if (node->segs == sinfo) node->segs = sinfo->next;
  386.                 nodes_insert_seg(end,sinfo,FALSE);
  387.                 end = sinfo;
  388.                 left->nsegs++;
  389.       bcase -1: nodes_split_seg(node->pseg,sinfo,&rseg,&lseg);
  390.                 sinfo->seg = rseg->seg;        /* make this the right SEG */
  391.                 right->nsegs++;
  392.                 blockfree(rseg);        /* don't need this now */
  393.                 if (end == sinfo) node->segs = sinfo->prev;
  394.                 nodes_insert_seg(end,lseg,FALSE);/* add left SEG to end */
  395.                 end = lseg;
  396.                 left->nsegs++;
  397.                 ninfo.nsegs++;            /* one more for total */
  398.     }
  399.     sinfo = next;
  400.   }
  401.   for (sinfo = node->segs, i = 0; i < right->nsegs; i++)
  402.     sinfo = sinfo->next;
  403.   right->segs = node->segs;            /* SEGS on right side of   */
  404.   nodes_segs_bounds(right);            /* partition line are here */
  405.   left->segs = sinfo;                /* EGS on left side of     */
  406.   nodes_segs_bounds(left);            /* partition line are here */
  407. }
  408.  
  409.  
  410. /******************************************************************************
  411.     ROUTINE:    nodes_partition_line(node)
  412.     WRITTEN BY:    Robert Fenske, Jr.
  413.     CREATED:    Mar. 1994
  414.     DESCRIPTION:    This routine searches for a suitable SEG to use as a
  415.             partition line (which will divide the input node).
  416.             Suitable is taken to mean the SEG that most equalizes
  417.             the number of SEGS on each side of the partition line
  418.             and mimimizes the number of SEG splits that need to be
  419.             done.  Ideally, the partition line should also do
  420.             this for all the node's children as well, but the
  421.             calculations would be far too time consuming; therefore
  422.             only the input node is considered.  The most suitable
  423.             partition is found by selecting the SEG that maximizes
  424.             the (geometric mean)^2 of the right and left side
  425.             counts and the number of splits.  The geometric means
  426.             are computed via A*Rc*Lc/(B*Sc+1) where Rc, Lc, Sc
  427.             are the right side, left side, and split counts
  428.             respectively and A, B are empirical constants (the
  429.             +1 is for the split count zero case).  The geometric
  430.             mean variables are initialized to -1 so that at least
  431.             one SEG will qualify (even if the maximum mean is
  432.             zero).  Two means are computed: interior-only SEGS,
  433.             and all SEGS.  The interior-only SEGS mean is computed
  434.             by noting that a border SEG will put the SEGS all on
  435.             one side or the other so that the right or left number
  436.             of SEGS will equal the number of SEGS in the node.
  437.             The interior-only mean is chosen if is >= zero, and
  438.             then the all mean.  This routine sets the partition
  439.             line fields of the input node with the indices of the
  440.             appropriate VERTEXES.
  441. ******************************************************************************/
  442. void nodes_partition_line(node)
  443. register NODE_TREE *node;
  444. {
  445.   long agm=-1, igm=-1;                /* max geometric mean counts */
  446.   long gm;                    /* geometric mean count */
  447.   int apndx, ipndx;                /* partition line indices */
  448.   int rcnt, lcnt, splits;
  449.   register int sideflag;
  450.   register SEGS_INFO *sinfo, *iseg;
  451.   register int s, i;
  452.  
  453.   sinfo = node->segs;
  454.   for (s = 0; s < node->nsegs; s++) {        /* scan SEGS in node */
  455.     printf(s&1?"/\010":"\\\010");
  456.     node->pseg = sinfo;                /* try as partition line */
  457.     rcnt = lcnt = splits = 0;
  458.     iseg = node->segs;
  459.     for (i = 0; i < node->nsegs; i++) {
  460.       sideflag = nodes_select_side(&node->pseg->seg,&iseg->seg);
  461.       if (sideflag == 0)       rcnt++;        /* count SEGS on both sides */
  462.       else if (sideflag == 1)  lcnt++;        /* of the partition line    */
  463.       else if (sideflag == -1) splits++;
  464.       iseg = iseg->next;
  465.     }
  466.     gm = 200*rcnt*lcnt/(16*splits/3+1);        /* 200, 16/3 are empirical */
  467.     if (agm < gm) agm = gm, apndx = s;
  468.     if (rcnt != node->nsegs && lcnt != node->nsegs)
  469.       if (igm < gm) igm = gm, ipndx = s;
  470.     sinfo = sinfo->next;
  471.   }
  472.   if (igm >= 0) s = ipndx;
  473.   else          s = apndx;
  474.     /* assign partition line; note that this SEG may be split   */
  475.     /* later and so won't represent the SEG as it currently is, */
  476.     /* but I don't think it really matters since it will still  */
  477.     /* represent the partition line                             */
  478.   node->pseg = node->segs;
  479.   for (i = 0; i < s; i++) node->pseg = node->pseg->next;
  480. }
  481.  
  482.  
  483. /******************************************************************************
  484.     ROUTINE:    nodes_subsector_test(node)
  485.     WRITTEN BY:    Robert Fenske, Jr.
  486.     CREATED:    Mar. 1994
  487.     DESCRIPTION:    This routine checks whether the input node can be
  488.             an SSECTOR or not.  To be a subsector, the SEGS in
  489.             the node must describe a convex polygon (no interior
  490.             angles > 180 degrees).
  491. ******************************************************************************/
  492. int nodes_subsector_test(node)
  493. register NODE_TREE *node;
  494. {
  495.   int subsector = TRUE;
  496.   register SEGS_INFO *sinfo, *iseg;
  497.   register int s, i;
  498.  
  499.   sinfo = node->segs;
  500.   for (s = 0; subsector && s < node->nsegs; s++) {/* scan all SEGS */
  501.     for (iseg = node->segs, i = 0; i < node->nsegs; i++) {
  502.       if (i != s) {
  503.         if (nodes_select_side(&sinfo->seg,&iseg->seg) != 0) {
  504.           subsector = FALSE;            /* interior angle > 180 degs */
  505.           break;                /* so not an SSECTOR         */
  506.         }
  507.       }
  508.       iseg = iseg->next;
  509.     }
  510.     sinfo = sinfo->next;
  511.   }
  512.   return subsector;
  513. }
  514.  
  515.  
  516. /******************************************************************************
  517.     ROUTINE:    nodes_partition_node(node)
  518.     WRITTEN BY:    Robert Fenske, Jr.
  519.     CREATED:    Mar. 1994
  520.     DESCRIPTION:    This routine performs the binary space partitioning.
  521.             It recursively divides (partitions) the input node
  522.             until each leaf of the subtree defined by the input
  523.             node is an SSECTOR.  A partition line is obtained and
  524.             the left and right subtrees are allocated.  The left
  525.             subtree is always checked first.  If it is not an
  526.             SSECTOR, a recursive call is made to further divide
  527.             the left subtree.  The same procedure is then performed
  528.             on the right subtree.  The number of left and right
  529.             children plus one for the current node is returned.
  530. ******************************************************************************/
  531. int nodes_partition_node(node)
  532. register NODE_TREE *node;
  533. {
  534.   int nl, nr;                    /* # left, right nodes */
  535.   register NODE_TREE *left, *right;        /* left, right children */
  536.  
  537.   nodes_partition_line(node);            /* obtain partition line */
  538.   node->right = tree_branch(right);
  539.   node->left = tree_branch(left);
  540.   nodes_divide_node(node,right,left);
  541.   if (right->nsegs == 0 ||
  542.       nodes_subsector_test(left)) {        /* found an SSECTOR */
  543.     if (right->nsegs == 0)
  544.       printf("\n<<error, going on with Partition Line %d==>%d>>\n",
  545.              node->pseg->seg.fndx,node->pseg->seg.tndx);
  546.     printf("*\010\010");
  547.     nl = 1;
  548.   }else {                    /* need further subdivision */
  549.     printf("L");
  550.     nl = nodes_partition_node(left);
  551.   }
  552.   if (left->nsegs == 0 ||
  553.       nodes_subsector_test(right)) {        /* found an SSECTOR */
  554.     if (left->nsegs == 0)
  555.       printf("\n<<error, going on with Partition Line %d==>%d>>\n",
  556.               node->pseg->seg.fndx,node->pseg->seg.tndx);
  557.     printf("*\010\010");
  558.     nr = 1;
  559.   }else {                    /* need further subdivision */
  560.     printf("R");
  561.     nr = nodes_partition_node(right);
  562.   }
  563.   return nl + nr + 1;                /* # left + # right + this 1 */
  564. }
  565.  
  566.  
  567. /******************************************************************************
  568.     ROUTINE:    nodes_place_node(nodes,nndx,sndx,nodetree)
  569.     WRITTEN BY:    Robert Fenske, Jr.
  570.     CREATED:    Mar. 1994
  571.     DESCRIPTION:    This routine builds the NODES structure from the
  572.             input node tree.  It traverses the node tree in a
  573.             post-order fashion, left side first.  As the tree is
  574.             scanned, the NODES, SSECTORS, and SEGS lists are filled
  575.             in as appropriate.  The SSECTORS and SEGS lists are
  576.             referenced through the ninfo block.  The node tree
  577.             entries are deleted after they are used.  The node
  578.             number (or index) is returned, unless an SSECTOR is
  579.             found, then a -(SSECTOR number) is returned.
  580. ******************************************************************************/
  581. int nodes_place_node(nodes,nndx,sndx,nodetree)
  582. register DOOM_NODE *nodes;
  583. int *nndx, *sndx;
  584. register NODE_TREE *nodetree;
  585. {
  586.   int nnum;                    /* node number to return */
  587.   int lnum, rnum;
  588.   SEGS_INFO *sinfo, *next;
  589.   register DOOM_NODE *node;
  590.   register int s;
  591.  
  592.   if (nodetree->left != NULL) {            /* traverse node subtree */
  593.     lnum = nodes_place_node(nodes,nndx,sndx,nodetree->left);
  594.     rnum = nodes_place_node(nodes,nndx,sndx,nodetree->right);
  595.     node = &nodes[nnum = (*nndx)++];
  596.     node->x = ninfo.sverts[nodetree->pseg->seg.fndx].x;/* these 4 describe   */
  597.     node->y = ninfo.sverts[nodetree->pseg->seg.fndx].y;/* the partition line */
  598.     node->xdel = ninfo.sverts[nodetree->pseg->seg.tndx].x - node->x;
  599.     node->ydel = ninfo.sverts[nodetree->pseg->seg.tndx].y - node->y;
  600.     node->lymax = nodetree->left->ymax;
  601.     node->lymin = nodetree->left->ymin;
  602.     node->lxmin = nodetree->left->xmin;
  603.     node->lxmax = nodetree->left->xmax;
  604.     if (lnum < 0) node->nndx[1] = 0x8000 | (-lnum-1);/* mark as SSECTOR */
  605.     else          node->nndx[1] = lnum;        /* mark as NODE */
  606.     blockfree(nodetree->left);            /* done with left subtree */
  607.     node->rymax = nodetree->right->ymax;
  608.     node->rymin = nodetree->right->ymin;
  609.     node->rxmin = nodetree->right->xmin;
  610.     node->rxmax = nodetree->right->xmax;
  611.     if (rnum < 0) node->nndx[0] = 0x8000 | (-rnum-1);/* mark as SSECTOR */
  612.     else          node->nndx[0] = rnum;        /* mark as NODE */
  613.     blockfree(nodetree->right);            /* done with right subtree */
  614.   }else {                    /* SSECTOR (tree leaf) */
  615.     ninfo.ssecs[*sndx].count = nodetree->nsegs;
  616.     if (*sndx == 0) ninfo.ssecs[*sndx].sndx = 0;
  617.     else            ninfo.ssecs[*sndx].sndx = ninfo.ssecs[*sndx-1].sndx+
  618.                                               ninfo.ssecs[*sndx-1].count;
  619.     sinfo = nodetree->segs;
  620.     for (s = 0; s < nodetree->nsegs; s++) {    /* copy node's SEGS to full */
  621.       ninfo.segs[ninfo.nsegs++] = sinfo->seg;    /* SEGS array               */
  622.       next = sinfo->next;
  623.       blockfree(sinfo);
  624.       sinfo = next;
  625.     }
  626.     nnum = -++(*sndx);                /* mark as leaf */
  627.   }
  628.   return nnum;                    /* ret node # or <0 if leaf */
  629. }
  630.  
  631.  
  632. /******************************************************************************
  633.     ROUTINE:    nodes_make(nodes,nnodes,ssecs,nssecs,segs,nsegs,
  634.                        verts,nverts,lines,nlines)
  635.     WRITTEN BY:    Robert Fenske, Jr.
  636.     CREATED:    Mar. 1994
  637.     DESCRIPTION:    This routine generates the NODES, SSECTORS, and SEGS
  638.             sections.  It first finds the minimum and maximum x,y
  639.             coordinates of the map to use in the root of the node
  640.             tree.  Then the node tree root is created.  The
  641.             necessary counters in the ninfo block are zeroed and
  642.             the SEGS vertices list is allocated.  Then
  643.             nodes_partition_node() is called to build the node
  644.             tree.  Next, the NODES, SSECTORS, and SEGS lists are
  645.             allocated based on the values calculated during the
  646.             construction of the node tree.  The necessary counters
  647.             are zeroed and nodes_place_node() is called to fill
  648.             the NODES, SSECTORS, and SEGS lists with the correct
  649.             information.  All the appropriate values are placed
  650.             into the return variables and the number of computed
  651.             node entries is returned.
  652. ******************************************************************************/
  653. int nodes_make(nodes,nnodes,ssecs,nssecs,segs,nsegs,verts,nverts,lines,nlines)
  654. DOOM_NODE **nodes;
  655. int *nnodes;
  656. DOOM_SSECTOR **ssecs;
  657. int *nssecs;
  658. DOOM_SEGS **segs;
  659. int *nsegs;
  660. DOOM_VERT **verts;
  661. int *nverts;
  662. DOOM_LINE **lines;
  663. int *nlines;
  664. {
  665.   NODE_TREE *nodetree;                /* BSP node tree */
  666.   register int i;
  667.  
  668.   ninfo.nsverts = -1;
  669.   for (i = 0; i < *nlines; i++) {        /* find maximum used vertex */
  670.     if (ninfo.nsverts < (*lines)[i].fndx) ninfo.nsverts = (*lines)[i].fndx;
  671.     if (ninfo.nsverts < (*lines)[i].tndx) ninfo.nsverts = (*lines)[i].tndx;
  672.   }
  673.   ninfo.nsverts++;
  674.   ninfo.sverts = blockmem(DOOM_VERT,2*ninfo.nsverts);/* assume no more than  */
  675.   for (i = 0; i < ninfo.nsverts; i++)        /* nsverts new verts created */
  676.     ninfo.sverts[i] = (*verts)[i];
  677.   ninfo.nsegs = nodes_segs_init(*lines,*nlines);/* initialize SEGS list */
  678.   nodetree = tree_branch(nodetree);        /* node tree root */
  679.   nodetree->nsegs = ninfo.nsegs;
  680.   nodetree->segs = ninfo.sinfo;
  681.   nodes_segs_bounds(nodetree);
  682.   printf("%d sides ==>  ",ninfo.nsegs);
  683.   ninfo.nnodes = nodes_partition_node(nodetree)/2;/* BSP it */
  684.   ninfo.nodes = blockmem(DOOM_NODE,ninfo.nnodes);
  685.   ninfo.nssecs = ninfo.nnodes+1;        /* always 1 more SSECTOR */
  686.   ninfo.ssecs = blockmem(DOOM_SSECTOR,ninfo.nssecs);
  687.   ninfo.segs = blockmem(DOOM_SEGS,ninfo.nsegs);
  688.   ninfo.nsegs = ninfo.nssecs = ninfo.nnodes = 0;
  689.   (void)nodes_place_node(ninfo.nodes,&ninfo.nnodes,&ninfo.nssecs,nodetree);
  690.   if (nodes != NULL)  *nodes = ninfo.nodes;
  691.   if (nnodes != NULL) *nnodes = ninfo.nnodes;
  692.   if (ssecs != NULL)  *ssecs = ninfo.ssecs;
  693.   if (nssecs != NULL) *nssecs = ninfo.nssecs;
  694.   if (segs != NULL)   *segs = ninfo.segs;
  695.   if (nsegs != NULL)  *nsegs = ninfo.nsegs;
  696.   if (verts != NULL)  *verts = ninfo.sverts;
  697.   if (nverts != NULL) *nverts = ninfo.nsverts;
  698.   blockfree(nodetree);                /* done with the node tree */
  699.   return *nnodes;                /* return number of nodes */
  700. }
  701.