城市环境下射线追踪加速算法范文

在三维城市建设的过程中，为了使得城市环境更具有真实感，往往需要为城市环境模拟一太阳光源，实现由于光照而引起的三维场景下的各种表现特征。研究在三维场景下的光线（射线）传播路径具有重要的应用价值，在广播数字电视、城市移动多媒体、移动通讯等领域，信号的传播都是利用电磁波进行的，而光本身也是一种电磁波，它们传播的方式一致。因此研究射线追踪技术，便可以将其引入到上述领域中开展应用。首先通过射线追踪技术找到发出的信号到达信号接收端的路径，然后结合信号在发射、路径传播过程中的电波传播特征，从而得到信号最终到达信号接收端的信号强度，实现基于射线追踪技术的电波传播预测，为广播数字电视、城市移动多媒体、移动通讯等领域的覆盖规划提供决策支持。本文在三维城区环境下，研究射线追踪技术的理论方法，即，某一光源（信号发射源）发出一条光线（射线）后，通过直射、反射、绕射等最终到达地面的光线（射线）传播路径。

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结束语

本文开展三维城市环境下射线追踪算法的研究，提出了基于城市布局分区、降维、加速多镜法的射线追踪加速算法，解决了传统算法海量计算的问题，提高了射线追踪算法的计算效率。在此基础上，结合电磁波传播理论，实现基于该算法的信号预测模型，并将该模型应用于城市移动多媒体领域的信号预测。预测结果表明，利用该模型计算的结果具有较高的准确度，可在广播数字电视、城市移动多媒体、移动通讯等多个领域开展信号传播预测和网络规划，因此具有广阔的应用前景。

作者：瞿海旺 范荣双 徐然 单位：中国测绘科学研究院 北京洛斯达科技发展有限公司