“Fast evaluation of smooth distance constraints on co-dimensional geometry” by Madan and Levin

We present a new method for computing a smooth minimum distance function based on the LogSumExp function for point clouds, edge meshes, triangle meshes, and combinations of all three. We derive blending weights and a modified Barnes-Hut acceleration approach that ensure our method approximates the true distance, and is conservative (points outside the zero isosurface are guaranteed to be outside the surface) and efficient to evaluate for all the above data types. This, in combination with its ability to smooth sparsely sampled and noisy data, like point clouds, shortens the gap between data acquisition and simulation, and thereby enables new applications such as direct, co-dimensional rigid body simulation using unprocessed lidar data.

1. Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin, and Claudio T. Silva. 2003. Computing and rendering point set surfaces. IEEE Transactions on visualization and computer graphics 9, 1 (2003), 3–15.Google ScholarDigital Library
2. Gavin Barill, Neil G Dickson, Ryan Schmidt, David IW Levin, and Alec Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Transactions on Graphics (TOG) 37, 4 (2018), 1–12.Google ScholarDigital Library
3. Josh Barnes and Piet Hut. 1986. A hierarchical O (N log N) force-calculation algorithm. nature 324, 6096 (1986), 446–449.Google Scholar
4. Alexander Belyaev, Pierre-Alain Fayolle, and Alexander Pasko. 2013. Signed Lp-distance fields. Computer-Aided Design 45, 2 (2013), 523–528. Solid and Physical Modeling 2012. Google ScholarDigital Library
5. Jonathan C Carr, Richard K Beatson, Jon B Cherrie, Tim J Mitchell, W Richard Fright, Bruce C McCallum, and Tim R Evans. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. 67–76.Google ScholarDigital Library
6. Zhiqin Chen and Hao Zhang. 2019. Learning Implicit Fields for Generative Shape Modeling. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). 5932–5941. Google ScholarCross Ref
7. Erwin Coumans and Yunfei Bai. 2016–2021. PyBullet, a Python module for physics simulation for games, robotics and machine learning. http://pybullet.org.Google Scholar
8. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2017. The Heat Method for Distance Computation. Commun. ACM 60, 11 (Oct. 2017), 90–99. Google ScholarDigital Library
9. Yu Fang, Minchen Li, Chenfanfu Jiang, and Danny M. Kaufman. 2021. Guaranteed Globally Injective 3D Deformation Processing. ACM Trans. Graph. (SIGGRAPH) 40, 4, Article 75 (2021).Google ScholarDigital Library
10. Zachary Ferguson, Minchen Li, Teseo Schneider, Francisca Gil-Ureta, Timothy Langlois, Chenfanfu Jiang, Denis Zorin, Danny M. Kaufman, and Daniele Panozzo. 2021. Intersection-free Rigid Body Dynamics. ACM Trans. Graph. 40, 4, Article 183 (2021).Google ScholarDigital Library
11. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
12. Karthik S. Gurumoorthy and Anand Rangarajan. 2009. A SchröDinger Equation for the Fast Computation of Approximate Euclidean Distance Functions. In Proceedings of the Second International Conference on Scale Space and Variational Methods in Computer Vision (Voss, Norway) (SSVM ’09). Springer-Verlag, Berlin, Heidelberg, 100–111. Google ScholarDigital Library
13. Alireza Ghaffari Hadigheh, Oleksandr Romanko, and Tamás Terlaky. 2007. Sensitivity analysis in convex quadratic optimization: simultaneous perturbation of the objective and right-hand-side vectors. Algorithmic Operations Research 2, 2 (2007), 94–94.Google Scholar
14. Michal Hapala, Tomáš Davidovič, Ingo Wald, Vlastimil Havran, and Philipp Slusallek. 2011. Efficient stack-less BVH traversal for ray tracing. In Proceedings of the 27th Spring Conference on Computer Graphics. 7–12.Google ScholarDigital Library
15. 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.Google ScholarCross Ref
16. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.Google Scholar
17. William Kahan. 2004. On the cost of floating-point computation without extra-precise arithmetic. World-Wide Web document (2004), 21.Google Scholar
18. Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. 2006. Poisson surface reconstruction. In Proceedings of the fourth Eurographics symposium on Geometry processing, Vol. 7.Google ScholarDigital Library
19. Michael Kazhdan and Hugues Hoppe. 2013. Screened poisson surface reconstruction. ACM Transactions on Graphics (ToG) 32, 3 (2013), 1–13.Google ScholarDigital Library
20. G. Kreisselmeier and R. Steinhauser. 1979. Systematic Control Design by Optimizing a Vector Performance Index. IFAC Proceedings Volumes 12, 7 (1979), 113–117. IFAC Symposium on computer Aided Design of Control Systems, Zurich, Switzerland, 29–31 August. Google ScholarCross Ref
21. Lei Lan, Yin Yang, Danny M. Kaufman, Junfeng Yao, Minchen Li, and Chenfanfu Jiang. 2021. Medial IPC: Accelerated Incremental Potential Contact With Medial Elastics. ACM Trans. Graph. (2021).Google Scholar
22. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020a. Incremental Potential Contact: Intersection- and Inversion-free Large Deformation Dynamics. ACM Trans. Graph. (SIGGRAPH) 39, 4, Article 49 (2020).Google ScholarDigital Library
23. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020b. Incremental Potential Contact: Intersection- and Inversion-free Large Deformation Dynamics. ACM Transactions on Graphics 39, 4 (2020).Google ScholarDigital Library
24. Minchen Li, Danny M. Kaufman, and Chenfanfu Jiang. 2021. Codimensional Incremental Potential Contact. ACM Trans. Graph. 40, 4, Article 170 (2021).Google ScholarDigital Library
25. Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Zach Corse. 2020. Local Optimization for Robust Signed Distance Field Collision. Proc. ACM Comput. Graph. Interact. Tech. 3, 1, Article 8 (April 2020), 17 pages. Google ScholarDigital Library
26. Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: position-based simulation of compliant constrained dynamics. In Proceedings of the 9th International Conference on Motion in Games. 49–54.Google ScholarDigital Library
27. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Efficient Elasticity for Character Skinning with Contact and Collisions. ACM Trans. Graph. 30, 4, Article 37 (July 2011), 12 pages. Google ScholarDigital Library
28. Lars Mescheder, Michael Oechsle, Michael Niemeyer, Sebastian Nowozin, and Andreas Geiger. 2019. Occupancy Networks: Learning 3D Reconstruction in Function Space. In Proceedings IEEE Conf. on Computer Vision and Pattern Recognition (CVPR).Google ScholarCross Ref
29. Nathan Mitchell, Mridul Aanjaneya, Rajsekhar Setaluri, and Eftychios Sifakis. 2015. Non-Manifold Level Sets: A Multivalued Implicit Surface Representation with Applications to Self-Collision Processing. ACM Trans. Graph. 34, 6, Article 247 (Oct. 2015), 9 pages. Google ScholarDigital Library
30. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (2e ed.). Springer, New York, NY, USA.Google Scholar
31. NVIDIA. 2021. NVIDIA PhysX SDK. https://developer.nvidia.com/physx-sdk.Google Scholar
32. Julian Panetta, Abtin Rahimian, and Denis Zorin. 2017. Worst-Case Stress Relief for Microstructures. ACM Trans. Graph. 36, 4, Article 122 (July 2017), 16 pages. Google ScholarDigital Library
33. Jeong Joon Park, Peter Florence, Julian Straub, Richard Newcombe, and Steven Love-grove. 2019. DeepSDF: Learning Continuous Signed Distance Functions for Shape Representation. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).Google Scholar
34. Jianbo Peng, Daniel Kristjansson, and Denis Zorin. 2004. Interactive Modeling of Topologically Complex Geometric Detail. ACM Trans. Graph. 23, 3 (Aug. 2004), 635–643. Google ScholarDigital Library
35. Jonathan Ragan-Kelley, Connelly Barnes, Andrew Adams, Sylvain Paris, Frédo Durand, and Saman Amarasinghe. 2013. Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. Acm Sigplan Notices 48, 6 (2013), 519–530.Google ScholarDigital Library
36. Manu Sethi, Anand Rangarajan, and Karthik Gurumoorthy. 2012. The Schrödinger distance transform (SDT) for point-sets and curves. In 2012 IEEE Conference on Computer Vision and Pattern Recognition. 198–205. Google ScholarCross Ref
37. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4 (2015).Google ScholarDigital Library
38. Brian Wyvill, Andrew Guy, and Eric Galin. 1999. Extending the CSG Tree. Warping, Blending and Boolean Operations in an Implicit Surface Modeling System. Computer Graphics Forum 18, 2 (1999), 149–158. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/1467-8659.00365 Google ScholarCross Ref
39. Chris Yu, Henrik Schumacher, and Keenan Crane. 2021. Repulsive Curves. ACM Trans. Graph. 40, 2 (2021).Google ScholarDigital Library
40. Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola. 2020. Dive into Deep Learning. https://d2l.ai.Google Scholar
41. Hong-Kai Zhao, Stanley Osher, and Ronald Fedkiw. 2001. Fast surface reconstruction using the level set method. In Proceedings IEEE Workshop on Variational and Level Set Methods in Computer Vision. IEEE, 194–201.Google ScholarDigital Library
42. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).Google Scholar