# US 12,217,350 B2 · Node encoding for spatially-organized ray tracing acceleration data structure

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

- Number: US 12,217,350 B2
- Document ID: US12217350B2
- Status: Granted
- Kind: B2
- Application number: 17/817,742
- Filed: 2022-08-05
- Published: 2022-11-24
- Granted: 2025-02-04
- Earliest claimed: 2020-07-30
- Assignees: Apple Inc.
- Applicants: Apple Inc.
- Inventors: Ali Rabbani Rankouhi; Christopher A. Burns; Justin A. Hensley; Luca Iuliano; Jonathan M. Redshaw
- Web page: https://patentgrep.com/patent/US12217350B2

## CPC

- G06T 15/06: Ray-tracing
- G06F 9/3887: {controlled by a single instruction for multiple data lanes [SIMD]}
- G06F 9/3888: {controlled by a single instruction for multiple threads [SIMT] in parallel}
- G06F 9/38885: {Divergence aspects}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5016: {the resource being the memory}
- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 30/31: Design entry, e.g. editors specifically adapted for circuit design
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06T 1/60: Memory management
- G06T 15/005: {General purpose rendering architectures}
- G06T 17/005: {Tree description, e.g. octree, quadtree}
- G06Q 10/101: Collaborative creation, e.g. joint development of products or services
- G06Q 50/04: Manufacturing
- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
- G06T 2210/12: Bounding box
- G06T 2210/21: Collision detection, intersection
- G16H 40/67: for remote operation
- Y02P 90/30: Computing systems specially adapted for manufacturing
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G16H: HEALTHCARE INFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR THE HANDLING OR PROCESSING OF MEDICAL OR HEALTHCARE DATA
- Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS

## Abstract

Disclosed techniques relate to acceleration data structure for ray intersection testing. In some embodiments, storage circuitry stores node data for a spatially organized acceleration data structure, including to store the following node information for a given node: origin coordinates for the node and, for a given child node of multiple child nodes, child information that includes: quantized bounding region information for a bounding region corresponding to the child node, where the quantized bounding region information encodes bounding region coordinates as offsets relative to the origin coordinates. Traversal circuitry may traverse multiple nodes of the data structure and determine whether a ray intersects a bounding region indicated by given a node of the data structure based on the node information. Disclosed techniques may provide substantial improvements to performance, data size, and power consumption.

## Claims

### Claim 1

An apparatus, comprising:
storage circuitry configured to store node data for a spatially organized acceleration data structure, including to store the following node information in a node data structure for a parent node:
origin coordinates for the node; and
child base address information that indicates a base address of a memory region within which data is stored for multiple child nodes of the parent node;
for a given child node of the multiple child nodes, child information that includes:
a field that indicates whether the child node is an interior node or a leaf node;
for an internal child node, quantized bounding region information for a bounding region corresponding to the child node, wherein the quantized bounding region information encodes bounding region coordinates as offsets relative to the origin coordinates;
for a leaf child node:
a field that indicates a size of data for the leaf child node, wherein the spatially organized acceleration data structure supports leaf nodes of different sizes and the parent node includes multiple leaf child nodes having different sizes; and
a field that indicates an offset, within the memory region, at which the data for the leaf node is located, relative to the child base address;
traversal circuitry that includes bounding region tester circuitry, wherein the traversal circuitry is configured to:
traverse multiple nodes of the data structure; and
test, using the bounding region tester circuitry during the traversal, whether a ray intersects a bounding region indicated by a node of the data structure, wherein the testing is based on the node information for the node and ray information for the ray.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein:
the bounding regions corresponding to the child nodes are box-shaped bounding regions;
the quantized bounding region information indicates two opposite corners of a given box-shaped bounding region; and
the quantized bounding region information is quantized using rounding out for the two opposite corners.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the node information further includes:
a scale factor for the node, wherein the bounding regions are defined by the bounding region coordinates for a given child node and the scale factor.

