# US 2022/0036652 A1 · Ray Intersection Data Structure with Many-to-Many Mapping between Bounding Regions and Primitives

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

- Number: US 2022/0036652 A1
- Document ID: US20220036652A1
- Status: Published application
- Kind: A1
- Application number: 17/103,352
- 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
- Web page: https://patentgrep.com/patent/US20220036652A1

## 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 an acceleration data structure for ray intersection with a many-to-many mapping between bounding regions and primitives. In some embodiments, one or more graphics processors access data for multiple graphics primitives in a graphics scene and generate a spatially organized data structure. Some nodes of the data structure indicate graphics primitives and some nodes indicate coordinates of bounding regions in the graphics scene. In some embodiments, the spatially organized data structure includes a node with a bounding region for which multiple primitives are indicated as children and also includes a primitive for which multiple bounding regions are indicated as parents. Disclosed techniques may generate bounding regions that closely fit primitives, which may reduce primitive testing for ray tracing. This in turn may increase performance or reduce power consumption relative to traditional techniques.

## Claims

### Claim 1

An apparatus, comprising:
one or more graphics processors configured to:
access data for multiple graphics primitives in a graphics scene to be rendered;
generate a spatially organized data structure wherein some nodes of the data structure indicate graphics primitives and some nodes indicate coordinates of bounding regions in the graphics scene, wherein:
the spatially organized data structure includes a node with a bounding region for which multiple primitives are indicated as children; and
the spatially organized data structure includes a primitive for which multiple nodes, corresponding to different bounding regions, are indicated as parents; and
traverse the spatially organized data structure to determine whether rays in the graphics scene intersect with primitives; and
shade intersected primitives based on the determination.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the one or more graphics processors are configured to quantize information that indicates a first bounding region in the spatially organized data structure to represent the first bounding region using a smaller number of bits than an original representation.

### Claim 3 (depends on 2)

The apparatus of claim 2, wherein the one or more graphics processors are configured to perform the quantization such that the quantized representation indicates a region that is larger than or equal to the first bounding region, thereby preventing false negative intersection results for the first bounding region.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the spatially organized data structure includes, for a first node that indicates one or more primitives, one or more fields that indicate:
an offset at which the one or more primitives are located; and
a number of primitives for the first node that are located at the offset.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the spatially organized data structure includes a node that has at least four child nodes.

### Claim 6 (depends on 1)

The apparatus of claim 1, where the spatially organized data structure encodes a memory location for a node at which all child nodes of the node are consecutively located.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein a driver for the one or more graphics processors is configured to insert debug data into memory space between children of one or more of the nodes.

### Claim 8 (depends on 1)

The apparatus of claim 1, wherein the spatially organized data structure specifies primitive information in leaf nodes and bounding region information in internal nodes.

### Claim 9 (depends on 1)

The apparatus of claim 1, wherein a first leaf node and a second leaf node in the spatially organized data structure have different data sizes, wherein respective parent nodes of the first leaf node and the second leaf node encode the different data sizes.

### Claim 10 (depends on 1)

The apparatus of claim 1, further comprising:
network interface circuitry; and
one or more central processing units.

### Claim 11

A method, comprising:
accessing, by a graphics processor, data for multiple graphics primitives in a graphics scene to be rendered;
generating a spatially organized data structure wherein nodes of the data structure indicate graphics primitives or coordinates of bounding regions in the graphics scene; and
traversing the spatially organized data structure to determine whether rays in the graphics scene intersect with primitives and shading intersected primitives based on the determination;
wherein the spatially organized data structure includes a node with a bounding region for which multiple primitives are indicated as children; and
wherein the spatially organized data structure includes a primitive for which multiple nodes, corresponding to different bounding regions, are indicated as parents.

### Claim 12 (depends on 11)

The method of claim 11, further comprising:
quantizing information that indicates a first bounding region in the spatially organized data structure to represent the first bounding region using a smaller number of bits than an original representation, wherein the quantization is performed such that the quantized representation indicates a region that is larger than or equal to the first bounding region.

### Claim 13 (depends on 11)

The method of claim 11, wherein a first leaf node and a second leaf node in the spatially organized data structure have different data sizes, wherein respective parent nodes of the first leaf node and the second leaf node encode the different data sizes.

### Claim 14

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:
one or more graphics processors configured to:
access data for multiple graphics primitives in a graphics scene to be rendered;
generate a spatially organized data structure wherein some nodes of the data structure indicate graphics primitives and some nodes indicate coordinates of bounding regions in the graphics scene, wherein:
the spatially organized data structure includes a node with a bounding region for which multiple primitives are indicated as children; and
the spatially organized data structure includes a primitive for which multiple nodes, corresponding to different bounding regions, are indicated as parents; and
traverse the spatially organized data structure to determine whether rays in the graphics scene intersect with primitives; and
shade intersected primitives based on the determination.

### Claim 15 (depends on 14)

The non-transitory computer readable storage medium of claim 14, wherein the one or more graphics processors are further configured to quantize information that indicates a first bounding region in the spatially organized data structure to represent the first bounding region using a smaller number of bits than an original representation.

### Claim 16 (depends on 15)

The non-transitory computer readable storage medium of claim 15, wherein the one or more graphics processors are configured to perform the quantization such that the quantized representation indicates a region that is larger than or equal to the first bounding region.

### Claim 17 (depends on 14)

The non-transitory computer readable storage medium of claim 14, wherein the spatially organized data structure includes, for a first node that indicates one or more primitives, a first field that indicates an offset at which the one or more primitives are located and a second field that indicates a number of primitives for the first node that are located at the offset.

### Claim 18 (depends on 14)

The non-transitory computer readable storage medium of claim 14, wherein the spatially organized data structure includes a node that has at least four child nodes.

### Claim 19 (depends on 14)

The non-transitory computer readable storage medium of claim 14, where the spatially organized data structure encodes a location for a node at which all child nodes of the node are consecutively located.

### Claim 20 (depends on 14)

The non-transitory computer readable storage medium of claim 14, wherein a first leaf node and a second leaf node in the spatially organized data structure have different data sizes, wherein respective parent nodes of the first leaf node and the second leaf node encode the different data sizes.