粒子系統的優化技術研究

摘要:總結分析了影響粒子系統實時性的主要因素，歸納并提出了優化方法，具體包括:為了提高繪制效率，可采用顯示列表#65380;公告板技術#65380;幾何形體優化#65380;多級粒子系統;為減少計算復雜性，采用碰撞檢測與處理優化#65380;存儲方式優化#65380;運動過程優化#65380;線性表#65380;局部力場;為了減少粒子數量，采用結構化粒子#65380;LOD技術#65380;偽粒子系統等。最后將上述部分方法應用于基于粒子系統的土壤可視化。結果表明，該方法簡單#65380;實用，優化后速度平均有60.2%的改進。

關鍵詞:粒子系統; 可視化; 優化; 土壤可視化

中圖分類號:TP391.72文獻標志碼:A

文章編號:1001－3695(2008)02－0495－03

煙火#65380;云霧#65380;瀑布#65380;植物和土壤等自然景物的可視化是計算機圖形學中極具挑戰性的研究課題，傳統的造型方法很難比較真實地描述它們的形狀和特征。1983年Reeves提出了粒子系統，并實現了對煙#65380;火#65380;云等不規則物體的模擬[1]。隨后，粒子系統不斷得到改進和完善，并被廣泛應用于花#65380;草#65380;樹#65380;瀑布#65380;閃電#65380;浪花等自然景物和動物群體運動的模擬[2，3]。1990年S.Karl提出粒子系統的并行繪制算法[4]，完成影片Particle Dream;文獻[5]提出節日焰火粒子系統繪制算法，用粒子衍生表現焰火粒子軌跡并實現多種焰火特殊效果;1998年M.Unbeschiden和A.Trembilski運用粒子系統，從云的物理原理出發，結合紋理映射技術建立了云的模型[6]。粒子系統適用于不規則物體的可視化仿真，但也存在實時性不好，不能很好地滿足可視化實時交互需要等問題，因此必須予以優化。本文綜合分析了國內外基于粒子系統的可視化應用系統的優化方法，并從繪制效率優化#65380;計算復雜性優化#65380;粒子數量優化等角度予以總結和評價，在基于粒子系統的土壤可視化應用中加以佐證。

1繪制效率優化

粒子系統運行的最終結果是在屏幕上繪制每個粒子形態，這個過程需要一定的時間，影響了系統的實時性。繪制效率優化就是采用特定方法減少粒子繪制時間，進而提高速度。優化包括系統級和代碼級兩種，系統級主要采用高速緩存保存編譯過的繪圖代碼，使用時不需再次編譯;代碼級主要基于人眼分辨率限制，少繪制或不繪制人眼不敏感或看不到的區域。

1.1顯示列表

OpenGL為加快圖形繪制速度提供了顯示列表接口，它是被存儲起來用于以后執行的一組OpenGL命令。與子程序不同，這些命令經過編譯，執行效率高，并且只占據系統高速緩存，不占用內存資源，能有效提高OpenGL繪圖性能。該方法使粒子消隱繪制的時間復雜度僅與繪制區域相關，而與粒子數量無關[7]。該方法適合于重復或周期性變化的粒子系統;不適合屬性隨時間無規則變化的粒子系統。

1.2公告板技術

公告板(billboarding)是矩形圖元渲染的一種擴展。其本質是用快速繪制二維圖形代替三維實體模型，使二維對象看起來具有三維效果[8]。使用紋理映射繪制二維圖元并將其固定于一點，隨著觀察者視角改變而不斷改變法向量旋轉，使它總能朝向觀察者(圖1)。該方法適宜繪制云霧#65380;雪花#65380;導彈尾焰#65380;海平面等規模龐大#65380;立體感要求不高的自然景觀，不適宜繪制層次感#65380;立體感比較強的自然景觀。

1.3幾何形體優化

粒子三維形體復雜程度對系統實時性影響重大。粒子由三角面片組成，減少面片個數能優化系統，但不可過于簡化，否則影響真實感。對兩者折中是優化的關鍵。層次感#65380;立體感要求不高時，可用二維形體代替三維形體。確實要用三維形體繪制粒子時，要盡量選擇系統自帶三維形體，如長方體#65380;圓柱體#65380;球體等。因為這些繪制函數經過測試和優化，性能穩定;若形體不是系統自帶三維形體，但不涉及坐標點計算時可用坐標變換生成。如橢球體可由球體經過縮放變換得到;涉及坐標點計算時可簡化三角面片數逐片繪制，也可采用平面不規則組合體表示三維形體。如禹海全等人提出利用交叉平面表現導彈火焰[9](圖2)。真實感要求比較高時進行形體優化還要考慮優化后貼圖難易程度。傳統方法在二維圖形中心為粒子貼圖，由于中心對稱性，需要繪制一定數目三角形來分割中心;宿春慧等人提出將粒子從中心移到周圍可被一個三角形覆蓋的范圍內，這樣只需繪制一個三角形即可[10](圖3)。

