“Swept volumes via spacetime numerical continuation” by Sellán, Aigerman and Jacobson

Given a solid 3D shape and a trajectory of it over time, we compute its swept volume – the union of all points contained within the shape at some moment in time. We consider the representation of the input and output as implicit functions, and lift the problem to 4D spacetime, where we show the problem gains a continuous structure which avoids expensive global searches. We exploit this structure via a continuation method which marches and reconstructs the zero level set of the swept volume, using the temporal dimension to avoid erroneous solutions. We show that, compared to other methods, our approach is not restricted to a limited class of shapes or trajectories, is extremely robust, and its asymptotic complexity is an order lower than standards used in the industry, enabling its use in applications such as modeling, constructive solid geometry, and path planning.

1. Karim Abdel-Malek, Jingzhou Yang, Denis Blackmore, and Ken Joy. 2006. Swept volumes: fundation, perspectives, and applications. International Journal of Shape Modeling 12, 01 (2006), 87–127.Google ScholarCross Ref
2. Steven Abrams and Peter K. Allen. 2000. Computing swept volumes. Comput. Animat. Virtual Worlds (2000).Google Scholar
3. Eugene L Allgower and Kurt Georg. 2003. Introduction to numerical continuation methods. SIAM.Google Scholar
4. Gavin Barill, Neil Dickson, Ryan Schmidt, David I.W. Levin, and Alec Jacobson. 2018. Fast Winding Numbers for Soups and Clouds. ACM Transactions on Graphics (2018).Google Scholar
5. Denis Blackmore, Roman Samulyak, and Ming C Leu. 1999. Trimming swept volumes. Computer-Aided Design 31, 3 (1999), 215–223.Google ScholarCross Ref
6. Jules Bloomenthal. 1988. Polygonization of implicit surfaces. Computer-Aided Geometric Design (1988).Google Scholar
7. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization.Google Scholar
8. Marcel Campen and Leif Kobbelt. 2010. Polygonal boundary evaluation of minkowski sums and swept volumes. In Computer Graphics Forum, Vol. 29. Wiley Online Library.Google Scholar
9. Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and Robust Mesh Arrangements Using Floating-Point Arithmetic. ACM Trans. Graph. (2020).Google Scholar
10. Thomas Davies, Derek Nowrouzezahrai, and Alec Jacobson. 2021. On the Effectiveness of Weight-Encoded Neural Implicit 3D Shapes. arXiv:2009.09808 [cs.GR]Google Scholar
11. Akash Garg, Alec Jacobson, and Eitan Grinspun. 2016. Computational Design of Reconfigurables. ACM Trans. Graph. 35, 4 (2016).Google ScholarDigital Library
12. Alec Jacobson, Ladislav Kavan, and Olga Sorkine-Hornung. 2013. Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 32, 4 (2013), 33:1–33:12.Google Scholar
13. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. http://libigl.github.io/libigl/.Google Scholar
14. Tao Ju, Frank Losasso, Scott Schaefer, and Joe D. Warren. 2002. Dual contouring of hermite data. ACM Trans. Graph. 21, 3 (2002), 339–346.Google ScholarDigital Library
15. Young J Kim, Gokul Varadhan, Ming C Lin, and Dinesh Manocha. 2004. Fast swept volume approximation of complex polyhedral models. Computer-Aided Design 36, 11 (2004), 1013–1027.Google ScholarDigital Library
16. Leif P Kobbelt, Mario Botsch, Ulrich Schwanecke, and Hans-Peter Seidel. 2001. Feature sensitive surface extraction from volume data. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. 57–66.Google ScholarDigital Library
17. William E Lorensen and Harvey E Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. ACM siggraph computer graphics 21, 4 (1987).Google Scholar
18. Jai Menon, Richard J Marisa, and Jovan Zagajac. 1994. More powerful solid modeling through ray representations. IEEE Computer Graphics and Applications 14, 3 (1994).Google ScholarDigital Library
19. Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer.Google Scholar
20. Jeong Joon Park, Peter Florence, Julian Straub, Richard A. Newcombe, and Steven Lovegrove. 2019. DeepSDF: Learning Continuous Signed Distance Functions for Shape Representation. In Proc. CVPR.Google ScholarCross Ref
21. Darko Pavic and Leif Kobbelt. 2008. High-Resolution Volumetric Computation of Offset Surfaces with Feature Preservation. Comput. Graph. Forum (2008).Google Scholar
22. Martin Peternell, Helmut Pottmann, Tibor Steiner, and Hongkai Zhao. 2005. Swept volumes. Computer-Aided Design and Applications 2, 5 (2005), 599–608.Google ScholarCross Ref
23. Íñigo Quílez. 2020. Interior SDFs. https://www.iquilezles.org/www/articles/interiordistance/interiordistance.htm. Accessed: 2021-05-12.Google Scholar
24. Jarek Rossignac, Jay J Kim, SC Song, KC Suh, and CB Joung. 2007. Boundary of the volume swept by a free-form solid in screw motion. Computer-Aided Design (2007).Google Scholar
25. Ryan M. Schmidt and Brian Wyvill. 2005. Generalized sweep templates for implicit modeling. In Proc. GRAPHITE. 187–196.Google Scholar
26. William J Schroeder, William E Lorensen, and Steve Linthicum. 1994. Implicit modeling of swept surfaces and volumes. In Proceedings Visualization’94. IEEE, 40–45.Google ScholarDigital Library
27. A. Sourin and A. Pasko. 1995. Function Representation for Sweeping by a Moving Solid. In Proc. Symp. on Solid Modeling and Applications.Google Scholar
28. Ugur Sungurtekin and H Voelcker. 1986. Graphical simulation & automatic verification of NC machining programs. In Proceedings. 1986 IEEE International Conference on Robotics and Automation, Vol. 3. IEEE, 156–165.Google ScholarCross Ref
29. Andreas Von Dziegielewski, Michael Hemmer, and Elmar Schömer. 2012. High quality conservative surface mesh generation for swept volumes. In 2012 IEEE International Conference on Robotics and Automation. IEEE, 764–769.Google ScholarCross Ref
30. W. P. Wang and K. K. Wang. 1986. Geometric Modeling for Swept Volume of Moving Solids. IEEE Computer Graphics and Applications 6, 12 (1986).Google Scholar
31. John D. Weld and Ming C. Leu. 1990. Geometric Representation of Swept Volumes with Application to Polyhedral Objects. Int. J. Robotics Res. (1990).Google Scholar
32. Geoff Wyvill, Craig McPheeters, and Brian Wyvill. 1986. Soft objects. In Advanced Computer Graphics. Springer, 113–128.Google Scholar
33. Xinyu Zhang, Young J Kim, and Dinesh Manocha. 2009. Reliable sweeps. In 2009 SIAM/ACM joint conference on geometric and physical modeling. 373–378.Google Scholar
34. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Trans. Graph. (2016).Google Scholar