袁昱緯，劉傳輝，全吉成，，王宏偉，劉 宇

（1.海軍航空工程學(xué)院電子信息工程系，山東煙臺264001；2.空軍航空大學(xué)航空航天情報系，長春130022）

大規(guī)模場景的百分比近鄰軟陰影繪制算法

袁昱緯1，劉傳輝1，全吉成1，2，王宏偉2，劉 宇2

（1.海軍航空工程學(xué)院電子信息工程系，山東煙臺264001；2.空軍航空大學(xué)航空航天情報系，長春130022）

針對傳統(tǒng)軟陰影繪制算法在面對大規(guī)模三維場景時繪制效率較低的問題，文章基于四叉樹加速結(jié)構(gòu)的陰影圖構(gòu)建，研究了鄰域節(jié)點的搜索方法和遍歷順序的選擇方法，提出了一種基于四叉樹的百分比近鄰軟陰影算法。實驗結(jié)果表明，與傳統(tǒng)算法相比，該方法能夠有效提高大規(guī)模三維場景的軟陰影繪制效率，且性能穩(wěn)定，可以渲染出高質(zhì)量的軟陰影效果。

三維場景；軟陰影；百分比近鄰濾波；四叉樹；鄰域搜索

陰影的計算和繪制是虛擬三維場景繪制中不可或缺的重要組成部分[1]。對于僅存在點光源的理想場景而言，采樣點僅存在位于陰影中和陰影外2種情況，這種陰影稱為硬陰影，不存在柔和的半影區(qū)。但是在三維場景的渲染中，為了提高場景的真實感，還需要繪制出面光源或體光源產(chǎn)生的半影效果，這種效果稱為軟陰影。軟陰影雖然更加復(fù)雜，但是可以產(chǎn)生柔和的過渡效果，渲染陰影的真實感更強[2]。

常用的陰影繪制算法包括陰影圖算法[3-5]、陰影體算法[6-7]、光線跟蹤算法[8-9]和光子映射算法[10]等，這些算法并不能直接繪制出高質(zhì)量的軟陰影，一般需要采用與濾波運算結(jié)合的方法，不對半影區(qū)的范圍進(jìn)行精確計算，僅在符合視覺規(guī)律的前提下，采用濾波算法消除鋸齒狀走樣和清晰的邊界?；跒V波的軟陰影算法主要包括百分比近鄰軟陰影算法[11]、時刻陰影圖[12]，基于層次的濾波預(yù)測陰影圖[13]、可分離軟陰影圖[14]，以及基于遮擋區(qū)域映射的軟陰影[15]等方法，但是當(dāng)三維場景由大量幾何數(shù)據(jù)構(gòu)成時，其中幾何體包含上萬甚至幾百萬個以上的多邊形[16]，即面對大規(guī)模三維場景時，由于基于陰影圖的算法計算量很大，使這些方法的軟陰影計算速度往往無法滿足實時性要求。本文針對大規(guī)模三維場景，通過為陰影圖構(gòu)建空間加速結(jié)構(gòu)，研究相應(yīng)的搜索、遍歷方法和濾波運算，提出改進(jìn)的百分比近鄰軟陰影算法，加快軟陰影計算速度，提高大規(guī)模三維場景的軟陰影繪制效率和質(zhì)量。

1 百分比近鄰軟陰影算法及其存在的問題

百分比近鄰軟陰影（Percentage Closer Soft Shadow，PCSS）算法是基于百分比近鄰濾波（Percentage Closer Filtering，PCF）提出的。該算法在傳統(tǒng)陰影圖算法中采用PCF濾波運算，能根據(jù)場景光源和幾何體的相對關(guān)系產(chǎn)生柔和的半影區(qū)域，軟陰影質(zhì)量較高。PCSS算法無須構(gòu)建多個陰影圖，無須對陰影圖進(jìn)行除濾波之外的處理，具有陰影圖算法的一般優(yōu)點[17]，工程實現(xiàn)較簡單。

