{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:57:17Z","timestamp":1777715837436,"version":"3.51.4"},"reference-count":35,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2001,6]]},"abstract":"<jats:p>Contact determination in terms of edge-face intersection tests permits handling nonconvex polyhedra directly, without decomposing them into convex entities, which saves the decomposition time and avoids having to deal with fictitious features but requires checking all possible pairings. However, by considering only translations and departing from a noninterfering situation, the number of pairings to be checked decreases drastically. The set of critical pairings can be determined efficiently using the spherical face orientation graph (SFOG), a representation developed by the authors. An algorithm to exploit the SFOG in convex settings provides controlled evidence of the pruning potential of this approach: the number of critical pairings grows linearly with the complexity of the polyhedra, instead of quadratically as the total number of pairings does. Experiments with a similar algorithm on nonconvex settings confirm the expected potential of the approach: for workpieces with many concavities moving in close proximity, the contact determination procedure presented in this paper performs one order of magnitude faster than RAPID, at the expense of a much higher preprocessing time.<\/jats:p>","DOI":"10.1177\/02783640122067499","type":"journal-article","created":{"date-parts":[[2003,7,19]],"date-time":"2003-07-19T01:53:44Z","timestamp":1058579624000},"page":"466-483","source":"Crossref","is-referenced-by-count":2,"title":["An Orientation-Based Pruning Tool to Speed Up Contact Determination between                 Translating Polyhedral Models"],"prefix":"10.1177","volume":"20","author":[{"given":"P.","family":"Jim\u00e9nez","sequence":"first","affiliation":[{"name":"Institut de Rob\u00f2tica i Inform\u00e0tica Industrial,                         Llorens i Artigas 4-6, E-08028 Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Torras","sequence":"additional","affiliation":[{"name":"Institut de Rob\u00f2tica i Inform\u00e0tica Industrial,                         Llorens i Artigas 4-6, E-08028 Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187809"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0219020"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"Basch, J., Guibas, L. J., and Ramkumar, G. D. 1996. Reporting red-blue intersections between connected sets of line segments . 4th European Symposium on Algorithms, pp. 302\u2013319 .","DOI":"10.1007\/3-540-61680-2_64"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/359046.359048"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/38.79455"},{"key":"atypb6","unstructured":"Canny, J. 1987. The Complexity of Robot Motion Planning. Cambridge, MA: MIT Press ."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"Cohen, J. D., Lin, M. C., Manocha, D., and Ponamgi, M. K. 1995. I-collide: An interactive and exact collision detection system for large-scale environments . Proceedings of the ACM International 3D Graphics Conference, Vol. 1, pp. 189\u2013196 . Available: http:\/\/www.cs.unc.edu\/<XEN=&tilde;xgeom\/LCOLLIDE.html.","DOI":"10.1145\/199404.199437"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90069-5"},{"key":"atypb9","unstructured":"Garc\u00eda-Alonso et al. 1994."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/56.2083"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Gottschalk, S., Lin, M. C., and Manocha, D. 1996. Obb-tree: A hierarchical structure for rapid interference detection. Proceedings of ACM Siggraph\u201996. Available: http:\/\/www.cs.unc.edu\/geom\/OBB\/OBBT.html","DOI":"10.1145\/237170.237244"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Hamlin, G. J., Kelley, R. B., and Tornero, J. 1992. Efficient distance calculation using the spherically-extended polytope (s-tope) model . Proceedings of the IEEE Conference on Robotics and Automation, Vol. 3, Nice, France, pp. 2502\u20132507 .","DOI":"10.1109\/ROBOT.1992.220065"},{"key":"atypb13","unstructured":"Hilbert, D., and Cohn-Vossen, S. 1987. Geometry and the Imagination. New York: Chelsea ."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1984.13073"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Hubbard, P. M. 1993. Interactive collision detection . Proceedings of the IEEE Symposium on Research Frontiers in Virtual Reality, Vol. 1, pp. 24\u201331 .","DOI":"10.1109\/VRAIS.1993.378267"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/2945.466717"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Hudson, T. C., Lin, M. C., Cohen, J. D., Gottschalk, S., and Manocha, D. 1997. V-collide: Accelerated collision detection for vrml . Proceedings of VRML. Available: http:\/\/www.cs.unc.edu\/geom\/V_COLLIDE.html","DOI":"10.1145\/253437.253472"},{"key":"atypb18","unstructured":"Jim\u00e9nez, P. 1998. Static and dynamic interference detection between nonconvex polyhedra. Ph.D. thesis, Universitat Polit\u00e8cnica de Catalunya. Available: http:\/\/wwwiri.upc.es\/people\/jimenez\/phdthesis.html"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(00)00130-8"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Jim\u00e9nez, P., and Torras, C. 1996. Speeding up interface detection between polyhedra . Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 2, Minneapolis, MN, pp. 1485\u20131492 .","DOI":"10.1109\/ROBOT.1996.506915"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"Jim\u00e9nez, P., and Torras, C. 1999. Benefits of applicability constraints in decomposition-free interference detection between nonconvex polyhedral models . Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 3, Detroit, MI, pp. 1856\u20131862 .","DOI":"10.1109\/ROBOT.1999.770379"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00063-1"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"Johnson, D., and Cohen, E. 2001. Spatialized normal cone hierarchies . Proceedings of the 2001 ACM Symposium on Interactive 3D Graphics, Vol. 2, Research Triangle Park, NC, pp. 129\u2013134 .","DOI":"10.1145\/364338.364380"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/2945.675649"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"Lin, M. C., and Canny, J. F. 1991. A fast algorithm for incremental distance calculation . Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 2, Sacramento, CA, pp. 1008\u20131014 .","DOI":"10.1109\/ROBOT.1991.131723"},{"key":"atypb26","unstructured":"Lin, M. C., and Gottschalk, S. 1998. Collision detection between geometric models: A survey . IMA Conference on Mathematics of Surfaces, Vol. 1, San Diego, CA, pp. 602\u2013608 ."},{"key":"atypb27","unstructured":"Mart\u00ednez et al. 1998."},{"key":"atypb28","unstructured":"Pearl, J. 1984. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading, MA: Addison-Wesley ."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/2945.582346"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"Preparata, F. F., and Shamos, M. I. 1985. Computational Geometry: An Introduction. Texts and Monographs in Computer Science. New York: Springer-Verlag .","DOI":"10.1007\/978-1-4612-1098-6_1"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37421"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1109\/70.134276"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"Thomas, F., and Torras, C. 1994. Interference detection between non-convex polyhedra revisited with a practical aim . Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 1, San Diego, CA, pp. 587\u2013594 .","DOI":"10.1109\/ROBOT.1994.351236"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"van der Bergen, G. 1997. Efficient collision detection of complex deformable models using aabb trees . Journal of Graphic Tools 2(4): 1\u201313 .","DOI":"10.1080\/10867651.1997.10487480"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1002\/vis.4340050105"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640122067499","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640122067499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:36Z","timestamp":1777457796000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783640122067499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,6]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,6]]}},"alternative-id":["10.1177\/02783640122067499"],"URL":"https:\/\/doi.org\/10.1177\/02783640122067499","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,6]]}}}