   Collision detection questions
  I am working on a RTS style minigame that features top down command of a variety of intelligent vehicles and players. The details of implementing the actual vehicles and players are not my responsibility but the work of the collision detection and physics are mine. The terrain will be a trimesh or heightmap of some sort that represents complex mountain ranges and or dunes in the desert. The modeling of destructible terrain is optional but desired. The main issue that I am faced with is this: most physics engines are designed around fairly small simulation areas. My simulation area can cover an area of up to a thousand square kilometers. I have the idea of using a verlet based integrator to do my physics computation due to the speed of calculation.I would like the ability to change the level of detail of my models on the fly, changing out a simple box with a single wheel moving across a plane to a fully articulated truck with springs and tires. For the higher level of detail, I may need to replace the verlet integrator with something a little more capable. My primary question is that of collision detection. Given that my vehicles will be constructed of convex trimeshes, what is the best way to handle the collisions between the ground plane and the actors?   
  For a real time strategy game you don't need very complex collision detection schemes, I assume, the player is going to be a fair distance away from the collisions taking place.  If that is the case, then I would simple look in to sphere-sphere collision checks for an easy out check to see if there is any possibility of collision, and then narrow down your collision checks to use object oriented bounding boxes around your units.Since it sounds like you are looking to have a large playfield, I assume you also want a large number of units.  If that's the case, I would look in to some sort of space partitioning scheme such as an oct-tree or quad-tree.For your collisions with the ground, if it is indeed just a plane you can just do a plane vs box test using the object oriented bounding box from before.If you're looking for ultra realistic physics though you're going to have to look in to things like the separating axis theorem or the GJK algorithm.  I would recommend you get the things I suggested previously done before looking in to either of those algorithms though.   ;  for colliding with a terrain, if your terrain is a nice heightmap, it should be trivial to detect what triangles are underneath your vehicle (it's mostly float to int conversions, to find the map area covered by your object). the SAT doesn't scale well as your convex object grows more complex. GJK is a much more complex algorythm, especially if you want to find out the details of the collision information.Also, note that for RTS, for a very low level of detail, you should be able to fudge the unit placement by simply finding the point under the centre of the unit on the heightmap, and re-aligning your unit to the slope of that point (both normal and position of the point on the heightmap can be done with simple linear interpolation). One drawback with heightmaps, is that you cannot do tunnels or over-hanging geometry easily.   ;  So far, the best implementation that I have been able to find is object oriented bounding boxes for my midphase. For most purposes, it seems to have pretty good performance. Thanks for the suggestions. As far as GJK vs Separation of Axis, which do you think would perform better (of course assuming a fairly optimal implementation of both) with concave meshes? Is there even a general solution for concave meshes without decomposing them to convex. Also, what do you suggest for terrain deformations?   ;  As for concave meshes, the best performance you are going to get is by decomposing them into convex parts, where each part has its own bounding volume (sphere, OBB, etc.). Then for each part of the concave mesh you run the convex collision algorithm. There are really no good fast collision detection methods for concave objects, while convex objects are the only objects which algorithms like SAT and GJK operate on.As for the algorithm to use, SAT is good when the complexity of the objects is minimal. Any more complicated than a box and the number of separating axes grows very quickly. GJK is a much better alternative when your convex objects are complex. While GJK may seem imposing at first, the implementation is not really that hard. Casey over at Molly Rocket has put together a video which describes an optimal implementation of GJK, one of the fastest around. It can be viewed or downloaded here, and the code for the tetrahedron case is on this page.   ;  G.J.K. would perform better for convex polytopes, however, the SAT is much easier to implement. So you can try that for a start. There are also optimisations you can perform to reduce the feature set and make the SAT more viable for convex polytopes. The SAT is great if your convex object has many redundant features. That reduces the set drastically. For example, a box is made of 6 faces, and 12 edges. Implementing the worst case SAT for box-box collision would require :6 + 6 + 12 x 12 = 156 tests.however, many faces and edges are parallel, so the set is reduced to :3 faces, 3 edge directions :3 + 3 + 3 x 3 = 15 tests.Also, you can do other optimisations to reduce the number of features to be tested against a particular object, depending on the object location. But G.J.K. will be faster and more solid, if you managed to implement it. As for terrains and deformation, if you choose an heightmap, the deformations would be reduced to 2D only. Meaning, you can only bring the heightmap vertices up and down. Foraging through terrain would not be possible, unless you use a 3D voxel map. Stan Melax had an interesting demo and paper on the subject, however it's not available any more (I suspect copyright material by Bioware). It's unfortunate, but it's not really hard to implement. There are of course other methods to implement terrain deformation. But my advice, a simple height map where you just dig holes in it would be very easy to implement and a pretty good first step. So, SAT, and height map with 1D (vertical axis deformation), for me, and linear interpolation to put units on the floor. Proper collision detection per units would be far too demanding.   