Re: [Algorithms] GJK

[Will P. <wi...@cs...>]

On Thu, 10 Aug 2000, Pierre Terdiman wrote:
> 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.

I'm actually implementing this algorithm now, and I find that I do not
have the background in this area of mathematics yet to understand
everything that is going on.  So the disclaimer: I'm not an expert on this
algorithm.  I welcome Ron Levine's input. :)

I assume by Johnson's algorithm you mean the sub-algorithm that computes
the minimal convex simplex that contains the new support point that is
closer to the origin?  I think all descriptions I have read of it have
been just hacky ways to determine how to convex-ly combine (by finding the
best lamda values to use) the points in the previous simplex and the new
support point to find the minimal convex simplex that contains that new
support point.  Does that seem correct?

By the way, what is the *intuitive* reason that the simplex can be up to
four dimensions (i.e. the tetrahedron)?  Is it because the closest points
can be from two edges?

Will