{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:07:59Z","timestamp":1784268479977,"version":"3.55.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Adobe Inc."},{"DOI":"10.13039\/100004675","name":"Autodesk","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100004675","id-type":"DOI","asserted-by":"crossref"}]},{"name":"New Frontiers of Research Fund","award":["NFRFE?201"],"award-info":[{"award-number":["NFRFE?201"]}]},{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs Program","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fields Centre for Quantitative Analysis and Modelling"},{"name":"NSERC Discovery","award":["RGPIN2017?05235, RGPAS?2017?507938"],"award-info":[{"award-number":["RGPIN2017?05235, RGPAS?2017?507938"]}]},{"DOI":"10.13039\/100004675","name":"MESH Inc","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004675","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ontario Early Research Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>\n            Given a solid 3D shape and a trajectory of it over time, we compute its\n            <jats:italic>swept volume<\/jats:italic>\n            - 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.\n          <\/jats:p>","DOI":"10.1145\/3450626.3459780","type":"journal-article","created":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T00:04:27Z","timestamp":1626739467000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Swept volumes via spacetime numerical continuation"],"prefix":"10.1145","volume":"40","author":[{"given":"Silvia","family":"Sell\u00e1n","sequence":"first","affiliation":[{"name":"University of Toronto"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noam","family":"Aigerman","sequence":"additional","affiliation":[{"name":"Adobe Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alec","family":"Jacobson","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218654306000858"},{"key":"e_1_2_2_2_1","volume-title":"Allen","author":"Abrams Steven","year":"2000","unstructured":"Steven Abrams and Peter K . Allen . 2000 . Computing swept volumes. Comput. Animat. Virtual Worlds ( 2000). Steven Abrams and Peter K. Allen. 2000. Computing swept volumes. Comput. Animat. Virtual Worlds (2000)."},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Eugene L Allgower and Kurt Georg. 2003. Introduction to numerical continuation methods. SIAM.  Eugene L Allgower and Kurt Georg. 2003. Introduction to numerical continuation methods. SIAM.","DOI":"10.1137\/1.9780898719154"},{"key":"e_1_2_2_4_1","volume-title":"Fast Winding Numbers for Soups and Clouds. ACM Transactions on Graphics","author":"Barill Gavin","year":"2018","unstructured":"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 ). 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)."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(99)00017-2"},{"key":"e_1_2_2_6_1","volume-title":"Polygonization of implicit surfaces. Computer-Aided Geometric Design","author":"Bloomenthal Jules","year":"1988","unstructured":"Jules Bloomenthal . 1988. Polygonization of implicit surfaces. Computer-Aided Geometric Design ( 1988 ). Jules Bloomenthal. 1988. Polygonization of implicit surfaces. Computer-Aided Geometric Design (1988)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization.  Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_2_8_1","volume-title":"Computer Graphics Forum","author":"Campen Marcel","unstructured":"Marcel Campen and Leif Kobbelt . 2010. Polygonal boundary evaluation of minkowski sums and swept volumes . In Computer Graphics Forum , Vol. 29 . Wiley Online Library . Marcel Campen and Leif Kobbelt. 2010. Polygonal boundary evaluation of minkowski sums and swept volumes. In Computer Graphics Forum, Vol. 29. Wiley Online Library."},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Gianmarco Cherchi Marco Livesu Riccardo Scateni and Marco Attene. 2020. Fast and Robust Mesh Arrangements Using Floating-Point Arithmetic. ACM Trans. Graph. (2020).  Gianmarco Cherchi Marco Livesu Riccardo Scateni and Marco Attene. 2020. Fast and Robust Mesh Arrangements Using Floating-Point Arithmetic. ACM Trans. Graph. (2020).","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_2_10_1","unstructured":"Thomas Davies Derek Nowrouzezahrai and Alec Jacobson. 2021. On the Effectiveness of Weight-Encoded Neural Implicit 3D Shapes. arXiv:2009.09808 [cs.GR]  Thomas Davies Derek Nowrouzezahrai and Alec Jacobson. 2021. On the Effectiveness of Weight-Encoded Neural Implicit 3D Shapes. arXiv:2009.09808 [cs.GR]"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925900"},{"key":"e_1_2_2_12_1","volume-title":"Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH) 32, 4","author":"Jacobson Alec","year":"2013","unstructured":"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. 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."},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo etal 2018. libigl: A simple C++ geometry processing library. http:\/\/libigl.github.io\/libigl\/.  Alec Jacobson Daniele Panozzo et al. 2018. libigl: A simple C++ geometry processing library. http:\/\/libigl.github.io\/libigl\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566586"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2004.01.004"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383265"},{"key":"e_1_2_2_17_1","volume-title":"Marching cubes: A high resolution 3D surface construction algorithm. ACM siggraph computer graphics 21, 4","author":"Lorensen William E","year":"1987","unstructured":"William E Lorensen and Harvey E Cline . 1987. Marching cubes: A high resolution 3D surface construction algorithm. ACM siggraph computer graphics 21, 4 ( 1987 ). William E Lorensen and Harvey E Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. ACM siggraph computer graphics 21, 4 (1987)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.279039"},{"key":"e_1_2_2_19_1","volume-title":"Numerical optimization","author":"Nocedal Jorge","unstructured":"Jorge Nocedal and Stephen Wright . 2006. Numerical optimization . Springer . Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00025"},{"key":"e_1_2_2_21_1","volume-title":"High-Resolution Volumetric Computation of Offset Surfaces with Feature Preservation. Comput. Graph. Forum","author":"Pavic Darko","year":"2008","unstructured":"Darko Pavic and Leif Kobbelt . 2008. High-Resolution Volumetric Computation of Offset Surfaces with Feature Preservation. Comput. Graph. Forum ( 2008 ). Darko Pavic and Leif Kobbelt. 2008. High-Resolution Volumetric Computation of Offset Surfaces with Feature Preservation. Comput. Graph. Forum (2008)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/16864360.2005.10738324"},{"key":"e_1_2_2_23_1","unstructured":"\u00cd\u00f1igo Qu\u00edlez. 2020. Interior SDFs. https:\/\/www.iquilezles.org\/www\/articles\/interiordistance\/interiordistance.htm. Accessed: 2021-05-12.  \u00cd\u00f1igo Qu\u00edlez. 2020. Interior SDFs. https:\/\/www.iquilezles.org\/www\/articles\/interiordistance\/interiordistance.htm. Accessed: 2021-05-12."},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"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).  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).","DOI":"10.1016\/j.cad.2007.02.016"},{"key":"e_1_2_2_25_1","volume-title":"Schmidt and Brian Wyvill","author":"Ryan","year":"2005","unstructured":"Ryan M. Schmidt and Brian Wyvill . 2005 . Generalized sweep templates for implicit modeling. In Proc. GRAPHITE. 187--196. Ryan M. Schmidt and Brian Wyvill. 2005. Generalized sweep templates for implicit modeling. In Proc. GRAPHITE. 187--196."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/951087.951099"},{"key":"e_1_2_2_27_1","volume-title":"Proc. Symp. on Solid Modeling and Applications.","author":"Sourin A.","unstructured":"A. Sourin and A. Pasko . 1995. Function Representation for Sweeping by a Moving Solid . In Proc. Symp. on Solid Modeling and Applications. A. Sourin and A. Pasko. 1995. Function Representation for Sweeping by a Moving Solid. In Proc. Symp. on Solid Modeling and Applications."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1986.1087729"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224921"},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"W. P. Wang and K. K. Wang. 1986. Geometric Modeling for Swept Volume of Moving Solids. IEEE Computer Graphics and Applications 6 12 (1986).  W. P. Wang and K. K. Wang. 1986. Geometric Modeling for Swept Volume of Moving Solids. IEEE Computer Graphics and Applications 6 12 (1986).","DOI":"10.1109\/MCG.1986.276586"},{"key":"e_1_2_2_31_1","volume-title":"Leu","author":"Weld John D.","year":"1990","unstructured":"John D. Weld and Ming C . Leu . 1990 . Geometric Representation of Swept Volumes with Application to Polyhedral Objects. Int. J. Robotics Res. ( 1990). John D. Weld and Ming C. Leu. 1990. Geometric Representation of Swept Volumes with Application to Polyhedral Objects. Int. J. Robotics Res. (1990)."},{"key":"e_1_2_2_32_1","volume-title":"Advanced Computer Graphics","author":"Wyvill Geoff","unstructured":"Geoff Wyvill , Craig McPheeters , and Brian Wyvill . 1986. Soft objects . In Advanced Computer Graphics . Springer , 113--128. Geoff Wyvill, Craig McPheeters, and Brian Wyvill. 1986. Soft objects. In Advanced Computer Graphics. Springer, 113--128."},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Xinyu Zhang Young J Kim and Dinesh Manocha. 2009. Reliable sweeps. In 2009 SIAM\/ACM joint conference on geometric and physical modeling. 373--378.  Xinyu Zhang Young J Kim and Dinesh Manocha. 2009. Reliable sweeps. In 2009 SIAM\/ACM joint conference on geometric and physical modeling. 373--378.","DOI":"10.1145\/1629255.1629306"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Qingnan Zhou Eitan Grinspun Denis Zorin and Alec Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Trans. Graph. (2016).  Qingnan Zhou Eitan Grinspun Denis Zorin and Alec Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Trans. Graph. (2016).","DOI":"10.1145\/2897824.2925901"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450626.3459780","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450626.3459780","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:16Z","timestamp":1750191436000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450626.3459780"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":34,"aliases":["10.1145\/3476576.3476603"],"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3450626.3459780"],"URL":"https:\/\/doi.org\/10.1145\/3450626.3459780","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,19]]},"assertion":[{"value":"2021-07-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}