Re: [Algorithms] GJK

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

> paper. Take the expression of f (lamda^2, lamda^3, ..., lamda^r). Then, if
> you compute df / d^i you just find the expected orthogonality between the
> expression of the closest point and any (Pi - P0), assuming Pi are the
> original points. Well, I admit this is not a difficult one, but it sure is
> somewhat delicate.

I can see that derivation; it's somewhat like finding a jacobian matrix to
do unconstrained optimization.  I haven't gotten (yet) where they got the
original expression f, though I understand their method for minimizing it.

> For example, Van Der Bergen in his GJK paper takes this
> orthogonality as granted, and at first it's very shocking.

That's the one I was thinking of: it came out of nowhere.

> While I'm at it : Gilbert wrote "Since f is convex...". How do we know that
> function is convex ?

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

> Well, I suppose you could probably invert the (41) matrix with the standard
> inversion code of your matrix class without even using those nasty Delta
> notations ! But since the algorithm takes a combinatoric approach, it would
> need to invert up to 15 4x4 matrices (correct me if I'm wrong), most of the
> involved terms beeing recomputed many times. I suppose those optimisations
> are worth the pain - but once everything else works, of course.

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

> BTW I think the intuitive reason for limiting the number of vertices to 4,
> is that the closest point figure we're looking for can be something like:
> - point vs point (2 vertices)
> - edge vs point (3 vertices)
> - edge vs edge (4 vertices)
> - face vs point (4 vertices)

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

Will