Real-time Precision Ray Tracing
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.