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

  • ©Silvia Sellán, Noam Aigerman, and Alec Jacobson




    Swept volumes via spacetime numerical continuation



    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

ACM Digital Library Publication:

Overview Page: