Patent Document ID: 20080043018
Application ID: 11737424
Patent Status: 0

Claim One:
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 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.