# Fast mesh collision 3D (C# XNA)

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!

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.

• Thanks - this is helpful - though I'm going to leave the question open a bit longer so here's an upvote. Anyway, will this method still work with my extremely large model (the fbx from blender) or will I have to scale it down? I'm assuming that the size of the model doesn't matter as long as the camera is positioned relatively close to the surface, but I'm not sure. (Basically, will the AABB collision method still suffer from overflow errors with extremely large distance checks?) – Superdoggy Mar 18 '15 at 11:55
• @Superdoggy, you will need to optimize your collision check by putting the vertices of your mesh into an octree, spatial hash map, or similar structure. You only want to check vertices near the player. You never want to loop through every triangle and do a collision test on each one. – mklingen Mar 18 '15 at 15:15
• OK, I guess it's time to get reading. I really don't know anything about how fbx files (and the vertices within them) are organized - so I guess I still have plenty to read up on. – Superdoggy Mar 18 '15 at 16:02