/*----------------------------------------------------------------------------* | This file is part of DEU (Doom Editing Utilities), created by the DEU team:| | Raphael Quinet, Brendon Wyber, Ted Vessenes and others. See README.1ST or | | the "about" dialog box for full credits. | | | | DEU is an open project: if you think that you can contribute, please join | | the DEU team. You will be credited for any code (or ideas) included in | | the next version of the program. | | | | If you want to make any modifications and re-distribute them on your own, | | you must follow the conditions of the DEU license. Read the file LICENSE | | in this directory or README.1ST in the top directory. If do not have a | | copy of these files, you can request them from any member of the DEU team, | | or by mail: Raphael Quinet, Rue des Martyrs 9, B-4550 Nandrin (Belgium). | | | | This program comes with absolutely no warranty. Use it at your own risks! | *----------------------------------------------------------------------------* B_BSP.C - BSP tree builder Created on Jun 9 1994 by Johannes Plass Converted to DEU 5.3 style on Jan 24 1995 by Renaud Paquay */ #include "deu.h" #include "d_misc.h" /* GetFarMemory() */ #include "d_config.h" /* Config (BSP_... fields) */ #include "w_struct.h" /* Thing, LineDef, Seg, ...*/ #include "w_levels.h" /* LevelInfo */ #include "w_object.h" /* InsertObject */ #include "b_bsp.h" /* CreateNodes() proto */ /*!RP moved here, because to pre-compile header, DEU.H must first file included */ #include /*! Should not be included... */ #include "g_gfx.h" /* ScrMaxX, ScrMaxY, + funct. to draw in ShowBSPProgress */ #include "g_mouse.h" /* UseMouse, HideMousePointer(), ShowMousePointer */ /* Local functions prototypes */ static void ComputeIntersection(LevelPtr level, SEPtr n, SEPtr l); static void LineOnSide (LevelPtr level, SEPtr n, SEPtr l); static Int32 EvaluateSplit (LevelPtr level, SEPtr n, SEPtr l, Int32 bestgrade, Int16 numsegs, Int16 slope); static SEPtr FindNodeLine(LevelPtr level, SEPtr seglist); static void ComputeBoundingBox(LevelPtr level, SEPtr seglist, Int16 *minx, Int16 *maxx, Int16 *miny, Int16 *maxy); static Int16 CreateSSector(LevelPtr level, SEPtr seglist); static UInt16 SegmentDistance(Int16 deltax, Int16 deltay); static UInt16 SegmentBA(Int16 deltax, Int16 deltay); static Bool MakeNodes(LevelPtr level, NPtr *node_r, Int16 *ssector_r, SEPtr seglist); static void BuildInitialSegList (LevelPtr level, SEPtr *pseglist, UInt16 *pnumsegs); /*RP: The SEGMENTS and SSECTORS array are passed as parameters to the CreatesNodes functions. These static vars. are only a copy of them. They can be static too */ static UInt16 loc_num_segs; /* number of SEGS */ static SEPtr loc_segs; /* SEGS data */ static SEPtr loc_last_seg; /* Last SEG pointer */ static UInt16 loc_num_ssectors; /* number of SSectors */ static SSPtr loc_ssectors; /* SSectors data */ static SSPtr loc_last_ssector; /* Last SSectors pointer */ /*! These macros should be removed from here and expanded in the code. They "hide" inefficient operations (several indirections for each access to a vertex). The code could certainly be optimized if these macros did not exist. RP: Done! (Apr 14 1995) */ /* #define VLSX(sss) loc_level.vertexes[loc_level.linedefs[sss->linedef].start].x #define VLSY(sss) loc_level.vertexes[loc_level.linedefs[sss->linedef].start].y #define VLEX(sss) loc_level.vertexes[loc_level.linedefs[sss->linedef].end].x #define VLEY(sss) loc_level.vertexes[loc_level.linedefs[sss->linedef].end].y #define VEX(abc) (loc_level.vertexes[abc->end].x) #define VEY(abc) (loc_level.vertexes[abc->end].y) #define VSX(abc) (loc_level.vertexes[abc->start].x) #define VSY(abc) (loc_level.vertexes[abc->start].y) */ /*!RP Moved these 3 vars in the 'config' struct, so these vars are now static (initialized by CreateNodes from Config struct) */ static Int16 BSP_splitfactor; static Int16 BSP_slopefactor; static Int16 BSP_speedfactor; /* Statistics about last build */ UInt32 BSP_2S_splits; UInt32 BSP_vertex_corrections; UInt32 BSP_splits; /* private */ static Int16 sideS, sideE, sideL; static Int16 interX, interY; static Int32 tmp_vertex_corrections; /* Indicate the progress. */ /*! This routine should be cleaned up (too many static vars) and moved to g_gfx.c, i_menus.c or i_dialog.c so that other parts of the code can use it. If it is moved in g_gfx.c, then the low-level graphics stuff can be used. Any volunteers? */ /*! More comments are needed - what is "kind" ? RP: Comment on this function: Draws a little box in the lower right corner of the screen, with a line rotating in it. This box has 4 components: - An outer 3D box - An inner 3D box, in which the rotating line is drawn - The rotating line (4 positions: | / \ -) - Between the two 3D boxes, there's another colored square. Meaning of 'color' and 'kind' parameters: kind == -1 ==> deletes the box with 'color' (usualy BLACK) kind == 0 ==> draws the outer and inner 3D boxes ('color' ignored) kind == 1 ==> draws the rotating line with 'color' kind == 2 ==> draws a colored square between the inner and outer boxes with 'color' */ /*! Maybe this function should be renamed? */ void RotateMessage(int color, int kind) { static int i = 0; /* Counter to decide when to draw the rotating line (every 30th call) */ static int j = 0; /* Counter which keeps the rotating line position: j == 0 ==> | j == 1 ==> / j == 2 ==> - j == 3 ==> \ */ static Int16 x0; /* X coord of the middle of the box */ static Int16 y0; /* Y coord of the middle of the box */ static Int16 wo = 14; /* 1/2 width of outer rect */ static Int16 wi = 8; /* 1/2 width of inner rect */ static Int16 le = 6; /* 1/2 length of rotating line */ static Int16 xs, ys, xe, ye; /* Last rotating line coords. */ static Int16 offset; /* Radius of colored rect */ /* Draw the rotating line */ if (kind == 1) { /* Draw only every 30th calls */ i ++; if (i != 30) return; /* Delete old rotating line */ SetLinePatternAndWidth(SOLID_PATTERN, 3); SetColor(LIGHTGRAY); DrawScreenLine(xs, ys, xe, ye); /* Calc. new line coords. */ switch (j) { case 0: xs = x0; ys = y0 - le; xe = x0; ye = y0 + le; break; case 1: xs = x0 + le - 1; ys = y0 - le + 1; xe = x0 - le + 1; ye = y0 + le - 1; break; case 2: xs = x0 - le; ys = y0; xe = x0 + le; ye = y0; break; case 3: xs = x0 - le + 1; ys = y0 - le + 1; xe = x0 + le - 1; ye = y0 + le - 1; break; } /* Draw new rotating line */ SetColor(color); DrawScreenLine(xs, ys, xe, ye); SetLinePatternAndWidth(SOLID_PATTERN, 1); i = 0; j ++; if (j == 4) j = 0; return; } /* Draw colored square */ else if (kind == 2) { SetLinePatternAndWidth(SOLID_PATTERN, 3); SetColor(color); offset = wi + 3; DrawScreenLine(x0 - offset, y0 - offset, x0 + offset, y0 - offset); DrawScreenLine(x0 - offset, y0 + offset, x0 + offset, y0 + offset); DrawScreenLine(x0 - offset, y0 - offset, x0 - offset, y0 + offset); DrawScreenLine(x0 + offset, y0 - offset, x0 + offset, y0 + offset); SetLinePatternAndWidth(SOLID_PATTERN, 1); return; } /* Draw both 3D boxes, and initialize rotating line vars */ else if (kind == 0) { x0 = ScrMaxX - wo - 1; y0 = ScrMaxY - wo - 1; DrawScreenBox3D(x0 - wo, y0 - wo, x0 + wo, y0 + wo); DrawScreenBox3D(x0 - wi, y0 - wi, x0 + wi, y0+ wi); xs = x0; ys = y0 - le; xe = x0; ye = y0 + le; i = 15; return; } /* Delete the full box */ else if (kind == -1) { SetColor(color); DrawScreenBox(x0 - wo, y0 - wo, x0 + wo, y0 + wo); return; } return; } /* Display some informations while the user is waiting */ void ShowBSPProgress(LevelPtr level, Int16 objtype) { static float oldratio = 0.0; float ratio; if (UseMouse) HideMousePointer(); switch (objtype) { case OBJ_VERTEXES: DrawScreenBox3D(0, 0, 203, 22); DrawScreenText(10, 8, "Number of Vertices: %d", level->num_vertexes); break; case OBJ_SIDEDEFS: DrawScreenBox3D(0, 30, 203, 52); DrawScreenText(10, 38, "Number of SideDefs: %d", level->num_sidedefs); oldratio = 0.0; break; case OBJ_SSECTORS: DrawScreenBox3D(0, 60, 203, 92); DrawScreenText(10, 68,"Number of Segs: %d", loc_num_segs); DrawScreenText(10, 78,"Number of SSectors: %d", loc_num_ssectors); ratio = (float)(loc_num_segs - BSP_splits) / ((float)level->num_sidedefs); if (ratio > oldratio) { DrawScreenMeter(225, 28, ScrMaxX - 10, 48, ratio); oldratio = ratio; } break; } if (UseMouse) ShowMousePointer(); } #define MINIMUM_DISTANCE 2 /* Find the point of intersection for two lines n,l. The intersection coordinates are stored in globals interX,interY. The globals sideS, sideE are modified if the intersection is too close to the start- or end-point of line l. */ void ComputeIntersection(LevelPtr level, SEPtr n, SEPtr l) { VPtr vnstart = &level->vertexes[n->start]; VPtr vnend = &level->vertexes[n->end]; VPtr vlstart = &level->vertexes[l->start]; VPtr vlend = &level->vertexes[l->end]; double xns = vnstart->x; double yns = vnstart->y; double xls = vlstart->x; double yls = vlstart->y; double ndx = vnend->x - vnstart->x; double ndy = vnend->y - vnstart->y; double ldx = vlend->x - vlstart->x; double ldy = vlend->y - vlstart->y; /*RP Removed 'static' here */ double d, u, v, w; /* double t; */ /*RP Removed 'static' here */ Int32 dist; d = ldy * ndx - ndy * ldx; u = yns * ndx - xns * ndy; v = yls * ldx - xls * ldy; w = (ldx * u - ndx * v) / d; /*! modf should be avoided in portable code */ /* RP removed ! modf(w + ((w < 0) ? -0.5 : 0.5), &t); interX = t; */ interX = (Int16) (w + ((w < 0) ? -0.5 : 0.5)); w = (ldy * u - ndy * v) / d; /*! modf should be avoided in portable code */ /* RP removed ! modf(w + ((w < 0) ? -0.5 : 0.5), &t); interY = t; */ interY = (Int16) (w + ((w < 0) ? -0.5 : 0.5)); /*RP BUG!!!!!! This line caused me 2 days of work to find it out :-( * Simply because of missing cast, the BSP builder was * making a LOT of bad split corrections .... * This used to cause plenty of HOM effects on levels built :-( * * dist = (interX - vlstart->x) * (interX - vlstart->x) + * (interY - vlstart->y) * (interY - vlstart->y); */ dist = (Int32)(interX - vlstart->x) * (Int32)(interX - vlstart->x) + (Int32)(interY - vlstart->y) * (Int32)(interY - vlstart->y); if (dist < MINIMUM_DISTANCE) { sideS = 0; ++tmp_vertex_corrections; return; } /*RP BUG!!!!!! This line caused me 2 days of work to find it out !!! * Simply because of missing cast, the BSP builder was * making a LOT of bad split corrections .... * This used to cause plenty of HOM effects on levels built :-( * * dist = (interX - vlend->x) * (interX - vlend->x) + * (interY - vlend->y) * (interY - vlend->y); */ dist = (Int32)(interX - vlend->x) * (Int32)(interX - vlend->x) + (Int32)(interY - vlend->y) * (Int32)(interY - vlend->y); if (dist < MINIMUM_DISTANCE) { sideE = 0; ++tmp_vertex_corrections; return; } return; } /*! descritpion missing */ /* Returns for sideL: 0 (line must be split), 1 (front), or 2 (back) If the line is colinear, it will be placed on the front side if it is going the same direction as the dividing line. Returns for sideS: 0 (colinear), 1 (front), or 2 (back) Returns for sideE: "" */ void LineOnSide (LevelPtr level, SEPtr n, SEPtr l) { VPtr vnstart = &level->vertexes[n->start]; VPtr vnend = &level->vertexes[n->end]; VPtr vlstart = &level->vertexes[l->start]; VPtr vlend = &level->vertexes[l->end]; /*RP Removed 'static' here */ Int32 dx1, dx2, dy1, dy2; dx1 = vnstart->x - vlstart->x; dy1 = vnstart->y - vlstart->y; dx2 = vnend->x - vlstart->x; dy2 = vnend->y - vlstart->y; if (dx1 * dy2 > dy1 * dx2) sideS = 2; else if (dx1 * dy2 < dy1 * dx2) sideS = 1; else sideS = 0; dx1 = vnstart->x - vlend->x; dy1 = vnstart->y - vlend->y; dx2 = vnend->x - vlend->x; dy2 = vnend->y - vlend->y; if (dx1 * dy2 > dy1 * dx2) sideE = 2; else if (dx1 * dy2 < dy1 * dx2) sideE = 1; else sideE = 0; if (sideE + sideS == 3) ComputeIntersection(level, n, l); if (sideS == sideE) { if (sideS == 0) { if ( ((vlstart->x <= vlend->x) ^ (vnstart->x <= vnend->x)) + ((vlstart->y <= vlend->y) ^ (vnstart->y <= vnend->y)) == 0) { sideL = 1; return; } else { sideL = 2; return; } } sideL = sideS; return; } if (sideS == 0) sideL = sideE; else if (sideE == 0) sideL = sideS; else sideL = 0; } /* Returns a number grading the quality of a split along the given line for the current list of lines. If the split line does not divide any of the lines at all, WORSTGRADE will be returned */ #define WORSTGRADE ((Int32)10000000L) #define GRADE(fff,bbb,sss) (((Int32)(fff > bbb ? fff : bbb)) + \ ((Int32)(BSP_splitfactor)) * ((Int32)sss) + \ ((Int32)slope)) /*!RP Param 'numsegs' never used !? */ Int32 EvaluateSplit (LevelPtr level, SEPtr n, SEPtr l, Int32 bestgrade, Int16 numsegs, Int16 slope) { register Bool twosided = FALSE; register int opt = 0; /*RP counter -> int is good */ Int16 side[3]; register SEPtr curseg; side[0] = side[1] = side[2] = 0; for (curseg = l; curseg; curseg = curseg->next) { if (level->linedefs[curseg->linedef].sidedef2 >= 0) { if (curseg->next) { if ((curseg->next)->linedef == curseg->linedef) twosided = TRUE; } } LineOnSide(level, n, curseg); side[sideL]++; if (! sideL) { side[1]++; side[2]++; } if (twosided) { if (sideL == 0) { side[0]++; side[1]++; side[2]++; } else if (sideL == 1) { if (sideS == 0 && sideE == 0) side[2]++; else side[1]++; } else if (sideL == 2) { if (sideS == 0 && sideE == 0) side[1]++; else side[2]++; } curseg = curseg->next; twosided = FALSE; } opt++; /* occasionally test if better grade exists */ if (opt == 4) { if (GRADE(side[1], side[2], side[0]) > bestgrade) return (WORSTGRADE-1); opt=0; } } if ((side[1] == 0) || (side[2] == 0)) { (n->flip) = (n->flip) | 2; /*###FLIP###*/ return WORSTGRADE; } return GRADE(side[1], side[2], side[0]); } /* Choose a nodeline amongst a given list of Segs. */ SEPtr FindNodeLine(LevelPtr level, SEPtr seglist) { /*RP Removed 'static' here */ Int32 grade,bestgrade; /*RP Removed 'static' here */ SEPtr nodeline, bestnodeline; /*RP Removed 'static' here */ Int16 numsegs, slope; Int16 jump = 0, cont = 0; bestnodeline = NULL; bestgrade = WORSTGRADE; numsegs = 0; for (nodeline = seglist; nodeline; nodeline = nodeline->next) numsegs++; if (BSP_speedfactor != 100) { jump = (numsegs * (100 - BSP_speedfactor)) / 100; } RotateMessage(LIGHTGRAY, 2); for (nodeline = seglist; nodeline; nodeline = nodeline->next) { if (jump) { if (bestgrade != WORSTGRADE) { cont ++; if (cont < jump) continue; cont = 0; jump = 0; } } RotateMessage(RED, 1); if ((nodeline->flip & 2) == 0) /*###FLIP###*/ { VPtr vstart = &level->vertexes[nodeline->start]; VPtr vend = &level->vertexes[nodeline->end]; if ((vstart->x - vend->x) && (vstart->y - vend->y)) slope = BSP_slopefactor; else slope = 0; grade = EvaluateSplit(level, nodeline, seglist, bestgrade, numsegs, slope); if (grade < bestgrade) { bestgrade = grade; bestnodeline = nodeline; } } } if (bestgrade == WORSTGRADE) bestnodeline = NULL; return bestnodeline; } /* Compute the bounding box (limits on X, Y) for a list of Segs. */ void ComputeBoundingBox(LevelPtr level, SEPtr seglist, Int16 *minx, Int16 *maxx, Int16 *miny, Int16 *maxy) { SEPtr curseg; VPtr v; register Int16 x, y; *maxx = -32767; *maxy = -32767; *minx = 32767; *miny = 32767; for (curseg = seglist; curseg; curseg = curseg->next) { v = &level->vertexes[curseg->start]; x = v->x; y = v->y; if (x < *minx) *minx = x; if (x > *maxx) *maxx = x; if (y < *miny) *miny = y; if (y > *maxy) *maxy = y; v = &level->vertexes[curseg->end]; x = v->x; y = v->y; if (x < *minx) *minx = x; if (x > *maxx) *maxx = x; if (y < *miny) *miny = y; if (y > *maxy) *maxy = y; } } /* Create a SSector from a list of Segs. */ Int16 CreateSSector(LevelPtr level, SEPtr seglist) { /* Add a SSECTOR in the list */ loc_num_ssectors++; if (loc_ssectors) { loc_last_ssector->next = (struct SSector *)GetFarMemory(sizeof(struct SSector)); loc_last_ssector = loc_last_ssector->next; } else { loc_ssectors = (struct SSector *)GetFarMemory(sizeof(struct SSector)); loc_last_ssector = loc_ssectors; } loc_last_ssector->next = NULL; /* number of first Segment in this SubSector */ loc_last_ssector->first = loc_num_segs; /* update the Segs list */ if (loc_segs == NULL) loc_segs = seglist; else loc_last_seg->next = seglist; loc_num_segs++; for ( loc_last_seg = seglist; loc_last_seg->next; loc_last_seg = loc_last_seg->next) loc_num_segs++; /* total number of Segments in this SubSector */ loc_last_ssector->num = loc_num_segs - loc_last_ssector->first; /* while the user is waiting... */ ShowBSPProgress(level, OBJ_SSECTORS); /* return the number of this SubSector */ return loc_num_ssectors - 1; } /*! comment missing */ /*RP Comment on this function returns the distance from (0,0) to to (deltax,delaty) deltax |--------- / | t/ | | s/ | | i/ |deltay | d/ | |/ | +-------------- (0,0) */ UInt16 SegmentDistance(Int16 deltax, Int16 deltay) { /*RP Removed 'static' here */ double d, dx, dy; /* double dr; */ /*RP Removed 'static' here */ UInt16 di; dx = deltax; dy = deltay; d = hypot(dx, dy); /*! modf should be avoided in portable code */ /*RP Removed! modf(d + 0.5, &dr); di = (UInt16)dr; */ di = (UInt16)(d + 0.5); return di; } /*! comment missing */ /*RP Comment on this function returns the angle between the horizontal axe (0,0) to (x,0) and the line going from (0,0) to (deltax,delaty) This angle is an UInt16 (-PI -> PI ==> 0 -> 65535) deltax |--------- / | / | | / | | / |deltay | /\ | |/ | a | +-------------- (0,0) */ UInt16 SegmentBA(Int16 deltax, Int16 deltay) { /*RP Removed 'static' here */ double a, dx, dy; /* double ar; */ /*RP Removed 'static' here */ UInt16 ai; dx = deltax; dy = deltay; a = atan2(dy, dx) * (double)10430.37835047; if ( a < 0 ) a += (double)65536.0; /*! modf should be avoided in portable code */ /*RP Remved! modf(a + 0.5, &ar); ai = (UInt16) ar; */ ai = (UInt16)(a + 0.5); /*RP Bug!!!! There was 'return ar' here! */ return ai; } /* Add the 'current' seg to the end of the segs list */ #define UPDATE_LIST_OF_SEGS_ON_SIDE(start,last,current) \ if (!start) \ { \ start = current; last = current; \ } \ else \ { \ last->next = current; last=current; \ } /*RP Allocate a new seg 'nnn', fill in the fields (partialy from 'ccc'), and update 'ccc' so that its end goes to the start of 'nnn'. Example: x (last vertex added) x---------------x ccc->start ccc->end After: ccc->end == nnn->start x (last vertex added) / \____ / \____ / \ x x ccc->start nnn->end */ #define INTRODUCE_NEW_SEG(nnn,ccc) \ { \ VPtr vstart; \ VPtr vend; \ LDPtr pld; \ VPtr vldstart; \ VPtr vldend; \ VPtr vcstart; \ VPtr vcend; \ \ BSP_splits++; \ if ((level->linedefs[ccc->linedef].flags) & 4) \ BSP_2S_splits ++; \ \ nnn = (struct Seg *)GetFarMemory(sizeof(struct Seg)); \ memset(nnn, 0, sizeof(struct Seg)); \ \ nnn->start = level->num_vertexes - 1; \ nnn->end = ccc->end; \ nnn->linedef = ccc->linedef; \ \ vstart = &level->vertexes[nnn->start]; \ vend = &level->vertexes[nnn->end]; \ nnn->angle = SegmentBA(vend->x - vstart->x, vend->y - vstart->y); \ \ nnn->flip = (ccc->flip) & 1; \ \ pld = &level->linedefs[nnn->linedef]; \ vldstart = &level->vertexes[pld->start]; \ vldend = &level->vertexes[pld->end]; \ if (nnn->flip) \ nnn->dist = SegmentDistance(vstart->x - vldend->x, \ vstart->y - vldend->y); \ else \ nnn->dist = SegmentDistance(vstart->x - vldstart->x, \ vstart->y - vldstart->y); \ \ ccc->end = level->num_vertexes - 1; \ ccc->flip = (ccc->flip) & 1; \ \ vcstart = &level->vertexes[ccc->start]; \ vcend = &level->vertexes[ccc->end]; \ ccc->angle = SegmentBA(vcend->x - vcstart->x, vcend->y - vcstart->y); \ } #define UPDATE_IF_TWOSIDED_SPLIT(sss1,eee1,sss2,eee2) \ if (level->linedefs[curseg->linedef].sidedef2 >= 0) \ { \ if (seglist) \ { \ if (seglist->linedef == curseg->linedef) \ { \ curseg = seglist; \ seglist = seglist->next; \ UPDATE_LIST_OF_SEGS_ON_SIDE(sss1, eee1, curseg) \ INTRODUCE_NEW_SEG(newSEPtr, curseg) \ UPDATE_LIST_OF_SEGS_ON_SIDE(sss2, eee2, newSEPtr)\ } \ } \ } #define UPDATE_IF_TWOSIDED(sss,eee) \ if (level->linedefs[curseg->linedef].sidedef2 >= 0) \ { \ if (seglist) \ { \ if (seglist->linedef == curseg->linedef) \ { \ curseg = seglist; \ seglist = seglist->next; \ UPDATE_LIST_OF_SEGS_ON_SIDE(sss, eee, curseg) \ } \ } \ } /* Create all Nodes from a list of Segs. */ Bool MakeNodes(LevelPtr level, NPtr *node_r, Int16 *ssector_r, SEPtr seglist) { NPtr node; SEPtr frontstart = NULL; SEPtr frontend = NULL; SEPtr backstart = NULL; SEPtr backend = NULL; SEPtr nodeline, curseg; SEPtr newSEPtr; VPtr vstart; /*RP Temporary used later */ VPtr vend; /*RP Temporary used later */ nodeline = FindNodeLine(level, seglist); if (nodeline == NULL) { RotateMessage(YELLOW, 2); *node_r = NULL; *ssector_r = CreateSSector(level, seglist) | 0x8000; return FALSE; } RotateMessage(LIGHTBLUE, 2); while (seglist) { curseg = seglist; seglist = seglist->next; tmp_vertex_corrections = 0; LineOnSide(level, nodeline, curseg); BSP_vertex_corrections += tmp_vertex_corrections; if (sideL == 0) { if (sideS == 1) { UPDATE_LIST_OF_SEGS_ON_SIDE(frontstart, frontend, curseg) InsertObject(level, OBJ_VERTEXES, -2, interX, interY); INTRODUCE_NEW_SEG(newSEPtr, curseg) UPDATE_LIST_OF_SEGS_ON_SIDE(backstart, backend, newSEPtr) UPDATE_IF_TWOSIDED_SPLIT(backstart, backend, frontstart, frontend) } else { UPDATE_LIST_OF_SEGS_ON_SIDE(backstart, backend, curseg) InsertObject(level, OBJ_VERTEXES, -2, interX, interY); INTRODUCE_NEW_SEG(newSEPtr, curseg) UPDATE_LIST_OF_SEGS_ON_SIDE(frontstart, frontend, newSEPtr) UPDATE_IF_TWOSIDED_SPLIT(frontstart, frontend, backstart, backend) } ShowBSPProgress(level, OBJ_VERTEXES); } if (sideL == 1) { UPDATE_LIST_OF_SEGS_ON_SIDE(frontstart, frontend, curseg) if (sideE != 0 || sideS != 0) { UPDATE_IF_TWOSIDED(frontstart, frontend) } else { UPDATE_IF_TWOSIDED(backstart, backend) } } else if (sideL == 2) { UPDATE_LIST_OF_SEGS_ON_SIDE(backstart, backend, curseg) if (sideE != 0 || sideS != 0) { UPDATE_IF_TWOSIDED(backstart,backend) } else { UPDATE_IF_TWOSIDED(frontstart,frontend) } } } if (frontstart == NULL || backstart == NULL) ProgError("could not split the Segs list (this is a BUG!)"); frontend->next = NULL; backend->next = NULL; /*RP Allocate new node and fill in info. */ node = (struct Node *)GetMemory(sizeof(struct Node)); memset(node, 0, sizeof(struct Node)); /*RP Temporary pointers to optimize array accesses */ vstart = &level->vertexes[nodeline->start]; vend = &level->vertexes[nodeline->end]; node->x = vstart->x; node->y = vstart->y; node->dx = vend->x - node->x; node->dy = vend->y - node->y; ComputeBoundingBox(level, frontstart, &(node->minx1), &(node->maxx1), &(node->miny1), &(node->maxy1)); ComputeBoundingBox(level, backstart, &(node->minx2), &(node->maxx2), &(node->miny2), &(node->maxy2)); MakeNodes(level, &(node->node1), &(node->child1), frontstart); MakeNodes(level, &(node->node2), &(node->child2), backstart); *node_r = node; *ssector_r = 0; return TRUE; } /* Build the initial list of segments */ void BuildInitialSegList (LevelPtr level, SEPtr *pseglist, UInt16 *pnumsegs) { UInt16 n; SEPtr seglist, lastseg; UInt16 numsegs; /* setup the initial list of segments */ seglist = NULL; lastseg = NULL; numsegs = 0; for (n = 0 ; n < level->num_linedefs ; n++) { LDPtr pld = &level->linedefs[n]; VPtr vstart = &level->vertexes[pld->start]; VPtr vend = &level->vertexes[pld->end]; if (pld->sidedef1 >= 0) { /* Add a SEG in the list */ if (seglist) { /*! RP Use GetFarMemory or GetMemory ? */ lastseg->next = (SEPtr) GetFarMemory(sizeof(struct Seg)); lastseg = lastseg->next; } else { /*! RP Use GetFarMemory or GetMemory ? */ seglist = (SEPtr) GetFarMemory(sizeof(struct Seg)); lastseg = seglist; } lastseg->next = NULL; lastseg->start = pld->start; lastseg->end = pld->end; lastseg->angle = SegmentBA(vend->x - vstart->x, vend->y - vstart->y); lastseg->linedef = n; lastseg->flip = 0; lastseg->dist = 0; numsegs ++; } if (pld->sidedef2 >= 0) { /* Add a SEG in the list */ if (seglist) { /*! RP Use GetFarMemory or GetMemory ? */ lastseg->next = (SEPtr) GetFarMemory(sizeof(struct Seg)); lastseg = lastseg->next; } else { /*! RP Use GetFarMemory or GetMemory ? */ seglist = (SEPtr) GetFarMemory(sizeof(struct Seg)); lastseg = loc_segs; } lastseg->next = NULL; lastseg->start = pld->end; lastseg->end = pld->start; lastseg->angle = SegmentBA(vstart->x - vend->x, vstart->y - vend->y); lastseg->linedef = n; lastseg->flip = 1; lastseg->dist = 0; numsegs ++; } } /* End for */ /* Init. return parameters */ *pseglist = seglist; *pnumsegs = numsegs; } /* Prepare calling MakeNodes. level Pointer to the LevelInfo to build. nodes_root Pointer to the Node root. segs_list Pointer to the Segs list. num_segs Pointer to the number of Segs var. ssectors_list Pointer to the SSectors list. num_ssectors Pointer to the number of SSectors var. */ /*!RP This function is not called recursively. Someone added the 'MakeNodes' function, which is called recursively */ int CreateNodes(LevelPtr level, NPtr *nodes_root, SEPtr *segs_list, UInt16 *num_segs, SSPtr *ssectors_list, UInt16 *num_ssectors) { Bool result; /* result of MakeNodes */ Int16 ssector_r; /* Dummy param to call MakeNodes */ SEPtr seglist; /* Initial list of segments */ UInt16 numsegs; /* Initial number of segments */ /*RP Copy BSP Config option to module static vars */ BSP_splitfactor = Config.BSP_splitfactor; BSP_slopefactor = Config.BSP_slopefactor; BSP_speedfactor = Config.BSP_speedfactor; /*RP Init SSegs, SSECTORS global vars */ loc_segs = NULL; loc_last_seg = NULL; loc_num_segs = 0; loc_ssectors = NULL; loc_last_ssector = NULL; loc_num_ssectors = 0; /*RP Build the initial list of segments */ BuildInitialSegList (level, &seglist, &numsegs); LogMessage(": Starting Nodes builder...\n"); LogMessage("\tNumber of Vertices: %d\n", level->num_vertexes); LogMessage("\tNumber of Segs: %d\n", numsegs); /*RP Draw box with rotating line */ RotateMessage(BLACK, 0); if (UseMouse) HideMousePointer(); /*RP Init. stats about what node builder does */ BSP_vertex_corrections = 0; BSP_splits = 0; BSP_2S_splits = 0; ShowBSPProgress(level, OBJ_VERTEXES); ShowBSPProgress(level, OBJ_SIDEDEFS); /*RP * Call the nodes builder * . nodes_root will contain the root of the node tree, * . ssector_r is a dummy param (the 3rd param is only used in recursive calls) * . seglist is the initial list of segments (made by BuildInitialSegList) */ ssector_r = 0; result = MakeNodes(level, nodes_root, &ssector_r, seglist); /*RP Delete box with rotating line */ RotateMessage(BLACK, -1); /*RP Set output params */ /* nodes_root is OK (MakeNodes) */ *segs_list = loc_segs; *num_segs = loc_num_segs; *ssectors_list = loc_ssectors; *num_ssectors = loc_num_ssectors; return result; } /* end of file */