## Thursday, 15 July 2010

### Collision

I've just been asked on a forum how I went about collision. As it links in to the model editor changes I made in the last post I thought I'd write up a summary.

To cut a long story short I have written three collision systems. The first two were Octrees based on a Ziggyware example. These worked nicely until I tried to get a smaller level of detail. The exponential amount of data this produced in the first version made the load time on the Xbox 360 about 7 minutes for a simple level! The second variation got down to 24 seconds load time but I still had not got the level of detail I wanted.

The final solution was grid registration. This assumes that even in a 3D scene most of the objects are positioned on a 2D plane. The world is mainly on a single level until you go inside a building.

The solution is to simply divide the world up in to a grid. Then work out where on that grid any object falls. It can fall in to several grid squares. Objects above each other would be in the same grid square.

When working out if a moving objects hits a stationary object first check the grid they are in. Then simply loop through all objects in the grid and carry out whatever collision test is needed.

My collision as previously stated is based entirely on spheres. Each object, animated, rigid, moving or static is divided up in to big spheres and then smaller spheres.

Every model and every sphere has an index and large spheres contain the index of the smaller spheres within and the smaller spheres contain the index of the triangles within.

The triangle are for use with positioning decals of bullet impacts which I won't go in to here.

Bump collision is now a simple series of loops testing each sphere in the moving object with each sphere in the static objects that are within the same grid. Working from the larger sphere to the smaller spheres. If any smaller spheres intersect then work out the overlap and use that to calculate an amount to push the spheres and therefore the models apart.

The collision of moving object against moving object does not use the grid but is fundamentally the same.

As I have a maximum of 32 moving objects at any one time in the game, I just test all 32 against each other. This is done first, so the end result is that moving objects could fractionally overlap other moving objects if they bounce off a static object but a moving object cannot end up overlapping a static object.