但是當(dāng)面對大規(guī)模三維場景時，PCSS算法就會出現(xiàn)一些不足之處，主要包括：①濾波運算效率較低。因為在大規(guī)模三維場景的陰影繪制時，為避免出現(xiàn)走樣和鋸齒現(xiàn)象，有時需要較大的半影區(qū)域，隨著半影區(qū)的增大，所需的濾波器尺寸增大，濾波的時間開銷也隨著增加；②受鄰域搜索算法效率的限制。大規(guī)模三維場景的陰影圖分辨率很高，占用的存儲空間較大，而濾波運算涉及陰影圖中大量采樣點的鄰域搜索，在龐大的線性存儲空間中進(jìn)行鄰域查詢的效率通常很低。

針對上述缺陷，本文基于四叉樹空間加速結(jié)構(gòu)，提高了濾波運算效率和鄰域搜索效率，改進(jìn)了PCSS軟陰影繪制算法，加快了大規(guī)模場景的軟陰影繪制速度。

2 基于四叉樹的陰影圖搜索加速結(jié)構(gòu)

大規(guī)模三維場景的陰影圖的數(shù)據(jù)量一般很大，包含的采樣點很多，在處理與搜索的過程中速度較慢，且加載到內(nèi)存的時間較長。因此，本文在進(jìn)行軟陰影計算前，基于四叉樹結(jié)構(gòu)對三維場景的陰影圖建立空間加速結(jié)構(gòu)，形成金字塔狀的多分辨率結(jié)構(gòu)，當(dāng)需要不同分辨率的陰影信息時，可以快速地從加速結(jié)構(gòu)中提取。同時，這種預(yù)構(gòu)建的多分辨率結(jié)構(gòu)可以大幅度減少鄰域搜索的計算量。

基于四叉樹的陰影圖搜索加速結(jié)構(gòu)的構(gòu)建過程為：將原始的陰影圖均勻分塊后作為四叉樹的葉子節(jié)點，分塊的大小一般為512×512或256×256個采樣點。然后，依次遍歷相鄰的2×2個分塊，對這4個分塊拼接后重采樣，使其分辨率降低一半，作為四叉樹的上一級節(jié)點。繼續(xù)這樣操作下去，直至四叉樹的根節(jié)點，完成基于四叉樹的陰影圖搜索加速結(jié)構(gòu)的構(gòu)建。四叉樹中的各層分別對應(yīng)不同分辨率的陰影圖，從四叉樹的底層到頂層，分辨率越來越低。

3 基于四叉樹的PCSS改進(jìn)算法

3.1 四叉樹結(jié)構(gòu)的鄰域搜索

在四叉樹結(jié)構(gòu)中進(jìn)行PCF操作時，涉及大量陰影圖分塊的鄰域搜索操作，由于每次PCF濾波操作僅在四叉樹中的某一層級進(jìn)行，且濾波所需的深度值分布在其中心的一個小區(qū)域，陰影圖分塊與其鄰域分塊在大部分情況下都共用了同一個父節(jié)點，每一次鄰域搜索不必從根節(jié)點開始，只須回溯到2節(jié)點分開的父節(jié)點，可以有效減少鄰域搜索的計算量。如圖1所示，當(dāng)節(jié)點1進(jìn)行PCF濾波計算時，節(jié)點2與其共用同一個父節(jié)點，僅須回溯一個層級即可。節(jié)點3與節(jié)點1，雖然不是同一父節(jié)點下的兄弟節(jié)點，但大部分搜索路徑相同，無須重復(fù)搜索，僅須要向上回溯2個層級即可。

3.2 鄰域節(jié)點的遍歷順序選擇

在濾波器的滑動和運算過程中，通常需要同時訪問若干個節(jié)點。根據(jù)四叉樹的鄰域搜索方法，每次相鄰節(jié)點的訪問僅須回溯到其遍歷路徑分叉的層級，提高節(jié)點鄰域搜索時的計算效率。