1.4多級粒子系統

粒子自身屬性和方法也占據內存容量，在一定程度上影響實時性。對粒子分級，設置不同屬性和方法，構成多級粒子系統，可提高實時性。圖4是爆炸過程可視化。其中:周圍點狀粒子和中心片狀粒子可做成不同屬性和方法的二級粒子[11]。本方法適宜粒子系統中粒子間差異比較大的情況。

2計算復雜性優化

粒子系統運行過程中需要大量計算，如碰撞檢測#65380;速度調整#65380;內存分配#65380;算術運算#65380;循環判斷等。這些計算消耗系統資源，間接表示時間復雜度大小，對系統實時性影響比較大，處理不好將嚴重影響系統速度。計算復雜性優化就是對上述計算過程予以優化，減少時間復雜度。

2.1碰撞檢測與處理優化

粒子之間碰撞由碰撞檢測#65380;速度調整#65380;位置調整三部分組成。對粒子而言，通過前兩部分就能實現碰撞前后運動狀態變化，而位置調整僅是為了增強碰撞瞬間可視化效果。對少量(幾個)粒子構成系統而言，位置調整可展現碰撞細微過程;如果系統中粒子數量很多，且目標是展現整體效應而非單個粒子運動規律，那么位置調整可簡化。

不同粒子形體不同，碰撞檢測和處理方式也不同。但實現起來很麻煩，故應從宏觀角度著手，把所有粒子統一成球體進行處理。根據粒子中心距離判斷是否發生碰撞，若兩粒子中心距離小于兩者粒徑之和，則表示發生碰撞;否則不發生碰撞。

碰撞檢測中計算粒子距離涉及平方#65380;開方等操作，但影響速度。采用坐標分量檢測可減少這些操作，提高速度。分別計算粒子間x#65380;y#65380;z坐標分量距離，若某一分量距離大于兩者粒徑之和，則表明兩粒子不會碰撞;若三個分量都小于兩者粒徑之和，那么再計算兩者距離，確定是否發生碰撞(圖5)。

2.2存儲方式優化

粒子系統中粒子越多，真實感就越強，但時間和空間消耗也隨之增加。大多性能問題源于內存管理失敗，應盡量少執行內存分配和釋放操作。不宜用鏈表作為粒子數據結構，因為鏈表產生和刪除粒子時會有大量分配和釋放內存操作，采用數組可避免該問題。利用標志位標記粒子生存還是死亡，不必釋放內存空間;產生新粒子時，判斷當前粒子是否死亡，若死亡則對其重新初始化。此外，基于程序運行局部性原理，當內存容量允許時，把與粒子有關方法集成到粒子類中，在一定程度上可提高實時性。

2.3運動過程優化

粒子運動過程異常復雜，完全遵循物理公式難以實現，但人的肉眼分辨率有限，一定范圍內差異覺察不到。所以完全遵循一來不現實，二來沒太大必要，尤其是展現成百上千粒子的整體效應，運動過程需要優化。常用運動過程優化方法有運動簡化#65380;運動逼近和運動插值等。運動簡化是把復雜運動變為簡單運動。如王潤杰等人提出忽略重力影響，將雨滴下落簡化為勻速直線運動#65380;雪花飄落簡化為正弦曲線下落[12]。運動逼近利用分段直線運動逼近曲線運動;如馬駿等人提出用分段直線逼近的拋物線來模擬噴泉粒子水珠運動[13]。運動插值獲取粒子運動過程中狀態變化關鍵幀，通過插值表現粒子運動狀態改變，避免求解復雜運動方程。

2.4線性表

粒子運動涉及大量三角函數#65380;對數函數#65380;指數函數等耗時運算，可予以優化提高實時性。現在PC機都有大容量內存，可以建立并查找線性表避免上述耗時運算。以給定步長為增量，將常用三角函數值#65380;對數函數值#65380;指數函數值用線性表存入內存，只要給定步長合理有效，即可滿足精度要求。

2.5局部力場

