Apparatus and method for bounding volume hierarchy (BVH) construction with stochastic processing

Patent metadata

Field	Value
Publication number	US-12548255-B2
Application number	US-202217852216-A
Country	US
Kind code	B2
Filing date	Jun 28, 2022
Priority date	May 18, 2022
Publication date	Feb 10, 2026
Grant date	Feb 10, 2026

Abstract

A method and apparatus for efficiently constructing a bounding volume hierarchy (BVH). For example, one embodiment of an apparatus comprises: a primitive sampler to identify a representative subset of input primitives of a graphics scene; bounding volume hierarchy (BVH) builder hardware logic to construct an approximate BVH based on the representative subset of input primitives; hardware logic to insert input primitives not in the representative subset into leaves of the approximate BVH; and the BVH builder or a different BVH builder to construct a final BVH based on the primitives inserted into the leaves of the approximate BVH.

First claim

We claim:

1 . An apparatus comprising:
sampler circuitry to identify a representative subset of input primitives of a graphics scene for bounding volume hierarchy (BVH) construction; BVH builder circuitry to construct an approximate BVH based on the representative subset of input primitives; circuitry to insert input primitives not in the representative subset into leaves of the approximate BVH; and the BVH builder circuitry or a different BVH builder circuitry to construct a final BVH based on the primitives inserted into the leaves of the approximate BVH.

2 . The apparatus of claim 1 wherein the sampler circuitry is to perform stochastic importance sampling to identify the representative subset of input primitives.

3 . The apparatus of claim 2 wherein selection of the subset of input primitives is biased to primitives that have a greater influence on the approximate BVH.

4 . The apparatus of claim 3 wherein relatively larger primitives are biased to be selected over relatively smaller primitives.

5 . The apparatus of claim 4 wherein a Cumulative Density Function (CDF) is implemented to identify the subset of input primitives.

6 . The apparatus of claim 1 wherein the BVH builder circuitry or the different BVH builder circuitry is to operate in parallel on the leaves after the input primitives not in the representative subset are inserted to construct the final BVH.

7 . The apparatus of claim 1 further comprising:
compression circuitry to perform compression and/or quantization on nodes of the final BVH to generate a compressed final BVH.

8 . The apparatus of claim 1 further comprising:
traversal circuitry to traverse a ray through the final BVH; and
intersection circuitry to identify intersections between the ray and one or more of the input primitives.

9 . A method comprising:
sampling input primitives of a graphics scene to identify a representative subset of the input primitives for bounding volume hierarchy (BVH) construction; constructing an approximate BVH based on the representative subset of input primitives; inserting input primitives not in the representative subset into leaves of the approximate BVH; and constructing a final BVH based on the primitives inserted into the leaves of the approximate BVH.

10 . The method of claim 9 wherein sampling input primitives further comprises performing stochastic importance sampling to identify the representative subset of input primitives.

11 . The method of claim 10 selection of the subset of input primitives is biased to primitives that have a greater influence on the approximate BVH.

12 . The method of claim 11 wherein relatively larger primitives are biased to be selected over relatively smaller primitives.

13 . The method of claim 12 wherein a Cumulative Density Function (CDF) is implemented to identify the subset of input primitives.

14 . The method of claim 9 wherein constructing the final BVH further comprises operating in parallel on the leaves after the input primitives not in the representative subset are inserted.

15 . The method of claim 9 further comprising:
performing compression and/or quantization on nodes of the final BVH to generate a compressed final BVH.

16 . The method of claim 9 further comprising:
traversing a ray through the final BVH; and
identifying intersections between the ray and one or more of the input primitives.

17 . A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform:
sampling input primitives of a graphics scene to identify a representative subset of the input primitives for bounding volume hierarchy (BVH) construction; constructing an approximate BVH based on the representative subset of input primitives; inserting input primitives not in the representative subset into leaves of the approximate BVH; and constructing a final BVH based on the primitives inserted into the leaves of the approximate BVH.

18 . The non-transitory machine-readable medium of claim 17 wherein sampling input primitives further comprises performing stochastic importance sampling to identify the representative subset of input primitives.

19 . The non-transitory machine-readable medium of claim 18 selection of the subset of input primitives is biased to primitives that have a greater influence on the approximate BVH.

20 . The non-transitory machine-readable medium of claim 19 wherein relatively larger primitives are biased to be selected over relatively smaller primitives.

21 . The non-transitory machine-readable medium of claim 20 wherein a Cumulative Density Function (CDF) is implemented to identify the subset of input primitives.

22 . The non-transitory machine-readable medium of claim 17 wherein constructing the final BVH further comprises operating in parallel on the leaves after the input primitives not in the representative subset are inserted.

23 . The non-transitory machine-readable medium of claim 17 further comprising program code to cause the machine to perform:
performing compression and/or quantization on nodes of the final BVH to generate a compressed final BVH.

24 . The non-transitory machine-readable medium of claim 17 further comprising program code to cause the machine to perform:
traversing a ray through the final BVH; and
identifying intersections between the ray and one or more of the input primitives.

Assignees

• Intel Corp

Inventors

• Tessari Lorenzo
• Dittebrandt Addis
• Doyle Michael
• Benthin Carsten

Classifications

• 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

• G06T17/20 Primary

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title