Collision against patches: do some major optimizations.
authordivverent <divverent@d7cf8633-e32d-0410-b094-e92efae38249>
Tue, 21 Jul 2009 19:23:09 +0000 (19:23 +0000)
committerdivverent <divverent@d7cf8633-e32d-0410-b094-e92efae38249>
Tue, 21 Jul 2009 19:23:09 +0000 (19:23 +0000)
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
collision.h
model_alias.c
model_brush.c
model_shared.h

index b97a0df..5694cdb 100644 (file)
@@ -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;
index ee4e156..339f1aa 100644 (file)
@@ -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);
 
index ebc5677..4068e3e 100644 (file)
@@ -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);
                }
        }
 }
index 612caa2..e9c35ff 100644 (file)
@@ -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);
index b182b7e..1708b49 100644 (file)
@@ -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