（计算机软件与理论专业论文）基于图形处理器的碰撞检测算法的研究.pdf

山东大学硕士学位论文 摘要 碰撞检测就是判断某一时刻两个移动的物体之间是否发生了碰撞。作为一个 典型而实用的方法，需要考虑在任意离散的时间帧序列，两个物体是否相交。碰 撞检测是计算机动画、游戏设计、机器人、计算机图形学等领域的一个重要的研 究方向。如一个移动的物体在虚拟现实场景中的漫游，移动的路径通常是通过人 机交互临时确定的，在这个过程中，实时的碰撞检测显得尤为重要。 尽管目前针对碰撞检测的研究已经有了许多有价值的成果，但随着诸如虚拟 现实等新兴领域的涌现以及随之而来的物体模型与场景越来越复杂，人们对交互 实时性、场景真实性的要求越来越高，特别是在大型的复杂场景中，由于场景中 的物体，甚至移动的物体数目都很多，这就需要反复的进行大量物体间的碰撞检 测，从而给碰撞检测问题带来了前所未有的挑战。 图形处理器( g r a p h i c sp r o c e s s i n gu n i t ，g p u ) ，作为一种高度并行的流处 理器，凭借其强大的处理能力和高存储带宽，为实时的、复杂的碰撞检测提供一 种有效的方案解决平台。围绕此方面进行的研究成为近几年来g p u 的应用之一， 并逐渐成为研究热点。本文充分的利用了图形处理器高度的并行处理能力，提出 了下面两个算法： 1 通过搜索两个凸多面体的分离平面来检测两个凸多面体是否碰撞。该算法使 用一个启发式策略搜索两个物体的分离平面，经过有限的步骤，算法或者找 到一个分离平面报告物体分离，或者证明两个凸多面体碰撞。在算法中，利 用g p u 加速了关键步骤一支撑顶点对的计算。并结合在g p u 中分区域求最 大值的约减( r e d u c e ) 方法，给出了适用于复杂场景中多个物体的实时碰撞 检测方案。 2 提出了一个基于g p u 实现的、针对于复杂的封闭、变形物体的实时碰撞检测 算法。算法有效的利用了图形处理器中的各种缓存，以及遮挡查询 ( o c c l u s i o nq u e r y ) 操作，同时该算法还可以应用于自碰撞检测。尽管目前 的算法还存在一定的局限性，但算法既不需要复杂的预处理过程，也不需要 复杂的数据结构来存储数据，而且算法可以直接应用于可以绘制的各种模 山东大学硕士学位论文 型，计算效率较高。 我们用多个实例测试了算法的性能，并将上述的算法与其他碰撞检测算法进 行了比较。 关键词：碰撞检测；图形处理器；基于图像空间的技术：虚拟现实。 i i 山东大学硕士学位论文 a b s t i 认c t c o l l i s i o nd e t e c t i o ni st od e t e r m i n ew h e t h e rt w om o 访n go b j e c t sc o l l i d eo rn o ta t a n ym o m e m i ti sr e q u i r e d , a sat y p i c a la n de f f 6 c i e n ta p p r o a c hi np r a c t i c e ，t oc o n s i d e r w h e t h e rt h et w oo b j e c t sc o l l i d e di na n yo fas e q u e n c eo fd i s c r e t et i m ef l a m e s c 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 tr e s e a r c h e si nt h ef i e l d so fc o m p u t e r a n i m a t i o n ，g a m ed e s i g n i n g ，r o b o t i c s ，c o m p u t e rg r a p h i c s ，a n ds oo n t h i st e c h n i q u ei s n e c e s s a r ye s p e c i a l l yw h e nt h em o t i o np a t ho fa no b j e c ti sd e f m e di n t e r a c t i v e l yr a t h e r t h a np r e s p e c i f i e d ，s u c ha sm o t i o np l a n n i n gi nr o b o t i c si nv i r t u a lr e a l i t ya p p l i c a t i o n t i l ln o w , al o to fa c h i e v e m e n t sh a v eb e e nm a d ei nt h ep r o b l e mo fc o l l i s i o n d e t e c t i o n h o w e v e r , t h ef i e l do fv i r t u a lr e a l i t yi sb e c o m i n gm o r ea n dm o r ep o p u l a r , w h i c hi sf o l l o w e db yt h ei n c r e a s i n gc o m p l e x i t yo fo b je c tm o d e l sa n de n v i r o n m e n t s ， p e o p l e si n c r e a s i n gr e q u i r e m e n t so ft h er e a l - t i m ei n t e r a c t i o na n de n v i r o n m e n tr e a l i t y e s p e c i a l l yi nl a r g ec o m p l i c a t e de n v i r o n m e n t sw h i c hc o n s i s to fal a r g ea m o u n to f m o v i n go b j e c t s ，i ti sr e q u i r e dt od oc o l l i s i o nd e t e c t i o na m o n gt h o s em o v i n go b j e c t s c o n s e q u e n t l y , u n p r e c e d e n t e dc h a l l e n g eh a sb e e nb r o u g h ta b o u tt ot h ep r o b l e mo f c o l l i s i o nd e t e c t i o n g r a p h i c sp r o c e s s i n gu n i t ( g p u ) ，as t r e a mp r o c e s s o r 丽t ll l i g hp a r a l l e l i s m , h i g h c o m p u t a t i o n a lp o w e ra n dm e m o 黟b a n d w i d t h ，s e r v e sa sa ne f f i c i e n ta n ds a t i s f y i n g s o l u t i o nt ot h i sp r o b l e m r e s e a r c h e so ns u c hk i n d o fp r o b l e mh a v eb e c o m eo n eo ft h e h o tt o p i c so ng p ur e s e a r c h t h i sp a p e ri n t r o d u c e st h ef o l l o w i n gt w oa l g o r i t h m sb o t h o fw h i c ha p p l yt h eh i g hc o m p u t a t i o n a lp o w e ra n dp a r a l l e l i s mo fg p ut oh e l p i n gs o l v e t h ep r o b l e mo fc o l l i s i o nd e t e c t i o n 1 d e t e c tc o l l i s i o no ft w op o l y t o p e sb ys e a r c h i n gas e p a r a t i n gp l a n e a ni t e r a t i n g h e u r i s t i cm e t h o di sa p p l i e dt of i n dt h es e p a r a t i n gp l a n e a f t e rc e r t a i ni t e r a t i n g s t e p s ，t h ea l g o r i t h mc a nb et e r m i n a t e db ye i t h e ras e p a r a t ep l a n e b e i n gf o u n do r p r o v i n gt h a tt h e s et w op o l y t o p e sa r ec o l l i d e d a tt h es a m et i m e ，g p ui sa d o p t e d t oa c c e l e r a t et h ek e ys t e p c o m p u t a t i o no ft h es u p p o r t i n gv e r t e xp a i r d u et ot h e i l l 山东大学硕士学位论文 h i 曲p a r a l l e l i s mo fg p u ，t h ec a l c u l a t i o no ft h ek e ys t e p ，g e t t i n gt h es u p p o r t v e r t e xp a i r s ，i sa c c e l e r a t e d ar e a l t i m ec o l l i s i o nd e t e c t i o nf o rm u l t i p l eo b je c t si n l a r g ee n v i r o n m e n t si s a l s oi n t r o d u c e di nt h i s p a p e r , b a s e do nt h er e d u c t i o n m e t h o df o rc o m p u t i n gt h em a xv a l u ei ng p u 2 a ne f f i c i e n t a l g o r i t h m f o rr e a lt i m ec o l l i s i o nd e t e c t i o nb e t w e e n c o m p l e x d e f o r m a b l eo b je c t sw i t hc l o s e ds u r f a c e sb yu s i n gg r a p h i c sh a r d w a r e t h e a l g o r i t h ma d o p t sa l le f f e c t i v eu s eo ft h er e n d e r i n gb u f f e r sa n dt h eo c c l u s i o n q u e r yo p e r a t i o n ，a n dc a na l s ob ea p p l i e dt od e t e c ts e l f - c o l l i s i o n t h o u g ho u r c u r r e n t a l g o r i t h m h a ss o m el i m i t a t i o n s ，i t r e q u i r e s n e i t h e r e x p e n s i v e p r e p r o c e s s i n gn o rc o m p l e xd a t as t r u c t u r e sa n di sd i r e c t l ya p p l i c a b l et oa l lk i n d s o fm o d e l sw h i c ha r er e a d yt or e n d e r i nc o n t r a s tt om o s te x i s t i n gm e t h o d s ，t h e p r o p o s e da l g o r i t h mi sc o m p l e t e l yi m p l e m e n t e di ng r a p h i c sh a r d w a r ea n dd o e s n o tp e r f o r mt i m ec o n s u m i n gf r a m e b u f f e rr e a d b a c k sf r o mg p u t h i ss i g n i f i c a n t l y i m p r o v e st h ep e r f o r m a n c e s e v e r a le x p e r i m e n t sa n dc o m p a r i s o n s 、历t l lo t h e ra l g o r i t h m sh a v eb e e nc a r r i e do u t t os h o wt h ep e r f o r m a n c ea n de f f i c i e n c yo fo u ra l g o r i t h m s k e yw o r d s ：c o l l i s i o nd e t e c t i o n ，g r a p h i c sp r o c e s s i n gu n i t s ，i m a g e b a s e d t e c h n i q u e s ，v i r t u a lr e a l i t y i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定 论文作者签名：导师签名： 山东大学硕士学位论文 ii i i 1 1 研究背景及意义 第1 章引言 碰撞检测，也叫相交测试或接触测试，是判断某一时刻两个物体之间是否发 生了碰撞。如今，碰撞检测技术在c a d c a m 、机器人路径规划、计算机动画、虚 拟现实和游戏设计等领域有着广泛的应用。由于其计算的复杂性及实时性的要 求，使其成为实时模拟中运动物体动态模拟的瓶颈，制约着三维物体运动模拟的 真实性。例如，游戏中搏斗和战争题材的模拟，需要及时的在大规模复杂场景中 检测出场景中的任意两个物体是否发生碰撞。如果物体没有碰撞，则可以按原来 的运动轨迹继续运动；如果碰撞，需要适时的做出碰撞以后的反应，使得物体运 动符合自然界的规律，否则会影响游戏的真实性。再比如，对于机器人的控制和 路径规划里，采用及时的碰撞检测可以帮助机器人避开障碍物，避免不必要的碰 撞。由上可见，精确而实时的碰撞检测技术是游戏设计和虚拟现实技术中研究的 关键技术之一。研究虚拟环境中的碰撞检测模型和实时高效的碰撞检测算法，对 于虚拟现实和人机交互发展具有重要的意义，长期以来一直是国内外研究的热 点。目前已提出了许多碰撞检测的算法，其中有些算法适用于特殊的应用，而有 些算法更侧重于一般理论的探讨，不同的算法处理的物体模型可能不同，采用的 解决问题的策略也可能不同，因而算法的效率也有所不同。但是目前的碰撞检测 算法普遍存在着如下几个问题： 1 最传统的碰撞检测算法是对两个物体所有的顶点做计算，看物体是否有交。 这样，随着虚拟环境中的物体模型与场景越来越复杂，所需的计算量往往是 随物体和场景复杂度指数级增长的。因此，碰撞检测速度是非常慢的，不能 满足实时性的要求。 2 针对上述缺点，产生了一系列的加速算法，如a a b b 包围盒，球形包围盒算 法，但是此类算法只是近似的碰撞检测算法，在精度上往往不能满足要求。 3 另外，还产生了一系列利用特殊的数据结构来构造物体，以加速碰撞检测的 算法，但此类算法约束较多，一般需要对物体进行费时的预处理操作，因此， 缺乏通用性。 山东大学硕士学位论文 皇皇皇曼曼曼皇量皇曼曼曼曼皇曼舅曼曼曼曼曼曼量1 量曼曼曼曼 一i i 曼量曼曼曼皇量曼皇曼量曼曼曼曼曼皇曼曼皇 4 目前，大部分的算法都不适用于形状变化的物体。但在虚拟场景中，形状不 断变化物体是普遍存在的，例如，行走中的人，水中游动的鱼，在风中摇曳 的树枝等等。 1 2 研究现状 在正式展开本文主要工作的论述之前，首先有必要先介绍下和本文的研究 内容相关的一些问题的研究现状。 早在2 0 世纪7 0 年代，就开始了最早的碰撞检测相关方面的研究，但受限于 当时计算机软硬件的发展，无法做到实时的计算，因此碰撞检测的计算往往都是 离线完成的。因此，当时的碰撞检测大部分只停留在理论研究方面，很难应用到 实际的应用中。随着计算机计算能力、存储容量、通信带宽等软硬件的迅猛发展， 尤其是进入2 0 世纪9 0 年代以来，人们对于交互的实时性和场景的真实性要求日 益严格，对于碰撞检测的研究也成为计算机图形学中的一大热点，相继出现了一 系列的经典的算法。 碰撞检测的分类有许多方法。目前，最常见的两种分类方式是：按被检测物 体的表示方法分类和按碰撞检测的采样方式分类。 图1 1 集合模型表示法分类 一种最常见的且目前普遍接受的按被检测的物体的表示方式的分类方法是 由l i n 于9 8 年提出的啪1 。如图1 1 所示。此种分类方法的碰撞检测算法我们不 做详述，我们着重介绍一下第二类常见的分类方法。 按碰撞检测的采样方式，碰撞检测问题可以分为基于物体空间的碰撞检测和 基于图像空间的碰撞检测1 。 基于物体空间的碰撞检测方法一般要依赖于物体的表示结构。因此，该类方 2 山东大学硕士学位论文 法常常结合层次表示、空间划分、包围盒、解析方法等手段加速处理。此类方法 一直是碰撞检测的研究重点，因此相关的算法已相当成熟。 基于包围盒层次结构的碰撞检测算法的应用较为广泛。此类方法需要预先针 对每一个物体构建一棵层次包围盒树。构建层次包围盒树既可采用自顶向下的策 略，也可以采用自底向上的策略来进行。物体的层次包围盒树可以根据其所采用 包围盒类型的不同来加以区分。主要包括层次球型( s p h e r et r e e s ) 包围盒树洲， a a b b ( a l i g n e da x i sb o u n d i n gb o x ) 层次包围盒树m 1 ，方向包围盒( o r i e n t e d b o u n d i n gb o x ，o b b ) 包围盒树h a l , k - d o p 层次包围盒树胁1 等等。其中较为著名且 比较实用的是g o t t s c h a l k 等人于1 9 9 6 年提出的o b b 包围盒树算法- r a p i d 算 法。该算法提出了一种数据结构及适用于该结构的碰撞检测算法。算法首先对物 体进行预计算，对物体模型构建包围较为紧密的o b b 层次结构树。进而，在程序 运行时，对两个物体的碰撞检测转换成对两棵o b b 树的遍历操作。同时利用分离 轴原理，进行树中节点的、在不同方向上的相交测试，从而实现物体的碰撞检测。 该算法大大减少了相交测试的物体对的数目，加快了执行速度。 另外，基于物体空间的碰撞检测方法还有许多经典的算法。 g i l b e r t 、j o h n s o n 和k e e r t h i 提出了经典的、适用于凸体的g j k 算法u 。 算法基于这样一个事实：两个物体的最短距离等于他们的m i n k o w s k i 差彤到原点 的距离。因此，算法将原来两凸体的碰撞检测转化为m i n k o w s k i 差彤与原点之间 的距离的计算。r a b b i t z 等人在1 9 9 4 年利用连贯性对g j k 进行了改进h u 。c a m e r o n 等人于1 9 9 7 年进一步改进了该算法，提出了g j k 增强算法( e n h a n c e dg j - k ) h 1 。 g j l 【增强算法在g j k 的基础上引入了爬山思想，提高了算法效率。 1 9 9 5 年，c o h e n 等人的i - c o l l i d e 算法h 3 采用“最近特征对算法”进行碰撞 检测，同时结合了时间连贯性以及a a b b 包围盒算法予以加速。该算法能够处理 多个运动物体组成的场景。1 9 9 6 年，c h u n g 等人提出了q - c o l l i d e 算法嘲，算 法将最近特征对的距离的计算改进为分离向量的搜索，当物体分离时，算法效率 较高。 l i 等人利用相似的原理，提出了一个新的用于凸多面体碰撞检测的算法一 h s j u m p 啪3 。算法建立了一个有效的碰撞检测模型用于报告物体的碰撞，同时 提供了一个快速的启发式的策略用于搜索两个凸多面体的分离向量。该算法利用 山东大学硕士学位论文 凸多面体的层次表示来搜索支撑顶点对，利用平衡二叉树来记录球面凸多边形的 顶点，并结合时间和空间相关性来加速了算法的执行。 但由于c p u 的发展受摩尔定律的限制，运算能力的提升缓慢，而基于物体空 间的碰撞检测方法的运行效率很大程度上依赖于c p u 的运算能力，因此此类算法 在2 0 0 0 年后逐渐进入一个研究的低谷。 基于图像空间的碰撞检测方法一般是将三维物体向投影面投影，降维到一个 二维的图像空间，然后分析保存在图像空间的各类缓存信息，得出物体之间是否 发生碰撞并进行下一步处理。这类算法优势在于能有效利用图形处理器强大的处 理能力和高存储带宽来减轻c p u 的计算负荷，从而达到提高算法效率的目的。但 是基于图像空间的碰撞检测算法由于其检测结果的不精确性和对图形处理器的 要求较高而一直发展较慢。近几年，随着图形硬件计算性能的迅速增长以及高精 度浮点数和整数的支持，基于图像空间的碰撞检测算法逐渐成为碰撞检测的热门 方向。 s h i n y a 等和r o s s i g n a c 等在这方面做了开创性的工作。1 9 9 1 年，s h i n y a 和 f o r g u e 等首先提出利用图形硬件的深度缓存来判断两凸体是否相交旧1 。算法在 绘制物体的同时，记录物体映射到图像空间后对应的每个像素的最大深度和最小 深度，然后针对每一像素，利用类似扫描线算法的方法判断最大深度值和最小深 度值的邻接情况来得到物体是否与其他物体碰撞，如果相邻，没有发生碰撞；否 则，与其他物体碰撞。但算法需要费时的深度缓存读取操作，因此速度较慢。1 9 9 2 年r o s s i g n a c 等人利用类似的方法，结合模板缓存来辅助进行碰撞检测池1 。 同样是同时利用扫描线算法的原理，并结合深度缓存和模板缓存， m y s z k o w s k i 等人提出了一类似的碰撞检测算法口们。该算法首先利用模板缓存来 保存视平面中每个像素所代表的射线进入一物体前进入和离开其他物体的次数， 然后读取模板缓存中的值来判断两物体是否相交。该算法同样也只能处理两个凸 体之间碰撞检测问题。 类似的，b a c i u 等人也提出了一个图形硬件加速的基于图像空间的碰撞检测 方法r e c 0 d e n l 。同样是利用扫描线算法的原理，算法分析了一个像素对应的 射线穿过两个凸体的八种情况，并然后根据每种情况判断两个物体的碰撞与否。 算法利用模板缓存来记录这八种情况，并通过分析得到模板缓存中值与碰撞与否 4 山东大学硕士学位论文 的关系加以判断。算法主要缺点是仅能处理凸多面体或由凸体组成的多面体，并 且算法需要回读模板缓存，也比较费时。 f a n 等人改进了r e c o d e 方法，使得算法不仅仅局限于凸体嘲。首先利用凸分 解技术将非凸的物体分解成多个凸体，然后利用r e c o d e 的思想判断碰撞与否。 算法没有从本质上改变r e c o d e 算法的不足，而且需要预先的凸分解操作，因此 也受到r e c o d e 算法缺点的限制，如需要进行耗时的g p u 回读操作。 2 0 0 3 年，g o v i n d a r a j u 等人提出了c u l l i d e 算法n 引，算法不局限于凸体，适 用性较高，而且速度较快。算法首先利用图形硬件支持良好的遮挡查询功能快速 去除大规模场景中明显不会发生碰撞的物体，即通过初步的物体级的裁剪 ( o b j e c tl e v e lp r u n i n g ) 和子物体级的裁剪( s u b o b j e c tl e v e lp r u n i n g ) 构建可 能碰撞物体的集合。然后利用几何的快速相交检测算法得到碰撞检测的结果。该 算法与一般的基于图象的碰撞检测算法略有不同，算法只是利用图形硬件进行物 体裁剪操作，而最终的精确碰撞检测阶段还是由c p u 来完成的。进而于2 0 0 4 年， g o v i n d a r a j u 等人又利用在c p u 上的1 d 重叠测试及g p u 上执行2 维半的重叠测 试进行处理，提出了一种适用于变形物体的自碰撞检测算法利，算法效率也比较 高。 也是在2 0 0 3 年，h e i d e l b e r g e r 提出了一种基于图像空间的碰撞检测算法乜1 1 ， 该算法可以适用于任意形状的、变形的物体。整个算法分为三步：首先，对每对 物体计算他们的a a b b 包围盒。如果a a b b 包围盒有交，执行第二步对每个物 体在a a b b 包围盒相交部分计算其相应的层次深度图( 1 a y e r e dd e p t hi m a g e ) 表 示。最后，通过图形硬件绘制过程来判断两物体在层次深度图的每个象素上是否 有相交区间存在，确定物体是否发生碰撞。此算法在2 0 0 4 经进一步改进胁1 ，实 现了对变形物体的自碰撞检测，适应性较高，但构建层次深度图的过程需要从 g p u 回读数据，一定程度上影响了算法的效率 但是基于图像的碰撞检测算法普遍存在以下两点缺陷： 1 由于图形硬件绘制图像时光栅化( r a s t e r i z a t i o n ) 操作本身固有的离散性， 不可避免地会产生一定误差，因此与c p u 相比，检测结果的精度上会有一定 的差距。 2 由于使用图形硬件辅助计算，基于图像的碰撞检测还需要考虑如何合理地平 山东大学硕士学位论文 衡c p u 和图形硬件的计算负荷以及如何平衡c p u 与图形硬件间数据传输造成 时间消耗。 然而，基于图像的碰撞检测算法的一般实现起来比较简单，而且它们可以有 效利用图形硬件的高性能计算能力，缓解c p u 的计算负荷，在整体上提高算法的 效率。并且，随着图形硬件的进一步发展，基于图像的碰撞检测算法发展前景广 阔。 1 3 主要研究内容 本文首先提出了一个碰撞检测算法的通用框架，框架描述了大规模场景中碰 撞检测的必要步骤以及内容，然后根据此框架讨论了两个碰撞检测的算法： 1 基于图形处理器( g p u ) 实现的启发式分离向量搜索的凸多面体碰撞检测算 法g h s j 删p 算法。算法基于l i 的h s j u m p 算法，并利用g p u 的高度并 行性加速了其中关键步骤支撑顶点对的计算。并结合在g p u 中分区域求最大 值的约减方法，给出了适用于复杂场景中多个物体的实时碰撞检测方案。 2 适用于复杂变形模型的、基于图形硬件的碰撞检测算法。算法有效的利用了 图形硬件中的绘制缓存如深度缓存，模板缓存等，并结合遮挡查询及多遍绘 制技术( m u l t i - r e n d e r i n g ) 。该算法的研究内容和其他相关研究的主要区别， 或者说是该算法的主要创新工作主要体现在以下四个方面： 1 )算法适用于任意形状的封闭物体，不需要复杂的预处理过程和数据结 构；并且对检测物体的运动轨迹没有要求，即物体可以以任意速率、加 速度做任意运动。 2 )算法使用图形硬件支持良好的遮挡查询来判断物体的碰撞与否，避免了 以往算法中大量缓存的回读操作，提高了算法的效率。 3 ) 整个碰撞检测算法是在图形硬件上完成的。这样，充分的解放了c p u ， 使其可以用作其他方面的计算，均衡了c p u 和g p u 的计算负载。 4 )算法简单有效，可以在普通p c 机上方便的利用o p e n g l 加以实现。 1 4 本文的组织结构 本文的余下内容将按照如下的章节进行组织。 6 山东大学硕士学位论文 第2 章首先提出了大规模复杂场景中碰撞检测的通用的模型框架。继而介绍 论文中涉及的相关数学理论、概念和定义，并介绍了基于图形处理器的通用计算 的计算模型。 第3 章论述了采用图形处理器加速的、基于分离平面搜索的凸多面体碰撞检 测算法g h s j u m p ，并设计了碰撞检测场景，将改进后的算法与原算法做了比 较。 第4 章介绍了一个基于图形处理器的、针对于复杂、封闭、变形物体的实时 的碰撞检测算法。算法有效的利用了图形处理器中的各种缓存，以及遮挡查询操 作，并且算法可以应用于自碰撞检测，适用性较广，效率较高。 第5 章是结束语及未来工作展望。 山东大学硕士学位论文 第2 章预备知识 2 1 碰撞检测算法框架描述 对于多个物体的碰撞检测，一般应该从以下两个方面进行突破。 1 好的裁剪算法。裁剪掉与其他物体一定不会相交的物体，使得待检测的物体 数目尽可能的少。 2 好的碰撞检测算法。使得检测用的时间尽可能的少。 第一方面研究的典型代表就是包围盒系列的算法。此类算法的主要目的就是 设计不同的包围盒，使得包围盒不但能够计算简单、快速，而且可以更紧密的包 围物体，使得对两个物体在精确检测之前先利用包围盒代替物体做快速的碰撞检 测。如果包围盒不相交，那么两个物体肯定不会碰撞，整个算法可以就此结束， 从而节省掉后续费时的物体间的碰撞检测。第二方面的研究就是平时说的各种各 样的碰撞检测算法。具体的算法可以参考1 2 节中介绍的各种方法。 本节主要提出了一个较为通用的碰撞检测的算法的框架( 见图2 1 ) ，该框 架作为后续两章碰撞检测算法的基础。 图2 1 碰撞检测算法的通用框架 对于一个大规模场景中的碰撞检测，场景中往往需要进行碰撞检测的物体个 山东大学硕士学位论文 数是非常多的，因此我们首先要进行裁剪操作以裁剪掉与其他物体肯定不碰撞的 物体。我们的框架中裁剪阶段使用了两步裁剪。首先使用一种裁剪算法对物体集 合进行多遍的裁剪。在前几遍裁剪时，可能裁剪掉的物体数目较多，但继续运行 裁剪方法时，可能一遍裁剪只能剔除掉少数几个物体。要注意，裁剪算法的运行 也是需要消耗时间的。因此，我们这里做了一个时间和效率的均衡，即当某遍裁 剪操作剔除掉的物体个数小于一个设定好的阈值。时，那么再继续进行裁剪所用 的时间的开销可能大于它的收益，这样就不再进行裁剪。此时剩余的物体集合构 成了可能碰撞的物体集合p c s ( p o t e n t i a lc o l l i d i n gs e t ) 。在后续的算法中， 只需对该p c s 集合中的物体做碰撞检测即可。 但可能碰撞物体集合p c s 中物体可能存在这样一种情形：在一个空间区域中 有a 个物体是碰撞的，而在另一个空间中又有b 个物体是碰撞的，那么这a + b 个 物体都是属于p c s 的，但a 个物体中的任意一个与b 个物体中的任意一个都是不 相交的，而且可能相隔较远。如果我们对整个p c s 中的物体进行两两的碰撞检测， 可能就会导致许多不必要的检测，时间复杂度为0 ( n 2 ) 级别的，这里n 为p c s 中 物体个数。如果p c s 中物体数目较多，那么两两的精确碰撞检测的时间也是不小 的。所以我们在进行精确碰撞检测之前又引入了包围盒碰撞检测，由包围盒的性 质我们知道，它可以快速有效的判断出两个物体的分离，从而避免了上述的问题。 最后进行精确的碰撞检测，这里的关键就是设计一个好的碰撞检测算法，使 得算法能够准确、有效、快速的得到检测物体碰撞与否的结果。本文后续两章就 主要介绍了本文提出的两个碰撞检测算法。其中第一个算法是针对凸体的，能够 实现精确的碰撞检测，但是算法只是利用g p u 加速了其中的关键步骤，而且对物 体形状限制较多，因此又设计了第二个算法，该算法对物体形状没有限制，而且 整个碰撞检测算法都是在g p u 上完成的，能适用的范围较广。两个算法的效率都 充分利用了图形处理器强大的处理能力，效率较高。 为方便叙述本文给出的碰撞检测算法，并使读者能够清楚的理解算法中涉及 的概念，下面就本文涉及的数学理论、概念和相关的定义做一下介绍。 9 山东大学硕士学位论文 2 2 分离平面 分 图2 2p 和q 分离 两个凸体p * 10 如果尸n0 = 0 ，则称p 和p 是不相交的、或分离的。否则 称两个凸体是相交的、或者接触的。对于两个分离的凸体，一定存在一个平面 使得p 和p 分别位于三的两侧，并且尸nl = 0 ，p nl = 0 ，即满足条件： ( p 一虼) s 0 ，v q q 或者，( p 一圪) s 0 ，v p p ，并且( 旷圪) s 0 。一般情况下，分 离平面和分离向量不是唯一的。另一方面，如果存在一个平面满足上面的条件， 则说明p 和p 是分离的，可以用此性质来判断两个凸体是否碰撞。 2 3 支撑顶点 令p 是占中一个封闭的凸体，矿例表示p 的所有顶点的集合。任意给定一 个向量s r 0 ，如果s p = m a x s ji _ ：r 矿例) ，这里p 矿例是p 的 边界上一个点，则称p 为p 的相对于s 一个支撑顶点( s u p p o r t i n gv e r t e x ) 。 一般情况下，p 对于s 的支撑顶点是唯一的，但如果p 上存在一个边p 垂直于s 并且e 的一个端点是p 的相对于s 的支撑顶点，则e 的另一个端点也是p 的相对 于s 的支撑顶点。类似的，如果p 上存在一个面，垂直于s 并且，的一个顶点 是p 的相对于占的支撑项点，则，上其他所有顶点均为p 的相对于s 的支撑顶点。 l o 山东大学硕士学位论文 _|li ii_i 2 4 支撑顶点对与单位支撑顶点向量 支撑 支撑顶点p 图2 3 支撑顶点对 给定一个向量s 和两个凸多面体尸和识令p 是p 的相对于s 的一个支撑 顶点，q 是p 的相对于s 的负方向巧的一个支撑顶点，则称有序对( b 曲为尸 和p 相对于向量s 的支撑顶点对( s u p p o r t i n gv e r t e xp a i r ) 。对于给定凸多面 体p 和9 ( 见图2 2 ) ，向量( q - p ) 称尸和p 相对于s 的支撑向量( s u p p o r t i n g v e c t o r ) ，r = ( g 韵i ( q - p ) l 为p 和p 相对于s 的单位支撑向量。 2 5 图形处理器g p u 图2 4 传统g p u 渲染管线 图形硬件在早期仅作为图形绘制的协处理器来加速三角形等基础面片的运 算及绘制操作，而且g p u 的渲染管线( p i p e l i n e ，或叫流水线) 是固定的，我们 只能在数据进入g p u 之前通过应用程序对数据进行操作，即进入g p u 之后就不能 人为的干涉中间的操作，类似于黑盒子。 l l 东大学硕七学位论文 图2 5 现代的g p u 渲染管线 然而近年来，由于受游戏市场的驱动，g p u 的可编程性、计算能力和处理精 度、灵活性等方面正飞速的发展，已经在许多方面上都胜过了传统的c p u 。这使 得它们能够处理更多的图形学以外的应用。 2 6 渲染引擎模式s h a d e rm o d e l 通常简称为s m 。所谓的s h a d e r 就是一段能够针对3 d 对象进行操作、并被 g p u 所执行的程序。通过这样的程序，人们能够获得绝大部分想要的三维图形效 果。s h a d e rm o d e l 根据操作对象的不同被分为：对顶点进行操作的顶点渲染引 擎( v e r t e xs h a d e r ) 和对像素进行各种操作的像素渲染引擎( p i x e ls h a d e r ) 。 其中顶点渲染引擎在软件层上来说就是一系列对顶点数据进行操作处理的指令 程序，在硬件上就是执行这些顶点渲染程序的处理单元。同样的，像素渲染引擎 在软件层上来说就是对像素及其相关属性进行操作处理的指令程序，在硬件上就 是执行像素渲染程序的处理单元。 在s h a d e rm o d e l 发展史上，从s m1 - 0 进化到s m2 0 称得上是真正意义上 的技术革命，后者赋予了显示芯片强大的能力，人们在游戏中也领略到前所未有 的视觉体验，例如水面光影和雾化等特效的出现使游戏场景更真实。从s h a d e r m o d e l4 0 开始，另一个重大变化就是在顶点渲染引擎和像素渲染引擎之间引入 山东大学硕士学位论文 了一个新的可编程图形层几何渲染引擎( g e o m e t r ys h a d e r ) 。原来的顶点渲 染引擎和像素渲染引擎只是对逐个顶点或像素进行处理，而新的几何渲染引擎可 以批量进行几何处理，快速的把模型类似的顶点结合起来进行运算，效率较高。 2 7c g 语言 图2 6c g 语言开发框架图 c g 呻1 ( cf o rg r a p h i c s ) 是由n v i d i a 公司开发的对g p u 编程的高级语言，它 的语法类似于c 语言，通过自带的c g c 编译器可以将此高级语言编译成g p u 支持 的汇编语言，然后由此汇编语言使用o p e n g l 扩展( 如a r b _ v e r t e x _ p r o g r a m , a r b _ f r a g m e n t _ p r o g r a m ) 和o p e n g l 定义的格式，转为o p e n g l 的命令送到图形硬 件渲染流水线进行处理，参照图2 6 。因此，避免了采用低级汇编语言开发带来 的难度大、效率低以及繁琐的扩展难以理解等问题，让开发者可以更灵活，更高 效的完成对g p u 的编程控制。 2 8 图形处理器中的缓存 图形处理器中通常包含，颜色缓存、累积缓存、深度缓存、模板缓存。通过 o p e n g l ，可以对其进行控制。 颜色缓存相信大家已经非常熟悉了，通常就是用于绘图的缓存。它包含了颜 色索引或r g b 颜色数据，还可能包含a l p h a 值。这里我们就不做过多的说明。 累积缓存与r g b a 模式下的颜色缓存一样，它也存储r g b a 颜色数据。累积缓 山东大学硕士学位论文 存通常用于吧一系列的图像合成为一副图像。由于本文没有使用，所以也不做过 多的说明。下面我们着重介绍一下深度缓存和模板缓存。 2 8 1 深度缓存 深度缓存存储每个像素的深度值。深度通常是根据物体和观察点的距离来测 量的，因此具有较大深度值的像素可能会被具有较小深度缓存值的像素所覆盖。 但是，这只是一种常见的约定，我们可以通过修改深度测试函数来更改深度缓存 的测试方案。由于在o p e n g l 中，我们使用x 表示屏幕上的水平方向位移，y 表 示屏幕上垂直方向的位移，z 表示从观察点到屏幕的垂直方向的距离，所以，深 度缓冲通常又被称为z 缓存。 2 8 2 模板缓存 模板缓存的一个应用就是把绘图限制在屏幕中的某个区域，就像使用纸板和 喷漆创建精确的绘图一样。也就是说，可以用于保持屏幕上某些部位的图像不变， 而只在指定的部位上进行绘制。例如，如果想绘制一幅在形状怪异的汽车挡风玻 璃上出现的图像，汽车内其他部位( 如仪表盘，方向盘等位置) 是不变的，这样 就可以在模板缓存中存储一幅挡风玻璃形状的图像，然后再绘制整个场景。模板 缓存可以防止那些透过挡风玻璃无法看到的物体被绘制出来。因此如果应用程序 是一个模拟驾驶的程序，可以只绘制车内的仪表和其他物体一次，当汽车开动时， 只更新车外的场景即可。 因为本文中的算法主要使用了模板缓存的某些功能，所以这里简单介绍一下 如何利用o p e n g l 控制模板缓存的各种操作。 首先我们需要使用函数g l e n a b l e0 启动模板测试： g l e n a bl e ( g l _ s t e n c i l _ _ t e s t ) ： 然后告诉o p e n g l 在程序中怎样使用模板缓存，这可以通过函数 g l s t e n c i l f u n e0 和g l s t e n c i l o p0 来实现。函数g l s t e n c i l f u n c0 的形式是： v o i dg l s t e n c il f u n c ( g l e n u mf u n c ，g 1i n tr e f ，g l u i n tm a s k ) ： 该函数设置所使用模板缓存的比较函数为f u n c ，参考值为r e f 以及模板掩 1 4 山东大学硕士学位论文 码为m a s k 。参考值使用比较函数与模板缓存中的值进行比较，但比较只在那些 对应的掩码设置为1 的位上