Block-based bounding volume hierarchy

摘要

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.

主权项

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, andprocessing, 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.