An improved algorithm for triangle to triangle intersection test

The triangle-to-triangle intersection test is a basic component of all collision detection data structures and algorithms. There are many algorithms that have been put forward in this area until now. Among these algorithms, there is one proposed by YU Hai-yan based on projection theory which can simplify the three-dimensional test into the two-dimensional test and certificate its robustness theoretically. However, the long calculation time can not satisfy the real-time performance. In this paper, an improved algorithm is proposed firstly. Then, the GPU parallel computing is adopted to accelerate our algorithm. Finally, some experiments were carried to validate the improved algorithm. Through the experiments, it shows that the improved algorithm is up to 13 times faster than the original algorithm on average when the triangles´ number increases to 2 million and the acceleration times will also increase when much more triangles are detected at the same time and however the algorithm is also stable.