My collision detection optimizations are finally ready for testing. I've done a couple things to the collision detection system in the Freespace Open engine.
First has been rewriting the time caching system that keeps track of all potential collision pairs in the gameplay simulation. Freespace brute forces this and ends up going through all n^2 pairs each frame in order to find valid collisions to test. This ends up becoming costly, especially when an object is deleted which results going through all n^2 pairs to find which pairs to delete.
I end up fixing this by finding potential collision pairs through applying Quicksort on all three axes to find objects that have their bounding boxes overlapping. I then use a hash table to store and keep track of the next check time for each pair that I get a positive on. The pair itself is collision tested business as usual if the next check time has been elapsed.
Second has been rewriting the collision data format for models. The internal data structure I use to store POF collision data from is much more leaner while being well formed. This means the traversal algorithm doesn't have to play with headache inducing pointer math to go down the collision data tree to find a hit on a model. The traversal algorithm is much simpler and much more readable which in the end should make it faster.
I've been playing around with multithreading the collision code. Due to the collision code becoming more efficient from my rewrites of these key portions, it's not longer necessary to multithread that section of the code.
My build with these changes are here:
http://www.hard-light.net/forums/index.php?topic=81087.0 . It includes a bunch of rendering optimizations including a soft particle rendering optimization and better OpenGL state change management.
