5.2.8 Neighbor Links Arrays

To reduce the number of hierarchical traversals within a tree, direct neighbor links to subboxes have been proposed [72]. Apart from single neighbor links between nodes at the same level of the kd-tree, neighbor links trees can be used [39] to link leaves which correspond to subboxes, directly. A tree is set up for each face of a subbox to enable direct traversals to neighboring subboxes. Hence, using the exit point the next traversed subbox can be obtained by querying the corresponding neighbor links tree.

Figure 5.4: The arrays ${B}_l^{+}$ and ${B}_l^{-}$ with $l\in\lbrace 1,2\rbrace$ store the neighbor links of all subboxes for the positive and negative ${x}_l$ -direction, respectively. The array indices ${i}_1^{(k)}$ and ${i}_2^{(k)}$ , which are stored together with box ${\mathcal {B}}_k$ in array ${Q}$ , give access to the corresponding links. The additional arrays ${A}_l^\pm$ with $l\in\lbrace 1,2\rbrace$ allow fast access from the outside.

In the following discussion a new neighbor links data structure is presented. Using the fact that splitting planes are always aligned with the grid, arrays can be used to store the links to neighbor boxes, as demonstrated for a two-dimensional example in Figure 5.4. The number of links which are required for box ${\mathcal {B}}_k$ , is equal to its surface area $\funcSA ({\mathcal{B}}_k)$ (measured in grid spacings). $2{D}$ different arrays ${B}_1^\pm,\ldots,{B}_{D}^\pm$ hold the neighbor links in a certain grid direction for all boxes. The number of links is equal for opposite directions. Hence, for each box ${\mathcal {B}}_k$ only ${D}$ array indices ${i}_1^{(k)},\ldots,{i}_{D}^{(k)}$ have to be stored in order to obtain the corresponding neighbor links. The size of the array ${B}_l^\pm$ is given by

$$\dim({B}_l^\pm)=\sum_{k=1}^{{{N}_{\text{B}}}}\funcFA _l({\mathcal{B}}_k)$$ (5.25)

where $\funcFA _l({\mathcal{B}}_k)$ is the area of the face for which the normal points in the ${x}_l$ -direction:

$$\funcFA _l({\mathcal{B}}_k):=\prod_{\substack{i=1\\ i\neq l}}^{D}\left({b}^{(k)}_{{\text{max}},i}-{b}^{(k)}_{{\text{min}},i}\right).$$ (5.26)

Here ${\vec{b}}^{(k)}_{\text{min}}\in\mathbb{Z}^{D}$ and ${\vec{b}}^{(k)}_{\text{max}}\in\mathbb{Z}^{D}$ are the minimum and maximum index vectors of the corner grid points of box ${\mathcal {B}}_k$ . The index number of the neighboring box at point ${\vec{x}}\in\mathbb{R}^{D}$ , where the ray leaves ${\mathcal {B}}_k$ in the positive or negative ${x}_l$ -direction, is given by

$${B}_l^\pm \left[ {i}_l^{(k)}+{\Lambda}_l^{(k)}(\lfloor{x}_{l+1}\rfloor,\ldots,\lfloor{x}_{l+{D}-1}\rfloor) \right].$$ (5.27)

Here all subscripts are assumed to be cyclic modulo ${D}$ plus 1 and $\lfloor\cdot\rfloor$ denotes the floor function. The bijective function

$${\Lambda}_l^{(k)} : \prod_{i=l+1}^{l+{D}-1} \lbrace {b}^{(k)}_{{\... ...-1\rbrace \leftrightarrow \lbrace 0,\ldots,\funcFA _l({\mathcal{B}}_k)-1\rbrace$$ (5.28)

is defined as

$${\Lambda}_l^{(k)}({p}_{l+1},\ldots,{p}_{l+{D}-1}):= \sum_{i=l+1}^... ...j=l+1}^{i-1}\left({b}^{(k)}_{{\text{max}},j}-{b}^{(k)}_{{\text{min}},j}\right).$$ (5.29)

The inverse function of ${\Lambda}_l^{(k)}$ is denoted as $\bar{{\Lambda}}_l^{(k)}$ .

Additional links from outside of ${\mathcal{B}}$ allow finding the box which must be traversed first. They are stored in the $2{D}$ arrays ${A}_1^\pm, \ldots, {A}_{D}^\pm$ with size

$$\dim({A}_l^\pm)=\funcFA _l({\mathcal{B}}).$$ (5.30)

The first subbox which is traversed by a ray entering the box ${\mathcal{B}}$ at point ${\vec{x}}$ in the positive or negative ${x}_l$ -direction, is given by

$${A}_l^\pm \left[ {\Lambda}_l(\lfloor{x}_{l+1}\rfloor,\ldots,\lfloor{x}_{l+{D}-1}\rfloor) \right].$$ (5.31)

The memory requirements of the neighbor links array data structure are primarily given by the total surface area of all boxes $\sum_{k=1}^{{N}_{\text{B}}}\funcSA ({\mathcal{B}}_k)$ . An upper bound estimation can be derived for this sum using (5.23) and the fact that the typical ray traversal costs are ${\mathcal{O}}(\log{{N}_\text{S}})$

$$\sum_{k=1}^{{N}_{\text{B}}}\funcSA ({\mathcal{B}}_k) \leq {\mathcal{O}}(\log{{N}_\text{S}})\cdot\funcSA ({\mathcal{B}}).$$ (5.32)

For common problems the surface area of the bounding box ${\mathcal{B}}$ scales with the surface size. Therefore, a ${\mathcal{O}}({{N}_\text{S}}\log{{N}_\text{S}})$ scaling law can be expected.

Once an appropriate spatial subdivision is found for ${\mathcal{B}}$ , the neighbor links data structure can be set up. For subdivisions which are obtained by binary splitting in depth-first order, the neighbor links arrays data structure can be set up in optimal time (directly proportional to the total memory requirements) using Algorithm 5.1.

The neighbor links data structure allows an easy treatment of periodic boundary conditions. The boxes which are situated at the boundary can be directly linked to the corresponding boxes at the opposite boundary.