IP Library › Granted Patent US 12,499,606
Granted Patent B2
US 12,499,606 · App. 17/699,060 · Granted Dec 16, 2025

Apparatus and method for accelerating BVH builds by merging bounding boxes

Inventors: Carsten Benthin (Völklingen, DE); Radoslaw Drabinski (Gdansk, PL); Michael Doyle (San Jose, CA); Joshua Barczak (Forest Hill, MD)
Assignee: Intel Corporation
G06T15/06G06T15/08G06T17/10G06T2210/12
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,499,606
App. No.
17/699,060
Granted
Dec 16, 2025
Kind
B2
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.

Claims (46)

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

16 . The non-transitory machine-readable medium of claim 15 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.

17 . The non-transitory machine-readable medium of claim 16 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.

18 . The non-transitory machine-readable medium of claim 16 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.

19 . The non-transitory machine-readable medium of claim 15 wherein, responsive to identifying the second AABB, storing an index of the second AABB in an index array.

20 . The non-transitory machine-readable medium of claim 15 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.

21 . The non-transitory machine-readable medium of claim 20 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.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 26, 2022
From: BENTHIN, CARSTEN; DRABINSKI, RADOSLAW; DOYLE, MICHAEL; BARCZAK, JOSHUA
To: INTEL CORPORATION
Reel/Frame 059740/0546 →
Continuity (1)
Related Publication 20230298254A1 · Sep 21, 2023
References Cited (67)
US 4942521A · Hanawa et al. · 1990 [cited by applicant]
US 6742102B2 · Sasahara · 2004 [cited by applicant]
US 6826636B2 · Liang · 2004 [cited by applicant]
US 7028159B2 · Matsubara et al. · 2006 [cited by applicant]
US 8289324B1 · Laine et al. · 2012 [cited by applicant]
US 8392669B1 · Nyland et al. · 2013 [cited by applicant]
US 8836702B2 · Yoon et al. · 2014 [cited by applicant]
US 9264265B1 · Wei · 2016 [cited by applicant]
US 9275494B2 · Lee et al. · 2016 [cited by applicant]
US 9418012B2 · De et al. · 2016 [cited by applicant]
US 9728000B2 · Lee et al. · 2017 [cited by applicant]
US 9965888B2 · Shin et al. · 2018 [cited by applicant]
US 9965889B2 · Hur et al. · 2018 [cited by applicant]
US 10019832B2 · Park et al. · 2018 [cited by applicant]
US 10043235B2 · Kim et al. · 2018 [cited by applicant]
US 10049488B2 · Lee et al. · 2018 [cited by applicant]
US 10115224B2 · Shin et al. · 2018 [cited by applicant]
US 10275358B2 · Lin · 2019 [cited by applicant]
US 10839475B2 · Benthin et al. · 2020 [cited by applicant]
US 11086781B2 · Bondarenko et al. · 2021 [cited by applicant]
US 11087522B1 · Surti et al. · 2021 [cited by applicant]
US 11321910B2 · Doyle et al. · 2022 [cited by applicant]
US 11403225B2 · Zheng et al. · 2022 [cited by applicant]
US 20140244968A1 · Greyzck et al. · 2014 [cited by applicant]
US 20140347355A1 · Yoon · 2014 [cited by applicant]
US 20170116775A1 · Shin et al. · 2017 [cited by applicant]
US 20170287202A1 · Wald et al. · 2017 [cited by applicant]
US 20180300939A1 · Benthin et al. · 2018 [cited by applicant]
US 20180307981A1 · Cilingir et al. · 2018 [cited by applicant]
US 20180315159A1 · Ould-Ahmed-Vall et al. · 2018 [cited by applicant]
US 20190377580A1 · Vorbach et al. · 2019 [cited by applicant]
US 20200159676A1 · Durham et al. · 2020 [cited by applicant]
US 20200211151A1 · Vaidyanathan et al. · 2020 [cited by applicant]
US 20200401376A1 · Najafi et al. · 2020 [cited by applicant]
US 20210311992A1 · Heller · 2021 [cited by applicant]
US 20210390760A1 · Muthler et al. · 2021 [cited by applicant]
US 20220051476A1 · Woop et al. · 2022 [cited by applicant]
US 20230206543A1 · Shkurko et al. · 2023 [cited by applicant]
Viitanen, Timo, et al. “PLOCTree: A fast, high-quality hardware BVH builder.” Proceedings of the ACM on Computer Graphics and Interactive Techniques 1.2 (2018): 1-19. (Year: 2018). [cited by examiner]
Benthin et al., “PLOC++ : Parallel Locally-Ordered Clustering for Bounding vol. Hierarchy Construction Revisited”, Pro. ACM Comput. Graph. Interact. Tech., vol. 5, No. 3, Article 31, Jul. 2022, 13 pages. [cited by applicant]
European Search Report and Search Opinion, EP App. No. 23155478.3, Jun. 16, 2023, 8 pages. [cited by applicant]
Meister et al., “Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction”, IEEE Transactions on Visualization and Computer Graphics, vol. 24, No. 3, Mar. 2018, pp. 1345-1353. [cited by applicant]
Mitanen et al., “PLOCTree: A Fast, High-Quality Hardware BVH Builder”, Proc. ACM Comput. Graph. Interact. Tech., vol. 1, No. 2, Article 35, Aug. 2018, pp. 35:1-35:19. [cited by applicant]
Benthin et al., “Improved Two-Level BVHs using Partial Re-Braiding”, ACM, 2017, 8 pages. [cited by applicant]
Burley et al., “The Design and Evolution of Disney's Hyperion Renderer”, vol. 37, No. 3, Article 33, ACM Transactions on Graphics, Jul. 2018, 22 pages. [cited by applicant]
European Search Report and Search Opinion, EP App. No. 23151144.5, Jun. 12, 2023, 10 pages. [cited by applicant]
European Search Report and Search Opinion, EP App. No. 23157180.3, Jun. 30, 2023, 12 pages. [cited by applicant]
Hu, Y., et al., “Parallel BVH Construction Using Locally Density Clustering”, Digital Object Identifier, IEEE Access, vol. 7, Jan. 1, 2019, pp. 105827-105839. [cited by applicant]
Intention to Grant, EP App. No. 23157180.3, Mar. 31, 2025, 6 pages. [cited by applicant]
Laine, “Restart Trail for Stackless BVH Traversal”, High Performance Graphics, The Eurographics Association 2010, 2010, 5 pages. [cited by applicant]
Lloyd et al., “Implementing Stochastic Levels of Detail with Microsoft DirectX Raytracing”, Nvidia Developer, available online at <https://developer.nvidia.com/blog/implementing-stochastic-lod-with-microsoft-dxr/>, Jun.… [cited by applicant]
Non-Final Office Action, U.S. Appl. No. 17/699,058, Apr. 10, 2025, 6 pages. [cited by applicant]
Non-Final Office Action, U.S. Appl. No. 17/699,059, Jun. 2, 2025, 9 pages. [cited by applicant]
Non-Final Office Action, U.S. Appl. No. 17/699,064, Apr. 22, 2025, 15 pages. [cited by applicant]
Non-Final Office Action, U.S. Appl. No. 17/699,066, May 19, 2025, 11 pages. [cited by applicant]
Non-Final Office Action, U.S. Appl. No. 17/699,067, May 8, 2025, 26 pages. [cited by applicant]
Office Action, EP App. No. 23151144.5, Mar. 14, 2025, 8 pages. [cited by applicant]
Office Action, EP App. No. 23155478.3, Mar. 17, 2025, 7 pages. [cited by applicant]
Shi et al., “A Digital Rights Enabled Graphics Processing System”, Graphics Hardware, 2006, 10 pages. [cited by applicant]
Tzeng et al., “Parallel White Noise Generation on a GPU via Cryptographic Hash”, I3D, Microsoft Research, 2007, pp. 79-88. [cited by applicant]
Vaidyanathan et al., “Wide BVH Traversal with a Short Stack”, Intel Corporation, 2019, 5 pages. [cited by applicant]
Askar et al., “Evaluation of Pseudo-Random Number Generation on GPU Cards”, Computation, vol. 9, No. 142, 2021, 16 pages. [cited by applicant]
Goda, Takashi, “A Note on Concatenation of Quasi-Monte Carlo and Plain Monte Carlo Rule in High Dimensions”, arXiv:2106.12184v4, Jan. 7, 2022, 13 pages. [cited by applicant]
Non-Final Office Action, U.S. Appl. No. 17/699,063, Aug. 7, 2025, 13 pages. [cited by applicant]
Notice of Allowance, U.S. Appl. No. 17/699,064, Aug. 8, 2025, 8 pages. [cited by applicant]
Rotenberg, Steve, “Random Numbers and Mapping”, UCSD, CSE168: Rendering Algorithms, 2017, 62 pages. [cited by applicant]
Wolfe, A., “Generating Random Numbers from a Specific Distribution with the Metropolis Algorithm (MCMC)”, The Blog at the Bottom of the Sea, May 25, 2019, 24 pages. [cited by applicant]