# US 2023/0410409 A1 · Intersection Testing in a Ray Tracing System Using Three-Dimensional Axis-Aligned Box

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

- Number: US 2023/0410409 A1
- Document ID: US20230410409A1
- Status: Published application
- Kind: A1
- Application number: 18/239,679
- Filed: 2023-08-29
- Published: 2023-12-21
- Earliest claimed: 2021-03-23
- Assignees: Imagination Technologies Limited
- Applicants: Imagination Technologies Limited
- Inventors: Gregory Clark; Simon Fenney
- Web page: https://patentgrep.com/patent/US20230410409A1

## CPC

- G06T 15/06: Ray-tracing
- G06T 15/005: {General purpose rendering architectures}
- G06T 2210/12: Bounding box
- G06T 2210/21: Collision detection, intersection
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Methods and intersection testing modules are provided for determining, in a ray tracing system, whether a ray intersects a 3D axis-aligned box representing a volume defined by a front-facing plane and a back-facing plane for each dimension. The front-facing plane of the box which intersects the ray furthest along the ray is identified. It is determined whether the ray intersects the identified front-facing plane at a position that is no further along the ray than positions at which the ray intersects the back-facing planes in a subset of the dimensions, and this determination is used to determine whether the ray intersects the axis-aligned box. The subset of dimensions comprises the two dimensions for which the front-facing plane was not identified, but does not comprise the dimension for which the front-facing plane was identified. It is determined whether the ray intersects the box without performing a test to determine whether the ray intersects the identified front-facing plane at a position that is no further along the ray than a position at which the ray intersects the back-facing plane in the dimension for which the front-facing plane was identified.

## Claims

### Claim 1

A method of determining, in a ray tracing system, whether a ray intersects a three-dimensional axis-aligned box, wherein the box represents a volume defined by a front-facing plane and a back-facing plane for each dimension of the three-dimensional axis-aligned box, the method comprising:
identifying which of the front-facing planes intersects the ray at a position that is furthest along a direction of the ray; and
determining whether the ray intersects the axis-aligned box in dependence on comparing (i) the position at which the ray intersects the identified front-facing plane with (ii) at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified;
wherein the method determines whether the ray intersects the box without comparing the position at which the ray intersects the identified front-facing plane with a position at which the ray intersects the back-facing plane in the dimension for which the front-facing plane was identified.

### Claim 2 (depends on 1)

The method of claim 1, wherein said steps of identifying which of the front-facing planes of the box intersects the ray at a position that is furthest along a direction of the ray and comparing (i) the position at which the ray intersects the identified front-facing plane with (ii) the at least one position at which the ray intersects one of the back-facing planes are performed without computing intersection distances to any of the planes of the box.

### Claim 3 (depends on 1)

The method of claim 1, wherein said identifying which of the front-facing planes of the box intersects the ray at a position that is furthest along the direction of the ray comprises:
performing a first front-facing test to determine which of a first front-facing plane and a second front-facing plane of the box the ray intersects furthest along the ray; and
performing a second front-facing test to determine which of the determined front-facing plane and a third front-facing plane of the box the ray intersects furthest along the ray, thereby identifying which of the front-facing planes of the box intersects the ray furthest along the ray.

### Claim 4 (depends on 1)

The method of claim 1, wherein said identifying which of the front-facing planes of the box intersects the ray at a position that is furthest along the direction of the ray comprises:
performing a first front-facing test to determine which of a first front-facing plane and a second front-facing plane of the box intersects the ray at a position that is furthest along the ray;
performing a second front-facing test to determine which of the first front-facing plane and a third front-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray;
performing a third front-facing test to determine which of the second front-facing plane and the third front-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray; and
using the results of the first, second and third front-facing tests to identify which of the front-facing planes of the box intersects the ray at a position that is furthest along the direction of the ray.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of comparing (i) the position at which the ray intersects the identified front-facing plane with (ii) the at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified comprises determining whether the position at which the ray intersects the identified front-facing plane is no further along the ray than the at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified.

### Claim 6 (depends on 5)

The method of claim 5, wherein said determining whether the position at which the ray intersects the identified front-facing plane is no further along the ray than the at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified comprises:
performing a first mixed-facing test to determine which of the identified front-facing plane and a first back-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray, wherein the first back-facing plane of the box is a back-facing plane for a first dimension of the two dimensions for which the front-facing plane was not identified;
performing a second mixed-facing test to determine which of the identified front-facing plane and a second back-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray, wherein the second back-facing plane of the box is a back-facing plane for a second dimension of the two dimensions for which the front-facing plane was not identified; and
using the results of the first and second mixed-facing tests to determine whether the position at which the ray intersects the identified front-facing plane is no further along the ray than the at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified.

