基于攝像機(jī)位置的大規(guī)模粒子云繪制加速算法

葛奇鵬

(武漢717 研究所，湖北武漢430000)

0 引言

無論在娛樂、教學(xué)、軍事還是輔助設(shè)計(jì)領(lǐng)域，只要涉及天空仿真，便不可避免的要遇到云團(tuán)繪制問題，粒子系統(tǒng)很好的解決了這類不規(guī)則模糊物體的仿真問題，但是由于粒子系統(tǒng)本身具有大量冗余三角網(wǎng)格，即使在這個(gè)顯卡處理能力日新月異的年代，粒子系統(tǒng)的效率依然是個(gè)巨大的難題［1］。

前人在粒子系統(tǒng)的加速及優(yōu)化上做過很多工作，被廣泛使用的技術(shù)有BSP 樹技術(shù)、shader 技術(shù)等，但是這些技術(shù)都無法解決數(shù)據(jù)冗余問題，計(jì)算機(jī)依然在繪制大量對(duì)視覺效果無增益的粒子，實(shí)時(shí)繪制大規(guī)模云團(tuán)依然是一大難題［2］。

眾所周知，人在觀察時(shí)，對(duì)遠(yuǎn)處物體的精細(xì)度要求低于近處物體。如果能夠基于攝像機(jī)對(duì)遠(yuǎn)處物體進(jìn)行細(xì)節(jié)降階處理，不僅于顯示效果損傷較小，還能夠大大降低需要繪制的粒子數(shù)量，從而達(dá)到提高繪制速度的目的。本文將就這個(gè)問題進(jìn)行一些探討，并提出了一個(gè)可行的解決方案，達(dá)到了提高繪制速度的目的。

1 粒子云計(jì)算與繪制

為了解決火焰、水波、云彩等不規(guī)則模糊物體的模擬問題，Reeves 于1983年提出了粒子系統(tǒng)。粒子系統(tǒng)是由大量粒子結(jié)合在一起來表現(xiàn)模糊物體的系統(tǒng)，其基本原理為:將模糊物體看作由大量不規(guī)則的、運(yùn)動(dòng)的、隨機(jī)分布的粒子組成的粒子集。不同的粒子雖然屬性、形狀、物理化學(xué)性質(zhì)、運(yùn)動(dòng)軌跡不同，但是他們都具有通用的屬性，在計(jì)算機(jī)里可以很方便的將其定義為粒子類，包含自身的外形、空間位置、紋理等等信息，他們不斷運(yùn)動(dòng)，不斷改變形態(tài)，合力表現(xiàn)景物的外部特征［3］。

三維云團(tuán)的模擬一般基于粒子系統(tǒng)?；舅枷胧钦J(rèn)為一個(gè)粒子為一個(gè)球形物體，粒子密度服從高斯分布。一個(gè)粒子的屬性包括:中心位置、半徑、密度、顏色等［4］，通過分型算法可隨機(jī)生成各式各樣的云粒子點(diǎn)集，一般存儲(chǔ)在一個(gè).mesh 文件中供調(diào)用。

本文例子中的云粒子類如下所示:

class SkyCloudParticle

{

…/ /省略了方法

protected:

float _rRadius;

float _rTransparency;

Vec3f _vecPosition;

Vec4f _vecBaseColor;

std::vector＜Vec4f ＞ _vecLitColors;

Vec3f _vecEye;

};

由于粒子系統(tǒng)極為龐大，成千上萬的粒子往往不可避免，雖然計(jì)算的時(shí)候會(huì)將粒子模型化、具體化，但是真正繪制的時(shí)候，往往用貼附粒子紋理的公告板代替。所謂公告板，就是一個(gè)始終朝向攝像機(jī)的有紋理的正方形面，相比于至少6個(gè)面的球體［5］，公告板對(duì)視覺效果的影響很低，但是性能極大地改善。本文采用最簡(jiǎn)易的公告板進(jìn)行粒子的繪制，效果如圖1所示。

圖1 使用公告板粒子渲染的大規(guī)模云團(tuán)

