5.2.7 Splitting Strategies

Different splitting strategies have been proposed to reduce the average number of traversed boxes [39,72]. Among the simplest are the spatial median (SM) and the object median (OM) splitting strategy. The first algorithm chooses the splitting plane in such a way that the box is separated into two boxes of approximately equal size. The second algorithm uses the OM instead, which attempts to create boxes containing approximately the same number of objects. The objects are in this case the non-empty cells. Figure 5.3 shows the corresponding spatial subdivisions for both strategies.

Figure 5.3: The computational effort for calculating a particle trajectory can be reduced by using a subdivision of the simulation domain into boxes. Empty grid cells are combined in larger boxes while non-empty grid cells (gray) are boxes by their own. There are various splitting strategies to obtain a suitable decomposition.

A much better strategy was presented in [72], which explicitly attempts to reduce the average number of traversed subboxes. The surface area heuristic (SAH) strategy uses a cost model to decide which splitting plane is best. For the following considerations all rays are assumed to be uniformly distributed. This corresponds to an arriving flux distribution at ${\mathcal {P}}$ , which obeys the most frequently used directional distribution, the cosine distribution (2.5). Furthermore, the cost for a complete traversal through ${\mathcal{B}}$ is considered, which is not the case in reality, because particles are only tracked, until they reach the surface.

According to geometric probability theory [102], a uniformly distributed ray which intersects ${\mathcal{B}}$ , also intersects another axis-aligned box ${\mathcal{B}}_i$ with ${\mathcal{B}}_i\subseteq{\mathcal{B}}$ with a probability of

$${p}({\mathcal{B}}_i\mid{\mathcal{B}})=\frac{\funcSA ({\mathcal{B}}_i)}{\funcSA ({\mathcal{B}})}.$$ (5.22)

Here $\funcSA ({\mathcal{B}})$ and $\funcSA ({\mathcal{B}}_i)$ denote the surface areas of boxes ${\mathcal{B}}$ and ${\mathcal{B}}_i$ , respectively. Hence the average number of traversed subboxes is given by

$$\sum_{i=1}^{{{N}_{\text{B}}}}{p}({\mathcal{B}}_i\mid{\mathcal{B}}... ...um_{i=1}^{{{N}_{\text{B}}}}\funcSA ({\mathcal{B}}_i)}{\funcSA ({\mathcal{B}})}.$$ (5.23)

The SAH strategy attempts to choose the splitting planes in such a way that this expression is minimized. Finding the absolute minimum of (5.23) is usually not possible in reasonable time. Instead, before subdividing a box, the additional costs are estimated in order to choose the best splitting plane.

Consider a box ${\mathcal{B}}_X$ during setup of the spatial subdivision, which needs to be split further. This is the case, if ${\mathcal{B}}_X$ is still larger than a grid cell and contains at least one non-empty cell. Let ${N}_X\geq1$ be the number of non-empty grid cells in ${\mathcal{B}}_X$ which is subdivided along a certain plane into boxes ${\mathcal{B}}_Y$ and ${\mathcal{B}}_Z$ , which then contain ${N}_Y$ and ${N}_Z$ (with ${N}_Y+{N}_Z={N}_X$ ) non-empty grid cells, respectively. The additional costs are reduced, if the expression

$${N}_Y\cdot\funcSA ({\mathcal{B}}_Y)+{N}_Z\cdot\funcSA ({\mathcal{B}}_Z)$$ (5.24)

is minimized [39,72,134]. Due to the restriction that boxes are only split along grid planes, it is possible to evaluate (5.24) for all potential splitting planes and to select the splitting plane with the minimum value. If the extent of box ${\mathcal{B}}_X$ in the ${x}_i$ -direction (in terms of grid spacings) is denoted by ${L}_i$ , the number of potential splitting planes is $\sum_{i=1}^{D}\left({L}_i-1\right)$ . Subdivisions are favorable, which result in empty subboxes, because they do not need to be split further. For that purpose, expression (5.24) can be multiplied by a constant weight factor ${\chi}\leq1$ , if and only if ${N}_Y=0\vee{N}_Z=0$ is true for the corresponding splitting plane [134].

For good splitting strategies, such as the SAH, a logarithmic scaling with the number of objects can be observed for the average number of traversed boxes (5.23) [39]. Here the objects correspond to the non-empty cells which scale linearly with the surface size. Hence, as already stated in Section 5.2.4, the expected computational complexity of ray tracing is in the order of ${\mathcal{O}}({{N}_\text{S}}\log{{N}_\text{S}})$ where ${{N}_\text{S}}$ is a measure of the surface size.