Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (17): 172-174.

• 图形、图像、模式识别 • Previous Articles     Next Articles

Improved collision detection based on dual Sphere-OBB bounding volume hierarchy and its application

JIANG Jianxun1,FANG Zhigang1,2,XU Jie2,WANG Xiaochi2   

  1. 1.Department of Information Science & Electronic Engineering,Zhejiang University,Hangzhou 310027,China
    2.Zhejiang University City College,Hangzhou 310015,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-06-11 Published:2011-06-11

基于Sphere-OBB的改进碰撞检测算法及其应用

蒋健勋1,方志刚1,2,徐 洁2,王晓池2   

  1. 1.浙江大学 信息与电子工程学系,杭州 310027
    2.浙江大学 城市学院,杭州 310015

Abstract: The problems of collision detection between two or more geometric models in static and dynamic environments are fundamental in computer graphics.Bounding volume hierarchy has proved to be the most successful in contemporary systems.This research presents an efficient algorithm for collision detection using a dual bounding hierarchy which consists of an Oriented Bounding Boxes(OBB) tree enhanced with bounding sphere.This algorithm combines the compactness of the OBBs with the efficient overlap test for spheres.More efficient sphere test is applied first to eliminate distant objects.The remaining objects in close proximity are tested using separation axis.Some separation axes are more effective and should be chosen first.The approach is applied to the acupuncture medical treatment systems,and the experimental results show that the new algorithm effectively reduces the query time and enhances the reality character.

Key words: collision detection, sphere, Oriented Bounding Boxes(OBB)

摘要: 静态或动态环境中两个或者多个几何模型之间的碰撞检测是计算机图形学基础问题之一,基于层次包围盒的碰撞检测算法是一种比较有效的碰撞检测算法。提出了OBB包围盒与球包围盒相结合的高效碰撞检测算法,该算法既具有OBB的包围紧密性,又具有球包围盒的测试简便性。用高效的球包围盒排除大量距离远的不相交物体,剩下距离近的物体用分离轴测试,其中一些分离轴效率更高应该优先被测试。将该算法用于虚拟针灸训练系统,实验结果表明算法减少了查询时间并增强了实时性。

关键词: 碰撞检测, 球包围盒, 有向包围盒(OBB)