high performance computing on graphics processing units: hgpu.org

Collision detection is a complex task that can be described simply: given a set of objects, we want to know which ones collide. In the literature, we can found numerous algorithms that depend on objects property, but we can’t find an overall solution that works on every objects. The internship focuses on a recent algorithm that shot rays from the surface of objects in the direction of the inward normal, collision is detected if a ray touches the interior of another object. This method allows deep penetrations and gives instantly the information needed to separate the colliding objects. To speedup this algorithm, we present a novel ray-tracing based technique that exploits spacial and temporal coherency. Our approach uses any existing standard ray-tracing algorithm as a starting point and we propose an iterative algorithm that updates the previous time step results at a lower cost. In addition, we present a new collision prediction algorithm to evaluate whenever two objects have potentially colliding vertices. These vertices are inserted into our iterative algorithm to strengthen the collision detection. The implementation of our iterative algorithm obtains a speedup up to 30 times compared to non-iterative ray-tracing algorithms. The use of two GPUs gives a speedup up to 1.77 times compared to one.