[發(fā)明專利]一種基于GPU八叉樹加速和SPH算法的流體模擬方法

在審

• 申請?zhí)枺?/td>: 202211111028.3
• 申請日: 2022-09-13
• 公開（公告）號: CN115438600A
• 公開（公告）日: 2022-12-06
• 發(fā)明（設(shè)計(jì)）人: 趙雅彬;張文輝;史翔天;林鎮(zhèn)源;陳少坤;車向明;丁逸飛
• 申請（專利權(quán)）人: 桂林電子科技大學(xué)
• 主分類號: G06F30/28
• 分類號: G06F30/28;G06T15/00;G06T9/40;G06T17/00;G06T1/20;G06F111/08;G06F113/08
• 代理公司: 桂林市持衡專利商標(biāo)事務(wù)所有限公司 45107
• 代理人: 陳躍琳

本發(fā)明公開一種基于GPU八叉樹加速和SPH算法的流體模擬方法，為了降低CPU的負(fù)荷，并將八叉樹的遍歷放在GPU中進(jìn)行，改良了傳統(tǒng)的八叉樹算法，使用線性表來存儲八叉樹的節(jié)點(diǎn)，將指針替換成線性表中的下標(biāo)，使其在傳入GPU時(shí)依然可用，無需指針重定位，并提出一個(gè)O(1)空間復(fù)雜度的迭代方法來做到對八叉樹的遍歷，既利用了GPU強(qiáng)大的并行計(jì)算能力，又發(fā)揮了八叉樹在近鄰搜索算法中的性能優(yōu)勢，經(jīng)GPU和線性八叉樹加速后，整體幀率受水體粒子數(shù)目的限制大幅減小，CPU負(fù)荷有較大程度的下降。

技術(shù)領(lǐng)域

本發(fā)明涉及水體粒子模擬技術(shù)領(lǐng)域，具體涉及一種基于GPU八叉樹加速和SPH算法的流體模擬方法。

背景技術(shù)

在計(jì)算機(jī)圖形學(xué)中，自然場景模擬特別是流體模擬被廣泛地應(yīng)用于現(xiàn)實(shí)生活中許多領(lǐng)域，包括廣泛應(yīng)用于科學(xué)研究、影視特效、電腦游戲、災(zāi)難營救、科普教育、體育競技、軍事仿真等應(yīng)用領(lǐng)域。目前流體模擬的主流方法主要分為兩類：歐拉法和拉格朗日法。歐拉法的主要思想是把流體分割為一個(gè)個(gè)獨(dú)立的單元網(wǎng)格，分開計(jì)算每個(gè)網(wǎng)格中的物理量，從而計(jì)算出整個(gè)水流體系統(tǒng)的位置變化。歐拉法精度較高，如果網(wǎng)格精度足夠高，可以近乎完美地還原液體流動的諸多細(xì)節(jié)，但歐拉法計(jì)算效率過低，資源開銷也較大，在如今的計(jì)算能力中很難被應(yīng)用到實(shí)際工程中。拉格朗日法作為一種無網(wǎng)格方法，其將每個(gè)水體粒子作為研究對象，分別計(jì)算出每個(gè)水體粒子的物理量，并計(jì)算出作用域下其他水體粒子對當(dāng)前水體粒子的影響，最終計(jì)算出每個(gè)水體粒子的位置變化，光滑水體粒子流體動力學(xué)方法(Smoothed Particle Hydrodynamics，SPH)就是其中的一種實(shí)例。SPH算法的基本思想是將連續(xù)的流體用相互作用的質(zhì)點(diǎn)組來描述，各個(gè)物質(zhì)點(diǎn)上承載各種物理量，包括質(zhì)量、速度等，通過求解質(zhì)點(diǎn)組的動力學(xué)方程和跟蹤每個(gè)質(zhì)點(diǎn)的運(yùn)動軌道，求得整個(gè)系統(tǒng)的力學(xué)行為。在SPH算法的緊鄰水體粒子搜索中，八叉樹算法為較常用的一種，但常規(guī)的八叉樹算法均是在CPU進(jìn)行建樹和遍歷，這將較大增加CPU的負(fù)擔(dān)，隨水體粒子數(shù)目的增加，緊鄰水體粒子搜索的時(shí)間將大大增加，從而造成幀率較低的情況。

發(fā)明內(nèi)容

本發(fā)明所要解決的是現(xiàn)有SPH算法中的八叉樹算法在CPU進(jìn)行建樹和遍歷，從而增加CPU的負(fù)擔(dān)，并造成幀率較低的問題，提供一種基于GPU八叉樹加速和SPH算法的流體模擬方法。

為解決上述問題，本發(fā)明是通過以下技術(shù)方案實(shí)現(xiàn)的：

一種基于GPU八叉樹加速和SPH算法的流體模擬方法，包括步驟如下：

步驟S1、初始化DirectX渲染管線；

步驟S2、使用CPU在預(yù)設(shè)范圍內(nèi)隨機(jī)生成水體粒子的坐標(biāo)；

步驟S3、在CPU中根據(jù)水體粒子的坐標(biāo)建立線性八叉樹；

步驟S4、在CPU中將水體粒子的坐標(biāo)和線性八叉樹一并傳至GPU；

步驟S5、在GPU中以深度優(yōu)先的順序遍歷線性八叉樹來檢測查詢水體粒子的近鄰水體粒子；

步驟S6、將水體粒子的坐標(biāo)從GPU返回CPU；

步驟S7、在CPU中運(yùn)用渲染方案對水體粒子進(jìn)行著色。

上述步驟S2中，隨機(jī)生成的水體粒子的坐標(biāo)的位于預(yù)設(shè)范圍內(nèi)為[-10,10]的立方體內(nèi)。

上述步驟S3的具體過程如下：

步驟S3.1、基于所有水體粒子的坐標(biāo)計(jì)算出所有水體粒子所形成的包圍盒的中心坐標(biāo)，以及該包圍盒的長寬高；