Intersection testing for ray tracing
AssigneeImagination Technologies Limited
InventorDaniel Barnard
Life of this patent
Estimating the term…
Abstract
A system and method for performing intersection testing of rays in a ray tracing system. The ray tracing system uses a hierarchical acceleration structure comprising a plurality of nodes, each identifying one or more elements for intersection testing. The system defines and updates progress information that identifies, for a ray, leaf nodes of the hierarchical acceleration structure which identify elements for which it is not yet known whether or not the ray interests.
Claims19
A computer-implemented method of performing intersection testing between a ray and elements identified by nodes of a hierarchical acceleration structure of a ray tracing system, wherein a node identifies one or more elements for intersection testing, wherein elements identified by non-leaf nodes of the hierarchical acceleration structure are represented by a further node of the hierarchical acceleration structure, the computer-implemented method comprising:
- defining a sequential value for each leaf node of the hierarchical acceleration structure, wherein the sequential values of the leaf nodes that branch from any given non-leaf node are sequential with respect to one another;
- defining a value for each non-leaf node of the hierarchical acceleration structure, wherein, for each non-leaf node, the value facilitates identification of the sequential values of any leaf nodes that branch from the said non-leaf node;
- defining progress information for the ray, the progress information comprising first progress information identifying the earliest sequential value amongst the sequential values of leaf nodes for which it is not known whether or not the ray intersects any of their elements;
- performing an intersection testing process to identify any intersections between the ray and elements identified by the nodes of the hierarchical acceleration structure;
- and
- during the intersection testing process, updating the progress information based on any identified intersections between the ray and the elements identified by the nodes of the hierarchical acceleration structure;
- wherein the progress information further comprises second progress information which identifies the sequentially earliest sequential value amongst:
- sequential values of any leaf nodes associated with any intersected element for which no ray request will be or has been defined in that iteration of the intersection testing process;
- and
- sequential values of any leaf node which branches from any non-leaf node, associated with any intersected element, for which no ray request will be or has been defined in that iteration of the intersection testing process.
An intersection testing system for performing intersection testing between one or more rays and elements identified by nodes of a hierarchical acceleration structure, wherein:
- a sequential value is defined for each leaf node of the hierarchical acceleration structure, wherein the sequential values of the leaf nodes that branch from any given non-leaf node are sequential with respect to one another;
- a value is defined for each non-leaf node of the hierarchical acceleration structure, wherein the value of a non-leaf node facilitates identification of the sequential values of any leaf nodes that branch from the non-leaf node;
- and
- progress information is defined for the ray, the progress information comprising first progress information identifying the earliest sequential value amongst the sequential values of leaf nodes for which it is not known whether or not the ray intersects any of their elements;
- wherein the intersection testing system is configured to:
- perform an intersection testing process to identify any intersections between the ray and elements identified by the nodes of the hierarchical acceleration structure;
- and
- during the intersection testing process, update the progress information based on any identified intersections between the ray and the elements identified by the nodes of the hierarchical acceleration structure;
- wherein the progress information further comprises second progress information which identifies the sequentially earliest sequential value amongst:
- sequential values of any leaf nodes associated with any intersected element for which no ray request will be or has been defined in that iteration of the intersection testing process;
- and
- sequential values of any leaf node which branches from any non-leaf node, associated with any intersected element, for which no ray request will be or has been defined in that iteration of the intersection testing process.
Dependencies are inferred from the claim text.