Non-Euclidean Sliced Optimal Transport Sampling


In machine learning and computer graphics, a fundamental task is the approximation of a probability density function through a well-dispersed collection of samples. Providing a formal metric for measuring the distance between probability measures on general spaces, Optimal Transport (OT) emerges as a pivotal theoretical framework within this context. However, the associated computational burden is prohibitive in most real-world scenarios. Leveraging the simple structure of OT in 1D, Sliced Optimal Transport (SOT) has appeared as an efficient alternative to generate samples in Euclidean spaces. This paper pushes the boundaries of SOT utilization in computational geometry problems by extending its application to sample densities residing on more diverse mathematical domains, including the spherical space S^d, the hyperbolic plane H^d, and the real projective plane P^d. Moreover, it ensures the quality of these samples by achieving a blue noise characteristic, regardless of the dimensionality involved. The robustness of our approach is highlighted through its application to various geometry processing tasks, such as the intrinsic blue noise sampling of meshes, as well as the sampling of directions and rotations. These applications collectively underscore the efficacy of our methodology.

Computer Graphics Forum (Proceedings of Eurographics)

We propose a new technique to generate well-dispersed samples on non-Euclidean domains (spherical, hyperbolic and projective spaces) using an extension of the sliced optimal transport sampling. As an example, this allows us to sample probability measures on the high-dimensional sphere (left). Using the uniformization theorem to conformally embed discrete manifolds to spherical or hyperbolic spaces, we can also generate blue noise samples in a purely intrinsic manner (red samples on the flatten geometry that exhibits blue noise properties when mapped back to a better embedding in R^3 in blue). Finally, we also demonstrate that such an approach can be used to blue noise sample unit quaternions (hence rotations) on the projective space of dimension 3 (right).

 authors = {Baptiste Genest, Nicolas Courty and David Coeurjolly},
 journal = {Computer Graphics Forum (Proceedings of Eurographics)},
 month = {April},
 number = {2},
 title = {Non-Euclidean Sliced Optimal Transport Sampling},
 volume = {43},
 year = {2024}