### Claim 4 (depends on 3)

The apparatus of claim 3, wherein the origin coordinates and scale factor are encoded as floating-point values and the bounding region coordinates are encoded as fixed-point values.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the child information includes a status field that indicates whether a given child node is an interior node or a leaf node.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein the node information includes a field that indicates whether to perform a transform on ray coordinates when traversing to child nodes of the node.

### Claim 7 (depends on 1)

The apparatus of claim 1, wherein the bounding region tester circuitry includes multiple bounding region tester circuits configured to test, at least partially in parallel during the traversal, whether multiple rays intersect multiple different bounding regions associated with a node of the data structure.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein the bounding region tester circuitry includes:
first circuitry configured to separately perform operations for different bounding regions; and
common node calculation circuitry configured to perform operations shared by the multiple different bounding regions.

### Claim 9 (depends on 8)

The apparatus of claim 8, wherein the common node calculation circuitry is configured to:
determine bounds represented by the quantized bounding region information;
generate a reciprocal of a given ray; and
order intersection results.

### Claim 10 (depends on 8)

The apparatus of claim 8, wherein the common node calculation circuitry is configured to operate on inputs represented using a greater precision than the first circuitry.

### Claim 11

A method, comprising:
storing, by a computing system, node data for a spatially organized acceleration data structure, including the following node information in a node data structure for a parent node:
origin coordinates for the node; and
child base address information that indicates a base address of a memory region within which data is stored for multiple child nodes of the parent node;
for a given child node of the multiple child nodes, child information that includes:
a field that indicates whether the child node is an interior node or a leaf node;
for an internal child node, quantized bounding region information for a bounding region corresponding to the child node, wherein the quantized bounding region information encodes bounding region coordinates as offsets relative to the origin coordinates;
for a leaf child node:
a field that indicates a size of data for the leaf child node, wherein the spatially organized acceleration data structure supports leaf nodes of different sizes and the parent node includes multiple leaf child nodes having different sizes; and
a field that indicates an offset, within the memory region, at which the data for the leaf node is located, relative to the child base address;
traversing, by the computing system, multiple nodes of the data structure; and
testing, by the computing system during the traversal, whether a ray intersects a bounding region indicated by a node of the data structure, wherein the testing is based on the node information for the node and ray information for the ray.

### Claim 12 (depends on 11)

The method of claim 11,
wherein the node information further includes a scale factor for the node, wherein the bounding regions are defined by the bounding region coordinates for a given child node and the scale factor; and
wherein the origin coordinates and scale factor are encoded as floating-point values and the quantized bounding region coordinates are encoded as fixed-point values.

### Claim 13

A non-transitory computer-readable medium having instructions stored thereon that are executable by a computing device to perform operations comprising:
generating a spatially organized acceleration data structure, that stores the following node information in a node data structure for a parent node:
origin coordinates for the node; and
child base address information that indicates a base address of a memory region within which data is stored for multiple child nodes of the parent node;
for a given child node of the multiple child nodes, child information that includes:
a field that indicates whether the child node is an interior node or a leaf node;
for an internal child node, quantized bounding region information for a bounding region corresponding to the child node, wherein the quantized bounding region information encodes bounding region coordinates as offsets relative to the origin coordinates; and
for a leaf child node:
a field that indicates a size of data for the leaf child node, wherein the spatially organized acceleration data structure supports leaf nodes of different sizes and the parent node includes multiple leaf child nodes having different sizes; and
a field that indicates an offset, within the memory region, at which the data for the leaf node is located, relative to the child base address.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein:
the bounding regions corresponding to the child nodes are box-shaped bounding regions;
the quantized bounding region information indicates two opposite corners of a given box-shaped bounding region; and
the quantized bounding region information is quantized using rounding out for the two opposite corners.

### Claim 15 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein the node information further includes:
a scale factor for the node, wherein the bounding regions are defined by the bounding region coordinates for a given child node and the scale factor.