Re: [Algorithms] GJK

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

> Actually for *that* one, I really would like to understand the whole theory
> before coding anything. I can't imagine how I would be able to fix a bug in
> the middle of this distance subalgorithm for example! :)  ...brrr... Now to
> tell the truth, I already coded the search for supporting vertices with
> hill-climbing, but I don't think that's the difficult part !

I agree... I'd definitely need to understand an algorithm before I can
debug it, but precision in algorithms is important (of course), and I find
it easier to be precise in C++ than in the univeral language of
mathematics (obscure movie reference).

> All in all, the whole system seems very easy to implement once you get the
> ideas. If you look at the existing implementations, the code is always very
> small, even with all the optimizations and caches. I got 3 of them: (do you
> know some others?)
> 
> - the enhanced GJK version 2.4 by Stephen Cameron. Without doubt the ugliest
> code I've ever seen :) But it was made on purpose....

I think even with comments and indenting kept in there it wouldn't be that
readable.  I'm a big fan of variables that mean something.

> - the SOLID 2.0 version. Not very much better, ahah! Comments are almost
> inexistant, and the use of caches and bit-arrays make the whole thing quite
> unclear.

Yeah, the paper is the best description of the algorithm I've seen, but
the set operations could have been encapsulated for easier reading with no
loss in efficiency.

> - the Graphics Gem IV version by Rich Rabbitz. Surprisingly the clearest
> version among those three - also the slowest since this is the basic GJK
> without any optimizations. I wish I had the book anyway (I just have the
> code) because it may contains some clear explanations about that famous
> Delta equation. I guess some of you guys have that book, hmmm? Anything
> useful there?

I'll send you the article offline (it's like I walked to the library to
make a copy for you, and then walked over to France to hand it to you,
right?)

> > 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.
> 
> Do we even need those values?

You're right.  I think they might not be needed.  I just like to see all
cases covered in a recursion. :)

> - in Van Den Bergen's paper about GJK, page 5:
> "This subset X is the largest of all nonempty Z....". Largest ? I would have
> said the smallest...? Typo ?

It would have to be... otherwise the set could grow very large or even
worse: there would be no termination to the algorithm because it could
cycle easier.

> - The delta formula is something like:
> 
> Delta(j)(X+yj) = Sigma(i in IX) (Delta(i)(X) * (yi | yk - yi | yj))
> 
> ...where | is a dot product.
> 
> Since k is said to be fixed, why don't they rewrite it that way :
> Delta(j)(X+yj) = (yk - yj) | Sigma(i in IX) (Delta(i)(X) * yi)
> 
> ...which saves a lot of dot products, and maybe make all those caches
> useless ?

using your notation:

Delta(j)(X + yj) = Sigma(i in IX) (Delta(i)(X) * ((yi | yk) - (yi | yj)))

Delta(j)(X + yj) = Sigma(i in IX) (Delta(i)(X) * (yi | (yk - yj)))

I don't think you can do that last step.

Will

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