一种用于隧道环境的射线追踪加速算法

摘要

本发明公开了一种用于隧道环境的射线追踪加速算法，其属于电磁信道仿真领域。所述加速算法可以用于隧道场景的电磁信道仿真，并作为通信基站布局的依据。算法的基本思想是将描述隧道的三角形网格分割为一系列的凸多面体，并且判断从隧道前截面射入凸多面体的射线与后截面是否相交。根据凸多面体的性质，如果射线与后截面相交，则必然与墙壁不相交；如果射线不与后截面相交，则必然与墙壁相交。通过采用预处理和查表法，射线与截面的相交和射线与墙壁的相交均能够在常数时间内完成。本发明公开的方法极大地减少了射线与三角形相交的计算量，提高了射线追踪算法的运算效率，使得隧道场景下的基站布局能够更高效地完成。

主权项

一种用于隧道环境的射线追踪加速算法，所述隧道截面表示为一个凸多边形，且所述任意一个隧道段表示为一个凸多面体，其特征在于：包括如下步骤步骤1：隧道截面的边界条件预处理，用于判断射线与隧道截面凸多边形的交点是否在凸多边形的内部；步骤2：隧道截面的快速映射表预处理，建立映射表，降低判断射线与隧道截面凸多边形的交点在凸多边形内部的平均计算时间；步骤3：隧道壁三角形网格的快速映射表预处理，所述隧道壁是由隧道截面凸多边形沿指定扫掠路径扫掠而成的曲面；步骤4：进行加速的射线追踪算法，其具体包括步骤4.1.从隧道外的任意一点发出的射线R，若其与隧道的入口多边形相交，并且射线方向为从入口射入隧道，且方向向量与入口多边形的法向量的点乘则标记该射线“在隧道内”，并且标记该射线所处的位置为“在隧道的第1段中”；若其与隧道的出口多边形相交，并且射线方向为从出口射入隧道，且方向向量与出口多边形的法向量的点乘则标记该射线“在隧道内”，并且标记该射线所处的位置为“在隧道的第n‑1段中”，其中n为扫掠路径的节点个数；步骤4.2.若射线R在隧道内，首先判断射线的方向，若射线的方向向量与隧道当前区间的路径向量的点乘则标记该射线的方向的“向前”，反之则标记方向为“向后”；接着判断射线与隧道当前区间的出口多边形是否相交；步骤4.3.若检测到射线与隧道壁上的某个三角形相交，则立刻返回交点的相关数据，根据隧道壁的材质参数对射线的能量进行更新，递归计算产生的反射射线。