射線跟蹤中三維矢量數(shù)據(jù)庫建立方法*

楊晉生，胡自勝，陳為剛

（天津大學電子信息工程學院 天津300072）

1 引言

射線跟蹤是一種高效的電波傳播特性分析方法，能精確預測城市微蜂窩以及室內場景的場強覆蓋，有效分析多徑強度、到達角、離開角和時延等重要的信道特性參數(shù)。近幾年，射線跟蹤已廣泛應用于電波傳播預測、無線網絡規(guī)劃以及無線定位等方面[1～3]。然而射線跟蹤方法的實現(xiàn)需要場景的三維矢量數(shù)據(jù)庫，并且計算復雜度高。

場景數(shù)據(jù)庫是射線跟蹤計算的基礎?，F(xiàn)有的三維場景建模方法很多，如基于二維GIS（geographic information system，地理信息系統(tǒng)）的三維建模，該方法雖經濟有效，但精度不高；基于影像的三維建模，該方法精度高，但成本較高，自動化建模難度較大；基于激光掃描系統(tǒng)的三維建模，該方法數(shù)據(jù)獲取速度快，實時性強，但后期處理工作量很大；CAD三維建模，該方法所需設備簡單，適合小區(qū)域建模，模型逼真，但工作量大[4]。建立可見元數(shù)據(jù)庫能減少參與射線跟蹤計算的面和劈的數(shù)量，是降低射線跟蹤計算復雜度的有效方法。在三維空間內求解可見元復雜度較高，參考文獻[5]使用掃描線算法通過對場景進行水平掃描和垂直掃描來求解可見元，需要進行大量線面求交運算，計算復雜度較高；參考文獻[6]的透視投影法通過空間分區(qū)和投影將三維幾何問題轉化到二維平面上處理，降低了復雜度，但未考慮室內場景建模。

本文針對上述問題，提出了一種適用于城市微蜂窩和室內場景的三維矢量數(shù)據(jù)庫建立方法。本文研究小區(qū)域場景建模，并且射線跟蹤模型需要的是場景的幾何信息和電磁信息，場景的紋理、光照等信息可以忽略，提出簡化的三維CAD建模方法來獲取城市微蜂窩和室內三維場景數(shù)據(jù)庫。為了降低射線跟蹤計算復雜度，進一步提出了一種適用于室外和室內場景的修正透視投影算法來建立三維可見元數(shù)據(jù)庫?；谏鲜龇椒▽Τ鞘形⒎涓C和室內場景進行建模分析表明，提出的方法能有效降低射線跟蹤信道建模方法的計算復雜度。

2 射線跟蹤原理

本文研究的射線跟蹤模型是基于反向射線跟蹤方法，根據(jù)幾何光學原理、GTD （geometrical theory of diffraction，幾何繞射理論）以及 UTD（uniform theory of diffraction，一致性繞射理論），結合仿真場景三維矢量數(shù)據(jù)庫，考慮電波的反射、繞射以及散射等機制，追蹤源點（發(fā)射天線）和場點（接收天線）之間的有效射線。

由反向射線跟蹤方法可知，利用射線跟蹤方法進行信道建模首先需要三維場景數(shù)據(jù)庫，包括場景內對象的幾何信息和電磁特性信息。對場景數(shù)據(jù)庫中所有的面和劈，基于鏡像法原理和GTD計算出有效的反射點和繞射點。根據(jù)不同傳播模式（直射、反射、繞射以及反射繞射的組合）依次連接源點、反射點/繞射點、場點，若所得的射線與場景中的面均無交點，則完成了對該射線的跟蹤。從上述射線跟蹤的過程中可知，直接使用場景數(shù)據(jù)庫的計算復雜度是難以接受的。因此，可以通過建立源點和場點關于場景的三維可見元數(shù)據(jù)庫來減少參與計算的面和劈的數(shù)量，提高計算效率。

3 三維矢量數(shù)據(jù)庫的建立

3.1 三維場景數(shù)據(jù)庫建立方法

3.1.1 場景建模分析

建立三維場景數(shù)據(jù)庫首先需要對不同類型場景進行建模分析，通過合理簡化降低建模復雜度。對于城市微蜂窩，一方面，相對于樹木、湖泊等，建筑物對電波傳播影響最大，因此建模過程中僅考慮建筑物；另一方面，隨著微小區(qū)范圍不斷縮小，建筑物高度不斷增高，天線的高度一般低于城市建筑的平均高度，建筑物頂面對電波傳播的影響較小，因此可將建筑物建模為直棱柱或者直棱柱的組合。對于室內場景，可以認為由兩部分組成：室內物體和室內6壁。室內物體建模方法與微小區(qū)建筑物的建模方法相同；室內6壁包括地面、天花板、墻壁以及墻壁上的門和窗戶等，可以將它們建模為帶有不同電磁參數(shù)的面。

3.1.2 場景三維CAD建模

基于簡化的三維CAD建模方法建立場景數(shù)據(jù)庫步驟如下。

