Agglomerative treelet restructuring for bounding volume hierarchies

Patent metadata

Field	Value
Publication number	US-9817919-B2
Application number	US-201314065321-A
Country	US
Kind code	B2
Filing date	Oct 28, 2013
Priority date	Jun 10, 2013
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

A system, method, and computer program product are provided for modifying a hierarchical tree data structure. An initial hierarchical tree data structure is received, and treelets of node neighborhoods are formed. A processor restructures the treelets using agglomerative clustering to produce an optimized hierarchical tree data structure that includes at least one restructured treelet, where each restructured treelet includes at least one internal node.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a parallel processing unit that is configured to execute threads in a group of threads in parallel, an initial hierarchical tree data structure;
forming treelets of node neighborhoods; and
restructuring, by the parallel processing unit executing the threads in parallel, a first treelet of the treelets to produce a restructured hierarchical tree data structure including at least one restructured treelet, wherein the restructuring comprises:
merging a portion of treelet nodes within the first treelet to produce internal treelet nodes;
computing a first surface area cost of the internal treelet nodes; and
before merging remaining treelet nodes within the first treelet, estimating a second surface area cost of additional internal treelet nodes to be produced by merging the remaining treelet nodes.

2. The method of claim 1 , wherein the restructuring further comprises:
initializing a set of nodes yet to be merged within the portion of treelet nodes to include n treelet leaf nodes;
merging, in parallel, two or more pairs of the nodes in the set to generate at least a portion of the internal treelet nodes; and
removing the two or more pairs of the nodes from the set.

3. The method of claim 2 , wherein the restructuring further comprises:
before the merging, adding at least one of the portion of the internal treelet nodes to the set of nodes; and
repeating the merging, removing, and adding until less than a pre-determined number of nodes remain in the set of nodes yet to be merged.

4. The method of claim 1 , wherein the restructuring further comprises:
constructing a restructured treelet corresponding to a second treelet of the treelets; and
replacing the second treelet with the restructured treelet if a cost function indicates that the restructured treelet improves the hierarchical tree data structure.

5. The method of claim 1 , wherein the restructuring further comprises reusing treelet leaf nodes of the first treelet to produce a restructured treelet having a different depth-first order of the treelet leaf nodes than the first treelet.

6. The method of claim 1 , wherein the initial hierarchical tree data structure is a bounding volume hierarchy tree data structure.

7. The method of claim 1 , wherein the restructuring of the first treelet is performed in parallel by allocating one of the threads to each treelet node in the portion of treelet nodes.

8. The method of claim 1 , further comprising constructing the initial hierarchical tree data structure using a construction technique that produces an initial hierarchical tree data structure having three or more nodes.

9. The method of claim 1 , further comprising:
restructuring the at least one restructured treelet to produce at least one additional restructured treelet; and
for each treelet root, selecting either a restructured treelet from the at least one restructured treelet or a corresponding restructured treelet from the at least one additional restructured treelet.

10. The method of claim 1 , further comprising:
restructuring a second treelet of the treelets using agglomerative clustering to produce a second restructured treelet;
using a combination of the first treelet and the second treelet.

11. The method of claim 1 , further comprising:
using the hierarchical tree data structure to perform intersection tests;
forming second treelets of node neighborhoods; and
restructuring the second treelets.

12. A system comprising:
a memory storing a initial hierarchical tree data structure; and
a parallel processing unit that is coupled to the memory and executes threads in a group of threads in parallel and is configured to:
receive the initial hierarchical tree data structure;
form treelets of node neighborhoods; and
restructure a first treelet of the treelets to produce a restructured hierarchical tree data structure by executing the threads in parallel, wherein the restructuring comprises:
merging a portion of treelet nodes within the first treelet to produce internal treelet nodes;
computing a first surface area cost of the internal treelet nodes; and
before merging remaining treelet nodes within the first treelet, estimating a second surface area cost of additional internal treelet nodes to be produced by merging the remaining treelet nodes.

13. The system of claim 12 , wherein the restructuring of the first treelet is performed in parallel by allocating one of the threads to each treelet node in the portion of treelet nodes.

14. A non-transitory computer-readable storage medium storing instructions that, when executed by a parallel processing unit, cause the parallel processing unit to modify a hierarchical tree data structure, comprising:
receiving, by a parallel processing unit that is configured to execute threads in a group of threads in parallel, an initial hierarchical tree data structure;
forming treelets of node neighborhoods; and
restructuring a first treelet of the treelets to produce a restructured hierarchical tree data structure by executing the threads in parallel, wherein the restructuring comprises:
merging a portion of treelet nodes within the first treelet to produce internal treelet nodes;
computing a first surface area cost of the internal treelet nodes; and
before merging remaining treelet nodes within the first treelet, estimating a second surface area cost of additional internal treelet nodes to be produced by merging the remaining treelet nodes.

Assignees

• Nvidia Corp

Inventors

• Aila Timo Oskari
• Karras Tero Tapani

Classifications

• G06F16/9027 Primary

  Trees · CPC title

• G06F17/30961 Primary

  Physics · mapped topic