| GJK, маленькое дополнение |
[Jun. 8th, 2017|07:18 am] |
я этого не написал, потому что казалось очевидно, но может и нет.
абсолютно все GJK-вариации, которые я тут представил, работают на одном и том же принципе: раздуваем один конвекс так, чтобы второй сдулся до точки. различаются они (алгоритмы) только условиями выхода, да условиями выбора следующего направления.
то есть, сначала редуцируем проблему до «один конвекс и точка» — её решить намного проще. отсюда же очевидно, почему это не работает для неконвексов: раздуть неконвекс в общем случае невозможно: иногда это получится, иногда нет (пойдут самопересечения), и не получится использовать симплекс (потому что любая отрезаная часть конвекса всегда валидный конвекс, что и позволяет нам рассматривать не весь раздутый полигон, а его части). и все проверки для неконвексов очень дорогие.
GJK-столкновение проверяет, находится ли сдутая точка (которая становится (0,0) в minkowski space) где-то внутри раздутого конвекса. соответственно, и направления выбираются такие, чтобы приближали нас к (0,0).
GJK-расстояние ищет минимальное расстояние от сдутой точки до раздутого конвекса. направления всё ещё идут к (0,0), потому что расстояние до него и есть нужное нам.
а GJK-рэйкастер просто кастит луч по раздутому конвексу. тут направление выбирается к началу луча.
если вы нарисуете процесс (извините, мне лень), то увидите глазами, и всё станет намного понятней. также станет понятно, по какому принципу из симплекса выкидываются старые точки.
(я бы тут ещё мог сказать про то, что на самом деле при выборе направления мы оперируем такой штукой, как voronoi regions, но кто это понял — тому оно не надо. а кто не понял — тому и тем более без нужды, потому что никакой полезной нагрузки это знание в данном случае не несёт.)
резюмируя: GJK работает очень просто (если описывать совсем без деталей).
1. выбираем рандомную точку на раздутом конвексе.
2. просим три ближайших точки в текущем направлении поиска.
3. смотрим, что там у нас с условиями — на основании полученого треугольника.
4. выбираем новое направление.
5. goto 2. |
|
|
