Relative encoding for a block-based bounding volume hierarchy

摘要

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.

主权项

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.