Re: [Algorithms] GJK

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

> Hill-climbing is a dramatic optimization provided the number of
> vertices gets "reasonable". Now, it's up to you :)

I agree totally (i.e. O(1) is better than O(n)).  There are just other
things that are slower and worth speeding up at this time and making it
O(1) (however easy it might be) will complicate the code.  For example,
I'm going to integrate my rigid bodies into a bsp-tree based world and
I'll need to do full collision detection there.  I expect those algorithms
will be costly.

> 
> Talking about cycling, it reminds me of something I forgot to mention
> so far. What termination condition do you use?

I'm using Gino's termination condition (the one that monotonically
increases to a tighter lower bound).

> Basically, you just need to keep recording the pair of vertices
> encountered, and you just stop the algorithm the day you find a
> reoccurrence. This is a lot more robust than everything else of
> course, since it doesn't imply numerical accuracy anymore. But would
> it be what you mean by "cycling" ?

This is what I was thinking that I might have to add in case the simplex
went through the same series of sets of points repeatedly.  But I haven't
seen it yet.

> Any thoughts regarding that particular, delicate point? I think it's
> important to improve GJK's robustness, I don't feel like playing with
> epsilons for ages, as Gino did.

I thought Gino's solution was to look for cycling?  That doesn't seem too
hard.

> There is also the implementation issue behind that : you must record
> pair of vertices. If P has p vertices and Q has q, then you basically
> can have to face pq different pairs. Recording them is easy. But you
> also must be able to tell whether a new pair has already been recorded
> or not - and of course in a very quick way. This is not a very big
> problem, but choices have to be made there. For the moment, and in the
> sake of laziness, I just scan the array of recorded pairs in search of
> current one, in a very stupid linear way. It could be improved using
> some dichotomy methods, but I didn't do it. I also could use a stupid
> array of pq bits, but it really would waste some ram for nothing.
> Comments welcome here as well.

Well, you could just remember which points are removed from the simplex in
that time step.... that shouldn't be too hard, and is constant time.

> What do you mean by "full contact manifold" ?

Like if two cubes are on top of each other.  The full contact manifold (or
roughly parts that touch) wouldn't just be one closest point as returned
by gjk, but a face or some other combination of features.  For my
purposes, it might not be worth calculating.

> It actually made me think to a new question! When the algorithm stops,
> it returns a pair of closest points expressed as : Cp = l0*P0 + l1*P1
> + ... Cq = l0*Q0 + l1*Q1 + ...
> 
> (assuming li are Lambda(i), Cp belongs to P, Cq belongs to Q) Now, I
> didn't notice it before, but Lamdbas are the same for Cp and Cq !?
> Isn't it a strong limitation regarding the actual positions of Cp and
> Cq on the convex hulls of P and Q ? I mean, when you start looking for
> two arbitrary points on P and Q, you're supposed to be able to express
> them with arbitrary Lambda values. There's a little something here I
> don't get. Weird. Do you find it shocking or normal ?...maybe there's
> an obvious reason I don't see. And maybe that's what you mean when you
> say it doesn't find a "full contact manifold" ?

It's weird, yes, but not that weird considering that the whole algorithm
works on the two polyhedra A and B at the same time to find the point in A
- B closest to the origin.

> Pheew, when you think it's finished, well, it's not :)

It never is.  The harder part is coming up with good collision
response/contact forces, and god forbid if I decide to go with nonlinear
springs for fear of patent violations. :)

Will


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