Ok, it’s about time for some posts!
So far shooting stuff has been based on your basic point/ray to sphere – a more sophisticated system was planned for later on in development – but to bring the wow-factor up a notch I’ve had to bring it forward.
I want a lot of objects whizzing about on screen – that means an awful lot of potential collisions – while I’ll go into the basics of the scene collision management in another post – this one is about what happens when one of your hundreds of missiles needs to hit a ship!
To make it look as believable as possible, the missile/bullet needs to impact the surface of the vessel and throw up sparks/debris/whatever. That means checking every single triangle in the model to see if your missile has hit it – quite a chore! And with models with hundreds of thousands of triangles in, even the beefiest CPU would buckle under the strain.
So, what to do? Well, as ever with computing – the least amount of work possible! Hit testing every triangle sounds like a lot of work, so how do we do less?
Octrees.
Octrees allow us to divide a large volume into smaller volumes (or containers) and then stick stuff into them. All we need to do is then find which container our missile would go in, and the check the missile against the contents of that container. Simples!
Well, not quite – but the principal is that easy. We create an octree volume the same size as the model itself, then start adding triangles to the volume. When there are more than say 50, we subdivide the volume (which creates 8 equal sized smaller volumes), and then move all the triangles into these smaller volumes. Then we continue adding triangles from our model. When we’ve reached the end of the models triangles, they should all be safely stashed away in the smallest volumes in the octree which should contain them. Depending on the models triangle count, and the number of triangles to be stashed into each volume – the octree will only be a few layers deep. This means we can quickly find the volume a point is in with only a few checks.
Model Octrees
You can see the process in the image above – going left to right, we have the model’s bounding volume (the maximum space it will occupy), then the Octree we get by repeatedly subdividing this volume into 8 until we get 50 triangles per volume. We then test an impact point to find out which volumes would be affected – finally showing those volumes, and the triangles we need to test in yellow. We’ve quickly gone from several thousand triangles down to a handful to test against.
To check for a collision, we have to bring that missile into model space – this means we find the missiles position and orientation relative to the model. We have to do this, as our octree and it’s triangles are always about the origin (0,0,0) and not in orbit about Canthen where you just shot at it. This helps speed up the testing as less math is involved.
We can now find the volume in the octree that this missile would go in, and then test it for a collision against each triangle. Each triangle which intersects the missile is flagged, and voila – we have our impact zone!
This consumes a lot more memory as the octree can be quite large for a large or highly detailed model, but the performance improvement over the brute force “check every triangle” is huge for larger models. Balancing the triangles-per-node against the volume of the model is the best way to tune the system at the moment.
So, that’s how you’ll be shooting stuff – the next thing to worry about is figuring out what’s shooting at what. Stay tuned!
Comments are closed.