Physics Simulation Forum


All times are UTC

Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Sat Jan 28, 2006 9:21 am 

Joined: Sat Jan 28, 2006 9:07 am
Posts: 3
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 :)

 Post subject:
PostPosted: Sat Jan 28, 2006 5:12 pm 
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 4041
Location: California, USA
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.

 Post subject:
PostPosted: Sun Jan 29, 2006 9:43 am 

Joined: Sat Jan 28, 2006 9:07 am
Posts: 3
thank you for your help

I ll try to do what you say


Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC

Who is online

Users browsing this forum: Baidu [Spider], Bing [Bot],, Exabot [Bot], Google [Bot] and 17 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group