# US 2024/0202178 A1 · 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 2024/0202178 A1
- Document ID: US20240202178A1
- Status: Published application
- Kind: A1
- Application number: 18/068,442
- Filed: 2022-12-19
- Published: 2024-06-20
- 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/US20240202178A1

## 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:
a processing unit comprising circuitry configured to:
select an input node of a plurality of nodes of a first hierarchical tree structure that represents a surface area;
identify a first new position for the input node, based at least in part on a change in the surface area that would result from moving the input node from an initial position to the first new position;
generate a perturbation to identify a second new position for the input node;
move the input node from the initial position to a second new position, to generate a second hierarchical tree structure; and
perform a ray tracing operation using the second hierarchical tree structure.

### Claim 2 (depends on 1)

The system as claimed in claim 1, wherein to generate the perturbation, the processing unit is configured to determine moving the input node from the initial position to the second new position would increase the surface area.

### Claim 3 (depends on 2)

The system as claimed in claim 2, wherein the processing unit is further configured to lock the input node, an output node at the second new position, and one or more intermediate nodes on a path between the input node and the output node, prior to moving the input node from the initial position to the second new position.

### Claim 4 (depends on 2)

The system as claimed in claim 2, wherein the processing unit is further configured to accept the second new position based in part on a computed probability distribution.

### Claim 5 (depends on 1)

The system as claimed in claim 1, wherein the processing unit is further configured to skip traversal to one or more branches of the first hierarchical tree when identifying the first new position, in response to a determination that pruning is to be applied to the traversal of the hierarchical tree.

### Claim 6 (depends on 1)

The system as claimed in claim 1, wherein the processing unit is configured to search for new positions for two or more nodes of the plurality of nodes in parallel.

### Claim 7 (depends on 1)

The system as claimed in claim 1, wherein the processing unit is configured to select a third new position for the input node, based at least in part on a decrease in surface area of one or more nodes located on a traversal path between the initial position and the third new position.

### Claim 8 (depends on 1)

The system as claimed in claim 1, wherein the processing unit is configured to select a third new position for the input node, based at least in part on a increase in surface area of one or more nodes located on a traversal path between the initial position and the third new position.

### Claim 9

A method comprising:
selecting an input node of a plurality of nodes of a first hierarchical tree structure representing a surface area;
identifying a first new position for the input node, based at least in part on a change in surface area that would result from moving the input node from an initial position to the first new position;
generating a perturbation, to identify a second new position for the input node;
moving the input node from the initial position to a second new position, to generate a second hierarchical tree structure; and
performing a ray tracing operation using the second hierarchical tree structure.

### Claim 10 (depends on 9)

The method as claimed in claim 9, further comprising determining moving the input node from the initial position to the second new position would increase the surface area.

### Claim 11 (depends on 10)

The method as claimed in claim 10, further comprising locking the input node, an output node at the second new position, and one or more intermediate nodes located on a traversal path between the input node and the output node, prior to moving the input node from the initial position to the second new position.

### Claim 12 (depends on 10)

The method as claimed in claim 10, further comprising skipping traversal of one or more branches of the first hierarchical tree, responsive to determining a parent node of the one or more branches does not intersect a ray.

### Claim 13 (depends on 9)

The method as claimed in claim 9, further comprising:
determining whether pruning is applied to traversal of the hierarchical tree; and
responsive to determining that pruning is applied to the traversal of the hierarchical tree, skip traversal to one or more branches of the tree when identifying the first new position and/or the second new position.

### Claim 14 (depends on 9)

The method as claimed in claim 9, further comprising searching new positions for two or more nodes of the plurality of nodes in parallel.

### Claim 15 (depends on 9)

The method as claimed in claim 9, further comprising selecting a third new position for moving the input node, based at least in part on a decrease in surface area of one or more nodes located on a traversal path between the initial position and the third new position.

### Claim 16 (depends on 9)

The method as claimed in claim 9, wherein during the perturbation, the method further comprising:
determining if a third new position is identified for the input node; and
responsive to determining that the third new position is identified for the input node, selecting the third new position for moving the input node, based at least in part on determination of an increase in surface area of one or more nodes located on a traversal path between the initial position and the third new position.

### Claim 17

A computing system comprising:
a central processing unit;
a memory controller; and
a command processor configured to:
select an input node of a plurality of nodes of a first hierarchical tree structure representing a surface area;
identify a first new position for the input node, based at least in part on a change in surface area that would result from moving the input node from an initial position to the first new position;
generate a perturbation, to identify a second new position for the input node;
move the input node from the initial position to a second new position, to generate a second hierarchical tree structure; and
perform a ray tracing operation using the second hierarchical tree structure.

### Claim 18 (depends on 17)

The system as claimed in claim 17, wherein during the perturbation, the command processor is configured to:
determine whether moving the first node from the initial position to the second new position would result in a reduction in the surface area represented by the hierarchical tree;
responsive to determining that moving the input node would not result in the reduction in the surface area, compute a value of a probability distribution given as a function of a difference in the surface area when the input node is placed at the initial position and the surface area when the input node is placed in the second new position; and
move the input node from the initial position to a second new position, to generate a second hierarchical tree structure, based at least in part on the value of the probability distribution.

### Claim 19 (depends on 18)

The system as claimed in claim 18, wherein the command processor is configured to:
determine if a third new position is identified for the input node; and
responsive to a determination that the third new position is identified for the input node, select the third new position for moving the input node, based at least in part on determination of a decrease in surface area of one or more nodes located on a traversal path between the initial position and the third new position.

### Claim 20 (depends on 18)

The system as claimed in claim 18, wherein during the perturbation, the command processor is configured to:
determine if a third new position is identified for the input node; and
responsive to a determination that the third new position is identified for the input node, select the third new position for moving the input node, based at least in part on determination of an increase in surface area of one or more nodes located on a traversal path between the initial position and the third new position.
