Re: [Algorithms] GJK

[Pierre T. <p.t...@wa...>]

Actually I posted the mail *because* the details included in the original
paper were... well, not so clear :)
I know the rough theory, but some parts of it remain unclear (eg the Johnson
algorithm, as I was telling in the previous mail).

----- Original Message -----
From: Jenny Alexandre <aj...@fr...>
To: <gda...@li...>
Sent: Thursday, August 10, 2000 8:56 AM
Subject: RE: [Algorithms] GJK


>
> 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
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list