Tree data structures based on a plurality of local coordinate systems

Patent metadata

Field	Value
Publication number	US-10025879-B2
Application number	US-201514697480-A
Country	US
Kind code	B2
Filing date	Apr 27, 2015
Priority date	Sep 4, 2014
Publication date	Jul 17, 2018
Grant date	Jul 17, 2018

Abstract

A system, computer readable medium, and method are disclosed for performing a tree traversal operation. The method includes the steps of executing, via a processor, a tree traversal operation for a tree data structure, receiving a transformation node that includes transformation data during the tree traversal operation, and transforming spatial data included in a query data structure based on the transformation data. Each node in the tree data structure is classified according to one of a plurality of nodesets, the plurality of nodesets corresponding to a plurality of local coordinate systems. 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 processor, a tree traversal operation for a tree data structure, wherein each node in the tree data structure is classified into one of a plurality of nodesets, the plurality of nodesets corresponding to a plurality of local coordinate systems, wherein spatial values encoded within each node are specified relative to the local coordinate system;
receiving, at the processor, a transformation node during the tree traversal operation, wherein the transformation node includes transformation data;
transforming, by the processor, a query shape represented by a query data structure from a global coordinate system to a first local coordinate system of the plurality of local coordinate systems based on the transformation data, wherein each local coordinate system has a higher level of spatial resolution compared with the global coordinate system; and
generating a color value for a pixel intersected by the query data structure when the transformed query shape intersects a first node in the tree data structure.

2. The method of claim 1 , wherein the tree data structure represents a bounding volume hierarchy (BVH).

3. The method of claim 1 , further comprising:
receiving the tree data structure at the processor; and
classifying, by the processor, the nodes of the tree data structure into the plurality of nodesets.

4. The method of claim 3 , wherein classifying the nodes of the tree data structure into the plurality of nodesets comprises:
creating an initial proposed classification for the nodes by classifying all nodes in the tree data structure into a single nodeset;
evaluating a cost function for each nodeset in the proposed classification to calculate a set of cost values;
determining that at least one nodeset in the proposed classification did not meet the acceptance criterion; and
adjusting the proposed classification of the nodes into one or more new nodesets, evaluating the cost function for each nodeset in the adjusted proposed classification, and determining whether each of the nodesets in the adjusted proposed classification meets the acceptance criterion.

5. The method of claim 4 , wherein adjusting the proposed classification of the nodes comprises, for each nodeset that does not meet the acceptance criterion:
classifying the root node of the nodeset into a top-level nodeset; and
splitting the nodeset into multiple lower-level nodesets, where each nodeset in the multiple lower-level nodesets corresponds to a subtree associated with a child node of the root node.

6. The method of claim 4 , wherein the cost function estimates the expected number of additional intersection tests that need to be performed due to conservative rounding.

7. The method of claim 1 , further comprising selecting the local coordinate system for each nodeset by calculating a geometric center of a set of bounding volumes associated with the nodes in the nodeset, wherein the geometric center is selected as the origin of the local coordinate system.

8. The method of claim 1 , wherein the transformation data comprises a scale factor represents a difference in scale between the global coordinate system and the first local coordinate system.

9. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform steps comprising:
executing a tree traversal operation for a tree data structure, wherein each node in the tree data structure is classified according to one of a plurality of nodesets, the plurality of nodesets corresponding to a plurality of local coordinate systems, wherein spatial values encoded within each node are specified relative to the local coordinate system;
receiving a transformation node during the tree traversal operation by the setup unit, wherein the transformation node includes transformation data;
transforming a query shape represented by a query data structure from a global coordinate system to a first local coordinate system of the plurality of local coordinate systems based on the transformation data, wherein each local coordinate system has a higher level of spatial resolution compared with the global coordinate system; and
generating a color value for a pixel intersected by the query data structure when the transformed query shape intersects a first node in the tree data structure.

10. The method of claim 1 , further comprising intersecting the transformed query shape with the spatial values encoded within the first node that are specified relative to the first local coordinate system.

11. The non-transitory computer-readable storage medium of claim 9 , wherein the transformation data comprises a scale factor represents a difference in scale between the global coordinate system and the first local coordinate system.

12. The non-transitory computer-readable storage medium of claim 9 , the steps further comprising:
receiving the tree data structure at the processor; and
classifying, by the processor, the nodes of the tree data structure into the plurality of nodesets.

13. The non-transitory computer-readable storage medium of claim 12 , wherein classifying the nodes of the tree data structure into the plurality of nodesets comprises:
creating an initial proposed classification for the nodes by classifying all nodes in the tree data structure into a single nodeset;
evaluating a cost function for each nodeset in the proposed classification to calculate a set of cost values;
determining that at least one nodeset in the proposed classification did not meet the acceptance criterion; and
adjusting the proposed classification of the nodes into one or more new nodesets, evaluating the cost function for each nodeset in the adjusted proposed classification, and determining whether each of the nodesets in the adjusted proposed classification meets the acceptance criterion.

14. The method of claim 13 , wherein adjusting the proposed classification of the nodes comprises, for each nodeset that does not meet the acceptance criterion:
classifying the root node of the nodeset into a top-level nodeset; and
splitting the nodeset into multiple lower-level nodesets, where each nodeset in the multiple lower-level nodesets corresponds to a subtree associated with a child node of the root node.

15. The non-transitory computer-readable storage medium of claim 9 , further comprising selecting the local coordinate system for each nodeset by calculating a geometric center of a set of bounding volumes associated with the nodes in the nodeset, wherein the geometric center is selected as the origin of the local coordinate system.

16. The non-transitory computer-readable storage medium of claim 9 , further comprising intersecting the transformed query shape with the spatial values encoded within the first node that are specified relative to the first local coordinate system.

17. A system, comprising:
a parallel processing unit that includes at least one tree traversal unit configured to:
execute a tree traversal operation for a tree data structure, wherein each node in the tree data structure is classified according to one of a plurality of nodesets, the plurality of nodesets corresponding to a plurality of local coordinate systems, wherein spatial values encoded within each node are specified relative to the local coordinate system,
receive a transformation node during the tree traversal operation, wherein the transformation node includes transformation data,
transform a query shape represented by a query data structure from a global coordinate system

Assignees

• Nvidia Corp

Inventors

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

Classifications

• G06T9/001

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

• G06T15/005

  General purpose rendering architectures · CPC title

• G06F16/9027 Primary

  Trees · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• H04N19/174

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