Apparatus and method for accelerating BVH builds by merging bounding boxes

Patent metadata

Field	Value
Publication number	US-12499606-B2
Application number	US-202217699060-A
Country	US
Kind code	B2
Filing date	Mar 18, 2022
Priority date	Mar 18, 2022
Publication date	Dec 16, 2025
Grant date	Dec 16, 2025

Abstract

Apparatus and method for accelerating bounding box merge operations. For example, one embodiment of an apparatus comprises: ray tracing acceleration hardware to be used to determine ray traversal results when traversing a ray through a bounding volume hierarchy (BVH), the BVH comprising a plurality of axis-aligned bounding boxes (AABBs); and a bounding box (BB) merge accelerator coupled to one or more execution units and coupled to a local memory in which to store a group of the AABBs, the BB merge accelerator, in response to the one or more EUs, to determine a second AABB to merge with a first AABB in accordance with a specified distance function.

First claim

What is claimed is:

1 . An apparatus comprising:
ray tracing acceleration hardware to be used to determine ray traversal results when traversing a ray through a bounding volume hierarchy (BVH), the BVH comprising a plurality of axis-aligned bounding boxes (AABBs); and a bounding box (BB) merge accelerator coupled to one or more execution units and coupled to a local memory in which to store a group of AABBs within the plurality of AABBs, the BB merge accelerator, in response to the one or more execution units, to select a second AABB to merge with a first AABB in accordance with a specified distance function, wherein selection of the second AABB from the group of AABBs to merge with the first AABB comprises:
for a first AABB merge candidate within the group of AABBs to merge with the first AABB, looking up a storage location to find a distance between the first AABB and the first AABB merge candidate in accordance with the specified distance function; and
upon the distance between the first AABB and the first AABB merge candidate being found at the storage location, using the distance for the first AABB merge candidate in the selection of the second AABB, and
upon the distance between the first AABB and the first AABB merge candidate not being found at the storage location,
determining and using the distance between the first AABB and the first AABB merge candidate for the first AABB merge candidate in the selection of the second AABB, and
storing the distance at the storage location for a subsequent distance determination with the first AABB being an AABB merge candidate to merge with the first AABB merge candidate.

2 . The apparatus of claim 1 wherein the BB merge accelerator is to determine a distance between the first AABB and each of all other AABBs in the group of AABBs in accordance with the specified distance function, and is to select the second AABB based on the second AABB resulting in the smallest distance to the first AABB.

3 . The apparatus of claim 2 wherein the smallest distance is determined based on the first AABB and the second AABB resulting in a smallest combined area or volume when merged compared to the areas or volumes resulting from merging the first AABB and other AABBs in the group.

4 . The apparatus of claim 2 wherein the BB merge accelerator is to determine the distance from the first AABB in accordance with a radius value, r, indicating a number of AABBs in a negative direction from the first AABB and a number of AABBs in a positive direction from the first AABB.

5 . The apparatus of claim 1 wherein, responsive to identifying the second AABB, the BB merge accelerator is to store an index of the second AABB in an index array.

6 . The apparatus of claim 1 wherein to identify the second AABB as having the smallest distance from the first AABB, the BB merge accelerator is to remove redundant distance operations using temporary distance values resulting from prior distance operations.

7 . The apparatus of claim 6 wherein at least one redundant operation comprises distance(a,b) where distance(b,a) has already been determined and stored as a temporary distance value, and where a comprises the first AABB and b comprises any other AABB in the group of AABBs.

8 . A method comprising:
determining ray traversal results when traversing a ray through a bounding volume hierarchy (BVH), the BVH comprising a plurality of axis-aligned bounding boxes (AABBs); selecting, by a bounding box (BB) merge accelerator coupled to one or more execution units (EUs) and coupled to a local memory, a second AABB from a group of AABBs within the plurality of AABBs to merge with a first AABB stored in the local memory in accordance with a specified distance function, wherein selection of the second AABB from the group of AABBs to merge with the first AABB comprises:
for a first AABB merge candidate within the group of AABBs to merge with the first AABB, looking up a storage location to find a distance between the first AABB and the first AABB merge candidate in accordance with the specified distance function; and
upon the distance between the first AABB and the first AABB merge candidate being found at the storage location, using the distance for the first AABB merge candidate in the selection of the second AABB, and
upon the distance between the first AABB and the first AABB merge candidate not being found at the storage location,
determining and using the distance between the first AABB and the first AABB merge candidate for the first AABB merge candidate in the selection of the second AABB, and
storing the distance at the storage location for a subsequent distance determination with the first AABB being an AABB merge candidate to merge with the first AABB merge candidate.

9 . The method of claim 8 wherein determining a second AABB further comprises:
determining a distance between the first AABB and each of all other AABBs in the group of AABBs in accordance with the specified distance function, and
selecting the second AABB based on the second AABB resulting in the smallest distance to the first AABB.

10 . The method of claim 9 wherein the smallest distance is determined based on the first AABB and the second AABB resulting in the smallest combined area or volume when merged compared to the areas or volumes resulting from merging the first AABB and other AABBs in the group.

11 . The method of claim 9 wherein the distance from the first AABB is determined in accordance with a radius value, r, indicating a number of AABBs in a negative direction from the first AABB and a number of AABBs in a positive direction from the first AABB.

12 . The method of claim 8 wherein, responsive to identifying the second AABB, storing an index of the second AABB in an index array.

13 . The method of claim 8 wherein to identify the second AABB as having the smallest distance from the first AABB, redundant distance operations are removed using temporary distance values resulting from prior distance operations.

14 . The method of claim 13 wherein at least one redundant operation comprises distance(a,b) where distance(b,a) has already been determined and stored as a temporary distance value, and where a comprises the first AABB and b comprises any other AABB in the group of AABBs.

15 . A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform:
determining ray traversal results when traversing a ray through a bounding volume hierarchy (BVH), the BVH comprising a plurality of axis-aligned bounding boxes (AABBs); selecting, by a bounding box (BB) merge accelerator coupled to one or more execution units (EUs) and coupled to a local memory, a second AABB from a group of AABBs within the plurality of AABBs to merge with a first AABB stored in the local memory in accordance with a specified distance function, wherein selection of the second AABB from the group of AABBs to merge with the first AABB comprises:
for a first AABB merge candidate within the group of AABBs to merge with the first AABB, looking up a storage location to find a distance between the first AABB and the first AABB merge candidate in accordance with the specified distance function; and
upon the distance between the first AABB and the first AABB merge candidate being found at the storage location, using the distance for the first AABB merge candidate in the selection of the second AABB, and
upon the distance between the first AABB and the first AABB merge candidate not being found at the storage location,
determining and using the distance bet

Assignees

• Intel Corp

Inventors

• Benthin Carsten
• Drabinski Radoslaw
• Doyle Michael
• Barczak Joshua

Classifications

• G06T2210/12

  Bounding box · CPC title

• G06T17/10

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

• G06T15/08

  Volume rendering · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title