A Heat Method for Generalized Signed Distance
Authors: 
Nicole Feng, 
Keenan CraneAuthors Info & Claims
Article No.: 92, Pages 1 - 19
Abstract
We introduce a method for approximating the signed distance function (SDF) of geometry corrupted by holes, noise, or self-intersections. The method implicitly defines a completed version of the shape, rather than explicitly repairing the given input. Our starting point is a modified version of the heat method for geodesic distance, which diffuses normal vectors rather than a scalar distribution. This formulation provides robustness akin to generalized winding numbers (GWN), but provides distance function rather than just an inside/outside classification. Our formulation also offers several features not common to classic distance algorithms, such as the ability to simultaneously fit multiple level sets, a notion of distance for geometry that does not topologically bound any region, and the ability to mix and match signed and unsigned distance. The method can be applied in any dimension and to any spatial discretization, including triangle meshes, tet meshes, point clouds, polygonal meshes, voxelized surfaces, and regular grids. We evaluate the method on several challenging examples, implementing normal offsets and other morphological operations directly on imperfect curve and surface data. In many cases we also obtain an inside/outside classification dramatically more robust than the one obtained provided by GWN.
Supplementary Material
supplemental
- Download
- 1.49 MB
References
[1]
Marc Alexa, Philipp Herholz, Max Kohlbrenner, and Olga Sorkine-Hornung. 2020. Properties of Laplace Operators for Tetrahedral Meshes. Computer Graphics Forum (2020).
[2]
P. Alliez, D. Cohen-Steiner, Y. Tong, and M. Desbrun. 2007. Voronoi-Based Variational Reconstruction of Unoriented Point Sets. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (Barcelona, Spain) (SGP '07). Eurographics Association, Goslar, DEU, 39--48.
[3]
Matan Atzmon and Yaron Lipman. 2019. SAL: Sign Agnostic Learning of Shapes from Raw Data. CoRR abs/1911.10414 (2019). arXiv:1911.10414 http://arxiv.org/abs/1911.10414
[4]
J.A. Bærentzen and H. Aanæs. 2005. Signed distance computation using the angle weighted pseudonormal. IEEE Transactions on Visualization and Computer Graphics 11, 3 (2005), 243--253.
[5]
J Andreas Bærentzen. 2005. Robust generation of signed distance fields from triangle meshes. In Fourth International Workshop on Volume Graphics, 2005. IEEE, 167--239.
[6]
Josh Barnes and Piet Hut. 1986. A hierarchical O (N log N) force-calculation algorithm. nature 324, 6096 (1986), 446--449.
[7]
Alexander Belyaev and Pierre-Alain Fayolle. 2020. An ADMM-based scheme for distance function approximation. Numerical Algorithms 84 (2020), 14 pages.
[8]
Alexander Belyaev, Pierre-Alain Fayolle, and Alexander Pasko. 2013. Signed Lp-distance fields. Computer-Aided Design 45, 2 (2013), 523--528.
[9]
Nicole Berline, Ezra Getzler, and Michèle Vergne. 1992. Heat Kernels and Dirac Operators (1 ed.). Springer Berlin, Heidelberg.
[10]
David Bommes and Leif Kobbelt. 2007. Accurate Computation of Geodesic Distance Fields for Polygonal Curves on Triangle Meshes. VMV, 151--160.
[11]
Alan Brunton and Lubna Abu Rmaileh. 2021. Displaced Signed Distance Fields for Additive Manufacturing. ACM Trans. Graph. 40, 4, Article 179 (July 2021), 13 pages.
[12]
Astrid Bunge, Philipp Herholz, Misha Kazhdan, and Mario Botsch. 2020. Polygon Laplacian Made Simple. Computer Graphics Forum 39, 2 (2020), 303--313. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.13931
[13]
Fatih Calakli and Gabriel Taubin. 2011. SSD: Smooth signed distance surface reconstruction. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1993--2002.
[14]
Antonin Chambolle and Thomas Pock. 2011. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. Journal of Mathematical Imaging and Vision 40 (2011).
[15]
Sungjoon Choi, Qian-Yi Zhou, Stephen Miller, and Vladlen Koltun. 2016. A Large Dataset of Object Scans. arXiv:1602.02481 (2016).
[16]
David Coeurjolly and Jacques-Olivier Lachaud. 2022. A Simple Discrete Calculus for Digital Surfaces. In IAPR Second International Conference on Discrete Geometry and Mathematical Morphology, Étienne Baudrier, Benoît Naegel, Adrien Krähenbühl, and Mohamed Tajine (Eds.). Springer, LNCS.
[17]
David Coeurjolly, Jacques-Olivier Lachaud, et al. 2010. DGtal: Digital Geometry tools and algorithms library. http://dgtal.org.
[18]
David Coeurjolly, Jacques-Olivier Lachaud, and Jérémy Levallois. 2014. Multigrid convergent principal curvature estimators in digital geometry. Computer Vision and Image Understanding 129 (2014), 27--41.
[19]
David Coeurjolly and Jérémy Levallois. 2015. VolGallery. https://github.com/dcoeurjo/VolGallery.
[20]
Keenan Crane, Fernando De Goes, Mathieu Desbrun, and Peter Schröder. 2013a. Digital geometry processing with discrete exterior calculus. In ACM SIGGRAPH 2013 Courses. 1--126.
[21]
Keenan Crane, Marco Livesu, Enrico Puppo, and Yipeng Qin. 2020. A Survey of Algorithms for Geodesic Paths and Distances. arXiv e-prints, Article arXiv:2007.10430 (July 2020), arXiv:2007.10430 pages. arXiv:2007.10430 [cs.GR]
[22]
Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013b. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics (TOG) 32, 5 (2013), 1--11.
[23]
George Dantzig. 1963. Linear programming and extensions. Princeton university press.
[24]
Alexandre Djerbetian and Mirela Ben Chen. 2016. Tangent Vector Fields on Triangulated Surfaces-An Edge-Based Approach. Ph. D. Dissertation. Computer Science Department, Technion.
[25]
Michal Edelstein, Nestor Guillen, Justin Solomon, and Mirela Ben-Chen. 2023. A Convex Optimization Framework for Regularized Geodesic Distances. In ACM SIGGRAPH 2023 Conference Proceedings (Los Angeles, CA, USA) (SIGGRAPH '23). Association for Computing Machinery, New York, NY, USA, Article 2, 11 pages.
[26]
Jeff Erickson. 2019. Algorithms. Jeff Erickson. http://jeffe.cs.illinois.edu/teaching/algorithms/
[27]
Alexandre Ern and Jean-Luc Guermond. 2004. Theory and Practice of Finite Elements (1 ed.). Applied Mathematical Sciences, Vol. 159. Springer, New York, NY.
[28]
Nicole Feng, Mark Gillespie, and Keenan Crane. 2023. Winding Numbers on Discrete Surfaces. ACM Trans. Graph. 42, 4, Article 36 (jul 2023), 17 pages.
[29]
Jean Gallier, Jocelyn Quaintance, Jean Gallier, and Jocelyn Quaintance. 2020. Operators on Riemannian Manifolds: Hodge Laplacian, Laplace-Beltrami Laplacian, the Bochner Laplacian, and Weitzenböck Formulae. Differential Geometry and Lie Groups: A Second Course (2020), 361--401.
[30]
Michael Garland and Paul S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '97). ACM Press/Addison-Wesley Publishing Co., USA, 209--216.
[31]
Izrail Moiseevitch Gelfand, Richard A Silverman, et al. 2000. Calculus of variations. Courier Corporation.
[32]
Mark Gillespie, Nicholas Sharp, and Keenan Crane. 2021. Integer Coordinates for Intrinsic Geometry Processing. ACM Trans. Graph. 40, 6 (2021).
[33]
Amos Gropp, Lior Yariv, Niv Haim, Matan Atzmon, and Yaron Lipman. 2020. Implicit Geometric Regularization for Learning Shapes. CoRR abs/2002.10099 (2020). arXiv:2002.10099 https://arxiv.org/abs/2002.10099
[34]
Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.
[35]
Eric Haines. 1994. Point in Polygon Strategies. Graphics Gems 4, 1 (1994), 24--46.
[36]
Si Hang. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw 41, 2 (2015), 11.
[37]
John C Hart. 1996. Sphere tracing: A geometric method for the antialiased ray tracing of implicit surfaces. The Visual Computer 12, 10 (1996), 527--545.
[38]
Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral meshing in the wild. ACM Trans. Graph. 37, 4 (2018), 60--1.
[39]
Saar Huberman, Amit Bracha, and Ron Kimmel. 2023. Deep Accurate Solver for the Geodesic Problem. In International Conference on Scale Space and Variational Methods in Computer Vision. Springer, 288--300.
[40]
Alec Jacobson, Ladislav Kavan, and Olga Sorkine. 2013. Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Trans. Graph. 32, 4 (2013).
[41]
Alec Jacobson and Daniele Panozzo. 2017. Libigl: Prototyping geometry processing research in c++. In SIGGRAPH Asia 2017 courses. 1--172.
[42]
Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.
[43]
Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson Surface Reconstruction. In Proceedings of the Fourth Eurographics Symposium on Geometry Processing (Cagliari, Sardinia, Italy) (SGP '06). Eurographics Association, Goslar, DEU, 61--70.
[44]
Michael Kazhdan and Hugues Hoppe. 2013. Screened Poisson Surface Reconstruction. ACM Trans. Graph. 32, 3, Article 29 (jul 2013), 13 pages.
[45]
Ron Kimmel and James A Sethian. 1998. Computing geodesic paths on manifolds. Proceedings of the national academy of Sciences 95, 15 (1998), 8431--8435.
[46]
Bruno Lévy and Hao Zhang. 2010. Spectral mesh processing. In ACM SIGGRAPH 2010 Courses. 1--312.
[47]
Moshe Lichtenstein, Gautam Pai, and Ron Kimmel. 2019. Deep eikonal solvers. In Scale Space and Variational Methods in Computer Vision: 7th International Conference, SSVM 2019, Hofgeismar, Germany, June 30--July 4, 2019, Proceedings 7. Springer, 38--50.
[48]
Roee Litman and Alex M Bronstein. 2016. Spectrometer: Amortized sublinear spectral approximation of distance on graphs. In 2016 Fourth International Conference on 3D Vision (3DV). IEEE, 499--508.
[49]
Charles Loop. 1987. Smooth Subdivision Surfaces Based on Triangles. Ph. D. Dissertation.
[50]
William E Lorensen and Harvey E Cline. 1998. Marching cubes: A high resolution 3D surface construction algorithm. In Seminal graphics: pioneering efforts that shaped the field. 347--353.
[51]
Zoë Marschner, Silvia Sellán, Hsueh-Ti Derek Liu, and Alec Jacobson. 2023. Constructive Solid Geometry on Neural Signed Distance Fields. In SIGGRAPH Asia 2023 Conference Papers. 1--12.
[52]
Joseph S. B. Mitchell, D. Mount, and C. Papadimitriou. 1987. The Discrete Geodesic Problem. SIAM J. Comput. 16, 4 (1987), 647--668.
[53]
Patrick Mullen, Fernando De Goes, Mathieu Desbrun, David Cohen-Steiner, and Pierre Alliez. 2010. Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets. Computer Graphics Forum 29, 5 (2010), 1733--1741. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8659.2010.01782.x
[54]
Ken Museth, David E Breen, Ross T Whitaker, and Alan H Barr. 2002. Level set surface editing operators. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 330--338.
[55]
Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Trans. Graph. 33, 4, Article 135 (jul 2014), 14 pages.
[56]
Giacomo Nazzaro, Enrico Puppo, and Fabio Pellacini. 2022. geoTangle: Interactive Design of Geodesic Tangle Patterns on Surfaces. ACM Transactions on Graphics 41, 2 (2022), 12:1--12:17.
[57]
Helen Oleynikova, Alexander Millane, Zachary Taylor, Enric Galceran, Juan Nieto, and Roland Siegwart. 2016. Signed distance fields: A natural representation for both mapping and planning. In RSS 2016 workshop: geometry and beyond-representations, physics, and scene understanding for robotics. University of Michigan.
[58]
Stanley Osher, Ronald Fedkiw, and K Piechor. 2004. Level set methods and dynamic implicit surfaces. Appl. Mech. Rev. 57, 3 (2004), B15--B15.
[59]
Jeong Joon Park, Peter Florence, Julian Straub, Richard Newcombe, and Steven Lovegrove. 2019. DeepSDF: Learning Continuous Signed Distance Functions for Shape Representation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
[60]
Konrad Polthier and Eike Preuß. 2003. Identifying Vector Field Singularities Using a Discrete Hodge Decomposition. In Visualization and Mathematics III, Hans-Christian Hege and Konrad Polthier (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 113--134.
[61]
Inigo Quilez. 2008. Raymarching Signed Distance Fields. https://iquilezles.org/articles/raymarchingdf/.
[62]
Sudhanshu Rawat and Mantosh Biswas. 2022a. Enhanced Heat Method for Computation of Geodesic Distance on Triangular Meshes. In 2022 IEEE 9th Uttar Pradesh Section International Conference on Electrical, Electronics and Computer Engineering (UPCON). IEEE, 1--5.
[63]
Sudhanshu Rawat and Mantosh Biswas. 2022b. Modified Heat Method using GMRES for Geodesic Distance. In 2022 IEEE Conference on Interdisciplinary Approaches in Technology and Management for Social Innovation (IATMSI). IEEE, 1--5.
[64]
Rohan Sawhney, Ruihao Ye, Johann Korndoerfer, and Keenan Crane. 2020. FCPW: Fastest Closest Points in the West.
[65]
Silvia Sellán and Alec Jacobson. 2022. Stochastic Poisson Surface Reconstruction. ACM Trans. Graph. 41, 6, Article 227 (nov 2022), 12 pages.
[66]
James A Sethian. 1999. Fast marching methods. SIAM review 41, 2 (1999), 199--235.
[67]
Nicholas Sharp and Keenan Crane. 2020a. A Laplacian for Nonmanifold Triangle Meshes. Computer Graphics Forum (SGP) 39, 5 (2020).
[68]
Nicholas Sharp and Keenan Crane. 2020b. You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges. ACM Trans. Graph. 39, 6 (2020).
[69]
Nicholas Sharp, Keenan Crane, et al. 2019a. GeometryCentral: A modern C++ library of data structures and algorithms for geometry processing. https://geometry-central.net/. (2019).
[70]
Nicholas Sharp, Mark Gillespie, and Keenan Crane. 2021. Geometry Processing with Intrinsic Triangulations. (2021).
[71]
Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019b. Navigating Intrinsic Triangulations. ACM Trans. Graph. 38, 4 (2019).
[72]
Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019c. The Vector Heat Method. ACM Trans. Graph. 38, 3 (2019).
[73]
Oded Stein, Max Wardetzky, Alec Jacobson, and Eitan Grinspun. 2020. A Simple Discretization of the Vector Dirichlet Energy. Computer Graphics Forum 39, 5 (2020).
[74]
Kaiyue Sun and Xiangyang Liu. 2022. Heat method of non-uniform diffusion for computing geodesic distance on images and surfaces. Multimedia Tools and Applications 81, 25 (2022), 36293--36308.
[75]
Jiong Tao, Juyong Zhang, Bailin Deng, Zheng Fang, Yue Peng, and Ying He. 2019. Parallel and scalable heat methods for geodesic distance computation. IEEE transactions on pattern analysis and machine intelligence 43, 2 (2019), 579--594.
[76]
Philip Trettner, David Bommes, and Leif Kobbelt. 2021. Geodesic distance computation via virtual source propagation. In Computer graphics forum, Vol. 40. Wiley Online Library, 247--260.
[77]
Sathamangalam R Srinivasa Varadhan. 1967. On the behavior of the fundamental solution of the heat equation with variable coefficients. Communications on Pure and Applied Mathematics 20, 2 (1967), 431--455.
[78]
Delio Vicini, Sébastien Speierer, and Wenzel Jakob. 2022. Differentiable Signed Distance Function Rendering. Transactions on Graphics (Proceedings of SIGGRAPH) 41, 4 (July 2022), 125:1--125:18.
[79]
Hongyi Xu and Jernej Barbič. 2014. Signed Distance Fields for Polygon Soup Meshes. Graphics Interface 2014 (2014).
[80]
Lior Yariv, Omri Puny, Natalia Neverova, Oran Gafni, and Yaron Lipman. 2023. Mosaic-SDF for 3D Generative Models. arXiv preprint arXiv:2312.09222 (2023).
[81]
Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1--15.
Index Terms
- A Heat Method for Generalized Signed Distance
Recommendations
Efficient evaluation of continuous signed distance to a polygonal mesh
SCCG '12: Proceedings of the 28th Spring Conference on Computer GraphicsAn efficient representation of a polygonal mesh by a signed continuous distance field is the main focus of this work. We compare different approaches to implementing such a representation and choose the most efficient one. Several optimizations to the ...
5-6-7 meshes
GI '12: Proceedings of Graphics Interface 2012We introduce a new type of meshes called 5-6-7 meshes. For many mesh processing tasks, low- or high-valence vertices are undesirable. At the same time, it is not always possible to achieve complete vertex valence regularity, i.e., to only have valence-6 ...
Towards flattenable mesh surfaces
In many industries, products are constructed by assembled surface patches in @?^3, where each patch is expected to have an isometric map to a corresponding region in @?^2. The widely investigated developable surfaces in differential geometry show this ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 July 2024
Published in TOG Volume 43, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 474Total Downloads
- Downloads (Last 12 months)474
- Downloads (Last 6 weeks)89
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in