Formation of bounding volume hierarchies

1 . A method performed by a graphics processor, the method comprising:

obtaining a starting bounding volume hierarchy (BVH), being a data structure comprising nodes representing different 3D regions of space in a 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, starting with a first iteration which starts with the starting BVH as a current BVH, each iteration comprising:

for each of a plurality of input nodes in the tree of the current BVH, searching for one or more candidate reinsertions which would move the input node from a respective old parent to a respective new parent in the tree, and which compared to the current BVH would reduce an expected computational cost of searching the tree to determine whether a modelled ray would intersect with one of the primitives; and

updating the current BVH with one or more selected reinsertions from among the candidate reinsertions;

wherein in the updating step of at least one of the iterations, the one or more selected reinsertions include at least one reinsertion that gives the new parent more than two children;

wherein the graphics processor comprises a buffer comprising a plurality of slots, each respective one of the nodes in the tree being represented as an entry in a respective one of the plurality of slots;

wherein the graphics processor is configured to run a plurality of processes including at least some in parallel with one another, wherein each process is configured to process a respective one or more of the input nodes, each process being identified by a respective process ID;

wherein in the updating step of at least one of the iterations, an old parent is removed from the tree and the old parent's respective slot in the buffer is freed for storing a new entry representing a newly created node created by a further one of the selected reinsertions; and

wherein none of the freed slots in the buffer is allowed to be used to store an entry representing any node other than a newly created node created by a process with the same process ID as that which freed the slot in the same or a preceding iteration.

2 . The method of claim 1 , wherein in the updating step of at least one of the iterations, at least one of the selected reinsertions leaves the respective old parent with more than one child.

3 . The method of claim 1 , wherein in the searching step of at least one of the iterations, the one or more candidate reinsertions include at least one candidate reinsertion that would change the number of children of the respective new parent from exactly two to more than two.

4 . The method of claim 3 , wherein in the updating step of at least one of the iterations, at least one of the selected reinsertions changes the number of children of the respective new parent from exactly two to more than two.

5 . The method of claim 1 , wherein in the searching step of at least one of the iterations, the one or more candidate reinsertions include at least one candidate reinsertion that changes the number of children of the respective old parent from more than two children to exactly two children.

6 . The method of claim 1 , wherein in the searching step of at least one of the iterations, the one or more candidate reinsertions comprise at least one candidate reinsertion that would leave the respective old parent with only one remaining child, such that the respective old parent would be removed from the tree and the remaining child would become the child of the old parent's parent.

7 . The method of claim 6 , wherein in the updating step of at least one of the iterations, at least one of the selected reinsertions comprises a reinsertion that leaves the respective old parent with only one remaining child, such that the respective old parent is removed from the tree and the remaining child becomes the child of the old parent's parent.

8 . The method of claim 7 ,

wherein when an old parent is removed in one of said iterations, the respective slot is freed for storing a new entry representing a newly created node created by a further one of the selected reinsertions in the same or a subsequent one of said iterations.

9 . The method of claim 8 , wherein said plurality of slots is a fixed number of slots.

10 . The method of claim 8 , wherein the further selected reinsertion leaves its respective old parent with at least two children, and creates the newly created node as the respective new parent in order to accommodate the input node as a sibling of another, target node in the tree.

11 . The method of claim 10 , wherein the graphics processor is configured to run a plurality of processes including at least some in parallel with one another, wherein each process is configured to process a respective one or more of the input nodes, each process comprises one or more threads or shader invocations, and each process is identified by a respective process ID; wherein the processing of each respective input node comprises:

performing the search for the candidate reinsertions of the respective input node,

performing scoring of the candidate reinsertions of the respective input node to determine the expected reduction in computational cost, and

if any one of the candidate reinsertions of the respective input node is selected as a respective one of the selected reinsertions, performing an execution of the selected reinsertion by performing the updating of the current BVH with the respective selected reinsertion; and

wherein in the execution of any of the selected reinsertions, none of the freed slots is allowed to be used to store an entry representing any input node other than a newly created node created by a process with the same process ID as that which freed the slot in the same or a preceding iteration.

12 . The method of claim 11 , wherein in the execution of at least one of the selected reinsertions, the freed slot is used to store an entry representing a newly created node created by a process with the same process ID as that which freed the slot in a preceding iteration.

