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

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 [font="Monaco,"][color="#000000"]btPolyhedralContactClipping[color="#666600"]::[color="#000000"]clipHullAgainstHull and [/font][font="Monaco,"]clipFace.[/font]
[font="Monaco,"] [/font]
[font="Monaco,"][color="#000000"]For general convex polyhedra you need to compute the connectivity and connected faces ([font=Monaco,]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: [/font][/font][font=Monaco,]http://code.google.com/p/bullet/source/browse/trunk/src/BulletCollision/CollisionDispatch/btBoxBoxDetector.cpp#574[/font]
[font="Monaco,"]
[/font]Thanks,
Erwin

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).

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

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?

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

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.

You'll generally have some a priori knowledge about the axis and supporting features that can be leveraged. For example, if the axis is a coordinate frame axis from one of the boxes (as is often the case), you know that the supporting feature for that box will be one of the two faces for which the normal is parallel to the axis. Also, I'm pretty sure that if the axis is an edge cross-product axis, the supporting features will be the two edges in question (it's been a while since I've implemented such a system though, so I might be forgetting something or other).

I remember that when I implemented this (for OBBs), the supporting features other than those known a priori were found by analyzing the components of the axis transformed into the local space of the box. Generally speaking, if two of the components of the transformed axis are near-zero, the supporting feature is a face; if one of the components of the transformed axis is near-zero, the feature is an edge; and if no components are near-zero the feature is a vertex. Furthermore, the signs and values of the components tell you which feature should be selected.

One more question. jyk mentioned doing continuous intersection testing. Do you have the name of a good algorithm for this?[/quote]
'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.)

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.