运用改进的八叉树算法实现精确碰撞检测

An Improved Algorithm for Octree-Based Exact Collision Detection

提出一种精确碰撞检测算法,通过计算空间多面体之间距离实现碰撞检测功能.在计算2个多面体之间距离时,运用空间层次划分技术高效地寻找多面体中充分接近的三角面片,然后在这些三角面片中进行距离计算,以提高算法效率;同时运用改进的八叉树层次分割算法,与基本八叉树算法相比,减少了算法的空间复杂度.文中算法已经在超导Tokamak实验装置(EAST)虚拟装配仿真系统的碰撞检测模块中得到应用,通过实验比较,证明了该算法的可行性.

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.