Short stack traversal of tree data structures

Patent metadata

Field	Value
Publication number	US-10235338-B2
Application number	US-201414563872-A
Country	US
Kind code	B2
Filing date	Dec 8, 2014
Priority date	Sep 4, 2014
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

Abstract

A system, computer readable medium, and method are disclosed for performing a tree traversal operation utilizing a short stack data structure. The method includes the steps of executing, via a processor, a tree traversal operation for a tree data structure utilizing a short stack data structure, determining that the short stack data structure is empty after testing a current node in the tree traversal operation, and executing, via the processor, a back-tracking operation for the current node to identify a new node in the tree data structure to continue the tree traversal operation. The processor may be a parallel processing unit that includes one or more tree traversal units, which implement the tree traversal operation in hardware, software, or a combination of hardware and software.

First claim

What is claimed is:

1. A method, comprising:
executing, via a tree traversal unit within a processor, a tree traversal operation for a tree data structure utilizing a portion of memory within the processor allocated to a short stack data structure that is sized to include a fixed number of slots;
determining that the short stack data structure is empty after testing a current node in the tree traversal operation;
in response to determining the short stack data structure is empty, the tree traversal unit executes a back-tracking operation for the current node by ascending up the tree data structure from a parent node of the current node to identify an untested node in the tree data structure;
pushing the untested node onto the short stack data structure to continue the tree traversal operation beginning at the untested node; and
generating image data based on data associated with the nodes of the tree data structure that are intersected by rays according to the testing.

2. The method of claim 1 , wherein each slot is configured to temporarily store a pointer to a node of the tree data structure.

3. The method of claim 1 , further comprising:
setting a flag variable to an initial value before beginning the tree traversal operation; and
setting the flag variable to a new value when at least one node is dropped from the bottom of the short stack data structure during execution of the tree traversal operation, wherein the flag variable is maintained until the short stack structure becomes empty.

4. The method of claim 3 , wherein the back-tracking operation is conditionally performed based on the flag variable when the short stack data structure is empty.

5. The method of claim 3 , wherein the flag variable stores a binary value.

6. The method of claim 3 , wherein the flag variable stores a counter.

7. The method of claim 1 , wherein the back-tracking operation comprises:
determining that at least one other child node of the parent node intersects a query data structure; and
pushing the at least one other child node onto the short stack data structure and continuing the tree traversal operation,
wherein each node in the at least one other child node is later in the traversal order than the current node.

8. The method of claim 1 , wherein the back-tracking operation comprises:
pushing the parent node onto the short stack data structure; and
storing a value in a state variable to indicate that the parent node is entered from the current node before continuing the tree traversal operation.

9. The method of claim 1 , wherein the back-tracking operation comprises:
determining that no other child node of the parent node intersects the query data structure, wherein each other child node is later in the traversal order than the current node;
setting the current node equal to the parent node; and
repeating the back-tracking operation.

10. The method of claim 1 , further comprising generating a color value for a pixel intersected by a ray and a geometric primitive included in the current node.

11. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform steps comprising:
executing, via a tree traversal unit within the processor, a tree traversal operation for a tree data structure utilizing a portion of memory within the processor allocated to a short stack data structure that is sized to include a fixed number of slots;
determining that the short stack data structure is empty after testing a current node in the tree traversal operation;
in response to determining the short stack data structure is empty, executing, via the tree traversal unit, a back-tracking operation for the current node by ascending up the tree data structure from a parent node of the current node to identify an untested node in the tree data structure;
pushing the untested node onto the short stack data structure to continue the tree traversal operation beginning at the untested node; and
generating image data based on data associated with the nodes of the tree data structure that are intersected by rays according to the testing.

12. The non-transitory computer-readable storage medium of claim 11 , the steps further comprising:
setting a flag variable to an initial value before beginning the tree traversal operation;
setting the flag variable to a new value when at least one node is dropped from the bottom of the short stack data structure during continuation of the tree traversal operation, wherein the flag variable is maintained until the short stack structure becomes empty.

13. The computer-readable medium of claim 12 , wherein the back-tracking operation is conditionally performed based on the flag variable when the short stack data structure is empty.

14. The non-transitory computer-readable storage medium of claim 11 , wherein the back-tracking operation comprises:
determining that at least one other child node of the parent node intersects a query data structure; and
pushing the at least one other child node onto the short stack data structure and continuing the tree traversal operation, wherein each node in the at least one other child node is later in the traversal order than the current node.

15. The non-transitory computer-readable storage medium of claim 11 , wherein the back-tracking operation comprises:
pushing the parent node onto the short stack data structure; and
storing a value in a state variable to indicate that the parent node is entered from the current node before continuing the tree traversal operation.

16. A system, comprising:
a parallel processing unit that includes at least one tree traversal unit configured to:
perform a tree traversal operation of a tree data structure utilizing a portion of memory within the parallel processing unit allocated to a short stack data structure that is sized to include a fixed number of slots,
determine that the short stack data structure is empty after testing a current node in the tree traversal operation,
perform, in response to determining the short stack data structure is empty, a back-tracking operation for the current node by ascending up the tree data structure from a parent node of the current node to identify an untested node in the tree data structure, and
push the untested node onto the short stack data structure to continue the tree traversal operation beginning at the untested node, wherein image data is generated based on data associated with the nodes of the tree data structure that are intersected by rays according to the testing.

17. The system of claim 16 , wherein the back-tracking operation comprises:
determining that at least one other child node of the parent node intersects a query data structure; and
pushing the at least one other child node onto the short stack data structure and continuing the tree traversal operation, wherein each node in the at least one other child node is later in the traversal order than the current node.

18. The system of claim 16 , wherein the back-tracking operation comprises:
pushing the parent node onto the short stack data structure; and
storing a value in a state variable to indicate that the parent node is entered from the current node before continuing the tree traversal operation.

19. The system of claim 16 , wherein the at least one tree traversal unit is configured to:
set a flag variable to an initial value before beginning the back-tracking operation; and
set the flag variable to a new value when at least one node is droppe

Assignees

• Nvidia Corp

Inventors

• Laine Samuli Matias
• Aila Timo Oskari

Classifications

• G06T9/001

  Model-based coding, e.g. wire frame · CPC title

• G06F16/9027 Primary

  Trees · CPC title

• G06T15/06

  Ray-tracing · CPC title

• H04N19/174

  the region being a slice, e.g. a line of blocks or a group of blocks · CPC title

• G06T15/08

  Volume rendering · CPC title