Real-time Precision Ray Tracing

Abstract

Systems and techniques are described for ray tracing and for the efficient construction of acceleration data structures required for fast ray tracing. A computer graphics system generates, for each pixel in an image, a pixel value that is representative of a point in a scene as recorded on an image plane of a simulated camera. The computer graphics system is configured to generate the pixel value for an image using a selected ray-tracing methodology . The selected ray-tracing methodology includes the use of a ray tree that includes at least one ray shot from the pixel into a scene along a selected direction. The ray-tracing methodology further includes calculating the intersections of rays and surfaces in the scene. An axis-aligned bounding box is defined that contains, for a given ray, the point of intersection of the ray and surface nearest the origin of the ray. The bounding box is iteratively refined until a predetermined termination criterion has been met.

1 . In a computer graphics system for generating a pixel value for a pixel in an image, the pixel value being representative of a point in a scene as recorded on an image plane of a simulated camera, the computer graphics system being configured to generate the pixel value for an image using a selected ray-tracing methodology, the selected ray-tracing methodology comprising the use of a ray tree, the ray tree including at least one ray shot from the pixel into a scene along a selected direction, the ray-tracing methodology further comprising the calculating of the intersections of rays and surfaces of objects in the scene, the improvement comprising:
 calculating intersections of rays and objects in the scene by utilizing bounding volume hierarchies, the calculating comprising:   defining, utilizing, and recursively and adaptively refining an axis-aligned bounding box to Locate, for a given ray, the point of ray/object intersection nearest the origin of the ray, and   continuing the refinement of the axis-aligned bounding box until a predetermined termination criterion is met.   
   
   
       2 . The improvement of  claim 1  further wherein the defining of an axis-aligned bounding box comprises determining parallel L- and R-planes to partition a set of virtual objects within the axis-aligned bounding box into a set of left objects and a set of right objects and to thereby define two axis-aligned bounding boxes by the two parallel planes, and
 further comprising processing the left and right objects recursively until the termination criterion is met.   
   
   
       3 . The improvement of  claim 1  further wherein, after computing the intersection point of a ray and a surface, values of the computed point are used along with the corresponding ray direction to again compute the intersection, thereby providing an iteration to the ray/surface intersection calculation to increase precision. 
   
   
       4 . The improvement of  claim 1  further wherein if a calculated intersection point is below a surface in the scene, the calculated point is shifted to the other side of the surface, yielding a modified calculated point. 
   
   
       5 . The improvement of  claim 4  wherein the shift is along the surface normal or along an axis determined by the longest component of the surface normal. 
   
   
       6 . The improvement of  claim 4  wherein the shifting is implemented by shifting the last bits of a floating point mantissa representing an intersection point by an integer epsilon, and wherein secondary, rays are defined to start from the modified calculated point. 
   
   
       7 . The improvement of  claim 1  further comprising utilizing a ray triangle intersection test wherein an intersection of a ray and the plane of a triangle subdivision of a surface in the scene is determined, and intersections outside a predetermined valid interval on the ray are excluded. 
   
   
       8 . In a computer graphics system for generating a pixel value for a pixel in an image, the pixel value being representative of a point in a scene as recorded on an image plane of a simulated camera, the computer graphics system being configured to generate the pixel value for an image using a selected ray-tracing methodology, the selected ray-tracing methodology comprising the use of a ray tree, the ray tree including at least one ray shot from the pixel into a scene along a selected direction, the ray-tracing methodology further comprising the calculating of the intersections of rays and objects in the scene, the improvement comprising:
 computer-executable software code operable to enable the calculating of intersections of rays and objects in the scene by utilizing bounding volume hierarchies, the calculating comprising:   defining, utilizing and recursively and adaptively refining an axis-aligned bounding box to locate, for a given ray, the point of ray/object intersection nearest the origin of the ray, and   continuing the refinement of the axis-aligned bounding box until a predetermined termination criterion is met.   
   
   
       9 . A computer graphics system for generating a pixel value for a pixel in an image, the pixel value being representative of a point in a scene as recorded on an image plane of a simulated camera, the computer graphics system being configured to generate the pixel value for an image using a selected ray-tracing methodology, the selected ray-tracing methodology comprising the use of a ray tree, the ray tree including at least one ray shot from the pixel into a scene along a selected direction, the ray-tracing methodology further comprising the calculating of the intersections of rays and surfaces of objects in the scene, the computer graphics system comprising:
 means for calculating intersections of rays and objects in the scene by utilizing bounding volume hierarchies, the means for calculating comprising:   means for defining, utilizing, and recursively and adaptively refining an axis-aligned bounding box to locate, for a given ray, the point of ray/object intersection nearest the origin of the ray, and   means for continuing the refinement of the axis-aligned bounding box until a predetermined termination criterion is met.   
   
   
       10 . In a computer graphics system for generating a pixel value for a pixel in an image, the pixel value being representative of a point in a scene as recorded on an image plane of a simulated camera the computer graphics system being configured to generate the pixel value for an image using a selected ray-tracing methodology, the selected ray-tracing methodology comprising the use of a ray tree, the ray tree including at least one ray shot from the pixel into a scene along a selected direction, the ray-tracing methodology further comprising the calculating of the intersections of rays and surfaces of objects in the scene, a method of calculating intersections of rays and objects in the scene, the method comprising:
 constructing bounding volume hierarchies, the constructing comprising:   defining, utilizing, and recursively and adaptively refining an axis-aligned bounding box to locate, for a given ray, the point of ray/object intersection nearest the origin of the ray, and   continuing the refinement of the axis-aligned bounding box until a predetermined termination criterion is met.   
   
   
       11 . The improvement of  claim 1  further comprising subdividing bounding boxes. 
   
   
       12 . The improvement of  claim 11  further comprising executing tree pruning by left-balancing from a selected depth, the tree pruning comprising pruning tree depth by approximately left-balancing the binary space partition starting from the selected depth.