Convex-Convex collision detection issues

[Suslik[PGS]]

Hello. I've implemented a convex-convex collision detection alghorithm it works right but too slow on relatively difficult geometries. And more than 99% of time takes finding the separating plane, using SAT. So I've found very interesting paper "Incremental Penetration Depth Estimation Between Convex Polytopes Using Dual-Space Expansion". It has all advantages I need:
- support of convex triangulated geometries
- almost constant working time in systems with high time coherence
- unnesessarity of huge additional data structures

but it has one serious disadvantage - it consists of many subalghorithms, and I have to implement ALL of them fast enought. For example the paper said that there is an alghorithm of finding directional penetration i O(log(n) * log(m)) so I've found paper with this solution, but it seems to be too complicated for me

So my questions are:
1) are there other alghorithms of finding directional penetration depth in less than linear time?
2) are there other incremental penetration depth estimation alghorithms that satisfy all my tree condidtions?

[Dirk Gregorius]

Have you seen this:

http://xenocollide.com

[Suslik[PGS]]

Have you seen this:

Interesting - no, i didn't. I think there are too few information about alghorithm's pros and cons. Especially its complexity. And are there any demos?

[Dirk Gregorius]

Man, this side opened just some days ago Gary Snethen works at Cyrstal and is a former colleague of Erin. They developed the engine for Tomb Raider. So personally I expect it to be of decent quality.

Besides this I suggest to ask questions about this algorithm on the associated webpage...

[Suslik[PGS]]

Besides this I suggest to ask questions about this algorithm on the associated webpage...

Done

But I wanted to listen for local specialists like Erwin, you know.

[Erwin Coumans]

You mean the DEEP , http://www.cs.unc.edu/~geom/DEEP ? I'm working with the author Young Kim, so if you have specific questions/issues I can bring them up.

Both DEEP and XenoCollide approximate a penetration depth, in a certain direction. This means the penetration direction they provide is not a global minimum. This can work well in practice, and in some cases having control over the actual penetration direction can be beneficial.

XenoCollide is very similar to GJK, using support mapping to specify objects. XenoCollide has the limitation that it doesn't calculate the closest distance, as far as I know, but it adds approximation for penetration depth. GJK needs a companion algorithm for this, such as EPA or sampling methods etc.

Bullet calculates the exact global minimum penetration depth using EPA, or approximates the global penetration depth using sampling methods. Both EPA and sampling probably meets your requirements too. One of the main costs in GJK/EPA is support mapping, which is typically O(n) in the number of vertices. However this n is usually very small for convex objects in games, say less then 100. For very complex convex objects, you can use Dobkin–Kirkpatrick hierarchy, which is O(log(n)). For convex objects in games with small n, the implementation and cache-access is often more important then time complexity.

Thanks,
Erwin

[Suslik[PGS]]

I've studied the XenoCollide alghorithm, It's pretty good, and I'm implementing it right now. But it's not exactly that, what I'm looking for. Any other ideas?

Note that I'm not looking for the general convex geom - convex geom CD alghorithm. Just polyhedra-polyhedra PD estimation technique.

[Dirk Gregorius]

Personally I could imagine that the following might be a nice combination. In this paper [1] a nice hybrid between LC and GJK for convex polygedra is described. What I like about the algorithm is that it returns the closest features which is nice to find the full manifold by using clipping. As GJK it seems only to work for disjoint shapes what requires some sort of margin. For the penetration solver I would use SAT then. Since we now know that the objects are intersecting it might be not necessary to search the global minimum, but do a quick local search. For contacts the major problem seems to be false positives.

Of course this would be restricted to convex polyhedra only. The support mapping approaches offer a wider range of possible shapes, but I see relatively few practical need in them since everything can be easily approximated as a polytope and you get some rolling resistance for free in the solver.


[1] http://citeseer.ist.psu.edu/707385.html

[Pierre]

You might find this useful: http://www.codercorner.com/blog/?p=24

[Dirk Gregorius]

Thanks Pierre. Very usefull indeed

[Suslik[PGS]]

You might find this useful: http://www.codercorner.com/blog/?p=24

Thanks, Pierre, but I already was there I've looked through the alghorithm you are using and it looks like you get rid of about half edges. Am I right?

By the way, there are a few cases when the actual and computed with "OptimizedAlgo" SATs do not coincide. That's strange.

[Pierre]

I've looked through the alghorithm you are using and it looks like you get rid of about half edges. Am I right?

Depends on the objects, and how deep the penetration is. It can be less than that or much more, really.

By the way, there are a few cases when the actual and computed with "OptimizedAlgo" SATs do not coincide.

