Steerable Importance Sampling

We present an algorithm for efficient stratified importance sampling of environment maps that generates samples in the positive hemisphere defined by local orientation of arbitrary surfaces while accounting for cosine weighting. The importance function is dynamically adjusted according to the surface normal using steerable basis functions. The algorithm is easy to implement and requires no user-defined parameters. As a preprocessing step, we approximate the incident illumination from an environment map as a continuous piecewise linear function on P2 and represent this as a triangulated height field. The product of this approximation and a dynamically orientable steering function, viz. the cosine lobe, serves as an importance sampling function. Our method allows the importance function to be sampled with an asymptotic cost of O(logn) per sample where n is the number of triangles. The most novel aspect of the algorithm is its ability to dynamically compute normalization factors which are integrals of the illumination over the positive hemispheres defined by the local surface normals during shading. The key to this feature is that the weight variation of each triangle due to the clamped cosine steering function can be well approximated by a small number of spherical harmonic coefficients which can be accumulated over any collection of triangles, in any orientation, without introducing higher-order terms. Consequently, the weighted integral of the entire steerable piecewise-linear approximation is no more costly to compute than that of a single triangle, which makes re-weighting and re-normalizing with respect to any surface orientation a trivial constant-time operation. The choice of spherical harmonics as the set of basis functions for our steerable importance function allows for easy rotation between coordinate systems. Another novel element of our algorithm is an analytic parametrization for generating stratified samples with linearly-varying density over- a triangular support.