{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:50:42Z","timestamp":1753879842522,"version":"3.41.2"},"reference-count":25,"publisher":"ASME International","issue":"1","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,3,1]]},"abstract":"<jats:p>This paper presents an algorithm for exact contact prediction between moving objects bounded by curved surfaces. The algorithm uses hierarchies of oriented bounding boxes (HOBBs) and local numerical methods for finding contact. Objects need not be convex and are described using the B-rep scheme. The bounding faces are represented by nonuniform rational B-splines (NURBS). The collision time is sought in short time intervals during the motion, during which time is one of the problem variables. HOBBs are based on curvature regions of the surfaces. This criterion ensures that local numerical methods will converge to the contact points if they exist. The patches enclosed in overlapping leaf nodes are tested for contact by solving a system of nonlinear equations, based on the type of collision expected. The types of collision studied are cusp\u2013cusp, cusp\u2013ridge, cusp\u2013face, ridge\u2013ridge, ridge\u2013face, and face\u2013face collisions. The current algorithm is implemented and compared to an efficient polyhedral collision package, and results appear promising.<\/jats:p>","DOI":"10.1115\/1.4005453","type":"journal-article","created":{"date-parts":[[2011,12,21]],"date-time":"2011-12-21T23:05:01Z","timestamp":1324508701000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":1,"title":["Contact Prediction Between Moving Objects Bounded by Curved Surfaces"],"prefix":"10.1115","volume":"12","author":[{"given":"Abdulmohsen","family":"Al Bedah","sequence":"first","affiliation":[{"name":"King Saud University, Ridya, Saudi Arabia e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John J.","family":"Uicker","sequence":"additional","affiliation":[{"name":"University of Wisconsin, Madison, WI 53706 e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2011,12,21]]},"reference":[{"key":"2019100411403610800_c1","doi-asserted-by":"crossref","unstructured":"Rossignac, J. R., and Requicha, A. A. G., 1999, \u201cSolid Modeling,\u201d Wiley Encyclopedia of Electrical and Electronics Engineering.","DOI":"10.1002\/047134608X.W7526"},{"key":"2019100411403610800_c2","doi-asserted-by":"crossref","unstructured":"Snyder, J. M. , 1995, \u201cAn Interactive Tool for Placing Curved Surfaces Without Interpenetration,\u201d Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, pp. 209\u2013218.","DOI":"10.1145\/218380.218444"},{"issue":"2","key":"2019100411403610800_c3","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. Graphics"},{"key":"2019100411403610800_c4","doi-asserted-by":"crossref","unstructured":"Schomer, E., Reichel, J., and Warken, T., 2002, \u201cEfficient Collision Detection for Curved Solid Objects,\u201d Proceedings 7th ACM Symposium on Solid Modeling and Applications, SM\u201902, June 17\u201321, pp. 321\u2013328.","DOI":"10.1145\/566313.566328"},{"key":"2019100411403610800_c5","unstructured":"Lennerz, C., and Schomer, E., 2002, \u201cEfficient Distance Computation for Quadratic Curves and Surfaces,\u201d Proceedings of Geometric Modeling and Processing. Theory and Applications, GMP 2002, pp. 1\u201310."},{"key":"2019100411403610800_c6","doi-asserted-by":"crossref","unstructured":"Choi, Y.-K., Wang, W., and Kim, M.-S., 2003, \u201cExact Collision Detection of Two Moving Ellipsoids Under Rational Motions,\u201d 2003 IEEE International Conference on Robotics and Automation, September 14\u201319, vol. 1, pp. 349\u2013354.","DOI":"10.1109\/ROBOT.2003.1241620"},{"issue":"4","key":"2019100411403610800_c7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/97880.97881","article-title":"Curved Surfaces and Coherence for Nonpenetrating Rigid Body Simulation","volume":"24","author":"Baraff","journal-title":"Comput. Graphics"},{"key":"2019100411403610800_c8","doi-asserted-by":"crossref","unstructured":"Duff, T. , 1992, \u201cInterval Arithmetic and Recursive Subdivision for Implicit Functions and Constructive Solid Geometry,\u201d Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, pp. 131\u2013138.","DOI":"10.1145\/142920.134027"},{"issue":"4","key":"2019100411403610800_c9","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1145\/127719.122745","article-title":"Generalized Implicit Functions for Computer Graphics","volume":"25","author":"Sclaroff","journal-title":"Comput. Graphics"},{"key":"2019100411403610800_c10","doi-asserted-by":"crossref","unstructured":"Pentland, A., and Williams, J., 1989, \u201cGood Vibrations: Model Dynamics for Graphics and Animation,\u201d Proceedings of the 16th Annual Conference on Computer Graphics and Interactive Techniques, pp. 215\u2013222.","DOI":"10.1145\/74333.74355"},{"key":"2019100411403610800_c11","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 the 20th Annual Conference on Computer Graphics and Interactive Techniques, pp. 321\u2013334.","DOI":"10.1145\/166117.166158"},{"issue":"4","key":"2019100411403610800_c12","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/97880.97883","article-title":"Geometric Collisions for Time-Dependent Parametric Surfaces","volume":"27","author":"Von Herzen","journal-title":"Comput. Graphics"},{"key":"2019100411403610800_c13","doi-asserted-by":"crossref","unstructured":"Krishnan, S., Gopi, M., Lin, M., Manocha, D., and Pattekar, A., 1998, \u201crapid and Accurate Contact Determination Between Spline Models Using Shelltrees,\u201d Eurographics Proceeding, 98 vol. 17, no. 3.","DOI":"10.1111\/1467-8659.00278"},{"key":"2019100411403610800_c14","unstructured":"Krishnan, S., Pattekar, A., Lin, M., and Manocha, D., 1998, \u201cSpherical shell: A higher order bounding volume for fast proximity queries,\u201d Proceedings of the 1998 Workshop on the Algorithmic Foundations of Robotics, pp. 287\u2013296."},{"issue":"1\u20132","key":"2019100411403610800_c15","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1142\/S0218195997000089","article-title":"Efficient Contact Determination in Dynamic Environment","volume":"7","author":"Lin","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"2019100411403610800_c16","doi-asserted-by":"crossref","unstructured":"Lin, C. M., and Canny, J. F., 1991, \u201cA Fast Algorithm for Incremental Distance Calculation,\u201d Proceedings of the 1991 IEEE International Conference on Robotics and Automation, vol. 2, pp. 1008\u20131014.","DOI":"10.1109\/ROBOT.1991.131723"},{"key":"2019100411403610800_c17","doi-asserted-by":"crossref","unstructured":"Colin, T., and Stephen, C., 1998, \u201cComputing Distances Between Nurbs-Defined Convex Objects,\u201d Proceedings IEEE International Conference on Robotics and Automation, vol. 4, pp. 3685\u20133690.","DOI":"10.1109\/ROBOT.1998.681406"},{"issue":"2","key":"2019100411403610800_c18","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1109\/56.2083","article-title":"A Fast Procedure for Computing the Distance Between Complex Objects in Three-dimensional Space","volume":"4","author":"Gilbert","journal-title":"IEEE J. Rob. Autom."},{"issue":"1","key":"2019100411403610800_c19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/70.88117","article-title":"Computing the Distance Between General Convex Objects in Three-dimensional Space","volume":"6","author":"Gilbert","journal-title":"IEEE Trans. Rob. Autom."},{"key":"2019100411403610800_c20","unstructured":"Rozas Merino, O. , 1998, \u201cCollision Detection in Mechanical Analysis With a Solid Model Based on a Boundary Representation of Nurbs Surfaces,\u201d Ph.D. Dissertation, Universidad de Navarra, Spain, pp. 1\u2013389."},{"key":"2019100411403610800_c21","doi-asserted-by":"crossref","unstructured":"Johnson, D.E., and Cohen, E., 1998, \u201cA Framework for Efficient Minimum Distance Computations,\u201d Proceedings of 1998 IEEE International Conference on Robotics and Automation, vol. 4, pp. 78\u201384.","DOI":"10.1109\/ROBOT.1998.681403"},{"key":"2019100411403610800_c22","doi-asserted-by":"crossref","unstructured":"Page, F., and Guibault, F., 2003, \u201cCollision Detection Algorithm for Nurbs Surfaces in Interactive Applications,\u201d CCECE 2003 Canadian Conference on Electrical and Computer Engineering: Toward a Caring and Humane Technology, May 4\u20137, vol. 2, pp. 1417\u20131420.","DOI":"10.1109\/CCECE.2003.1226166"},{"volume-title":"\u201cMatrix Methods in the Design Analysis of MultiBody Systems,\u201d","author":"Uicker","key":"2019100411403610800_c23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139032339"},{"key":"2019100411403610800_c24","unstructured":"Deuflhard, P. , 2004, \u201cNewton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms,\u201d Springer Series in Computational Mathematics, vol. 35."},{"key":"2019100411403610800_c25","doi-asserted-by":"crossref","unstructured":"Klein, J., and Zachmann, G., 2005, \u201cThe Expected Running Time of Hierarchical Collision Detection,\u201d SIGGRAPH \u201905: ACM SIGGRAPH 2005 Posters, p. 117.","DOI":"10.1145\/1186954.1187087"}],"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.4005453\/5532311\/011003_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4005453\/5532311\/011003_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,16]],"date-time":"2025-03-16T10:14:29Z","timestamp":1742120069000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4005453\/455399\/Contact-Prediction-Between-Moving-Objects-Bounded"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,21]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4005453","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2011,12,21]]},"article-number":"011003"}}