Patent ID: 7499053
Filing Date: 2009-03-03
Classification: G06T

Abstract:
1. A method executable in a computer processor, the computer processor comprising computer hardware and being operable to generate 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 processor 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 method 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, 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, and wherein the determining of L- and R-planes comprises: determining a splitting plane M by execution of a 3D-tree construction, the 3D-tree construction being based upon coordinates of triangles into which surfaces in the scene are partitioned, and partitioning the objects such that the overlap of the resulting L- and R-planes of the axis-aligned bounding boxes minimally overlaps the splitting plane M.