# US 2017/0287100 A1 · Reduction of BVH-Node Bandwidth with Incremental Traversal

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

- Number: US 2017/0287100 A1
- Document ID: US20170287100A1
- Status: Published application
- Kind: A1
- Application number: 15/157,667
- Filed: 2016-05-18
- Published: 2017-10-05
- Earliest claimed: 2016-04-04
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Gabor Liktor; Karthik Vaidyanathan
- Web page: https://patentgrep.com/patent/US20170287100A1

## CPC

- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06F 12/0871: Allocation or management of cache space
- G06T 15/06: Ray-tracing
- G06T 17/005: {Tree description, e.g. octree, quadtree}
- G06F 2212/1016: Performance improvement
- G06F 2212/302: In image processor or graphics adapter
- G06F 2212/401: Compressed data
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Incremental encoding of Bounding Volume Hierarchies (BVH) enables coarse quantization of bounding volumes, significantly reducing their memory footprint. However, reducing the size of the BVH alone does not yield a comparable reduction in memory bandwidth in some embodiments. While the bounding volumes of the BVH nodes can be aggressively quantized, the size of the child node pointers remains a significant overhead. A two-level clustering method introduces a memory layout and node addressing scheme, which allows the reordering of BVH nodes to reduce their memory footprint in hardware ray tracing systems using reduced precision ray traversal.

## Claims

### Claim 1

A method comprising:
implementing reduced precision ray traversal for a bounding volume-node hierarchy in a graphics processor;
using address clustering as one clustering level; and
using cache clustering as another clustering level.

### Claim 2 (depends on 1)

The method of claim 1 including generating low resolution child pointers between clustered nodes.

### Claim 3 (depends on 1)

The method of claim 1 including connecting two clusters using a glue node between the two clusters.

### Claim 4 (depends on 3)

The method of claim 3 including performing cache aware node reordering within each cluster.

### Claim 5 (depends on 3)

The method of claim 3 including only loading glue nodes when crossing a border between clusters.

### Claim 6 (depends on 1)

The method of claim 1 including merging child nodes in a cluster until the cluster is full.

### Claim 7 (depends on 1)

The method of claim 1 including moving full clusters that match a cache line size to the beginning of an address cluster.

### Claim 8 (depends on 1)

The method of claim 1 including storing cache clusters in a multi-level ordered depth-first layout.

### Claim 9 (depends on 1)

The method of claim 1 including padding cache lines.

### Claim 10 (depends on 1)

The method of claim 1 including processing nodes using a traversal unit that traverses one ray per thread and storing a traversal state for the ray.
A method comprising:

### Claim 11

One or more non-transitory computer readable media storing instructions to perform a sequence comprising:
implementing reduced precision ray traversal for a bounding volume-node hierarchy in a graphics processor;
using address clustering as one clustering level; and
using cache clustering as another clustering level.

### Claim 12 (depends on 11)

The media of claim 11, further storing instructions to perform a sequence including generating low resolution child pointers between clustered nodes.

### Claim 13 (depends on 11)

The media of claim 11, further storing instructions to perform a sequence including connecting two clusters using a glue node between the two clusters.

### Claim 14 (depends on 13)

The media of claim 13, further storing instructions to perform a sequence including performing cache aware node reordering within each cluster.

### Claim 15 (depends on 13)

The media of claim 13, further storing instructions to perform a sequence including only loading glue nodes when crossing a border between clusters.

### Claim 16 (depends on 11)

The media of claim 11, further storing instructions to perform a sequence including merging child nodes in a cluster until the cluster is full.

### Claim 17 (depends on 11)

The media of claim 11, further storing instructions to perform a sequence including moving full clusters that match a cache line size to the beginning of an address cluster.

### Claim 18 (depends on 11)

The media of claim 11, further storing instructions to perform a sequence including storing cache clusters in a multi-level ordered depth-first layout.

### Claim 19 (depends on 11)

The media of claim 11, further storing instructions to perform a sequence including padding cache lines.

### Claim 20 (depends on 11)

The media of claim 11, further storing instructions to perform a sequence including processing nodes using a traversal unit that traverses one ray per thread and storing a traversal state for the ray.

### Claim 21

An apparatus comprising:
a processor to implement reduced precision ray traversal for a bounding volume-node hierarchy, use address clustering as one clustering level, use cache clustering as another clustering level; and
a memory coupled to said processor.

### Claim 22 (depends on 21)

The apparatus of claim 21, said processor to generate low resolution child pointers between clustered nodes.

### Claim 23 (depends on 21)

The apparatus of claim 21, said processor to connect two clusters using a glue node between the two clusters.

### Claim 24 (depends on 23)

The apparatus of claim 23, said processor to perform cache aware node reordering within each cluster.

### Claim 25 (depends on 23)

The apparatus of claim 23, said processor to only load glue nodes when crossing a border between clusters.

### Claim 26 (depends on 21)

The apparatus of claim 21, said processor to merge child nodes in a cluster until the cluster is full.

### Claim 27 (depends on 21)

The apparatus of claim 21, said processor to move full clusters that match a cache line size to the beginning of an address cluster.

### Claim 28 (depends on 21)

The apparatus of claim 21, said processor to store cache clusters in a multi-level ordered depth-first layout.

### Claim 29 (depends on 21)

The apparatus of claim 21, said processor to pad cache lines.

### Claim 30 (depends on 21)

The apparatus of claim 21, said processor to process nodes using a traversal unit that traverses one ray per thread and storing a traversal state for the ray.