Patent ID: 8325186

Claim:
A non-transitory computer readable storage medium storing one or more computer programs adapted to cause a processor based system to execute steps comprising: identifying a set of shadow casters and a set of shadow receivers in a frame of a scene that is lighted by at least a first light source; constructing a first three-dimensional (3D) grid, from the first light source's point of view, that fully encloses a first volume of the scene, comprising one or more shadow casters of the set of shadow casters that fall within the first volume of the scene; projecting each of the one or more shadow casters to generate one or more projected shadow casters; performing a union of each cell of the first 3D grid and at least one of the one or more shadow casters to form one or more grown cells of the first grid; constructing a second three-dimensional (3D) grid, from the first light source's point of view, that fully encloses the first volume of the scene, comprising one or more shadow receivers of the set of shadow receivers that fall within the first volume of the scene; performing a union of each cell of the second 3D grid corresponding to a cell of the first grid having at least one grown cell of the first grid and at least one of the one or more shadow receivers to form one or more grown cells of the second grid; marking for rendering each shadow receiver for which a grown cell of the second 3D grid has been formed; forming one or more grown cells of a third 3D grid by intersecting the first 3D grid with the second 3D grid such that the third 3D grid comprises the grown cells of the first grid and the grown cells of the second grid that intersect; and marking for rendering into a shadow map each shadow caster that intersects the third 3D grid.