Back to results
US 12,762,104 B2Granted
Simulated annealing for parallel insertion-based BVH optimization
AssigneeAdvanced Micro Devices, Inc.
InventorsDaniel Meister, Jirí Bittner
Life of this patent
Estimating the term…
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.
Claims20
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.
3 more elements
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.
2 more elements
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.
6 more elements
Dependencies are inferred from the claim text.