An Improved Equiangular Division Algorithm for SBR based Ray Tracing Channel Modeling

In SBR, rays are launched on the faces of a regular polyhedron by dividing the edges and connecting division points. Compared with a hexahedron whose faces are squares, a regular polyhedron with triangular faces is more suitable for launching rays. Because the rays transmit in the form of cones, overlapping area is inevitable, which causes double counting. As shown in Fig. 1, a square has larger adjacent overlapping area than a triangle, causing the hexahedra inappropriate for ray launching. A dodecahedron is less suitable owing to its pentagon faces which cannot be flattened.

The method in [11] generates ray points at equal intervals on the faces of the regular polyhedron and then projects these points onto the sphere, referred to as equidistant division here. In the projection process, the spacing of rays launched near the polygon face center expands more, while that of rays launched near vertices hardly changes, which leads to a smaller ray density at the face center than that at the vertices. Compared with an icosahedron, an octahedron has fewer faces, larger area of triangular faces, and a farther distance to the spherical surface at face centers, so this diffusion effect becomes more obvious, verified in Fig. 2 and Fig. 2. A tetrahedron has even fewer faces than an octahedron, so it has the worst performance among regular polyhedrons with triangular faces.

By calculating the azimuth and elevation angles of rays, and drawing a density map, the ray launching density of different ray emission methods can be compared. But it should be noted that the horizontal circular section of a sphere is the longest at the equator and shortest at the poles. The radius of the horizontal circle is $R\cos(pitch)$, where $R$ is radius of the sphere. In order to make a fair comparison, we should use azimuth multiplied by $\cos(pitch)$ as the abscissa of figures, instead of azimuth angle simply. In this way, the sphere can be expanded to a two-dimensional plane, with the area unchanged as $4{\pi}R^{2}$. The density of points on the sphere suffers little impact in this way, and the visualization of the density map is better due to expansion to the plane.

The color in Fig. 2 is less uniform than that in Fig. 2, meaning an icosahedron is more suitable for launching rays. However, there is still a ray density gap between the vertices and the face centers. A new approach enabling ray density much more uniform is proposed below.

The results of the equidistant division on an icosahedron still have a problem of high ray density at the vertices. This is an inherent problem that comes with equidistant division. Since the rays are finally launched on a spherical surface, and the actual distance is related to the angle between the rays, ray positions should be divided by equal angles in the beginning. Fig. 3 is an icosahedron, on which rays are launched with the method in Fig. 3. The equidistant division method satisfies $AB=BC=CD=DE$, while the equiangular division method satisfies $\angle{AOB}=\angle{BOC}=\angle{COD}=\angle{DOE}$, where $O$ is the center of the icosahedron circumscribed sphere. In this way, the angular intervals of ray points on the edge are the same so that ray density is the same. The inner layer is constructed using an iterative method. As shown in Fig. 3, $\overrightarrow{AF}=\overrightarrow{AB}+\overrightarrow{AB_{1}}$. New vertices ($F,HandG$) on the inner layer are constructed.

Here, $P^{b}_{a}$ is defined as one ray point launched on one triangular surface of the icosahedron, where $a$ is the layer number and $b$ is the point number on the layer. The outermost layer of the triangular is layer 0. When an inner layer is generated, the number is added by 1, shown in Fig. 3. The ray points are arranged clockwise on the triangle, with $A$ being the first point $P^{0}_{0}$. The edges are divided into $n$ subdivisions. In this way, $P^{0}_{0}$, $P^{n}_{0}$ and $P^{2n}_{0}$ are the vertices of the outermost triangle layer. Ray points are generated by

with $a=0$, launching $3n$ rays on the outermost layer.

Then, the vertices of the inner layer $P^{0}_{a+1}$, $P^{n-3a-3}_{a+1}$ and $P^{2n-6a-6}_{a+1}$ are generated by its outer layer

The $3n-9a$ ray points on the layer $a$ are generated by (1).

There are three possible situations on the innermost layer, with the number and location of the innermost rays being none; one ray at the center of the face; three rays generated from the outer layer, depending on $n$. Each face of an icosahedron is divided in this way to launch rays.

The numbers of rays launched by both methods are the same. It is shown in Fig. 2 and Fig. 2 that equiangular division enables the rays to distribute more uniformly after projection. So, a consistent angle can be adopted at the receiving end. Also, this uniform division is the basis for the subsequent precise algorithm.

The flowchart of SBR in this paper is in Fig. 4. Propagation mechanisms of ray-tracing include reflection and diffraction.

There are two path test parts. The first step is for removing double counting. The transmitting end inevitably has overlapping areas, so it is necessary to exclude repeated rays at the receiving end. The method of exclusion is excluding the one with a larger error angle if the two paths pass through exactly the same faces or wedges. Here the error angle is defined as

where $d_{Rx-ray}$ is the distance between Rx and the ray that satisfies the reception judgment, and $d_{ray}$ is the propagation distance of the ray. Error angle is the angle between departure direction of accurate path and the obtained path from Tx.

The second test can judge validity of the paths, ensuring the paths collide with the faces or wedges. Also, because the rays of SBR are cones, there may be some redundant paths. After precision, the collision points of these paths are actually outside the faces or wedges, so these paths should be excluded.

The path results obtained by the SBR algorithm are inaccurate because the rays are emitted in the form of cones. Error angle is used to compare the error of each path which is defined in (3). Since the condition for the path to be accepted is that Rx is inside the ray cone, we have $\theta_{error}\leqslant\theta_{launch}$.

Reducing the cone angle of ray emission can effectively reduce the error, and increasing the number of emitted rays can reduce the cone angle. If the emitting end takes $n$ equal parts to launch rays on the regular icosahedron, after some derivation, the total number of rays is $N_{rays}=10n^{2}+2$, and cone angle is

where $\theta_{0}$ is the angle connecting the adjacent vertices of the icosahedron to the center, as $\angle{AOE}$ in Fig. 3, equaling to $63.4349^{\circ}$. So, the relationship between error angle and number of rays is

To reduce the error, it is necessary to greatly increase the number of emitted rays. This results in many invalid rays, which do not constitute paths but need to be calculated. Time cost increases greatly and error decreases insignificantly if error angles are reduced by increasing the number of rays.

When the number of rays is $4412$, all paths can be traced for most scenes. In order to improve accuracy, the paths should be processed, rather than many useless rays to be launched. An exact algorithm that takes very little time is proposed below.

As shown in Fig. 5, the large circle represents the initial ray cone, and this area is divided into six small areas, represented by the smaller circles. Rays are emitted in these six sub-regions respectively, then several paths are obtained. The error angles of these paths are calculated. The path with the smallest error angle is reserved, and six sub-rays are emitted again within its ray cone, as shown in Fig. 5. Finally, the ray cones iterate in this way until the error angle satisfies the requirements or times of run reach the set number of iterations.

The directions of all diffraction paths are recorded in order to reduce the time consumption of the precise algorithm. The sub-rays diffract according to the recorded direction, and several rays are emitted to both sides of the diffraction cone. If all the diffraction rays of the six sub-rays are recalculated, there will be a lot of invalid rays, which do not consist of paths. This will waste much time.

Using this exact algorithm, the ray cone angle shrinks to $1/\sqrt{3}$ each iteration, so the error angle for the $ith$ iteration is

In this way, 10 iterations can lead to 24dB reduction in error of angle, distance and power. Besides, exponential error reduction can be achieved with a linear time penalty.