Instant ray tracing

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.

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.

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.