Started by Apr 13 2011 03:48 AM

,
7 replies to this topic

Posted 13 April 2011 - 03:48 AM

Note: 3D not 2D

OBB-OBB (oriented bounding box) intersection tests are fairly well covered (separating axis) but I can't find much information about generating intersection data (contact point, normal, penetration depth) for collision response.

I'm using a separating axis test to determine whether or not they are in contact. If they ARE I need to generate collision data. This is what I have/know currently.

for vertex-face collisions:

Test each vertex of each box against the other box to see if it lies within its boundaries. If it lies within the box's boundaries use the closest face's normal as the contact normal, and the distance to that face as penetration depth. This seems fine although it seems like a lot of tests? (16, one for each vertex on each box)

for edge-edge collisions:

Test each edge from each box against each other. This is what I'm not too sure about. The only method I can find is to do a test on each edge line to find the closest points on each. Then determine if these points lie on the segments of the lines that make up the edge. If so test whether point a is closer to the center of body b than point b, and vice versa. This seems massively inefficient. 12*12 = 144 tests, and it's a pretty expensive test.

Can anyone shed any light (or links) on this?

Cheers

edit: numbers

OBB-OBB (oriented bounding box) intersection tests are fairly well covered (separating axis) but I can't find much information about generating intersection data (contact point, normal, penetration depth) for collision response.

I'm using a separating axis test to determine whether or not they are in contact. If they ARE I need to generate collision data. This is what I have/know currently.

for vertex-face collisions:

Test each vertex of each box against the other box to see if it lies within its boundaries. If it lies within the box's boundaries use the closest face's normal as the contact normal, and the distance to that face as penetration depth. This seems fine although it seems like a lot of tests? (16, one for each vertex on each box)

for edge-edge collisions:

Test each edge from each box against each other. This is what I'm not too sure about. The only method I can find is to do a test on each edge line to find the closest points on each. Then determine if these points lie on the segments of the lines that make up the edge. If so test whether point a is closer to the center of body b than point b, and vice versa. This seems massively inefficient. 12*12 = 144 tests, and it's a pretty expensive test.

Can anyone shed any light (or links) on this?

Cheers

edit: numbers

Posted 13 April 2011 - 08:49 AM

One approximate way to generate contact points between two convex polyhedra A and B, is the following recipe:

1) find a separating axis between A and B using your favorite method (SAT, GJK etc)

2) find reference face on A and a incident face on B with a normal that is closest to this separating axis

3) perform Sutherland-Hodgman clipping on the vertices of this face on A against the polyhedron B

This clipping can be performed either in worldspace or in the local space of B, using the faces connected to face B

I recently implemented this method in the open source Bullet physics library, part of the Bullet 2.78 release, so you can test the implementation and read the code here:

http://code.google.c...actClipping.cpp in particular btPolyhedralContactClipping::clipHullAgainstHull and clipFace.

For general convex polyhedra you need to compute the connectivity and connected faces (m_connectedFaces in above code), Bullet uses the btConvexHullComputer for this. For the special case of OBB-OBB this information can be hard-coded, you can see the OBB-OBB clipping code in ODE/Bullet here: http://code.google.com/p/bullet/source/browse/trunk/src/BulletCollision/CollisionDispatch/btBoxBoxDetector.cpp#574

Thanks,

Erwin

1) find a separating axis between A and B using your favorite method (SAT, GJK etc)

2) find reference face on A and a incident face on B with a normal that is closest to this separating axis

3) perform Sutherland-Hodgman clipping on the vertices of this face on A against the polyhedron B

This clipping can be performed either in worldspace or in the local space of B, using the faces connected to face B

I recently implemented this method in the open source Bullet physics library, part of the Bullet 2.78 release, so you can test the implementation and read the code here:

http://code.google.c...actClipping.cpp in particular btPolyhedralContactClipping::clipHullAgainstHull and clipFace.

For general convex polyhedra you need to compute the connectivity and connected faces (m_connectedFaces in above code), Bullet uses the btConvexHullComputer for this. For the special case of OBB-OBB this information can be hard-coded, you can see the OBB-OBB clipping code in ODE/Bullet here: http://code.google.com/p/bullet/source/browse/trunk/src/BulletCollision/CollisionDispatch/btBoxBoxDetector.cpp#574

Thanks,

Erwin

Posted 13 April 2011 - 02:44 PM

Just to echo what Erwin said, you shouldn't need to do any sort of search to find the intersecting features. Since you know the 'intersection axis' (that is, the axis corresponding to the minimum penetration depth for the discrete test, or the 'axis of last intersection' for the continuous test), you can find the features that will intersect (they'll be the supporting features of the boxes with respect to the axis and its negative).

Once you have the supporting features, you can then clip them together to yield the contact manifold.

