（计算机应用技术专业论文）虚拟环境中碰撞检测算法及并行化研究.pdf

华中科技大学硕士学位论文 摘要 f 虚拟现实技术正在日益成为对世界影响深远的技术，各种基于虚拟现实技术的应用 也方兴未艾。在虚拟现实技术中，研究在虚拟交互环境中检测某一时刻物体之间是否发 生了碰撞的问题称为碰撞检测问题。由于虚拟环境中物体的实时、精确、完全的碰撞检 测对虚拟环境的构建起着至关重要的作用，因此碰撞检测问题是虚拟现实技术的基本和 关键问题之一。当要判断两个物体在当前时刻是否碰撞时，一般需要对组成物体模型的 所有基本几何元素进行两两相交测试，当虚拟环境或是物体模型的复杂度增高时，这种 穷举式的相交测试显然是无法容忍的。因此减少基本几何元素两两相交测试的数目，提 、 高算法速度，以保证虚拟环境的实时交互性是碰撞检测问题的核心。一 为了解决虚拟环境中碰撞检测的实时性问题，我们实现了一种改进的碰撞检测算 法。该算法主要包含了以下三点内容：在上层算法中采用一种基于混合模型的碰撞检测 算法，对包围盒树的每个非叶子结点建立包围盒链表，根据当前情况选择合适的包围盒 进行相交测试；在下层算法中对包围盒树的叶子结点不再使用包围盒算法，而使用时间 复杂度近似于常数的距离跟踪算法，用以减少叶子结点相交测试所耗费的时间；在总体 上利用在虚拟环境中帧与帧之间的关联性，采用保存物体之间最近的已发生的碰撞信息 的方法，对混合模型的碰撞检测算法进行优化。 随着并行技术的发展，复杂计算的问题可以在并行计算环境中实时的完成。这里实 现了上述改进算法的并行算法。通过构建平衡的包围盒树而达到并行程序的负载平衡， 。_ + 4 。1 _ 一 利用分而治之的并行程序设计策略实现了并行算法。在此基础上给出了基于p v m 并行 计算环境的系统实现p a r h y c d 。 关键词：虚拟环境；碰撞检测；层次包围盒：并 南虚拟现实 i 华中科技大学项士学位论文 a b s t r a c t v t r m a lr e a l i t y ( t ) t e c h n o l o g i e sa r eb e c o m i n gam o 陀a n dm o r ei n f l u e n t i a lt e c h n o l o g y o ft h ew o r l d a n da l lk i n d so fa p p l i c a t i o n sb a s e do nv rt e c h n o l o g i e sa l eb o o m i n g i nv r t e c h n o l o g i e s ，t h e r e i sak i n do fs o c a l l e d p r o b l e m s o fc o l l i s i o nd e t e c t i o ni n v i r t u a l e n v i r o n m e n to 电) ，w h i c hi sa b o u th o wt od e t e c tw h e t h e rc o l l i s i o nh a p p e n e db e t w e e no b j e c t s i no n es p e c i f i cm o m e n ti nv i r t u a li n t e r a c t i v ee n v i r o n m e n t r e a lt i m e ，a c c u r a t ea n da d e q u a t e c o l l i s i o nd e t e c t i o nb e t w e e n o b j e c t si nv e i so f t h em o s t i m p o r t a n c eo f t h e c o n s t r u c t i o no f v e ， s oc o l l i s i o nd e t e c t i o ni so n eo ft h eb a s i ca n dk e yi s s u e so f v r t e c h n o l o g i e s w h e nt od e t e c t w h e t h e rt w oo b j e c t si n t e r v e n ei nt h ec u r r e n tm o m e n t ，p a i r w a r ei n t e r v e n t i o nd e t e c t i o ni s n e e d e dt od ob e t w e e na l lb a s i cg e o m e t r i c a le l e m e n t so ft h eo b j e c tm o d e l s a n dw h e nt h e c o m p l i c a c yr i s e s ，t h i s k i n do fa l l o v e ri n t e r v e n t i o nd e t e c t i o n si s o b v i o u s l yi n t o l e r a b l e s o d e c r e a s i n gt h en u m b e r so fp a i r w a r ei n t e r v e n t i o nd e t e c t i o n so fb a s i cg e o m e t r i c a le l e m e n t s ， i m p r o v i n g t h es p e e do f a l g o r i t h m s ，a n ds ot h a ta c h i e v i n g t h er e a l t i m ei n t e r a c t i o no fv ea l e t h ec o r et h i n g so f a l lp r o b l e m so f c o l l i s i o nd e t e c t i o n i no r d e rt os o l v et h er e a l f i m ep r o b l e mo fc o l l i s i o nd e t e c t i o ni nv e ，i m p l e m e n t a t i o no fa k i n do fa l g o r i t h mo nc o l l i s i o nd e t e c t i o ni sp r e s e n t e d t h ea l g o r i t h mm a i n l yc o n t a i nt h r e e i s s u e s ：i nt h eh i g h - l e v e la l g o r i t h mak i n do f h y b r i dm o d e l sa n dt h ea l g o r i t h ma l ea d o p t e d ，i n w h i c hl i n kl i s t so f b o u n d i n gb o x e so f t h en o n - l e a fn o d e si nt h eh i e r a r c h i c a lb o u n d i n gb o x m o d e l sa r ec o n t r u c t e d , a n dd y n a m i c c h o o s i n gt h eo p t i m a lb o u n d i n g b o xi su s e dt od ot e s t si n t h ec u r r e n tm o m e n t ；i nt h el o w - l e v e la l g o r i t h m , f o rt h el e a f n o d eo f t h eb o x t r e et h e a l g o r i t h m b a s e do nd i s t a n c e 慨ew h i c ht h et i m ec o m p l e x i t yi sac o n s t a n ti sa d o p t e d , i n s t e a do f u s i n g b o x t r e ea l g o r i t h m ；a n do nt h ew h o l et h ec o r r e l a t i o nb e t w e e nf l a n l ea n df l a l l ew h i c h o c c u r r e dc o l l i s i o n si nv ei su s e dt ob u f f e rt h eh a v i n go c c u r r e dc o l l i s i o n s ，s ot h a tt h en e x t c o l l i s i o nd e t e c t i o nc a nu s et h ei n f o r m a t i o no ft h el a s td e t e c t e dc o l l i s i o n , a n dt h i sm e t h o dc a n b eu s e dt oo p t i m i z et h ea l g o r i t h m s a st h et e c h n o l o g i e so fp a r a l l e l i s mm a k ep r o g r e s s ，t h e c o m p u t a t i o nw h i c ha r ev e r y 华中科技大学硕士学位论文 c o m p l e x c a nb er e a l t i m ed o n ei nap a r a l l e l c o m p u t i n ge n v i r o n m e n t a c c o r d i n g t ot h e i m p r o v e m e n to ft h ea b o v ea l g o r i t h mo f c o l l i s i o nd e t e c t i o n , ak i n do fp r a r l l e la l g o r i t h mi s p r e s e n t e di nt h i s t h e s i s i nt h i sa l g o r i t h m ，c o n s t r u c t i n gab a l a n c a b l eh r e r a r c h i c a lb o u n d i n g b o x e si su s e dt oa c h i e v et h el o a db a l a n c eo f p a r a l l e lp r o g r a m sa n dt h ef a t h e rp r o c e d u r ea n d t h es o np r o c e d u r ea l g o r i t h ma r ei m p l e m e n t e du s i n gd i v i d i n ga n dc o n q u e r i n gp r o g r a m m i n g p o f i c yo fp a r a l l e l i s m a n dt h e nt h ei m p l e m e n t a t i o no f t h es y s t e mb a s e do np v m p a r a l l e l e n v i r o n m e n t , p a r h y c d ，i sp r e s e n t e d k e y w o r d s ：v i r t u a le n v i r o n m e n t ，c o l l i s i o nd e t e c t i o n ，h i e r a r c h i c a l b o u n d i n gb o x ，p a l l e l i s m ， v i r t u a lr e a l i t y t 丌 华中科技大学硕士学位论文 1 绪论 1 1 课题背景 虚拟现实( x r t r t u a lr e a l i t y ，简称为v r ) 是一种可以让用户主动或被动的创建和体 验虚拟世界的计算机系统，虚拟世界是包含全体虚拟环境或给定的全体仿真对象的集 合。虚拟环境是由计算机生成的，通过视、听、触觉等作用于用户、使之产生身临其境 的感觉的交互式视景仿真。因而，为了研究如何设计和构成一个身临其境的虚拟现实系 统，需要包括计算机图形学、图象处理与模式识别、智能接口技术、人工智能技术、多 传感器技术、语音处理与音响技术、网络技术、并行处理技术和高性能计算机系统等等 技术的综合发展“1 。 虚拟现实系统的基本特征为3 i ，即i m m e r s i o n - - i n t e r a c t i o n - - i m a g i n a t i o n ( 沉浸一交 互一构想) 。要实现3 i 的性能，特别是m m e r s i o n ，虚拟现实系统必须让用户获得与真 实物理世界中相同或是相似的感受，让用户有身临其境的感觉，这就要求虚拟环境有足 够的逼真性，其中尤为重要的是物体运动的逼真性即物体需要具有逼真的状态变化，例 如，物体位置、方向和形状等状态变化规律与真实世界中的相同或相似。在物体运动真 实性问题的研究中有一个很重要的问题，即物体之间的碰撞问题。 随着计算机图形学、虚拟现实技术和计算机硬件技术的发展，用高质量的计算机虚 拟环境来对现实世界进行模拟与再创造已成为可能，很多专家和学者都研究了上文提到 的在虚拟环境演示与模拟中的一个很重要的问题物体之间的干涉和碰撞，并在理论 和实际方面提出了许多有重要价值的研究结果。图形移动时的碰撞检测问题在计算机图 形学、c a d c a m 、动态系统模拟、机器人学以及实时干涉布局等同题中都有着广泛的 应用。碰撞问题的具体应用很广泛，例如，虚拟环境应用中的飞行员和宇航员的培养与 调练、机器人的路径规划和学习、交互式动画系统，服装c a d 中衣物与人体躯干的配 合等。 但是在三维空间碰撞检测中，涉及到复杂场景或复杂物体的碰撞检测问题( 例如大 规模作战演练系统中的碰撞检测问题，其涉及的场景就很复杂) ，或者是要求非常精确的 碰撞检测( 例如制造业中机器臂拾取物体的问题，就要求碰撞检测年常精确) ，都会使系 华中科技大学硕士学位论文 统的运行速度变得很慢，不能满足虚拟环境的实时性的要求。究其原因，是因为目前的 计算机硬件的发展还未能满足虚拟现实技术或者是虚拟环境的要求，特别是实时性的要 求，而在虚拟现实技术中系统的实时性是很重要的一个方面，若是虚拟现实系统不能满 足实时性的要求，就不能实现虚拟现实系统的沉浸感，无法满足用户的需求。解决这个 问题可以从两方面来考虑：一方面，可以研究快速的碰撞检测算法，提高检测算法的效 率；另一方面，可以将已有的算法并行化，从并行的角度来提高系统的响应速度。目前， 已经研究出来了一些快速的碰撞检测算法，但是单从提高算法的效率的角度仍然不能满 足系统的实时性需要。因此，将碰撞检测算法并行化，以提高其实时性，就具有重要的 意义。本课题就在于研究快速的物体的三维碰撞检测算法，并将其在并行机的环境下实 现。 1 2 国内外研究概况 碰撞检测问题是虚拟现实技术中的基本问题之一，它对虚拟环境的构建及表示起着 至关重要的作用，因为它是否被成功解决决定了虚拟环境是否具有足够的逼真性，而虚 拟环境的逼真性又是虚拟现实系统的基本特征之一。目前已有许多学者研究了这个问 题，但是用现有的算法解决碰撞检测的实时性问题却始终不能令人满意，在这方面还有 许多工作值得去做。 1 2 1 国内外类似系统的研究概况 1 ) i - c o l l i d e i - c o l l i 舻是北卡罗来那大学( u n i v e r s i t y o f n o r t hc a r o l i n a ) 研制开发的碰撞检测系 统，它适合于大规模复杂场景的碰撞检测。它的高层采用一个扫描修剪算法来确定需要 进行检测的物体对，其底层进一步采用l i n - c a n n y 算法来检测两个物体间的碰撞情况。 该系统的关键之处在于如何降低扫描修剪过程的时间复杂度：若一个大规模场景中有n 个运动物体和m 个静止物体，则常规算法中要对n 2 + m n 个物体对进行检测，时间复 杂度为0 ( n 2 + m n ) 。i - c o l l i d e 采用在三维空间中对包围每个物体的包围盒进行排序的 方法，以确定哪些包围盒重叠，只要对这些已判定出的包围盒重叠的物体调用底层算法 进行进一步的精确检测即可。 华中科技大学硕士学位论文 在三维空间中要对物体的包围盒进行排序仍然是一件非常耗时的工作，i - c o l l i d e 采 用降低维度的方法：如果两个物体在三维空间中相交，当且仅当它们在x y ，y z 和及平 面上的垂直投影必定重叠。因此，i - c o l l i d e 采用轴向包围盒a a b b ( a x i s - a l i g n e db o u n d i n g b o x ) 来作为物体的包围盒，通过其在低维空间的投影进行排序。排序后，全局活动多 面体对表中就保存了当前时刻的满足包围盒重叠条件的所有多面体对，然后，系统将此 表中的元素逐一提交给底层算法处理，用以检测两个物体间的碰撞情况。 - c o l l i d e 的底 层算法采用l i n c a n n y 算法，在这两个物体上随机找一对特征对作为候选特征对，从这 个候选特征对开始，通过算法搜索找到最近特征对；若两物体不是初次参与底层检测， 则利用上一次找到的最近特征对作为候选特征对，继续进行搜索。 总体上说，i - c o l l i d e 是一个用于精确检测包含多个凸多面体的环境中的碰撞情况的 算法库，但它的输入模型要求是凸多面体，因为它是利用物体的这一特性来加速的，因 此在物体中包含凹多面体的情况下它将不能正常工作。 2 ) v - c o u i d e + v - c o l l i d e l 3 1 也是由北卡罗来那大学( u n i v e r s i t y o f n o r t hc a r o l i n a ) 研制开发的碰撞检 澜算法库，它可用于大的动态环境的碰撞检测。它的输入模型为“多边形汤”( 即无拓 扑信息的多边形的集合，其中不包括任何连接信息和拓扑约束，这样的模型被称为“多 边形汤”。这些模型的边界可能是缺口，t 连接点，或者简单几何体，目前没有种已 知的健壮算法能够化简这样的模型) 。v - c o l l i d e 的高层处理算法仍然采用i - c o l l i d e 的处 理多个物体碰撞的包围盒排序法，其底层算法则采用r a p i d 中采用的比较适合于检测 两个距离非常接近的物体间的碰撞情况的算法。 v - c o l l i d e 比较适合于检测包含大量静止或动态物体的场景，因为其底层的高效算 法，它能够快速的检测出场景中物体的碰撞情况，而且它还允许动态的增删物体，即在 检铡的过程中若有新的物体加入场景中或者物体从场景中删除时，只需将该物体加入待 检测的活动表中或是将其在活动表中删除即可。v - c o l l i d e 的这特性非常有用，因为在 实际应用中我们有可能碰到需要在动态场景中快速的检测物体的碰撞的情况，例如在虚 拟装配中，机械手拾取物体装配到系统中，在这种情况下就需要在场景中动态的加入此 物体并进行碰撞检测。 3 ) h - c o l l i d e 3 华中科技大学硕士学位论文 h - c o , l l i d e 是一个支持在虚拟环境中用于触觉交互的碰撞检测算法的软件包。它综合 利用了包围盒，空间划分法等多种技术，并提出对线段和包围盒之间的快速求交算法。 据称，它比s e n s a b l c 公司提供的g h o s t 软件库的碰撞检测算法速度提高了2 2 0 倍。 触觉交互碰撞检测中要解决的问题是：给定触觉交互设备的上一帧位置和当前的位 置，要判断该设备在两帧间是否经过了场景中的物体。若确定有交集，则可根据与物体 的交点进一步计算反馈力。相对于触觉反馈的频率来说，触觉交互设备的移动很小，这 意味着只需要检查一个相对小的空间区域即可。在这种情况下，若采用空间划分法，对 于非常复杂的场景，此方法的空间耗费非常大。而另一方面，若采用o b b t r e e 层次包 围盒法，对于非常复杂的场景，会导致树的层次非常深，需要耗费大量的时间来从根节 点遍历到叶子节点。因此，h - c o l l i d e 采用一种混合技术：给定一个非常复杂的场景，例 如有数万个多边形面片的场景，预先为该场景计算一个混合层次表示，首先，将整个场 景划分为租粒度的均匀网格。然后，对于每个包含了多边形面片的网格单元分别计算一 个o b b t r e e ，并将指向这些o b b t r e e 的指针用一个哈希表存储起来。 以上的混合层次表示是预先计算好的，而每一步的碰撞检测分三步进行：第一步， 用预先计算的哈希表检查触觉交互设备所经过的路径与哪些网格单元有关；第二步，遍 历有交集的网格单元的o b b t r e 七，确定设备所经过的路径是否与其中的多边形面片相 交；第三步。若有交集，则计算出触觉交互设备与物体的表面接触点。 综合来说，h c o l l i d e 适用于一个物体( 如触觉交互设备) 在场景中漫游的应用，由 于其快速的碰撞检测算法，它能够适应虚拟环境中用于触觉交互的碰撞检测。 4 ) v - c l i p v l i p 嗍是一个跟踪计算两个多面体间距离的算法库。它对i a n - c a n n y 算法做了改 进，除了可以处理一对凸多面体，还可以处理一对表示成凸多面体层次的非凸多面体。 另外，它除了可以计算出两物体间的距离外，还可以报告两物体的穿透位置，以及发生 穿透的物体对问的近似距离。 v - c l i p 的输入物体模型可以是多面体或是4 多边形汤”，它适于处理不太复杂的场 景的碰撞检测，它还可以处理可变形物体的碰撞检测。 5 ) q t 五c k d q 试d ( c d p l 是一个用于检测两个物体间的碰撞情况的算法库，其中的一个物体是指 华中科技大学硕士学位论文 场景中的静止部分，另一个物体指在场景中飞行的一个物体。它采用k - d o p 层次包围盒 算法，其输入物体模型是“多边形汤”，适于处理一个物体在一个大的虚拟环境中飞行 的情况，如场景漫游系统。 1 2 2 主要关键技术的研究概况 对虚拟环境中的碰撞检测算法及其并行化的研究主要包括以下几方面的技术： 1 ) 基本几何元素之间的碰撞检测 2 ) 复杂物体模型之间的碰撞检测及优化技术 3 ) 物体的碰撞规避技术 4 ) 碰撞检测的并行化技术 这些关键技术是碰撞检测算法及其并行化的研究的重点和难点，下面我们逐一介绍 这几方面的关键技术。 1 1 基本几何元素之间的碰撞检测 基本几何元素( 一般为凸多面体) 之间的碰撞检测是碰撞检测中最基本的问题，因 为无论物体模型和场景模型有多么复杂，最终还是会涉及到基本几何元素的碰撞，这些 复杂模型要做的也就是想办法降低模型的复杂度，因此降低基本几何元素的碰撞检测算 法的复杂度，也就成了碰撞检测问题中最基本的一类问题。 由于凸多面体的简单性，可以采用很多技巧性的方法来降低算法的复杂度。目前主 要有下列方法：采用空间占有的方法【6 ，即物体在目标空间移动，当试图占有相同的 球体时来检测它们的碰撞。利用这种方法可以研究两个多边形的相交和最小距离问趔引。 利用凸多面体上点集的关系的方法。如利用最大最小坐标的顶点子集的方法【9 】可研究 一个凸多边形沿一给定方向移动时是否与另一凸多边形发生碰撞，并且利用斜支撑线的 方法来研究一个凸多边形相对于另一个凸多边形的可移动区域问题。再如对于平面内两 个互不相交的凸多边形p 和q ，若p 沿给定方向d 移动时将与q 相碰撞，可以采用 折半搜索技术来确定p 与q 相碰撞时两者的最初相碰撞的顶点和边【1 0 】。再如可以利用 凸多边形顶点集上的偏序关系，可以采用四分搜索方法构造判定凸多边形p 沿直线以平 移方式运动时是否与q 相撞【n 】，也可起到加速算法的作用。由于基本几何元素一般 为凸多面体，也可利用多面体的凸性来加速算法。而且对于凹多面体，也可以用这种方 5 华中科技大学硕士学位论文 法来解决，因为可以将凹多边形分解为凸多边形的方法来求解碰撞问趔1 2 l ，其实质还是 凸多边形的碰撞问题。 2 ) 复杂物体模型之间的碰撞检测及优化技术 在有关虚拟现实的应用中，复杂物体模型之间的碰撞检测的实时性成为最突出的问 题之一。由于虚拟环境中物体模型及场景模型的复杂性，若不采用降低模型及算法复杂 度的方法，则精确、实时、完全的碰撞检测根本不可能实现。这促使人们想办法对复杂 物体模型之间的碰撞检测算法作出各种各样的改进及优化。 目前主要有两方面的途径可以对复杂物体模型之间的碰撞检测进行优化。利用物 体模型的特殊性。如在多面体之间的基于在给定轨迹上反复利用静态干涉检测被称为 “单步检测”的方法，采用递归空间分割算法和面对面相交算法 b j 4 。再如利用构造实 体几何模型( c s g ) d s , 1 6 , 1 7 1 、边界表示模式( b - r 印) 1 8 , 1 9 1 和八叉树表示法【2 0 1 ，其中八叉树 表示因对空问的均匀剖分而显得灵活度不够，而且八叉树的建构亦相当费时，但相对来 说八叉树仍可算是较好的算法。采用层次包围盒技术。其基本思想是用一个体积略大 而形状简单的包围盒代替复杂的几何对象，当需要对两物体作碰撞检测时，首先检测两 物体的包围盒相不相交，若不相交，则两物体不可能相交，否则进一步缩小包围盒进行 更精细的判断阱0 3 矧。这种方法通过预处理过程( 建立包围盒、包围球等) 来加速碰 撞检测过程【2 5 】。 3 ) 物体的碰撞规避技术 碰撞规避也是碰撞检测问题中较重要的一类问题。碰撞规避问题即是多个物体的无 碰撞运动。它可以分为两类：连续运动或动态路径规划技术和静态碰撞检测技术。 在动态路径规划技术中有以下方法：四维相交测试方法闭。这种方法将时间也作为 物体的一维。最初的3 d 物体被时间维来延伸，因而产生新的4 d 物体。假如没有检测 到碰撞，物体的路径是无碰撞的。这种方法的主要局限性是根据它所能考虑的物体的形 状和运动的复杂程度来决定的。简单形状和线性运动在这种场景下运行很好，但是比较 复杂的物体或路径就不能很好地处理。 在静态碰撞检测技术中有以下方法：利用范围树来近似物体的方法鲫。在这种方 法中，物体用范围树来近似，范围树基于它们之间的碰撞检测算法和实行相交测试的有 效c p u 时间来逐渐精化，这样可以保证交互性。八叉树方法圆。这种方法对场景中 6 华中科技大学项士学位论文 的物体自动地产生排斥力八叉树向量场，移动的物体都受到它们邻近区域的向量场的影 响。当两个移动的物体彼此接近时，它们的排斥力向量场将互相作用而使它们彼此分开a 静态碰撞检测算法的优越性在于它们不需要预先知道物体的位置和速度，并且多个运动 的物体也能够用一种自然的方式来处理。静态检测算法的主要弱点是由于它们的不连续 性，碰撞可能被遗漏。这种情况可使当一个或两个碰撞的物体从一个时间步到下一个时 间步中，从一种不相交状态完全彼此穿透到另一种不相交状态时移动的距离足够大【2 9 】。 碰撞检测的并行化技术 网络技术和高级并行机的高速发展，给研究者带来了前所未有的机遇和挑战。但是 由于将虚拟现实的关键技术在并行机的环境中来实现还是一个较新的课题，所以国内外 关于这方面的研究还不多。由于并行计算环境的多样性，针对不同的并行环境，有不同 的碰撞检测的并行化技术。 现在主要有下列算法：面向对象的分布式碰撞检测算法【3 0 1 ，主要应用于分布式虚 拟环境中，并讨论了在分布式环境中碰撞检测的完全性和唯一性的问题。由于以往由单 机承受的繁重计算任务可通过分布式环境中多台计算机来共同完成，故算法具有较高的 效率。自适应空间剖分并行方法f 3 l 】。该算法面向动态复杂场景采用层次的自适应空间 剖分方法建构物体的平衡包围盒树，然后通过并行遍历包围盒树来加速碰撞检测。 1 3 本课题主要研究工作 本课题研究的是虚拟环境中的快速的碰撞检测算法，并以机群为基础，实现合适的 碰撞检测算法并行化实现。主要的研究工作分为以下两个方面： 1 研究现有的基于虚拟现实环境的三维碰撞检测算法，实现了h y c d 碰撞检测算 法算法，在计算速度上有了改善。算法主要包含了以下三点内容： ( 1 ) 在上层算法中采用种基于混合模型的碰撞检测算法，在预处理阶段即针对 包围盒树的非叶子结点建立包围盒链表( 包含几种包围盒的循环链表) ，在碰撞检测时 通过检测包围盒链表的优先权域来自适应和动态的选择当前情况下最佳的包围盒进行 碰撞测试，当物体的状态以及相对于其它包围盒的关系发生变化对，贝更新其优先权域 的值： ( 2 ) 在下层算法中对包围盒树的叶子结点不再使用包围盒算法，而使用时间复杂 华中科技大学硕士学位论文 度近似于常数的距离跟踪算法，用以减少叶子结点相交测试所耗费的时间； ( 3 ) 在总体算法上利用虚拟环境中发生碰撞的帧与帧之间的关联性，保存最近已 发生的碰撞，以便下一次的碰撞检测可以利用已检测的上一次碰撞的信息，加快碰撞检 测的速度，同时利用预测试方法扩展了这种算法，对混合模型碰撞检测算法进行优化。 2 根据实现的h y c d 碰撞检测算法实现了h y c d 算法的并行算法。通过构建平衡 的包围盒树而达到并行程序的负载平衡，利用分而治之的并行程序设计策略实现了父进 程及子进程算法。然后给出了基于p v m 并行计算环境的系统实现p a r h y c d 。 本文的章节安排如下： 第一章为绪论，介绍了课题的背景、国内外研究发展概况及主要研究内容； 第二章对基本的碰撞检测算法及其实现进行了详述； 第三章是本文的重点，主要论述h y c d 碰撞检测算法； 第四章介绍了h y c d 算法的并行化实现； 第五章介绍p a r h y c d 系统的实现和性能评测； 第六章为本文的总结和展望。 8 华中科技大学硕士学位论文 2 碰撞检测算法 2 1 引言 在现实生活中，碰撞是一种自然而且常见的现象，我们能够根据发生碰撞后物体的 动作和物体状态的改变察觉到发生了碰撞。但是在虚拟环境中，这种物体的碰撞响应不 是自然存在的，这就需要支撑虚拟环境运行的系统主动的检测是否有碰撞发生以及碰撞 响应。例如，当用户去拿虚拟环境中的杯子时，虚拟环境必须首先检测到有碰撞发生， 才能进一步的虚拟杯子的动作【3 2 1 。这里面包含了两方面的问题，一是需要检测到碰撞是 否发生以及发生碰撞的位置，即碰撞检测问题：二是发生了碰撞的物体的反应以及下一 步的动作，即碰撞响应问题。碰撞响应问题一般与具体的应用环境有关，而碰撞检测问 题作为碰撞响应的先决条件，具有广泛的研究前景。 实时、精确、完全的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感有 着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求。 在有关虚拟现实的应用中，碰撞检测的实时性成为最突出的问题之一。本节主要对碰撞 检测的基本概念和方法作出简要介绍。 2 1 1 一般方法 现实生活中，一个物体要占据一定的几何空间，不可能发生同一个几何空间被两个 物体占据的情况。同理，在虚拟环境中当两个物体试图占据同一几何空间时，虚拟环境 应认为此时发生了碰撞，这就是碰撞检测的一般方法。用形式化的语言描述如下： 设a 集合为a 物体所包含的所有点集，b 集合为b 物体所包含的所有点集，若某 一时刻a n b 由，则判定物体a 与物体b 发生碰撞( 巾表示空集) 。 碰撞检测系统的输入模型是构成几何对象的基本几何元素的集合，目前大多数系统 采用的都是多面体模型，其最小的集合元素通常是三角形，该模型使用基本的三角形面 片来构造几何对象。具体到采用多面体模型时，碰撞检测的一般方法可描述如下： 对两个任意形状的多面体a 和b ，a 和b 发生碰撞当且仅当下述三个条件至少成立 其一：1 多面体a 中至少存在一条边与多面体b 中的某一个面相交；2 多面体b 中 9 华中科技大学项士学位论文 至少存在一条边与多面体a 中的某一个面相交；3 多面体a 包含多面体b 或多面体b 包含多面体a 。 碰撞检测的任务一般有两个：一是确定在当前时刻是否发生了碰撞，二是当碰撞发 生时找到发生碰撞的位置。对于一般的应用，完成以上两个任务就已经足够了，对于特 殊的应用环境，如机器人虚拟装配的应用中，还需检测出物体间的距离和检测出下一次 碰撞将在何时何处发生，以便系统作出动作来避免碰撞发生，即碰撞规避问题。 最原始最简单的碰撞检测算法就是对两个输入模型中的所有基本几何元素进行两 两相交测试，当模型的复杂度增高时，这种0 ( n 2 ) 次的相交测试显然是无法容忍的。因 此减少基本几何元素两两相交测试的数目，提高算法速度，以保证虚拟环境的实时交互 性是碰撞检测问题的核心。 以上所述的情况均为虚拟环境中的两个物体的碰撞检测问题，当虚拟环境中的物体 数多于两个时，则需要对其中的运动物体两两之间进行检测。若一个虚拟环境中有n 个 运动物体和m 个静止物体，则常规算法中要对n 2 + m n 个物体对进行检测，时间复杂 度为d ( n 2 + m n ) ，这样高昂的检测代价是现在的虚拟现实系统无法承受的，必须想办 法降低时间复杂度。可以从两方面着手解决，一是想办法减少需要进行检测的物体对数， 去掉一些明显不可能发生碰撞的物体对，避免对所有的物体对进行碰撞测试。二是改进 两物体的碰撞检测算法，加速两物体的求交运算。 2 1 2 碰撞检测的要求 虚拟环境对于碰撞检测的要求有如下三点：实时性，精确性和完全性。 由于虚拟环境是一种能与人实时交互的计算机生成环境，故虚拟环境中的碰撞检测 必须能实时完成。针对虚拟环境的视觉显示要求而言，碰撞检测的速度至少要达到2 4 h z ， 才能满足实时性的要求。对于两个物体的碰撞检测算法来说，最原始最简单的算法是对 两个输入模型中的所有基本几何元素进行两两相交测试，然而这种算法的时间复杂度为 d ( n 2 ) ，当模型的复杂度很大时，这种大规模的相交测试次数显然是无法容忍的，无法 达到实时性的要求。因此为了保证虚拟环境的实时交互性，必须减少基本几何元素两两 相交测试的数目，提高算法的速度 显而易见，精确的磋撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感有着 1 0 华中科技大学硕士学位论文 至关重要的作用。不过精确性是相对的，它取决于具体的应用环境。例如，在虚拟漫游 环境应用中，碰撞检测的精确性就不需要太高，只要两个物体距离比较近，在某一阈值 内，就可以近似的认为两物体发生了碰撞，而碰撞发生的位置的计算也可以交粗略：而 在虚拟制造和装配应用中，就需要精确的检测碰撞发生与否以及精确计算碰撞发生的位 置 完全性也是碰撞检测的一个重要的性质。完全性可以分为第一类完全性和第二类完 全性。具有第一类完全性的碰撞检测方法可以检测出虚拟环境中的所有碰撞，不遗漏任 何碰撞。而具有第二类完全性的碰撞检测方法可以检测出某一时刻虚拟环境中的需要处 理的所有碰撞。追求碰撞检测方法的完全性、减少碰撞遗漏是碰撞检测的重要目标。 以下介绍几种有效的检测物体间的碰撞情况的算法。 2 2 层次包围盒法 碰撞检测及其相关问题有较长的研究历史，特别是刚体间碰撞检测的研究，已形成 了一些比较成熟的技术。如层次包围盒方法，其基本思想是用一个体积略大而形状简单 的包围盒代替复杂的几何对象，当需要对两物体作碰撞检测时，首先检测两物体的包围 盒相不相交，若不相交，则两物体不可能相交，否则进一步缩小包围盒进行更精细的判 断。层次包围盒法的核心就在于对包围盒的求交算法比对物体的求交算法简单的多，从 而通过包围盒问的相交测试快速地排除不相交的基本几何元素对，以减少相交测试的次 数，从而达到了加速算法的目的。 层次包围盒算法的步骤如下： 1 首先建立两个待测物体a 和b 的层次包围盒结构，通常情况下，它们都是二叉 树，也可称之为包围盒树，树的根结点为整个对象的包围盒，而每个子结点上的包围盒 都对应于组成该对象的基本几何元素集合的一个子集，二叉树的叶子节点是组成该虚拟 物体的最基本的几何元素，若是其精度足够高，每个叶子节点都代表一个三角形。 2 有效的遍历这两棵树，以确定在当前位置下，对象a 的某些部分是否与对象b 的某些部分发生碰撞。这要分为以下步骤：( 1 ) 用对象b 的根结点去遍历对象a 的这 棵树。( 2 ) 如果能到达a 的叶子节点，再用这个叶子节点去遍历对象b 的包围盒二叉 树( 3 ) 如果能到达对象b 的叶子结点，则进一步进行基本几何元素的相交测试。 华中科技大学硕士学位论文 3 以上情况都是各个对象的包围盒树有相交的情况发生时要做的事，若是两个结 点上的包围盒树不相交，则它们所包围的对象的基本几何元素的子集不相交，从而不需 要对子集中的元素作进一步的相交测试，直接跳出算法。这样就体现了层次包围盒算法 的优势，可以有效的减少相交测试的次数。 2 2 1 包围盒的评价标准 包围盒的特点是比物体略大而能包围住物体，同时其相交情况的测试相对于物体的 相交测试来说比较简单，根据这个特点比较常见的包围盒有沿坐标轴的包围盒 a a b b ( a x i s a l i g n e d b o u n d i n g b o x e s ) 、包围球( s p h e r e s ) 、方向包围盒o b b ( o r i e n t e d b o u n d i n g b o x e s ) 、固定方向凸包的包围盒f d h ( f i x e dd i r e c t i o nc o n v e xh u l l ) 等。就刚体的碰撞检测 而言，平均性能最好的是基于o b b 的碰撞检测算法，曾一度作为评价碰撞检测算法的 标准。 选择何种包围盒需要根据不同的需要和具体的情况来定。假设已知两个物体的模型 以及它们的层次表示，碰撞检测的总的价值函数如下： t = n v c v + n p x c p ( 2 1 ) 各字母含义如下： t ：碰撞检测总价值函数 n v ：需进行相交测试的包围体对的数量 c v ：进行相交测试的包围体对的价值量 n d ：进行碰撞检测的基本几何体对的数量 c d ：进行碰撞检测的基本几何体对的价值量 根据以上的价值函数，各种层次数据结构的特征描述如下： 选择包围盒的类型：选择包围盒基于两个互相矛盾的约束条件： 1 包围盒应能够尽可能的紧密包围原始模型( 减少n v z g l n p 的值) 2 测试i 露i # - 这样的包围盒的相交情况应尽可能的快( 减少c v 的值) 象包围球和坐标轴向包围盒丸蝠b 在第二个约束条件下做的很好，但是它们不能紧 密的包围倾斜的长瘦形的多面体。相反，最小椭圆体和o b b 能紧密的包围原始模型，但 它们之间的相交测试相对比较耗时因此必须在这两个互相矛盾的约束条件之间取一折 1 2 华中科技大学硕士学位论文 衷。 层次分解( 构造包围盒树) ：给定一个大模型，它的包围盒树可以自底向上构建也 可以自顶向下构建。现在已有很多的技术来将一个包围盒分解或分割成两个或更多的子 包围体，较常用的是自项向下的分解策略，从整个物体的包围盒开始，采用某种策略递 归的划分节点，直至到达叶节点。对于不同的物体表示模型来说，层次包围盒的叶结点 可能对应于不同的几何实体，对于常用的多面体模型，叶节点可髓对应于少量三角形的 集合或是凸多面体；而对于其它的模型表示法，叶节点则对应于另外的几何元素。具体 分解到何种程度取决于系统的精度。基于不同的分解准则，包围盒树的一些性质也会不 同，例如树的度数和高度。显然分解的结果能够影响式( 2 1 ) 中的n v 和n p 的值。 很明显没有一种层次包围盒法能在所有情况下都有最好的性能。而且，已知两个大 模型，它们进行碰撞检测的价值量随着模型之间的相对位置的不同相差很大。特别的， 当两个模型相距很远时，基于包围球和a a b b 的层次表示法性能表现的很好。然而，当 两个模型距离很近时，需进行包围体的碰撞检测的次数n 哙增加，有时这种情况也会导 致原始体的相交测试的次数n p 的增加。对于个给定的模型，o b b 树的n v 和n p 比用包 围球和a a b b 的n v 和n p 要小。同时，已知的最好的检测两个o b b 的相交状态的算法比测 试两个包围球或a 柚b 相交状态的算法要快两个数量级。若给定的模型相当复杂，基于 o b b 树的碰撞检测算法则比使用包围球和a a b b i 对的算法快得多。 2 2 2a a b b 层次包围盒法 坐标轴向的包围盒a a b b ( a x i s - a l g n e db o u n d i n gb o x e s ) 相对来说较简单的一种包围 盒嘲。一个物体的a a b b 定义为包含该物体，且边平行于坐标轴的最小六面体。因此， 描述一个a a b b 仅需六个标量。在构造a a b b 包围盒时，需沿着碰撞体局部坐标系统的 轴向，y ，刁来构造，所以所有的a a b b 包围盒具有一致的方向。a a b b 树是基于 a a b b 的二叉树，按照由上至下的递归细分方式构造生成的。在每一次递归过程中，要 求取最小的a a b b ，需沿所选择的剖分面将碰撞体分为正负两半，并将所对应的原始几 何元素( 如三角i r a ) 分别归属正、负两边，整个递归过程类似于空间二叉剖分，只是每次 剖分的对象是a a b b ，面不是空间区域。递归细分一直要进行到每一个叶子节点只包含 一个原始几何元素为止，因此具有n 个原始几何元素的a a b b 树具有n - 1 个非叶子节点 华中科技大学硕士学位论文 和n 个叶子节点。 a a b b 之间的相交测试比较简单，两个a a b b 相交当且仅当它们在三个坐标轴上 的投影区间均相交。通过投影，即可将三