“Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects”
Conference:
Type:
Title:
- Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects
Session/Category Title: Let's Get in Contact
Presenter(s)/Author(s):
Moderator(s):
Abstract:
This article presents a new version of the Gilbert-Johnson-Keerthi (GJK) algorithm that circumvents the shortcomings introduced by degenerate geometries. The original Johnson algorithm and Backup procedure are replaced by a distance subalgorithm that is faster and accurate to machine precision, thus guiding the GJK algorithm toward a shorter search path in less computing time. Numerical tests demonstrate that this effectively is a more robust procedure. In particular, when the objects are found in contact, the newly proposed subalgorithm runs from 15% to 30% times faster than the original one. The improved performance has a significant impact on various applications, such as real-time simulations and collision avoidance systems. Altogether, the main contributions made to the GJK algorithm are faster convergence rate and reduced computational time. These improvements may be easily added into existing implementations; furthermore, engineering applications that require solutions of distance queries to machine precision can now be tackled using the GJK algorithm.
References:
1. S. Cameron. 1997a. A comparison of two fast algorithms for computing the distance between convex polyhedra. IEEE Transactions on Robotics and Automation 13, 6 (Dec. 1997), 915–920.Google ScholarCross Ref
2. S. Cameron. 1997b. Enhancing GJK: Computing minimum and penetration distances between convex polyhedra. In Proceedings of the 1997 IEEE International Conference on Robotics and Automation, Vol. 4.Google ScholarCross Ref
3. S. A. Cameron and R. K. Culley. 1986. Determining the minimum translational distance between two convex polyhedra. In Proceedings of the IEEE International Conference on Robotics and Automation. 591–596.Google Scholar
4. K. Chung and W. Wang. 1996. Quick collision detection of polytopes in virtual environments. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology. 125–131. Google ScholarDigital Library
5. H. S. M. Coxeter. 1989. Introduction to Geometry. Wiley.Google Scholar
6. P. A. Cundall and O. D. L. Strack. 1979. A discrete numerical model for granular assemblies. Gotechnique 29, 1 (Jan. 1979), 47–65.Google ScholarCross Ref
7. A. Dax. 2006. The distance between two convex sets. Linear Algebra and Its Applications 416, 1 (2006), 184–213. cited By 15.Google ScholarCross Ref
8. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. 2008. Computational Geometry. Springer, Berlin. Google ScholarDigital Library
9. A. Dietrich, T. Wimbock, A. Albu-Schaffer, and G. Hirzinger. 2012. Reactive whole-body control: Dynamic mobile manipulation using a large number of actuated degrees of freedom. IEEE Robotics 8 Automation Magazine 19, 2 (June 2012), 20–33.Google Scholar
10. H. Edelsbrunner and E. P. Mucke. 1990. Simulation of simplicity. A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics 9, 1 (1990), 66–104. cited By 261. Google ScholarDigital Library
11. C. Ericson. 2004. Real-Time Collision Detection. Morgan Kaufmann. Google ScholarDigital Library
12. J. Gallier. 2011. Geometric Methods and Applications. Springer, New York. Google ScholarDigital Library
13. E. G. Gilbert, D. W. Johnson, and S. S. Keerthi. 1988. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Journal of Robotics and Automation 4, 2 (1988), 193–203.Google ScholarCross Ref
14. R. A. Gingold and J. J. Monaghan. 1977. Smoothed particle hydrodynamics-theory and application to non-spherical stars. Monthly Notices of the Royal Astronomical Society 181 (1977), 375–389. http://adsabs.harvard.edu/full/1977MNRAS.181.375GGoogle ScholarCross Ref
15. A. Haji-Akbari, E. R. Chen, M.l Engel, and S. C. Glotzer. 2013. Packing and self-assembly of truncated triangular bipyramids. Physical Review E 88, 1 (July 2013), 012127.Google ScholarCross Ref
16. M. Held. 1998. ERIT—A collection of efficient and reliable intersection tests. Journal of Graphics Tools 2 (1998), 25–44. Google ScholarDigital Library
17. T. J. R. Hughes, J. A. Cottrell, and Y. Bazilevs. 2005. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement. Computer Methods in Applied Mechanics and Engineering 194, 3941 (Oct. 2005), 4135–4195.Google ScholarCross Ref
18. P. Jimnez, F. Thomas, and C. Torras. 2001. 3D collision detection: A survey. Computers 8 Graphics 25, 2 (April 2001), 269–285.Google Scholar
19. D. W. Johnson. 1987. The Optimization of Robot Motion in the Presence of Obstacles. Ph.D. dissertation. University of Michigan, Ann Arbor, MI. AAI8720285. Google ScholarDigital Library
20. S. D. Laycock and A. M. Day. 2007. A survey of haptic rendering techniques. Computer Graphics Forum 26, 1 (March 2007), 50–65.Google ScholarCross Ref
21. M. C. Lin and J. F. Canny. 1991. A fast algorithm for incremental distance calculation. In Proceedings of the 1991 IEEE International Conference on Robotics and Automation, Vol. 2.1008–1014.Google Scholar
22. A. Liu, F. Tendick, K. Cleary, and C. Kaufmann. 2003. A survey of surgical simulation: Applications, technology, and education. Presence: Teleoperators and Virtual Environments 12, 6 (Dec. 2003), 599–614. Google ScholarDigital Library
23. T. Lozano-Perez. 1983. Spatial planning: A configuration space approach. IEEE Transactions on Computers 32, 2 (1983), 108–120. Google ScholarDigital Library
24. J. A. Millan, D. Ortiz, G. van Anders, and S. C. Glotzer. 2014. Self-assembly of Archimedean tilings with enthalpically and entropically patchy polygons. ACS Nano 8, 3 (March 2014), 2918–2928.Google ScholarCross Ref
25. B. Mirtich. 1998. V-Clip: Fast and robust polyhedral collision detection. ACM Transactions on Graphics 17, 3 (July 1998), 177–208. Google ScholarDigital Library
26. N. Movshovitz, E. Asphaug, and D. Korycansky. 2012. Numerical modeling of the disruption of comet D/1993 F2 shoemaker-levy 9 representing the progenitor by a gravitationally bound assemblage of randomly shaped polyhedra. The Astrophysical Journal 759, 2 (2012).Google ScholarCross Ref
27. K. Museth, D. E. Breen, R. T. Whitaker, S. Mauch, and D. Johnson. 2005. Algorithms for interactive editing of level set models. Computer Graphics Forum 24, 4 (Dec. 2005), 821–841.Google ScholarCross Ref
28. B. Nye, A. V. Kulchitsky, and J. B. Johnson. 2014. Intersecting dilated convex polyhedra method for modeling complex particles in discrete element method. International Journal for Numerical and Analytical Methods in Geomechanics 38, 9 (June 2014), 978–990.Google ScholarCross Ref
29. C.-J. Ong and E. G. Gilbert. 2001. Fast versions of the Gilbert-Johnson-Keerthi distance algorithm: Additional results and comparisons. IEEE Transactions on Robotics and Automation 17, 4 (Aug. 2001), 531–539.Google Scholar
30. K. Ozaki, T. Ogita, and S. Oishi. 2012. A robust algorithm for geometric predicate by error-free determinant transformation. Information and Computation 216 (2012), 3–13. Special Issue: 8th Conference on Real Numbers and Computers. Google ScholarDigital Library
31. J. N. Reddy. 2006. An Introduction to the Finite Element Method. McGraw-Hill Higher Education, New York, NY.Google Scholar
32. S. Redon, A. Kheddar, and S. Coquillart. 2002. Fast continuous collision detection between rigid bodies. Computer Graphics Forum 21, 3 (Sept. 2002), 279–287.Google ScholarCross Ref
33. L. Seiler, D. Carmean, E. Sprangle, T. Forsyth, M. Abrash, P. Dubey, S. Junkins, A. Lake, J. Sugerman, R. Cavin, R. Espasa, E. Grochowski, T. Juan, and P. Hanrahan. 2008. Larrabee: A many-core x86 architecture for visual computing. ACM Transactions on Graphics 27, 3, Article 18 (Aug. 2008), 15 pages. Google ScholarDigital Library
34. J. R. Shewchuk. 1996. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete 8 Computational Geometry 18 (1996), 305–363.Google Scholar
35. A. Tasora and M. Anitescu. 2011. A matrix-free cone complementarity approach for solving large-scale, nonsmooth, rigid body dynamics. Computer Methods in Applied Mechanics and Engineering 200, 5–8 (Jan. 2011), 439–453.Google ScholarCross Ref
36. V. Tereshchenko, S. Chevokin, and A. Fisunenko. 2013. Algorithm for finding the domain intersection of a set of polytopes. Procedia Computer Science 18 (2013), 459–464.Google ScholarCross Ref
37. C. Turnbull and S. Cameron. 1998. Computing distances between NURBS-defined convex objects. In Proceedings of the 1998 IEEE International Conference on Robotics and Automation, Vol. 4. 3685–3690.Google Scholar
38. G. van den Bergen. 1999. A fast and robust GJK implementation for collision detection of convex objects. Journal of Graphics Tools 4, 2 (1999), 7–25. Google ScholarDigital Library
39. G. van den Bergen. 2003. Collision Detection in Interactive 3D Environments. Morgan Kaufmann, San Francisco. Google ScholarDigital Library
40. A. Wachs, L. Girolami, G. Vinay, and G. Ferrer. 2012. Grains3D, a flexible DEM approach for particles of arbitrary convex shape Part I: Numerical model and validations. Powder Technology 224 (July 2012), 374–389.Google Scholar
41. R. Webster. 1995. Convexity. Oxford University Press, Oxford, England.Google Scholar
42. Y. Zheng, C. M. Chew, and A. H. Adiwahono. 2011. A GJK-based approach to contact force feasibility and distribution for multi-contact robots. Robotics and Autonomous Systems 59, 34 (March 2011), 194–207. Google ScholarDigital Library
43. Y. Zheng and K. Yamane. 2013. Ray-shooting algorithms for robotics. IEEE Transactions on Automation Science and Engineering 10, 4 (Oct. 2013), 862–874.Google ScholarCross Ref
