Re: [Algorithms] GJK

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

> I think it just fits the definition of convex, like the ones given in
> appendix A of Van Der Bergen's paper.

Hmm, to me the definition of a convex function (not of a polytope) is that
the second derivative has a constant sign. That way, to minimize the
function we just have to assure the first derivative is zero. For example
how would we *maximize* the function? ...in the exact same way, yep...
Difference comes from the second derivative. There must be a very good
reason in our case to assume there's no need to check for it, but I don't
find it obvious. You must be right anyway: it must be related to the
original definition of the function, but ... well, I just don't see why it
is obvious :) Anyway this is a detail, really.


> 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.


> That makes sense... I think I saw something similar in the gdc hardcore
> proceedings.

Is there a GDC paper about GJK ?


>Mathematically, it make sense.  It makes me wonder if there is any
>intuition about it, or they just make that observation about
>perpendicularity (is that a word?) for no particular reason.

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

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 ?

Pierre