（1）利用 CAD繪制三維場景，并存儲為 DXF（drawing exchange format，繪圖交換格式）文件。對于室外對象和室內物體，繪制其底面多邊形以及一條側棱；室內6壁單獨進行繪制。對象的電磁特性信息可通過編輯面的屬性參數(shù)獲得。

（2）提取DXF文件數(shù)據(jù)，建立三維場景數(shù)據(jù)庫。按照步驟 （1）的繪圖方法，三維模型的幾何信息只包含于Header段和Entities段內，所以建立室外場景數(shù)據(jù)庫時只需提取DXF文件中這兩段中數(shù)據(jù)。

3.1.3 場景數(shù)據(jù)庫的數(shù)據(jù)結構

三維場景數(shù)據(jù)庫使用結構體鏈表存儲建模場景詳細的幾何信息以及電磁信息。數(shù)據(jù)庫Objectdata中存儲的是場景中的對象，每個對象由該對象的基本信息（cube）以及子對象信息（face、edge、point）組成?；拘畔▽ο蟮拿?、劈以及頂點的總數(shù)；子對象信息包括這些幾何元素的位置坐標、拓撲關系以及電磁參數(shù)（電導率、磁導率以及介電常數(shù)）。

3.2 三維可見元數(shù)據(jù)庫建立方法

可見面的求解是三維可見元數(shù)據(jù)庫建立的難點，可見劈可以由可見面得到。下面主要介紹給定視點關于場景的三維可見面提取方法。

3.2.1 三維可見面提取

[6]通過透視投影法將三維面投影到二維平面上進行處理。該方法首先使用背面消隱算法剔除所有背向視點的面，然后對剩余的面進行空間分區(qū)以及透視投影，接下來在投影平面內使用掃描線算法得到這些二維面的遮擋關系，進一步基于多邊形減法算法去除被遮擋的部分面，得到二維可見面，最后將其進行逆透視投影即可得到所需的三維可見面。本文基于透視投影法，提出了一種三維空間分區(qū)算法；并且從降低射線跟蹤計算復雜度出發(fā)，修正了透視投影算法對地面以及室內場景的處理。

（1）空間分區(qū)算法

空間分區(qū)的目的是將場景中的面按照以視點為中心的空間預劃分方法進行切割，使得各個空間區(qū)域的面能夠在該區(qū)內進行透視投影。不同的空間劃分方法會影響透視投影算法的復雜度，本文使用空間6分區(qū)方法，如圖1(a)所示，以視點S為中心將空間劃分為6個區(qū)。接下來是將場景中的面經過切割劃分到各個區(qū)域內部。如果直接使用圖1(a)中的分區(qū)分界線（虛線所示）對面進行求交，則會產生大量的線面求交運算。因此，本文先將場景中的前向面的俯視圖由y=x和y=-x分割為4個區(qū)，然后分別對4個分區(qū)內的面在z方向上分割為3個區(qū)。如圖1所示，圖1(b)中一個前向面A，向地面投影得到線段PQ；圖1(c)中將PQ在平面內由B1、B2兩條邊界線進行分區(qū)；圖1(d)中將平面分區(qū)結果還原至三維，由面SB1B2和面SB3B4切割面片PQMN，將其劃分到上、右和下3個分區(qū)內。

圖1 空間6分區(qū)示意

（2）基于城市微小區(qū)場景的修正

對于城市微小區(qū)場景，一方面，天線高度一般低于建筑物平均高度，通過頂面反射到達接收點的射線貢獻非常小，因此可以忽略建筑物頂面；另一方面，如果對地面采取透視投影法，則會大大地增加參與計算的面的數(shù)量，從而增加計算復雜度，本文直接將地面加入到可見元數(shù)據(jù)庫中。

（3）基于室內場景的修正

對于室內場景，首先，室內物體可以直接使用透視投影算法，但由于天線高度和室內物體高度關系是不確定的，因此需要考慮室內物體的頂面和底面；其次，對于視點，室內6壁的面大部分是可見的，并且室內6壁面數(shù)目一般少于使用透視投影法求解的可見面數(shù)，因此可直接將室內6壁的面加入到三維可見面數(shù)據(jù)庫中。

3.2.2 可見元數(shù)據(jù)庫的數(shù)據(jù)結構

三維可見元數(shù)據(jù)庫使用鏈表結構將可見面數(shù)據(jù)和可見劈數(shù)據(jù)分開存儲。數(shù)據(jù)庫中的重要變量見表1。

表1中的面頂點性質Vflag表示可見面的頂點是否為三維場景中對象的頂點，邊性質Eflag是指該可見面的各邊是否為三維場景中對象的劈或劈的一部分，索引號Index為該可見元在三維場景數(shù)據(jù)庫中的位置。

表1 三維可見元數(shù)據(jù)庫變量說明

4 場景建模與仿真實驗

基于上述三維矢量數(shù)據(jù)庫建立方法，本文分別對城市微小區(qū)和室內場景進行了建模，并計算了不同場景下給定視點的面可見比例Rf（可見元數(shù)據(jù)庫中面的數(shù)量與場景數(shù)據(jù)庫中面的數(shù)量之比）和劈可見比例Re（可見元數(shù)據(jù)庫中劈的數(shù)量與場景數(shù)據(jù)庫中劈的數(shù)量之比），最后分析了基于可見元數(shù)據(jù)庫的射線跟蹤計算復雜度。

