Instant ray tracing

Abstract

Methods, systems, devices and computer program products operable in a computer graphics system include constructing a hierarchical ray tracing acceleration data structure comprising a tree structure, the nodes of which are generated utilizing a bounding interval hierarchy based on defining an axis-aligned scene bounding box and two parallel planes to partition a set of objects in a scene into left objects and right objects, and matching split planes to object bounding boxes. The two planes are perpendicular to a selected one of x, y, or z-axes. Given a splitting plane, each object in an image is classified either left or right based on a left/right selection criterion, and two splitting plane values of the child nodes are determined by the maximum and minimum coordinate of the left and right objects, respectively.

1 . In a computer graphics system comprising a computer and a display element, the display element being operable to display a human-perceptible image in response to a display-controlling electrical output from the computer, the computer being operable to generate the display-controlling electrical output based on calculations of pixel values for pixels in the image, respective pixel values being representative of points in a scene as recorded on an image plane of a simulated camera, the computer being operable to generate pixel values for an image using a ray-tracing methodology, the ray-tracing methodology comprising the use of a ray tree and an associated ray tracing data structure, 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, and the ray-tracing being determined in response to the results of processing of objects in an image, the improvement comprising:
 constructing a hierarchical ray tracing acceleration data structure comprising a tree structure, the nodes of which are generated utilizing a bounding interval hierarchy based on defining an axis-aligned scene bounding box and two parallel planes to partition a set of objects in a scene into left objects and right objects, and matching split planes to object bounding boxes,   wherein the two planes are perpendicular to a selected one of x, y, or z-axes,   wherein, given a splitting plane, each object in an image is classified either left or right based on a left/right selection criterion, and two splitting plane values of the child nodes are determined by the maximum and minimum coordinate of the left and right objects, respectively,   wherein, given a bounding box and the selected axis, a left child L results from replacing a maximum value of a left object's coordinates along the selected axis by the first plane, and a right child R results from replacing a minimum value of a right object's coordinates by the second plane, and wherein any resulting zero volumes are used to represent empty children,   wherein splitting planes are determined by:   (a) selecting candidate splitting planes by hierarchically subdividing an axis-aligned scene bounding box along the longest side in the middle, wherein all candidate splitting planes form a regular grid,   (b) if a candidate plane is outside the bounding box of a volume element to subdivide, continuing with candidate planes from the half where the volume element resides,   and further comprising:   (a) recursively partitioning the bounding box into object bounding boxes,   (b) if a split plane candidate separates objects without overlap, fitting the resulting split planes to the objects on the left and right, thereby maximizing empty space, and   (c) terminating the recursion when no more than a predetermined number of objects remains.   
   
   
       2 . In a computer graphics system comprising a computer and a display element, the display element being operable to display a human-perceptible image in response to a display-controlling electrical output from the computer, the computer being operable to generate the display-controlling electrical output based on calculations of pixel values for pixels in the image, respective pixel values being representative of points in a scene as recorded on an image plane of a simulated camera, the computer being operable to generate pixel values for an image using a ray-tracing methodology, the ray-tracing methodology comprising the use of a ray tree and an associated ray tracing data structure, 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, and the ray-tracing being determined in response to the results of processing of objects in an image, a computer software product comprising:
 computer-executable code stored in computer-readable form on a computer-readable medium, the computer software product further comprising computer-executable code stored on the computer-readable medium and executable by the computer to enable the computer to construct a hierarchical ray tracing acceleration data structure comprising a tree structure, the nodes of which are generated utilizing a bounding interval hierarchy based on defining an axis-aligned scene bounding box and two parallel planes to partition a set of objects in a scene into left objects and right objects, and matching split planes to object bounding boxes,   wherein the two planes are perpendicular to a selected one of x, y, or z-axes,   wherein, given a splitting plane, each object in an image is classified either left or right based on a left/right selection criterion, and two splitting plane values of the child nodes are determined by the maximum and minimum coordinate of the left and right objects, respectively,   wherein, given a bounding box and the selected axis, a left child L results from replacing a maximum value of a left object's coordinates along the selected axis by the first plane, and a right child R results from replacing a minimum value of a right object's coordinates by the second plane, and wherein any resulting zero volumes are used to represent empty children,   wherein splitting planes are determined by:   (a) selecting candidate splitting planes by hierarchically subdividing an axis-aligned scene bounding box along the longest side in the middle, wherein all candidate splitting planes form a regular grid,   (b) if a candidate plane is outside the bounding box of a volume element to subdivide, continuing with candidate planes from the half where the volume element resides,   and further comprising:   (a) recursively partitioning the bounding box into object bounding boxes,   (b) if a split plane candidate separates objects without overlap, fitting the resulting split planes to the objects on the left and right, thereby maximizing empty space, and   (c) terminating the recursion when no more than a predetermined number of objects remains.   
   
   
       3 . In a computer graphics system comprising a computer and a display element, the display element being operable to display a human-perceptible image in response to a display-controlling electrical output from the computer, the computer being operable to generate the display-controlling electrical output based on calculations of pixel values for pixels in the image, respective pixel values being representative of points in a scene as recorded on an image plane of a simulated camera, the computer being operable to generate pixel values for an image using a ray-tracing methodology, the ray-tracing methodology comprising the use of a ray tree and an associated ray tracing data structure, 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, and the ray-tracing being determined in response to the results of processing of objects in an image, the method comprising:
 constructing a hierarchical ray tracing acceleration data structure comprising a tree structure, the nodes of which are generated utilizing a bounding interval hierarchy based on defining an axis-aligned scene bounding box and two parallel planes to partition a set of objects in a scene into left objects and right objects, and matching split planes to object bounding boxes,   wherein the two planes are perpendicular to a selected one of x, y, or z-axes,   wherein, given a splitting plane, each object in an image is classified either left or right based on a left/right selection criterion, and two splitting plane values of the child nodes are determined by the maximum and minimum coordinate of the left and right objects, respectively,   wherein, given a bounding box and the selected axis, a left child L results from replacing a maximum value of a left object's coordinates along the selected axis by the first plane, and a right child R results from replacing a minimum value of a right object's coordinates by the second plane, and wherein any resulting zero volumes are used to represent empty children,   wherein splitting planes are determined by:   (a) selecting candidate splitting planes by hierarchically subdividing an axis-aligned scene bounding box along the longest side in the middle, wherein all candidate splitting planes form a regular grid,   (b) if a candidate plane is outside the bounding box of a volume element to subdivide, continuing with candidate planes from the half where the volume element resides,   and further comprising:   (a) recursively partitioning the bounding box into object bounding boxes,   (b) if a split plane candidate separates objects without overlap, fitting the resulting split planes to the objects on the left and right, thereby maximizing empty space, and   (c) terminating the recursion when no more than a predetermined number of objects remains.   
   
   
       4 . In a computer graphics system comprising a computer and a display element, the display element being operable to display a human-perceptible image in response to a display-controlling electrical output from the computer, the computer being operable to generate the display-controlling electrical output based on calculations of pixel values for pixels in the image, respective pixel values being representative of points in a scene as recorded on an image plane of a simulated camera, the computer being operable to generate pixel values for an image using a ray-tracing methodology, the ray-tracing methodology comprising the use of a ray tree and an associated ray tracing data structure, 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, and the ray-tracing being determined in response to the results of processing of objects in an image, a sub-system comprising:
 means for constructing a hierarchical ray tracing acceleration data structure comprising a tree structure, the nodes of which are generated utilizing a bounding interval hierarchy based on defining an axis-aligned scene bounding box and two parallel planes to partition a set of objects in a scene into left objects and right objects, and matching split planes to object bounding boxes,   wherein the two planes are perpendicular to a selected one of x, y, or z-axes,   wherein, given a splitting plane, each object in an image is classified either left or right based on a left/right selection criterion, and two splitting plane values of the child nodes are determined by the maximum and minimum coordinate of the left and right objects, respectively,   wherein, given a bounding box and the selected axis, a left child L results from replacing a maximum value of a left object's coordinates along the selected axis by the first plane, and a right child R results from replacing a minimum value of a right object's coordinates by the second plane, and wherein any resulting zero volumes are used to represent empty children,   wherein splitting planes are determined by:   (a) selecting candidate splitting planes by hierarchically subdividing an axis-aligned scene bounding box along the longest side in the middle, wherein all candidate splitting planes form a regular grid,   (b) if a candidate plane is outside the bounding box of a volume element to subdivide, continuing with candidate planes from the half where the volume element resides,   and further comprising:   (a) recursively partitioning the bounding box into object bounding boxes,   (b) if a split plane candidate separates objects without overlap, fitting the resulting split planes to the objects on the left and right, thereby maximizing empty space, and   (c) terminating the recursion when no more than a predetermined number of objects remains.