Convex-Convex collision detection issues

Please don't post Bullet support questions here, use the above forums instead.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Convex-Convex collision detection issues

Post by Dirk Gregorius »

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).
Hmmm, don't you change the direction of the edge this way? Obvioulsy (-0.5, 0.5, 0) is *not* the same direction as (0.5, 0.5 ,0). Actually they would be orthogonal. Maybe Suslik can try if this resolves the problems where the reference and optimized implementation don't yield the same results.
Pierre
Posts: 67
Joined: Mon Jul 25, 2005 8:56 am

Re: Convex-Convex collision detection issues

Post by Pierre »

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?
I never saw your second version, only the first one with projected intervals. But I think what I said about "precomputing a projection value" is equivalent to your second method. For each face of polytope1 you have a precomputed plane equation (f.plane). In my case I have a face normal and the "precomputed projection value"... which I think would be the same as the "d" coefficient in your plane equation. I think it's just two different ways to look at the same thing.
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
This is just a very different way to implement this, that I didn't see before. I don't do any of that, not sure if it's good or bad :)

I think I do the part where you negate(n) only once, in the end, on the final penetration vector.

TestEdgeForSupport... Well, I just don't do it. If it's a slow operation as you say, it's unclear to me whether it saves any time overall. "GetSupport" seems like an equally expensive operation, so I don't see big gains there. I mean, you have:

- 2 "TestEdgeForSupport" calls
- 1 "GetSupport" call
- potential early exits

VS

- 2 "GetSupport" calls
- no early exits

No clear winner...

Needless to say (but I'll mention it just in case), for complex shapes there are multiple ways to optimize the "GetSupport" calls, with small precomputed tables, hill climbing, etc. For small shapes though, brute force is usually better.
Another downside is that I am testing directions several times. I only would like *unique* directions
Yeah, the "AddEdge" function in my code does this filtering. Not really smart or anything but works ok.
Hmmm, don't you change the direction of the edge this way? Obvioulsy (-0.5, 0.5, 0) is *not* the same direction as (0.5, 0.5 ,0).
Certainly, but my example was (-0.5, -0.5, 0) and (+0.5, +0.5, 0) :)
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Convex-Convex collision detection issues

Post by Dirk Gregorius »

Hey Pierre,

thanks for the reply. Can you maybe sketch how you would build an edge contact after you have identified that the axis of minimum separation is the cross product between edge directions? Obviously you cannot just build the closest approach between the edges you store in the partial hull, since the edges in contact might be parallel ones that were filtered out.


Cheers,
-Dirk
Pierre
Posts: 67
Joined: Mon Jul 25, 2005 8:56 am

Re: Convex-Convex collision detection issues

Post by Pierre »

Well, for me there's no difference between an "edge contact" and another kind of contact. The separating vector is used as a "witness" vector to pickup two convex polygons, one from each object. Those polygons are clipped against each-other, and that's where the real contacts are coming from.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Convex-Convex collision detection issues

Post by Dirk Gregorius »

Interesting idea. So how do you pick-up the two convex polygons (faces) from each object? Do you find the "support face" in the direction of the witnesss axis or do you choose the face whose normal is the most parallel to the this witness axis? The support face could be found by projecting the geometric centres of the convex polygons onto the witness axis - similar to finding support points.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Convex-Convex collision detection issues

Post by Erin Catto »

Pierre, thanks for you contribution. This is a very interesting and important topic for game physics development.

I noticed with your demo much of the performance gains are due to multiple parallel axes being collapsed into a single test. This makes the gain much higher than it would be for more general polytopes. Still, I agree that this is an important optimization.

Some other optimizations are possible. When checking a face on polytope A, you can easily store the offset of the face plane. Then you only need to compute the supporting vertex on polytope B in the opposite direction. You essentially stated the same thing already.

More significant gains can be made in the edge-edge case. If you store the faces that are adjacent to each edge then you can examine the face normals on the Gauss Map (normals on the unit sphere). On the unit sphere the faces become points (single normal) and vertices become faces (a region of possible normals). I won't get into details, but you can check the edge pair on the unit sphere and determine if they could possibly form a face on the Minkowski sum. If they don't form a Minkowski face then the edge pair can be skipped. If they do form a Minkowski face then the separation can be found computing the signed distance between the edges. This is a O(1) cost per edge pair.

See this paper for more information on the Gauss-Map:
Collision Detection of Convex Polyhedra Based on Duality Transformation, by Yi-King Choi, Xueqing Li, Wenping Wang, Stephen Cameron

Looking at EPA, it seems like a very effective way of doing SAT culling. It does a global search while excluding big chunks of the Minkowski sum. It should be possible to extract feature information from EPA, making it functionally equivalent to SAT.

