（计算机应用技术专业论文）实时流体交互性模拟算法的研究与实现.pdf

摘要 摘要 近几十年来，由于影视动画、虚拟现实和计算机游戏等领域的不断发展，基 于物理的计算机动画成为人们研究的热点方向，它通过探索真实世界中自然现象 的物理本质，利用计算机为物体建立精确的运动模型，从而更加逼真的表现物体 的形象和运动。但是，由于物理方程计算的复杂性，基于物理的计算机动画总是 存在耗时严重的问题，满足不了许多对时间要求较高的图形学应用领域的要求。 本文以基于物理的流体实时动画作为研究目标，试图在物理模拟的真实感和效率 之间寻求一个良好的平衡点，从而满足计算机游戏领域的需求。 基于物理的建模已经成为计算机图形学域非常活跃的研究方向。本文介绍了 具有代表性的基于物理的流体建模方法，包括欧拉法、拉格朗日法、平滑粒子流 体动力学等。讨论了相关连续现象的模拟，如流体、群体动画等。 本文对这一课题的研究主要集中在以下两个方面： 第一，提出基于平滑粒子流体力学的自由界面流体模拟方法，采用了范德瓦 尔斯方程与粒子间短距离排斥力和长距离吸引力作用的表面张力，设计出基于 g p u 的粒子泼溅算法。渲染算法完全消除了时间离散假象，具有交互式的高质量 渲染效果。与传统拉格朗日算法相比，该方法具有简化的表面张力模型，快速的 渲染方式，大大减小了运算的复杂性，有效提高了系统的运行速度。另外，本文 还介绍了一种模拟中小尺度不可压缩性粘性流体与固体耦合的新方法。为呈现生 动的流体动画效果，使用光滑粒子流体动力学方法，模拟中尺度流体的运动；在 此基础上，进一步研究小尺度流体在固体表面的吸收和依附现象。主要使用吸收 方程和线性弹簧缓冲阻尼模型来构建液体的渗透和依附效果，真实模拟出流体缓 慢渗透进入固体过饱和状态，以及飞溅流体附着于固体表面的真实感运动过程。 这种方法有效的解决多尺度流体与固体耦合在宏观与微观真实感模拟上的问题。 它兼顾了系统对真实感和实时性两方面的要求。 第二，运用流体的思想，提出超大规模群流动画的算法，深入研究了针对随 场景复杂性、群体行为多样性和群体角色数量增加而出现的问题，采用基于流体 运动的物理模型来解决以上问题。该算法使用一个全局的动态势能场来驱动人群 的运动。这个动态势能场同时考虑了人群的密度、人群的速度、地势高低以及舒 适度的问题，将局部的碰撞避免和全局的路径控制结合在一起，但要求以组为单 摘要 位进行模拟，每组内的个体拥有相同的运动特性，并且在二维环境中进行模拟。 另外，还考虑了群体的一些智能行为，主要有碰撞避免、交通灯模拟、坡地模拟 以及火焰喷发等交互性场景。 关键词：基于物理的建模，流体动画，群流动画，平滑粒子流体力学，流固耦合， 多尺度流体，动态势能场 i i a b s t r a c t r e c e n t l yp h y s i c a l l yb a s e dc o m p u t e ra n i m a t i o ni sa l w a y s ah o tt o p i ci nc o m p m e r 伊印k c s ，e s p e c i a l l yi nt h es p e c i a le f f e c t si n d u s t r y f o rf i l m sa n dg a m e s p h y s i c a l l y b a s e dm o d e l i n gi su s e dt ob u i l dp r e c i s em o v e m e n tm o d e lf o ro b j e c t su s i n gc o n l p u t c r t l l r o u g he x p l o r i n gp h y s i c a ln a t u r eo fn a t u r a lp h e n o m e n ai nt h e r e a lw o r l d ，a n dt h e n s i l n u l a t e o b j e c t s m o v e m e n tm o r er e a l i s t i c a l l y h o w e v e r , t h ec o m p l e x i t y o ft h e p h y s i c a lc o m p u t a t i o no f t e nl e a d st os e r i o u sp e r f o r m a n c ed e g r a d a t i o n ，s oi tl sn e c e s s a 巧 t oi n v e s t i g a t eo nt h ea c c e l e r a t i o nt e c h n i q u e s t h i sp a p e ra i m st os o l v e t h ep r o b l e mb y s e e k i n gf o rat r a d e o f fb e t w e e nt h er e a l i s t i ce f f e c t sa n d r e a lt i m ep e r f o r m a n c e ，t om e e t t h en e e d sf r o mc o m p u t e rg a m e s p l a y s i c a l l yb a s e dm o d e l sh a v eb e e np o p u l a r i nc o m p u t e rg r a p h i c sc o m m u n i t y in e m o s ts i g n i f i c a n tc o n t r i b u t i o n sh a v eb e e np r e s e n t e d ，w h i c hp r o d u c es u c hp e r c e i v a b l y r e a l i s t i c 踟：l i r n a t i o i l s ： e u l e rm e t h o d ，l a g r a n g em e t h o d ， s m o o t h e d p a r t i c l e h v d r o d y n a m i c s ，a n de t c w e a l s om a k eac o n n e c t i o nt ot h es i m u l a t i o no f0 也e r c o n t i n u a , s u c ha sf l u i d ，c r o w df l o wf o rc o m p l e t e n e s s t h i sp a p e rf o c u s e so nt h es t u d yi nt w oa s p e c t s ： 1 w ep r o p o s e da na p p r o a c hb a s e do ns m o o t h e d p a r t i c l eh y d r o d y n a m i c st os i m u l a t e f l u i d s 、加廿l 丘c es u r f a c e s ，w h i l es u r f a c et e n s i o nw a s m o d e l e db yu s i n gav a nd e r w a a l se q u a t i o no fs t a t e w i t hac o m b i n a t i o no fs h o r t - r a n g er e p u l s i v e 如d i o n 呈r e r r 龃g ea t t r a c t i v ei n t e r a c t i o n sb e t w e e nf l u i dp a r t i c l e s ，f i n a l l y d e s i g n e da g p u - b a s e dp a r t i c l es p l a t t i n ga l g o r i t h mf o rr e n d e r i n g t h i sa p p r o a c hc o m p l e t e l y a v o i d st 1 1 et e m p o r a ld i s c r e t i z a t i o na r t i f a c t s ，w h i c hr e s u l t si nt h ei n t e r a c t i v eh i g h q u a l i t yr e n d e r i n ge f f e c t s i nc o n t r a s tt ot r a d i t i o n a ll a g r a n g i a na p p r o a c h e s ，t h i s m e t l l o du s e st h es i m p l i f i e ds u r f a c et e n s i o nm o d e lw i t hf a s tr e n d e r i n ga l g o r i t h m , r e d u c e st h ec o m p l e x i t yo ft h es i m u l a t i o na n de f f i c i e n t l ya d v a n c e st h em - t i m e s p e e d f u r t h e r m o r e ，t h ep u r p o s eo ft h i ss t u d yi s t op r e s e n tan o v e lm e t l l o dt o r s i i n u l 触gm i d d l e - a n ds m a l l - s c a l ed e t a i l so fi n c o m p r e s s i b l ev i s c o u sf l u i d sa n d s 0 1 i dc o u p l i l l g t oa n i m a t et h ef l u i dm o d e l ，t h es m o o t h e d p a r t i c l eh y d r o d y n a m i c s i l i a b s t r a c t ( s p h ) m e t h o dm o d e l st h ef l o wa sap a r t i c l es y s t e mi nm i d d l e s c a l e ，a n db a s e do n i t ，t h er e s e a r c hf o c u s e so nt h ei n t e r a c t i o nb e t w e e nw a t e ra n ds o l i ds u r f a c e ， e s p e c i a l l yt h ee f f e c t so fa b s o r p t i o na n da d h e s i o n t h ea b s o r p t i o ni ss i m u l a t e db y a b s o r p t i o ne q u a t i o n s ，a n dt h ea d h e s i o ni ss i m u l a t e db yal i n e a rs p r i n ga n dd a s h p o t m o d e l ，w h i c hc a ns i m u l a t et h ea d h e s i v ef o r c e t h ep r o p o s e dm e t h o dw o r k s h e r et o r e a l i s t i c a l l ya n i m a t et h ew a t e rg r a d u a l l yp e n e t r a t i n gi n t ot h es o l i do b j e c t ，a sw e l l a ss o m em o v e m e n t so fr u n o f fa n df l a s h i n gw a t e r t h i sn e wm e t h o dt h u si m p r o v e s e x i s t i n g f l u i ds i m u l a t i o n s ，m a k i n gt h e mc a p a b l eo fg e n e r a t i n gn e wk i n d so f m u l t i s c a l ei n t e r a c t i o n sw h i c hh a v en o tr e a l i z e di nt h ep r e s e n tr e s e a r c h e s e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a to u rm e t h o di ss a t i s f a c t o r ya n di se f f i c i e n t e n o u g ht om e e tt h ed e m a n d so fr e a l i s t i ca n dr e a lt i m ei nc o m p u t e rg a m e 2 ，f o c u s e do nt h ea l g o r i t h mo ft h er e a l - t i m ec r o w da n i m a t i o ni nl a r g e - s c a l ea n d s i m u l a t e dt h er e a l t i m ed y n a m i cs c e n a r i o r e s e a r c h e di nt h ek e yt e c h n i q u e so f r e a l t i m ec r o w da n i m a t i o n , e s p e c i a l l yo nh o wt oe n h a n c et h ee f f e c to fr e a l - t i m e s i m u l a t i o na n dr e n d e r i n gs p e e di nv e r yl a r g e - s c a l e t h i sa l g o r i t h mu s e st h eg l o b a l d y n a m i cp o t e n t i a lf i e l dt od r i v et h ec r o w dt om o v e m e a n w h i l e ，t h i sm o d e l c o n s i d e r st h ef a c t o r so fp e o p l e sd e n s i t y , v e l o c i t y , t o p o g r a p h y , a n dd i s c o m f o r tf i e l d o u ra p p r o a c hu n i f i e sg l o b a lp a t hp l a n n i n ga n dl o c a lc o l l i s i o na v o i d a n c ei n t oa s i n g l eo p t i m i z a t i o nf r a m e w o r k o u rf o r m u l a t i o ni sd e s i g n e d f o rg r o u p sw i t h c o m m o ng o a l s ，w h e r ee a c hp e r s o n sf e a t u r ei sd i f f e r e n ti nt h eg r o u p t h es y s t e mi s i m p l e m e n t e di n t h e2 de n v i r o n m e n t m o r e o v e r , w er e g a r ds o m ei n t e l l i g e n t b e h a v i o r so ft h e c r o w d ，s u c h a sc o l l i s i o na v o i d a n c e ，t r a f f i cs i m u l a t i o n , t o p o g r a p h i c a lm o v i n g ，a n df i r ea v o i d a n c es i m u l a t i o n s ，e t c k e yw o r d s ：p h y s i c a l l yb a s e dm o d e l i n g ，f l u i da n i m a t i o n ，c r o w df l o wa n i m a t i o n , s m o o t h e dp a r t i c l eh y d r o d y n a m i c s ，f l u i d s o l i dc o u p l i n g ，m u l t i s c a l ef l u i d ，d y n a m i c p o t e n t i a lf i e l d w 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：鲑查 日期妒降j 月习日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规 签名：鲑查查 导师签名 日期：咔r 月习e l 第一章绪论 1 1 课题来源 第一章绪论 本文是基于物理的实时流体交互性算法研究与模拟，是以国家8 6 3 项目“支 持数字媒体内容创作的集成环境 ( n o 2 0 0 6 a a 0 1 2 3 3 5 ) 和国家8 6 3 项目“虚拟 环境下群体动画实时模型与绘制技术 ( n o 2 0 0 7 a a 0 1 2 3 2 2 ) 为依托研究开发的。 前者是该项目的主要任务为构建能够支持动漫、游戏、数字影视等数字媒体产品 开发的创作工具集和通用引擎。支持多种媒体融合的建模技术、高效的数字媒体 渲染服务新技术。后者是研究关于群体动画的若干关键技术，目标是构建一个群 体动画引擎模块，在我们已开发的三维图形引擎基础上增加群体动画控制模块， 实现群体行为验证演示系统。 1 2 课题背景和研究意义 当今，计算机动画研究已经成为计算机图形学的一个分支，是计算机图形学 和人类艺术相结合的产物。伴随着计算机图形算法和硬件技术的高速发展，它综 合利用计算机科学、数学、物理、艺术和相关学科的知识在计算机上生成绚丽多 彩的、真实感很强的虚拟画面，给人们提供了一个充分展示个人想象力和艺术才 能的新舞台。 一直以来，计算机动画都处在研究的前沿，人们不仅需要图形的真实感模拟， 而且也需要运动的真实感模拟。但是，真实感运动的复杂度往往较大，使得人们 难以用一些过程来实现，这个时候只有借助于利用真实世界的物理规律才能得以 表达。真实的现象一般都是基于物理学理论而产生的，物理描述了物体的运动规 律以及物体之间的相互影响。但是，首先，世界上的有些物理规律本身就很复杂， 并不能很好的用物理知识来描述自然现象，所以这些对应的学科发展也尚不成熟， 因此，在计算机图形学领域人们也很难建立一个比较完善的物理模型来表达自然 现象；其次，即使存在一个模型可供利用，但往往与计算机图形学的研究目标不 相符，或者是由于计算的复杂度，或者是与视觉上的效果并无关系，从而导致直 接应用比较困难。总之，这些因素都使得计算机动画的研究充满艰辛与挑战。 电子科技大学硕士学位论文 据研究表明，基于物理的计算机动画的优点在于：一方面，使得本身体现的 现象能充分满足人们对真实感的需要，来提高整个沉浸感；另一方面，减轻了程 序开发人员和艺术家的劳动强度和工作量，这样就不再需要单独去管理每一个细 小事件，不再需要脚本去控制物体，因为所有的事情都会按照它本身的物理规律 来实现和完成。其中包括：物体的材料属性( 如密度、表面粗糙度、弹性、硬度、 渗透性、吸收率、依附性等) 、刚体动力学和碰撞检测，关节和弹簧、流体、气体、 粒子系统、烟雾、布料等各个方面，这些目前不仅在电影特效和广告制作中得到 广泛应用，在新的一代计算机游戏中也正迅速普及开来。 但是，在实时性的要求方面，使得物理的计算面临很多的难题。一方面，要 求提高现有平台的计算能力，例如：需要高速的c p u 、较大的内存容量，以及最 新的图形硬件等；另一方面，要对算法本身进行优化和改进，从而提出模拟更加 逼真、速度更快的优秀算法。 本文首先基于物理的流体模拟的发展概况，总结了该研究领域所采用的各类 研究方法，并结合具体现象的特点分门别类的进行详细阐述，总体上可以分为欧 拉法和拉格朗日法。本章还进一步讨论了相关的分类问题，如自由运动界面、小 尺度流体、混合流和多相流，流固耦合等。最后展望了未来发展的方向，从而使 流体模拟能够很好地满足当今人们对真实感、实时l 生以及灵活性的要求。 然后研究了逼真的流体运动。提出基于平滑粒子流体力学的自由界面流体模 拟方法，采用了范德瓦尔斯方程与粒子间短距离排斥力和长距离吸引力作用的表 面张力，设计出基于g p u 的粒子泼溅算法。渲染算法完全消除了时间离散假象， 具有交互式的高质量渲染效果。与传统拉格朗日算法相比，该方法具有简化的表 面张力模型，快速的渲染方式，大大减小了运算的复杂性，有效提高了系统的运 行速度。 接着以中、小尺度真实感流固耦合动画模拟为主要研究内容，提出基于物理 模型的新型模拟算法。依据流体与固体交互作用的视觉效应，重点研究流固耦合 运动和小尺度液体依附与渗透作用模拟方法，提出独立于图形渲染引擎的真实感 流体动画模拟算法。在涉及流固耦合边界运动的模拟中，提出液体依附与渗透作 用的模拟，充分考虑小尺度流体与固体作用的微观物理模型，进而有效模拟固体 表面薄膜流体的细节运动，和流体渗透作用下固体物理属性的真实感变化过程。 该算法的研究工作取得了真实的流固耦合模拟效果，为基于物理的流固动画模拟 提供新的思路，必将有助于推动计算机动画研究的进程，为高沉浸感交互式虚拟 现实技术的应用推广奠定基础。 2 第一章绪论 最后，运用流体的思想，提出超大规模群流动画的算法，深入研究了针对随 场景复杂性、群体行为多样性和群体角色数量增加而出现的问题，采用基于流体 运动的物理模型来解决以上问题。 1 3 国内外研究现状 据资料显示，基于物理模型的造型研究的提出可追溯到2 0 世纪8 0 年代中叶， 但是正式提出此术语是在2 0 世纪8 0 年代末的s i g g r a p h 会议上，r o n e nb a r z e l 和a l a nb a r r 做了一个名为“t o p i ci np h y s i c a l l yb a s e dm o d e l i n g ”的报告，从此基 于物理模型的方法得到了世界广泛的关注。 简要的来讲，基于物理的造型方法的基本思路是：用物理规律控制物体的运 动，然后用图形学方法把物体形状渲染出来。由于物体的运动是遵循物理规律的， 所以动画里物体的动态逼真性可以得到有效的保证。另外一个优势是基于物理模 型的方法可以自动产生逼真的细节性动作，用户可以不具备艺术家那样的高雅艺 术修养，也可以轻松地制作出逼真的动画效果。 本文主要侧重于以下几个方面：基于物理的流体模拟；流体模拟，即基于g p u 的无网格流体实时渲染和多尺度流体的真实感模拟；以及群体模拟，即超大规模 群流动画的实时模拟。下面三个小节中我们将逐一作一个简单介绍。 1 3 1 基于物理的流体模拟 基于物理的可变形体动画是计算机图形学分支之一，从文献 1 对弹性物体的 模拟至今已发展了2 0 多年。这项跨学科领域含盖了牛顿动力学，连续介质力学， 数值计算，微分几何，矢量计算，逼近理论和计算机图形学等。基于物理的可变 形物体建模包含对象建模，断裂力学，弹塑性，布料动画，流体模拟，时程积分 策略，偏微分方程的离散与数字解法，形式化分析，时空适应性，多分辨率建模 等。从建模的观点来分析相近应用的不同物理建模方法，包括两大类：欧拉法和 拉格朗日法。欧拉法中在固定不变的点集上求解模型的属性，拉格朗日法的模型 包含位置和属性不断变化的点集。本文主要的研究是基于物理的流体模拟计算机 动画，其涉及的范围比较广，主要有：烟雾、火焰、流体运动、起泡、波浪等现 象。这些现象的模拟主要是运用流体动力学( c f d ：c o m p u t a t i o n a lf l u i dd y n a m i c s ) 的相关理论和方法。这个领域的研究将成为今后计算机动画的发展热点话题。 3 电子科技大学硕士学位论文 1 3 2 流体模拟 计算机动画的流体模拟的兴起基于文献 2 】，其使用有限差分方法在欧拉网格 上求解纳维一斯托克斯方程来模拟流体运动。该方法将烟看作无质量粒子在网格上 对流，并扩散到附加的温度域中；另外还定义了烟的热浮力，进而增强涡旋效果。 此外，采用标量密度场定义烟粒的数量【3 】，通过引入无条件稳定性的半拉格朗日 方法和隐式求解法改进了算法【2 1 。增添温度域和可变粘性项到固体模型中【4 j ，进 而可以模拟出固体熔化到液体的过程。该模型由无质量粒子构成，运用泼溅技术 构建用于渲染的表面网格。将刚性物体投影到欧拉网格上，模拟刚体与流体的交 互运动【5 】，刚体运动的求解步骤穿插于流体方程的求解过程之中。 在图形学中首次采用水平集模拟流体边界的算法出自文献【1 。水平集是额外 的纯常量，保存每个网格点到流体表面的有符号距离。该方法存在高分辨率细节 的丢失的问题，但采用粒子水平集技术【6 】来增强细节。该技术运用大量的粒子来 修补水平集，并随流体表面被动地进行对流运动。 平滑粒子流体力学方法s p h ( s m o o t h e dp a r t i c l eh y d r o d y n a m i c s ) 是近2 0 多年 来逐步发展起来的一种无网格方法，该方法的基本思想是将连续的流体( 或固体) 用相互作用的质点组来描述，各个物质点上承载各种物理量，包括质量、速度等， 通过求解质点组的动力学方程和跟踪每个质点的运动轨道，求得整个系统的力学 行为。平滑粒子流体力学属于拉格朗日法，首次引入计算机图形学便模拟了火和 其他气态现象【7 】。文献 8 】根据高斯积分在固体表面上引入幽灵粒子来模拟拉格朗 日流体与网格可变形固体的交互边界。这类似于物理学中的粒子云( p a r t i c l e i n c e l l ) 模拟，从原理上说，只要质点的数目足够多，就能精确地描述力学过程。虽然在 s p h 方法中，解的精度也依赖于质点的排列，但它对点阵排列的要求远远低于网 格的要求。由于质点之间不存在网格关系，因此它可避免极度大变形时网格扭曲 而造成的精度破坏等问题，并且也能较为方便的处理不同介质的交界面。s p h 的 优点还在于它是一种纯l a g r a n g e 方法，能避免e u l e r 描述中欧拉网格与材料的界 面问题，因此特别适合于求解高速碰撞等动态大变形问题。文献 9 扩展了传统的 s p h ，能有效地模拟沸腾的开水，液体中包围的空气，熔岩灯运动等现象。由于 移动立方体方法的使用，往往带来明显的时间离散假象。并且，s p h 方法主要应 用于中尺度的流体模拟，对于本文将要研究的小尺度流体的运动模拟无法实现。 对于流体流动导致的物体表面效果的变化，文献 1 0 】采用粒子模型模拟了流 体冲刷物体表面后的效果，其中采用吸收模型计算出表面对水的吸收，采用沉积 4 第一章绪论 模型计算出各种物质的输运沉积效果。文献【1 1 模拟了石头在天气的作用下发生 的腐蚀效果，计算出湿度在物体表层以下的渗透扩散过程，天气条件作为边界压 强条件传递给压强扩散方程，从而求出湿度往表层以下的渗透速度，计算出矿物 质的溶解和再循环过程。但是他们模拟的都是一种作用的长期效果，而且没有模 拟表面流体的运动情形，没有考虑外部水流本身会对物体表层的影响。文献 1 3 】 模拟了水、烟和细薄可变形、以及刚性固体的耦合效果，但是未能解决物体在吸 收液体时的外部表面变化情况，以及液滴依附在物体表面的问题。 1 3 3 群体模拟 一直以来，大规模群体动画的模拟与实现都是极具有挑战性的问题，即便是 对于当今具有多个快速处理器、多个高速存储资源和强大的图形处理卡的p c 系 统来说，大规模群体动画的实时模拟和渲染仍将是个比较艰巨的任务。一方面， 要求渲染的群体具有较强的真实感，另一方面，又要求能提供交互性，满足实时 性的要求，这些都远远超过了计算机的硬件绘制能力，从而只有在软件和算法上 进行改进和加强。 目前，在群体动画模拟方面的研究主要分为以下两种方法：基于个体的方法 ( a g e n t b a s e da p p r o a c h ) 和基于非个体的方法( n o n a g e n t b a s e da p p r o a c h ) ，也就是采 用群流( c r o w df l o w ) 的思想。 基于个体的方法的优点在于：可以体现每个个体的不同属性，如：运动的各 向异性、有各自的决策和目标位置、更容易适应局部因素等。缺点在于：每个个 体的计算复杂性比较大。在大规模群体动画中，实时性、真实感都会受到个体的 数量增加所带来的影响。 基于群流的方法的优点在于：大大降低了大规模群体的计算复杂代价，把整 个群体看作是一个运动的流体，但是它在个体的属性体现力上不是很充分。 1 3 4 可编程图形硬件技术 计算机图形硬件正在以令人不可估量的速度发展。计算机游戏引擎技术和真 实感渲染技术的展示都需要通过g p u ( g r a p h i cp r o c e s s i n gu n i t ) 来进行。g p u 是 图形显示卡的核心，自从2 0 世纪9 0 年代末n v i d i a 首次提出g p u 的可编程这 一概念开始，无论是在g p u 的架构还是功能上都发生了巨大的改变，特别是其 3 d 渲染流水线，经历了由固定功能管线到强大的可编程功能管线的革命性转变。 5 电子科技大学硕士学位论文 g p u 从一开始就由于其特殊的应用( 渲染) 而具有高度的并行性，并且其变化速 度甚至超过了c p u 的演变：g p u 的运算能力每6 个月就提升一倍，每1 8 个月就 经历一次架构的改变。 1 3 4 1 可编程管线 现今，图形硬件设计上最明显的趋势和优势是在图形处理器内提供更多的可 编程性。就以图形处理器中的顶点和片元处理器为例，其已经从可配置转变为可 编程了。在图1 1 中，我们展示了一个可编程图形处理器的流水线。首先应用程 序把三维顶点数据( v e r t i c e s ) 送至l j 显卡的g p u 上，进行顶点处理，即是把三维的顶 点坐标从世界坐标系转换到屏幕坐标系中，并且计算每个顶点的光照，然后将二 维的屏幕坐标送入组合图元阶段，依据顶点的连接关系集装成图元。接着将这些 图元光栅化成片元，最后送入片元处理单元中处理，并将处理结果写入帧缓存中， 显示到屏幕上。这个过程就是可编程管线的处理流程。 应用程序 a p p l i c a t i o n c p l j 1 ， g p u 聪她l h a 1 h 兰e m 薰b 重l eh i r a l 煳t e r i z a 化t ih p 版i x e ls 她h a d e r v e r t e x s h a d e rr a s t e r i z a t i o n p i x e ls h a d e r ip n m l t l v e s 上 帧缓存 f r a m eb u f f e r 图1 1 可编程管线图 在图1 1 中，可编程的部分是用灰色表示的，包括顶点处理单元和片元处理 单元。顶点处理单元的功能是实现顶点的光照计算和坐标变换。在现在的可编程 图形硬件中，用户可以通过编程设计并实现自己所需的光照模型和坐标系转换计 算公式。而过去的硬件只能实现一些固定的光照模型和坐标系计算，即是当应用 程序完全使用默认着色器程序时，这个流水线就叫做固定管线。 片元处理单元的功能基本上包括了所有光栅化以后的操作：采样纹理、雾化 效果计算和颜色混合计算等。在片元处理器中，允许采用多种纹理访问方式，每 个像素的绘制信息( 如像素颜色值、纹理坐标等) 均保存在寄存器中，通过完成 寄存器之间的加法、乘法或者点积等运算操作，实现像素级的光照模型计算。而 6 第一章绪论 在传统图形硬件中每个顶点的纹理坐标需要通过人为来指定或者根据空间坐标来 计算。 1 3 4 2g p g p u 通用计算 人们不仅可以充分利用g p u 上提供的运算器来设计一些算法以实现图形硬 件的可编程性，而且可以通过整个渲染流水线来完成一定的任务。由于在流水线 中存在多个处理单元，即有一定的并行处理能力，从而可以加速某些运算。 由于g p u 变得日益强大，人们首先将图形流水线的某些处理阶段以及某些图 形算法，如局部光照计算，凸凹纹理映射绘制等，从c p u 向g p u 转移。这几年 来，基于图形硬件的通用计算( g p g p u ) 成为g p u 的应用之一，除了计算机图形学 本身的应用，还涉及到其它多个领域，已经成为一个研究的热点。 随着图形芯片的发展，基于g p u 的通用计算也随之发展起来。以前的图形卡 主要只是针对图形本身，如深度检测，光照计算、光栅化、反走样等等的应用， 虽然也出现了譬如说利用颜色来标示物体序号等的更为通用的应用。但可编程性 的普及才真正地使其全面开展起来。直到2 0 0 1 年g e f o r c e 3 的出现，使得顶点级 可编程( v e r t e xp r o g r a m ) 开始普及【1 3 】。2 0 0 2 年，人们把t e x t u r es h a d e r 与r e g i s t e r c o m b i n e r 相结合起来来求解扩散方程【1 4 】，到了2 0 0 3 年，人们就开始利用像素程 序来求解一般代数问题，甚至是优化问题的求解和偏微分方程组( p d e s ) 求解【l 5 1 。 显然，g p u 在通用计算的应用将越来越广泛【l6 】。 1 4g p u 渲染加速算法 一直以来，拥有足够强大的计算和处理能力是人们对于计算机的一个最大的 理想。在实时渲染中，具有更高的分辨率，更高的帧率和更复杂的场景物体是评 价其性能的三个目标。现今，1 6 0 0 1 2 0 0 的分辨率足以满足人们的要求，6 5 8 5 帧率的速度通常认为是较为理想的。而在场景的复杂度上没有规定。所以，只有 更快更优的算法才能满足大规模场景的实时渲染的要求。在这一小节中，针对流 体的实时渲染，我们主要介绍如何运用细节层次( l e v e lo f d e t a i l ，l o d ) 技术来降低 整个场景的绘制复杂度。 细节层次( l e v e lo fd e t a i l 。l o d ) 是指使用具有不同细节的描述方法对同一个 场景或场景中的物体，从而得到一组模型，供绘制时选择使用。例如，一个所包 含的细节信息比较丰富的汽车模型，其中包含有上万个三角形面片，在不同的视 7 电子科技人学硕士学位论文 点使用不同的模型表示。当视点靠近物体时可以采用详细的细节表示t 相反地， 视点远离物体时，则用一种比较简单的模型替代。距离会使得简化后的模型近似 于细节比较丰富的模型，从而获得一个比较好的加速效果。 一般来说，l o d 算法包括生成、选择和切换三个主要部分。l o d 算法对场 景的处理的复杂性，使得我们不仅可以更加自由地去控制场景渲染，而且还能更 加方便地使用显卡的硬件加速功能。由于的特殊性即通常是个规则的矩形网格， 我们存运川l o d 算法的时候有一些特殊的技巧。地形( 水面) 的简化模式可以 有两种，如图1 ，2 和图13 ：规则的简化和非规则的简化。规则的简化通常是耵这 个矩形网格聚用自顶向下f u p 一1 0 d o w n ) 、分而治之的策略，典型的有二叉树和四 叉树的方法，即从场景的虽低细节层度开始按需要不断地提高细节。非规则的 简化通常是采用自底向上( d o w n t o u p ) 的方法来处理的，它的实现通常较少。 上述可知，其实l o d 算法并不很复杂，本文归纳其关键之处如下： 数据的存储布局：数据在内存中的布局必须要方便算法的实现，同时最好还要 降低操作系统缺页中断的次数，也就是降低内外存之间数据交换的次数。 如何生成连续l o d 化的地形( 水面) 网格：在地形l o d 化过程中，要实现平滑 的过度两个不同层度的细节的区域。 节点评价系统：系统必须要使生成的两格尽量少地产生几何形变，尽最的幢画 面质量能接近全分辨率时候的地形( 水面) ，同时还要保证实时性 图卜2 规则的简化 14 1 静态地形与动态地形 图卜3 不荆则的简化 地形的渲染通常分为动态和静态的两种。 静态地形的细节可以是均匀的，也可以是不均匀的。由于细节通常在事先就 计算好了，不均匀细节的静态地形也有许多的优点：即利用这种不均匀性的特点 来进行分层次的渲染，以有效提高真实感和实时性。以水面为例。对十起伏频繁 的水面使用较高的细节等级来渲染，平静的水面则可以使用较低的细节进行渲 第一章绪论 染。 动态地形是与视点相关的。它是本文将要研究和实现的方法。动态地形相对 于静态地形来说是一种更为先进的算法，其随着视点的移动，地形网格将被实时 更新。这样，就更加符合人的视觉特性：即看到的细节是变化的。但是动态地形 也有其弊端，那就是网格的建立和更新要耗费额外的时间，这就需要我们在精度 和速度之间选择一个合适的平衡点。动态地形网格的建立需要注意很多东西：细 节的决定，裂缝的避免，不可见的部分切除，乃至是几何形变也应该被考虑到。 动态地形在模拟实现的过程中对地形数据进行实时的改动，即可以修改内存 中的数据，也可以对原有数据库中的部分单元进行删除，并将新生成的元素有机 地存放进地形数据库，这样在模拟过程中生成新的地形数据库，以后的模拟运行 总是匹配更新后的地形环境，而不保留原有地形数据库的任何信息。 大规模场景中地形渲染运用最多的方法是基于高度图的3 d 地形渲染，其最 基本的原理就是，地形上各个点的高度值存于一个文件中( 高度图) ：渲染时， 把高度图中的高度数据设为顶点缓冲区中对应顶点的y 坐标值，那么自然就会产 生高低起伏的地形了。 1 4 2 算法基本思想 在提出基本的算法之前，为了简化模拟过程，本文必须对要渲染的地形做如 下的规定：地形必须是一个大小为( 2 。+ 1 ) ( 2 “+ 1 ) 的正方形区域，且具有均匀的采 样间隔。如图1 4 所示，采用四叉树的概念来描述一个多分辨率地形，每一个正 方形代表四叉树的一个节点，每个节点保存了一定区域的经纬度，中心点的高度， 边节点的高度等信息。每一个正方形被递归地不断地分割( s u b - d i v i d e ) 成相等的 四个区域，因为分辨率会随着分割的深度而提高。即分割深度每提高一层，采样 密度提高一倍。图1 5 演示了分割的过程。 c ae fai 、 飞i 夕 i l 图1 - 4 地形四叉树，a 区域为观察者能看见的范围 9 电子科技大学硕士学位论文 s u b d t 讲d e i e v e i1 图1 - 5 分割过程不意图 采用四叉树来表示多分辨率的地形有许多的优点，一个最直接有效的受益就 是裁剪，如图1 4 所示，其中a 区域为观察者能看到的部分。我们很容易知道观 察者能看到的只是a 区域所占的节点，其余的节点则根本不需要考虑。因此，我 们可以在节点递归分割的初期只花很少的代价就可直接把这些看不到的区域简单 地丢弃掉。 我们还要在地形的逻辑表示建立后后，再建立一个节点评价系统来判定何时 需要将一个节点继续分割或直接丢弃。当一个节点没有被继续分割或丢弃，则送 入渲染a p i 进行图元渲染。 1 4 3 数据存储与节点评价 在高度图里，地形数据通常以一个二维数组的形式存储在内存里。我们知道， 四叉树有着类似于二叉树的顺序结构。不同的是，这里采用二维数组而不是一维 数组。我们把全分辨率的地形数据存储在一个二维数组中，这样四又树节点的信 息( 9 个顶点的信息) 可以直接通过索引在数组中读取。同时我们还要建立一个 和这个地形数据数组大小相同的标志数组，其指示四叉树节点的状态。如果一个 节点需要被继续分割，则相应的位置标记为“1 ”，否则标记为“0 ”。如图1 6 所 示，标着问号的地方表示没有被访问到( 注意没有被访问到的地方的数值是不确 定的) 。 图卜6 地形标记数组 图卜7 地形渲染节点 接着，还需建立个评价系统，来决定对一个节点是否进行继续分割准确时 机。该评价系统主要两个部分构成：与视点相关的以及与水面( 地形) 本身的粗糙 程度相关的。所以，该系统的评价标准也围绕着这两个部分来构成。 1 0 第一章绪论 。j 穴 。d 图1 - 8 视点距离因素示意图 标准一，与视点相关。地方细节随着视点的拉近而增多，反之则减少。值得 注意的是，当我们将距离因素应用到一个节点的时候，还必须考虑到节点的大小。 因此，结合图1 8 我们如下的公式： l d 0 和 o 将界