home *** CD-ROM | disk | FTP | other *** search
/ D!Zone (Collector's Edition) / D_ZONE_CD.ISO / programs / editors / vnb1050 / nodes.c < prev    next >
C/C++ Source or Header  |  1994-05-25  |  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 + sqr