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. Chen, W., Bouguet, J., Chu, M., and Grzeszczuk, R. 2002. Light field mapping: Efficient representation and hardware rendering of surface light fields. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 447--456.
3. Dorsey, J., Arvo, J., and Greenberg, D. 1995. Interactive design of complex time-dependent lighting. IEEE Computer Graphics and Applications 15, 2, 26--36.
4. Durand, F., Holzschuch, N., Soler, C., Chan, E., and Sillion, F. 2005. A frequency analysis of light transport. ACM Transactions on Graphics (SIGGRAPH 2005) 25, 3, 1115--1126.
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. Gray, R. 2006. Toeplitz and circulant matrices: A review. Foundations and Trends in Communications and Information Theory 2, 3, 155--239.
7. Grenander, U., and Szego, G. 1958. Toeplitz Forms and Their Applications. University of Calif. Press, Berkeley and Los Angeles.
8. Lawrence, J., Ben-Artzi, A., DeCoro, C., Matusik, W., Pfister, H., Ramamoorthi, R., and Rusinkiewicz, S., 2006. Inverse shade trees for non-parametric material representation and editing. ACM Transactions on Graphics (SIGGRAPH 2006) 25, 3 (jul).
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. Matusik, W., Pfister, H., Ngan, A., Beardsley, P., Ziegler, R., and McMillan, L. 2002. Image-based 3D photography using opacity hulls. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 427--437.
11. Nayar, S., Belhumeur, P., and Boult, T. 2004. Lighting-sensitive displays. ACM Transactions on Graphics 23, 4, 963--979.
12. Ng, R., Ramamoorthi, R., and Hanrahan, P. 2003. All-frequency shadows using non-linear wavelet lighting approximation. ACM Transactions on Graphics (SIGGRAPH 2003) 22, 3, 376--381.
13. Nimeroff, J., Simoncelli, E., and Dorsey, J. 1994. Efficient re-rendering of naturally illuminated environments. In EuroGraphics Workshop on Rendering, 359--373.
14. Nishino, K., Sato, Y., and Ikeuchi, K., 2001. Eigen-texture method: Appearance compression and synthesis based on a 3d model. IEEE PAMI 23, 11, 1257--1265.
15. Nishino, K., Nayar, S., and Jebara, T. 2005. Clustered blockwise pca for representing visual data. IEEE Transactions on Pattern Analysis and Machine Intelligence 27, 10, 1675--1679.
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. Ramamoorthi, R., and Hanrahan, P. 2004. A signal processing framework for reflection. ACM TOG 23, 4, 1004--1042.
18. Ramamoorthi, R., Koudelka, M., and Belhumeur, P. 2005. A fourier theory for cast shadows. IEEE Transactions on Pattern Analysis and Machine Intelligence 27, 2, 288--295.
19. Ramamoorthi, R. 2002. Analytic PCA construction for theoretical analysis of lighting variability in images of a lambertian object. IEEE PAMI 24, 10, 1322--1333.
20. Shirdhonkar, S., and Jacobs, D. 2005. Non-negative lighting and specular object recognition. In ICCV 05, 1323--1330.
21. Sloan, P., Kautz, J., and Snyder, J. 2002. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. ACM Transactions on Graphics (SIGGRAPH 2002) 21, 3, 527--536.
22. Sloan, P., Hall, J., Hart, J., and Snyder, J. 2003. Clustered principal components for precomputed radiance transfer. ACM Transactions on Graphics (SIGGRAPH 2003) 22, 3, 382--391.
23. Soler, C., and Sillion, F. 1998. Fast calculation of soft shadow textures using convolution. In SIGGRAPH 98, 321--332.
24. Wang, R., Tran, J., and Luebke, D. 2006. All-frequency relighting of glossy objects. ACM Transactions on Graphics 25, 2, 293--318.

Index Terms

• Computing methodologies

  • Computer graphics

    • Image manipulation

      • Texturing