一種射線跟蹤建模的新方法

楊 鑫,魏 兵

(1.西安電子科技大學物理與光電工程學院,陜西西安 710071; 2.西安電子科技大學信息感知協同創新中心,陜西西安 710071)

一種射線跟蹤建模的新方法

楊 鑫1,2,魏 兵1,2

(1.西安電子科技大學物理與光電工程學院,陜西西安 710071; 2.西安電子科技大學信息感知協同創新中心,陜西西安 710071)

在射線跟蹤的研究中,針對計算區域進行網格劃分問題,以單位球內接二十面體為基礎,提出了一種基于降維度計算的空間曲面三角形網格劃分方案.通過對球面的三角形劃分,介紹了該方法的具體實現過程,給出了兩種網格的編號方案;結合電磁輻射的方向圖對射線進行篩選;給出了曲面三角形劃分以及射線選擇的算例.數值算例證明了該算法的有效性.

射線跟蹤;降維方法;網格劃分;射線選擇

在射線跟蹤法(Ray Tracing,RT)的計算中,首先要解決的問題就是計算域的網格劃分問題,即將輻射區域劃分為一定數量的射線管束.然后,再對射線進行跟蹤計算便可得到特定的目標區域的電磁響應參量.而射線的跟蹤計算通常可分為正向跟蹤計算和反向跟蹤計算兩類[1-6],其中,正向跟蹤計算的實現方法是:先對劃分所得的所有射線做一遍跟蹤計算,然后將有貢獻的射線的計算結果累加至目標區域.這種方法的優點是,方便簡潔且易于程序的實現,但同時也需要花費大量的時間計算對目標區域沒有貢獻的射線,因此效率較低;而反向射線跟蹤計算的方法為:首先篩選出對目標區域有貢獻的射線,然后再依次對這些篩選出來的射線進行跟蹤計算,便可得到目標區域的電磁響應參量.這種方法克服了正向跟蹤計算效率較低的缺點,但是具有明顯的數學以及程序實現的復雜性,特別是在多徑問題的跟蹤計算中.

射線跟蹤法常將經過輻射球面的射線管束劃分為三角形、四邊形以及六邊形網格形式,但是三角形網格是更為基礎和常用的形式,在其基礎上就可方便地實現其他網格形式的劃分.因此,該問題的實質是曲面的三角形網格劃分的問題.而在曲面的三角形網格劃分方面,前人已做了許多的工作[7-14].文獻[7]在重心一致Delaunay三角化方法基礎上得到了平面的三角網格劃分.文獻[8]在最優Delaunay三角化方法的基礎上將曲面劃分為局部網格和全局網格,并通過減小插值誤差的方法實現了網格的平滑優化.文獻[9]采用epsilon-net方法和泊松表面重構法實現了對巖石表面的網格劃分及近似.文獻[10]采用調和映射的方法對三角網格曲面進行參數化,提出一種三角網格曲面等參數線刀軌生成算法.文獻[11]在將曲面劃分為可展曲面和不可展曲面的基礎上,利用Watson算法實現了曲面的三角網格劃分.上述的網格劃分方法普適性好,但其數學過程和程序實現一般比較復雜,在具體的工程應用中實現起來難度較大.因此,針對上述問題以及為滿足射線跟蹤法的需要,筆者以球內接二十面體為基礎,提出了一種基于降維度計算的空間曲面的三角形網格劃分方案.該方案的思路是:將三維空間曲面的網格劃分轉化為三維空間平面的網格劃分,然后將三維空間平面轉化為二維平面的網格劃分,接著把二維空間平面的劃分轉化為一維線段的劃分,這樣就可得到空間曲面的三角形網格劃分.而對于球面特定部分需要劃分的場景,可對二十面體進行選擇性的劃分,以此便可在一定程度上達到提高計算效率的目的.

射線跟蹤法中通常需要建立全向模型,但不需要進行全向計算,而只需要計算特定方向上的空間范圍.比如在計算天線輻射場時,就可根據天線的輻射方向圖對空間進行劃分,在有輻射場方向上對空間進行計算,而對沒有輻射場或是輻射場很弱的空間范圍則無需計算.鑒于此,筆者設計了一種基于正向跟蹤的網格選擇方案以及網格編號方法.該方案首先對球面劃分所得的三角網格進行編號,然后根據輻射方向圖對特定方向上的射線進行選擇跟蹤,從而提高了跟蹤計算的效率.

1　球面的三角形網格劃分