基于上述思想，本文通過選擇須要回溯最少層級數(shù)的遍歷順序，實現(xiàn)減少在回溯過程中的搜索次數(shù)。如圖2所示，圖中的實線和虛線分別表示從一個節(jié)點到另一個節(jié)點存在2條可能的路徑。

在采用圖2中2條路徑進(jìn)行遍歷時，須要回溯到的最高層級分別為Li或Lj。

遍歷時，可以訪問Li1次、Lj2次，或訪問Li1次、Lj2次。為了縮短回溯路徑的長度，減少回溯操作的次數(shù)，在選擇遍歷順序時，盡量讓更高的層級只回溯到一次，如圖2中的虛線路徑。對于某些尺寸濾波器，鄰域搜索可能存在較多遍歷順序選擇，可以采用預(yù)先計算的最優(yōu)搜索順序表。遍歷時，僅須在表中進(jìn)行簡單查找，即可獲得當(dāng)前所需的遍歷順序，減少路徑選擇時的重復(fù)計算和判斷。

在搜索的過程中，僅須要存儲回溯到的層級的路徑，沒必要使用一個堆棧來完整存儲整個四叉樹的節(jié)點，減少內(nèi)存空間。

3.3 PCF濾波器的濾波操作優(yōu)化

在采用PCSS算法進(jìn)行軟陰影繪制之前，須要選擇合適的濾波器尺寸。首先將屏幕空間的像素投影變換到三維場景空間中，計算屏幕中每個像素在三維場景空間中對應(yīng)區(qū)域的大小。濾波器的尺寸應(yīng)當(dāng)比該區(qū)域略大，以保證足夠的半影區(qū)域，并防止出現(xiàn)明顯的走樣現(xiàn)象。

當(dāng)使用濾波器進(jìn)行濾波運算時，一般最多同時訪問4個節(jié)點。當(dāng)濾波器須要同時訪問多個節(jié)點時，為了提高濾波計算效率，本文為每個訪問到的節(jié)點對應(yīng)的陰影圖深度值產(chǎn)生一個模板，以快速清除在濾波范圍之外的深度值，如圖3所示。

PCF濾波器和訪問的節(jié)點都將模板與對應(yīng)的陰影圖按位與運算后，可以快速濾波范圍內(nèi)的深度值，統(tǒng)計陰影圖中非0的深度值并與采樣點的深度值進(jìn)行比較，按照PCF算法得到位于陰影中的采樣點占濾波器總采樣點的百分比，獲得濾波后采樣點的陰影值，即為PCF濾波運算的結(jié)果。

忽聽一人道：“大哥，既然說到公事，現(xiàn)在公事未完，怎可你先來？還是大哥殿后，我先來。”只見攝魂寅客李雙岱搶步上前，迅速來到牌坊下，亮出兵器。讓秦鐵崖詫異的是，李雙岱所使的卻不是佩刀。

3.4 基于四叉樹的PCSS軟陰影改進(jìn)算法

為了保證繪制軟陰影效果，通常采用濾波器進(jìn)行濾波操作。但是，大規(guī)模三維場景的陰影圖分辨率很高，如果以同一個分辨率的陰影圖來進(jìn)行濾波操作，那么在距離視點較遠(yuǎn)的區(qū)域就需要一個較大的濾波器內(nèi)核，以確保陰影具有足夠大的半影區(qū)，保證軟陰影的繪制效果。但是濾波器內(nèi)核的增大，必然導(dǎo)致濾波器在濾波過程中運算規(guī)模的增大。為了避免過大的運算規(guī)模，同時保證軟陰影質(zhì)量，本文對基于四叉樹的PCSS軟陰影繪制算法進(jìn)一步優(yōu)化。