Also, if all you need is the penetration depth, you can skip all that (the penetration depth and direction can be derived directly from the results of the discrete test).

Once you have the supporting features, you can then clip them together to yield the contact manifold.

Also, if all you need is the penetration depth, you can skip all that (the penetration depth and direction can be derived directly from the results of the discrete test).

Posted 14 April 2011 - 05:56 AM

Thanks for the replies.

For SAT, by separating axis do you mean the axis on which the projections show the least penetration/overlap.

For GJK how would you go about finding such an axis? My understanding of GJK was that it is just a true/false intersection test.

Also I've seen posts of people describing modifications to the GJK algorithm to find actual collision data. Is that an acceptable approach or is it simpler/better to just use clipping. Only because I haven't looked into clipping and it seems like it may just be simpler to just look into the GJK modification if it's a reasonable alternative.

cheers

For SAT, by separating axis do you mean the axis on which the projections show the least penetration/overlap.

For GJK how would you go about finding such an axis? My understanding of GJK was that it is just a true/false intersection test.

Also I've seen posts of people describing modifications to the GJK algorithm to find actual collision data. Is that an acceptable approach or is it simpler/better to just use clipping. Only because I haven't looked into clipping and it seems like it may just be simpler to just look into the GJK modification if it's a reasonable alternative.

cheers

Posted 14 April 2011 - 07:17 AM

Gjk gives you a separating axis, distance and closest points if objects don't overlap. It requires an additional algorithm for the penetrating case, such as SAT or expanding polythope algorithm (EPA). Still, this only gives you an axis (normal) and a single point.

To gather multiple points for polyhedra, you better simply combine SAT and clipping.

An alternative to clipping is contact caching, where you add a contacts to a small cache, and update this cache (in Bullet this is called a persistent contact manifold). You can use any method to add contacts to this cache, including GJK/EPA. GJK/EPA/contact caching is more complicated but also more generic, it can deal with a wider range of shape types. For example implicit (not tesselated) cylinders, cones etc. Bullet implements all those methods, so you can compare.

Is the SAT/clipping idea clear?

To gather multiple points for polyhedra, you better simply combine SAT and clipping.

An alternative to clipping is contact caching, where you add a contacts to a small cache, and update this cache (in Bullet this is called a persistent contact manifold). You can use any method to add contacts to this cache, including GJK/EPA. GJK/EPA/contact caching is more complicated but also more generic, it can deal with a wider range of shape types. For example implicit (not tesselated) cylinders, cones etc. Bullet implements all those methods, so you can compare.

Is the SAT/clipping idea clear?

Posted 14 April 2011 - 08:36 AM

I guess the GJK implementation I looked at must have been a refined one. I'll probably take the SAT/clipping approach anyway as it seems simpler at this point. Computing the connected faces seems like it may be painful to implement, but I'll just hardcode it like you mentioned for the OBB-OBB case for the time being.

Just to clarify:

1) Use SAT to find the axis showing least penetration (which is also the contact normal and penetration depth)

2) Find the faces from A and B with normals closest to the separating axis and its negative.

3) Perform clipping on A face using B face + connected faces as the clip geometry

From here the contact points are the new vertices created in the clipping process?

Is this right?

One more question. jyk mentioned doing continuous intersection testing. Do you have the name of a good algorithm for this?

cheers

Just to clarify:

1) Use SAT to find the axis showing least penetration (which is also the contact normal and penetration depth)

2) Find the faces from A and B with normals closest to the separating axis and its negative.

3) Perform clipping on A face using B face + connected faces as the clip geometry

From here the contact points are the new vertices created in the clipping process?

Is this right?

One more question. jyk mentioned doing continuous intersection testing. Do you have the name of a good algorithm for this?

cheers

Posted 14 April 2011 - 01:37 PM

That sounds right, except that the features can be faces, edges, or vertices, rather than just faces. Also, I'm not sure there's any need to concern yourself with connected faces.Just to clarify:

1) Use SAT to find the axis showing least penetration (which is also the contact normal and penetration depth)

2) Find the faces from A and B with normals closest to the separating axis and its negative.

3) Perform clipping on A face using B face + connected faces as the clip geometry

You'll generally have some

I remember that when I implemented this (for OBBs), the supporting features other than those known

'Continuous' is probably as good a term as any, although 'swept' and 'dynamic' are sometimes used as well. (A search for 'obb continuous sat' or 'obb swept sat' would probably turn up some relevant info.)One more question. jyk mentioned doing continuous intersection testing. Do you have the name of a good algorithm for this?

Posted 16 April 2011 - 12:53 AM

I decided to go ahead and code connected faces and clipping in properly. I figured this way it's more robust and if I extend my SAT implementation to handle arbitrary convex polyhedra I can use it for more than just box-box collisions. I don't think it was really much more work anyway.

Thanks for all the help.

Thanks for all the help.