Convex-Convex collision detection issues
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Convex-Convex collision detection issues
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?
- 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?
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: Convex-Convex collision detection issues
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?Have you seen this:
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Convex-Convex collision detection issues
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...
Besides this I suggest to ask questions about this algorithm on the associated webpage...
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: Convex-Convex collision detection issues
DoneDirk Gregorius wrote:Besides this I suggest to ask questions about this algorithm on the associated webpage...
But I wanted to listen for local specialists like Erwin, you know.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Convex-Convex collision detection issues
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
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
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: Convex-Convex collision detection issues
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.
Note that I'm not looking for the general convex geom - convex geom CD alghorithm. Just polyhedra-polyhedra PD estimation technique.
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Convex-Convex collision detection issues
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
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
-
- Posts: 67
- Joined: Mon Jul 25, 2005 8:56 am
Re: Convex-Convex collision detection issues
You might find this useful: http://www.codercorner.com/blog/?p=24
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Convex-Convex collision detection issues
Thanks Pierre. Very usefull indeed
-
- Posts: 30
- Joined: Fri Jan 04, 2008 1:51 pm
Re: Convex-Convex collision detection issues
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?Pierre wrote:You might find this useful: http://www.codercorner.com/blog/?p=24
By the way, there are a few cases when the actual and computed with "OptimizedAlgo" SATs do not coincide. That's strange.
-
- Posts: 67
- Joined: Mon Jul 25, 2005 8:56 am
Re: Convex-Convex collision detection issues
Depends on the objects, and how deep the penetration is. It can be less than that or much more, really.I've looked through the alghorithm you are using and it looks like you get rid of about half edges. Am I right?
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.By the way, there are a few cases when the actual and computed with "OptimizedAlgo" SATs do not coincide.
- Pierre
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Convex-Convex collision detection issues
Hey Pierry,
I looked through the code a bit more sorrowly today and I don't understand one aspect in PartialHull::AddEdge():
What are the initial lines good for?
I also read the Readme and you write:
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?
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 ....
}
I also read the Readme and you write:
Can you elaborate a little bit more on these two?- precomputing projection values for face normals (results are already known for one object at least)
- culling features more aggressively
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?
-
- Posts: 67
- Joined: Mon Jul 25, 2005 8:56 am
Re: Convex-Convex collision detection issues
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).What are the initial lines good for?
The standard SAT test does 3 things:precomputing projection values for face normals (results are already known for one object at least)
- 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.
I only culled vertices/edges using the first thing that came to mind. It should be possible to do betterculling features more aggressively
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.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
PS: expect lags in future answers, going to Sweden tomorrow for some days!
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Convex-Convex collision detection issues
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.
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.:
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
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;
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