Clustered principal components for precomputed radiance transfer

• US 7,167,176 B2
• Filed: 08/15/2003
• Issued: 01/23/2007
• Est. Priority Date: 08/15/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Snyder, John Michael, Sloan, Peter-Pike, Hall, Jesse D.
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): REPKO, JASON MICHAEL
• Application Number:
  US10/641,472
• Publication Number:
  US 20050035965A1
• Time in Patent Office: 1,257 Days
• Field of Search: 382/252, 382/253, 345/426
• US Class Current: 345/426
• CPC Class Codes: G06T 15/50 Lighting effects

Abstract

Real-time processing includes per-point transfer matrices forming a high-dimensional surface signal that is compressed using clustered principal component analysis (CPCA). CPCA partitions multiple samples into fewer clusters, each cluster approximating the signal as an affine subspace. Further, source radiance is input to a processor, which approximates source radiance using spherical harmonic basis to produce a set of source radiance coefficients. A graphics processing unit (GPU) processes the source radiance coefficients through the transfer matrix model for each cluster. The result of such processing is the exit radiance, which parameterizes the radiance leaving the surface of the object at each point, thus producing the shading for each point of the virtual object in real time.

Claims

1. A graphics processing method for illuminating a geometrical object, the method comprising:

compressing a quantity of per-vertex transfer matrices by, at least;

partitioning the per-vertex matrices into a quantity of clusters fewer in number than the quantity of per-vertex matrices, and

approximating each cluster as an affine subspace with a dimensionality dependent on at least the cluster;

computing a transfer matrix model for each cluster; and

producing an exit radiance for each cluster by applying the transfer matrix model to at least one input parameter the exit radiance producing shading for rendering and presentation on a display.

2. The method according to claim 1, wherein the at least one input parameter is a viewing parameter.

3. The method according to claim 1, wherein the at least one input parameter is a lighting parameter.

4. The method according to claim 1, wherein the transfer matrix model includes a transfer matrix.

5. The method according to claim 4, wherein the exit radiance is:

y(v_p)·

(M_pl)

wherein

l is a light column vector,

M_p is a transfer matrix, and

y(v_p) is an exit radiance basis in direction v_p.

6. The method according to claim 1, wherein the transfer matrix model includes a diffuse transfer vector.

7. The method according to claim 6, wherein the exit radiance is:

t_p·

l

wherein

l is a light column vector, and

t_p, is a diffuse transfer row vector.

8. The method according to claim 1, wherein

the exit radiance is:

t_p·

l

wherein

l is a light column vector, and

t_p is a transfer vector.

9. The method according to claim 1, wherein the transfer matrix model includes an exit radiance vector.

10. The method according to claim 9, wherein

the exit radiance is:

y(v_p)·

e_p

wherein

y(v_p) is an exit radiance basis in direction v_p, and

e_p is an exit radiance colunm vector.

11. The method according to claim 1, wherein the per-vertex transfer matrices correspond to surface points of the geometrical object.

12. The method according to claim 1, wherein compressing the per-vertex matrices into clusters includes:

partitioning the per-vertex matrices based on a distance from a per-vertex transfer matrix to a mean of the transfer matrices in each cluster, and

performing a PCA analysis on the transfer matrices.

13. The method according to claim 1, wherein compressing the per-vertex matrices into clusters includes partitioning into respective clusters per-vertex matrices based upon a measured approximation error.

14. The method according to claim 13, wherein partitioning into respective clusters per-vertex matrices based upon a measured approximation error includes iteratively replacing the transfer matrix model of the respective clusters with a mean of the corresponding transfer matrices added to a linear combination of representative transfer matrices.

15. The method according to claim 1, wherein the transfer matrix model for each cluster is determined as a linear combination of representative transfer matrices.

16. The method according to claim 15, wherein linear weights vary for each representative transfer matrix of the respective clusters.

17. The method according to claim 1, wherein e_p is an exit radiance spherical function (in exit basis), and wherein producing the exit radiance for each cluster includes computing e_p(v_p) which is the exit radiance in direction v_p, as:

$e_p<br><br>\left(v_p\right)=y^T<br><br>\left(v_p\right)<br><br>\left(\left(M_{C_p}^0<br><br>l\right)+\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>w_p^i<br><br>\left(M_{C_p}^i<br><br>l\right)\right)$

wherein further y(v_p) is an exit basis evaluated in direction v_p,

C_p is the cluster of which p is a member,

Mⁱ_Cp is the i-th representative source-to-exit transfer matrix for cluster C_p, and

l is a light vector (in source basis).

18. The method according to claim 1, wherein producing the exit radiance includes approximating exit radiance vectors using a least-squares optimal projection of spherical harmonics onto a hemisphere.

19. The method according to claim 1, wherein the compressing and computing are processed in an off-line domain and the producing is processed in an on-line domain.

20. The method according to claim 1, wherein compressing per-vertex transfer matrices into clusters includes producing radiance transfer data for multiple surface points of the object by simulating self shadowing and inter-reflections at each of the multiple surface points.

21. The method according to claim 1, further comprising re-classifying each per-vertex transfer matrix into clusters corresponding to adjacent vertices in order to reduce overdraw.