本文例子由OpenGL 實(shí)現(xiàn)，另繪制了山巒、天空盒、海水等其他物體以增強(qiáng)可視效果。

2 基于攝像機(jī)的分層加速

粒子系統(tǒng)的特點(diǎn)是粒子繁多，但是每個(gè)粒子的結(jié)構(gòu)都相對(duì)簡(jiǎn)單，可削減性強(qiáng)，對(duì)于較遠(yuǎn)的云團(tuán)，減少一定數(shù)量的粒子是可以接受的。如果2 個(gè)粒子之間距離為L(zhǎng) 時(shí)人眼可以感覺出差異，當(dāng)距離縮減為L(zhǎng)/2 以下時(shí)，便可用一個(gè)粒子表示這2 個(gè)粒子，我們認(rèn)為云團(tuán)整體變成1/2 大小時(shí)，云團(tuán)的粒子數(shù)降低一半是不影響視覺效果的。

由此可推出公式:

M 為減少粒子的倍率;D 為粒子距離攝像頭的距離;?，β 皆為與視景體相關(guān)的參數(shù);F為相關(guān)函數(shù)。

基于攝像機(jī)的場(chǎng)景分層如圖2所示。在圖2 的視景體下，可以將裁減后的場(chǎng)景分為3個(gè)部分，紅色部分云團(tuán)使用全體粒子進(jìn)行繪制，藍(lán)色部分使用1/2 粒子進(jìn)行繪制，灰色部分使用1/4 粒子進(jìn)行繪制。

圖2 基于攝像機(jī)的場(chǎng)景分層

這種不規(guī)則分層方式消除了相當(dāng)數(shù)量粒子，而由于人眼的觀察特性，這些粒子的缺失是不影響視覺效果的，在加速的同時(shí)無畫面質(zhì)量的降低。

3 基于BSP 樹的算法實(shí)現(xiàn)及優(yōu)化

一種經(jīng)典的云團(tuán)繪制算法是利用BSP 樹以AABB 包圍盒為基礎(chǔ)將云團(tuán)進(jìn)行排序［6］。BSP 樹可以有效的加速遍歷，當(dāng)某一個(gè)分枝被檢測(cè)到不與視景體相交，則其下的所有子樹都無需繼續(xù)遍歷，用這種方法判斷哪些云團(tuán)需要繪制，哪些不需要，這樣可以節(jié)約大量計(jì)算時(shí)間，不僅如此，在本文的算法中，涉及到了云團(tuán)與3 部分視景體的碰撞檢測(cè)，同樣要使用到BSP 樹進(jìn)行加速。

3.1 使用BSP 樹對(duì)粒子繪制進(jìn)行加速

首先用AABB 包圍盒將云團(tuán)分割成以云團(tuán)為最小單位的BSP 樹，然后根據(jù)視景體進(jìn)行判斷，如圖3所示。

圖3 基于AABB 包圍盒的云團(tuán)BSP 組織

判斷哪些云團(tuán)需要被繪制的方法如下:

1)以一個(gè)AABB 包圍盒包圍視景體，遍歷BSP 樹進(jìn)行碰撞檢測(cè)，裁減掉不相交的BSP 分枝［7］。

2)用視景體遍歷剩下的BSP 樹作碰撞檢測(cè)，裁減掉不相交BSP 分枝，最后得到需要繪制的云團(tuán)列表［8］。

3.2 使用BSP 樹進(jìn)行分層判斷加速

判斷云團(tuán)階層的方式跟判斷哪些云團(tuán)需要被繪制的方法類似，設(shè)置3 個(gè)列表，分別存放一階、二階、三階云團(tuán)的代號(hào)。從一階視景體開始，將其用AABB 包圍盒包裹，與已確定要顯示的云團(tuán)BSP 樹進(jìn)行碰撞檢測(cè)，得到結(jié)果之后，再用實(shí)際視景體進(jìn)行碰撞檢測(cè)，得到一階云團(tuán)，將這些云團(tuán)放入一階云團(tuán)列表，并從云團(tuán)顯示總表中移出。用同樣的方式將剩下的顯示總表與二階、三階視景體繼續(xù)進(jìn)行碰撞檢測(cè)。最后依次以繪制100% 數(shù)量粒子、50%數(shù)量粒子、25% 數(shù)量粒子的方式對(duì)一階、二階、三階云團(tuán)表進(jìn)行計(jì)算以及渲染。

