（计算机应用技术专业论文）三维网格模型的快速碰撞检测及相交体计算.pdf

浙江大学硕士学位论文 摘受 摘要 随着三维网格模型技术的快速发展以及三维模型在计算机图形学、动画多媒 体、虚拟动态模拟、c a d c a m 、机械以及空间布局等领域中的广泛应用，碰撞检 测逐渐成为获取三维模型物理特征的主要方法之一，碰撞检测在逆向工程、动画、 工程领域的应用也越来越广泛。从网格特征提取的角度看，碰撞检测是三维模型 特征提取中最初的、最基本的测试过程。然而网格特征应用多样化后所带来的各 种特征提取要求，给三维网格模型碰撞计算和及特征提取都带来了问题。 本文从网格模型特征提取的角度进行了研究，提出了几种比较有用的特征提 取方法。同时在网格特征提取的基础上，又进步提出了网格特征构造的方法， 从而实现了网格模型碰撞时，既能进行特征提取，又能进行特征构造。这样在实 际应用中，我们不仅可以通过网格特征得到阕格彼此物理特性，或者继而进行相 应的碰撞响应；而且可以在适当的时候构造一些需要的网格特征或网格模型。 本文通过层次树包围盒进行网格模型试探碰撞检测，然后再通过空间三角形 位置特征计算判断网格体彼此的接触情况。根据层次树包围盒检测的思想，网格 模型首先被o b b 包围盒包住，然后逐层以间隔重叠测试方法进行判断，得到相交 的包同盒：接下来对相交包围盒中的三角形进行彼此位置关系计算，产生可交三 角形对和相应的三角形交线。为了解决复杂的三维网格模型碰撞过程中出现的计 算问题，运用了一些优化过程 网格模型碰撞后的网格体重构，基于网格模型的特征提取。针对网格模型特 征提取的特点，利用三角形对的序列关系和位置关系，实现了从三角形交线到网 格相交线或相交环的构造。根据层次树包围盒的碰撞检测思想，重新提出一种可 以测试相交和测试包含的包围盒包含判断算法，继而实时地判断出那些三角形处 于被其他网格体包含的情况；这样结合最初特征提取出来的网格体相交三角形， 可以实现网格轮廓体的重建。 在网格体特征提取和特征重构的基础上，实现了网格特征的其它一些应用， 如网格特征检索，网格特征轮廓体体积估箅等。 关键词：0 b b n 次, n ， 分离轴，轮廓环，a a b b g 嗣盒，特征构造 浙江大学硕士学位论文摘要 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm e s hm o d e l s t h e i ra p p li c a t i o ni n c o m p u t e rg r a p h i c s 、a n i m a t i o ng u l t j m e d i a 、v i r t u a ld y n a m i cs i m u l a t i o n 、 c a d c a m 、m e c h a n i s ma n ds p a t i a ll a y o u t ，c o l l i s i o nd e t e c t i o ni sr e c e i v i n g m o r ea n dm o r ea t t e n t i o na n dg r a d u a l l yb e c o m i n go n eo ft h em a i n3 dm o d e l c h a r a c t e r se x t r a c t i o n i ti sn o ww i d e l yu s e di nr e v e r s ee n g i n e e r i n g ， a n i m a t i o d ，a n dm e c b a n i cm a n u f a c t u r ef i e l d s a m o n gt h em e s h c h a r a c i e r d i s t i i i i n gm e t h o d s ，c o l l i s i o nd e t e c t i o n i sab a s i ca n di n i t i a lo n e h o w e v e r ，ad i v e r s i f i c a t i o no fm e s hc h a r a c t e ra p p l i c a t i o nu s u a l l yc a u s e s k i n d so fc h a r a c t e re x t r a c t i o n ，w h i l et h i sp r o d u c ea1 0 to fp r o b l e m sf o r c o l l i s i o nc o m p u t ea n dc h a r a c t e re x t r a c t i o n i nm e s ho b j e c t s f r o mt h ep o i n to fc h a r a c t e re x t r a c t i o no f3 dm e s h ，t h i sp a p e rp r e s e n t s s e v e r a lu s e f u ld is t i l l i n gm e t h o d s m e a n w h i l ew ef u r t h e rp u tu pm e s h c o n s t r u c t i o nw a yo nt h eb a s eo ft h ec h a r a c t e re x t r a c t e db e f o r e ，s oa s t o a c h i e v cr e s u i t so nb o t hc h a r a c t e re x t r a c t i o na n dm e s hc o n s t r u c t i o n ， i n r e a la p p l i c a t i o n ，w en o to n l yg e tt h ep h y s i c a li d i o s y n c r a s yt h r o u g hm e s h c h a r a c t e ro ri m p l e m e n tc o r r e s p o n d i n gc e l l i s i o nr e s p o n s e ，b u ta l s oo nt h e r i g h tti m ec a nc o n s t r u c tn e e d e dm e s hc h a r a c t e ro r m e s hm o d e l s t h et h e s i st e s t sah i e r a r c h i c a lr e p r e s e n t a t i o no f m o d e l su s i n g t i g h t f i t t i n go r i e n t e db o u n d i n gb o xt r e e s ( o b b t r e e s ) ，a n dt h e nc o m p u t e s t h ei 几t e r f e r e n c ed e t e c t i o ns t a t u sa m o n g s tc o m p l e x m o d e l su n d e r g o i n gr i g i d m o t i 。n 0 nt h eb a s jso fb o u n d i n gb o xd e t e c t ， m e s hs h o u l db ew r a p p e di n t h eb o xa n db ej u d g e dt h r o u g hi n t e r v a lo v e r l a p m e t h o d sa st og e tc o n t a c t e d b o x e s d e p e n d in g o nt h el o c a ti o nr e l a t i o nb e t w e e nt h et r i a n g l e s i n c o n t a c t e db o x e s ，w ec a dc a l c u l a t ec o n t a c t e dt r i a n g l e sa n d c o n t a c t e dl i n e s b e t w e e nc o n t a c t e dt r i a n g l e s t om i n i m i z et h ec o m p u t et i m ea n dc o m p l e x i t y 。fc o l i i s i o np r o c e s s ，o p t i m i z a t i o n isa l s ou s e d m e s hc h a r a c t e rc o n f o r m a t i o na f t e rc e n t a c t e d i sb a s eo fm o d e ls e 浙江大学硬十学位论文 摘要 c h a r a c t e re x t r a c t i o n i nv i e wo fs p e c i a l t ya b o u tm e s hm o d e l se x t r a c t i o n ， t h r o u g ht h es e q u e n c ea n dl o c a t i o nr e a t i o nb e t w e e nt r i a n g l e sc o n t a c t e d ， c o n t a c t e d1 n e si nt r i a n g l ec a nb ec o n s t r u c t e dt oc o n t a c t e d1 i n e so rl o o p s i nm e s h f r o mt h eo r i e n t e db o u n d i n gb o xc o i l i s i o nd e t e c t i o np o i n t ，a b o u n d i n gb o xi n c l u s i o na l g o r i t h mi sd e v e l o p e dw h i c ht e s tc o n t a c t i n ga n d i n c l u d i n g t h e r e f o r et h et r i a n g l e si n c l u d e di nt h eo t h e rb o x e sc a nb e j u d g e db y t h i sw a y f i n a l l y ，t h eo r i g i n a lc o n t a c t e dt r i a n g l e sc o m b i n e d w i t ht h ein c u d e dl r i a n g l e si nt h ep r o c e s sc a ni m p l e m e n tt h em e s hb o d y r e c o n s t r u c t i o n w ea 1s op r e s e n tm e s hc h a r a c t e rr e t r i e v ea n dm e s hc o n t o u rb o d yv o l u m e e s t i m a t i o nm e t h o d sb a s e do nt h em e s hc h a r a c t e re x t r a c t i o na n dc h a r a c t e r c o n s t r u c t i o nr e p r e s e n t a t i o ni nf u r t h e ra p p t i c a t i o n s k e y w o r d s ：o b bh i e r a r c h i c a ls t r u c t u r e ，s e p a r a t ea x e s ，c o n t o u rl o o p ，a a b b b o u n d in gb o x ，c h a r a c t e rc o n f o r m a t io n 。6 浙江人学硕士学位论文 第一章结论 i i 相关概念 第一章绪论 实时碰撞检测是机器人学、计算机辅助设计与制造、动画仿真、虚拟现实等 领域中一个非常关键的问题。它牵涉到运动学、动力学、几何建模、机器人学、 计算机图形学等学科的内容。它的研究方法也与上述学科有着主要联系。 随着计算机图形学、仿真技术和硬件技术的发展，用高质量的计算机动画来 对现实世界进行模拟与再创造已成为可能。很多专家和学者都研究了在动画演示 与模拟中的一个很重要的问题物体之间的干涉和碰撞，并在理论和实际方面 提出了许多有重要价值的研究结果。图形移动时的碰撞检测问题在计算机图形 学、c a d 、c a m 、动态系统模拟、机器人学以及实时干涉布局等问题中都有着 广泛的应用。 碰撞问题牵涉到碰撞检测和碰撞响应两部分内容。由于碰撞响应问题属于力 学的研究领域，故本文主要对碰撞检测问题的研究与发展过程作一个较全面的综 述。碰撞问题的具体应用很广泛，例如，虚拟环境应用中的飞行员和宇航员的培 养与训练、机器人的路径规划和学习、交互式动画系统、服装c a d 中衣物与人 体躯干的配合等。碰撞检测问题按运动物体所处的空间可分为：二维平面碰撞检测 和三维空间碰撞检测。由于平面物体的构造都可用多边形来表示，故其检测算法 相对要简单一些；丽三维物体的构造比较复杂，所以，其碰撞检测算法也比较困 难。 关于平面碰撞检测问题的研究主要有3 个方面，包括可碰撞、可移动区域和 最初碰撞部位的检测。关于三维空间碰撞问题的研究一般有可碰撞和碰撞规避两 方面。所谓可碰撞问题就是物体a 和b 在空间沿给定轨迹移动时是否发生碰撞。 可移动区域就是物体a 沿给定的规律运动，而不与物体b 发生碰撞的所有可能运 动的区域。最初碰撞点的检测就是当物体a 以给定的运动规律运动，并将与物体 b 发生碰撞时，检测它们在最初发生碰撞时的接触部位。碰撞规避就是两个或 多个物体的无碰撞运动。以卜是碰撞检测的相关问题。 1 平面碰撞问题 2 ，三维空间的碰撞检测问题 7 浙江人学硕士学位论文 第一章绪沦 2 1 静态干涉检测算法 2 2 可碰撞问题 2 | 3 碰撞规避问题 在这个基础上，进行交线、交线环、轮廓体特征计算是当今各个领域动态网 格特征描述的进一步研究内容。 1 2 本文的研究意义及应用领域 碰撞检测及应用问题不应归结为一般的求交问题，针对不同的应用对象，检 测问题不仅涉及检测方法的复杂性、可靠性和效率，而且涉及检测后特征提取、 特征分析、特征构造、碰撞处理等问题。不同的检测算法和提取的不同特征具有 不同的特点，面向的对象也不同，所以我们需要对各种碰撞检测方法和自己的目 的要求进行详细的分析，这样才可以找到满足研究结果的算法。 针对碰撞检测已有了大量有价值的研究成果，但随着c a d c a m 、动画模拟、 车床数控、机器人运动要求的不断提高，碰撞榆测技术所面临的进步深入要求 也日益突出，其中最核心的问题是如何有效地在碰撞过程中提取我们所需要的各 种特征，并且根据特征构造理想的模型或做出相应的判断。 在对各类碰撞检测算法做出全面了解、透彻分析的基础上，针对碰撞检测技 术、特征提取以及轮廓构造等问题，本文分别从以下两个角度出发，设计、实现 并验证了一组新的特征提取和特征构造算法，对如何利用已有碰撞检测算法，对 如何快速提取特征以及如何在有部分特征和信息的情况下重构网格体进行了有 益的探索性研究： 1 1 从碰撞检测算法和三维物体物理特征提取的角度出发，研究并提出一种 新的基于o b b 层次包围盒的快速特征提取算法，通过将层次树包围盒的计算优势 和简化的三角形空间计算相结合，以实现复杂物体问的碰撞特征提取。算法在继 承一般基于层次树包围盒的碰撞检测算法优点的同时，进一步深入了它们的内 容，能够在保证效率的前提下处理任意形状多面体之问的碰撞特征提取问题。算 法首先自动将物体构建对应的包围体，并合理地组织成层次二叉树结构以有效利 用物体的空间连贯性来进行碰撞检测；然后根据碰撞得到的结果快速求出相交三 角形和相应的三角形交线。为进一步提高碰撞检测的效率，在具体绘制操作之前， r 一 浙江大学硕士学位论文 第一章绪论 采用7 0 b b 包围盒树技术以尽可能早地排除彼处不发生碰撞的凸包围体，并有效 利用了 o b b 包围盒重叠检测的结果来得到三角形相交测试的初始数据；最后充分 利用了三角形相交优化算法对计算过程进行了优化。 2 ) 从碰撞体特征构造的角度出发，首先采用了一种基于拓扑和环关系的轮 廓构造算法：通过实时地分析碰撞网格体复杂的交线情况，如多环、相交环、重 叠环等情况，结合利用交线环分离处理办法，在碰撞网格体周围生成了相应的轮 廓线或轮廓环。其次我们需要估计出碰撞体的相交轮廓体，所以我们在o b b 层次 树包围盒的基础l ，创新地提出了一种快速的轮廓体构造算法。为此，算法首先 根据包围盒的位置关系，提出三种不同的情况：第一种为分离，第! ：种为相交， 第三种为包含。上面的求交线算法可以判断前两种情况，但是不能处理第三种情 况，从而对包围盒重叠判断算法进行了扩展，得到了另外一种算法，即包围盒包 含判断算法。然后，通过三角形与多面体空间关系判断，可以知道网格体彼此相 互包含的三角形，最后，结合前面的相交三角形实现轮廓体的构造。在对算法复 杂度和轮廓精确度分析的基础上，给出了一定的优化技术以进一步提升算法效率 和特征结果。 碰撞检测和特征提取有许多应用领域，虽然它一般不作为一个独立的系统 但在某些系统中它是必不可少的一部分，它的主要应有： 1 1 2 1 计算机图形学 1 汁算机动回和模拟 计算机动画与模拟是利用计算机对真实世界具有运动能力的物体进行模拟 的一种方法。这里既有物理过程的模拟，又有自然物体的模拟。在模拟过程中， 必须检测碰撞以及碰撞时产生的情况，也就是特征，如发生碰撞，力的大小和方 向改变，模拟就进入碰撞后的状态。计算机模拟在飞行器模拟中具有重要的意义。 2 ，虚拟现实 模拟现实是用计算机模拟应用真实环境的一种新技术，在虚拟现实应用中， 模拟刚体的装配环境需要解决的问题之一就是碰撞干涉检测和特征提取分析的 问题。 浙江大学硕十学位论文 第一章绪论 1 2 2c a d ，c a m 1 数控加工过程的干涉测试 刀具与工件的干涉检测与特征提取是数控编程软件刀位验证所必不可少的， 特别是复杂区域和腔槽的加工，除n c 切削加工外，n c 成型过程中存在严重的碰撞 危险，如在数控弯管过程中，管子与周围环境可能发生的碰撞，应用干涉检测方 法和特征提取方法进行检测和准确估计。 2 运动及运动机构设计 在c a d 系统中，产品的性能分析中一般包含了对运动机构设计的测试。运动 机构设计应保证各铰链的正确位置以及接于各铰链之上的各运动机构之间4 i 发 生干涉。 3 ，装配干涉 零件的装配不但要保证组件正确，而且要保证在装配和拆卸过程中零件之间 不能发生干涉，用计算机模拟这个过程可以尽早地发现问题，纠正设计中的错误。 1 2 3 计算机工程 1 机器人运动规划 机器人在运动过程中可能与障碍物，如静止的机床、零部件相撞，又可能与 其它运动的机器人相撞，机器人的避撞路径规划是机器人学研究的一个重要方 面。而且在具体细节要求越来越高的情况下，检测后的特征提取成为不可缺少的， 所以需要我们在检测后得到进一步的准确特征。 2 空间布局 空间布局指的是在一定的空间内满足一定的条件，将若干物体置于一容器内 而不发生干涉现象，如设备舱中仪器设备安排，管道布局等。 1 3 本文的内容 本文共分二f i 章，各章的内容安排如f ： 第章回顾了碰撞检测技术的概念、应用领域和意义，并着重对碰撞检测技 浙 工大学硕士学位论文 第一章绪论 术的应用进行了扼要的描述。 第二章从碰撞检测技术的发展状况、实际应用、基于不同情况的检测方法与 面向不同对象的检测方法等各个层面对碰撞检测作了综合分类介绍，并集中介绍 了几种常用的基本的碰撞榆测方法，如a a b b 层次包围盒树的碰撞检测算法， r a p i d 碰撞检测算法，s w i f t + + 碰撞检测算法。 第三章叙述了基于网格体碰撞的特征提取技术。其中描述了一些空间物理求 交点和求交线的算法。同时结合本文的需要，详细讲解了相应特征提取的算法和 整个过程。 第四章在特征提取的基础上，利用数学拓扑和环关系，计算出了相交面的轮 廓线。进一步，利用构造技术和实体生成技术，我们在碰撞相交的情况下，粗略 生成了相交轮廓体的外形，这对多面体模型交叉建造具有很重要的意义。 第五章对本文的研究成果及意义做总结，并探讨了进一步研究的方向。 浙江大学硕士学位论文 第二章碰撞检测技术 第二章碰撞检测技术 由于本文是基于碰撞检测的，许多地方都是用到了碰撞检测的算法和思想， 所以碰撞检测的算法和介绍自然是本文的基础。这里我们先将碰撞检测技术分类介 绍一下。 2 1 碰撞检测算法分类 2 1 1 基于时问域的碰撞检测算法分类 从时间域的角度来分，碰撞检测算法可分为静态碰撞检测算法、离散碰撞检测 算法和连续碰撞检测算法三类。 静态碰撞检测算法是指当场景中物体在整个时间轴t 上都不发生变化时，用来检 测在这个静止状态中各物体之间是否发生碰撞的算法。离散碰撞检测算法则是指在 时间轴的每个离散点t o ，t l ，t n 上不断地检测场景中所有物体之间是否发生碰撞 的算法。而连续碰撞检测算法是指在一个连续的时间间隔 t o ，t n 内，判断运动物 体是否与其他物体相交的算法。 静态碰撞检测问题在计算几何中有着广泛的研究，一般对这类算法没有实时性 的要求，但往往对算法精度要求较高 d o b k i n1 9 8 5 a g a r w a 1 9 9 1 c h a z e l l e 1 9 8 9 。 从本质上说，离散碰撞检测算法在每一时间离散点上可以通过类似于静态碰撞 检测算法的方法来实现的，但它更注重算法效率。从整个时间轴来看，由于算法的 时问离散特性，这类算法至少存在以下两个问题：( 1 ) 存在刺穿现象。当时间步长 过大时，两物体可能已发生了一定深度的刺穿才被检测到已发生碰撞，因此无法保 证物体的运动真实性；( 2 ) 会遗漏发生碰撞的情况。对于较狭窄的物体，当运动物 体在相邻时间离散点上的两个位置恰好处于该狭窄物体两侧时，离散算法将无法正 确地检测出物体所发生的碰撞。 浙江大学硕士学位论文 第二章碰撞检测技术 连续碰撞检测算法的研究一般涉及到四维时空问题或结构空间精确的建模 c a m e r o n1 9 9 0 c a n n y1 9 8 6 r e d o n2 0 0 1 r e d o n2 0 0 2 a ，这类算法能较好地解决 离散碰撞检测算法存在的上述两个问题，但通常计算速度比较慢，尤其是在大规模 场景中无法实现实时的碰撞检测。 离散碰撞检测算法尽管存在。些问题，但由于其检测过程盼决速性能较好地迎 合多数应用对实时碰撞检测的需求，所以仍是目前碰撞检测算法研究的重点和热点 l i n1 9 9 8 j i m 6 n e z2 0 0 1 。此外，人们还可通过一些优化方法在定程度上减轻 或降低离散碰撞检测算法的上述两个问题的影响。例如，自适应步长技术和可中断 的碰撞检测技术等均有助于改善这两个问题 h u b b a r d1 9 9 5 d i n g l i a n a2 0 0 0 d i n g i a n a2 0 0 1 0 s u l l i v a n1 9 9 9 。 2 1 2 基于空间域的碰撞检测算法分类 从空间域的角度来分，碰撞检测算法犬体可分为两大类：一类是基于物体空间 的碰撞检测算法；一类是基于图象空间的碰撞检测算法。这两类算法的主要区别在 于是利用物体二维几何特性进行求交计算还是利用物体二维投影的图象加上深度信 息来进行相交分析。目前在基r 物体空间的碰撞检测上，研究人员已经做了相当多 的工作 l i n1 9 9 8 j i m d n e z2 0 0 1 。基于图象空间的碰撞检测算法是一类比较新的碰撞 检测算法，它能有效利用图形硬件的绘制加速功能来提高碰撞检测算法的效率。近 ，l 年图形硬件技术的飞速发展，图形加速卡在性能不断迅速提高的同时甚至出现了 可编程的功能，使得基于图象空间的碰撞检测算法进入了一个新的发展阶段 l i n 2 0 0 2 】。 1 。基于物体空间的碰撞检测算法 基于物体空间的碰撞检测算法一直是人们研究的重点，已有相当的研究成果。 研究人员把各种技术如层次表示法、几何推理、代数范式、空间划分、解析方法和 最优化方法等应用到碰撞检n ! j e p l i n1 9 9 8 】 王志强1 9 9 9 j i m n e z 2 0 0 1 。本文从两 个方面来进一步区分基于物体空间的碰撞检测算法：一是基于物体的不同表示模型； 二是基于不同的空间结构。 浙江大学硕上学位论文 第一章碰撞检测技术 a 采用一般表示模型的碰撞检测算法 碰撞检测算法与物体采用的表示模型相关。面向小同表示模型的碰掩检测算法 各有特点，算法效率也有不同。目前在c a d c a m 和三维图形领域中存在多种几何模型， 但其中最主要的是多边形表示模型和非多边形表示模型两类。 多边形表示模型又可再细分为多边形集合( p o l y g o ns o u p ) 和结构化模型两类； 而非多边形表示模型则可分为c s g 表示模型、隐函数曲面、参数曲面和体表示模型 等。图2 1 给出了几何模型的一个分类。 图2 一j 几伺模型表不法分类 多边形表示模型是计算机图形学中最常用的几何模型，其特点是表示简单、通 用，因此很多碰撞检测算法都面向多边形表示模型设计。多边形表示模型中多边形 集合是一种常用的几何表示模型。这种表示模型中，物体表面被简单地表示为组 多边形的集合。面向这种表示模型的碰撞检测算法 h u b b a r d1 9 9 5 g o t t s c h a l k1 9 9 6 k l o s o w s k i1 9 9 8 z a c h m a n n1 9 9 8 一般有较广的适用范围。 当多边形表示模型的表面多边形彤成了一个封闭的闭包，并由此确定了内部和 外部区域，这种模型就称为多边形表示的结构化模型或称为多面体。多面体模型又 有凸多面体和非f l l 多面体之分。为叙述简便，本文将凸多面体简称为凸体，将非凸 浙江大学硕士学位论文 第= 章碰撞检测技术 多面体简称为非凸体。多面体为凸的含义是多面体内部的任意两点连线完全处于该 多面体的内部。多面体尤其是凸体良好的空间结构特性如空间连贯性可被利用来优 化碰撞检测的效率。因此，基于多面体，尤其是基于凸体的碰撞检测算法一直是碰 撞检测算法中的一个研究重点 l i n1 9 9 8 j i m 4 n e z2 0 0 1 。 面向凸体的碰撞检测算法大体上又可分为两类：一类是基于特征的碰撞检测算 法；另一类是基丁二单纯形( s i m p l e x ) 的碰撞检测算法。这两类算法分别由两个从不 同角度解决碰撞检测问题的经典算法发展演变而来。 基于特征的碰撞检测算法基本上都是源自于l i nc a n n y 的“最邻近特征算 法” l i n1 9 9 1 ，l i n l 9 9 3 。它们都按照多面体的特征( 如顶点、边、面等) 进行区 间剖分，并对每个特征建构其相应的v o r o n o i 区域。一个特征的v o r o n o i 区域是指那 些距离当前特征比其他特征更近的点所组成的区域。图2 2 显示了一个物体的顶点， 边，和面所对应的v o r o n o i 区域。这类算法依据v o r o n o i 区域的特性利用物体空间的 连贯性提高效率，其他主要代表算法有 l i n1 9 9 5 ， c o h e n1 9 9 5 ， c h u n g1 9 9 6 ， m i r t ic h1 9 9 8 ， e h m a n n2 0 0 0 ， e h m a n n2 0 0 1 。 ， j i 弋刁l i沙$ 烈l l 一， i ， 罗铲圆 圈2 2 一个立方体顶点，边和面分别对应的v o r o n o i 区域 而基于单纯形的碰撞检测算法，最初由g i l b e r t 、j o h n s o n 和k e e r t h i g i l b e r t 1 9 8 8 g i l b e r t1 9 9 0 提出，n o g j k 算法。这类算法通常将两物体看作一个单纯形， 通过单纯形的儿何特性来计算它们之间的分离或刺穿距离。e c a m e r o n1 9 9 7 b e r g e n 1 9 9 9 x 对g j k 算法作出了有益的改进，使算法具有良好的实时性和强壮性。几何模型 除了多边形表示模型外，还有一类称为非多边形表示模型，包括t c s g 表示模型、隐 函数曲面、参数曲面和体表示模型等。c s g ( c o n s t r u c t i v e s o l i dg e o m e t r y ) 表示模 型用一些基本体素如氏方体、球、柱体、锥体和圆环等，通过集合运算如并、交、 浙江大学硕士学位沦文 第= 章碰撞检测技术 差等操作来组合形成物体 r e q u i c h a1 9 9 2 ，h o f f m a n n1 9 8 9 。c s g 表示的优点之一是 它使得物体形状的建构更直观，即可以通过剪切( 交、差) 和粘贴( 并) 简单形状 物体米形成更复杂的物体。这也使得它更容易找到碰撞的确切位置 c a m e r o n1 9 9 1 。 $ c s c 表示的特殊性，基于该类模型表示的碰撞检测算法 z e i l l e r1 9 9 3 s u 1 9 9 6 p o u t a i n2 0 0 1 主要面向c a d 应用。隐函数曲面是指由隐函数定义的曲面模 型。当隐函数把三维字问映射到实数域上，f ：r 3 一r ，隐函数曲面就是由所有满足 f ( x ，y ，z ) = 0 的点组成的曲面。这时隐函数明确地定义了物体内部，即f ( x ，y ，z ) 0 。因此隐函数曲面一般都具有封闭的理想特点。隐函数 代数曲面的特例是二次曲面，即在x ，y ，z 上最高幂为二次的多项式所表示的曲面。 它可以在个统一的框架下表示锥体，球体和圆柱体等曲面。由于二次曲面在许多 实际工程中应用较广，研究人员因此提出了一些而向二次曲面的特定碰撞检测算法 f a r o u k i1 9 8 9 m i l l e r1 9 9 1 儿s h e n e1 9 9 1 来处理二次曲面之间的求交计算。参 数曲面表示是二维平面的子集到三维空间的映射，f ：r 2 一r 3 。砩i 同于隐函数曲面， 参数曲面一般来说不是封闭的。但参数曲面比隐函数曲面更易于用多边形来离散表 示，也更易于绘制。其中一个特殊的类别非均匀有理b 样条 | j 线( n u r b s ) 在c a d 领域 中使用非常广泛 l a n e1 9 8 0 f a r i n1 9 9 3 。基于参数曲面的碰撞检测算法也有部分 研究工作 t u r n b u l11 9 9 8 。 体表示模型用简单体素来描述物体对象的结构，其基本几何构件散为立方体 或四而体。与面模型不同，体模型一般用于软体对象的几何建模，它拥有对象的内 部信息，能表达模型在外力作用下的变化特征( 变形、分裂等) ，但其计算时间和空 间复杂度也相应增加。目前，基于体模型的碰撞检测算法丰要用于虚拟手术中可变 形物体的碰撞检测 h e i d e l b2 0 0 3 b o y l e s l 9 9 9 魏迎梅2 0 0 1 。此外，将复杂的三 维物体转化为简单体索进行表示，进行处理，使得基于该表示的求交算法简单而高 效，因此在对碰撞检测速度要求较高的场合也往往有一些应用 m c n e e l y1 9 9 9 。 2 采用空间结构的碰撞检测算法 物体空间的碰撞检测算法司采用不同的空间结构来提高效率，根据所用空间结 构的不同可将它们分为两类：空间剖分法( s p a c ed e c o m p o s i t i o n ) 和层次包围体树 法( h i e r a r c h i c a lb o u n d i n gv o l u m et r e e s ) 。这两类方法都是通过尽可能减少进行 浙江人学硕十学位论文 第二章碰撞检测技术 精确求交的物体对或基本几何元素的个数来提高算法效率的。不同的是，空间剖分 法采用对整个场景的层次剖分技术来实现，而层次包围体树法则是对场景中每个物 体建构合理的层次包围体树来实现。 1 ) 空间剖分法 场景的层次剖分方法主要有均匀剖分、b s p 树、k d 树和八叉树( o c t r e e ) 等 s a m e t 1 9 8 9 n a y l o r1 9 9 0 3 0 u r m a1 9 9 1 。基于这些空间剖分技术的碰撞检测算法也频繁 出现 n a y l o r1 9 9 0 g a r e i a1 9 9 4 h a m a d a1 9 9 6 m c n e e l y1 9 9 9 。但这类碰撞检测 算法较难在处理不同的场景和具有不同形状及复杂度的物体时保持比较一致的检测 效率。 2 ) 层次包围体树法 物体的层次包围体树可以根据其所采用包围体类型的不同来加以区分，主要包 括层次包围球树 h u b b a r d1 9 9 3 h u b b a r d1 9 9 5 p a l m e r1 9 9 5 o s u l l i v a n1 9 9 9 1 、 a a b b 层次树( a l i g n e d a x i s b o u n d i n g b o x ) z a c h m a n n1 9 9 7 b e r g e n1 9 9 7 l a r s s o n 2 0 0 1 、o b b 层次树( o r i e n t e d b o u n d i n g b o x ) g o t t s c h a l k1 9 9 6 1 、k - d o p 层次树( d i s c r e t e o r i e n t a t i o np o l y t o p e ) 【k l o s o w s k i1 9 9 8 1 z a c h m a n n1 9 9 9 、q u o s p o 层次树( q u a n t i z e d o r i e n t a t i o ns l a b s w i t hp r i m a r y o r i e n t a t i o n s ) 【h e l 9 9 9 】、凸块层次树 e h m a n n2 0 0 1 以 及混合层次包围体树 w a n2 0 0 1 等等。图2 3 给出了各种包围体类型在二维上的示例。 建构物体层次包围体树既可采取自顶向下的策略，也可自底向上来进行。目前基于 层次包围体树的算法多数采取自顶向下的方式来建构物体的层次包围体树。采用不 同的层次包围体树的碰撞检测算法各有其优缺点，我们将在主要算法介绍中对其作 进一步分析。 囫锣秒 ( a ) 包围盒( b ) a a b b 包同盒( c ) o b b 包围盒( d ) 6 - d o p 包围盒( e ) 凸包围盒 图2 - 3 包围体二维示意图 1 1 浙江大学硕士学位论文 第二章碰撞检测技术 3 基于图象空闻的碰撞检测算法 基于图象空间的碰撞检测算法一般利用图形硬件对物体的= 维图象采样和相应 的深度信息来判别两物体之间的相交情况。图形硬件有时也称为图形处理单元 ( g r a p h i c s p r o c e s s u n i t ，g p u ) 。如不特别指明，本文中_ 二者完全对等。 这类算法优势在于能有效利用图形硬件加速技术来减轻c p u 的计算负荷，从而 达到提高算法效率的l ：j 的。但是基于图象空间的碰撞检测算法由于其检测结果的不 精确性和依赖硬件支持而一直发展较慢。近些年，随着图形硬件计算性能的迅速增 长，基于图象空间的碰撞检测算法进入了一个新的快速发展阶段。 s h i n y a 等 s h i n y a1 9 9 1 芹l l r o s s i g n a c 等 r o s s i g n a c1 9 9 2 】于1 9 9 1 年前后开创性地 提出了图形硬件辅助碰撞检测的方法。随后，m y s z k o w s k i 等 m y s z k o w1 9 9 5 利用模 板缓存( s t e n c i lb u f f e r ) 检测每帧的变化状况，提出了一种有效的改进算法。b a c i u 等 b a c i u1 9 9 7 b a c i u1 9 9 9 进一步利用深度缓存和模板缓存的组合功能，提高图象空 间碰撞检测算法的效率，并使算法可在常规图形上作站甚至是普通个人台式电脑上 运行。h o f f 等 h o f f 2 0 0 1 】* 日k i m 等 k i m2 0 0 2 将图象空间碰撞检测算法利物体空间碰 撞检测算法结台起来，利用二者优点增强了算法的功能，同时通过一定的负载平衡 策略，在c p u 与图形硬件单元( g p u ) 问进行合理调配来保证算法的熬体效率。这 方面的其他研究工作还包括 l o m b a r d o1 9 9 9 v a s s i l e v2 0 0 1 h e i d e l b2 0 0 3 g o v i n d a r 2 0 0 3 。 下面给出所有碰撞检测算法的分类图， 如图2 4 浙江人学硕士学位论文第_ 章碰撞检测技术 图2 4 碰撞检测算法的分类总体 浙江大学硕士学位论文 第二章碰撞检测技术 2 2 主要算法介绍 下面介绍碰撞检测领域的代表性研究工作和最新研究成果，具体分为以下四个 方面：( 1 ) 面向i “i 体的碰撞检测算法：( 2 ) 基于般表示的碰撞检测算法；( 3 ) 基 于层次包围体树的碰撞检测算法；( 4 ) 基于图象空问的碰撞检测算法。 2 2 1 面向凸体的碰撞检测算法 面向凸体的碰撞检测算法大体上又可分为两类： 一类是基于特征的碰撞检测算 法；另一类是基于单纯形的碰撞检测算法。 1 基于特征的碰撞检测算法 顶点、边和面称为多面体的特征。基于特征的碰撞检测算法主要通过判别两个 多面体的顶点、边和面之间的相互关系进行它们之间的相交检测。所有基于特征的 方法基本上都源自于l ，i n c a n n y 的工作 l i n1 9 9 1 l j n1 9 9 3 。 l i n c a n n y 算法通过计算两个物体间最邻近特征的距离来确定它们是否相交。该算法 利用了连贯性来加快相交检测的速度。具体地，因为在连续的两帧之间最邻近特征 般不会明显变化，因此可通过将当前的最邻近特征保存到特征缓存中来加快下一 帧的相交检测速度。当最邻近特征发生了变化后，算法依据特征的v o r o n o i 区域先查 找与上一帧中保留特征的相邻特征，以此提高查找效率，从而提高相交检测的效率。 当碰撞检测的时间步相对物体移动速度较小时，算法可在预定的常数时间内进行特 征跟踪。这里假定碰撞检测算法每个循环计算是在场景运动变化后进行的。 卜c o l l i d e c o h e n1 9 9 5 是以l i n c a n n y 算法为基础，结合了时间连贯性的一个精确 的碰掩检测共享库，可用于由凸多面体构成的模型，并能够处理多个运动物体组成 的场景。 然而，l i n c a n n y 算法并不能够处理刺穿多面体的情况。面对刺穿情况，算法会 进入死循环。一个简单的解决办法是在算法达到最大循环数后强制中止，返回物体 发牛碰撞。但这种解决方法太慢，且无法判定物体是否真正相互刺穿。事实卜，只 浙江大学硕士学位论文 第：章碰撞检测技术 要物体不是移动太慢或碰撞检测的时间问隔不是十分短，物体相互刺穿的现象非常 常见。算法无法检测剌穿，这对实时应用环境如游戏和虚拟现实是不可想象的。当 相瓦刺穿发生又要求更精确的接触时间信息时，就要回溯到碰撞发生的精确瞬间， 这种过程也是非常缓慢和繁琐的。 p o n a m g i1 9 9 7 等引入了ir 1 多面体的伪内部 v o r o n o i 区域米克服这个问题。但同时引入了需要解决的其它问题，包括如何处理平 行特征面等特殊情况和如何配置容错闽值以将算法调整到理想性能等问题。 另一个具有代表性的基于特征的碰撞检测算法是v c l j p ( v o r o n o ic 1 i 口) m i r t i c h1 9 9 8 。m i t t i c h 宣称解决了l i n c a n n y 算法的局限性。v c l i p 算法能处理 刺穿情况，不需要用容错闽值来调整，而且不会有死循环的现象。同时由于特例情 况少而实现起来更加简单。它是目前所有算法中，处理j 、体之问的碰撞检测最快速 有效的算法之一。v c l i p 既可以处理凸体，也可处理非i ”i 体，甚至还可处理不连通的 物体，在物体发生刺穿时还能返回刺穿深度。它的算法效率相对i c o 1 i d e 和 e n h a n c e dg j k 有明显的改善，而h 比较强壮。 之