implementing Bounding Interval Hierarchy collision culling trees for

q3bsp, not used yet

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@9957 d7cf8633-e32d-0410-b094-e92efae38249

diff --git a/bih.c b/bih.c
new file mode 100644 (file)
index 0000000..caf6e7e
--- /dev/null
+++ b/bih.c
@@ -0,0 +1,140 @@
+
+// This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
+
+#include <stdlib.h>
+#include <memory.h>
+#include "bih.h"
+
+static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist)
+{
+       int i;
+       int j;
+       int longestaxis;
+       int axis;
+       int nodenum;
+       int front;
+       int back;
+       bih_node_t *node;
+       bih_leaf_t *child;
+       float splitdist;
+       float d;
+       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;
+       // calculate bounds of children
+       child = bih->leafs + leaflist[0];
+       mins[0] = child->mins[0];
+       mins[1] = child->mins[1];
+       mins[2] = child->mins[2];
+       maxs[0] = child->maxs[0];
+       maxs[1] = child->maxs[1];
+       maxs[2] = child->maxs[2];
+       for (i = 1;i < numchildren;i++)
+       {
+               child = bih->leafs + leaflist[i];
+               if (mins[0] > child->mins[0]) mins[0] = child->mins[0];
+               if (mins[1] > child->mins[1]) mins[1] = child->mins[1];
+               if (mins[2] > child->mins[2]) mins[2] = child->mins[2];
+               if (maxs[0] < child->maxs[0]) maxs[0] = child->maxs[0];
+               if (maxs[1] < child->maxs[1]) maxs[1] = child->maxs[1];
+               if (maxs[2] < child->maxs[2]) maxs[2] = child->maxs[2];
+       }
+       size[0] = maxs[0] - mins[0];
+       size[1] = maxs[1] - mins[1];
+       size[2] = maxs[2] - mins[2];
+       // store bounds for node
+       node->mins[0] = mins[0];
+       node->mins[1] = mins[1];
+       node->mins[2] = mins[2];
+       node->maxs[0] = maxs[0];
+       node->maxs[1] = maxs[1];
+       node->maxs[2] = maxs[2];
+       // 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)
+       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;
+               }
+               // 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;
+               for (i = 0;i < numchildren;i++)
+               {
+                       child = bih->leafs + leaflist[i];
+                       d = (child->mins[axis] + child->maxs[axis]) * 0.5f;
+                       if (d < splitdist)
+                               bih->leafsortscratch[back++] = leaflist[i];
+                       else
+                               leaflist[front++] = leaflist[i];
+               }
+               // now copy the back ones into the space made in the leaflist for them
+               if (back)
+                       memcpy(leaflist + front, bih->leafsortscratch, back*sizeof(leaflist[0]));
+               // if both sides have some children, it's good enough for us.
+               if (front && back)
+                       break;
+       }
+       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;
+               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);
+       return nodenum;
+}
+
+int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch)
+{
+       int i;
+
+       memset(bih, 0, sizeof(*bih));
+       bih->numleafs = numleafs;
+       bih->leafs = leafs;
+       bih->leafsort = temp_leafsort;
+       bih->leafsortscratch = temp_leafsortscratch;
+       bih->numnodes = 0;
+       bih->maxnodes = maxnodes;
+       bih->nodes = nodes;
+
+       // clear things we intend to rebuild
+       memset(bih->nodes, 0, sizeof(bih->nodes[0]) * bih->maxnodes);
+       for (i = 0;i < bih->numleafs;i++)
+               bih->leafsort[i] = i;
+
+       BIH_BuildNode(bih, bih->numleafs, bih->leafsort);
+       return bih->error;
+}

