城市环境下射线追踪加速算法.docx

《城市环境下射线追踪加速算法.docx》由会员分享，可在线阅读，更多相关《城市环境下射线追踪加速算法.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、城市环境下射线追踪加速算法在三维城市建设的经过中，为了使得城市环境更具有真实感，往往需要为城市环境模拟一太阳光源，实现由于光照而引起的三维场景下的各种表现特征。研究在三维场景下的光线射线传播途径具有重要的应用价值，在广播数字电视、城市移动多媒体、移动通讯等领域，信号的传播都是利用电磁波进行的，而光本身也是一种电磁波，它们传播的方式一致。因而研究射线追踪技术，便能够将其引入到上述领域中开展应用。首先通过射线追踪技术找到发出的信号到达信号接收端的途径，然后结合信号在发射、途径传播经过中的电波传播特征，进而得到信号最终到达信号接收端的信号强度，实现基于射线追踪技术的电波传播预测，为广播数字电视、城市

2、移动多媒体、移动通讯等领域的覆盖规划提供决策支持。本文在三维城区环境下，研究射线追踪技术的理论方法，即，某一光源信号发射源发出一条光线射线后，通过直射、反射、绕射等最终到达地面的光线射线传播途径。1射线追踪介绍射线跟踪方法的理论基础是几何光学GeometricalOptics，GO理论，即，光在空间中以射线的方式进行传播，在碰到障碍物时，遵循光的反射定律会产生反射现象，射线追踪即模拟光在空间中的反射途径。对于空间障碍物边缘发射的绕射，则引入几何绕射理论和一致性绕射理论，模拟信号在碰到障碍物时发生的绕射情况。图1为信号经过直射、反射、衍射绕射后到达信号接收端的示意图。由于从一个信号发射端会发出无

3、数条射线，而且当碰到障碍物时，每条射线又会在障碍物外表发生反射、绕射等显现，因而在三维空间中找到所有射线的计算量宏大，甚至是计算机不可承受的。本文在充分研究传统射线追踪算法的基础上，提出基于城市布局分区、降维、加速多镜法的射线追踪技术，提高射线追踪算法的计算效率。2技术方法2.1分区加速算法2.1.1城市布局分区城市的布局特征与自然环境密切联络，例如武汉市城市总体布局以长江的走势为基础向东西两侧进行延伸。其街道路网布局方式根据长江的走势布设，构成依托地理环境的独特城市布局。城市的布局特征与人文因素有关，以城市交通为例，交通线路的发展会对城市布局产生深远影响。以北京市为例，北京市随着人口激增、经

4、济不断增长，逐步在二环线的基础上修建三环、四环、五环、六环，而随着每一次环线的建设，北京市都会在此基础进行城市扩张。北京市城市布局以环线为基本脉络，构成网状规则的布局。城市空间布局综合考虑地理、人文等因素如水系、交通等因素，或根据现有地理因素建设，构成不规则布局形状，或根据人文环境建设相对规则的布局；城市内部构造布局则根据总体布局成相对规则格局。如武汉市城区内部布局根据长江的走势而成相对规则的块状布局；北京市城区内部布局以长安街为中轴线，以道路、河流等组成相对规则块状构造。2.1.2空间索引机制由于城市地理环境的复杂性、数据的海量性，因而怎样快速、高效地索引数据便成为射线追踪实现的关键。本文充

5、分借鉴地图分幅的原理，对于大范围区域首先采用规则格网的方式对城市区域进行划分，建立规则格网空间索引。在划分的城市格网的基础上，结合城市由于地理、人文因素所构成的不规则块状构造，对基本格网进一步划分，采用CELL树构造对规则格网下的空间建立空间索引。如图2所示。图3为北京市海淀区五环内部分区域。从图上能够看出该区域被五环线、京藏高速、学院路、荷清路、学清路等几条主要道路划分为块状构造，因而，以这几条路为骨干线，对该区域进行分块处理，得到分块布局图。图中将区域划分为13个不规则区域，其命名形如J50E0100120008，其中前10位表示方格网编号，最后4位表示在格网中的编号。2.2降维加速算法降

6、维法是在射线追踪经过中，将三维环境下的建筑物进行投影，变为二维场景后进行射线计算。该算法适用于信号发射端高度低于建筑物的情况。如图4所示，信号发射端距离地面高度为h，障碍物1的高度为H1，障碍物2的高度为H2，且图中信号发射端发出两条射线，射线1和射线2，射线1与水平方向的夹角为a，为仰角，射线2与水平方向的夹角为b，为俯角。能够看出射线1不能到达地面接收端，射线2能够到达信号接收端；同时由于障碍物1对位于其后面的障碍物2相对于信号发射端发射的信号而言造成了部分遮挡，而射线可见部分与水平面的夹角均为仰角，即由信号发射端直接到达障碍物2的射线不能通过反射到达信号接收端；位于射线3和射线4之间的射

