GJK on GPU or any other good algorithms?

[lilo]

Hi

I have a serial implementation of GJK, and want to port it to GPU because I have a broadphase algorithms running on GPU and thought that it would be nice to do narrowphase on GPU.

Is GJK a good choice of narrowphase alg. on GPU?

My take: The biggest concern that I can come up with is the support point search (given a direction vector) of the minkowski sum A+(-B) but also fitting the polyhedra on GPU. If polyhedra cannot fit on-chip shared mem (thinking about nvidia hardware now) one have to access the slower global memory.

Are there any papers resources regarding GPU GJK. Cannot really find anything except Erwins slides talking about bullet on OpneCL, but no algorithmic details of how porting is done.

GPU Gems 3 have a parallel implementation of a LCP solver based on Lemke's algorithm that can be used to determine shortest distance I believe:

http://http.developer.nvidia.com/GPUGem ... _ch33.html

But doesn't the algorithm have issues with floating point imprecisions (=> large errors) because one is solving a large linear system of eq => divides => fp representation problems? But of course the algorithm is inherently parallel.

Are there any other good choice parallel algorithms to perform narrowphase CD?

Thanks

[Johan Gidlund]

GJK is a good fit for GPU physics.
Just Google it and you should find plenty of papers about it.

Due to branching costs it might be worth to make the simplex solver branch free and just solve the worst cases all the time.

[lilo]

Hi Johan. thanks for answering.

I have searched the net about GPU GJK and cannot really find anything related to GPU GJK. I do have a serial implementation. I guess it it "just" to port it.

Due to branching costs it might be worth to make the simplex solver branch free and just solve the worst cases all the time.

You mean that one should perform all valid regions even though a smallest simplex set is determined in some earlier voronoi region tests. Meaning redundant test is done?

The biggest problem in my mind when trying to port GJK to GPU I think is the limited shared memory available. How is that tackled? For highly tesselated convex objects, a pair of highly tesselated obj wont fit shared memory.

Also I wonder how a search for best vertex given a direction dir is done in a good way. In CPU I had a neighbouring datastructure to perform hill climbing, but on GPU datastrucutres such as maps ans sets isn't it quite a complex task to implement good and safe? In the search I guess a max prefix sum have to be done on every vertex to determine a support map for pair of objects. Or is it another better way?

If convex objects are to large one have to perform loop of GJK on CPU and voronoi simplex solver in GPU I think. If objects fit GJK most part can be done in GPU.

[Johan Gidlund]

If I find time for it I will dig up some paper and post a link.

Yes you should do redundant tests. Just remove all the "smart" if cases and do the work. GPU:s can do lots of matrix math but they don't do branching well.

Generally speaking you should not do collision detection for complex objects on the GPU.
GPU collision is best suited for effect physics where you have tons of simple rigid bodies.

If you need to work with large complex object try to subdividing them into several simpler shapes. GPUs have tremedous throughput, you just need to exploit it fully by maximizing parallell execution.