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

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

1射線追蹤介紹

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

2技術方法

2.1分區加速算法

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

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

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

2.3朝向背向、遮擋測試

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

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

3算法流程

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

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

3.3射線傳播路徑找尋

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

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

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

4算法實現

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

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

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

5結束語

本文開展三維城市環境下射線追蹤算法的研究，提出了基于城市布局分區、降維、加速多鏡法的射線追蹤加速算法，解決了傳統算法海量計算的問題，提高了射線追蹤算法的計算效率。在此基礎上，結合電磁波傳播理論，實現基于該算法的信號預測模型，并將該模型應用于城市移動多媒體領域的信號預測。預測結果表明，利用該模型計算的結果具有較高的準確度，可在廣播數字電視、城市移動多媒體、移動通訊等多個領域開展信號傳播預測和網絡規劃，因此具有廣闊的應用前景。

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