基于物理的計算機流體動畫生成的高性能算法研究.pdf

1、本文全面探討流體動畫生成的各個方面，分析其性能瓶頸，并對若干重要問題的高性能計算進(jìn)行深入研究。主要研究內(nèi)容包括三維流體數(shù)據(jù)場高性能生成，Navier-Stokes方程組高性能求解，顆粒流模擬離散元方法高性能求解以及高性能流體仿真軟件平臺的架構(gòu)設(shè)計。
　　三維流體數(shù)據(jù)場的生成不僅是流體模擬的重要數(shù)據(jù)準(zhǔn)備，而且可能貫穿整個模擬過程。為此，本文首先研究流體數(shù)據(jù)場的高性能生成，特別是帶符號距離場的生成。本文提出了從三角面片生成帶符號距離場

2、的雙層粒子算法，該算法首先構(gòu)造圍繞三角面片的內(nèi)外兩層粒子以逼近三角面片，然后分別計算兩層粒子的無符號距離場，最后通過一個簡單的公式計算帶符號距離場。該算法形式簡潔，避免了復(fù)雜的幾何配置，且具有天然的并行性。實驗結(jié)果顯示，雙層粒子算法具有較高的并行效率，大約有10-40倍的并行加速比。
　　其次，為了高效求解Navier-Stokes方程，本文提出了求解壓力Poisson方程的適于并行計算的預(yù)處理共軛梯度法。新的預(yù)處理方法將線性代數(shù)

3、方程組的求解回歸到背景網(wǎng)格上來考慮，將稀疏矩陣的非零元素表示為直觀的網(wǎng)格模板，直接設(shè)計預(yù)處理矩陣的逆矩陣，且設(shè)計預(yù)處理逆矩陣時采用理論猜測、數(shù)據(jù)分析和實驗驗證相結(jié)合的辦法以確定最優(yōu)參數(shù)。本文在研究過程中發(fā)現(xiàn)了重構(gòu)矩陣的稀疏結(jié)構(gòu)可以顯著降低條件數(shù)這一規(guī)律，并借此進(jìn)一步推廣了所提算法。數(shù)值實驗表明，新的預(yù)處理共軛梯度法有著良好的收斂速度和并行效率:相同誤差限制條件下，迭代次數(shù)降為原共軛梯度法的1/2左右，推廣后的算法迭代次數(shù)進(jìn)一步降為原來的

4、1/3左右;而且新算法大約有5-10倍的并行加速比。
　　本文還研究了顆粒流模擬離散元方法的高性能計算問題。圖形學(xué)中的離散元方法，一般采用組合球形粒子的方法來建模顆粒，據(jù)我們所知，文獻(xiàn)中尚未出現(xiàn)針對這一方案的GPGPU并行算法設(shè)計與實現(xiàn)。設(shè)計該算法并行版本的關(guān)鍵難點在于，GPGPU設(shè)備不直接支持可變長數(shù)據(jù)結(jié)構(gòu)。本文提出一種適合GPGPU并行計算的數(shù)據(jù)結(jié)構(gòu)以克服這一難點，并在此基礎(chǔ)上提出高效的并行算法。數(shù)值結(jié)果表明，新的并行算法相比

5、原算法約有10倍的加速比。
　　最后，本文提出一種適合高性能流體模擬的軟件架構(gòu)，并實現(xiàn)為軟件平臺PBAT。PBAT架構(gòu)設(shè)計采取變化分離和功能模塊松耦合的原則，界面與模擬模塊高度分離，各模擬模塊功能高度松耦合，非易變性功能高度組件化。流體模擬參數(shù)被設(shè)計為獨立模塊，從而使得參數(shù)改變對整體架構(gòu)的影響局部化。PBAT架構(gòu)在設(shè)計上兼顧了開發(fā)期屬性和運行期屬性，兼顧了通用性與性能。PBAT目前已實現(xiàn)許多數(shù)學(xué)工具和模擬模塊，而且設(shè)計并實現(xiàn)了一個