主权项 |
1. A method for constructing a bounding volume hierarchical structure, comprising:
defining a parent node for the bounding volume hierarchical structure, the parent node including a parent node bounding volume enclosing a plurality of objects; computing, utilizing a processor, an object split cost for performing an object partition of the parent node bounding volume to produce a first plurality of child node bounding volumes; computing a spatial split cost for performing a spatial partitioning of the parent node bounding volume to produce a second plurality of child node bounding volumes by:
identifying a plurality of candidate split planes interesting the parent node bounding volume for spatially partitioning the parent node bounding volume by:
identifying a first candidate split plane along which the parent node bounding volume is partitioned into first and second child node bounding volumes, wherein when the parent node bounding volume is spatially partitioned along the first candidate split plane a particular object traverses the first candidate split plane into each of the first and second child node bounding volumes; andidentifying a second candidate split plane along which the parent node bounding volume is partitioned into third and fourth child node bounding volumes, wherein when the parent node bounding volume is spatially partitioned along the second candidate split plane the particular object is completely included in the third child node bounding volume and does not extend into the fourth child node bounding volume;computing a plurality of candidate costs, each candidate cost corresponding to a cost for performing a spatial partition of the parent node bounding volume along a respective one of the plurality of candidate split planes, by computing first and second candidate costs for performing a spatial partitioning of the parent node bounding volume along each of the first and second candidate split planes, respectively; anddetermining the lowest of the plurality of candidate costs as the spatial split cost by determining the lowest of the first and the second candidate costs, wherein the lowest candidate cost has one of the plurality of candidate split planes associated therewith; and constructing the bounding volume hierarchical structure implementing the second plurality of child node bounding volumes produced from the spatial partitioning of the parent node bounding volume if the second cost is lower than the first cost, wherein constructing the bounding volume hierarchical structure comprises implementing the plurality of child node bounding volumes which are produced from the spatial partitioning along the one of the plurality of candidate split planes associated with the lowest candidate cost. |