Mattia Montanari
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
- 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 Scholar
Cross Ref
- 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
- 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
- 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
- H. S. M. Coxeter. 1989. Introduction to Geometry. Wiley.Google Scholar
- 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
- 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
- M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. 2008. Computational Geometry. Springer, Berlin. Google ScholarDigital Library
- 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
- 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
- C. Ericson. 2004. Real-Time Collision Detection. Morgan Kaufmann. Google ScholarDigital Library
- J. Gallier. 2011. Geometric Methods and Applications. Springer, New York. Google ScholarDigital Library
- 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
- 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
- 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
- M. Held. 1998. ERIT—A collection of efficient and reliable intersection tests. Journal of Graphics Tools 2 (1998), 25--44. Google ScholarDigital Library
- 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
- P. Jimnez, F. Thomas, and C. Torras. 2001. 3D collision detection: A survey. Computers 8 Graphics 25, 2 (April 2001), 269--285.Google Scholar
- 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
- 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
- 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
- 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
- T. Lozano-Perez. 1983. Spatial planning: A configuration space approach. IEEE Transactions on Computers 32, 2 (1983), 108--120. Google ScholarDigital Library
- 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
- B. Mirtich. 1998. V-Clip: Fast and robust polyhedral collision detection. ACM Transactions on Graphics 17, 3 (July 1998), 177--208. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- J. N. Reddy. 2006. An Introduction to the Finite Element Method. McGraw-Hill Higher Education, New York, NY.Google Scholar
- 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
- 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
- J. R. Shewchuk. 1996. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete 8 Computational Geometry 18 (1996), 305--363.Google Scholar
- 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
- 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
- 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
- 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
- G. van den Bergen. 2003. Collision Detection in Interactive 3D Environments. Morgan Kaufmann, San Francisco. Google ScholarDigital Library
- 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
- R. Webster. 1995. Convexity. Oxford University Press, Oxford, England.Google Scholar
- 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
- 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
Index Terms
- Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects
Recommendations
Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects
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 ...
An Algorithm for Computing the Minimum Distance between Two Convex Polyhedra in Three-Dimensional Space
KAM '08: Proceedings of the 2008 International Symposium on Knowledge Acquisition and ModelingEfficient and exact collision detection is very important to improving reality and enhancing immersion in virtual environment. A fast algorithm for computing the minimum distance between two convex polyhedra is presented. Any polyhedral objects can be ...
Exact and efficient construction of Minkowski sums of convex polyhedra with applications
We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R^3. Our implementation is complete in the sense that it does not assume general position. Namely, it can handle degenerate input, and it ...
Comments