基于多重网格法的实时流体模拟

基于多重网格法的实时流体模拟，实时流体模拟，实现流体的多重网格绘制。7期周世哲等:基于多重网格法的实时流体模拟937长影响的特点3.其效率明显优于 Jacob和GS等restrict: I-IT, y)=I(2x -1, 2y-1) (5)固定网格步长迭代法Step4.误差延拓.将本层产生的解误差e传递到上层较粗网格,为了满足式(3)的二阶光滑性要求,我们使用双线对一维问题f=0,在步长为h的均匀网性插值,将粗网格中的一点延拓到上层细网格中相应位置以格上中心差分离散格式为及相邻的上右和右上的4个点e1+1= extend(e1)2u:+uf2其G-S迭代格式可写成I1+1(2x+1,2y+1)=I/(x,y)相应位置2-1-2lh-fI2+1(2x+1,2y+2)(I1(x,y)+I(x,y+1))上对于误差r=l1-2l,显然r;和u2具有同样的迭I+1(2x+2,2y+1)s1代格式r2-t-2n2+2+1=02(1(x,y)+(x+1,y)右若对误差作傅里叶展开将其第k重谐波分量记11(2x+2,2y+2)=(1(x,y)+L1(x+1,y+1)+为r(k)=Ae-1,An=1为该分量的振幅,可I2(x,y+1)+I(x+1,y)右上A"入5-4sh式(4),(5)中的L(x,y)表示L层网格上位于第x列,第yλ|代表该谐波振幅的衰减速度,||越小,该行的数据网格最左下角的数据是1(1,1)分量衰减越慢.当h在区间(0,p)内增大时,|AMGM算法的具体流程以图1来表示.其中,变小,h越大,表明该分量的频率越高.说明在固定divu表示在RFS求压强的步骤中MGM的输入为步长h的情况下,误差n中的高频分量在迭代过程速度的散度,而p表示输出为压强图1中,“●”表中衰减得较快,而低频分量收敛得慢,这也是 Jacobi示网格残差r,“■”表示解误差e,“\”表示限定,和GS等固定网格步长迭代法的收敛速度慢的原“/”表示延拓,“⌒”表示松弛迭代,“”表示求网格因.针对这个缺陷,可将迭代过程进行改进:在以初残差.算法大体上可分为先下降和后上升2个阶始步长h的网格上迭代若干次后误差中后面的高段:下降阶段即将最细层上的残差限定到底(最粗层频部分已经基本衰减掉了,剩下位于前部从k=1layr1);上升阶段则是将最粗层精确求出的误差当开始的低频分量,这时可将步长h放大,hh随之增成上层的校正量,将校正量插值到顶(最细层大,使这些低频分量获得较高的衰减速度;然后进layer4);最后在最细层校正后得到新的近似解.重步将步长增大,更低频的误差分量也得以加速衰减.复这个过程可得到满足精度要求的解.这种方法MGM算法包含松弛迭代、计算网格残差、残差做多层V循环的MGM算法31限定和误差延拓4大步骤.为了便于网格点上数据的传递与插值,本文采用4层标准粗化系列网格3即每层网格是均匀剖分,相邻2层网格步长比为2lavery下标L表示对应的网格层,越细的网格层l越大Step.松弛迭代.在最细网格上迭代初始解使之达到相应阶数的平滑.对线性方程组(3)laver可简单采用 Jacobi迭代法完成,也可使用加权的 Jacobi迭代图1MGM算法流程示意图法7;得该层的不精确解u1Step2.计算网格残差.将式(3)迭代数次后得到的不精为了完成在GPU上的流处理计算,我们把计确解u2代入算过程需要的网格数据分别保存在纹理中.MGMr=∫-Lt(4)运行过程所需的全都是正交网格数据,这也是它便求得该层网格残差于在GPU上编程的优势之一.统计所需纹理到每Siep3.残差限定.将细网格的残差向下层粗网格传递,层上,为保证算法的连续执行,必须在每一层上保在我们使用的标准化网格上 restrict限定算子为简单的平凡存该层的误差e和残差r1,如果每个网格数据用一单射个纹理来保存,则需要的纹理数N2是网格层数N2II-1restrICL( Tl的2倍,N2=2×N938计算机辅助设计与图形学学报2007年算法分为下降和上升2个阶段.在下降阶段,渲染区内不同位置上的纹素分别使用不同的像素程渲染区域逐层缩小,而在上升阶段则相反.被渲染序.如图3所示,灰色区域为模板所遮盖的区域的纹理依次为下降阶段的误差纹理E4,E3,E2,E1GPU将不会在这些区域执行像素程序.首先运行第和上升阶段的网格残差纹理R1,R2,R3,R4,为了个像素程序,配合“井”字形的模板,使绿色○的值最大限度地发挥GPU的运算能力,本文采用渲染由下层粗网格传递上来(如图3左图所示);然后运到纹理( render to teαture,Rr)的计算方式,将程行第二个像素程序,配合隔列的“‖”形模板,使蓝序运行所需的所有数据资源和计算场所移植到色三角形的值等于左右两侧网格值和的一半(如GPU与其配套的帧缓存( frame buffers,FB)上来,图3中图所示);最后第三个像素程序,配合隔行的以避免缓慢的显存-主存间的数据交换.我们使用当形模板,使红色方框的值等于上下相邻网格值前流行的为 Opengl开发的 FBO Extension存储管和的一半(如图3右图所示).经过这3个流程后,理方案便能完成满足式(6)的延拓效果,所需模板缓存事先Goodnight等6的纹理储存管理方法使用以纹理形式保存.该方法能避免在像素程序中出现OpengL Pixel Buffer中的 FRONT和BACK帧缓存动态分支操作,因为对目前的GPU来说,在每个像切换法来满足算法在每一层上计算误差和残差时所素上都进行if, while等动态分支操作的效率是极其需的渲染区,这样做需要不断地在存放各网格层数低下的.据的 Buffer间来回切换.与文献[6]不同,本文将下口口降阶段依次生成的4个网格残差纹理作为一组附着在同一个FB上,再将上升阶段依次生成的4个误差纹理作为一组附着在另一个FB上,如图2所示口囗口口图2中,蓝色表示存放网格残差的纹理R1,红色表示存放误差的纹理E,被网格覆盖的区域为渲染图3多模板缓存示意图区.4个R都附着在FB1上,而4个E都附着在FB2上这样做不但不需要与系统主存数据交换,还减少了运行时在不同的FB间切换的次数.实验证4GPU实时流体模拟的实现明:这样做的确可以获得约5%的性能提升.我们使用4层网格,相比文献[7]的2层网格更能发挥我们将模拟程序分为更新速度场、更新密度场MGM的优势,同时还能刚好将一个FB上的4个纹和可视化密度场三大部分来依次完成对于流场内理附着区用完,更大地发挥图形硬件的效能的初始速度场和初始密度场我们分别制成纹理保存在更新速度场部分,对每个时间步长首先按照文有纹理0看理1对着纹理0着纹理1献[5]中稳定流体的半拉格朗日方法计算输运方程;然后用4层MGM计算黏度扩散方程和压强方程;在解压强方程的步骤中,以速度的散度场divu作对纹理2對群理3时着纹理2对稻纹聞3为 layer4的r,将所求的压强p作为 layer4的et(如图1所示);对以下各层,都以全零网格作为下降阶段的迭代初始预估值e;,当最终回到顶层 layer4b.时,即可得到结果e4,也就是我们想要的压强p.在图2MGM计算纹理布局黏度扩散方程中,MGM算法的输入/输出都是速度场;最后用压强修正速度场以满足连续性方程.在我们用CG语言编写MGM算法的核程序.在更新密度场部分,以更新后的速度场来计算密度的MGM的限定程序中,使用CG内建的投影取样函输运方程式(2);并显示更新后的密度场数 texrECTproj(tex,hal/3( coords, scale),这样在在数据管理方面,以往采用的 pBuffer方每个像素上都能节省一次二元数组的除法,能使限式[1819需要将纹理数据写回系统主存.与此不同,定步骤的GPU计算量减少本文采用RTT方式在GPU上执行这一系列的运在延拓程序上,本文使用多模板缓存方法对被算,每一个步骤的结果都以纹理保存并作为下一个7期周世哲等:基于多重网格法的实时流体模拟939程序的输入,所有的计算输入输出包括中间结果都以纹理的形式存储,并附着在FB上,整个过程不需要显存与系统主存间的数据交换在边界条件的处理上,我们采取的方法和文献第1帧第3帧第6中第17[5]基本一致.对于式(2),其边界条件离散到我们的网格上,就是流域边界线两侧网格压强值相等,这样就能达成在边界线上压强导数处处为“0”的边界:≤条件;而对于黏度扩散方程,使速度在边界线两侧互第46帧第66帧第101帧为相反数,以满足所谓的不可穿越条件S.本文区别对待在MGM算法执行过程中生成的网格残差与误差的边界条件.对于误差e,因为它们是上层较细网格解的修正量,最终是解压强p的一部分,所第157帧第212帧第433帧第600以它们与p满足同样的边界条件,即对每一个误差a901次 Jacobi迭代纹理E4,其边界纹素与相邻的纹素相同;而对于网格残差r,它们不存在边界限制,所以残差纹理R1的边界纹元为全0第3帧第17帧5实验结果和分析本文实验使用 Geforce6800GS显卡,内建有12条像素渲染管线,核心频率是350MHz.为了保第46帧第66帧第101帧证模拟动画一定的流畅度,必须采用额定迭代次数的方法,在目前的GPU实时流体模拟程序[1819中基本上都采取这样的方式.文献[5,18]的研究发现,一般迭代次数在30~50次就可以很好地满足视第1579第212帧3辆第600帧觉要求.但是这样做会损失流体模拟的精度,如果ba对应的MCM算法模拟动画截图提高迭代次数,则模拟可以有更准确的细节和更真图4不可压缩二维方腔流的模拟实的表现采用文献[6]方法,我们使用GF6800GS提供对于同等规模和较低的精度要求的情形,我们设的硬件遮挡查询设定迭代前后2次的误差阈值,不定了适当的迭代次数,使得 Jacob程序和MGM程序额定迭代次数,对模拟在第一时间步长内达到预定能获得相同的帧数,如图5所示图5中,初设条件与精度收敛所需要迭代次数进行了记录.结果如下图4相同,只是将染料换成了紫色.图5a中,细网格如果要达到精度为10-4的稳态,采用Jaob迭代法上迭代24次,粗网格上迭代35次.图5a,5b的帧数需要901次,动画帧数为1.5帧/s,如图4a所示;要都为17帧/s左右.不难发现,MGM程序模拟的流体达到精度为106的稳态,采用Jabi迭代法需要4动画在形态上更加接近图4a,细节也更加丰富.而与527次,动画的帧数仅为0.3帧/左右,如图4b所之对比的Jao程序虽然拥有相同的帧数,但是在模示.图4中,流场离散规模为514×514.初始的密拟到第212帧时,与图4的第212帧相比其形态已度场表示为第1帧中的一块正方形淡红色染料,在完全走样,说明 Jacobi迭代法在较大规模的RFS问受到自上而下和自右向左的2个外力冲击后,产生题上如果迭代次数较少,模拟的精度是很差的.由流体运动的形态图4a中,动画帧数为1.5帧/s;图于本文采用存储管理方式,这里的 Jacob程序与文4b12幅图使用4层V循环MGM算法,在 layer4献[18]在同样规模和同样的迭代次数下的运行帧数到 layer1上的 Jacob迭代次数分别为128,64,32相比高3~5帧/s.本文实验说明:仅用2层网格也和75,动画的帧数为4.8帧s.我们截取了2种模能让RFS在保持速度的前提下获得较高的模拟精拟在相同帧时的图片,以进行模拟效果的比较度,但是效果提升度不如4层网格明显940计算机辅助设计与图形学学报2007年[5 Stam J. Stable fluids [C]//Computer Graphics ProceedingsAnnual Conference Series, ACM SIGGRAPH, Los angeles1999:121-128[6 Godnight Nolan, Lewin Gregory, Luebke David,et almultigridsolverproblems usingprogrammable graphics hardware [R]. Virginia: University of第17帧第101帧第212帧Virginia, 20032层网格MGM法[7] Bolz J, Farmer I, Grinspun E, et aL. Sparsethe GPU: conjugate gradients and multigrid [C] //ComputerGraphics Proceedings, Annual Conference Series, ACMSIGGRAPH, San Diego, 2003: 917-924[8] Stam J, Fiume E. Turbulent wind fields for gaseous phenomena[C /Computer Graphics Proceedings, Annual Conferenc第17帧第101帧第212帧Series, ACM SIGGRAPH, Anaheim, 1993 369-376b60次 Jacobi迭代[9 Fedkiw R, Stam J, Jensen H W. Visual simulation of smoke图5有相同帧数的2层网格MGM程序和 Jacob迭代[CJ/Computer Graphics ProceedinferenceSeries, ACM SIGGRAPH, Los Angeles, 2001: 15-22程序的模拟效果对比图[10] Nguyen D Q, Fedkiw R, Jensen H W. Physically based实验证明:在GPU上进行高精度的RFS,特别modeling and animation of fire [C] //Computer Graphics是在流场的离散规模较大的情况下,MGM能成倍Proceedings, Annual Conference Series, ACM SIGGRAPHSan antonio, 2002: 721-728地提高速度;而且对只需满足视觉要求的RFS,在[11]Haann T, et al. Simulatio速度相同的情况下使用MGM也能让模拟更准确、of cloud dynamics on graphics hardware [C]//Proceedings of th细节更加丰富、更加接近工程要求的模拟精度.同Graphics Hardware of Eurographics Association, Aire-la-Ville时,本文方法没有改变RFS的可交互性,也没有破2003:92-101坏基于GPU的RFS的模块化结构,因而可以很容12]wngc, Guendelman e,Low.ta. Efficient simulation易地移植到三维情形.与文献[7]采用的2层网格of large bodies of water by coupling two and three dimensional相比,本文方法的网格层数更多;并且由于我们采用techniques [c] //Computer Graphics. Proceedings, AnnualConference Series, ACM SIGGRAPH, Boston, 2006: 805-811的编程模式可以充分地利用图形硬件的显存容量,[13] Treuille a, Lewis a, opovi'c Z. Model reduction for real-time使得进一步提高RFS的离散规模和网格层数变得fluids [c// Computer graphics Proceedings, Annual Conference简便易行Series. ACM SiGGRaPH, Boston, 2006: 826-834[14] Klingner B M, Feldman B E, Chentanez N, et al. Fluid参考文献himation with Dynamic Meshes [C] //Computer GraphicsProceedings Annual Conference Series, ACM SIGGRAPHBoston,2006:820825[1]HughesWF,BrightonJA.Schaum'soutlineoftheoryand[15]gpgpu.Gpgpu[ol].(2006-12-3)[2007-5-1].http://wwwproblems of fluid dynamics [M]. Beijing: Science Press, 2002:gpgpu. ong1-88(in Chinese)[16 Kruger J, Westermann R. Linear algebra operators for GPU( HugheswF, brighton A.流体动力学[M].徐燕侯,过明implementation of numerical algorithms [C] / C道,徐立功,等译.北京:科学出版社,2002:1-88)Graphics Proceedings, Annual Conference Series, ACM2] Wu Ziniu. The basic principles of computational fluid dynamicsSIGGRAPH, San Diego, 2003: 908-916[]. Beijing Science Press, 2001: 20-63(in Chinese)[17] Rumpf M, Strgodka R. Using graphics cards for quantized FEM(吴子牛.计算流体力学基本原理[M].北京:科学出版社computations [C] //Pof iastedⅤ isualizatie2001:20-63)Imaging and Image Processing Conference, Marbella, 20013 Li Wei. Finite analytic numerical method for viso193-202dynamics [M]. Beijing: Science Press, 2001: 1-117(in [18] Harris Mark J. Fast fluid dynamics simulation on the GPU [CChapel Hill: University of North Carolina at Chapel Hill(李炜.粘性流体混合有限分析解法[M].北京:科学出版2004:637-665社,2000:1-117)[19] Liu Youquan, Liu Xuehui, Wu Enhua. Real-time 3D fluid[4 Li Deyuan, Xu Guorong, Shui Hongshou, et al. The numericalsimulation on GPU with complex obstacles [J]. Journal ofmethod for two-dimensional unsteady fluid dynamics [M]Software, 2006, 17(3): 568-576(in ChineseBeijing: Science Press, 1998: 1-98(in Chinese)(柳有权,刘学慧,吴恩华.基于GPU带有复杂边界的三维(李德元,徐国荣,水鸿寿,等.二维非定常流体力学数值方实时流体模拟[J].软件学报,2006,17(3):568-576)法[M].北京:科学出版社,1998:1-98)基于多重网格法的实时流体模拟旧WANFANG DATA文献链接作者:周世哲,满家巨, Zhou shizhe, Man Jiaju作者单位:湖南师范大学数学与计算机科学学院,长沙,410081刊名:计算机辅助设计与图形学学报 ISTIC EIPKU英文刊名:JOURNAL OF COMPUTER-AIDED design COMPUTER GRAPHICS年,卷(期)2007,19(7)引用次数:0次参考文献(19条1. Hughes W r. Brighton Ja.徐燕侯.过明道.徐立功流体动力学20022.吴子牛计算流体力学基本原理20013.李炜粘性流体混合有限分析解法20004.李德元.徐国荣.水鸿寿二维非定常流体力学数值方法19985. Stam J Stable fluids 19996. Godnight Nolan Lewin Gregory Luebke David A multigrid solver for boundary value problems usingprogrammable graphics hardware 2007. Bolz J Farmer I Grinspun E Sparse matrix solvers on the GPU: conjugate gradients and multigrid 20038. Stam J Fiume E Turbulent wind fields for gaseous phenomena 19939. Fedkiw R Stam J. Jensen H W Visual simulation of smoke 200110. Nguyen D Q Fedkiw R Jensen H W Physically based modeling and animation of fire 200211. Harris M J. Baxter III W V Scheuermann T Simulation of cloud dynamics on graphics hardware 200312. Irving G. Guendelman E Losasso F Efficient simulation of large bodies of water by coupling two andthree dimensional techniques 200613. Treuille A Lewis A Popovic Z Model reduction for real-time fluids 200614. Klingner B M Feldman B E. Chentanez n Fluid Animation with Dynamic Meshes 200615.査看详情200716. Kruger J Westermann R Linear algebra operators for GPU implementation of numerical algorithms200317. Rumpf M. Strgodka R Using graphics cards for quantized FEM computations 200118. Harris Mark J Fast fluid dynamics simulation on the GPU 200419.柳有权.刘学慧.吴恩华基于GPU带有复杂边界的三维实时流体模拟[期刊论文]软件学报2006(3相似文献(3条)1.学位论文张乐冰基于谱方法的实时流体模拟2009用计算机真实地再现水、云、烟为代表的流体在自然界中的运动过程和运动规律,即流体模拟是计算机图形学中的一个重要研究领域。流体模拟技术广泛应用于流体力学硏究、航空航天、气象硏究、海洋工程、汽车设计以及计算杋动画等众多领域,是有关基础科学理论硏究和应用工程设计研究的重要手段。因此,流体模拟的研究在理论研究和工程实践上都有着重要的意义。本文从计算机图形学的角度,依据流体力学的基本理论,用谱方法模拟不可压均匀低速流体的运动规律。基于谱方法的流体模拟是有别于目前通用的半拉格朗日稳定流体模拟方法的另一种尝试。该方法将流体运动从通常的实空间转换到谱空间进行运算,对纳维一斯托克斯方程采用谱配置法进行求解,从而直接消去了压力项,并将原方程中的扩散、平流、外力项做为一个整体用简单的代数运算来进行处理,避免了把纳维一斯托克斯方程拆成几项分别求解带来的误差和用迭代法求解泊松方程的繁复运算,大大降低了实时流体模拟过程中的运算量。在计算机的实现上,本方法充分利用图形处理器(G門U)强大的并行运算能力,采用渲染到纹理的计算方式,帧缓展的纹理管理方法,实现了对流体的实时模拟。通过实验比对可以看到,基于谱方法的流体模拟在模拟的实时性和流体细节精度等方面较半拉格朗日稳定流体模拟方法都有着不同程度的提高。2.期刊论文柳有权.刘学慧.吴恩华. LIU You-Quan. LIU Xue-Hui. WU En-Hua基于GPU带有复杂边界的三维实时流体模拟-软件学报2006,17(3)在GPU( grhics processing unit)上求解了复杂场景中的三维流动问题,充分利用了GPU并行能力以加速计算.与前人的方法不同,该方法对于边界条件的处理更为通用.首先,通过在图像空间生成实心的剖切截面构成整个障碍物信息图,算法使得流体计算与整个几何场景的复杂度无关,通过对各体素进行分类并结合边界条件,根据障碍物形成修正因子来修改对应的值;另外,采用更为紧凑的数据格式,以充分利用硬件的并行性.通过将所有标量的运算压缩到纹元的4个颜色通道并结合平铺三维纹理,减少了三维流场计算所需要的绘制次数.实验结果显示出算法的有效性和高效率.该算法可以实时计算并显示个采用中等规模离散的复杂场景3.学位论文彭伟采用格子 Boltzmann方法的实时流体模拟研究2009自然景物的模拟是现在计算机图形学的一个热点,寻求能准确地描述现实世界中各种现象与景观的数学模型,并逼真地再现这些现象与景观,是计算杋图形学的一个重要硏究课题。影视制作、计算杋动画、计算机游戏设计、虚拟现实等相关领域都需要模拟自然景物,但是很多自然景物难以用几何模型描述,如烟雾、植物、水波、火焰等。特别是流体这种形状多变的自然现象,它没有圊定的形状,很难使用建模的方法去表现。这使得流体模拟成为计算机图形学中的一个难点,很多学者对这方面进行深入研究。近几年来,计算机图形学的顶级会议 SIGGRAPH会议每年都会有一个流体仿真的专题总结这方面的成果在计算机图形学中模拟流体可以追溯到上个世纪八十年代,那个时期的流体模拟算法一般采用构造的方法或高度场的」去表现高低起伏的波形,这些方法往往难以控制而且对于一些复杂的现象不再适用。九十年代以后,基于物理的方法开始引入到计算机图形学中,它主要是基于流体动力学中的 Navier- Stokes方程,按照描述方式的不同可以分为拉格朗日方法和欧拉方法。这两种方法都是从宏观层次上把流体假设成为连续的介质,然后根据质量守恒和动量守恒推导出离散的 NAvier- Stokes方程,再离散求解。而本文主要研究的格子 Boltzmann方法是基于介观层次的,它假设流体被离散成为一系列的流体微团,微团在尺度上比分子要大但是在宏观级别上又很小,然后再把 Boltzmann方程在时间和空间上离散化得到格子 Boltzman方程,这个方程能恢复到宏观上的 Navier- stokes方程。介观方法在宏观方法难以胜任的多相流等复杂流体现象中则表现出强大的优势。与其他宏观方法比起来,它具有清晰的物理意义,边界条件处理简单和易于并行计算等优点,是研究流体模拟的一个热点。本文主要硏究格子Boltzmann方法在图形学上的应用,使用格子 Boltzmann方法描述水流的运动及其和空气的交互,并用VoF( Volume of fluid)方法去追踪水流的自由表面,针对模拟过程中可能出现的负分布函数做了处理,为了进一步减少内存开销,引入插值格子 Boltzman方法,减少计算网格的数量提高实时性。采用图形处理器(GPU)去计算水面的反射和折射效果,提高真实性。这个方法可以为实时水体模拟提供一条新思路,并可以应用到虚拟现实、游戏制作、电影动画设计、计算机艺术等相关领域本文链接http://d.g.wanfangdata.comcn/periodicAljsjfzsjytxxxb200707021.aspx下载时间:2010年3月1日