射线跟踪中三维矢量数据库建立方法*

杨晋生，胡自胜，陈为刚

（天津大学电子信息工程学院 天津300072）

1 引言

射线跟踪是一种高效的电波传播特性分析方法，能精确预测城市微蜂窝以及室内场景的场强覆盖，有效分析多径强度、到达角、离开角和时延等重要的信道特性参数。近几年，射线跟踪已广泛应用于电波传播预测、无线网络规划以及无线定位等方面[1～3]。然而射线跟踪方法的实现需要场景的三维矢量数据库，并且计算复杂度高。

场景数据库是射线跟踪计算的基础。现有的三维场景建模方法很多，如基于二维GIS（geographic information system，地理信息系统）的三维建模，该方法虽经济有效，但精度不高；基于影像的三维建模，该方法精度高，但成本较高，自动化建模难度较大；基于激光扫描系统的三维建模，该方法数据获取速度快，实时性强，但后期处理工作量很大；CAD三维建模，该方法所需设备简单，适合小区域建模，模型逼真，但工作量大[4]。建立可见元数据库能减少参与射线跟踪计算的面和劈的数量，是降低射线跟踪计算复杂度的有效方法。在三维空间内求解可见元复杂度较高，参考文献[5]使用扫描线算法通过对场景进行水平扫描和垂直扫描来求解可见元，需要进行大量线面求交运算，计算复杂度较高；参考文献[6]的透视投影法通过空间分区和投影将三维几何问题转化到二维平面上处理，降低了复杂度，但未考虑室内场景建模。

本文针对上述问题，提出了一种适用于城市微蜂窝和室内场景的三维矢量数据库建立方法。本文研究小区域场景建模，并且射线跟踪模型需要的是场景的几何信息和电磁信息，场景的纹理、光照等信息可以忽略，提出简化的三维CAD建模方法来获取城市微蜂窝和室内三维场景数据库。为了降低射线跟踪计算复杂度，进一步提出了一种适用于室外和室内场景的修正透视投影算法来建立三维可见元数据库。基于上述方法对城市微蜂窝和室内场景进行建模分析表明，提出的方法能有效降低射线跟踪信道建模方法的计算复杂度。

2 射线跟踪原理

本文研究的射线跟踪模型是基于反向射线跟踪方法，根据几何光学原理、GTD （geometrical theory of diffraction，几何绕射理论）以及 UTD（uniform theory of diffraction，一致性绕射理论），结合仿真场景三维矢量数据库，考虑电波的反射、绕射以及散射等机制，追踪源点（发射天线）和场点（接收天线）之间的有效射线。

由反向射线跟踪方法可知，利用射线跟踪方法进行信道建模首先需要三维场景数据库，包括场景内对象的几何信息和电磁特性信息。对场景数据库中所有的面和劈，基于镜像法原理和GTD计算出有效的反射点和绕射点。根据不同传播模式（直射、反射、绕射以及反射绕射的组合）依次连接源点、反射点/绕射点、场点，若所得的射线与场景中的面均无交点，则完成了对该射线的跟踪。从上述射线跟踪的过程中可知，直接使用场景数据库的计算复杂度是难以接受的。因此，可以通过建立源点和场点关于场景的三维可见元数据库来减少参与计算的面和劈的数量，提高计算效率。

3 三维矢量数据库的建立

3.1 三维场景数据库建立方法

3.1.1 场景建模分析

建立三维场景数据库首先需要对不同类型场景进行建模分析，通过合理简化降低建模复杂度。对于城市微蜂窝，一方面，相对于树木、湖泊等，建筑物对电波传播影响最大，因此建模过程中仅考虑建筑物；另一方面，随着微小区范围不断缩小，建筑物高度不断增高，天线的高度一般低于城市建筑的平均高度，建筑物顶面对电波传播的影响较小，因此可将建筑物建模为直棱柱或者直棱柱的组合。对于室内场景，可以认为由两部分组成：室内物体和室内6壁。室内物体建模方法与微小区建筑物的建模方法相同；室内6壁包括地面、天花板、墙壁以及墙壁上的门和窗户等，可以将它们建模为带有不同电磁参数的面。

