From f0b236ba9b71e554bc642d15089a4f25143fd4b0 Mon Sep 17 00:00:00 2001
From: havoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Date: Fri, 4 Nov 2005 12:32:52 +0000
Subject: [PATCH] eliminated use of node bounding box when recursing collision
 traces and lights through the BSP tree, now only uses BoxOnPlaneSide
 approach, with an optimized axial case inlined

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@5787 d7cf8633-e32d-0410-b094-e92efae38249
---
 gl_rsurf.c    | 16 ++++++++++------
 model_brush.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 62 insertions(+), 7 deletions(-)

diff --git a/gl_rsurf.c b/gl_rsurf.c
index c038227c..2591649a 100644
--- a/gl_rsurf.c
+++ b/gl_rsurf.c
@@ -529,18 +529,22 @@ void R_Q1BSP_RecursiveGetLightInfo(r_q1bsp_getlightinfo_t *info, mnode_t *node)
 	mleaf_t *leaf;
 	for (;;)
 	{
-		if (!BoxesOverlap(info->lightmins, info->lightmaxs, node->mins, node->maxs))
-			return;
-		if (!node->plane)
+		mplane_t *plane = node->plane;
+		//if (!BoxesOverlap(info->lightmins, info->lightmaxs, node->mins, node->maxs))
+		//	return;
+		if (!plane)
 			break;
-		sides = BoxOnPlaneSide(info->lightmins, info->lightmaxs, node->plane) - 1;
-		if (sides == 2)
+		if (plane->type < 3)
+			sides = ((info->lightmaxs[plane->type] >= plane->dist) | ((info->lightmins[plane->type] < plane->dist) << 1));
+		else
+			sides = BoxOnPlaneSide(info->lightmins, info->lightmaxs, plane);
+		if (sides == 3)
 		{
 			R_Q1BSP_RecursiveGetLightInfo(info, node->children[0]);
 			node = node->children[1];
 		}
 		else
-			node = node->children[sides];
+			node = node->children[sides - 1];
 	}
 	leaf = (mleaf_t *)node;
 	if (info->pvs == NULL || CHECKPVSBIT(info->pvs, leaf->clusterindex))
diff --git a/model_brush.c b/model_brush.c
index 44512720..cd92bb8c 100644
--- a/model_brush.c
+++ b/model_brush.c
@@ -5091,7 +5091,7 @@ static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, model_t *model,
 static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, model_t *model, mnode_t *node, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
 {
 	int i;
-	//int sides;
+	int sides;
 	float nodesegmentmins[3], nodesegmentmaxs[3];
 	mleaf_t *leaf;
 	colbrushf_t *brush;
@@ -5312,6 +5312,57 @@ static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, model_t *model
 		}
 	*/
 #if 1
+	for (;;)
+	{
+		mplane_t *plane = node->plane;
+		if (!plane)
+			break;
+		// axial planes are much more common than non-axial, so an optimized
+		// axial case pays off here
+		if (plane->type < 3)
+		{
+			// this is an axial plane, compare bounding box directly to it and
+			// recurse sides accordingly
+			// recurse down node sides
+			// use an inlined axial BoxOnPlaneSide to slightly reduce overhead
+			//sides = BoxOnPlaneSide(nodesegmentmins, nodesegmentmaxs, plane);
+			sides = ((segmentmaxs[plane->type] >= plane->dist) | ((segmentmins[plane->type] < plane->dist) << 1));
+			if (sides == 3)
+			{
+				// segment box crosses plane
+				Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+				sides = 2;
+			}
+		}
+		else
+		{
+			// this is a non-axial plane, entire trace bounding box
+			// comparisons against it are likely to be very sloppy, so in if
+			// the whole box is split by the plane we then test the start/end
+			// boxes against it to be sure
+			sides = BoxOnPlaneSide(segmentmins, segmentmaxs, plane);
+			if (sides == 3)
+			{
+				// segment box crosses plane
+				// now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
+				sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, plane);
+				if (sides == 3)
+				{
+					Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+					sides = 2;
+				}
+			}
+		}
+		// take whichever side the segment box is on
+		node = node->children[sides - 1];
+	}
+	nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
+	nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
+	nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
+	nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
+	nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
+	nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
+#elif 1
 	for (;;)
 	{
 		nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
-- 
2.39.2