本文考慮在四叉樹完成構(gòu)建后，自下而上地處理最低層級至某個層級中每個陰影輪廓上的節(jié)點，以該節(jié)點為中心，按照PCF濾波器原理，計算該節(jié)點的陰影占有率，并存儲在節(jié)點中，這個陰影占有率的計算過程在四叉樹中自下而上地進(jìn)行，相當(dāng)于濾波的過程。上述操作在陰影繪制之前完成。

當(dāng)進(jìn)行濾波時，只須在四叉樹中找到對應(yīng)節(jié)點并獲得其中的陰影占有率值，即可停止搜索，該陰影占有率就相當(dāng)于濾波后的陰影值。如果需要大尺寸濾波器的濾波效果，僅須對這些節(jié)點中的陰影占有率值使用小尺寸濾波器進(jìn)行濾波，不須要在原始分辨率下進(jìn)行PCF濾波，而是在加速結(jié)構(gòu)的某一級對節(jié)點保存的陰影占有率值進(jìn)行濾波計算，以獲得大尺寸濾波器濾波的效果。濾波的加速結(jié)構(gòu)層級越高，獲得的半影區(qū)范圍越大，陰影效果越柔和。

4 實驗與分析

本文實驗平臺的軟硬件環(huán)境為：CPU Intel Core i7-67003.4GHz，RAM 32GB，NVIDIA GTX 1070，Win?dows 7 Ultimate x64操作系統(tǒng)。實驗素材為Chalmers大學(xué)提供的2個大規(guī)模三維場景，Closed Citadel場景和Villa場景，如圖4所示。上述2個實驗場景分別包含6.14×105和8.89×104個三角形面，以及3.10×106和5.01×104個頂點。實驗的對比算法包括不同尺寸濾波器下的本文改進(jìn)PCSS算法，以及不同層級數(shù)量的級聯(lián)陰影圖算法（CSM）[18]。對比實驗包括陰影計算效率和軟陰影繪制質(zhì)量2個方面。在實驗前已完成了本文提出的基于四叉樹的陰影圖遍歷加速結(jié)構(gòu)的構(gòu)建，實驗時不重新構(gòu)建，繪制時僅須對加速結(jié)構(gòu)進(jìn)行搜索和遍歷。

4.1 陰影計算效率測試

在陰影計算效率測試中，本文以Closed Citadel場景為例，測試了本文提出的PCSS算法在優(yōu)化前后的時間開銷，包含本文提出的改進(jìn)PCSS算法在3×3濾波器和7×7濾波器濾波時的情況，以及相應(yīng)算法在改進(jìn)前的情況，如圖5所示。實驗時，視角飛過三維場景上方，記錄每種方法在每一幀所需的陰影計算時間。圖中橫坐標(biāo)為在場景中連續(xù)變化的視角對應(yīng)的連續(xù)的每一幀，縱坐標(biāo)為時間開銷。

圖5可以看出，在3×3濾波器下的時間開銷平均縮短55.1%，在7×7濾波器下的時間開銷平均縮短42.9%，本文改進(jìn)的PCSS算法的時間開銷明顯優(yōu)于改進(jìn)前，且相對穩(wěn)定。其原因是當(dāng)計算距離視點較遠(yuǎn)的場景區(qū)域時，濾波運算在葉子節(jié)點層的鄰域搜索涉及的節(jié)點較多，改進(jìn)前的算法需要在節(jié)點之間反復(fù)回溯。而采用改進(jìn)后的PCSS算法之后，可以在加速結(jié)構(gòu)的較高層級停止搜索，無須每次計算都到達(dá)葉子節(jié)點層，減少了運算量。

在與其他算法的對比實驗中，包含本文提出的改進(jìn)PCSS算法在3×3濾波器和7×7濾波器濾波時的情況，以及采用4級CSM算法和8級CSM算法的情況，CSM算法在繪制軟陰影時，采用3×3的PCF濾波。對于CSM算法，本文對其視域進(jìn)行分割時，采用文獻(xiàn)[16]中均勻分割和對數(shù)分割相結(jié)合的方法，并應(yīng)用于各個實驗場景中。

