View Full Version : Help Developing Surface Collision detection system

08 August 2003, 08:32 PM
I've been reading as much as possible on collision detection and so far I've only been able to enable impliment Sphere collision detection (and thats was quite easy todo).

I've been reading but all I seen are articles on triangles for collision but what about quads as well?

08 August 2003, 06:15 PM
You've probably already seen these basic tutorials, but in case you havent....

As for quads, couldn't you triangulate the mesh in your code first? I could be wrong, but I got the impression most collision detection engines work that way. Someone else might have better info.

08 August 2003, 03:28 AM
Wow this is great man! i never seen this ^_^.

The reason was is becuase someone might want to use sub-d on a mesh. but o well ^_^ its more then enough to get me started

08 August 2003, 01:29 PM

The reason everyone talks about tris instead of quads is because _all_ non-degenerate triangles are guaranteed to be planar (i.e. flat), convex, and have a well-defined normal. This means that the surface is simple to work with (mathematically) and well defined.

The problem with quads is that _in general_ they are neither flat nor convex, both of which make the mathematics much more complex.

So, for collision detection, convert quads into tris.

To get you started, here is a simple (but not efficient) method for detecting whether two closed _convex_ objects A and B are colliding:

collision = false;
For each vertex v in A, {
front = false;
For each triangle t in B {
Calculate signed distance of v from plane of t
If distance is positive, v is in front of t, and is thus outside of object. Set front = true and break out of inner loop.
If front is false then v is behind all triangles in B, so it's inside B, hence A and B are colliding, set collision = true, and break out of outer loop.

collision is now true or false as appropriate...

Note that this on its own is not foolproof, because it only checks whether the vertices of A are within the object B, so it doesn't detect the case of B being totally enclosed by A, for example.

A simple (again, not efficient) solution for this case is to check for a collision between A and B, and if it reports no collision, then check B against A. If either of these report a collision, then you have a collision.

This still isn't perfect though because you can get intersections between objects without any vertices from one object being inside another. For example, think of two planes, rotate one 90 degrees, then push them together along their shared axis. Each plane pierces the other, but neither has a vertex within the other (By the way, for collision detection, you should treat a plane as two back to back surfaces to give you a closed object.)

To fix this, you need to check edges against triangles, instead of vertices against triangles. To do this, instead of calculating distance of a vertex from the plane of each triangle, you need to calculate the distance of the edge. If the edge passes through the plane, then you need to calculate the point at which it does this, and then determine whether that point is contained within the triangle.

Once you've done that you should have the ability to accurately detect collisions between arbitrary closed _convex_ objects (unless there's some case I've forgotten...).

To deal with potentially convex models, one approach is to split the object up into a set of convex pieces, and run the test against each of them.

As you've probably gathered, collision detection can get quite complex, and fast collision detection even most so.
If you are interested in learning about this though, I'd recommend trying to implement the algorithm(s) I've described above as a starting point.

Hope this is useful.

Cheers - Steve

08 August 2003, 02:32 PM
Do a google search on intersections, this will turn up some useful code.

Consider adding simplified detections to your code; Checking bounding boxes or bounding spheres first will speed up your code a lot.

08 August 2003, 02:46 PM
Good point Stew.

Because accurate collision detection is computationally intensive, it's well-worth doing a quick bounding sphere or box test first to check whether there's any chance at all of them colliding. Most of the time there won't be a collision, and this saves you from doing the proper test.

Cheers - Steve

CGTalk Moderation
01 January 2006, 09:00 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.