Relative encoding for a block-based bounding volume hierarchy

Patent metadata

Field	Value
Publication number	US-9552664-B2
Application number	US-201514589910-A
Country	US
Kind code	B2
Filing date	Jan 5, 2015
Priority date	Sep 4, 2014
Publication date	Jan 24, 2017
Grant date	Jan 24, 2017

Abstract

A system, method, and computer program product for implementing a tree traversal operation for a tree data structure 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 and processing, via a tree traversal operation algorithm executed by a processor, one or more nodes of the tree data structure by intersecting the one or more nodes of the tree data structure with a query data structure. A first node of the tree data structure is associated with a first local coordinate system and a second node of the tree data structure is associated with a second local coordinate system, the first node being an ancestor of the second node, and the first local coordinate system and the second local coordinate system are both specified relative to a global coordinate system.

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; and
processing, via a tree traversal operation algorithm executed by a tree traversal unit of a processor, one or more nodes of the tree data structure by intersecting the one or more nodes of the tree data structure with a query data structure,
wherein a first local coordinate system associated with a first node of the plurality of nodes and a second local coordinate system associated with a second node of the plurality of nodes are encoded in the tree data structure,
wherein the first node is an ancestor of the second node in a hierarchy of the tree data structure,
wherein the first local coordinate system and the second local coordinate system are specified relative to a global coordinate system, and
wherein the tree traversal unit includes a scheduler unit, a setup unit, one or more traversal units, and local storage for a plurality of query data structures and a plurality of stack data structures.

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

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

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

5. The method of claim 3 , wherein the scale factor for each axis of the local coordinate system is represented by a corresponding n-bit integer having a value e, and wherein the extents of the local coordinate system may be calculated by multiplying unit vectors corresponding to each axis of the global coordinate system by a power of two, where the value e is the exponent of the power of two.

6. The method of claim 1 , wherein the tree data structure is encoded as a plurality of compression block data structures stored in a memory, and wherein each compression block data structure includes data associated with a subset of nodes of the tree.

7. The method of claim 6 , wherein each compression block data structure encodes a local coordinate system specified relative to the global coordinate system, wherein the local coordinate system is associated with a block root node of the compression block data structure and one or more bounding volumes specified relative to the local coordinate system.

8. The method of claim 7 , wherein the one or more bounding volumes in the compression block data structure comprise axis-aligned bounding boxes (AABBs) that include six planes, each plane specified relative to the local coordinate system associated with the compression block data structure.

9. The method of claim 8 , wherein a location of each plane, relative to the local coordinate system, may be specified by an n-bit integer having a value m that indicates a distinct location on a particular axis of the local coordinate system based on a product of the value m and a scale factor s.

10. The method of claim 9 , wherein the value m is encoded as an unsigned 8-bit integer having a value between 0 and 255, and the scale factor s is encoded by a low-precision value e that is an 8-bit signed integer having a value between −128 and 127.

11. 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; and
processing, via a tree traversal operation algorithm executed by a tree traversal unit of the processor, one or more nodes of the tree data structure by intersecting the one or more nodes of the tree data structure with a query data structure,
wherein a first local coordinate system associated with a first node of the plurality of nodes and a second local coordinate system associated with a second node of the plurality of nodes are encoded in the tree data structure,
wherein the first node is an ancestor of the second node in a hierarchy of the tree data structure,
wherein the first local coordinate system and the second local coordinate system are specified relative to a global coordinate system, and
wherein the tree traversal unit includes a scheduler unit, a setup unit, one or more traversal units, and local storage for a plurality of query data structures and a plurality of stack data structures.

12. The computer-readable storage medium of claim 11 , wherein each of the local coordinate systems is encoded using three high-precision values to specify an origin of the local coordinate system relative to the global coordinate system and three low-precision values to specify a scale factor for each axis of the local coordinate system.

13. The computer-readable storage medium of claim 12 , wherein the scale factor for each axis of the local coordinate system is represented by a corresponding n-bit integer having a value e, and wherein the extents of the local coordinate system may be calculated by multiplying unit vectors corresponding to each axis of the global coordinate system by a power of two, where the value e is the exponent of the power of two.

14. The computer-readable storage medium of claim 11 , wherein the tree data structure is encoded as a plurality of compression block data structures stored in a memory, and wherein each compression block data structure includes data associated with a subset of nodes of the tree.

15. The computer-readable storage medium of claim 14 , wherein each compression block data structure encodes a local coordinate system specified relative to the global coordinate system, wherein the local coordinate system is associated with a block root node of the compression block data structure and one or more bounding volumes specified relative to the local coordinate system.

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; and
a processor configured to execute a tree traversal operation algorithm that causes the processor to:
receive at least a portion of the tree data structure, and
process, by a tree traversal unit of the processor, one or more nodes of the tree data structure by intersecting the one or more nodes of the tree data structure with a query data structure,

wherein a first local coordinate system associated with a first node of the plurality of nodes and a second local coordinate system associated with a second node of the plurality of nodes are encoded in the tree data structure,
wherein the first node is an ancestor of the second node in a hierarchy of the tree data structure,
wherein the first local coordinate system and the second local coordinate system are specified relative to a global coordinate system, and
wherein the tree traversal unit includes a scheduler unit, a setup unit, one or more traversal units, and local storage for a plurality of query data structures and a plurality of stack data structures.

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

18. Th

Assignees

• Nvidia Corp

Inventors

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

Classifications

• G06T17/005 Primary

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

• G06T15/10 Primary

  Geometric effects · CPC title

• G06T15/06

  Ray-tracing · CPC title

• G06T17/10

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06T15/80

  Shading · CPC title