基于随机平行六面体包围盒的碰撞检测研究

Research into Collision Detection Algorithm based on Stochastic Parallelepiped Bounding Box

为使包围盒更加逼近原模型,提出一种比一般方向包围盒算法更为灵活的平行六面体自适应包围盒算法.使用时间复杂度仅为O(n)的Melkman算法求解凸包,在此基础上调节收敛公式.在保证复杂度相同的情况下,该算法比一般方向包围盒算法的长方体包围盒体积减少约8%;对较复杂的模型就可以用更少的子包围盒逼近,大大减少相交测试的次数,提高了碰撞检测效率.经过复杂度分析和试验论证,对偏球率介于0.3至0.8的模型,该算法响应速度快、碰撞检测效率较高.

To make a bounding box more approximate to an original model, an algorithm of parallelepiped self-adaptive bounding boxes is proposed. Melkman algorithm whose time complexity is only O（ n） is used to find convex hulls. And on this basis, convergence formula is adjusted. The volume of the cuboid bounding box is reduced by about 8% compared to Oriented Bounding Box when the complexity is the same. In this way, more complex models can be approximated with fewer sub-boundary boxes, which greatly reduces the number of intersection tests and improves collision detection efficiency. Complexity analysis and experimental demonstration confirm that the algorithm has fast response and high efficiency in collision detection of models with similar-to-sphere rate between 0. 3 and 0. 8.