葛奇鵬

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

0 引言

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

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

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

1 粒子云計算與繪制

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

三維云團的模擬一般基于粒子系統(tǒng)。基本思想是認為一個粒子為一個球形物體，粒子密度服從高斯分布。一個粒子的屬性包括:中心位置、半徑、密度、顏色等［4］，通過分型算法可隨機生成各式各樣的云粒子點集，一般存儲在一個.mesh 文件中供調用。

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

class SkyCloudParticle

{

…/ /省略了方法

protected:

float _rRadius;

float _rTransparency;

Vec3f _vecPosition;

Vec4f _vecBaseColor;

std::vector＜Vec4f ＞ _vecLitColors;

Vec3f _vecEye;

};

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

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

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

2 基于攝像機的分層加速

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

由此可推出公式:

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

基于攝像機的場景分層如圖2所示。在圖2 的視景體下，可以將裁減后的場景分為3個部分，紅色部分云團使用全體粒子進行繪制，藍色部分使用1/2 粒子進行繪制，灰色部分使用1/4 粒子進行繪制。

圖2 基于攝像機的場景分層

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

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

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

3.1 使用BSP 樹對粒子繪制進行加速

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

圖3 基于AABB 包圍盒的云團BSP 組織

判斷哪些云團需要被繪制的方法如下:

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

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

3.2 使用BSP 樹進行分層判斷加速

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

4 本算法的加速效能計算

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

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

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

5 結束語

云團的繪制是場景仿真中不可缺少的部分，從以往的經驗可得，云團的繪制由于其固有屬性，占據了天空繪制60%以上的資源［9］，提高云團繪制速度即可提高天空場景的仿真速度。

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

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

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

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

［4］龔琳，顧大權，范茵，等.三維云場景的模擬［J］.解放軍理工大學學報(自然科學版)，2006，7(5):496－500

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

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

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

［8］汪繼文，陸和軍，張妍妍.基于粒子系統(tǒng)的水滴濺落模擬［J］.科學技術與工程，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