實驗時，視角飛過三維場景上方，記錄每種方法在每一幀所需的陰影計算時間。如圖6、7所示，圖中橫坐標(biāo)為在場景中連續(xù)變化的視角對應(yīng)的連續(xù)的每一幀，縱坐標(biāo)為時間開銷。

此外，從圖6、7的統(tǒng)計數(shù)據(jù)還可以看出，本文算法在使用7×7濾波器時的時間開銷與使用3×3濾波器相比，在2個實驗場景中分別平均增加19.4%和32.1%。隨著濾波器尺寸的增大，運算時間的增長幅度并沒有同比例增大。

4.2 軟陰影繪制質(zhì)量測試

為了對比軟陰影繪制算法的繪制質(zhì)量，本文將改進(jìn)的PCSS算法、改進(jìn)前的PCSS算法[17]和傳統(tǒng)陰影圖算法進(jìn)行了對比，其中，傳統(tǒng)陰影圖算法按照文獻(xiàn)[19]中的傳統(tǒng)陰影圖算法流程進(jìn)行了實現(xiàn)。測試以Closed Citadel場景為例，在構(gòu)建加速結(jié)構(gòu)和陰影圖時，邊長的分辨率都設(shè)定為2 K。PCSS算法采用7×7濾波器。圖8為陰影繪制效果的局部放大圖。

從圖8中可以看出，陰影圖算法在某些區(qū)域的陰影邊緣的繪制質(zhì)量較低，具有較明顯的方塊狀現(xiàn)象，而PCSS算法在繪制的陰影邊緣存在一定范圍的柔和的半影區(qū)，繪制效果較好，且改進(jìn)前后的PCSS軟陰影繪制效果幾何沒有差別。

5 結(jié)論

本文針對大規(guī)模三維場景，提出一種基于四叉樹結(jié)構(gòu)的PCSS軟陰影算法。通過為三維場景的陰影圖構(gòu)建基于四叉樹的加速結(jié)構(gòu)，利用優(yōu)化的鄰域節(jié)點搜索方法、遍歷順序選擇方法、PCF濾波方法，并進(jìn)一步改進(jìn)PCSS算法，能夠利用四叉樹節(jié)點中已經(jīng)存儲的陰影占有率，無須在原始陰影圖分辨率下進(jìn)行濾波操作。同時，可以共用遍歷路徑中相同的部分，有效減少濾波過程中的計算量，提高軟陰影繪制速度，且性能穩(wěn)定，能夠渲染出高質(zhì)量的軟陰影效果。

[1]SUFFER K.光線跟蹤算法技術(shù)[M].劉天慧，譯.北京：清華大學(xué)出版社，2011：1-3.SUFFER K.Ray tracing from the ground up[M].LIU TIANHUI，Translated.Beijing：TsinghuaUniversity Press，2011：1-3.（in Chinese）

[2]WOO A，POULIN P.Shadow algorithms data miner[M].Florida：Chemical Rubber Company Press，2012：2-10.

[3]SELGRAD K，DACHSBACHER C，MEYER Q，et al.Filtering multi-layer shadow maps for accurate soft shadows[J].Computer Graphics Forum，2015，34（1）：205-215.

[4]SCANDOLO L，BAUSZAT P，EISEMANN E.Merged multiresolution hierarchies for shadow map compression[J].Computer Graphics Forum，2016，35（7）：383-390.

[5]郭釗，范湘濤，譚劍.基于光源空間透視的平行分割陰影圖算法[J].地理與地理信息科學(xué)，2016，32（1）：39-43.GUO ZHAO，F(xiàn)AN XIANGTAO，TAN JIAN.Parallel split shadow map algorithm based on light space perspective[J].Geography and Geo-Information Science，2016，32（1）：39-43.（in Chinese）

