Triangle to triangle collision detection in 3D

Question

I understand triangle to triangle collision detection betwheen 2 triangles. Can someone explain how could I use this with a 3D object made-up of 1000s of vertexes? How can I create a list of triangles for each Mesh? Do I have to take every permutation of vertexes? That would lead up to O(n^3) which I find very bad.

How can I generalise this?

I will require to read data from a format. If all else fails, can someone suggest a format that makes the Mesh from triangles? I would also need a catalog of Meshes for the format, at least for starters.

Thanks very much.

Answer 1

There are lots of optimizations you can apply to detecting collisions between meshes:

• Space partitioning, as described by James.

• Early rejection using bounding volumes. For example, sphere–sphere collision is cheap, so before testing whether meshes A and B collide, you might see if a sphere surrounding A collides with a sphere surrounding B. If the spheres miss, obviously the meshes can't collide, so no need to test them. Different kinds of objects might need different kinds of bounding volumes: axis-aligned cuboids and cylinders are common.

• Caching of witnesses. In some collision tests you end up computing a "witness" to the collision, for example when you apply the separating axis test you compute a separating axis. If an axis separates two objects at time t, it's likely that it continues to separate them at time t + δ, so it can pay to cache the axis you found and try it first next time (see Rabbitz, "Fast Collision Detection of Moving Convex Polyhedra" in Graphics Gems IV).

Answer 2

http://en.wikipedia.org/wiki/Binary_space_partitioning

A BSP tree is a very efficient way of checking collision of static meshes, but it does require some preprocessing of the mesh to make sure no triangles intersect. It works by partitioning the mesh into half-spaces. This makes collision checking and physics easier.

EDIT:

I feel as though I should also mention the Octree. Same general idea as the BSP tree but it partitions the model into recursively smaller cubes instead of half-spaces.

http://en.wikipedia.org/wiki/Octree

In answer to your second question, something like the .obj file format might be what you are looking for.

http://en.wikipedia.org/wiki/Wavefront_.obj_file