Patent ID: 7952583

Claim:
A method, executable 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 at least one point 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 simulating of at least one ray shot from the pixel into a scene, or from the scene to a pixel, 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 simulating of trajectories of rays illuminating objects in the scene, the method comprising: within the computer, constructing an object list partitioning in linear time, in a bottom up manner, (1) creating bounding boxes based on a regular grid to enable a bucket sort operation, (2) storing an original resolution of the grid utilized for the bucket sort in counters, (3) utilizing a round-robin approach to select a counter having a non-zero value, (4) dividing the counter value of the selected counter by a selected value and utilizing an axis assigned to the selected counter, (5) looping over all boxes, including merging directly neighboring boxes along the axis and creating a partitioning node if all directly neighboring boxes are non-empty, or if only one is non-empty, determining whether an additional partitioning node for empty space cut-off is to be created, and (6) continuing at least (2) through (5) until only a root box remains.