Collision detection, half space representation

[Bublik]

Hi!
i'm writing a small rigid body simulator to understand how these things works and become interested in collision detection.

1) How can i generate contact points given two convex polyhedra represented as two lists of bounding planes?
Is there anything better than GJK ?

There's an article in GPU Gems 3 ("LCP Algorithms for Collision Detection Using CUDA"), but it seems, they only compute separation distance. I don't know how they compute contact forces.

Volume representation seems to have some advantages over the vertex-based one:
a) Exact time of impact can be found, even in presence of fast rotational motion ("A Linear Programming Solution for Exact Collision Detection");
b) Inside/Outside is clearly defined.

2) How do i compute contact manifold given a list of linear inequalities?
I'm especially interested in calculating contact normal and penetration depth.

3) Will three contact points suffice for producing a stable simulation?

The following may seems stupid, just random thoughts...
Bounding planes and vertices are dual to each other, maybe, there should exist an analog of GJK using 'support planes' or something. Vertex-based representation works faster for finding extreme points, but bounding planes take up less space. They are naturally aligned, can be 'constrained' (finite set of planes,k-DOPs). drop contact points and work on contact volumes instead?

Thanks for your time.

[dneckels]

I work with a similar problem in my quake map renderer: the collision 'brushes' are all represented as the intersection of half-planes. I use code from bullet to solver for the vertices that describe the convex hull, and use GJK on those.

I guess vertices might be better than planes for the support function since the extrema of a convex shape is almost always at a vertex as opposed to on the surface of a 2d plane. So by solving for the vertices you are a step closer to providing answers to the support query....

Bullet (and my engine) use 4 contact points and that seems to work great. These points are generated by collecting closests points over a time frame and maximizing the area between the points....

Not sure that helps, but hope it does...