基于改进碰撞检测算法的肝门静脉结扎仿真

计算机工程与科学

基于改进碰撞检测算法的肝门静脉结扎仿真

刘敏1，熊岳山1，谭珂2，潘新华2

（1.国防科学技术大学计算机学院，湖南长沙 410073；2.解放军总医院教育技术中心，北京 100853）

收稿日期:2015-05-06 修回日期:2015-07-16 出版日期:2017-01-25 发布日期:2017-01-25
基金资助:
国家自然科学基金(61379103)；北京市自然科学基金(4132080)

Ligaturing simulation of liver blood vessels

based on an improved collision detection algorithm

LIU Min1，XIONG Yueshan1，TAN Ke2，PAN Xinhua2

(1.College of Computer,National University of Defense Technology,Changsha 410073;

2.Educational Technology Center,the PLA General Hospital,Beijing 100853,China)

Received:2015-05-06 Revised:2015-07-16 Online:2017-01-25 Published:2017-01-25

摘要/Abstract

摘要：

为了对虚拟肝脏手术中肝门静脉的结扎进行仿真，提出了一种改进的碰撞检测算法。改进的碰撞检测算法主要包括三个方面：缝合线的自碰撞检测、缝合线的运动分解，以及缝合线与肝门静脉模型的碰撞检测。缝合线的模拟采用跟踪控制点FTL算法，采用包围球法对缝合线进行自碰撞检测；提出运动分解方法来防止缝合线发生自穿透；将包围球法和空间网格划分法相结合，实现缝合线和肝门静脉之间的碰撞检测；同时，肝门静脉的形变采用设置刚体核的几何模型来模拟，使用虚拟弹簧振子来实现结扎时的触觉反馈。将改进的碰撞检测算法运用到虚拟肝脏手术中，满足虚拟场景中真实感和实时性的要求。

关键词: 结扎仿真, 碰撞检测, 运动分解, 触觉反馈

Abstract:

We propose an improved collision detection algorithm for ligaturing simulation of liver blood vessels in virtual liver surgery. The improved algorithm mainly includes three aspects: selfcollision detection of suture, motion decomposition of suture, and collision detection of suture and blood vessels. We employ the follow the leader (FTL) algorithm to configure the motion of suture, and temporary restrictions are set to achieve the suture’s “equivalent friction”. The bounding volume hierarchies (BVH) method increases the efficiency of suture’s selfcollision detection, and the motion decomposition method manages to prevent penetrations. The integration of the BVH method and the grid method can handle the collision detection of suture and liver blood vessels. Moreover, a rigid core is used to limit the deformation of liver blood vessels mesh, and a virtual mass spring is used to implement the haptic feedback of ligaturing simulation. The improved algorithm works well for the ligaturing simulation of liver blood vessels in virtual liver surgery.

Key words: ligaturing simulation, collision detection, motion decomposition, haptic feedback

刘敏1，熊岳山1，谭珂2，潘新华2. 基于改进碰撞检测算法的肝门静脉结扎仿真[J]. 计算机工程与科学.

LIU Min1，XIONG Yueshan1，TAN Ke2，PAN Xinhua2.

Ligaturing simulation of liver blood vessels

based on an improved collision detection algorithm

[J]. Computer Engineering & Science.

参考文献［14］