球面三角形網格劃分在其內接正二十面體的基礎上實現[6,15].以單位球面網格劃分為例,首先,在待劃分球面內,內接正二十面體(如圖1所示);然后,可對二十面體的各個頂點進行編號,以便于后續網格計算.在球坐標系下,可方便地求出二十面體的各頂點的坐標值[15]:A(1,0,0)、B(1,π,0)、C(1,a,0)、D(1,a,a)、E(1,a,2a)、F(1,a,3a)、G(1,a,4a)、H(1,π-a,2.5a)、I(1,π-a,3.5a)、J(1,π-a,4.5a)、K(1,π-a,0.5a)、L(1,π-a,1.5a),其中,a=1.107 149.這樣,對球面的網格劃分就可轉化為對二十面體的網格劃分,二十面體的網格劃分結果只需要徑向投影至球面就可得到球面的網格劃分.而這轉化過程只需用直角坐標與球坐標系之間的互換關系就可以實現.

圖1　單位球內接正二十面體

2　網格的編號方法

單位球面內接二十面體的三角面編號為:△ACG為T1,△ADC為T2,△AED為T3,△AFE為T4,△AGF為T5,△GCJ為T6,△CKJ為T7,△CDK為T8,△DLK為T9,△DEL為T10,△EH L為T11,△EFH為T12,△FIH為T13,△FGI為T14,△GJI為T15,△BJK為T16,△BKL為T17,△BHL為T18,△BIH為T19,△BJI為T20.

圖2　母三角形3階網格劃分及編號結果

以上述20個三角形中的任意一個三角形為母三角形,采用對其邊取中點的方式可得到高階劃分的子三角形網格(如圖2所示).例如,對母三角形的每條邊取中點,就可得到母三角形的1階網格劃分,從而形成4個子三角形網格;然后,再對所得的4個子三角形以取每邊中點的方式可得到2階網格劃分,形成16個子三角形;以此類推,就可得到母三角形的更高階網格劃分.這樣,原二十面體的每個母三角形在進行n階網格劃分后,其所含的子三角形的行數為2n,每行含2m-1個子三角形(m為該子三角形所在行的行編號),而每個母三角形所含子三角形總數為22n.于是每個子三角形可取(i,j,k)編號形式,其中,i為母三角形編號(i≤20),j為子三角形在母三角形中的行編號(j≤2n),k為該子三角形在其所在行內的位置編號(k≤2m-1).對于每個格點的編號,可采用如下方法:以順時針方向對每個子三角形的3個點排序,每個點可以編號為(i,j,k,l),其中,l為取值1、2或3,分別代表三角網格的3個組成點.另外,還可采取直接用點編號方式代替對三角網格的編號.對于進行n階網格劃分后的每個母三角形中的點可編號為(i,j,k),其中,i為該點所在母三角形的編號(i≤20),j為該編號點所在的行編號(j≤2n+1),k為其所在行內的位置編號(k≤m,m為該點所在的行編號即行數).

在文中的計算中,采用上述兩種編號結合的方法,即分別給三角網格點和網格面編號.首先,由網格劃分方法計算出每個網格點的坐標值;然后,再由網格點計算相應的三角網格的面積;最后,得到平面及曲面的所有網格劃分點和網格面積.

3　網格的計算方法

對空間曲面進行網格劃分,可先將曲面劃分為若干個對應的平面,然后可對這些平面進行網格劃分,最后將劃分好的平面投影到曲面之上,即可得到曲面的網格劃分.由此可見,對曲面網格劃分的關鍵是如何得到平面的網格劃分.下面給出文中算法的具體實現方案.

圖3　網格劃分的降維示意圖

以空間平面三角形網格劃分為例,如圖3所示,在直角坐標系Oxyz中,對三角形ABC進行n階三角網格劃分,則可先將其投影到任意兩個坐標面(圖3中的投影面選為x Oz和x Oy面)形成二維投影三角形(△ABCxz和△ABCxy),然后對兩投影三角形進行n階網格劃分,最后將劃分所得的網格投影坐標點合成,即可得到空間平面三角形的n階網格劃分點.而對于二維的投影三角形,其n階網格點劃分則可轉化為一維線段的n階劃分:首先,對三角形的3邊進行劃分,計算其n階網格劃分點;然后,由3邊計算所得的劃分點再計算該三角形內部所需的劃分點.其中,三角形的內部所需的劃分點可以分為3個類型,即分別與3邊平行的線段上的劃分點;最后,由這3類線段和三角形3邊的n階網格劃分點,合成即可得到坐標投影平面內的二維三角形的n階網格劃分點.圖4給出了三角形頂點分別位于點A(-50,0,50)、點B(0,70,0)以及點C(50,0,50)處的3階網格劃分點的分布情況.

圖4　三角形的3階網格劃分點分布

