From 1fa82ae49ae155e5258c0675fb619922281d6439 Mon Sep 17 00:00:00 2001 From: havoc Date: Mon, 21 Mar 2011 06:14:02 +0000 Subject: [PATCH] added mod_collision_bih_childrengrouping cvar (default 16), this accelerates BIH traces by using a shallower tree git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@10954 d7cf8633-e32d-0410-b094-e92efae38249 --- bih.c | 50 ++++++++++++++++++++++++-- bih.h | 16 ++++++--- gl_rsurf.c | 52 +++++++++++++++++++-------- model_brush.c | 99 +++++++++++++++++++++++++++++++++++++++++++++++++-- 4 files changed, 193 insertions(+), 24 deletions(-) diff --git a/bih.c b/bih.c index d5044bff..48a56e42 100644 --- a/bih.c +++ b/bih.c @@ -72,6 +72,19 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *tota 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; @@ -120,7 +133,7 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *tota 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; @@ -132,6 +145,9 @@ int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_nod 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); @@ -150,6 +166,36 @@ static void BIH_GetTriangleListForBox_Node(const bih_t *bih, int nodenum, int ma 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) { @@ -177,7 +223,7 @@ static void BIH_GetTriangleListForBox_Node(const bih_t *bih, int nodenum, int ma if (*numtrianglespointer >= maxtriangles) { ++*numtrianglespointer; // so the caller can detect overflow - return; + break; } if(trianglelist_surf) trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex; diff --git a/bih.h b/bih.h index 810cf9ca..f1af0ef2 100644 --- a/bih.h +++ b/bih.h @@ -6,6 +6,8 @@ #ifndef BIH_H #define BIH_H +#define BIH_MAXUNORDEREDCHILDREN 16 + typedef enum biherror_e { BIHERROR_OK, // no error, be happy @@ -17,15 +19,16 @@ typedef enum bih_nodetype_e { 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; @@ -42,6 +45,8 @@ typedef struct bih_node_s // 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; @@ -73,13 +78,14 @@ typedef struct bih_s // 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); diff --git a/gl_rsurf.c b/gl_rsurf.c index e2827766..4ee874d6 100644 --- a/gl_rsurf.c +++ b/gl_rsurf.c @@ -956,6 +956,9 @@ static void R_Q1BSP_RecursiveGetLightInfo_BIH(r_q1bsp_getlightinfo_t *info, cons int axis; int surfaceindex; int t; + int nodeleafindex; + int nodenumleafs; + const int *nodeleaflist; int currentmaterialflags; qboolean castshadow; msurface_t *surface; @@ -977,30 +980,51 @@ static void R_Q1BSP_RecursiveGetLightInfo_BIH(r_q1bsp_getlightinfo_t *info, cons { // 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 diff --git a/model_brush.c b/model_brush.c index 499a5941..71c55bcc 100644 --- a/model_brush.c +++ b/model_brush.c @@ -52,6 +52,7 @@ cvar_t mod_q3shader_default_polygonoffset = {0, "mod_q3shader_default_polygonoff 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; @@ -87,6 +88,7 @@ void Mod_BrushInit(void) 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)); @@ -5978,6 +5980,31 @@ static void Mod_CollisionBIH_TracePoint_RecursiveBIHNode(trace_t *trace, dp_mode 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) { @@ -5993,6 +6020,10 @@ static void Mod_CollisionBIH_TracePoint_RecursiveBIHNode(trace_t *trace, dp_mode 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: @@ -6042,6 +6073,37 @@ static void Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace_t *trace, dp_model 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) @@ -6325,6 +6387,37 @@ static void Mod_CollisionBIH_TraceBrush_RecursiveBIHNode(trace_t *trace, dp_mode 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)) @@ -7050,7 +7143,7 @@ bih_t *Mod_MakeCollisionBIH(dp_model_t *model, qboolean userendersurfaces, bih_t 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); @@ -7164,7 +7257,7 @@ void Mod_Q3BSP_Load(dp_model_t *mod, void *buffer, void *bufferend) 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; @@ -7463,7 +7556,7 @@ void Mod_OBJ_Load(dp_model_t *mod, void *buffer, void *bufferend) 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; -- 2.39.2