I'm curious about your SAT optimizations. Did you ever get it to be faster than EPA?
Pierre
Posts: 67
Joined: Mon Jul 25, 2005 8:56 am

Re: Convex-Convex collision detection issues

Post by Pierre »

or do you choose the face whose normal is the most parallel to the this witness axis?
Something like this, yes. I'd have to check the code again but IIRC it was a bit hacky.
I won't get into details, but you can check the edge pair on the unit sphere and determine if they could possibly form a face on the Minkowski sum.
Do you do this using section 4.3 in aforementioned paper? In other words, do you only need to check that the arcs cross each-other on the sphere? Seems simple enough.
If they don't form a Minkowski face then the edge pair can be skipped.
So: if they don't cross (O(1) test), I can skip the edge pair? I definitely have to try this :)
If they do form a Minkowski face then the separation can be found computing the signed distance between the edges.
I don't care much about the separation -distance-. I only care about the separation -direction-. Can it be computed as well?
Looking at EPA, it seems like a very effective way of doing SAT culling. It does a global search while excluding big chunks of the Minkowski sum. It should be possible to extract feature information from EPA, making it functionally equivalent to SAT.
Yeah, although if I had EPA I wouldn't need SAT :)
I'm curious about your SAT optimizations. Did you ever get it to be faster than EPA?
I don't know, I never found a working version of EPA. I briefly tried Solid 3.5 at some point but it just never worked in a reliable way. I didn't have time to investigate the issue properly or re-implement it myself (management needed "convex collisions for yesterday"), so I went for the easiest route - SAT. And then I got caught in the SAT code and spent time optimizing it instead of starting other approaches.

I'd say EPA is probably faster. In my case the trick was that I usually don't compute the penetration distance/vector anyway, it only happens from time to time, rather than each frame. So the performance impact of SAT or EPA was spread over multiple frames, making it less of an issue. I think EPA is probably faster for complex shapes, and SAT might win on simple ones.

- Pierre
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Convex-Convex collision detection issues

Post by Erwin Coumans »

Pierre wrote: I never found a working version of EPA.
Bullet should have a working version of EPA.

The problems you mentioned before have been fixed in the past, and your cylinder-cylinder EPA repro has been included as Bullet demo. It seems to work well enough for games, and there has been no report of Bullet EPA not working.

Perhaps you were not aware those issues were already fixed? What cases do not work for Bullet's EPA implementation?
Erwin
Pierre
Posts: 67
Joined: Mon Jul 25, 2005 8:56 am

Re: Convex-Convex collision detection issues

Post by Pierre »

I don't remember if I tried the fixed version, Erwin. But what do you mean with "well enough for games" ? If you mean it breaks in case of deep penetration, then it still "doesn't work" for me (as I don't have a special case for deep/shallow penetrations).

I could still benchmark it though.

- Pierre
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Convex-Convex collision detection issues

Post by Erwin Coumans »

Pierre wrote:But what do you mean with "well enough for games" ? If you mean it breaks in case of deep penetration, then it still "doesn't work" for me
Bullet EPA should be good enough for games, but I would not recommend it for risky business, such as surgical operations etc.

Bullet EPA should work fine for deep penetrations, based on my own experience and because it has been tested for about 1.5 years by many users.
I could still benchmark it though.
Apart from a Cell SPU port, it hasn't been optmized fully, because it hardly gets called. I agree with you and expect EPA only to be faster for complex convexes, so a fair benchmark should test both simple and complex meshes. In Bullet, GJK catches most penetrations. Just make sure to use it in combination with btGjkPairDetector. You can check your own Bullet\Demos\EPAPenDepthDemo\PenetrationTestBullet.cpp for usage.

Thanks,
Erwin
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Convex-Convex collision detection issues

Post by Erin Catto »

Pierre wrote:I don't care much about the separation -distance-. I only care about the separation -direction-. Can it be computed as well?
Yeah, it is just the edge-edge cross product. Getting the sign is tricky. I chose the sign according to the vector connecting the two centroids.

So the edge-edge test is O(1) pass or fail. This is good because there are a lot of edge-edge tests. I used the quad-edge data structure to make this work.

I'm guessing you only perform the SAT when there is a large change in the relative transform? Or do you just continue with the same features until clipping fails to return a point? Another possibility is to check the cached separating axis. If it hasn't gone deeper then it is still good.
Pierre
Posts: 67
Joined: Mon Jul 25, 2005 8:56 am

Re: Convex-Convex collision detection issues

Post by Pierre »

