Fix a typo in DrawQ_RotPic which broke it badly.

[xonotic/darkplaces.git] / bih.c

diff --git a/bih.c b/bih.c
index fdda1d6d3bb3a20b64003008234723645e3217a7..749cae2d3fcc56635bcb33d41e2dd3f2f201fb3b 100644 (file)
--- 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 Forest Hale (darkplacesengine gmail com), and placed into public domain.

 
 #include <stdlib.h>
 #include <string.h>
 
 #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];
        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;
        // 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;
        }
        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->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;
        // pick longest axis
        longestaxis = 0;
        if (size[0] < size[1]) longestaxis = 1;


@@ -141,3 +151,66 @@ 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;
 }
        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;
+}