{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T02:52:10Z","timestamp":1777603930443,"version":"3.51.4"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NIH","award":["U2C CA233303"],"award-info":[{"award-number":["U2C CA233303"]}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Implicit surface networks, such as arrangements of implicit surfaces and materials interfaces, are used for modeling piecewise smooth or partitioned shapes. However, accurate and numerically robust algorithms for discretizing either structure on a grid are still lacking. We present a unified approach for computing both types of surface networks for piecewise linear functions defined on a tetrahedral grid. Both algorithms are guaranteed to produce a correct combinatorial structure for any number of functions. Our main contribution is an exact and efficient method for partitioning a tetrahedron using the level sets of linear functions defined by barycentric interpolation. To further improve performance, we designed look-up tables to speed up processing of tetrahedra involving few functions and introduced an efficient algorithm for identifying nested 3D regions.<\/jats:p>","DOI":"10.1145\/3528223.3530176","type":"journal-article","created":{"date-parts":[[2022,7,22]],"date-time":"2022-07-22T21:06:27Z","timestamp":1658523987000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Robust computation of implicit surface networks for piecewise linear functions"],"prefix":"10.1145","volume":"41","author":[{"given":"Xingyi","family":"Du","sequence":"first","affiliation":[{"name":"Washington University in St. Louis"}]},{"given":"Qingnan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Nathan","family":"Carr","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Tao","family":"Ju","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis"}]}],"member":"320","published-online":{"date-parts":[[2022,7,22]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Handbook of computational geometry","author":"Agarwal Pankaj K","unstructured":"Pankaj K Agarwal and Micha Sharir. 2000. Arrangements and their applications. In Handbook of computational geometry. Elsevier, 49--119."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2008.06.009"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_2_4_1","volume-title":"A Marching-tetrahedra Algorithm for Feature-preserving Meshing of Piecewise-smooth Implicit Surfaces. Procedia Engineering 163 (12","author":"Bagley Brigham","year":"2016","unstructured":"Brigham Bagley, Shankar Sastry, and Ross Whitaker. 2016. A Marching-tetrahedra Algorithm for Feature-preserving Meshing of Piecewise-smooth Implicit Surfaces. Procedia Engineering 163 (12 2016), 162--174."},{"key":"e_1_2_2_5_1","first-page":"1","article-title":"Polygon Nesting and","volume":"35","author":"Bajaj C. L.","year":"1990","unstructured":"C. L. Bajaj and T. Dey. 1990. Polygon Nesting and Robustness. Inf. Process. Lett. 35, 1 (jun 1990), 23--32.","journal-title":"Robustness. Inf. Process. Lett."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331684.2331698"},{"key":"e_1_2_2_7_1","volume-title":"Computer Graphics Forum","author":"Bernstein Gilbert","unstructured":"Gilbert Bernstein and Don Fussell. 2009. Fast, exact, linear booleans. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1269--1278."},{"key":"e_1_2_2_8_1","volume-title":"Sascha K\u00f6hn, and Hans Hagen.","author":"Bertram Martin","year":"2005","unstructured":"Martin Bertram, Gerd Reis, Rolf Hendrik van Lengen, Sascha K\u00f6hn, and Hans Hagen. 2005. Non-manifold mesh extraction from time-varying segmented volumes used for modeling a human heart.. In EuroVis. Citeseer, 199--206."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/218380.218462"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1735603.1735630"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1260744"},{"key":"e_1_2_2_12_1","volume-title":"Adaptive and unstructured mesh cleaving. Procedia engineering 82","author":"Bronson Jonathan R","year":"2014","unstructured":"Jonathan R Bronson, Shankar P Sastry, Joshua A Levine, and Ross T Whitaker. 2014. Adaptive and unstructured mesh cleaving. Procedia engineering 82 (2014), 266--278."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073222"},{"key":"e_1_2_2_14_1","volume-title":"Computer Graphics Forum","author":"Campen Marcel","unstructured":"Marcel Campen and Leif Kobbelt. 2010. Exact and robust (self-) intersections for polygonal meshes. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 397--406."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/147508.147511"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2732197"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3226247.3226436"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480564"},{"key":"e_1_2_2_20_1","volume-title":"Construction of Simplified Boundary Surfaces from Serial-sectioned Metal Micrographs. Visualization and Computer Graphics","author":"Dillard Scott","year":"2007","unstructured":"Scott Dillard, John Bingert, Dan Thoma, and Bernd Hamann. 2007. Construction of Simplified Boundary Surfaces from Serial-sectioned Metal Micrographs. Visualization and Computer Graphics, IEEE Transactions on 13 (12 2007), 1528--1535."},{"key":"e_1_2_2_21_1","first-page":"214","article-title":"An Efficient Method of Triangulating Equi-Valued Surfaces by Using Tetrahedral Cells","volume":"74","author":"Doi Akio","year":"1991","unstructured":"Akio Doi and Akio Koide. 1991. An Efficient Method of Triangulating Equi-Valued Surfaces by Using Tetrahedral Cells. IEICE Transactions on Information and Systems 74 (1991), 214--224.","journal-title":"IEICE Transactions on Information and Systems"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275006"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459870"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_56"},{"key":"e_1_2_2_25_1","volume-title":"Minneapolis","author":"Edelsbrunner Herbert","year":"2002","unstructured":"Herbert Edelsbrunner and John Harer. 2002. Jacobi sets of multiple Morse functions. Foundations of Computational Mathematics, Minneapolis (2002), 37--57."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014496"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653865"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Powei Feng Tao Ju and Joe Warren. 2010. Piecewise Tri-linear Contouring for MultiMaterial Volumes. Lecture notes in computer science 6130 43--56.","DOI":"10.1007\/978-3-642-13411-1_4"},{"key":"e_1_2_2_29_1","volume-title":"Abseil: C++ Libraries from Google. https:\/\/abseil.io\/.","year":"2017","unstructured":"Google. 2017. Abseil: C++ Libraries from Google. https:\/\/abseil.io\/."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.enggeo.2021.106047"},{"key":"e_1_2_2_31_1","unstructured":"Hans-Christian Hege Martin Seebass Detlev Stalling and Malte Z\u00f6ckler. 1997. A generalized marching cubes algorithm based on non-binary classifications. (1997)."},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo et al. 2018. libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566586"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1882261.1866197"},{"key":"e_1_2_2_36_1","volume-title":"Proc. Implicit Surfaces. 145--151","author":"Kim Dae Hyun","year":"2000","unstructured":"Dae Hyun Kim, Ulf Doering, and Beat Bruderlin. 2000. Polygonization of non-manifolds with the aid of interval operators. In Proc. Implicit Surfaces. 145--151."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.10.004"},{"key":"e_1_2_2_38_1","unstructured":"Bruno L\u00e9vy and Alain Filbois. 2015. Geogram: a library for geometric algorithms. (2015)."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44199-2_43"},{"key":"e_1_2_2_40_1","volume-title":"The Annual SIGRAD Conference. Special Theme-Real-Time Simulations. Conference Proceedings from SIGRAD2003","author":"Ljung Patric","year":"2003","unstructured":"Patric Ljung and Anders Ynnerman. 2003. Extraction of intersection curves from iso-surfaces on co-located 3d grids. In The Annual SIGRAD Conference. Special Theme-Real-Time Simulations. Conference Proceedings from SIGRAD2003. Citeseer, 23--28."},{"key":"e_1_2_2_41_1","volume-title":"Cline","author":"Lorensen William E.","year":"1987","unstructured":"William E. Lorensen and Harvey E. Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm.. In SIGGRAPH, Maureen C. Stone (Ed.). ACM, 163--169."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141960"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2008.154"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1055715.1646512"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2021.103015"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Gregory Nielson and R. Franke. 1997. Computing the separating surface for segmented data. 229--233.","DOI":"10.1109\/VISUAL.1997.663887"},{"key":"e_1_2_2_47_1","volume-title":"conference 20","author":"Pons J","year":"2007","unstructured":"J Pons, E S\u00e9gonne, Jean-Daniel Boissonnat, Laurent Rineau, Mariette Yvinec, and Renaud Keriven. 2007. High-Quality Consistent Meshing of Multi-Label Datasets. Information processing in medical imaging : proceedings of the ... conference 20, 198--210."},{"key":"e_1_2_2_48_1","unstructured":"Bernhard Reitinger Alexander Bornik and Reinhard Beichel. 2005. Constructing smooth non-manifold meshes of multi-labeled volumetric datasets. (2005)."},{"key":"e_1_2_2_49_1","unstructured":"Aristides AG Requicha and Herbert B Voelcker. 1977. Constructive solid geometry. (1977)."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-013-0335-9"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2012.04.004"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.007"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2009.08.003"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1364901.1364931"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_2_2_56_1","first-page":"380","article-title":"A solid modelling system free from topological inconsistency","volume":"12","author":"Sugihara Kokichi","year":"1989","unstructured":"Kokichi Sugihara, Masao Iri, et al. 1989. A solid modelling system free from topological inconsistency. Journal of Information Processing 12, 4 (1989), 380--393.","journal-title":"Journal of Information Processing"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1006\/gmip.1996.0042"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7322(01)00330-0"},{"key":"e_1_2_2_59_1","volume-title":"Computer Graphics Forum","author":"Wang Peihui","unstructured":"Peihui Wang, Na Yuan, Yuewen Ma, Shiqing Xin, Ying He, Shuangmin Chen, Jian Xu, and Wenping Wang. 2020. Robust Computation of 3D Apollonius Diagrams. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 43--55."},{"key":"e_1_2_2_60_1","unstructured":"Hans-Martin Will. 1999. Computation of additively weighted Voronoi cells for applications in molecular biology. Ph. D. Dissertation. ETH Zurich."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.775"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/GMAP.2002.1027505"},{"key":"e_1_2_2_63_1","volume-title":"Proceedings of the 16th International Meshing Roundtable, 367--386","author":"Zhang Yongjie","year":"2007","unstructured":"Yongjie Zhang, Thomas Hughes, and Chandrajit Bajaj. 2007. Automatic 3D Mesh Generation for a Domain with Multiple Materials. Proceedings of the 16th International Meshing Roundtable, 367--386."},{"key":"e_1_2_2_64_1","volume-title":"Thomas JR Hughes, and Chandrajit L Bajaj","author":"Zhang Yongjie","year":"2008","unstructured":"Yongjie Zhang, Thomas JR Hughes, and Chandrajit L Bajaj. 2008. Automatic 3d mesh generation for a domain with multiple materials. In Proceedings of the 16th international meshing roundtable. Springer, 367--386."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2012.07.022"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2009.08.001"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925901"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528223.3530176","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3528223.3530176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:49Z","timestamp":1750186969000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528223.3530176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":66,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.1145\/3528223.3530176"],"URL":"https:\/\/doi.org\/10.1145\/3528223.3530176","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"2022-07-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}