13 . The method of claim 11 , further comprising one of said processes searching for a candidate reinsertion that would use a slot freed in a previous iteration, only if the slot was freed by a process in a previous iteration with the same respective process ID as said one of the processes.

14 . The method of claim 1 , wherein the method further comprises determining a starting score being a score of the starting BVH according to a metric for estimating an expected computational cost of searching the tree, wherein the first iteration starts with the starting score as a current score of the current BVH; and wherein in at least one of the iterations, the updating further comprises updating the current score to account for the update.

15 . The method of claim 1 , further comprising after said one or more iterations, searching the tree of the current BVH to determine whether a modelled ray intersects with any of the primitives.

16 . The method of claim 15 , further comprising outputting graphical data for controlling a screen to render a scene representing at least part of the modelled environment, including a lighting effect based on the modelled ray.

17 . The method of claim 1 , further comprising, in each of said iterations in between the identifying of the candidate reinsertions and the updating of the current BVH, performing a conflict resolution to determine whether any of the candidate reinsertions form a subset of conflicting reinsertions which would affect a same part of the tree as one another, and if so, from among each subset so to select only one of the candidate reinsertions as one of the selected reinsertions with which to update the current BVH, the other or others of the candidate reinsertions in the same subset being rejected for inclusion in the update.

18 . A non-transitory computer readable storage medium having stored thereon computer executable code configured to, when run on a graphics processor, perform a method comprising:

obtaining a starting bounding volume hierarchy (BVH), being a data structure comprising nodes representing different 3D regions of space in a 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, starting with a first iteration which starts with the starting BVH as a current BVH, each iteration comprising:

for each of a plurality of input nodes in the tree of the current BVH, searching for one or more candidate reinsertions which would move the input node from a respective old parent to a respective new parent in the tree, and which compared to the current BVH would reduce an expected computational cost of searching the tree to determine whether a modelled ray would intersect with one of the primitives; and

updating the current BVH with one or more selected reinsertions from among the candidate reinsertions;

wherein in the updating step of at least one of the iterations, the one or more selected reinsertions include at least one reinsertion that gives the new parent more than two children;

wherein the graphics processor comprises a buffer comprising a plurality of slots, each respective one of the nodes in the tree being represented as an entry in a respective one of the plurality of slots;

wherein the graphics processor is configured to run a plurality of processes including at least some in parallel with one another, wherein each process is configured to process a respective one or more of the input nodes, each process being identified by a respective process ID;

wherein in the updating step of at least one of the iterations, an old parent is removed from the tree and the old parent's respective slot in the buffer is freed for storing a new entry representing a newly created node created by a further one of the selected reinsertions; and

wherein none of the freed slots in the buffer is allowed to be used to store an entry representing any node other than a newly created node created by a process with the same process ID as that which freed the slot in the same or a preceding iteration.

19 . 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 so as when run to perform a method comprising:

obtaining a starting bounding volume hierarchy (BVH), being a data structure comprising nodes representing different 3D regions of space in a 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, starting with a first iteration which starts with the starting BVH as a current BVH, each iteration comprising:

for each of a plurality of input nodes in the tree of the current BVH, searching for one or more candidate reinsertions which would move the input node from a respective old parent to a respective new parent in the tree, and which compared to the current BVH would reduce an expected computational cost of searching the tree to determine whether a modelled ray would intersect with one of the primitives, and

updating the current BVH with one or more selected reinsertions from among the candidate reinsertions;

wherein in the updating step of at least one of the iterations, the one or more selected reinsertions include at least one reinsertion that gives the new parent more than two children;

wherein the graphics processor comprises a buffer comprising a plurality of slots, each respective one of the nodes in the tree being represented as an entry in a respective one of the plurality of slots;

wherein the graphics processor is configured to run a plurality of processes including at least some in parallel with one another, wherein each process is configured to process a respective one or more of the input nodes, each process being identified by a respective process ID;

wherein in the updating step of at least one of the iterations, an old parent is removed from the tree and the old parent's respective slot in the buffer is freed for storing a new entry representing a newly created node created by a further one of the selected reinsertions; and

wherein none of the freed slots in the buffer is allowed to be used to store an entry representing any node other than a newly created node created by a process with the same process ID as that which freed the slot in the same or a preceding iteration.