How to create the contact manifold ?

[Erwin Coumans]

So, I guess the question here is how to combine a constraint-based simulation and a conservative advancement scheme based on TOIs. I assume that you would ignore TOIs from static constacts and only consider dynamic (colliding) contacts.

Time of Impact calculation and contact points generation can either be done in one go, or completely seperate. I tried both succesfully, however I handle them seperate in my current approach. Also I don't distinguish between colliding or static contacts.

In the algebraic approach (implementation of Redon's paper) based on relative screwing motion the time of impact is calculated for all feature pairs. This automatically gives all contact point at once. However one must be careful, because the contact points have a timestamp. If this timestamp is much later then the actual time of impact, the contactpoint are not valid at all.

As said before, I handle TOI calculation and manifold generation seperately. For the contact point generation stage I use tradional discrete collision detector (GJK) and a persistent manifold.

Basically the discrete collision detector adds one (or more) clostest point (or deepest penetration) to a persistent contact manifold. It keeps the existing points.
Every frame the contact points in the manifold get updated, and points that exceed the maximum distance are removed. When the manifold is full, and another point is added, the following strategy is used:
- keep points with deepest penetration
- keep the triangle with largest area

This works quite well for implicit convex, polyhedra and convex on concave. See Bullet demos and source for details. I dont handle the concave-concave case.

How do others create their contact manifold ? During the TOI calculation, or seperate ?

[Erin Catto]

Here's what I do for box-box collision:

1. Find the separating axis with minimum overlap. In this determination, I bias against edge-edge contact.
2. If the minimum axis is edge-edge, I just generate one point.
3. If the minimum axis is face-(vert | edge | face), I determine the reference face according to the minimum axis and the incident face on the other box. I then clip the incident face against the reference face. I then reduce the generated points to at most 4 using an approximate convex hull.

This algorithm can be extended to convex polyhedra. The problem is to determine the minimum axis quickly.

Erin

[kenny]

In my opinion stable and robust contact point generation is a topic that could use some attention. It is in my opinion largely neglected by people doing research in collision detection.

In my experience contact point generation is one of the major sources to unstable simulations. In my opinion temporal coherence seems to be the most vital property that a good contact point generation algorithm should have. By temporal coherence I mean that the trajectories of contact points should follow piecewise continuous paths. Similar requirement should be used on the contact normals. Some of the few methods described in the litterature results in nearly flickering contacts during smooth object motion.

I try to exploit caching and I often use pseudo normals of surfaces (angle weighted normals seem to work quite nice for polygonal objects).
Contact reduction algorithms do, in my experience, often add more trouble than they are worth, simply because the book-keeping can be quite expensive. For algorithms such as GJK or VCLIP I have succesfully applied recursive search methods for generating contacts. This works well for polygonal objects. For primitives I usually apply case-analysis. Objects represented by implicit surfaces I use simple sampling and inside outside testing. BVHs are a bit tricky due to the risk of multiple reported contacts (neighboring triangles share edges). Edge-edge contacts seem to be important for rigid bodies, but not very important for deformable objects.

[Erwin Coumans]

In my opinion stable and robust contact point generation is a topic that could use some attention.

I agree, its once of the reasons to set up this forum. continuous collision detection is another one, and all the extra bits that are hardly spoken out

For algorithms such as GJK or VCLIP I have succesfully applied recursive search methods for generating contacts. This works well for polygonal objects.

In Bullet, I use one generic approach which works well for implicit and polyhedral objects, but it relies on some tresholds (mainly welding treshold and breaking contact treshold).

Could you go into more detail what you mean by 'recursive search method' ?

For primitives I usually apply case-analysis.

Can you describe this case analysis ? And how would you handle implicit cylinder rolling or resting on a cone, or a cone resting on a triangle ?

[kenny]

Could you go into more detail what you mean by 'recursive search method' ?

It is essentially a tandem neighborhood search of features. Initially seeded at a feature pair making up the ``first'' principal contact.

Look at work done by Joukhada, Laugier and Sundaraj, that will give you the basic idea.

Can you describe this case analysis ?

It depends on the types of geometries. I guess the most simple example is that of a point and triangle testing. You start by figuring out wheter the projected point lies inside the edges or if it lies outside then the closest edge/or vertex. One the closest edge or vertex is found you have all the information you need.

Another case would be cylinder point test. First project the point onto center line of cylinder, then figure out if point lies inside end caps or outside. If inside end caps then test distance to line bla bla bla and so on.

The case-analysis idea extend straigthforwardly. The SAT testing can be seen as a case analysis.

And how would you handle implicit cylinder rolling or resting on a cone, or a cone resting on a triangle ?

Cylinder and cones sucks, they have curved surfaces and edges (yielding infinitely many contacts:-). I would probably use capsyles instead of cylinders. A capsyle is basically a line segment and two spheres. I haven't really considered a cone.

There is an inherent complexity limit on the geometries that are easily dealt with using case-analysis. If things get too complicated it is often easier to use something like GJK.

To device algorithms for case analysis I have from time to time found it very helpfull and instructive to think in terms of external voronoi regions. Once you have a good understanding of these, you simply need a method to prune away external voronoi regions, which are of no interest.

[Erwin Coumans]

To device algorithms for case analysis I have from time to time found it very helpfull and instructive to think in terms of external voronoi regions. Once you have a good understanding of these, you simply need a method to prune away external voronoi regions, which are of no interest.

I agree. I'm using the voronoi idea (inspired by Christer Ericson) inside the sub distance algorithm of GJK, as an alternative to Johnsons' determinant method.

By the way, doesn't Mirtich not have a patent in that area of using voronoi regions in collision detection ?

But Kenny,

There is an inherent complexity limit on the geometries that are easily dealt with using case-analysis. If things get too complicated it is often easier to use something like GJK.

I don't get it. If I follow your recipy for the following case:

Take a few implicit primitives, things get complicated (sorry),
So instead of case analysis you revert to GJK as you told.
But this only gives you one point. How do you get a stable situation with just 1 point ?

That's exactly why I have worked on this contact manifold generation and reduction on top of GJK. And I'm very curious what alternative others have for implicit difficult cases.

[Erwin Coumans]

Here's what I do for box-box collision:
1. Find the separating axis with minimum overlap. In this determination, I bias against edge-edge contact.
2. If the minimum axis is edge-edge, I just generate one point.
3. If the minimum axis is face-(vert | edge | face), I determine the reference face according to the minimum axis and the incident face on the other box. I then clip the incident face against the reference face. I then reduce the generated points to at most 4 using an approximate convex hull.
This algorithm can be extended to convex polyhedra. The problem is to determine the minimum axis quickly.

I've heard such approach first mentioned by John Nagle, in this thread:
http://groups.google.co.uk/group/comp.g ... 17f95d39db

This works for polyhedral objects, so you tesselate your cylinders and cones ?

[Erin Catto]

I think tesselation is not a bad thing. You automatically get rolling resistance. This was done with barrels in Half Life 2.

[kenny]

By the way, doesn't Mirtich not have a patent in that area of using voronoi regions in collision detection ?

Actually I think Lin-Canny predates him on using external voronoi regions.

But Kenny,

There is an inherent complexity limit on the geometries that are easily dealt with using case-analysis. If things get too complicated it is often easier to use something like GJK.

I don't get it. If I follow your recipy for the following case:

Take a few implicit primitives, things get complicated (sorry),
So instead of case analysis you revert to GJK as you told.
But this only gives you one point. How do you get a stable situation with just 1 point ?

I was simply making the point that if you have too many cases you need to search through in a brute force manner. Maybe you are better of with a method that works on general geometries.

Using GJK you would need a post-processing phase for contact determination.

For implicit objects you do not have an explicit surface, so you need some way to detect the surface.

That's exactly why I have worked on this contact manifold generation and reduction on top of GJK. And I'm very curious what alternative others have for implicit difficult cases.

There is a paper from siggraph 93 which deals with the problem of implict representations

http://www.gg.caltech.edu/papers/collideabstract.html

[Erwin Coumans]

I think tesselation is not a bad thing. You automatically get rolling resistance. This was done with barrels in Half Life 2.

Interesting. So how do you deal with all the contact points ? For a cylinder you can easily get loads. Do you have a post-processing stage to reduce them ? If so, how do you do this ?

[Erin Catto]

The Novodex guys describe how to find an approximate convex hull for the contact manifold in their Game Programming Gems 4 article. Basically you find the min-max contact points along two orthogonal axes in the contact plane.

I use a simlar technique so that a table with four boxes for legs only gets four contact points, even on a highly tesselated mesh. This turns out to be quite cheap and gives a great performance boost in the solver.

Also, remember that the rendered mesh on a barrel can be smoother than the collision.

[Stephane Redon]

How do others create their contact manifold ? During the TOI calculation, or seperate ?

In my case during the TOI calculation. Then contacts are maintained or not from one step to the other based on the small positive distance between the contact features. Nothing fancy .

[Erwin Coumans]

In my case during the TOI calculation. Then contacts are maintained or not from one step to the other based on the small positive distance between the contact features. Nothing fancy .

sounds quite fancy to me though. Because how do you deal with the 'timestap' of the contacts ? During the TOI calculation, the TOI assumably gets smaller and smaller, and all the time contact points are collected, each with a different time stamp.
So I'm probably intested in your filtering scheme.

Also, at which distance is the contact created, given your 3 epsilons in the french thesis or english http://www.inrialpes.fr/i3d/people/redo ... al2004.pdf

Eb, Es, Er or exactly at the isosurface where the distance equals 0.
If the latter, I tried this, and the TOI is not robust anymore. Somehow the contacts needs to be at least distance 'Er' ?

[Stephane Redon]

In my case during the TOI calculation. Then contacts are maintained or not from one step to the other based on the small positive distance between the contact features. Nothing fancy .

sounds quite fancy to me though. Because how do you deal with the 'timestap' of the contacts ? During the TOI calculation, the TOI assumably gets smaller and smaller, and all the time contact points are collected, each with a different time stamp.
So I'm probably intested in your filtering scheme.

Also, at which distance is the contact created, given your 3 epsilons in the french thesis or english http://www.inrialpes.fr/i3d/people/redo ... al2004.pdf

Eb, Es, Er or exactly at the isosurface where the distance equals 0.
If the latter, I tried this, and the TOI is not robust anymore. Somehow the contacts needs to be at least distance 'Er' ?

Yes, you never reach a perfectly contacting state, you just get close. Say you're looking for collisions in [0,1]. At some point of the detection you find one collision at 0.7. It's the first collision in the interval, so you keep it. Then you find one at 0.6995. Because the time difference is less than a threshold you keep both contact points. If then you find a collision at 0.3, you only keep this new one. If you don't find a new collision, you keep both 0.6995 and 0.7. That's the detection part.

Then, you position the objects, thanks to the motions used for collision detection, slightly before the first impact, say 0.699. At that point, the contacts are necessarly at a strictly positive distance, because the objects were slightly separated at the previous time step. You then do a check for repositioning (i.e. you slightly separate the objects if one contact distance is less than Er). In the end of this step "detection - potential repositioning", the objects are slightly separated and you can go to the next time step. With constraint-based dynamics, these contact points will not be re-detected at the next time step (well, sometimes it happens, if you use explicit linearized constraints which are valid at the beginning of the time step only).

[Erwin Coumans]

Thanks Stephane,

There are still quite a few unknowns that one has to solve for a working implementation:

- how do you determine the distance of the contact points ? Do you use discrete collision detection for that ? Or do you update the distance incrementally ?

- do you convert 'distance space' into 'time-of-impact' space ? Do you use linear+angular velocity for that ? And do you project this on the seperating axis ?

Another problem: for example for a featurepair vertex-face:
If a vertex is approaching 'almost' parallel to the face, the location of the contact might vary a lot, even for small differences in distances in the face-normal direction.

How do you deal with that ?