### Claim 7 (depends on 5)

The method of claim 5, wherein said determining whether the position at which the ray intersects the identified front-facing plane is no further along the ray than the at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified comprises:
performing a back-facing test to determine which of a first back-facing plane and a second back-facing plane of the box intersects the ray at a position that is the least far along the direction of the ray, wherein the first back-facing plane and the second back-facing plane each have a respective dimension of the two dimensions for which the front-facing plane was not identified;
performing a mixed-facing test to determine which of the identified front-facing plane and the determined back-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray; and
using the result of the mixed-facing test to determine whether the position at which the ray intersects the identified front-facing plane is no further along the ray than the at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
storing one or more intermediate results which are determined in said identifying which of the front-facing planes of the box intersects the ray at a position that is furthest along the direction of the ray; and
reading the stored one or more intermediate results for use in the step of comparing (i) the position at which the ray intersects the identified front-facing plane with (ii) the at least one position at which the ray intersects one of the back-facing planes.

### Claim 9 (depends on 1)

The method of claim 1, further comprising determining whether a maximum distance condition is satisfied, wherein the maximum distance condition is satisfied if a maximum valid distance of the ray from the ray origin is greater than or equal to a minimum distance from the ray origin to any intersection of the ray with a point within the box,
wherein said determining whether the ray intersects the axis-aligned box further comprises using the determination of whether the maximum distance condition is satisfied.

### Claim 10 (depends on 1)

The method of claim 1, further comprising determining whether a minimum distance condition is satisfied, wherein the minimum distance condition is satisfied if a minimum valid distance of the ray from the ray origin is less than or equal to a maximum distance from the ray origin to any intersection of the ray with a point within the box;
wherein said determining whether the ray intersects the axis-aligned box further comprises using the determination of whether the minimum distance condition is satisfied.

### Claim 11 (depends on 10)

The method of claim 10, further comprising determining whether a maximum distance condition is satisfied, wherein the maximum distance condition is satisfied if a maximum valid distance of the ray from the ray origin is greater than or equal to a minimum distance from the ray origin to any intersection of the ray with a point within the box;
wherein said determining whether the ray intersects the axis-aligned box further comprises using the determination of whether the maximum distance condition is satisfied; and
wherein said determining whether a maximum distance condition is satisfied and said determining whether a minimum distance condition is satisfied are performed in parallel with the step of comparing (i) the position at which the ray intersects the identified front-facing plane and (ii) the at least one position at which the ray intersects one of the back-facing planes.

### Claim 12

A method of determining, in a ray tracing system, whether a ray intersects a three-dimensional axis-aligned box, wherein the box represents a volume defined by a front-facing plane and a back-facing plane for each dimension of the three-dimensional axis-aligned box, the method comprising:
identifying which of the back-facing planes intersects the ray as a position that is the least far along a direction of the ray; and
determining whether the ray intersects the axis-aligned-box in dependence on comparing (i) the position at which the ray intersects the identified back-facing plane with (ii) at least one position at which the ray intersects one of the front-facing planes for the two dimensions for which the back-facing plane was not identified;
wherein the method determines whether the ray intersects the box without comparing the position at which the ray intersects the identified back-facing plane with a position at which the ray intersects the front-facing plane in the dimension for which back-facing plane was identified.

### Claim 13 (depends on 12)

The method of claim 12, wherein said identifying which of the back-facing planes of the box intersects the ray as a position that is the least far along the direction of the ray comprises:
performing a first back-facing test to determine which of a first back-facing plane and a second back-facing plane of the box intersects the ray intersects as a position that is the least far along the direction of the ray; and
performing a second back-facing test to determine which of the determined back-facing plane and a third back-facing plane of the box intersects the ray as a position that is the least far along the direction of the ray, thereby identifying which of the back-facing planes of the box intersects the ray at a position that is the least far along the direction of the ray.

### Claim 14 (depends on 12)

The method of claim 12, wherein said identifying which of the back-facing planes of the box intersects the ray as a position that is the least far along the direction of the ray comprises:
performing a first back-facing test to determine which of a first back-facing plane and a second back-facing plane of the box intersects the ray at a position that is the least far along the direction of the ray;
performing a second back-facing test to determine which of the first back-facing plane and a third back-facing plane of the box intersects the ray at a position that is the least far along the direction of the ray;
performing a third back-facing test to determine which of the second back-facing plane and the third back-facing plane of the box intersects the ray at a position that is the least far along the direction of the ray; and
using the results of the first, second and third back-facing tests to identify which of the back-facing planes of the box intersects the ray as a position that the least far along the direction of the ray.