這樣,利用上述的降維方法,就得到空間三角形的網格劃分.然后將該方法依次作用于球面內接二十面體的各個表面之上,就可得到二十面體的n階網格劃分點.

4　曲面的網格劃分算列

在進行高階劃分后的二十面體的網格點,可利用坐標變換公式

將計算所得的劃分點投影到球面上,即可得球面的內接高階多面體及相應的球面三角網格劃分.圖5給出了4階網格劃分下的球面網格點分布圖.

對于其他類型的曲面,同樣可先通過將其劃分為一定數量的空間平面母三角形,然后再利用文中所使用的方法對這些平面母三角形網格劃分,最后再投影回原曲面上,即可得到該曲面的任意階網格劃分.圖6給出了曲面z=x2+x y3的5階網格點分布情況.

圖5　球面的4階網格劃分點分布

圖6　曲面的5階網格劃分點分布

5　射線的選擇

在射線跟蹤法中,為提高跟蹤計算的效率,常將跟蹤射線分為有效射線和無效射線.嚴格上來講,有效射線即是對接收點有能量貢獻的射線;反之,沒有貢獻的射線即稱為無效射線.而廣義上來說,即便射線對接收點有能量貢獻,但若該貢獻小于一定的閾值,則依然可將其視為無效射線.但總的說來,可用設定閾值的方法來劃分有效射線和無效射線.把射線進行如此劃分之后,就可對射線進行選擇性的跟蹤,以此就可達到提高計算效率的目的,即對有效射線進行跟蹤計算而放棄對無效射線的跟蹤,這樣,就需要解決如何選擇跟蹤射線或者網格點的問題了.

在無線電波的射線跟蹤問題中,電波一般可視為天線所發出的,因此,電波的分布可用方向圖來描述.而方向圖一般為(θ,φ)的函數,這時就可通過控制θ和φ變量,實現格點的選擇.圖7是矩形波導天線的輻射方向圖,在上述6階網格劃分的情形下會生成10 242根射線.利用文中算法可自由地對上述射線根據強度選擇,從而提高射線跟蹤的計算效率.不同閾值下有效射線數量、原有射線跟蹤所需時間與選擇后射線跟蹤所需時間的比值(加速比)如表1所示.由表1可見,隨著閾值的降低,需要跟蹤的射線條數有所增加,然而相比于全向跟蹤算法選擇后的計算時間明顯降低.

圖7　矩形方孔輻射方向圖

表1　控制閾值與加速比觀察表

在某些電磁輻射問題的射線選擇中,可能還存在方向函數難以計算的問題,比如非常復雜的方向函數或者難以尋找甚至是不存在的方向函數.對于這些問題,由于球面是在內接二十面體的基礎上實現網格劃分的,所以,對于上述問題中的射線選擇就可以轉化為對二十面體的面的選擇,即計算有輻射母三角面而忽略沒有輻射的母三角面的計算,以此也可達到提高計算效率的目的.

最后,對于已知場點的情況下尋找有效輻射面元的問題,則可根據該場點坐標值(R,θ,φ)找到電磁波的運動軌跡,然后以其軌跡與球面求交點的方式即可找到該點的有效輻射面元.而對于直射問題,面元的尋找就顯得相對容易,只需找出與場點有相同θ和φ分量的輻射面元即可.

6　結束語

為解決電波射線的空間劃分以及提高計算效率等問題,文中給出了一種根據射線跟蹤的空間曲面的三角形網格劃分方法,在該方法的基礎上也可容易地實現曲面的四邊形以及六邊形網格劃分;同時,在已知電波的輻射特性的條件下,比如輻射方向圖或者電波的大致覆蓋范圍等,文中還設計了一種根據正向射線跟蹤法建立的射線選擇方案,該方案有效剔除了無需計算的冗余射線,從而提高了射線跟蹤的計算效率.最后,整個方案的數值結果表明了文中算法的正確有效性,并且由該方法的實現原理和結果亦可表明,其具有較好的普適性.總的來說,該方法具有簡單高效、易于工程中程序實現的特點.

[1]張忠波.基于射線跟蹤技術的室內電波傳播預測研究[D].西安:西安電子科技大學,2012.

[2]de ADANA F S,BLANCO O G,DIEGO I G,et al.Propagation Model Based on Ray Tracing for the Design of Personal Communication Systems in Indoor Environments[J].IEEE Transactions on Vehicular Technology,2000,49(6): 2105-2112.

