城市環(huán)境下射線追蹤加速算法范文

本站小編為你精心準(zhǔn)備了城市環(huán)境下射線追蹤加速算法參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

在三維城市建設(shè)的過程中，為了使得城市環(huán)境更具有真實感，往往需要為城市環(huán)境模擬一太陽光源，實現(xiàn)由于光照而引起的三維場景下的各種表現(xiàn)特征。研究在三維場景下的光線（射線）傳播路徑具有重要的應(yīng)用價值，在廣播數(shù)字電視、城市移動多媒體、移動通訊等領(lǐng)域，信號的傳播都是利用電磁波進行的，而光本身也是一種電磁波，它們傳播的方式一致。因此研究射線追蹤技術(shù)，便可以將其引入到上述領(lǐng)域中開展應(yīng)用。首先通過射線追蹤技術(shù)找到發(fā)出的信號到達信號接收端的路徑，然后結(jié)合信號在發(fā)射、路徑傳播過程中的電波傳播特征，從而得到信號最終到達信號接收端的信號強度，實現(xiàn)基于射線追蹤技術(shù)的電波傳播預(yù)測，為廣播數(shù)字電視、城市移動多媒體、移動通訊等領(lǐng)域的覆蓋規(guī)劃提供決策支持。本文在三維城區(qū)環(huán)境下，研究射線追蹤技術(shù)的理論方法，即，某一光源（信號發(fā)射源）發(fā)出一條光線（射線）后，通過直射、反射、繞射等最終到達地面的光線（射線）傳播路徑。

1射線追蹤介紹

射線跟蹤方法的理論基礎(chǔ)是幾何光學(xué)（GeometricalOptics，GO）理論，即，光在空間中以射線的方式進行傳播，在遇到障礙物時，遵循光的反射定律會產(chǎn)生反射現(xiàn)象，射線追蹤即模擬光在空間中的反射路徑。對于空間障礙物邊緣發(fā)射的繞射，則引入幾何繞射理論和一致性繞射理論，模擬信號在遇到障礙物時發(fā)生的繞射情況。圖1為信號經(jīng)過直射、反射、衍射（繞射）后到達信號接收端的示意圖。由于從一個信號發(fā)射端會發(fā)出無數(shù)條射線，而且當(dāng)遇到障礙物時，每條射線又會在障礙物表面發(fā)生反射、繞射等顯現(xiàn)，因此在三維空間中找到所有射線的計算量巨大，甚至是計算機不可承受的。本文在充分研究傳統(tǒng)射線追蹤算法的基礎(chǔ)上，提出基于城市布局分區(qū)、降維、加速多鏡法的射線追蹤技術(shù)，提高射線追蹤算法的計算效率。

2技術(shù)方法

2.1分區(qū)加速算法

2.1.1城市布局分區(qū)城市的布局特征與自然環(huán)境密切聯(lián)系，例如武漢市城市總體布局以長江的走勢為基礎(chǔ)向東西兩側(cè)進行延伸。其街道路網(wǎng)布局方式依據(jù)長江的走勢布設(shè)，形成依托地理環(huán)境的獨特城市布局。城市的布局特征與人文因素有關(guān)，以城市交通為例，交通線路的發(fā)展會對城市布局產(chǎn)生深遠影響。以北京市為例，北京市隨著人口激增、經(jīng)濟不斷增長，逐漸在二環(huán)線的基礎(chǔ)上修建三環(huán)、四環(huán)、五環(huán)、六環(huán)，而隨著每一次環(huán)線的建設(shè)，北京市都會在此基礎(chǔ)進行城市擴張。北京市城市布局以環(huán)線為基本脈絡(luò)，形成網(wǎng)狀規(guī)則的布局。城市空間布局綜合考慮地理、人文等因素（如水系、交通等因素），或依據(jù)現(xiàn)有地理因素建設(shè)，形成不規(guī)則布局形狀，或依據(jù)人文環(huán)境建設(shè)相對規(guī)則的布局；城市內(nèi)部結(jié)構(gòu)布局則根據(jù)總體布局成相對規(guī)則格局。如武漢市城區(qū)內(nèi)部布局依據(jù)長江的走勢而成相對規(guī)則的塊狀布局；北京市城區(qū)內(nèi)部布局以長安街為中軸線，以道路、河流等組成相對規(guī)則塊狀結(jié)構(gòu)。

