Block-based bounding volume hierarchy

Patent metadata

Field	Value
Publication number	US-9582607-B2
Application number	US-201514589904-A
Country	US
Kind code	B2
Filing date	Jan 5, 2015
Priority date	Sep 4, 2014
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

Abstract

A system, method, and computer program product for implementing a tree traversal operation for a tree data structure divided into compression blocks is disclosed. The method includes the steps of receiving at least a portion of a tree data structure that represents a tree having a plurality of nodes, pushing a root node of the tree data structure onto a traversal stack data structure associated with an outer loop of a tree traversal operation algorithm, and, for each iteration of an outer loop of a tree traversal operation algorithm, popping a top element from the traversal stack data structure and processing, via an inner loop of the tree traversal operation algorithm, the compression block data structure that corresponds with the top element. The tree data structure may be encoded as a plurality of compression block data structures that each include data associated with a subset of nodes of the tree.

First claim

What is claimed is:

1. A method, comprising:
receiving at least a portion of a tree data structure that represents a tree having a plurality of nodes, the tree data structure encoded as a plurality of compression block data structures stored in a memory, wherein each compression block data structure includes data associated with a subset of nodes of the tree;
pushing a root node of the tree data structure onto a traversal stack data structure associated with an outer loop of a tree traversal operation algorithm that is configured, when executed by a processor, to process compression block data structures that are intersected by a query data structure; and
for each iteration of the outer loop:
popping a top element from the traversal stack data structure that corresponds with a compression block data structure, and
processing, via an inner loop of the tree traversal operation algorithm executed by the processor, the compression block data structure that corresponds with the top element.

2. The method of claim 1 , wherein the query data structure comprises a ray data structure that specifies a ray to be intersected with the tree data structure during execution of the tree traversal operation algorithm.

3. The method of claim 1 , wherein a size of each compression block data structure is equal to a size of a memory transaction quantum.

4. The method of claim 1 , wherein each compression block data structure encodes a bounding volume associated with a block root node for the corresponding compression block data structure using six high-precision values.

5. The method of claim 1 , wherein each compression block data structure encodes a local coordinate system associated with a block root node of the corresponding compression block data structure and a bounding volume associated with each additional node of the corresponding compression block data structure, wherein bounding volumes within a particular compression block data structure are specified relative to the local coordinate system associated with the block root node of the particular compression block data structure.

6. The method of claim 5 , wherein the local coordinate system is encoded using three high-precision values to specify an origin of the local coordinate system relative to a global coordinate system and three low-precision values to specify a scale factor for each axis of the local coordinate system.

7. The method of claim 6 , wherein the high-precision values comprise 32-bit floating point values and the low-precision values comprise 8-bit integers.

8. The method of claim 1 , wherein each compression block data structure encodes a topology of the corresponding subset of nodes by associating each node corresponding to the compression block data structure with a node type identifier.

9. The method of claim 1 , wherein a bounding volume for at least one node in the compression block data structure is associated with information that indicates which planes of a first axis-aligned bounding box associated with the node are inherited from a second axis-aligned bounding box associated with a parent node of the node.

10. The method of claim 1 , wherein at least one subset of nodes includes an internal node, a leaf node, and a transition node.

11. The method of claim 1 , wherein at least one compression block data structure included in the tree data structure includes at least two transition nodes or at least two leaf nodes, and wherein pointers associated with the at least two transition nodes or at least two leaf nodes are encoded using a node indexing technique that explicitly encodes a first pointer associated with a first transition node or a first leaf node in the compression block data structure and implicitly encodes one or more additional pointers associated with one or more additional transition nodes or one or more additional leaf nodes based on a topology of nodes within the compression block data structure.

12. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform steps comprising:
receiving at least a portion of a tree data structure that represents a tree having a plurality of nodes, the tree data structure encoded as a plurality of compression block data structures stored in a memory, wherein each compression block data structure includes data associated with a subset of nodes of the tree;
pushing a root node of the tree data structure onto a traversal stack data structure associated with an outer loop of a tree traversal operation algorithm that is configured, when executed by a processor, to process compression block data structures that are intersected by a query data structure; and
for each iteration of the outer loop:
popping a top element from the traversal stack data structure that corresponds with a compression block data structure, and
processing, via an inner loop of the tree traversal operation algorithm executed by the processor, the compression block data structure that corresponds with the top element.

13. The computer-readable storage medium of claim 12 , wherein each compression block data structure encodes a local coordinate system associated with a block root node of the corresponding compression block data structure and a bounding volume associated with each additional node of the corresponding compression block data structure, wherein bounding volumes within a particular compression block data structure are specified relative to the local coordinate system associated with the block root node of the particular compression block data structure.

14. The computer-readable storage medium of claim 12 , wherein at least one compression block data structure included in the tree data structure includes at least two transition nodes or at least two leaf nodes, and wherein pointers associated with the at least two transition nodes or at least two leaf nodes are encoded using a node indexing technique that explicitly encodes a first pointer associated with a first transition node or a first leaf node in the compression block data structure and implicitly encodes one or more additional pointers associated with one or more additional transition nodes or one or more additional leaf nodes based on a topology of nodes within the compression block data structure.

15. The computer-readable storage medium of claim 12 , wherein the processor is a parallel processing unit that includes one or more tree traversal units, and wherein a size of each compression block data structure is equal to a size of one cache line in a local cache unit included in each of the tree traversal units.

16. A system, comprising:
a memory storing at least a portion of a tree data structure that represents a tree having a plurality of nodes, the tree data structure encoded as a plurality of compression block data structures, wherein each compression block data structure includes data associated with a subset of nodes of the tree; and
a processor for performing a tree traversal operation, the processor configured to:
push a root node of the tree data structure onto a traversal stack data structure associated with an outer loop of a tree traversal operation algorithm that is configured to process compression block data structures that are intersected by a query data structure, and
for each iteration of the outer loop executed by the processor:
pop a top element from the traversal stack data structure that corresponds with a compression block data structure, and
process, via an inner loop of the tree traversal operation algorithm, the compression block data structure that

Assignees

• Nvidia Corp
• Nividia Corp

Inventors

• Laine Samuli Matias
• Aila Timo Oskari
• Karras Tero Tapani

Classifications

• G06T9/001

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

• G06F16/254

  Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title

• G06T9/40

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

• G06T15/10

  Geometric effects · CPC title