“Sliced optimal transport sampling” by Paulin, Bonneel, Coeurjolly, Iehl, Webanck, et al. …

  • ©Lois Paulin, Nicolas Bonneel, David Coeurjolly, Jean-Claude Iehl, Antoine Webanck, Mathieu Desbrun, and Victor Ostromoukhov




    Sliced optimal transport sampling


Session Title: Monte Carlo and Perception


    In this paper, we introduce a numerical technique to generate sample distributions in arbitrary dimension for improved accuracy of Monte Carlo integration. We point out that optimal transport offers theoretical bounds on Monte Carlo integration error, and that the recently-introduced numerical framework of sliced optimal transport (SOT) allows us to formulate a novel and efficient approach to generating well-distributed high-dimensional pointsets. The resulting sliced optimal transport sampling, solely involving repeated 1D solves, is particularly simple and efficient for the common case of a uniform density over a d-dimensional ball. We also construct a volume-preserving map from a d-ball to a d-cube (generalizing the Shirley-Chiu mapping to arbitrary dimensions) to offer fast SOT sampling over d-cubes. We provide ample numerical evidence of the improvement in Monte Carlo integration accuracy that SOT sampling brings compared to existing QMC techniques, and derive a projective variant for rendering which rivals, and at times outperforms, current sampling strategies using low-discrepancy sequences or optimized samples.


    1. Franz Aurenhammer, Friedrich Hoffmann, and Boris Aronov. 1998. Minkowski-type theorems and least-squares clustering. Algorithmica 20, 1 (1998), 61–76.Google ScholarCross Ref
    2. Martin Bálint and Rafał K. Mantiuk. 2019. Closed Form Transmittance in Heterogeneous Media Using Cosine Noise. In Central European Seminar on Computer Graphics. https://www.cl.cam.ac.uk/~rkm38/pdfs/balint2019cosine_noise.pdfGoogle Scholar
    3. Michael Balzer, Thomas Schlömer, and Oliver Deussen. 2009. Capacity-Constrained Point Distributions: A Variant of Lloyd’s Method. ACM Trans. Graph. 28, 3 (2009), 86:1–8.Google ScholarDigital Library
    4. Nicolas Bonneel and David Coeurjolly. 2019. SPOT: Sliced Partial Optimal Transport. ACM Trans. Graph. 38, 4 (July 2019).Google ScholarDigital Library
    5. Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. 2015. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision 51, 1 (2015).Google ScholarDigital Library
    6. Nicolas Bonnotte. 2013. Unidimensional and evolution methods for optimal transportation. Ph.D. Dissertation. Paris 11.Google Scholar
    7. Robert Bridson. 2007. Fast Poisson Disk Sampling in Arbitrary Dimensions. In ACM SIGGRAPH Sketches. 22–23.Google Scholar
    8. Per Christensen, Julian Fong, Jonathan Shade, Wayne Wooten, Brenden Schubert, Andrew Kensler, Stephen Friedman, Charlie Kilpatrick, Cliff Ramshaw, Marc Bannister, and et al. 2018a. RenderMan: An Advanced Path-Tracing Architecture for Movie Rendering. ACM Trans. Graph. 37, 3 (2018), Art. 30.Google ScholarDigital Library
    9. Per Christensen, Andrew Kensler, and Charlie Kilpatrick. 2018b. Progressive Multi-Jittered Sample Sequences. Computer Graphics Forum 37, 4 (2018), 21–33.Google ScholarCross Ref
    10. Robert L. Cook. 1986. Stochastic Sampling in Computer Graphics. ACM Trans. Graph. 5, 1 (Jan. 1986), 51–72.Google ScholarDigital Library
    11. Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6 (2012), 171.Google Scholar
    12. Josef Dick and Friedrich Pillichshammer. 2010. Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press.Google ScholarDigital Library
    13. Mark A. Z. Dippé and Erling Henry Wold. 1985. Antialiasing through Stochastic Sampling. Computer Graphics 19, 3 (July 1985), 69–78.Google ScholarDigital Library
    14. Fredo Durand. 2011. A frequency analysis of Monte-Carlo and other numerical integration schemes. MIT CSAIL Technical report TR-2011-052 (2011).Google Scholar
    15. Raanan Fattal. 2011. Blue-Noise Point Sampling Using Kernel Density Model. ACM Trans. Graph. 30, 4 (July 2011), 48:1–48:12.Google ScholarDigital Library
    16. Iliyan Georgiev and Marcos Fajardo. 2016. Blue-Noise Dithered Sampling. 35:1–35:1. https://doi.org/10/gfznbxGoogle Scholar
    17. Jens André Griepentrog, Wolfgang Höppner, Hans-Christoph Kaiser, and Joachim Rehberg. 2008. A bi-Lipschitz continuous, volume preserving map from the unit ball onto a cube. Note di Matematica 28, 1 (2008), 177–193.Google Scholar
    18. Daniel Heck, Thomas Schlömer, and Oliver Deussen. 2013. Blue Noise Sampling with Controlled Aliasing. ACM Trans. Graph. 32, 3 (2013), 25:1–25:12.Google ScholarDigital Library
    19. Eric Heitz and Laurent Belcour. 2019. Distributing Monte Carlo Errors as a Blue Noise in Screen Space by Permuting Pixel Seeds Between Frames. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 149–158.Google Scholar
    20. Eric Heitz, Laurent Belcour, Victor Ostromoukhov, David Coeurjolly, and Jean-Claude Iehl. 2019. A Low-Discrepancy Sampler that Distributes Monte Carlo Errors as a Blue Noise in Screen Space. In ACM SIGGRAPH Talk.Google Scholar
    21. Edmund Hlavka. 1961. Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Annali di Matematica Pura ed Applicata 54, 1 (1961), 325–333.Google Scholar
    22. Wenzel Jakob. 2013. Mitsuba Renderer. http://www.mitsuba-renderer.org.Google Scholar
    23. Wojciech Jarosz, Afnan Enayet, Andrew Kensler, Charlie Kilpatrick, and Per Christensen. 2019. Orthogonal Array Sampling for Monte Carlo Rendering. Computer Graphics Forum 38, 4 (2019), 135–147.Google ScholarCross Ref
    24. Stephen Joe and Frances Y Kuo. 2008. Constructing Sobol sequences with better two-dimensional projections. SIAM Journal on Scientific Computing 30, 5 (2008), 2635–2654.Google ScholarDigital Library
    25. Leonid Vitalevich Kantorovich. 1948. Functional analysis and applied mathematics. Uspekhi Matematicheskikh Nauk 3, 6 (1948), 89–185.Google Scholar
    26. Leonid V. Kantorovich and Gennady S. Rubinstein. 1958. On a space of completely additive functions. Vestnik Leningrad. Univ 13, 7 (1958), 52–59.Google Scholar
    27. Alexander Keller. 2004. Stratification by rank-1 lattices. In Monte Carlo and Quasi-Monte Carlo Methods 2002, Harald Niederreiter (Ed.). Springer, 299–313.Google Scholar
    28. Alexander Keller. 2013. Quasi-Monte Carlo Image Synthesis in a Nutshell. In MCQMC, Josef Dick, Frances Y. Kuo, Gareth W. Peters, and Ian H. Sloan (Eds.). Springer, 213–249.Google Scholar
    29. Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, and Dani Lischinski. 2006. Recursive Wang Tiles for Real-Time Blue Noise. ACM Trans. Graph. 25, 3 (2006), 509–518.Google ScholarDigital Library
    30. Christopher Kulla, Alejandro Conty, Clifford Stein, and Larry Gritz. 2018. Sony Pictures Imageworks Arnold. ACM Trans. Graph. 37, 3 (2018).Google ScholarDigital Library
    31. Ares Lagae and Philip Dutré. 2006. An Alternative for Wang Tiles: Colored Edges versus Colored Corners. ACM Trans. Graph. 25, 4 (Oct. 2006), 1442–1459.Google ScholarDigital Library
    32. Pierre L’Ecuyer and David Munger. 2016. Lattice Builder: A General Software Tool for Constructing Rank-1 Lattice Rules. https://github.com/umontreal-simul/latnetbuilder.Google Scholar
    33. Christiane Lemieux. 2009. Monte Carlo and Quasi Monte Carlo Sampling. Springer-Verlag New York.Google Scholar
    34. Bruno Lévy. 2015. A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM: Mathematical Modelling and Numerical Analysis 49, 6 (2015), 1693–1715.Google ScholarCross Ref
    35. Quentin Mérigot. 2011. A multiscale approach to optimal transport. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1583–1592.Google Scholar
    36. Don P. Mitchell. 1987. Generating Antialiased Images at Low Sampling Densities. Computer Graphics 21, 4 (Aug. 1987), 65–72.Google ScholarDigital Library
    37. Don P Mitchell. 1991. Spectrally optimal sampling for distribution ray tracing. Computer Graphics 25, 4 (1991), 157–164.Google ScholarDigital Library
    38. Patrick Mullen, Pooran Memari, Fernando de Goes, and Mathieu Desbrun. 2011. HOT: Hodge-optimized Triangulations. ACM Trans. Graph. 30, 4 (2011), Art. 103.Google Scholar
    39. Georges Nader and Gael Guennebaud. 2018. Instant transport maps on 2D grids. ACM Trans. Graph. 37, 6 (2018), 13.Google Scholar
    40. Jan Novák, Iliyan Georgiev, Johannes Hanika, and Wojciech Jarosz. 2018. Monte Carlo Methods for Volumetric Light Transport Simulation. 37, 2 (2018).Google Scholar
    41. Victor Ostromoukhov, Charles Donohue, and Pierre-Marc Jodoin. 2004. Fast hierarchical importance sampling with blue noise properties. In ACM Trans. Graph., Vol. 23. ACM, 488–495.Google ScholarDigital Library
    42. Art B. Owen. 1998. Scrambling Sobol’s and Niederreiter-Xing Points. Journal of Complexity 14, 4 (1998), 466–489.Google ScholarDigital Library
    43. A. Cengiz Öztireli. 2016. Integration with Stochastic Point Processes. ACM Trans. Graph. 35, 5 (Aug. 2016), Art. 160.Google ScholarDigital Library
    44. Hélène Perrier, David Coeurjolly, Feng Xie, Matt Pharr, Pat Hanrahan, and Victor Ostromoukhov. 2018. Sequences with Low-Discrepancy Blue-Noise 2-D Projections. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 339–353.Google Scholar
    45. Matt Pharr, Wenzel Jakob, and Greg Humphreys. 2016. Physically Based Rendering: From Theory to Implementation (3 ed.). Morgan-Kaufmann.Google Scholar
    46. Adrien Pilleboue, Gurprit Singh, David Coeurjolly, Michael Kazhdan, and Victor Ostromoukhov. 2015. Variance Analysis for Monte Carlo Integration. ACM Trans. Graph. 34, 4 (July 2015), 124:1–124:14.Google ScholarDigital Library
    47. Francois Pitié, Anil C. Kokaram, and Rozenn Dahyot. 2005. N-Dimensional Probablility Density Function Transfer and Its Application to Colour Transfer. In IEEE Int. Conf. on Computer Vision (ICCV).Google Scholar
    48. Hongxing Qin, Yi Chen, Jinlong He, and Baoquan Chen. 2017. Wasserstein blue noise sampling. ACM Trans. Graph. 36, 4 (2017), Art. 137.Google ScholarDigital Library
    49. Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. 2011. Wasserstein barycenter and its application to texture mixing. In International Conference on Scale Space and Variational Methods in Computer Vision. Springer, 435–446.Google Scholar
    50. Johann Radon. 1986. On the determination of functions from their integral values along certain manifolds. IEEE Transactions on Medical Imaging 5, 4 (1986), 170–176.Google ScholarCross Ref
    51. Bernhard Reinert, Tobias Ritschel, Hans-Peter Seidel, and Iliyan Georgiev. 2016. Projective blue-noise sampling. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 285–295.Google Scholar
    52. Mark Rowland, Krzysztof M Choromanski, François Chalus, Aldo Pacchiano, Tamas Sarlos, Richard E Turner, and Adrian Weller. 2018. Geometrically Coupled Monte Carlo Sampling. In Advances in Neural Information Processing Systems. Vol. 31. 195–206.Google Scholar
    53. Peter Shirley and Kenneth Chiu. 1997. A low distortion map between disk and square. Journal of Graphics Tools 2, 3 (1997), 45–52.Google ScholarDigital Library
    54. Gurprit Singh and Wojciech Jarosz. 2017. Convergence Analysis for Anisotropic Monte Carlo Sampling Spectra. ACM Trans. Graph. 36, 4 (July 2017), 137:1–137:14.Google ScholarDigital Library
    55. Gurprit Singh, Kartic Subr, David Coeurjolly, Victor Ostromoukhov, and Wojciech Jarosz. 2019. Fourier Analysis of Correlated Monte Carlo Importance Sampling. Computer Graphics Forum 38, 1 (April 2019).Google ScholarCross Ref
    56. Justin Solomon, Fernando de Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains. ACM Trans. Graph. 34, 4 (2015), Art. 66.Google ScholarDigital Library
    57. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. 2014. Earth Mover’s Distances on Discrete Surfaces. ACM Trans. Graph. 33, 4 (2014), Art. 67.Google ScholarDigital Library
    58. Kartic Subr and Jan Kautz. 2013. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Trans. Graph. 32, 4, Article 128 (2013), 12 pages.Google ScholarDigital Library
    59. Peter Aundal Toft and John Aasted Sørensen. 1996. The Radon transform-theory and implementation. (1996).Google Scholar
    60. Salvatore Torquato, Obioma Uche, and Frank Stillinger. 2006. Random sequential addition of hard spheres in high Euclidean dimensions. Physical Review E 74, 6 (2006), 061308.Google ScholarCross Ref
    61. Robert Ulichney. 1987. Digital Halftoning. MIT Press, Cambridge, MA, USA.Google ScholarDigital Library
    62. Eric Veach. 1997. Robust Monte Carlo methods for light transport simulation. Stanford University PhD thesis.Google ScholarDigital Library
    63. Cédric Villani. 2009. Optimal Transport: Old and New. Fundamental Principles of Mathematical Sciences, Vol. 338. Springer-Verlag.Google ScholarCross Ref
    64. Li-Yi Wei. 2010. Multi-Class Blue Noise Sampling. ACM Trans. Graph. 29, 4 (July 2010), 79:1–79:8.Google ScholarDigital Library
    65. Yahan Zhou, Haibin Huang, Li-Yi Wei, and Rui Wang. 2012. Point sampling with general noise spectrum. ACM Trans. Graph. 31, 4 (2012), 76.Google ScholarDigital Library

ACM Digital Library Publication: