Re: [Algorithms] GJK

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

> > 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.
> 
> Ok, let's fix that, because it may be important. Either it works and nobody
> noticed it before (hence, I'm very happy), either it does not work and it
> probably means I'm not using the right delta formula, which would explain
> why I can't re-derive it (hence, I'm very happy as well because I found my
> bug :)
> 
> Let's get rid of the Sigma, painful to write in ASCII. Am I wrong, or do we
> have the following pattern :

All math is painful to write in ASCII.  I'd prefer latex, because I can
read and write it. :)

>     D(j) = d(0) * y0|(yk - yj)   +   d(1) * y1|(yk - yj)   +   d(2) *
> y2|(yk - yj)  + ......
> 
> with d(i) = scalar values, yi = vectors.
> 
> The dot-product is associative: (rX)|Y = r(X|Y)
> 
> Hence
>     D(j) = (d(0)*y0)|(yk - yj)   +   (d(1)*y1)|(yk - yj)   +
>   (d(2)*y2)|(yk - yj)  + ......
> 
> The dot-product is commutative: X|Y = Y|X
> 
> Hence
>     D(j) = (yk - yj)|(d(0)*y0)   +   (yk - yj)|(d(1)*y1)   +   (yk -
> yj)|(d(2)*y2)  + ......
> 
> The dot-product is distributive: X|(Y+Z) = X|Y + X|Z
> And since yk and yj are fixed (they don't depend on i in the Sigma
> expression):
> 
>     D(j) = (yk - yj)| [ (d(0)*y0)   +  (d(1)*y1)   +   (d(2)*y2)  + ...... ]
> 
> 
> Unless I'm blind and totally missing a key point somewhere, here it is. What
> do you think ?

Actually, I think your math is right (I had to write it in pencil :) ).  
The reason why it's not a big win is that with this formulation you
require three multiplies for each term and then a dot product, as opposed
to just one multiply per term with the dot product table lookups.  This is
assuming, of course, that multiplies are the expensive operations.

Will

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