# US 11,308,683 B2 · Intersection testing in a ray tracing system using ray bundle vectors

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

- Number: US 11,308,683 B2
- Document ID: US11308683B2
- Status: Granted
- Kind: B2
- Application number: 16/914,684
- Filed: 2020-06-29
- Published: 2021-12-30
- Granted: 2022-04-19
- Earliest claimed: 2020-06-29
- Assignees: Imagination Technologies Limited
- Applicants: Imagination Technologies Limited
- Inventors: Gregory Clark; Steven J. Clohset; Luke T. Peterson
- Web page: https://patentgrep.com/patent/US11308683B2

## CPC

- G06T 15/06: Ray-tracing
- G06T 7/13: Edge detection
- G06T 7/60: Analysis of geometric attributes
- G06T 2210/12: Bounding box
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Ray tracing systems and computer-implemented methods perform intersection testing on a bundle of rays with respect to a box. Silhouette edges of the box are identified from the perspective of the bundle of rays. For each of the identified silhouette edges, components of a vector providing a bound to the bundle of rays are obtained and it is determined whether the vector passes inside or outside of the silhouette edge. Results of determining, for each of the identified silhouette edges, whether the vector passes inside or outside of the silhouette edge, are used to determine an intersection testing result for the bundle of rays with respect to the box.

## Claims

### Claim 1

A computer-implemented method of performing intersection testing in a ray tracing system, the method comprising:
receiving a bundle of rays to be tested for intersection with a box;
identifying silhouette edges of the box from the perspective of the bundle of rays;
for each of the identified silhouette edges:
obtaining components of a vector providing a bound to the bundle of rays, and
determining whether the vector passes inside or outside of the silhouette edge; and
using results of determining, for each of the identified silhouette edges, whether the vector passes inside or outside of the silhouette edge, to determine an intersection testing result for the bundle of rays with respect to the box.

### Claim 2 (depends on 1)

The method of claim 1 wherein, for each of the identified silhouette edges, said obtaining components of a vector comprises obtaining components of a single vector providing a single bound to the bundle of rays.

### Claim 3 (depends on 1)

The method of claim 1 wherein, for each of the identified silhouette edges, the vector for which it is determined whether the vector passes inside or outside of the silhouette edge is the only vector for which a determination is made for the bundle of rays as to whether the vector passes inside or outside of the silhouette edge.

### Claim 4 (depends on 1)

The method of claim 1 wherein the intersection testing result for the bundle of rays with respect to the box is determined using said results of determining, for each of the identified silhouette edges, whether the vector passes inside or outside of the silhouette edge, and without using any other results of determining whether any other vectors pass inside or outside of the silhouette edges.

### Claim 5 (depends on 1)

The method of claim 1 wherein, for each of the identified silhouette edges, said vector provides an external bound to the bundle of rays with respect to said identified silhouette edge, such that if it does not pass outside the identified silhouette edge then it is known that none of the rays of the bundle pass outside said identified silhouette edge.

### Claim 6 (depends on 5)

The method of claim 5, wherein if it is determined that, for each of the identified silhouette edges, the vector passes inside the respective identified silhouette edge, then the intersection testing result for the bundle of rays with respect to the box is that all of the rays in the bundle of rays intersect the box; and
wherein if it is determined that, for one or more of the identified silhouette edges, the vector passes outside the respective identified silhouette edge, then the intersection testing result for the bundle of rays with respect to the box is not that all of the rays in the bundle of rays intersect the box.

### Claim 7 (depends on 6)

The method of claim 6 wherein if the intersection testing result for the bundle of rays with respect to the box is not that all of the rays in the bundle of rays intersect the box, then the method further comprises determining whether any of the rays in the bundle of rays intersect the box.

### Claim 8 (depends on 1)

The method of claim 1 wherein, for each of the identified silhouette edges, said vector provides an internal bound to the bundle of rays with respect to said identified silhouette edge, such that if it does not pass inside the identified silhouette edge then it is known that none of the rays of the bundle pass inside said identified silhouette edge.

### Claim 9 (depends on 8)

The method of claim 8, wherein if it is determined that, for each of the identified silhouette edges, the vector passes inside the respective identified silhouette edge, then the intersection testing result for the bundle of rays with respect to the box is not that all of the rays in the bundle of rays miss the box; and
wherein if it is determined that, for one or more of the identified silhouette edges, the vector passes outside the respective identified silhouette edge, then the intersection testing result for the bundle of rays with respect to the box is that all of the rays in the bundle of rays miss the box.

### Claim 10 (depends on 9)

The method of claim 9 wherein if the intersection testing result for the bundle of rays with respect to the box is not that all of the rays in the bundle of rays miss the box, then the method further comprises determining which of the rays in the bundle of rays intersect the box.

### Claim 11 (depends on 1)

