My approach to generalized convex CD

[Suslik[PGS]]

Hello

I've developed general Convex-Convex depth computation and contact manifold generation alghorithm. And want to share my results with you.

Here are the pros of my approach:
+ the alghorithm is iterative - the more iterations you choose, the more accurate will be the result
+ the alghorithm is completely incremental. Using coherence, it usually converges after less than two iterations
+ it builds all the contact manifold at time - i'm not persistent manifold fan
+ it uses only support mappings of two geometries
+ when the penetration isn't too deep, it converges in almost a constant time

It's cons
- too much space for optimization. There are too much vector normalizations and devisions
- the alghorithm hasn't been thoroughly tested yet - it may be sometimes unstable.
- as EPA, alghorithm "dislikes" too long geometries and converges slowr on them
- only convex geometries. it's quite common "con"

Screenshot:


You may see that there are 43 bodies in this scene and complete physics simulation step takes 2.5ms on Intel Core 2 Duo 2.4GHz, using only one core.

Thanks, Alex

[John McCutchan]

Why not share the details of your algorithm?

[Suslik[PGS]]

Actually the project is closed-source, so I may not share its code, but I may share its basic ideas:

Here is the pseudocode of my approach:

Code: Select all

bool ContactManifold::GetSeparatingAxis(Vector3 &separatingAxis)
//under separating axis I assume the direction of Penetration Depth vector
{
  //First of all we choose the initial axis
  //it may be the central difference or the axis form the previous iteration.
  separatingAxis = this->GetGeom2()->GetCenter() - this->GetGeom1()->GetCenter(); //
  //incremental part
  while(notFinished)
  {
    Vector3 point, normal;
    //we obtain the intersection of ray collinear to the current axis with CSO
    //In addition, we compute the normal vector at the point of intersection
    GetCSORayIntersection(separatingAxis, point, normal);
    //Then we update the current axis using the value of normal computed
    separatingAxis = normal;
  }
}

[John McCutchan]

I don't expect you to share code. But, I was hoping you would provide a cogent description of how your algorithm works, why it converges and how it is different than GJK and EPA.

thanks,
John

[Suslik[PGS]]

>But, I was hoping you would provide a cogent description of how your algorithm works, why it converges and how it is different than GJK and EPA.
I'm not too good at English, so it's very difficult for me to explain the theoretical proves why it converges.

In spite of the GJK or EPA, my alghorithm finds local minima, not global, but in most cases with small penetration depth they coincide.

[John McCutchan]

Could you try and compare your algorithm with XenoCollide. That might help you explain your ideas to us.

[Suslik[PGS]]

You may dowload its demos here (added local cached copy, admin)

Sorry, I don't have enough time right now. Tomorrow I'll try to inform you more about my tecnique.

[Xeno]

Minkowski Portal Refinement (MPR) provides an alternative to EPA for finding the minimum penetration depth.

To do this, I use XenoCollide (MPR using the vector between the center points as the origin ray) to find the first normal and contact point. I then iterate using MPR to find a new contact point and normal by using the previous normal as the direction of the new origin ray.

Over subsequent iterations, the new and previous normals will converge. Once they've converged, the normal represents the direction of least penetration and the distance from the contact point to the origin represents the minimum penetration depth.

For polyhedra, this converges precisely. For curved surfaces, an error tolerance needs to be set.

Based on your pseudo-code, I think you may have come up with the same technique. Does my description sound similar to your algorithm?

[By the way, this is also the technique I use for obtaining precise penetration depth along the direction of the contact normal found by XenoCollide -- but I only need one extra pass.]

[Suslik[PGS]]

Minkowski Portal Refinement (MPR) provides an alternative to EPA for finding the minimum penetration depth.
...
Based on your pseudo-code, I think you may have come up with the same technique. Does my description sound similar to your algorithm?

Yes, my approach is very similar to yours. But this alghorithm actually converges to local minima, not global. In most of common cases that doesn't matter, but there are a few stress-tests(like collision of a very long box along a small sphere), when the local minima isn't the same as global one. To find the intersection of a ray and CSO you are using MPR alghorithm. It's quite nice, but it converges in O(log(1 / precise * O(support_function_complexity))) - and my approach is iterative, so it converges in almost a constant time.

[Xeno]

Yes, my approach is very similar to yours. But this alghorithm actually converges to local minima, not global. In most of common cases that doesn't matter, but there are a few stress-tests(like collision of a very long box along a small sphere), when the local minima isn't the same as global one.

The algorithm I described also converges to a local minimum.

To find the intersection of a ray and CSO you are using MPR alghorithm. It's quite nice, but it converges in O(log(1 / precise * O(support_function_complexity))) - and my approach is iterative, so it converges in almost a constant time.

When you say that your approach is iterative, do you mean that it uses temporal coherence to begin the next frame with the search direction it used on the previous frame?

If we say that XenoCollide converges in O[ log(1 / precision) * O(support_function_complixity) ], then shouldn't we also say that your use of temporal coherence requires O(support_function_complexity) each frame?

[Suslik[PGS]]

The algorithm I described also converges to a local minimum.

When I said

this alghorithm actually converges to local minima, not global

I meant both mine and yours alghorithms, because act idenctically in outer loop. Outer loop - the loop, where we change current axis after determening its intersection with CSO in inner loop.

If we say that XenoCollide converges in O[ log(1 / precision) * O(support_function_complixity) ], then shouldn't we also say that your use of temporal coherence requires O(support_function_complexity) each frame?

Of course, it does. My alghorithm converges after O(1) iterations, each iteration costs O(support mapping).