Point-based global illumination directional importance mapping

1. A computer-implemented method for shading locations for use in rendering a computer-generated scene having one or more objects represented by a point cloud, the method comprising:

(a) obtaining a hierarchy for the point cloud, wherein the point cloud includes a plurality of emitter points that contain an indication of light emitted from surface elements of the objects in the scene, and wherein the hierarchy has a plurality of clusters of emitter points of the point cloud;

(b) selecting a receiver point to shade;

(c) obtaining a desired solid angle;

(d) selecting a first cluster from the plurality of clusters, wherein the first cluster represents a first set of points in the point cloud, and wherein the solid angle that subtends the first cluster from the receiver point is not greater than the desired solid angle;

(e) determining an importance weight for the first cluster, wherein the importance weight is based on the luminance of an area of the scene in the direction of the first cluster;

(f) determining a maximum allowed solid angle based on the importance weight of the first cluster;

(g) determining whether the solid angle that subtends the first cluster from the receiver point is greater than the maximum allowed solid angle; and

(h) in response to a determination that the solid angle that subtends the first cluster from the receiver point is not greater than the maximum allowed solid angle, shading the receiver point based on an indication of light emitted from the first cluster.

2. The method of claim 1 further comprising:

(i) in response to a determination that the solid angle that subtends the first cluster from the receiver point is greater than the maximum allowed solid angle, shading the receiver point based on an indication of light emitted from a second cluster representing a second set of points, wherein the solid angle that subtends the second cluster from the receiver point is not greater than the maximum allowed solid angle.

3. The method of claim 2 , wherein the first set of points includes all of the points of the second set of points and at least one additional point.

4. The method of claim 1 further comprising:

(i) in response to a determination that the solid angle that subtends the first cluster from the receiver point is greater than the maximum allowed solid angle, repeating steps (e)-(h) for a second cluster, wherein the solid angle that subtends the second cluster from the receiver point is not greater than the maximum allowed solid angle, and wherein the second cluster represents a subset of points of the first set of points.

5. The method of claim 1 , wherein the hierarchy is a tree structure.

6. The method of claim 1 , wherein the importance weight is linearly proportional to the luminance of the area of the scene in the direction of the first cluster.

7. The method of claim 1 , wherein the maximum allowed solid angle is a linear function of the importance weight.

8. The method of claim 1 , wherein the importance weight is based on a level of reflectance for the area of the scene in the direction of the first cluster.

9. A non-transitory computer-readable storage medium encoded with a computer program for shading locations for use in rendering a computer-generated scene having one or more objects represented by a point cloud, the computer program comprising computer executable instructions for:

(a) obtaining a hierarchy for the point cloud, wherein the point cloud includes a plurality of emitter points that contain an indication of light emitted from surface elements of the objects in the scene, and wherein the hierarchy has a plurality of clusters of emitter points of the point cloud;

(b) selecting a receiver point to shade;

(c) obtaining a desired solid angle;

(d) selecting a first cluster from the plurality of clusters, wherein the first cluster represents a first set of points in the point cloud, and wherein the solid angle that subtends the first cluster from the receiver point is not greater than the desired solid angle;

(e) determining an importance weight for the first cluster wherein the importance weight is based on the luminance of an area of the scene in the direction of the first cluster;

(f) determining a maximum allowed solid angle based on the importance weight of the first cluster;

(g) determining whether the solid angle that subtends the first cluster from the receiver points is greater than the maximum allowed solid angle; and

(h) in response to a determination that the solid angle that subtends the first cluster from the receiver point is not greater than the maximum allowed solid angle shading the receiver point based on an indication of light emitted from the first cluster.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the computer program further comprises computer executable instructions for:

(h) in response to a determination that the solid angle that subtends the first cluster from the receiver point is greater than the maximum allowed solid angle, shading the location based on an indication of light emitted from a second cluster representing a second set of points, wherein the solid angle that subtends the second cluster from the receiver point is not greater than the maximum solid angle.

11. The non-transitory computer-readable storage medium of claim 10 , wherein the first set of points includes all of the points of the second set of points and at least one additional point.

12. The non-transitory computer-readable storage medium of claim 9 , wherein the computer program further comprises computer executable instructions for:

(i) in response to a determination that the solid angle that subtends the first cluster from the receiver point is greater than the maximum allowed solid angle, repeating steps (e)-(h) for a second cluster, wherein the solid angle that subtends the second cluster from the receiver point is not greater than the maximum allowed solid angle, and wherein the second cluster represents a subset of points of the first set of points.

13. The non-transitory computer-readable storage medium of claim 9 , wherein the hierarchy is a tree structure.

14. The non-transitory computer-readable storage medium of claim 9 , wherein the importance weight is linearly proportional to the luminance of the area of the scene in the direction of the first cluster.

15. The non-transitory computer-readable storage medium of claim 9 , wherein the maximum allowed solid angle is a linear function of the importance weight.

16. The non-transitory computer-readable storage medium of claim 9 , wherein the importance weight is based on a level of reflectance of the area of the scene in the direction of the first cluster.

17. An animation system for shading locations for use in rendering a computer-generated scene having one or more objects represented by a point cloud, the system comprising:

at least one processor; and

memory storing instructions, the instructions configured for execution by the at least one processor to cause the at least one processor to:

obtain a hierarchy for the point cloud, wherein the point cloud includes a plurality of emitter points that contain an indication of light emitted from surface elements of the objects in the scene, and wherein the hierarchy has a plurality of clusters of emitter points of the point cloud;

select a receiver point to shade;

obtain a desired solid angle;

select a first cluster from the plurality of clusters, wherein the first cluster represents a first set of points in the point cloud and wherein the solid angle that subtends the first cluster from the location to shade is not greater than the desired solid angle;

determine an importance weight for the first cluster, wherein the importance weight is based on the luminance of an area of the scene in the direction of the first cluster;

determine a maximum allowed solid angle for the first cluster based on the importance weight of the first cluster;

determine whether the solid angle that subtends the first cluster from the receiver point is greater than the maximum allowed solid angle; and

in response to a determination that the solid angle that subtends the first cluster from the receiver point is not greater than the maximum allowed solid angle, shading the receiver point based on an indication of light emitted from the first cluster.