Boundary volume hierarchy generation and traversal for out-of-core rendering of objects part of large 3d model

A computer-implemented method for building a bounding volume hierarchy, wherein the method comprises:

• obtaining, by a computer, a sorted list of a plurality of objects in a three-dimensional, 3D, model of an environment, wherein the sorted list includes the plurality of objects in descending order of sizes;
• determining, by the computer, a root node cut-off diameter based on one or more objects included in the sorted list;
• generating, by the computer, a root node of the bounding volume hierarchy, the root node corresponding to a root node bounding volume enclosing one or more objects that are located in one or more beginning positions of the sorted list, wherein a number of the one or more objects enclosed in the root node bounding volume is dependent on the root node cut-off diameter;
• determining, by the computer, a child node cut-off diameter based on remaining objects in the plurality of objects that are included in the sorted list and that are not enclosed by the root node bounding volume;
• and
• generating, by the computer, one or more child nodes of the root node to be included in the bounding volume hierarchy, wherein each of the one or more child nodes corresponds to a child node bounding volume enclosing one or more objects that is determined from the remaining objects in the plurality of objects in the 3D model based on applying a spatial splitting function, wherein a number of the one or more objects enclosed in each child node bounding volume is dependent on the child node cut-off diameter.

A system comprising:

• one or more computers;
• and
• one or more storage devices communicatively coupled to the one or more computers, wherein the one or more storage devices store instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
• obtaining, by a computer having a display device and a local memory, a bounding volume hierarchy including nodes corresponding to a plurality of objects in a three-dimensional, 3D, model of an environment, wherein the bounding volume hierarchy distributes the plurality of objects into the nodes based on spatial partitioning of the 3D model, and wherein objects of the nodes are ranked in a descending order of sizes from a root node of the bounding volume hierarchy to leaf nodes of the bounding volume hierarchy;
• initiating, by the computer, a queue data structure in the local memory of the computer;
• traversing, by the computer, the bounding volume hierarchy to add one or more nodes of the nodes of the bounding volume hierarchy to the queue data structure, wherein objects of the one or more nodes are to be rendered on the display device of the computer, and wherein the traversing of the bounding volume hierarchy stops when objects of one or more other nodes of the bounding volume hierarchy that are not yet added to the queue data structure (i) are not visible from a current viewpoint for a user within the environment or (ii) have screen space sizes that do not satisfy a predetermined threshold screen space size;
• and
• rendering, by the computer, the objects of the one or more nodes on the display device.

One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

• obtaining, by a computer having a display device and a local memory, a bounding volume hierarchy including nodes corresponding to a plurality of objects in a three-dimensional, 3D, model of an environment, wherein the bounding volume hierarchy distributes the plurality of objects into the nodes based on spatial partitioning of the 3D model, and wherein objects of the nodes are ranked in a descending order of sizes from a root node of the bounding volume hierarchy to leaf nodes of the bounding volume hierarchy;
• initiating, by the computer, a queue data structure in the local memory of the computer;
• traversing, by the computer, the bounding volume hierarchy to add one or more nodes of the nodes of the bounding volume hierarchy to the queue data structure, wherein objects of the one or more nodes are to be rendered on the display device of the computer, and wherein the traversing of the bounding volume hierarchy stops when objects of one or more other nodes of the bounding volume hierarchy that are not yet added to the queue data structure (i) are not visible from a current viewpoint for a user within the environment or (ii) have screen space sizes that do not satisfy a predetermined threshold screen space size;
• and
• rendering, by the computer, the objects of the one or more nodes on the display device.

A system comprising:

• one or more computers;
• and
• one or more storage devices communicatively coupled to the one or more computers, wherein the one or more storage devices store instructions that, when executed by the one or more computers, cause the one or more computers to perform operations for building a bounding volume hierarchy, wherein the operations comprise:
• obtaining, by a computer, a sorted list of a plurality of objects in a three-dimensional, 3D, model of an environment, wherein the sorted list includes the plurality of objects in descending order of sizes;
• determining, by the computer, a root node cut-off diameter based on one or more objects included in the sorted list;
• generating, by the computer, a root node of the bounding volume hierarchy, the root node corresponding to a root node bounding volume enclosing one or more objects that are located in one or more beginning positions of the sorted list, wherein a number of the one or more objects enclosed in the root node bounding volume is dependent on the root node cut-off diameter;
• determining, by the computer, a child node cut-off diameter based on remaining objects in the plurality of objects that are included in the sorted list and that are not enclosed by the root node bounding volume;
• and
• generating, by the computer, one or more child nodes of the root node to be included in the bounding volume hierarchy, wherein each of the one or more child nodes corresponds to a child node bounding volume enclosing one or more objects that is determined from the remaining objects in the plurality of objects in the 3D model based on applying a spatial splitting function, wherein a number of the one or more objects enclosed in each child node bounding volume is dependent on the child node cut-off diameter.

One or more non-transitory computer storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations for building a bounding volume hierarchy, wherein the operations comprise:

• obtaining, by a computer, a sorted list of a plurality of objects in a three-dimensional, 3D, model of an environment, wherein the sorted list includes the plurality of objects in descending order of sizes;
• determining, by the computer, a root node cut-off diameter based on one or more objects included in the sorted list;
• generating, by the computer, a root node of the bounding volume hierarchy, the root node corresponding to a root node bounding volume enclosing one or more objects that are located in one or more beginning positions of the sorted list, wherein a number of the one or more objects enclosed in the root node bounding volume is dependent on the root node cut-off diameter;
• determining, by the computer, a child node cut-off diameter based on remaining objects in the plurality of objects that are included in the sorted list and that are not enclosed by the root node bounding volume;
• and
• generating, by the computer, one or more child nodes of the root node to be included in the bounding volume hierarchy, wherein each of the one or more child nodes corresponds to a child node bounding volume enclosing one or more objects that is determined from the remaining objects in the plurality of objects in the 3D model based on applying a spatial splitting function, wherein a number of the one or more objects enclosed in each child node bounding volume is dependent on the child node cut-off diameter.