Internship project 2014:
"Collision Detection on GPU for real-time applications"

This subject can adapt to several cursus (Master, Engineering...), for 3 to 6 monthes


Fabrice NEYRET,   Prashant GOSWAMI,   Pascal GUEHL   -   Maverick team, LJK, at INRIA-Montbonnot


In real-time applications like games or simulators, realistic things occur only if you simulate them: for characters lay on the floor or rocks roll down the terrain instead of sinking inside Earth, you have to reproduce contact and reactions. Same for the contact of a virtual tool with virtual clay for an interactive sculpting application. In case of contact, the reaction is obtained from the initial motion and the normal vector at the contact point.

Detecting contact or collision is a complex and costly task. Even if approximated as the intersection of two meshes, in theory one should test the intersection of each pair of triangles. For many or complex objects interacting with the environment or together (e.g., rock fall, avalanche or water flow), the cost could be overwhelming. Our GigaVoxels approach represents scenes as Sparse Voxels Octrees on GPU. This brings structure to space (direct access to location and neighborhood, natural ordering, spatial hierarchy) that meshes miss. This allows for fast and high-quality realtime operations.

The purpose of this project is to use GigaVoxels for detecting collisions and providing the necessary data for its treatment.

Description of the subject

In this project, the student is expected to implement the collision detection and collision response functionality in GigaVoxels.

As a first step, the student is expected to determine the presence of matter to check for collision for a given position by determining if a given 3D neighborhood (e.g., a box around the position) contains some matter or not. The idea is to take advantage of the hierarchical structure to do this as efficiently as possible on the GPU octree.

In a second step, the pseudo normal at contact location is approximated. The idea is to approximate a pseudo-normal from the contact neighborhood which would be then used for collision response.

We expect the student to design and implement an efficient algorithm collision detection and response algorithm on GigaVoxels and to evaluate its limitations and performances.