Patent Document ID: 7567248
Application ID: 11119302
Patent Status: 1

Claim One:
1. A method for determining in a computer system intersections between a plurality of light rays residing in three dimensional (3D) space and one or more surface elements residing in said 3D space, where said light rays or lines corresponding to said light rays share a common intersection point determined in connection with a light viewpoint, the method comprising: determining 3D points visible from an eye viewpoint to provide a set of points on which subsequent shadow processing is performed; processing intersection points irregularly arranged on a light projection surface with a center of projection at said light viewpoint comprising: (i) for each 3D point visible from said eye viewpoint: computing a two-dimensional location (2D) location of an intersection point of a light ray with said light projection surface by projecting said 3D point onto said light projection surface; explicitly storing said two-dimensional (2D) location in a spatial data structure, in which 2D locations and not surface elements are stored, that supports efficient range queries for large numbers of points such that a distinct two-dimensional (2D) location is separately stored for each of said light rays, wherein an association is maintained between said two-dimensional (2D) location and said points visible from said eye viewpoint; and (ii) processing each of said surface elements subsequent to said explicit storage of said 2D locations, including performing range query processing including determining, using intersection testing, which of the intersection points irregularly arranged on the light projection surface and stored in said data structure are inside a two-dimensional (2D) region, determined using projection, that represents projection of said surface element onto said light projection surface, wherein intersection points determined to be inside said 2D region represent intersections between said surface element and the light rays corresponding to said irregularly arranged intersection points; wherein stored 2D locations of irregularly arranged intersection points are used in the intersection testing, and wherein determination of whether or not a point is in shadow is performed as a function of the association maintained.