System and method of improved calculation of diffusely reflected light
The present invention is related to rendering computer animated video and/or images generally, and to improving the calculation of diffusely reflected light. The present invention includes a system and method of computing diffusely reflected light at one or more positions on surfaces in an object scene from object scene data. The present invention typically includes the step of and/or instructions for selecting a non-regular order for processing a plurality of positions on a surface—the plurality of positions having been predetermined. The present invention also includes the step of and/or instruction for processing the plurality of positions in the non-regular order. This processing typically includes computing diffusely reflected light at a position in the plurality of positions by reference to diffusely reflected light incident on the position when deriving the diffusely reflected light at the position by reference to diffusely reflected light at other positions computed by reference to diffusely reflected light incident on the other positions is inaccurate. Alternatively, deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions computed by reference to diffusely reflected light incident on the other positions when deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions is accurate.
1. A method of computing diffusely reflected light at one or more positions on surfaces in an object scene from object scene data, the method comprising
selecting a non-regular order for processing a plurality of positions on a surface, said plurality of positions having been predetermined;
processing the plurality of positions in the non-regular order, said processing including
computing diffusely reflected light at a position in the plurality of positions by reference to diffusely reflected light incident on said position when deriving said diffusely reflected light at the position by reference to diffusely reflected light at other positions computed by reference to diffusely reflected light incident on said other positions is inaccurate; and
deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions computed by reference to diffusely reflected light incident on said other positions when said deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions is accurate.
2. The method of claim 1 , wherein
the surface comprises a NURBS; and
the plurality of positions correspond to control points of the NURBS.
3. The method of claim 1 , wherein
the surface is a subdivision surface; and
the plurality of positions correspond to vertices of the subdivision surface.
4. The method of claim 1 , wherein
the object comprises a parametric patch; and
the plurality of positions correspond to control points of the parametric patch.
5. The method of claim 1 , wherein
the surface comprises a grid of micropolygons; and
the plurality of positions correspond to vertices of the grid of micropolygons.
6. The method of claim 1 , wherein the non-regular order comprises a random order.
7. The method of claim 1 , wherein the non-regular order comprises a pseudo-random order.
8. The method of claim 1 , wherein the non-regular order comprises a quasi-random order.
9. The method of claim 1 , wherein the selecting comprises
creating a list, said list including an entry for each of said plurality of positions, a value of each entry equal to a position of said each entry in the list; and
shuffling the values of said each entry in the list, said list subsequently in the non-regular order, said list referred to during the processing step.
10. The method of claim 1 , wherein computing diffusely reflected light at a position in the plurality of positions by reference to diffusely reflected light incident on said position includes
casting a ray for the position into the object scene for intersection with an object in the object scene to compute diffuse light reflected by said object onto said position.
11. The method of claim 1 , wherein determining whether the deriving the diffusely reflected light at the position by reference to diffusely reflected light at the other positions computed by reference to diffusely reflected light incident on said other positions is inaccurate includes
computing an error value by reference to a location of the position, a location of one of said other positions, an average length of rays cast from said location of one of said other positions, a surface normal of said location of the position, and a surface normal of said location of one of said other positions; and
comparing the error value to a predefined error tolerance, wherein the deriving said diffusely reflected light at the position by reference to diffusely reflected light at other positions computed by reference to diffusely reflected light incident on said other positions is inaccurate when said error value is greater than or equal to said predefined error tolerance.
12. The method of claim 11 , further comprising
executing said computing an error value step for each of the other positions to produce a plurality of error values;
adjusting the predefined error tolerance by reference to a count of said other positions, wherein said predefined error tolerance is increased when the count reaches a predefined value; and
comparing an average of said error values to the predefined error tolerance following said adjusting step.
13. The method of claim 11 , wherein
the reference to the location of the position, the location of one of said other positions, the average length of rays cast from said location of one of said other positions, the surface normal of said location of the position, and the surface normal of said location of one of said other positions takes a form of:
ɛ
1
=
P
->
-
P
->
1
R
1
+
1
-
n
^
·
n
^
1
,
where ε 1 is the error value,
where {right arrow over (P)} is the location of the position,
where {right arrow over (P)} 1 is the location of one of said other positions,
where R 1 is the harmonic mean distance of rays cast from the location of one of said other positions,
where {circumflex over (n)} is the surface normal of the location of the position, and
where {circumflex over (n)} 1 is the surface normal of the location of one of said other positions.
14. The method of claim 1 , wherein said deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions computed by reference to diffusely reflected light incident on said other positions includes computing a weighted average of said diffusely reflected light at the other positions.
15. The method of claim 14 , wherein said computing the weighted average takes a form of:
E
=
∑
i
⟹
1
n
ɛ
i
∑
i
⟹
1
n
E
i
(
n
^
i
×
n
^
)
·
V
->
r
E
i
+
(
P
->
-
P
->
i
)
·
V
->
t
E
i
ɛ
i
where E is the weighted average of said diffusely reflected light at other positions,
where ε i is an error value computed for one of said other positions,
where n is a count of said other positions,
where E i is diffusely reflected light at said one of said other positions,
where {right arrow over (V)} r is a rotational gradient computed in conjunction with E i ,
where {right arrow over (V)} i is a translational gradient computed in conjunction with E i ,
where {right arrow over (P)} is a location of the position,
where {right arrow over (P)} i is a location of said one of said other positions,
where {circumflex over (n)} is a surface normal of the location of the position, and
where {circumflex over (n)} i is a surface normal of the location of said one of said other positions.
16. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable medium and a computer program mechanism embedded therein, the computer program mechanism comprising:
a data structure for storing object scene data, said object scene data describing objects in the object scene; and
a program including
instructions for selecting a non-regular order for processing a plurality of positions on a surface of an object in the object scene, said plurality of positions having been predetermined;
instructions for processing the plurality of positions in the non-regular order, said instructions for processing including
instructions for computing diffusely reflected light at a position in the plurality of positions by reference to diffusely reflected light incident on said position when deriving said diffusely reflected light at the position by reference to diffusely reflected light at other positions computed by reference to diffusely reflected light incident on said other positions is inaccurate; and
instructions for deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions computed by reference to diffusely reflected light incident on said other positions when said deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions is accurate.
17. The computer program product of claim 16 , wherein
the surface comprises a NURBS; and
the plurality of positions correspond to control points of the NURBS.
18. The computer program product of claim 16 , wherein
the surface is a subdivision surface; and
the plurality of positions correspond to vertices of the subdivision surface.
19. The computer program product of claim 16 , wherein
the object comprises a parametric patch; and
the plurality of positions correspond to control points of the parametric patch.
20. The computer program product of claim 16 , wherein
the surface comprises a grid of micropolygons; and
the plurality of positions correspond to vertices of the grid of micropolygons.
21. The computer program product of claim 16 , wherein the non-regular order comprises a random order.
22. The computer program product of claim 16 , wherein the non-regular order comprises a pseudo-random order.
23. The computer program product of claim 16 , wherein the non-regular order comprises a quasi-random order.
24. The computer program product of claim 16 , wherein the instructions for selecting comprises
instructions for creating a list, said list including an entry for each of said plurality of positions, a value of each entry equal to a position of said each entry in the list; and
instructions for shuffling the values of said each entry in the list, said list subsequently in the non-regular order, said list referred to during the processing step.
25. The computer program product of claim 16 , wherein the instructions for computing diffusely reflected light at a position in the plurality of positions by reference to diffusely reflected light incident on said position includes
instructions for casting a ray for the position into the object scene for intersection with an object in the object scene to compute diffuse light reflected by said object onto said position.
26. The computer program product of claim 16 , wherein the instructions for determining whether the deriving the diffusely reflected light at the position by reference to diffusely reflected light at the other positions computed by reference to diffusely reflected light incident on said other positions is inaccurate includes
instructions for computing an error value by reference to a location of the position, a location of one of said other positions, an average length of rays cast from said location of one of said other positions, a surface normal of said location of the position, and a surface normal of said location of one of said other positions; and
instructions for comparing the error value to a predefined error tolerance, wherein the deriving said diffusely reflected light at the position by reference to diffusely reflected light at other positions computed by reference to diffusely reflected light incident on said other positions is inaccurate when said error value is greater than or equal to said predefined error tolerance.
27. The computer program product of claim 11 , further comprising
instructions for executing said computing an error value step for each of the other positions to produce a plurality of error values;
instructions for adjusting the predefined error tolerance by reference to a count of said other positions, wherein said predefined error tolerance is increased when the count reaches a predefined value; and
instructions for comparing an average of said error values to the predefined error tolerance following said adjusting step.
28. The computer program product of claim 16 , wherein the instructions for deriving the diffusely reflected light at the position by reference to the diffusely reflected light at the other positions computed by reference to diffusely reflected light incident on said other positions includes
instructions for computing a weighted average of said diffusely reflected light at the other positions.