Paper Info
Title
An Improved Algorithm For Triangle To Triangle Intersection Test
Abstract
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.
Year
DOI
Venue
2015
10.1109/ICInfA.2015.7279740
2015 IEEE INTERNATIONAL CONFERENCE ON INFORMATION AND AUTOMATION
Keywords
Field
DocType
triangle to triangle intersection, collision detection, GPU parallel computing, projection theory
Data structure,Collision detection,Algorithm design,Computer science,Parallel algorithm,Algorithm,Robustness (computer science),Acceleration,Statistical classification,Certificate
Conference
Citations 
PageRank 
References 
0
0.34
4
Authors
4
Name
Order
Citations
PageRank
Xiufen Ye14210.31
le huang220.69
lin wang320.69
huiming xing422.38