added mod_collision_bih_childrengrouping cvar (default 16), this
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Mon, 21 Mar 2011 06:14:02 +0000 (06:14 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Mon, 21 Mar 2011 06:14:02 +0000 (06:14 +0000)
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
bih.h
gl_rsurf.c
model_brush.c

diff --git a/bih.c b/bih.c
index d5044bf..48a56e4 100644 (file)
--- 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 810cf9c..f1af0ef 100644 (file)
--- 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);
 
index e282776..4ee874d 100644 (file)
@@ -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
index 499a594..71c55bc 100644 (file)
@@ -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;