用于心脏手术仿真的虚拟力反馈模型及软件实现

单位代码 10006 学 号 分类号 密 级 秘 密 毕业设计(论文)用于心脏手术仿真的虚拟力反馈模型及软件实现院（系）名称生物与医学工程学院专业名称生物工程学生姓名王青春指导教师刘文勇2014年6月用于心脏手术仿真的虚拟力反馈模型及软件实现 王青春 北京航空航天大学 北京航空航天大学本科生毕业设计（论文）任务书、毕业设计（论文）题目： 用于心脏手术仿真的虚拟力反馈模型及软件实现 、毕业设计（论文）使用的原始资料（数据）及设计技术要求：原始资料：7自由度的力反馈器（Omega.7）（已购买） 心血管主动 脉弓的几何建模（初步完成） OpenGL开发环境（已搭建） Chai3D Demo源代码（已获得） 技术要求：1. 实现三维心脏模型的变形显示 2. 实现三维心脏模型的实时力反馈计算 3. 利用Omega.7实现三维心脏模型的力感知 、毕业设计（论文）工作内容：1. 搭建虚拟力反馈硬件平台 2. 编写基于Chai3D/OpenGL的软件平台 3. 建立心脏三维几何模型 4. 实现一种心脏受力变形算法 、主要参考资料：Majumder S, Roychowdhury A, Pal S. Simulation of hip fracture in sideways fall using a 3D finite element model of pelvisfemursoft tissue complex with simplified representation of whole bodyJ. Medical engineering & physics, 2007, 29(10): 1167-1178. Xie K, Yang J, Zhu Y M. Fast collision detection based on nose augmentation virtual surgeryJ. Computer methods and programs in biomedicine, 2007, 88(1): 1-7. Verlet L. Computer experiments on classical fluids. I. Thermodynamical properties of Lennard-Jones moleculesJ. Physical review, 1967, 159(1): 98. 生物与医学工程 学院（系） 生物工程 专业类 101011 班学生 王青春 毕业设计（论文）时间： 2014 年 3 月 1 日至 2014 年 5 月 25 日答辩时间： 2014 年 6 月 10 日成 绩： 指导教师： 兼职教师或答疑教师（并指出所负责部分）： 系（教研室） 主任（签字）： 注：任务书应该附在已完成的毕业设计（论文）的首页。本人声明我声明，本论文及其研究工作是由本人在导师指导下独立完成的，在完成论文时所利用的一切资料均已在参考文献中列出。作者：王青春签字：时间：2014年 6 月北京航空航天大学毕业设计(论文)第 32 页用于心脏手术仿真的虚拟力反馈模型及软件实现学 生：王青春指导老师：刘文勇摘要由于现代人生活方式和生活条件的变化，心脏病日益成为一种常见疾病，同时心脏手术的需求量也急剧增加，然而由于培训方式和材料的特殊性，目前远远无法满足需求。虚拟现实技术是利用电脑模拟产生一个三维的虚拟世界，提供给使用者视觉、听觉、触觉等感官的模拟，让使用者如同身临其境一般，可以及时、没有限制的观察三维空间内的事物，使用者进行位置移动时，计算机可以立即进行复杂的运算，将改变后的三维世界影响传回产生临场感。随着硬件和软件技术的发展，以及对虚拟现实技术研究的不断深入，目前已经有条件实现虚拟手术。针对这个问题，本课题以虚拟现实技术为基础，以虚拟环境中的心脏模型作为研究对象，以Omega.7作为力反馈设备，用于向虚拟对象施加作用力，同时对输入的力用配备英伟达专业显卡的图形工作站进行处理，将得到的反作用力反馈给使用者，从而得到真实可感的力觉和触觉反馈。这种方法有望克服传统医生训练过程中采用人或其他动物标本作为研究对象的诸多缺点，可以更高效、便捷的培养外科医生，使其足以承担心脏手术的工作，满足患者对手术的需求。本课题主要借助开源项目Chai3D和由瑞士Force Dimension提供的力反馈设备Omega. 7进行。Chai3D提供了一套对虚拟环境中的对象进行操作的编程接口和一组示例程序，可以在此基础上进行二次开发得到针对心脏手术的算法。Qt是一个跨平台的C+应用程序开发框架，提供了一套便捷的C+图形库和集成开发环境，原生支持OpenGL程序，为了更便捷的对虚拟环境中的对象进行操作，将给这个系统原型添加一个基于Qt的图形前端。同时本次研究作为虚拟手术仿真项目的一个先导课题，为后续的深入研究做一些基础性工作。关键词：心脏手术，手术仿真，力反馈，虚拟现实，碰撞检测A virtual force feedback model for the simulation of cardiac surgery and its software implementationAuthor: 王青春Tutor: 刘文勇AbstractAs peoples life style and quality is changing rapidly, heart disease has been developing to a common disease thus theres a great need of doctors who can handle such operations. However, because of the special methods and special materials they use, much more doctors are needed for now.Virtual Reality technology is a technology which generates a three-dimensional virtual world with computers, supplying visual and hearing and haptic simulation, making the users feel that they are actually in the real environment, where they can observe the objects in the virtual world in time and without any limits, when the users move, the computers compute the new world in almost no time and then give the new world to the users.Computers are changing the world everywhere. Now both the hardware and software technology have been developed in a significant degree, in addition to the research in virtual reality theory, virtual surgery can be realized for now.The heart model in the virtual environment acts as the object being manipulated, forces and torques applied to the heart model via the haptic device Omega.7, and then the feedback forces and torques are computed in the workstation equipped with a nVIDIA Quadro graphics card and then exported via the same haptic device. Thus users can obtain a real force and haptic feedback. This training method is promising to avoid the disadvantages of the traditional methods in which human or animal specimens are used to simulate the real organism of a live human. The open source project Chai3D is used in the subject to supply the algorithm of force and torque feedback and the haptic device Omega.7 is used to implement the feedback. Qt is corss-platform C+ development framework which is not only a productive tool but also very beautiful and looks like native applications, hence, I also add a Qt5 front-end to the system in order to make it easier to use.This subject is a sub-subject of the virtual surgery system, the research also do a lot of foundational works for incoming research.Key words: Cardiac surgery, Simulation, Force feedback, Virtual-Reality technology目 录1绪论11.1 研究背景11.2 研究内容11.3 研究现状21.4 研究意义31.5 研究方法31.5.1 硬件方面31.5.2 软件方面51.5.3 理论基础71.6 论文构成72方案设计82.1 实验材料82.2 碰撞检测算法92.2.1 轴对齐包围盒法122.2.2 包围球法122.2.3 方向包围盒法122.2.4 固定方向包围盒法122.3 力反馈算法142.3.1 有限元模型152.3.2 弹簧-质点模型152.4 变形算法173平台搭建183.1 硬件平台183.1.1 硬件选择183.1.2 安装软件环境183.1.3 设备初始化193.1.4 问题排除193.1.5 效果示例203.1.6 小结204实验步骤224.1 模型处理224.1.1 模型获取224.1.2 格式转换224.1.3 材质处理244.2 模型导入245结果26结论27致谢28参考文献29附录A 计算反作用力30附录B 计算力的效果311 绪论1.1 研究背景随着现代人生活方式和习惯的改变，饮食结构发生了很大变化，高糖、高蛋白、高脂肪含量的食物越来越普遍，加上生活环境的恶化，工作、生活和经济压力的增加，都导致现代人心脏病发病率明显增高。据统计，我国每年有超过15万人接受心脏手术，而需要接受心脏手术的患者多达800万人1，这产生了对能胜任心脏手术的外科医生的巨大需求。同时由于现代外科手术的复杂程度越来越高，不经过充分的训练，很难适应现代外科手术的要求。据统计，通常训练一名合格的外科医生需要5-7年的时间2，其间医生必须进行大量的手术训练。对医生进行手术训练的传统方法是使用人体或动物标本代替病人进行3，然而动物的解剖结构与人体的解剖结构不同，而尸体的材料特性与活体组织都存在较大差异，这些缺点严重地影响了培养外科手术医生的效果和效率。同时这类方法使用的材料都存在资源短缺，同时无法重复使用的缺点，因此培训成本很高。现代计算机技术的发展日新月异，尤其是虚拟现实技术已经渗入到我们生活的方方面面，但力触觉结合的虚拟现实技术在软组织中的应用仍不太广泛。应用这种虚拟现实技术，使用者可以通过终端输入操作数据，数据经计算机处理后反馈给使用者相应的力觉和触觉，让使用者获得如在真实世界中触摸物体一样的感官体验4。同时，虚拟手术可以模拟活体组织的各种物理特性和生理特性，提高培训效果；此外由于所用的电子设备都可以重复使用，并可以根据实际需要修改以提供不同类型的实验对象，从长远看来可以大大降低培养外科医生的成本。1.2 研究内容研究内容主要分为以下几个部分：1. 搭建虚拟力反馈硬件平台硬件主要用到了由瑞士Force Dimension提供的Omega.7力反馈设备和一台图形工作站，由于后期需要3D立体显示和对OpenGL的硬件加速需要，还配备了一块nVIDIA高性能专业显卡。2. 编写基于Chai3D/OpenGL的软件平台软件系统架构在开源项目Chai3D之上，而Chai3D中大量使用了OpenGL的API，支持7种力反馈设备，具有良好的通用型。3. 建立心脏三维几何模型心脏模型是由CT成像技术得到的，但原始图像文件无法适用于Chai3D系统，需要做多步处理。4. 实现一种心脏受力变形算法心脏模型是静态的，而虚拟手术中需要其在受到外力的作用后作出相应的外形变化同时计算出对虚拟末端控制器的反作用力，并表现到力反馈设备上。5. 形成心脏手术虚拟仿真训练系统原型原计划编写一套基于Qt的仿真训练系统，但研究中发现Qt的pro工程文件和Chai3D中使用的Makefile差别较大，从后者移植到前者的结构需要大量时间和精力，考虑到毕设时间限制，该步没有完成。1.3 研究现状目前，国外已经有许多商业公司和研究机构对虚拟手术仿真技术做了深入的研究和实践，如美国波士顿力学研究中心对虚拟手术器械模拟操作的研究，加利福尼亚圣弗朗西斯科大学外科系与伯克利学院的电子工程与计算机科学系对虚拟腹腔手术的研究，斯坦福大学的SRI正在进行的对组织和脉管缝合的虚拟手术技术的研究等；在欧洲，法国国家信息和自动化研究所（INRIA）、德国国家信息技术研究中心（GMD）、法兰克福计算机图形研究所（IGD）等研究单位也对虚拟手术及相关的技术进行了深入的研究5。我国关于计算机建模和仿真的研究开展较早，在上世纪70年代初主要集中在航空航天领域。数十年来，我国多所高校入北京航空航天大学、浙江大学、清华大学、北京大学、国防科技大学等和多所科研院所及其他许多应用部门和单位的研究人员进行了各具背景、各具特色的研究工作4。近年来国内的研究多集中在对医学图像的三维重建及可视化方面，但对带有力反馈的虚拟手术系统，尤其是软组织如脏器等的手术仿真研究方面投入较少。苏永松等人在2002年设计了基于二维鼠标的骨科手术模拟系统6；谭珂等人在2005年设计了鼻腔镜虚拟手术仿真系统7；许天春等人在2006年也使用PHANToM设备设计了一个声带肿物切除仿真系统8。1.4 研究意义虚拟手术对于现代外科手术具有积极的推动作用。首先，它可以为外科医生培训提供用之不尽的实验对象。传统的培训中使用的动物或人体标本都存在或资源短缺或与实际活体组织各方面物理属性和生理属性不同的缺点。虚拟手术充分利用了虚拟现实技术对视觉和触觉的支持，可以根据不同情况调整参数，提供不同种类的实验对象，大大提高了培训灵活性。其次，传统的培训使用的两种材料都无法重复使用，导致训练的成本高昂且效率低下，由于虚拟手术使用的电子产品，可以提供近乎无限次地使用寿命，从长远观点看，将极大的降低总体培训成本。最后，由于虚拟手术极强的定制性，不仅可以用于外科医生的培训，还可以满足不同的需求，比如对手术结果进行预测，辅助制定手术计划和手术导航等。本课题是使用比较新的组合Omega.7力反馈设备（配置Force Dimension驱动和Chai3D）进行虚拟手术研究的一次尝试。国内对于力反馈方面的研究工作多集中于使用美国SensAble公司提供的PHANToM力反馈设备（配备GHOST SDK开发包），而对Chai3D的研究目前还较少，虽然Chai3D可以支持包括PHANToM在内的7种力反馈设备，但事实上由于设计生产Omega.7力反馈设备的瑞士Force Dimension公司和Chai3D的关系，Chai3D可以完美支持Force Dimension公司生产的力反馈设备的所有功能。课题的目标是实现一个操作界面基于Qt，后端动作基于Chai3D的虚拟手术系统的原型，然而由于前期对工作量的预计失误，导致Qt和Chai3D的结合在结题时仍无法完成，但在研究的过程中总结了一套经验和教训，为后续的研究提供了借鉴。1.5 研究方法1.5.1 硬件方面力反馈设备使用了瑞士Force Dimension公司的固定式力反馈装置，采用独特的并联运动结构，将轻巧的铝制金属杆与牢固的传动装置结合在一起，具有超高的性能。它共有7个自由度，包括3个平移自由度，3个旋转自由度和1个抓取功能。其中平移关节和抓取关节都具有力反馈。它具有卓越的机械刚度，同时采用实时USB2.0控制器，在Windows下可以以4.3kHz左右的速率对接触力进行处理，而在Linux下可以达到稳定在7.9kHz左右，远远高于最低标准500Hz8，这样在发生碰撞检测时可以获得平滑的效果，保证力触觉交互系统的稳定性。为了确保较高的触觉透明度，设备通过将启动与未启动的部件相结合，保证了在平移和其他方向区域的重力补偿。每个系统均可进行单独校准，确保可重复的最佳精度和性能。前期由于Omega.7未到货，暂时用国内的代理商红京鸟（北京）科技有限公司临时提供的Omega.3作为替代，二者在基本功能和性能上无差异）。Omega.7在Omega.3的基础功能上，将末端控制器改为具有夹取功能的力反馈手柄，并包括左右手配置，可以建立双手工作站以实现双手控制，从而增加了高精度主动式抓握功能和方向感功能。其中12N的持续力反馈与8N的夹取力，可以满足在虚拟显示技术研究中的基本需求。 (a) Omega.3设备 (b) Omega.3末端控制器 (c) Omega.7设备 (d) Omega.7末端控制器图 1.1 Omega.3和Omega.7对比在图形和图像运算方面，由于运算量较大且对实时性的要求较高，同时考虑到经费的因素，选择了采用最新开普勒架构的英伟达的专业级显卡Quadro K5000，显存带宽173GB/s，具有1536个流处理器、128个纹理单元、32个ROP单元，核心频率700MHz左右，搭配256位4GB GDDR5显存，最高支持分辨率为4096x2196。同时支持3D输出，可以满足后续研究中添加3D显示器的需求。在通用计算方面，由于需要渲染的数据量巨大，为了从根本上避免性能低下的集成显卡带来的影响，并且尽可能的提高CPU的整体性能，同时考虑了价格因素，选择了英特尔E3 1230v3。它是由Intel发布的Haswell架构的LGA1150型CPU，默认主频3.3GHz，具有4个物理核心，同时由于超线程技术实际上可利用8线程，性能强劲。其他方面，考虑整体性能，选择2*4G 1600mHz内存，加配128G固态硬盘作为系统盘，大大提高了系统的整体性能。1.5.2 软件方面软件方面分为运行环境和开发工具，运行环境主要依赖Force Dimension和Chai3D，而开发工具根据平台不同，在Windows平台下采用Visual Studio2013（由DreamSpark提供专业版授权）和Qt Creator 5.3（beta），Linux平台下采用Vim 7.4和Qt Creator 5.2。OpenGL全称“开放式图形库”，它是一个方便和快速的三维图形和模型库。最初算法是由SGI（Silicom Graphics, Inc）公司开发和优化的。它定义了一个跨程序设计语言、跨平台的应用程序接口（API）规范，用于生成二维、三维图像，这个接口由近350个不同的函数调用组成，用来从简单的图形位元绘制复杂的三维图像。OpenGL的高效实现（利用了图形加速硬件）存在于Windows、很多UNIX平台和OS X，这些实现一般由显卡厂商提供，而且非常依赖于该厂商提供的硬件。OpenGL规范描述了绘制二维和三维图形的抽象API，尽管这些绘制可以由软件实现，但它是为大部分或者全部使用硬件加速而设计的。OpenGL与语言无关，但出于性能的考虑，台式计算机本地的应用程序一般使用C+语言实现，同时Chai3D也是用C/C+作为实现语言。在项目进行时，所用的英伟达驱动程序支持OpenGL 4.4标准。Force Dimension是Omega系列力反馈设备配备的原厂驱动程序，同时内置了一系列简单的示例程序和性能测试工具，能够很好的检测设备是否能够正常运行。Chai3D是一套为计算机触觉、视觉和实时交互仿真而设计的开放源代码并且可以自由获得的C+库。Chai3D支持7种商业许可的三自由度、六自由度和七自由度的触觉设备，并且让支持新的定制的触觉设备成为可能。Chai3D尤其适合教育和科研的目的，因为它提供了一个轻量级的平台，可以在这个平台上开发扩展。Chai3D支持多个触觉设备，因此可以很容易的将应用程序发送到远程的不同的硬件设备上执行。本课题使用Chai3D 2.0版本。Windows平台上的Visual Studio是最常用的C/C+集成开发工具，它是一个基本完整的开发工具集，包括了软件生命周期中所需要的大部分工具，如UML工具、代码管控工具、集成开发环境等等，所写的目标代码适用于微软支持的所有平台。Windows平台上使用了Qt Creator 5.3，而不是当时的稳定版本5.2，是由于Qt Creator自身并不集成编译器，需要使用系统已有的编译器，5.2在当时只支持稍旧的Visual Studio2012编译器，无法适用于已经存在的Visual Studio 2013，因此需要使用稳定性差一下（使用过程中并未发现异常情况）但已经支持最新版Visual Studio 2013的Qt Creator 5.3RC版。它是一款跨平台的集成开发环境，特别针对Qt开发者，是Qt SDK的组件，可运行于Windows、Linux/X11及OS X等操作系统平台，允许开发者为多桌面环境及移动设备平台创建应用程序。同时Qt内建了对OpenGL的支持，能较好的支持用Qt为操作提供前端界面的目的。在处理心脏模型中用到了一系列图像处理软件，具体如下：1、 MimicsMimics是一种专门为处理医学图像而开发的商业软件。用Mimics处理三维医学图像断层（来自CT、MRI、micro-CT、CBCT、3D超声、共聚焦显微镜）并导出病人解剖学的高度精确的三维模型。可以继续用这些根据病人区分的模型进行不同的工程应用开发。在本课题中用其对原始工程文件进行处理，导出每个部位的独立文件，然后选择需要的部位在blender中进行连接。2、 BlenderBlender是一套三维绘图和渲染软件，支持几乎所有的操作系统平台，支持不同的几何图元，包括多边形网纹、快速表层塑模、曲线及矢量字符，使用Python语言来创作及制作游戏及工作自动化脚本。在本课题中，将选择的8个部位的图形文件以此导入blender中，将其连接在一起，并导出obj文件，交给Geomagic Studio继续处理。3、 Geomagic StudioGeomagic Studio是将三维扫描数据转换为高精度曲面、多边形和通过CAD模型的整套工具组。其整合了强大的自动化工具，可以使使用者显著缩短时间并降低人力成本。它提供了简化模型功能，在本课题中主要利用它简化模型的功能，因为原始模型文件过于复杂，不仅没有必要而且会严重影响结果的实时性。4、 MeshLabMeshLab是立体网格处理软件，可管理和处理大量的非结构化网格，并提供编辑、清理、修复和查核等功能，可对模型进行渲染和格式转换。在本课题中，使用MeshLab将已经使用Geomagic Studio简化过的模型文件进行属性编辑，如加上材质库信息，并导出适当的格式。1.5.3 理论基础课题主要涉及三个方面的理论研究。1、碰撞检测碰撞检测是整个课题的基础，顾名思义，就是检测在虚拟环境中的两个物体是否能发生碰撞和碰撞发生后的一系列变化，如变形和产生的反作用力9。这方面比较成熟的方法是使用轴对齐包围盒（Axis Aligned Bounding Box，AABB）检测算法。2、力反馈算法力反馈算法主要有两种方法，一种是用简单但精度不高的弹簧-质点模型，另一种用有限元分析法。前者简单实用，但精确度不高，后者运算复杂并且计算量极大，很难满足实时性的要求10。由于本课题面对的实时性目的，同时Chai3D的力反馈算法也是使用弹簧-质点模型，本文主要讨论弹簧-质点模型。3、变形算法变形算法分为两种情形，当虚拟对象可以变形时，且整体相对全局坐标系的位置不发生变化时，则变形量根据虚拟操纵终端的位移决定；当虚拟对象不可变形，且虚拟对象只有中心位置固定，而整体可以运动时，则在受到外力时，虚拟对象绕中心转动，并不会发生表面的形变。1.6 论文构成文章主要分下面几部分。第二章方案设计，主要讲述虚拟对象与虚拟操纵终端之间的碰撞检测算法的研究和移植。第三章平台搭建，介绍虚拟力反馈系统软硬件的搭建详细过程。第四章实验步骤，介绍心脏模型处理和实现力反馈效果的过程。第五章结果，总结本课题所得到的结果。2 方案设计2.1 实验材料整个过程中使用的虚拟对象是由（安贞医院）提供的心脏模型。该心脏模型是由CT图像经过处理得到的，并且已经根据心脏各个部分性质在Mimics中根据阈值调整而分割开。整个过程中用到了几种中间文件格式。详细如下：1、 mcsMimics的工程文件，心脏模型原始文件格式，通过这种格式将心脏的各部分分开，得到后续步骤中需要用的文件。图 2.1心脏模型原始文件2、 ASCII stl计算机图形系统中用于表示三角形网格的一种文件格式，它的格式非常简单，应用广泛，它是快速原型系统所应用的标准文件类型，是用三角网格来表现三维CAD模型。这里用其作为向目标文件类型的中间格式，因为Mimics无法直接导出为obj，而obj和3ds是Chai3D所支持的文件类型。3、 3ds3D Studio R4网格文件格式，其包括以下信息，视图中的背景（实心、渐变和位图），场景中的雾、分层雾和距离线索，场景中的环境光级别，材质中相减的透明度转换为“过滤器”透明度，而过滤器的颜色设置为“漫反射”，材质的透明度衰减设置，材质中所有贴图通道，所有贴图参数，包括UV变换、负值、景象和螺旋，材质中的自动反射贴图第N帧和“贴图尺寸”设置，对目标材质和“噪波”进行SXP平移。这里使用3ds文件类型时三角面片数量不能大于65536，这个限制导致图像无法太精确。4、 ObjAlias Wavefront公司为它的一套工作站的3D建模和动画软件Advanced Visualizer开发的一种标准3D模型文件，适合在不同的3D软件模型之间作为中间文件互导。Obj文件是一种文本文件，可以直接用文本编辑器软件查看和编辑修改。Obj文件格式支持直线、多边形、表面和 自由形态曲线，直接通和多边形通过它们的点来描述，曲线和表面则根据它们的控制点和依附于曲线类型的额外信息来定义，这些信息支持规则和不规则的曲线，包括基于贝塞尔曲线、B样条、基数和泰勒方程的曲线。它不包含动画、材质特性、贴图路径、动力学、粒子等信息。因此，在Chai3D中使用obj文件需要对应的mtl文件来表明其材质。obj文件不包含面的颜色信息，不过可以引用材质库，材质库信息存储在一个后缀是mtl的独立文件中，obj文件中的mtllib即材质库的意思。材质库中包含材质的漫射（diffuse）、环境（ambient）、光泽（specular）的RGB的定义值，以及反射（specularity）、折射（refraction）、透明度（transparency）等其他特征。2.2 碰撞检测算法碰撞检测自20世纪80年代开始受到人们的重视，在计算几何和机器人等领域得到了广泛的研究和应用12，形成了一些较为成熟的技术。简单地讲，碰撞检测就是检测虚拟场景中不同对象之间是否发生了碰撞。从几何上讲，碰撞检测表现为两个多面体的求交测试问题；按对象所处的空间可分为二维平面碰撞检测和三维空间碰撞检测。平面碰撞检测相对简单一些，已经有较为成熟的检测算法，而三维空间碰撞检测则要复杂很多13-14，主要是如何解决碰撞检测的实时性和精确性的矛盾。在不同的应用场景中，对精确性和实时性的要求不同，就本课题而言，目标是应用在虚拟心脏手术的仿真系统中，因此对实时性的要求比较高，但同时由于是手术仿真，要求其精度也要达到相当高的要求。碰撞检测算法主要有以下几类：基于包围盒的碰撞检测算法，基于距离计算的碰撞检测算法，基于维诺图的碰撞检测算法。其中，基于距离计算的碰撞检测算法和基于维诺图的碰撞检测算法只能解决凸多边形之间的碰撞检测，对于本课题中形状较为复杂的心脏模型都不适用，因此采用包围盒碰撞检测算法。包围盒法的基本思想是使用简单的几何体来代替复杂的几何体，先对对象的包围盒进行粗略的检测，当包围盒之间可以相交时，对象本身才有可能相交，当包围盒之间不可相交，则对象本身也一定不相交。这样就可以排除大量不可能相交的几何体和几何部位，从而更加快速的找到相交的对象。一个对象可以用不同的层次表达的包围盒来近似对象，结合层次表达法如二叉树，可以把对象用近似包围盒分层次的表达，使用一个大的包围盒包围住整个对象，再把对象分成两部分，用两个包围盒包围各自的部分，这样细分下去，直到每个包围盒只包含一个基本的几何元素，形成一棵层次表达的包围盒二叉树。这样在进行碰撞检测时只需要根节点遍历包围盒二叉树，那么这两个对象不相交，否则继续向下一级走，进行下一级的碰撞检测，如果在某个节点两个包围盒不相交，则以该节点为根节点的子树就不需要再检测。当检测到叶节点时，如果叶节点包围盒相交就要进行基本的几何元素的相交检测，否则这两个基本几何元素不相交。这样通过由粗到细的检测，只有粗检相交的对象才进行下一级更细的检测，可以提前筛选出不可能相交的对象，大大加快了碰撞检测的时间。算法流程图如下：图 2.2碰撞检测算法流程图目前存在多种为计算机图形学和计算机视觉的不同应用而开发的不同的包围盒，例如方向包围盒（Oriented Bounding Box, OBB），离散方向多边形（Discrete Orientation Polytope, k-DOPs），固定方向包围盒（Fixed Directions Hulls，FDH），球包围盒（Bounding Sphere）和轴对齐包围盒（Axis Aligned Bounding Box, AABB）等15。2.2.1 轴对齐包围盒法轴对齐包围盒法简单性好，但是紧密型差；当物体旋转之后需要对包围盒进行同样的旋转并更新；当物体变形之后只需要对变形了的基本几何元素对应的包围盒重新计算，然后可以自底向上由子节点的包围盒合成父节点的包围盒，最后进行包围盒树的更新。因此轴对齐包围盒法尤其适合可变形对象的碰撞检测。2.2.2 包围球法层次包围球法简单性好，无论几何体相交检测都很简单；但是它的紧密型差；但是当物体旋转之后，层次包围盒不用更新；当物体变形之后，包围球树需要重新计算。因此包围球法不适合可变形对象的碰撞检测。2.2.3 方向包围盒法方向包围盒法是Gottschalk在1996年实现的RAPID系统中首先使用的，当时该系统声称是最快的碰撞检测系统，曾一度作为评价碰撞检测算法的标准。方向包围盒的计算相对复杂，其关键是寻找最佳方向，并确定在该方向上包围对象的包围盒的最小尺寸。方向包围盒间相交测试的代价比较大。但是它的紧密型是最好的，可以成倍的减少参与相交检测包围盒的树木和基本几何元素的数量，在大多数情况下其总体性能优于轴对齐包围盒和包围球。此外，当几何对象发生旋转运动后，只要对方向包围盒的基底进行同样的旋转即可。因此，对于刚体的碰撞检测，方向包围盒是一种较好的选择，但至今为止，还没有找到一种更有效的方法来解决对象变形后方向包围盒树更新的问题，而重新计算每个节点的方向包围盒的代价太大。因此，方向包围盒法无法满足可变形对象碰撞检测中的实时性要求。2.2.4 固定方向包围盒法固定方向凸包法优于包围盒的所有面的法向量均来自一个固定的方向向量集合，它的简单性比较好；它的紧密性也是比较好的；当物体旋转之后，可以通过线性规划的方法来进行优化计算；当物体变形之后可以通过重新计算变形叶节点的包围盒，然后严格按照自底向上的顺序，由子节点的固定方向包围盒合成父节点的固定方向包围盒。总体比较结果如下表：表 2.1几种包围盒法比较包围盒方法简单性紧密型旋转后更新变形全部重新计算适用可变形对象AABB好差是否是BS好差否是否OBB差最好否是否FDH好较好可优化否综上，AABB法最适合用于可变形对象，在本课题中是虚拟心脏模型的场景一个对象的AABB被定义为包含该对象，且边平行于局部坐标系的坐标轴的最小立方体。因此，描述一个AABB，仅需要六个标量。在构造AABB时，需沿着物体局部坐标系的轴向（X, Y, Z）来构造，所以所有的AABB具有一致的方向。AABB树是基于AABB的二叉树，按照从上到下的递归细分方向构造生成。在每一次递归过程中，要求取最小的AABB，需沿所选的剖面分别将对象分为正负两半，并将所对应的原始几何元素分别归属正、负两边，整个递归过程类似于空间二叉剖分，只是每次剖分的对象是AABB，而不是空间区域。递归细分一致要进行到每一个叶子节点只包含一个原始几何元素为止，所以具有n个原始几何元素的AABB树具有n-1个非叶子节点和n个叶子节点。对于剖分面的选择，一般是选择垂直于AABB的最长轴，且平分该轴的平面。经试验证明，采用这种方式，大多数情况下算法的复杂度为O(1)，较其他剖分面选择方法有了极大的提高。至于原始几何元素的归属依据几何元素的重心P在最长轴的投影坐标来确定。若投影坐标大于剖分面的坐标，则在剖分面的正向；否则在负向。图 2.3树状层次包围盒图2.3展示了一个典型的轴对齐包围盒。虚拟心脏的中心是局部坐标系的坐标原点，包围盒是能包围住虚拟心脏的最小的立方体，如果虚拟心脏的形状比较复杂（如图2.1），则会以树状分层结构构造多个包围盒。2.3 力反馈算法虚拟手术的仿真，就是通过对真实人体的组织结构和物理属性来进行几何建模和物理建模，来逼真的模拟组织器官在真实手术器械的外力交互作用下变形甚至被切割的过程，同时通过视觉/力学反馈的形式来提供逼真的手术现场临场感。为了达到高度的真实感，虚拟手术仿真技术中面临两个关键的技术难点，高逼真和精确的人体组织器官建模技术和高逼真度和实时的人体组织力觉（触觉）反馈技术。力反馈是一种重要的触觉通道，这种作用于体内的触觉通道可以感知物体的重量以及物体对外力产生的反作用力。只有提供与世纪手术中相近的力反馈，虚拟手术的仿真才有现实意义。虚拟环境中的力的表示采用了机器人学和遥控学中描述的算法和模型来进行底层控制。虚拟手术系统中的力反馈必须要维持一个非常高的刷新频率，否则使用者会感觉到力反馈设备的震动而不是从虚拟对象传出的反作用力，因此一般要求刷新频率高于500Hz。实际Omega.7力反馈设备的性能（最高8kHz）要远远超出这个标准。力反馈算法主要有两种模型可以选择。2.3.1 有限元模型有限元分析是一种求解微分方程组或积分方程组数值解的数值技术，这一解法基于完全消除微分方程，即将微分方程转化为代数方程组，或将偏微分方程（组）改写为常微分方程（组）的逼近，这样可以用标准的数值技术进行求解。利用有限元方法可以得到精细的反作用力，但存在一个很严重的缺陷，就是针对目前的硬件系统，尚远远达不到实时性的要求。因为有限元需要的数据量极大，并且在使用者操作系统的过程中，虚拟对象和虚拟操纵终端的位置及相互作用的关系在不断变化，需要大量的实时运算。因此，在实际的力反馈研究中很少有使用有限元方法进行反作用计算的先例。2.3.2 弹簧-质点模型弹簧-质点模型和有限元模型是两种常用的形变模拟模型。弹簧-质点模型的原理简单，计算也较为简单，容易满足实时性的要求，但是精度较差；而有限元模型模型复杂，精度较高。Chai3D系统中，computeForces()方法使用的即是弹簧-质点模型，利用胡克定律进行计算。在这里有一个非常重要的概念虚拟代理（Virtual Proxy），虚拟代理是假设虚拟操纵终端上连接的一个虚拟物体。自然状态下虚拟代理的运动是贪婪的（greedy），只要没有被阻挡，它会一直沿着力的方向运动。一旦它在虚拟环境中碰上了表面或者某个对象，它的就会被限制在表面上的位置，这种情况下真实对象的内陷深度会在局部达到最小。这是通过基于虚拟代理的位置和速度（也就是虚拟操纵终端的位置和速度）来预测两个物体可能发生碰撞的位置实现的，其中位置和速度是通过其运动轨迹上前一帧和简单线性插值来获得的。在当前帧的开始，连接在虚拟操纵终端上的物体被限制只能在一个基于预先设计的距离阈值，从而来使内陷的值最小化。首先设定虚拟对象和虚拟末端控制器在虚拟环境中的位置，初始位置二者没有接触，也不会产生作用力。当虚拟末端控制器位于包围盒外部时，则二者不可能发生碰撞，无需检测。当虚拟末端控制器位于包围盒内部以后，系统实时计算其与虚拟心脏边缘的距离，当距离为0时，碰撞发生。随着虚拟末端控制器继续向内部移动，由于对虚拟对象材质设定的不同分两种情况：1、 对象边界可以穿透，则虚拟末端控制器进入虚拟心脏，开始实时计算虚拟代理的位移x，反作用力通过公式（2.1）可以得到。2、 对象边界不可穿透，则虚拟操纵对象接触虚拟心脏后后者开始形变，这里代入胡克定律可知变形越大，则作用力越大。图 2.4力反馈算法流程图2.4 变形算法软组织形变的物理模型是计算机图形学中非常重要的，但又是很富有挑战性的一个课题。目前多数虚拟手术仿真的课题研究的研究对象是刚性组织如骨骼，而针对内脏这类可变形组织的研究较少。软组织的物理建模不仅要使用物体的几何模型，还要利用其生物力学特性建立它的动力学模型，给几何模型赋予在适当场景下的物理行为，达到视觉和触觉上逼真的用户体验。与力反馈算法类似，软组织的物理建模一般也分为有限元方法和弹簧-质点方法两种。两种方法都是希望将无限的问题简化为有限的问题，求解微积分方程，得到问题的近似解。离散化程度的高低，一方面影响仿真的真实程度，一方面影响计算量的大小。而计算量的大小又会对实时性产生极大的影响。弹簧质点模型以简单易行，计算量小等优点，被广泛的应用于软组织变形的实时仿真中。其核心思想是把要仿真的对象用质点离散化，质点之间用复合线性弹性模型（“胡克定律”）（也可以是非线性的，在很多情形下，可以近似看作线性）的弹簧连接而成，质点除了受到弹簧的弹力作用外，同时还受到与速度成正比的阻尼力的约束。当一个质点在外力的作用下运动时，其产生的作用力会作用在其周围的其他质点，带动其他质点的运动，这样可以看到，物体的变形是由质点的运动和传递而产生的。由牛顿力学定律，每个质点i的动力学方程为：miai=Fi（2.1）其中Fi=jngij-divi+fexti（2.2）mi是质点的质量，ai，vi分别是质点的速度和加速度，di是粘性系数， fexti是外力，gij是质点i和质点j之间的弹簧对质点i的应力，且gij=xj-xixj-xi(kijxj-xi-Rij)（2.3）其中xj，xi是弹簧两端点的位置，kij是弹簧的弹性系数，Rij是弹簧的静止长度。3 平台搭建3.1 硬件平台3.1.1 硬件选择由于心脏模型的精密度比较高，包含较多细节，并且手术环境对实时性的要求较高，因此需要性能强劲的硬件设备才能很好的支持图形的处理和保证实时的运算。综合考虑了性能和成本等因素后决定工作站的硬件配置如下：表 3.1 图形工作站硬件配置配件CPUGPU内存硬盘力反馈设备名称/型号英特尔E3 1230v3英伟达Quadro K5000威刚4GB*2威刚S900 128GB SSDForce Dimension Omega.73.1.2 安装软件环境根据红京鸟力维（北京）科技有限公司工作人员的建议，同时考虑了我本人的使用习惯，采用Linux平台作为开发和测试环境。但由于此平台在实验室其他人员中的普及度不高，故同时使用了Windows平台。在进行本课题时，微软已经发布了Windows 8，但Chai3D 2.0的时代对Windows 8的支持度无法得知，故采用了相对老旧但兼容性更好的Windows 7 64位。1、 Linux平台Linux是自由软件，它是一个开放源代码的类UNIX操作系统，在遵循GNU通用许可证的条件下任何人都可以自由的使用Linux所有的底层源代码，也可以自由的修改和再发布。Linux实际上是一个执行内存管理、任务调度的内核，通常使用者使用的Linux全称GNU/Linux，即包含Linux内核和由GNU项目开发的一套软件系统。Arch Linux是Linux的一个发行版，它是一个相对非常自由的发行版，使用者可以根据需要定制系统的组件，并且由于该操作系统针对64位处理器做了优化，因此性能较通常的其他发行版如Ubuntu等会有一定程度的提升。按照Arch Linux官方Wiki安装了操作系统之后，根据力反馈设备的安装说明书，需要安装以下组件：（1） Quadro专业显卡桌面驱动程序331.79（Linux 64位），提供了对最新OpenGL标准4.4的支持。（2） libusb-1.0，它是一个开源的C程序库，它使应用在不同的操作系统上可以很容易的访问USB设备。Libusb设计了一系列外部API为应用程序调用，通过这些API应用程序可以操作硬件，从libusb的源代码可以看出这些API调用了内核的底层接口，和内核驱动中所用到的函数所实现的功能相似，但libusb更加接近USB规范，使得libusb的使用也比开发内核驱动相对容易得多。（3） freeglut 2.8，GLUT最初是OpenGL编程指南（第二版）中的示例程序，自那以后，GLUT简单、跨平台的特点使其在各种应用中得到广泛使用。但GLUT并不是开源软件，无法自由使用，且该项目目前已经停止开发，同时由于其许可证的原因，禁止任何人发布对其修改后的版本。Freeglut是于1999年12月由开源社区发起的项目，目的是重新实现GLUT，并以一种更自由的许可条款发布出来供自由使用。目前freeglut具有GLUT的几乎所有功能，并且有一些更灵活的扩展。（4） Qt 5.2开发套件。Qt当前的最新正式版本是5.2，包括SDK和集成开发环境Qt Creator。英伟达驱动程序从官方网站获取，下载完成后添加可执行权限，执行安装即可。其他软件可以通过pacman S libusb freeglut qtcreator来获取。2、 Windows平台Windows平台下安装Quad