2.1.2空間索引機制由于城市地理環(huán)境的復(fù)雜性、數(shù)據(jù)的海量性，因此如何快速、高效地索引數(shù)據(jù)便成為射線追蹤實現(xiàn)的關(guān)鍵。本文充分借鑒地圖分幅的原理，對于大范圍區(qū)域首先采用規(guī)則格網(wǎng)的方式對城市區(qū)域進行劃分，建立規(guī)則格網(wǎng)空間索引。在劃分的城市格網(wǎng)的基礎(chǔ)上，結(jié)合城市由于地理、人文因素所形成的不規(guī)則塊狀結(jié)構(gòu)，對基本格網(wǎng)進一步劃分，采用CELL樹結(jié)構(gòu)對規(guī)則格網(wǎng)下的空間建立空間索引。如圖2所示。圖3為北京市海淀區(qū)五環(huán)內(nèi)部分區(qū)域。從圖上可以看出該區(qū)域被五環(huán)線、京藏高速、學(xué)院路、荷清路、學(xué)清路等幾條主要道路劃分為塊狀結(jié)構(gòu)，因此，以這幾條路為骨干線，對該區(qū)域進行分塊處理，得到分塊布局圖。圖中將區(qū)域劃分為13個不規(guī)則區(qū)域，其命名形如J50E0100120008，其中前10位表示方格網(wǎng)編號，最后4位表示在格網(wǎng)中的編號。

2.2降維加速算法降維法是在射線追蹤過程中，將三維環(huán)境下的建筑物進行投影，變?yōu)槎S場景后進行射線計算。該算法適用于信號發(fā)射端高度低于建筑物的情況。如圖4所示，信號發(fā)射端距離地面高度為h，障礙物1的高度為H1，障礙物2的高度為H2，且圖中信號發(fā)射端發(fā)出兩條射線，射線1和射線2，射線1與水平方向的夾角為a，為仰角，射線2與水平方向的夾角為b，為俯角。可以看出射線1不能到達地面接收端，射線2可以到達信號接收端；同時由于障礙物1對位于其后面的障礙物2相對于信號發(fā)射端發(fā)射的信號而言造成了部分遮擋，而射線可見部分與水平面的夾角均為仰角，即由信號發(fā)射端直接到達障礙物2的射線不能通過反射到達信號接收端；位于射線3和射線4之間的射線都可以直接到達障礙物2，但是由于其夾角都為仰角，所以這些射線經(jīng)過障礙物2的反射后會向海拔高度更高的位置反射，因此信號無法通過反射射線到達信號接收端。由于當(dāng)信號發(fā)射端的高度低于障礙物高度所具有的這種性質(zhì)，即一旦距離信號發(fā)射端較近障礙物對較遠障礙物造成了遮擋，則信號不能通過反射射線到達較遠障礙物。因此，基于射線傳播的這種性質(zhì)，可以將三維空間的建筑物先投影到二維平面上，在二維平面內(nèi)對投影的建筑物進行求交運算，求得射線在二維平面內(nèi)的傳播路徑，一旦收發(fā)點之間的傳播路徑被找到，則將在二維平面內(nèi)的傳播路徑轉(zhuǎn)化到三維空間中。由于在二維平面內(nèi)的求交運算較三維空間簡單得多，所以可以減少運算量，從而提高射線追蹤的運算效率。

2.3朝向背向、遮擋測試

