Today I was playing with one of our demos at work, trying to work out whether the physics stuff I was seeing was a bug or expected behavior. Physics has always been one of those things I’ve been interested in, but my mathematical ability places something of a barrier on me. I understand a good many of the concepts, but once you start talking complicated solvers or Navier-Stokes I get a bit dizzy.
Andy J dropped in and we chatted a little. He asked me if we were using any kind of acceleration structure (ala an Octtree) to accelerate physics; I didn’t know and still don’t, but now that I’ve had time to think the problem through more, I rather doubt it.
In regards to collision with terrain, if you’ve got the position of an entity, its velocity, and a bounding sphere, you can work out a set of ‘candidate triangles’ for a heightmap-based terrain by projecting those over the heightmap and building a list of all the possible triangles that entity could hit that frame. This can be really slow for large objects or objects moving quickly along the X & Z axes. As for large objects, I don’t see any alternative - the larger an object is, the more space you have to check for a collision. And fast moving objects are often problematic for collision systems.
An (loose) octtree or something similar might help for entity-entity collision - which may have been the gist of Andy’s question in the first place - but there are better alternatives we talked about. He mentioned something involving hashing which I really don’t know anything about, but I might probe him tomorrow for more info. The method we both were familiar with was one where you sort all your entities initially by their position/extents in space, such that when you need to test for collision you only need to check some immediate neighbors in the list, and you keep them sorted using a linear sorting algorithm (bubble, insertion). If you think it through, it’s rather elegant - objects tend to rearrange themselves in the list rather slowly between frames, and you typically only end up swapping a couple neighboring objects when something moves. Again, this method breaks down with fast-moving objects. If you have a bunch of fast-moving objects, you have to do more and more resorting.
I’d like to know how people are solving the fast-moving object problem. It seems like there’s no clear solution - the more something moves in a frame, the larger the number of things that must be checked for collision. But then, I’m not a domain expert, and most of my knowledge in the area comes from forum posts and the couple of books I own.
At any rate, I think physics packages are one of the places where middleware is really shining. Havok, PhysX, Tokomak, Bullet, Newton. There are a lot of strong packages out there that meet different requirements (price, hardware acceleration, rigid-body vs soft-body, fluid dynamics). More importantly, none of them require domain experts to be useful - having a degree in Physics is nice, but you can get a lot out of any of those systems with a passing familiarity with the concepts. Considering all the challenges associated with the domain, it’s great to be able to integrate these well-established, heavily tested, and often free solutions.
This trick is really easy, and nobody will be able to tell how you did it.