{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T00:13:10Z","timestamp":1676938390819},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2018,8,31]]},"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.<\/jats:p>","DOI":"10.1145\/3197517.3201348","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T15:56:23Z","timestamp":1533052583000},"page":"1-10","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Robust optimization for topological surface reconstruction"],"prefix":"10.1145","volume":"37","author":[{"given":"Roee","family":"Lazar","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science"}]},{"given":"Nadav","family":"Dym","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}]},{"given":"Yam","family":"Kushinsky","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}]},{"given":"Zhiyang","family":"Huang","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis"}]},{"given":"Tao","family":"Ju","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis"}]},{"given":"Yaron","family":"Lipman","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9531-z"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431214"},{"key":"e_1_2_2_3_1","volume-title":"Computer Graphics Forum","author":"Barequet Gill","unstructured":"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. 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."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2007.893283"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019627.2019632"},{"key":"e_1_2_2_6_1","volume-title":"Symposium on Geometry Processing. 89--98","author":"Boissonnat Jean-Daniel","year":"2007","unstructured":"Jean-Daniel Boissonnat and Pooran Memari . 2007 . Shape reconstruction from unorganized cross-sections . In Symposium on Geometry Processing. 89--98 . Jean-Daniel Boissonnat and Pooran Memari. 2007. Shape reconstruction from unorganized cross-sections. In Symposium on Geometry Processing. 89--98."},{"key":"e_1_2_2_8_1","unstructured":"Fan RK Chung. 1997. Spectral graph theory. Number 92. American Mathematical Soc. Fan RK Chung. 1997. Spectral graph theory. Number 92. American Mathematical Soc."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(00)00036-4"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2013.04.004"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2005.1577670"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2732197"},{"key":"e_1_2_2_13_1","volume-title":"Algebraic connectivity of graphs. Czechoslovak mathematical journal 23, 2","author":"Fiedler Miroslav","year":"1973","unstructured":"Miroslav Fiedler . 1973. Algebraic connectivity of graphs. Czechoslovak mathematical journal 23, 2 ( 1973 ), 298--305. Miroslav Fiedler. 1973. Algebraic connectivity of graphs. Czechoslovak mathematical journal 23, 2 (1973), 298--305."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2006.377282"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073644"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276430"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01112.x"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37422"},{"key":"e_1_2_2_19_1","unstructured":"Jing Qian Venkatesh Saligrama and Yuting Chen. 2014. Connected sub-graph detection. In Artificial Intelligence and Statistics. 796--804. Jing Qian Venkatesh Saligrama and Yuting Chen. 2014. Connected sub-graph detection. In Artificial Intelligence and Statistics. 796--804."},{"key":"e_1_2_2_20_1","volume-title":"Eurographics.","author":"Sharf Andrei","unstructured":"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.pdf 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.pdf"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276431"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_2_2_23_1","article-title":"Adaptive cube tessellation for topologically correct isosurfaces","volume":"5","author":"Velasco Francisco","year":"2008","unstructured":"Francisco Velasco , Juan Carlos Torres , Alejandro Le\u00f3n , and Francisco Soler . 2008 . Adaptive cube tessellation for topologically correct isosurfaces . JVRB-Journal of Virtual Reality and Broadcasting 5 , 3 (2008). Francisco Velasco, Juan Carlos Torres, Alejandro Le\u00f3n, and Francisco Soler. 2008. Adaptive cube tessellation for topologically correct isosurfaces. JVRB-Journal of Virtual Reality and Broadcasting 5, 3 (2008).","journal-title":"JVRB-Journal of Virtual Reality and Broadcasting"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/990002.990007"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661241"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2008.07.008"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661238"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766976"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12182"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3197517.3201348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T20:15:54Z","timestamp":1672517754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197517.3201348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3197517.3201348"],"URL":"http:\/\/dx.doi.org\/10.1145\/3197517.3201348","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":["Computer Graphics and Computer-Aided Design"],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}