### Claim 15 (depends on 12)

The method of claim 12, wherein the step of comparing (i) the position at which the ray intersects the identified back-facing plane with (ii) the at least one position at which the ray intersects one of the front-facing planes for the two dimensions for which the back-facing plane was not identified comprises determining whether the at least one position at which the ray intersects one of the front-facing planes for the two dimensions for which the back-facing plane was not identified is no further along the ray than the position at which the ray intersects the identified back-facing plane.

### Claim 16 (depends on 15)

The method of claim 15, wherein said determining whether the at least one position at which the ray intersects one of the front-facing planes for the for the two dimensions for which the back-facing plane was not identified is no further along the ray than the position at which the ray intersects the identified back-facing plane comprises:
performing a first mixed-facing test to determine which of the identified back-facing plane and a first front-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray, wherein the first front-facing plane of the box is a front-facing plane for a first dimension for the two dimensions for which the back-facing plane was not identified;
performing a second mixed-facing test to determine which of the identified back-facing plane and a second front-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray, wherein the second front-facing plane of the box is a front-facing plane for a second dimension for the two dimensions for which the back-facing plane was not identified; and
using the results of the first and second mixed-facing tests to determine whether the at least one position at which the ray intersects one of the front-facing planes for the for the two dimensions for which the back-facing plane was not identified is no further along the ray than the position at which the ray intersects the identified back-facing plane.

### Claim 17 (depends on 15)

The method of claim 15, wherein said determining whether the at least one position at which the ray intersects one of the front-facing planes for the for the two dimensions for which the back-facing plane was not identified is no further along the ray than the position at which the ray intersects the identified back-facing plane comprises:
performing a front-facing test to determine which of a first front-facing plane and a second front-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray, wherein the first front-facing plane of the box and the second front-facing plane of the box each have a respective dimension of the two dimensions for which the back-facing plane was not identified;
performing a mixed-facing test to determine which of the identified back-facing plane and the determined front-facing plane of the box intersects the ray at a position that is furthest along the direction of the ray; and
using the result of the mixed-facing test to determine whether the at least one position at which the ray intersects one of the front-facing planes for the two dimensions for which the back-facing plane was not identified is no further along the ray than the position at which the ray intersects the identified back-facing plane.

### Claim 18 (depends on 1)

The method of claim 1, further comprising selectively reversing the axes for the components of the ray and the axis-aligned box, such that Di≥0, Dj≥0 and Dk≥0, before identifying which of the front-facing planes of the box intersects the ray at a position that is furthest along the direction of the ray, wherein Di, Dj and Dk are the components of a direction vector of the ray in the ith, jth and kth dimensions respectively.

### Claim 19

An intersection testing module implemented in fixed function circuitry, for use in a ray tracing system, configured to determine whether a ray intersects a three-dimensional axis-aligned box, wherein the box represents a volume defined by a front-facing plane and a back-facing plane for each dimension of the three-dimensional axis-aligned box, the intersection testing module being configured to:
identify which of the front-facing planes intersects the ray at a position that is furthest along a direction of the ray; and
determine whether the ray intersects the axis-aligned box in dependence on comparing (i) the position at which the ray intersects the identified front-facing plane with (ii) at least one position at which the ray intersects one of the back-facing planes for the two dimensions for which the front-facing plane was not identified;
wherein the intersection testing module is configured to determine whether the ray intersects the box without comparing the position at which the ray intersects the identified front-facing plane with a position at which the ray intersects the back-facing plane in the dimension for which the front-facing plane was identified.

### Claim 20

An intersection testing module implemented in fixed function circuitry, for use in a ray tracing system, configured to determine whether a ray intersects a three-dimensional axis-aligned box, wherein the box represents a volume defined by a front-facing plane and a back-facing plane for each dimension of the three-dimensional axis-aligned box, the intersection testing module being configured to:
identify which of the back-facing planes intersects the ray at a position that is the least far along a direction of the ray; and
determine whether the ray intersects the axis-aligned-box in dependence on comparing (i) the position at which the ray intersects the identified back-facing plane with (ii) at least one position at which the ray intersects one of the front-facing planes for the two dimensions for which the back-facing plane was not identified;
wherein the intersection testing module is configured to determine whether the ray intersects the box without comparing the position at which the ray intersects the identified back-facing plane with a position at which the ray intersects the front-facing plane in the dimension for which back-facing plane was identified.
