Apparatus and method for cross-instance front-to-back traversal for ray tracing heavily-instanced scenes

A graphics processing apparatus comprising:

• ray tracing circuitry to construct a hierarchical acceleration structure over a plurality of instances of one or more base geometric objects, the hierarchical acceleration structure comprising a plurality of nodes arranged in a hierarchy, the plurality of instances comprising a first instance and a second instance each includes one or more nodes of the plurality of nodes;
• and
• traversal circuitry to perform ray traversal on the hierarchical acceleration structure using a ray, wherein the ray traversal is performed based on a traversal queue that orders nodes in the plurality of instances based on distances of the nodes to a ray origin of the ray, wherein the ray traversal is performed on a first node in the first instance, followed by a second node in the second instance, wherein the second node in the second instance is traversed ahead of a third node in the first instance based on the traversal queue.

A method comprising:

• constructing a hierarchical acceleration structure over a plurality of instances of one or more base geometric objects, the hierarchical acceleration structure comprising a plurality of nodes arranged in a hierarchy, the plurality of instances comprising a first instance and a second instance each includes one or more nodes of the plurality of nodes;
• and
• performing ray traversal on the hierarchical acceleration structure using a ray, wherein the ray traversal is performed based on a traversal queue that orders nodes in the plurality of instances based on distances of the nodes to a ray origin of the ray, wherein the ray traversal is performed on a first node in the first instance, followed by a second node in the second instance, wherein the second node in the second instance is traversed ahead of a third node in the first instance based on the traversal queue.

A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, is capable of causing the machine to perform:

• constructing a hierarchical acceleration structure over a plurality of instances of one or more base geometric objects, the hierarchical acceleration structure comprising a plurality of nodes arranged in a hierarchy, the plurality of instances comprising a first instance and a second instance each includes one or more nodes of the plurality of nodes;
• and
• performing ray traversal on the hierarchical acceleration structure using a ray, wherein the ray traversal is performed based on a traversal queue that orders nodes in the plurality of instances based on distances of the nodes to a ray origin of the ray, wherein the ray traversal is performed on a first node in the first instance, followed by a second node in the second instance, wherein the second node in the second instance is traversed ahead of a third node in the first instance based on the traversal queue.