7、线都能够直接到达障碍物2，但是由于其夹角都为仰角，所以这些射线经过障碍物2的反射后会向海拔高度更高的位置反射，因而信号无法通过反射射线到达信号接收端。由于当信号发射端的高度低于障碍物高度所具有的这种性质，即一旦距离信号发射端较近障碍物对较远障碍物造成了遮挡，则信号不能通过反射射线到达较远障碍物。因而，基于射线传播的这种性质，能够将三维空间的建筑物先投影到二维平面上，在二维平面内对投影的建筑物进行求交运算，求得射线在二维平面内的传播途径，一旦收发点之间的传播途径被找到，则将在二维平面内的传播途径转化到三维空间中。由于在二维平面内的求交运算较三维空间简单得多，所以能够减少运算量，进而提高射线追踪的

8、运算效率。2.3朝向背向、遮挡测试2.3.1建筑物朝向、背向测试当一束光线射向建筑物时，建筑物的某些面会由于处在光线的反面而不能进行反射。对于处在背向光线传播方向的面，能够不介入反射计算，这样能够提高计算效率，因而需要进行建筑物朝向、背向测试。在计算中，通过射线向量与面的夹角来判定某面能否背向射线。在实际计算中利用面的法向量与射线之间的夹角来判定面与射线的关系，假如两向量乘积，则建筑物朝向射线；反之，则背向射线。如图5面的法向量，面的法向量，信号发射塔发出一射线R，该射线与构成的夹角为，由于为钝角，所以N0，则面对射线R可见。当一束源点向某一方向发出射线时，首先进行建筑物的朝向、背向测试，判定

9、建筑物的侧面与射线的朝向情况。假如面朝向射线，则射线与面之间有可能存在视距途径；假如面背向射线，则射线和面之间不可能存在视距途径。2.3.2遮挡测试在对建筑物完成朝向、背向测试后，要对建筑物的面进行遮挡测试，判定建筑物的面能否与源点可视。当信号发射端的高度小于建筑物高度时，信号发射端发出的射线不能通过直达射线到达建筑物的顶面；同时，当信号发射端的高度高于建筑物高度，但是在信号发射端和建筑物之间有另一障碍物，且该障碍物的高度大于信号发射端的高度时，此时直射射线也不能到达建筑物顶面以及垂直面。如图6中，障碍物2的高度大于信号发射端的高度，即此时信号不能到达障碍物2的顶面；障碍物3的高度小于信号发射

10、端的高度，即此时信号被障碍物2遮挡，不能到达障碍物3。因而，在这种情况下，建筑物的顶面对于射线不可视，而且也不能通过顶面到达位于某一建筑物后方的建筑物，可将建筑物三维场景通过投影变换转化为二维情况，进而求信号发射源点的可视面。由于二维的求交运算较三维简单，所以通过这种方式能够提高计算效率。图7为将某区域三维空间进行投影后的二维空间略图。从图中能够看出在信号发射端北方向，且距离发射端近期的建筑物是建筑物4。通过朝向、背向测试可知，建筑物4的面1位于信号发射端的可视区域内，面2、3、4都位于信号发射端的反面，所以为非可视区域。对于建筑物4的面1，则分别连接信号发射端与面1两个端点构成两条射线，其夹

11、角为a1，则位于该夹角内的所有建筑物的面均不可见。从图中能够看到，建筑物1和建筑物2的所有面以及建筑物3的面4的部分区域均在该夹角内，所以这些面均不可见。对距离信号发射端近期的第一个建筑物以及在其射线构成的夹角内的建筑物进行可视判定后，根据一定方向本文按顺时针方向继续查找距离信号发射端较近的建筑物，图中为建筑物3。建筑物3和建筑物4构成的可视区夹角为a2，进而能够判定位于该区域内的可视面，即建筑物3的面1以及部分面4。以此类推，得到可视夹角，即信号发射端在方向上都被判定，进而得到信号发射端的所有可视区域。3算法流程3.1建立三维城市地理环境数据库首先，搜集城市环境的矢量数据，包括建筑物数据的坐

12、标系统、各个建筑物的位置信息、各建筑物的高度信息、建筑物形状特征，组成建筑物的每个垂直面和顶面坐标以及介电特性。然后对建筑物数据进行预处理，主要包括：对城市建筑不同坐标系的处理、对建筑物高度的统一求解以及对建筑物形状的统一处理。当将所有的城市建筑数据处理完毕后，进行数据库的建库工作。在对城市建筑物进行建库时，要充分考虑城市建筑的布局特征，首先根据城市比例尺划定规则格网，建立索引，然后根据在规则格网内的城市布局建立CELL树索引。3.2信号接收端场点可视区计算首先通过信号覆盖计算场的范围确定介入计算的建筑物的范围。在城市中，距离信号预测范围之外区域的建筑物对于信号场的计算结果影响较小，所以在计算

