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

Research into Collision Detection Algorithm based on Stochastic Parallelepiped Bounding Box

作　　者：朱大伟[1] 顾勇翔 朱学民 韦智睿 ZHU Da-wei;GU Yong-xiang;ZHU Xue-min;WEI Zhi-rui(School of Communication Engineering,Nanjing Institute of Technology,Nanjing 211167,China)

机构地区：[1]南京工程学院通信工程学院,江苏南京211167

出　　处：《南京工程学院学报（自然科学版）》2018年第2期69-73,共5页Journal of Nanjing Institute of Technology(Natural Science Edition)

基　　金：南京工程学院大学生科技创新基金项目(TB201806029)

摘　　要：为使包围盒更加逼近原模型,提出一种比一般方向包围盒算法更为灵活的平行六面体自适应包围盒算法.使用时间复杂度仅为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.

关 键 词：分离轴定理 一般方向包围盒算法 Melkman算法 碰撞检测 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]