How to do collision detection on marching cubes terrain?

Question

I'm writing the physics part of my game engine. The world uses the marching cubes algorithm on a 3d perlin noise to make the terrain.

How do I do collision detection on the resulting mesh? I can't use SAT since the terrain is not convex and subdividing it into smaller convex parts seems to be nearly impossible.

What is the best collision detection algorithm for such a mesh? The objects that are supposed to collide with the terrain can be any convex polyhedron.

EDIT: The terrain is not "cubed" (like minecracft). The terrain is smooth with slopes. This is pretty close to what my terrain looks like (this is NOT my video): https://www.youtube.com/watch?v=-4rA3fdKWQA

I am looking for a general collision detection here. I need the point(s) of contact and the normals so that I can put these into my collision resolver.

Example of usage is throwing a box onto the terrain and it should roll and bounce approximately like it would in the real world.

Answer 1

Minor Edit:

I made an assumption here that you are looking to do your physics simulation / collision detection on the resulting mesh that you have generated rather than on say ... your point cloud (voxel) data (another assumption made that you are using voxels too) as this is the normal scenario.

Such collision detection on voxels would be problematic at best.

End of edit

How do I do collision detection on the resulting mesh?

The simplest way to answer this is ... How would you do collision detection on any mesh?

Throw a raycast in the direction you intend to perform your collision check then "pick" the vert that was hit and decide what action you want to take.

I don't know what technology you are using so it's hard to be too specific but here's an example of how its been done using OpenGL ...

3D Ray Casting / Picking

However based on this comment in your question ...

Example of usage is throwing a box onto the terrain and it should roll and bounce approximately like it would in the real world.

... I would say that without realising it what you need is a little more than collision detection, you need a physics simluation engine that can handle complex interactions between collisionable objects.

I went down this route when faced with the same problem ...

Most people because of the complexity of the math pull in a physics engine to their game engine code handle that for them, in my case I am using SharpDX and I chose to sit BulletSharp on top of that to handle physics simlations like rolling a mesh about on my terrain in the manner you describe.

The Bullet engine is great and comes with a ton of examples that can help you get started and has other wrappers than the one i'm using ...

https://code.google.com/p/bulletsharp/

I would give you a code sample here on exactly how all this clicks together but the code can be quite lengthy and I think the guys that provide Bullet are better placed to give you better description and a full working demo project to show this in action.

Answer 2

It depends if you are walking on it or flying over it. i.e. collision frequency. also it depends if your cubes are squares like minecraft, which makes it easy.

You have to make some kind of mesh collider, or some triangles around the point of collision.

Normally your program should have a way of making a mesh collider.

For advanced coders, and specific kinds of projects, you can use the perlin noise function to see how close an object is to a the terrain boundary. the isovalue is a guide for collision.

as a rough guide, the cheapest way to check collision is ISO value of noise, you can find a value, say >4 which is very far from the 0 isometric value, and only objects with a diamter larger than 20 say, could reach it. so first check the isovalue of the objects or of their boundaries.

if they are within a few meters of the boundary, have a 3d array of all the cubes in space, only a few of which will have triangles precomputed in them... fill that array when the cubes compute, and when necessary, you can check exact cubes that can collide using that array, very fast also.

then you can construct a dynamic collider using this array because you can access all triangles positions that you need instantly.

also there is the bullet physics engine under zlib licence.