Bounded volume hierarchy (BVH) tree traversal using spatial division

1. A method comprising:

organizing a scene as a plurality of bounding volumes in a hierarchical data structure;

generating a grid based on the hierarchical data structure;

mapping each node of the hierarchical data structure to at least one cell of the grid;

identifying a cell of the grid corresponding to an initial intersection location of a ray and the scene;

determining a non-root node of the hierarchical data structure as a start node for traversing the hierarchical data structure based on the identified cell; and

traversing the hierarchical data structure starting from the start node to identify a plurality of primitives intersected by the ray, traversing the hierarchical data comprising:

traversing to a subsequent cell via a three-dimensional digital differential analyzer (DDA) function when the identified cell is NULL or previously visited; and

terminating the traversing via the three-dimensional DDA function based on a distance between a boundary of the identified cell and a boundary of the subsequent cell being greater than a distance to an intersection between the ray and a primitive in the identified cell.

2. The method of claim 1 , further comprising mapping each node to a grid cell based on a depth first search of the hierarchical data structure.

3. The method of claim 1 , in which mapping each node comprises:

identifying at least one cell in the grid comprising a portion of a bounding volume corresponding to the node;

determining whether the at least one cell is associated with an other node;

mapping a least one common ancestor of the node and the other node when the at least one cell is associated with the other node; and

mapping the node to the at least one cell when the at least one cell is not associated with the other node.

4. The method of claim 1 , in which the hierarchical data structure comprises a bounded volume hierarchy (BVH) tree.

5. An apparatus for wireless communication, comprising:

a processor;

memory coupled with the processor; and

instructions stored in the memory and operable, when executed by the processor, to cause the apparatus:

to organize a scene as a plurality of bounding volumes in a hierarchical data structure;

to generate a grid based on the hierarchical data structure;

to map each node of the hierarchical data structure to at least one cell of the grid;

to identify a cell of the grid corresponding to an initial intersection location of a ray and the scene;

to determine a non-root node of the hierarchical data structure as a start node for traversing the hierarchical data structure based on the identified cell; and

to traverse the hierarchical data structure starting from the start node to identify a plurality of primitives intersected by the ray, execution of the instructions that cause the apparatus to traverse the hierarchical data further cause the apparatus:

to traverse to a subsequent cell via a three-dimensional digital differential analyzer (DDA) function when the identified cell is NULL or previously visited; and

to terminate the traversing via the three-dimensional DDA function based on a distance between a boundary of the identified cell and a boundary of the subsequent cell being greater than a distance to an intersection between the ray and a primitive in the identified cell.

6. The apparatus of claim 5 , in which execution of the instructions further cause the apparatus to map each node to a grid cell based on a depth first search of the hierarchical data structure.

7. The apparatus of claim 5 , in which execution of the instructions that cause the apparatus to map each node, further cause the apparatus:

to identify at least one cell in the grid comprising a portion of a bounding volume corresponding to the node;

to determine whether the at least one cell is associated with an other node;

to map a least one common ancestor of the node and the other node when the at least one cell is associated with the other node; and

to map the node to the at least one cell when the at least one cell is not associated with the other node.

8. The apparatus of claim 5 , in which the hierarchical data structure comprises a bounded volume hierarchy (BVH) tree.

9. A non-transitory computer-readable medium having program code recorded thereon, the program code executed by an apparatus and comprising:

program code to organize a scene as a plurality of bounding volumes in a hierarchical data structure;

program code to generate a grid based on the hierarchical data structure;

program code to map each node of the hierarchical data structure to at least one cell of the grid;

program code to identify a cell of the grid corresponding to an initial intersection location of a ray and the scene;

program code to determine a non-root node of the hierarchical data structure as a start node for traversing the hierarchical data structure based on the identified cell; and

program code to traverse the hierarchical data structure starting from the start node to identify a plurality of primitives intersected by the ray, the program code to traverse the hierarchical data further comprising:

program code to traverse to a subsequent cell via a three-dimensional digital differential analyzer (DDA) function when the identified cell is NULL or previously visited; and

program code to terminate the traversing via the three-dimensional DDA function based on a distance between a boundary of the identified cell and a boundary of the subsequent cell being greater than a distance to an intersection between the ray and a primitive in the identified cell.

10. The non-transitory computer-readable medium of claim 9 , further comprising program code to map each node to a grid cell based on a depth first search of the hierarchical data structure.

11. The non-transitory computer-readable medium of claim 9 , in which the program code to map each node comprises:

program code to identify at least one cell in the grid comprising a portion of a bounding volume corresponding to the node;

program code to determine whether the at least one cell is associated with an other node;

program code to map a least one common ancestor of the node and the other node when the at least one cell is associated with the other node; and

program code to map the node to the at least one cell when the at least one cell is not associated with the other node.

12. The method of claim 1 , in which dimensions of the grid are based on dimensions of a root node of the hierarchical data structure.

13. The apparatus of claim 5 , in which dimensions of the grid are based on dimensions of a root node of the hierarchical data structure.

14. The non-transitory computer-readable medium of claim 9 , in which dimensions of the grid are based on dimensions of a root node of the hierarchical data structure.