A theory of locally low dimensional light transport

ABSTRACT

Blockwise or Clustered Principal Component Analysis (CPCA) is commonly used to achieve real-time rendering of shadows and glossy reflections with precomputed radiance transfer (PRT). The vertices or pixels are partitioned into smaller coherent regions, and light transport in each region is approximated by a locally low-dimensional subspace using PCA. Many earlier techniques such as surface light field and reflectance field compression use a similar paradigm. However, there has been no clear theoretical understanding of how light transport dimensionality increases with local patch size, nor of the optimal block size or number of clusters.

In this paper, we develop a theory of locally low dimensional light transport, by using Szego's eigenvalue theorem to analytically derive the eigenvalues of the covariance matrix for canonical cases. We show mathematically that for symmetric patches of area A, the number of basis functions for glossy reflections increases linearly with A, while for simple cast shadows, it often increases as √A. These results are confirmed numerically on a number of test scenes. Next, we carry out an analysis of the cost of rendering, trading off local dimensionality and the number of patches, deriving an optimal block size. Based on this analysis, we provide useful practical insights for setting parameters in CPCA and also derive a new adaptive subdivision algorithm. Moreover, we show that rendering time scales sub-linearly with the resolution of the image, allowing for interactive all-frequency relighting of 1024 x 1024 images.

REFERENCES

• 1: Basri, R., and Jacobs, D. 2001. Lambertian reflectance and linear subspaces. In International Conference on Computer Vision, 383--390.
• 2: Wei-Chao Chen , Jean-Yves Bouguet , Michael H. Chu , Radek Grzeszczuk, Light field mapping: efficient representation and hardware rendering of surface light fields, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 3: Julie Dorsey , James Arvo , Donald Greenberg, Interactive Design of Complex Time-Dependent Lighting, IEEE Computer Graphics and Applications, v.15 n.2, p.26-36, March 1995 [doi>10.1109/38.365003]
• 4: Frédo Durand , Nicolas Holzschuch , Cyril Soler , Eric Chan , François X. Sillion, A frequency analysis of light transport, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 5: Garg, G., Talvala, E., Levoy, M., and Lensch, H. 2006. Symmetric photography: Exploiting data-sparseness in reflectance fields. In EuroGraphics Symposium on Rendering, 251--262.
• 6: Robert M. Gray, Toeplitz and circulant matrices: a review, Communications and Information Theory, v.2 n.3, p.155-239, August 2005 [doi>10.1561/0100000006]
• 7: Grenander, U., and Szego, G. 1958. Toeplitz Forms and Their Applications. University of Calif. Press, Berkeley and Los Angeles.
• 8: Jason Lawrence , Aner Ben-Artzi , Christopher DeCoro , Wojciech Matusik , Hanspeter Pfister , Ravi Ramamoorthi , Szymon Rusinkiewicz, Inverse shade trees for non-parametric material representation and editing, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 9: Liu, X., Sloan, P., Shum, H., and Snyder, J. 2004. All-frequency precomputed radiance transfer for glossy objects. EuroGraphics Symposium on Rendering 2004, 337--344.
• 10: Wojciech Matusik , Hanspeter Pfister , Addy Ngan , Paul Beardsley , Remo Ziegler , Leonard McMillan, Image-based 3D photography using opacity hulls, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 11: Shree K. Nayar , Peter N. Belhumeur , Terry E. Boult, Lighting sensitive display, ACM Transactions on Graphics (TOG), v.23 n.4, p.963-979, October 2004 [doi>10.1145/1027411.1027414]
• 12: Ren Ng , Ravi Ramamoorthi , Pat Hanrahan, All-frequency shadows using non-linear wavelet lighting approximation, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 13: Nimeroff, J., Simoncelli, E., and Dorsey, J. 1994. Efficient re-rendering of naturally illuminated environments. In EuroGraphics Workshop on Rendering, 359--373.
• 14: Ko Nishino , Yoichi Sato , Katsushi Ikeuchi, Eigen-Texture Method: Appearance Compression and Synthesis Based on a 3D Model, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1257-1265, November 2001 [doi>10.1109/34.969116]
• 15: Ko Nishino , Shree K. Nayar , Tony Jebara, Clustered Blockwise PCA for Representing Visual Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.10, p.1675-1679, October 2005 [doi>10.1109/TPAMI.2005.193]
• 16: Okikioulu, K. 1996. The analogue of the strong Szego limit theorem on the 2- and 3- dimensional spheres. Journal of the American Mathematical Society 9, 2, 345--372.
• 17: Ravi Ramamoorthi , Pat Hanrahan, A signal-processing framework for reflection, ACM Transactions on Graphics (TOG), v.23 n.4, p.1004-1042, October 2004 [doi>10.1145/1027411.1027416]
• 18: Ravi Ramamoorthi , Melissa Koudelka , Peter Belhumeur, A Fourier Theory for Cast Shadows, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.2, p.288-295, February 2005 [doi>10.1109/TPAMI.2005.22]
• 19: Ravi Ramamoorthi, Analytic PCA Construction for Theoretical Analysis of Lighting Variability in Images of a Lambertian Object, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.10, p.1322-1333, October 2002 [doi>10.1109/TPAMI.2002.1039204]
• 20: Sameer Shirdhonkar , David W. Jacobs, Non-Negative Lighting and Specular Object Recognition, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1323-1330, October 17-20, 2005 [doi>10.1109/ICCV.2005.168]
• 21: Peter-Pike Sloan , Jan Kautz , John Snyder, Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 22: Peter-Pike Sloan , Jesse Hall , John Hart , John Snyder, Clustered principal components for precomputed radiance transfer, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 23: Cyril Soler , François X. Sillion, Fast calculation of soft shadow textures using convolution, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.321-332, July 1998 [doi>10.1145/280814.280927]
• 24: Rui Wang , John Tran , David Luebke, All-frequency relighting of glossy objects, ACM Transactions on Graphics (TOG), v.25 n.2, p.293-318, April 2006 [doi>10.1145/1138450.1138456]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

Keywords:
all-frequency relighting, dimensionality analysis, local light transport, rendering cost analysis