Triangular Mesh Collision/ Resolution

Question

I've been trying some different approaches for collision detection and now I want to try to implement simple Mesh-Mesh collision detection for triangular meshes. I'm wondering if I'm on the right track, or if I'm missing something critical.

My general idea for collision detection involves a moving object with no rotation, against stationary objects. I also want the moving objects to slide across the surface/ edge of stationary objects in which they collide. The algorithm is:

• Make a list of all the stationary objects which are in range of the moving object origin.
• Add to the list of all the stationary objects which are in range of the displaced moving object
• Sort the list by shortest distance to the moving object origin.
• Iterate through the list and detect collisions between the displaced moving object and stationary object
  • find the shortest distance in which a vertex of the moving object passes through a triangle of the stationary object (or vice versa).
  • find the shortest distance in which an edge of the moving object passes through an edge of the stationary object.
  • If shortest distance was vertex
    • Project the displacement across the broken triangle plane and locate the end point.
    • Recalculate the displacement using this end point and the origin
    • Restart iterations
  • If shortest distance was vertex
    • Project the displacement across the plane created by these two edges at the point of contact. Find the end point of this projection
    • Recalculate the displacement using this end point and the origin
    • Restart iterations
  • If no collisions found then continue iterating
• Apply final displacement to position of the moving object

The reason the iteration is repeated after a collision is found is to avoid the case where the resolution causes a new collision in previously checked objects.

---

To get the vertex and edge intersections I have made two equations, both of which have M as the displacement I wish to apply to the moving object.

All capital variables are Vec3's, Two capitals next to eachother are deltas AB == B - A. lowercase variables are scalars. Mat3's take Vec3's as columns

This is my equation for testing a moving vertex against a stationary triangle:

//Ray: 
P = M*t + Q
//Trianlge: 
P = A + AB*u + AC*v
//Ray-Triangle Intersect: 
M*t + Q = P = A + AB*u + AC*v
AQ = -M*t + AB*u + AC*v
AQ = Mat3(-M, AB, AC*v) * Vec3(t, u, v)

Vec3(t, u, v) = Mat3(-M, AB, AC*v)^-1 * AQ

t, u, v must all be [0,1], and u + v <= 1 for a collision to occur

This is my equation for testing a moving edge against a stationary edge:

//Moving Ray:
P = AB*u + M*t + A
//Stationary Ray
P = CD*v + C
//Moving Ray - Ray Intersect
AB*u + M*t + A = CD*v + C
AC = M*t + AB*u - CD*v
AC = Mat3(M, AB, -CD) * Vec3(t, u, v)

Vec3(t, u, v) = Mat3(M, AB, DC)^-1 * AC

t, u, v must all be [0,1] for a collision to occur

---

So how does this look?

Answer 1

Are you on track, yes no maybe.

Figuring collision sets (moving vs. stationary) is helpful, but will not bring you far. If you implement a general NxM solution that is efficient you may actually get more bang for your buck.

For starters you should separate your collision detection from your collision response. This makes sense since you may want to collide different shapes, but the actual response is the same.

For the collision repose you implement a spring system (rigid body physics?). If the moving body overlaps with a static object (any body overlaps with any other body), you apply a force along surface normal to separate the two again.

The collision detection on the other hand is quite involved. Before we look at the nitty gritty details, we need to talk about early discarding collision detection. Here you want bounding boxes or bounding spheres. Spheres are really sexy, since they are dirt cheep to test collision on (length(o1 - o1) < r1 + r2). If the bounding volumes do not intersect, no need to test collision on the meshes.

If you want to handle a really large amount of objects it may be advisable to additionally use a special organisation structure, such as an octtree. The even prevents testing the bounding volumes of objects that are not even in the same general area.

Now that we have determined that the bounding volumes intersect, we can start to test meshes. In the naive approach you basically test each triangle with each other. This can be optimized further, such as storing spatially organized lists, but that may be overkill.

The actual triangle / triangle intersection is quite well understood. For example this algorithm is quite efficient. The basic approach is to intersect the two planes the triangles are in and then looking if the points where the triangles "start" and "end" on the line overlap.

I have not extensively checked your math but it looks sane at first glance.

Then again, why are you not using a physics library for this, like ODE or Bullet? If you absolutely do not want to use the ridgid body physics implemented there you can only use collision subsystem.