Triverse presents some interesting collision problems. On the one hand, having a shape defined in a grid makes partitioning, and thus queries, simpler to implement. On the other hand, both terrain and ships are potentially large grids, which can make for complex collisions. I want to go through some of the basic parts of the collision system that enable efficient intersection tests in the game.
Consider a binary image consisting of black and white pixels to represent an object. Here’s a blob/asteroid I generated:
The asteroid is a black region of pixels in a regular square grid. We want to query this grid space for collisions with objects, which is a fairly common scenario given the explosion of voxel-based games. If the colliding objects are close to the size of the pixels/voxels, it’s trivial to look up the surrounding cells. For larger objects, or for general proximity queries within a space such as a circle/sphere, we need to do a bit more work.
The full problem I’m facing is colliding potentially large, changing grids with other objects, which may in fact be grids themselves. Each of the objects reacts dynamically according to its physical properties and the collision. The grids may be at arbitrary positions and orientations. As far as scale, they can be 1k x 1k cells, and change at the rate of 1k cells per second. For real-time scenarios, this is large enough that an efficient strategy is needed.
At the lowest level, we need to represent the underlying geometry of the object defined by occupied cells within the grid. By considering the occupancy of a given cell along with its neighbors, we can come up with a reasonably natural asteroid surface:
Now we have to store this in a form that is efficient to modify and can be passed to a physics system. Here are some choices:
- Build a mesh consisting of vertices and edges/triangles. Because we haven’t made any restrictions on shape, it could be concave, which would probably require the physics or collision system to decompose it into convex pieces.
- Use simple convex meshes for parts of the object: These parts could be individual cells or clusters of cells. This way we take advantage of locality information obtained from the grid rather than forcing another system to decompose the object.
- Use primitives such as spheres or rectangles for individual cells or cell clusters. Intersections are fast to calculate, but we may impose a greater burden on broad phase collision detection if many primitives are produced.
The first way is a general solution that could be implemented as marching squares/cubes or similar. However, with just a giant mesh to work with, collision detection cannot take advantage of any specialized information provided by the grid. These problems could be alleviated by partioning the grid and only generating meshes in regions of interest.
The second and third approaches are reasonable, but whether it’s more beneficial to use meshes or primitives probably depends on the specific geometry and the collision detection implementation. I’ve gone with the primitives approach, generated on the fly to drastically reduce the number of primitives pushed to the collision system. I’ll cover this in another post.