虚拟装配中快速碰撞检测算法的研究与实现

针对虚拟装配中碰撞检测的特殊要求，提出了一种基于包围盒与空间剖分法的两级碰撞检测算法HSDHBB。该算法首先用空间剖分法找出潜在的相交区域，然后用包围盒求得碰撞的三角面片对和精确的碰撞点。给出了层次包围盒树的构造方法和空间网格的剖分方法，在空间剖分中采用哈希表的数据结构加快检索速度。最后，在CATIA环境中实现了该算法，结果表明该算法能够满足虚拟装配系统的实时性和精确性的要求。

Research and realization on fast collision detection algorithm in virtual assembly

Concerning the special requirements of collision detection in the virtual assembly environment, a virtual assembly-oriented two-layer exact collision detection algorithm named HSDHBB was proposed based on bounding volume boxes and space division method. The algorithm firstly usd space decomposition method to identify potential regional intersection and then used bounding volume boxes to locate the intersection triangles and the exact points. Methods of constructing the bounding volume boxes tree and space division were given, and the data structure of Hash table was used to accelerate the collision detection in space division. Finally, the algorithm was applied in CATIA, the results show that the algorithm can effectively meet the real-time and accuracy requirements of the virtual assembly environment.