Yeah, it is just the edge-edge cross product.
Oh, yeah, of course, silly me. I was stupid when saying I don't care about the distance, I of course need it, if only to compare against the other ones. Maybe I should stop doing N things at the same time :)
Getting the sign is tricky. I chose the sign according to the vector connecting the two centroids.
I do the same.
So the edge-edge test is O(1) pass or fail. This is good because there are a lot of edge-edge tests. I used the quad-edge data structure to make this work.
Great to know it works! I will definitely try that when I have some time (I'm not doing much physics those days)
I'm guessing you only perform the SAT when there is a large change in the relative transform?
Yes.
Or do you just continue with the same features until clipping fails to return a point?
If clipping fails I force a SAT computation for this frame, but simply waiting until it fails didn't work for me.
Another possibility is to check the cached separating axis. If it hasn't gone deeper then it is still good.
Didn't try that.

- Pierre
Pierre
Posts: 67
Joined: Mon Jul 25, 2005 8:56 am

Re: Convex-Convex collision detection issues

Post by Pierre »

I noticed with your demo much of the performance gains are due to multiple parallel axes being collapsed into a single test.
Ok, I quickly tried the crossing-edges test and I got mixed results. It seems to work, but only if I disable the optimization above. However, without this optimization, the code is not as fast as before. For some reason it seems I can't mix the two optimizations. Not sure why, no time to really investigate.

For what it's worth here's the quick-and-dirty edge test. Might be bugs somewhere, it's just a super quick attempt because I couldn't resist :)

Code: Select all

__forceinline float Det(const btVector3& a, const btVector3& b, const btVector3& c)
{
	const float a11 = a.x();
	const float a21 = a.y();
	const float a31 = a.z();

	const float a12 = b.x();
	const float a22 = b.y();
	const float a32 = b.z();

	const float a13 = c.x();
	const float a23 = c.y();
	const float a33 = c.z();

	return a11*a22*a33 + a12*a23*a31 + a13*a21*a32 - a31*a22*a13 - a32*a23*a11 - a33*a21*a12;
}

bool EdgesIntersect(const MyConvex& c0, const MyConvex& c1, short a, short b, short c, short d)
{
	btVector3 A(c0.mPolys[a].mPlane[0], c0.mPolys[a].mPlane[1], c0.mPolys[a].mPlane[2]);
	btVector3 B(c0.mPolys[b].mPlane[0], c0.mPolys[b].mPlane[1], c0.mPolys[b].mPlane[2]);
	btVector3 C(c1.mPolys[c].mPlane[0], c1.mPolys[c].mPlane[1], c1.mPolys[c].mPlane[2]);
	btVector3 D(c1.mPolys[d].mPlane[0], c1.mPolys[d].mPlane[1], c1.mPolys[d].mPlane[2]);

	const float DetCBA = Det(C, B, A);
	const float DetDBA = Det(D, B, A);
	if(DetCBA * DetDBA >= 0.0f)
		return false;

	const float DetADC = Det(A, D, C);
	const float DetBDC = Det(B, D, C);
	if(DetADC * DetBDC >= 0.0f)
		return false;

	// ACB = CBA
	// DCB = BDC
	if(DetCBA * DetBDC <= 0.0f)
		return false;

	return true;
}
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Convex-Convex collision detection issues

Post by Dirk Gregorius »

I don't care much about the separation -distance-. I only care about the separation -direction-. Can it be computed as well?


Yeah, it is just the edge-edge cross product. Getting the sign is tricky. I chose the sign according to the vector connecting the two centroids.
I don't follow. The tested separating axis is the cross product between the edges. In order to find the correct heading (sign) I use the dot product between the potential separating axis and the offset vector from the first to the second body. But how do I find the actual distance or penetration? Is the a short cut, but to project the vertices onto this axis?
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Convex-Convex collision detection issues

Post by Erin Catto »

Pierre wrote:Ok, I quickly tried the crossing-edges test and I got mixed results. It seems to work, but only if I disable the optimization above. However, without this optimization, the code is not as fast as before. For some reason it seems I can't mix the two optimizations. Not sure why, no time to really investigate.
Yeah this makes sense because all the parallel edges have different representations on the unit sphere. In other words, they have different adjacent faces. So the quick edge-edge test only helps for shapes that have few parallel edges, like a tetrahedron.
Dirk Gregorius wrote:I don't follow. The tested separating axis is the cross product between the edges. In order to find the correct heading (sign) I use the dot product between the potential separating axis and the offset vector from the first to the second body. But how do I find the actual distance or penetration? Is the a short cut, but to project the vertices onto this axis?
You can compute the line-line distance using the edge vertices.
Post Reply