The algorithms to detect collisions in a three-dimensional (3D) world can be classified as follows: image-space culling algorithms based on graphical processing unit (GPU) calculations, which take advantage of the runtime performance of graphic processing, but lack accuracy that can result in missing some collisions; object-space culling algorithms based on central processing unit (CPU) calculations, which have the advantage of having the high precision of CPU calculations, but are slower than GPU-based algorithms; and hybrid approaches that combine GPU and CPU calculations to take advantage of both approaches.
The algorithm presented in this paper can be considered a hybrid approach to detect collisions between triangulated models. The algorithm, called FAR (for fast and reliable), consists of two parts: the first part uses fine-grained GPU-based processing to cull away triangles that are not in close proximity, and the second part uses coarse-grained CPU-based processing to discriminate between close proximity and real collisions of triangles. The paper focuses only on the first GPU-based phase of the algorithm, and no details are given about the second phase.
The novelty of this algorithm is that it is more reliable than prior similar methods, in the sense that, unlike other GPU-based approaches, it does not fail to detect collisions, and the authors affirm that it is more efficient in culling triangles than the existing CPU-based approaches. FAR extends a previous algorithm by the same authors, called CULLIDE, that implements a GPU-based collision detection. To guarantee that no collision is missed, this novel algorithm computes a tight bounding volume for each triangle, and CULLIDE is applied to this representation instead of the original triangles. Triangles that are not in close proximity are culled away, and exact collisions are detected in the second phase.
For readers with knowledge of GPU programming, the paper presents the pseudocode of the algorithm and some details of implementation, particularly related to the use of Z-buffer and face culling.