/****************************************************************************** MODULE: BLOCKMAP.C WRITTEN BY: Robert Fenske, Jr. (rfenske@swri.edu) Southwest Research Institute Electromagnetics Division 6220 Culebra San Antonio, Texas 78238-5166 CREATED: Feb. 1994 DESCRIPTION: This module contains routines to generate the BLOCKMAP section. See the generation routine for an explanation of the method used to generate the BLOCKMAP. The optimizations for the horizontal LINEDEF, vertical LINEDEF, and single block cases came from ideas presented in the Unofficial DOOM Specs written by Matt Fell. DOOM is a trademark of id Software, Inc. ******************************************************************************/ #include #include #include #include "dmglobal.i" local short *Blockmap; /* built BLOCKMAP */ /****************************************************************************** ROUTINE: blockmap_add_line(block,lndx,nlines) WRITTEN BY: Robert Fenske, Jr. CREATED: Feb. 1994 DESCRIPTION: This routine adds the LINEDEF lndx to the block's block LINEDEF list. If no list exists yet for the block, one is created. Memory is allocated for no more than fifty LINEDEFS (to save memory); thus this routine assumes that no more than fifty LINEDEFS will be in any one block. ******************************************************************************/ void blockmap_add_line(block,lndx,nlines) register short **block; int lndx, nlines; { register int k; if (*block == NULL) /* allocate if no list yet */ *block = blockmem(short,min(nlines,50)); for (k = 0; (*block)[k]; k++); /* seek to end of list */ (*block)[k] = lndx+1; /* add this LINEDEF */ } /****************************************************************************** ROUTINE: blockmap_make(blockmap,lines,nlines,vert) WRITTEN BY: Robert Fenske, Jr. CREATED: Feb. 1994 DESCRIPTION: This routine builds the BLOCKMAP section given the LINEDEFS and VERTEXES. The BLOCKMAP section has the following information (all are 16-bit words): block grid X origin block grid Y origin # blocks along X axis (total # blocks --> ) # blocks along Y axis (N = Xn * Yn ) block 0 offset (# words) block 1 offset (# words) . . block N-1 offset (# words) block 0 data (M words: 0,LINEDEFs in block 0,FFFF) block 1 data (M words: 0,LINEDEFs in block 1,FFFF) . . block N-1 data (M words: 0,LINEDEFs in block N-1,FFFF) Block 0 is at the lower left, block 1 is to the right of block 0 along the x-axis, ..., block N-1 is at the upper right. An N-element pointer array is allocated to hold pointers to the list of LINEDEFS in each block. If no LINEDEFS occur within a block, it's pointer will be NULL. Then the LINEDEFS are scanned to find the blocks each line occupies, building the lists of LINEDEFS along the way. Four cases are considered for each LINEDEF. The line is either diagonal, horizontal, vertical, or resides in a single block (regardless of orientation). The non-diagonal cases can be optimized since the blocks occupied can be directly calculated. The diagonal case basically computes the blocks occupied on each row for all the rows between the LINEDEF endpoints. Once this is complete the actual blockmap is allocated and filled. It returns the number of words in the blockmap. MODIFIED: Robert Fenske, Jr. Mar. 1994 Added in the optimizations for the orthogonal line cases using the ideas presented in the Unofficial DOOM Specs written by Matt Fell. ******************************************************************************/ int blockmap_make(blockmap,lines,nlines,vert) register short **blockmap; /* built BLOCKMAP */ register DOOM_LINE *lines; /* map LINEDEFS */ int nlines; /* map # lines */ DOOM_VERT *vert; /* map VERTEXES */ { short xmin,ymin, xmax,ymax; /* map coords min/max */ long scl = 1000; /* line following scaling */ short size = 0x80; /* block size (map coords) */ short xorig, yorig; /* blockmap x,y origin */ short xn, yn; /* # blocks in x,y dirs */ short xcc, xcl; long xf,yf, xt,yt; long xd, yd; /* x direction, y direction */ int o; int l, k, i, p, c, m; register short **boxlist; /* array of blocks' lists */ register int b; register int t; xmin = ymin = (short)0x7FFF, xmax = ymax = (short)0x8000; for (l = 0; l < nlines; l++) { /* find min/max map coords */ xf = vert[lines[l].fndx].x, yf = vert[lines[l].fndx].y; if (xf < xmin) xmin = (short)xf; /* check from vertex */ if (yf < ymin) ymin = (short)yf; if (xmax < xf) xmax = (short)xf; if (ymax < yf) ymax = (short)yf; xt = vert[lines[l].tndx].x, yt = vert[lines[l].tndx].y; if (xt < xmin) xmin = (short)xt; /* check to vertex */ if (yt < ymin) ymin = (short)yt; if (xmax < xt) xmax = (short)xt; if (ymax < yt) ymax = (short)yt; } xorig = xmin-8; /* get x origin */ yorig = ymin-8; /* get y origin */ xn = (xmax-xmin+size)/size; /* get # in x direction */ yn = (ymax-ymin+size)/size; /* get # in y direction */ boxlist = blockmem(short *,xn*yn); t = 0; /* total len of all lists */ for (l = 0; l < nlines; l++) { /* scan LINEDEFS here */ xf = vert[lines[l].fndx].x-xorig; yf = vert[lines[l].fndx].y-yorig; xt = vert[lines[l].tndx].x-xorig; yt = vert[lines[l].tndx].y-yorig; xd = sgn(xt-xf), yd = sgn(yt-yf); switch (2*(xf/size == xt/size) + (yf/size == yt/size)) { bcase 0: c=0, p=yd*xn;/* diagonal line */ bcase 1: c=abs(xt/size-xf/size)+1, p=xd; /* horizontal line */ bcase 2: c=abs(yt/size-yf/size)+1, p=yd*xn;/* vertical line */ bcase 3: c=0+1, p=1; /* start,end in same block */ } b = xf/size + xn*(yf/size); /* start @ this block */ for (i = 0; i < c; i++, b+=p) { /* add to lists for special */ blockmap_add_line(&boxlist[b],l,nlines); /* cases: horizontal, */ t++; /* vertical, & single block */ } if (c == 0) { /* handle diagonal lines */ m = scl*(yt-yf)/(xt-xf); /* spanning > 1 block */ xcl = (short)xf; if (yd == -1) xcc = xf + scl*((yf/size)*size - 1 - yf)/m; else xcc = xf + scl*((yf/size)*size + 128 - yf)/m; do { for (c = 0; c < abs(xcc/size - xcl/size) + 1; c++, b+=xd) { blockmap_add_line(&boxlist[b],l,nlines); t++; } b += p-xd; xcl = xcc, xcc += yd*scl*size/m; if (xd*xcc > xd*xt) xcc = (short)xt; /* don't overrun endpoint */ } while (xd*xcl < xd*xt); } } blockfree(Blockmap); Blockmap = blockmem(short,4+xn*yn+t+2*xn*yn); t = 0; Blockmap[t++] = xorig; /* fill in X,Y origin */ Blockmap[t++] = yorig; Blockmap[t++] = xn; /* fill in # in X and */ Blockmap[t++] = yn; /* Y directions */ o = t; t += xn*yn; for (i = 0; i < xn*yn; i++) { /* now fill in BLOCKMAP */ Blockmap[o++] = t; /* offset in BLOCKMAP */ Blockmap[t++] = 0; /* always zero */ if (boxlist[i] != NULL) { for (k = 0; boxlist[i][k]; k++) /* list of lines in this */ Blockmap[t++] = boxlist[i][k]-1; /* block */ blockfree(boxlist[i]); } Blockmap[t++] = -1; /* always -1 */ } blockfree(boxlist); *blockmap = Blockmap; return t; /* # words in BLOCKMAP */ }