基于物理的计算机流体动画生成的高性能算法研究

摘要

本文全面探讨流体动画生成的各个方面，分析其性能瓶颈，并对若干重要问题的高性能计算进行深入研究。主要研究内容包括三维流体数据场高性能生成，Navier-Stokes方程组高性能求解，颗粒流模拟离散元方法高性能求解以及高性能流体仿真软件平台的架构设计。
　　三维流体数据场的生成不仅是流体模拟的重要数据准备，而且可能贯穿整个模拟过程。为此，本文首先研究流体数据场的高性能生成，特别是带符号距离场的生成。本文提出了从三角面片生成带符号距离场的双层粒子算法，该算法首先构造围绕三角面片的内外两层粒子以逼近三角面片，然后分别计算两层粒子的无符号距离场，最后通过一个简单的公式计算带符号距离场。该算法形式简洁，避免了复杂的几何配置，且具有天然的并行性。实验结果显示，双层粒子算法具有较高的并行效率，大约有10-40倍的并行加速比。
　　其次，为了高效求解Navier-Stokes方程，本文提出了求解压力Poisson方程的适于并行计算的预处理共轭梯度法。新的预处理方法将线性代数方程组的求解回归到背景网格上来考虑，将稀疏矩阵的非零元素表示为直观的网格模板，直接设计预处理矩阵的逆矩阵，且设计预处理逆矩阵时采用理论猜测、数据分析和实验验证相结合的办法以确定最优参数。本文在研究过程中发现了重构矩阵的稀疏结构可以显著降低条件数这一规律，并借此进一步推广了所提算法。数值实验表明，新的预处理共轭梯度法有着良好的收敛速度和并行效率:相同误差限制条件下，迭代次数降为原共轭梯度法的1/2左右，推广后的算法迭代次数进一步降为原来的1/3左右;而且新算法大约有5-10倍的并行加速比。
　　本文还研究了颗粒流模拟离散元方法的高性能计算问题。图形学中的离散元方法，一般采用组合球形粒子的方法来建模颗粒，据我们所知，文献中尚未出现针对这一方案的GPGPU并行算法设计与实现。设计该算法并行版本的关键难点在于，GPGPU设备不直接支持可变长数据结构。本文提出一种适合GPGPU并行计算的数据结构以克服这一难点，并在此基础上提出高效的并行算法。数值结果表明，新的并行算法相比原算法约有10倍的加速比。
　　最后，本文提出一种适合高性能流体模拟的软件架构，并实现为软件平台PBAT。PBAT架构设计采取变化分离和功能模块松耦合的原则，界面与模拟模块高度分离，各模拟模块功能高度松耦合，非易变性功能高度组件化。流体模拟参数被设计为独立模块，从而使得参数改变对整体架构的影响局部化。PBAT架构在设计上兼顾了开发期属性和运行期属性，兼顾了通用性与性能。PBAT目前已实现许多数学工具和模拟模块，而且设计并实现了一个简易的图形用户界面。由于较好的架构设计，软件具有良好的可重用性、可扩展性、可维护性、异构性和跨平台特性，而且由于许多算法采用OpenCL进行并行实现，PBAT具有较高的性能。

目录

摘要

第一章 绪论

§1．1 基于物理的计算机流体动画概述

§1．2 GPGPU高性能计算概述

§1．3 计算机流体动画中的GPU高性能计算现状

§1．4 本文主要内容

第二章 流体数据场的高性能生成

§2．1 带符号距离函数

§2．2 带符号距离场生成的相关工作

§2．3 双层粒子算法

§2．3．1 计算无符号距离场

§2．3．2 生成带符号距离场

§2．4 双层粒子算法的分析与优化

§2．4．1 算法误差分析

§2．4．2 几个优化策略

§2．5 实验结果及其讨论

§2．5．1 误差测量

§2．5．2 性能分析

§2．6 带符号距离函数在流体动画中的应用举例

§2．6．1 用于构造复杂模拟场景

§2．6．2 用于烟雾模拟

第三章 Navier-Stokes方程高性能求解

§3．1 Navier-Stokes方程的时空离散格式

§3．1．1 时间方向离散格式

§3．1．2 MAC网格与边界条件离散

§3．1．3 不同流体现象的模拟

§3．2 平流方程的求解

§3．3 压Poisson方程的高性能求解

§3．3．1 预处理共轭梯度法

§3．3．2 本文提出的预处理算法

§3．3．3 算法的推广

§3．4 实验结果与讨论

第四章 颗粒流模拟离散元方法的并行计算

§4．1 颗粒流模型

§4．1．1 单个颗粒动力学模型

§4．1．2 颗粒形状建模

§4．1．3 颗粒间作用力建模

§4．2 离散元方法

§4．3 并行计算

§4．3．1 数据结构设计

§4．3．2 并行算法设计

§4．4 实验结果及其分析

第五章 PBAT软件平台

§5．1 PBAT的开发目的与关键问题

§5．2 PBAT总体架构设计

§5．3 数学工具库架构

§5．4 模拟器架构

§5．5 PBAT实现情况

§5．5．1 数学工具库实现情况

§5．5．2 模拟器实现情况

§5．6 用户界面和一些模拟结果

§5．7 本章小结

总结与展望

参考文献

攻读博士学位期间的主要工作

致谢

声明