ref: a3c5162093a589f793e01347c92ef1cc59f0b577
parent: 3bda65bfe8bc9583d30d9096d19b54c17d55ce94
parent: d3a77733f886d51c879e324d7c87baf4635de5e0
author: Andrew Apted <ajapted@gmail.com>
date: Fri Dec 15 13:55:58 EST 2023
Merge branch 'pragmatic' into master.
--- a/README.md
+++ b/README.md
@@ -8,7 +8,7 @@
About
-----
-This is a project to make a simple node-builder which can be plugged
+This is a project to make a simple node-builder which can be dropped
into an existing DOOM code-base, and build nodes at level-load time.
It is written in C, and uses fixed-point math (no FPU required).
@@ -28,8 +28,14 @@
the nodes are even slightly different.
-Engine changes
---------------
+Status
+------
+
+Finished, working, usable.
+
+
+Using this code in a DOOM port
+------------------------------
The bulk of my node-building code is in two new source files:
```
@@ -37,16 +43,18 @@
nano_bsp.h
```
-However, several other parts of the engine need to be updated, due to
-the changes to the *node_t* and *subsector_t* types in the `r_defs.h`
-header file, since these structs no longer exist in one big array,
-but now get allocated individually and linked via pointers.
+So firstly (and obviously) those files need to be added.
-The following functions need to be updated:
-- R_RenderBSPNode() and R_Subsector() in `r_bsp.c`
-- R_PointInSubsector() in `r_main.c`
-- P_CrossBSPNode() and P_CrossSubsector() in `p_sight.c`
-- P_LoadSegs(), P_LoadSubsectors(), P_LoadNodes() in `p_setup.c`
+Secondly, the *seg_t* struct in `r_defs.h` needs two new fields, `side`
+and `next`. Look at that file in this repository and copy'n'paste
+those fields.
+
+Finally, add `#include "nano_bsp.h"` to p_setup.c, and within the
+P_SetupLevel function call `BSP_BuildNodes()`. In this code-base, it
+is always called unless explicitly disabled by a command-line option
+or when playing back demos. In your code-base, you may want to only
+invoke it when the map is lacking nodes, and/or give users a config
+setting to explictly enable it.
About this repository
--- a/nano_bsp.c
+++ b/nano_bsp.c
@@ -46,9 +46,17 @@
#define DIST_EPSILON (FRACUNIT / 64)
+// this value is a trade-off. lower values will build nodes faster,
+// but higher values allow picking better BSP partitions (and hence
+// produce better BSP trees).
#define FAST_THRESHOLD 128
+// reducing splits is important to get good BSP trees. making this
+// value really low produces trees which have a *lot* more nodes
+// (I am not sure exactly why). higher values are okay.
+#define SPLIT_COST 11
+
#undef MAX
#define MAX(a, b) ((a) > (b) ? (a) : (b))
@@ -56,6 +64,25 @@
#define MIN(a, b) ((a) < (b) ? (a) : (b))
+typedef struct Nanode nanode_t;
+
+struct Nanode
+{+ // when non-NULL, this is actually a leaf of the BSP tree
+ seg_t * segs;
+
+ // final index number of this node / leaf
+ int index;
+
+ // partition line (start coord, delta to end)
+ fixed_t x, y, dx, dy;
+
+ // right and left children
+ struct Nanode * right;
+ struct Nanode * left;
+};
+
+
vertex_t * BSP_NewVertex (fixed_t x, fixed_t y)
{vertex_t * vert = Z_Malloc(sizeof(vertex_t), PU_LEVEL, NULL);
@@ -71,23 +98,15 @@
return seg;
}
-subsector_t * BSP_NewSubsector (void)
+nanode_t * BSP_NewNode (void)
{- subsector_t * sub = Z_Malloc (sizeof(subsector_t), PU_LEVEL, NULL);
- memset (sub, 0, sizeof(*sub));
- return sub;
-}
-
-node_t * BSP_NewNode (void)
-{- node_t * node = Z_Malloc (sizeof(node_t), PU_LEVEL, NULL);
+ nanode_t * node = Z_Malloc (sizeof(nanode_t), PU_LEVEL, NULL);
memset (node, 0, sizeof(*node));
return node;
}
-
/* DEBUG:
-void DumpNode (node_t * N, int lev)
+void DumpNode (nanode_t * N, int lev)
{char spaces[256];
@@ -101,11 +120,7 @@
printf ("%snode %p\n", spaces, N);- printf ("%sbbox (%d %d) .. (%d %d)\n", spaces,- N->bbox[BOXLEFT] >> 16, N->bbox[BOXBOTTOM] >> 16,
- N->bbox[BOXRIGHT] >> 16, N->bbox[BOXTOP] >> 16);
-
- if (N->sub == NULL)
+ if (N->segs == NULL)
{ printf ("%spartition (%d %d) --> (%d %d)\n", spaces,N->x >> 16, N->y >> 16,
@@ -123,12 +138,10 @@
}
else
{- subsector_t * sub = N->sub;
+ printf ("%ssector #%d\n", spaces, (int)(N->segs->frontsector - sectors));- printf ("%ssector #%d\n", spaces, (int)(sub->sector - sectors));-
seg_t * S;
- for (S = sub->segs ; S != NULL ; S = S->next)
+ for (S = N->segs ; S != NULL ; S = S->next)
{ printf ("%s line #%d, side %d : (%d %d) --> (%d %d)\n", spaces,(int) (S->linedef - lines), S->side,
@@ -155,35 +168,30 @@
{// Note: not using M_AddToBox() here, because it is broken!
- bbox[BOXLEFT ] = INT_MAX; bbox[BOXRIGHT ] = INT_MIN;
- bbox[BOXBOTTOM] = INT_MAX; bbox[BOXTOP ] = INT_MIN;
+ bbox[BOXLEFT] = INT_MAX; bbox[BOXRIGHT] = INT_MIN;
+ bbox[BOXBOTTOM] = INT_MAX; bbox[BOXTOP] = INT_MIN;
seg_t * S;
for (S = soup ; S != NULL ; S = S->next)
{- bbox[BOXLEFT ] = MIN (bbox[BOXLEFT ], S->v1->x);
- bbox[BOXLEFT ] = MIN (bbox[BOXLEFT ], S->v2->x);
-
+ bbox[BOXLEFT] = MIN (bbox[BOXLEFT], S->v1->x);
+ bbox[BOXLEFT] = MIN (bbox[BOXLEFT], S->v2->x);
bbox[BOXBOTTOM] = MIN (bbox[BOXBOTTOM], S->v1->y);
bbox[BOXBOTTOM] = MIN (bbox[BOXBOTTOM], S->v2->y);
- bbox[BOXRIGHT ] = MAX (bbox[BOXRIGHT ], S->v1->x);
- bbox[BOXRIGHT ] = MAX (bbox[BOXRIGHT ], S->v2->x);
-
- bbox[BOXTOP ] = MAX (bbox[BOXTOP ], S->v1->y);
- bbox[BOXTOP ] = MAX (bbox[BOXTOP ], S->v2->y);
+ bbox[BOXRIGHT] = MAX (bbox[BOXRIGHT], S->v1->x);
+ bbox[BOXRIGHT] = MAX (bbox[BOXRIGHT], S->v2->x);
+ bbox[BOXTOP] = MAX (bbox[BOXTOP], S->v1->y);
+ bbox[BOXTOP] = MAX (bbox[BOXTOP], S->v2->y);
}
}
-void BSP_MergeBounds (node_t * node)
+void BSP_MergeBounds (fixed_t * out, fixed_t * box1, fixed_t * box2)
{- fixed_t * L_bbox = node->left ->bbox;
- fixed_t * R_bbox = node->right->bbox;
-
- node->bbox[BOXLEFT ] = MIN (L_bbox[BOXLEFT ], R_bbox[BOXLEFT ]);
- node->bbox[BOXBOTTOM] = MIN (L_bbox[BOXBOTTOM], R_bbox[BOXBOTTOM]);
- node->bbox[BOXRIGHT ] = MAX (L_bbox[BOXRIGHT ], R_bbox[BOXRIGHT ]);
- node->bbox[BOXTOP ] = MAX (L_bbox[BOXTOP ], R_bbox[BOXTOP ]);
+ out[BOXLEFT] = MIN (box1[BOXLEFT], box2[BOXLEFT]);
+ out[BOXBOTTOM] = MIN (box1[BOXBOTTOM], box2[BOXBOTTOM]);
+ out[BOXRIGHT] = MAX (box1[BOXRIGHT], box2[BOXRIGHT]);
+ out[BOXTOP] = MAX (box1[BOXTOP], box2[BOXTOP]);
}
void BSP_SegForLineSide (int i, int side, seg_t ** list_var)
@@ -193,7 +201,6 @@
if (ld->sidenum[side] < 0)
return;
- // create the seg
seg_t * seg = BSP_NewSeg ();
seg->v1 = side ? ld->v2 : ld->v1;
@@ -229,32 +236,12 @@
return list;
}
-node_t * BSP_CreateLeaf (seg_t * soup)
+nanode_t * BSP_CreateLeaf (seg_t * soup)
{- subsector_t * sub = BSP_NewSubsector ();
- node_t * node = BSP_NewNode ();
+ nanode_t * node = BSP_NewNode ();
- sub->segs = soup;
+ node->segs = soup;
- // to determine the sector, avoid self-referencing lines
- // since they are often used for special effects.
-
- seg_t * S;
- for (S = soup ; S != NULL ; S = S->next)
- {- if (S->frontsector != S->backsector)
- {- sub->sector = S->frontsector;
- break;
- }
- }
-
- if (sub->sector == NULL)
- sub->sector = soup->frontsector;
-
- node->sub = sub;
- BSP_BoundingBox (soup, node->bbox);
-
return node;
}
@@ -458,8 +445,8 @@
if (vert_ok && horiz_ok)
{- int vert_cost = abs (v_eval.left - v_eval.right) * 2 + v_eval.split * 11;
- int horiz_cost = abs (h_eval.left - h_eval.right) * 2 + h_eval.split * 11;
+ int vert_cost = abs (v_eval.left - v_eval.right) * 2 + v_eval.split * SPLIT_COST;
+ int horiz_cost = abs (h_eval.left - h_eval.right) * 2 + h_eval.split * SPLIT_COST;
return (horiz_cost < vert_cost) ? horiz_part : vert_part;
}
@@ -487,7 +474,7 @@
if (BSP_EvalPartition (part, soup, &eval))
{- int cost = abs (eval.left - eval.right) * 2 + eval.split * 11;
+ int cost = abs (eval.left - eval.right) * 2 + eval.split * SPLIT_COST;
if (cost < best_cost)
{@@ -516,7 +503,6 @@
return seg->v1->y + FixedMul (seg->v2->y - seg->v1->y, along);
}
-
fixed_t BSP_HorizIntersection (fixed_t part_y, seg_t * seg)
{// vertical seg?
@@ -531,7 +517,6 @@
return seg->v1->x + FixedMul (seg->v2->x - seg->v1->x, along);
}
-
void BSP_ComputeIntersection (seg_t * part, seg_t * seg, fixed_t * x, fixed_t * y)
{// vertical partition?
@@ -590,7 +575,6 @@
*y = seg->v1->y + FixedMul (seg->v2->y - seg->v1->y, along);
}
-
//
// For segs not intersecting the partition, just move them into the
// correct output list (`lefts` or `rights`). otherwise split the seg
@@ -665,7 +649,7 @@
}
}
-node_t * BSP_SubdivideSegs (seg_t * soup)
+nanode_t * BSP_SubdivideSegs (seg_t * soup)
{seg_t * part = BSP_PickNode_Fast (soup);
@@ -675,7 +659,7 @@
if (part == NULL)
return BSP_CreateLeaf (soup);
- node_t * N = BSP_NewNode ();
+ nanode_t * N = BSP_NewNode ();
N->x = part->v1->x;
N->y = part->v1->y;
@@ -703,20 +687,128 @@
N->right = BSP_SubdivideSegs (rights);
N->left = BSP_SubdivideSegs (lefts);
- BSP_MergeBounds (N);
-
return N;
}
//----------------------------------------------------------------------------
-void Nano_BuildBSP (void)
+static int nano_seg_index;
+
+void BSP_CountStuff (nanode_t * N)
{+ if (N->segs == NULL)
+ {+ // must recurse first, to ensure root node gets highest index
+ BSP_CountStuff (N->left);
+ BSP_CountStuff (N->right);
+
+ N->index = numnodes;
+ numnodes += 1;
+ }
+ else
+ {+ N->index = numsubsectors;
+ numsubsectors += 1;
+
+ seg_t * seg;
+ for (seg = N->segs ; seg != NULL; seg = seg->next)
+ numsegs += 1;
+ }
+}
+
+void BSP_WriteSubsector (nanode_t * N)
+{+ subsector_t * out = &subsectors[N->index];
+
+ out->numlines = 0;
+ out->firstline = nano_seg_index;
+ out->sector = NULL; // determined in P_GroupLines
+
+ seg_t * seg;
+
+ while (N->segs != NULL)
+ {+ seg = N->segs;
+
+ // unlink this seg from the list
+ N->segs = seg->next;
+ seg->next = NULL;
+
+ // copy and free it
+ memcpy (&segs[nano_seg_index], seg, sizeof(seg_t));
+
+ Z_Free (seg);
+
+ nano_seg_index += 1;
+ out->numlines += 1;
+ }
+}
+
+unsigned int BSP_WriteNode (nanode_t * N, fixed_t * bbox)
+{+ unsigned int index = N->index;
+
+ if (N->segs != NULL)
+ {+ index |= NF_SUBSECTOR;
+
+ BSP_BoundingBox (N->segs, bbox);
+ BSP_WriteSubsector (N);
+ }
+ else
+ {+ node_t * out = &nodes[N->index];
+
+ out->x = N->x;
+ out->y = N->y;
+ out->dx = N->dx;
+ out->dy = N->dy;
+
+ int c;
+ for (c = 0 ; c < 2 ; c++)
+ {+ nanode_t * child = (c == 0) ? N->right : N->left;
+
+ out->children[c] = BSP_WriteNode (child, out->bbox[c]);
+ }
+
+ BSP_MergeBounds (bbox, out->bbox[0], out->bbox[1]);
+ }
+
+ Z_Free (N);
+
+ return index;
+}
+
+void BSP_BuildNodes (void)
+{seg_t * list = BSP_CreateSegs ();
- root_node = BSP_SubdivideSegs (list);
+ nanode_t * root = BSP_SubdivideSegs (list);
/* DEBUG:
- DumpNode (root_node, 0);
+ DumpNode (root, 0);
*/
+ // determine total number of nodes, subsectors and segs
+ numnodes = 0;
+ numsubsectors = 0;
+ numsegs = 0;
+
+ BSP_CountStuff (root);
+
+ // allocate the global arrays
+ nodes = Z_Malloc (numnodes*sizeof(node_t), PU_LEVEL, NULL);
+ subsectors = Z_Malloc (numsubsectors*sizeof(subsector_t), PU_LEVEL, NULL);
+ segs = Z_Malloc (numsegs*sizeof(seg_t), PU_LEVEL, NULL);
+
+ // clear the initial contents
+ memset (nodes, 0, numnodes*sizeof(node_t));
+ memset (subsectors, 0, numsubsectors*sizeof(subsector_t));
+
+ nano_seg_index = 0;
+
+ fixed_t dummy[4];
+
+ // this also frees stuff as it goes
+ BSP_WriteNode (root, dummy);
}
--- a/nano_bsp.h
+++ b/nano_bsp.h
@@ -26,8 +26,6 @@
#ifndef __NANO_BSP_H__
#define __NANO_BSP_H__
-node_t * BSP_NewNode (void);
-
-void Nano_BuildBSP (void);
+void BSP_BuildNodes (void);
#endif
--- a/p_setup.c
+++ b/p_setup.c
@@ -51,21 +51,18 @@
int numvertexes;
vertex_t* vertexes;
+int numsegs;
+seg_t* segs;
+
int numsectors;
sector_t* sectors;
-// andrewj: made these local to this file, added root_node.
-static int numsegs;
-static seg_t* segs;
+int numsubsectors;
+subsector_t* subsectors;
-static int numsubsectors;
-static subsector_t* subsectors;
+int numnodes;
+node_t* nodes;
-static int numnodes;
-static node_t* nodes;
-
-node_t* root_node;
-
int numlines;
line_t* lines;
@@ -207,50 +204,49 @@
//
// P_LoadSegs
//
-// andrewj: updated this code (etc) for nano-bsp.
-//
void P_LoadSegs (int lump)
{- byte* data;
- int i;
- mapseg_t* ml;
- seg_t* li;
- line_t* ldef;
- int linedef;
- int sidenum;
-
+ byte* data;
+ int i;
+ mapseg_t* ml;
+ seg_t* li;
+ line_t* ldef;
+ int linedef;
+ int side;
+ int sidenum;
+
numsegs = W_LumpLength (lump) / sizeof(mapseg_t);
- segs = Z_Malloc (numsegs*sizeof(seg_t),PU_LEVEL,0);
+ segs = Z_Malloc (numsegs*sizeof(seg_t),PU_LEVEL,0);
memset (segs, 0, numsegs*sizeof(seg_t));
data = W_CacheLumpNum (lump,PU_STATIC);
-
+
ml = (mapseg_t *)data;
li = segs;
for (i=0 ; i<numsegs ; i++, li++, ml++)
{- li->v1 = &vertexes[LE_SHORT(ml->v1)];
- li->v2 = &vertexes[LE_SHORT(ml->v2)];
+ li->v1 = &vertexes[LE_SHORT(ml->v1)];
+ li->v2 = &vertexes[LE_SHORT(ml->v2)];
- li->angle = (LE_SHORT(ml->angle))<<FRACBITS;
- li->offset = (LE_SHORT(ml->offset))<<FRACBITS;
- linedef = LE_SHORT(ml->linedef);
- ldef = &lines[linedef];
- li->linedef = ldef;
- li->side = LE_SHORT(ml->side);
+ li->angle = (LE_SHORT(ml->angle))<<FRACBITS;
+ li->offset = (LE_SHORT(ml->offset))<<FRACBITS;
+ linedef = LE_SHORT(ml->linedef);
+ ldef = &lines[linedef];
+ li->linedef = ldef;
+ side = LE_SHORT(ml->side);
// e6y: check for wrong indexes
- if ((unsigned)ldef->sidenum[li->side] >= (unsigned)numsides)
+ if ((unsigned)ldef->sidenum[side] >= (unsigned)numsides)
{ I_Error("P_LoadSegs: linedef %d for seg %d references a non-existent sidedef %d",- linedef, i, (unsigned)ldef->sidenum[li->side]);
+ linedef, i, (unsigned)ldef->sidenum[side]);
}
- li->sidedef = &sides[ldef->sidenum[li->side]];
- li->frontsector = sides[ldef->sidenum[li->side]].sector;
+ li->sidedef = &sides[ldef->sidenum[side]];
+ li->frontsector = sides[ldef->sidenum[side]].sector;
if (ldef-> flags & ML_TWOSIDED)
{- sidenum = ldef->sidenum[li->side ^ 1];
+ sidenum = ldef->sidenum[side ^ 1];
// If the sidenum is out of range, this may be a "glass hack"
// impassible window. Point at side #0 (this may not be
@@ -269,10 +265,10 @@
}
else
{- li->backsector = NULL;
+ li->backsector = 0;
}
}
-
+
W_ReleaseLumpNum(lump);
}
@@ -282,35 +278,25 @@
//
void P_LoadSubsectors (int lump)
{- byte* data;
- int i;
- mapsubsector_t* ms;
- subsector_t* ss;
-
+ byte* data;
+ int i;
+ mapsubsector_t* ms;
+ subsector_t* ss;
+
numsubsectors = W_LumpLength (lump) / sizeof(mapsubsector_t);
- subsectors = Z_Malloc (numsubsectors*sizeof(subsector_t),PU_LEVEL,0);
- memset (subsectors, 0, numsubsectors*sizeof(subsector_t));
+ subsectors = Z_Malloc (numsubsectors*sizeof(subsector_t),PU_LEVEL,0);
data = W_CacheLumpNum (lump,PU_STATIC);
-
+
ms = (mapsubsector_t *)data;
memset (subsectors,0, numsubsectors*sizeof(subsector_t));
ss = subsectors;
-
+
for (i=0 ; i<numsubsectors ; i++, ss++, ms++)
{- int numlines = LE_SHORT(ms->numsegs);
- int firstline = LE_SHORT(ms->firstseg);
-
- if (numlines > 0)
- {- ss->segs = &segs[firstline];
-
- int i;
- for (i = 1 ; i < numlines ; i++)
- segs[firstline + i - 1].next = &segs[firstline + i];
- }
+ ss->numlines = LE_SHORT(ms->numsegs);
+ ss->firstline = LE_SHORT(ms->firstseg);
}
-
+
W_ReleaseLumpNum(lump);
}
@@ -320,30 +306,30 @@
//
void P_LoadSectors (int lump)
{- byte* data;
- int i;
- mapsector_t* ms;
- sector_t* ss;
-
+ byte* data;
+ int i;
+ mapsector_t* ms;
+ sector_t* ss;
+
numsectors = W_LumpLength (lump) / sizeof(mapsector_t);
- sectors = Z_Malloc (numsectors*sizeof(sector_t),PU_LEVEL,0);
+ sectors = Z_Malloc (numsectors*sizeof(sector_t),PU_LEVEL,0);
memset (sectors, 0, numsectors*sizeof(sector_t));
data = W_CacheLumpNum (lump,PU_STATIC);
-
+
ms = (mapsector_t *)data;
ss = sectors;
for (i=0 ; i<numsectors ; i++, ss++, ms++)
{- ss->floorheight = LE_SHORT(ms->floorheight)<<FRACBITS;
- ss->ceilingheight = LE_SHORT(ms->ceilingheight)<<FRACBITS;
- ss->floorpic = R_FlatNumForName(ms->floorpic);
- ss->ceilingpic = R_FlatNumForName(ms->ceilingpic);
- ss->lightlevel = LE_SHORT(ms->lightlevel);
- ss->special = LE_SHORT(ms->special);
- ss->tag = LE_SHORT(ms->tag);
- ss->thinglist = NULL;
+ ss->floorheight = LE_SHORT(ms->floorheight)<<FRACBITS;
+ ss->ceilingheight = LE_SHORT(ms->ceilingheight)<<FRACBITS;
+ ss->floorpic = R_FlatNumForName(ms->floorpic);
+ ss->ceilingpic = R_FlatNumForName(ms->ceilingpic);
+ ss->lightlevel = LE_SHORT(ms->lightlevel);
+ ss->special = LE_SHORT(ms->special);
+ ss->tag = LE_SHORT(ms->tag);
+ ss->thinglist = NULL;
}
-
+
W_ReleaseLumpNum(lump);
}
@@ -353,78 +339,35 @@
//
void P_LoadNodes (int lump)
{- byte* data;
- int i;
- int j;
- int k;
- mapnode_t* mn;
- node_t* no;
-
+ byte* data;
+ int i;
+ int j;
+ int k;
+ mapnode_t* mn;
+ node_t* no;
+
numnodes = W_LumpLength (lump) / sizeof(mapnode_t);
- nodes = Z_Malloc (numnodes*sizeof(node_t),PU_LEVEL,0);
- memset (nodes, 0, numnodes*sizeof(node_t));
+ nodes = Z_Malloc (numnodes*sizeof(node_t),PU_LEVEL,0);
data = W_CacheLumpNum (lump,PU_STATIC);
-
+
mn = (mapnode_t *)data;
no = nodes;
-
- for (i=0 ; i < numnodes ; i++, no++, mn++)
+
+ for (i=0 ; i<numnodes ; i++, no++, mn++)
{- no->x = LE_SHORT(mn->x) << FRACBITS;
- no->y = LE_SHORT(mn->y) << FRACBITS;
- no->dx = LE_SHORT(mn->dx) << FRACBITS;
- no->dy = LE_SHORT(mn->dy) << FRACBITS;
-
- for (j=0 ; j < 2 ; j++)
- {- unsigned short childnum = LE_SHORT(mn->children[j]);
-
- node_t * child;
-
- if (childnum & NF_SUBSECTOR)
- {- child = BSP_NewNode ();
- child->sub = &subsectors[childnum ^ NF_SUBSECTOR];
- }
- else
- {- child = &nodes[childnum];
- }
-
- if (j == 0)
- no->right = child;
- else
- no->left = child;
- }
+ no->x = LE_SHORT(mn->x)<<FRACBITS;
+ no->y = LE_SHORT(mn->y)<<FRACBITS;
+ no->dx = LE_SHORT(mn->dx)<<FRACBITS;
+ no->dy = LE_SHORT(mn->dy)<<FRACBITS;
+ for (j=0 ; j<2 ; j++)
+ {+ no->children[j] = LE_SHORT(mn->children[j]);
+ for (k=0 ; k<4 ; k++)
+ no->bbox[j][k] = LE_SHORT(mn->bbox[j][k])<<FRACBITS;
+ }
}
-
- // the second pass handles the bounding boxes
-
- mn = (mapnode_t *)data;
- no = nodes;
-
- for (i=0 ; i < numnodes ; i++, no++, mn++)
- {- for (j=0 ; j < 2 ; j++)
- {- node_t * child = (j == 0) ? no->right : no->left;
-
- for (k=0 ; k < 4 ; k++)
- child->bbox[k] = LE_SHORT(mn->bbox[j][k]) << FRACBITS;
- }
- }
-
+
W_ReleaseLumpNum(lump);
-
- if (numnodes > 0)
- {- root_node = &nodes[numnodes-1];
- }
- else
- {- root_node = BSP_NewNode ();
- root_node->sub = &subsectors[0];
- }
}
@@ -651,14 +594,16 @@
line_t* li;
sector_t* sector;
subsector_t* ss;
+ seg_t* seg;
fixed_t bbox[4];
int block;
-
+
// look up sector number for each subsector
ss = subsectors;
for (i=0 ; i<numsubsectors ; i++, ss++)
{- ss->sector = ss->segs->sidedef->sector;
+ seg = &segs[ss->firstline];
+ ss->sector = seg->sidedef->sector;
}
// count number of lines in each sector
@@ -904,13 +849,13 @@
// *WILL* desync otherwise.
if (demoplayback || M_CheckParm("-nobsp") > 0) {- P_LoadSegs (lumpnum+ML_SEGS);
P_LoadSubsectors (lumpnum+ML_SSECTORS);
P_LoadNodes (lumpnum+ML_NODES);
+ P_LoadSegs (lumpnum+ML_SEGS);
}
else
{- Nano_BuildBSP ();
+ BSP_BuildNodes ();
}
P_GroupLines ();
--- a/p_sight.c
+++ b/p_sight.c
@@ -122,148 +122,172 @@
//
// P_CrossSubsector
-// Returns true if strace crosses the given subsector successfully.
+// Returns true
+// if strace crosses the given subsector successfully.
//
-boolean P_CrossSubsector (subsector_t * sub)
+boolean P_CrossSubsector (int num)
{+ seg_t* seg;
+ line_t* line;
+ int s1;
+ int s2;
+ int count;
+ subsector_t* sub;
+ sector_t* front;
+ sector_t* back;
+ fixed_t opentop;
+ fixed_t openbottom;
+ divline_t divl;
+ vertex_t* v1;
+ vertex_t* v2;
+ fixed_t frac;
+ fixed_t slope;
+
+//#ifdef RANGECHECK
+ if (num>=numsubsectors)
+ I_Error ("P_CrossSubsector: ss %i with numss = %i",+ num,
+ numsubsectors);
+//#endif
+
+ sub = &subsectors[num];
+
// check lines
- seg_t * seg;
- for (seg = sub->segs ; seg != NULL ; seg = seg->next)
+ count = sub->numlines;
+ seg = &segs[sub->firstline];
+
+ for ( ; count ; seg++, count--)
{- line_t * line = seg->linedef;
+ line = seg->linedef;
- // allready checked other side?
- if (line->validcount == validcount)
- continue;
+ // allready checked other side?
+ if (line->validcount == validcount)
+ continue;
+
+ line->validcount = validcount;
- line->validcount = validcount;
+ v1 = line->v1;
+ v2 = line->v2;
+ s1 = P_DivlineSide (v1->x,v1->y, &strace);
+ s2 = P_DivlineSide (v2->x, v2->y, &strace);
- vertex_t * v1 = line->v1;
- vertex_t * v2 = line->v2;
+ // line isn't crossed?
+ if (s1 == s2)
+ continue;
+
+ divl.x = v1->x;
+ divl.y = v1->y;
+ divl.dx = v2->x - v1->x;
+ divl.dy = v2->y - v1->y;
+ s1 = P_DivlineSide (strace.x, strace.y, &divl);
+ s2 = P_DivlineSide (t2x, t2y, &divl);
- int s1 = P_DivlineSide (v1->x, v1->y, &strace);
- int s2 = P_DivlineSide (v2->x, v2->y, &strace);
+ // line isn't crossed?
+ if (s1 == s2)
+ continue;
- // line isn't crossed?
- if (s1 == s2)
- continue;
-
- divline_t divl;
-
- divl.x = v1->x;
- divl.y = v1->y;
- divl.dx = v2->x - v1->x;
- divl.dy = v2->y - v1->y;
-
- s1 = P_DivlineSide (strace.x, strace.y, &divl);
- s2 = P_DivlineSide (t2x, t2y, &divl);
-
- // line isn't crossed?
- if (s1 == s2)
- continue;
-
// Backsector may be NULL if this is an "impassible
// glass" hack line.
if (line->backsector == NULL)
+ {return false;
+ }
- // stop because it is not two sided anyway
- // might do this after updating validcount?
- if ( !(line->flags & ML_TWOSIDED) )
- return false;
+ // stop because it is not two sided anyway
+ // might do this after updating validcount?
+ if ( !(line->flags & ML_TWOSIDED) )
+ return false;
+
+ // crosses a two sided line
+ front = seg->frontsector;
+ back = seg->backsector;
- // crosses a two sided line
- sector_t * front = seg->frontsector;
- sector_t * back = seg->backsector;
+ // no wall to block sight with?
+ if (front->floorheight == back->floorheight
+ && front->ceilingheight == back->ceilingheight)
+ continue;
- // no wall to block sight with?
- if (front->floorheight == back->floorheight
- && front->ceilingheight == back->ceilingheight)
- continue;
+ // possible occluder
+ // because of ceiling height differences
+ if (front->ceilingheight < back->ceilingheight)
+ opentop = front->ceilingheight;
+ else
+ opentop = back->ceilingheight;
- fixed_t opentop;
- fixed_t openbottom;
-
- // possible occluder
- // because of ceiling height differences
- if (front->ceilingheight < back->ceilingheight)
- opentop = front->ceilingheight;
- else
- opentop = back->ceilingheight;
-
- // because of ceiling height differences
- if (front->floorheight > back->floorheight)
- openbottom = front->floorheight;
- else
- openbottom = back->floorheight;
-
- // quick test for totally closed doors
- if (openbottom >= opentop)
- return false; // stop
-
- fixed_t frac = P_InterceptVector2 (&strace, &divl);
- fixed_t slope;
-
- if (front->floorheight != back->floorheight)
- {- slope = FixedDiv (openbottom - sightzstart , frac);
- if (slope > bottomslope)
- bottomslope = slope;
- }
-
- if (front->ceilingheight != back->ceilingheight)
- {- slope = FixedDiv (opentop - sightzstart , frac);
- if (slope < topslope)
- topslope = slope;
- }
-
- if (topslope <= bottomslope)
- return false; // stop
+ // because of ceiling height differences
+ if (front->floorheight > back->floorheight)
+ openbottom = front->floorheight;
+ else
+ openbottom = back->floorheight;
+
+ // quick test for totally closed doors
+ if (openbottom >= opentop)
+ return false; // stop
+
+ frac = P_InterceptVector2 (&strace, &divl);
+
+ if (front->floorheight != back->floorheight)
+ {+ slope = FixedDiv (openbottom - sightzstart , frac);
+ if (slope > bottomslope)
+ bottomslope = slope;
+ }
+
+ if (front->ceilingheight != back->ceilingheight)
+ {+ slope = FixedDiv (opentop - sightzstart , frac);
+ if (slope < topslope)
+ topslope = slope;
+ }
+
+ if (topslope <= bottomslope)
+ return false; // stop
}
-
// passed the subsector ok
- return true;
+ return true;
}
+
//
// P_CrossBSPNode
// Returns true
// if strace crosses the given node successfully.
//
-boolean P_CrossBSPNode (node_t * bsp)
+boolean P_CrossBSPNode (int bspnum)
{-loop:
- if (bsp->sub != NULL)
- return P_CrossSubsector (bsp->sub);
+ node_t* bsp;
+ int side;
+ if (bspnum & NF_SUBSECTOR)
+ {+ if (bspnum == -1)
+ return P_CrossSubsector (0);
+ else
+ return P_CrossSubsector (bspnum&(~NF_SUBSECTOR));
+ }
+
+ bsp = &nodes[bspnum];
+
// decide which side the start point is on
- divline_t div;
- div.x = bsp->x;
- div.y = bsp->y;
- div.dx = bsp->dx;
- div.dy = bsp->dy;
-
- int side = P_DivlineSide (strace.x, strace.y, &div);
+ side = P_DivlineSide (strace.x, strace.y, (divline_t *)bsp);
if (side == 2)
- side = 0; // an "on" should cross both sides
+ side = 0; // an "on" should cross both sides
// cross the starting side
- if (! P_CrossBSPNode (side ? bsp->left : bsp->right))
- return false;
-
+ if (!P_CrossBSPNode (bsp->children[side]) )
+ return false;
+
// the partition plane is crossed here
- if (side == P_DivlineSide (t2x, t2y, &div))
+ if (side == P_DivlineSide (t2x, t2y,(divline_t *)bsp))
{- // the line doesn't touch the other side
- return true;
+ // the line doesn't touch the other side
+ return true;
}
-
- // cross the ending side
- bsp = side ? bsp->right : bsp->left;
- goto loop;
+
+ // cross the ending side
+ return P_CrossBSPNode (bsp->children[side^1]);
}
@@ -320,7 +344,7 @@
strace.dy = t2->y - t1->y;
// the head node is the last node output
- return P_CrossBSPNode (root_node);
+ return P_CrossBSPNode (numnodes-1);
}
--- a/r_bsp.c
+++ b/r_bsp.c
@@ -492,36 +492,50 @@
// Add sprites of things in sector.
// Draw one or more line segments.
//
-void R_Subsector (subsector_t * sub)
+void R_Subsector (int num)
{+ int count;
+ seg_t* line;
+ subsector_t* sub;
+
+//#ifdef RANGECHECK
+ if (num>=numsubsectors)
+ I_Error ("R_Subsector: ss %i with numss = %i",+ num,
+ numsubsectors);
+//#endif
+
sscount++;
+ sub = &subsectors[num];
frontsector = sub->sector;
+ count = sub->numlines;
+ line = &segs[sub->firstline];
if (frontsector->floorheight < viewz)
{- floorplane = R_FindPlane (frontsector->floorheight,
- frontsector->floorpic,
- frontsector->lightlevel);
+ floorplane = R_FindPlane (frontsector->floorheight,
+ frontsector->floorpic,
+ frontsector->lightlevel);
}
else
- floorplane = NULL;
-
- if (frontsector->ceilingheight > viewz
- || frontsector->ceilingpic == skyflatnum)
+ floorplane = NULL;
+
+ if (frontsector->ceilingheight > viewz
+ || frontsector->ceilingpic == skyflatnum)
{- ceilingplane = R_FindPlane (frontsector->ceilingheight,
- frontsector->ceilingpic,
- frontsector->lightlevel);
+ ceilingplane = R_FindPlane (frontsector->ceilingheight,
+ frontsector->ceilingpic,
+ frontsector->lightlevel);
}
else
- ceilingplane = NULL;
+ ceilingplane = NULL;
+
+ R_AddSprites (frontsector);
- R_AddSprites (frontsector);
-
- seg_t * line;
- for (line = sub->segs ; line != NULL ; line = line->next)
+ while (count--)
{- R_AddLine (line);
+ R_AddLine (line);
+ line++;
}
}
@@ -531,25 +545,32 @@
// Renders all subsectors below a given node,
// traversing subtree recursively.
// Just call with BSP root.
-void R_RenderBSPNode (node_t * bsp)
+void R_RenderBSPNode (int bspnum)
{-loop:
+ node_t* bsp;
+ int side;
+
// Found a subsector?
- if (bsp->sub != NULL)
+ if (bspnum & NF_SUBSECTOR)
{- R_Subsector (bsp->sub);
- return;
+ if (bspnum == -1)
+ R_Subsector (0);
+ else
+ R_Subsector (bspnum&(~NF_SUBSECTOR));
+ return;
}
-
+
+ bsp = &nodes[bspnum];
+
// Decide which side the view point is on.
- int side = R_PointOnSide (viewx, viewy, bsp);
+ side = R_PointOnSide (viewx, viewy, bsp);
// Recursively divide front space.
- R_RenderBSPNode (side ? bsp->left : bsp->right);
+ R_RenderBSPNode (bsp->children[side]);
// Possibly divide back space.
- bsp = side ? bsp->right : bsp->left;
- if (R_CheckBBox (bsp->bbox))
- goto loop;
+ if (R_CheckBBox (bsp->bbox[side^1]))
+ R_RenderBSPNode (bsp->children[side^1]);
}
+
--- a/r_bsp.h
+++ b/r_bsp.h
@@ -55,7 +55,7 @@
void R_ClearDrawSegs (void);
-void R_RenderBSPNode (node_t * bsp);
+void R_RenderBSPNode (int bspnum);
#endif
--- a/r_defs.h
+++ b/r_defs.h
@@ -210,6 +210,23 @@
//
+// A SubSector.
+// References a Sector.
+// Basically, this is a list of LineSegs,
+// indicating the visible walls that define
+// (all or some) sides of a convex BSP leaf.
+//
+typedef struct subsector_s
+{+ sector_t* sector;
+ short numlines;
+ short firstline;
+
+} subsector_t;
+
+
+
+//
// The LineSeg.
//
typedef struct seg_s
@@ -217,9 +234,9 @@
vertex_t* v1;
vertex_t* v2;
- int side;
- fixed_t offset;
- angle_t angle;
+ fixed_t offset;
+ angle_t angle;
+ int side;
side_t* sidedef;
line_t* linedef;
@@ -237,38 +254,24 @@
//
-// A SubSector.
-// References a Sector.
-// Basically, this is a list of LineSegs,
-// indicating the visible walls that define
-// (all or some) sides of a convex BSP leaf.
-//
-typedef struct subsector_s
-{- sector_t * sector;
- seg_t * segs;
-} subsector_t;
-
-
-
-//
// BSP node.
//
-typedef struct node_s
+typedef struct
{- // when non-NULL, this is actually a leaf of the BSP tree
- subsector_t * sub;
+ // Partition line.
+ fixed_t x;
+ fixed_t y;
+ fixed_t dx;
+ fixed_t dy;
- // partition line (start coord, delta to end)
- fixed_t x, y, dx, dy;
+ // Bounding box for each child.
+ fixed_t bbox[2][4];
- // bounding box for this node / leaf
- fixed_t bbox[4];
-
- // right and left children
- struct node_s * right;
- struct node_s * left;
+ // If NF_SUBSECTOR its a subsector.
+ unsigned short children[2];
+
} node_t;
+
--- a/r_main.c
+++ b/r_main.c
@@ -702,17 +702,29 @@
//
// R_PointInSubsector
//
-subsector_t * R_PointInSubsector (fixed_t x, fixed_t y)
+subsector_t*
+R_PointInSubsector
+( fixed_t x,
+ fixed_t y )
{- node_t * node = root_node;
+ node_t* node;
+ int side;
+ int nodenum;
- while (node->sub == NULL)
+ // single subsector is a special case
+ if (!numnodes)
+ return subsectors;
+
+ nodenum = numnodes-1;
+
+ while (! (nodenum & NF_SUBSECTOR) )
{- int side = R_PointOnSide (x, y, node);
- node = side ? node->left : node->right;
+ node = &nodes[nodenum];
+ side = R_PointOnSide (x, y, node);
+ nodenum = node->children[side];
}
-
- return node->sub;
+
+ return &subsectors[nodenum & ~NF_SUBSECTOR];
}
@@ -774,7 +786,7 @@
NetUpdate ();
// The head node is the last node output.
- R_RenderBSPNode (root_node);
+ R_RenderBSPNode (numnodes-1);
// Check for new console commands.
NetUpdate ();
--- a/r_state.h
+++ b/r_state.h
@@ -72,10 +72,17 @@
extern int numvertexes;
extern vertex_t* vertexes;
+extern int numsegs;
+extern seg_t* segs;
+
extern int numsectors;
extern sector_t* sectors;
-extern node_t* root_node;
+extern int numsubsectors;
+extern subsector_t* subsectors;
+
+extern int numnodes;
+extern node_t* nodes;
extern int numlines;
extern line_t* lines;
--
⑨