optimized BoxTouchingPVS code to no longer be recursive

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@3868 d7cf8633-e32d-0410-b094-e92efae38249

diff --git a/model_brush.c b/model_brush.c
index 4db80c951ddfbf77924cbc8e234d92bc10797fbe..995f0d0424535a0b5515a30156d98e260a91904b 100644 (file)
--- a/model_brush.c
+++ b/model_brush.c
@@ -5027,32 +5027,49 @@ static void Mod_Q3BSP_TraceBox(model_t *model, int frame, trace_t *trace, const
        }
 }
 
-
-static int Mod_Q3BSP_BoxTouchingPVS_RecursiveBSPNode(const model_t *model, const q3mnode_t *node, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
+static int Mod_Q3BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
 {
-       int clusterindex, side;
-       while (node->plane)
+       int clusterindex, side, nodestackindex = 0;
+       q3mnode_t *node, *nodestack[1024];
+       node = model->brushq3.data_nodes;
+       for(;;)
        {
-               // node - recurse down the BSP tree
-               side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
-               if (side < 2)
-                       node = node->children[side];
+               if (node->plane)
+               {
+                       // node - recurse down the BSP tree
+                       side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
+                       if (side < 2)
+                       {
+                               // box is on one side of plane, take that path
+                               node = node->children[side];
+                       }
+                       else
+                       {
+                               // box crosses plane, take one path and remember the other
+                               nodestack[nodestackindex++] = node->children[0];
+                               node = node->children[1];
+                       }
+               }
                else
                {
-                       // recurse for one child and loop for the other
-                       if (Mod_Q3BSP_BoxTouchingPVS_RecursiveBSPNode(model, node->children[0], pvs, mins, maxs))
+                       // leaf - check cluster bit
+                       clusterindex = ((q3mleaf_t *)node)->clusterindex;
+                       if (pvs[clusterindex >> 3] & (1 << (clusterindex & 7)))
+                       {
+                               // it is visible, return immediately with the news
                                return true;
-                       node = node->children[1];
+                       }
+                       else
+                       {
+                               // nothing to see here, try another path we didn't take earlier
+                               if (nodestackindex == 0)
+                                       break;
+                               node = nodestack[--nodestackindex];
+                       }
                }
        }
-       // leaf
-       clusterindex = ((q3mleaf_t *)node)->clusterindex;
-       return pvs[clusterindex >> 3] & (1 << (clusterindex & 7));
-}
-
-static int Mod_Q3BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
-{
-       return Mod_Q3BSP_BoxTouchingPVS_RecursiveBSPNode(model, model->brushq3.data_nodes, pvs, mins, maxs);
+       // it is not visible
+       return false;
 }
 
 //Returns PVS data for a given point