From 8edf1312167781c2d2ae2334fc110767895ed583 Mon Sep 17 00:00:00 2001
From: havoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Date: Tue, 3 Feb 2004 19:22:06 +0000
Subject: [PATCH] optimized BoxTouchingPVS code to no longer be recursive

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@3868 d7cf8633-e32d-0410-b094-e92efae38249
---
 model_brush.c | 55 +++++++++++++++++++++++++++++++++------------------
 1 file changed, 36 insertions(+), 19 deletions(-)

diff --git a/model_brush.c b/model_brush.c
index 4db80c95..995f0d04 100644
--- 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
-- 
2.39.2