“Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects”

  • ©Paul Vouga, Breannan Smith, Danny M. Kaufman, Rasmus Tamstorf, and Eitan Grinspun

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


ACM Digital Library Publication: