Patent ID: 8471845
Filing Date: 2013-06-25
Classification: G06T

Abstract:
1. A method for constructing a bounding volume hierarchical structure, comprising; defining, utilizing at least one processor, a parent node for a bounding volume hierarchical structure, the parent node including a parent node bounding volume enclosing a plurality of objects; computing, utilizing the at least one processor, a first cost for performing an object partition of the parent node bounding volume to produce a first plurality of child node bounding volumes; computing, utilizing the at least one processor, a second cost for performing a spatial partitioning of the parent node bounding volume to produce a second plurality of child node bounding volumes; and constructing, utilizing the at least one processor, 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 computing the second cost for performing the spatial partitioning of the parent node bounding volume comprises: wherein constructing the bounding volume hierarchical structure comprises constructing the bounding volume hierarchical structure implementing a plurality of child node bounding volumes which are produced from the spatial partition along the candidate split plane associated with the lowest candidate cost; wherein identifying the plurality of candidate planes includes: wherein computing the plurality of candidate costs comprises 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; and wherein determining the lowest of the plurality of candidate costs as the second cost comprises determining the lowest of the first and second candidate costs.