“Robust optimization for topological surface reconstruction” by Lazar, Dym, Kushinsky, Huang, Ju, et al. …
Conference:
Type:
Entry Number: 46
Title:
- Robust optimization for topological surface reconstruction
Session/Category Title: An Immersion in Computational Geometry
Presenter(s)/Author(s):
Moderator(s):
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.
References:
1. Omid Amini, Jean-Daniel Boissonnat, and Pooran Memari. 2013. Geometric tomography with topological guarantees. Discrete & Computational Geometry 50, 4 (2013), 821–856. Google ScholarDigital Library
2. Marco Attene, Marcel Campen, and Leif Kobbelt. 2013. Polygon mesh repairing: An application perspective. ACM Computing Surveys (CSUR) 45, 2 (2013), 15. Google ScholarDigital Library
3. Gill Barequet and Amir Vaxman. 2009. Reconstruction of Multi-Label Domains from Partial Planar Cross-Sections. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1327–1337. Google ScholarDigital Library
4. Pierre-Louis Bazin and Dzung L Pham. 2007. Topology-preserving tissue classification of magnetic resonance brain images. IEEE transactions on medical imaging 26, 4 (2007), 487–496.Google ScholarCross Ref
5. Amit Bermano, Amir Vaxman, and Craig Gotsman. 2011. Online reconstruction of 3D objects from arbitrary cross-sections. ACM Transactions on Graphics (TOG) 30, 5 (2011), 113. Google ScholarDigital Library
6. Jean-Daniel Boissonnat and Pooran Memari. 2007. Shape reconstruction from unorganized cross-sections. In Symposium on Geometry Processing. 89–98. Google ScholarDigital Library
7. Evgeni Chernyaev. 1995. Marching cubes 33: Construction of topologically correct isosurfaces. Technical Report.Google Scholar
8. Fan RK Chung. 1997. Spectral graph theory. Number 92. American Mathematical Soc.Google Scholar
9. Paolo Cignoni, Fabio Ganovelli, Claudio Montani, and Roberto Scopigno. 2000. Reconstruction of topologically correct and adaptive trilinear isosurfaces. Computers & Graphics 24, 3 (2000), 399–418.Google ScholarCross Ref
10. Lis Custodio, Tiago Etiene, Sinesio Pesco, and Claudio Silva. 2013. Practical considerations on Marching Cubes 33 topological correctness. Computers & Graphics 37, 7 (2013), 840–850. Google ScholarDigital Library
11. Arindam Kumar Das and Mehran Mesbahi. 2005. K-node connected power efficient topologies in wireless networks: a semidefinite programming approach. In Global Telecommunications Conference, 2005. GLOBECOM’05. IEEE, Vol. 1. IEEE, 6–pp.Google ScholarCross Ref
12. Bruno Rodrigues De Araújo, Daniel S Lopes, Pauline Jepp, Joaquim A Jorge, and Brian Wyvill. 2015. A survey on implicit surface polygonization. ACM Computing Surveys (CSUR) 47, 4 (2015), 60. Google ScholarDigital Library
13. Miroslav Fiedler. 1973. Algebraic connectivity of graphs. Czechoslovak mathematical journal 23, 2 (1973), 298–305.Google Scholar
14. Arpita Ghosh and Stephen Boyd. 2006. Growing well-connected graphs. In Decision and Control, 2006 45th IEEE Conference on. IEEE, 6605–6611.Google ScholarCross Ref
15. Zhiyang Huang, Ming Zou, Nathan Carr, and Tao Ju. 2017. Topology-controlled Reconstruction of Multi-labelled Domains from Cross-sections. ACM Transactions on Graphics (TOG) 36, 4 (2017), 76. Google ScholarDigital Library
16. Tao Ju, Qian-Yi Zhou, and Shi-Min Hu. 2007. Editing the Topology of 3D Models by Sketching. ACM Trans. Graph. 26, 3, Article 42 (July 2007). Google ScholarDigital Library
17. Lu Liu, C. Bajaj, Joseph Deasy, Daniel A. Low, and Tao Ju. 2008. Surface Reconstruction From Non-parallel Curve Networks. Comput. Graph. Forum 27, 2 (2008), 155–163. http://dblp.uni-trier.de/db/journals/cgf/cgf27.html#LiuBDLJ08Google ScholarCross Ref
18. William E Lorensen and Harvey E Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In ACM siggraph computer graphics, Vol. 21. ACM, 163–169. Google ScholarDigital Library
19. Jing Qian, Venkatesh Saligrama, and Yuting Chen. 2014. Connected sub-graph detection. In Artificial Intelligence and Statistics. 796–804.Google Scholar
20. Andrei Sharf, Thomas Lewiner, Ariel Shamir, Leif Kobbelt, and Daniel Cohen-Or. 2006. Competing fronts for coarse-to-fine surface reconstruction. In Eurographics. Vienna, 389–398. http://www.mat.puc-rio.br/~tomlew/competing_fronts_eg.pdfGoogle Scholar
21. Andrei Sharf, Thomas Lewiner, Gil Shklarski, Sivan Toledo, and Daniel Cohen-Or. 2007. Interactive topology-aware surface reconstruction. ACM Transactions on Graphics (TOG) 26, 3 (2007), 43. Google ScholarDigital Library
22. Mechthild Stoer and Frank Wagner. 1997. A simple min-cut algorithm. Journal of the ACM (JACM) 44, 4 (1997), 585–591. Google ScholarDigital Library
23. Francisco Velasco, Juan Carlos Torres, Alejandro León, and Francisco Soler. 2008. Adaptive cube tessellation for topologically correct isosurfaces. JVRB-Journal of Virtual Reality and Broadcasting 5, 3 (2008).Google Scholar
24. Zoë Wood, Hugues Hoppe, Mathieu Desbrun, and Peter Schröder. 2004. Removing excess topology from isosurfaces. ACM Transactions on Graphics (TOG) 23, 2 (2004), 190–208. Google ScholarDigital Library
25. Kangxue Yin, Hui Huang, Hao Zhang, Minglun Gong, Daniel Cohen-Or, and Baoquan Chen. 2014. Morfit: interactive surface reconstruction from incomplete point clouds with curve-driven topology and geometry control. ACM Trans. Graph. 33, 6 (2014), 202–1. Google ScholarDigital Library
26. Yun Zeng, Dimitris Samaras, Wei Chen, and Qunsheng Peng. 2008. Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in N-D images. Computer vision and image understanding 112, 1 (2008), 81–90. Google ScholarDigital Library
27. Shizhe Zhou, Changyun Jiang, and Sylvain Lefebvre. 2014. Topology-constrained synthesis of vector patterns. ACM Trans. Graph. 33, 6 (2014), 215–1. Google ScholarDigital Library
28. Ming Zou, Michelle Holloway, Nathan Carr, and Tao Ju. 2015. Topology-constrained surface reconstruction from cross-sections. ACM Transactions on Graphics (TOG) 34, 4 (2015), 128. Google ScholarDigital Library
29. Ming Zou, Tao Ju, and Nathan Carr. 2013. An algorithm for triangulating multiple 3D polygons. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 157–166. Google ScholarDigital Library
