Apparatus and method for acceleration data structure refit

Patent metadata

Field	Value
Publication number	US-11501484-B2
Application number	US-202017032964-A
Country	US
Kind code	B2
Filing date	Sep 25, 2020
Priority date	Dec 28, 2018
Publication date	Nov 15, 2022
Grant date	Nov 15, 2022

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.

First claim

What is claimed is:

1. A system comprising:
a central processing unit (CPU) comprising a first plurality of cores that are heterogeneous and that includes a first set of cores and a second set of cores that have a lower power consumption than the first set;
a graphics processor comprising:
a second plurality of cores to execute program code to render images, wherein at least one core comprises:
execution circuitry associated with the at least one core to execute at least a portion of the program code to perform a plurality of operations comprising:
constructing an acceleration data structure based on a plurality of primitives located within a three dimensional (3D) space, the acceleration data structure comprising nodes arranged in a hierarchy, each node associated with a bounding volume within the 3D space, the nodes including:
a plurality of leaf nodes at a bottom of the hierarchy, each leaf node bounding one or more of the primitives; and
one or more inner nodes, each inner node bounding one or more leaf nodes,

traversing one or more rays through the acceleration data structure,
identifying intersections between the one or more rays and one or more of the primitives,
detecting movement of one or more of the primitives to new locations in the 3D space, and
performing a bottom-up refit operation to adjust nodes of the acceleration data structure based on the new locations of the one or more primitives, the bottom-up refit operation comprising:
adjusting one or more of the leaf nodes based on the new locations of the one or more primitives, wherein the adjusting comprises moving the bounding volumes of the leaf nodes to reflect the new locations of the one or more primitives; and
adjusting an inner node if a leaf node bounded by the inner node was adjusted, wherein adjusting the inner node comprises merging the bounding volumes of the leaf nodes bounded by the inner node;

a memory controller to couple the first and second plurality of cores to a system memory device; and
the system memory device to be shared by the first plurality of cores including the first and second sets of cores, and the second plurality of cores,
wherein the CPU, the graphics processor, and the system memory device are within a system on a chip (SOC) of the system.

2. The system of claim 1 wherein the bottom-up refit operation comprises adjusting leaf nodes and inner nodes in a reverse depth-first search (DFS) order.

3. The system of claim 1 wherein adjusting the leaf nodes and inner nodes further comprises compressing the leaf nodes using a specified quantization.

4. The system of claim 1 wherein the execution circuitry is to perform the additional operation of: generating intersection results comprising hit data usable to launch one or more secondary rays.

5. The system of claim 1 wherein the acceleration data structure comprises a bounding volume hierarchy.

6. The system of claim 5 wherein the leaf nodes and inner nodes comprise 3D volumes within the hierarchy.

7. The system of claim 1 wherein the execution circuitry is to adjust the leaf nodes in parallel without any dependencies.

8. A graphics processor comprising:
a plurality of cores to execute program code to render images, wherein at least one core comprises:
execution circuitry associated with the at least one core to execute at least a portion of the program code to perform a plurality of operations comprising:
constructing an acceleration data structure based on a plurality of primitives located within a three dimensional (3D) space, the acceleration data structure comprising nodes arranged in a hierarchy, each node associated with a bounding volume within the 3D space, the nodes including:
a plurality of leaf nodes at a bottom of the hierarchy, each leaf node bounding one or more of the primitives; and
one or more inner nodes, each inner node bounding one or more leaf nodes,

traversing one or more rays through the acceleration data structure,
identifying intersections between the one or more rays and one or more of the primitives,
detecting movement of one or more of the primitives to new locations in the 3D space, and
performing a bottom-up refit operation to adjust nodes of the acceleration data structure based on the new locations of the one or more primitives, the bottom-up refit operation comprising:
adjusting one or more of the leaf nodes based on the new locations of the one or more primitives, wherein the adjusting comprises moving the bounding volumes of the leaf nodes to reflect the new locations of the one or more primitives; and
adjusting an inner node if a leaf node bounded by the inner node was adjusted, wherein adjusting the inner node comprises merging the bounding volumes of the leaf nodes bounded by the inner node.

9. The graphics processor of claim 8 wherein the bottom-up refit operation comprises adjusting leaf nodes and inner nodes in a reverse depth-first search (DFS) order.

10. The graphics processor of claim 8 wherein adjusting the leaf nodes and inner nodes further comprises compressing the leaf nodes using a specified quantization.

11. The graphics processor of claim 8 wherein the execution circuitry is to perform the additional operation of: generating intersection results comprising hit data usable to launch one or more secondary rays.

12. The graphics processor of claim 8 wherein the acceleration data structure comprises a bounding volume hierarchy.

13. The graphics processor of claim 12 wherein the leaf nodes and inner nodes comprise 3D volumes within the hierarchy.

14. The graphics processor of claim 8 wherein the execution circuitry is to adjust the leaf nodes in parallel without any dependencies.

15. A method comprising:
constructing an acceleration data structure based on a plurality of primitives located within a three dimensional (3D) space, the acceleration data structure comprising nodes arranged in a hierarchy, each node associated with a bounding volume within the 3D space, the nodes including a plurality of leaf nodes at a bottom of the hierarchy, each leaf node bounding one or more of the primitives, and one or more inner nodes, each inner node bounding one or more leaf nodes;
traversing one or more rays through the acceleration data structure;
identifying intersections between the one or more rays and one or more of the primitives;
detecting movement of one or more of the primitives to new locations in the 3D space; and
performing a bottom-up refit operation to adjust nodes of the acceleration data structure based on the new locations of the one or more primitives, the bottom-up refit operation comprising:
adjusting one or more of the leaf nodes based on the new locations of the one or more primitives, wherein the adjusting comprises moving the bounding volumes of the leaf nodes to reflect the new locations of the one or more primitives, and
adjusting an inner node if a leaf node bounded by the inner node was adjusted, wherein adjusting the inner node comprises merging the bounding volumes of the leaf nodes bounded by the inner node.

16. The method of claim 15 wherein the bottom-up refit operation comprises adjusting leaf nodes and inner nodes in a reverse depth-first search (DFS) order.

17. The method of claim 15 wherein adjusting the leaf nodes and inner nodes further comprises compressing the leaf nodes using a specified quantization.

18. The method of claim 15 further comprising: generating intersection results comprising hit data usable to launch one or more secondary rays.

19. The method of

Assignees

• Intel Corp

Inventors

• Apodaca Michael
• Benthin Carsten
• Xiao Kai
• Brownlee Carson
• Rowley Timothy
• Barczak Joshua
• Schluessler Travis

Classifications

• G06F7/14

  Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06N3/02

  Neural networks · CPC title

• G06F16/9027

  Trees · CPC title

• G06T1/60

  Memory management · CPC title