Collision detection of convex shapes on voxel terrain

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.