# US 12,762,104 B2 · Simulated annealing for parallel insertion-based BVH optimization > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,762,104 B2 - Document ID: US12762104B2 - Status: Granted - Kind: B2 - Application number: 18/068,442 - Filed: 2022-12-19 - Published: 2024-06-20 - Granted: 2026-10-13 - Earliest claimed: 2022-12-19 - Assignees: Advanced Micro Devices, Inc. - Applicants: Advanced Micro Devices, Inc. - Inventors: Daniel Meister; Jirí Bittner - Web page: https://patentgrep.com/patent/US12762104B2 ## CPC - G06F 16/2246: {Trees, e.g. B+trees} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems, apparatuses, and methods for optimizing a bounding volume hierarchy (BVH) are disclosed. A system selects a first node having an initial position in the BVH structure. The system determines a new position for the first node in the BVH structure and restructures the BVH structure by removal of the first node from the initial position and insertion of the first node in the new position to replace a second node. The restructured BVH is optimized using perturbation to achieve global surface area reduction. ## Claims ### Claim 1 A system comprising: processing circuitry configured to: access data corresponding to a bounding volume hierarchy (BVH) comprising a plurality of nodes representing bounding volumes for scene primitives, the BVH having a first surface area comprising a cumulative surface area of bounding volumes represented by internal nodes; generate a probability value, based at least in part on a difference between the first surface area and a second surface area that would result from repositioning a first node from a first location to a second location; modify the data by repositioning the first node from a first location to a second location, based on a comparison between the probability value and at least in part on a randomly generated value, wherein repositioning comprises removing the first node from the first location in the BVH and inserting the first node at the second location in the BVH, and wherein the repositioning results in the second surface area being greater than the first surface area; and perform a ray tracing operation using the BVH by traversing the BVH to test ray intersections with the scene primitives. ### Claim 2 (depends on 1) The system as claimed in claim 1, wherein the processing circuitry is configured to modify the data responsive to a calculated probability being greater than the randomly generated value. ### Claim 3 (depends on 2) The system as claimed in claim 2, wherein the calculated probability decreases as the difference between the first surface area and the second surface area increases. ### Claim 4 (depends on 1) The system as claimed in claim 1, wherein a decision as to whether to reposition the first node is influenced by a perturbation derived from a randomly generated value. ### Claim 5 (depends on 4) The system as claimed in claim 4, wherein the processing circuitry is further configured to: iteratively process a plurality of locations within the BVH to select the second location; generate, during each iteration, the randomly generated value; and reject a given location of the plurality of locations as a candidate location for repositioning the first node, responsive to the randomly generated value being lower than a threshold. ### Claim 6 (depends on 5) The system as claimed in claim 5, wherein the processing circuitry is configured to generate the value as a clamped sine function. ### Claim 7 (depends on 1) The system as claimed in claim 1, wherein the processing circuitry is configured to: calculate a third surface area corresponding to repositioning the first node to a third location, wherein the third surface area is less than the first surface area; generate a probability value based at least in part on a difference between the first surface area and the third surface area; and modify the data to reposition the first node to the third location, responsive to the probability value exceeding a randomly generated value. ### Claim 8 (depends on 1) The system as claimed in claim 1, wherein, based on a comparison between a calculated probability value and a randomly generated value, processing circuitry selectively performs the repositioning of the first node for a move resulting in either: a second surface area greater than the first surface area; or a second surface area less than the first surface area. ### Claim 9 A method comprising: accessing, by processing circuitry, data corresponding to a bounding volume hierarchy (BVH) comprising a plurality of nodes representing bounding volumes for scene primitives, the BVH having a first surface area comprising a cumulative surface area of bounding volumes represented by internal nodes; generating, by the processing circuitry, a probability value, based at least in part on a difference between the first surface area and a second surface area that would result from repositioning a first node from a first location to a second location; modifying, by the processing circuitry, the data by repositioning the first node from a first location to a second location, based on a comparison between the probability value and a randomly generated value, wherein repositioning comprises removing the first node from the first location in the BVH and inserting the first node at the second location in the BVH, and wherein the repositioning results in the second surface area being greater than the first surface area; and performing, by the processing circuitry, a ray tracing operation using the BVH by traversing the BVH to test ray intersections with the scene primitives. ### Claim 10 (depends on 9) The method as claimed in claim 9, further comprising modifying, by the processing circuitry, the data, responsive to a calculated probability being greater than the randomly generated value. ### Claim 11 (depends on 10) The method as claimed in claim 10, wherein the calculated probability decreases as the difference between the first surface area and the second surface area increases. ### Claim 12 (depends on 9) The method as claimed in claim 9, wherein a decision as to whether to reposition the first node is influenced by a perturbation derived from a randomly generated value. ### Claim 13 (depends on 12) The method as claimed in claim 12, further comprising: iteratively processing a plurality of locations within the BVH to select the second location; generating, by the processing circuitry during each iteration, the randomly generated value; and rejecting, by the processing circuitry, a given location of the plurality of locations as a candidate location for repositioning the first node, responsive to the randomly generated value being lower than a threshold. ### Claim 14 (depends on 13) The method as claimed in claim 13, further comprising generating, by the processing circuitry, the value as a clamped sine function. ### Claim 15 (depends on 9) The method as claimed in claim 9, further comprising: calculating a third surface area corresponding to repositioning the first node to a third location, wherein the third surface area is less than the first surface area; generating a probability value based at least in part on a difference between the first surface area and the third surface area; and modifying the data to reposition the first node to the third location, responsive to the probability value exceeding a randomly generated value. ### Claim 16 (depends on 9) The method as claimed in claim 9, wherein the repositioning of the first node may be performed for a move resulting in a higher or lower surface area, based on a calculated probability exceeding a random threshold. ### Claim 17 A computing system comprising: a central processing unit; a memory controller; and a command processor configured to: access data corresponding to a bounding volume hierarchy (BVH) comprising a plurality of nodes representing bounding volumes for scene primitives, the BVH having a first surface area comprising a cumulative surface area of bounding volumes represented by internal nodes; generate a probability value, based at least in part on a difference between the first surface area and a second surface area that would result from repositioning a first node from a first location to a second location; modify the data by repositioning the first node from a first location to a second location, based on a comparison between the probability value and a randomly generated value, wherein repositioning comprises removing the first node from the first location in the BVH and inserting the first node at the second location in the BVH, and wherein the repositioning results in the second surface area being greater than the first surface area; and perform a ray tracing operation using the BVH by traversing the BVH to test ray intersections with the scene primitives. ### Claim 18 (depends on 17) The system as claimed in claim 17, wherein the probability value is calculated based at least in part on a magnitude and a direction of the difference between the first surface area and the second surface area. ### Claim 19 (depends on 18) The system as claimed in claim 18, wherein the probability value that is calculated decreases as the difference between the first surface area and the second surface area increases. ### Claim 20 (depends on 17) The system as claimed in claim 17, wherein the repositioning of the first node may be performed for a move resulting in a higher or lower surface area, based on a calculated probability exceeding a random threshold.