Re: [Algorithms] GJK

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

Yeah, here we go again !

> I have one working as well, but I'm not taking hill-climbing into account
> (I could add it, but for simple shapes like cubes I wouldn't be surprised
> if it were more expensive to generate the adjacencies and load-time and
> check them in the support point computation routine).  I haven't
> encountered cycling yet, though it's easy enough to detect that issue.

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

Talking about cycling, it reminds me of something I forgot to mention so
far. What termination condition do you use? Gino's one is the same as
Gilbert's one, and you can read in his paper how much pain he had to make it
more robust. That's why I discarded it and I used an "improved" termination
condition presented in the Q-COLLIDE thesis. 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" ? I don't know where
this improved termination condition comes from, I trusted Kelvin Chung on
that point - regarding the rest of the thesis I think I can. Best proof of
that is just that it works indeed, and very well. Now, I'm a little upset
about one of the last paragraphs in Cameron's papers about his enhanced GJK.
I must read it again, but I think he claims this new termination condition
doesn't handle all possible cases. 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.

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.


> I substituted this GJK implementation in the place of the separating plane
> stuff I had beforehand, and although it doesn't find a full contact
> manifold, it looks pretty decent in the context of a rigid body
> simulation.

Looks like we're all doing the same. I already had the separating vector
from Q-COLLIDE, and I actually started GJK to implement the "combined
algorithm" presented in the end.

What do you mean by "full contact manifold" ? 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" ?


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

Pierre