“Structured importance sampling of environment maps”

We introduce structured importance sampling, a new technique for efficiently rendering scenes illuminated by distant natural illumination given in an environment map. Our method handles occlusion, high-frequency lighting, and is significantly faster than alternative methods based on Monte Carlo sampling. We achieve this speedup as a result of several ideas. First, we present a new metric for stratifying and sampling an environment map taking into account both the illumination intensity as well as the expected variance due to occlusion within the scene. We then present a novel hierarchical stratification algorithm that uses our metric to automatically stratify the environment map into regular strata. This approach enables a number of rendering optimizations, such as pre-integrating the illumination within each stratum to eliminate noise at the cost of adding bias, and sorting the strata to reduce the number of sample rays. We have rendered several scenes illuminated by natural lighting, and our results indicate that structured importance sampling is better than the best previous Monte Carlo techniques, requiring one to two orders of magnitude fewer samples for the same image quality.

1. BLINN, J., AND NEWELL, M. 1976. Texture and reflection in computer generated images. Communications of the ACM 19, 542–546. Google ScholarDigital Library
2. CABRAL, B., MAX, N., AND SPRINGMEYER, R. 1987. Bidirectional reflection functions from surface bump maps. In SIGGRAPH 87, 273–281. Google ScholarDigital Library
3. CABRAL, B., OLANO, M., AND NEMEC, P. 1999. Reflection space image based rendering. In SIGGRAPH 99, 165–170. Google Scholar
4. COHEN, J., AND DEBEVEC, P., 2001. LightGen, HDRShop plugin. http://www.ict.usc.edu/~jcohen/lightgen/lightgen.html.Google Scholar
5. DEBEVEC, P. 1998. Rendering synthetic objects into real scenes: Bridging traditional and image-based graphics with global illumination and high-dynamic range photography. In SIGGRAPH 98, 189–198. Google Scholar
6. DROR, R., LEUNG, T., ADELSON, E., AND WILLSKY, A. 2001. Statistics of real-world illumination. In CVPR 01, 164–171.Google Scholar
7. FEDER, T., AND GREENE, D. 1988. Optimal algorithms for approximate clustering. In ACM Symposium on Theory of Computing. Google Scholar
8. FIELD, D. 1987. Relations between the statistics of natural images and the response properties of cortical cells. JOSA A, 4, 2379–2394.Google ScholarCross Ref
9. GONZALEZ, R. C., AND WOODS, R. E. 2001. Digital Image Processing. Prentice Hall. Google Scholar
10. GREENE, N. 1986. Environment mapping and other applications of world projections. IEEE Computer Graphics & Applications 6, 11, 21–29. Google ScholarDigital Library
11. HOCHBAUM, D., AND SHMOYS, D. 1985. A best possible heuristic for the k-center problem. Mathematics of Operations Research.Google Scholar
12. HUANG, J., AND MUMFORD, D. 1999. Statistics of natural images and models. In CVPR, 541–547.Google Scholar
13. KAJIYA, J. 1986. The rendering equation. In SIGGRAPH 86, 143–150. Google ScholarDigital Library
14. KAUTZ, J., AND MCCOOL, M. 2000. Approximation of glossy reflection with prefiltered environment maps. In Graphics Interface, 119–126.Google Scholar
15. KAUTZ, J., VÁZQUEZ, P., HEIDRICH, W., AND SEIDEL, H. 2000. A unified approach to prefiltered environment maps. In EGRW 00, 185–196. Google ScholarDigital Library
16. MILLER, G., AND HOFFMAN, C. 1984. Illumination and reflection maps: Simulated objects in simulated and real environments. SIGGRAPH 84 Advanced Computer Graphics Animation seminar notes.Google Scholar
17. NEMHAUSER, G. L., AND WOLSEY, L. A. 1988. Integer and Combinatorial Optimization. John Wiley and Sons, Inc. Google Scholar
18. RAMAMOORTHI, R., AND HANRAHAN, P. 2001. An efficient representation for irradiance environment maps. In SIGGRAPH 01, 497–500. Google Scholar
19. RAMAMOORTHI, R., AND HANRAHAN, P. 2002. Frequency space environment map rendering. In SIGGRAPH 02, 517–526. Google Scholar
20. SLOAN, P., KAUTZ, J., AND SNYDER, J. 2002. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. In SIGGRAPH 02, 527–536. Google Scholar
21. VEACH, E., AND GUIBAS, L. J. 1995. Optimally combining sampling techniques for monte carlo rendering. In SIGGRAPH ’95, 419–428. Google Scholar
22. WARD, G. J., RUBINSTEIN, F. M., AND CLEAR, R. D. 1988. A ray tracing solution for diffuse interreflection. In Computer Graphics (SIGGRAPH ’88 Proceedings), J. Dill, Ed., vol. 22, 85–92. Google Scholar
23. WARD, G. 1991. Adpative shadow testing for ray tracing. In Second Eurographics Workshop on Rendering.Google Scholar