General strategie of a physics engine for contact generation

[Dani3L]

I have a simple general question.

In a physics engine where we can use several types of bounding volumes (box, sphere, cone, cylinder, ...). I understand that we can use for instance the GJK algorithm between any kind of those types of volumes to know their distance and closest points with a single "generic" algorithm. Is that right ?

But for the contact generation (contact manifold), Does it exist a kind of "generic" algorithm to find the contact points between any types of bounding volumes or do we have to code the generation of contact points for each kind of pair of volumes. For instance a piece of code to compute the contact points for a Box-Box collision, another piece of code for Box-Sphere collision, another for Cone-Cylinder collision, ... ?

For instance how does it work in bullet ?

[Dirk Gregorius]

One strategie as e.g. used in Bullet is to use a generic convex vs. convex collision algorithm. Convex shapes can be defined in terms of a support mapping and therefore you can use GJK for closest point computation. In the easiest solution you then cache the closest point to build the full manifold over several frames. You might look at btPersistentManifold for example. You can also vary this algorithm to build the full manifold directly. E.g. you could use the separating axis to identify the closest faces and clip them or pertubate the separating axis to "scan" the touching features.

The other alternative is to have special algorithms for each combination of shapes. With such an approach you propably would describe quadrics (cylinders, cones, etc) as convex meshes. E.g. Bullet uses a special box-box collider as well.

HTH,
-Dirk

[Dani3L]

Ok thank you very much for your answer. There is something I don't understand : Why bullet uses both alternatives. For instance bullet uses GJK algorithm (alternative 1) but also a special box-box collision algorithm (alternative 2). Why ?

Is it possible to use only GJK algorithm to compute the contact manifold of any kind of pairs of bounding volumes (box, cylinder, cone, sphere, ...) without using special algorithms ? Are special algorithms necessary because in some cases it is not possible to compute the contact manifold with GJK perturbations ?

[Dirk Gregorius]

I would imagine that it is a simple optimization. Boxes are relatively often used and the contact generation can be easily optimized.

Well, GJK is an algorithm to compute the closest point between *disjoint* convex shapes which can be described in terms of a support function. You can even combine (Minkowski addition) convex shapes to build more complex ones, e.g. you can use a disc and a sphere to model some kind of wheel. Anyway, it still might happen that your shapes get into penetration. In this case GJK would fail and you need another algorithm like e.g. EPA. So yes, GJK is very versatile and can be used to compute contact manifolds between any kind of convex shapes in combination with some caching scheme.

[Dani3L]

Ok I understand. Thank you.