Re: [Algorithms] GJK

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

> > I definitely agree that it is worth saving the dot products when running
> > the sub algorithm once (because of the combinatorial nature), but I'm not
> > sure that it's worth doing between calls to the subagorithm (although most
> > of the points in the simplex do not change).
> 
> Oh... I mixed things up, right. I forgot there were some caches inside *and*
> outside the subalgorithm. Well. I'll save that for later, for the moment I
> didn't write a single line of code.

I'm in the middle of writing the code; I find writing code to implement an
algorithm helps me understand it.

> > That makes sense... I think I saw something similar in the gdc hardcore
> > proceedings.
> 
> Is there a GDC paper about GJK ?

No, it was from http://www.gdconf.com/hardcore/physics.htm.  I didn't
attend, but my mentor from my summer position was kind enough to purchase
the proceedings for me.

> Gilbert claims it's "geometrically obvious".... :) But I'm not that good, I
> can't even visualize the Minkowski difference of the two polytopes.

Everything is obvious after it's understood.  I wish scientific papers
were written with that in mind. :)

> I have some troubles with the recursive formula used to compute the deltas.
> Where does it come from? I followed Gilbert's steps, in vain. There's always
> something wrong in the end. Did you try to re-derive it ?

I haven't yet because the formula isn't really very clear to me.  For
example, it says that delta_i (y_i) is 1, but it never says what
delta_(not i) (y_i) is.  Perhaps it's zero, but it's certainly not written
there.

It's pretty easy to use cramer's rule; I think I'll just rederive it to
see where the formula comes from.  It makes some sense that the cofactors
can be written in terms of the cofactors from a matrix representing
smaller simplices.  I think it's written to take advantage of the fact
that you want to test all subsets of Y and save computations if possible,
which unfortunately makes it less opaque. :)

Will

----
Will Portnoy
http://www.cs.washington.edu/homes/will