Analysis of collision detection algorithms in three-dimensional virtual environments

Abstract

The problem addressed in this paper concerns the real-time detection of collisions in virtual environments, which can consume a significant portion of computational re-sources, particularly in complex simulations with numerous objects. Ensuring a minimum frame rate of 30 FPS is crucial for user-friendly simulations. The focus is on the narrow phase of collision detection, where objects in close proximity are examined for potential collisions. This paper proposes a collision detection algorithm leveraging Directed Bounding Parallels (AABB) R-tree structure and Oriented Bounding Parallelepiped Inter-section (OAABB) method to address this phase efficiently. Experimental results demon-strate the effectiveness of the algorithm in detecting intersections with high interaction rates. Various publicly available toolkits exist for narrow phase collision detection, em-ploying different bounding volume hierarchies and constraint volumes. Comparing these approaches is challenging due to performance variations influenced by factors such as object shapes, contact types, and model sizes. Nonetheless, these algorithms are crucial for accurately detecting collisions in virtual environments and gaming applications. Bounding Volume Hierarchies (BVH), commonly used for collision detection, organ-ize object geometry and improve performance by reducing test pair numbers through vol-ume constraints. The proposed algorithm utilizes R-tree hierarchies of directed bounding parallelepipeds and OAABB to enhance collision detection efficiency by minimizing up-date and intersect operations. The choice of constraint volume type impacts collision de-tection performance, with oriented parallelepipeds offering faster intersections. To expedite collision detection, each feature is represented by an R-tree data struc-ture in its local coordinate system. Hierarchical trees are constructed by grouping adja-cent surfaces, with leaves indicating surface geometry. Additionally, R-trees are em-ployed to spatially organize triangles within surfaces to quickly discard non-intersecting triangles. The algorithm leverages OAABB, a concept involving the common volume between two oriented bounding parallelepipeds, to filter out primitives that cannot intersect. Tra-versal algorithms are utilized to reduce the number of node visits, addressing inefficien-cies observed in traditional schemes. OAABB contributes significantly to reducing volume refresh operations. Experimental evaluations demonstrate the proposed algorithm's efficacy in real-world industrial applications, achieving interactive performance. Comparisons with al-ternative methods highlight the algorithm's effectiveness in collision detection. Overall, the proposed approach offers a robust solution to the narrow phase collision detection problem in virtual environments.