From d5af28c8b70b48fc900e64471ace80da8f9274f8 Mon Sep 17 00:00:00 2001 From: divverent Date: Tue, 21 Jul 2009 19:23:09 +0000 Subject: [PATCH] Collision against patches: do some major optimizations. Keep an array of combined mins and maxs of every 32 consecutive triangles of the patch mesh. Always collide against the mins/maxs in this array first before actually trying the triangles. Improves collision performance a LOT, testcase.pk3 (a huge 31x31 patch mesh) becomes playable. mod_q3bsp_collision_curves_stride value still needs optimizing, I think. git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@9065 d7cf8633-e32d-0410-b094-e92efae38249 --- collision.c | 74 +++++++++++++++++++++++++++++++++++++++++--------- collision.h | 4 +-- model_alias.c | 4 +-- model_brush.c | 57 +++++++++++++++++++++++++++++++++++--- model_shared.h | 2 ++ 5 files changed, 120 insertions(+), 21 deletions(-) diff --git a/collision.c b/collision.c index b97a0df3..5694cdb4 100644 --- a/collision.c +++ b/collision.c @@ -901,7 +901,7 @@ void Collision_TraceBrushPolygonFloat(trace_t *trace, const colbrushf_t *thisbru Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush); } -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 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, texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs) { int i; polyf_brush.numpoints = 3; @@ -914,17 +914,44 @@ void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *th polyf_brush.planes[i].q3surfaceflags = q3surfaceflags; polyf_brush.planes[i].texture = texture; } - for (i = 0;i < numtriangles;i++, element3i += 3) + if(stride) { - if (TriangleOverlapsBox(vertex3f + element3i[0]*3, vertex3f + element3i[1]*3, vertex3f + element3i[2]*3, segmentmins, segmentmaxs)) + int k, cnt, tri; + cnt = (numtriangles + stride - 1) / stride; + for(i = 0; i < cnt; ++i) { - VectorCopy(vertex3f + element3i[0] * 3, polyf_points[0].v); - VectorCopy(vertex3f + element3i[1] * 3, polyf_points[1].v); - VectorCopy(vertex3f + element3i[2] * 3, polyf_points[2].v); - Collision_SnapCopyPoints(polyf_brush.numpoints, polyf_points, polyf_points, COLLISION_SNAPSCALE, COLLISION_SNAP); - Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); - //Collision_PrintBrushAsQHull(&polyf_brush, "polyf_brush"); - Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush); + if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs)) + { + for(k = 0; k < stride; ++k) + { + tri = i * stride + k; + if(tri >= numtriangles) + break; + VectorCopy(vertex3f + element3i[tri * 3 + 0] * 3, polyf_points[0].v); + VectorCopy(vertex3f + element3i[tri * 3 + 1] * 3, polyf_points[1].v); + VectorCopy(vertex3f + element3i[tri * 3 + 2] * 3, polyf_points[2].v); + Collision_SnapCopyPoints(polyf_brush.numpoints, polyf_points, polyf_points, COLLISION_SNAPSCALE, COLLISION_SNAP); + Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); + //Collision_PrintBrushAsQHull(&polyf_brush, "polyf_brush"); + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush); + } + } + } + } + else + { + for (i = 0;i < numtriangles;i++, element3i += 3) + { + if (TriangleOverlapsBox(vertex3f + element3i[0]*3, vertex3f + element3i[1]*3, vertex3f + element3i[2]*3, segmentmins, segmentmaxs)) + { + VectorCopy(vertex3f + element3i[0] * 3, polyf_points[0].v); + VectorCopy(vertex3f + element3i[1] * 3, polyf_points[1].v); + VectorCopy(vertex3f + element3i[2] * 3, polyf_points[2].v); + Collision_SnapCopyPoints(polyf_brush.numpoints, polyf_points, polyf_points, COLLISION_SNAPSCALE, COLLISION_SNAP); + Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); + //Collision_PrintBrushAsQHull(&polyf_brush, "polyf_brush"); + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush); + } } } } @@ -948,13 +975,34 @@ void Collision_TraceLinePolygonFloat(trace_t *trace, const vec3_t linestart, con Collision_TraceLineBrushFloat(trace, linestart, lineend, &polyf_brush, &polyf_brush); } -void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, 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, texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs) { int i; #if 1 // FIXME: snap vertices? - for (i = 0;i < numtriangles;i++, element3i += 3) - Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[0] * 3, vertex3f + element3i[1] * 3, vertex3f + element3i[2] * 3, supercontents, q3surfaceflags, texture); + if(stride) + { + int k, cnt, tri; + cnt = (numtriangles + stride - 1) / stride; + for(i = 0; i < cnt; ++i) + { + if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs)) + { + for(k = 0; k < stride; ++k) + { + tri = i * stride + k; + if(tri >= numtriangles) + break; + Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[tri * 3 + 0] * 3, vertex3f + element3i[tri * 3 + 1] * 3, vertex3f + element3i[tri * 3 + 2] * 3, supercontents, q3surfaceflags, texture); + } + } + } + } + else + { + for (i = 0;i < numtriangles;i++, element3i += 3) + Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[0] * 3, vertex3f + element3i[1] * 3, vertex3f + element3i[2] * 3, supercontents, q3surfaceflags, texture); + } #else polyf_brush.numpoints = 3; polyf_brush.numplanes = 5; diff --git a/collision.h b/collision.h index ee4e1564..339f1aaa 100644 --- a/collision.h +++ b/collision.h @@ -102,10 +102,10 @@ colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, i colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents); 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_TraceBrushPolygonFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, int supercontents); -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 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, 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_TraceLinePolygonFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numpoints, const float *points, int supercontents); -void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, 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, 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); diff --git a/model_alias.c b/model_alias.c index ebc56776..4068e3e9 100644 --- a/model_alias.c +++ b/model_alias.c @@ -657,7 +657,7 @@ static void Mod_MDLMD2MD3_TraceBox(dp_model_t *model, int frame, trace_t *trace, for (i = 0, surface = model->data_surfaces;i < model->num_surfaces;i++, surface++) { model->AnimateVertices(model, frameblend, vertex3f, NULL, NULL, NULL); - Collision_TraceLineTriangleMeshFloat(trace, start, end, model->surfmesh.num_triangles, model->surfmesh.data_element3i, vertex3f, SUPERCONTENTS_SOLID | (surface->texture->basematerialflags & MATERIALFLAGMASK_TRANSLUCENT ? 0 : SUPERCONTENTS_OPAQUE), 0, surface->texture, segmentmins, segmentmaxs); + Collision_TraceLineTriangleMeshFloat(trace, start, end, model->surfmesh.num_triangles, model->surfmesh.data_element3i, vertex3f, 0, NULL, SUPERCONTENTS_SOLID | (surface->texture->basematerialflags & MATERIALFLAGMASK_TRANSLUCENT ? 0 : SUPERCONTENTS_OPAQUE), 0, surface->texture, segmentmins, segmentmaxs); } } else @@ -687,7 +687,7 @@ static void Mod_MDLMD2MD3_TraceBox(dp_model_t *model, int frame, trace_t *trace, vertex3f = (float *)Z_Malloc(maxvertices * sizeof(float[3])); } model->AnimateVertices(model, frameblend, vertex3f, NULL, NULL, NULL); - Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, model->surfmesh.num_triangles, model->surfmesh.data_element3i, vertex3f, SUPERCONTENTS_SOLID | (surface->texture->basematerialflags & MATERIALFLAGMASK_TRANSLUCENT ? 0 : SUPERCONTENTS_OPAQUE), 0, surface->texture, segmentmins, segmentmaxs); + Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, model->surfmesh.num_triangles, model->surfmesh.data_element3i, vertex3f, 0, NULL, SUPERCONTENTS_SOLID | (surface->texture->basematerialflags & MATERIALFLAGMASK_TRANSLUCENT ? 0 : SUPERCONTENTS_OPAQUE), 0, surface->texture, segmentmins, segmentmaxs); } } } diff --git a/model_brush.c b/model_brush.c index 612caa2d..e9c35ffd 100644 --- a/model_brush.c +++ b/model_brush.c @@ -39,6 +39,7 @@ cvar_t r_subdivisions_collision_mintess = {0, "r_subdivisions_collision_mintess" cvar_t r_subdivisions_collision_maxtess = {0, "r_subdivisions_collision_maxtess", "1024", "maximum number of subdivisions (prevents curves beyond a certain detail level, limits smoothing)"}; cvar_t r_subdivisions_collision_maxvertices = {0, "r_subdivisions_collision_maxvertices", "4225", "maximum vertices allowed per subdivided curve"}; cvar_t mod_q3bsp_curves_collisions = {0, "mod_q3bsp_curves_collisions", "1", "enables collisions with curves (SLOW)"}; +cvar_t mod_q3bsp_curves_collisions_stride = {0, "mod_q3bsp_curves_collisions_stride", "32", "collisions against curves: optimize performance by doing a combined collision check for this triangle amount first"}; cvar_t mod_q3bsp_optimizedtraceline = {0, "mod_q3bsp_optimizedtraceline", "1", "whether to use optimized traceline code for line traces (as opposed to tracebox code)"}; cvar_t mod_q3bsp_debugtracebrush = {0, "mod_q3bsp_debugtracebrush", "0", "selects different tracebrush bsp recursion algorithms (for debugging purposes only)"}; 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, ..."}; @@ -65,6 +66,7 @@ void Mod_BrushInit(void) Cvar_RegisterVariable(&r_subdivisions_collision_maxtess); Cvar_RegisterVariable(&r_subdivisions_collision_maxvertices); Cvar_RegisterVariable(&mod_q3bsp_curves_collisions); + Cvar_RegisterVariable(&mod_q3bsp_curves_collisions_stride); Cvar_RegisterVariable(&mod_q3bsp_optimizedtraceline); Cvar_RegisterVariable(&mod_q3bsp_debugtracebrush); Cvar_RegisterVariable(&mod_q3bsp_lightmapmergepower); @@ -4995,6 +4997,53 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l) 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); + + // now optimize the collision mesh by finding triangle bboxes... + if(mod_q3bsp_curves_collisions_stride.integer > 0) + { + int k, cnt, tri; + float *mins, *maxs, *vert; + out->num_collisionstride = mod_q3bsp_curves_collisions_stride.integer; + cnt = (out->num_collisiontriangles + out->num_collisionstride - 1) / out->num_collisionstride; + out->data_collisionbbox6f = (float *) Mem_Alloc(loadmodel->mempool, sizeof(float[6]) * cnt); + for(j = 0; j < cnt; ++j) + { + mins = &(out->data_collisionbbox6f[6 * j + 0]); + maxs = &(out->data_collisionbbox6f[6 * j + 3]); + for(k = 0; k < out->num_collisionstride; ++k) + { + tri = j * out->num_collisionstride + k; + if(tri >= out->num_collisiontriangles) + break; + vert = &(out->data_collisionvertex3f[out->data_collisionelement3i[3 * tri + 0] * 3]); + if(!k || vert[0] < mins[0]) mins[0] = vert[0]; + if(!k || vert[1] < mins[1]) mins[1] = vert[1]; + if(!k || vert[2] < mins[2]) mins[2] = vert[2]; + if(!k || vert[0] > maxs[0]) maxs[0] = vert[0]; + if(!k || vert[1] > maxs[1]) maxs[1] = vert[1]; + if(!k || vert[2] > maxs[2]) maxs[2] = vert[2]; + vert = &(out->data_collisionvertex3f[out->data_collisionelement3i[3 * tri + 1] * 3]); + if(vert[0] < mins[0]) mins[0] = vert[0]; + if(vert[1] < mins[1]) mins[1] = vert[1]; + if(vert[2] < mins[2]) mins[2] = vert[2]; + if(vert[0] > maxs[0]) maxs[0] = vert[0]; + if(vert[1] > maxs[1]) maxs[1] = vert[1]; + if(vert[2] > maxs[2]) maxs[2] = vert[2]; + vert = &(out->data_collisionvertex3f[out->data_collisionelement3i[3 * tri + 2] * 3]); + if(vert[0] < mins[0]) mins[0] = vert[0]; + if(vert[1] < mins[1]) mins[1] = vert[1]; + if(vert[2] < mins[2]) mins[2] = vert[2]; + if(vert[0] > maxs[0]) maxs[0] = vert[0]; + if(vert[1] > maxs[1]) maxs[1] = vert[1]; + if(vert[2] > maxs[2]) maxs[2] = vert[2]; + } + } + } + else + { + out->num_collisionstride = 0; + } + if (developer.integer >= 100) Con_Printf("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); break; @@ -5528,7 +5577,7 @@ static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, dp_model_t *mod if (surface->num_collisiontriangles && surface->collisionmarkframe != 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->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs); + Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionstride, surface->data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs); } } } @@ -5609,7 +5658,7 @@ static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, dp_model_t *mo if (surface->num_collisiontriangles && surface->collisionmarkframe != 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->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs); + Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionstride, surface->data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs); } } } @@ -5657,7 +5706,7 @@ static void Mod_Q3BSP_TraceBox(dp_model_t *model, int frame, trace_t *trace, con 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->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs); + Collision_TraceLineTriangleMeshFloat(trace, start, end, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionstride, surface->data_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); @@ -5688,7 +5737,7 @@ static void Mod_Q3BSP_TraceBox(dp_model_t *model, int frame, trace_t *trace, con 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, thisbrush_end, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs); + Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, surface->num_collisiontriangles, surface->data_collisionelement3i, surface->data_collisionvertex3f, surface->num_collisionstride, surface->data_collisionbbox6f, surface->texture->supercontents, surface->texture->surfaceflags, surface->texture, segmentmins, segmentmaxs); } else Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model, model->brush.data_nodes, thisbrush_start, thisbrush_end, ++markframe, segmentmins, segmentmaxs); diff --git a/model_shared.h b/model_shared.h index b182b7e4..1708b49b 100644 --- a/model_shared.h +++ b/model_shared.h @@ -571,6 +571,8 @@ typedef struct msurface_s int *data_collisionelement3i; // q3bsp int num_collisionvertices; // q3bsp float *data_collisionvertex3f; // q3bsp + float *data_collisionbbox6f; // collision optimization - contains combined bboxes of every data_collisionstride triangles + int num_collisionstride; struct q3deffect_s *effect; // q3bsp // FIXME: collisionmarkframe should be kept in a separate array int collisionmarkframe; // q3bsp // don't collide twice in one trace -- 2.39.2