IP Library › Granted Patent US 12,488,530
Granted Patent B2
US 12,488,530 · App. 17/699,064 · Granted Dec 2, 2025

Apparatus and method for acceleration data structure re-braiding with camera position

Inventors: Carsten Benthin (Voelklingen, DE); Radoslaw Drabinski (Gdansk, PL); Joshua Barczak (Forest Hill, MD); Sven Woop (Voelklingen, DE); Holger H. Gruen (Bavaria, DE); Pawel Majewski (Rotmanka, PL)
Assignee: Intel Corporation
G06T15/06G06T7/70G06T15/005G06T17/005
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,488,530
App. No.
17/699,064
Granted
Dec 2, 2025
Kind
B2
Abstract

Apparatus and method for camera-aware BVH re-braiding. 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); and BVH processing hardware logic to modify the BVH to reduce spatial overlap between one or more BVH subtrees based on a detected camera position to produce a modified BVH.

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); and

BVH processing hardware logic to modify the BVH to reduce spatial overlap between one or more BVH subtrees based on a plurality of reference points to produce a modified BVH, wherein the plurality of reference points includes:

a detected camera position relative to one or more candidate BVH nodes associated with the one or more BVH subtrees, and

one or more light source locations.

2 . The apparatus of claim 1 wherein the one or more candidate BVH nodes are selected based on corresponding weights assigned to the one or more candidate BVH nodes.

3 . The apparatus of claim 1 wherein the BVH processing hardware logic is to select the one or more candidate BVH nodes associated with the one or more BVH subtrees, and to replace the one or more candidate BVH nodes with a corresponding one or more references to child nodes of the one or more candidate BVH nodes.

4 . The apparatus of claim 3 wherein the BVH processing hardware logic is to select the one or more candidate BVH nodes based on the detected camera position.

5 . The apparatus of claim 4 wherein the one or more candidate BVH nodes are selected based on being in closer proximity to the detected camera position than one or more unselected BVH nodes.

6 . The apparatus of claim 3 wherein the BVH processing hardware logic is to subdivide the one or more BVH subtrees into left and right sub-segments.

7 . The apparatus of claim 6 wherein the BVH processing hardware logic is to perform surface-area heuristic (SAH)-based operations to select a particular hierarchical arrangement of nodes of the one or more BVH subtrees.

8 . The apparatus of claim 7 wherein the SAH-based operations include evaluating surface areas of one or more BVH nodes associated with the one or more BVH subtrees as seen from the detected camera position.

9 . A method comprising:

performing traversal operations on ray tracing acceleration hardware to determine ray traversal results when traversing a ray through a bounding volume hierarchy (BVH); and

modifying the BVH, by BVH processing hardware logic, to reduce spatial overlap between one or more BVH subtrees based on a plurality of reference points to produce a modified BVH, wherein the plurality of reference points includes:

a detected camera position relative to one or more candidate BVH nodes associated with the one or more BVH subtrees, and

one or more light source locations.

10 . The method of claim 9 wherein modifying the BVH further comprises:

selecting the one or more candidate BVH nodes based on corresponding weights assigned to the one or more candidate BVH nodes.

11 . The method of claim 9 wherein modifying the BVH further comprises:

selecting the one or more candidate BVH nodes associated with the one or more BVH subtrees, and

replacing the one or more candidate BVH nodes with a corresponding one or more references to child nodes of the one or more candidate BVH nodes.

12 . The method of claim 11 wherein the one or more candidate BVH nodes are selected based on the detected camera position.

13 . The method of claim 12 wherein the one or more candidate BVH nodes are selected based on being in closer proximity to the detected camera position than one or more unselected BVH nodes.

14 . The method of claim 11 wherein modifying the BVH further comprises:

subdividing the one or more BVH subtrees into left and right sub-segments.

15 . The method of claim 14 further comprising:

performing surface-area heuristic (SAH)-based operations to select a particular hierarchical arrangement of nodes of the one or more BVH subtrees.

16 . The method of claim 15 wherein the SAH-based operations include evaluating surface areas of one or more BVH nodes associated with the one or more BVH subtrees as seen from the detected camera position.

17 . A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform:

performing traversal operations on ray tracing acceleration hardware to determine ray traversal results when traversing a ray through a bounding volume hierarchy (BVH); and

modifying the BVH, by BVH processing hardware logic, to reduce spatial overlap between one or more BVH subtrees based on a plurality of reference points to produce a modified BVH, wherein the plurality of reference points includes:

a detected camera position relative to one or more candidate BVH nodes associated with the one or more BVH subtrees, and

one or more light source locations.

18 . The non-transitory machine-readable medium of claim 17 wherein modifying the BVH further comprises:

selecting the one or more candidate BVH nodes are selected based on corresponding weights assigned to the one or more candidate BVH nodes.

19 . The non-transitory machine-readable medium of claim 17 wherein modifying the BVH further comprises:

selecting one or more candidate BVH nodes associated with the one or more BVH subtrees, and

replacing the one or more candidate BVH nodes with a corresponding one or more references to child nodes of the one or more candidate BVH nodes.

20 . The non-transitory machine-readable medium of claim 19 wherein the one or more candidate BVH nodes are selected based on the detected camera position.

21 . The non-transitory machine-readable medium of claim 20 wherein the one or more candidate BVH nodes are selected based on being in closer proximity to the detected camera position than one or more unselected BVH nodes.

22 . The non-transitory machine-readable medium of claim 19 wherein modifying the BVH further comprises:

subdividing the one or more BVH subtrees into left and right sub-segments.

23 . The non-transitory machine-readable medium of claim 22 further comprising:

performing surface-area heuristic (SAH)-based operations to select a particular hierarchical arrangement of nodes of the one or more BVH subtrees.

24 . The non-transitory machine-readable medium of claim 23 wherein the SAH-based operations include evaluating surface areas of one or more BVH nodes associated with the one or more BVH subtrees as seen from the detected camera position.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 5, 2022
From: BENTHIN, CARSTEN; DRABINSKI, RADOSLAW; BARCZAK, JOSHUA; WOOP, SVEN; GRUEN, HOLGER H.; MAJEWSKI, PAWEL
To: INTEL CORPORATION
Reel/Frame 059610/0364 →
Continuity (1)
Related Publication 20230298255A1 · Sep 21, 2023
References Cited (65)
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 · 2018 [cited by examiner]
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 · 2017 [cited by examiner]
US 20170287202A1 · Wald · 2017 [cited by examiner]
US 20180300939A1 · Benthin · 2018 [cited by examiner]
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]
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]
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 vol. Hierarchy Construction”, IEEE Transactions on Visualization and Computer Graphics, vol. 24, No. 3, Mar. 2018, pp. 1345-1353. [cited by applicant]
Viitanen 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]
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,060, Apr. 24, 2025, 10 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 Psuedo-Random Number Generation of GPU Cards”, Computation, vol. 9, No. 142, 2021, 16 pages. [cited by applicant]
Goda, Takashi, “A Note on Concatenation of Quasi-Monte Carlo 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]
Rotenberg, Steve, “Random Number and Mapping”, UCSD, CSE168: Rendering Algorithms, 2017, 62 pages. [cited by applicant]
Wolfe, A., “Generating Random Numbers from a Specific Distribution with the Metropolis Alorithm (MCMC)”, The Blog at the Bottom of the Sea, May 25, 2019, 24 pages. [cited by applicant]