Page 277 - 《软件学报》2020年第10期

肖祥云 等:基于物理及数据驱动的流体动画研究 3253

性方程组(3).但在三维情况下,所形成的线性系统维度与网格精度为平方关系,也即:如果网格离散精度为 1024×
3
3
3
1024×1024 求解该泊松方程(1),则流体模拟所形成的线性方程组维度为 1024 ×1024 ,亦即 A 是大小为 1024 ×
3
1024 的矩阵.如此巨大的线性系统,需要非常有效的求解方法来处理.
投影步泊松方程(公式(3))的求解常用的预处理共轭梯度法(PCG)对于小规模计算收敛快且易于实现,但在
处理大规模网格计算时,收敛速度会变慢 [13] .因此,很多流体模拟算法针对投影步泊松方程的求解提出了一系列
的优化与改进策略.例如,McAdams 等人使用了多重网格作为共轭梯度法的预处理过程 [14] ,场景规模较大时加
速效果比较明显.同时,我们还可结合并行算法 [14−16] 进一步提速.而 GPU 技术 [17] 也被用于多重网格泊松解算器
中,以提高投影步的计算效率.例如:Molemaker 等人 [18] 结合了 IOP(iterated orthogonal projection)算法与多重网
格法去求解投影步方程,并利用 GPU 并行将效率提高了一个数量级;Jung 等人 [19] 提出的基于 CPU-GPU 的多重
网格泊松解算器,也较为有效地提高了泊松方程的计算效率.而陈曦等人 [20] 利用 GPU 实现了流体场景的实时模
拟,并且将 GPU 技术应用到带有复杂边界的三维实时流体模拟算法中 [21] .同样,在火焰模拟中也有 GPU 并行算
法 [22,23] 的应用.特别地,Lentine 等人 [24] 提出的粗网格投影方法大幅加速了泊松方程在整体流体模拟计算中的计
算过程,但同时也降低了仿真精度.最近,Yang 等人 [25] 提出了快速迭代正交投影方法,其算法可在一定程度上减
少迭代次数,使得方程计算快速收敛到所需模拟精度.而文献[26]与文献[27]均基于舒尔补(Schur complement),
提出了相应的并行加速方法,较为有效地从并行层面上加速了泊松方程的求解过程(如图 1 所示).

(a) 文献[26]部分结果 (b) 文献[27]部分结果
Fig.1 Parallel solver using Schur complement—Parallel Poisson solver
图 1 利用 Schur Complement 进行并行解算——并行泊松解算

但是,不论是利用多重网格作为共轭梯度的预计算方法 [14] ,还是利用并行加速方法 [27,28] ,对于求解投影步中
所涉及到的泊松方程的求解,也即大型稀疏线性方程组的求解,传统的方法均无法避免直接或者迭代地求
解 [29,30] .这对于需要反复调参追求最佳流体模拟效果的动画媒体设计师来说,所需要耗费的重复计算的时间成
本是巨大的.
1.2 复合网格格式方法

使用复合网格格式求解泊松方程是另一种常见的流体模拟加速方法.普通的流体仿真大多采用均匀网格
或者均匀交错网格 [31] 的方式,例如公式(2)所依据的离散网格即为均匀网格.但无论是均匀网格还是交错网格,
随着网格精度的增加,其计算耗时均呈爆炸式增长,使用复合网格则是将更多的计算资源分配在更感兴趣的区
域,在保持重要细节的同时,加速计算过程.例如,Losasso 等人 [32] 利用八叉树数据结构创建了计算网格,在细节较
多、较明显的区域使用精细网格,而在流场较稳定的区域使用稀疏网格.Feldman 等人 [33] 通过优化四面体网格生
成来减少一定的计算量,而 Klingner 等人 [34] 则利用动态网格(meshes)来加速泊松方程的求解过程.Irving 等人 [35]
通过应用非均匀自适应网格来减少计算单元个数.Chentanez 等人 [36] 在水体表面采用普通网格,内部使用长方
体高度网格.Yu 等人 [37] 结合粒子法与动态四叉树技术,在大规模地形上实现了视线相关的可变尺度的江河流动
效果.Zhu 等人 [38] 采用变步长网格,在所关注区域设置精细步长网格,其他位置设置稀疏步长网格.Da 等人 [39] 则
主要关注流体的表面计算(如图 2 所示).