An Improved Algorithm for Octree-Based Exact Collision Detection

This paper introduces an improved method of exact collision detection by means of computing the distance among space polyhedra. The polyhedron is represented by a set of triangles, as the most fundamental components of complex objects in common 3D applications. In calculating the distance between two polyhedra, it is important to search efficiently the closest triangles using the technology of space hierarchical division algorithm such as octree division method. This octree method would divide the environment and get the most possible parts of virtual scene effectively and easily in real time. The paper also improves octree division algorithm by decreasing space complexity in contrast to ordinary octree algorithm. This algorithm has been applied to the experiment advanced superconducting Tokamak(EAST) virtual assembly simulation system, a project demanding exact collision detection in its assembly processing. After testing and comparison with other collision detection methods, this algorithm proves to be feasible.