From: havoc Date: Wed, 17 Feb 2010 06:55:00 +0000 (+0000) Subject: implemented and debugged BIH (Bounding Interval Hierarchy) code, more X-Git-Tag: xonotic-v0.1.0preview~230^2~504 X-Git-Url: http://de.git.xonotic.org/?p=xonotic%2Fdarkplaces.git;a=commitdiff_plain;h=a5c12e5524c2af491c483e0207f48524f1cf072a;ds=sidebyside implemented and debugged BIH (Bounding Interval Hierarchy) code, more optimizations possible but this is a good start mod_collision_bih cvar added, defaults to 0 because it is not yet consistently faster than q3bsp collisions git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@9965 d7cf8633-e32d-0410-b094-e92efae38249 --- diff --git a/bih.c b/bih.c index caf6e7e1..8797d20d 100644 --- a/bih.c +++ b/bih.c @@ -5,7 +5,7 @@ #include #include "bih.h" -static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist) +static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist, float *totalmins, float *totalmaxs) { int i; int j; @@ -21,17 +21,10 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist) 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; + float frontmins[3]; + float frontmaxs[3]; + float backmins[3]; + float backmaxs[3]; // calculate bounds of children child = bih->leafs + leaflist[0]; mins[0] = child->mins[0]; @@ -53,6 +46,25 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist) size[0] = maxs[0] - mins[0]; size[1] = maxs[1] - mins[1]; size[2] = maxs[2] - mins[2]; + // provide bounds to caller + totalmins[0] = mins[0]; + totalmins[1] = mins[1]; + totalmins[2] = mins[2]; + totalmaxs[0] = maxs[0]; + totalmaxs[1] = maxs[1]; + totalmaxs[2] = maxs[2]; + // if there is only one child this is a leaf + if (numchildren < 2) + return -1-leaflist[0]; + // if we run out of nodes it's the caller's fault, but don't crash + if (bih->numnodes == bih->maxnodes) + { + if (!bih->error) + bih->error = BIHERROR_OUT_OF_NODES; + return -1-leaflist[0]; + } + nodenum = bih->numnodes++; + node = bih->nodes + nodenum; // store bounds for node node->mins[0] = mins[0]; node->mins[1] = mins[1]; @@ -64,25 +76,14 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist) 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) + // iterate possible split axis choices, starting with the longest axis, if + // all fail it means all children have the same bounds and we simply split + // the list in half because each node can only have two children. 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; - } + // pick an axis + axis = (longestaxis + j) % 3; // 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; @@ -104,16 +105,18 @@ static int BIH_BuildNode(bih_t *bih, int numchildren, int *leaflist) } 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; + // somewhat common case: no good choice, divide children arbitrarily + axis = 0; 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); + node->type = BIH_SPLITX + axis; + node->front = BIH_BuildNode(bih, front, leaflist, frontmins, frontmaxs); + node->frontmin = frontmins[axis]; + node->back = BIH_BuildNode(bih, back, leaflist + front, backmins, backmaxs); + node->backmax = backmaxs[axis]; return nodenum; } @@ -135,6 +138,6 @@ int BIH_Build(bih_t *bih, int numleafs, bih_leaf_t *leafs, int maxnodes, bih_nod for (i = 0;i < bih->numleafs;i++) bih->leafsort[i] = i; - BIH_BuildNode(bih, bih->numleafs, bih->leafsort); + bih->rootnode = BIH_BuildNode(bih, bih->numleafs, bih->leafsort, bih->mins, bih->maxs); return bih->error; } diff --git a/bih.h b/bih.h index 7a98045f..56632b36 100644 --- a/bih.h +++ b/bih.h @@ -30,7 +30,11 @@ typedef struct bih_node_s 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]; + int front; + int back; + // interval of children + float frontmin; // children[0] + float backmax; // children[1] } bih_node_t; @@ -54,6 +58,10 @@ typedef struct bih_s // nodes are constructed by BIH_Build int numnodes; bih_node_t *nodes; + int rootnode; // 0 if numnodes > 0, -1 otherwise + // bounds calculated by BIH_Build + float mins[3]; + float maxs[3]; // fields used only during BIH_Build: int maxnodes; diff --git a/collision.c b/collision.c index cd587f28..10e2d70e 100644 --- a/collision.c +++ b/collision.c @@ -155,7 +155,7 @@ void Collision_CalcEdgeDirsForPolygonBrushFloat(colbrushf_t *brush) VectorSubtract(brush->points[i].v, brush->points[j].v, brush->edgedirs[j].v); } -colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents, int q3surfaceflags, texture_t *texture, int hasaabbplanes) +colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents, int q3surfaceflags, const texture_t *texture, int hasaabbplanes) { // TODO: planesbuf could be replaced by a remapping table int j, k, l, m, w, xyzflags; @@ -613,7 +613,7 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) } } -colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents, int q3surfaceflags, texture_t *texture) +colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents, int q3surfaceflags, const texture_t *texture) { colbrushf_t *brush; brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colplanef_t) * (numpoints + 2) + sizeof(colpointf_t) * numpoints); @@ -647,7 +647,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *trace_sta vec4_t startplane; vec4_t endplane; vec4_t newimpactplane; - texture_t *hittexture = NULL; + const texture_t *hittexture = NULL; vec_t startdepth = 1; vec3_t startdepthnormal; @@ -856,7 +856,7 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const vec4_t startplane; vec4_t endplane; vec4_t newimpactplane; - texture_t *hittexture = NULL; + const texture_t *hittexture = NULL; vec_t startdepth = 1; vec3_t startdepthnormal; @@ -1034,7 +1034,7 @@ void Collision_SnapCopyPoints(int numpoints, const colpointf_t *in, colpointf_t } } -void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs) +void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs) { int i; colpointf_t points[3]; @@ -1116,7 +1116,7 @@ void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *th } } -void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs) +void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs) { int i; // FIXME: snap vertices? @@ -1145,7 +1145,41 @@ void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart } } -void Collision_BrushForBox(colboxbrushf_t *boxbrush, const vec3_t mins, const vec3_t maxs, int supercontents, int q3surfaceflags, texture_t *texture) +void Collision_TraceBrushTriangleFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const float *v0, const float *v1, const float *v2, int supercontents, int q3surfaceflags, const texture_t *texture) +{ + int i; + colpointf_t points[3]; + colpointf_t edgedirs[3]; + colplanef_t planes[5]; + colbrushf_t brush; + memset(&brush, 0, sizeof(brush)); + brush.isaabb = false; + brush.hasaabbplanes = false; + brush.numpoints = 3; + brush.numedgedirs = 3; + brush.numplanes = 5; + brush.points = points; + brush.edgedirs = edgedirs; + brush.planes = planes; + brush.supercontents = supercontents; + brush.q3surfaceflags = q3surfaceflags; + brush.texture = texture; + for (i = 0;i < brush.numplanes;i++) + { + brush.planes[i].q3surfaceflags = q3surfaceflags; + brush.planes[i].texture = texture; + } + VectorCopy(v0, points[0].v); + VectorCopy(v1, points[1].v); + VectorCopy(v2, points[2].v); + Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP); + Collision_CalcEdgeDirsForPolygonBrushFloat(&brush); + Collision_CalcPlanesForPolygonBrushFloat(&brush); + //Collision_PrintBrushAsQHull(&brush, "brush"); + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush); +} + +void Collision_BrushForBox(colboxbrushf_t *boxbrush, const vec3_t mins, const vec3_t maxs, int supercontents, int q3surfaceflags, const texture_t *texture) { int i; memset(boxbrush, 0, sizeof(*boxbrush)); @@ -1278,7 +1312,7 @@ float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double return impactdist / linelength; } -void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2, int supercontents, int q3surfaceflags, texture_t *texture) +void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2, int supercontents, int q3surfaceflags, const texture_t *texture) { #if 1 // more optimized diff --git a/collision.h b/collision.h index 52c52e87..f541de4a 100644 --- a/collision.h +++ b/collision.h @@ -48,7 +48,7 @@ typedef struct trace_s // the q3 surfaceflags of the impacted surface int hitq3surfaceflags; // the texture of the impacted surface - struct texture_s *hittexture; + const struct texture_s *hittexture; // initially false, set when the start leaf is found // (set only by Q1BSP tracing and entity box tracing) int startfound; @@ -60,8 +60,8 @@ typedef struct trace_s trace_t; void Collision_Init(void); -void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, texture_t *boxtexture); -void Collision_ClipTrace_Point(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, texture_t *boxtexture); +void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, const texture_t *boxtexture); +void Collision_ClipTrace_Point(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, const texture_t *boxtexture); typedef struct colpointf_s { @@ -71,7 +71,7 @@ colpointf_t; typedef struct colplanef_s { - struct texture_s *texture; + const struct texture_s *texture; int q3surfaceflags; vec3_t normal; vec_t dist; @@ -100,7 +100,7 @@ typedef struct colbrushf_s int numtriangles; int *elements; // texture data for cases where an edgedir is used - struct texture_s *texture; + const struct texture_s *texture; int q3surfaceflags; // optimized collisions for common cases int isaabb; // indicates this is an axis aligned box @@ -118,21 +118,22 @@ typedef struct colboxbrushf_s colboxbrushf_t; void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush); -colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents, int q3surfaceflags, texture_t *texture); -colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents, int q3surfaceflags, texture_t *texture, int hasaabbplanes); +colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents, int q3surfaceflags, const texture_t *texture); +colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents, int q3surfaceflags, const texture_t *texture, int hasaabbplanes); void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end); -void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs); +void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs); void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end); -void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs); +void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs); void Collision_TracePointBrushFloat(trace_t *trace, const vec3_t point, const colbrushf_t *thatbrush); qboolean Collision_PointInsideBrushFloat(const vec3_t point, const colbrushf_t *brush); -void Collision_BrushForBox(colboxbrushf_t *boxbrush, const vec3_t mins, const vec3_t maxs, int supercontents, int q3surfaceflags, texture_t *texture); +void Collision_BrushForBox(colboxbrushf_t *boxbrush, const vec3_t mins, const vec3_t maxs, int supercontents, int q3surfaceflags, const texture_t *texture); void Collision_BoundingBoxOfBrushTraceSegment(const colbrushf_t *start, const colbrushf_t *end, vec3_t mins, vec3_t maxs, float startfrac, float endfrac); float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double *sphereorigin, double sphereradius, double *impactpoint, double *impactnormal); -void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2, int supercontents, int q3surfaceflags, texture_t *texture); +void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2, int supercontents, int q3surfaceflags, const texture_t *texture); +void Collision_TraceBrushTriangleFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const float *v0, const float *v1, const float *v2, int supercontents, int q3surfaceflags, const texture_t *texture); // traces a box move against a single entity // mins and maxs are relative diff --git a/gl_rmain.c b/gl_rmain.c index ad459952..a3b5b241 100644 --- a/gl_rmain.c +++ b/gl_rmain.c @@ -12109,6 +12109,7 @@ static void R_DrawModelDecals(void) } } +extern cvar_t mod_collision_bih; void R_DrawDebugModel(void) { entity_render_t *ent = rsurface.entity; @@ -12127,7 +12128,7 @@ void R_DrawDebugModel(void) GL_DepthMask(false); GL_BlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); - if (r_showcollisionbrushes.value > 0 && model->collision_bih.numleafs) + if (r_showcollisionbrushes.value > 0 && model->collision_bih.numleafs && mod_collision_bih.integer) { int triangleindex; int bihleafindex; @@ -12137,6 +12138,7 @@ void R_DrawDebugModel(void) 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); + cullbox = false; for (bihleafindex = 0, bihleaf = bih->leafs;bihleafindex < bih->numleafs;bihleafindex++, bihleaf++) { if (cullbox && R_CullBox(bihleaf->mins, bihleaf->maxs)) @@ -12148,6 +12150,7 @@ void R_DrawDebugModel(void) brush = model->brush.data_brushes + bihleaf->itemindex; if (brush->colbrushf && brush->colbrushf->numtriangles) { + R_Mesh_VertexPointer(brush->colbrushf->points->v, 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, brush->colbrushf->numpoints, 0, brush->colbrushf->numtriangles, brush->colbrushf->elements, NULL, 0, 0); } diff --git a/model_brush.c b/model_brush.c index c2f5320c..ee82cde8 100644 --- a/model_brush.c +++ b/model_brush.c @@ -46,6 +46,7 @@ cvar_t mod_q3bsp_debugtracebrush = {0, "mod_q3bsp_debugtracebrush", "0", "select cvar_t mod_q3bsp_lightmapmergepower = {CVAR_SAVE, "mod_q3bsp_lightmapmergepower", "4", "merges the quake3 128x128 lightmap textures into larger lightmap group textures to speed up rendering, 1 = 256x256, 2 = 512x512, 3 = 1024x1024, 4 = 2048x2048, 5 = 4096x4096, ..."}; cvar_t mod_q3bsp_nolightmaps = {CVAR_SAVE, "mod_q3bsp_nolightmaps", "0", "do not load lightmaps in Q3BSP maps (to save video RAM, but be warned: it looks ugly)"}; cvar_t mod_q3bsp_tracelineofsight_brushes = {0, "mod_q3bsp_tracelineofsight_brushes", "0", "enables culling of entities behind detail brushes, curves, etc"}; +cvar_t mod_collision_bih = {0, "mod_collision_bih", "0", "enables use of generated Bounding Interval Hierarchy tree instead of compiled bsp tree in collision code"}; static texture_t mod_q1bsp_texture_solid; static texture_t mod_q1bsp_texture_sky; @@ -75,6 +76,7 @@ void Mod_BrushInit(void) Cvar_RegisterVariable(&mod_q3bsp_lightmapmergepower); Cvar_RegisterVariable(&mod_q3bsp_nolightmaps); Cvar_RegisterVariable(&mod_q3bsp_tracelineofsight_brushes); + Cvar_RegisterVariable(&mod_collision_bih); memset(&mod_q1bsp_texture_solid, 0, sizeof(mod_q1bsp_texture_solid)); strlcpy(mod_q1bsp_texture_solid.name, "solid" , sizeof(mod_q1bsp_texture_solid.name)); @@ -1017,7 +1019,7 @@ static int Mod_Q1BSP_PointSuperContents(struct model_s *model, int frame, const return Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num); } -void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, texture_t *boxtexture) +void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, const texture_t *boxtexture) { #if 1 colbrushf_t cbox; @@ -1123,7 +1125,7 @@ void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cm #endif } -void Collision_ClipTrace_Point(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, texture_t *boxtexture) +void Collision_ClipTrace_Point(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, int hitsupercontentsmask, int boxsupercontents, int boxq3surfaceflags, const texture_t *boxtexture) { memset(trace, 0, sizeof(trace_t)); trace->fraction = 1; @@ -5669,6 +5671,365 @@ static qboolean Mod_Q3BSP_TraceLineOfSight(struct model_s *model, const vec3_t s } } +static void Mod_BIH_TracePoint_RecursiveBIHNode(trace_t *trace, dp_model_t *model, int nodenum, const vec3_t point) +{ + const bih_leaf_t *leaf; + const bih_node_t *node; + const colbrushf_t *brush; + int axis; + while (nodenum >= 0) + { + node = model->collision_bih.nodes + nodenum; + axis = node->type - BIH_SPLITX; + if (point[axis] <= node->backmax) + { + if (point[axis] >= node->frontmin) + Mod_BIH_TracePoint_RecursiveBIHNode(trace, model, node->front, point); + nodenum = node->back; + } + else if (point[axis] >= node->frontmin) + nodenum = node->front; + else // no overlap with either child? just return + return; + } + if (!model->collision_bih.leafs) + return; + leaf = model->collision_bih.leafs + (-1-nodenum); + switch(leaf->type) + { + case BIH_LEAF: + // brush + brush = model->brush.data_brushes[leaf->itemindex].colbrushf; + Collision_TracePointBrushFloat(trace, point, brush); + break; + case BIH_LEAF + 1: + // triangle - skipped because they have no volume + break; + default: + break; + } +} + +static void Mod_BIH_TraceLine_RecursiveBIHNode(trace_t *trace, dp_model_t *model, int nodenum, const vec3_t start, const vec3_t end, const vec3_t linestart, const vec3_t lineend) +{ + const bih_leaf_t *leaf; + const bih_node_t *node; + const colbrushf_t *brush; + const int *e; + const texture_t *texture; + int axis; +#if 0 + int sideflags; + vec_t frontdist1; + vec_t frontdist2; + vec_t frontfrac; + vec_t backdist1; + vec_t backdist2; + vec_t backfrac; + vec3_t clipped[2]; +#endif + vec3_t segmentmins; + vec3_t segmentmaxs; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + while (nodenum >= 0) + { + node = model->collision_bih.nodes + nodenum; +#if 0 + if (!BoxesOverlap(segmentmins, segmentmaxs, node->mins, node->maxs)) + return; +#endif + axis = node->type - BIH_SPLITX; +#if 1 + if (segmentmins[axis] <= node->backmax) + { + if (segmentmaxs[axis] >= node->frontmin) + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, start, end, linestart, lineend); + nodenum = node->back; + } + else if (segmentmaxs[axis] >= node->frontmin) + nodenum = node->front; + else + return; // trace falls between children +#else + frontdist1 = start[axis] - node->backmax; + frontdist2 = end[axis] - node->backmax; + backdist1 = start[axis] - node->frontmin; + backdist2 = end[axis] - node->frontmin; + sideflags = 0; + if (frontdist1 < 0) + sideflags |= 1; + if (frontdist2 < 0) + sideflags |= 2; + if (backdist1 < 0) + sideflags |= 4; + if (backdist2 < 0) + sideflags |= 8; + switch(sideflags) + { + case 0: + // start end START END + nodenum = node->front; + continue; + case 1: + // START end START END + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[0]); + start = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->front; + break; + case 2: + // start END START END + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[0]); + end = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->front; + break; + case 3: + // START END START END + return; // line falls in gap between children + case 4: + // start end start END + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, start, end, linestart, lineend); + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + end = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 5: + // START end start END + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[1]); + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, clipped[1], end, linestart, lineend); + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + end = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 6: + // start END start END + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[1]); + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, start, clipped[1], linestart, lineend); + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + end = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 7: + // START END start END + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + end = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 8: + // start end START end + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, start, end, linestart, lineend); + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + start = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 9: + // START end START end + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[1]); + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, clipped[1], end, linestart, lineend); + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + start = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 10: + // start END START end + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[1]); + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, start, clipped[1], linestart, lineend); + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + start = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 11: + // START END START end + backfrac = backdist1 / (backdist1 - backdist2); + VectorLerp(start, backfrac, end, clipped[0]); + start = clipped[0]; + segmentmins[0] = min(start[0], end[0]); + segmentmins[1] = min(start[1], end[1]); + segmentmins[2] = min(start[2], end[2]); + segmentmaxs[0] = max(start[0], end[0]); + segmentmaxs[1] = max(start[1], end[1]); + segmentmaxs[2] = max(start[2], end[2]); + nodenum = node->back; + break; + case 12: + // start end start end + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, start, end, linestart, lineend); + nodenum = node->back; + break; + case 13: + // START end start end + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[1]); + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, clipped[1], end, linestart, lineend); + nodenum = node->back; + break; + case 14: + // start END start end + frontfrac = frontdist1 / (frontdist1 - frontdist2); + VectorLerp(start, frontfrac, end, clipped[1]); + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, node->front, start, clipped[1], linestart, lineend); + nodenum = node->back; + break; + case 15: + // START END start end + nodenum = node->back; + continue; + } +#endif + } + if (!model->collision_bih.leafs) + return; + leaf = model->collision_bih.leafs + (-1-nodenum); +#if 1 + if (!BoxesOverlap(segmentmins, segmentmaxs, leaf->mins, leaf->maxs)) + return; +#endif + switch(leaf->type) + { + case BIH_LEAF: + // brush + brush = model->brush.data_brushes[leaf->itemindex].colbrushf; + Collision_TraceLineBrushFloat(trace, linestart, lineend, brush, brush); + break; + case BIH_LEAF + 1: + // triangle + e = model->brush.data_collisionelement3i + 3*leaf->itemindex; + texture = model->data_textures + leaf->textureindex; + Collision_TraceLineTriangleFloat(trace, linestart, lineend, model->brush.data_collisionvertex3f + e[0] * 3, model->brush.data_collisionvertex3f + e[1] * 3, model->brush.data_collisionvertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture); + break; + default: + break; + } +} + +static void Mod_BIH_TraceBrush_RecursiveBIHNode(trace_t *trace, dp_model_t *model, int nodenum, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const vec3_t segmentmins, const vec3_t segmentmaxs) +{ + const bih_leaf_t *leaf; + const bih_node_t *node; + const colbrushf_t *brush; + const int *e; + const texture_t *texture; + int axis; + while (nodenum >= 0) + { + node = model->collision_bih.nodes + nodenum; + axis = node->type - BIH_SPLITX; +#if 0 +#if 0 + if (!BoxesOverlap(segmentmins, segmentmaxs, node->mins, node->maxs)) + return; +#endif + Mod_BIH_TraceBrush_RecursiveBIHNode(trace, model, node->front, thisbrush_start, thisbrush_end, segmentmins, segmentmaxs); + nodenum = node->back; + continue; +#endif + if (segmentmins[axis] <= node->backmax) + { + if (segmentmaxs[axis] >= node->frontmin) + Mod_BIH_TraceBrush_RecursiveBIHNode(trace, model, node->front, thisbrush_start, thisbrush_end, segmentmins, segmentmaxs); + nodenum = node->back; + } + else if (segmentmaxs[axis] >= node->frontmin) + nodenum = node->front; + else + return; // trace falls between children + } + if (!model->collision_bih.leafs) + return; + leaf = model->collision_bih.leafs + (-1-nodenum); +#if 1 + if (!BoxesOverlap(segmentmins, segmentmaxs, leaf->mins, leaf->maxs)) + return; +#endif + switch(leaf->type) + { + case BIH_LEAF: + // brush + brush = model->brush.data_brushes[leaf->itemindex].colbrushf; + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, brush, brush); + break; + case BIH_LEAF + 1: + // triangle + e = model->brush.data_collisionelement3i + 3*leaf->itemindex; + texture = model->data_textures + leaf->textureindex; + Collision_TraceBrushTriangleFloat(trace, thisbrush_start, thisbrush_end, model->brush.data_collisionvertex3f + e[0] * 3, model->brush.data_collisionvertex3f + e[1] * 3, model->brush.data_collisionvertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture); + break; + default: + break; + } +} + static void Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace_t *trace, dp_model_t *model, mnode_t *node, const vec3_t point, int markframe) { int i; @@ -5869,7 +6230,9 @@ static void Mod_Q3BSP_TracePoint(dp_model_t *model, const frameblend_t *frameble trace->fraction = 1; trace->realfraction = 1; trace->hitsupercontentsmask = hitsupercontentsmask; - if (model->brush.submodel) + if (mod_collision_bih.integer) + Mod_BIH_TracePoint_RecursiveBIHNode(trace, model, model->collision_bih.rootnode, start); + else if (model->brush.submodel) { for (i = 0, brush = model->brush.data_brushes + model->firstmodelbrush;i < model->nummodelbrushes;i++, brush++) if (brush->colbrushf) @@ -5902,7 +6265,9 @@ static void Mod_Q3BSP_TraceLine(dp_model_t *model, const frameblend_t *frameblen segmentmaxs[0] = max(start[0], end[0]) + 1; segmentmaxs[1] = max(start[1], end[1]) + 1; segmentmaxs[2] = max(start[2], end[2]) + 1; - if (model->brush.submodel) + if (mod_collision_bih.integer) + Mod_BIH_TraceLine_RecursiveBIHNode(trace, model, model->collision_bih.rootnode, start, end, start, end); + else if (model->brush.submodel) { for (i = 0, brush = model->brush.data_brushes + model->firstmodelbrush;i < model->nummodelbrushes;i++, brush++) if (brush->colbrushf) @@ -5957,7 +6322,9 @@ static void Mod_Q3BSP_TraceBox(dp_model_t *model, const frameblend_t *frameblend VectorAdd(end, boxmaxs, boxendmaxs); Collision_BrushForBox(&thisbrush_start, boxstartmins, boxstartmaxs, 0, 0, NULL); Collision_BrushForBox(&thisbrush_end, boxendmins, boxendmaxs, 0, 0, NULL); - if (model->brush.submodel) + if (mod_collision_bih.integer) + Mod_BIH_TraceBrush_RecursiveBIHNode(trace, model, model->collision_bih.rootnode, &thisbrush_start.brush, &thisbrush_end.brush, segmentmins, segmentmaxs); + else if (model->brush.submodel) { for (i = 0, brush = model->brush.data_brushes + model->firstmodelbrush;i < model->nummodelbrushes;i++, brush++) if (brush->colbrushf) @@ -5976,8 +6343,14 @@ static int Mod_Q3BSP_PointSuperContents(struct model_s *model, int frame, const int i; int supercontents = 0; q3mbrush_t *brush; + if (mod_collision_bih.integer) + { + trace_t trace; + Mod_Q3BSP_TracePoint(model, NULL, NULL, &trace, point, 0); + supercontents = trace.startsupercontents; + } // test if the point is inside each brush - if (model->brush.submodel) + else if (model->brush.submodel) { // submodels are effectively one leaf for (i = 0, brush = model->brush.data_brushes + model->firstmodelbrush;i < model->nummodelbrushes;i++, brush++) @@ -6028,7 +6401,7 @@ void Mod_MakeCollisionData(dp_model_t *model) 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; + bihmaxnodes = bihnumleafs - 1; // allocate the memory for the BIH leaf nodes bihleafs = Mem_Alloc(loadmodel->mempool, sizeof(bih_leaf_t) * bihnumleafs); @@ -6041,7 +6414,7 @@ void Mod_MakeCollisionData(dp_model_t *model) 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); + VectorCopy(brush->colbrushf->maxs, bihleafs[bihleafindex].maxs); bihleafindex++; } @@ -6050,18 +6423,18 @@ void Mod_MakeCollisionData(dp_model_t *model) 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++) + e = collisionelement3i + 3*surface->num_firstcollisiontriangle; + for (triangleindex = 0;triangleindex < surface->num_collisiontriangles;triangleindex++, e += 3) { 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])); + bihleafs[bihleafindex].mins[0] = min(collisionvertex3f[3*e[0]+0], min(collisionvertex3f[3*e[1]+0], collisionvertex3f[3*e[2]+0])) - 1; + bihleafs[bihleafindex].mins[1] = min(collisionvertex3f[3*e[0]+1], min(collisionvertex3f[3*e[1]+1], collisionvertex3f[3*e[2]+1])) - 1; + bihleafs[bihleafindex].mins[2] = min(collisionvertex3f[3*e[0]+2], min(collisionvertex3f[3*e[1]+2], collisionvertex3f[3*e[2]+2])) - 1; + bihleafs[bihleafindex].maxs[0] = max(collisionvertex3f[3*e[0]+0], max(collisionvertex3f[3*e[1]+0], collisionvertex3f[3*e[2]+0])) + 1; + bihleafs[bihleafindex].maxs[1] = max(collisionvertex3f[3*e[0]+1], max(collisionvertex3f[3*e[1]+1], collisionvertex3f[3*e[2]+1])) + 1; + bihleafs[bihleafindex].maxs[2] = max(collisionvertex3f[3*e[0]+2], max(collisionvertex3f[3*e[1]+2], collisionvertex3f[3*e[2]+2])) + 1; bihleafindex++; } }