Methods, computer program and apparatus for an ordered traversal of a subset of nodes of a tree structure and for determining an occlusion of a point along a ray in a raytracing scene

A method for determining an occlusion of a point along a ray in a raytracing scene, wherein the raytracing scene comprises a plurality of objects, wherein the plurality of objects are represented by a plurality of nodes of a tree structure, the method comprising:

• determining a direction of the ray;
• traversing the tree structure using a method for an ordered traversal of a subset of nodes of a tree structure, by:
• obtaining ordering information indicating a desired order of the ordered traversal of the tree structure,
• selecting a predetermined ordering parameter template from a plurality of predetermined ordering parameter templates based on the ordering information, copying the subset of nodes of the tree structure from a first memory region to a second memory region using a single processor operation of a vector processing processor instruction set such that the subset of nodes of the tree structure is stored within the second memory region in the desired order, wherein the selected predetermined ordering parameter template is used as a parameter for the single processor operation,
• choosing one or more nodes of the subset of nodes based on a selection criterion using a vector comparison operation,
• determining a compaction parameter of a further single processor operation of the vector processing processor instruction set based on the chosen one or more nodes, wherein the further single processor operation is a vector compaction operation, and copying the one or more nodes from the second memory region to a third memory region using the further single processor operation and the compaction parameter such that the one or more nodes are stored adjacently within the third memory region,
• wherein the desired ordering of the ordered traversal is with respect to a direction of the ray,
• wherein a first subset of nodes of the tree structure to be processed as the subset of nodes is chosen from a root of the tree structure,
• wherein subsequent subsets of nodes to be processed as the subset of nodes are chosen based on the one or more chosen nodes,
• wherein the selection criterion to be used is, whether the ray intersects a bounding box associated with a node of the subset of nodes, and
• wherein leaf nodes among the chosen one or more nodes are added to a plurality of intersecting leaf nodes;
• and
• determining the occlusion of the point along the ray based on the plurality of intersecting leaf nodes.