基于OSG的虚拟现实碰撞检测及GPU并行加速

河北大学硕士学位论文基于OSG的虚拟现实碰撞检测及GPU并行加速姓名：刘京申请学位级别：硕士专业：检测技术与自动化装置指导教师：王洪瑞2011-05摘要I摘要碰撞问题是机器人、动画仿真、虚拟现实、计算几何、CAD/CAM等领域的关键问题之一，而实时性和精确性是衡量一个碰撞检测算法是否优越的重要标准。尽管国内外已经对碰撞检测问题做了许多有意义的工作，但是随着计算机软硬件及网络等技术的日益成熟，尤其是GPU并行计算技术的快速发展，不同规模程度场景下实时而又精确的碰撞检测问题逐步成为当前研究的热点。针对大规模复杂场景的碰撞检测问题，本文首先从场景渲染入手，在详细了解OSG渲染引擎的场景组织方式、渲染流程之后，利用新一代的三维图形渲染系统的功能特性，搭建一个高效的基于场景图的河北大学新校区校园漫游系统。进而在场景交互方面，通过深入研究基于图像的碰撞检测算法，提出了实时性更好的基于向指定平面投影、模板测试和深度测试的改进型图像空间碰撞检测算法，实现了虚拟校园漫游系统中对漫游角色模型与场景模型之间的快速碰撞检测。同时引入GPU并行计算，调高了碰撞检测的效率。对于更加注重于碰撞检测精度的虚拟手术仿真系统来说，本文在基于距离的碰撞检测算法基础之上，通过扫描线确定模型间潜在碰撞区域内的刨分顶点、自适应面刨分、构造刨分三角形、判断刨分点到刨分三角形之间的距离实现了骨锯模型和头盖骨模型间的精确碰撞检测。该算法不仅能获得碰撞发生位置，还把碰撞区域局限在几个刨分顶点构成的多个刨分三角形之内，同时还继续引入GPU并行计算技术，优化了整个碰撞检测算法，缩短了计算周期。关键词：虚拟现实碰撞检测OSGGPU并行计算AbstractⅡAbstractAlthoughmanyresearchershaddonemuchmeaningfulworkaboutcollisiondetection,butalongwiththecomputersoftwareandhardwareandnetworktechnologyfastdeveloping,especiallytheGPUparallelcomputingtechnology,real-timeandaccuratecollisiondetectionproblemwiththedifferentscalesceneshasbecameahotissues.Forcollisiondetectionproblemsoflargescaleandcomplicatedscenes,wefirstlyorganizedavirtualcampusroamingsceneofHebeiuniversityusingthefunctioncharacteristicsofnew3dgraphicsrenderingsystemafterindetailedunderstandingtheorganizedwayandrenderingprocessofOSGrenderingengine.Thenthroughdeeplystudyingofthecollisiondetectionalgorithmbasedonimage,designingaimprovedbasedonimagecollisiondetectionwiththedesignatedplanarprojection,stenciltestanddepthtest,realizingthecollisiondetectionbetweenroamingrolemodelandscenemodelsofthevirtualcampusroamingsystem.MeanwhileintroducingtheGPUparallelcomputing,improvingtheefficiencyofcollisiondetection.Forthevirtualsurgerysimulationwhichmorefocusedoncollisiondetectionaccuracy.Inthispaper,afterresearchedthecollisionalgorithmbasedondistance,wecompetedthroughthescanninglinetocomputesegmentationvertexes,adaptivesurfacedividing,constructingdividingtriangles,computingthedistancebetweensegmentationvertexesanddividingtrianglestojudgewhetherskullmodelandbonesawhadcollided.Thisalgorithmcannotonlygetthecollidingposition,butalsocanconfinethecollisionregionalinsomedividingtriangles.AlsowecontinuetointroduceGPUparallelcomputingtechnology,optimizethecollisiondetectionalgorithm,andshortenthecomputationcycle.Keywords：VirtualRealityCollisionDetectionOSGGPUparallelcomputing第1章绪论1第1章绪论1.1课题的研究意义1.1.1课题的研究意义自20世纪90年代以来，虚拟现实技术(VirtualReality，简称VR)作为一种新兴的强大人机交互技术，一直是信息领域研究开发和应用的热点方向之一。由于它具有强大的三维表现能力和人机交互能力，不仅可以实时的模拟各种真实场景，还可以在通过人机交互设备的辅助下，与虚拟场景中的模型对象进行交互操作，具有高度的沉浸感、真实感，使人产生一种身临其境的感觉。近年来，随着科学技术水平的不断发展，虚拟现实技术已经广泛应用于军事、生物医学、机械、教育、建筑和文化等多个领域，并发挥着越来越重要的作用。我国对虚拟现实技术的正式研究起步却很晚，对于沉浸式多交互虚拟环境系统研究较少，在虚拟现实系统的研究中交互技术还不够成熟。本课题将综合运用多项技术，拟在分布式虚拟现实领域有所突破和发展，此项研究也充分体现了国家中长期科技发展规划纲要中“五、前沿技术”的“2．信息技术”中“（8）虚拟现实技术”的科技发展方向，具有重要的意义。一个大规模的虚拟场景可能包含成千上万个模型，而随着场景复杂度不断提高每个模型又需要由成千上万个三角面组成，如何有效的对这些物体进行组织和管理以满足实时绘制的要求，是一个非常重要的问题。另外，为了更加真实的反应虚拟环境的效果，需要增加光照、阴影、特效等功能，并且在虚拟交互过程中，为了达到实时的交互效果同时保证模型渲染的逼真度，细节层次等技术必须应用其中，实时图形处理对于系统资源的消耗量非常大，因而如何借助计算机和图形技术的发展，完成图形性能优化就显得尤为重要。为了方便虚拟场景的开发同时对图形性能进行优化，近年来基于场景图理论的场景渲染成为了复杂场景的虚拟现实系统渲染的研究热点。场景图是一种简单有效的组织图形图像的数据结构，是特殊的有向非循环图，它保存了场景中模型信息及其相互关系[1]。场景图是一个K叉树状结构，根节点代表整个虚拟场景，树中的每个节点可以有任意多个子节点，每个节点存储场景集成的数据结构。它通常包含三类基本节点：组节点、几何体节点和变换节点。其中组节点是对所有节点实现分组管理；几何体节点是对物体的基本性质进行描述；变换节点主要用于三维几何河北大学工学硕士学位论文2变换，包括平移、旋转等。虽然，场景图技术在工业界得到了广泛的应用，但至今尚未统一。每一种较成功的场景图都有其适用的范围和局限性，很难找到适于各种应用的场景图系统。与传统的信息系统相比，虚拟现实是一个新型的、多维化的、人机和谐的信息系统。在这种系统内，交互的实时性控制带来的真实感是人们所能感受到的昀突出的特点之一，也是提高在虚拟环境中“身临其境”的沉浸感以及实现人机和谐的关键。因此，高效而快速的进行物体间的碰撞检测，在提高虚拟环境的真实性、增强虚拟环境的沉浸感以及加强实时交互操作等方面都起着至关重要的作用。随着虚拟现实应用领域的日益扩大及应用内容的复杂化，对碰撞检测算法提出了更高的要求。严格的实时性和真实性要求在向研究者们提出巨大挑战的同时，也使大型复杂场景下的快速碰撞检测成为该领域的研究热点。国内外许多专家和学者已经针对碰撞检测问题开展了很多有重要价值的研究工作，其研究可分为基于物体空间的碰撞检测和基于图像空间的碰撞检测。基于物体空间的碰撞检测已有了较为充分的研究并建立了相应的算法，但这些算法的效率主要的取决于物体模型的构造方式和场景的复杂程度。近年来，随着图形处理器（GPU）的快速发展，基于图像空间的碰撞检测逐步成为研究的热点。GPU的高性能并行计算和可编程功能，为图形处理以外的数字图像处理和通用并行计算提供了良好的运行平台，也为基于图像空间的碰撞检测方法提供了广阔的发展空间。本课题的研究将利用新一代的三维图形渲染系统的功能特性，搭建一个高效的基于场景图的复杂虚拟现实渲染系统，完成场景显示的真实性和实时性。进而在场景交互方面，摆脱图形硬件信息存储的限制，提高碰撞检测的速度和精度，从而适用于大规模复杂场景的快速实时碰撞检测。本课题是把虚拟现实技术应用于实际的一个有益尝试，具有很高的学术价值。同时，本课题的研究成果可以直接应用于模拟驾驶训练、运动训练、虚拟旅游、虚拟城市建设等众多领域，应用前景十分广阔。1.1.2课题来源本课题得到了科技部国际科技合作项目《载人六自由度并联机器人及虚拟环境的交互控制研究》（2008DFR10530）的资助和支持。本课题还得到了河北省科技厅科技支撑项目《分布式虚拟场景的实时绘制与一致性第1章绪论3控制研究》(08243531D)的资助和支持。1.2国内外的研究现状1.2.1场景渲染随着网络技术、图形技术和硬件设备的迅速发展，虚拟场景的渲染技术也不断进步，在OpenGL的基础上出现了多种类型的渲染引擎和渲染平台。OpenGL是一个开放的三维图形软件包，它独立于窗口系统和操作系统，昀底层的图形开发API，可以被认为是图形硬件的一种软件接口，其设计目的主要是为了作为一种流水线型、独立于硬件的接口，以它为基础开发的应用程序可以应用在不同的硬件平台之上。但是在处理复杂问题的时候非常繁琐，它对于每个几何体都必须逐点详细说明所有的数据，同时不具备面向对象的特征，不便于大场景的开发和管理。近年来，随着计算机图形学的不断发展，基于场景图的渲染技术越来越得到研究人员的重视。目前常用的基于场景图的渲染引擎主要包括:OSG、Java3D、Virtools、OGRE、VRML等，它们被广泛的应用于各个领域中。如刘小兵、卜淮原、郑恩昌利用VRML、3DMAX、CAD等几种不同的可视化三维建模软件相结合实现了某军事基地网上虚拟场景系统[2]；北京工商大学的魏薇和陈谊利用MultiGen建模工具和VRML实现了以北京工商大学良乡校区为例的虚拟校园漫游系统[3]；刘晓明、李勤、王晓哲等人利用Virtools三维开发工具,设计实现了某采油厂厂区虚拟漫游系统，该系统虚拟场景逼真，漫游功能齐全，而且以Web形式发布，用户可以在浏览器上进行多视点、多场景的浏览，让用户有身临其境的感觉，宣传效果极佳[4]；王乐、陈定方、李勋祥等人利用VIRTOOLS开发了分布式虚拟驾驶环境。基于VirTool的分布式虚拟现实技术在教育、娱乐、科研等方面都会有很好的应用前景[5]；上海交通大学的刘晓波、张琴舜、张和林等人以大亚湾核电站为原型，使用建模工具MutiGen和开发工具Vega，开发虚拟核电站实时漫游系统[6]；于海凤、邢桂芬、张凯基于MutiGen和Vega开发了三维战场视景[7]；张翔和罗炳伟