3D Shape Reconstruction via Optimal Transport Project


Julie Digne  David Cohen-Steiner  Pierre Alliez  Fernando de Goes  Mathieu Desbrun
Overview of the method: 3d shape reconstruction by decimating an initial 3D delaunay.

This project, done during my postdoc, aims at reconstructing 3D shapes from a set of points using an optimal transportation inspired metric to guide the reconstruction. Assuming that the set of input points is a set of Dirac masses and the mesh it is transported to as a piecewise constant measure on each triangle, the problem can be formulated as a linear problem. Using a local relaxation (which converges to a local minium of the Optimal Transport Cost), the problem can be efficiently solved.
Apart from 3d reconstruction, the method can be used to recover sharp features and surface boundaries as a post-processing step after using a semi-smooth closed shape reconstruction method.

Notation of the transport plan: each input sample with given mass can be transported to several ttiangle bins

Each point pi with mass mi can be partially transported to several bin locations bj, this transportation is naturally computed so that it minimizes the transport cost (Wasserstein 2). Let s(j) be the index of the simplex containing bin bj, an cj the capacity of bin bj (proportional to the area of bin bj on simplex s(j)). Thus the program can be rewritten using variables mij (partial mass of pi transported to bin bj) with the constraints:

Paper: Feature-Preserving Surface Reconstruction and Simplification from Defect-Laden Point Sets

final PDF file (2013)

preprint - June 2012

Version fran├žaise - communication aux GTMG 2013

Abstract of the paper

We introduce a robust and feature-capturing surface reconstruction and simplification method that turns an input point set into a low triangle-count simplicial complex. Our approach starts with a (possibly non-manifold) simplicial complex filtered from a 3D Delaunay triangulation of the input points. This initial approximation is iteratively simplified based on an error metric that measures, through optimal transport, the distance between the input points and the current simplicial complex---both seen as mass distributions. Our approach is shown to exhibit both robustness to noise and outliers, as well as preservation of sharp features and boundaries. Our new feature-sensitive metric between point sets and triangle meshes can also be used as a post-processing tool that, from the smooth output of a reconstruction method, recovers sharp features and boundaries present in the initial point set.

Some results from the paper

Initial Points (left) and final reconstructed shape (right)

Initial Point set
Reconstruction via Poisson Reconstruction [Kazhdan et al. 2006]
Post-processing via our method, the sharp edges are well recovered


journal={Journal of Mathematical Imaging and Vision},
title={Feature-Preserving Surface Reconstruction and Simplification from Defect-Laden Point Sets},
publisher={Springer US},
keywords={Optimal transportation; Wasserstein distance; Linear programming; Surface reconstruction; Shape simplification; Feature recovery},
author={Digne, Julie and Cohen-Steiner, David and Alliez, Pierre and de Goes, Fernando and Desbrun, Mathieu},