典型粒子系統包括粒子#65380;粒子源及施加在粒子上的力場。其中:力場是三維空間中對粒子運動施加外力的區域;力場對其中的粒子產生力的作用，使其具有勢能。力場是粒子系統改進的關鍵。傳統力場實質是全局力場，每個力場都遍歷整個粒子系統，即使有的力場并不作用于某些粒子，也要進行遍歷，粒子數量很多時會影響實時性。可將全局力場劃分成若干局部力場，每個局部力場都有一定作用范圍，當粒子進入該范圍內才受到它的作用。局部力場單獨作為一個模塊處理粒子運動，局部力場作用疊加符合平行四邊形法則。本方法適宜繪制在屏幕部分區域顯示的圖形，如球形禮花#65380;扁平火焰和細長煙霧等[14]。

3粒子數量優化

粒子系統的基本組成是具有一定屬性和方法的粒子，粒子數量可間接表示空間復雜度大小。粒子數量越多，可以表現的細節就越清晰，真實感就越強。但是粒子數量越多，會帶來更多的空間開銷，影響系統運行速度。如何平衡真實感和粒子數量之間的矛盾，是一個亟待解決的問題。粒子數量優化就是在不影響系統真實感的前提下，盡可能地減少粒子數量，減少空間復雜度。

3.1結構化粒子

粒子數量也是影響可視化實時性的重要因素，傳統粒子系統的特點是采用大量離散粒子表現物體，但忽略粒子之間相似性。這樣會帶來兩方面問題:首先，大量粒子耗費很多存儲空間#65380;計算和繪制時間，難以保證實時性;其次，忽略相似性影響圖形真實感。張芹等人提出基于相似關系的結構化粒子。其核心內容是先生成一個結構化粒子，然后改變其屬性，生成與之相似的粒子[7]。若要進行可視化計算，那就有規律改變其屬性，以便計算時能獲取結構化粒子生成的其他粒子屬性;否則就隨機改變其屬性，體現粒子系統復雜性和隨機性。若一個結構化粒子近似表示n個基本粒子，則理想情況下運行效率近似為原系統n倍(假設粒子動態計算與粒子數成線性關系)。

3.2LOD技術

LOD(level of detail，細節層次)技術用于繪制遠近不同區域。其原理是根據景物距視點距離，采用不同細節層次模型繪制。距離近的繪制精細些，遠的繪制粗糙些，既縮短時間，又不降低真實感。不同LOD模型制作時常采用相似幾何體不斷逼近，同時調整模型附加紋理分辨率[15]。應用LOD后，不同LOD模型之間切換容易出現突變現象。可采用中間插值使動畫變形的方法解決該問題。

3.3偽粒子系統

虛擬場景存在近大遠小透視效果。當視點與景物相距比較遠時，由于人對景物分辨率有限，主要關心畫面連續性而非景物細節，此時采用偽粒子系統優化可提高實時性[10]。該方法使用一組整體反映待做效果過程并具有alpha通道的紋理圖片，然后進行播放。

4基于粒子系統的土壤可視化優化

4.1系統概述

土壤是植物生長的基礎。構建土壤可視化模型，對于研究植物生長發育#65380;獲取土壤結構參數等具有重要意義[16]。研究表明，反映土壤結構狀況的一些參數，如土壤粒徑分布#65380;孔隙度#65380;孔隙連通狀況都表現出分形特征[17]。構成土壤主體的土壤顆粒具有分形特征，與粒子系統中的粒子相似。大量粒子無規則運動是一種穩態運動，可以模擬土壤。基于此，采用粒子系統實現了土壤的土體結構可視化。圖6表示利用粒子系統生成的三維可視化土壤。

4.2系統優化

根據本系統實現的特點，先分別采用顯示列表#65380;幾何形體優化#65380;多級粒子系統#65380;碰撞檢測與處理優化#65380;線性表等方法對系統進行優化。其中:碰撞檢測與處理優化效果最好，平均改進22.6%。最后綜合五種方法進行優化，平均改進60.2%。具體結果如下。

4.2.1顯示列表

采用顯示列表優化本系統，不同數目粒子優化前后幀頻對比如表1所示。采用本方法優化后，速度有4.7%~12.1%的改進，平均改進7.7%。

4.2.2幾何形體優化

土壤粒子共計九種:片狀#65380;鱗片狀#65380;棱柱狀#65380;柱狀#65380;棱塊狀#65380;團塊狀#65380;核狀#65380;粒狀#65380;團粒狀。其中:鱗片狀和核狀分別是由四邊形環帶構成的半橢球和整橢球。系統中具有成百上千個這樣的粒子，同時繪制降低速度。因此需簡化四邊形環帶條數和每條環帶中四邊形個數，在不失真情況下盡量提高速度。原來繪制一個鱗片狀(核狀)粒子需10(20)條由20個四邊形構成的環帶;經實驗發現，采用5(10)條由10個四邊形構成的環帶繪制鱗片狀(核狀)粒子仍不失真(優化前后基本粒子形狀見圖7)。

