虚拟手术中的快速碰撞检测算法

doi:10.3724/SP.J.1087.2012.00719

计算机应用 ›› 2012, Vol. 32 ›› Issue (03): 719-721.DOI: 10.3724/SP.J.1087.2012.00719

虚拟手术中的快速碰撞检测算法

谢倩茹,耿国华

西北大学信息科学与技术学院, 西安710127

收稿日期:2011-08-23 修回日期:2011-11-13 发布日期:2012-03-01 出版日期:2012-03-01
通讯作者: 谢倩茹
作者简介:谢倩茹(1975-),女,山西万荣人,讲师,博士研究生,主要研究方向:图像处理、模式识别;耿国华(1955-),女,山东莱西人,教授,博士生导师,博士,主要研究方向:三维可视化、模式识别。
基金资助:
国家自然科学基金资助项目(60873094)。

Fast collision detection method in virtual surgery

XIE Qian-ru, GENG Guo-hua

Institute of Information Science and Technology, Northwest University, Xi'an Shaanxi 710027, China

Received:2011-08-23 Revised:2011-11-13 Online:2012-03-01 Published:2012-03-01

摘要/Abstract

摘要： 为了解决当前虚拟手术仿真中使用单一包围盒进行碰撞检测实时性不能满足要求的问题,提出了一种针对虚拟手术的基于层次包围体的快速碰撞检测方法。该方法主要应用了层次包围盒(BVH)的思想,同时根据不同对象的拓扑结构特征,采用不同的包围盒技术来表示。首先,用层次包围盒来表示手术工具,用层次包围球表示手术对象;然后,利用包围球和方向包围盒的相交测试快速排除不相交部分;最后,对于可能发生碰撞的部分再使用更为精确的三角面片相交测试来确定碰撞信息。实验结果表明,在相同的虚拟手术场景下,提出的这种方法较使用单一的层次包围盒具有更快的速度。

关键词: 碰撞检测, 虚拟手术, 包围球, 方向包围盒, 层次包围体

Abstract: The paper proposed an efficient algorithm of collision detection by using Bounding Volume Hierarchy (BVH) in order to improve the real-time performance in virtual surgery. The main contribution of this work was to use the technology of mixed bounding volume hierarchy to represent different objects according to different topology structure. First, surgical instruments and objects were represented as hierarchy tree. Then the intersection test was implemented between sphere and oriented bounding box for eliminating disjoint parts fast. After that more accurate triangle collision test was used to determine the contact status in overlapping parts. Experimental results show that our algorithm achieves higher speed compared to the algorithm of single bounding box.

Key words: collision detection, virtual surgery, bounding sphere, Oriented Bounding Box (OBB), Bounding Volume Hierarchy (BVH)

中图分类号:

谢倩茹耿国华. 虚拟手术中的快速碰撞检测算法[J]. 计算机应用, 2012, 32(03): 719-721.

XIE Qian-ru GENG Guo-hua. Fast collision detection method in virtual surgery[J]. Journal of Computer Applications, 2012, 32(03): 719-721.

参考文献

[1]PALMER I J, GRIMADALE R L. Collision detection for animation using sphere-trees[J]. Computer Graphics Forum,1995,14(2):105-116,

[2]van den BERGEN G. Efficient collision detection of complex deformable models using AABB trees [J]. Journal of Graphics Tools, 1997, 2(4):1-14.

[3]GOTTSCHALK S, LIN M C, MANOCHA D. OBB tree: A hierarchical structure for rapid interference detection[C]// Proceedings of the 23rd ACM Conference on Computer Graphics and Interactive Techniques. New York, USA: ACM Press, 1996: 171-180.

[4]FIGUEIREDO M, FEENANDO T. An efficient parallel collision detection algorithm for virtual prototype environments [C]// Proceedings of the 10th International Conference on Parallel and Distributed Systems. Piscataway, NJ: IEEE Press, 2004: 249-256.