2.3.1建筑物朝向、背向測試當(dāng)一束光線射向建筑物時，建筑物的某些面會因為處在光線的背面而不能進行反射。對于處在背向光線傳播方向的面，可以不參與反射計算，這樣可以提高計算效率，因此需要進行建筑物朝向、背向測試。在計算中，通過射線向量與面的夾角來判斷某面是否背向射線。在實際計算中利用面的法向量與射線之間的夾角來判斷面與射線的關(guān)系，如果兩向量乘積，則建筑物朝向射線；反之，則背向射線。如圖5面的法向量，面的法向量，信號發(fā)射塔發(fā)出一射線R，該射線與形成的夾角為，，由于為鈍角，所以N<0，則面對射線R可見。當(dāng)一束源點向某一方向發(fā)出射線時，首先進行建筑物的朝向、背向測試，判斷建筑物的側(cè)面與射線的朝向情況。如果面朝向射線，則射線與面之間有可能存在視距路徑；如果面背向射線，則射線和面之間不可能存在視距路徑。

2.3.2遮擋測試在對建筑物完成朝向、背向測試后，要對建筑物的面進行遮擋測試，判斷建筑物的面是否與源點可視。當(dāng)信號發(fā)射端的高度小于建筑物高度時，信號發(fā)射端發(fā)出的射線不能通過直達射線到達建筑物的頂面；同時，當(dāng)信號發(fā)射端的高度高于建筑物高度，但是在信號發(fā)射端和建筑物之間有另一障礙物，且該障礙物的高度大于信號發(fā)射端的高度時，此時直射射線也不能到達建筑物頂面以及垂直面。如圖6中，障礙物2的高度大于信號發(fā)射端的高度，即此時信號不能到達障礙物2的頂面；障礙物3的高度小于信號發(fā)射端的高度，即此時信號被障礙物2遮擋，不能到達障礙物3。因此，在這種情況下，建筑物的頂面對于射線不可視，而且也不能通過頂面到達位于某一建筑物后方的建筑物，可將建筑物三維場景通過投影變換轉(zhuǎn)化為二維情況，進而求信號發(fā)射源點的可視面。由于二維的求交運算較三維簡單，所以通過這種方式可以提高計算效率。圖7為將某區(qū)域三維空間進行投影后的二維空間略圖。從圖中可以看出在信號發(fā)射端北方向，且距離發(fā)射端最近的建筑物是建筑物4。通過朝向、背向測試可知，建筑物4的面1位于信號發(fā)射端的可視區(qū)域內(nèi)，面2、3、4都位于信號發(fā)射端的背面，所以為非可視區(qū)域。對于建筑物4的面1，則分別連接信號發(fā)射端與面1兩個端點形成兩條射線，其夾角為a1，則位于該夾角內(nèi)的所有建筑物的面均不可見。從圖中可以看到，建筑物1和建筑物2的所有面以及建筑物3的面4的部分區(qū)域均在該夾角內(nèi)，所以這些面均不可見。對距離信號發(fā)射端最近的第一個建筑物以及在其射線形成的夾角內(nèi)的建筑物進行可視判斷后，按照一定方向（本文按順時針方向）繼續(xù)查找距離信號發(fā)射端較近的建筑物，圖中為建筑物3。建筑物3和建筑物4形成的可視區(qū)夾角為a2，從而可以判斷位于該區(qū)域內(nèi)的可視面，即建筑物3的面1以及部分面4。以此類推，得到可視夾角，即信號發(fā)射端在方向上都被判斷，從而得到信號發(fā)射端的所有可視區(qū)域。

3算法流程

3.1建立三維城市地理環(huán)境數(shù)據(jù)庫首先，搜集城市環(huán)境的矢量數(shù)據(jù)，包括建筑物數(shù)據(jù)的坐標(biāo)系統(tǒng)、各個建筑物的位置信息、各建筑物的高度信息、建筑物形狀特征，組成建筑物的每個垂直面和頂面坐標(biāo)以及介電特性。然后對建筑物數(shù)據(jù)進行預(yù)處理，主要包括：對城市建筑不同坐標(biāo)系的處理、對建筑物高度的統(tǒng)一求解以及對建筑物形狀的統(tǒng)一處理。當(dāng)將所有的城市建筑數(shù)據(jù)處理完畢后，進行數(shù)據(jù)庫的建庫工作。在對城市建筑物進行建庫時，要充分考慮城市建筑的布局特征，首先根據(jù)城市比例尺劃定規(guī)則格網(wǎng)，建立索引，然后根據(jù)在規(guī)則格網(wǎng)內(nèi)的城市布局建立CELL樹索引。

