{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:46:12Z","timestamp":1753879572218,"version":"3.41.2"},"reference-count":37,"publisher":"ASME International","issue":"2","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2009,6,1]]},"abstract":"<jats:p>This paper describes a new approach to perform continuous collision and interference detection between a pair of arbitrarily complex objects moving according to general three-dimensional affine motions. Our approach, which does not require any envelope computations, recasts the problem of detecting collisions and computing the interfering subsets in terms of inherently parallel set membership classification tests of specific curves against the original (static) geometric representations. We show that our approach can compute the subsets of the moving objects that collide and interfere, as well as the times of collision, which has important applications in mechanical design and manufacturing. Our approach can be implemented for any geometric representation that supports curve-solid intersections, such as implicit and parametric representations. We describe an implementation of the proposed technique for solids given as a boundary representation (B-rep), and illustrate its effectiveness for several rigid and deformable moving objects bounded by tesselated and freeform surfaces of various complexities. Furthermore, we show that our approach can be extended to also identify the local and global self-intersections of the envelopes of the moving objects without requiring to compute these envelopes explicitly. The paper concludes by summarizing the proposed approach as well as reviewing relevant computational improvements that can decrease the computational cost of the prototype implementation by orders of magnitude.<\/jats:p>","DOI":"10.1115\/1.3130142","type":"journal-article","created":{"date-parts":[[2009,6,4]],"date-time":"2009-06-04T18:25:47Z","timestamp":1244139947000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":7,"title":["Continuous Collision and Interference Detection for 3D Geometric Models"],"prefix":"10.1115","volume":"9","author":[{"given":"Horea T.","family":"Ilie\u015f","sequence":"first","affiliation":[{"name":"Department of Mechanical Engineering, Computational Design Laboratory, University of Connecticut, Storrs, CT 06269-3139"}]}],"member":"33","published-online":{"date-parts":[[2009,6,4]]},"reference":[{"key":"2019100514385249000_c1","first-page":"121","article-title":"Interval Analysis for Computer Graphics","volume-title":"SIGGRAPH \u201992: Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques","author":"Snyder"},{"key":"2019100514385249000_c2","first-page":"15","article-title":"Collision Detection and Proximity Queries","volume-title":"SIGGRAPH \u201904: ACM SIGGRAPH 2004 Course Notes","author":"Hadap"},{"key":"2019100514385249000_c3","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1109\/TPAMI.1986.4767773","article-title":"Collision Detection for Moving Polyhedra","volume":"PAMI-8","author":"Canny","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell.","ISSN":"https:\/\/id.crossref.org\/issn\/0162-8828","issn-type":"print"},{"issue":"1","key":"2019100514385249000_c4","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1115\/1.2919312","article-title":"Dynamic Collision Detection Using Space Partitioning","volume":"115","author":"Ganter","journal-title":"ASME J. Mech. Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0161-8458","issn-type":"print"},{"article-title":"Dynamic Collision Detection Using Swept Solids","author":"Ganter","key":"2019100514385249000_c5","doi-asserted-by":"crossref","DOI":"10.1115\/1.3258768"},{"key":"2019100514385249000_c6","doi-asserted-by":"crossref","unstructured":"Ponamgi, M. K., Manocha, D., and Lin, M. C., 1994, \u201cIncremental Algorithms for Collision Detection Between General Solid Models,\u201d Department of Computer Science, University of North Carolina-Chapel Hill, Technical Report No. TR94-061.","DOI":"10.1145\/218013.218076"},{"issue":"2","key":"2019100514385249000_c7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0097-8493(00)00130-8","article-title":"3D Collision Detection: A Survey","volume":"25","author":"Jim\u00e9nez","journal-title":"Comput. Graph.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-8930","issn-type":"print"},{"issue":"9","key":"2019100514385249000_c8","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1016\/j.cad.2004.09.018","article-title":"Precise Global Collision Detection in Multi-Axis NC-Machining","volume":"37","author":"Ilushin","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"key":"2019100514385249000_c9","first-page":"393","article-title":"Bd-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models","volume-title":"SIGGRAPH \u201904: ACM SIGGRAPH 2004 Papers","author":"James"},{"key":"2019100514385249000_c10","first-page":"321","article-title":"Efficient Collision Detection for Curved Solid Objects","volume-title":"SMA \u201902: Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications","author":"Sch\u00f6mer"},{"key":"2019100514385249000_c11","first-page":"39","article-title":"Geometric Collisions for Time-Dependent Parametric Surfaces","volume-title":"SIGGRAPH \u201990: Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques","author":"Herzen"},{"key":"2019100514385249000_c12","first-page":"155","article-title":"Efficient and Accurate Interference Detection for Polynomial Deformation","volume-title":"CA \u201996: Proceedings of the Computer Animation","author":"Hughes"},{"first-page":"1417","article-title":"Collision Detection Algorithm for NURBS Surfaces in Interactive Applications","author":"Page","key":"2019100514385249000_c13"},{"issue":"9","key":"2019100514385249000_c14","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1016\/j.cad.2008.07.005","article-title":"Classifying Points for Sweeping Solids","volume":"40","author":"Erdim","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"issue":"1","key":"2019100514385249000_c15","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1142\/S0218654306000858","article-title":"Swept Volumes: Foundations, Perspectives, and Applications","volume":"12","author":"Abdel-Malek","journal-title":"Int. J. Shape Model.","ISSN":"https:\/\/id.crossref.org\/issn\/0218-6543","issn-type":"print"},{"issue":"3","key":"2019100514385249000_c16","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0010-4485(99)00015-9","article-title":"The Dual of Sweep","volume":"31","author":"Ilie\u015f","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"issue":"3","key":"2019100514385249000_c17","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0010-4485(97)00060-2","article-title":"Interpolation Schemes for Rigid Body Motion","volume":"30","author":"Zefran","journal-title":"CAD","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"issue":"3","key":"2019100514385249000_c18","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0010-4485(97)00056-0","article-title":"Rational Motion Design\u2014A Survey","volume":"30","author":"R\u00f6schel","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"key":"2019100514385249000_c19","unstructured":"Tilove, R. B.\n          , 1977, \u201cA Study of Geometric Set Membership Classification,\u201d MS thesis, University of Rochester, Rochester, NY"},{"issue":"4","key":"2019100514385249000_c20","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1145\/356827.356833","article-title":"Representations for Rigid Solids: Theory, Methods and Systems","volume":"12","author":"Requicha","journal-title":"ACM Comput. Surv.","ISSN":"https:\/\/id.crossref.org\/issn\/0360-0300","issn-type":"print"},{"issue":"10","key":"2019100514385249000_c21","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1109\/TC.1980.1675470","article-title":"Set Membership Classification: A Unified Approach to Geometric Intersection Problems","volume":"C-29","author":"Tilove","journal-title":"IEEE Trans. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9340","issn-type":"print"},{"key":"2019100514385249000_c22","unstructured":"Requicha, A.\n          , 2006, \u201cGeometric Modeling: A First Course,\u201d available online, http:\/\/www-pal.usc.edu\/~requicha\/book.html"},{"key":"2019100514385249000_c23","unstructured":"TetGen, Weierstrass Institute for Applied Analysis and Stochastics, http:\/\/tetgen.berlios.de\/."},{"issue":"1","key":"2019100514385249000_c24","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/174462.156635","article-title":"Three-Dimensional Alpha Shapes","volume":"13","author":"Edelsbrunner","journal-title":"ACM Trans. Graph.","ISSN":"https:\/\/id.crossref.org\/issn\/0730-0301","issn-type":"print"},{"issue":"8","key":"2019100514385249000_c25","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1016\/j.cagd.2004.07.008","article-title":"Developable Surface Fitting to Point Clouds","volume":"21","author":"Peternell","journal-title":"Comput. Aided Geom. Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-8396","issn-type":"print"},{"volume-title":"Reconstructing Manifold and Non-Manifold Surfaces From Point Clouds","author":"Wang","key":"2019100514385249000_c26"},{"volume-title":"Curves and Singularities","author":"Bruce","key":"2019100514385249000_c27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172615"},{"issue":"10","key":"2019100514385249000_c28","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1016\/j.cad.2007.03.007","article-title":"Detecting and Quantifying Envelope Singularities in the Plane","volume":"39","author":"Erdim","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"key":"2019100514385249000_c29","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1115\/1.2826869","article-title":"Computer-Aided Design With Spatial Rational B-Spline Motions","volume":"118","author":"J\u00fcttler","journal-title":"ASME J. Mech. Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0161-8458","issn-type":"print"},{"key":"2019100514385249000_c30","first-page":"271","article-title":"Spatial Rational Motions and Their Applications in Computer Aided Geometric Design","volume-title":"Mathematical Methods for Curves and Surfaces","author":"J\u00fcttler"},{"issue":"2","key":"2019100514385249000_c31","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0010-4485(95)92152-I","article-title":"Planar Rational B-Spline Motions","volume":"27","author":"Wagner","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"key":"2019100514385249000_c32","first-page":"151","article-title":"Computer Aided Design of Robot Trajectories Using Rational Motions","volume-title":"Recent Advances in Robot Kinematics","author":"Wagner"},{"issue":"9","key":"2019100514385249000_c33","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1016\/S0167-8396(97)00008-3","article-title":"Algebraic Pruning: A Fast Technique for Curve and Surface Intersection","volume":"14","author":"Manocha","journal-title":"Comput. Aided Geom. Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-8396","issn-type":"print"},{"issue":"3","key":"2019100514385249000_c34","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0010-4485(97)00061-4","article-title":"Cartesian Spline Interpolation for Industrial Robots","volume":"30","author":"Horsch","journal-title":"Comput.-Aided Des.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-4485","issn-type":"print"},{"key":"2019100514385249000_c35","unstructured":"QHULL, The Geometry Center, http:\/\/www.qhull.org."},{"key":"2019100514385249000_c36","unstructured":"The NIST Design Repository, http:\/\/www.designrepository.org\/."},{"key":"2019100514385249000_c37","unstructured":"The Stanford 3D Scanning Repository, http:\/\/graphics.stanford.edu\/data\/3Dscanrep\/."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.3130142\/5502557\/021007_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.3130142\/5502557\/021007_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T14:39:02Z","timestamp":1570286342000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.3130142\/465815\/Continuous-Collision-and-Interference-Detection"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.3130142","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2009,6,1]]},"article-number":"021007"}}