Unified architecture for BVH construction based on hardware pre-sorting and a parallel, reconfigurable clustering array

Patent metadata

Field	Value
Publication number	US-11727528-B2
Application number	US-202217724299-A
Country	US
Kind code	B2
Filing date	Apr 19, 2022
Priority date	Dec 28, 2018
Publication date	Aug 15, 2023
Grant date	Aug 15, 2023

Abstract

An apparatus comprising a sorting unit to sort primitives of a graphics image, the primitives to be grouped, each group to form a first level node of a hierarchical acceleration structure; a parallel reconfigurable clustering array to construct the hierarchical acceleration structure, the parallel reconfigurable clustering array comprising a plurality of processing clusters, each cluster comprising: parallel efficiency analysis circuitry to evaluate different groupings of the first level nodes for a next level of the hierarchical acceleration structure to determine efficiency values for the different groupings; and node merge circuitry to merge the first level nodes based on the efficiency values to form second level nodes.

First claim

What is claimed is:

1. An apparatus comprising:
memory array to store data for a first set of primitives of a graphics image, the first set of primitives sorted into groups each forming a first level node of a hierarchical acceleration structure;
efficiency analysis circuitry to access the data in the memory array and to evaluate, in parallel, a plurality of potential next-level groupings of the first level nodes to determine an efficiency estimation for each of the plurality of potential next-level groupings in accordance with a dynamically programmable cost or distance function; and
node merging circuitry to merge the first level nodes to form next-level nodes in the hierarchical acceleration structure based on the efficiency estimation for each potential next-level grouping.

2. The apparatus of claim 1 , wherein the cost or distance function comprising a surface area heuristic (SAH) and/or a Euclidean distance function, wherein the SAH function is used to calculate an expected cost of tracing a non-terminating random ray through the graphic image under a particular of grouping of the first level nodes.

3. The apparatus of claim 1 , further comprising:
controller circuitry to select the first set of primitives from a plurality of primitives of the graphics image stored in a main memory and to sort the first set of primitives into groups based on relative spatial locality between the primitives.

4. The apparatus of claim 1 , further comprising:
node injection circuitry to select a subset of the next-level nodes to be stored to the memory array for further evaluation by the efficiency analysis circuitry.

5. The apparatus of claim 1 , wherein the hierarchical acceleration structure comprises a bounding volume hierarchy (BVH).

6. The apparatus of claim 1 , wherein the memory array comprises a high-bandwidth SRAM array.

7. A method comprising:
sorting a first set of primitives of a graphics image into groups, each group forming a first level node of a hierarchical acceleration structure;
storing data for the sorted first set of primitives of a graphics image in a memory array;
accessing the data in the memory array and evaluating, in parallel, a plurality of potential next-level groupings of the first level nodes to determine an efficiency estimation for each of the plurality of potential next-level groupings in accordance with a dynamically programmable cost or distance function; and
merging the first level nodes to form next-level nodes in the hierarchical acceleration structure based on the efficiency estimation for each potential next-level grouping.

8. The method of claim 7 , wherein the cost or distance function comprising a surface area heuristic (SAH) and/or a Euclidean distance function, wherein the SAH function is used to calculate an expected cost of tracing a non-terminating random ray through the graphic image under a particular of grouping of the first level nodes.

9. The method of claim 7 , further comprising:
selecting the first set of primitives from a plurality of primitives of the graphics image stored in a main memory; and
sorting the first set of primitives into groups based on relative spatial locality between the primitives.

10. The method of claim 7 , further comprising:
selecting a subset of the next-level nodes to be stored to the memory array for further evaluation.

11. The method of claim 7 , wherein the hierarchical acceleration structure comprises a bounding volume hierarchy (BVH).

12. The method of claim 7 , wherein the memory array comprises a high-bandwidth SRAM array.

13. A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform operations of:
sorting a first set of primitives of a graphics image into groups, each group forming a first level node of a hierarchical acceleration structure;
storing data for the sorted first set of primitives of a graphics image in a memory array;
accessing the data in the memory array and evaluating, in parallel, a plurality of potential next-level groupings of the first level nodes to determine an efficiency estimation for each of the plurality of potential next-level groupings in accordance with a dynamically programmable cost or distance function; and
merging the first level nodes to form next-level nodes in the hierarchical acceleration structure based on the efficiency estimation for each potential next-level grouping.

14. The non-transitory machine-readable medium of claim 13 , wherein the cost or distance function comprising a surface area heuristic (SAH) and/or a Euclidean distance function, wherein the SAH function is used to calculate an expected cost of tracing a non-terminating random ray through the graphic image under a particular of grouping of the first level nodes.

15. The non-transitory machine-readable medium of claim 13 , wherein the operations further comprise:
selecting the first set of primitives from a plurality of primitives of the graphics image stored in a main memory; and
sorting the first set of primitives into groups based on relative spatial locality between the primitives.

16. The non-transitory machine-readable medium of claim 13 , wherein the operations further comprise:
selecting a subset of the next-level nodes to be stored to the memory array for further evaluation.

17. The non-transitory machine-readable medium of claim 13 , wherein the hierarchical acceleration structure comprises a bounding volume hierarchy (BVH).

18. The non-transitory machine-readable medium of claim 13 , wherein the memory array comprises a high-bandwidth SRAM array.

Assignees

• Intel Corp

Inventors

• Doyle Michael
• Schluessler Travis
• Liktor Gabor
• Kuwahara Atsuo
• Amstutz Jefferson

Classifications

• G06T1/20 Primary

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06F9/3877

  using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12) · CPC title

• G06F9/3891

  organised in groups of units sharing resources, e.g. clusters · CPC title

• G06F9/5077

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• G06F16/9027

  Trees · CPC title