Hi all, I'm working on a 3D space combat game and recently I've been trying to get collision detection working. The algorithm that I've gone with appears to be very slow, so I was wondering if anyone had any better ideas for how to go about it? Some of the ships have complex shapes, so bounding spheres etc won't be very believable. My current approach does a simple rejection test for entities in the game world using a bounding sphere calculated at load time. So when an object moves it cycles through other entities in the world doing a simple "do our spheres collide" test which is quite cheap performance wise. If one of these tests succeeds then it moves on to doing a triangle-triangle collision test using a collision mesh created by the artists working on the project. Collisions meshes only consist of < 100 polys, yet the test reduces the frame rate from 450FPS down to about 15 when you are close to an object in the world. Maybe just the triangle collision test that I am using is slow, but do you think this is a viable approach for a real time 3D shooter? Thanks in advance for any comments.

You can use some kind of partitioning structure to not do 100^2 tests, but rather just test each triangle against those that are close to it.

A very easy way, which might help a lot if your objects are kinda large, is to just do that sphere test for each triangle you test. If you go through each triangle in the first object, check the distance from it to the center of the second object, and see if it's inside the bounding sphere of the second object. Then possibly even check for every triangle you test it against to see it's close enough to the first object, depending on how much faster the sphere test is compared to the triangle test.

If you want it really efficient you must probably find some better data-structure, such as an octree or BSP, to get asymptotically better performance.

Thanks for your help guys. I managed to find a much faster triangle intersection algorithm which gives adequate FPS (around 300) when in the vicinity of another model. I might extend it further to use bounding spheres on sub groups of triangles or use some sort of spatial partitioning scheme, but for the moment performance is acceptable.

Thanks again for all your help.