Technique for generating a bounding volume hierarchy
A technique for building a bounding volume hierarchy is disclosed. The technique subdividing a candidate box node based on a resolution to generate a plurality of cells of the candidate box node; identifying a plurality of nodes of a triangle set collection that fit within the cells; generating a plurality of candidate splits based on the plurality of nodes; selecting a candidate split based on a selection criterion to obtain a selected candidate split; and generating child box nodes for a box node of a bounding volume hierarchy under construction, based on the selected candidate split.
1 . A method of building a bounding volume hierarchy, the method comprising:
generating a primitive set collection that includes an initial bounding volume hierarchy (“BVH”) that defines a plurality of nodes, each having bounding volume that bound corresponding one or more primitives, each node defining a centroid box that bounds the centroids of the corresponding one or more primitives;
subdividing a candidate box node for a BVH under construction based on a resolution to generate a plurality of cells of the candidate box node; and
generating child box nodes for a box node of the BVH under construction, based on a selected candidate split, which is selected from among a plurality of candidate splits that split the cells of the plurality of cells, wherein each cell bounds a set of highest nodes of the initial BVH whose centroid boxes fit within the cell.
2 . The method of claim 1 , wherein the resolution indicates a number of cells into which to subdivide the candidate box node.
3 . The method of claim 1 , further comprising identifying the highest nodes that fit within the cells, including identifying nodes whose centroid boxes fit within a single cell of the cells of the candidate box node.
4 . The method of claim 3 , wherein the centroid boxes comprise boxes that bound centroids of primitives of a node.
5 . The method of claim 1 , further comprising generating the plurality of candidate splits by splitting a bounding volume of the candidate box node based on a boundary aligned with the plurality of cells.
6 . The method of claim 1 , further comprising selecting the candidate split by evaluating a plurality of candidate splits according to a selection criterion and selecting one of the candidate splits.
7 . The method of claim 6 , wherein the selection criterion is a lowest total bounding box surface area criterion.
8 . The method of claim 6 , wherein generating the child box nodes comprises generating a child box node for each side of the selected candidate split, where each child box node has a bounding box that bounds each primitive of a side corresponding to the child box node.
9 . The method of claim 1 , further comprising repeating the generating the primitive set collection, the subdividing, and the generating the child box nodes for multiple box nodes of a bounding volume hierarchy under construction.
10 . A system of building a bounding volume hierarchy, the system comprising:
a memory configured to store a bounding volume hierarchy; and
a bounding volume hierarchy builder configured to build the bounding volume hierarchy, by performing operations including:
generating a primitive set collection that includes an initial bounding volume hierarchy that defines a plurality of nodes, each having bounding volumes that bound corresponding one or more primitives, each node defining a centroid box that bounds the centroids of the corresponding one or more primitives;
subdividing a candidate box node for the bounding volume hierarchy based on a resolution to generate a plurality of cells of the candidate box node; and
generating child box nodes for a box node of the bounding volume hierarchy under construction, based on a selected candidate split, which is selected from among a plurality of candidate splits that split the cells of the plurality of cells, wherein each cell bounds a set of highest nodes of the initial BVH whose centroid boxes fit within the cell.
11 . The system of claim 10 , wherein the resolution indicates a number of cells into which to subdivide the candidate box node.
12 . The system of claim 10 , the operations further include identifying the highest nodes that fit within the cells including identifying nodes whose centroid boxes fit within a single cell of the cells of the candidate box node.
13 . The system of claim 12 , wherein the centroid boxes comprise boxes that bound centroids of primitives of a node.
14 . The system of claim 10 , wherein the operations further include generating the plurality of candidate splits by splitting a bounding volume of the candidate box node based on a boundary aligned with the plurality of cells.
15 . The system of claim 10 , wherein the operations further include selecting the candidate split by evaluating a plurality of candidate splits according to a selection criterion and selecting one of the candidate splits.
16 . The system of claim 15 , wherein the selection criterion is a lowest total bounding box surface area criterion.
17 . The system of claim 15 , wherein generating the child box nodes comprises generating a child box node for each side of the selected candidate split, where each child box node has a bounding box that bounds each primitive of a side corresponding to the child box node.
18 . The system of claim 10 , wherein the bounding volume hierarchy builder is further configured to repeat the generating the primitive set collection, the subdividing, and the generating the child box nodes for multiple box nodes of a bounding volume hierarchy under construction.
19 . A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform operations comprising:
generating a primitive set collection that includes an initial bounding volume hierarchy that defines a plurality of nodes, each having bounding volumes that bound corresponding one or more primitives, each node defining a centroid box that bounds the centroids of the corresponding one or more primitives;
subdividing a candidate box node for a BVH under construction based on a resolution to generate a plurality of cells of the candidate box node; and
generating child box nodes for a box node of the BVH under construction, based on a selected candidate split, which is selected from among a plurality of candidate splits that split the cells of the plurality of cells, wherein each cell bounds a set of highest nodes of the initial BVH whose centroid boxes fit within the cell.
20 . The non-transitory computer-readable medium of claim 19 , wherein the resolution indicates a number of cells into which to subdivide the candidate box node.