13、时，不考虑信号覆盖区以外的范围。在详细计算时，首先根据计算范围索引出与该范围相关的格网，并根据格网索引出建筑物。如图8中，可从信号覆盖范围确定出与该覆盖范围相关的规则网格。对于信号覆盖区域，根据规则格网划分区域，确定信号接收端位置，每一信号接收端为网格的交点见图9。对每一信号接收端首先进行朝向、背向测试，舍弃位于信号端反面的面；然后进行遮挡测试，由于信号接收端的高度较低，所以对覆盖区域内的三维空间数据做降维处理，在二维空间中进行遮挡测试，求得计算区域内每个信号接收端的可见区域，建立每个信号接收端与其可视域的索引。通过射线追踪方法计算到达每一格网点的信号强度，进而判定整个信号覆盖区域的信号整体接

14、收情况。3.3射线传播途径找寻3.3.1直达射线计算由于信号覆盖区域事先已知且信号接收端、信号发射端的位置已知，所以能够判定收发信号之间的直达途径。假如在信号覆盖区域内，信号收发端之间的线段与建筑物的垂直面或者顶面存在交点，则讲明信号不是直达射线；假如在覆盖区域内测得与建筑物的面均无交点，则讲明该途径为直达途径。3.3.2镜像树建立对于反射射线，需要建立镜像树。根据信号发射端的位置对信号覆盖区内的建筑物根据距离排序，然后根据建筑物与信号发射端的位置关系由近及远进行可视区域计算。详细步骤如下：1首先对覆盖区域内的建筑物进行朝向、背向测试，舍弃位于信号发射端反面的建筑物的垂直面和顶面。2在完成朝向

15、、背向测试后，判定信号发射端的高度与需要进行遮挡测试的建筑物的高度的关系，进行遮挡测试。假如信号发射端的高度小于建筑物的高度，则信号发出的射线不能到达该建筑物的顶面，则可将建筑物在二维平面内进行遮挡测试，且位于由该建筑物生成的可视角度内、同时位于该建筑后方的所有建筑物的面均不可见，能够舍弃。图10为信号发射端与建筑物A的遮挡测试示意图，其中信号发射端的高度低于建筑物A的高度，信号被建筑物A的面1遮挡，使得位于A后方的建筑物B、C、D、E遭到遮挡，此时即便后方建筑物的高度低于信号发射端的高度也会被遮挡。所以在进行遮挡测试时能够判定由于面A所致，建筑物B、C、D、E被遮挡。3在找到某一建筑物的可视

16、面后，需要确定信号发射端源点相对于该可见面的镜像点。在找到源点可视区域，同时确定了镜像点后，建立以源点为根节点，以可视区域为子节点的镜像树。其中子节点中包含可视区所属的建筑物、该可视面的镜像点、可视区域的坐标表示等内容。同时建立信号接收端的镜像树，其中包括每个信号接收端的可视区域以及镜像点和信号接收端的连线与可视区的交点坐标。4在建立了信号收发端的镜像树后，便可根据可视域找寻射线途径。对于一次反射途径，则信号发射端、镜像点和信号接收端的连线与可视区的交点坐标、信号接收端三个空间点位的连线构成一次反射途径。5对于N次反射，则以新产生的镜像点为新的信号发射端源点，重复步，依次建立N次信号反射途径。

17、3.3.3绕射途径计算采用一致性绕射理论计算绕射射线到达信号接收端的绕射途径。4算法实现4.1模型构建利用射线追踪算法计算出反射途径，利用GO理论计算得出绕射途径，并求得直射途径。然后结合信号传播规律，便能够得到信号经过传播途径后最终到达信号接收端的信号强度，进而对信号覆盖情况进行预测。算法实现见图11。4.2算法实现结果本文利用C+实现算法，可进行点对点射线追踪，即从三维空间某一点作为光源信号发射点，以另一点为光源信号的到达点，通过射线追踪模块计算出从光线源点到达目的点的光线传播途径，并在三维场景中显示。图12为射线经过一次反射后到达地面的射线。4.3算法在信号预测中的应用本文将射线追踪模型

18、应用于城市移动多媒体信号覆盖预测领域，能够实现对于信号的覆盖预测。应用结果表明，利用该模型进行城市移动多媒体的信号预测具有计算精度高、预测准确的优点，能够为相关部门在台站选址、台站网优化等方面提供决策支持，具有实际的应用价值。图13为利用射线追踪模型在城市移动多媒体领域进行信号覆盖预测截图，从图中能够看出，由于建筑物的影响，信号会构成比拟明显的街道效应，相对于传统的预测模型，将射线追踪应用于该领域进行信号预测更为准确。5结束语本文开展三维城市环境下射线追踪算法的研究，提出了基于城市布局分区、降维、加速多镜法的射线追踪加速算法，解决了传统算法海量计算的问题，提高了射线追踪算法的计算效率。在此基础上，结合电磁波传播理论，实现基于该算法的信号预测模型，并将该模型应用于城市移动多媒体领域的信号预测。预测结果表明，利用该模型计算的结果具有较高的准确度，可在广播数字电视、城市移动多媒体、移动通讯等多个领域开展信号传播预测和网络规划，因而具有广阔的应用前景。