Jump to content
  • Advertisement
Sign in to follow this  

Determining contact points in 3D collision detection

This topic is 4144 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm looking for a good explanation or resource of how to generate a complete set of contact points in a continuous 3D collision detection algorithm with spheres, capsules, AABBs and OBBs, colliding these with arbitrary convex meshes (for level collisions). I understand it's got to do with triangle-triangle intersections and that sort of thing but I don't know how it all fits together... Thanks for your help on this matter! :)

Share this post

Link to post
Share on other sites
basically create yourself a physics class

include a load of different functions in it such as a sphere colliding with a static sphere

a sphere colliding with a moving sphere

a cube colliding with a plane

etc etc etc

then have some tags somewhere on your objects to say what kind of bounding objects they use so that u can just pass the objects to your physics class and itll automatically handle it for you

obviously you will need to do some research into the best ways of colliding different objects etc, but this should give u a rough idea

Share this post

Link to post
Share on other sites
In broad generalisations, the contact point is defined by the point on the Minkowski sum the closest to the origin, that's assuming convex geometry.

That doesn't really help finding the points though :) but in general, it's the closest pair(s) of point(s) on the two surface, and if the objects are intersecting, the points that will provide the MTD (Minimum Translation Distance), that will push the objects away from each other so they do not intersect anymore.

Now, each case (sphere, capsule, triangle, box, convex hull) usually have a specific algo to find the contact points(s), but there is a general, 'do it all' algorithm for finding the contact point is the GJK algorythm, which is making use of the first principle. The algo is quite complex and has problems with some of the cases (not the algo itself, but the problem of innacuracies assossiated with floating point calculations). It's an approximation as well, it wont give you 'the' contact point(s), only something very very close to it, which is usually sufficient.

Well, what GJK will give you, and any other collision detection algo, will be the normal of the collision, the depth of intersection (both combined give you the MTD), and / or the time of collision.

The normal of collision can then be used to find the support points on the two surface. The support points are basically the points on the objects that provide a stable base along the normal of collision.

If you consider a ball sitting on a box, the normal of collision will be pointing up, the contact point on the ball will be the point at the bottom of the ball, and the support points of the box will be the 4 corners of the top face of the box. Those point define a polygon really. So usually, instead of talking about support pints, it's usually better to consider them as supporting 'feature'. These features can be either, a point, an edge, a polygon, or some parametric surface (for a cylinder, that could be a disk).

Then, these support points can be used to find the contact point, by doing a bit of volume clipping. In the case of a sphere on a box, it's simple. It's the support of the sphere, and the point on the top surface right under it.

If you consider two boxes (box A sitting on box B), one sitting on top of the other, you will get 4 support points a piece (one polygon each). The bottom face of box A, and the top face of box B.

To find the contact points, you 'clip' one polygon against another.

If you imagine the impossible case of a box B resting on a box A on a single edge, then you would get a face and a edge intersection. That case is even simpler, you just need to clip the edge with the face, to get the two contact points.

In the even more improbable case of a box sitting on another box, say, spinning on a corner, then it goes back to the sphere / face collision. It's just the corner itself, and the corresponding point on the face.

In the case of a cylinder, it will be hard to properly 'clip' a disc against a volume. So what you could do is apporximate the disk to a polygon, and use that polygon as your supporting feature.

GJK on the other hand, should provide you with a proper set of contact points without any messy surface approximation, whatever the surface. GJK in fact does the approximation itself. I broad terms, it's finding the local contacts by reducing the volumes to a tetrahedron, and keeps refining that tetrahedron until a feature of the tetrahedron (face, corner, edge) is found to be the feature the closest to the origin (point(0, 0, 0)). Using parametric coefficients, you can then derive the points on the two objects.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!