I'm still discovering FS architecture & code so I can't comment more on it yet but I can talk about how Allegiance handles collision detection.
Allegiance being a multiplayer only game with a dedicated server, only the server actually computes the collisions. To do this efficiently on 10 years ago hardware and allowing up to 200 players per game, they had to really optimize the collision code. Even more since there is no 'beam' weapon but only 'particle' weapons firing bullets (called projectiles) each been handled as a distinct object in the game logic code (and so in the collision code too).
The 1st thing they did is to not use the 3D models directly but instead use specially computed models made of
convex hulls. These convex hulls use variable n-polygons instead of triangles and are convex (orly?) which speed up greatly collision detection.
At compile time, the 3D models are transformed using
QHull and a CVH (convex hull) file is generated for each 3D model file.
Also instead of using a classical bounding box, the CVH files include a bounding ellipsoid of each object, optimizing even more the initial computation (that same bounding ellipsoid is also used for energy shields).
Then the code uses and updates a
K-D tree to store the objects and compute the collisions more efficiently as illustrated
here.
The collision code only uses CVH files and not the more complex 3D model files.
so to sum up , current optimizations are:
- bounding ellipsoids instead of bounding boxes
- special pre-computed 'convex hulls' models instead of the 3D gfx models
- k-d tree structure to store and sort the objects, updated every frame
There are more optimizations beyond that but they are more Allegiance specific (like 'sectoring' and separating moving and non moving objects).
