(计算机应用技术专业论文)实时喷泉模型中的碰撞检测算法研究.pdf_第1页
(计算机应用技术专业论文)实时喷泉模型中的碰撞检测算法研究.pdf_第2页
(计算机应用技术专业论文)实时喷泉模型中的碰撞检测算法研究.pdf_第3页
(计算机应用技术专业论文)实时喷泉模型中的碰撞检测算法研究.pdf_第4页
(计算机应用技术专业论文)实时喷泉模型中的碰撞检测算法研究.pdf_第5页
已阅读5页,还剩43页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

r e s e a r c ho nt h e a l g o r i t h m o fc o l l i s i o n d e t e c t i o nf o r t h ef o u n t a i nm o d e li nt h er e a l t i m e at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to f t h er e q u i r e m e n t f o rt h em s d e g r e ei nc o m p u t e ra p p l i c a t i o nt e c h n o l o g y b y l i ux i a o y a p o s t g r a d u a t ep r o g r a m c o m p u t e rs c i e n c ed e p a r t m e n t c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r :j i nh a n j a n a c a d e m i ct i t l e :p r o f e ! s s o r s i g n a t u r e a p p r o v e d m a y , 2 0 1 1 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名:斟1 8 l 曳吐 日期:伽f 降6 月日 作 或 在 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定,即:研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版,允许学位论文被查阅和借阅; 学校可以公布学位论文的全部或部分内容,可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释:本学位论文属于保密,在年解密后适用本授权书。 非保密论文注释:本学位论文不属于保密范围,适用本授权书。 作者签名:当t 11 3 瓦也 日期矶j 年6 月f 日 导师签名:a 叉够 日期g b 年易月e l 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ,同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布,并可按“章程”中的 规定享受相关权益。回重途塞握窒蜃溢卮;旦圭生;旦二生;旦三生筮查! 作者签名:轰、1 d 芤弘 日期加l 降6 月1 日 导师签名: 日期| t 年6 只 日 沉浸在其 模拟。例 如,如果在虚拟场景中织物碰到桌子边缘没有变形、小球碰到地面没有弹起、甚至 物体有穿墙而过等现象,这些场景一点都不符合客观规律,没有真实感。造成这一 现象的原因就在于场景中运动的物体违反了物体运动的自然规律,缺乏对物理现象 进行模拟。因此,基于物理原理的物体间的碰撞检测问题成为三维动画、计算机游 戏、虚拟手术、织物仿真等领域的研究热点问题。 目前,对于刚体之间,以及刚体与变形体之间的碰撞检测算法的研究已趋于成 熟,但对基于物理方法表示的模型的相关算法研究较少。因此,本文主要从以下几 个方面进行: 首先,研究从物理原理出发,结合粒子系统实现了真实感喷泉模型的模拟,本 文提出了一种新的双缓冲机制对喷泉水珠粒子进行存储,实现粒子属性的实时更 新。由于对粒子的相关静态属性值只存储一次,相比以往的双缓冲机制,在空间复 杂度上进行了很大的优化;其次,提出了利用泊松分布的概率密度函数,近似求出 喷泉系统的粒子源在单位时间内发射的粒子数目以及发生碰撞的粒子数目,为进一 步维护整个系统的能量守恒提供依据;最后,本文重点研究了喷泉模型中水珠粒子 与障碍物之间的碰撞问题,提出一种新的碰撞检测算法,该算法根据每个水珠粒子 当前的状态值,从粒子能量的角度去判断某一粒子是否与障碍物发生碰撞,从而克 服了粒子数量巨大、障碍物本身的复杂特性、及粒子之间的碰撞等缺陷,节省了大 量的相交测试所耗费的时间。并且与已有的算法相比较,在时间复杂度和空间复杂 度上都实现了很大的突破。模拟实验证明,本文算法效率良好,能满足实时性要求, 生成的图形也比较真实。这些工作的完成是对基于粒子系统的碰撞检测算法的一种 有益探索。 关键词:喷泉模型;碰撞检测;粒子系统;泊松分布;双缓冲机制 f a b r i cw i t h o u td i s t o r t i o nw h e ni tt o u c h e st h ee d g eo ft h et a b l e ,a n dt h es m a l lb a l lw i t h o u t b o u n c ew h e ni tf a l l sd o w nt ot h ef l o o r ,e v e nt h eo b j e c t sc a ng ot h r o u g ht h ew a l l ,t h e s e s c e n e sd o n tc o n f o r mt ot h eo b j e c t i v el a w s ,a n dh a v en or e a l i s t i cf e e l i n g s t h er e a s o nf o r t h i sp h e n o m e n o ni st h a tt h es c e n eg o e sa g a i n s tt h en a t u r a lr u l e so ft h em o v e m e n to ft h e o b j e c t s ,a n da l s o l a c ko ft h es i m u l a t i o nf o rp h y s i c a lp h e n o m e n o n t h e r e f o r e ,c o l l i s i o n d e t e c t i o nb a s e do np h y s i c a lt h e o r yh a sb e c o m eo n er e s e a r c ht o p i ci nt h ef i e l do f3 d g r a p h i c ,c o m p u t e rg a m e s ,v i r t u a ls u r g e r ya n df a b r i cs i m u l a t i o n ,a n ds oo n a tp r e s e n t ,r e s e a r c ho nc o l l i s i o nd e t e c t i o nb e t w e e nr i g i db o d ya n dr i g i db o d y ,a l s o b e t w e e nd e f o r m a b l eb o d ya n dr i g i db o d y ,h a sa c h i e v e dm a t u r e ,b u tt h er e s e a r c ho n r e l a t e da l g o r i t h m st or e p r e s e n tm o d e lb a s e do np h y s i c a lm e t h o d sh a sn o tb e e nf u l l y s t u d i e d s ot h i sa r t i c l em a i n l yp u t sf o r w a r ds o m ea s p e c t sa sf o l l o w e d : f i r s t l y ,w ep r o c e e df r o mt h ep h y s i c a lt h e o r y ,a n dr e a l i z et h es i m u l a t i o no ft h e f o u n t a i nm o d e lc o m b i n e dw i t l lr e l a t e dt h e o r ya b o u tp a r t i c l es y s t e m a tt h es a m et i m e t h i sa r t i c l ep u tf o r w a r dan e wd o u b l e b u f f e r i n gm e c h a n i s mf o rw a t e rp a r t i c l e s s t o r a g e , r e a l i z et h er e a lt i m eu p d a t i n go ft h ep a r t i c l e s p r o p e r t y o w i n gt oj u s ts t o r et h er e l a t e d s t a t i cp r o p e r t yo ft h ep a r t i c l e ,o u rm e t h o do p t i m i z et h es p a c ec o m p l e x i t yc o m p a r e dw i t h o t h e rd o u b l e b u f f e r i n gm e c h a n i s m ;s e c o n d l y ,w ep r o p o s et om a k eu s eo ft h ep r o b a b i l i t y d e n s i t yf u n c t i o no fp o i s s o nd i s t r i b u t i o n ,g e ta l la p p r o x i m a t en u m b e ro fp a r t i c l e sl a u n c h e d b yt h ep a r t i c l es o u r c ea tp e ru n i tt i m e ,a l s oc a ng e th o wm a n yp a r t i c l e sm a yh a p p e n c o l l i s i o n ,t h e s ed a t as u p p l yt h e f o u n d a t i o nf o rt h e f u r t h e rw o r ko ft h e e n e r g y c o n s e r v a t i o n ;a tl a s t ,t h i sa r t i c l ef o c u so nr e s e a r c h i n gt h ec o l l i s i o ni s s u e sb e t w e e nt h e w a t e rp a r t i c l e sa n do b s t a c l e s ,a n dp r o p o s ean e wa l g o r i t h ma b o u tt h ec o l l i s i o nd e t e c t i o n w ej u d g ew h e t h e rt h ec o l l i s i o nh a p p e n e db e t w e e naw a t e rp a r t i c l ea n dt h eo b s t a c l e sf r o m t h ep e r s p e c t i v eo fe n e r g yo fe v e r yp a r t i c l eb a s e do nt h ec u r r e n ts t a t eo ft h ep a r t i c l e s o w eo v e r c o m et h ed e f e c t so ft h el a r g en u m b e ro fp a r t i c l e s ,t h ec o m p l e xp r o p e r t yo ft h e o b s t a c l e s ,a n dt h es e l f - c o l l i s i o no ft h ep a r t i c l e s ,s a v eal o to ft i m ef r o mt h ei n t e r s e c t t e s t i n g t h es i m u l a t i o ne x p e r i m e n th a sp r o v e dt h a tt h ee f f i c i e n c yo ft h ea l g o r i t h m s i i i i i i i i 第1 章绪论1 1 1 研究背景及意义1 1 2 国内外研究现状3 1 3 本文工作4 1 4 论文组织结构4 第2 章碰撞检测算法综述5 2 1 碰撞检测5 2 1 1 概念5 2 1 2 碰撞检测的约束条件5 2 2 碰撞检测算法分类6 2 2 1 层次包围盒6 2 2 2 空间分割9 2 2 3 距离场1 0 2 2 4 图像空间1 l 2 2 5 随机方法1 2 2 3 本章小结1 3 第3 章基于粒子系统的碰撞检测算法1 4 3 1 粒子系统1 4 3 1 1 粒子的属性1 4 3 1 2 粒子的状态及存储结构1 5 3 1 3 粒子的运动模型1 6 3 2 基于粒子系统的典型应用1 6 3 3 基于粒子系统的碰撞检测经典算法1 8 3 4 本章小结2 0 第4 章一种基于粒子系统的喷泉模型的碰撞检测算法2 1 5 2 算法分析3 4 5 3 本章小结3 5 第6 章总结和展望3 6 6 1 总结3 6 6 2 展望3 6 参考文献3 7 硕士期间发表的论文和参与科研项目4 0 致谢4 1 随着虚拟现实( v i r t u a lr e a l i t y ,v r ) 、计算机动画仿真等领域的迅猛发展,人 们要求搭建真实感场景呼声越来越高,然而,真实感虚拟场景的搭建最核心的问题 就是如何有效地进行实时的碰撞检测。碰撞检测的原理是基于两个或多个物体不可 能同时占有同一片空间区域这样一个简单的客观事实,而实时碰撞检测的基本任务 就是快速而又准确地确定两个或者多个物体之间是否发生交叉、穿透等失真现象, 并且能够及时地做出碰撞反应,如图1 1 所示, 图1 1 碰撞检测示例( 红色表示碰撞发生的位置) 自上个世纪七十年代,在自动装配规划、机器人路径规划等领域,国内外学者 开始有关碰撞检测问题的研究,考虑到机器人与场景中的物体、以及机器人自身的 零件与零件之间是否发生碰撞,提出了一系列相关的碰撞检测算法。但是,由于当 时计算技术及研究条件等因素的滞后发展,这些算法基本上都不能够实时完成。目 前,国内外相关学者在碰撞检测领域已经取得了大量很有价值的研究成果,但是随 着虚拟场景的规模日益壮大、三维几何模型的同益复杂、以及人们对于场景真实性、 交互实时性的要求日益提高,碰撞检测领域所面临的种种问题也随之凸显。 虚拟场景中存在大量的几何形状复杂的物体对象,这些对象或是运动的,或是 在运动过程中变形的,或是其它更为复杂的状态。它们在运动的过程中随时都有可 能与其它物体对象发生碰撞,并且包括自身碰撞,这就需要我们及时的检测出碰撞 发生的位置,做出碰撞反应,以免发生穿透、交叉等失真现象。同时,由于这些对 象自身结构和运动等属性的固有复杂性,使得我们的碰撞检测进程在运行时间和存 硕士学位论文 m a s t e r st h e s i s 储空间上都要占去相当一部分资源。因此,快速而准确的碰撞检测算法及其实现成 为提高虚拟环境的真实感和沉浸感的关键问题。 目前,对于刚体之间,以及刚体与变形体之间的碰撞检测算法的研究己趋向成 熟,包含这些物体的虚拟场景的搭建也近于完善,与此同时,场景中包含的自然景 物的模拟成为计算机图形学学者当前所面临的巨大挑战。由于云、水、火等自然景 物的形状千变万化,并且是随机的,用传统的曲面表示形式很难描述。经过广泛的 研究,粒子系统被引入来模拟水、火等类似的不规则物体。d a v i dk m c a l l i s t e r l l j 利用c + + 语言,并结合o p e n g l 图形函数库,开发了一套粒子系统的应用程序接口 ( a p p l i c a t i o np r o g r a mi n t e r f a c e ,a p i ) 。 利用上述应用程序接口,我们可以很方便地模拟处于运动变化状态的物体,尤 其是对随机变化的自然景物的模拟。首先,对场景中各个粒子的活动进行简单的描 述,即对其相关属性进行初始化;接着,定义各个粒子的运动状态及规则;最后, 对整个粒子系统进行场景渲染,同时,结合相关的纹理映射使得所搭建的虚拟场景 生动逼真。该系统已被国内外很多专家学者用来进行实验仿真,例如,m c a l l i s t e r 实验室已经利用该应用程序接口成功的模拟出了火、烟雾、运动的小球、视频的虚 幻特效等流体对象,如图1 2 所示。 图1 2 基于粒子系统应用程序接口构造的虚拟场景 2 _ , 硕士学位论文 m a s t e r st h e s i s 粒子系统及其相关的应用程序接口的研究和发展,对于计算机图形学向着更深 跟完善的领域发展意义深远而重大,它可以很轻松地模拟出非规则形状的特殊物体 对象,这些对象往往可以使得我们的虚拟场景更加的生动形象,同时,粒子系统理 论体系的发展将推动计算机图形学领域迈向一个新的台阶。 本文的主要工作就是将粒子系统的相关原理应用于虚拟场景的搭建,实现喷泉 模型的仿真,考虑到整个粒子系统工作的能量守恒问题,并且着重研究了基于粒子 系统的喷泉模型中水珠粒子与障碍物之间的碰撞问题,完善了一种复杂形态下虚拟 环境中用户与对象的实时交互。 1 2 国内外研究现状 目前,国内外学者在碰撞检测领域做了很多深入的研究,提出了一些比较成熟 的算法并得以验证。从总体上说,这些算法可以归为两类:一种是静态的碰撞检测 算法。主要用于检测静止状态中各物体之间是否发生干涉的算法。这类算法对实时 性要求不高,但对精度要求较高。另一种是动态的碰撞检测算法。重在研究场景中 物体的相对位置不断地随时间发生变化而导致的碰撞。研究人员做了大量的工作, 对于动态的碰撞检测算法主要分为层次包围盒、空间分割、距离场、图像空间、随 机方法等,这些算法目前也渐趋于成熟。 而对于本文重点研究的喷泉模型的碰撞问题,国内外学者则很少关注,大部分 着眼于喷泉模型的实时生成算法,却忽视了其所涉及的碰撞检测进程,从而影响了 整个系统的真实感和沉浸感。近二十年来,针对喷泉模型的实时生成,由于喷泉这 类自然景物的表面包含丰富的细节或具有随机变化的形状,用传统的造型方法实现 十分困难。自1 9 8 3 年r e e v e s 2 提出粒子系统以来,已有很多学者利用粒子的特性 来模拟自然现象。p e a c h e y 3 1 、f o u r n i e r 4 1 等人曾采用粒子系统模拟过水珠,他们 所采用以圆球为代表的三维实体作为基本粒子对水珠进行造型。由于圆球在相互靠 近时产生变形,并且再进一步靠近时就会融合在一起,这恰恰类似于水滴相互靠近 时相互融合的事实。由于喷泉模型包含大量的粒子数量,渲染这些圆球粒子将耗费 巨大的时间。之后,相关学者又采用了线元来代替圆球这一基本绘制单元。考虑到 在线元本身的绘制效率比圆球高,在粒子数量巨大的情况下也能得到满意的绘制效 果,并且线元适合对水珠的运行轨迹的模拟。同时,可以通过逐渐淡化融合的技术, 即减小粒子的透明度a l p h a 值来模拟水珠明亮晶莹的效果。 1 3 本文工作 在本文中,首先探讨了近二十年的关于虚拟环境中碰撞检测算法的研究现状, 并明确各种方法所适应的相关场合和算法效率。接着,从物理角度出发,结合粒子 系统的相关原理实现喷泉模型的仿真,并考虑了整个喷泉系统的能量平衡问题,保 证整个喷泉系统稳定有序运行。最后,着重研究喷泉模型中水珠粒子与障碍物之间 的碰撞问题并验证算法的运行效率。 本文的创新之处体现在: ( 1 ) 结合粒子系统的相关原理来实现实时喷泉模拟,引入了双缓冲存储机制 实现喷泉粒子的存储优化,并利用泊松分布的概率密度函数,近似求出喷泉系统的 粒子源单位时间内发射的粒子数目、发生碰撞的粒子数目,从而为进一步维护整个 系统的能量守恒提供依据。 ( 2 ) 首次提出从每个水珠粒子的能量的角度去判断某一粒子是否与障碍物发生 碰撞,克服了粒子数量巨大、障碍物本身的复杂特性及粒子之间的碰撞等缺陷,从 而节省了大量的相交测试所耗费的时间。 实验结果证明该算法实现简单,模拟的喷泉效果满足实时性和逼真性的要求, 同时加速了碰撞检测的进程。 1 4 论文组织结构 论文开篇在绪论章节首先介绍当前碰撞检测在虚拟现实、计算机图形学等领域 的重要地位,然后指出了基于粒子系统的碰撞检测问题的研究现状及发展前景,提 出本文所要研究的内容及要解决的问题基于粒子系统的喷泉模型的碰撞检测 问题研究。在第二章首先对碰撞检测的相关知识做了概述,接着通过对已有的碰撞 检测算法的对比分析,最后得出了各个算法所适用的场合及算法实现的效率。在论 文第三章首先针对粒子系统做了简要的概述,接着,介绍了粒子系统的经典的应用 场景及其相关的碰撞检测问题研究。在第四章中详细讨论并具体实现了基于粒子系 统的实时喷泉模型的模拟,引入了新的粒子存储机制,并利用泊松分布的概率密度 函数得到碰撞检测的预测数据,从而进一步维护整个喷泉系统的持续稳定运行,最 后,针对之前的经典算法,提出一种新的碰撞检测算法。第五章紧接着给出了整个 喷泉场景的搭建结果,并针对我们所提出的算法进行了算法分析。第六章对前面所 做工作的结果进行评价,并提出不足及改进之处。最后进行展望,提出了下一步的 工作目标。 4 2 1 碰撞检测 2 1 1 概念 碰撞检测是虚拟现实【5 1 、计算机游戏、机器人技术、计算机仿真等领域的一个 重要组成部分,在我们所搭建的虚拟场景中加入碰撞检测技术之后,可以使场景更 加地逼真、自然。给出一个直观地例子,如果场景中的虚拟人物走到了面墙壁, 如果缺乏了碰撞检测技术,往往就会出现“人物穿墙而过”类似的失真效果,如 图2 1 所示。 图2 1 计算机游戏中人物穿墙而过的失真效果 一般来说,碰撞检测就是去检测场景中的各个不同物体之间是否发生了碰撞; 从几何的角度看待碰撞检测,就是对不同多面体之间进行求交测试;从其具体的工 作内容来看待碰撞检测,可分为两个具体步骤:第一步,检测出是否发生碰撞,第 二步,计算出发生碰撞的具体位置。 为使用户在虚拟场景中具有极强的真实感、沉浸感以及完善的交互,快速而又 精确的碰撞检测技术是必不可少的。总的来说,碰撞检测所研究的目标就是尽可能 增强大规模复杂场景实时交互的真实性。 2 1 2 碰撞检测的约束条件 碰撞检测有很多具体的约束条件,其中最为重要的两个约束条件是实时性和精 确性的要求。 实时性,主要是从用户视觉显示要求的角度来定义,也就是说,碰撞检测应该 在一个很短的时间范围内实现。对于一般的可视化场景,碰撞检测的速度要求达到 2 4 h z ,才能体现其实时性能。 就精确性而言,则要取决于具体的应用场合。对于虚拟校园、虚拟步行街、虚 拟展厅等类似的环境漫游系统,其碰撞检测系统要求的不高,一般只需求出一个大 概的碰撞情形,即当两物体的距离低于事先设定的某个阈值时,我们就可假定这两 个物体发生了碰撞,无需对其碰撞位置做出精确地计算。但是,对于一些虚拟装配、 虚拟手术等类似的仿真系统,则要求极高,我们需要精确地求出碰撞发生的具体位 置。 实时性和精确性,不仅是我们构建虚拟场景是要考虑的重要问题,也是我们对 以往工作进行参数对比的重要参考。 2 2 碰撞检测算法分类 目前,对于动态的碰撞检测算法 6 1 主要包括层次包围盒、空间分割、距离场7 。9 1 、 图像空间、随机方法等,这些算法也渐趋于成熟,这些方法已被证明同时适用于刚 体和变形体的碰撞检测问题。 2 2 1 层次包围盒 层次包围盒( b o u n d i n g v o l u m eh i e r a r c h i e s ,b v h s ) 1 0 - 1 2 是目前碰撞检测领域 使用最为广泛的数据结构之一,它已被证明可以很好的适用于刚体及变形体的碰撞 检测问题研究。国内外学者已经提出了许多包围盒的类型,例如,包围球( s p h e r e ) 、 轴向包围盒( a a b b ) 【1 3 】、定向包围盒( o b b ) 、k - d o p j 4 】、凸包( c o n v e xh u l l ) 等。如图 2 2 所示: 圈 包禹球a a b bo b b 纱参 k - d o p ( k - - - 6 ) 凸包 图2 2 各种包围盒类型 6 要比二叉树强,主要体现在:遍历时递归深度低、更少的节点需要更新、更新耗费 低、同时减少了内存需求。 考虑两个不同的三维物体a 1 和a 2 ,利用层次包围盒方法的碰撞检测过程的大 致步骤如下: ( 1 ) 构造三维物体a 1 和a 2 的b v h ( 三种方式:自上而下、自下而上、插入) ; ( 2 ) 对a 1 、a 2 的b v h 进行求交测试【1 5 】; ( 3 ) 若a 1 、a 2 为变形体,更新其b v h ,转至步骤2 ;若a l 、a 2 为刚体,直 接转至步骤4 ; ( 4 ) 场景运行结束,退出。 对a 1 、a 2 进行求交测试的算法思想如下: ( 1 ) 遍历a 1 、a 2 ; ( 2 ) 判断a 1 和a 2 是否重叠,若不重叠,退出; ( 3 ) 若a 1 、a 2 是叶子节点,则返回a 1 和a 2 所包含的相交几何元; ( 4 ) 对a 1 的所有孩子节点( 这里记为a 1 i ) 与a 2 进行遍历,直至发现碰 撞位置; ( 5 ) 算法结束。 生锏 7 ( b ) 层次遍历两物体的b v h 并找出碰撞位置( 红色标识碰撞节点) 图2 3 用二叉树表示b v h 及其碰撞检测过程 适用层次包围盒对物体进行碰撞检测时要考虑物体的形态及运动状态两个重 要的因素。物体的形态主要分为刚体和变形体等形态,运动状态分为运动和静止两 种状态。对于刚体对象,不论其在何种运动状态下,层次包围盒构建完成后,无需 对其进行更新,除非刚体对象形状收到外界力量强制改变。而对于变形体对象,无 论其处于何种运动状态,都要在每一个时间帧内对其进行检测,更新其层次包围盒。 层次包围盒的更新可采用自底向上和自顶向下两种方法进行,l a r s s o n l l 6 1 等人 对这两种方法进行了比较,发现当包围盒深层节点更新数目较多时,自底向上的方 法性能更好,而当深层节点更新数目不多时,自顶向下的方法将更快。因此,l a r s s o n 等人提出了一种混合更新方法,即首先利用自底向上的方法更新层次包围盒,若没 有发现有节点要更新,然后就再自顶向下遍历更新。m e z g e r l l7 j 等人又进一步对更新 算法进行了优化,通过省略更新过程的若干步骤来简化更新进程,他们还尝试了增 加包围盒的规模来尽可能减小包围盒的更新。v a nd e nb e r g e n o s 通过构建a a b b 包 围盒还发现对包围盒的重修要比重新构建快1 0 倍。 基于层次包围盒的碰撞检测算法已被广泛应用于刚体及变形体场景的碰撞检 测,g o t t s c h a l k t l 9 】首次运用o b b 层次包围盒对刚体进行碰撞检测,这也就是著名的 基于o b b 的“r a p i d 系统,该系统要求输入的物体模型是一组无结构的多边形, 其可以实现任意多边形之间的碰撞检测,但是,其适用场合比较局限于两个距离比 较接近的物体间的碰撞。l i n t 2 0 】等人提出了“i - c o l l i d e 系统,主要是通过对包围盒 的排序来减少进行碰撞检测的物体对数,同时结合了预测试方法来加速算法效率, 8 该系统可适用于大规模复杂场景的碰撞检测。v a nd e nb e r g e n 等人开发的“s o l i d 系统要求输入的物体模型可以是多边形或是多面体,采用a a b b 层次包围盒实现, 该系统可适用于变形体的碰撞检测。除了这些碰撞检测系统之外,国内外学者也相 继开发了很多适用于不同场合的碰撞检测系统,例如,v - c o l l i d e 、v - c l i p 、e n h a n c e d g j k 等。 2 2 2 空间分割 基于空间分割的碰撞检测算法,其基本思想是: ( 1 ) 对整个三维空间沿x 、y 、z 轴进行分割,形成一系列空间网格; ( 2 ) 判断位于同一个空间网格内的对象之问是否发生碰撞。 对整个三维空间沿x 、y 、z 三轴进行分割的方法有很多,一般采取的有均匀网 格、- - y 空间分割树( b i n a r ys p a c ep a r t i t i o n i n g ,b s p t 2 1 】【2 2 1 ) 、四又树、八叉树 等,如图2 4 的平面表示结构。这里要注意,数据结构的选择直接影响到算法的性 能及效率,对于空间分割的实现尤为重要。 一 l 均匀列格阴叉褥 :叉窀蛳分割 ;孽 图2 4 空间分割采用的数据结构 四叉树和b s p 树数据结构,在处理刚体对象的碰撞时可以达到很好的性能。均 匀网格数据结构,对于变形体对象之间及自身的碰撞检测提供了非常有效的途径, 同时也很好的适用于刚体对象。 空间分割方法去除了对物体基本几何元素的限制,即不仅可以处理三角面片这 种基本的几何元素,还可以处理类似于四面体之类复杂的几何元素,所以适用范围 更加广阔。 文献 2 3 首次使用了哈希函数对空间网格进行索引,而不是使用复杂的八叉树 或是其它复杂的数据结构,将3 d 网格单元映射至一个哈希表,这种方法可以处理 潜在的无限空间网格,因此,该方法不需要构建全局包围盒,对算法进行了简化和 加速。 空间分割方法适用于均匀分布且对象较少的三维空间,对于对象较多且分布不 均的三维空间算法效率将大大降低。考虑到空间分割规模的划分对碰撞检测的效率 9 并快速的定位碰撞发生的位置,提高了碰撞检测的效率。 2 2 3 距离场 距离场【2 5 1 是一个标量场,它表示的是三维空间中的任一点到另一个物体表面的 最短距离,其可分为无符号距离场和有符号距离场。通常,我们使用有符号的距离 场来判断空间中任意点是在物体之内还是之外。文献 2 6 给出了无符号和有符号距 离场的具体定义: 定义一若给定三维空间中的任意一集合s 、任意一点p ,则点p 至集合s 中 最近点的无符号距离场的表示方式为d i s t s ( p ) = i n f i x p l j 。 定义二设是集合s 的闭合曲面,p 为空间内任意一点,则点p 到闭合曲面 最近点的有符号距离场的表示方式为d i s t z ( p ) = s i 9 7 2 ( p ) i n f l x p l l ,其中有, | ,一l p s ,p 正 s i g n ( p ) = 0p 【l p 甓s 有了距离场的具体定义,我们可以根据场值的正负来判断空间中一点与物体的 位置关系是:当该场值为正时,点位于物体之外;场值为负时,点位于物体之内。 在此基础是上得到基于有符号距离场的碰撞检测算法思想如下: ( 1 ) 生成三维物体的距离场,即一个包围物体对象的封闭曲面; ( 2 ) 计算其他对象是位于曲面( 距离场) 内部或是外部来判断是否发生碰撞。 另外,除了上述的距离场计算函数之外,合适的距离场存储结构对距离场算 法效率的影响也是不容小觑的。对三维物体构造距离场的采用的数据结构有很多, 一般采用均匀三维网格、八叉树、b s p 树等( 可参见图2 4 ) 。均匀网格的内存需求 巨大、适用特征简单的物体对象,对于特征复杂的物体对象其解决方案有限。文献 2 7 提出一种自适应采样距离场( a d a p t i v e l ys a m p l e dd i s t a n c ef i e l d s ,a d f s ) 来克服这些缺陷,通过采用八叉树结构对三维物体进行存储,达到一个很好的压缩 比,节省了内存空间。文献 2 8 使用b s p 树,通过分段线性的方法构造距离场,选 择合适的分割平面来构造b s p 树。因此,b s p 树存储压缩紧凑,但同时构造b s p 树 的计算量很大,这一缺陷不像a d f 方法的缺陷那样容易克服。 1 0 一, 硕士学位论文 m a s t e r st h e s i s 在文献 2 9 中,以参数形式表示三角面片,将计算点到三角形面片的有向距离 的问题转化为计算在三角面片的定义域上计算点到三角面片上任一点的距离,从而 减少了计算时间。同时,使用一种矩阵式八叉树的存储结构来克服传统的线性八叉 树和指针八叉树在访问效率和存储空间上的缺陷。 基于距离场的碰撞检测算法有很多优势。首先,用距离场表示的物体其表面可 以是凹的或是凸的,其形态可以是刚体也可是变形体,及该方法克服了物体拓扑的 限制。其次,该方法与对象的几何复杂性无关。最后,该方法平衡了计算效率和准 确度之间的矛盾。 2 2 4 图像空间 基于图像空间的碰撞检测算法的基本思想是: ( 1 ) 将三维空间的物体对象通过投影转换至二维平面; ( 2 ) 在二维平面上判断这些物体的投影是否发生了碰撞。 文献 3 0 】最早将图像空间方法应用于碰撞检测进程,通过两个深度缓冲区实现 其算法,但是该算法要求物体对象必须是凸的,并且不能明确的指出是否适合变形 体对象。在此基础上,文献【3 1 】对其进行了改进,提出了分层深度图像( l p y e r e d d e p t h i m a g e ,l d i ) 来近似表示二维投影的包围盒结构,如图2 5 所示,这种方法克服了 之前对物体对象拓扑的局限,并且很好的兼容了可变形物体的碰撞检测。 心了 ( a ) 通过a a a b 检测 ( b ) 在包围盒内构建l 1 ) i( c ) l d i 内计算相交都分 图2 5 三维物体利用l d i 技术进行碰撞检测 图像空间技术不需要对物体对象进行预处理,并且也不要求对象特殊的拓扑结 构,因而,节省了大量的时间,提高了算法的应用场景。同时,该技术通常利用图 形硬件来进行加速,更好的提高了算法性能。 雪萋雾露蘩蓼 : 硕士学位论丈 m a s t e r st h e s i s 2 2 5 随机方法 基于随机学的碰撞检测算法,根据其使用的随机学方式的不同,可分为 a v e r a g e c a s e 方法和基于随机选择几何元的碰撞检测方法。 a v e r a g e - c a s e 方法的基本思想是: ( 1 ) 随机的、快速的计算每一对包围盒内部的多边形之间发生碰撞的可能性; ( 2 ) 以该可能性为优先权,从而去指导遍历碰撞可能性高的包围盒。 该方法往往通过构造层次包围盒,利用队列先进先出的结构优势实现,算法易 拓展。下面给出了a v e r a g e c a s e 方法实现的伪代码: 基于随机选择几何元方法的主要思想是: ( 1 ) 对所有的碰撞对象,进行随机取样,并将其作为初始的、潜在的发生碰 撞的区域的猜测; ( 2 ) 在采样得到的可能碰撞集内,利用时空一致性原理,进行快速的碰撞检 测。 该方法无需构造层次包围盒,直接作用于几何元对。文献 3 2 提出了一种新的 方法来更新曲面结构的局部距离最小值,用m 、n 表示邻近几何元的数目,使算法的 时间复杂度从o ( m n ) 降低到o ( m + n ) 。 a v e r a g e c a s e 和随机选择几何元两种方法都可以实现碰撞检测的计算效率和 准确性之间的平衡,但往往不适用于对碰撞检测精确性要求高的场景,然而对于那 些碰撞检测实时性要求高的场景,随机方法能够很好的实现。 1 2 硕士学位论文 m a s t e r st h e s i s 2 3 本章小结 本章对碰撞检测的相关知识进行了系统、条理性的整理、对比和分析,从其基 本概念、约束条件出发,深入探讨了当前碰撞检测领域的经典算法,当然随着计算 机图形学领域突飞猛进的发展,物体的形态将越来越复杂,也将产生越来越多可行 性强、性能更优的方法。 本章重点研究讨论了层次包围盒、空间分割、距离场、图像空间、随机方法等 这些常用的碰撞检测算法的思想、运用场景、适用对象、性能优劣。其中,层次包 围盒的使用最为广泛,经常与其它方法一起结合使用,目前也已经开发了诸多著名 的用层次包围盒实现的软件包。空间分割方法克服了物体本身复杂性的局限,但是 其仅适用于均匀分布且对象较少的三维空间,对于对象较多且分布不均的三维空间 算法效率将大大降低。距离场方法则克服了物体形态及拓扑结构的限制,平衡了计 算效率和准确度之间的矛盾。图像空间技术由于不需要对物体对象进行预处理,并 且也不要求对象特殊的拓扑结构,能够节省大量的时间,提高了算法的应用场景。 随机学方法能够很好的实现碰撞检测进程的实时性能,但是往往不适用于对碰撞检 测精确性要求高的场景,只能在精确性与实时性之间折中。 其实,在实际运用中,这些算法往往是融会贯通、混合使用的,不管怎样,最 终目标就是要使虚拟场景尽可能的真实,在实时性与精确性之间寻求最优的平衡 点。 3 1 粒子系统 第3 章基于粒子系统的碰撞检测算法 1 9 8 3 年,r e e v e s 首次提出了粒子系统【3 3 1 ,已有许多利用粒子系统来模拟自然现 象的研究工作,例如液体的流动、草地的模拟、鸟群的飞行【3 4 j 等,也可用来确定动 画角色的位置,粒子系统现在已经成为一种模拟物理现象【3 5 1 的标准建模方法。粒子 系统方法的基本思想是将许多简单形状的粒子作为基本元素聚集起来,形成一个不 规则的模糊物体,从而构成一个封闭的粒子系统。 粒子系统是许多粒子的集合,基本特征是具有质量,其动力学运动规律通过差 分方程组的解实现,利用物理规律可以得到这些差分方程。粒子系统已被应用于许 多领域,尤其在流体动力学领域,如湍流现象等。在这些应用中,粒子的位置就由 其动力学规律确定,然后,我们在每一个粒子的位置上放置一个图形对象并应用纹 理贴图来代替粒子本身,例如烟花模型的模拟中,粒子就可以用一个彩色的点渲染。 通过这种方法,我们就可利用粒子系统实现三维物体对象的模拟。 3 1 1 粒子的属性 粒子系统是一个不断有新粒子加入,并有旧的粒子消亡的动态运行系统,粒子 可随系统的运行改变其位置、形状,同时,粒子数目等也会不断发生变化。粒子系 统中的每个粒子都有类似位置、速度、颜色和能量等属性,用户根据具体应用的需 求自定义粒子的属性组。 一个粒子系统是不断进化的。在生命期的每一刻,都要完成以下工作,如图3 1 所示: 1 4 图3 1 粒子生命周期结构示意图 在确定了所有粒子的属性之后,就可以开始绘制进程。由于在一个粒子系统中 包含大量的粒子,这时若采用传统的画面绘制算法,就需要进行复杂的消除隐藏面 的计算。因此,r e e v e s 曾提出了一个专门针对粒子系统的的绘制方法,但前提是, 该方法是基于以下的两个假设: ( 1 ) 假设粒子系统所绘制的物体对象( 一般是自然景物) 不与其他物体对象相 交,即忽略了其碰撞现象的发生。将粒子系统对象与其他对象分为不同的子场景, 在绘制时考虑它们之间的前后关系,采用合成技术得到最终场景。 ( 2 ) 假设每一个粒子就是一个点光源,辅助调节整个场景的光亮度,由粒子 的颜色和透明度决定其大小。 由此可见,r e e v e s 所提出的粒子系统应用还不是很全面,最重要的原因就是其 没有考虑碰撞交互的存在,适用于简单的、不存在相交测试的场景。因此,该算法 具有一定的局限性。但是,从另一个角度来看,该算法无需任何排序操作、也不存 在消隐计算问题,从而很大程度上提高了算法效率。 3 1 2 粒子的状态及存储结构 根据当前系统中粒子状态的存储状况,可将粒子系统分为保存状态的粒子系统 和不保存状态的粒子系统。 对于不保存状态的粒子系统,可根据定义时状态的初始值及当前的时间,利用 一系列函数,来计算每个粒子当前的状态值。而对于保存状态的粒子系统,通过使 用数值及迭代积分的方法,根据前一帧粒子的状态值及场景的动态变化,计算当前 粒子的状态值。通常,在实际应用中,一般选取存取状态的粒子系统来模拟场景。 粒子的存储结构,一般是在系统运行时申请一片连续的缓冲区来存储所定义粒 子的各个属性值,在程序中可以使用一个类或结构体实现。这里要注意的是,各个 粒子的属性值是实时更新的,所以就迫切需要一种运行效率快、更新速度快的存储 机制,传统的存储结构显然不能满足其要求,本文将在第4 章具体介绍粒子存储结 3 1 3 粒子的运动模型 在整个粒子系统

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论