[ODE] Re: Convex collision (was: New tri_tri_intersect)

[Aras Pranckevicius]

> Unless I'm missing something (I only read it "diagonally"), it 
> doesn't say anything about the actual problem : contact generation. 
> Finding intersecting triangles between convex objects is not really 
> an issue...

Certainly! Just "colliding" is easy. Now, try to generate contact points and 
penetration depth from that :)

Some methods I've seen:
* S.Cameron's penetration bounds estimation from his Enhancing GJK paper. 
Probably too inaccurate.
* G. van den Bergen's "expanding polytopes" (quite similar to GJK, works on 
final GJK simplex).
* DEEP ("Incremental Penetration Depth Estimation Between Convex Polytopes 
Using Dual-space Expansion"). Actually it's not that scary (as you might 
think, when reading "now we construct Gauss mapping of the features").
* There's P.K.Agarwal's method that gives best theoretic complexity, but no 
implementations are know. All that I've understood from that that it's some 
randomized method :)

Any others?

All these solve (or estimate) penetration depth for convex polythedra (Bergen 
also supports any convex objects). I guess that contact points (in most cases 
you need multiple contact points for resting contact) could be generated (or 
approximated), say, from final simplex in GJK case.

My own implementation ended up with plain Enhanced GJK only, with no 
penetration depths etc., so all above is just paper reading and guessing...


Aras Pranckevicius aka NeARAZ
http://www.gim.ktu.lt/nesnausk/nearaz/