[3]劉忠玉,郭立新,種稚萌,等.城市微蜂窩環境下一種改進的射線跟蹤預測模型[J].西安電子科技大學學報,2014,41 (2):137-143. LIU Zhongyu,GUO Lixin,ZHONG Zhimeng,et al.Improved Ray Tracing Prediction Model in Urban Microcellular Environments[J].Journal of Xidian University,2014,41(2):137-143.

[4]李祥震,韓香娥.均勻橢球粒子的彩虹角分析[J].西安電子科技大學學報,2010,37(4):731-736. LI Xiangzhen,HAN Xiange.Rainbow Angle Analysis of a Homogeneous Spheroid[J].Journal of Xidian University,2010,37(4):731-736.

[5]楊紹華,張福順,焦永昌.天線罩電磁特性的仿真分析[J].西安電子科技大學學報,2004,31(6):873-876. YANG Shaohua,ZHANG Fushun,JIAO Yongchang.An Analysis of the Parameters for Antennas with the Dome[J]. Journal of Xidian University,2004,31(6):873-876.

[6]袁正午.移動通信系統終端射線跟蹤定位理論與方法[M].北京:電子工業出版社,2007.

[7]WANGA B,KHOOC B C,XIE Z Q,et al.Fast Centroidal Voronoi Delaunay Triangulation for Unstructured Mesh Generation[J].Journal of Computational and Applied Mathematics,2014,280:158-173.

[8]CHEN L,HOLST M.Efficient Mesh Optimization Schemes Based on Optimal Delaunay Triangulations[J].Computer Methods in Applied Mechanics and Engineering,2011,200:967-984.

[9]LAI P,SAMSON C,BOSE P.Surface Roughness of Rock Faces Through the Curvature of Traingulated Meshes[J]. Computers and Geosciences,2014,70:229-237.

[10]陳曉兵,廖文和,戴寧.三角網格曲面等參數線刀軌生成算法[J].中國機械工程,2013,24(8):1047-1051. CHEN Xiaobing,LIAO Wenhe,DAI Ning.Algorithm for ISO-parametric Tool Path Generation for Triangular Mesh Surface Machining[J].Chinese Mechanical Engineering,2013,24(8):1047-1051.

[11]陳永府,張華,陳興.任意曲面的三角形網格劃分[J].計算機輔助設計與圖形學學報,1997,9(5):396-401. CHEN Yongfu,ZHANG Hua,CHEN Xin.Triangle Meshing for Surface[J].Journal of Computer Aided Design and Computer Graphics,1997,9(5):396-401.

[12]胡曉娟,盧兆林,葛德彪,等.基于三角面元的涂層目標FDTD共形網格生成技術[J].系統工程與電子技術,2010,32 (9):1884-1888. HU Xiaojuan,LU Zhaolin,GE Debiao,et al.Conformal FDTD Mesh-generating Scheme for Coated Targets Based on Triangle-patch[J].Systems Engineering and Electronics,2010,32(9):1884-1888.

[13]ZHONG Z C,LIANG S,MAO J,et al.Anisotropic Surface Meshing with Conformal Embedding[J].Graphical Models,2014,76(5):468-483.

[14]CHEN X,CHEN L,SHI M D.A Highly Solid Model Boundary Preserving Method for Large-scale Parallel 3D Delaunay Meshing on Parallel Computers[J].Computer-Aided Design,2015,58:73-83.

[15]王毅.極低頻電磁波時域方法的理論研究及其應用[D].南京:南京航空航天大學,2012.

(編輯:齊淑娟)

New modeling method for ray tracing

YANG Xin1,2,WEI Bing1,2
(1.School of Physics and Optoelectronic Engineering,Xidian Univ.,Xi’an 710071,China;2.Collaborative Innovation Center of Information Sensing and Understanding,Xidian Univ.,Xi’an 710071,China)

It is often necessary to divide the spatial domain into grids in the ray tracing method.Based on the unit sphere inscribed icosahedron in this paper,a method of triangulation of the space curved surfaces by dimension reduction calculation is proposed.The process of this method is presented in detail by the triangulation of a unit sphere and two grid numbering schemes are given simultaneously.Then,combined with the direction of the electromagnetic radiation figure,the rays are selected.Finally,the examples of surface triangulation and tube selection are presented,which show the validation and effectiveness of this algorithm.

ray tracing;dimension reduction;surface meshing;ray selection

TN011

A

1001-2400(2016)03-0073-05

10.3969/j.issn.1001-2400.2016.03.013

2015-02-20

時間:2015-07-27

國家自然科學基金資助項目(61231003,61571348,61401344)

楊 鑫(1988-),男,西安電子科技大學博士研究生,E-mail:e?yangx@126.com.

魏 兵(1970-),男,教授,E-mail:bwei@xidian.edu.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20150727.1952.013.html