US2020211259A1PendingUtilityA1

Apparatus and method for acceleration data structure refit

53
Assignee: INTEL CORPPriority: Dec 28, 2018Filed: Dec 28, 2018Published: Jul 2, 2020
Est. expiryDec 28, 2038(~12.4 yrs left)· nominal 20-yr term from priority
Inventors:Michael ApodacaCarsten BenthinKai XiaoCarson BrownleeTimothy RowleyJoshua BarczakTravis T. Schluessler
Y02D10/00G06T 1/60G06T 1/20G06T 15/06G06F 9/3877G06F 16/9027G06N 3/02G06F 7/14G06T 5/002G06T 5/70
53
PatentIndex Score
0
Cited by
0
References
0
Claims

Abstract

Apparatus and method for acceleration data structure refit. For example, one embodiment of an apparatus comprises: a ray generator to generate a plurality of rays in a first graphics scene; a hierarchical acceleration data structure generator to construct an acceleration data structure comprising a plurality of hierarchically arranged nodes including inner nodes and leaf nodes stored in a memory in a depth-first search (DFS) order; traversal hardware logic to traverse one or more of the rays through the acceleration data structure; intersection hardware logic to determine intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; a node refit unit comprising circuitry and/or logic to read consecutively through at least the inner nodes in the memory in reverse DFS order to perform a bottom-up refit operation on the hierarchical acceleration data structure.

Claims

exact text as granted — not AI-modified
What is claimed is: 
     
         1 . An apparatus comprising:
 a ray generator to generate a plurality of rays in a first graphics scene;   a hierarchical acceleration data structure generator to construct an acceleration data structure comprising a plurality of hierarchically arranged nodes including inner nodes and leaf nodes stored in a memory in a depth-first search (DFS) order;   traversal hardware logic to traverse one or more of the rays through the acceleration data structure;   intersection hardware logic to determine intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure;   a node refit unit comprising circuitry and/or logic to read consecutively through at least the inner nodes in the memory in reverse DFS order to perform a bottom-up refit operation on the hierarchical acceleration data structure.   
     
     
         2 . The apparatus of  claim 1  wherein the node refit unit is to perform a first sequence of operations to iterate over all leaf nodes which point to leaf data, the node refit unit to update bounding volumes associated with one or more of the leaf nodes. 
     
     
         3 . The apparatus of  claim 2  wherein the node refit unit is to iterate in reverse DFS order over the inner nodes following the first sequence of operations. 
     
     
         4 . The apparatus of  claim 3  wherein the node refit unit is to further update bounding volumes associated with one or more of the inner nodes as part of the bottom-up refit operation. 
     
     
         5 . The apparatus of  claim 4  wherein updating bounding volumes associated with one or more of the inner nodes comprises merging one or more child nodes into one or more parent nodes. 
     
     
         6 . The apparatus of  claim 1  wherein the hierarchical acceleration data structure generator constructs the hierarchical acceleration data structure based on locations of primitives within the first graphics scene. 
     
     
         7 . The apparatus of  claim 6  wherein the node refit unit modifies the hierarchical acceleration data structure based on new locations of primitives within a second graphics scene. 
     
     
         8 . The apparatus of  claim 1  wherein the intersection hardware logic is to generate intersection results comprising hit data usable to launch one or more secondary rays. 
     
     
         9 . The apparatus of  claim 1  wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy, and wherein the nodes comprise portions of the hierarchy. 
     
     
         10 . A method comprising:
 generating a plurality of rays in a first graphics scene;   constructing an acceleration data structure comprising a plurality of hierarchically arranged nodes including inner nodes and leaf nodes stored in a memory in a depth-first search (DFS) order;   traversing one or more of the rays through the acceleration data structure;   determining intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; and   reading consecutively through at least the inner nodes in the memory in reverse DFS order to perform a bottom-up refit operation on the hierarchical acceleration data structure.   
     
     
         11 . The method of  claim 10  further comprising:
 performing a first sequence of operations to iterate over all leaf nodes which point to leaf data; and 
 updating bounding volumes associated with one or more of the leaf nodes. 
 
     
     
         12 . The method of  claim 10  further comprising:
 iterating in reverse DFS order over the inner nodes following the first sequence of operations. 
 
     
     
         13 . The method of  claim 12  further comprising:
 updating bounding volumes associated with one or more of the inner nodes as part of the bottom-up refit operation. 
 
     
     
         14 . The method of  claim 13  wherein updating bounding volumes associated with one or more of the inner nodes comprises merging one or more child nodes into one or more parent nodes. 
     
     
         15 . The method of  claim 10  further comprising:
 constructing the hierarchical acceleration data structure based on locations of primitives within the first graphics scene. 
 
     
     
         16 . The method of  claim 15  further comprising:
 modifying the hierarchical acceleration data structure based on new locations of primitives within a second graphics scene. 
 
     
     
         17 . The method of  claim 10  further comprising:
 generating intersection results comprising hit data usable to launch one or more secondary rays. 
 
     
     
         18 . The method of  claim 10  wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy, and wherein the nodes comprise portions of the hierarchy. 
     
     
         19 . A machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:
 generating a plurality of rays in a first graphics scene;   constructing an acceleration data structure comprising a plurality of hierarchically arranged nodes including inner nodes and leaf nodes stored in a memory in a depth-first search (DFS) order;   traversing one or more of the rays through the acceleration data structure;   determining intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; and   reading consecutively through at least the inner nodes in the memory in reverse DFS order to perform a bottom-up refit operation on the hierarchical acceleration data structure.   
     
     
         20 . The machine-readable medium of  claim 19  further comprising program code to cause the machine to perform the operations of:
 performing a first sequence of operations to iterate over all leaf nodes which point to leaf data; and 
 updating bounding volumes associated with one or more of the leaf nodes. 
 
     
     
         21 . The machine-readable medium of  claim 20  further comprising program code to cause the machine to perform the operations of:
 iterating in reverse DFS order over the inner nodes following the first sequence of operations. 
 
     
     
         22 . The machine-readable medium of  claim 21  further comprising program code to cause the machine to perform the operations of:
 updating bounding volumes associated with one or more of the inner nodes as part of the bottom-up refit operation. 
 
     
     
         23 . The machine-readable medium of  claim 22  wherein updating bounding volumes associated with one or more of the inner nodes comprises merging one or more child nodes into one or more parent nodes. 
     
     
         24 . The machine-readable medium of  claim 19  further comprising program code to cause the machine to perform the operations of:
 constructing the hierarchical acceleration data structure based on locations of primitives within the first graphics scene. 
 
     
     
         25 . The machine-readable medium of  claim 24  further comprising program code to cause the machine to perform the operations of:
 modifying the hierarchical acceleration data structure based on new locations of primitives within a second graphics scene. 
 
     
     
         26 . The machine-readable medium of  claim 19  further comprising program code to cause the machine to perform the operations of:
 generating intersection results comprising hit data usable to launch one or more secondary rays. 
 
     
     
         27 . The machine-readable medium of  claim 10  wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy, and wherein the nodes comprise portions of the hierarchy.

Join the waitlist — get patent alerts

Track US2020211259A1 — get alerts on status changes and closely related new filings.

We store only your email — no account needed. See our privacy policy.