X-Git-Url: http://git.xonotic.org/?a=blobdiff_plain;f=bih.c;h=8f631623aa4726d35a4171bb6317e262816a5cbf;hb=5297b46dcb238b0e738e2bad7ea5b34413d361a8;hp=58cc0715e049df6c54ff4d2a7f60b8db0aebe633;hpb=3af0b7fb7378c916612c11f76e5880164497a0d1;p=xonotic%2Fdarkplaces.git

diff --git a/bih.c b/bih.c
index 58cc0715..8f631623 100644
--- a/bih.c
+++ b/bih.c
@@ -1,5 +1,5 @@
 
-// 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 <string.h>
@@ -53,15 +53,12 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *tota
 	totalmaxs[0] = maxs[0];
 	totalmaxs[1] = maxs[1];
 	totalmaxs[2] = maxs[2];
-	// if there is only one child this is a leaf
-	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];
+		return 0;
 	}
 	nodenum = bih->numnodes++;
 	node = bih->nodes + nodenum;
@@ -72,6 +69,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 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;
@@ -142,19 +152,49 @@ int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_nod
 	return bih->error;
 }
 
-static void BIH_GetTriangleListForBox_Node(const bih_t *bih, int nodenum, int maxtriangles, int *trianglelist, int *numtrianglespointer, const float *mins, const float *maxs)
+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;
-	while (nodenum >= 0)
+	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, numtrianglespointer, mins, maxs);
+				BIH_GetTriangleListForBox_Node(bih, node->front, maxtriangles, trianglelist_idx, trianglelist_surf, numtrianglespointer, mins, maxs);
 			nodenum = node->back;
 			continue;
 		}
@@ -166,26 +206,11 @@ static void BIH_GetTriangleListForBox_Node(const bih_t *bih, int nodenum, int ma
 		// fell between the child groups, nothing here
 		return;
 	}
-	leaf = bih->leafs + (-1-nodenum);
-	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])
-		return;
-	switch(leaf->type)
-	{
-	case BIH_RENDERTRIANGLE:
-		if (*numtrianglespointer >= maxtriangles)
-			return;
-		trianglelist[(*numtrianglespointer)++] = leaf->itemindex;
-		break;
-	default:
-		break;
-	}
 }
 
-int BIH_GetTriangleListForBox(const bih_t *bih, int maxtriangles, int *trianglelist, const float *mins, const float *maxs)
+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, 0, maxtriangles, trianglelist, &numtriangles, mins, maxs);
+	BIH_GetTriangleListForBox_Node(bih, bih->rootnode, maxtriangles, trianglelist_idx, trianglelist_surf, &numtriangles, mins, maxs);
 	return numtriangles;
 }