diff --git a/bih.h b/bih.h
new file mode 100644 (file)
index 0000000..7a98045
--- /dev/null
+++ b/bih.h
@@ -0,0 +1,68 @@
+
+// This code written in 2010 by Forest Hale (lordhavoc ghdigital com), and placed into public domain.
+
+// Based on information in http://zach.in.tu-clausthal.de/papers/vrst02.html (in particular vrst02_boxtree.pdf)
+
+#ifndef BIH_H
+#define BIH_H
+
+typedef enum biherror_e
+{
+       BIHERROR_OK, // no error, be happy
+       BIHERROR_OUT_OF_NODES, // could not produce complete hierarchy, maxnodes too low (should be roughly half of numleafs)
+}
+biherror_t;
+
+typedef enum bih_nodetype_e
+{
+       BIH_SPLITX = 0,
+       BIH_SPLITY = 1,
+       BIH_SPLITZ = 2,
+       BIH_LEAF = 3,
+}
+bih_nodetype_t;
+
+typedef struct bih_node_s
+{
+       bih_nodetype_t type; // = BIH_SPLITX and similar values
+       // TODO: store just one float for distance, and have BIH_SPLITMINX and BIH_SPLITMAXX distinctions, to reduce memory footprint and traversal time, as described in the paper (vrst02_boxtree.pdf)
+       // TODO: move bounds data to parent node and remove it from leafs?
+       float mins[3];
+       float maxs[3];
+       // < 0 is a leaf index (-1-leafindex), >= 0 is another node index (always >= this node's index)
+       int children[2];
+}
+bih_node_t;
+
+typedef struct bih_leaf_s
+{
+       bih_nodetype_t type; // = BIH_LEAF
+       float mins[3];
+       float maxs[3];
+       // data past this point is generic and entirely up to the caller...
+       int textureindex;
+       int itemindex; // triangle or brush index
+}
+bih_leaf_t;
+
+typedef struct bih_s
+{
+       // permanent fields
+       // leafs are constructed by caller before calling BIH_Build
+       int numleafs;
+       bih_leaf_t *leafs;
+       // nodes are constructed by BIH_Build
+       int numnodes;
+       bih_node_t *nodes;
+
+       // fields used only during BIH_Build:
+       int maxnodes;
+       int error; // set to a value if an error occurs in building (such as numnodes == maxnodes)
+       int *leafsort;
+       int *leafsortscratch;
+}
+bih_t;
+
+int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_node_t *nodes, int *temp_leafsort, int *temp_leafsortscratch);
+
+#endif

