Back to results
US 12,608,881 B2Granted
Formation of bounding volume hierarchies
AssigneeImagination Technologies Limited
InventorJoseph John Davison
Life of this patent
Estimating the term…
Abstract
A method in a graphics processor searches for a candidate reinsertion for each of a plurality of input nodes in a current bounding volume hierarchy (BVH), which would move the respective input node from an old parent to a new parent, and which would reduce the expected computational cost of searching the BVH for a ray intersection; and updates the current BVH with one or more selected reinsertions selected from among the candidates. In the search for candidate reinsertions, either or both of: a) the new parent is limited to being related to the old parent by an ancestor at no more than a predetermined number of hierarchal levels above the old parent, and/or b) the input nodes are limited to being at or above a hierarchical level a predetermined number of hierarchical levels below the root node.
Claims20
A method performed by a graphics processor, the method comprising:
- obtaining a starting bounding volume hierarchy (BVH) modelling an environment at a modelled point in time in the modelled environment, the BVH being a data structure comprising nodes representing different 3D regions of space in the modelled environment, the data structure comprising a tree in which the nodes are arranged hierarchically from a root node down to a plurality of leaf nodes, wherein the region modelled by each leaf node encompasses at least one primitive or part of a primitive;
- performing one or more iterations to the modelling of the environment as at said modelled point in time, starting with a first iteration which starts with the starting BVH as a current BVH, each iteration comprising:
- for each respective one of a plurality of input nodes in the tree of the current BVH, searching for at least one respective candidate reinsertion which would move the respective input node from an old parent to a new parent in the tree, and which compared to the current BVH would reduce an expected computational cost of traversing the tree to determine whether a modelled ray would intersect with one of the primitives, according to a metric for estimating the expected computational cost, and
- performing at least a first update to update the current BVH with one or more selected reinsertions selected from among the candidate reinsertions;
- wherein in the search for candidate reinsertions, either or both of:
- the new parent is limited to being related to the old parent by an ancestor at no more than a predetermined number of hierarchical levels above the old parent in the tree of the current BVH, and/or
- the input nodes are limited to being at or above a hierarchical level in the tree of the current BVH a predetermined number of hierarchical levels below the root node,
- thereby restricting a scope of the searching to a subset of the nodes of the current BVH.
5 more elements
A non-transitory computer readable storage medium having stored thereon computer executable code configured such that when run on a graphics processor causes said graphics processor to perform a method comprising:
- obtaining a starting bounding volume hierarchy (BVH) modelling an environment at a modelled point in time in the modelled environment, the BVH being a data structure comprising nodes representing different 3D regions of space in the modelled environment, the data structure comprising a tree in which the nodes are arranged hierarchically from a root node down to a plurality of leaf nodes, wherein the region modelled by each leaf node encompasses at least one primitive or part of a primitive;
- performing one or more iterations to the modelling of the environment as at said modelled point in time, starting with a first iteration which starts with the starting BVH as a current BVH, each iteration comprising:
- for each respective one of a plurality of input nodes in the tree of the current BVH, searching for at least one respective candidate reinsertion which would move the respective input node from an old parent to a new parent in the tree, and which compared to the current BVH would reduce an expected computational cost of traversing the tree to determine whether a modelled ray would intersect with one of the primitives, according to a metric for estimating the expected computational cost;
- and
- performing at least a first update to update the current BVH with one or more selected reinsertions selected from among the candidate reinsertions;
- wherein in the search for candidate reinsertions, either or both of:
- the new parent is limited to being related to the old parent by an ancestor at no more than a predetermined number of hierarchical levels above the old parent in the tree of the current BVH, and/or
- the input nodes are limited to being at or above a hierarchical level in the tree of the current BVH a predetermined number of hierarchical levels below the root node,
- thereby restricting a scope of the searching to a subset of the nodes of the current BVH.
6 more elements
A graphics processor comprising:
- memory comprising one or more memory units, and
- processing apparatus comprising one or more execution units;
- wherein the memory stores code arranged to run on the processing apparatus, the code being configured when run to cause the processing apparatus to perform a method comprising:
- obtaining a starting bounding volume hierarchy (BVH) modelling an environment at a modelled point in time in the modelled environment, the BVH being a data structure comprising nodes representing different 3D regions of space in the modelled environment, the data structure comprising a tree in which the nodes are arranged hierarchically from a root node down to a plurality of leaf nodes, wherein the region modelled by each leaf node encompasses at least one primitive or part of a primitive;
- performing one or more iterations to the modelling of the environment as at said modelled point in time, starting with a first iteration which starts with the starting BVH as a current BVH, each iteration comprising:
- for each respective one of a plurality of input nodes in the tree of the current BVH, searching for at least one respective candidate reinsertion which would move the respective input node from an old parent to a new parent in the tree, and which compared to the current BVH would reduce an expected computational cost of traversing the tree to determine whether a modelled ray would intersect with one of the primitives, according to a metric for estimating the expected computational cost;
- and
- performing at least a first update to update the current BVH with one or more selected reinsertions selected from among the candidate reinsertions;
- wherein in the search for candidate reinsertions, either or both of:
- the new parent is limited to being related to the old parent by an ancestor at no more than a predetermined number of hierarchical levels above the old parent in the tree of the current BVH, and/or
- the input nodes are limited to being at or above a hierarchical level in the tree of the current BVH a predetermined number of hierarchical levels below the root node,
- thereby restricting a scope of the searching to a subset of the nodes of the current BVH.
9 more elements
Dependencies are inferred from the claim text.