Help with choosing narrowphase CD algorithm

[lilo]

I need help to choose a narrow phase CD algorithm.

I have come down to 2 choices:

V-clip
Enhanced GJK

The problem is I need to fully backup my choices because this is a thesis work and I really find it hard to do so.

As experiments has shown by Brian V-clip is is said to be faster and more robust than Enhanced GJK. The thing is he made the comparison using the number of floating point operations. Not sure if it is a better way than measuring the time?

Another point is that he compares to enhanced GJK written by Cameron and not the enhanced GJK written by Bergen. Bergen's version is said to be faster than Cameron's. So I have not really found a way to determine which algorithm to go with. Both are stated to almost be constant time by respective author I think, when exploiting the coherence.

Also stated by another paper:

http://isg.cs.tcd.ie/cosulliv/Pubs/LeveyWSCG00.pdf

it is said that voronoi regions takes much memory and need preprocessing so a deformable object need to reupdate the regions. Is computations of voronoi regions really needed?. Isn't it just using dot and cross products of neighbouring features to determine wheter a feature is inside a voronoi region? They state that GJK is to prefer when it comes to deformable models.

I am also curious why Bullet choose GJK rather than V-clip?

Also wonder how Ericson's voronoi simplex solver works when it comes to deformable meshes. It should work totally fine in my mind, but as mentioned above in the paper voronoi regions have to be recomputed, but in a sumplex where a tetrahedron is concerned this maybe is no problem when considering performance?

Another thing is which algorithm is easiest to use in accompany to determine contact points and penetration depth. I know EPA can be used for GJK.

Thx. This turned out to be quite a big post

[Erwin Coumans]

Bullet uses GJK because it is a very fast and generic convex collision detection algorithm. GJK is an excellent choice, especially when combined with EPA and some persistent contact caching algorithm. V-clip only support polyhedral convex shapes, whereas GJK supports general convex shapes (including implicit spheres, cylinders, cones etc).

For soft bodies, usually the performance comes from simplifications and acceleration structures, next to the innerloop (triangle versus triangle or tetrahedron versus tetradron).

Also wonder how Ericson's voronoi simplex solver works when it comes to deformable meshes.

It is not necessary to cache the simplex, so the data for the simplex solver can be recomputed every frame. If this really becomes a bottle-neck, you could use a highly optimized triangle versus triangle, or tetrahedron versus tetrahedron collision implementation using the separating axis theorem (SAT).

The fact that V-clip (and SAT) only support polyhedral shapes makes GJK a better choice in my opinion.
Thanks,
Erwin

[lilo]

Thanks for answering Erwin. I need some clarifications:

V-clip only support polyhedral convex shapes, whereas GJK supports general convex shapes (including implicit spheres, cylinders, cones etc).

Not totally sure what you really mean. I mean V-clip should work perfectly fine with cones and cylinders, because they are convex models. Not sure what implicit spheres are and the uses of it.

Also wonder how Ericson's voronoi simplex solver works when it comes to deformable meshes.

It is not necessary to cache the simplex, so the data for the simplex solver can be recomputed every frame. If this really becomes a bottle-neck, you could use a highly optimized triangle versus triangle, or tetrahedron versus tetrahedron collision implementation using the separating axis theorem (SAT).

Hmm. Do not understand why you mention SAT and triangle triangle, tetrahedron tetrahedron tests. I mean in GJK in 3D the simplex is a tetrahedron and one need to find the closest point from origin to the simplex, am I correct.

[Erwin Coumans]

Not totally sure what you really mean. I mean V-clip should work perfectly fine with cones and cylinders, because they are convex models. Not sure what implicit spheres are and the uses of it.

How can V-clip work with cones and cylinders if there are no polyhedra? From the description, V-clip only works with polyhedra. 'implicit' for spheres, cones and cylinders refers to the fact that we deal with the perfectly rounded implicit surface (quadric) defined by parameters (radius, height etc) and not by triangles or polyhedra. How would you calculate the voronoi regions of a sphere (or cylinder, cone)?

Hmm. Do not understand why you mention SAT and triangle triangle, tetrahedron tetrahedron tests.

I just mention SAT as a fast third alternative method, in case V-clip of GJK is too slow. Again, SAT only deals with polydra, which might not be a problem for you.

Thanks,
Erwin

[aokman]

How can V-clip work with cones and cylinders if there are no polyhedra? From the description, V-clip only works with polyhedra. 'implicit' for spheres, cones and cylinders refers to the fact that we deal with the perfectly rounded implicit surface (quadric) defined by parameters (radius, height etc) and not by triangles or polyhedra. How would you calculate the voronoi regions of a sphere (or cylinder, cone)?

Although have not taken any experiment, I think V-clip may work with quadric surface(eg. sphere defined by position and radius). The following is my silly opinion:
1. If given a polyhedra and a quadric surface, treat the whole quadric surface as a feature, then to compute the distance between a feature from the polyhedra and the quadric surface is not a hard thing. So, if the witness point on the quadric surface is not within the voronoi region of the feature from the polyhedra, then move onto the neighbor feature of the current feature from the polyhedra which will not make the distance increase.
2. If given two quadric surfaces, there is no need for V-Clip.
3. If given two polyhedra, use the normal V-Clip algorithm.

