Bounded volume hierarchy (BVH) tree traversal using spatial division

Patent metadata

Field	Value
Publication number	US-11282260-B2
Application number	US-202016896955-A
Country	US
Kind code	B2
Filing date	Jun 9, 2020
Priority date	Jun 9, 2020
Publication date	Mar 22, 2022
Grant date	Mar 22, 2022

Abstract

A method is presented. The method includes organizing a scene as a number of bounding volumes in a hierarchical data structure. The method also includes generating a grid based on the hierarchical data structure. The method further includes mapping each node of the hierarchical data structure to at least one cell of the grid. The method additionally includes identifying a cell of the grid corresponding to an initial intersection location of a ray and the scene. The method still further includes 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. The method also includes traversing the hierarchical data structure starting from the start node to identify a number a primitives intersected by the ray.

First claim

What is claimed is:

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.

Assignees

• Qualcomm Inc

Inventors

• Gupta Piyush
• Malhotra Geetika
• Akkaraju Pavan Kumar

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T15/08

  Volume rendering · CPC title

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title

• G06T2210/12

  Bounding box · CPC title