3.2信號接收端（場點）可視區(qū)計算首先通過信號覆蓋計算場的范圍確定參與計算的建筑物的范圍。在城市中，距離信號預(yù)測范圍之外區(qū)域的建筑物對于信號場的計算結(jié)果影響較小，所以在計算時，不考慮信號覆蓋區(qū)以外的范圍。在具體計算時，首先根據(jù)計算范圍索引出與該范圍相關(guān)的格網(wǎng)，并根據(jù)格網(wǎng)索引出建筑物。如圖8中，可從信號覆蓋范圍確定出與該覆蓋范圍相關(guān)的規(guī)則網(wǎng)格。對于信號覆蓋區(qū)域，按照規(guī)則格網(wǎng)劃分區(qū)域，確定信號接收端位置，每一信號接收端為網(wǎng)格的交點（見圖9）。對每一信號接收端首先進行朝向、背向測試，舍棄位于信號端背面的面；然后進行遮擋測試，由于信號接收端的高度較低，所以對覆蓋區(qū)域內(nèi)的三維空間數(shù)據(jù)做降維處理，在二維空間中進行遮擋測試，求得計算區(qū)域內(nèi)每個信號接收端的可見區(qū)域，建立每個信號接收端與其可視域的索引。通過射線追蹤方法計算到達每一格網(wǎng)點的信號強度，從而判斷整個信號覆蓋區(qū)域的信號整體接收情況。

3.3射線傳播路徑找尋

3.3.1直達射線計算由于信號覆蓋區(qū)域事先已知且信號接收端、信號發(fā)射端的位置已知，所以可以判斷收發(fā)信號之間的直達路徑。如果在信號覆蓋區(qū)域內(nèi)，信號收發(fā)端之間的線段與建筑物的垂直面或者頂面存在交點，則說明信號不是直達射線；如果在覆蓋區(qū)域內(nèi)測得與建筑物的面均無交點，則說明該路徑為直達路徑。

3.3.2鏡像樹建立對于反射射線，需要建立鏡像樹。根據(jù)信號發(fā)射端的位置對信號覆蓋區(qū)內(nèi)的建筑物按照距離排序，然后按照建筑物與信號發(fā)射端的位置關(guān)系由近及遠進行可視區(qū)域計算。具體步驟如下：1）首先對覆蓋區(qū)域內(nèi)的建筑物進行朝向、背向測試，舍棄位于信號發(fā)射端背面的建筑物的垂直面和頂面。2）在完成朝向、背向測試后，判斷信號發(fā)射端的高度與需要進行遮擋測試的建筑物的高度的關(guān)系，進行遮擋測試。如果信號發(fā)射端的高度小于建筑物的高度，則信號發(fā)出的射線不能到達該建筑物的頂面，則可將建筑物在二維平面內(nèi)進行遮擋測試，且位于由該建筑物生成的可視角度內(nèi)、同時位于該建筑后方的所有建筑物的面均不可見，可以舍棄。圖10為信號發(fā)射端與建筑物A的遮擋測試示意圖，其中信號發(fā)射端的高度低于建筑物A的高度，信號被建筑物A的面1遮擋，使得位于A后方的建筑物B、C、D、E受到遮擋，此時即使后方建筑物的高度低于信號發(fā)射端的高度也會被遮擋。所以在進行遮擋測試時可以判斷由于面A所致，建筑物B、C、D、E被遮擋。3）在找到某一建筑物的可視面后，需要確定信號發(fā)射端源點相對于該可見面的鏡像點。在找到源點可視區(qū)域，同時確定了鏡像點后，建立以源點為根節(jié)點，以可視區(qū)域為子節(jié)點的鏡像樹。其中子節(jié)點中包含可視區(qū)所屬的建筑物、該可視面的鏡像點、可視區(qū)域的坐標(biāo)表示等內(nèi)容。同時建立信號接收端的鏡像樹，其中包括每個信號接收端的可視區(qū)域以及鏡像點和信號接收端的連線與可視區(qū)的交點坐標(biāo)。4）在建立了信號收發(fā)端的鏡像樹后，便可根據(jù)可視域找尋射線路徑。對于一次反射路徑，則信號發(fā)射端、鏡像點和信號接收端的連線與可視區(qū)的交點坐標(biāo)、信號接收端三個空間點位的連線形成一次反射路徑。5）對于N次反射，則以新產(chǎn)生的鏡像點為新的信號發(fā)射端源點，重復(fù)①—④步，依次建立N次信號反射路徑。