If you see that in my small test, feel free to dump the object's poses and send them back. This is some new code that I just rewrote, I didn't use it before. So there might be some bugs.

- Pierre

[Dirk Gregorius]

Hey Pierry,

I looked through the code a bit more sorrowly today and I don't understand one aspect in PartialHull::AddEdge():

Code: Select all

bool PartialHull::AddEdge(const btVector3& axis)
{
	btVector3 RealAxis;
	if(axis.x()<0.0f)	RealAxis = -axis;
	else				RealAxis = axis;

        // Snip ....
}

What are the initial lines good for?

I also read the Readme and you write:

- precomputing projection values for face normals (results are already known for one object at least)
- culling features more aggressively

Can you elaborate a little bit more on these two?



And one final question. How do you compute the contact position for the edge cases from your example code? The two edges that build the axis of minimum separation must not necessarily realize the contact. So is there an extra step to find the "support edge" in the direction of the separating axis?

[Pierre]

What are the initial lines good for?

It makes sure a direction N and a direction -N are seen as the same axis. For example (0.5, 0.5, 0) should be the same as (-0.5, -0.5 ,0). I keep the one with a positive X only (this is arbitrary).

precomputing projection values for face normals (results are already known for one object at least)

The standard SAT test does 3 things:
- tests face normals from convex A
- tests face normals from convex B
- tests edge cross products from AxB

The thing is that we have to project both A and B on each of those axes. For the face normals, we can precompute the projection values for one of the convex, since we're projecting along its own normals.

culling features more aggressively

I only culled vertices/edges using the first thing that came to mind. It should be possible to do better

How do you compute the contact position for the edge cases from your example code? The two edges that build the axis of minimum separation must not necessarily realize the contact. So is there an extra step to find the "support edge" in the direction of the separating axis?

Yes, there is an extra step. The code in the test only computes the penetration vector, giving the same result as, say EPA. But contact generation is another thing entirely. Which is actually another big optimization: most of the time you don't really need to compute the penetration vector at all. At least we didn't in Novodex. It was only done once in a while.

- Pierre

PS: expect lags in future answers, going to Sweden tomorrow for some days!

[Dirk Gregorius]

Thanks for the reply.

I have some other questions:

Q1) Basically there are at least two ways to implement SAT. The first is to project the polytope vertices and check the intervals. This is what you are doing in your example. The second approach is to build a witness plane and test vertices against this plane. E.g.

Code: Select all

// We test the face normals from polytope 1:

for ( each face f in polytope1 )
  Vec3 S = polytope2->GetSupport( -f.Normal );
  
  float distance = f.Plane.GetDistance( S );
  if ( distance > 0 )
    // We found a separating axis

  if ( distance < min_distance )
    min_distance = distance;

I think the later approach can save quite some transforms (local coordinates ) and also save memory since I currently don't see that it would be necessary to precompute any projections since we don't need to project the vertices onto its face normals in this case as you suggest. What are your thoughts on this?


Q2) When we test the edges it is a necessary condition that the edges are "supports" in the direction of the cross product. When I test edge cases I choose the first polytope as my reference. Then I build the cross product and make sure that it points towards the second polytope. Next I validate that the edges are a "support edge" in the direction of the cross product (that means all vertices must lie behind a plane through the edge). Next I find the support point in the negative direction on the second polytope and compute the distance to the plane. I think a better way would be to use the Gauss Map and test whether the associated arcs intersect. E.g.:

Code: Select all

// Test all edge cross products

for ( all edges e1 in Polytope1 )
  for ( all edges e2 in Polytope2 )
    Vec3 n = cross( e1.Direction, 2.Direction );
    normalize( n );

    if ( n points *not* in direction of polytope2  )
      negate( n );

    // Test if the edges are supports
    if ( !polytope1->TestEdgeForSupport( e1,  n ) )
      continue;

    if ( !polytope2->TestEdgeForSupport( e2, -n ) )
      continue;

    Vec3 S = polytope2->GetSupport( -n );

    float distance = n * S - n * e1.Origin;

    if ( distance > 0.0f )
      // We found a separating axis

    if ( distance < min_distance )
      min_distance = distance;
    

The Polytope::TestEdgeForSupport() iterates over all vertices and test if the there are no vertices in front of a plane through the tested edge in the direction of the axis (e1.Direction x e2.Direction). These tests are quite inefficient and I would like to get rid of them. One alternativ would be (as already mentioned) to use the Gauss Map. Another downside is that I am testing directions several times. I only would like *unique* directions. Do you have other suggestions? Can you give an example how you would compute the edge contact as an extension to your code? Other ideas are welcome



Enjoy your stay in Sweden!

Cheers,
-Dirk