# US 12,602,403 B2 · Scalable parallel construction of bounding volume hierarchies > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,403 B2 - Document ID: US12602403B2 - Status: Granted - Kind: B2 - Application number: 17/669,293 - Filed: 2022-02-10 - Published: 2023-04-20 - Granted: 2026-04-14 - Earliest claimed: 2021-10-18 - Assignees: NVIDIA Corporation - Applicants: Nvidia Corporation - Inventors: Ingo Wald - Web page: https://patentgrep.com/patent/US12602403B2 ## CPC - G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning} - G06F 16/24554: {Unary operations; Data partitioning operations} - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - G06T 2210/12: Bounding box - G06T 2210/21: Collision detection, intersection - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract One embodiment of the present invention sets forth a technique for generating a bounding volume hierarchy. The technique includes determining a first set of objects associated with a first node. The technique also includes generating a first plurality of child nodes that are associated with the first node. The technique further includes for each object included in the first set of objects, storing within the object an identifier for a corresponding child node included in the first plurality of child nodes based on a first set of partitions associated with the first set of objects. ## Claims ### Claim 1 A computer-implemented method for generating a bounding volume hierarchy, the method comprising: determining a first set of objects represented by a first node of the bounding volume hierarchy, wherein each object included in the first set of objects stores a first identifier for the first node and comprises a graphics element of a graphics scene, wherein the first node represents a first bounding volume; in response to determining that the first node is not a leaf node of the bounding volume hierarchy, generating a first set of partitions that divides the first bounding volume into a plurality of new bounding volumes; generating a first plurality of child nodes of the first node for representing the plurality of new bounding volumes; for a first object included in the first set of objects, changing the first identifier stored within the first object to a second identifier for a corresponding first child node included in the first plurality of child nodes that represents a first new bounding volume in the plurality of new bounding volumes that includes the first object; and performing one or more graphics processing operations based on the second identifier stored within the first object included in the first set of objects. ### Claim 2 (depends on 1) The computer-implemented method of claim 1, further comprising determining the first set of partitions based on one or more partitioning criteria. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, further comprising: generating a second set of partitions associated with the first plurality of child nodes; and generating a second plurality of child nodes based on the second set of partitions, wherein each child node included in the second plurality of child nodes is associated with a corresponding parent node that is included in the first plurality of child nodes. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, further comprising: generating a second plurality of child nodes, wherein each child node included in the second plurality of child nodes is associated with a corresponding parent node that is included in the first plurality of child nodes; generating a first set of bounding volumes for the second plurality of child nodes; and for each parent node included in the first plurality of child nodes, generating a bounding volume for the parent node based on two or more bounding volumes for two or more child nodes of the parent node. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, further comprising converting a second node included in the first plurality of child nodes into a leaf node based on one or more leaf node criteria. ### Claim 6 (depends on 5) The computer-implemented method of claim 5, wherein the one or more leaf node criteria comprise a threshold for a number of objects assigned to the second node. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, further comprising storing a list of objects assigned to a second node included in the first plurality of child nodes based on a first counter that stores a number of objects assigned to the second node and a second counter that stores a total number of objects that have been assigned to leaf nodes. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, wherein determining the first set of objects represented by the first node comprises determining that the first identifier for the first node is stored within each object included in the first set of objects. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, further comprising executing a plurality of parallel operations to determine the first set of partitions. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, wherein the first set of partitions comprises a split plane. ### Claim 11 (depends on 1) The computer-implemented method of claim 1, further comprising, prior to changing the first identifier stored within the first object to the second identifier, reassigning the first object included in the first set of objects from the first node to the first child node. ### Claim 12 (depends on 11) The computer-implemented method of claim 11, wherein the first object included in the first set of objects is reassigned from the first node to the first child node without allocating, storing, or maintaining an object list associated with at least one of the first node or the first child node. ### Claim 13 One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause the one or more processors to perform the steps of: determining a first set of objects represented by a first node of a bounding volume hierarchy, wherein each object included in the first set of objects stores a first identifier for the first node and comprises a graphics element of a graphics scene, wherein the first node represents a first bounding volume; in response to determining that the first node is not a leaf node of the bounding volume hierarchy, generating a first set of partitions that divides the first bounding volume into a plurality of new bounding volumes; generating a first plurality of child nodes of the first node for representing the plurality of new bounding volumes; for a first object included in the first set of objects, changing the first identifier stored within the first object to a second identifier for a corresponding first child node included in the first plurality of child nodes that represents a first new bounding volume in the plurality of new bounding volumes that includes the first object; and performing one or more graphics processing operations based on the second identifier stored within the first object included in the first set of objects. ### Claim 14 (depends on 13) The one or more non-transitory computer-readable media of claim 13, wherein the instructions further cause the one or more processors to perform the steps of: creating the first node as a root node associated with the bounding volume hierarchy; and storing the first identifier for the first node within the first set of objects prior to determining that the first set of objects is associated with the first node. ### Claim 15 (depends on 13) The one or more non-transitory computer-readable media of claim 13, wherein the instructions further cause the one or more processors to perform the steps of: determining that a second object is invalid; and storing an indicator that the second object should not be assigned to the first node. ### Claim 16 (depends on 13) The one or more non-transitory computer-readable media of claim 13, wherein the instructions further cause the one or more processors to perform the steps of: executing a plurality of parallel operations to generate a second set of partitions associated with the first plurality of child nodes; and generating a second plurality of child nodes based on the second set of partitions, wherein each child node included in the second plurality of child nodes is associated with a corresponding parent node that is included in the first plurality of child nodes. ### Claim 17 (depends on 13) The one or more non-transitory computer-readable media of claim 13, wherein the instructions further cause the one or more processors to perform the step of converting a second node included in the first plurality of child nodes into a leaf node based on one or more leaf node criteria. ### Claim 18 (depends on 17) The one or more non-transitory computer-readable media of claim 17, wherein the instructions further cause the one or more processors to perform the steps of: determining a second set of objects associated with the second node; and for each object included in the second set of objects, storing an indicator that the object does not need to be reassigned. ### Claim 19 (depends on 13) The one or more non-transitory computer-readable media of claim 13, wherein storing within the first object the second identifier for the corresponding first child node comprises determining the corresponding first child node based on a representative point for the first object and the first new bounding volume represented by the corresponding first child node. ### Claim 20 (depends on 13) The one or more non-transitory computer-readable media of claim 13, wherein the instructions further cause the one or more processors to perform the step of executing a plurality of parallel operations to determine the first set of partitions. ### Claim 21 (depends on 13) The one or more non-transitory computer-readable media of claim 13, wherein the first set of objects comprises at least one of a point, a line, a triangle, or a polygon. ### Claim 22 A system, comprising: one or more memories that store instructions, and one or more processors that are coupled to the one or more memories and, when executing the instructions, are configured to: determine a first set of objects represented by a first node of the bounding volume hierarchy, wherein each object included in the first set of objects stores a first identifier for the first node and comprises a graphics element of a graphics scene, wherein the first node represents a first bounding volume; in response to determining that the first node is not a leaf node of the bounding volume hierarchy, generate a first set of partitions that divides the first bounding volume into a plurality of new bounding volumes; generate a first plurality of child nodes of the first node for representing the plurality of new bounding volumes; for a first object included in the first set of objects, change the first identifier stored within the first object to a second identifier for a corresponding first child node included in the first plurality of child nodes that represents a first new bounding volume in the plurality of new bounding volumes that includes the first object; and perform one or more graphics processing operations based on the second identifier stored within the first object included in the first set of objects.