Need help with non-convex CD approaches

[lilo]

Hi.

I have implemented GJK and ISA-GJK and have been thinking on actually how helpful these algorithms are for non-covex CD. Of course GJK and ISA-GJK only work for convex objects. I wonder more how actually one can present to GJK a decomposed concave polyhedra. I have done some reading and found 2 ways.

1. Create a BVH and traverse it down to triangle level (leaves) and then perform collision detection. My question is now: How good is it to use GJK in this situation compared to just doing a triangle-triangle intersection/distance test? Which approach is faster?

I mean GJK is fast for convex objects because you can exploit frame to frame coherency. But if you go down to triangle level, this coherence is actually negligible? Considering support point finding with prev supp vert caching, you now have to track down to primitive level of a polyhedra, am I correct? But I mean searching for best vertex of 3 vertices do not need hill climbing and caching.

2. From a paper by Ponagmi: Do Narrowphase CD on convex hull and if intersection occurred determine if penetration features are from cap part of the convex hull (feature do not belong to original polyhedra, only to CH). In this case GJK will be used on CH and then the interior of concave polyhedra consist of AABB tree are tested for intersection with AABB tree (if i do not remember wrong). In the paper they do hierarchical sweep and prune to cull collisions and then use Lin-canny alg after finding AABB pair overlaps. GJK can replace Lin-Canny alg in my opinion.

Or is there even a third alternative? I cannot find anymore.

Any idea of which is the preferred one (1 or 2)? In recent research it seems 1 the more used one, am I correct? Due to BVH creation and traversal can be parallelized (alg. are inherently parallel). Actually how are things done on Bullet, and why is it done in such a way? Is bullet using approach 1, and is BVH used for CUDA Bullet for non-convex objects?

Because I already have an implementation of GJK and ISA-GJK, and I do want to parallelize using CUDA it seems that if I want CD of non-convex objects, it seems that approach 1 is preferred. Am I correct? In that case GJK will be used for triangle-triangle distance calc. It seems somewhat wasted to use a very general CD alg on primitive-primitive test I think.

Any opinions?

[Johan Gidlund]

Nice thing about using GJK is that your concave meshes (or rather their triangles) will collide nicely with hulls, spheres etc.
Also GJK for 2 triangles should be really fast.

Another option is to use convex decomposition to turn your concave object into a set of convex polyhedra.
If this works well or not depends on the content you have.