“Spelunking the deep: guaranteed queries on general neural implicit surfaces via range analysis” by Sharp and Jacobson

Neural implicit representations, which encode a surface as the level set of a neural network applied to spatial coordinates, have proven to be remarkably effective for optimizing, compressing, and generating 3D geometry. Although these representations are easy to fit, it is not clear how to best evaluate geometric queries on the shape, such as intersecting against a ray or finding a closest point. The predominant approach is to encourage the network to have a signed distance property. However, this property typically holds only approximately, leading to robustness issues, and holds only at the conclusion of training, inhibiting the use of queries in loss functions. Instead, this work presents a new approach to perform queries directly on general neural implicit functions for a wide range of existing architectures. Our key tool is the application of range analysis to neural networks, using automatic arithmetic rules to bound the output of a network over a region; we conduct a study of range analysis on neural networks, and identify variants of affine arithmetic which are highly effective. We use the resulting bounds to develop geometric queries including ray casting, intersection testing, constructing spatial hierarchies, fast mesh extraction, closest-point evaluation, evaluating bulk properties, and more. Our queries can be efficiently evaluated on GPUs, and offer concrete accuracy guarantees even on randomly-initialized networks, enabling their use in training objectives and beyond. We also show a preliminary application to inverse rendering.

1. Stavros P Adam, George D Magoulas, Dimitrios A Karras, and Michael N Vrahatis. 2016. Bounding the search space for global optimization of neural networks learning error: an interval analysis approach. Journal of Machine Learning Research 17 (2016), 1–40.Google Scholar
2. Götz Alefeld and Günter Mayer. 2000. Interval analysis: theory and applications. Journal of computational and applied mathematics 121, 1–2 (2000), 421–464.Google ScholarDigital Library
3. Martin Arjovsky, Soumith Chintala, and Léon Bottou. 2017. Wasserstein generative adversarial networks. In International conference on machine learning. PMLR, 214–223.Google Scholar
4. Matan Atzmon and Yaron Lipman. 2020a. Sal: Sign agnostic learning of shapes from raw data. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2565–2574.Google ScholarCross Ref
5. Matan Atzmon and Yaron Lipman. 2020b. SALD: Sign Agnostic Learning with Derivatives. In International Conference on Learning Representations.Google Scholar
6. Csaba Bálint and Gábor Valasek. 2018. Accelerating Sphere Tracing. Proceedings of Eurographics Short Papers (2018), 4 pages.Google Scholar
7. Jonathan T Barron, Ben Mildenhall, Matthew Tancik, Peter Hedman, Ricardo Martin-Brualla, and Pratul P Srinivasan. 2021. Mip-nerf: A multiscale representation for anti-aliasing neural radiance fields. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 5855–5864.Google ScholarCross Ref
8. David Betancourt and Rafi Muhanna. 2021. Interval Deep Learning for Uncertainty Quantification in Safety Applications. arXiv preprint arXiv:2105.06438 (2021).Google Scholar
9. James F Blinn. 1977. Models of light reflection for computer synthesized pictures. In Proceedings of the 4th annual conference on Computer graphics and interactive techniques. 192–198.Google ScholarDigital Library
10. James F. Blinn. 1982. A Generalization of Algebraic Surface Drawing. ACM Trans. Graph. 1, 3 (1982), 235–256.Google ScholarDigital Library
11. Jules Bloomenthal, Chandrajit Bajaj, Jim Blinn, Marie-Paule Cani, Alyn Rockwood, Brian Wyvill, and Geoff Wyvill. 1997. Introduction to Implicit Surfaces.Google Scholar
12. James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018. JAX: composable transformations of Python+NumPy programs. http://github.com/google/jaxGoogle Scholar
13. Bryan Chan. 2008. Static Analysis for Efficient Affine Arithmetic on GPUs. Master’s thesis. University of Waterloo.Google Scholar
14. Zhiqin Chen and Hao Zhang. 2019. Learning Implicit Fields for Generative Shape Modeling. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16–20, 2019. Computer Vision Foundation / IEEE, 5939–5948. http://openaccess.thecvf.com/content_CVPR_2019/html/Chen_Learning_Implicit_Fields_for_Generative_Shape_Modeling_CVPR_2019_paper.htmlGoogle Scholar
15. Forrester Cole, Kyle Genova, Avneesh Sud, Daniel Vlasic, and Zhoutong Zhang. 2021. Differentiable surface rendering via non-differentiable sampling. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 6088–6097.Google ScholarCross Ref
16. JLD Comba and J Stolfi. 1993. Affine arithmetic and its applications to computer graphics. Anais do VII SIBGRAPI, 9–18.Google Scholar
17. Hongkai Dai, Benoit Landry, Lujie Yang, Marco Pavone, and Russ Tedrake. 2021. Lyapunov-stable neural-network control. Robotics: Science and Systems (2021).Google ScholarCross Ref
18. Thomas Davies, Derek Nowrouzezahrai, and Alec Jacobson. 2020. On the Effectiveness of Weight-Encoded Neural Implicit 3D Shapes. (2020). https://arxiv.org/abs/2009.09808Google Scholar
19. A De Cusatis, Luiz Henrique De Figueiredo, and Marcelo Gattass. 1999. Interval methods for ray casting implicit surfaces with affine arithmetic. In XII Brazilian Symposium on Computer Graphics and Image Processing (Cat. No. PR00481). IEEE, 65–71.Google ScholarCross Ref
20. Tom Duff. 1992. Interval Arithmetic Recursive Subdivision for Implicit Functions and Constructive Solid Geometry. In Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’92). Association for Computing Machinery, New York, NY, USA, 131–138. Google ScholarDigital Library
21. Tim Elsner, Moritz Ibing, Victor Czech, Julius Nehring-Wirxel, and Leif Kobbelt. 2021. Intuitive Shape Editing in Latent Space. (2021). https://arxiv.org/abs/2111.12488Google Scholar
22. Andreas Fabri and Sylvain Pion. 2009. CGAL: The computational geometry algorithms library. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. 538–539.Google ScholarDigital Library
23. Jorge Flórez, Mateu Sbert, Miguel A Sainz, and Josep Vehí. 2006. Improving the interval ray tracing of implicit surfaces. In Computer Graphics International Conference. Springer, 655–664.Google ScholarDigital Library
24. Oleg Fryazinov, Alexander A. Pasko, and Peter Comninos. 2010. Fast reliable interrogation of procedurally defined implicit surfaces using extended revised affine arithmetic. Comput. Graph. 34, 6 (2010), 708–718. Google ScholarDigital Library
25. Eric Galin, Eric Guérin, Axel Paris, and Adrien Peytavie. 2020. Segment Tracing Using Local Lipschitz Bounds. Comput. Graph. Forum 39, 2 (2020), 545–554. Google ScholarCross Ref
26. Manuel N Gamito and Steve C Maddock. 2007. Ray casting implicit fractal surfaces with reduced affine arithmetic. The Visual Computer 23, 3 (2007), 155–165.Google ScholarDigital Library
27. Kyle Genova, Forrester Cole, Avneesh Sud, Aaron Sarna, and Thomas A. Funkhouser. 2020. Local Deep Implicit Functions for 3D Shape. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13–19, 2020. Computer Vision Foundation / IEEE, 4856–4865.Google Scholar
28. Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. 2018. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.12715 (2018).Google Scholar
29. Amos Gropp, Lior Yariv, Niv Haim, Matan Atzmon, and Yaron Lipman. 2020. Implicit Geometric Regularization for Learning Shapes. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13–18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119). PMLR, 3789–3799.Google Scholar
30. John C. Hart. 1996. Sphere Tracing: A Geometric Method for the Antialiased Ray Tracing of Implicit Surfaces. The Visual Computer 12, 10 (Dec. 1996), 527–545. Google ScholarCross Ref
31. Wolfgang Heidrich and Hans-Peter Seidel. 1998. Ray-tracing Procedural Displacement Shaders. In Proceedings of the Graphics Interface 1998 Conference, June 18–20, 1998, Vancouver, BC, Canada, Wayne A. Davis, Kellogg S. Booth, and Alain Fournier (Eds.). Canadian Human-Computer Communications Society, 8–16.Google Scholar
32. Wolfgang Heidrich, Philipp Slusallek, and Hans-Peter Seidel. 1998. Sampling Procedural Shaders Using Affine Arithmetic. ACM Trans. Graph. 17, 3 (1998), 158–176. Google ScholarDigital Library
33. Matt Jordan and Alexandros G. Dimakis. 2020. Exactly Computing the Local Lipschitz Constant of ReLU Networks. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6–12, 2020, virtual, Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.).Google Scholar
34. Tao Ju, Frank Losasso, Scott Schaefer, and Joe Warren. 2002. Dual contouring of hermite data. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 339–346.Google ScholarDigital Library
35. Matthew J. Keeter. 2020. Massively Parallel Rendering of Complex Closed-Form Implicit Surfaces. ACM Trans. Graph. 39, 4, Article 141 (jul 2020), 10 pages. Google ScholarDigital Library
36. Benjamin Keinert, Henry Schäfer, Johann Korndörfer, Urs Ganse, and Marc Stamminger. 2013. Improved Ray Casting of Procedural Distance Bounds. Journal of Graphics Tools 17, 4 (Oct. 2013), 127–138.Google ScholarCross Ref
37. Aaron Knoll, Younis Hijazi, Charles Hansen, Ingo Wald, and Hans Hagen. 2007. Interactive Ray Tracing of Arbitrary Implicits with SIMD Interval Arithmetic. In 2007 IEEE Symposium on Interactive Ray Tracing. 11–18.Google Scholar
38. Aaron Knoll, Younis Hijazi, Andrew E. Kensler, Mathias Schott, Charles D. Hansen, and Hans Hagen. 2009. Fast Ray Tracing of Arbitrary Implicit Surfaces with Interval and Affine Arithmetic. Comput. Graph. Forum 28, 1 (2009), 26–40. Google ScholarCross Ref
39. Jiabao Lei and Kui Jia. 2020. Analytic Marching: An Analytic Meshing Solution from Deep Implicit Surface Networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13–18 July 2020, Virtual Event (Proceedings of Machine Learning Research, Vol. 119). PMLR, 5789–5798.Google Scholar
40. Tzu-Mao Li, Miika Aittala, Frédo Durand, and Jaakko Lehtinen. 2018. Differentiable monte carlo ray tracing through edge sampling. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–11.Google ScholarDigital Library
41. Yiyi Liao, Simon Donne, and Andreas Geiger. 2018. Deep marching cubes: Learning explicit surface representations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2916–2925.Google ScholarCross Ref
42. William E Lorensen and Harvey E Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. ACM siggraph computer graphics 21, 4 (1987), 163–169.Google Scholar
43. Jai Menon. 1996. An Introduction to Implicit Techniques.Google Scholar
44. Lars Mescheder, Michael Oechsle, Michael Niemeyer, Sebastian Nowozin, and Andreas Geiger. 2019. Occupancy networks: Learning 3d reconstruction in function space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 4460–4470.Google ScholarCross Ref
45. Ben Mildenhall, Pratul P. Srinivasan, Matthew Tancik, Jonathan T. Barron, Ravi Ramamoorthi, and Ren Ng. 2020. NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis. In ECCV 2020, Vol. 12346. Springer, 405–421.Google ScholarDigital Library
46. Matthew Mirman, Maximilian Baader, and Martin Vechev. 2021. The Fundamental Limits of Interval Arithmetic for Neural Networks. arXiv preprint arXiv:2112.05235 (2021).Google Scholar
47. Don P Mitchell. 1990. Robust ray intersection with interval arithmetic. In Proceedings of Graphics Interface, Vol. 90. 68–74.Google Scholar
48. Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. 2018. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:1802.05957 (2018).Google Scholar
49. Ramon E Moore, R Baker Kearfott, and Michael J Cloud. 2009. Introduction to interval analysis. SIAM.Google Scholar
50. Thomas Müller, Alex Evans, Christoph Schied, and Alexander Keller. 2022. Instant Neural Graphics Primitives with a Multiresolution Hash Encoding. arXiv:2201.05989 (Jan. 2022).Google Scholar
51. Mohammad Sina Nabizadeh, Ravi Ramamoorthi, and Albert Chern. 2021. Kelvin transformations for simulations on infinite domains. ACM Transactions on Graphics (TOG) 40, 4 (2021), 1–15.Google ScholarDigital Library
52. Baptiste Nicolet, Alec Jacobson, andWenzel Jakob. 2021. Large steps in inverse rendering of geometry. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–13.Google ScholarDigital Library
53. Michael Niemeyer, Lars Mescheder, Michael Oechsle, and Andreas Geiger. 2020. Differentiable volumetric rendering: Learning implicit 3d representations without 3d supervision. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 3504–3515.Google ScholarCross Ref
54. Merlin Nimier-David, Delio Vicini, Tizian Zeltner, and Wenzel Jakob. 2019. Mitsuba 2: A retargetable forward and inverse renderer. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–17.Google ScholarDigital Library
55. Jeong Joon Park, Peter Florence, Julian Straub, Richard Newcombe, and Steven Love-grove. 2019. Deepsdf: Learning continuous signed distance functions for shape representation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 165–174.Google ScholarCross Ref
56. Ken Perlin and Eric M. Hoffert. 1989. Hypertexture. In Proceedings of the 16th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1989, Boston, MA, USA, July 31 – August 4, 1989, James J. Thomas (Ed.). ACM, 253–262.Google Scholar
57. Magdalena Proszewska, Marcin Mazur, Tomasz Trzciński, and Przemysław Spurek. 2021. HyperCube: Implicit Field Representations of Voxelized 3D Models. arXiv preprint arXiv:2110.05770 (2021).Google Scholar
58. Inigo Quilez. 2008. 3D SDF functions. https://www.iquilezles.org/www/articles/distfunctions/distfunctions.htmGoogle Scholar
59. Dietmar Ratz. 1996. An optimized interval slope arithmetic and its application. Inst. für Angewandte Mathematik.Google Scholar
60. Tim Reiner, Gregor Mückl, and Carsten Dachsbacher. 2011. Interactive Modeling of Implicit Surfaces Using a Direct Visualization Approach with Signed Distance Functions. Computers and Graphics 35, 3 (June 2011), 596–603.Google ScholarDigital Library
61. Edoardo Remelli, Artem Lukoianov, Stephan R. Richter, Benoît Guillard, Timur M. Bagautdinov, Pierre Baqué, and Pascal Fua. 2020. MeshSDF: Differentiable Iso-Surface Extraction. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6–12, 2020, virtual.Google Scholar
62. Alexander Reshetov, Alexei Soupikov, and Jim Hurley. 2005. Multi-level ray tracing algorithm. ACM Transactions on Graphics (TOG) 24, 3 (2005), 1176–1185.Google ScholarDigital Library
63. A. Ricci. 1973. A Constructive Geometry for Computer Graphics. Comput. J. 16, 2 (1973), 157–160. Google ScholarCross Ref
64. Siegfried M Rump. 1999. INTLAB—interval laboratory. In Developments in reliable computing. Springer, 77–104.Google Scholar
65. Siegfried M Rump and Masahide Kashiwagi. 2015. Implementation and improvements of affine arithmetic. Nonlinear Theory and Its Applications, IEICE 6, 3 (2015), 341–359.Google Scholar
66. Deepti Moyi Sahoo, Abhishek Das, and Snehashish Chakraverty. 2015. Interval data-based system identification of multistorey shear buildings by artificial neural network modelling. Architectural Science Review 58, 3 (2015), 244–254.Google ScholarCross Ref
67. Rohan Sawhney and Keenan Crane. 2020. Monte Carlo Geometry Processing: A Grid-Free Approach to PDE-Based Methods on Volumetric Domains. ACM Trans. Graph. 39, 4 (2020).Google ScholarDigital Library
68. Dario Seyb, Alec Jacobson, Derek Nowrouzezahrai, and Wojciech Jarosz. 2019. Nonlinear sphere tracing for rendering deformed signed distance fields. ACM Trans. Graph. 38, 6 (2019), 229:1–229:12.Google ScholarDigital Library
69. Tianchang Shen, Jun Gao, Kangxue Yin, Ming-Yu Liu, and Sanja Fidler. 2021. Deep Marching Tetrahedra: a Hybrid Representation for High-Resolution 3D Shape Synthesis. Advances in Neural Information Processing Systems 34 (2021).Google Scholar
70. Jorge Stolfi and Luiz Henrique De Figueiredo. 1997. Self-validated numerical methods and applications. In Monograph for 21st Brazilian Mathematics Colloquium, IMPA, Rio de Janeiro. Citeseer, Vol. 5. Citeseer.Google Scholar
71. Towaki Takikawa, Joey Litalien, Kangxue Yin, Karsten Kreis, Charles Loop, Derek Nowrouzezahrai, Alec Jacobson, Morgan McGuire, and Sanja Fidler. 2021. Neural geometric level of detail: Real-time rendering with implicit 3D shapes. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 11358–11367.Google ScholarCross Ref
72. Ayush Tewari, Justus Thies, Ben Mildenhall, Pratul Srinivasan, Edgar Tretschk, Yifan Wang, Christoph Lassner, Vincent Sitzmann, Ricardo Martin-Brualla, Stephen Lombardi, et al. 2021. Advances in neural rendering. arXiv preprint arXiv:2111.05849 (2021).Google Scholar
73. Theo Thonat, Francois Beaune, Xin Sun, Nathan Carr, and Tamy Boubekeur. 2021. Tessellation-Free Displacement Mapping for Ray Tracing. 40, 6, Article 282 (dec 2021), 16 pages. Google ScholarDigital Library
74. Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. 2018. Lipschitz-margin training: scalable certification of perturbation invariance for deep neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems. 6542–6551.Google Scholar
75. Aladin Virmaux and Kevin Scaman. 2018. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3–8, 2018, Montréal, Canada. 3839–3848.Google Scholar
76. Yifan Wang, Shihao Wu, Cengiz Öztireli, and Olga Sorkine-Hornung. 2021. Iso-Points: Optimizing Neural Implicit Surfaces With Hybrid Representations. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19–25, 2021. Computer Vision Foundation / IEEE, 374–383.Google Scholar
77. Geoff Wyvill, Craig McPheeters, and Brian Wyvill. 1986. Data structure for soft objects. Vis. Comput. 2, 4 (1986), 227–234. Google ScholarCross Ref
78. Yiheng Xie, Towaki Takikawa, Shunsuke Saito, Or Litany, Shiqin Yan, Numair Khan, Federico Tombari, James Tompkin, Vincent Sitzmann, and Srinath Sridhar. 2022. Neural Fields in Visual Computing and Beyond. Computer Graphics Forum (2022).Google Scholar
79. Guandao Yang, Serge Belongie, Bharath Hariharan, and Vladlen Koltun. 2021. Geometry Processing with Neural Fields. Advances in Neural Information Processing Systems 34 (2021).Google Scholar
80. Lior Yariv, Jiatao Gu, Yoni Kasten, and Yaron Lipman. 2021. Volume Rendering of Neural Implicit Surfaces. NeurIPS (2021).Google Scholar
81. Wang Yifan, Lukas Rahmann, and Olga Sorkine-hornung. 2022. Geometry-Consistent Neural Shape Representation with Implicit Displacement Fields. In International Conference on Learning Representations.Google Scholar
82. Rosalind Cecily Young. 1931. The algebra of many-valued quantities. Math. Ann. 104, 1 (1931), 260–290.Google ScholarCross Ref