Apparatus and method for performing box queries in ray traversal hardware

Patent metadata

Field	Value
Publication number	US-12450833-B2
Application number	US-202418587800-A
Country	US
Kind code	B2
Filing date	Feb 26, 2024
Priority date	Mar 15, 2020
Publication date	Oct 21, 2025
Grant date	Oct 21, 2025

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 first circuitry to construct a bounding volume hierarchy (BVH) to include a plurality of hierarchically arranged BVH nodes; and
a second circuitry to traverse both query boxes and rays through the BVH, wherein traversal of a query box through a BVH node is to:
read the BVH node from a top of a BVH node storage and to read the query box;
compare maximum and minimum sets of coordinates of the BVH node and the query box to generate an overlap indication responsive to overlap being detected for each of one or more corresponding dimensions indicated by the sets of coordinates; and
sort the BVH node within a set of one or more additional BVH nodes based on extent of the overlap between the BVH node and the query box, wherein the BVH node and the set of one or more additional BVH nodes are to be stored based on the sorting.

2. The apparatus of claim 1 , wherein the maximum and minimum sets of coordinates for the BVH is generated by dequantizing a quantized set of coordinates associated with the BVH node.

3. 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.

4. The apparatus of claim 1 , wherein the extent of the overlap between the BVH node and the query box is indicated through a distance value generated by the second circuitry.

5. The apparatus of claim 4 , wherein generation of the distance value comprises:
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 sets of 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 sets of coordinates a minimum of the first and second penetration distances.

6. The apparatus of claim 4 , wherein one or more additional distance values associated with the set of one or more additional BVH nodes are determined, and a sorted order of the BVH node and the set of one or more additional BVH nodes is generated based on the distance value and the one or more additional distance values.

7. The apparatus of claim 1 , wherein the BVH node and the set of one or more additional BVH nodes are to be stored to the BVH node storage in a sorted order based on the sorting.

8. The apparatus of claim 1 , wherein traversal of a ray through the BVH node is to determine whether the ray hits the BVH node, and wherein responsive to that the ray hits the BVH node, a hit distance value is determined representing a coordinate at which the ray hits the BVH node, the BVH node within the set of one or more additional BVH nodes is sorted based on 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) to include a plurality of hierarchically arranged BVH nodes; and
traversing both query boxes and rays through the BVH, wherein traversal of a query box through a BVH node comprising:
reading the BVH node from a top of a BVH node storage and to read the query box;
comparing maximum and minimum sets of coordinates of the BVH node and the query box to generate an overlap indication responsive to overlap being detected for each of one or more corresponding dimensions indicated by the sets of coordinates; and
sorting the BVH node with a set of one or more additional BVH nodes based on extent of the overlap between the BVH node and the query box, wherein the BVH node and the set of one or more additional BVH nodes are to be stored based on the sorting.

10. The method of claim 9 , wherein the maximum and minimum sets of coordinates for the BVH is generated by dequantizing a quantized set of coordinates associated with the BVH node.

11. 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.

12. The method of claim 9 , wherein the extent of the overlap between the BVH node and the query box is indicated through a distance value generated through traversing the query box through the BVH node.

13. The method of claim 12 , wherein generation of the distance value comprises:
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 sets of 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 sets of coordinates a minimum of the first and second penetration distances.

14. The method of claim 12 , wherein one or more additional distance values associated with the set of one or more additional BVH nodes are determined, and a sorted order of the BVH node and the set of one or more additional BVH nodes is generated based on the distance value and the one or more additional distance values.

15. The method of claim 9 , wherein the BVH node and the set of one or more additional BVH nodes are to be stored to the BVH node storage in a sorted order based on the sorting.

16. The method of claim 9 , wherein traversal of a ray through the BVH node is to determine whether the ray hits the BVH node, and wherein responsive to that the ray hits the BVH node, a hit distance value is determined representing a coordinate at which the ray hits the BVH node, the BVH node within the set of one or more additional BVH nodes is sorted based on 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:
constructing a bounding volume hierarchy (BVH) to include a plurality of hierarchically arranged BVH nodes; and
traversing both query boxes and rays through the BVH, wherein traversal of a query box through a BVH node comprising:
reading the BVH node from a top of a BVH node storage and to read the query box;
comparing maximum and minimum sets of coordinates of the BVH node and the query box to generate an overlap indication responsive to overlap being detected for each of one or more corresponding dimensions indicated by the sets of coordinates; and
sorting the BVH node with a set of one or more additional BVH nodes based on extent of the overlap between the BVH node and the query box, wherein the BVH node and the set of one or more additional BVH nodes are to be stored based on the sorting.

18. The non-transitory machine-readable medium of claim 17 , wherein the maximum and minimum sets of coordinates for the BVH is generated by dequantizing a quantized set of coordinates associated with the BVH node.

19. The non-transitory machine-readable medium of claim 17 , wherein the BVH node and the set of one or more additional BVH nodes comprise nodes at a common level of the BVH.

20. The non-transitory machine-readable medium of claim 17 , wherein the extent of the overlap between the BVH node and the query box is indicated through a distance value generated through traversing the query box through the BVH node.

Assignees

• Intel Corp

Inventors

• Vaidyanathan Karthik
• Benthin Carsten
• Woop Sven

Classifications

• G06T17/205

  Re-meshing · CPC title

• G06T15/08

  Volume rendering · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T15/005

  General purpose rendering architectures · CPC title

• G06T1/20

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