3 / 16
Моделирование взаимодействия мобильного робота и опорного основания…
Инженерный журнал: наука и инновации
# 12·2016 3
находят по касательной скорости
tan
v
, нормальной силе и коэффици-
енту трения, т. е.
K
;
( ,
);
( , )
tan
pnt
N
pnt
pnt
T
tan N
v v v F f r v
F f v F
= −
=
=
;
где
K
v
— скорость точки контакта.
Однако для адекватного разрешения контакта прежде всего необ-
ходимо определить факт пересечения геометрии грунта и транспорт-
ной машины. Для решения этой задачи наиболее подходит алгоритм
GJK (Gilbert–Johnson–Keerthi).
Алгоритм GJK (Gilbert–Johnson–Keerthi)
.
В конце 1980-х гг.
разработан алгоритм GJK, предназначенный для эффективного ана-
лиза пересечения многогранников и нахождения расстояния между
ними. С тех пор видоизмененные версии алгоритма применяются в
различных приложениях — от компьютерных игр до систем модели-
рования [5, 6]. В Интернете доступно множество описаний GJK и
примеров его реализации [7].
Приведем только основные положения алгоритма. Итак, для пары
выпуклых многогранников можно построить так называемое
конфи-
гурационное пространство препятствий
— CSO (Configure Space
Obstacle, по терминологии его разработчиков), представляющее со-
бой массив вершин. Координаты вершин CSO вычисляют как разность
координаты каждой вершины первого и каждой вершины второго мно-
гогранника. После чего можно утверждать, что выпуклые многогранни-
ки пересекутся только в том случае, когда составленная из внешних
вершин CSO фигура будет содержать начало координат (рис. 2).
Для многогранников на рис. 2, имеющих шесть и восемь вершин,
пространство CSO состоит из 48 вершин, поэтому в процессе работы
алгоритма полностью CSO нельзя вычислить. Вместо этого ищут
простейшую геометрическую фигуру — симплекс (в трехмерном
случае — тетраэдр
ABCD
на рис. 3), содержащую начало координат
(точка
О
). Обычно для построения тетраэдра используют так называ-
емую
вспомогательную функцию
(support function), которая находит
самую дальнюю вершину CSO в заданном направлении. С помощью
этой функции случайно выбранную в CSO точку последовательно
развивают до линии, треугольника, тетраэдра, всякий раз выбирая
направление на начало координат.
Если по итогам работы алгоритма GJK удается построить сим-
плекс, содержащий начало координат, то можно сделать вывод о пе-
ресечении многогранников. В противном случае, находят вектор рас-
стояния между ними — от ближайшего треугольника симплекса до
начала координат. В настоящей работе алгоритм GJK используется
только для определения факта пересечения, хотя часто его применя-
ют и для нахождения прочих параметров контакта [5].