The method of claim 1 further comprising:
performing a direction check to determine whether the box is behind an origin of the bundle of rays, wherein if the direction check determines that the box is behind the origin of the bundle of rays then the intersection testing result is that the bundle of rays misses the box; and/or
performing a distance check to determine whether the bundle of rays terminates at a point in front of the box, wherein if the distance check determines that the bundle of rays terminates at a point in front of the box then the intersection testing result is that the bundle of rays misses the box.

### Claim 12 (depends on 1)

The method of claim 1 wherein all of the rays of the bundle of rays have the same origin and wherein, for each of the identified silhouette edges, said determining whether the vector passes inside or outside of the silhouette edge comprises performing a comparison in accordance with (po,i−oi)dj<(po,j−oj)i, wherein po,i is the ith component of a point on a first plane representing a first of the sides of the box which forms the silhouette edge, po,j is the jth component of a point on a second plane representing a second of the sides of the box which forms the silhouette edge, oi and oj are the ith and jth components of the origin of the rays of the bundle of rays, and di and dj are the obtained ith and jth components of the vector providing a bound to the bundle of rays.

### Claim 13 (depends on 1)

The method of claim 1 wherein it is not the case that all of the rays of the bundle of rays have the same origin and wherein, for each of the identified silhouette edges, said determining whether the vector passes inside or outside of the silhouette edge comprises performing a comparison in accordance with (po,i−oi,[min,max])dj<(po,j−oj,[min,max])di, wherein po,i is the ith component of a point on a first plane representing a first of the sides of the box which forms the silhouette edge, po,j is the jth component of a point on a second plane representing a second of the sides of the box which forms the silhouette edge, oi[min,max] is either the minimum or the maximum of the ith components of the origins of the rays of the bundle of rays, oj[min,max] is either the minimum or the maximum of the jth components of the origins of the rays of the bundle of rays, and di and dj are the obtained ith and jth components of the vector providing a bound to the bundle of rays.

### Claim 14 (depends on 1)

The method of claim 1 further comprising:
receiving rays; and
constructing bundles of rays from the received rays to be tested for intersection with the box, wherein said constructing bundles of rays comprises grouping together received rays based on their similarity.

### Claim 15 (depends on 14)

The method of claim 14 wherein said constructing bundles of rays comprises:
maintaining a set of open bundles to which new rays can be added; and
for each of the received rays:
determining a level of similarity of the received ray with each of the open bundles;
identifying a best match open bundle of said set of open bundles for the received ray based on the determined levels of similarity; and
if the determined level of similarity of the received ray with the best match open bundle is above a threshold, adding the received ray to the best match open bundle.

### Claim 16 (depends on 14)

The method of claim 14 wherein either:
said received rays from which the bundles are constructed: (i) include new rays which have not previously been included in a bundle of rays, but (ii) do not include rays which have previously been included in a bundle of rays; or
said received rays from which the bundles are constructed include: (i) new rays which have not previously been included in a bundle of rays, and (ii) rays which have previously been included in a bundle of rays which has been deconstructed.

### Claim 17 (depends on 1)

The method of claim 1 further comprising splitting up a bundle of rays into individual rays if a splitting metric is satisfied, wherein the splitting metric is based on one or more of:
a number of rays in the bundle of rays;
a spread of the rays in the bundle of rays;
a size of an area defined by the silhouette edges of the box;
whether the source of the rays in the bundle of rays is a frame shader or a ray shader; and
data provided by the shader which created the rays in the bundle of rays.

### Claim 18

A ray tracing system comprising:
a tester module configured to receive a bundle of rays to be tested for intersection with a box, wherein the tester module comprises:
a set of one or more testing blocks configured to perform intersection testing on the received bundle of rays with respect to the box by:
identifying silhouette edges of the box from the perspective of the bundle of rays;
for each of the identified silhouette edges:
obtaining components of a vector providing a bound to the bundle of rays; and
determining whether the vector passes inside or outside of the silhouette edge; and
using results of determining, for each of the identified silhouette edges, whether the vector passes inside or outside of the silhouette edge, to determine an intersection testing result for the bundle of rays with respect to the box.

### Claim 19 (depends on 18)

The ray tracing system of claim 18 wherein a testing block of said set of one or more testing blocks is configured to perform intersection testing for a bundle of rays and to perform intersection testing for a single ray.

### Claim 20

A non-transitory computer readable storage medium having stored thereon an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a ray tracing system which comprises:
a tester module configured to receive a bundle of rays to be tested for intersection with a box, wherein the tester module comprises:
a set of one or more testing blocks configured to perform intersection testing on the received bundle of rays with respect to the box by:
identifying silhouette edges of the box from the perspective of the bundle of rays;
for each of the identified silhouette edges:
obtaining components of a vector providing a bound to the bundle of rays, and
determining whether the vector passes inside or outside of the silhouette edge; and
using results of determining, for each of the identified silhouette edges, whether the vector passes inside or outside of the silhouette edge, to determine an intersection testing result for the bundle of rays with respect to the box.