# US 12,182,900 B2 · Unified architecture for BVH construction based on hardware pre-sorting and a parallel, reconfigurable clustering array > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,182,900 B2 - Document ID: US12182900B2 - Status: Granted - Kind: B2 - Application number: 18/231,379 - Filed: 2023-08-08 - Published: 2024-02-08 - Granted: 2024-12-31 - Earliest claimed: 2018-12-28 - Assignees: Intel Corporation - Applicants: Intel Corporation - Inventors: Michael Doyle; Travis Schluessler; Gabor Liktor; Atsuo Kuwahara; Jefferson Amstutz - Web page: https://patentgrep.com/patent/US12182900B2 ## CPC - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06F 9/3877: {using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12)} - G06F 9/3891: {organised in groups of units sharing resources, e.g. clusters} - G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)} - G06F 16/9027: {Trees} - G06T 15/005: {General purpose rendering architectures} - G06T 15/06: Ray-tracing - G06T 15/10: Geometric effects - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 An apparatus comprising: a memory array to store data for a first set of primitives of a graphic image, the first set of primitives forming first level nodes of a hierarchical acceleration structure; and circuitry to construct the hierarchical acceleration structure based on the data for the first set of primitives stored in the memory array, the construction of the hierarchical acceleration structure comprising: evaluating 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 based on a 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 of the plurality of potential next-level groupings. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the hierarchical acceleration structure is a hierarchical ray tracing acceleration structure. ### Claim 3 (depends on 1) The apparatus of claim 1, wherein the programmable cost or distance function comprising one of a surface area heuristic function and a Euclidean distance function, and wherein the surface area heuristic 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. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein the circuitry to construct the hierarchical acceleration structure further comprises a plurality of processing clusters, wherein the evaluation of the plurality of potential next-level groupings of the first level nodes is performed in parallel by the plurality of processing clusters. ### Claim 5 (depends on 4) The apparatus of claim 4, wherein the circuitry to construct the hierarchical acceleration structure further comprises a plurality of fetch units, each fetch unit corresponding to one of the plurality of processing clusters to fetch or more of the first level nodes to be processed by a corresponding processing cluster of the plurality of processing clusters. ### Claim 6 (depends on 4) The apparatus of claim 4, wherein each processing cluster of the plurality of processing clusters comprises one or more reconfigurable cells, each reconfigurable cell including a plurality of reconfigurable functional units and a reconfigurable communication fabric interconnecting the plurality of reconfigurable functional units. ### Claim 7 (depends on 6) The apparatus of claim 6, wherein each reconfigurable cell comprises: a scratchpad memory to store data related to the first level nodes and/or next-level nodes; and an arithmetic logic unit (ALU) coupled to the scratchpad memory over the reconfigurable communication fabric. ### Claim 8 (depends on 1) The apparatus of claim 1, wherein sorting the first set of primitives into groups of the first level nodes comprises splitting the primitives based on spatial locality in the graphic image. ### Claim 9 (depends on 1) The apparatus of claim 1, wherein the hierarchical acceleration structure comprises a bounding volume hierarchy. ### Claim 10 A method comprising: storing data in a memory array for a first set of primitives of a graphic image, the first set of primitives forming first level node of a hierarchical acceleration structure; and constructing the hierarchical acceleration structure based on the data for the first set of primitives stored in the memory array, the construction of the hierarchical acceleration structure comprising: evaluating 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 based on a 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 of the plurality of potential next-level groupings. ### Claim 11 (depends on 10) The method of claim 10, wherein the hierarchical acceleration structure is a hierarchical ray tracing acceleration structure. ### Claim 12 (depends on 10) The method of claim 10, wherein the programmable cost or distance function comprising one of a surface area heuristic function and a Euclidean distance function, and wherein the surface area heuristic 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. ### Claim 13 (depends on 10) The method of claim 10, wherein the construction of the hierarchical acceleration structure is performed by a plurality of processing clusters, wherein the evaluation of the plurality of potential next-level groupings of the first level nodes is performed in parallel by the plurality of processing clusters. ### Claim 14 (depends on 13) The method of claim 13, wherein each processing cluster of the plurality of processing clusters comprises one or more reconfigurable cells, each reconfigurable cell including a plurality of reconfigurable functional units and a reconfigurable communication fabric interconnecting the plurality of reconfigurable functional units. ### Claim 15 (depends on 10) The method of claim 10, wherein sorting the first set of primitives into groups of the first level nodes comprises splitting the primitives based on spatial locality in the graphic image. ### Claim 16 A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform operations of: storing data in a memory array for a first set of primitives of a graphic image, the first set of primitives forming first level nodes of a hierarchical acceleration structure; and constructing the hierarchical acceleration structure based on the data for the first set of primitives stored in the memory array, the construction of the hierarchical acceleration structure comprising: evaluating 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 based on a 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 of the plurality of potential next-level groupings. ### Claim 17 (depends on 16) The non-transitory machine-readable medium of claim 16, wherein the programmable cost or distance function comprising one of a surface area heuristic function and a Euclidean distance function, and wherein the surface area heuristic 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. ### Claim 18 (depends on 16) The non-transitory machine-readable medium of claim 16, wherein the construction of the hierarchical acceleration structure is performed by a plurality of processing clusters, wherein the evaluation of the plurality of potential next-level groupings of the first level nodes is performed in parallel by the plurality of processing clusters. ### Claim 19 (depends on 18) The non-transitory machine-readable medium of claim 18, wherein each processing cluster of the plurality of processing clusters comprises one or more reconfigurable cells, each reconfigurable cell including a plurality of reconfigurable functional units and a reconfigurable communication fabric interconnecting the plurality of reconfigurable functional units. ### Claim 20 (depends on 16) The non-transitory machine-readable medium of claim 16, wherein sorting the first set of primitives into groups of the first level nodes comprises splitting the primitives based on spatial locality in the graphic image.