[6]KOLIVAND H，SUNAR M S.Survey of shadow volume algorithms in computer graphics[J].IETE Technical Review，2013，30（1）：38-46.

[7]GERHARDS J，MORA F，AVENEAU L，et al.Partitioned shadow volumes[J].Computer Graphics Forum，2015，34（2）：549-559.

[8]ZHOU P，MENG X.SIMD friendly ray tracing on GPU[C]//International Conference on Computer-Aided Design and Computer Graphics.Jinan：Cad/Graphics，2011：87-92.

[9]NAH J H，KIM J W，PARK J，et al.HART：A hybrid architecture for ray tracing animated scenes[J].IEEE Transactions on Visualization and Computer Graphics，2015，21（3）：389-401.

[10]孟祥雨.基于光子映射的分布式全局光照計算方法研究[D].濟(jì)南：山東大學(xué)，2016.MENG XIANGYU.Distributed global illumination method based on photon mapping[D].Jinan：Shandong University，2016.（in Chinese）

[11]FERNANDO R.Percentage-closer soft shadows[C]//Acm Siggraph 2005 Sketches.ACM，2005：1-35，38.

[12]PETERS C，KLEIN R.Moment shadow mapping[C]//Proceedings of the 19thSymposium on Interactive 3D Graphics and Games.San Francisco：Association for Computing Machinery，2015：7-14.

[13]ANDERSSON M，HASSELGREN J，MUNKBERG J，et al.Filtered stochastic shadow mapping using a layered approach[J].Computer Graphics Forum，2015，34（8）：119-129.

[14]BUADES J M，GUMBAU J，CHOVER M.Separable soft shadow mapping[J].The Visual Computer，2016，32（2）：1-12.

[15]謝依妨，楊紅雨.基于遮擋區(qū)間映射的軟陰影的研究與實現(xiàn)[J].計算機工程與設(shè)計，2015，36（3）：687-692.XIE YIFANG，YANG HONGYU.Research and implementation of soft shadow based on occlusion interval mapping[J].Computer Engineering and Design，2015，36（3）：687-692.（in Chinese）

[16]付杰.大規(guī)模場景實時渲染若干技術(shù)問題研究[D].西安：西北大學(xué)，2009.FU JIE.Study on some technical problems in real-time rendering of large-scale scenes[D].Xi’an：Northwest University，2009.（in Chinese）

[17]晏福興，王毅剛.改進(jìn)的百分比靠近軟陰影技術(shù)的研究與實現(xiàn)[J].計算機工程與應(yīng)用，2011，47（1）：185-187.YAN FUXING，WANG YIGANG.Research and implement of improved percentage-closer soft shadows[J].Computer Engineering and Applications，2011，47（1）：185-187.（in Chinese）

[18]ZHANG F，SUN H，XU L，et al.Parallel-split shadow maps for large-scale virtual environments[C]//Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications.Hongkong：Association for Computing Machinery，2006：311-318.

[19]劉志旭.基于可視度圖的實時軟陰影算法研究[D].北京：中國石油大學(xué)，2011.LIU ZHIXU.Research on real-time soft shadow algorithm based on visibility map[D].Beijing：China University of Petroleum，2011.（in Chinese）

簡訊：

學(xué)院“圖學(xué)與機械課程示范教學(xué)與創(chuàng)新教學(xué)法”觀摩競賽獲佳績