基于上述優化方法，不同數目粒子優化前后幀頻對比如表2所示。采用本方法優化后，速度改進12.5%~33.7%，平均改進19.6%。

4.2.3多級粒子系統

建立三級粒子系統，粒徑較小的粒子繪制成點，粒徑適中的粒子照原樣繪出，粒徑較大#65380;影響整體顯示效果和實時性的粒子忽略。采用三級粒子優化后，不同數目粒子優化前后幀頻對比如表3所示。采用本方法優化后，速度改進6.0%~10.8%，平均改進7.4%。

4.2.4碰撞檢測與處理優化

對本系統而言，采用2.1節介紹的坐標分量碰撞檢測法檢測碰撞，忽略碰撞后位置調整。不同數目粒子優化前后幀頻對比如表4所示。采用本方法優化后，速度改進19.8%~25.0%，平均改進22.6%，粒子數目越多，改進效果越明顯。

4.2.5線性表

將常用三角函數值#65380;對數函數值#65380;指數函數值用線性表存入內存，采用查找線性表代替算術運算優化系統。不同數目粒子優化前后幀頻對比如表5所示。采用本方法優化后，速度改進3.2%~9.6%，平均改進6.7%。

綜合上述五種優化方法改進系統，不同數目粒子優化前后幀頻對比如表6所示。由此可知，速度改進50.0%~81.9%，平均改進60.2%。

5結束語

本文歸納總結國內外粒子系統優化的相關研究成果，從繪制效率#65380;計算復雜性#65380;粒子數量諸方面分析探討，以提高粒子系統實時性。基于實際情況，采用部分方法在基于粒子系統的土壤可視化中進行應用，速度平均改進60.2%，在一定程度上可提高繪制效率，減少計算復雜性。文中論述的方法切實#65380;有效，具有一定的理論參考和應用價值。

參考文獻:

[1]REEVES W T. Particle system: a technique for modeling a class of fuzzy object[J]. Computer Graphics， 1983，17(3):359－376.

[2]REEVES W T，BLAU R. Approximate and probabilistic algorithms for shading and rendeing structured particle system[J]. Computer Graphics， 1985，19(3):313－322.

[3]REYNOLDS C W. Flocks， beds， and schools: a distributed beha－vioal model[J]. Computer Graphics， 1987，21(4):25－34.

[4]KARL S. Particle animation and rendering using data parallel computation[J]. Computer Graphics， 1990，24(4):405－413.

[5]STOLK J， VAN WIJK J J.Surface particles for 3D flow visualization[C]//POST F H， HIN A J. Advances in Scientific Visulaization. Berlin: Springer， 1992.

[6]UNBESCHIDEN M， TREMBILSKI A. Cloud simulation in virtual environments[C]//IEEE Visualization Proceedings. 1998:98－104.

[7]張芹，張健，閔建平.提高粒子系統實時性的方法研究[J]. 計算機工程， 2003，29(18):46－48.

[8]和平鴿工作室.OpenGL高級編程與可視化系統開發[M].北京:中國水利水電出版社，2003.

[9]禹海全，李巖，馮振聲.基于某型防空導彈的尾焰仿真研究[J].計算機仿真，2004，21(2):22－24.

[10]宿春慧，張雪蘭，李彥輝.虛擬戰場中不規則物體的實時顯示研究[J].微機發展，2004，14(5):47－49.

[11]劉宏芳.實時爆炸效果的真實感模擬[J].計算機應用，2000，20(增刊):206－207.

[12]王潤杰，田景全，倪政國.基于粒子系統的實時雨雪模擬[J].系統仿真學報，2003，15(4):495－496.

[13]馬駿，朱衡君.基于動態紋理和粒子系統的噴泉模擬[J].北京交通大學學報，2005，29(1):90－94.

[14]于靜怡，朱衡君.基于局部力場的粒子系統仿真[J].計算機仿真，2006，23(6):184－188.

[15]陶偉，應文燁.基于Vega的虛擬海洋場景視景仿真[J].航海工程，2005(6):1－3.

[16]KAI L N. Fractal geometry of root systems: field observations of contrasting genotypes of common bean[J]. Plant and Soil， 1999，206:181－190.

[17]李保國.分形理論在土壤科學中的應用及其展望[J].土壤學進展，1994，22(1):1－9.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”