Mapping + Transport

OptCuts: Joint Optimization of Surface Cuts and Parameterization

Abstract: Low-distortion mapping of three-dimensional surfaces to the plane is a critical problem in geometry processing. The intrinsic distortion introduced by such UV mappings is highly dependent on the choice of surface cuts that form seamlines which break mapping continuity. Parameterization applications typically require UV maps with an application-specific upper bound on distortion to avoid mapping artifacts; at the same time they seek to reduce cut lengths to minimize discontinuity artifacts. We propose OptCuts, an algorithm for jointly optimizing the parameterization and cutting of a three-dimensional mesh. OptCuts starts from an arbitrary initial embedding and a user-requested distortion bound. It requires no parameter setting and automatically seeks to minimize seam lengths subject to satisfying the distortion bound of the mapping computed using these seams. OptCuts alternates between topology and geometry update steps that consistently decrease distortion and seam length, producing a UV map with compact boundaries that strictly satisfies the distortion bound. OptCuts automatically produces high-quality, globally bijective UV maps without user intervention. While OptCuts can thus be a highly effective tool to create new mappings from scratch, we also show how it can be employed to improve pre-existing embeddings. Additionally, when semantic or other priors on seam placement are desired, OptCuts can be extended to respect these user preferences as constraints during optimization of the parameterization.We demonstrate the scalable performance of OptCuts on a wide range of challenging benchmark parameterization examples, as well as in comparisons with state-of-the-art UV methods and commercial tools.

Authors/Presenter(s): Minchen Li, University of British Columbia, Adobe Research, United States of America
Danny M. Kaufman, Adobe Research, United States of America
Vladimir G. Kim, Adobe Research, United States of America
Justin Solomon, Massachusetts Institute of Technology, United States of America
Alla Sheffer, University of British Columbia, Canada

Continuous and Orientation-preserving Correspondences via Functional Maps

Abstract: We propose a method for efficiently computing orientation-preserving and approximately continuous correspondences between non-rigid shapes, using the functional maps framework. We first show how orientation preservation can be formulated directly in the functional (spectral) domain without using landmark or region correspondences and without relying on external symmetry information. This allows us to obtain functional maps that promote orientation preservation, even when using descriptors, that are invariant to orientation changes. We then show how higher quality, approximately continuous and bijective pointwise correspondences can be obtained from initial functional maps by introducing a novel refinement technique that aims to simultaneously improve the maps both in the spectral and spatial domains. This leads to a general pipeline for computing correspondences between shapes that results in high-quality maps, while admitting an efficient optimization scheme. We show through extensive evaluation that our approach improves upon state-of-the-art results on challenging isometric and non-isometric correspondence benchmarks according to both measures of continuity and coverage as well as producing semantically meaningful correspondences as measured by the distance to ground truth maps.

Authors/Presenter(s): Jing Ren, KAUST, Saudi Arabia
Adrien Poulenard, Ecole Polytechnique, France
Peter Wonka, KAUST, Saudi Arabia
Maks Ovsjanikov, Ecole Polytechnique, France

Instant Transport Maps on 2D Grids

Abstract: In this paper, we introduce a novel and extremely fast algorithm to compute continuous transport maps between 2D probability densities discretized on uniform grids. The core of our method is a novel iterative solver computing the $L^2$ optimal transport map from a grid to the uniform density in the 2D Euclidean plane. A transport map between arbitrary densities is then recovered through numerical inversion and composition. In this case, the resulting map is only approximately optimal, but it is continuous and density preserving. Our solver is derivative-free, and it converges in a few cheap iterations. We demonstrate interactive performance in various applications such as adaptive sampling, feature sensitive remeshing and caustic design.

Authors/Presenter(s): Georges Nader, Inria Bordeaux Sud-Ouest, France
Gael Guennebaud, Inria Bordeaux Sud-Ouest, France

Dynamical Optimal Transport on Discrete Surfaces

Abstract: We propose a technique for interpolating between probability distributions on discrete surfaces, based on the theory of optimal transport. Unlike previous attempts that use linear programming, our method is based on a dynamical formulation of quadratic optimal transport proposed for flat domains by Benamou and Brenier, adapted to discrete surfaces. Our structure-preserving construction yields a Riemannian metric on the (finite-dimensional) space of probability distributions on a discrete surface, which translates the so-called Otto calculus to discrete language. From a practical perspective, our technique provides a smooth interpolation between distributions on discrete surfaces with less diffusion than state-of-the-art algorithms involving entropic regularization. Beyond interpolation, we show how our discrete notion of optimal transport extends to other tasks, such as distribution-valued Dirichlet problems and time integration of gradient flows.

Authors/Presenter(s): Hugo Lavenant, Université Paris-Sud, France
Sebastian Claici, Massachusetts Institute of Technology, United States of America
Edward Chien, Massachusetts Institute of Technology, United States of America
Justin Solomon, Massachusetts Institute of Technology, United States of America

A Genetic Isometric Shape Correspondence Algorithm with Adaptive Sampling

Abstract: We exploit the permutation creation ability of genetic optimization to find the permutation of one point set that puts it into correspondence with another one. To this end, we provide a genetic algorithm for the 3D shape correspondence problem, which is the main contribution of this paper. As another significant contribution, we present an adaptive sampling approach that relocates the matched points based on the currently available correspondence via an alternating optimization. The point sets to be matched are sampled from two isometric (or nearly isometric) shapes. The sparse one-to-one correspondence, i.e., bijection, that we produce is validated both in terms of running time and accuracy in a comprehensive test suite that includes four standard shape benchmarks and state-of-the-art techniques.

Authors/Presenter(s): Yusuf Sahillioglu, Middle East Technical University, Turkey