Rendering images using ray tracing with multiple light sources

1. A method for rendering an image of a scene, wherein the scene is affected by a plurality of light sources, the method comprising:

subdividing the scene into a plurality of cells;

performing data collection to generate significance values, including:

sampling a plurality of light source—point pairs, each pair including a respective light source of the plurality of light sources and a point in the scene;

for each pair, determining a contribution value of the light source in the pair to a color of the point in the pair;

for each cell and for each light source:

determining a maximum contribution value of the contribution values for the light source to the color of the points that are in the cell;

determining, based on the maximum contribution value, a significance value that is a measure of an estimated importance of the light source in rendering a portion of the image corresponding to the cell; and

adjusting the significance value to obtain an adjusted significance value; and

rendering the image of the scene by sampling light sources having a higher adjusted significance value more often than light sources having a lower adjusted significance value.

2. The method of claim 1 , wherein determining a contribution value of the light source in a pair to a color of the point in the pair comprises:

casting a ray from the point to the light source; and

performing an analysis of the ray to determine the contribution value.

3. The method of claim 2 , further comprising:

determining, for each cell and for each light source, a ratio of a count of rays cast to the light source from the points in the cell that reached the light source and a total count of rays cast to the light source from the points in the cell; and

updating each adjusted significance value for each cell and each light source based on the ratio associated with the corresponding cell and light source.

4. The method of claim 1 , wherein adjusting the significance value comprises:

normalizing each significance value associated with the cell based on a sum of all significance values associated with the cell.

5. The method of claim 1 , wherein:

the image is captured from an image capturing point; and

subdividing the scene into the plurality of cells comprises:

creating a virtual space around the image capturing point,

generating a plurality of quadrilaterals that neighbor the virtual space, and

assigning points covered by each quadrilateral to a cell of the plurality of cells.

6. The method of claim 1 , wherein subdividing the scene into the plurality of cells comprises dividing the scene into a plurality of 3-dimensional voxels and assigning points in an area covered by each 3-dimensional voxel to a cell of the plurality of cells.

7. The method of claim 1 , wherein subdividing the scene into the plurality of cells comprises:

dividing the image into a plurality of portions;

determining an area in the scene covered by each portion of the plurality of portions; and

assigning points in each area in the scene covered by each portion of the plurality of portions to a cell of the plurality of cells.

8. A system for rendering in image of a scene, wherein the scene is affected by a plurality of light sources, comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations for rendering an image, the operations comprising:

subdividing the scene into a plurality of cells;

performing data collection to generate significance values, including:

sampling a plurality of light source—point pairs, each pair including a respective light source of the plurality of light sources and a point in the scene;

for each pair, determining a contribution value of the light source in the pair to a color of the point in the pair;

for each cell and for each light source:

determining a maximum contribution value of the contribution values for the light source to the color of the points that are in the cell;

determining, based on the maximum contribution value, a significance value that is a measure of an estimated importance of the light source in rendering a portion of the image corresponding to the cell; and

adjusting the significance value to obtain an adjusted significance value; and

rendering the image of the scene by sampling light sources having a higher adjusted significance value more often than light sources having a lower adjusted significance value.

9. The system of claim 8 , wherein determining a contribution value of the light source in a pair to a color of the point in the pair comprises:

casting a ray from the point to the light source; and

performing an analysis of the ray to determine the contribution value.

10. The system of claim 9 , the operations further comprising:

determining, for each cell and for each light source, a ratio of a count of rays cast to the light source from the points in the cell that reached the light source and a total count of rays cast to the light source from the points in the cell; and

updating each adjusted significance value for each cell and each light source based on the ratio associated with the corresponding cell and light source.

11. The system of claim 8 , wherein adjusting the significance value comprises:

normalizing each significance value associated with the cell based on a sum of all significance values associated with the cell.

12. The system of claim 8 , wherein:

the image is captured from an image capturing point; and

subdividing the scene into the plurality of cells comprises:

creating a virtual space around the image capturing point,

generating a plurality of quadrilaterals that neighbor the virtual space, and

assigning points covered by each quadrilateral to a cell of the plurality of cells.

13. The system of claim 8 , wherein subdividing the scene into the plurality of cells comprises dividing the scene into a plurality of 3-dimensional voxels and assigning points in an area covered by each 3-dimensional voxel to a cell of the plurality of cells.

14. The system of claim 8 , wherein subdividing the scene into the plurality of cells comprises:

dividing the image into a plurality of portions;

determining an area in the scene covered by each portion of the plurality of portions; and

assigning points in each area in the scene covered by each portion of the plurality of portions to a cell of the plurality of cells.

15. A computer program product encoded on one or more non-transitory computer storage media, the computer program product comprising instructions that when executed by one or more computers cause the one or more computers to perform operations for rendering an image of a scene, wherein the scene is affected by a plurality of light sources, the operations comprising:

subdividing the scene into a plurality of cells;

performing data collection to generate significance values, including:

sampling a plurality of light source—point pairs, each pair including a respective light source of the plurality of light sources and a point in the scene;

for each pair, determining a contribution value of the light source in the pair to a color of the point in the pair;

for each cell and for each light source:

determining a maximum contribution value of the contribution values for the light source to the color of the points that are in the cell;

determining, based on the maximum contribution value, a significance value that is a measure of an estimated importance of the light source in rendering a portion of the image corresponding to the cell; and

adjusting the significance value to obtain an adjusted significance value; and

rendering the image of the scene by sampling light sources having a higher adjusted significance value more often than light sources having a lower adjusted significance value.

16. The computer program product of claim 15 , wherein determining a contribution value of the light source in a pair to a color of the point in the pair comprises:

casting a ray from the point to the light source; and

performing an analysis of the ray to determine the contribution value.

17. The computer program product of claim 15 , wherein adjusting the significance value comprises:

normalizing each significance value associated with the cell based on a sum of all significance values associated with the cell.

18. The computer program product of claim 15 , wherein:

the image is captured from an image capturing point; and

subdividing the scene into the plurality of cells comprises:

creating a virtual space around the image capturing point,

generating a plurality of quadrilaterals that neighbor the virtual space, and

assigning points covered by each quadrilateral to a cell of the plurality of cells.

19. The computer program product of claim 15 , wherein subdividing the scene into the plurality of cells comprises dividing the scene into a plurality of 3-dimensional voxels and assigning points in an area covered by each 3-dimensional voxel to a cell of the plurality of cells.

20. The computer program product of claim 15 , wherein subdividing the scene into the plurality of cells comprises:

dividing the image into a plurality of portions;

determining an area in the scene covered by each portion of the plurality of portions; and

assigning points in each area in the scene covered by each portion of the plurality of portions to a cell of the plurality of cells.