RE: [Algorithms] GJK

[Jenny A. <aj...@fr...>]

I studied this algorithm months ago, so let's go :

I suppose that you have two polytope, that is two set of vertices, which
are supposed to be convex (for concave object, you have to decompose the
object in a sum of concave object, but that's quiet complex).

So finding, these closest points is equivalent to find the closest point
from origin to minkoski sum of the object (quiet easy to check).

The GTK algorithm creates a set of simplex which is imbricated, that is
the new simplex is smaller that the previous one and so on. And as the
number
of vertex is not infinite, the algorithm ends in a finite time.

For the details of the set construction, I'm afraid that you should read
original paper, or this one, which improves time coherance of the algorithm
:

A fast and robust GTK implementation for collision detection of convex
objects, Gino van den Bergen
http://www.win.tue.nl/cs/tt/gino/solid/index.html#papers

Alexandre

-----Message d'origine-----
De : Pierre Terdiman [mailto:p.t...@wa...]
Envoyé : jeudi 10 août 2000 02:03
À : gda...@li...
Objet : [Algorithms] GJK


Hi,

I'd like to implement my own version of the GJK algorithm involved in
collision detection, without just using any of the available packages
(Solid, Stephen Cameron's version, etc). But I admit I have some
difficulties with the theory behind it. Is there any GJK expert here, who
would be kind enough to briefly summarize that algorithm? For example, even
Gilbert's underlying layer - that is, Johnson's algorithm to compute the
closest point to the origin for a simplex - looks quite weird to me. The
original paper by Gilbert is quite painful to read IMHO, and I don't really
understand what's going on here. So, to start with, if someone can explain
in a few words Johnson's algorithm, it would be cool. I'm familiar with
Minkowski sums, supporting vertices and most of the usual terminology, so
don't be afraid to use the right words in the right place.

Pierre



_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list