[5]MACIEL A, BOULIE R, THALMANN D. Efficient collision detection within deforming spherical sliding contact [J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(3):518-529.

[6]LAI K C, KANG S C. Collision detection strategies for virtual construction simulation [J]. Automation in Construction, 2009, 18(6):724-736.

[7]CHANG J-W, WANG W P, KIM M S. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy [J]. Computer-Aided Design, 2010, 42(1): 50-57.

[8]MACIEL A, BOULIC R, THALMANN D. Efficient collision detection within deforming spherical sliding contact [J]. IEEE Transactions on Visualization and Computer Graphics, 2007, 13(3): 518-529.

[9]CHANG J W, WANG W P, KIM M S. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy [J]. Computer Aided Design, 2008, 42(1): 50-57.

[10]SPILLMANN J, BECKER M, ESCHNER M. Efficient updates of bounding sphere hierarchies for geometrically deformable models[J]. Journal of Virtual Communication and Image Representation, 2007, 18(2): 101-108.

[11]ARBABI E, BOULIE R, THALMANN D. Fast collision detection methods for joint surfaces [J]. Journal of Biomechanics, 2009, 42(2):91-99.

[12]李红波,周东谕, 吴渝. 基于混合包围盒的碰撞检测算法[J].计算机应用,2010,30(12):3304-3310.

[13]GOVINDARAJU N K, KABUL I, LIN M C, et al. Fast continuous collision detection among deformable models using graphics processors[J]. Computers & Graphics, 2007, 31(1):5-14.

[14]TANG M, MANOCHA D, TONG R. MCCD: Multi-core collision detection between deformable models using front-based decomposition [J]. Graphical Models, 2010, 72(2):7-23.

[15]XIE K, YANG J, ZHU Y M. Fast collision detection based on nose augmentation virtual surgery [J]. Computer Methods and Programs in Biomedicine, 2007, 88(1):1-7.

虚拟手术中的快速碰撞检测算法

Fast collision detection method in virtual surgery

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王江坤, 何坤金, 曹红飞, 王金强, 张燕. 基于光滑粒子流体动力学方法的交互式水流加热仿真[J]. 计算机应用, 2020, 40(5): 1409-1414.
[2]	李丹妮, 刘奇, 田琪, 赵雷昱, 何凌, 黄韫栀, 张劲. 面向上颌骨骨折复位手术的虚拟系统设计[J]. 计算机应用, 2015, 35(6): 1730-1733.
[3]	孙劲光, 吴素红. 基于分类遍历的碰撞检测优化算法[J]. 计算机应用, 2015, 35(1): 194-197.
[4]	施鹏熊岳山徐凯谭珂潘新华. 虚拟肝脏手术中实时动态渗血效果模拟[J]. 计算机应用, 2013, 33(10): 2911-2913.
[5]	史玲玲王伟东闫志远. 虚拟手术中基于可变方向凸包的碰撞检测算法[J]. 计算机应用, 2013, 33(09): 2614-2616.
[6]	于海军马纯永张涛陈戈. 基于图像空间的快速碰撞检测算法[J]. 计算机应用, 2013, 33(02): 530-533.
[7]	向宇侯进徐芳吴铃. 分类应变限制下的服装仿真[J]. 计算机应用, 2012, 32(06): 1589-1593.
[8]	蒲骏逸雷秀仁. 核向量机与支持向量机相结合的二阶段快速学习方法[J]. 计算机应用, 2012, 32(02): 419-424.
[9]	李运锋刘修国. 基于方向包围盒投影转换的轮廓线拼接算法[J]. 计算机应用, 2011, 31(12): 3353-3356.
[10]	陈学工杨兰黄伟季兴. 三维网格模型的布尔运算方法[J]. 计算机应用, 2011, 31(06): 1543-1545.
[11]	王海玲印桂生陈怀友张菁. 基于拓扑层次图的碰撞检测算法[J]. 计算机应用, 2011, 31(02): 347-350.
[12]	陆忠华陈定方. 基于粒子约束的布料实时模拟[J]. 计算机应用, 2011, 31(01): 289-292.
[13]	李红波周东谕吴渝. 基于混合包围盒的碰撞检测算法[J]. 计算机应用, 2010, 30(12): 3304-3306.
[14]	叶秀芬乔冰郭书祥郭庆昌. 虚拟手术仿真中人体软组织形变技术的研究[J]. 计算机应用, 2009, 29(2): 568-573.
[15]	苏新新李学庆祁斌. 基于PhysX物理引擎的布料仿真技术的研究与实现[J]. 计算机应用, 2009, 29(12): 3445-3448.