X-Git-Url: https://git.xonotic.org/?a=blobdiff_plain;f=bih.c;h=8f631623aa4726d35a4171bb6317e262816a5cbf;hb=refs%2Fheads%2Fbones_was_here%2Fnet_s4;hp=caf6e7e195e7e808b837f9deabb9b2f2c077ae8d;hpb=8c4a05a0e34eb4c21be65315d58841c0f8268197;p=xonotic%2Fdarkplaces.git

diff --git a/bih.c b/bih.c
index caf6e7e1..8f631623 100644
--- a/bih.c
+++ b/bih.c
@@ -1,19 +1,19 @@
 
-// This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
+// This code written in 2010 by Ashley Rose Hale (LadyHavoc) (darkplacesengine gmail com), and placed into public domain.
 
 #include <stdlib.h>
-#include <memory.h>
+#include <string.h>
 #include "bih.h"
 
-static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
+static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *totalmins, float *totalmaxs)
 {
 	int i;
 	int j;
 	int longestaxis;
-	int axis;
+	int axis = 0;
 	int nodenum;
-	int front;
-	int back;
+	int front = 0;
+	int back = 0;
 	bih_node_t *node;
 	bih_leaf_t *child;
 	float splitdist;
@@ -21,17 +21,10 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
 	float mins[3];
 	float maxs[3];
 	float size[3];
-	if (numchildren < 2)
-		return -1-leaflist[0];
-	// if we run out of nodes it's the caller's fault, but don't crash
-	if (bih->numnodes == bih->maxnodes)
-	{
-		if (!bih->error)
-			bih->error = BIHERROR_OUT_OF_NODES;
-		return -1-leaflist[0];
-	}
-	nodenum = bih->numnodes++;
-	node = bih->nodes + nodenum;
+	float frontmins[3];
+	float frontmaxs[3];
+	float backmins[3];
+	float backmaxs[3];
 	// calculate bounds of children
 	child = bih->leafs + leaflist[0];
 	mins[0] = child->mins[0];
@@ -53,6 +46,22 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
 	size[0] = maxs[0] - mins[0];
 	size[1] = maxs[1] - mins[1];
 	size[2] = maxs[2] - mins[2];
+	// provide bounds to caller
+	totalmins[0] = mins[0];
+	totalmins[1] = mins[1];
+	totalmins[2] = mins[2];
+	totalmaxs[0] = maxs[0];
+	totalmaxs[1] = maxs[1];
+	totalmaxs[2] = maxs[2];
+	// if we run out of nodes it's the caller's fault, but don't crash
+	if (bih->numnodes == bih->maxnodes)
+	{
+		if (!bih->error)
+			bih->error = BIHERROR_OUT_OF_NODES;
+		return 0;
+	}
+	nodenum = bih->numnodes++;
+	node = bih->nodes + nodenum;
 	// store bounds for node
 	node->mins[0] = mins[0];
 	node->mins[1] = mins[1];
@@ -60,29 +69,31 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
 	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 there are few enough children to store an unordered node
+	if (numchildren <= BIH_MAXUNORDEREDCHILDREN)
+	{
+		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;
 	if (size[longestaxis] < size[2]) longestaxis = 2;
-	// iterate possible split axis choices:
-	// longest (best raytracing performance)
-	// x (longest had identical children, try X axis)
-	// y (longest and X axis had identical children, try Y axis)
-	// z (longest and X and Y axes had identical children, try Z axis)
-	// arbitrary (all children have same bounds, divide the list)
+	// iterate possible split axis choices, starting with the longest axis, if
+	// all fail it means all children have the same bounds and we simply split
+	// the list in half because each node can only have two children.
 	for (j = 0;j < 3;j++)
 	{
-		// if longest axis fails, we try each one until something works
-		// (this also can fail, see below)
-		switch(j)
-		{
-		default:
-		case 0: axis = longestaxis;break;
-		case 1: axis = (longestaxis + 1) % 3;break;
-		case 2: axis = (longestaxis + 2) % 3;break;
-		}
+		// pick an axis
+		axis = (longestaxis + j) % 3;
 		// sort children into front and back lists
-		node->type = BIH_SPLITX + axis;
 		splitdist = (node->mins[axis] + node->maxs[axis]) * 0.5f;
 		front = 0;
 		back = 0;
@@ -104,16 +115,18 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
 	}
 	if (j == 3)
 	{
-		// the almost impossible case happened; all children have identical
-		// bounds, so just divide them arbitrarily into two lists.
-		node->type = BIH_SPLITX;
+		// somewhat common case: no good choice, divide children arbitrarily
+		axis = 0;
 		back = numchildren >> 1;
 		front = numchildren - back;
 	}
 
 	// we now have front and back children divided in leaflist...
-	node->children[0] = BIH_BuildNode(bih, front, leaflist);
-	node->children[1] = BIH_BuildNode(bih, back, leaflist + front);
+	node->type = (bih_nodetype_t)((int)BIH_SPLITX + axis);
+	node->front = BIH_BuildNode(bih, front, leaflist, frontmins, frontmaxs);
+	node->frontmin = frontmins[axis];
+	node->back = BIH_BuildNode(bih, back, leaflist + front, backmins, backmaxs);
+	node->backmax = backmaxs[axis];
 	return nodenum;
 }
 
@@ -135,6 +148,69 @@ int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_nod
 	for (i = 0;i < bih->numleafs;i++)
 		bih->leafsort[i] = i;
 
-	BIH_BuildNode(bih, bih->numleafs, bih->leafsort);
+	bih->rootnode = BIH_BuildNode(bih, bih->numleafs, bih->leafsort, bih->mins, bih->maxs);
 	return bih->error;
 }
+
+static void BIH_GetTriangleListForBox_Node(const bih_t *bih, int nodenum, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, int *numtrianglespointer, const float *mins, const float *maxs)
+{
+	int axis;
+	bih_node_t *node;
+	bih_leaf_t *leaf;
+	for(;;)
+	{
+		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)
+		{
+			if (maxs[axis] > node->frontmin)
+				BIH_GetTriangleListForBox_Node(bih, node->front, maxtriangles, trianglelist_idx, trianglelist_surf, numtrianglespointer, mins, maxs);
+			nodenum = node->back;
+			continue;
+		}
+		if (maxs[axis] > node->frontmin)
+		{
+			nodenum = node->front;
+			continue;
+		}
+		// fell between the child groups, nothing here
+		return;
+	}
+}
+
+int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist_idx, int *trianglelist_surf, const float *mins, const float *maxs)
+{
+	int numtriangles = 0;
+	BIH_GetTriangleListForBox_Node(bih, bih->rootnode, maxtriangles, trianglelist_idx, trianglelist_surf, &numtriangles, mins, maxs);
+	return numtriangles;
+}