4.1 城市微小區(qū)場景建模與仿真

圖2(a)是基于三維場景矢量數(shù)據(jù)庫建立方法得到的一個假想城市小區(qū)的三維場景模型。小區(qū)由16個底面不規(guī)則的直棱柱對象組成，面積為350 m×250 m，建筑對象的平均高度為70 m左右。圖2(a)中的陰影面即為以圖中圓點為視點的可見面，建筑物對象的頂面沒有加入可見面數(shù)據(jù)庫中。假設發(fā)射天線的位置坐標為(210,120)，高度40 m；接收天線的位置坐標為(90,210)，高度2 m?；谌S場景數(shù)據(jù)庫和三維可見元數(shù)據(jù)庫，通過射線跟蹤模型仿真得到發(fā)射天線和接收天線之間的射線如圖2(b)所示。

4.2 室內場景建模與仿真

圖3(a)是基于室內場景建模方法得到的模型。該室內場景模型包括6個室內物體對象和8個室內6壁面對象，底面為15 m×3.5 m，高度為3.5 m。圖3(a)中的陰影面即為以圖中圓點為視點的可見面，其中室內物體可見的頂面和底面均加入到可見面數(shù)據(jù)庫中。假設發(fā)射天線的位置坐標為(4,1.5)，高度2 m；接收天線的位置坐標為(12,0.8)，高度1.5 m。基于室內三維矢量數(shù)據(jù)庫，通過射線跟蹤模型計算得到從發(fā)射天線經歷一次反射加一次繞射到達接收天線的射線，如圖3(b)所示。

圖2 城市微蜂窩場景建模及仿真

圖3 室內場景建模及仿真

4.3 射線跟蹤計算復雜度分析

由于射線跟蹤模型計算復雜度取決于用于計算的面和劈的數(shù)量，因此通過計算不同場景下的Rf和Re可以分析射線跟蹤模型的計算復雜度。本文針對3個城市微小區(qū)場景以及1個室內場景，每個場景隨機給定5個視點，得到的平均Rf和平均Re見表2。從表2中可以看出：不論是城市微小區(qū)還是室內場景，基于修正的透視投影法能夠較大地降低參與射線跟蹤計算的面和劈的數(shù)量。

為了進一步分析三維可見元數(shù)據(jù)庫對射線跟蹤算法計算復雜度的改善，本文基于VC 6.0平臺，比較了上述場景在建立三維可見元數(shù)據(jù)庫前后的情況下仿真100個場點所需的時間Tv與Tc，并計算了時間復雜度之比Rt=Tv/Tc。從表2中可見，通過建立三維可見元數(shù)據(jù)庫，可以較大地降低射線跟蹤計算復雜度。

表2 不同場景下計算復雜度分析

5 結束語

本文通過分析室外場景與室內場景的特點，提出了一種適用于城市微小區(qū)以及室內場景三維矢量數(shù)據(jù)庫建立方法。首先通過簡化的CAD建模方法快速地建立簡化場景的三維模型和場景數(shù)據(jù)庫；然后基于改進的透視投影算法有效地建立關于視點的三維可見元數(shù)據(jù)庫。仿真結果表明，本文提出的方法能有效地應用于三維射線跟蹤模型中數(shù)據(jù)庫的建立，降低計算復雜度。在下一步的研究中將建立具有不同幾何精度的矢量數(shù)據(jù)庫并分析幾何精度對射線跟蹤模型分析電磁特性參數(shù)的影響。

參考文獻

1 Liang G,Bertoni H L.A new approach to 3-D ray tracing for propagation prediction in cities.IEEE Transactions on Antennas and Propagation,1998,46(6):853～863

2 Zhengqing Yun,Sungkyun Lim,Iskander M F.An integrated method of ray tracing and genetic algorithm for optimizing coverage in indoor wireless networks.Antennas and Wireless Propagation Letters,2008(7):145～148

3 Jacob M,Schon S,Weinbach U,et al.Ray tracing supported precision evaluation for GPS indoor positioning.Proceedings of Workshop on Positioning,Navigation and Communication,Hannover,Germany:IEEE Press,2009:15～22

4 Ran Chen.The developmentof3D city modeland its applications in urban planning.Proceedings of 19th International Conference on Geoinformatics.Shanghai,China:IEEE Press,2011:1～5

5 Aguado Agelet F,Formella A,Hernando Rabanos J M,et al.Efficient ray-tracing acceleration techniques for radio propagation modeling. IEEE Transactions on Vehicular Technology,2000,49(6):2 089～2 104

6 Maurer J,Drumm O,Didascalou D.A novel approach in the determination of visible surfaces in 3D vector geometries for ray-optical wave propagation modeling.Proceedings of IEEE Vehicular Technology Conference,Tokyo,Japan:IEEE Press,2000:1 651～1 655