X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=bih.c;h=d5044bff43bfa765df10e6101c77c2606d176af4;hb=2e7cb61671ac916469ea6b800eb585b8f7f2c762;hp=8797d20dcfcde1bcb587f949cba18a79457ebf2d;hpb=9e106b76f1968d3c64a67c0073f7c42332a3ef97;p=xonotic%2Fdarkplaces.git

diff --git a/bih.c b/bih.c
index 8797d20d..d5044bff 100644
--- a/bih.c
+++ b/bih.c
@@ -2,7 +2,7 @@
 // This code written in 2010 by Forest Hale (lordhavoc ghdigital 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, float *totalmins, float *totalmaxs)
@@ -10,10 +10,10 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *tota
 	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;
@@ -112,7 +112,7 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *tota
 	}
 
 	// we now have front and back children divided in leaflist...
-	node->type = BIH_SPLITX + axis;
+	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);
@@ -141,3 +141,57 @@ int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_nod
 	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;
+	while (nodenum >= 0)
+	{
+		node = bih->nodes + nodenum;
+		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;
+	}
+	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)
+		{
+			++*numtrianglespointer; // so the caller can detect overflow
+			return;
+		}
+		if(trianglelist_surf)
+			trianglelist_surf[*numtrianglespointer] = leaf->surfaceindex;
+		trianglelist_idx[*numtrianglespointer] = leaf->itemindex;
+		++*numtrianglespointer;
+		break;
+	default:
+		break;
+	}
+}
+
+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_idx, trianglelist_surf, &numtriangles, mins, maxs);
+	return numtriangles;
+}