🗊Презентация The Gilbert-Johnson-Keerthi (GJK) Algorithm

The Gilbert-Johnson-Keerthi (GJK) Algorithm

Talk outline What is the GJK algorithm Terminology “Simplified” version of the algorithm One object is a point at the origin Example illustrating algorithm The distance subalgorithm GJK for two objects One no longer necessarily a point at the origin GJK for moving objects

GJK solves proximity queries Given two convex polyhedra Computes distance d Can also return closest pair of points PA, PB

GJK solves proximity queries Generalized for arbitrary convex objects As long as they can be described in terms of a support mapping function

Terminology 1(3)

Terminology 2(3)

Terminology 3(3)

The GJK algorithm Initialize the simplex set Q with up to d+1 points from C (in d dimensions) Compute point P of minimum norm in CH(Q) If P is the origin, exit; return 0 Reduce Q to the smallest subset Q’ of Q, such that P in CH(Q’) Let V=SC(–P) be a supporting point in direction –P If V no more extreme in direction –P than P itself, exit; return ||P|| Add V to Q. Go to step 2

GJK example 1(10)

GJK example 2(10) Initialize the simplex set Q with up to d+1 points from C (in d dimensions)

GJK example 3(10)

GJK example 4(10) If P is the origin, exit; return 0 Reduce Q to the smallest subset Q’ of Q, such that P in CH(Q’)

GJK example 5(10) Let V=SC(–P) be a supporting point in direction –P

GJK example 6(10) If V no more extreme in direction –P than P itself, exit; return ||P|| Add V to Q. Go to step 2

GJK example 7(10)

GJK example 8(10) If P is the origin, exit; return 0 Reduce Q to the smallest subset Q’ of Q, such that P in CH(Q’)

GJK example 9(10) Let V=SC(–P) be a supporting point in direction –P

GJK example 10(10) If V no more extreme in direction –P than P itself, exit; return ||P||

Distance subalgorithm 1(2) Approach #1: Solve algebraically Used in original GJK paper Johnson’s distance subalgorithm Searches all simplex subsets Solves system of linear equations for each subset Recursive formulation From era when math operations were expensive Robustness problems See e.g. Gino van den Bergen’s book

Distance subalgorithm 2(2) Approach #2: Solve geometrically Mathematically equivalent But more intuitive Therefore easier to make robust Use straightforward primitives: ClosestPointOnEdgeToPoint() ClosestPointOnTriangleToPoint() ClosestPointOnTetrahedronToPoint() Second function outlined here The approach generalizes

Closest point on triangle

Closest point on triangle

Closest point on triangle

Closest point on triangle

GJK for two objects

Minkowski sum & difference

Minkowski sum & difference

The generalization

GJK for moving objects

Transform the problem…

…into moving vs stationary

Alt #1: Point duplication

Alt #2: Support mapping

Alt #2: Support mapping

GJK for moving objects Presented solution Gives only Boolean interference detection result Interval halving over v gives time of collision Using simplices from previous iteration to start next iteration speeds up processing drastically Overall, always starting with the simplices from the previous iteration makes GJK… Incremental Very fast

References Ericson, Christer. Real-time collision detection. Morgan Kaufmann, 2005. http://www.realtimecollisiondetection.net/ van den Bergen, Gino. Collision detection in interactive 3D environments. Morgan Kaufmann, 2003. Gilbert, Elmer. Daniel Johnson, S. Sathiya Keerthi. “A fast procedure for computing the distance between complex objects in three dimensional space.” IEEE Journal of Robotics and Automation, vol.4, no. 2, pp. 193-203, 1988. Gilbert, Elmer. Chek-Peng Foo. “Computing the Distance Between General Convex Objects in Three-Dimensional Space.” Proceedings IEEE International Conference on Robotics and Automation, pp. 53-61, 1990. Xavier Patrick. “Fast swept-volume distance for robust collision detection.” Proc of the 1997 IEEE International Conference on Robotics and Automation, April 1997, Albuquerque, New Mexico, USA. Ruspini, Diego. gilbert.c, a C version of the original Fortran implementation of the GJK algorithm. ftp://labrea.stanford.edu/cs/robotics/sean/distance/gilbert.c