node->maxs[0] = maxs[0];
node->maxs[1] = maxs[1];
node->maxs[2] = maxs[2];
+ node->front = 0;
+ node->back = 0;
+ node->frontmin = 0;
+ node->backmax = 0;
+ memset(node->children, -1, sizeof(node->children));
+ // check if this should be an unordered node to reduce recursion depth
+ if (numchildren <= bih->maxchildrenunordered)
+ {
+ node->type = BIH_UNORDERED;
+ for (j = 0;j < numchildren;j++)
+ node->children[j] = leaflist[j];
+ return nodenum;
+ }
// pick longest axis
longestaxis = 0;
if (size[0] < size[1]) longestaxis = 1;
return nodenum;
}
-int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch)
+int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch, int maxchildrenunordered)
{
int i;
bih->numnodes = 0;
bih->maxnodes = maxnodes;
bih->nodes = nodes;
+ bih->maxchildrenunordered = maxchildrenunordered;
+ if (bih->maxchildrenunordered > BIH_MAXUNORDEREDCHILDREN)
+ bih->maxchildrenunordered = BIH_MAXUNORDEREDCHILDREN;
// clear things we intend to rebuild
memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
while (nodenum >= 0)
{
node = bih->nodes + nodenum;
+ // check if this is an unordered node (which holds an array of leaf numbers)
+ if (node->type == BIH_UNORDERED)
+ {
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = bih->leafs + node->children[axis];
+ if (mins[0] > leaf->maxs[0] || maxs[0] < leaf->mins[0]
+ || mins[1] > leaf->maxs[1] || maxs[1] < leaf->mins[1]
+ || mins[2] > leaf->maxs[2] || maxs[2] < leaf->mins[2])
+ continue;
+ switch(leaf->type)
+ {
+ case BIH_RENDERTRIANGLE:
+ if (*numtrianglespointer >= maxtriangles)
+ {
+ ++*numtrianglespointer; // so the caller can detect overflow
+ break;
+ }
+ if(trianglelist_surf)
+ trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
+ trianglelist_idx[*numtrianglespointer] = leaf->itemindex;
+ ++*numtrianglespointer;
+ break;
+ default:
+ break;
+ }
+ }
+ return;
+ }
+ // splitting node
axis = node->type - BIH_SPLITX;
if (mins[axis] < node->backmax)
{
if (*numtrianglespointer >= maxtriangles)
{
++*numtrianglespointer; // so the caller can detect overflow
- return;
+ break;
}
if(trianglelist_surf)
trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
#ifndef BIH_H
#define BIH_H
+#define BIH_MAXUNORDEREDCHILDREN 16
+
typedef enum biherror_e
{
BIHERROR_OK, // no error, be happy
{
BIH_SPLITX = 0,
BIH_SPLITY = 1,
- BIH_SPLITZ = 2
+ BIH_SPLITZ = 2,
+ BIH_UNORDERED = 3,
}
bih_nodetype_t;
typedef enum bih_leaftype_e
{
- BIH_BRUSH = 3,
- BIH_COLLISIONTRIANGLE = 4,
- BIH_RENDERTRIANGLE = 5
+ BIH_BRUSH = 4,
+ BIH_COLLISIONTRIANGLE = 5,
+ BIH_RENDERTRIANGLE = 6
}
bih_leaftype_t;
// interval of children
float frontmin; // children[0]
float backmax; // children[1]
+ // BIH_UNORDERED uses this for a list of leafindex (positive), -1 = end of list
+ int children[BIH_MAXUNORDEREDCHILDREN];
}
bih_node_t;
// fields used only during BIH_Build:
int maxnodes;
+ int maxchildrenunordered;
int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
int *leafsort;
int *leafsortscratch;
}
bih_t;
-int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch);
+int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch, int maxchildrenunordered);
int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs);
int axis;
int surfaceindex;
int t;
+ int nodeleafindex;
+ int nodenumleafs;
+ const int *nodeleaflist;
int currentmaterialflags;
qboolean castshadow;
msurface_t *surface;
{
// node
node = bih->nodes + nodenum;
- axis = node->type - BIH_SPLITX;
+ if (node->type == BIH_UNORDERED)
+ {
+ nodeleaflist = node->children;
+ for (nodenumleafs = 0;nodenumleafs < BIH_MAXUNORDEREDCHILDREN;nodenumleafs++)
+ if (node->children[nodenumleafs] < 0)
+ break;
+ }
+ else
+ {
+ axis = node->type - BIH_SPLITX;
#if 0
- if (!BoxesOverlap(info->lightmins, info->lightmaxs, node->mins, node->maxs))
- continue;
+ if (!BoxesOverlap(info->lightmins, info->lightmaxs, node->mins, node->maxs))
+ continue;
#endif
#if 0
- if (!r_shadow_compilingrtlight && R_CullBoxCustomPlanes(node->mins, node->maxs, rtlight->cached_numfrustumplanes, rtlight->cached_frustumplanes))
- continue;
+ if (!r_shadow_compilingrtlight && R_CullBoxCustomPlanes(node->mins, node->maxs, rtlight->cached_numfrustumplanes, rtlight->cached_frustumplanes))
+ continue;
#endif
- if (info->lightmins[axis] <= node->backmax)
- {
- if (info->lightmaxs[axis] >= node->frontmin && nodestackpos < GETLIGHTINFO_MAXNODESTACK)
+ if (info->lightmins[axis] <= node->backmax)
+ {
+ if (info->lightmaxs[axis] >= node->frontmin && nodestackpos < GETLIGHTINFO_MAXNODESTACK)
+ nodestack[nodestackpos++] = node->front;
+ nodestack[nodestackpos++] = node->back;
+ continue;
+ }
+ else if (info->lightmaxs[axis] >= node->frontmin)
+ {
nodestack[nodestackpos++] = node->front;
- nodestack[nodestackpos++] = node->back;
+ continue;
+ }
+ else
+ continue; // light falls between children, nothing here
}
- else if (info->lightmaxs[axis] >= node->frontmin)
- nodestack[nodestackpos++] = node->front;
- else
- continue; // light falls between children, nothing here
}
else
{
// leaf
- leaf = bih->leafs + (-1-nodenum);
+ nodenum = -1-nodenum;
+ nodenumleafs = 1;
+ nodeleaflist = &nodenum;
+ }
+
+ for (nodeleafindex = 0;nodeleafindex < nodenumleafs;nodeleafindex++)
+ {
+ leaf = bih->leafs + nodeleaflist[nodeleafindex];
if (leaf->type != BIH_RENDERTRIANGLE)
continue;
#if 1
cvar_t mod_q1bsp_polygoncollisions = {0, "mod_q1bsp_polygoncollisions", "0", "disables use of precomputed cliphulls and instead collides with polygons (uses Bounding Interval Hierarchy optimizations)"};
cvar_t mod_collision_bih = {0, "mod_collision_bih", "1", "enables use of generated Bounding Interval Hierarchy tree instead of compiled bsp tree in collision code"};
+cvar_t mod_collision_bih_childrengrouping = {0, "mod_collision_bih_childrengrouping", "16", "this setting prevents excessive recursion depth in the BIH tree by building a shallow tree"};
cvar_t mod_recalculatenodeboxes = {0, "mod_recalculatenodeboxes", "1", "enables use of generated node bounding boxes based on BSP tree portal reconstruction, rather than the node boxes supplied by the map compiler"};
static texture_t mod_q1bsp_texture_solid;
Cvar_RegisterVariable(&mod_q3shader_default_polygonoffset);
Cvar_RegisterVariable(&mod_q1bsp_polygoncollisions);
Cvar_RegisterVariable(&mod_collision_bih);
+ Cvar_RegisterVariable(&mod_collision_bih_childrengrouping);
Cvar_RegisterVariable(&mod_recalculatenodeboxes);
memset(&mod_q1bsp_texture_solid, 0, sizeof(mod_q1bsp_texture_solid));
while (nodenum >= 0)
{
node = model->collision_bih.nodes + nodenum;
+ if (node->type == BIH_UNORDERED)
+ {
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = model->collision_bih.leafs + node->children[axis];
+#if 1
+ if (!BoxesOverlap(point, point, leaf->mins, leaf->maxs))
+ continue;
+#endif
+ switch(leaf->type)
+ {
+ case BIH_BRUSH:
+ brush = model->brush.data_brushes[leaf->itemindex].colbrushf;
+ Collision_TracePointBrushFloat(trace, point, brush);
+ break;
+ case BIH_COLLISIONTRIANGLE:
+ // collision triangle - skipped because they have no volume
+ break;
+ case BIH_RENDERTRIANGLE:
+ // render triangle - skipped because they have no volume
+ break;
+ }
+ }
+ return;
+ }
axis = node->type - BIH_SPLITX;
if (point[axis] <= node->backmax)
{
if (!model->collision_bih.leafs)
return;
leaf = model->collision_bih.leafs + (-1-nodenum);
+#if 1
+ if (!BoxesOverlap(point, point, leaf->mins, leaf->maxs))
+ return;
+#endif
switch(leaf->type)
{
case BIH_BRUSH:
if (!BoxesOverlap(segmentmins, segmentmaxs, node->mins, node->maxs))
return;
#endif
+ if (node->type == BIH_UNORDERED)
+ {
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = model->collision_bih.leafs + node->children[axis];
+#if 1
+ if (!BoxesOverlap(segmentmins, segmentmaxs, leaf->mins, leaf->maxs))
+ continue;
+#endif
+ switch(leaf->type)
+ {
+ case BIH_BRUSH:
+ brush = model->brush.data_brushes[leaf->itemindex].colbrushf;
+ Collision_TraceLineBrushFloat(trace, linestart, lineend, brush, brush);
+ break;
+ case BIH_COLLISIONTRIANGLE:
+ if (!mod_q3bsp_curves_collisions.integer)
+ continue;
+ e = model->brush.data_collisionelement3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceLineTriangleFloat(trace, linestart, lineend, model->brush.data_collisionvertex3f + e[0] * 3, model->brush.data_collisionvertex3f + e[1] * 3, model->brush.data_collisionvertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ case BIH_RENDERTRIANGLE:
+ e = model->surfmesh.data_element3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceLineTriangleFloat(trace, linestart, lineend, model->surfmesh.data_vertex3f + e[0] * 3, model->surfmesh.data_vertex3f + e[1] * 3, model->surfmesh.data_vertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ }
+ }
+ return;
+ }
axis = node->type - BIH_SPLITX;
#if 0
if (segmentmins[axis] <= node->backmax)
while (nodenum >= 0)
{
node = model->collision_bih.nodes + nodenum;
+ if (node->type == BIH_UNORDERED)
+ {
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = model->collision_bih.leafs + node->children[axis];
+#if 1
+ if (!BoxesOverlap(segmentmins, segmentmaxs, leaf->mins, leaf->maxs))
+ continue;
+#endif
+ switch(leaf->type)
+ {
+ case BIH_BRUSH:
+ brush = model->brush.data_brushes[leaf->itemindex].colbrushf;
+ Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, brush, brush);
+ break;
+ case BIH_COLLISIONTRIANGLE:
+ if (!mod_q3bsp_curves_collisions.integer)
+ continue;
+ e = model->brush.data_collisionelement3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceBrushTriangleFloat(trace, thisbrush_start, thisbrush_end, model->brush.data_collisionvertex3f + e[0] * 3, model->brush.data_collisionvertex3f + e[1] * 3, model->brush.data_collisionvertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ case BIH_RENDERTRIANGLE:
+ e = model->surfmesh.data_element3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceBrushTriangleFloat(trace, thisbrush_start, thisbrush_end, model->surfmesh.data_vertex3f + e[0] * 3, model->surfmesh.data_vertex3f + e[1] * 3, model->surfmesh.data_vertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ }
+ }
+ return;
+ }
axis = node->type - BIH_SPLITX;
#if 1
if (!BoxesOverlap(segmentmins, segmentmaxs, node->mins, node->maxs))
temp_leafsortscratch = temp_leafsort + bihnumleafs;
// now build it
- BIH_Build(out, bihnumleafs, bihleafs, bihmaxnodes, bihnodes, temp_leafsort, temp_leafsortscratch);
+ BIH_Build(out, bihnumleafs, bihleafs, bihmaxnodes, bihnodes, temp_leafsort, temp_leafsortscratch, mod_collision_bih_childrengrouping.integer);
// we're done with the temporary data
Mem_Free(temp_leafsort);
mod->TraceLine = Mod_Q3BSP_TraceLine;
mod->TracePoint = Mod_Q3BSP_TracePoint;
mod->PointSuperContents = Mod_Q3BSP_PointSuperContents;
- mod->TraceLineAgainstSurfaces = Mod_CollisionBIH_TraceLineAgainstSurfaces;
+ mod->TraceLineAgainstSurfaces = Mod_CollisionBIH_TraceLine;
mod->brush.TraceLineOfSight = Mod_Q3BSP_TraceLineOfSight;
mod->brush.SuperContentsFromNativeContents = Mod_Q3BSP_SuperContentsFromNativeContents;
mod->brush.NativeContentsFromSuperContents = Mod_Q3BSP_NativeContentsFromSuperContents;
loadmodel->TraceBrush = Mod_CollisionBIH_TraceBrush;
loadmodel->TraceLine = Mod_CollisionBIH_TraceLine;
loadmodel->TracePoint = Mod_CollisionBIH_TracePoint_Mesh;
- loadmodel->TraceLineAgainstSurfaces = Mod_CollisionBIH_TraceLineAgainstSurfaces;
+ loadmodel->TraceLineAgainstSurfaces = Mod_CollisionBIH_TraceLine;
loadmodel->PointSuperContents = Mod_CollisionBIH_PointSuperContents_Mesh;
loadmodel->brush.TraceLineOfSight = NULL;
loadmodel->brush.SuperContentsFromNativeContents = NULL;
projects / xonotic / darkplaces.git / commitdiff