Apparatus and method for performing box queries in ray traversal hardware

Patent metadata

Field	Value
Publication number	US-11915369-B2
Application number	US-202016819120-A
Country	US
Kind code	B2
Filing date	Mar 15, 2020
Priority date	Mar 15, 2020
Publication date	Feb 27, 2024
Grant date	Feb 27, 2024

Abstract

Apparatus and method for box-box testing. For example, one embodiment of a processor comprises: a bounding volume hierarchy (BVH) generator to construct a BVH comprising a plurality of hierarchically arranged BVH nodes; traversal circuitry to traverse query boxes through the BVH, the traversal circuitry to read a BVH node from a top of a BVH node stack and to read a query box from a local storage or memory, the traversal circuitry further comprising: box-box testing circuitry and/or logic to compare maximum and minimum X, Y, and Z coordinates of the BVH node and the query box and to generate an overlap indication if overlap is detected for each of the X, Y, and Z dimensions; distance determination circuitry and/or logic to generate a distance value representing an extent of overlap between the BVH node and the query box; and sorting circuitry and/or logic to sort the BVH node within a set of one or more additional BVH nodes based on the distance value.

First claim

What is claimed is:

1. An apparatus comprising:
a bounding volume hierarchy (BVH) generator to construct a BVH comprising a plurality of hierarchically arranged BVH nodes; and
multi-function traversal circuitry to both traverse query boxes through the BVH and traverse rays through the BVH, the multi-function traversal circuitry to read a BVH node from a top of a BVH node stack and to read a query box from a local storage or memory, the multi-function traversal circuitry further comprising:
box-box testing circuitry and/or logic to compare maximum and minimum X, Y, and Z coordinates of the BVH node and the query box and to generate an overlap indication if overlap is detected for each of the X, Y, and Z dimensions;
distance determination circuitry and/or logic to generate a distance value representing an extent of overlap between the BVH node and the query box; and
sorting circuitry and/or logic to sort the BVH node within a set of one or more additional BVH nodes based on the distance value.

2. The apparatus of claim 1 further comprising:
dequantization circuitry and/or logic to generate the maximum and minimum X, Y, and Z coordinates for the BVH node by dequantizing quantized X, Y and Z coordinates associated with the BVH node.

3. The apparatus of claim 1 wherein the distance determination circuitry is to generate the distance value by performing operations of:
determining a first penetration distance from a first axis-aligned direction and a second penetration distance from a second axis-aligned direction for each of the X, Y, and Z coordinates, the first penetration distance indicating overlap when the query box penetrates the BVH node from the first direction and the second penetration distance indicating overlap when the query box penetrates the BVH node from the second direction; and
selecting for each of the X, Y, and Z coordinates a minimum of the first and second penetration distances.

4. The apparatus of claim 1 wherein the BVH node and the set of one or more additional BVH nodes comprise nodes at a common level of the BVH.

5. The apparatus of claim 4 wherein the distance determination circuitry and/or logic is to determine one or more additional distance values associated with the set of one or more additional BVH nodes, and the sorting circuitry is to generate a sorted order of the BVH node and the set of one or more additional BVH nodes based on the distance value and the one or more additional distance values.

6. The apparatus of claim 5 wherein the BVH node and the set of one or more additional BVH nodes are to be stored to the BVH stack in the sorted order.

7. The apparatus of claim 1 wherein the multi-function traversal circuitry further comprises:
ray traversal circuitry to traverse input rays through the BVH, wherein the ray traversal circuitry comprises ray testing circuitry and/or logic to determine whether an input ray hits the BVH node, wherein the ray testing circuitry and/or logic comprises the box-box testing circuitry and/or logic or a portion thereof.

8. The apparatus of claim 7 wherein if the ray testing circuitry and/or logic determines that the ray hits the BVH node, then the distance determination circuitry is to determine a hit distance value representing a coordinate at which the ray hits the BVH node and the sorting circuitry and/or logic is to sort the BVH node within the set of one or more additional BVH nodes based one or more additional hit distance values associated with the set of one or more additional BVH nodes.

9. A method comprising:
constructing a bounding volume hierarchy (BVH) comprising a plurality of hierarchically arranged BVH nodes;
reading, by multi-function traversal circuitry, a BVH node from a top of a BVH node stack, the multi-function traversal circuitry configured to both traverse query boxes through the BVH and traverse rays through the BVH, wherein to traverse query boxes through the BVH, the multi-function traversal circuitry performs additional operations of:
reading a query box from a local storage or memory;
comparing maximum and minimum X, Y, and Z coordinates of the BVH node and the query box;
generating an overlap indication if overlap is detected for each of the X, Y, and Z dimensions;
generating a distance value representing an extent of overlap between the BVH node and the query box; and

sorting the BVH node within a set of one or more additional BVH nodes based on the distance value.

10. The method of claim 9 wherein the multi-function traversal circuitry is to perform the operations of:
dequantizing quantized X, Y and Z coordinates associated with the BVH node to generate the maximum and minimum X, Y, and Z coordinates.

11. The method of claim 9 wherein the distance value is generated by performing the operations of:
determining a first penetration distance from a first axis-aligned direction and a second penetration distance from a second axis-aligned direction for each of the X, Y, and Z coordinates, the first penetration distance indicating overlap when the query box penetrates the BVH node from the first direction and the second penetration distance indicating overlap when the query box penetrates the BVH node from the second direction; and
selecting for each of the X, Y, and Z coordinates a minimum of the first and second penetration distances.

12. The method of claim 9 wherein the BVH node and the set of one or more additional BVH nodes comprise nodes at a common level of the BVH.

13. The method of claim 12 further comprising:
determining one or more additional distance values associated with the one or more additional BVH nodes, and
generating a sorted order of the BVH node and the set of one or more additional BVH nodes based on the distance value and the one or more additional distance values.

14. The method of claim 13 wherein the BVH node and the set of one or more additional BVH nodes are to be stored to the BVH stack in the sorted order.

15. The method of claim 9 further comprising:
traversing, the by multi-function traversal circuitry, an input ray through the BVH by comparing coordinates of the input ray with the maximum and minimum X, Y, and Z coordinates of the BVH node, wherein a common set of testing circuitry and/or logic is used to determine whether the input ray hits the BVH node and is also used for comparing the maximum and minimum X, Y, and Z coordinates of the BVH node and the query box.

16. The method of claim 15 wherein if the input ray is determined to hit the BVH node, then the method further comprises:
determining a hit distance value representing a coordinate at which the ray hits the BVH node; and
sorting the BVH node within the set of one or more additional BVH nodes based one or more additional hit distance values associated with the set of one or more additional BVH nodes.

17. A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform operations of:
constructing a bounding volume hierarchy (BVH) comprising a plurality of hierarchically arranged BVH nodes;
reading, by multi-function traversal circuitry, a BVH node from a top of a BVH node stack, the multi-function traversal circuitry configured to both traverse query boxes through the BVH and traverse rays through the BVH, wherein to traverse query boxes through the BVH, the multi-function traversal circuitry performs additional operations of:
reading a query box from a local storage or memory; comparing maximum and minimum X, Y, and Z coordinates of the BVH node and the query box;
generating

Assignees

• Intel Corp

Inventors

• Vaidyanathan Karthik
• Benthin Carsten
• Woop Sven

Classifications

• G06T17/10 Primary

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06F7/24

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title