Efficient Sampling of Products of Functions
using Wavelets

M.S. Thesis

Petrik Clarberg
Lund University


Advisor: Tomas Akenine-Möller

Completed: March 2005



This thesis presents a novel method for importance sampling the product of two-dimensional functions. The functions are represented as wavelets, which enables rapid computation of the product as well as efficient compression. The sampling is done by computing wavelet coefficients for the product on-the-fly, and hierarchically sampling the wavelet tree. The wavelet multiplication is guided by the sampling distribution. Hence, the proposed method is very efficient as it avoids a full computation of the product. The generated sampling distribution is superior to previous methods, as it exactly matches the probability density of the product of the two functions. As an application, the method is applied to the problem of rendering a virtual scene with realistic measured materials under complex direct illumination provided by a high-dynamic range environment map.


My original idea for this thesis was to implement a PRT (precomputed radiance transfer) system using wavelets to represent the transport vectors, and then try to extend previous work in order to find a way to handle dynamic scenes. The work soon evolved into research of methods for importance sampling according to the wavelet representations. I then realized that it is relatively straightforward to combine wavelet sampling with wavelet products, introduced by Ng et al. in 2004. Thus, efficient sampling of products of functions was made possible. By using this novel sampling method, samples can be distributed according to the product of a BRDF and an environment map. The samples are then used for sampling the visibility through standard ray tracing, hence eliminating the need for precomputed visibility.

Most of my thesis research was conducted at the University of California at San Diego, where I was visiting during August 2004 to the end of February 2005. Together with Henrik Wann Jensen, Tomas Akenine-Möller, and Wojciech Jarosz, we further developed the ideas presented in this thesis. The main extensions were a generalization of the wavelet product to higher dimensions, and a novel sampling scheme that uses multi-dimensional low-discrepancy points for reducing the variance. Our efforts resulted in a paper that was published at SIGGRAPH 2005.


[ thesis.pdf ] (10MB Adobe PDF)



Simple scene rendered using 30 samples per pixel. The samples were generated by wavelet-based importance sampling of the BRDF times the environment map. The lighting is from Galileo's Tomb and the BRDFs are measured from real materials.


Comparison between wavelet-based product sampling (top two rows) and
environment map importance sampling (bottom two rows).