（计算机应用技术专业论文）复杂流体场景的实时模拟研究.pdf

浙江大学硕士学位论文摘要 摘要 实时模拟具有复杂边界的大规模流体场景具有极其重要的研究与应用价值。 为了加速模拟具有较大规模的流体场景，并且能够实时地与复杂流体边界进行交 互，本文提出了一套可在通用图形处理器上并行计算的基于物理的流体模拟算 法。 本文第l 章介绍了大规模流体场景的模拟对人们现实生活产生的重要意义， 同时回顾了海洋学界和图形学界的研究历史以及相关理论与技术方面的研究进 展，并简要叙述本文的主要研究工作。 本文第2 章首先介绍了流体模拟的基本方法，然后阐述了基于物理的 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 p h 粒子系统进行非均匀的采样，从而在 减少流体模拟所需的粒子数的同时还保证了流体的模拟效果。接着提出了在采样 过程中处理复杂边界的方式以及非均匀采样时粒子的分裂与合并的准则。 本文第3 章提出了流体模拟过程中处理复杂边界和障碍物的方式。对本文提 出的基于体素化的两步法做详细的阐述。由于对场景的保守体素化方法几乎无关 于场景的几何复杂度，所以该算法可以明显地提高处理粒子与边界交互的速度。 本文第4 章提出了基于g p u ( 通用图形处理器) 的并行模拟算法。基于三维网 格划分的算法，加快了模拟过程中对邻域粒子的查找及其相互作用计算的时间。 关键词：流体模拟，非均匀采样的粒子系统，复杂边界，光滑粒子流体动力学， 流体与复杂边界的交互，基于通用图形处理器的并行加速算法，实时模拟 浙江大学硕士学位论文a b s t r a c t a bs t r a c t t h er e a l - - t i m es i m u l a t i o no fl a r g e - s c a l ef l u i ds c e n e sw i t hc o m p l e xb o u n d a r yi so f g r e a tv a l u ei nb o t hr e s e a r c ha n da p p l i c a t i o n t oa c c e l e r a t et h es i m u l a t i o no fl a r g c - s c a l e f l u i da n db ea b l et od e a lw i t hc o m p l e xb o u n d a r yi nr e a l t i m e ，w ep r e s e n tac o l l e c t i o n o fa l g o r i t h ma p p l i e dt ot h es i m u l a t i o no ff l u i do nu n i v e r s a lg p uw i t l lp a r a l l e l c o m p u t a t i o n i nc h a p t e r1 ，w ei n t r o d u c et h ec r u c i a ls i g n i f i c a n c eo ff l u i ds i m u l a t i o ni no u rd a i l y l i f e ，a tt h es a m et i m e ，r e v i e w i n gt h er e l a t e dw o r ki nt h ea r e ao fo c e a na n dc o m p u t e r g r a p h i c s ，a n db r i e f l yd e s c r i b i n gt h em a i na s p e c to ft h er e s e a r c ho ft h i sp a p e r t h e n ，i nc h a p t e r2 ，w ea r g u et h eb a s i ct h e o r i e so ff l u i ds i m u l a t i o n , e s p e c i a l l y f o c u s i n go np h y s i c a l b a s e ds 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 ) f l u i ds i m u l a t i o n m e t h o d w h a t sm o r e ，t h i sc h a p t e rr e p r e s e n t st h ec o n c e p to ft h en o n - u n i f o r ms a m p l e d p a r t i c l es y s t e ma n di l l u s t r a t e s am e t h o do fn o n u n i f o r ms a m p l i n gb a s e do nt h e f i e l d - b a s e dp a r t i c l er e s a m p l i n gf u n c t i o nw i t hg e o m e t r y , p h y s i c sa n dt h ed e n s i t yo ft h e n e i g h b o r h o o dp a r t i c l e s f u r t h e r m o r e ，w ee l a b o r a t ear u l et or e s o l v et h ep r o b l e mo f s p l i t t i n ga n dm e r g i n gp a r t i c l e s m e a n w h i l e ，t h ec h a p t e r3i l l u s t r a t e st h es o l u t i o nt od e a lw i t ht h em a t t e ro f c o m p l e xb o u n d a r ya n do b s t a c l e i na d d i t i o n ，t h em e t h o d ，n a m e db yt h ec o n s e r v a t i v e v o x e l i z a t i o n ，w h i c hi sh i g h l ye f f i c i e n to nt h ec o l l i s i o nd e t e c t i o nb e c a u s eo fl i t t l e c o n n e c t i o no ft h eg e o m e t r i c a lc o m p l e x i t y , i sa l s or e p r e s e n t e dh e r e f i n a l l y , i nc h a p t e r4 ，a na l g o r i t h mo fg p u b a s e dp a r a l l e lc o m p u t a t i o ni s p r e s e n t e d m o r e o v e r ，t h e m e t h o do ft h r e e d i m e n s i o n g r i d s u b d i v i s i o ng r e a t l y a c c e l e r a t e st h es e a r c h i n go fn e i g h b o r h o o dp a r t i c l e s ，a sw e l la s ，t h ec o m p u t a t i o no f i n t e r a c t i o na m o n g p a r t i c l e s k e y w o r d s ：f l u i ds i m u l a t i o n ，n o n - u n i f o r ms a m p l e dp a r t i c l es y s t e m ，c o m p l e x b o u n d a r y , 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 - c o m p l e xb o u n d a r yi n t e r a c t i o n ， g p u - b a s e dp a r a l l e la c c e l e r a t e da l g o r i t h m ，r e a l - t i m es i m u l a t i o n ， 浙江大学硕士学位论文 图目录 图目录 图1 1 流体场景在电影后天中的自然特效模拟2 图1 2 游戏孤岛危机中水面模拟场景3 图1 3 由暴雨导致的泥石流的真实场景3 图2 1 用f f t 方法生成的水面高度图( 左) 以及对应法线图( 右) 1 0 图2 2 用高度场模拟的二维海面一1 1 图2 3 基于网格的欧拉流体模拟方法的示意图。1 2 图2 4s p h 方法图示16 图2 5a d a m s 等人在2 0 0 7 年提出的自适应s p h 算法的效果【2 0 1 一1 8 图2 6 自适应采样s p h 的算法效果【2 8 1 1 9 图2 7 均匀采样与非均匀采样s p h 的对比图示【2 8 1 2 0 图2 8 非均匀采样s p h 中邻域粒子的定义2 l 图2 9 流体的几何复杂度特征2 4 图2 1 0 非均匀采样的粒子系统图示2 6 图2 1 1 粒子分裂图示2 7 图2 1 2 粒子分裂时避免局部高压强2 7 图2 1 3 均匀采样与非均匀采样所需的粒子数量对比2 8 图2 1 4 均匀采样的粒子系统的流体模拟结果2 9 图2 1 5 卷浪的绘制结果2 9 图2 1 6 卷浪冲击大坝场景的模拟与绘制结果3 0 图3 1 刚体离散化成粒子3 3 图3 2 边界物的保守体素化3 6 图3 3 小溪场景的体素化。3 6 图3 4 粒子与网络的碰撞检测示意图3 7 图3 5 碰撞检测效率分析3 9 图3 6a r m a d i l l o 流体场景3 9 图4 1 基于g p u 的流体加速算法总体框架4 1 图4 2 邻域粒子查找结果存储方式。4 4 图4 3 基于g p u 的粒子重采样图示4 5 图4 4 算法步骤效率分析4 6 图4 5 小溪场景的实时模拟4 7 i 浙江大学硕士学位论文表目录 表目录 表4 1 各流体模拟场景的数值对比4 8 i v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝江太堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解浙江太堂有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签名： 签字日期：年月 日 签字日期：年月日 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 引言 本章主要阐述了此论文的选题背景，介绍了自然场景模拟特别是流体模拟的 重要应用及研究意义。回顾海洋学和计算机图形学领域对流体模拟研究的发展历 史及现状。最后，通过分析流体模拟研究现状中存在的一些问题，引出本文工作 的必要性。 1 2 自然场景模拟 本节简单介绍了自然场景模拟的研究意义，主要介绍基于物理的流体模拟， 由此引出本文选题的背景及意义。 自然场景的真实感实时模拟，被广泛地应用于现实生活中许多领域。自然场 景的模拟大致可分为以下几个不同的内容：地形地貌的模拟、花草树木的模拟、 自然气象现象的模拟( 比如：雨、雪和沙尘暴等) 、大气现象的模拟( 比如：烟 尘、彩虹和雨雾等) 和流体场景的模拟( 比如海洋、龙卷风和火烟等) 。其中， 特别是流体场景的模拟，在影视特效、电脑游戏、灾难营救、科普教育、体育竞 技、军事仿真等产业有着极其广泛的应用。因此，流体场景的真实感模拟，一直 是计算机图形学以及相关领域的研究热点和难点。 影视产业中，特效制作起着越来越大的作用。在新近放映的大片阿凡达 ( a v a t a r ) 中，精美惊险的3 d 特效制作吸引了全球无数影迷的眼球，其票房也达 2 0 亿美元左右的惊人高度! 并引发了全球追逐i m a x 银幕的狂潮。 融入流体模拟的计算机动画也频频成功应用于影视特效和电脑游戏中。“咆 哮的海啸飓风，百米高的滔天大浪瞬间淹没纽约 ，这就是耗资1 3 亿美元的美国 大片后天中用电脑特效营造的视觉效果，如图1 1 。如果没有电脑特效的帮 助，我们便无法欣赏到拥有此般震撼的自然场景的电影。从之前的未来水世界 到最近的( ( 2 0 1 2 世界末日，之间无数的与自然场景有关的电影在离开计算机制 浙大学论文第1 章绪* 作的影视特效的情况下，便很难取得成功。 乒j 、，? 。j 痨g 暂甜 k 。= 攀曼 鹱 图l l 流体场景在电影后天中的自然特效模拟 其次，随着计算机硬件，特别是图形显卡技术的不断发展，越来越多的游戏 制作公司在三维的游戏场景中加入了水、烟和风等流体相关的特效。从起初简单 的水面，到之后可与游戏人物交互的水面( 如半条命、孤岛危机等，见图 l2 ) ，再到后来用基于物理的水体模拟方法来模拟水的特效的( ( c r y o s t a s i s ，无一 不表明流体模拟对电脑游戏产业的巨大影响。 此外，流体模拟在灾难模拟与营救模拟中起着极其重要的作用。特别是对于 我国来说我国幅员辽阔同时遭受各种天气系统的影响，气候多变。同时我们地 壳变动性大地质结构较为复杂等等的这些原因使得我国是世界上自然灾害较 多的国家之一。地震、泥石流、山地滑坡频频发生。如图l3 。得利于流体模拟 的研究，可以模拟出这些自然灾害，为防灾救灾提供多一种方式。 另外，在军事模拟、体育竞技荨领域，流体模拟也占据着举足轻重的地位。 比如f l 赛车竞技中，工程师们也用流体模拟的方式来测试赛车的空气动力学部 蛰匪 渐 学硕士赴支第1 章绪论 件；在军事模拟中演示大风和海洋对导弹的影响等等 圉l2 游戏孤岛危机中水面模拟场景 圉1 3 由暴雨导致的泥石流的真实场景 浙江大学硕士学位论文第l 章绪论 1 3 国内外研究现状 目前，国内外关于流体模拟的研究主要分为基于海洋统计学的水面模拟，以 及基于物理的流体模拟两种，并且都已经有了相当多的研究工作。研究工作主要 侧重于流体的模拟速度、流体的物理模型、流体的边界检测模型和绘制效果的不 同部分。本节将综述计算机图形学中流体模拟的相关研究工作。 1 3 1 非物理的流体模拟的研究 早期的流体模拟的研究主要是基于非物理的过程式建模方式。在计算机图形 学和海洋学研究的相关文献中，最早描述水波运动的文章之一是f o u m i e ra n d r e e v e s i l j ，在这篇文章中他们通过一种称为深海小振幅的波来模拟水的表面。在 1 9 6 3 年，d u n t l e y 2 提出包含了与计算机图形学密切相关的海洋的一些光学数据。 幽n e 【3 】提出的模型根据海浪变化的圆周轨道来模拟海浪。泡沫和浪花由虚拟的 不规则的粒子系统来模拟，但他们只能产生比较简单的海浪，而且很难保证计算 与绘制的实时性。p e l i n e 利用合成的噪声来模拟海洋的表面【4 1 。m a s t e m 5 1 提出利 用f o u r i e r 变换来合成水波块的方法，之后将其无缝拼接成一个很大的海域。通过 很多正弦波的叠加，从而可以合成整个高度场。因为合成过程是符合海洋的统计 模型以及经验模型，并且使用了相当多的正弦波，因此用这种方法所得到的结果 就显得非常自然。k a s s 和m i l l e r t 6 1 通过简化水波方程提出了一个实时的波浪模型， 并且可以处理波浪的折射和反射。上述的方法都是将三维的流体模拟简化到二维 的高度场上，虽然模拟速度较快，但也存在着许多不足。首先，由于把流体映射 到了二维的高度场上，所以一个水平的位置只可能映射到一个高度，所以基于高 度场的流体模拟很难模拟翻滚的浪、水花泡沫等细节效果。其次，由于这种方法 本质上不是基于物理原理，所以其真实性不足，不符合许多流体的物理规律。由 于这些不足，对这类流体方法的应用有了一些限制，所以目前计算机图形学界越 来越多的学者开始研究基于物理的流体模拟。 1 3 2 基于物理的流体模拟的研究 在计算机图形学中，基于物理的流体模拟方法大致可以分为两类，即基于网 4 浙江大学硕士学位论文第l 章绪论 格的欧拉方法和基于粒子的拉格朗日方法。 早期的基于物理的流体模拟研究侧重于基于网格的欧拉方法【刀，这种方法通 过采用有限差分法在均匀的网格上求解n a v i e r - s t o k e s 方程来实现。1 9 9 9 年，s t a m 提出了基于半拉格朗日法求解n a v i e r - s t o k e s 方程【8 】，文章提出的半拉格朗日水平 对流求解方法由于它的无条件稳定性和易于被实现的优点，为之后许多流体模拟 研究奠定了良好的基础。f e d l d w 等人对s t a m 的方法所导致的较大能量耗消的问 题通过引入漩涡力限制得到了一定程度的控制1 9 】。另一个解决能量耗消的方法由 s e l l e 等人【1o 】提出，他们把拉格朗日机制加入欧拉求解方法中，通过加入漩涡粒子 来限制流体的运动。为了更精确地表示网格模拟的水面，f o s t e r 等人提出了p a r t i c l e l e v e ls e t ( 粒子水平集) 方法【l i 】，在流体模拟过程中把两个不同的粒子集分布于 由水平集函数表示的曲面的两侧，然后由这些粒子来检查模拟过程中产生的误 差，最后通过误差修正的方法更精确地表示流体表面。 虽然基于网格的欧拉法已经在计算机图形学领域被研究了许多年，并且应用 于诸多不同的领域，但是当我们想要在三维空间内模拟具有丰富细节的流体时， 基于网格的方法并不是一个非常好的选择。所以，最近计算机图形学领域中越来 越多的研究者开始研究基于拉格朗日的方法来进行流体模拟。其中，特别是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 ，即：平滑粒子流体动力学) 方法，由于可以模 拟更多的流体细节( 如泡沫、水花等) 和处理更复杂的流体表面，逐渐替代了欧 拉方法。 s p h 方法起初被提出用来建模宇宙论的流体1 2 , 1 3 】。1 9 8 3 年r e e v e s 首次将粒 子系统引入了计算机图形学领域【l4 1 。2 0 0 2 年m u l l e r 等人首次用粒子系统来模拟 水体运动【1 5 】。在他们方法的基础上，通过在网格上加入边界粒子的方法被扩展应 用于可交互的流体中【1 6 1 。随后，利用s p h 流体模拟方法模拟多相流、烟、水、气 泡、水花飞溅等效果的文章层出不穷【1 7 , 1 8 。 然而，上述这些工作均没有考虑到自适应采样的粒子系统，所以计算量较大， 特别当被模拟的流体需要非常多的粒子来拟合时更是如此。d e s b r u n 首先引入了 自适应采样的粒子系统框架【1 9 1 ，这个系统在时间和空间上进行粒子的自适应调 浙江大学硕士学位论文第l 章绪论 整，但是在整个自适应过程中只考虑了粒子系统的物理特性。a d a m s 在2 0 0 7 时 通过引入局部粒子特性函数把这个自适应框架用于水体的模拟凹1 ，但是他们所提 出的这个方法没有考虑到水体的物理特性，同时算法较难在g p u 上进行并行处 理。本文的工作就是在这些工作的基础上提出一个适用于g p u 并行计算的粒子 系统来模拟流体。 1 3 3 场景体素化的研究 计算机图形学中的体素化技术有着非常广泛的应用。1 9 8 6 年k a u f m a n 等人 在计算机图形学中引入了基于网格的三维扫描转换算法 2 1 1 。1 9 8 7 年k a u f i n a n 又 提出了关于参数化曲面、曲线和空间体的三维扫描转换算法【2 2 1 。体素化可分为两 大类：表面体素化和实体体素化。d a c h i l l e 等人在2 0 0 0 年提出了增量式的三角面 片体素化方法【2 3 1 ，这是表面体素化的方法之一。同为做表面体素化的还有s t o t l e 等人的一篇文章，提出了一个鲁棒的表面体素化方法 2 4 1 。s r a m e k 等人在1 9 9 9 年 提出了一种自由对称的实体体素化方法【2 5 1 。随后，h a u m o n t 等人提出了完全的由 多边形构成的场景体素化方法【2 6 1 。本文基于这些工作，把体素化算法引入流体边 界的检测中，从而加速了具有复杂边界的流体的模拟。 1 4 本文的工作 由于流体模拟可以广泛应用于科学研究、影视特效、电脑游戏、灾难营救、 科普教育、体育竞技、军事仿真等应用领域，因此对具有大规模复杂边界的流体 场景进行实时的模拟有着非常重要的现实意义。 在本文中，我们通过引入特性场函数对s p h 粒子系统进行非均匀地采样，从 而提出一套非均匀采样的粒子系统。本文流体模拟的主要工作分为如下3 项： 非均匀采样的粒子系统：包括特征场函数，非均匀采样系统以及粒子的 重采样准则。 流体与复杂边界和障碍物的交互：提出两步法来处理流体与边界的交互， 同时为进一步优化算法，提出了一个基于预处理的边界和障碍物的表面 细分步骤。 6 浙江大学硕士学位论文 第l 章绪论 基于g p u ( g r a p h i c sp r o c e s s i n gu n i t ，图形处理器) 的并行计算算法。 本文的主要内容组织安排如下： 本文第2 章，讨论了非均匀采样的s p h 流体模拟新方法。首先介绍了流体模 拟的基本方法，包括基于高度场的方法及基于物理的方法，着重介绍s p h 方法； 然后分析现有s p h 方法的不足，提出非均匀采样的粒子系统以及物理建模的基 础；并提出了采用特征场函数用来对原s p h 粒子系统进行非均匀的采样。最后提 出了在采样过程中处理复杂边界的方式以及非均匀采样时粒子的分裂与合并的 准则。 本文第3 章，提出了流体模拟过程中处理复杂边界和障碍物的方法。首先详 细阐述了基于体素化的两步法，然后介绍场景的二值保守体素化算法，以及精确 边界交互算法。 本文第4 章提出了基于g p u 的流体场景并行模拟算法，并对本文的流体模 拟新算法同其它算法进行分析和对比。 在本文的最后，作者对全文的研究工作进行总结，并提出了进一步可研究的 方向以及相关的内容。 7 浙江大学硕士学位论文第2 章非均匀采样的流体模拟 第2 章非均匀采样的流体模拟 2 1 引言 基于粒子系统的s p h 方法有利于模拟较为复杂的流体，处理几何拓扑变换较 大的流体表面，如卷浪、漩涡等。除此之外，s p h 方法还可以处理水花飞溅、水 泡和泡沫等流体细节，因为这些细节可以容易地用粒子系统来模拟。因此，在计 算机图形学界中越来越多的学者开始研究s p h 方法。对于一个流体系统，研究者 多数是从模拟的动画与流体的绘制两方面来考虑。尤其是对于流体动画的模拟， 一般着重于动画的真实性和模拟速度两方面。本文的工作主要是从模拟速度方面 着手，在s p h 算法上通过引入非均匀采样的s p h 算法来提高流体模拟的速度。 简单地说，在不降低流体模拟效果的同时，通过减少模拟流体所需粒子数从而加 快流体模拟的速度。 本章首先介绍流体模拟的基本方法和理论基础，然后介绍非均匀采样的s p h 以及在非均匀采样的情况下粒子间作用力的计算，接着阐述本文中非均匀采样的 规则，即特征场函数，最后介绍粒子重采样的规则。 2 2 流体模拟的基本方法介绍 早期的流体模拟的研究主要是基于非物理的参数式的过程式建模方式。由于 这种流体建模方式较难模拟复杂、细节丰富的流体效果，并且本质上不是基于物 理原理，所以其真实性不足，不符合许多流体的物理规律。因此，图形学界许多 研究者开始研究基于物理的流体模拟方法。基于物理的流体模拟方法，大致可以 分成两类，即基于网格的欧拉方法以及基于粒子的拉格朗日方法。 本节首先简单介绍基于高度场的二维流体模拟方法，然后介绍两种基于物理 的流体模拟基本方法：欧拉方法和拉格朗日方法两种。在拉格朗日方法中，着重 阐述目前广泛应用的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 ) 方法，它是本文流 8 浙江大学硕士学位论文第2 章非均匀采样的流体模拟 体研究工作的基础。 2 2 1 基于高度场的二维流体模拟 海洋学家通过观察获取了一些水体的统计模型【5 1 。在这些模型中，波浪的高 度被认为是关于水平位置和时间步长的一个函数，h ( x ，f ) 。统计学模型把波浪的高 度分解为多个正弦波和余弦波的组合。分解出来的波振幅具有良好的数学和统计 方面的性质。分解方法一般采用快速傅里叶变换。 基于快速傅里叶变换表示的水波高度场用h ( x ，f ) 来表示t 时刻在水平位置 x = ( x ，z ) 上的复数域上的所有正弦函数值的和： h ( x ，) = 万岳，力e 印( 岳r x ) 公式( 2 1 ) 在这个公式中，云是一个二维向量云= ( k x 蚴知等舡等舯聊满足 一譬刀譬和一了m 聊了m ，f 表示时间。f f t 生成了离散点( 鲁，堕m ) 上的高 度场。傅里叶部分的高度振幅万( x ，f ) 决定了流体表面起伏的形状。 通过对诸多海面上的浮标、照片以及雷达测量的统计分析发现，水波高度振 幅i ( x ，f ) 在基本是一个稳定且独立的高斯波动，可用以下空间域频谱公式来表示： 驰m 铲附 公式( 2 2 ) 流体的二维高度场通常根据指定空间分布形式的高斯随机数来生成，此生成 方法在傅里叶域中有着较好的表现。波浪高度的傅里叶振幅可以由以下公式得 到： h o ( k ) = 百1 ( 钉+ 晚) 厄丽 公式( 2 3 ) 其中，钉和是互相独立的均值为o ，标准差为l 的高斯随机数。使用高斯分 布的随机数符合海洋水波的实验数据。此时，水波在时间t 的傅里叶振幅可以被 表示为： 艿( 云，f ) = 瓦( 云) 唧u o ( i k l ) f ) + 蔚( 毒) 唧 一f 以i 纠) f ) 公式( 2 4 ) 9 堂垩盔兰堡三! 竺兰墨 量! ! 兰兰翌兰堂竺至竺苎型 这个公式通过将水渡“向左”和“向右”传播，从而保留了复共轭的性质。 由于基于快速傅里叶变换，当前的木渡高度场仅和当前的傅里叶振幅状态相关。 最终，我们可用此f f t ( f a s t f o u r i e r t r a n s f o r m ，快速傅里叶变换) 方法在水 平面上生成一个高度场块。通过重复平铺这个块便可建立一个庞大的水面，而且 在拼接的边缘是完全无缝的，从而达到一个巨大规模的海洋表面。虽然这种重复 的平铺会在绘制时造成周期性走样，但是只要这个块相对于可见区域来说是足够 的大，用户就很难感觉到走样。通常，我们把生成的高度场存入一张纹理，称为 高度图。高度图的太小和分辨率与被模拟的水面区域的分辨率相同，每个水面的 网格节点对应于高度图中的一个像素，以表示在此处水面的高度。高度图中的每 一个像素仅用来表示一个浮点数据( 即高度) ，因此高度图通常被表示成灰度图。 为了在g p u 上实现更高效的计算，我们直接由高度图生成与其相对应的法 线图。为了计算水面的光照，在绘制时必须得到每个网格顶点赴的法向量，从而 模拟水面的反射、折射等效果。其中，法线图的r g b 三个通道存放相关的法线 信息，即把法向量在三个维度上的信息分别存入纹理的r 、g 、b 三个通道，同 时在a l p h a 通道中存放顶点的高度值。这样不仅可以减少法向的计算量，还可以 减少纹理所占用的内存和显存空间如图2 1 。 擀 固21 用f 丌方法生成的水面高度图( 左) 以厦对应法线图( 右) 在获得高度图和对应的法线图后，我们只需要把高度图叠加到二维的平面网 * 学硕学t 论文弟2 章非均匀采样的流悻模拟 格上，并且在每个时问步长里动态地更新高度图以及对应的法向量等信息就可以 模拟基于高度场的海面，如图22 。 圈2 2 用高度场模拟的= 维海面 2 2 2 流体模拟的物理基础 基于物理的流体模拟，无论是基于网格的欧拉法还是基于粒子的拉格朗日 法，多数都是以n a v i e r - s t o k e s 作为基本的流体运动物理方程进行力的求解与模拟。 n a v i e r - s t o k e s 方程，是描述不可压缩流体的动量守恒运动方程，对于恒温、带有 滞粘性的流体，其基本的物理量有速度、质量以及压强。n a v i e r - s t o k e s 方程见公 式25 和公式26 ： “兰+ “v ) f = 一印+ 胛( v “) + ， 公式( 25 ) 讲 v “= o 公式f 2 6 1 其中，公式( 25 ) 中，p 为密度，“为速度，卢为粘滞系数，为外力。 描述动量守恒的公式( 25 ) 本质上是对流体应用牛顿第二定律。式子右侧表 浙江大学硕士学位论文第2 章非均匀采样的流体模拟 示作用于流体的合力，式子左侧是质量与加速度的乘积。对于流体来说，其加速 度是速度场的导数，见公式( 2 7 ) 。 面du ( f ，r ( 嘞= ( 昙+ 如v 卜 公式( 2 7 ) 公式( 2 6 ) 为流体的质量守恒方程，定义了速度的散度为0 ，以确保流体的 体积守恒。若加上此方程的限制则表示被模拟的流体是不可压缩的。对于密度的 实导数，可得公式( 2 8 ) 匀 等+ v ( 肛) = 0公式( 2 8 ) 优 在公式( 2 7 ) 中，当整个流体的质量密度是恒定的时候，也就是当坐：0 研 和刃u = v z ，时，那么流体被称为不可压缩流体。 2 2 3 欧拉方法 本节将简要介绍基于网格的欧拉流体模拟方法。在欧拉方法中，整个流体分 布于均匀的网格中，用网格中有序排列的节点来控制整个流体，如图2 3 。 tttttt -l- - - - 一 。t 。? f 一? 一坶+一一口 lii ”移i 。糍一i r # 帮一- ，? = 口n t-ytvt -ii， ， ： ，y 一 v1 rv -堪-，i蠢- l vvi，v- 司争唾，鸯 争 l-l ty_ v vt ； iil ，司 ，蠢- i j - 图2 3 基于网格的欧拉流体模拟方法的示意图 它将n a v i e r - s t o k e s 方程离散化于网格节点上，然后在每个时间步长中求解 1 2 浙江大学硕士学位论文 第2 章非均匀采样的流体模拟 n a v i e r - s t o k e s 方程以得到各个网格节点上状态量的变化，从而最终得到整个流场。 虽然欧拉方法可以很好的描述流体的许多属性( 比如密度、压强等) ，但流 体模拟的细节和表面的细节都是取决于网格的精细程度。采用2 5 6 2 5 6 2 5 6 的 网格，每帧也需要3 到4 分钟时间。为了提升流体的计算速度，l o s a s s o 等人提 出了八叉树等加速算法，但速度仍然不够理想。为了丰富流体的模拟细节，e n r i g h t 等人在网格的基础上，通过引入粒子水平集的方法在流体表面加入了粒子来跟踪 流体表面。因此，图形学界越来越多的流体研究工作者开始研究基于粒子的拉格 朗日方法。 2 2 4 拉格朗日及s p h 方法 本节首先简单介绍基于粒子的拉格朗日流体模拟方法。然后着重介绍代表拉 格朗日方法的s p h 流体模拟算法。 拉格朗日方法从分析流体的微团( 即粒子) 开始，分析粒子的速度、压强、 密度、粘滞力、漩涡力等参数，这些参数随着时间而变化，从而表示整个被模拟 的水体。 拉格朗日方法也采用n a v i e r - s t o k e s 方程来模拟流体的运动，公式( 2 9 ) 表示 的是其不可压缩的恒温流体的基本拉格朗日形式： p 警一v p + 2 f 公式( 2 9 ) 公式2 9 的右侧是流体内部力与外部力的加和，所以其作用力的数量场可以 表示为： f = i n 鲫耐+ 厂删硎耐公式( 2 1 0 ) 因此对于每个粒子i 的加速度可以表示为公式2 1 1 ： 铲车：曼 公式( 2 1 1 ) 铲言2 艿 公n 厶 其中a i 和”；分别是粒子f 的加速度和速度。e 是作用于粒子i 上所有力的合 力，p ，是粒子在其位置p ，处的质量密度。 整个流体由粒子来表示。每个粒子拥有自己的质量，在没有粒子合并或者分 1 3 浙江大学硕士学位论文第2 章非均匀采样的流体模拟 裂的情况下，可以保证质量守恒。所以其优点之一是容易表达整个流体的运动、 表面以及诸如气泡、飞溅的水花和泡沫等细节。但是用拉格朗日法模拟流体的速 度会随着粒子的增多而变慢。 2 241 质量密度 在拉格朗日方法中，其力的计算如压强、粘滞力等，都是在其粒子的质量以 及质量密度已知的情况下计算。其中，粒子的质量的是一个用户定义的数据，粒 子的质量密度是作用于整个流体中的一个连续的属性，必须在每个时间步长中计 算。所以在粒子f 处其质量密度为： 肛= m j w ( r 。- 5 ，办) 公式( 2 1 2 ) j 其中w 是s p h 方法中的核函数，m 是粒子的质量，h 是核半径的大小，是 粒子f 核半径内粒子的数量。，厂，分别为粒子i 与j 的位置。 2 2 4 2 内部力 内部力指的是那些仅仅在流体内部产生的力。比如：压强与粘滞力。其中压 强计算公式如下： 其压强核函数为： 粘滞力计算公式如下： 矿一一否半考v 吣功 蝴2 m ) 删= 等p 滞- 。 公式( 2 2 7 ) 9 ( 2 砌2 ) 7 2 在本文的- 1 作中，我们使用了m u l l e r 等【1 5 1 在2 0 0 3 以下的核函数： 炉丽3 1 5 , f l 2 一妒户浑- 0 。 2 0 0 9 年，延诃用f a s t m a r c h i n g 算法来估计每个粒子到表面的距离，从一定 程度上失去了高教的并行性。而我们通过两个独立的步骤处理了这个几何特征， 所以并行性较前者有很大的提高。另外，他提出的几何特性没有考虑流体与边界 碰撞时产生的局部高压强，所以会产生局部不稳定、粒子乱飞的现象。 因此，我们在模拟的过程中把流体与障碍物的边界也作为流体的表面来处 理。对于这些粒子的查找，首先采用体素化的方法来确定边界物的大概位置，随 后遍历所有粒子以确定哪些处于边界物附近( 体素化的相关理论与算法将于第3 章作详细阐述) 。因此对于流体几何复杂度的特征如图29 ： 百丽 3 d m a x3_辫obstacle v o ii o o ：o o l j o 圉2 9 流体的几何复杂度特征 2 4 2 物理特征 接着，我们开始研究影响流体效果的物理特性。 如果仅考虑流体的几何复杂度则不能够精细地模拟表面的形变状况。因此， 若在流体漾处分布的均是半径较大的粒子，