4 本算法的加速效能計(jì)算

以本文程序?yàn)槔?，視景體投影為一個(gè)頂角為45°的等腰三角形。當(dāng)云團(tuán)足夠多時(shí)認(rèn)為一階、二階、三階中繪制的云團(tuán)與視景體面積成正比，則最終繪制的粒子數(shù)與未使用算法之前的比為:

可見減少的粒子數(shù)跟三階的分割比例有很大關(guān)系。當(dāng)一階越大，顯示效果越好，但繪制所需時(shí)間越多;反之當(dāng)三階越大，繪制速度極大提高，但繪制越粗糙。只要確保L1小于視景體長(zhǎng)度的1/3，這種算法就能將繪制速度提高2 倍以上。

在本例中，多次試驗(yàn)得到結(jié)果為:不使用加速算法的場(chǎng)景繪制漫游平均幀數(shù)為27 幀，而使用之后可以提高到49 幀。

5 結(jié)束語

云團(tuán)的繪制是場(chǎng)景仿真中不可缺少的部分，從以往的經(jīng)驗(yàn)可得，云團(tuán)的繪制由于其固有屬性，占據(jù)了天空繪制60%以上的資源［9］，提高云團(tuán)繪制速度即可提高天空?qǐng)鼍暗姆抡嫠俣取?/p>

本文的分階思想簡(jiǎn)單明了，實(shí)踐證明提高了繪制速度，但是尚有可繼續(xù)挖掘的地方。本文只進(jìn)行了三階分階，如采用更加精細(xì)的分割，對(duì)視覺效果的影響可能會(huì)更低，剔除的無需繪制的粒子可能更多，但是計(jì)算量可能會(huì)增加，編程復(fù)雜度也可能會(huì)相應(yīng)增加，需要大量的研究和試驗(yàn)，但卻不失為一個(gè)可以研究和探尋的方向［10］。

［1］陳華杰，余小清，唐經(jīng)洲，等.基于粒子系統(tǒng)與LOD 技術(shù)的實(shí)時(shí)雨雪效果模擬［J］.計(jì)算機(jī)仿真，2008(4):194－197

［2］丁紀(jì)云，陳利平，李思昆.基于OpenGL 的煙花動(dòng)態(tài)模擬方法的研究與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程，2002，28(4):240－241

［3］王功明，郭新宇，趙春江，等.粒子系統(tǒng)的優(yōu)化技術(shù)研究［J］.計(jì)算機(jī)應(yīng)用研究，2008，25(2):495－497

［4］龔琳，顧大權(quán)，范茵，等.三維云場(chǎng)景的模擬［J］.解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2006，7(5):496－500

［5］郭佳佳.基于粒子系統(tǒng)的自然景物模擬研究［J］.電腦知識(shí)與技術(shù)，2009(4):1006－1008

［6］馬登武，葉文.虛擬現(xiàn)實(shí)技術(shù)及其在飛行仿真中的應(yīng)用［M］.北京:清華大學(xué)出版社，2005:76－176

［7］胡英芳，黃強(qiáng)強(qiáng)，江順亮.基于OpenGL 的離散粒子系統(tǒng)顯示方法及其改進(jìn)［J］.計(jì)算機(jī)與現(xiàn)代化，2011(2):53－57

［8］汪繼文，陸和軍，張妍妍.基于粒子系統(tǒng)的水滴濺落模擬［J］.科學(xué)技術(shù)與工程，2010(6):1547－1550

［9］Andersen S，Andersen L.Analysis of spatial interpolation inthe material－point method［J］.Computers and Structures，2010 (6):506－518

［10］Fang Jiannong，Parriaux Aurele，Rentschler Martin，et al.Improved SPH methods for simulating free surface flows ofviscous fluids［J］.Applied Numerical Mathematics，2009(3):251－271