For a game, I want to be able to have collision meshes for the player to collide with, and the player itself would be represented by a mesh. All the meshes would be very simple, only a few ploys. I've scoured the internet for information for triangle mesh to triangle mesh collision detection, but all of it is useless to me because it either does too much (its overcomplicated) or it uses an external library. I don't want to use any kind of external library, because I don't need full physics, super complicated collisions or anything like that. If anyone knew of any method or place with source code that just does this kind of collision and not even any kind of responses that would be much appreciated. Thanks.

Ps. I load in models from an obj, so I store them as triangle data ex: faces[0].x1,faces[0].y1......

Efficient mesh collision detection is very complicated. You will have an easier time integrating the most complicated physics libraries then writing this yourself.

However, if you are feeling up to it, and would like to learn, here is what you do:

A: Slow and Naive Method:

For each two triangles in your game, check if they collide with each-other. (Find a triangle-to-triangle intersection method on the internet.)

B: You will very shortly realise that this will kill your CPU. So add a spatial indexer (AABB-Tree or Quad-Tree) to minimize the amount of checks:

For each pair of meshes, check with an AABB-Tree if they might be colliding before you check their triangles.

1. Consruct an AABB-Tree containing all of your meshes as boxes.

2. Find out roughly which meshes might be colliding with the help of the AABB-Tree.

C: This will be enough if your meshes are extremely simple, and rareley collide. If they are not extremely simple, you will need to add another layer of AABBTree on the meshes:

1. Consruct an AABB-Tree containing all of your meshes as boxes.

2. Find out roughly which meshes might be colliding with the help of the AABB-Tree.

3. Pre-process an AABB-Tree for each of your meshes. (At the beginning of the level, when you load your meshes)

4. Transform mesh1 into mesh2's space.

5. For each triangle in mesh1 check in the AABBTree if it collides with a traingle in mesh2.

5a. If positive in AABBTree, check again with triangle-to-triangle intersection algorithm.

So the two algorithms you need to learn are:

1. AABBTrees, quadTrees, or Octrees. http://en.wikipedia.org/wiki/Octree

2. Intersection of two triangles. http://stackoverflow.com/questions/7113344/find-whether-two-triangles-intersect-or-not

However, if you have never implemented any of this before, it will take you over a month to get it right. In which case, my suggestion to you is:

1. Use bounding boxes instead of meshes for collisions.

or

2. Use a library.

If you are after simplicity you should consider representing the player with an ellipsoid so the core of your player-to-world interaction only requires an ellipsoid-vs-triangle detection routine. This type of simplification exists in even the most advanced engines and is ideal given the type of movement in games where the player controls a character (as opposed to a vehicle). If the character is animated then a bounding ellipsoid is computed for each frame of animation to prevent from arms, legs or whatever else from extending beyond the bounding ellipsoid. Here's a pretty good overview of how to get something like this up and running:

Improved Collision Detection and Response

Doing collision detection and response between polygon soups requires a lot of work. If you want to implement this with the least amount of code as possible you'll need a few different things:

1) A function that can detect when one triangle intersects another; Here's a good start on how to do that. Once you have this working detecting when a mesh collides with another is trivial; just compare each triangle against every other.

2) A way to detect the instant before a collision happens; this is called the time-of-impact or TOI. You can use a binary search over the time interval in conjunction with your mesh collider to find the TOI. Be warned: this type of things works much better (and faster) when your collision data is based on convex meshes (or assemblies of convex meshes if you need generality) and a GJK style detector.

3) Collision response! With the TOI in hand and hopefully some information about the type of contact made (vertex-to-face, edge-to-edge, edge-to-face, face-to-fact) you can back your object up to the TOI and then readjust it's velocity based on the contact information. For example, if a vertex made contact with a face then you want to project the object's velocity onto the plane of the face.

As you can see there is no miracle shortcut to accomplish what you want; you can cut corners for sure but it's going to take some work.

