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 trajec- tories, 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.
@article{Sellan:Swept:2021,
title = {Swept Volumes via Spacetime Numerical Continuation},
author = {Silvia Sellán and Noam Aigerman and Alec Jacobson},
year = {2021},
journal = {ACM Transactions on Graphics},
}
This project is funded in part by NSERC Discovery (RGPIN2017–05235, RGPAS–2017–507938), New Frontiers of Research Fund (NFRFE–201), the Ontario Early Research Award program, the Canada Research Chairs Program, the Fields Centre for Quantitative Analysis and Modelling and gifts by Adobe Systems, Autodesk and MESH Inc.
We thank Oded Stein, Abhishek Madan and Rahul Arora for their help rendering our results; Thomas Davies and David Farrell for providing us the inputs for Fig. 22 and Fig. 16, respectively; Xuan Dam, John Hancock and all the University of Toronto Department of Computer Science research, administrative and maintenance staff that literally kept our lab running during a very hard year.