Do you think this will work?

Thx.

[lilo]

Thanks for answering.

How can V-clip work with cones and cylinders if there are no polyhedra? From the description, V-clip only works with polyhedra. 'implicit' for spheres, cones and cylinders refers to the fact that we deal with the perfectly rounded implicit surface (quadric) defined by parameters (radius, height etc) and not by triangles or polyhedra. How would you calculate the voronoi regions of a sphere (or cylinder, cone)?

Although have not taken any experiment, I think V-clip may work with quadric surface(eg. sphere defined by position and radius). The following is my silly opinion:
1. If given a polyhedra and a quadric surface, treat the whole quadric surface as a feature, then to compute the distance between a feature from the polyhedra and the quadric surface is not a hard thing. So, if the witness point on the quadric surface is not within the voronoi region of the feature from the polyhedra, then move onto the neighbor feature of the current feature from the polyhedra which will not make the distance increase.
2. If given two quadric surfaces, there is no need for V-Clip.
3. If given two polyhedra, use the normal V-Clip algorithm.

Do you think this will work?

Thx.

I do believe that the case with the implicit sphere might work and determining the closest point from the sphere can be done in such a way as you mentioned. To get the closest point I think what one can see the sphere as a point and then determine the distance from implicit sphere to polyhedra (after testing the whole implicit sphere against the polyhedra). After that the true distance will be to subtract the radius from distance from feature to sphere center.

I think that handling cases as implicit cones and cylinders might be more complicated because one have to consider the orientation of the implicit surface.

How can V-clip work with cones and cylinders if there are no polyhedra? From the description, V-clip only works with polyhedra. 'implicit' for spheres, cones and cylinders refers to the fact that we deal with the perfectly rounded implicit surface (quadric) defined by parameters (radius, height etc) and not by triangles or polyhedra. How would you calculate the voronoi regions of a sphere (or cylinder, cone)?

Ok i think i understand what you mean. Thx.

I just mention SAT as a fast third alternative method, in case V-clip of GJK is too slow. Again, SAT only deals with polydra, which might not be a problem for you.

Actually how is enhanced GJK compared to SAT complexity-wise? I think it may not be such big difference or? Isn't SAT also quite close to constant if one exploit the coherence and if the changes are not so extreme (very big orientation changes)? A cons might be as mentioned by you is that in SAT you are restricted to polyhedra. I guess SAT is useful in midphase where you for example test oob against oob.

[dneckels]

Another thought:

(From experience) GJK is very very easy (you can even borrow the bullet simplex solver!!).

VClip seems quite complex....

[lilo]

Another thought:

(From experience) GJK is very very easy (you can even borrow the bullet simplex solver!!).

VClip seems quite complex....

Yeah I think the idea is kinda intuitive in V-clip. At least the basic ideas. Then there are a lot of cases to consider depending on what features are currently beeing active that makes things worse.

I think the idea of GJK is kinda easy to understand, but reading the papers are like tormenting yourself So much math to describe a very simple algorithm. I guess it is because everything have to be precise.

[dneckels]

Yeah I think the idea is kinda intuitive in V-clip. At least the basic ideas. Then there are a lot of cases to consider depending on what features are currently beeing active that makes things worse.

I think the idea of GJK is kinda easy to understand, but reading the papers are like tormenting yourself So much math to describe a very simple algorithm. I guess it is because everything have to be precise.

This paper was the most straightforward that I found out there (seen it?):

http://www.win.tue.nl/~gino/solid/jgt98convex.pdf

[lilo]

Yeah I think the idea is kinda intuitive in V-clip. At least the basic ideas. Then there are a lot of cases to consider depending on what features are currently beeing active that makes things worse.

I think the idea of GJK is kinda easy to understand, but reading the papers are like tormenting yourself So much math to describe a very simple algorithm. I guess it is because everything have to be precise.

This paper was the most straightforward that I found out there (seen it?):

http://www.win.tue.nl/~gino/solid/jgt98convex.pdf

Yeah I have read it. I think this is the easier understanding paper compared to the original and Cameron's paper

I guess I should start implementing the algorithm. Hopefully the implementation is not to hard.

[Erwin Coumans]

On the other hand, GJK is already implemented in Bullet, why re-invent the wheel?

An open source V-clip, under the Zlib license, would be a great contribution to Bullet, and you could do some comparisons between GJK and V-clip for polyhedra.
I think that would be more useful than yet another duplicate implementation of GJK.

Note that the Bullet GJK implementation has several improvements over the enhanced GJK version by van den Bergen.
Cheers,
Erwin

[lilo]

On the other hand, GJK is already implemented in Bullet, why re-invent the wheel?

An open source V-clip, under the Zlib license, would be a great contribution to Bullet, and you could do some comparisons between GJK and V-clip for polyhedra.
I think that would be more useful than yet another duplicate implementation of GJK.

Cheers,
Erwin

Hehe I guess you want me to use bullet's GJK implementation.

Yeah, I must admit it is really tempting to compare V-clip with enhanced GJK (Bergen/Ericson version). I think I might do this in the future, but for the moment I have to much to do on my thesis (CD system).

* removed stuff *