## GPU-accelerated triangle-triangle intersection tester algorithm

Pixelux Entertainement

HEIG-VD, Haute Ecole d’Ingenierie et de Gestion, de Canton de Vaud, 2012

@article{maffina2012gpu,

title={GPU-accelerated triangle-triangle intersection tester algorithm},

author={Maffina, Romain},

year={2012}

}

The goal of the project is to develop a triangle-triangle collision algorithm. A reference triangle is given as well as a variably-sized array of many other triangles. The algorithm must check if one triangle intersects with the reference triangle. That operation has to be led for each "non-reference" triangle with the reference triangle. If one triangle intersects with the reference triangle the algorithm must return a true value, otherwise (if none of the triangles in the array intersects with the reference triangle) it must return a false value. The algorithm has to be as fast as possible. Therefore we are trying to use the capabilities of massively parallel computations with GPUs (Graphics Processing Units). In particular the NVIDIA technology was chosen. Therefore the implementation of the algorithm is done in CUDA C. Here is the specifications given by Pixelux Entertainement on March 1st, 2012: The project is to build a CUDA-accelerated triangle-triangle intersection test. This could benefit our auto-cage tool that constructs watertight "cages" used for tessellation around geometry objects. The project is defined as such: 1. Assume you have a triangle. A triangle is represented as a 2D object but it is represented in 3D coordinates. So very simply defined as a set of 3 3D coordinates. 2. Assume you have a list of triangles that you will be comparing a single triangle to. I would imagine that in CUDA, this would ideally be represented as some sort of array. 3. Write a CUDA function that compares a single triangle to the list of triangles and returns True or False. True if the triangle intersects any of the triangles in the list, and False if it does not. We prefer the code be written in "C" and, of course, CUDA.

October 3, 2013 by hgpu