一种利用Delaunay 三角剖分的碰撞检测算法

虚拟现实中物体对象分布及运动情况呈现复杂多样，碰撞检测算法很难达到实时 性和准确性的要求。提出了一种基于Delaunay 三角剖分的多物体碰撞检测实时算法。该算法运 用包围体紧密拟合物体对象，以包围体的中心构建离散数据点集，生成Delaunay 三角网格，实 施碰撞检测，避免层次包围盒和空间划分的不利因素，物体的更新等操作限定在局部的三角形 内。实验表明在多物体的碰撞检测中，即使存在若干移动物体，算法能够满足实时性和准确性 的要求。

A Collision Detection Algorithm Using Delaunay Triangulation

The distribution and movement of objects in virtual reality show varied complications, so that the real-time and accuracy of collision detection algorithms are difficult to meet the requirements. A real-time algorithm is presented for multi-body collision detection based on Delaunay triangulation. The algorithm uses bounding volume close fitting objects, constructs discrete aggregates using centers of bounding volume, generate Delaunay triangular mesh, implements collision detection. This algorithm avoids the unfavorable factors of bounding volume hierarchy and space division. The update operation of objects is defined in the local triangles. The experiments show that the algorithm can meet the real-time and accuracy requirements in the multi objects detection system in the presence of several moving objects.