diff --git a/gl_rmain.c b/gl_rmain.c
index c2f1a1cf07dfd179fc0e2af1e3a5f1186da87f7b..ad45995203bcd52b8f4fef2043104670d3137ab1 100644 (file)
--- a/gl_rmain.c
+++ b/gl_rmain.c
@@ -12113,7 +12113,6 @@ void R_DrawDebugModel(void)
 {
        entity_render_t *ent = rsurface.entity;
        int i, j, k, l, flagsmask;
-       q3mbrush_t *brush;
        const msurface_t *surface;
        dp_model_t *model = ent->model;
        vec3_t v;
@@ -12128,25 +12127,43 @@ void R_DrawDebugModel(void)
        GL_DepthMask(false);
        GL_BlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 
-       if (r_showcollisionbrushes.value > 0 && model->brush.num_brushes)
+       if (r_showcollisionbrushes.value > 0 && model->collision_bih.numleafs)
        {
+               int triangleindex;
+               int bihleafindex;
+               qboolean cullbox = ent == r_refdef.scene.worldentity;
+               const q3mbrush_t *brush;
+               const bih_t *bih = &model->collision_bih;
+               const bih_leaf_t *bihleaf;
+               float vertex3f[3][3];
                GL_PolygonOffset(r_refdef.polygonfactor + r_showcollisionbrushes_polygonfactor.value, r_refdef.polygonoffset + r_showcollisionbrushes_polygonoffset.value);
-               for (i = 0, brush = model->brush.data_brushes + model->firstmodelbrush;i < model->nummodelbrushes;i++, brush++)
+               for (bihleafindex = 0, bihleaf = bih->leafs;bihleafindex < bih->numleafs;bihleafindex++, bihleaf++)
                {
-                       if (brush->colbrushf && brush->colbrushf->numtriangles)
-                       {
-                               R_Mesh_VertexPointer(brush->colbrushf->points->v, 0, 0);
-                               GL_Color((i & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((i >> 5) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((i >> 10) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, r_showcollisionbrushes.value);
-                               R_Mesh_Draw(0, brush->colbrushf->numpoints, 0, brush->colbrushf->numtriangles, brush->colbrushf->elements, NULL, 0, 0);
-                       }
-               }
-               for (i = 0, surface = model->data_surfaces + model->firstmodelsurface;i < model->nummodelsurfaces;i++, surface++)
-               {
-                       if (surface->num_collisiontriangles)
+                       if (cullbox && R_CullBox(bihleaf->mins, bihleaf->maxs))
+                               continue;
+                       switch (bihleaf->type)
                        {
-                               R_Mesh_VertexPointer(surface->data_collisionvertex3f, 0, 0);
-                               GL_Color((i & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((i >> 5) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((i >> 10) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, r_showcollisionbrushes.value);
-                               R_Mesh_Draw(0, surface->num_collisionvertices, 0, surface->num_collisiontriangles, surface->data_collisionelement3i, NULL, 0, 0);
+                       case BIH_LEAF:
+                               // brush
+                               brush = model->brush.data_brushes + bihleaf->itemindex;
+                               if (brush->colbrushf && brush->colbrushf->numtriangles)
+                               {
+                                       GL_Color((bihleafindex & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((bihleafindex >> 5) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((bihleafindex >> 10) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, r_showcollisionbrushes.value);
+                                       R_Mesh_Draw(0, brush->colbrushf->numpoints, 0, brush->colbrushf->numtriangles, brush->colbrushf->elements, NULL, 0, 0);
+                               }
+                               break;
+                       case BIH_LEAF + 1:
+                               // triangle
+                               triangleindex = bihleaf->itemindex;
+                               VectorCopy(model->brush.data_collisionvertex3f + 3*model->brush.data_collisionelement3i[triangleindex*3+0], vertex3f[0]);
+                               VectorCopy(model->brush.data_collisionvertex3f + 3*model->brush.data_collisionelement3i[triangleindex*3+1], vertex3f[1]);
+                               VectorCopy(model->brush.data_collisionvertex3f + 3*model->brush.data_collisionelement3i[triangleindex*3+2], vertex3f[2]);
+                               R_Mesh_VertexPointer(vertex3f[0], 0, 0);
+                               GL_Color((bihleafindex & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((bihleafindex >> 5) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, ((bihleafindex >> 10) & 31) * (1.0f / 32.0f) * r_refdef.view.colorscale, r_showcollisionbrushes.value);
+                               R_Mesh_Draw(0, 3, 0, 1, polygonelement3i, polygonelement3s, 0, 0);
+                               break;
+                       default:
+                               break;
                        }
                }
        }

diff --git a/makefile.inc b/makefile.inc
index 22478d5d89ce1f731cd90b50f623084ba10011f9..1c3412023cfa89be357d6b6d795db9b0600569b1 100644 (file)
--- a/makefile.inc
+++ b/makefile.inc
@@ -88,6 +88,7 @@ OBJ_NOCD=cd_null.o
 
 # Common objects
 OBJ_COMMON= \
+       bih.o \
        cap_avi.o \
        cap_ogg.o \
        cd_shared.o \

diff --git a/model_brush.c b/model_brush.c
index 8aa9c0634635a5eac138456c80ba999504ff6cf5..dff011ed1678c567c794fd612d6f04d8e02c0ce0 100644 (file)
--- a/model_brush.c
+++ b/model_brush.c
@@ -522,17 +522,17 @@ static void Mod_Q1BSP_FindNonSolidLocation_r_Leaf(findnonsolidlocationinfo_t *in
                surface = info->model->data_surfaces + *mark;
                if (surface->texture->supercontents & SUPERCONTENTS_SOLID)
                {
-                       if(surface->num_bboxstride > 0)
+                       if(surface->deprecatedq3num_bboxstride > 0)
                        {
                                int i, cnt, tri;
-                               cnt = (surface->num_triangles + surface->num_bboxstride - 1) / surface->num_bboxstride;
+                               cnt = (surface->num_triangles + surface->deprecatedq3num_bboxstride - 1) / surface->deprecatedq3num_bboxstride;
                                for(i = 0; i < cnt; ++i)
                                {
-                                       if(BoxesOverlap(surface->data_bbox6f + i * 6, surface->data_bbox6f + i * 6 + 3, info->absmin, info->absmax))
+                                       if(BoxesOverlap(surface->deprecatedq3data_bbox6f + i * 6, surface->deprecatedq3data_bbox6f + i * 6 + 3, info->absmin, info->absmax))
                                        {
-                                               for(k = 0; k < surface->num_bboxstride; ++k)
+                                               for(k = 0; k < surface->deprecatedq3num_bboxstride; ++k)
                                                {
-                                                       tri = i * surface->num_bboxstride + k;
+                                                       tri = i * surface->deprecatedq3num_bboxstride + k;
                                                        if(tri >= surface->num_triangles)
                                                                break;
                                                        Mod_Q1BSP_FindNonSolidLocation_r_Triangle(info, surface, tri);
@@ -4797,7 +4797,7 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
 {
        q3dface_t *in, *oldin;
        msurface_t *out, *oldout;
-       int i, oldi, j, n, count, invalidelements, patchsize[2], finalwidth, finalheight, xtess, ytess, finalvertices, finaltriangles, firstvertex, firstelement, type, oldnumtriangles, oldnumtriangles2, meshvertices, meshtriangles, numvertices, numtriangles, cxtess, cytess;
+       int i, oldi, j, n, count, invalidelements, patchsize[2], finalwidth, finalheight, xtess, ytess, finalvertices, finaltriangles, firstvertex, firstelement, type, oldnumtriangles, oldnumtriangles2, meshvertices, meshtriangles, collisionvertices, collisiontriangles, numvertices, numtriangles, cxtess, cytess;
        float lightmaptcbase[2], lightmaptcscale[2];
        //int *originalelement3i;
        //int *originalneighbor3i;
@@ -4808,6 +4808,8 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
        float *originalcolor4f;
        float *originaltexcoordtexture2f;
        float *originaltexcoordlightmap2f;
+       float *surfacecollisionvertex3f;
+       int *surfacecollisionelement3i;
        float *v;
        patchtess_t *patchtess = NULL;
        int patchtesscount = 0;
@@ -4989,6 +4991,8 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
        while (again);
 
        // Calculate resulting number of triangles
+       collisionvertices = 0;
+       collisiontriangles = 0;
        for(i = 0; i < patchtesscount; ++i)
        {
                finalwidth = Q3PatchDimForTess(patchtess[i].info.xsize, patchtess[i].info.lods[PATCH_LOD_VISUAL].xtess);
@@ -5000,14 +5004,31 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
                oldout[patchtess[i].surface_id].num_triangles = numtriangles;
                meshvertices += oldout[patchtess[i].surface_id].num_vertices;
                meshtriangles += oldout[patchtess[i].surface_id].num_triangles;
+
+               finalwidth = Q3PatchDimForTess(patchtess[i].info.xsize, patchtess[i].info.lods[PATCH_LOD_COLLISION].xtess);
+               finalheight = Q3PatchDimForTess(patchtess[i].info.ysize,patchtess[i].info.lods[PATCH_LOD_COLLISION].ytess);
+               numvertices = finalwidth * finalheight;
+               numtriangles = (finalwidth - 1) * (finalheight - 1) * 2;
+
+               oldout[patchtess[i].surface_id].num_collisionvertices = numvertices;
+               oldout[patchtess[i].surface_id].num_collisiontriangles = numtriangles;
+               collisionvertices += oldout[patchtess[i].surface_id].num_collisionvertices;
+               collisiontriangles += oldout[patchtess[i].surface_id].num_collisiontriangles;
        }
 
        i = oldi;
        in = oldin;
        out = oldout;
        Mod_AllocSurfMesh(loadmodel->mempool, meshvertices, meshtriangles, false, true, false);
+       if (collisiontriangles)
+       {
+               loadmodel->brush.data_collisionvertex3f = Mem_Alloc(loadmodel->mempool, collisionvertices * sizeof(float[3]));
+               loadmodel->brush.data_collisionelement3i = Mem_Alloc(loadmodel->mempool, collisiontriangles * sizeof(int[3]));
+       }
        meshvertices = 0;
        meshtriangles = 0;
+       collisionvertices = 0;
+       collisiontriangles = 0;
        for (;i < count && meshvertices + out->num_vertices <= loadmodel->surfmesh.num_vertices;i++, in++, out++)
        {
                if (out->num_vertices < 3 || out->num_triangles < 1)
@@ -5018,6 +5039,7 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
                firstelement = LittleLong(in->firstelement);
                out->num_firstvertex = meshvertices;
                out->num_firsttriangle = meshtriangles;
+               out->num_firstcollisiontriangle = collisiontriangles;
                switch(type)
                {
                case Q3FACETYPE_FLAT:
@@ -5098,26 +5120,40 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
                        finalvertices = finalwidth * finalheight;
                        finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
 
-                       out->data_collisionvertex3f = (float *)Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * finalvertices);
-                       out->data_collisionelement3i = (int *)Mem_Alloc(loadmodel->mempool, sizeof(int[3]) * finaltriangles);
+                       // legacy collision geometry implementation
+                       out->deprecatedq3data_collisionvertex3f = (float *)Mem_Alloc(loadmodel->mempool, sizeof(float[3]) * finalvertices);
+                       out->deprecatedq3data_collisionelement3i = (int *)Mem_Alloc(loadmodel->mempool, sizeof(int[3]) * finaltriangles);
                        out->num_collisionvertices = finalvertices;
                        out->num_collisiontriangles = finaltriangles;
-                       Q3PatchTesselateFloat(3, sizeof(float[3]), out->data_collisionvertex3f, patchsize[0], patchsize[1], sizeof(float[3]), originalvertex3f, cxtess, cytess);
-                       Q3PatchTriangleElements(out->data_collisionelement3i, finalwidth, finalheight, 0);
+                       Q3PatchTesselateFloat(3, sizeof(float[3]), out->deprecatedq3data_collisionvertex3f, patchsize[0], patchsize[1], sizeof(float[3]), originalvertex3f, cxtess, cytess);
+                       Q3PatchTriangleElements(out->deprecatedq3data_collisionelement3i, finalwidth, finalheight, 0);
 
                        //Mod_SnapVertices(3, out->num_vertices, (loadmodel->surfmesh.data_vertex3f + 3 * out->num_firstvertex), 0.25);
-                       Mod_SnapVertices(3, out->num_collisionvertices, out->data_collisionvertex3f, 1);
+                       Mod_SnapVertices(3, out->num_collisionvertices, out->deprecatedq3data_collisionvertex3f, 1);
 
                        oldnumtriangles = out->num_triangles;
                        oldnumtriangles2 = out->num_collisiontriangles;
-                       out->num_collisiontriangles = Mod_RemoveDegenerateTriangles(out->num_collisiontriangles, out->data_collisionelement3i, out->data_collisionelement3i, out->data_collisionvertex3f);
+                       out->num_collisiontriangles = Mod_RemoveDegenerateTriangles(out->num_collisiontriangles, out->deprecatedq3data_collisionelement3i, out->deprecatedq3data_collisionelement3i, out->deprecatedq3data_collisionvertex3f);
 
                        // now optimize the collision mesh by finding triangle bboxes...
-                       Mod_Q3BSP_BuildBBoxes(out->data_collisionelement3i, out->num_collisiontriangles, out->data_collisionvertex3f, &out->data_collisionbbox6f, &out->num_collisionbboxstride, mod_q3bsp_curves_collisions_stride.integer);
-                       Mod_Q3BSP_BuildBBoxes(loadmodel->surfmesh.data_element3i + 3 * out->num_firsttriangle, out->num_triangles, loadmodel->surfmesh.data_vertex3f, &out->data_bbox6f, &out->num_bboxstride, mod_q3bsp_curves_stride.integer);
+                       Mod_Q3BSP_BuildBBoxes(out->deprecatedq3data_collisionelement3i, out->num_collisiontriangles, out->deprecatedq3data_collisionvertex3f, &out->deprecatedq3data_collisionbbox6f, &out->deprecatedq3num_collisionbboxstride, mod_q3bsp_curves_collisions_stride.integer);
+                       Mod_Q3BSP_BuildBBoxes(loadmodel->surfmesh.data_element3i + 3 * out->num_firsttriangle, out->num_triangles, loadmodel->surfmesh.data_vertex3f, &out->deprecatedq3data_bbox6f, &out->deprecatedq3num_bboxstride, mod_q3bsp_curves_stride.integer);
+
+                       // store collision geometry for BIH collision tree
+                       surfacecollisionvertex3f = loadmodel->brush.data_collisionvertex3f + collisionvertices * 3;
+                       surfacecollisionelement3i = loadmodel->brush.data_collisionelement3i + collisiontriangles * 3;
+                       Q3PatchTesselateFloat(3, sizeof(float[3]), surfacecollisionvertex3f, patchsize[0], patchsize[1], sizeof(float[3]), originalvertex3f, cxtess, cytess);
+                       Q3PatchTriangleElements(surfacecollisionelement3i, finalwidth, finalheight, collisionvertices);
+                       Mod_SnapVertices(3, finalvertices, surfacecollisionvertex3f, 1);
+                       oldnumtriangles = out->num_triangles;
+                       oldnumtriangles2 = out->num_collisiontriangles;
+                       out->num_collisiontriangles = Mod_RemoveDegenerateTriangles(out->num_collisiontriangles, surfacecollisionelement3i, surfacecollisionelement3i, loadmodel->brush.data_collisionvertex3f);
 
                        if (developer_extra.integer)
                                Con_DPrintf("Mod_Q3BSP_LoadFaces: %ix%i curve became %i:%i vertices / %i:%i triangles (%i:%i degenerate)\n", patchsize[0], patchsize[1], out->num_vertices, out->num_collisionvertices, oldnumtriangles, oldnumtriangles2, oldnumtriangles - out->num_triangles, oldnumtriangles2 - out->num_collisiontriangles);
+
+                       collisionvertices += finalvertices;
+                       collisiontriangles += out->num_collisiontriangles;
                        break;
                default:
                        break;
@@ -5727,10 +5763,10 @@ static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, dp_model_t *mod
                for (i = 0;i < leaf->numleafsurfaces;i++)
                {
                        surface = model->data_surfaces + leaf->firstleafsurface[i];
-                       if (surface->num_collisiontriangles && surface->collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, surface->mins, surface->maxs))
+                       if (surface->num_collisiontriangles && surface->deprecatedq3collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, surface->mins, surface->maxs))
                        {
-                               surface->collisionmarkframe = markframe;
-                               Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionbboxstride, surface->data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
+                               surface->deprecatedq3collisionmarkframe = markframe;
+                               Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, surface->num_collisiontriangles, surface->deprecatedq3data_collisionelement3i, surface->deprecatedq3data_collisionvertex3f, surface->deprecatedq3num_collisionbboxstride, surface->deprecatedq3data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
                        }
                }
        }
@@ -5808,10 +5844,10 @@ static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, dp_model_t *mo
                for (i = 0;i < leaf->numleafsurfaces;i++)
                {
                        surface = model->data_surfaces + leaf->firstleafsurface[i];
-                       if (surface->num_collisiontriangles && surface->collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, surface->mins, surface->maxs))
+                       if (surface->num_collisiontriangles && surface->deprecatedq3collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, surface->mins, surface->maxs))
                        {
-                               surface->collisionmarkframe = markframe;
-                               Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionbboxstride, surface->data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
+                               surface->deprecatedq3collisionmarkframe = markframe;
+                               Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, surface->num_collisiontriangles, surface->deprecatedq3data_collisionelement3i, surface->deprecatedq3data_collisionvertex3f, surface->deprecatedq3num_collisionbboxstride, surface->deprecatedq3data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
                        }
                }
        }
@@ -5868,7 +5904,7 @@ static void Mod_Q3BSP_TraceLine(dp_model_t *model, const frameblend_t *frameblen
                if (mod_q3bsp_curves_collisions.integer)
                        for (i = 0, surface = model->data_surfaces + model->firstmodelsurface;i < model->nummodelsurfaces;i++, surface++)
                                if (surface->num_collisiontriangles)
-                                       Collision_TraceLineTriangleMeshFloat(trace, start, end, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionbboxstride, surface->data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
+                                       Collision_TraceLineTriangleMeshFloat(trace, start, end, surface->num_collisiontriangles, surface->deprecatedq3data_collisionelement3i, surface->deprecatedq3data_collisionvertex3f, surface->deprecatedq3num_collisionbboxstride, surface->deprecatedq3data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
        }
        else
                Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model, model->brush.data_nodes, start, end, 0, 1, start, end, ++markframe, segmentmins, segmentmaxs);
@@ -5923,7 +5959,7 @@ static void Mod_Q3BSP_TraceBox(dp_model_t *model, const frameblend_t *frameblend
                if (mod_q3bsp_curves_collisions.integer)
                        for (i = 0, surface = model->data_surfaces + model->firstmodelsurface;i < model->nummodelsurfaces;i++, surface++)
                                if (surface->num_collisiontriangles)
-                                       Collision_TraceBrushTriangleMeshFloat(trace, &thisbrush_start.brush, &thisbrush_end.brush, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionbboxstride, surface->data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
+                                       Collision_TraceBrushTriangleMeshFloat(trace, &thisbrush_start.brush, &thisbrush_end.brush, surface->num_collisiontriangles, surface->deprecatedq3data_collisionelement3i, surface->deprecatedq3data_collisionvertex3f, surface->deprecatedq3num_collisionbboxstride, surface->deprecatedq3data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs);
        }
        else
                Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, model->brush.data_nodes, &thisbrush_start.brush, &thisbrush_end.brush, ++markframe, segmentmins, segmentmaxs);
@@ -5961,6 +5997,88 @@ static int Mod_Q3BSP_PointSuperContents(struct model_s *model, int frame, const
        return supercontents;
 }
 
+void Mod_MakeCollisionData(dp_model_t *model)
+{
+       int j;
+       int bihnumleafs;
+       int bihmaxnodes;
+       int brushindex;
+       int triangleindex;
+       int bihleafindex;
+       int nummodelbrushes = model->nummodelbrushes;
+       int nummodelsurfaces = model->nummodelsurfaces;
+       const int *e;
+       const int *collisionelement3i;
+       const float *collisionvertex3f;
+       bih_leaf_t *bihleafs;
+       bih_node_t *bihnodes;
+       int *temp_leafsort;
+       int *temp_leafsortscratch;
+       const msurface_t *surface;
+       const q3mbrush_t *brush;
+
+       // find out how many BIH leaf nodes we need
+       bihnumleafs = model->nummodelbrushes;
+       surface = model->data_surfaces + model->firstmodelsurface;
+       for (j = 0, surface = model->data_surfaces + model->firstmodelsurface;j < nummodelsurfaces;j++, surface++)
+               bihnumleafs += surface->num_collisiontriangles;
+       bihmaxnodes = bihnumleafs >> 1;
+
+       // allocate the memory for the BIH leaf nodes
+       bihleafs = Mem_Alloc(loadmodel->mempool, sizeof(bih_leaf_t) * bihnumleafs);
+
+       // add BIH leaf nodes for all the collision brushes
+       bihleafindex = 0;
+       for (brushindex = 0, brush = model->brush.data_brushes + brushindex+model->firstmodelbrush;brushindex < nummodelbrushes;brushindex++, brush++)
+       {
+               bihleafs[bihleafindex].type = BIH_LEAF;
+               bihleafs[bihleafindex].textureindex = brush->texture - model->data_textures;
+               bihleafs[bihleafindex].itemindex = brushindex+model->firstmodelbrush;
+               VectorCopy(brush->colbrushf->mins, bihleafs[bihleafindex].mins);
+               VectorCopy(brush->colbrushf->mins, bihleafs[bihleafindex].maxs);
+               bihleafindex++;
+       }
+
+       // add BIH leaf nodes for all the collision surfaces
+       collisionelement3i = model->brush.data_collisionelement3i;
+       collisionvertex3f = model->brush.data_collisionvertex3f;
+       for (j = 0, surface = model->data_surfaces + model->firstmodelsurface;j < nummodelsurfaces;j++, surface++)
+       {
+               e = collisionelement3i + surface->num_firstcollisiontriangle;
+               for (triangleindex = 0;triangleindex < surface->num_collisiontriangles;triangleindex++)
+               {
+                       bihleafs[bihleafindex].type = BIH_LEAF + 1;
+                       bihleafs[bihleafindex].textureindex = surface->texture - model->data_textures;
+                       bihleafs[bihleafindex].itemindex = triangleindex+surface->num_firstcollisiontriangle;
+                       bihleafs[bihleafindex].mins[0] = min(collisionvertex3f[3*e[0]+0], min(collisionvertex3f[3*e[1]+0], collisionvertex3f[3*e[2]+0]));
+                       bihleafs[bihleafindex].mins[1] = min(collisionvertex3f[3*e[0]+1], min(collisionvertex3f[3*e[1]+1], collisionvertex3f[3*e[2]+1]));
+                       bihleafs[bihleafindex].mins[2] = min(collisionvertex3f[3*e[0]+2], min(collisionvertex3f[3*e[1]+2], collisionvertex3f[3*e[2]+2]));
+                       bihleafs[bihleafindex].maxs[0] = max(collisionvertex3f[3*e[0]+0], max(collisionvertex3f[3*e[1]+0], collisionvertex3f[3*e[2]+0]));
+                       bihleafs[bihleafindex].maxs[1] = max(collisionvertex3f[3*e[0]+1], max(collisionvertex3f[3*e[1]+1], collisionvertex3f[3*e[2]+1]));
+                       bihleafs[bihleafindex].maxs[2] = max(collisionvertex3f[3*e[0]+2], max(collisionvertex3f[3*e[1]+2], collisionvertex3f[3*e[2]+2]));
+                       bihleafindex++;
+               }
+       }
+
+       // allocate buffers for the produced and temporary data
+       bihnodes = Mem_Alloc(loadmodel->mempool, sizeof(bih_node_t) * bihmaxnodes);
+       temp_leafsort = Mem_Alloc(loadmodel->mempool, sizeof(int) * bihnumleafs * 2);
+       temp_leafsortscratch = temp_leafsort + bihnumleafs;
+
+       // now build it
+       BIH_Build(&model->collision_bih, bihnumleafs, bihleafs, bihmaxnodes, bihnodes, temp_leafsort, temp_leafsortscratch);
+
+       // we're done with the temporary data
+       Mem_Free(temp_leafsort);
+
+       // resize the BIH nodes array if it over-allocated
+       if (model->collision_bih.maxnodes > model->collision_bih.numnodes)
+       {
+               model->collision_bih.maxnodes = model->collision_bih.numnodes;
+               model->collision_bih.nodes = Mem_Realloc(loadmodel->mempool, model->collision_bih.nodes, model->collision_bih.numnodes * sizeof(bih_node_t));
+       }
+}
+
 static int Mod_Q3BSP_SuperContentsFromNativeContents(dp_model_t *model, int nativecontents)
 {
        int supercontents = 0;
@@ -6273,6 +6391,8 @@ void Mod_Q3BSP_Load(dp_model_t *mod, void *buffer, void *bufferend)
                if (j < mod->nummodelsurfaces)
                        mod->DrawAddWaterPlanes = R_Q1BSP_DrawAddWaterPlanes;
 
+               Mod_MakeCollisionData(mod);
+
                // generate VBOs and other shared data before cloning submodels
                if (i == 0)
                        Mod_BuildVBOs();

diff --git a/model_shared.h b/model_shared.h
index 5ea12a222af0851e3a717954dbd405be634c8eb4..96e9fb38c013f17015a5eba5724798dec28faf91 100644 (file)
--- a/model_shared.h
+++ b/model_shared.h
@@ -579,10 +579,11 @@ typedef struct msurface_s
        // fog volume info in q3bsp
        struct q3deffect_s *effect; // q3bsp
        // mesh information for collisions (only used by q3bsp curves)
-       int *data_collisionelement3i; // q3bsp
-       float *data_collisionvertex3f; // q3bsp
-       float *data_collisionbbox6f; // collision optimization - contains combined bboxes of every data_collisionstride triangles
-       float *data_bbox6f; // collision optimization - contains combined bboxes of every data_collisionstride triangles
+       int num_firstcollisiontriangle;
+       int *deprecatedq3data_collisionelement3i; // q3bsp
+       float *deprecatedq3data_collisionvertex3f; // q3bsp
+       float *deprecatedq3data_collisionbbox6f; // collision optimization - contains combined bboxes of every data_collisionstride triangles
+       float *deprecatedq3data_bbox6f; // collision optimization - contains combined bboxes of every data_collisionstride triangles
 
        // surfaces own ranges of vertices and triangles in the model->surfmesh
        int num_triangles; // number of triangles
@@ -596,14 +597,15 @@ typedef struct msurface_s
        // mesh information for collisions (only used by q3bsp curves)
        int num_collisiontriangles; // q3bsp
        int num_collisionvertices; // q3bsp
-       int num_collisionbboxstride;
-       int num_bboxstride;
+       int deprecatedq3num_collisionbboxstride;
+       int deprecatedq3num_bboxstride;
        // FIXME: collisionmarkframe should be kept in a separate array
-       int collisionmarkframe; // q3bsp // don't collide twice in one trace
+       int deprecatedq3collisionmarkframe; // q3bsp // don't collide twice in one trace
 }
 msurface_t;
 
 #include "matrixlib.h"
+#include "bih.h"
 
 #include "model_brush.h"
 #include "model_sprite.h"
@@ -683,6 +685,12 @@ typedef struct model_brush_s
        //pvschain = model->brush.data_pvsclusters + mycluster * model->brush.num_pvsclusterbytes;
        //if (pvschain[thatcluster >> 3] & (1 << (thatcluster & 7)))
 
+       // collision geometry for q3 curves
+       int num_collisionvertices;
+       int num_collisiontriangles;
+       float *data_collisionvertex3f;
+       int *data_collisionelement3i;
+
        // a mesh containing all shadow casting geometry for the whole model (including submodels), portions of this are referenced by each surface's num_firstshadowmeshtriangle
        shadowmesh_t *shadowmesh;
 
@@ -868,6 +876,8 @@ typedef struct model_s
        // range of collision brush numbers in this (sub)model
        int                             firstmodelbrush;
        int                             nummodelbrushes;
+       // BIH (Bounding Interval Hierarchy) for this (sub)model
+       bih_t                   collision_bih;
        // for md3 models
        int                             num_tags;
        int                             num_tagframes;