2017年7月17日至19日，海軍航空工程學(xué)院飛行器工程系機械基礎(chǔ)教研室趙敏、周仙娥、唐偉峰三位教員赴蘭州參加第四屆全國高等學(xué)校教師圖學(xué)與機械課程示范教學(xué)與創(chuàng)新教學(xué)法觀摩競賽。該項賽事是由教育部工程圖學(xué)課程教學(xué)指導(dǎo)委員會、軍隊院校圖學(xué)與機械基礎(chǔ)教學(xué)協(xié)作聯(lián)席會、中國圖學(xué)學(xué)會制圖技術(shù)專業(yè)委員會主辦，蘭州交通大學(xué)承辦，高等教育出版社贊助的全國性教學(xué)比賽。本次比賽共有來自48所地方與部隊高校的98名教師參賽。比賽設(shè)一等獎（20%）、二等獎（25%）、三等獎（25%）。比賽中，三位教員展現(xiàn)了優(yōu)異的教學(xué)素質(zhì)和講臺風(fēng)采，給各位專家和評委留下了深刻的印象，獲得了較高的評價。經(jīng)過激烈角逐，3名教員均取得優(yōu)異成績，2人獲得一等獎，1人獲得二等獎。

學(xué)院舉辦“2017年中國國際飛行器設(shè)計挑戰(zhàn)賽暨科研類全國航空航天模型公開賽”

2017年5月28日至29日，由國家體育總局航管中心、中國航空運動協(xié)會主辦，海軍航空工程學(xué)院承辦的“2017年中國國際飛行器設(shè)計挑戰(zhàn)賽暨科研類全國航空航天模型公開賽”在煙臺舉行。來自中國民航大學(xué)、南京航空航天大學(xué)、魯東大學(xué)、解放軍信息工程大學(xué)、陸軍軍官學(xué)院、武警工程大學(xué)等全國17所高校的147名運動員參加比賽。結(jié)合本次比賽安排，組委會特別邀請清華大學(xué)、北京航空航天大學(xué)的知名教授和部隊專家開設(shè)了3場學(xué)術(shù)講座。

“中國國際飛行器設(shè)計挑戰(zhàn)賽暨科研類全國航空航天模型公開賽”自2004年起已成功舉辦13屆。截止2016年，競賽共吸引了來自109所院校的2100余名選手參加，賽事規(guī)模再創(chuàng)歷史新高，已經(jīng)成為國內(nèi)水平最高、規(guī)模最大、等級最高的科研類航空航天模型賽事，與歐洲ACC競賽和美國SAE競賽被并稱為世界三大高校科研類航空航天模型賽事。

本屆公開賽共設(shè)置“電動滑翔機”、“地偵察與打擊”、“二對二遙控空戰(zhàn)”、“模型火箭運載與返回”4個項目。經(jīng)過一天的緊張角逐，最終，海軍航空工程學(xué)院代表隊獲得“電動滑翔機”、“對地偵察與打擊項目”第一名。

Algorithm of Soft Shadow Rendering for Large Scale Scene

YUAN Yuwei1,LIU Chuanhui1,QUAN Jicheng1,2,WANG Hongwei2,LIU Yu2
（1.Department of Electronic and Information Engineering,NAAU,Yantai Shandong 264001,China;2.Department of Aeronautic and Astronautic Intelligence,Aviation University of Air Force,Changchun 130022,China）

In order to overcome the problems of low efficiency of the traditional soft shadow rendering algorithm in the face of large scale 3D scene,in this paper,an acceleration structure based on the quad tree was built for shadow map of 3D scene,the method for searching neighbor node and the method for selecting traversal sequence was studied,and a percent?age closer soft shadow algorithm based on quad tree was proposed.The experimental results indicated that,compared with the traditional algorithm,the proposed algorithm could effectively improve the soft shadow rendering efficiency of large scale 3D scene,and the performance was stable,the high quality soft shadows could be rendered.

3D scene;soft shadow;percentage closer filtering;quad tree;neighborhood search

TP391.9

A

1673-1522（2017）04-0341-06

10.7682/j.issn.1673-1522.2017.04.001

2017-03-04；

2017-07-12

國家自然科學(xué)基金資助項目（61301233）；吉林省自然科學(xué)基金資助項目（20130101069JC）

袁昱緯（1988-），男，博士生。