［1］	Kühnapfel U, Cakmak H K, Maaβ H.Endoscopic surgery training using virtual reality and deformable tissue simulation［J］.Computers & Graphics,2000,24(5):671682.
［2］	LeDuc M,Payandeh S,Dill J.Toward modeling of a suturing task［C］∥Graphics Interface,2003:273279.
［3］	Lenoir J,Meseure P,Grisoni L,et al.A suture model for surgical simulation［M］∥Medical Simulation.Berlin:Springer Berlin Heidelberg,2004:105113.
［4］	Brown J,Sorkin S,Latombe J C,et al.Algorithmic tools for realtime microsurgery simulation［J］.Medical Image Analysis,2002,6(3):289300.
［5］	Brown J,Latombe J C,Montgomery K.Realtime knottying simulation［J］.The Visual Computer,2004,20(23):165179.
［6］	Wang F,Burdet E,Vuillemin R,et al.Knottying with visual and force feedback for VR laparoscopic training［C］∥ Proc of the Engineering in Medicine and Biology Society,2005:57785781.
［7］	Zhang Jingsi.Realtime and haptic suture simulation in virtual surgery:Theory and application［D］.Shanghai:Shanghai Jiao Tong University,2008.(in Chinese)
［8］	Jia Shiyu,Pan Zhenkuan.Realtime knot tying simulation of ropes with haptics［J］.Journal of System Simulation,2009,21(20):65196523.(in Chinese)
［9］	Jia Shiyu,Pan Zhenkuan.Preliminary study of simulating suture operation in virtual surgery［J］.Journal of System Simulation,2012,24(8):16181623.(in Chinese)
［10］	Halperin D, Overmars M H.Spheres,molecules,and hidden surface removal［J］.Computational Geometry,1998,11(2):83102.
［11］	Bergen G V D. Efficient collision detection of complex deformable models using AABB trees［J］.Journal of Graphics Tools,1997,2(4):113.
［12］	Gottschalk S,Lin M C,Manocha D.OBBTree:A hierarchical structure for rapid interference detection［C］∥Proc of the 23rd Annual Conference on Computer Graphics and Interactive Techniques,1996:171180.
［13］	Palmer I J,Grimsdale R L.Collision detection for animation using spheretrees［C］∥Computer Graphics Forum,1995:105116.
［14］	Wang Yanzhen,Xiong Yueshan,Xu Kai,et al.An improved massspring model using surface mesh［J］.Journal of Computeraided Design & Computer Graphics,2007,19(2):168171.(in Chinese)
［15］	Müller M,Schirm S,Teschner M,et al.Interaction of fluids with deformable solids［J］.Computer Animation and Virtual Worlds,2004,15(3):159171.
［16］	Müller M, Stam J, James D, et al.Real time physics:class notes［C］∥Proc of ACM SIGGRAPH 2008 Classes,2008:1020.
	附中文参考文献：
［7］	张静思.虚拟手术中带力反馈的缝合模拟研究［D］.上海：上海交通大学,2008.
［8］	贾世宇,潘振宽.具备触觉反馈的实时绳子打结仿真［J］.系统仿真学报,2009,21(20):65196523.
［9］	贾世宇,潘振宽.虚拟手术中缝合仿真的初步研究［J］.系统仿真学报,2012,24(8):16181623.
［14］	王彦臻,熊岳山,徐凯,等.改进的采用表面网格的弹簧振子模型［J］.计算机辅助设计与图形学学报,2007,19(2):168171.

[1]	魏巍1,2，郭晨1，段晓东2. 虚拟装配中基于公差约束的装配方法研究[J]. J4, 2013, 35(6): 162-173.
[2]	郑延斌, 郭凌云, 刘晶晶. 基于混合包围盒的碰撞检测优化算法[J]. 计算机工程与科学, 2013, 35(4): 87-92.
[3]	胡咏梅. 基于层次包围盒的混合碰撞检测算法[J]. J4, 2012, 34(6): 127-130.
[4]	王晓荣，王萌，李春贵. 基于AABB包围盒的碰撞检测算法的研究[J]. J4, 2010, 32(4): 59-61.
[5]	申静波唐国维李井辉. 基于夹边边对的凸多边形间快速相交检测算法[J]. J4, 2007, 29(12): 93-94.
[6]	熊玉梅陈一民林锋. 任意多面体的剖分算法及应用[J]. J4, 2004, 26(9): 57-61.
[7]	李超陈一民等. JAVA 3D与VRML在机器人仿真和碰撞检测中的应用[J]. J4, 2002, 24(5): 83-85.
[8]	魏迎梅[1] 吴泉源[2] 等. 虚拟环境中的碰撞检测方法[J]. J4, 2001, 23(2): 44-47.