To solve the optimal transport problem between two uniform discrete measures of the same size, one seeks a bijective assignment that minimizes some matching cost. For this task, exact algorithms are intractable for large problems, while approximate ones may lose the bijectivity of the assignment. We address this issue and the more general cases of non-uniform discrete measures with different total masses, where partial transport may be desirable. The core of our algorithm is a variant of the Quicksort algorithm that provides an efficient strategy to randomly explore many relevant and easy-to-compute couplings, by matching BSP trees in loglinear time. The couplings we obtain are as sparse as possible, in the sense that they provide bijections, injective partial matchings or sparse couplings depending on the nature of the matched measures. To improve the transport cost, we propose efficient strategies to merge k sparse couplings into a higher quality one. For k = 64, we obtain transport plans with typically less than 1% of relative error in a matter of seconds between hundreds of thousands of points in 3D on the CPU. We demonstrate how these high-quality approximations can drastically speed-up usual pipelines involving optimal transport, such as shape interpolation, intrinsic manifold sampling, color transfer, topological data analysis, rigid partial registration of point clouds and image stippling.

We present a novel comprehensive construction algorithm of Apollonius diagrams designed for GPUs. Efficient and robust algorithms have been proposed for the computation of Voronoi diagrams or Power diagrams. In contrast, Apollonius cells are neither convex nor bounded by straight boundaries, making their computation complex, especially in more than two dimensions. Their parallel computation also represents a challenge because of the sequential nature of state-of-the-art algorithms. In this article, we tackle the computation of these diagrams from the geometry of their cells. Our strategy is based on a core cell topology update allowing the iterative insertion of new sites found through nearest neighbor queries. To benefit from the highly parallel environment of modern GPUs and fit their memory restriction, we define a lightweight data structure allowing the representation of the complex topology of Apollonius cells. Additionally, we provide several space exploration procedures for their efficient construction under both homogeneous and heterogeneous spatial distributions. Our method outperforms the fastest state-of-the-art CPU implementation while computing the complete geometry. As a possible use case, we show an application for molecular illustration.

Abstract Restricted Voronoi diagrams are a fundamental geometric structure used in many applications such as surface reconstruction from point sets or optimal transport. Given a set of sitesV= {vk}nk=1⊂ ℝdand a meshXwith vertices inℝdconnected by triangles, the restricted Voronoi diagram partitionsXby computing for each site the portion ofXfor which the site is the nearest. The restricted Voronoi diagram is the intersection between the regular Voronoi diagram and the mesh. Depending on the site distribution or the ambient space dimension computing the regular Voronoi diagram may not be feasible using classical algorithms. In this paper, we extend Lévy and Bonneel's approach [ LB12 ] based on nearest neighbor queries. We show that their method is limited when the sites are not located onX. We propose a new algorithm for computing restricted Voronoi which reduces the number of sites considered for each triangle of the mesh and scales smoothly when the sites are far from the surface.

Abstract We propose a method that computes a piecewise constant approximation of a function defined on a mesh. The approximation is associated with the cells of a restricted Voronoï diagram. Our method optimizes an objective function measuring the quality of the approximation. This objective function depends on the placement of the samples that define the restricted Voronoï diagram and their associated function values. We study the continuity of the objective function, derive the closed‐form expression of its derivatives and use them to design a numerical solution mechanism. The method can be applied to a function that has discontinuities, and the result aligns the boundaries of the Voronoï cells with the discontinuities. Some examples are shown, suggesting potential applications in image vectorization and compact representation of lighting.

Abstract Surface materials are commonly described by attributes stored in textures (for instance, color, normal, or displacement). Interpolation during texture lookup provides a continuous value field everywhere on the surface, except at the chart boundaries where visible discontinuities appear. We propose a solution to make these seams invisible, while still outputting a standard texture atlas. Our method relies on recent advances in quad remeshing using global parameterization to produce a set of texture coordinates aligning texel grids across chart boundaries. This property makes it possible to ensure that the interpolated value fields on both sides of a chart boundary precisely match, making all seams invisible. However, this requirement on the uv coordinates needs to be complemented by a set of constraints on the colors stored in the texels. We propose an algorithm solving for all the necessary constraints between texel values, including through different magnification modes (nearest, bilinear, biquadratic and bicubic), and across facets using different texture resolutions. In the typical case of bilinear magnification and uniform resolution, none of the texels appearing on the surface are constrained. Our approach also ensures perfect continuity across several MIP‐mapping levels.