Fast mesh collision 3D (C# XNA)

Question

I'm trying to write a simple program where a 3D landscape can be walked about with a basic camera. However, I've found it very difficult to do even simple collisions with my terrain. I'm wondering if anybody has encountered a similar issue before and possibly might know how to solve it a better way?

I've seen a lot of 3D collision questions, but I noticed that a lot of the answers are to approximate the mesh objects with spheres or cubes - however I find this impractical with something as complicated as terrain. I'm using a .fbx model of terrain made with blender, grabbing its entire list of vertices, finding the one closest to the camera, and trying to set the camera Y to the vertex Y + a constant. However, I keep running into a bunch of problems such as:

• finding the closest vertex is difficult because if the model is too big, distances measured between the camera and the vertices will overflow some variable types, but if the model is too small, distances will often be indistinguishable and inaccurate.

• my method is very slow, because the terrain has a lot of detail, so I find myself only checking every 20 vertices or so.

• I end up with very bad collision detection because my method appears to be inexact and malfunctioning.

Here's some of my code, if anybody wants to see what I'm doing... (btw the d_check array is a list of vertices of the model, and C is my camera.)

    private void BasicCameraCollisionTest(int radius, int offset)
    {
        float smallest_d = float.MaxValue;
        float c_d = 0;
        int i_cache = 0;
        for (int i = 0; i < d_check.Length; i+=20 )
        {
            c_d = Vector2.Distance(new Vector2(d_check[i].X, d_check[i].Z), new Vector2(C.position.X, C.position.Y));

            if (c_d < smallest_d)
            {
                smallest_d = c_d;
                i_cache = i;
            }
        }
        C.position = Vector3.Lerp(C.position, new Vector3(C.position.X, d_check[i_cache].Y + radius + offset, C.position.Z), 0.02f);
    }

If anybody could point me in the right direction, I'd be very grateful. Thanks!

Answer 1

While it is true that approximating geometry with primitives is the general solution in collision detection, in this case that's not entirely true. What most engines do is use a triangle mesh for the terrain and a vertically oriented capsule for the character. To keep the cost of testing down the triangle mesh is partitioned with some kind of spatial structure (KD-Tree, AABB tree) to make collecting the candidate triangles a fast operation. Collision detection between a triangle and a capsule is performed using a distance-from-line-segment to triangle test. Both David Eberly's website (http://www.geometrictools.com/GTEngine/Include/GteDistLine3Triangle3.h) and Christer Ericson's book Realtime Collision Detection outline two approaches.

So to review:

• Create a vertically-oriented capsule to represent the player character
• Calculate the bounding axis aligned bounding box (AABB) of the capsule
• Use the AABB to collect a collection of candidate triangles for the triangle mesh - triangles that overlap the AABB.
• Perform distance linesegment to triangle test and if the distance is less than the radius of the capsule then a collision exists.

I hope that helps.