| Abstract [eng] |
Interection detection between objects is a relevant topic in computer graphics, physics based particle interaction systems and robotics. Precise intersection detection between objects is a very computationally expensive process, especialy when the objects are composed of a large set of constructional elements or there is a large number of interacting objects themselves. Thus, research of methods to speed up intersection detection is being carried out to this day. Observing a tendency, that the computational power of CPU is often not enough to perform complex intersection detection in real time, increasing attention is given to parallel computing in the GPU. In this paper, research concerning triangle-triangle intersection algorithm efficiency is presented, multiple spatial subdivision methods are compared and evaluated based on their time and memory consumption. Also the parralelization of algorithms for GPU is examined, using Nvidia CUDA capable graphics cards of multiple generations. Lastly, existing modifications for classic intersection detection algorithms are analyzed and new ones suggested. Research determines the fastest triangle detection algorithm out of two compared candidates, determines the generation of graphics cards whose parallel computing can outperform the CPU, presents direct access modifications to serial uniform grid and recursive octree algorithms for usage in the GPU. The research also compares the times of different phases of spatial subdivision algorithms, insight is presented about which methods are more suitable for which tasks. Finally, the research concludes with a time comparison of the fastest serial CPU algorithm and the fastest parallel GPU algorithm. |
