“A theory of locally low dimensional light transport” by Mahajan, Kemelmacher-Shlizerman, Ramamoorthi and Belhumeur

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.

1. Basri, R., and Jacobs, D. 2001. Lambertian reflectance and linear subspaces. In International Conference on Computer Vision, 383–390.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarCross Ref
6. Gray, R. 2006. Toeplitz and circulant matrices: A review. Foundations and Trends in Communications and Information Theory 2, 3, 155–239. Google ScholarDigital Library
7. Grenander, U., and Szego, G. 1958. Toeplitz Forms and Their Applications. University of Calif. Press, Berkeley and Los Angeles.Google Scholar
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). Google ScholarDigital Library
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. Google ScholarCross Ref
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. Google ScholarDigital Library
11. Nayar, S., Belhumeur, P., and Boult, T. 2004. Lighting-sensitive displays. ACM Transactions on Graphics 23, 4, 963–979. Google ScholarDigital Library
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. Google ScholarDigital Library
13. Nimeroff, J., Simoncelli, E., and Dorsey, J. 1994. Efficient re-rendering of naturally illuminated environments. In EuroGraphics Workshop on Rendering, 359–373.Google Scholar
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google ScholarCross Ref
17. Ramamoorthi, R., and Hanrahan, P. 2004. A signal processing framework for reflection. ACM TOG 23, 4, 1004–1042. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
20. Shirdhonkar, S., and Jacobs, D. 2005. Non-negative lighting and specular object recognition. In ICCV 05, 1323–1330. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
23. Soler, C., and Sillion, F. 1998. Fast calculation of soft shadow textures using convolution. In SIGGRAPH 98, 321–332. Google ScholarDigital Library
24. Wang, R., Tran, J., and Luebke, D. 2006. All-frequency relighting of glossy objects. ACM Transactions on Graphics 25, 2, 293–318. Google ScholarDigital Library