Optimal Transport Approximation of 2-Dimensional Measures
Provides a unified algorithmic framework for optimal transport-based projection onto structured measures, with convergence guarantees and acceleration strategies, benefiting computational geometry and graphics.
Proposes a fast, scalable algorithm for projecting 2D densities onto structured measures (e.g., discrete points or curves), generalizing blue-noise sampling techniques. Demonstrates applications in sampling, rendering, and path planning.
We propose a fast and scalable algorithm to project a given density on a set of structured measures defined over a compact 2D domain. The measures can be discrete or supported on curves for instance. The proposed principle and algorithm are a natural generalization of previous results revolving around the generation of blue-noise point distributions, such as Lloyd's algorithm or more advanced techniques based on power diagrams. We analyze the convergence properties and propose new approaches to accelerate the generation of point distributions. We also design new algorithms to project curves onto spaces of curves with bounded length and curvature or speed and acceleration. We illustrate the algorithm's interest through applications in advanced sampling theory, non-photorealistic rendering and path planning.