“An unbiased ray-marching transmittance estimator” by Kettunen, d’Eon, Pantaleoni and Novák

We present an in-depth analysis of the sources of variance in state-of-the-art unbiased volumetric transmittance estimators, and propose several new methods for improving their efficiency. These combine to produce a single estimator that is universally optimal relative to prior work, with up to several orders of magnitude lower variance at the same cost, and has zero variance for any ray with non-varying extinction. We first reduce the variance of truncated power-series estimators using a novel efficient application of U-statistics. We then greatly reduce the average expansion order of the power series and redistribute density evaluations to filter the optical depth estimates with an equidistant sampling comb. Combined with the use of an online control variate built from a sampled mean density estimate, the resulting estimator effectively performs ray marching most of the time while using rarely-sampled higher-order terms to correct the bias.

1. John Amanatides and Andrew Woo. 1987. A Fast Voxel Traversal Algorithm for Ray Tracing. In EG 1987-Technical Papers. Eurographics Association. Google ScholarCross Ref
2. Nir Benty, Kai-Hwa Yao, Petrik Clarberg, Lucy Chen, Simon Kallweit, Tim Foley, Matthew Oakes, Conor Lavelle, and Chris Wyman. 2020. The Falcor Rendering Framework. https://github.com/NVIDIAGameWorks/FalcorGoogle Scholar
3. H. W. Bertini. 1963. Monte Carlo simulations on intranuclear cascades. Technical Report ORNL-3383. Oak Ridge National Laboratory, Oak Ridge, TN, USA. Google Scholar
4. Alexandros Beskos, Omiros Papaspiliopoulos, Gareth O Roberts, and Paul Fearnhead. 2006. Exact and computationally efficient likelihood-based estimation for discretely observed diffusion processes (with discussion). Journal of the Royal Statistical Society: Series B (Statistical Methodology) 68, 3 (2006), 333–382. Google ScholarCross Ref
5. Gyan Bhanot and Anthony D Kennedy. 1985. Bosonic lattice gauge theory with noise. Physics letters B 157, 1 (1985), 70–76. Google ScholarCross Ref
6. Benedikt Bitterli, Srinath Ravichandran, Thomas Müller, Magnus Wrenninge, Jan Novák, Steve Marschner, and Wojciech Jarosz. 2018. A radiative transfer framework for non-exponential media. ACM Transactions on Graphics 37, 6 (2018). Google ScholarDigital Library
7. Thomas E Booth. 2007. Unbiased Monte Carlo estimation of the reciprocal of an integral. Nuclear science and engineering 156, 3 (2007), 403–407. Google ScholarCross Ref
8. NP Buslenko, DI Golenko, Yu A Shreider, I.M. Sobol’,, and VG Sragovich. 1966. The Monte Carlo method: the method of statistical trials. Vol. 87. Pergamon.Google Scholar
9. J. C. Butcher and H. Messel. 1958. Electron Number Distribution in Electron-Photon Showers. Phys. Rev. 112 (Dec. 1958), 2096–2106. Issue 6. Google ScholarCross Ref
10. RH Cameron. 1954. The generalized heat flow equation and a corresponding Poisson formula. Annals of Mathematics (1954), 434–462. Google ScholarCross Ref
11. LL Carter, ED Cashwell, and WM Taylor. 1972. Monte Carlo sampling with continuously varying cross sections along flight paths. Nucl. Sci. Eng 48 (1972), 403–411. Google ScholarCross Ref
12. Subrahmanyan Chandrasekhar. 1960. Radiative Transfer. Dover.Google Scholar
13. Nan Chen and Zhengyu Huang. 2012. Brownian meanders, importance sampling and unbiased simulation of diffusion extremes. Operations research letters 40, 6 (2012), 554–563. Google ScholarCross Ref
14. W. A. Coleman. 1968. Mathematical Verification of a Certain Monte Carlo Sampling Technique and Applications of the Technique to Radiation Transport Problems. Nuclear Science and Engineering 32, 1 (1968), 76–81. Google ScholarCross Ref
15. DR Cox and PAW Lewis. 1966. The statistical analysis of Series of Events. Wiley.Google Scholar
16. SN Cramer. 1978. Application of the fictitious scattering radiation transport model for deep-penetration Monte Carlo calculations. Nuclear Science and Engineering 65, 2 (1978), 237–253. Google ScholarCross Ref
17. Eugene d’Eon. 2019. A reciprocal formulation of nonexponential radiative transfer. 1: Sketch and motivation. Journal of Computational and Theoretical Transport 48, 6 (2019), 201–262. Google ScholarCross Ref
18. Mouna El Hafi, Stephane Blanco, Jérémi Dauchet, Richard Fournier, Mathieu Galtier, Loris Ibarrart, Jean-Marc Tregan, and Najda Villefranque. 2021. Three viewpoints on null-collision Monte Carlo algorithms. Journal of Quantitative Spectroscopy and Radiative Transfer 260, 107402. Google ScholarCross Ref
19. Paul Fearnhead, Omiros Papaspiliopoulos, and Gareth O Roberts. 2008. Particle filters for partially observed diffusions. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 70, 4 (2008), 755–777. Google ScholarCross Ref
20. M. Galtier, S. Blanco, Cyril Caliot, C. Coustet, J. Dauchet, Mouna El-Hafi, Vincent Eymet, R. Fournier, J. Gautrais, A. Khuong, B. Piaud, and Guillaume Terrée. 2013. Integral formulation of null-collision Monte Carlo algorithms. Journal of Quantitative Spectroscopy and Radiative Transfer 125 (Aug. 2013), 57–68. Google ScholarCross Ref
21. Iliyan Georgiev, Zackary Misso, Toshiya Hachisuka, Derek Nowrouzezahrai, Jaroslav Křivánek, and Wojciech Jarosz. 2019. Integral formulations of volumetric transmittance. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia) 38, 6 (Nov. 2019). https://doi.org/10/dffnGoogle Scholar
22. Mark Girolami, Anne-Marie Lyne, Heiko Strathmann, Daniel Simpson, and Yves Atchade. 2013. Playing Russian roulette with intractable likelihoods. arXiv preprint arXiv:1306.4032 (2013). https://arxiv.org/abs/1306.4032Google Scholar
23. Gerald J Glasser. 1962. Minimum variance unbiased estimators for Poisson probabilities. Technometrics 4, 3 (1962), 409–418. Google ScholarCross Ref
24. Paul R Halmos. 1946. The theory of unbiased estimation. The Annals of Mathematical Statistics (1946), 34–43. Google ScholarCross Ref
25. Pierre E Jacob, Alexandre H Thiery, et al. 2015. On nonnegative unbiased estimators. The Annals of Statistics 43, 2 (2015), 769–784. Google ScholarCross Ref
26. Adrian Jarabo, Carlos Aliaga, and Diego Gutierrez. 2018. A Radiative Transfer Framework for Spatially-Correlated Materials. ACM Transactions on Graphics 37, 4 (2018), 14. Google ScholarDigital Library
27. NL Johnson. 1951. Estimators of the probability of the zero class in Poisson and certain related populations. The Annals of Mathematical Statistics 22, 1 (1951), 94–101. Google ScholarCross Ref
28. Daniel Jonsson, Joel Kronander, Jonas Unger, Thomas B Schon, and Magnus Wrenninge. 2020. Direct Transmittance Estimation in Heterogeneous Participating Media Using Approximated Taylor Expansions. IEEE Transactions on Visualization and Computer Graphics (2020). Google ScholarCross Ref
29. Robert W Klein and Stephen D Roberts. 1984. A time-varying Poisson arrival process generator. Simulation 43, 4 (1984), 193–195. Google ScholarCross Ref
30. Christopher Kulla and Marcos Fajardo. 2011. Importance Sampling of Area Lights in Participating Media. ACM SIGGRAPH 2011 Talks, SIGGRAPH’11, 55. Google ScholarDigital Library
31. Anthony Lee, Simone Tiberi, and Giacomo Zanella. 2019. Unbiased approximations of products of expectations. Biometrika 106, 3 (Sept. 2019). Google ScholarCross Ref
32. A J Lee. 1990. U-statistics: Theory and Practice. Routledge.Google Scholar
33. David Legrady, Balazs Molnar, Milan Klausz, and Tibor Major. 2017. Woodcock tracking with arbitrary sampling cross section using negative weights. Annals of Nuclear Energy 102 (04 2017), 116–123. Google ScholarCross Ref
34. L Lin, K F Liu, and J Sloan. 2000. A noisy Monte Carlo algorithm. Physical Review. D, Particles Fields 61 (Apr 2000). Issue 7. Google ScholarCross Ref
35. Savino Longo. 2002. Direct derivation of Skullerud’s Monte Carlo method for charged particle transport from the linear Boltzmann equation. Physica A: Statistical Mechanics and its Applications 313, 3-4 (2002), 389–396. Google ScholarCross Ref
36. Anne-Marie Lyne, Mark Girolami, Yves Atchadé, Heiko Strathmann, Daniel Simpson, et al. 2015. On Russian roulette estimates for Bayesian inference with doubly-intractable likelihoods. Statistical science 30, 4 (2015), 443–467. Google ScholarCross Ref
37. D. G. Mead. 1992. Newton’s Identities. The American Mathematical Monthly 99, 8 (1992), 749–751. http://www.jstor.org/stable/2324242Google ScholarCross Ref
38. GA Mikhailov. 1970. A method for simulating the mean free path of a particle. Soviet Atomic Energy 28, 2 (1970), 224–225. Google ScholarCross Ref
39. Gennadii A. Mikhailov. 1992. Optimization of weighted Monte Carlo methods. Springer. https://www.springer.com/gp/book/9783642759833Google Scholar
40. Rupert G Miller. 1974. The jackknife-a review. Biometrika 61, 1 (1974), 1–15. Google ScholarCross Ref
41. Sarat Babu Moka, Dirk P Kroese, and Sandeep Juneja. 2019. Unbiased estimation of the reciprocal mean for non-negative random variables. In 2019 Winter Simulation Conference (WSC). IEEE, 404–415. Google ScholarCross Ref
42. Ken Museth. 2013. VDB: High-Resolution Sparse Volumes with Dynamic Topology. ACM Trans. Graph. 32, 3, Article 27 (July 2013), 22 pages. Google ScholarDigital Library
43. Adolfo Muñoz. 2014. Higher Order Ray Marching. Computer Graphics Forum 33, 8 (2014), 167–176. Google ScholarDigital Library
44. Jerzy Neyman and Elizabeth L Scott. 1960. Correction for bias introduced by a transformation of variables. The Annals of Mathematical Statistics 31, 3 (1960), 643–655. https://www.jstor.org/stable/2237574Google ScholarCross Ref
45. Jan Novák, Iliyan Georgiev, Johannes Hanika, and Wojciech Jarosz. 2018. Monte Carlo Methods for Volumetric Light Transport Simulation. Computer Graphics Forum (Proceedings of Eurographics – State of the Art Reports) 37, 2 (May 2018). Google ScholarCross Ref
46. Jan Novák, Andrew Selle, and Wojciech Jarosz. 2014. Residual ratio tracking for estimating attenuation in participating media. ACM Trans. Graph. 33, 6 (2014), 179–1. Google ScholarDigital Library
47. Omiros Papaspiliopoulos. 2011. Monte Carlo probabilistic inference for diffusion processes: a methodological framework. Cambridge University Press, 82–103. Google ScholarCross Ref
48. Raghu Pasupathy. 2011. Generating Nonhomogeneous Poisson Processes. American Cancer Society. Google ScholarCross Ref
49. Mark Pauly, Thomas Kollig, and Alexander Keller. 2000. Metropolis Light Transport for Participating Media. Rendering Techniques 2000 (11 2000). Google ScholarCross Ref
50. Matthias Raab, Daniel Seibert, and Alex Keller. 2006. Unbiased Global Illumination with Participating Media. In Monte Carlo and Quasi Monte Carlo Methods 2006. Springer, 591–601. Google ScholarCross Ref
51. Ravi Ramamoorthi, John Anderson, Mark Meyer, and Derek Nowrouzezahrai. 2012. A Theory of Monte Carlo Visibility Sampling. ACM Trans. Graph. 31, 5, Article 121 (Sept. 2012). Google ScholarDigital Library
52. H. R. Skullerud. 1968. The stochastic computer simulation of ion motion in a gas subjected to a constant electric field. Journal of Physics D: Applied Physics 1, 11 (1968), 1567–1568. Google ScholarCross Ref
53. László Szirmay-Kalos, Balázs Tóth, and Milán Magdics. 2011. Free path sampling in high resolution inhomogeneous participating media. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 85–97. Google ScholarCross Ref
54. Wolfgang Wagner. 1987. Unbiased Monte Carlo evaluation of certain functional integrals. J. Comput. Phys. 71, 1 (1987), 21–33. Google ScholarDigital Library
55. Wolfgang Wagner. 1988. Monte Carlo evaluation of functionals of solutions of stochastic differential equations. Variance reduction and numerical examples. Stochastic Analysis and Applications 6, 4 (1988), 447–468. Google ScholarCross Ref
56. E Woodcock, T Murphy, P Hemmings, and S Longworth. 1965. Techniques used in the GEM code for Monte Carlo neutronics calculations in reactors and other systems of complex geometry. Technical Report ANL-7050. Argonne National Laboratory.Google Scholar
57. C. D. Zerby, R. B. Curtis, and H. W. Bertini. 1961. The relativistic doppler problem. Technical Report ORNL-61-7-20. Oak Ridge National Laboratory, Oak Ridge, TN, USA. Google ScholarCross Ref