Efficient mesh collision detection is very complicated. You will have an easier time integrating the most complicated physics libraries then writing this yourself.

However, if you are feeling up to it, and would like to learn, here is what you do:

A: Slow and Naive Method:

For each two triangles in your game, check if they collide with each-other. (Find a triangle-to-triangle intersection method on the internet.)

B: You will very shortly realise that this will kill your CPU. So add a spatial indexer (AABB-Tree or Quad-Tree) to minimize the amount of checks:

For each pair of meshes, check with an AABB-Tree if they might be colliding before you check their triangles.

1. Consruct an AABB-Tree containing all of your meshes as boxes.

2. Find out roughly which meshes might be colliding with the help of the AABB-Tree.

2a. If positive in AABBTree, check again with triangle-to-triangle intersection algorithm.

C: This will be enough if your meshes are extremely simple, and rareley collide. If they are not extremely simple, you will need to add another layer of AABBTree on the meshes:

1. Consruct an AABB-Tree containing all of your meshes as boxes.

2. Find out roughly which meshes might be colliding with the help of the AABB-Tree.

3. Pre-process an AABB-Tree for each of your meshes. (At the beginning of the level, when you load your meshes)

4. Transform mesh1 into mesh2's space.

5. For each triangle in mesh1 check in the AABBTree if it collides with a traingle in mesh2.

5a. If positive in AABBTree, check again with triangle-to-triangle intersection algorithm.

So the two algorithms you need to learn are:

1. AABBTrees, quadTrees, or Octrees. http://en.wikipedia.org/wiki/Octree

2. Intersection of two triangles. http://stackoverflow.com/questions/7113344/find-whether-two-triangles-intersect-or-not

However, if you have never implemented any of this before, it will take you over a month to get it right. In which case, my suggestion to you is:

1. Use bounding boxes instead of meshes for collisions.

or

2. Use a library.

I had looked into the separating axis theorem, but I've had no luck implementing it, do you think what you described would be less resource hoggy than that? I had already decided to use a bounding box as a possible collision checker and then do the nitty gritty with mesh to mesh.

I had already decided to use a bounding box as a possible collision checker and then do the nitty gritty with mesh to mesh.

Did you add a spatial indexer ( tree ) for your bounding boxes? If you have many simple meshes to check then that should be the most important step.

Also, did you have look at the sub-link in stack-overflow: http://www.realtimerendering.com/intersections.html

It contains many implementations of different primitive collision checks that you can copy-paste.

I used one of them a while back. It was very good.

Regarding hogging resources, I'm not sure what you mean. There are three resources:

1. CPU performance.

2. Memory size. (having better indexes improve CPU but eat up memory).

3. Programmer time: You should use the simplest solution which is good enough.

So what I'm saying is: Decide where your problem is:

a. Do you have one moving mesh intersecting a static background mesh?

b. Do you have one moving mesh intersecting other moving meshes?

c. Do you have many moving meshes intersecting many moving meshes?

d. How complicated is each mesh? (Do you have a simplified physics model)

e. How much time do you have to implement all of this?

f. What kind of machine does this run on: Mobile/PC?

g. Do you need complex physics (you allready answered "no" but if you change your answer than the collision alogrithm requirements change).

I had already decided to use a bounding box as a possible collision checker and then do the nitty gritty with mesh to mesh.

Did you add a spatial indexer ( tree ) for your bounding boxes? If you have many simple meshes to check then that should be the most important step.

Also, did you have look at the sub-link in stack-overflow: http://www.realtimerendering.com/intersections.html

It contains many implementations of different primitive collision checks that you can copy-paste.

I used one of them a while back. It was very good.

Regarding hogging resources, I'm not sure what you mean. There are three resources:

1. CPU performance.

2. Memory size. (having better indexes improve CPU but eat up memory).

3. Programmer time: You should use the simplest solution which is good enough.

So what I'm saying is: Decide where your problem is:

