Work on the physics engine is progressing remarkably quickly! Last week I implemented a fairly nice, albeit basic, collision resolution system. To test it, I set up a sizable asteroid field (~1000 asteroids) and a simple ship. I gave the ship the ability to spew small pellets, which serve to test the collision engine. I'm really, really happy with how painless it is to setup the physics engine: it just takes one initialization call, one "Add" call for each object in the system, and then a "FindAllCollisions" call in the update step. Everything else is automatic - the engine keeps track of the objects, their collision meshes and density fields, and figures out when objects are colliding.
Everything on the screen is collidable, so there are no special cases or exceptions. If asteroids are included in the physics engine, then all asteroids can collide with all other asteroids. If bullets are included, bullets can collide with bullets as well as with asteroids, etc. Everything functions just as you would expect. Finally, the part that really matters - the performance - is really, really good!!! I was amazed by how fast the engine runs. I can get about 1000 asteroids + several thousand bullets on screen at once while maintaining 60fps. That's a lot of colliders! It's really cool to watch bullets collide multiple times off of different asteroids.
There's still work to be done. The system still has a few glitches: bullets are occasionally piercing asteroids, the system could be even faster, and the physics could be more realistic (Newton would be crying if he saw my collision response equations). The next step is probably to implement spatial signatures, just to see if I can squeeze some more performance out of the system. When everything gets tightened up, I'll definitely be recording a video demonstration of it.
All in all, I couldn't have hoped for better luck with the physics engine I'm quite proud of it! I think the engine will serve the inhabitants of my reality well.
Yes, I'm quite happy with my collision detection engine. But could it be faster? Probably!
Here's an idea I had today. Obviously, I'm obsessed with spatial hashing. It's probably my favorite thing ever. Well, what about this: take a mesh, create a spatial grid of booleans (which can, of course, be represented super-efficiently as a bit vector), then loop over every triangle in the mesh. For any spatial grid that the triangle intersects, the corresponding hash bucket gets set to true. Once this has been done for all triangles, you are left with an array of bits that represents the spatial buckets with which the mesh collides. Purely for the sake of being able to throw around cool and esoteric terminology, I'll call this array the "spatial signature" of the object.
Now, here's the fun part. In my previous technique, I looped over the vertices of one mesh, checking them against the density function of the second. The most expensive part of this check is, without a doubt, evaluating the density function. Well, instead, we could prune the possibilities by first checking the vertex against the spatial signature of the object! It's quite inexpensive to hash the vertex to a bucket in the same space as the one in which the spatial signature was created. Then, we simply check the corresponding index in the bit array. If the array indicates that no triangles intersect that spatial bucket, then there's absolutely no chance that the vertex could be colliding with the mesh. On the other hand, in the event that the bit is turned on, then we continue as before with the full-blown density check.
This is, of course, a completely untested idea, but it seems to me that the speed with which a bit array could be accessed would significantly cut down on the narrow-phase collision check, especially when dealing with complex density functions.
The war is over; the battle has been won. For now.
I merged the previously-discussed narrow-phase collision engine with the broad-phase spatial hashing engine that I wrote a few months ago, and the results couldn't have been more pleasing! Everything works just as I had wanted, and now the whole collision detection system is as simple as adding objects to the engine, then requesting collision reports in the update step. Everything else is handled automatically - and it doesn't require choosing a certain type of collision mesh or pre-building any special data for collision detection! All it requires is the density function that was used to generate the object's mesh. Furthermore, it's fast
I also made a minor optimization to the spatial hashing engine that's worth mentioning, as it kicked my framerate back up to 60 when doing collision detection on the large, rotating space station in my demo had taking it down to 10 fps or so. The idea is that, when adding an object to spatial buckets, it's a good idea to 'over-allocate,' so to speak. In other words, scale the bounding box by 150% or so, then add this enlarged box to the spatial buckets. It may waste a few checks in the broad-phase cycle, but it cuts down on the frequency with which you have to change the spatial buckets around, which I found to be a huge bottleneck for really large, moving objects (especially when the spatial grid is kept relatively small).
If you do the aforementioned, then when an object moves, you need only modify the spatial grid if the object's new bounding box isn't contained in the 'over-allocated' one. Now, if you've got a grid size of 1 and a battleship that's 50 x 50 x 50, suffice it to say that it's going to get really expensive, really fast to update the spatial grid every frame if the battleship is moving. So don't!
A celebratory shot of me swooping triumphantly over the station, headed back toward the mothership:
But it took a while. The biggest problem I encountered in implementing my scheme was due to slight inaccuracies in the construction of the surfaces from the polygonization algorithm that ended up causing noticeable detection problems when meshes were scaled up. To fix it, I implemented a pseudo-binary search to ensure that the algorithm places vertices at points at which the absolute value of the density function is no more than some very small error tolerance, ensuring that the algorithm stays as true to the real surface as possible. Linear interpolation of the density function just isn't good enough when you introduce metaballs with variable power (i.e., to create rectilinear shapes), which can cause sharp, sudden variations in the density function.
After increasing the precision of the polygonized surfaces, the detection worked like a charm! The time required to check two bodies is highly dependent on the resolution of the point set used for the first body. I found that it generally sufficed to use point sets generated from low-resolution meshes for the collision. With optimization, I can get the checking time down to around 0.1 ms per check.
I've been pondering narrow phase collision detection a lot lately, as it's really the only thing that stands between me and a working space shooter demo. Unfortunately, it's not at all an easy problem, especially considering the fact that I have on-the-fly meshes generated and can make no assumptions about the topology, nor can I rely on hand-construction of bounding trees.
I had been getting pretty excited about an idea I had that involved a two-phase check using AABB-trees for pruning and then spatial bucketing (a la spatial hashing) for triangle-to-triangle testing. Then it hit me: why am I running in circles? I started with a mathematical model of the mesh: an isosurface of a well-defined density function. I used a complex algorithm to convert the isosurface into a polygonized mesh. Now I was trying to go back to a mathematical representation that would be conducive to collision detection. Why??
Here's the punchline: why not use the original density field description for checking? After all...the density field is even more precise than the triangular mesh! All that collision detection really is, thanks to the nature of my engine, is a solver for the intersection of two isosurfaces, both of which can be completely described using formulae! Of course, I'm sure the math would get incredibly nasty for an analytic solution, and I'm not really up for exploring that option at the moment. But here's a better idea: use a set of points (the vertex positions generated by the polygonization algorithm) to describe one isosurface, then check each point against the other surface's density function. Then, if you ever find a sign change, you immediately know that there's a collision!
This is a pretty cool idea, since it only requires a set of points and a density function to work. It definitely avoids a lot of mess associated with computing BVHs. Most importantly, however, it just makes sense! If you're working with a precise, mathematical definition of a surface, then use it!
I'll probably be implementing a rough draft of this system quite soon, so we'll see if it measures up to my expectations. I would imagine that sampling the density function will be cheaper than other types of collision detection, but I'll need to do some extensive profiling to make sure that this idea is actually as clever as I believe it to be.
I've been working on a physics engine for XDX (I know, it's excessive, but I want to learn how to make *every* component of a game). Spatial partitioning has been getting me down - in particular, octrees are painful because of all the edge cases that have to be considered - especially when one cannot restrict the system to a given space...because I'd rather my games be able to handle "infinite" space.
Last week, I found the answer to all of my problems: spatial hashing. It's a really beautiful scheme, and since it uses a uniform grid for the partitioning, it's particularly simple to implement. However, the fact that grid cells are hashed to buckets means that the flexibility is unrivaled: not only can one specify the size of a grid cell, but one can also specify how many buckets will be used to attach to grid cells. The system easily handles infinite space (since the hashing function works for any x,y,z triple).
I'm pretty excited about the implementation of this collision detection system, and I can't wait to see what kind of results I get! Physics-enabled space games may not be so far off for XDX!