3.1.2 场景三维CAD建模

基于简化的三维CAD建模方法建立场景数据库步骤如下。

（1）利用 CAD绘制三维场景，并存储为 DXF（drawing exchange format，绘图交换格式）文件。对于室外对象和室内物体，绘制其底面多边形以及一条侧棱；室内6壁单独进行绘制。对象的电磁特性信息可通过编辑面的属性参数获得。

（2）提取DXF文件数据，建立三维场景数据库。按照步骤 （1）的绘图方法，三维模型的几何信息只包含于Header段和Entities段内，所以建立室外场景数据库时只需提取DXF文件中这两段中数据。

3.1.3 场景数据库的数据结构

三维场景数据库使用结构体链表存储建模场景详细的几何信息以及电磁信息。数据库Objectdata中存储的是场景中的对象，每个对象由该对象的基本信息（cube）以及子对象信息（face、edge、point）组成。基本信息包括对象的面、劈以及顶点的总数；子对象信息包括这些几何元素的位置坐标、拓扑关系以及电磁参数（电导率、磁导率以及介电常数）。

3.2 三维可见元数据库建立方法

可见面的求解是三维可见元数据库建立的难点，可见劈可以由可见面得到。下面主要介绍给定视点关于场景的三维可见面提取方法。

3.2.1 三维可见面提取

[6]通过透视投影法将三维面投影到二维平面上进行处理。该方法首先使用背面消隐算法剔除所有背向视点的面，然后对剩余的面进行空间分区以及透视投影，接下来在投影平面内使用扫描线算法得到这些二维面的遮挡关系，进一步基于多边形减法算法去除被遮挡的部分面，得到二维可见面，最后将其进行逆透视投影即可得到所需的三维可见面。本文基于透视投影法，提出了一种三维空间分区算法；并且从降低射线跟踪计算复杂度出发，修正了透视投影算法对地面以及室内场景的处理。

（1）空间分区算法

空间分区的目的是将场景中的面按照以视点为中心的空间预划分方法进行切割，使得各个空间区域的面能够在该区内进行透视投影。不同的空间划分方法会影响透视投影算法的复杂度，本文使用空间6分区方法，如图1(a)所示，以视点S为中心将空间划分为6个区。接下来是将场景中的面经过切割划分到各个区域内部。如果直接使用图1(a)中的分区分界线（虚线所示）对面进行求交，则会产生大量的线面求交运算。因此，本文先将场景中的前向面的俯视图由y=x和y=-x分割为4个区，然后分别对4个分区内的面在z方向上分割为3个区。如图1所示，图1(b)中一个前向面A，向地面投影得到线段PQ；图1(c)中将PQ在平面内由B1、B2两条边界线进行分区；图1(d)中将平面分区结果还原至三维，由面SB1B2和面SB3B4切割面片PQMN，将其划分到上、右和下3个分区内。

图1 空间6分区示意

（2）基于城市微小区场景的修正

对于城市微小区场景，一方面，天线高度一般低于建筑物平均高度，通过顶面反射到达接收点的射线贡献非常小，因此可以忽略建筑物顶面；另一方面，如果对地面采取透视投影法，则会大大地增加参与计算的面的数量，从而增加计算复杂度，本文直接将地面加入到可见元数据库中。

（3）基于室内场景的修正

对于室内场景，首先，室内物体可以直接使用透视投影算法，但由于天线高度和室内物体高度关系是不确定的，因此需要考虑室内物体的顶面和底面；其次，对于视点，室内6壁的面大部分是可见的，并且室内6壁面数目一般少于使用透视投影法求解的可见面数，因此可直接将室内6壁的面加入到三维可见面数据库中。

