# US 2022/0036637 A1 · Grouping Techniques for Ray Intersection Traversal

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

- Number: US 2022/0036637 A1
- Document ID: US20220036637A1
- Status: Published application
- Kind: A1
- Application number: 17/103,317
- Filed: 2020-11-24
- Published: 2022-02-03
- 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/US20220036637A1

## 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 grouping rays during traversal of a spatially-organized acceleration data structure (e.g., a bounding volume hierarchy) for ray intersection processing. The grouping may provide temporal locality for accesses to bounding region data. In some embodiments, ray intersect circuitry is configured to group rays based on the node of the data structure that they target next. The ray intersect circuitry may select one or more groups of rays for issuance each clock cycle, e.g., to bounding region test circuitry.

## Claims

### Claim 1

An apparatus, comprising:
ray intersect circuitry, configured to:
receive one or more ray intersect requests that indicate origin and direction information for multiple rays in a set of rays in a graphics scene;
traverse multiple nodes a spatially-organized acceleration data structure whose nodes indicate coordinates corresponding to bounding regions of the graphics scene, to determine whether rays intersect bounding regions, including to:
group, by grouping circuitry, portions of the set of rays into multiple groups based on the node of the data structure that they target next; and
process, by bounding region test circuitry based on the grouping, a first group that includes a subset of the set of rays that target a first node to determine whether rays in the first group intersect with one or more bounding regions of the first node.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the ray intersect circuitry is configured to select one or more groups of rays during a clock cycle and schedule rays in the groups of rays for issuance to the bounding region test circuitry.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the selection is based on the oldest ray in different groups of rays.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the grouping provides temporal locality for accesses to bounding region data that is cached in one or more data caches.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the ray intersect circuitry includes separate grouping circuitry for leaf nodes of the acceleration data structure and internal nodes of the acceleration data structure.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein the first group is specified by a linked list.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein entries in a ray queue include a field that points to a next ray in the linked list for the corresponding ray's current group.

### Claim 8 (depends on 1)

The apparatus of claim 1, wherein the first group includes rays from multiple different SIMD groups processed by a shader processor.

### Claim 9 (depends on 1)

The apparatus of claim 1, wherein the ray intersect circuitry is configured to assign a ray to a new group each time the ray traverses between levels of the acceleration data structure.

### Claim 10 (depends on 9)

The apparatus of claim 9, wherein the ray intersect circuitry implements a traversal stack for the ray for a depth-first search of the acceleration data structure and wherein the ray intersect circuitry is configured to assign the ray to a new group each time a top of the traversal stack changes.

### Claim 11 (depends on 1)

The apparatus of claim 1, wherein to determine a group for a ray, the ray intersect circuitry is configured to:
use a key that is based on the next node targeted by the ray as an input to a hash function to determine a set of groups; and
search the set of groups to determine whether an allocated group in the set matches the key.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the ray intersect circuitry is configured to allocate a new group for a ray that does not match any currently-allocated group.

### Claim 13 (depends on 1)

The apparatus of claim 1, wherein the bounding region test circuitry includes parallel test circuitry configured to test a ray against multiple bounding regions of a node in parallel.

### Claim 14

A method, comprising:
receiving, by ray intersect circuitry, one or more ray intersect requests that indicate origin and direction information for multiple rays in a set of rays in a graphics scene;
traversing, by the ray intersect circuitry, multiple nodes a spatially-organized acceleration data structure, wherein nodes of the data structure indicate coordinates corresponding to bounding regions of the graphics scene, wherein the traversing includes:
grouping, by grouping circuitry, portions of the set of rays into multiple groups based on the node of the data structure that they target next; and
processing, using bounding region test circuitry based on the grouping, a first group that includes a subset of the set of rays that target a first node to determine whether rays in the first group intersect with one or more bounding regions of the first node.

### Claim 15 (depends on 14)

The method of claim 14, wherein determining a group for a ray during the grouping includes:
using a key that is based on the next node targeted by the ray as an input to a hash function to determine a set of groups; and
searching the set of groups to determine whether an allocated group in the set matches the key.

### Claim 16 (depends on 14)

The method of claim 14, further comprising:
selecting one or more groups of rays and schedule rays in the groups of rays for issuance to the bounding region test circuitry.

### Claim 17

A non-transitory computer readable storage medium having stored thereon design information that specifies a design of at least a portion of a hardware integrated circuit in a format recognized by a semiconductor fabrication system that is configured to use the design information to produce the circuit according to the design, wherein the design information specifies that the circuit includes:
ray intersect circuitry, configured to:
receive one or more ray intersect requests that indicate origin and direction information for multiple rays in a set of rays in a graphics scene;
traverse multiple nodes a spatially-organized acceleration data structure whose nodes indicate coordinates corresponding to bounding regions of the graphics scene, to determine whether rays intersect bounding regions, including to:
group, by grouping circuitry, portions of the set of rays into multiple groups based on the node of the data structure that they target next; and
process, by bounding region test circuitry based on the grouping, a first group that includes a subset of the set of rays that target a first node to determine whether rays in the first group intersect with one or more bounding regions of the first node.

### Claim 18 (depends on 17)

The non-transitory computer readable storage medium of claim 17, wherein the ray intersect circuitry is configured to select one or more groups of rays and schedule rays in the groups of rays for issuance to the bounding region test circuitry.

### Claim 19 (depends on 17)

The non-transitory computer readable storage medium of claim 17, wherein the ray intersect circuitry is configured to specify groups generated by the grouping using singly linked lists.

### Claim 20 (depends on 17)

The non-transitory computer readable storage medium of claim 17, wherein to determine a group for a ray, the ray intersect circuitry is configured to:
use a key that is based on the next node targeted by the ray as an input to a hash function to determine a set of groups; and
search the set of groups to determine whether an allocated group in the set matches the key.