a. Do you have one moving mesh intersecting a static background mesh?

b. Do you have one moving mesh intersecting other moving meshes?

c. Do you have many moving meshes intersecting many moving meshes?

d. How complicated is each mesh? (Do you have a simplified physics model)

e. How much time do you have to implement all of this?

f. What kind of machine does this run on: Mobile/PC?

g. Do you need complex physics (you allready answered "no" but if you change your answer than the collision alogrithm requirements change).

Here are the answers to your questions

a. yes

b. not currently but in the future perhaps

c. no

d. I plan to use 5-10 polygon meshes for collisions and physics

e. I have quite a bit of spare time, and its just a personal project, so quite a bit.

f. PC, specifically a mac (also using openGl)

g. Not particularly, basic collisions and gravity is all I can really see myself doing right now and in a large part of the future.

And I have taken a look at the link, but I haven't been able to make out most of what is in the polyhedra to polyhedra collisions.

Ok,

Assuming that you only have one mesh which moves, and that mesh intersects many other triangles. Like a man moving over terrain.

Then your solution is:

Index all of your static triangles in an AABBTree. Do not index the moving mesh.

Since you only have ~5 triangles in your single moving mesh, there is no need to index it, or any other meshes.

Since you are running on PC there is no need for you to save any RAM.

So assuming you have a man walking on a background mesh:

1. At startup index all of the background triangles in a Tree of your choice. (use Axis Aligned bounding boxes on each triangle). Since the background doesn't change, you only do this once.

2. For every frame of your game:

2a. Check every traingle in your man for AABB collisions with the tree. (assuming your man is very simple (less then 100 polys, this should not be a problem) )

2b. If any AABBs cross eachother, check triangle vs. triangle.

You do not need most of the shapes there, just triangle to triangle.

If you are using c++, I see that this link is still active: http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html.

Finding an octree implementation should be relatively simple.

Ok,

Assuming that you only have one mesh which moves, and that mesh intersects many other triangles. Like a man moving over terrain.

Then your solution is:

Index all of your static triangles in an AABBTree. Do not index the moving mesh.

Since you only have ~5 triangles in your single moving mesh, there is no need to index it, or any other meshes.

Since you are running on PC there is no need for you to save any RAM.

So assuming you have a man walking on a background mesh:

1. At startup index all of the background triangles in a Tree of your choice. (use Axis Aligned bounding boxes on each triangle). Since the background doesn't change, you only do this once.

2. For every frame of your game:

2a. Check every traingle in your man for AABB collisions with the tree. (assuming your man is very simple (less then 100 polys, this should not be a problem) )

2b. If any AABBs cross eachother, check triangle vs. triangle.

You do not need most of the shapes there, just triangle to triangle.

I see a lot of the triangle to triangle links in the table are broken. bummer it was an excellent resource.

If you are using c++, I see that this link is still active: http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html.

Finding an octree implementation should be relatively simple.

So test every triangle against every triangle for the 2 meshes? Thats seems pretty extreme. And because they are triangles, also in 2d space and are of a model, some could miss and others need to be tested so I would need to test until I have a collision, correct?

So test every triangle against every triangle for the 2 meshes? Thats seems pretty extreme. And because they are triangles, also in 2d space and are of a model, some could miss and others need to be tested so I would need to test until I have a collision, correct?

You missed a step (the octree).

Test the man-mesh vs the octree-of-the-background mesh.. It should reduce the amount of triangles you are checking by a whole lot. It's like the difference between inserting integers in a sorted array and the difference between inserting integers in a sorted tree. There's a world of difference here.

Assuming you have 100 triangles in your man mesh, and 1000,000 triangles in your backdrop. You would only be making 100*LOG8(1,000,000) axis-aligned-bounding-box checks ( much much simpler than triangle tests) . The remaining triangle checks should be relatively few (you only check the AABB tests that passed). So you will be making about 600-1200 simple checks instead of 100,000,000 complicated triangle tests.