* The incident ray is diffracted from one of the three edges of the facet.
Therefore, a ray-triangle intersection algorithm is required to test if a given ray hits a given facet of a building. Unfortunately, even very fast ray-triangle intersection algorithms are computationally very expensive. If the mesh triangles are not organized spatially, a brute-force SBR solver will have to perform NÃM intersection calculations, where N is the total number of rays and M is the total number of triangular facets in the scene. This is one of the main reasons why conventional ray tracers take a significant amounts of time to solve large-scale propagation scenes that involve hundreds of buildings and thousands of rays.
The solution to the geometric problem of ray-facet intersections can be significantly accelerated by using a k-dimensional (k-d) tree to subdivide the computational domain. A k-d tree, a special case of a binary tree, is a spatial partitioning data structure that is used for organizing points in a k-dimensional space. Using a k-d tree reduces the number of ray-triangle intersection calculations that is required for each ray. In other words, the algorithm used to navigate or traverse a k-d tree is computationally less expensive than a brute-force ray-triangle intersection calculation. The k-d tree is constructed by dividing the computational domain into two partitions and then sorting all the triangles into the two partitions. This process is repeated for the two newly generated partitions until a termination criterion is met. The key to constructing a useful and computationally efficient k-d tree is intelligently deciding on when and where to split each space. A well constructed k-d tree can be many times faster than a poorly constructed one.