3.2.2 可见元数据库的数据结构

三维可见元数据库使用链表结构将可见面数据和可见劈数据分开存储。数据库中的重要变量见表1。

表1中的面顶点性质Vflag表示可见面的顶点是否为三维场景中对象的顶点，边性质Eflag是指该可见面的各边是否为三维场景中对象的劈或劈的一部分，索引号Index为该可见元在三维场景数据库中的位置。

表1 三维可见元数据库变量说明

4 场景建模与仿真实验

基于上述三维矢量数据库建立方法，本文分别对城市微小区和室内场景进行了建模，并计算了不同场景下给定视点的面可见比例Rf（可见元数据库中面的数量与场景数据库中面的数量之比）和劈可见比例Re（可见元数据库中劈的数量与场景数据库中劈的数量之比），最后分析了基于可见元数据库的射线跟踪计算复杂度。

4.1 城市微小区场景建模与仿真

图2(a)是基于三维场景矢量数据库建立方法得到的一个假想城市小区的三维场景模型。小区由16个底面不规则的直棱柱对象组成，面积为350 m×250 m，建筑对象的平均高度为70 m左右。图2(a)中的阴影面即为以图中圆点为视点的可见面，建筑物对象的顶面没有加入可见面数据库中。假设发射天线的位置坐标为(210,120)，高度40 m；接收天线的位置坐标为(90,210)，高度2 m。基于三维场景数据库和三维可见元数据库，通过射线跟踪模型仿真得到发射天线和接收天线之间的射线如图2(b)所示。

4.2 室内场景建模与仿真

图3(a)是基于室内场景建模方法得到的模型。该室内场景模型包括6个室内物体对象和8个室内6壁面对象，底面为15 m×3.5 m，高度为3.5 m。图3(a)中的阴影面即为以图中圆点为视点的可见面，其中室内物体可见的顶面和底面均加入到可见面数据库中。假设发射天线的位置坐标为(4,1.5)，高度2 m；接收天线的位置坐标为(12,0.8)，高度1.5 m。基于室内三维矢量数据库，通过射线跟踪模型计算得到从发射天线经历一次反射加一次绕射到达接收天线的射线，如图3(b)所示。

图2 城市微蜂窝场景建模及仿真

图3 室内场景建模及仿真

4.3 射线跟踪计算复杂度分析

由于射线跟踪模型计算复杂度取决于用于计算的面和劈的数量，因此通过计算不同场景下的Rf和Re可以分析射线跟踪模型的计算复杂度。本文针对3个城市微小区场景以及1个室内场景，每个场景随机给定5个视点，得到的平均Rf和平均Re见表2。从表2中可以看出：不论是城市微小区还是室内场景，基于修正的透视投影法能够较大地降低参与射线跟踪计算的面和劈的数量。

为了进一步分析三维可见元数据库对射线跟踪算法计算复杂度的改善，本文基于VC 6.0平台，比较了上述场景在建立三维可见元数据库前后的情况下仿真100个场点所需的时间Tv与Tc，并计算了时间复杂度之比Rt=Tv/Tc。从表2中可见，通过建立三维可见元数据库，可以较大地降低射线跟踪计算复杂度。

表2 不同场景下计算复杂度分析

5 结束语

本文通过分析室外场景与室内场景的特点，提出了一种适用于城市微小区以及室内场景三维矢量数据库建立方法。首先通过简化的CAD建模方法快速地建立简化场景的三维模型和场景数据库；然后基于改进的透视投影算法有效地建立关于视点的三维可见元数据库。仿真结果表明，本文提出的方法能有效地应用于三维射线跟踪模型中数据库的建立，降低计算复杂度。在下一步的研究中将建立具有不同几何精度的矢量数据库并分析几何精度对射线跟踪模型分析电磁特性参数的影响。

参考文献

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