{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T07:40:17Z","timestamp":1778658017237,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,7,29]],"date-time":"2007-07-29T00:00:00Z","timestamp":1185667200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2007,7,29]]},"abstract":"<jats:p>\n            We present a fast continuous collision detection (CCD) algorithm for articulated models using Taylor models and temporal culling. Our algorithm is a generalization of conservative advancement (CA) from convex models [Mirtich 1996] to articulated models with non-convex links. Given the initial and final configurations of a moving articulated model, our algorithm creates a continuous motion with constant translational and rotational velocities for each link, and checks for interferences between the articulated model under continuous motion and other models in the environment and for self-collisions. If collisions occur, our algorithm reports the first time of contact (TOC) as well as\n            <jats:italic>collision witness features<\/jats:italic>\n            . We have implemented our CCD algorithm and applied it to several challenging scenarios including locomotion generation, articulated-body dynamics and character motion planning. Our algorithm can perform CCDs including self-collision detection for articulated models consisting of many links and tens of thousands of triangles in 1.22 ms on average running on a 3.6 GHz Pentium 4 PC. This is an improvement on the performance of prior algorithms of more than an order of magnitude.\n          <\/jats:p>","DOI":"10.1145\/1276377.1276396","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":67,"title":["Continuous collision detection for articulated models using Taylor models and temporal culling"],"prefix":"10.1145","volume":"26","author":[{"given":"Xinyu","family":"Zhang","sequence":"first","affiliation":[{"name":"Ewha Womans University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephane","family":"Redon","sequence":"additional","affiliation":[{"name":"INRIA Rhone-Alpes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minkyoung","family":"Lee","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Young J.","family":"Kim","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,7,29]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Abdel-Malek K. Blackmore D. and Joy K. 2002. Swept volumes: foundations perspectives and applications. International Journal of Shape Modeling.  Abdel-Malek K. Blackmore D. and Joy K. 2002. Swept volumes: foundations perspectives and applications. International Journal of Shape Modeling ."},{"key":"e_1_2_2_2_1","volume-title":"Workshop on Algorithmic Foundations of Robotics, 83--96","author":"Agarwal P. K.","unstructured":"Agarwal , P. K. , Basch , J. , Guibas , L. J. , Hershberger , J. , and Zhang , L . 2001. Deformable free space tiling for kinetic collision detection . In Workshop on Algorithmic Foundations of Robotics, 83--96 . Agarwal, P. K., Basch, J., Guibas, L. J., Hershberger, J., and Zhang, L. 2001. Deformable free space tiling for kinetic collision detection. In Workshop on Algorithmic Foundations of Robotics, 83--96."},{"key":"e_1_2_2_3_1","unstructured":"Ageia. 2006. PhysX. http:\/\/www.ageia.com.  Ageia. 2006. PhysX . http:\/\/www.ageia.com."},{"key":"e_1_2_2_4_1","unstructured":"Baraff D. and Witkin A. 2001. Physically-based modeling. ACM SIGGRAPH Course Notes.  Baraff D. and Witkin A. 2001. Physically-based modeling . ACM SIGGRAPH Course Notes."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1127"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009958918582"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24738-8_9"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767773"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.862479"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the VI Sibgrapi","author":"Comba J. L. D.","unstructured":"Comba , J. L. D. , and Stolfi , J . 1993. Affine arithmetic and its applications to computer graphics . In Proceedings of the VI Sibgrapi . Recife, Brazil. Comba, J. L. D., and Stolfi, J. 1993. Affine arithmetic and its applications to computer graphics. In Proceedings of the VI Sibgrapi. Recife, Brazil."},{"key":"e_1_2_2_11_1","unstructured":"Coumans E. 2006. Bullet Physics library. http:\/\/www.continuousphysics.com.  Coumans E. 2006. Bullet Physics library . http:\/\/www.continuousphysics.com."},{"key":"e_1_2_2_12_1","volume-title":"Introduction to Robotics: Mechanics and Control","author":"Craig J. J.","unstructured":"Craig , J. J. 1989. Introduction to Robotics: Mechanics and Control . Prentice Hall . Craig, J. J. 1989. Introduction to Robotics: Mechanics and Control. Prentice Hall."},{"key":"e_1_2_2_13_1","volume-title":"Computer Graphics Forum (Proc. of Eurographics '2001)","author":"Ehmann S.","unstructured":"Ehmann , S. , and Lin , M. C . 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition . Computer Graphics Forum (Proc. of Eurographics '2001) 20, 3, 500--510. Ehmann, S., and Lin, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics '2001) 20, 3, 500--510."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237244"},{"key":"e_1_2_2_15_1","unstructured":"Havok. 2006. Havok Physics. http:\/\/www.havok.com.  Havok. 2006. Havok Physics . http:\/\/www.havok.com."},{"key":"e_1_2_2_16_1","volume-title":"Dept. of Computer Science","author":"Hubbard P. M.","unstructured":"Hubbard , P. M. 1993. Space-time bounds for collision detection. Technical report cs-93-04 , Dept. of Computer Science , Brown University , Feb . Hubbard, P. M. 1993. Space-time bounds for collision detection. Technical report cs-93-04, Dept. of Computer Science, Brown University, Feb."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/781606.781612"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.722297"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336219"},{"key":"e_1_2_2_20_1","volume-title":"Tech. Rep. TR99-018, Department of Computer Science","author":"Larsen E.","year":"1999","unstructured":"Larsen , E. , Gottschalk , S. , Lin , M. , and Manocha , D . 1999 . Fast proximity queries with swept sphere volumes. Tech. Rep. TR99-018, Department of Computer Science , University of North Carolina . Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 1999. Fast proximity queries with swept sphere volumes. Tech. Rep. TR99-018, Department of Computer Science, University of North Carolina."},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.  Lin M. and Manocha D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry .","DOI":"10.1201\/9781420035315.ch35"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344866"},{"key":"e_1_2_2_25_1","volume-title":"Methods and Applications of Interval Analysis","author":"Moore R. E.","unstructured":"Moore , R. E. 1979. Methods and Applications of Interval Analysis . SIAM , Philadelphia . ISBN 0-89871-161-4. Moore, R. E. 1979. Methods and Applications of Interval Analysis. SIAM, Philadelphia. ISBN 0-89871-161-4."},{"key":"e_1_2_2_26_1","unstructured":"MPK-Team. 2006. Motion Planning Kit. http:\/\/ai.stanford.edu\/~mitul\/mpk\/.  MPK-Team. 2006. Motion Planning Kit . http:\/\/ai.stanford.edu\/~mitul\/mpk\/."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-6918-6_14"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/VR.2006.18"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation, 4200--4205","author":"Redon S.","unstructured":"Redon , S. , and Lin , M. C . 2005. Practical local planning in the contact space . In Proceedings of IEEE International Conference on Robotics and Automation, 4200--4205 . Redon, S., and Lin, M. C. 2005. Practical local planning in the contact space. In Proceedings of IEEE International Conference on Robotics and Automation, 4200--4205."},{"key":"e_1_2_2_30_1","volume-title":"Proc. of IEEE Conference on Robotics and Automation.","author":"Redon S.","unstructured":"Redon , S. , Kheddar , A. , and Coquillart , S . 2000. An algebraic solution to the problem of collision detection for rigid polyhedral objects . Proc. of IEEE Conference on Robotics and Automation. Redon, S., Kheddar, A., and Coquillart, S. 2000. An algebraic solution to the problem of collision detection for rigid polyhedral objects. Proc. of IEEE Conference on Robotics and Automation."},{"key":"e_1_2_2_31_1","volume-title":"Proc. of Eurographics (Computer Graphics Forum).","author":"Redon S.","unstructured":"Redon , S. , Kheddar , A. , and Coquillart , S . 2002. Fast continuous collision detection between rigid bodies . Proc. of Eurographics (Computer Graphics Forum). Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. Proc. of Eurographics (Computer Graphics Forum)."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/VR.2004.46"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of ACM Symposium on Solid Modeling and Applications.","author":"Redon S.","unstructured":"Redon , S. , Kim , Y. J. , Lin , M. C. , and Manocha , D . 2004. Fast continuous collision detection for articulated models . In Proceedings of ACM Symposium on Solid Modeling and Applications. Redon, S., Kim, Y. J., Lin, M. C., and Manocha, D. 2004. Fast continuous collision detection for articulated models. In Proceedings of ACM Symposium on Solid Modeling and Applications."},{"key":"e_1_2_2_34_1","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR).","author":"Schwarzer F.","unstructured":"Schwarzer , F. , Saha , M. , and Latombe , J . -C. 2002. Exact collision checking of robot paths . In Workshop on Algorithmic Foundations of Robotics (WAFR). Schwarzer, F., Saha, M., and Latombe, J.-C. 2002. Exact collision checking of robot paths. In Workshop on Algorithmic Foundations of Robotics (WAFR)."},{"key":"e_1_2_2_35_1","unstructured":"Spong M. W. Hutchinson S. and Vidyasagar M. 2005. Robot Modeling and Control. Wiley.  Spong M. W. Hutchinson S. and Vidyasagar M. 2005. Robot Modeling and Control . Wiley."},{"key":"e_1_2_2_36_1","article-title":"Ray casting against general convex objects with application to continuous collision detection","author":"van den Bergen G.","year":"2004","unstructured":"van den Bergen , G. 2004 . Ray casting against general convex objects with application to continuous collision detection . Journal of Graphics Tools. van den Bergen, G. 2004. Ray casting against general convex objects with application to continuous collision detection. Journal of Graphics Tools.","journal-title":"Journal of Graphics Tools."},{"key":"e_1_2_2_37_1","unstructured":"Zhang X. Y. and Kim Y. J. 2007. Motion interpolation and bounds calculations in CATCH. Tech. Rep. CSE-TR-2007-01 Ewha Womans University Seoul Korea.  Zhang X. Y. and Kim Y. J. 2007. Motion interpolation and bounds calculations in CATCH. Tech. Rep. CSE-TR-2007-01 Ewha Womans University Seoul Korea."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0060-0"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1276377.1276396","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1276377.1276396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:17Z","timestamp":1750258337000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1276377.1276396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,29]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,7,29]]}},"alternative-id":["10.1145\/1276377.1276396"],"URL":"https:\/\/doi.org\/10.1145\/1276377.1276396","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,29]]},"assertion":[{"value":"2007-07-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}