# Collision detection of convex shapes on voxel terrain

I have some standard convex shapes (cubes, capsules) on a voxel terrain. It is very easy to detect single vertex collisions. However, it becomes computationally expensive when many vertices are involved.

To clarify, currently my algorithm represents a cube as multiple vertices covering every face of the cube, not just the corners. This is because the cubes can be much bigger than the voxels, so multiple sample points (vertices) are required (the distance between sample points must be at least the width of a voxel). This very rapidly becomes intractable.

It would be great if there were some standard algorithm(s) for collision detection between convex shapes and arbitrary voxel based terrain (like there is with OBB's and seperating axis theorem etc).

Any help much appreciated.

In my engine I perform collision detection/physics against the extracted surface mesh, rather than the underlying voxel data. This avoids the type of problem you describe - the physics engine doesn't know there are voxels involved at all and perfroms standard mesh to mesh calculations.

Of course, I can appriciate that using the voxel data has certain advantages (and it's something I would like to research in the future) but I found my current approach quite satisfactory. You can see a video of it in action and/or download a demo from my website: http://www.thermite3d.org

• I had a look at your website before posting this question to see how you did it, noticed you are still using the marching cubes mesh. Unfortunately, I've had several problems with that approach (marching cubes passed to Bullet), mostly due to tunneling through the mesh unless I have ridiculously small timesteps. Still, your engine is something I really do admire, keep meaning to check out the code.
– Dave
Commented Feb 1, 2011 at 18:38

It seems to me that bounding box techniques still apply - even though you might consider your cubes "supersampled". I would approach the problem in a hierarchical manner: you should know the maximal extents of the cube (even though a number of points might exist "between" those points) - so consider those maximal vertices as the cube's bounding box.

Assuming you have some sort of BB structure defined for the landscape, your can then use BB intersection techniques as a high-level hit-test. From there, you can "dive down" into the cube in order to determine precisely which vertices intersected.

• My intutition is that you are on to something, but the problem I can't resolve in my head is that the surface can be arbitrary. E.g. you have a 'spike' protruding from the surface that is extremely thin, I can't think how to detect that without iterating over every point on the shape.
– Dave
Commented Feb 1, 2011 at 18:42
• An irregular shape (i.e. one with a protrusion) is definitely suited to a hierarchical BB structure (think something like a specialized octree). In the case of a simple cube with a spike, I would enclose the whole object in one large bounding box. Within that box, I would have two smaller BB's - one enclosing the cube and one enclosing the spike. At worst, you have three high-level hit tests before knowing that an intersection occurred with the spike. Of course, this strategy assumes you can decompose your complex objects into a number of smaller ones. (I think that's reasonable.) Commented Feb 1, 2011 at 19:23

Look into the GJK algorithm, which may be used for convex shape collision. You may be able to make appropriate adjustments to make it work with your voxels, I wouldn't know. Here's a great video explaining it: https://mollyrocket.com/849

I think if you can create a function which can give the position of the voxel furthest along in a certain direction (ie, the support), you can probably make the algorithm work. Of course, you need to constrain your support vector function for voxel terrain to some region around the object you're testing collision with, since it makes no sense to check far away terrain.