用于干涉检验的八叉树层次球状模型和相应的快速检验算法

A Hierarchy of Oct-sphere Model and A Fast Detecting Algorithm for Collision and Interference Detection

提出了一种运动物体干涉碰撞检测的快速算法,在进行物体的干涉碰撞检测时,可将物体用一种八叉树层次球状模型描述。给出了构造八叉树层次球状模型的方法,在八叉树层次球状模型的基础上,对运动物体的干涉检验,只需要对物体表面上的模型节点进行相交测试。而且,由于模型节点代表的是一个球形区域,所以,不管物体怎样运动,测试节点间的相交性只要计算节点间的距离即可。最后,给出一个例子,分析了算法的效率。

This paper presents a new effective algorithm for collision and interference detection Objects can be represented for efficient collision and interference detection by a hierarchy of oct-sphere model (HOSM).Algorithms are given for building a hierarchy of oct-sphere model (HOSM) and for detecting collisions and interferences between moving objects.On the basis of HOSM,the algorithm checks only intersections between HOSM's nodes which are on the surfaces of the objects.Furthermore,because a node of HOSM represents a spherical region,collision between two nodes can be easily found just by calculating the distance between two spheres corresponding to them no matter how the objects move.Finally,the efficiency of the algorithm is demonstrated by an example.