From e325198b1353345954232afcdaa84cb0fc30a54a Mon Sep 17 00:00:00 2001 From: havoc 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 ::stable-branch::merge=8c4a05a0e34eb4c21be65315d58841c0f8268197 --- 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 +#include +#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.2