The Gilbert-Johnson-Keerthi (GJK) Algorithm - презентация, доклад, проект скачать

Нажмите для полного просмотра!

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №1

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №2

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №3

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №4

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №5

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №6

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №7

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №8

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №9

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №10

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №11

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №12

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №13

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №14

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №15

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №16

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №17

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №18

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №19

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №20

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №21

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №22

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №23

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №24

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №25

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №26

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №27

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №28

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №29

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №30

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №31

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №32

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №33

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №34

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №35

The Gilbert-Johnson-Keerthi (GJK) Algorithm, слайд №36

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему The Gilbert-Johnson-Keerthi (GJK) Algorithm. Доклад-сообщение содержит 36 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

The Gilbert-Johnson-Keerthi (GJK) Algorithm

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Terminology 1(3)

Слайд 6

Описание слайда:

Terminology 2(3)

Слайд 7

Описание слайда:

Terminology 3(3)

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

GJK example 1(10)

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

GJK example 3(10)

Слайд 12

Описание слайда:

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’)

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

GJK example 7(10)

Слайд 16

Описание слайда:

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’)

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

Closest point on triangle

Слайд 22

Описание слайда:

Closest point on triangle

Слайд 23

Описание слайда:

Closest point on triangle

Слайд 24

Описание слайда:

Closest point on triangle

Слайд 25

Описание слайда:

GJK for two objects

Слайд 26

Описание слайда:

Minkowski sum & difference

Слайд 27

Описание слайда:

Minkowski sum & difference

Слайд 28

Описание слайда:

The generalization

Слайд 29

Описание слайда:

GJK for moving objects

Слайд 30

Описание слайда:

Transform the problem…

Слайд 31

Описание слайда:

…into moving vs stationary

Слайд 32

Описание слайда:

Alt #1: Point duplication

Слайд 33

Описание слайда:

Alt #2: Support mapping

Слайд 34

Описание слайда:

Alt #2: Support mapping

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

References Ericson, Christer. Real-time collision detection. Morgan Kaufmann, 2005. 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.