（计算机科学与技术专业论文）虚拟现实中碰撞检测技术的研究.pdf

摘要 实时碰撞检测是虚拟现实中一个非常关键的问题，其基本任务是 确定两个或多个物体彼此之间是否发生接触、接触面积大小和穿透的 深度。尽管针对碰撞检测已有了大量有价值的研究成果，但随着人们 对交互实时性、场景真实性要求的不断提高，碰撞检测技术所面临的 问题也日益突出，其中最核心的问题是如何有效地提高碰撞检测的速 度。本文对碰撞检测相关技术进行了深入的研究，主要包括以下几个 方面的内容： 首先，从图形硬件发展的历史开始，介绍和分析最新g p u 在通 用计算方面的应用及其技术原理和发展状况。 然后，对目前现有的碰撞检测算法进行了分类归纳，同时总结了 一般碰撞检测算法所采用的总体框架，并着重介绍与分析了基于层次 包围体树和基于图像空间的碰撞检测算法。 在此基础上，本文提出了一种基于g p u 的对参数化表面的碰撞 检测方法。通过使用几何图像表示的参数化表面，可以实时的生成 g p u 优化的包围体层次结构，然后在这个层次结构的基础上实现优 化的基于g p u 的层次碰撞检测算法。结果显示本方法可以有效的提 高碰撞检测的速度。 关键字碰撞检测，可编程图形处理器，几何图像，层次包围盒， m l p m a p a bs t r a c t r e a lt i m ec o l l i s i o nd e t e c t i o ni so n eo ft h em o s ti m p o r t a n tp r o b l e m s i nt h ef i e l d so fv i r t u a lr e a l i t y i t sf u n d a m e n t a lt a s ki st od e t e c tw h e t h e r t h e r ea r ec o n t a c t so rp e n e t r a t i o n sb e t w e e nt w oo ra m o n gm u l t i p l eo b je c t s 、i l e t h e r eh a v eb e e nm a n yr e s e a r c ha c h i e v e m e n t so ns o l v i n gt h e p r o b l e mo fc o l l i s i o nd e t e c t i o n 。t h i sp r o b l e mi sb e t t e rt ob es o l v e dw i t ht h e m o r eh i g hd e m a n d so fr e a lt i m ei n t e r a c t i v i t ya n dr e a l i s t i cs i m u l a t i o no f m o t i o n so fv i r t u a lo b j e c t st h e r e a t t e r t h i sp a p e rs t u d i e st h et e c h n i q u eo f c o l l i s i o nd e t e c t i o nd e e p l y i tc o n t a i n st h ef o l l o w i n gp a r t s ： f i r s t l y , s t a r t i n gf r o mab r i e fi n t r o d u c t i o nt os o m eh i s t o r i c a le v e n t so n g r a p h i c sh a r d w a r ed e v e l o p m e n t ，ad e t a i li n t r o d u c t i o na n da n a l y s i sw i l lb e g i v e nt ot h et e c h n i q u ea n dt h el a t e s td e v e l o p m e n to fg p uf o rg e n e r a l p u r p o s ec o m p u t a t i o n s s e c o n d l y t h i st h e s i sr e v i e w sr e c e n tr e s e a r c h e so nc o l l i s i o nd e t e c t i o n a n ds u m m a r i z e st h eg e n e r a lf r a m e w o r ko fac o l l i s i o nd e t e c t i o na l g o r i t h m t h e ni tf o c u s e so ni n t r o d u c i n ga n da n a l y z in gt h ec o l l i s i o nd e t e c t i o n a l g o r i t h m sb a s e do nb o u n d i n gv o l u m eh i e r a r c h ya n di m a g es p a c e f i n a l l y , b a s eo nt h ea b o v ec o n t e n t s ，t h et h e s i sd e s c r i b eag p u b a s e d c o l l i s i o nd e t e c t i o nm e t h o df o rp a r a m e t e r i z e ds u r f a c e sb yg e o m e t r y i m a g e sa l l o w st og e n e r a t eg p u o p t i m i z e db o u n d i n gv o l u m eh i e r a r c h i e s i nr e a l t i m et h a ts e r v ea sab a s i sf o ra no p t i m i z e dg p u b a s e dh i e r a r c h i c a l c o l l i s i o nd e t e c t i o na l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a to u r m e t h o di sf a s t e rt h a nt h ec p u b a s e dm e t h o d k e yw o r d sc o l l i s i o nd e t e c t i o n ，g p u ，g e o m e t r yi m a g e ，h i e r a r c h i c a l b o u n d i n gv o l u m e ，m i p m a p 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名_ 丛互 日期：逊仁年互月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者躲监导师签名毒磐嗍详年上月篮日 硕十学位论文 第一章绪论 1 1 研究背景及意义 第一章绪论 虚拟现实( v i r t u a lr e a l i t y , v r ) 是一项涉及计算机图形学、人工智能等学科 的综合技术。虚拟化是网络世界的自然发展，也是在面临同益严峻的国际性挑战 时，保持经济强大且具竞争力的重要工具。虚拟化可以帮助企业获得竞争优势， 使民众能通过教育和培训而不断提高，并使政府得以为民众提供更出色的服务。 我国九五规划、国家自然科学基金委、国家高技术研究发展计划等都把v r 列入 了研究项目。十一五规划将v r 写入国家中长期科学和技术发展纲要，定为三大 前沿技术之一。 随着计算机软硬件及网络等技术的日益成熟，尤其是计算机动画仿真、虚拟 现实等技术的快速发展，人们迫切希望能对现实世界进行真实模拟，而这其中亟 需解决的关键技术之一即是实时碰撞检测。目前，三维几何模型越来越复杂，虚 拟环境场景规模越来越大，同时人们对交互的实时性，场景的真实性的要求也越 来越高。严苛的实时性和真实性要求在向研究者们提出巨大的挑战的同时，也令 实时碰撞检测再度成为研究热点。 本课题研究的目的正是在于利用当前发展迅速的可编程g p u 的强大处理能 力来进行碰撞检测的计算，以提高复杂场景中的物体之间的碰撞检测速度。 1 2 碰撞检测的应用领域和问题类型 1 2 1 碰撞检测的应用领域 如果说物体或者模型是三维空问的一个子集，而且可以用多边形、简单的立 体形状、曲面的集合来加以描述，碰撞检测就是判断给定物体是否相交。 碰撞检测的应用领域非常广泛，包括计算机动画、物理模拟、游戏机器人技 术、虚拟原型设计、以及几乎所有的虚拟现实模拟。 在计算机三维游戏中，碰撞检测保证了虚拟世界的真实感，使游戏中的人物 不会穿墙而过或陷入地面下边；给出瞄准线，是游戏中的人物在发现敌人时可以 发起攻击。 碰撞检测在计算机动画领域的应用例如对布料进行物理模拟，确保衣物的行 为更加真实，使之能够随人物一起移动。碰撞检测还用于机器人技术中的路径规 硕学位论文 第一章绪论 划，来帮助控制机器人避开障碍物。在虚拟原型设计中，碰撞检测用于帮助计算 i b j 隙，在不制造真实模型的情况下对原型进行优化。碰撞检测还可以用于破损试 验以及其他的工业模拟。图1 - 1 为虚拟装配模拟。 圈卜1 虚拟装配模扭( 绿色为碰撞部分 122 碰撞检测的问题类型 碰撞问韪包括碰撞检测和碰撞响应两部分。碰撞检测的日标是发现碰撞并报 告；碰撞响应是在碰撞发生后根据碰撞点和其它参数促使发生碰撞的对象做出 正确的动作，以反应真实的动态效果。碰撞响应涉及到力学反馈、运动物理学等 领域的知识。我们研究的主要是碰撞检测问题 最简单的碰撞榆测是相交测试，确定两个给定位置和方向的物体是否重叠。 这种回答是或否的柿尔类型的帽交问题是比较容易完成的。然而，有些情况f ， 只返回布尔结果还不够，还需要找到相交的位置。 有些应用只需要找到物体之间的一个公共点。还有一些应用如刚体模拟， 则需要确定接触点集( 切触流形) 。准确的确定切触流形是很困难的。 如果两个物体相互穿透，有衅应j j 需要确定穿透深度。通常根据最小平移距 离，即分离像个物体需要的移动向量的长度，米确定穿透深度。通常，这个移动 向黾的计算是个比较复杂的问题。两个物体的分离距离为两个物体卜最近的两点 之州的距离，如果分离距离为0 ，则两物体十r 交。分离距离对下一时段的碰撞预 判很有用处。更一般的问题是找到两个物体之间的最邻近点，即确定分离距离的 点。虽邻近点可能不是唯一的。对于动态物体，计算f 一次碰撞时问称为预计到 达时间( e t a ) ，e a t 常用于刚体模拟中确定时州步长。 硕- 上学位论文 第一章绪论 1 3 国内外研究现状 近二十多年来，研究人员在碰撞检测领域中做了相当多有意义的工作，对虚 拟现实的发展起到了推动作用。碰撞检测算法种类繁多，各有侧重。纵观这些算 法，大致可分为基于图形和基于图像的碰撞检测算法。 在基于图形的碰撞检测上，研究人员已经做了大量的工作，形成了空间分解 法和层次包围体法等成熟算法。空间分解法主要是先将整个虚拟空间划分成等体 积的规则单元格，以此将场景中的物体分割成更小的组群，并只对占据了同一单 元格或相邻单元格的几何对象进行相交测试。一般来说，空间分解法在每次碰撞 检测时都需要确定每个物体占有的空间单元。如果场景中不可动的模型很多，可 以预先划分好空问单元格并确定每个模型占有的空间单元。当有模型运动时，只 需要重新计算运动模型所占有的空间就可以了。空间分解法比较典型的例子有 k d 树、八叉树、b s p 树、四面体网和规则网格等。采用层次划分方法进行空间 分解可以进一步提高算法的速度。 层次包围体法的核心思想是用体积略大而几何特性简单的包围体来近似的 描述复杂的几何对象，从而只需对包围体重叠的对象进行进一步的相交测试。此 外通过构造树状层次结构可以越来越逼近对象的几何模型，直到几乎完全获得对 象的几何特征。基于包围体的碰撞检测方法的不同点在于树节点的包围体类型不 同或者采用不同的技术来建立、更新和平衡包围体树。典型的包围体有轴对齐包 围盒( a a b b ) 、包围球、有向包围盒( o b b ) 和离散有向多面体( k d o p ) 。 近些年，随着图形硬件计算性能的迅速增长，基于图像的碰撞检测算法进入 了一个新的快速发展的阶段。该方法一般将三维几何对象通过投影绘制到图像平 面上，降维得到一个二维的图像空间；然后分析该空间中保存在各类缓存的信息， 进而检测出对象之间是否发生相交。这类算法的优势在于能有效利用图形硬件加 速技术来减轻c p u 的计算负荷，从而达到提高算法效率的目的。 近年来的研究热点主要集中于变形体对象的碰撞检测。变形体对象会在运动 中发生形变，其包围体树必须实时的重新构建或者更新，而重新构建整个数据结 构的时间耗费在一个实时的仿真环境中是不能接受的，因此在层次包围体方法中 必须避免整棵树的重新构建。研究这根据不同包围体的特性进行改进，将层次包 围体方法也用于变形体对象的碰撞检测。 s m i t h0 1 a l 1 】提出了一种基于a a b b 包围盒的解决变形体对象的方法，该方 法每一步都重新计算对象的包围盒，其缺点是当模型复杂时不能得到实时计算。 v a nd e nb e r g e n 2 】提出一种基于s o l i d 库的方法，并在每个时候由叶节点开 始完成自底向上的更新，缺点是发生大尺度变形时，a a b b 包围盒的紧密性就比 3 硕士学位论文 第一章绪论 较差，并且包围盒与包围盒之间有非常大的重叠区域。 y a s h i f u m ik i t a m u r a 3 l 等人提出了一种用于解决复杂场景下的变形体的碰撞 检测方法，这种算法的本质是包围盒方法与空间分解法的结合。此方法的缺点是 采用八叉树的数据结构复杂。 j m e z g e r 【4 】等人在布料仿真时对层次包围盒结构作了很多优化。它采用的 包围盒类型是k d o p ，由于k d o p 在最坏情况下只需k 2 次相交测试，因此， j m e z g e r 等人采用的是四叉树。这样做的优点是减少相交测试时递归调用的深 度，从某种意义上减少了内存消耗。另外它还采用了“向量圆锥 来解决自相交 问题。 m a t t h i a st e s c h n e r t 5 】等人提出了用一种优化的哈希表来解决变形体以及自相 交问题。 国防科技大学魏迎梅等人【6 】提出了一种基于固定方向凸包f d h 包围盒层次 的碰撞检测方法，用于虚拟手术仿真，为解决复杂环境中的碰撞检测问题提供了 一条有效途径。 浙江大学范昭炜等人【7 】对实时碰撞检测技术进行了研究，利用图形硬件的高 计算性能、可编程性及多处理机的并行计算能力来加速碰撞检测过程。 1 4 主要工作 尽管有关碰撞检测的研究成果已经比较丰富，但随着计算机图形学的不断发 展，以及包括虚拟现实在内的新兴领域的涌现，实际应用对碰撞检测技术的要求 越来越高。目前碰撞检测领域仍然存在着一些问题，如处理大规模复杂场景的能 力和处理非凸体的能力等。针对碰撞检测技术目前存在的问题，本文围绕如何利 用可编程g p u 的通用计算能力来完成碰撞检测的计算，从而有效地提高碰撞检 测算法的效率展开了研究，并以解决上述问题作为主要研究目标。主要的贡献包 括以下三个方面。 通过使用几何图像将表达物体的网格的几何信息转化为可在g p u 上渲 染的图元，利用g p u 完成碰撞检测的计算。 提出了一种适合g p u 计算的包围体层次表示。对于刚体模型间的碰撞 检测，基于层次结构的方法被证明是最有效和准确的。我们使用定制的 m i p m a p 生成方法来创建包围体的四叉层次结构。这种结构对广度优先 遍历有着很好的并行性。 提出了一种基于改进的非均匀流压缩技术的层次遍历方法。流压缩即去 除g p u 上流计算中的无效数据。通过对现有方法进行改进，使之更适 合用于我们的四叉树层次结构。 4 硕士学位论文第一章绪论 1 5 论文结构 本文共分五章。 第一章为绪论，介绍了课题的研究背景和主要的研究工作。 第二章介绍了g p u 通用计算的发展现状和碰撞检测算法的基本框架。随后 对常用的碰撞检测算法进行了分析和比较。 第三章讨论了基于g p u 的碰撞检测算法。通过几何图像来表示物体网格和 包围盒层次结构，在g p u 上完成碰撞检测的计算。 第四章对算法的性能进行了分析和评价。 第五章为总结，在对所做工作进行总结的基础上，阐述了进一步的工作目标。 硕士学位论文 第二章g p u 通用计算与碰撞榆测 第二章g p u 通用计算与碰撞检测 2 1g p u 通用计算 2 1 1g p u 概述 综观计算机图形学的发展进程，图形学的每次重大进展都与图形处理硬件的 突破密切相关【8 】。最突出的例子莫过于八十年代初期g e o m e t r ye n g i n e t 9 】芯片的 推出对于二十年来图形发展和变革所产生的巨大影响。g e o m e t r ye n g i n e ( g e ) 从设 计上可以由一个寄存器的定制码定制出不同的功能分别用于图形流水线中的 几何变换，裁剪计算，投影缩放等。而在初期设计的i r i s ( i n t e g r a t e dr a s t e r i m a g i n gs y s t e m ) 系列中，1 2 个g e 单元即可组成完整的三维图形流水线。以g e 作为核心技术，其设计者j a m e sc l a r k 作为c e o 所成立的s g i 公司的产品在其 后的图形发展和工业应用中产生了巨大影响。举例来说，从s g i 的g l 直至今 天作为事实上图形界面工业标准的o p e n g l ，一个为人熟知的、最突出的特点就 是将其造型变换( m o d e l i n gt r a n s f o r m a t i o n ) 与观察变换( v i e w i n gt r a n s f o r m a t i o n ) 结 合为一体，用m o d e l v i e w 矩阵栈直接完成其统一的变换过程以及复杂物体的层 次造型。 图形处理的并行性以及可编程功能一直是图形硬件发展所追求的目标。这其 中的佼佼者莫过于北卡罗莱那大学在上世纪8 0 年代所设计的p i x e lp l a n e s 系列图 形系统【1 0 , 1 1 , 1 2 】。其中于8 0 年代后期所设计的p i x e lp l a n e5 ，作为当时图形处理能 力最强的处理系统，曾经达到每秒绘制一百万个p h o n g 模型多边形的能力，这在 今天看起来亦是一个值得惊叹的数字。p i x e lp l a n e s 的高度并行性是由象素级的 驱动单元实现的。其硬件系统可以包括多达3 2 个数学处理器和1 6 个绘制部件， 而每个绘制部件可以对一个1 2 8 1 2 8 象素阵列的每个象素实行二次多项式的并 行计算。并行性采用的是s i m d 结构。从某种程度上说，它是一个专用于图形图 象处理的s i m d ( s i n g l ei n s t r u c t i o n ，m u l t i p l ed a t a ) 结构的并行处理机。为此p i x e l p l a n e s 虽然具有超级的处理速度，却不能不受s i m d 结构的并行处理方式所制 约，其高效性只适用于那些能够有效地分解其算法到s i m d 结构上运行的图形应 用。 伴随着p c 级微机的崛起和普及，多年来计算机图形的大部分应用发生了从 工作站向微机的大转移，而这种转移甚至发生在象虚拟现实、计算机仿真这样的 实时( 中、小规模) 应用中。实时应用的计算机游戏的普及亦是这一发展的标志。 6 硕士学位论文第二章g p u 通用计算与碰撞检测 这一切的发生从很大程度上源自于图形硬件的发展和革新。随着计算技术和集成 电路技术的发展，图形硬件的更新速度迅猛。g p u ( g r a p h i c sp r o c e s s i n gu n i o 自 1 9 9 9 年首先由n v i d i a 公司提出来后，就其发展的速度而言，是c p u 更迭速度 的三倍多。目前图形芯片的主要市场被n v i d i a 和a t i 这两家公司占领，从高 端到低端都有相应的产品来满足市场。 新的图形硬件带来一些新的特征，这些特征概括起来有如下几方面： 1 1 在顶点级和像素级提供了灵活的可编程特性： 2 ) 在顶点级和像素级运算上都支持i e e e 3 2 位浮点运算； 3 ) 支持多遍绘制的操作，这样避免了多次的c p u 与g p u 之间的数据交换； 4 ) 支持绘制到纹理的功能( r e n d e r - t o t e x t u r e p b u f f e r ) ，从而避免将计算结果 拷贝到纹理这一比较费时的过程： 5 ) 支持依赖纹理功能，以方便数据的索引访问，可以将纹理作为内存来使 用。 g p u 是完全专用于图形输出流水线的处理和加速。因此当g p u 的功能越来 越强时，与图形有关的处理便自然而然地从c p u 向g p u 转移。最先发生的转 移是最靠近应用程序的几何变换部分，其中包括造型变换和观察变换，其次是局 部或特殊光照效果的计算和生成。当顶点级和象素级的可编程功能越来越灵活 时，图形本身的处理速度和灵活性都得到了前所未有的提高。而当g p u 内部像 素级的纹理元达到可以参与编程的运算时，它从某种程度上模拟了类似于p i x e l p l a n e s 处理单元的部分功能，以至于向着可作通用计算的方向发展。这时，基于 g p u 的通用计算便应运而生了。 基于g p u 的通用计算( g p g p u g e n e r a lp u r p o s eg p u ) 指的是利用图形卡来 实现一般意义上的计算，而不单纯是绘制。本文关注的就是如何利用g p u 来实 现矢量、矩阵的基本代数运算，然后在这个基础上如何实现一些相对复杂的运算， 如线性方程组的求解，从而实现复杂应用问题的求解。 相对于以前采用固定渲染管道的图形硬件，上述提到的这些新特征无疑加快 了g p u 在通用计算方面的应用。文献 1 3 简短地阐述了g p u 的发展历史。2 0 0 3 年被认为是图形硬件被用来做通用计算的一个旱程碑【l4 1 ，文献 1 5 】也认为g p u 在2 0 0 3 年已经进入计算的主流。而采用图形硬件来做通用计算的主要目的是为 了加速，加速的动力来自这些新硬件所具有的以下主要优势： 1 ) 一定的并行性。这一功能主要是通过多个渲染管道和r g b a 四个颜色 通道同时计算来体现的，另外在一个时钟周期内可以同时获取2 个甚至更多副纹 理。顶点程序的多个渲染管道意味着一个时钟周期可以并行处理多个顶点，而对 于像素程序同样如此。相对于并行机而言，图形卡提供的并行性虽然很弱，但它 7 硕士学位论文第二章g p u 通用计算与碰撞检测 在十分廉价的基础上为很多应用提供了一个很好的并行方案，尤其是对于图形本 身的应用来说。 2 ) 高密集的运算。由于图形卡内部的内存接口位宽大于c p u 上的位宽， 如g e f o r e ef x 的内存位宽达2 5 6 位，显然高于c p u 上3 2 位的位宽，这样整个 计算的带宽大大提高。g p u 相对于c p u 来说，更适应传输大块的数据，虽然 c p u 上有c a c h e 以加速整个计算过程，但c p u 上的c a c h e 相对于图形卡显存来 说太小，一般只有6 4 k b ，而现在的显存大多都在6 4 m 以上，由此可见一斑。 3 ) 减少了g p u 与c p u 的数据通信。尤其是当整个应用针对图形生成的时 候，不再需要在c p u 与g p u 之间进行多次数据交换，从而可以让c p u 解放出 来做其他的事情。 这些优势使得g p u 比c p u 更适用于流处理计算，因此g p u 也被认为是一 个s i m d 的并行机或者流处理器【1 6 】，可以用于处理大规模数据集，使得应用得 到加速。而相比之下，c p u 本质上是一个标量计算模型，而计算单元偏少，主 要针对复杂控制和低延迟而非高带宽进行了若干优化。图2 1 给出了当前g p u 的渲染管道示意图。 图2 - 1g p u 渲染管道示意图 2 1 2 高级着色语言 目前世界上存在两大著名的图形a p i ( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ) 标准：o p e n g l 和d i r e c t x 。这两套a p i 在早期都是用纯软件的方式实现的。也 就是说，早期的程序员在使用这两套a p i 时，根本体会不到图形加速硬件的存 在。但是，随着可编程g p u 的出现，这种情况迅速地被改变。专门针对g p u 而 设计的高级着色语言( h l s l ，h i g h l e v e ls h a d i n gl a n g u a g e s ) 不断涌现。最具 代表性的商品化高级着色语言有如下四种： 8 硕士学位论文第二章g p u 通用计算与碰撞柃测 1 c g ( cf o rg - r a p h i c s ) ：作为首个推出可编程图形硬件的厂商，n v i d i a 公 司从一开始就致力于实现一个完善的高级着色语言以封装图形硬件的可 编程性。因此c g 语言的目标就是一个标准的高级着色语言，现在说它已 经达到了这个目标有些为时过早，但是c g 语言的发展将深刻地影响这高 级着色语言的标准的发展。 2 h l s l ( h i g hl e v e ls h a d i n gl a n g u a g e ) ：微软公司在d i r e c t x 9 0 中推出高 级着色语言，这种高级着色语言是和n v i d i a 公司共同研发的，因此可以 很好的兼容n v i d i a 公司的c g 语言。由于拥有了个人电脑操作系统软件 的垄断权，微软公司设计的高级着色语言的目的是使d i r e c t x 具有更好的 兼容性以满足各个图形硬件厂商的产品的不同特点。 3 r e n d e r m o n k e y ：更准确的说，a t i 公司的r e n d e r m o n k e y 是一个材质开发 工具，其目的比前两者要更加明确，就是利用这套材质开发工具在可编程 图形硬件上进行材质的设计和开发，而这些材质程序将作为组件用在各种 实时绘制的场合中，具有很强的重要性。 4 g l s l ( o p e n g ls h a d i n gl a n g u a g e ) o p e n g l 绘制语言是在o p e n g l 2 0 的基础上提出的高级着色语言标准。一直作为图形程序开发标准的 o p e n g l 函数，目前正面临着微软d i r e c t x 的强力挑战，3 d l a b s 等公司认 识到如果没有自己的实时绘制语言，o p e n g l 将无法继续保持其固有的地 位。于是在o p e n g l 2 0 中，推出了g l s l 2 1 3g p u 通用计算 1 g p u 的优势 使用g p u 进行通用计算主要出于以下三个方面的原因：第一个原因是性能。 现代的g p u 的浮点运算比今天的c p u 快得多。以现在顶级的i n t e lc o r ei 79 6 5 处理器来说，在默认情况下，它的浮点计算能力只有n v i d i ag e f o r o eg t x2 8 0 g p u 的1 1 3 ，与a m d 的r a d e o nh d 4 8 7 0x 2 相比差距就更大了( 如表2 1 ) 。 表2 - 1 当前c p u 与c p u 计算能力对比 c p u g p u 型号对应3 2 位单精度浮点运算能力 i i l t e lc o r e i 79 6 5 7 2g f l o p s ( 每秒十亿次浮点运算) n v i d i ag e f o r c eg t x2 8 09 3 3g f l o p s a m dr a d e o nh d 4 8 7 0x 22 4 t f l o p s ( 每秒万亿次浮点运算) 9 硕士学位论文 第二章g p u 通用计算与碰撞检测 第二个理由是负载平衡。如果c p u 限制了应用程序的性能，使得g p u 有空 闲周期，可以把工作交给g p u ，让程序能够全速运转。 第三从未来发展来看，g p u 性能的增加将比c p u 快得多。从r a d e o nh d 4 6 7 0 到h d 4 8 7 0 ，不到一年的时间，a m d 的g p u 就从4 8 0 g f l o p s 增加到2 4 t f l o p s 。 在性能方面，g p u 已经超过c p u ，而且在未来会继续保持超过的势头。 2 g p u 编程模式 众所周知，在编程方面，g p u 和c p u 之间有很大的不同。我们不能仅仅改 变几个编译器标记，然后就重新编译。原因是编程模型略有不同。 主要的区别在于g p u 不是一个串行处理器，而是一个流式处理器。v o n n e u m a n n 体系结构的串行处理器连续地运行指令，更新它访问过的内存。而一 个流式处理器的工作方式略有不同，它在一组输入记录上运行一个函数( 例如一 个片段着色程序) ，并行的产生一组输出记录( 着色的像素) 。流式处理器通常要 提到这样一个称为内核( k e r n a l ) 的函数，以及作为流的一组记录。数据流入处 理器，经过一个内核函数的运算，输出到内存，如图2 2 所示。进入处理器的每 个元素都是独立的处理，在元素之间没有任何相关性。这允许体系结构并行地运 行程序，而不需要程序员了解并行单元或任何并行结构。这些函数和记录不一定 必须是像素和着色器，它们可以是任何数据，例如网格点和物理方程式。本文正 是尝试使用浮点纹理和帧缓冲区来保存几何模型的网格数据和包围体层次结构， 通过片段程序来进行相交测试的计算，最后得到碰撞检测的结果。 输入流 ( 片段) t 输入流 ( 片段) 卜口 输出流 ( 像素) 图2 - 2 在g p u 上的一个流式程序的模型 3 g p u 通用计算成果 基于g p u 的通用计算是随着图形芯片的发展而发展起来的，虽然以前的图 形卡主要只是针对图形本身的应用，如光照计算、深度检测、光栅化、反走样等 1 0 、0l， 、1， 数擘 一 函程 一 船脒 一 内片 、 ，l 、 ， 。、 卜 硕上学位论文第二章g p u 通用计算与碰撞检测 等，但针对其他更为通用的应用也有出现，如利用颜色来标示物体序号【l7 j 等。 但真正全面开展起来是因为可编程性的普及。随着2 0 0 1 年g e f o r c e 3 的出现， 顶点级可编程开始普及 1 8 】，即v e r t e xp r o g r a m ，虽然这个时候像素级上还只是固 定的几条指令。但这方面的应用已经开始全面展开，到了2 0 0 2 年人们开始利用 t e x t u r es h a d e r 结合r e g i s t e rc o m b i n e r 来求解扩散方型1 9 】，而到了2 0 0 3 年像素级 可编程性出现，很多人开始利用像素程序来求解一般代数问题，甚至有限差分方 程组求解( p d e s ) 1 4 , 2 0 2 1 1 和优化问题的求解【2 2 】。显然，随着时间的推移g p u 在 通用计算的应用也将越来越广。 文献 2 3 ，2 4 ，2 5 对g p u 通用计算的发展状况进行了总结。早在1 9 8 8 年c o h e n 等人在求解辐射度方程的时候利用颜色来标示物体序号，从而利用深度缓冲来辅 助计算物体可见性。l e n g y e l 等人利用图形硬件进行实时的机器人运动规划，即 利用颜色来标示障碍物多边形，然后将帧缓冲读回进行操作。h o f f 等人利用图 形硬件的多边形光栅化过程和深度缓冲检测来计算二维和三维的通用v o r o n o i 图，其中利用颜色来标示每个位置，通过光栅化重构出距离函数；而深度缓冲用 来进行距离比较，从而得到最近或者最远的位置。 在光线跟踪方面，c a n 等人【2 6 】在像素级进行多根光线和一个三角形求交运 算，一幅纹理存放各根光线的起始点，另一幅纹理存放对应光线的方向，同时用 三幅纹理来存放三角形，每次对一个三角形进行求交运算。p u r c e l l 等人将整个 场景采用均匀网格来表示，将所有三角形的顶点组织到三幅纹理中，并建立一个 三角形链表纹理，这样将整个光线跟踪的算法放到g p u 上来执行。 c a n 等人针对辐射度和子表面散射光照模型采用g p u 来加速计算，利用 g p u 雅可比迭代来求解矩阵辐射度方程。对于子表面算法，利用顶点编程或者 像素编程形成若干辐射图，最后采用标准的o p e n g l 光照模型来进行绘制。 c o o m b e 等人则进一步将整个辐射度的计算转移到g p u 上去，将能量发射、可 见性计算以及形状因子的计算全部放在g p u 上完成，并采用了建立纹理四叉树 的策略对场景进行自适应细分。 p u r c e l l 等人1 27 】将p h o t o nm a p p i n g 方法移植到g p u 上，将p h o t o n s 存贮在 规则网格上，并给出了两种实现思路，一个是采用多遍技术利用像素程序对这些 p h o t o n s 进行排序，另一个就是利用顶点程序结合模版缓冲将p h o t o n s 排布到网 格上，这里模版缓冲用来控制写入位置。从而采用宽度优先的随机光线跟踪求解 出全局光照效果。而其中排序、路由以及搜索运算都是基于g p u 实现。 m o r e l a n d 等人将图像处理从时域空间转换到频域空间，利用g p u 实现快速 傅里叶变换，通过灵活组织索引避免重新排序，虽然最终的效率不如f f t w 库， 但却展示了g p u 的一个很好应用前景。而文献 2 8 】利用g p u 来做三维卷积运 硕士学位论文第二章g p u 通用计算与碰掩检测 算，文献【2 9 】则利用g p u 来做小波变换，两者都是利用o p e n g l l 2 以上版本 提供的颜色矩阵和卷积操作来实现的。t r e n d a l l 等人利用硬件提供的颜色融合和 o p e n g l 图像子集的卷积和颜色矩阵等运算功能计算折射散射效果。r u m p f 等人 利用图形硬件求解传热和各向异性扩散有限单元方程，实现图像处理的功能。 j a m e s 等人利用现有的有限元包分析出变形物体的自振频率，然后采用模态 分析的方法利用顶点编程将物体各个振型进行叠加以得到新位置，这样可以将以 前在c p u 上进行的计算全部转移到g p u 上去。 另外在碰撞检测方面，文献【3 0 】采用两遍绘制的方法来计算潜在碰撞集合 ( p c s ) ，而在文献 3 1 】中采用了多个g p u 来加速可见性的计算，二者都利用了 硬件遮挡查询操作来加速。文献 7 】将表示物体的三角形表示成边纹理的形式， 实现了基于流的实时碰撞检测算法。 在代数运算方面，l a r s e n 等人利用多纹理技术实现了矩阵乘法。h a l l 等人 更进一步充分利用硬件的可编程性对矩阵乘法运算做了很多优化工作使得计算 效率大大提升。t h o m p s o n 基于顶点编程开发了一个框架系统用来进行矢量的运 算，并在此基础上实现矩阵乘法和3 - s a t 问题的求解。k r u g e r 等人【1 4 】利用像素 程序来做基本代数运算，然后在此基础上实现共轭梯度法和高斯赛德尔迭代法， 从而完成p d e s 的求解。b o l z 等人【2 0 】实现了基于像素编程的稀疏非结构化矩阵 的共轭梯度法和正交网格的多重网格法，并用于加速几何处理和流体模拟。 h i l l e s l a n d 等人【2 2 l 将最速下降法和共轭梯度法求解带有简单约束和规则化的非 线性最小二乘优化问题映射到最新的图形硬件上，并将其应用到复杂的图像建模 问题上。 “等人采用l b m ( l a t t i c eb o l t z m a n nm e t h o d ) 来模拟流体和烟的效果。通过 将粒子包合成纹理，将b o l t z m a n n 方程组映射到光栅化和帧缓冲操作上，整个计 算是采用r e g i s t e rc o m b i n e r 来实现的。更进一步，在文献【3 2 】中利用硬件计算 l b m 来模拟物体在风中飞舞的情形，虽然这个时候g p u 已经开始支持像素级 浮点精度，但考虑到计算速度的问题，仍然用的是固定渲染管道。h a r r i s 等人( 3 3 】 通过r e g i s t e rc o m b i n e r 编程求解c m l 问题( c o u p l e dm a pl a t t i c e ) ，从而实现交 互的对流模拟、反应扩散以及沸腾效果模拟。而在文献 3 4 中，作者开始采用像 素程序来求解p d e s 以模拟云彩的运动。 g o o d n i g h t 等人实现了基于像素程序的多重网格算法，用来求解边界值问 题( 热传导问题、流体力学问题) 。k i m 等人【3 5 】将冰晶体生长过程采用g p u 来 实施物理计算，整个物理方程组的计算在g p u 上执行。l e f 0 l l l l 等人将l e v e l s e t 的等值面数据压缩为一个动态稀疏纹理格式，针对不同边界情况采用不同的像素 程序来进行计算l e v e l s e t 的p d e s ，另外将下一个活跃的片段信息压缩成一个位 1 2 硕士学位论文 第二章g p u 通用计算与碰撞检测 矢量消息，将该消息传递给c p u 以决定它需要传送给g p u 的顶点和纹理坐标， 这里还充分利用了硬件的自动m i p m a p p i n g 技术低采样截止到一个像素。 2 2 碰撞检测 碰撞检测问题是对一个立体几何模型( 其模型可以有其物理属性) 集合中模 型之间的空间位置关系进行判断，决定在任何时刻两个移动的物体或者一个移动 的物体与周围的障碍物是否碰撞。在一个需要碰撞检测的系统中( 如虚拟现实技 术中) 碰撞检测关于几何模型此时空间位置关系的报告将影响系统的下一步行 动，如停止某遇到障碍物的模型的进一步运动，或者对模型进行物理力学、运动 学的分析模拟，进而改变模型的物理、几何属性。 碰撞检测在计算机图形学、计算机辅助设计、计算机动态模拟，虚拟现实、 场景浏览、机器人路径安排等领域有着广泛的应用。碰撞检测算法的效率直接影 响到上述应用的实时性，特别是在大型场景的应用中，由于周围场景的物体和移 动的物体比较多，需要反复地进行大量物体之间的碰撞检测，碰撞检测已成为这 种应用的一个计算瓶颈，因此快速的碰撞检测方法是实现这种应用的一个非常重 要的关键技术。 在碰撞检测的研究中主要涉及下面几方面的内容：1 ) 碰撞检测算法所涉及 的几何模型：2 d 模型或3 d 模型，凸体或非凸体，曲面或多面体；2 ) 碰撞检测 算法所输出的信息：两个物体的最短距离，给定时间段内两个移动物体是否碰撞， 实时报告两个物体是否碰撞，其他如最近特征、最近实现点对等辅助信息；3 ) 碰撞检测技术和方法：有空间划分( s p a t i a ld e c o m p o s i t i o n ) 和包围体技术，膨胀卷、 扫描卷技术，重复冲突检测技术，计算几何技术、线性优化等技术【3 6 l 。 由于碰撞检测的重要应用，人们对它进行了广泛而深入的研究。目前在计算 几何、机器人特别是计算机图形等应用领域提出了许多碰撞检测算法。不同的算 法适合于不同的场景，其中有些适合特殊的场合，有些侧重于一般理论的探讨。 还没有能够满足所有情况的通用碰撞检测算法。 按每次检测所检查的时间范围分类，各种碰撞检测思想可分为时间片和空间 时间包围体两种，前者只检查在调用碰撞检测的时间点上是否有碰撞发生，后者 检查包括调用时间点的一段时间内是否有碰撞发生。时间片基本上又分成空间分 割和包围体层次树两种，根据包围体的不同，包围体层次树又可分为多种如球包 围体，矩形包围盒等【3 7 】。 2 2 1 碰撞检测算法的一般框架 在包含个运动物体和m 个静止物体的复杂虚拟环境中，运动物体在可能 与静止物体发生碰撞的同时，运动物体之间也可能发生碰撞。在每个时间间隔中， 硕士学位论文第二章g p u 通用计算与碰撞检测 需要进行i1 ：i + n m 次物体之间的两两碰撞检测。随着和m 的增大将变得非 l2 常耗时。为达到可交互的速度，必须在进行物体间两两碰撞检测之前，首先将多 数明显不相交的物体对进行快速排除，减少算法执行的次数【3 8 l 。我们把这个过 程称为初步检测阶段。对于初步检测阶段的后继阶段，我们称之为碰撞检测算法 的详细检测阶段。在详细碰撞检测阶段，基于层次包围体树的碰撞检测算法首先 会同时遍历物体对的层次树，递归检测层次树节点之间是否相交，直到层次树叶 子节点，进而精确检测叶子节点中所包围的物体多边形面片是否相交。 1 初步检测阶段 扫描一修剪方法【3 9 舯】是初步检测阶段的常用技术