Apparatus and method for efficiently merging bounding volume hierarchy data

Patent metadata

Field	Value
Publication number	US-11989818-B2
Application number	US-202117533531-A
Country	US
Kind code	B2
Filing date	Nov 23, 2021
Priority date	Apr 14, 2017
Publication date	May 21, 2024
Grant date	May 21, 2024

Abstract

An apparatus and method for efficiently reconstructing a BVH. For example, one embodiment of a method comprises: constructing an object bounding volume hierarchy (BVH) for each object in a scene, each object BVH including a root node and one or more child nodes based on primitives included in each object; constructing a top-level BVH using the root nodes of the individual object BVHs; performing an analysis of the top-level BVH to determine whether the top-level BVH comprises a sufficiently efficient arrangement of nodes within its hierarchy; and reconstructing at least a portion of the top-level BVH if a more efficient arrangement of nodes exists, wherein reconstructing comprises rebuilding the portion of the top-level BVH until one or more stopping criteria have been met, the stopping criteria defined to prevent an entire rebuilding of the top-level BVH.

First claim

What is claimed is:

1. A graphics processing apparatus comprising:
a hierarchical tree structure construction circuitry to:
construct a top-level tree structure using root nodes of individual object tree structures, wherein an individual object tree structure of the individual object tree structures includes a root node and one or more child nodes and is built based on primitives included in a corresponding object, and
reconstruct build primitives within at least a portion of the top-level tree structure, wherein reconstructing the build primitives comprises:
iteratively selecting a plurality of build primitives from the portion of the top-level tree structure to split into a plurality of two subsets of build primitives for reconstruction, wherein in a first iteration of the iterative selection for reconstruction, a first pair of two subsets of build primitives is not reconstructed responsive to the first pair of two subsets of build primitives belonging to a same object.

2. The graphics processing apparatus of claim 1 , further comprising:
an intersection circuitry to intersect rays with the portion of the top-level tree structure upon reconstruction of the build primitives.

3. The graphics processing apparatus of claim 1 , wherein the portion of the top-level tree structure is selected from an upper hierarchy of the top-level tree structure.

4. The graphics processing apparatus of claim 1 , wherein reconstruction of the build primitives completes once a single primitive is left in the portion of the top-level tree structure upon the iterative selection.

5. The graphics processing apparatus of claim 1 , wherein the iterative selection further comprises constructing a second pair of two subsets of build primitives in a second iteration of the iterative selection for reconstruction, wherein in the second iteration a parent node within the individual object tree structure is replaced by child nodes of the parent node to create a new set of build primitives.

6. The graphics processing apparatus of claim 5 , wherein the new set of build primitives is split into two subsets, wherein a split position is selected based on a surface area heuristic cost calculation.

7. The graphics processing apparatus of claim 5 , wherein a weight of the parent node is distributed among its child nodes when the parent node is replaced by its child nodes.

8. The graphics processing apparatus of claim 7 , wherein the weight of the parent node is based on how many primitives are included in the parent node.

9. A method comprising:
constructing a top-level tree structure using root nodes of individual object tree structures, wherein an individual object tree structure of the individual object tree structures includes a root node and one or more child nodes and is built based on primitives included in a corresponding object; and
reconstructing build primitives within at least a portion of the top-level tree structure, wherein reconstructing the build primitives comprises:
iteratively selecting a plurality of build primitives from the portion of the top-level tree structure to split into a plurality of two subsets of build primitives for reconstruction, wherein in a first iteration of the iterative selection for reconstruction, a first pair of two subsets of build primitives is not reconstructed responsive to the first pair of two subsets of build primitives belonging to a same object, wherein the iterative selection comprises not reconstructing a first pair of two subsets of build primitives responsive to the first pair of two subsets of build primitives belonging to a same object in a first iteration.

10. The method of claim 9 , further comprising:
intersecting rays with the portion of the top-level tree structure upon reconstruction of the build primitives.

11. The method of claim 9 , wherein the portion of the top-level tree structure is selected from an upper hierarchy of the top-level tree structure.

12. The method of claim 9 , wherein reconstruction of the build primitives completes once a single primitive is left in the portion of the top-level tree structure upon the iterative selection.

13. The method of claim 9 , wherein the iterative selection further comprises constructing a second pair of two subsets of build primitives in a second iteration of the iterative selection for reconstruction, wherein in the second iteration a parent node within the individual object tree structure is replaced by child nodes of the parent node to create a new set of build primitives.

14. A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, are capable of causing the machine to perform:
constructing a top-level tree structure using root nodes of individual object tree structures, wherein an individual object tree structure of the individual object tree structures includes a root node and one or more child nodes and is built based on primitives included in a corresponding object; and
reconstructing build primitives within at least a portion of the top-level tree structure, wherein reconstructing the build primitives comprises:
iteratively selecting a plurality of build primitives from the portion of the top-level tree structure to split into a plurality of two subsets of build primitives for reconstruction, wherein in a first iteration of the iterative selection for reconstruction, a first pair of two subsets of build primitives is not reconstructed responsive to the first pair of two subsets of build primitives belonging to a same object, wherein the iterative selection comprises not reconstructing a first pair of two subsets of build primitives responsive to the first pair of two subsets of build primitives belonging to a same object in a first iteration.

15. The non-transitory machine-readable medium of claim 14 , wherein the portion of the top-level tree structure is selected from an upper hierarchy of the top-level tree structure.

16. The non-transitory machine-readable medium of claim 14 , wherein reconstruction of the build primitives completes once a single primitive is left in the portion of the top-level tree structure upon the iterative selection.

17. The non-transitory machine-readable medium of claim 14 , wherein the iterative selection further comprises constructing a second pair of two subsets of build primitives in a second iteration of the iterative selection for reconstruction, wherein in the second iteration a parent node within the individual object tree structure is replaced by child nodes of the parent node to create a new set of build primitives.

18. The non-transitory machine-readable medium of claim 17 , wherein the new set of build primitives is split into two subsets, wherein a split position is selected based on a surface area heuristic cost calculation.

19. The non-transitory machine-readable medium of claim 17 , wherein a weight of the parent node is distributed among its child nodes when the parent node is replaced by its child nodes.

20. The non-transitory machine-readable medium of claim 19 , wherein the weight of the parent node is based on how many primitives are included in the parent node.

Assignees

• Intel Corp

Inventors

• Benthin Carsten
• Woop Sven

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T17/00

  Three-dimensional [3D] modelling for computer graphics · CPC title