# US 2020/0402291 A1 · Early termination in bottom-up acceleration data structure refit

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0402291 A1
- Document ID: US20200402291A1
- Status: Published application
- Kind: A1
- Application number: 16/915,599
- Filed: 2020-06-29
- Published: 2020-12-24
- Earliest claimed: 2018-12-28
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: KAI XIAO; MICHAEL APODACA; CARSON BROWNLEE; THOMAS RAOUX; JOSHUA BARCZAK; GABOR LIKTOR
- Web page: https://patentgrep.com/patent/US20200402291A1

## CPC

- G06T 15/06: Ray-tracing
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06T 2200/04: involving 3D image data
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Apparatus and method for bottom-up BVH refit. For example, one embodiment of an apparatus comprises: a hierarchical acceleration data structure generator to construct an acceleration data structure comprising a plurality of hierarchically arranged nodes; traversal hardware logic to traverse one or more rays through the acceleration data structure; intersection hardware logic to determine intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; a node unit comprising circuitry and/or logic to perform refit operations on nodes of the hierarchical acceleration data structure, the refit operations to adjust spatial dimensions of one or more of the nodes; and an early termination evaluator to determine whether to proceed with refit operations or to terminate refit operations for a current node based on refit data associated with one or more child nodes of the current node.

## Claims

### Claim 1

An apparatus comprising:
a hierarchical acceleration data structure generator to construct an acceleration data structure comprising a plurality of hierarchically arranged nodes;
traversal hardware logic to traverse one or more rays through the hierarchical acceleration data structure;
intersection hardware logic to determine intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; and
a node refit unit comprising circuitry and/or logic to perform refit operations on nodes of the hierarchical acceleration data structure to adjust spatial dimensions of one or more of the nodes,
wherein the node refit unit is to conditionally refit a current node based on refit data associated with one or more child nodes of the current node.

### Claim 2 (depends on 1)

The apparatus of claim 1 wherein if the current node needs to be enlarged, the node refit unit is to refit the current node.

### Claim 3 (depends on 2)

The apparatus of claim 2 wherein if the current node needs to be reduced, the node refit unit is to refit the current node if the refit is justified based on benefits and/or costs associated therewith.

### Claim 4 (depends on 2)

The apparatus of claim 2 wherein if the current node needs to be reduced, the node refit unit is to refit the current node if the refit is justified based on one or more threshold values being reached.

### Claim 5 (depends on 4)

The apparatus of claim 4 wherein one of the thresholds comprises a ratio of volume occupancy of the one or more child nodes over the volume of the current node.

### Claim 6 (depends on 4)

The apparatus of claim 4 wherein one of the thresholds comprises degraded performance over a threshold period of time or number of processing cycles.

### Claim 7 (depends on 1)

The apparatus of claim 1 wherein the node refit unit is to perform a first sequence of operations to iterate over all leaf nodes which point to leaf data, the node refit unit to update bounding volumes associated with one or more of the leaf nodes.

### Claim 8 (depends on 1)

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

### Claim 9 (depends on 1)

The apparatus of claim 1 wherein refit operations include adjusting dimensions of the current node based on changes to dimensions or locations of the one or more child nodes.

### Claim 10

A method comprising:
constructing a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes;
traversing one or more rays through the hierarchical acceleration data structure;
determining intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure;
performing refit operations on nodes of the hierarchical acceleration data structure to adjust spatial dimensions of one or more of the nodes; and
conditionally refitting a current node based on refit data associated with one or more child nodes of the current node.

### Claim 11 (depends on 10)

The method of claim 10 wherein conditionally refitting the current node comprises refitting the current node if the current node needs to be enlarged.

### Claim 12 (depends on 11)

The method of claim 11 wherein conditionally refitting the current node further comprises refitting the current node if the current node needs to be reduced and the refit is justified based on benefits and/or costs associated therewith.

### Claim 13 (depends on 11)

The method of claim 11 wherein conditionally refitting the current node further comprises refitting the current node if the current node needs to be reduced and the refit is justified based on one or more threshold values being reached.

### Claim 14 (depends on 13)

The method of claim 13 wherein one of the thresholds comprises a ratio of volume occupancy of the one or more child nodes over the volume of the current node.

### Claim 15 (depends on 13)

The method of claim 13 wherein one of the thresholds comprises degraded performance over a threshold period of time or number of processing cycles.

### Claim 16 (depends on 11)

The method of claim 11 further comprises performing a first sequence of operations to iterate over all leaf nodes which point to leaf data and updating bounding volumes associated with one or more of the leaf nodes.

### Claim 17 (depends on 11)

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

### Claim 18 (depends on 11)

The method of claim 11 further comprise adjusting dimensions of the current node based on changes to dimensions or locations of the one or more child nodes.

### Claim 19

A machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:
constructing a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes;
traversing one or more rays through the hierarchical acceleration data structure;
determining intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure;
performing refit operations on nodes of the hierarchical acceleration data structure to adjust spatial dimensions of one or more of the nodes; and
conditionally refitting a current node based on refit data associated with one or more child nodes of the current node.

### Claim 20 (depends on 19)

The machine-readable medium of claim 19 wherein conditionally refitting the current node comprises refitting the current node if the current node needs to be enlarged.

### Claim 21 (depends on 20)

The machine-readable medium of claim 20 wherein conditionally refitting the current node further comprises refitting the current node if the current node needs to be reduced and the refit is justified based on benefits and/or costs associated therewith.

### Claim 22 (depends on 20)

The machine-readable medium of claim 20 wherein conditionally refitting the current node further comprises refitting the current node if the current node needs to be reduced and the refit is justified based on one or more threshold values being reached.

### Claim 23 (depends on 22)

The machine-readable medium of claim 22 wherein one of the thresholds comprises a ratio of volume occupancy of the one or more child nodes over the volume of the current node.

### Claim 24 (depends on 22)

The machine-readable medium of claim 22 wherein one of the thresholds comprises degraded performance over a threshold period of time or number of processing cycles.

### Claim 25 (depends on 20)

The machine-readable medium of claim 20 wherein the operations further comprise performing a first sequence of operations to iterate over all leaf nodes which point to leaf data and updating bounding volumes associated with one or more of the leaf nodes.

### Claim 26 (depends on 20)

The machine-readable medium of claim 20 wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy (BVH).

### Claim 27 (depends on 20)

The machine-readable medium of claim 20 wherein the operations further comprise adjusting dimensions of the current node based on changes to dimensions or locations of the one or more child nodes.