22. The method according to claim 1, further comprising rendering an image of the geometrical object by, for every mesh face in a cluster to which a corresponding vertex belongs, blending using a linear partition of unity if the respective mesh face straddles multiple clusters.

45. The method according to claim 1, wherein compressing further comprises superclustering to reduce overdraw.

46. The method according to claim 45, wherein a number of clusters in a supercluster is limited to a number of clusters capable of being rendered as a unit by rendering hardware.

23. A computer-readable medium storing one or more instructions to be executed by one or more processors to render an illuminated virtual object, the one or more instructions causing the one or more processors to:

compress a quantity of per-point transfer matrices of the virtual object by, at least;

partitioning the per-point transfer matrices into a quantity of clusters lesser in number than the quantity of per-point matrices, and

approximating each cluster as an affine subspace with a dimensionality dependent on at least the cluster;

determine a transfer matrix model for each cluster; and

produce an exit radiance for each cluster by applying the transfer matrix model for each cluster to at least one input parameter.

24. The computer-readable medium according to claim 23, wherein the at least one input parameter is a viewing parameter.

25. The computer-readable medium according to claim 23, wherein the at least one input parameter is a lighting parameter.

26. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to compress the per-point transfer matrices of the virtual object into clusters includes an instruction to partition transfer matrices based on the distance from a per-point transfer matrix to a mean of the transfer matrices in each cluster.

27. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to compress per-point transfer matrices of the virtual object into clusters includes an instruction to partition per-point transfer matrices based on a distance from a per-point transfer matrix to the transfer matrix model in each cluster.

28. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to compress the per-point matrices into clusters includes one or more instructions causing one or more processors to:

partition the per-point matrices based on a measured approximation error, and

iteratively replace the transfer matrix model of the respective clusters with a mean of the corresponding transfer matrices added to a linear combination of representative transfer matrices.

29. The computer-readable medium according to claim 23, wherein the transfer matrix model for each cluster is determined as a linear combination of representative transfer matrices for each of the respective clusters.

30. The computer-readable medium according to claim 29, wherein linear weights vary for each representative transfer matrix of the respective clusters.

31. The computer-readable medium according to claim 23, wherein the transfer matrix model approximates a transfer matrix signal, and wherein further

the exit radiance is:

y(v_p)·

(M_pl)

wherein

l is a light vector,

M_p is a transfer matrix, and

y(v_p) is an exit radiance basis in direction v_p.

32. The computer-readable medium according to claim 23, wherein the transfer matrix model approximates a diffuse transfer vector, and wherein further

the exit radiance is:

t_p·

l

wherein

l is a light vector, and

t_p is a diffuse transfer vector.

33. The computer-readable medium according to claim 23, wherein the exit radiance is:

t_p·

l

wherein

l is a light column vector, and

t_p is a transfer vector.

34. The computer-readable medium according to claim 23, wherein the transfer matrix model approximates an exit radiance vector, and wherein further the exit radiance is:

y(v_p)·

e_p

y(v_p) is an exit radiance basis in direction v_p, and

e_p, is an exit radiance vector.

35. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to produce an exit radiance includes an instruction to approximate exit radiance vectors using a least-squares optimal projection of spherical harmonics onto a hemisphere.

36. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to produce the exit radiance includes one or more instructions to:

calculate source lighting data for sampling points in the lighting environment; and

linearly transform the source lighting data.

37. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to compress transfer matrices of the virtual object into clusters is executed in an off-line domain.

38. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to determine a transfer matrix model is executed in an off-line domain.

39. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to produce the exit radiance is executed in real-time.

40. The computer-readable medium according to claim 23, further comprising one or more instructions to cause one or more processors to:

classify each transfer matrix to a cluster based on a measured approximation error;

update the transfer matrices of the respective clusters by determining a mean thereof; and

perform a PCA analysis on the updated transfer matrices.

41. The computer-readable medium according to claim 40, wherein a number of representative transfer matrices varies from one cluster to another.

42. The computer-readable medium according to claim 23, further comprising one or more instructions to cause one or more processors to re-classify each per-point transfer matrix to clusters corresponding to adjacent transfer matrices to reduce overdraw.

43. The computer-readable medium according to claim 23, further including one or more instructions to cause one or more processors to render an image of the geometrical object by, for every mesh face in a cluster to which a corresponding surface signal belongs, blending using a linear partition of unity if the respective mesh face straddles multiple clusters.

44. The computer-readable medium according to claim 23, wherein the one or more instructions causing the one or more processors to produce the exit radiance includes an instruction for a processor to compute:

$e_p<br><br>\left(v_p\right)=y^T<br><br>\left(v_p\right)<br><br>\left(\left(M_{C_p}^0<br><br>l\right)+\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>w_p^i<br><br>\left(M_{C_p}^i<br><br>l\right)\right)$

wherein further e_p is an exit radiance spherical function (in exit basis),

e_p(v_p) is an exit radiance in direction v_p,

y(v_p) is an exit basis evaluated in direction v_p,

C_p is the cluster of which p is a member,

Mⁱ_Cp is the i-th representative source-to-exit transfer matrix for cluster C_p, and

l is a light vector (in source basis).