Cache Utilization Optimized Ray Traversal Algorithm with Minimized Memory Bandwidth Requirements

Abstract

Embodiments of the invention provide methods and apparatus for recording the traversal history of a ray through a spatial index structure and utilizing the recorded traversal history. An image processing system may initially determine which nodes a ray intersects as it traverses through a spatial index. Results of the node intersection determinations may be recorded as the ray traverses the spatial index, and the recorded determinations may be associated with the ray. Furthermore, the image processing system may decide upon a traversal path based upon some probability of striking primitives corresponding to the nodes which make up the spatial index. This traversal path may also be recorded and associated with the ray. If the image processing system needs to re-traverse the spatial index at a later time, the recorded traversal history may be used to eliminate the need to recalculate ray-node intersections, and eliminate incorrect traversal path determinations.

1 . A method of ray tracing utilizing a spatial index having nodes defining bounded volumes of a three dimensional scene comprising:
 generating a ray into the scene;   traversing the spatial index by taking branches from internal nodes until a leaf node is reached, wherein branches are taken based on whether the ray intersects bounding volumes defined by the nodes;   recording a traversal history indicating one or more nodes defining bounding volumes the ray intersects and branches taken when traversing the spatial index;   determining if the ray hits a primitive contained in the bounding volume defined by the leaf node; and   if the ray does not hit a primitive contained in the bounding volume defined by the leaf node, re-traversing the spatial index using the recorded traversal history.   
   
   
       2 . The method of  claim 1 , wherein the spatial index contains a plurality of internal node levels, and the traversal history is recorded for each node level. 
   
   
       3 . The method of  claim 1 , wherein the spatial index contains a plurality of internal node levels and the traversal history comprises four bits for each internal node level of the spatial index 
   
   
       4 . The method of  claim 3 , wherein two of the traversal history bits indicate whether the ray intersects bounding volumes defined by a node located within one of the internal node levels, and wherein two of the traversal history bits indicate branches taken when traversing the spatial index from the node on one of the internal node levels. 
   
   
       5 . The method of  claim 1 , further comprising:
 storing the ray traversal history with information defining the ray; and   transmitting information defining the ray and the traversal history from a workload manager executing on a first processing element to a vector throughput engine executing on a second processing element, wherein the workload manager and the vector throughput engine communicate through a memory mapped address space.   
   
   
       6 . The method of  claim 5 , wherein the workload manager determines whether the ray intersects bounding volumes defined by the nodes, wherein the workload manager records the traversal history, and wherein the vector throughput engine determines if the ray hits a primitive contained in the bounding volume defined by the leaf node. 
   
   
       7 . The method of  claim 6 , wherein the workload manager and the vector throughput engine are located on the same processing element. 
   
   
       8 . The method of  claim 6 , wherein the workload manager and the vector throughput engine are located on separate processing elements. 
   
   
       9 . The method of  claim 1 , wherein re-traversing the spatial index using the recorded traversal history comprises,
 determining a lowest level on the spatial index where bounding volumes corresponding to a node were intersected by the ray, but a branch from the node was not taken;   traversing the spatial index based on the branches taken and recorded in the traversal history to the lowest level;   taking the branch from the node not yet taken; and   traversing the spatial index below lowest level by taking branches from internal nodes until a leaf node is reached, wherein branches are taken based on whether the ray intersects bounding volumes defined by the nodes;   recording a traversal history below the lowest level indicating one or more nodes defining bounding volumes the ray intersects and branches taken when traversing the spatial index; and   determining if the ray hits a primitive contained in the bounding volume below the lowest level and defined by the leaf node.   
   
   
       10 . A computer readable medium containing a program which, when executed, performs an operation for ray tracing utilizing a spatial index having nodes defining bounded volumes of a three dimensional scene, the operation comprising:
 generating a ray into the scene;   traversing the spatial index by taking branches from internal nodes until a leaf node is reached, wherein branches are taken based on whether the ray intersects bounding volumes defined by the nodes;   recording a traversal history indicating one or more nodes defining bounding volumes the ray intersects and branches taken when traversing the spatial index;   determining if the ray hits a primitive contained in the bounding volume defined by the leaf node; and   if the ray does not hit a primitive contained in the bounding volume defined by the leaf node, re-traversing the spatial index using the recorded traversal history.   
   
   
       11 . The computer readable medium of  claim 10 , wherein the spatial index contains a plurality of internal node levels, and the traversal history is recorded for each node level. 
   
   
       12 . The computer readable medium of  claim 10 ,
 wherein the spatial index contains a plurality of internal node levels and the traversal history comprises four bits for each internal node level of the spatial index, wherein two of the traversal history bits indicate whether the ray intersects bounding volumes defined by a node on one of the internal node levels, and wherein two of the traversal history bits indicate branches taken when traversing the spatial index from the node on one of the internal node levels.   
   
   
       13 . The computer readable medium of  claim 10 , wherein the operations further comprise:
 storing the ray traversal history with information defining the ray; and   transmitting information defining the ray and the traversal history from a workload manager executing on a first processing element to a vector throughput engine executing on a second processing element, wherein the workload manager and the vector throughput engine communicate through a memory mapped address space.   
   
   
       14 . The computer readable medium of  claim 13 , wherein the workload manager determines whether the ray intersects bounding volumes defined by the nodes, wherein the workload manager records the traversal history, and wherein the vector throughput engine determines if the ray hits a primitive contained in the bounding volume defined by the leaf node. 
   
   
       15 . The computer readable medium of  claim 10 , wherein re-traversing the spatial index using the recorded traversal history comprises:
 determining a lowest level on the spatial index where bounding volumes corresponding to a node were intersected by the ray, but the branch from the node was not taken;   traversing the spatial index based on the branches taken and recorded in the traversal history to the lowest level;   taking the branch from the node not yet taken; and   traversing the spatial index below lowest level by taking branches from internal nodes until a leaf node is reached, wherein branches are taken based on whether the ray intersects bounding volumes defined by the nodes; and wherein the operations further comprise:   recording a traversal history below the lowest level indicating one or more nodes defining bounding volumes the ray intersects and branches taken when traversing the spatial index; and   determining if the ray hits a primitive contained in the bounding volume below the lowest level and defined by the leaf node.   
   
   
       16 . A system, comprising:
 a spatial index having nodes defining bounded volumes of a three dimensional scene; and   a first processing element, wherein the first processing element is configured to:
 generate a ray into the scene; 
 traverse the spatial index by taking branches from internal nodes until a leaf node is reached, wherein branches are taken based on whether the ray intersects bounding volumes defined by the nodes; 
 record a traversal history indicating one or more nodes defining bounding volumes the ray intersects and branches taken when traversing the spatial index; 
 determine if the ray hits a primitive contained in the bounding volume defined by the leaf node; and 
 if the ray does not hit a primitive contained in the bounding volume defined by the leaf node, re-traverse the spatial index using the recorded traversal history. 
   
   
   
       17 . The system of  claim 16 , wherein the first processing element further comprises:
 a plurality of threads; and   a memory mapped address space; and   the first processing element is further configured to:
 store the ray traversal history with information defining the ray; and 
 transmit information defining the ray and the traversal history from a workload manager executing on a first processing element thread to a vector throughput engine executing on a second processing element thread, wherein the workload manager and the vector throughput engine communicate through the memory mapped address space. 
   
   
   
       18 . The system of  claim 17 , wherein the workload manager determines whether the ray intersects bounding volumes defined by nodes, the workload manager records the traversal history, and the vector throughput engine determines if the ray hits a primitive contained in the bounding volume defined by the leaf node. 
   
   
       19 . The system of  claim 17 , wherein the system further comprises:
 a second processing element comprising a second plurality of threads and a second memory mapped address space;   a high speed bus coupling the first processing element to the second processing element; and   wherein the workload manager executes on the first processing element and the vector throughput engine executes on the second processing element, and wherein the workload manager and the vector throughput engine communicate through the high speed bus and the memory mapped address spaces.   
   
   
       20 . The system of  claim 16 , wherein re-traversing the spatial index using the recorded traversal history comprises,
 determining a lowest level on the spatial index where bounding volumes corresponding to a node that were intersected by the ray, but a branch from the node was not taken;   traversing the spatial index based on the branches taken and recorded in the traversal history to the lowest level;   taking the branch from the node not yet taken; and   traversing the spatial index below lowest level by taking branches from internal nodes until a leaf node is reached, wherein branches are taken based on whether the ray intersects bounding volumes defined by the nodes; and wherein the system is further configured to:   record a traversal history below the lowest level indicating one or more nodes defining bounding volumes the ray intersects and branches taken when the system traverses the spatial index; and   determine if the ray hits a primitive contained in the bounding volume below the lowest level and defined by the leaf node.