Презентация 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