In this project, we developed methods for accurately and efficiently sampling free path, the distance between two successive scattering points, inside inhomogeneous participating media. In the computer graphics field, ray marching is widely used to sample the free path. However, it will usually introduce bias if the sampling interval is not small enough. In the nuclear physics field, Woodcock tracking (also known as delta tracking, pseudo scattering, ...) has been used for free path sampling. Although Woodcock tracking is proven to be unbiased, it becomes inefficient for inhomogeneous participating media.

In this project, we extend Woodcock tracking and introduce automatic space partitioning techniques to accelerate Woodcock tracking. The resulting algorithm is still unbiased.

First, we developed a cost model for partitioning the space in the 1D case, and incorporated a heuristic approach to use this model for partitioning the 3D space. The resulting space partitioning structure is a kd-tree. Using our method, we obtain one to two orders of magnitude speed up over Woodcock tracking.

"Unbiased, Adaptive Stochastic Sampling for Rendering Inhomogeneous Participating Media" Yonghao Yue, Kei Iwasaki, Bing-Yu Chen, Yoshinori Dobashi, and Tomoyuki Nishita ACM Transactions on Graphics (Proc. SIGGRAPH Asia 2010) Vol.29, No.6, pp.177:1-7, 2010, Seoul, Korea [Abstract, paper, video]

Then we generalized the cost model to the 3D case. Given a space partitioning structure, we can estimate the parformance gain using the cost model (a closed form function). Based on this cost model, we can utilize different types of data structures for partitioning the space, like unifrom grid, octree, kd-tree.

"Toward Optimal Space Partitioning for Unbiased, Adaptive Free Path Sampling of Inhomogeneous Participating Media" Yonghao Yue, Kei Iwasaki, Bing-Yu Chen, Yoshinori Dobashi, and Tomoyuki Nishita Computer Graphics Forum (Proc. Pacific Graphics 2011) Vol.30, No.7, pp.1911-1919, Sep 2011, Kaohsiung, Taiwan [Abstract, paper]

Keywords:
Participating media, free path sampling, space partitioning, Monte Carlo technique, unbiased