Robust optimization for topological surface reconstruction
Authors:
Open Access
- 30 July 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 37 (4) , 1-10
Abstract
Surface reconstruction is one of the central problems in computer graphics. Existing research on this problem has primarily focused on improving the geometric aspects of the reconstruction (e.g., smoothness, features, element quality, etc.), and little attention has been paid to ensure it also has desired topological properties (e.g., connectedness and genus). In this paper, we propose a novel and general optimization method for surface reconstruction under topological constraints. The input to our method is a prescribed genus for the reconstructed surface, a partition of the ambient volume into cells, and a set of possible surface candidates and their associated energy within each cell. Our method computes one candidate per cell so that their union is a connected surface with the prescribed genus that minimizes the total energy. We formulate the task as an integer program, and propose a novel solution that combines convex relaxations within a branch and bound framework. As our method is oblivious of the type of input cells, surface candidates, and energy, it can be applied to a variety of reconstruction scenarios, and we explore two of them in the paper: reconstruction from cross-section slices and iso-surfacing an intensity volume. In the first scenario, our method outperforms an existing topology-aware method particularly for complex inputs and higher genus constraints. In the second scenario, we demonstrate the benefit of topology control over classical topology-oblivious methods such as Marching Cubes.Keywords
This publication has 21 references indexed in Scilit:
- An algorithm for triangulating multiple 3D polygonsComputer Graphics Forum, 2013
- Polygon mesh repairingACM Computing Surveys, 2013
- Online reconstruction of 3D objects from arbitrary cross-sectionsACM Transactions on Graphics, 2011
- Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in N–D imagesComputer Vision and Image Understanding, 2008
- Surface Reconstruction From Non‐parallel Curve NetworksComputer Graphics Forum, 2008
- Interactive topology-aware surface reconstructionACM Transactions on Graphics, 2007
- Editing the topology of 3D models by sketchingACM Transactions on Graphics, 2007
- Removing excess topology from isosurfacesACM Transactions on Graphics, 2004
- A simple min-cut algorithmJournal of the ACM, 1997
- Marching cubes: A high resolution 3D surface construction algorithmACM SIGGRAPH Computer Graphics, 1987