Robust Inside-Outside Segmentation using Generalized Winding Numbers


Alec Jacobson
ETH Zurich
 
Ladislav Kavan
University of Pennsylvania
ETH Zurich
 
Olga Sorkine-Hornung
ETH Zurich
 


The Big SigCat input mesh has 3442 pairs of intersecting triangles (bright red), 1020 edges on open boundaries (dark red), 344 non-manifold edges (purple) and 67 connected components (randomly colored). On top of those problems, a SIGGRAPH logo shaped hole is carved from her side.



Abstract

Solid shapes in computer graphics are often represented with boundary descriptions, e.g. triangle meshes, but animation, physically-based simulation, and geometry processing are more realistic and accurate when explicit volume representations are available. Tetrahedral meshes which exactly contain (interpolate) the input boundary description are desirable but difficult to construct for a large class of input meshes. Character meshes and CAD models are often composed of many connected components with numerous self-intersections, non-manifold pieces, and open boundaries, precluding existing meshing algorithms. We propose an automatic algorithm handling all of these issues, resulting in a compact discretization of the input's inner volume. We only require reasonably consistent orientation of the input triangle mesh. By generalizing the winding number for arbitrary triangle meshes, we define a function that is a perfect segmentation for watertight input and is well-behaved otherwise. This function guides a graphcut segmentation of a constrained Delaunay tessellation (CDT), providing a minimal description that meets the boundary exactly and may be fed as input to existing tools to achieve element quality. We highlight our robustness on a number of examples and show applications of solving PDEs, volumetric texturing and elastic simulation.



accompanying video





fast forward





Publication

Alec Jacobson, Ladislav Kavan, Olga Sorkine-Hornung. Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Transaction on Graphics 32(4) [Proceedings of SIGGRAPH], 2013.  


Links and Downloads

Paper

 
BibTeX

 
Supplemental Material

 
Data



Acknowledgements

We are indebted to Ilya Baran, Leo Guibas, Pierre Alliez, Alexander Sorkine-Hornung and Daniele Panozzo for illuminating conversations. We are grateful to Leonardo Koller Sacht, Fabian Hahn and Kaan Yücer for helping create results. Thanks to Josef Pelikan for recognizing the practical significance of winding numbers and including them in introductory computer graphics classes. Thanks to the Pascal Frey and the University of Paris VI for releasing the Medit software (used to visualize our 3D results) to the public domain. Also, thanks to Marco Attene for making his MeshFix program open source. This work was supported in part by the ERC grant iModel (StG-2012-306877), by an SNF award 200021_137879 and the Intel Doctoral Fellowship.