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
My approach to generalized convex CD
-
- Posts: 133
- Joined: Wed Jul 27, 2005 1:05 pm
- Location: Berkeley, CA
Re: My approach to generalized convex CD
Why not share the details of your algorithm?
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: My approach to generalized convex CD
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:
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;
}
}
-
- Posts: 133
- Joined: Wed Jul 27, 2005 1:05 pm
- Location: Berkeley, CA
Re: My approach to generalized convex CD
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
thanks,
John
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: My approach to generalized convex CD
>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.
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.
-
- Posts: 133
- Joined: Wed Jul 27, 2005 1:05 pm
- Location: Berkeley, CA
Re: My approach to generalized convex CD
Could you try and compare your algorithm with XenoCollide. That might help you explain your ideas to us.
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: My approach to generalized convex CD
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.
Sorry, I don't have enough time right now. Tomorrow I'll try to inform you more about my tecnique.
-
- Posts: 4
- Joined: Sat Feb 16, 2008 1:44 am
Re: My approach to generalized convex CD
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.]
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.]
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: My approach to generalized convex CD
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.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?
-
- Posts: 4
- Joined: Sat Feb 16, 2008 1:44 am
Re: My approach to generalized convex CD
The algorithm I described also converges to a local minimum.Suslik[PGS] wrote: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.
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?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.
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?
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: My approach to generalized convex CD
When I saidXeno wrote:The algorithm I described also converges to a local minimum.
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.Suslik[PGS] wrote:this alghorithm actually converges to local minima, not global
Of course, it does. My alghorithm converges after O(1) iterations, each iteration costs O(support mapping).Xeno wrote: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?