step after closest point detection??

Post Reply
Posts: 3
Joined: Sat Jan 28, 2006 9:07 am

step after closest point detection??

Post by lolito » Sat Jan 28, 2006 9:21 am

Hello (sorry for my bad english :oops: )

I m a beginner who try to make a simple simulator in physic (just with impulsion for the moment)

I ve implemented the algorithm of Vclip, it works fine and returns me the closest feature beetween two Object

With this two features i've got the closest points and the normal .

But the probem is that i ve just one contact point with this method.

So my problem is how to find all the contact point knowing the closest features??

I ve an idea but im not very sure:
_Compute the 2 convex hull(in 2D) of the point which are on" the separating plane"

_And Compute the intersection of this two convex hull

Can you tell me what to do , a paper ,an another way to do this ..

Thank you :)

User avatar
Erwin Coumans
Site Admin
Posts: 4101
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA

Post by Erwin Coumans » Sat Jan 28, 2006 5:12 pm

There are roughly 2 different ways you can tackle the contact manifold generation: incrementally, or at once.

For incrementally:
Basically you need a couple of things:

every collision step:

1) calculate a new closest point (vclip, or other algo like gjk)

2) check if this point is already in the contact cache.
2a) If you keep track of feature-id's, you can do this very efficient.y.
2b) Otherwise use the worldspace distance to check for equality (with a treshold).

3a) if the point exists do nothing
3b) if it is a new point, add it to the contact cache. preferably in local coordinates of both rigidbodies/shapes.

4) if the contact cache exceed some upper size, reduce.
4a) keep the point with the deepest penetration
4b) build some kind of heuristic to choose the points that approximate the 2d convex hull best.

5) after each integration, refresh the contact cache:
5a) calculate 2 new worldspace coordinates for each contact point, using the local coordinates in body A and body B, and the new transforms of each body.

5b) check if the contact is still valid, similar to using (2b).

You can see the sample implementation here: ... ource.html

There is some extra heuristic for step 4b and 5b in this implementation.
4b: quick appriximation by using triangle with biggest area
5b) take the projection onto the normal into account, so even when the distance between the two projections into worldspace exceed the maximum distance treshold, you keep it. This will allow to keep points that cause deeper penetrations. They still break on motion in the contact plane, orthogonal to the normal.

There is also a paper by Adam and Pierre from Novodex with some variations on this theme: ... draft9.doc

For 'at once', which only works if you got feature information like planes, vertices, edges (not for implicit shapes like sphere, cylinders etc).
I won't explain too much about this case. ODE uses this for box-box for example, but you can generalize this for convex-convex polyhedra.
You can find the two polygons that share the closest point, and that are most parallel (some heuristic here). Then clip all triangles from one polyhedron on this plane, and on the other polygons edges.

Posts: 3
Joined: Sat Jan 28, 2006 9:07 am

Post by lolito » Sun Jan 29, 2006 9:43 am

thank you for your help

I ll try to do what you say


Post Reply