{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T19:10:19Z","timestamp":1734203419725,"version":"3.30.2"},"reference-count":54,"publisher":"ASME International","issue":"4","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2003,12,1]]},"abstract":"<jats:p>The prediction of collisions amongst N rigid objects may be reduced to a series of computations of the time to first contact for all pairs of objects. Simple enclosing bounds and hierarchical partitions of the space-time domain are often used to avoid testing object-pairs that clearly will not collide. When the remaining pairs involve only polyhedra under straight-line translation, the exact computation of the collision time and of the contacts requires only solving for intersections between linear geometries. When a pair is subject to a more general relative motion, such a direct collision prediction calculation may be intractable. The popular brute force collision detection strategy of executing the motion for a series of small time steps and of checking for static interferences after each step is often computationally prohibitive. We propose instead a less expensive collision prediction strategy, where we approximate the relative motion between pairs of objects by a sequence of screw motion segments, each defined by the relative position and orientation of the two objects at the beginning and at the end of the segment. We reduce the computation of the exact collision time and of the corresponding face\/vertex and edge\/edge collision points to the numeric extraction of the roots of simple univariate analytic functions. Furthermore, we propose a series of simple rejection tests, which exploit the particularity of the screw motion to immediately decide that some objects do not collide or to speed-up the prediction of collisions by about 30%, avoiding on average 3\/4 of the root-finding queries even when the object actually collide.<\/jats:p>","DOI":"10.1115\/1.1632526","type":"journal-article","created":{"date-parts":[[2003,12,24]],"date-time":"2003-12-24T23:00:38Z","timestamp":1072306838000},"page":"295-301","update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":3,"title":["Collision Prediction"],"prefix":"10.1115","volume":"3","author":[{"given":"Byungmoon","family":"Kim","sequence":"first","affiliation":[{"name":"GVU Center and College of Computing, Georgia Institute of Technology, Atlanta, GA 30332"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jarek","family":"Rossignac","sequence":"additional","affiliation":[{"name":"GVU Center and College of Computing, Georgia Institute of Technology, Atlanta, GA 30332"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2003,12,24]]},"reference":[{"unstructured":"Ahuja, N., Chien, R. T., Yen, R., Bridwell, N., 1980, \u201cInterference Detection and Collision Avoidance among Three Dimensional Objects,\u201d In Ist Annual National Conference on AI, Stanford University.","key":"2019100521564059700_r1"},{"doi-asserted-by":"crossref","unstructured":"Bonner, S., and Kelley, R. B., 1988, \u201cA Representation Scheme for Rapid 3-D Collision Detection,\u201d Proceedings of IEEE International Symposium on Intelligent Control, pp. 320\u2013325.","key":"2019100521564059700_r2","DOI":"10.1109\/ISIC.1988.65450"},{"doi-asserted-by":"crossref","unstructured":"Boyse, J. W. , 1979, \u201cInterference Detection Among Solids and Surfaces,\u201d Commun. ACM, 22(1), pp. 3\u20139.","key":"2019100521564059700_r3","DOI":"10.1145\/359046.359048"},{"unstructured":"Lin, M. C., and Gottschalk, S., 1998, \u201cCollision Detection Between Geometric Models: A Survey,\u201d Proceedings of IMA Conference on Mathematics of Surfaces, volume 1, pp. 602\u2013608.","key":"2019100521564059700_r4"},{"doi-asserted-by":"crossref","unstructured":"Hayward, V., 1986, \u201cFast Collision Detection Scheme by Recursive Decomposition of a Manipulator Workspace,\u201d Proceedings of IEEE International Conference on Robotics and Automation, pp. 1044\u20131049.","key":"2019100521564059700_r5","DOI":"10.1109\/ROBOT.1986.1087620"},{"doi-asserted-by":"crossref","unstructured":"Jimenez, P., Thomas, F., and Torras, C., 2001, \u201c3D Collision Detection: A Survey,\u201d Comput. Graph., 25(2), pp. 269\u2013285.","key":"2019100521564059700_r6","DOI":"10.1016\/S0097-8493(00)00130-8"},{"unstructured":"Korein, J. U., 1984, A Geometric Investigation of Reach. The MIT Press.","key":"2019100521564059700_r7"},{"doi-asserted-by":"crossref","unstructured":"Snyder, J. M., Woodbury, A. R., Fleischer, K., Currin, B., and Barr, A. H., 1993, \u201cInterval Methods for Multi-point Collisions Between Time-dependent Curved Surfaces,\u201d Proceedings of ACM Siggraph, pp. 321\u2013334.","key":"2019100521564059700_r8","DOI":"10.1145\/166117.166158"},{"doi-asserted-by":"crossref","unstructured":"Von Herzen, A. H. B. B., and Zatz, H. R., 1990, \u201cGeometric Collisions for Time-dependent Parametric Surfaces,\u201d ACM Computer Graphics, 24(4), pp. 39\u201348.","key":"2019100521564059700_r9","DOI":"10.1145\/97880.97883"},{"doi-asserted-by":"crossref","unstructured":"Lin, M. C., and Canny, J. F., 1991, \u201cA Fast Algorithm for Incremental Distance Calculation,\u201d Proceedings of IEEE International Conference on Robotics and Automation, volume 2, pp. 1008\u20131014.","key":"2019100521564059700_r10","DOI":"10.1109\/ROBOT.1991.131723"},{"doi-asserted-by":"crossref","unstructured":"Rimon, E., and Boyd, S. P., 1997, \u201cObstacle Collision Detection Using Best Ellipsoid Fit,\u201d J. Intell. Robotic Syst., 18(2), pp. 105\u2013126.","key":"2019100521564059700_r11","DOI":"10.1023\/A:1007960531949"},{"doi-asserted-by":"crossref","unstructured":"Bajaj, C., and Dey, T., 1992, \u201cConvex Decomposition of Polyhedra and Robustness,\u201d SIAM J. Comput., 21(2), pp. 9\u201364.","key":"2019100521564059700_r12","DOI":"10.1137\/0221025"},{"doi-asserted-by":"crossref","unstructured":"Chazelle, B. , 1984, \u201cConvex Partitions of Polyhedra: A Lower Bound and a Worst-case Optimal Algorithm,\u201d SIAM J. Comput., 13(3), pp. 488\u2013507.","key":"2019100521564059700_r13","DOI":"10.1137\/0213031"},{"doi-asserted-by":"crossref","unstructured":"Chazelle, B., Dobkin, D., Shouraboura, N., and Tal, A., 1997, \u201cStrategies for Polyhedral Surface Decomposition: An Experimental Study,\u201d Computational Geometry: Theory and Applications, 7(4-5), pp. 327\u2013342, 484.","key":"2019100521564059700_r14","DOI":"10.1016\/S0925-7721(96)00024-7"},{"doi-asserted-by":"crossref","unstructured":"Bandi, S., and Thalmann, D., 1995, \u201cAn Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animating Rigid Bodies,\u201d Proceedings of Eurographics \u201995, pp. 259\u2013270.","key":"2019100521564059700_r15","DOI":"10.1111\/1467-8659.1430259"},{"unstructured":"Bouma, W., and Vanecek, G., 1991, \u201cCollision Detection and Analysis in a Physical Based Simulation,\u201d Euro-graphics Workshop on Animation and Simulation, pp. 191\u2013203.","key":"2019100521564059700_r16"},{"unstructured":"Pobil, A. P. D., Serna, M. A., and Llovet, J., 1992, \u201cA New Representation for Collision Avoidance and Detection,\u201d Proceedings of IEEE International Conference on Robotics and Automation, volume 1, pp. 246\u2013251.","key":"2019100521564059700_r17"},{"doi-asserted-by":"crossref","unstructured":"Dobkin, D., Kirkpatrick, D., 1990, \u201cDetermining the Separation of Preprocessed Polyhedra\u2014A Unified Approach,\u201d Lecture Notes in Computer Science, volume 443, pp. 400\u2013413.","key":"2019100521564059700_r18","DOI":"10.1007\/BFb0032047"},{"doi-asserted-by":"crossref","unstructured":"Gottschalk, S., Lin, M. C., and Manocha, D., 1996, \u201cOBB-Tree: A Hierarchical Structure for Rapid Interference Detection,\u201d Proceedings of ACM Siggraph.","key":"2019100521564059700_r19","DOI":"10.1145\/237170.237244"},{"doi-asserted-by":"crossref","unstructured":"Hamada, K., and Hori, Y., 1996, \u201cOctree-Based Approach to Real-time Collision-free Path Planning for Robot Manipulator,\u201d ACM96-MIE, pp. 705\u2013710.","key":"2019100521564059700_r20","DOI":"10.1109\/AMC.1996.509334"},{"doi-asserted-by":"crossref","unstructured":"Hubbard, P., 1993, \u201cInteractive Collision Detection,\u201d Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality, pp. 24\u201331.","key":"2019100521564059700_r21","DOI":"10.1109\/VRAIS.1993.378267"},{"doi-asserted-by":"crossref","unstructured":"Klosowski, J., Held, M., Mitchell, J., Sowizral, H., and Zikan, K., 1998, \u201cEfficient Collision Detection Using Bounding Volume Hierarchies of K-DOPS,\u201d IEEE Trans. Vis. Comput. Graph., 4(1), pp. 21\u201336.","key":"2019100521564059700_r22","DOI":"10.1109\/2945.675649"},{"unstructured":"Martinez, B., DelPobil, A. P., and Perez, M., 1998, \u201cVery Fast Collision Detection for Practical Motion Planning. Part i: The Spatial Representation,\u201d In Proceedings of IEEE International Conference on Robotics and Automation, pp. 624\u2013629.","key":"2019100521564059700_r23"},{"doi-asserted-by":"crossref","unstructured":"Palmer, I. J., and Grimsdale, R. L., 1995, \u201cCollision Detection for Animation Using Sphere-trees,\u201d Computer Graphics Forum, 14(2), pp. 105\u2013116.","key":"2019100521564059700_r24","DOI":"10.1111\/1467-8659.1420105"},{"doi-asserted-by":"crossref","unstructured":"Bobrow, J. E. , 1983, \u201cA Direct Optimization Approach for Obtaining the Distance Between Convex Polyhedra,\u201d Int. J. Robot. Res., 8(3), pp. 65\u201376.","key":"2019100521564059700_r25","DOI":"10.1177\/027836498900800304"},{"doi-asserted-by":"crossref","unstructured":"Cameron, S. A., and Culley, R. K., 1986, \u201cDetermining the Minimum Translational Distance Between Two Convex Polyhedra,\u201d Proceedings of IEEE International Conference on Robotics and Automation, pp. 591\u2013596.","key":"2019100521564059700_r26","DOI":"10.1109\/ROBOT.1986.1087645"},{"doi-asserted-by":"crossref","unstructured":"Gilbert, E. G., and Foo, C. P., 1990, \u201cComputing the Distance Between General Convex Objects in Three-Dimensional Space,\u201d IEEE Trans. Rob. Autom., 6(1), pp. 53\u201361.","key":"2019100521564059700_r27","DOI":"10.1109\/70.88117"},{"unstructured":"Quinlan, S., 1994, \u201cEfficient Distance Computation Between Non-convex Objects,\u201d Proceedings of IEEE International Conference on Robotics and Automation, volume 4, pp. 3324\u20133329.","key":"2019100521564059700_r28"},{"doi-asserted-by":"crossref","unstructured":"Cameron, S. A. , 1997, \u201cA Comparison of Two Fast Algorithms for Computing the Distance Between Convex Polyhedra,\u201d IEEE Trans. Rob. Autom., 13(6), pp. 915\u2013920.","key":"2019100521564059700_r29","DOI":"10.1109\/70.650170"},{"doi-asserted-by":"crossref","unstructured":"Cameron, S. A., 1997, \u201cEnhancing GJK: Computing Minimum and Penetration Distances Between Convex Polyhedra,\u201d Proceedings of IEEE International Conference on Robotics and Automation, pp. 3112\u20133117.","key":"2019100521564059700_r30","DOI":"10.1109\/ROBOT.1997.606761"},{"doi-asserted-by":"crossref","unstructured":"Bergen, G. V. D. , 1999, \u201cA Fast and Robust GJK Implementation for Collision Detection of Convex Objects,\u201d Journal of Graphics, 4(2), pp. 7\u201325.","key":"2019100521564059700_r31","DOI":"10.1080\/10867651.1999.10487502"},{"doi-asserted-by":"crossref","unstructured":"Gilbert, E. G., Johnson, D. W., and Keerthi, S., 1988, \u201cA Fast Procedure for Computing the Distance Between Complex Objects in Three Dimensional Space,\u201d IEEE Trans. Rob. Autom., 4(2), pp. 193\u2013203.","key":"2019100521564059700_r32","DOI":"10.1109\/56.2083"},{"doi-asserted-by":"crossref","unstructured":"Canny, J. F. , 1986, \u201cCollision Detection for Moving Polyhedra,\u201d IEEE Trans. Pattern Anal. Mach. Intell., 8(2), pp. 200\u2013209.","key":"2019100521564059700_r33","DOI":"10.1109\/TPAMI.1986.4767773"},{"doi-asserted-by":"crossref","unstructured":"Cohen, J. D., Lin, M. C., Manocha, D., and Ponamgi, M. K., 1995, \u201cI-collide: An Interactive and Exact Collision Detection System for Large-scale Environments,\u201d Proceedings of ACM International 3D Graphics Conference, volume 1, pp. 189\u2013196.","key":"2019100521564059700_r34","DOI":"10.1145\/199404.199437"},{"doi-asserted-by":"crossref","unstructured":"Culley, R. K., Kempf, K. G., 1986, \u201cA Collision Detection Algorithm Based on Velocity and Distance Bounds,\u201d IEEE International Conference on Robotics and Automation, pp. 1064\u20131069.","key":"2019100521564059700_r35","DOI":"10.1109\/ROBOT.1986.1087575"},{"doi-asserted-by":"crossref","unstructured":"Hudson, T. C., Lin, M. C., Cohen, J. D., Gottschalk, S., and Manocha, D., 1997, \u201cV-collide: Accelerated Collision Detection for VRML,\u201d Proceedings of VRML.","key":"2019100521564059700_r36","DOI":"10.1145\/253437.253472"},{"doi-asserted-by":"crossref","unstructured":"Cameron, S. A., 1985, \u201cA Study of the Clash Detection Problem in Robotics,\u201d Proceedings of IEEE International Conference on Robotics and Automation, pp. 488\u2013493.","key":"2019100521564059700_r37","DOI":"10.1109\/ROBOT.1985.1087245"},{"doi-asserted-by":"crossref","unstructured":"Hu, Z., and Ling, Z., 1994, \u201cGenerating Swept Solumes with Instantaneous Screw Axes,\u201d Proceedings of 94 ASME Design Technical Conference, Part 1, pp. 7\u201314.","key":"2019100521564059700_r38","DOI":"10.1115\/DETC1994-0172"},{"doi-asserted-by":"crossref","unstructured":"Keiffe, J., and Litvin, L., 1991, \u201cSwept Volume Determination and Interference of Moving 3-D Solids,\u201d ASME J. Mech. Des., 113(4), pp. 456\u2013463.","key":"2019100521564059700_r39","DOI":"10.1115\/1.2912805"},{"doi-asserted-by":"crossref","unstructured":"Sambandan, K., and Wang, K. K., 1989, \u201cFive-axis Swept Volumes for Graphic NC Simulation and Verification,\u201d ASME Design Automation Conference DE\u2013Vol. 19(1), pp. 143\u2013150.","key":"2019100521564059700_r40","DOI":"10.1115\/DETC1989-0030"},{"doi-asserted-by":"crossref","unstructured":"Wang, W. P. K., and Wang, K., 1986, \u201cGeometric Modeling for Swept Volume of Moving Solids,\u201d IEEE Comput. Graphics Appl., 6(12), pp. 8\u201317.","key":"2019100521564059700_r41","DOI":"10.1109\/MCG.1986.276586"},{"doi-asserted-by":"crossref","unstructured":"Cameron, S. A. , 1990, \u201cCollision Detection by Four-dimensional Intersection Testing,\u201d IEEE J. Rob. Autom., 6(3), pp. 291\u2013302.","key":"2019100521564059700_r42","DOI":"10.1109\/70.56661"},{"unstructured":"Canny, J., 1987, The Complexity of Robot Motion Planning. MIT Press, Cambridge, MA.","key":"2019100521564059700_r43"},{"doi-asserted-by":"crossref","unstructured":"Schomer, E., and Thiel, C., 1995, \u201cEfficient Collision Detection for Moving Polyhedra,\u201d Proceedings of the Eleventh Annual Symposium on Computational Geometry, pp. 51\u201360.","key":"2019100521564059700_r44","DOI":"10.1145\/220279.220285"},{"doi-asserted-by":"crossref","unstructured":"Jimenez, P., and Torras, C., 1995, \u201cCollision Detection: A Geometric Approach,\u201d Modelling and Planning for Sensor Based Intelligent Robot Systems, pp. 68\u201385. World Scientific Pub. Co.","key":"2019100521564059700_r45","DOI":"10.1142\/9789812797773_0005"},{"doi-asserted-by":"crossref","unstructured":"Redon, S., Kheddar, A., and Coquillart, S., 2000, \u201cAn Algebraic Solution to the Problem of Collision Detection for Rigid Polyhedral Objects,\u201d Proceedings of IEEE International Conference on Robotics and Automation, pp. 3733\u20133738.","key":"2019100521564059700_r46","DOI":"10.1109\/ROBOT.2000.845313"},{"unstructured":"Redon, S., Kheddar, A., and Coquillart, S., 2001, \u201cCONTACT: Arbitrary In-between Motions for Continuous Collision Detection,\u201d Proceedings of IEEE ROMAN.","key":"2019100521564059700_r47"},{"unstructured":"Redon, S., Private Communication 2003.","key":"2019100521564059700_r48"},{"doi-asserted-by":"crossref","unstructured":"Redon, S., Kheddar, A., and Coquillart, S. 2002, \u201cFast Continuous Collision Detection between Rigid Bodies,\u201d Proceedings of Eurographics.","key":"2019100521564059700_r49","DOI":"10.1111\/1467-8659.t01-1-00587"},{"doi-asserted-by":"crossref","unstructured":"Ohwovoriole, M., and Roth, B., 1981, \u201cAn Extension of Screw Theory,\u201d ASME J. Mech. Des., 103(4), pp. 725\u2013735.","key":"2019100521564059700_r50","DOI":"10.1115\/1.3254979"},{"doi-asserted-by":"crossref","unstructured":"Zefran, M., and Kumar, V., 1998, \u201cInterpolation Schemes for Rigid Body Motions,\u201d Computer-Aided Design 30(3), pp. 179\u2013189.","key":"2019100521564059700_r51","DOI":"10.1016\/S0010-4485(97)00060-2"},{"doi-asserted-by":"crossref","unstructured":"Rossignac, J. R., and Kim, J. J., 2001, \u201cComputing and Visualizing Pose-Interpolating 3D Motions,\u201d Computer Aided Design, 33(4), pp. 279\u2013291.","key":"2019100521564059700_r52","DOI":"10.1016\/S0010-4485(00)00086-5"},{"doi-asserted-by":"crossref","unstructured":"Hubbard, P. M. , 1996, \u201cApproximating Polyhedra with Spheres for Time-critical Collision Detection,\u201d ACM Trans. Graphics, 15(3), pp. 179\u2013210.","key":"2019100521564059700_r53","DOI":"10.1145\/231731.231732"},{"unstructured":"Bottema, O., and Roth, B., 1979, Theoretical Kinematics. North-Holland Publishing Company, Amsterdam, pp. 56\u201362, New York, Oxford.","key":"2019100521564059700_r54"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/3\/4\/295\/5525553\/295_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/3\/4\/295\/5525553\/295_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T18:44:19Z","timestamp":1734201859000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/3\/4\/295\/445318\/Collision-Prediction"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12,1]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,12,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.1632526","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2003,12,1]]}}}