3.3.3繞射路徑計算采用一致性繞射理論計算繞射射線到達信號接收端的繞射路徑。

4算法實現(xiàn)

4.1模型構(gòu)建利用射線追蹤算法計算出反射路徑，利用GO理論計算得出繞射路徑，并求得直射路徑。然后結(jié)合信號傳播規(guī)律，便可以得到信號經(jīng)過傳播路徑后最終到達信號接收端的信號強度，從而對信號覆蓋情況進行預(yù)測。算法實現(xiàn)見圖11。

4.2算法實現(xiàn)結(jié)果本文利用C++實現(xiàn)算法，可進行點對點射線追蹤，即從三維空間某一點作為光源（信號）發(fā)射點，以另一點為光源（信號）的到達點，通過射線追蹤模塊計算出從光線源點到達目標(biāo)點的光線傳播路徑，并在三維場景中顯示。圖12為射線經(jīng)過一次反射后到達地面的射線。

4.3算法在信號預(yù)測中的應(yīng)用本文將射線追蹤模型應(yīng)用于城市移動多媒體信號覆蓋預(yù)測領(lǐng)域，可以實現(xiàn)對于信號的覆蓋預(yù)測。應(yīng)用結(jié)果表明，利用該模型進行城市移動多媒體的信號預(yù)測具有計算精度高、預(yù)測準(zhǔn)確的優(yōu)點，可以為相關(guān)部門在臺站選址、臺站網(wǎng)優(yōu)化等方面提供決策支持，具有實際的應(yīng)用價值。圖13為利用射線追蹤模型在城市移動多媒體領(lǐng)域進行信號覆蓋預(yù)測截圖，從圖中可以看出，由于建筑物的影響，信號會形成比較明顯的街道效應(yīng)，相對于傳統(tǒng)的預(yù)測模型，將射線追蹤應(yīng)用于該領(lǐng)域進行信號預(yù)測更為準(zhǔn)確。

5結(jié)束語

本文開展三維城市環(huán)境下射線追蹤算法的研究，提出了基于城市布局分區(qū)、降維、加速多鏡法的射線追蹤加速算法，解決了傳統(tǒng)算法海量計算的問題，提高了射線追蹤算法的計算效率。在此基礎(chǔ)上，結(jié)合電磁波傳播理論，實現(xiàn)基于該算法的信號預(yù)測模型，并將該模型應(yīng)用于城市移動多媒體領(lǐng)域的信號預(yù)測。預(yù)測結(jié)果表明，利用該模型計算的結(jié)果具有較高的準(zhǔn)確度，可在廣播數(shù)字電視、城市移動多媒體、移動通訊等多個領(lǐng)域開展信號傳播預(yù)測和網(wǎng)絡(luò)規(guī)劃，因此具有廣闊的應(yīng)用前景。

作者：瞿海旺 范榮雙 徐然 單位：中國測繪科學(xué)研究院 北京洛斯達科技發(fā)展有限公司