基于物理的計(jì)算機(jī)流體動(dòng)畫(huà)生成的高性能算法研究.pdf

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

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

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

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

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