From 8c4a05a0e34eb4c21be65315d58841c0f8268197 Mon Sep 17 00:00:00 2001
From: havoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Date: Mon, 15 Feb 2010 12:56:48 +0000
Subject: [PATCH] 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
---
bih.c | 140 +++++++++++++++++++++++++++++++++++++++++
bih.h | 68 ++++++++++++++++++++
gl_rmain.c | 49 ++++++++++-----
makefile.inc | 1 +
model_brush.c | 164 ++++++++++++++++++++++++++++++++++++++++++-------
model_shared.h | 24 +++++---
6 files changed, 401 insertions(+), 45 deletions(-)
create mode 100644 bih.c
create mode 100644 bih.h
diff --git a/bih.c b/bih.c
new file mode 100644
index 00000000..caf6e7e1
--- /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
index 00000000..7a98045f
--- /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 c2f1a1cf..ad459952 100644
--- 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 22478d5d..1c341202 100644
--- 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 8aa9c063..dff011ed 100644
--- 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 5ea12a22..96e9fb38 100644
--- 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;
--
2.39.5