5 / 18
Расчет областей пересечения поверхностей захватных устройств манипуляторов…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
101
Рис. 3.
Области потенциального взаимодействия ОМ с одним из звеньев ЗУМ
На рис. 3,
б
эти же ОПВ представлены отдельно. Синими точками обозна-
чены вершины ОМ, находящиеся внутри ОПВ, соответствующей OBB ОМ, ро-
зовыми — вершины звена ЗУМ, расположенные в ОПВ OBB звена ЗУ. Видно,
что число точек и полигонов, вершинами которых они являются, существенно
меньше общего числа вершин и полигонов моделей поверхностей ОМ и ЗУМ.
Очевидно, что пересечение поверхностей ОМ и ЗУМ может происходить толь-
ко внутри ОПВ. Причем для практики представляют интерес только те случаи,
когда в ОПВ находятся одновременно вершины многогранников и ОМ,
и ЗУМ.
Подход с использованием ОПВ увеличивает надежность определения факта
пересечения, поскольку уменьшается число случаев, когда имеет место пересе-
чение ОП, но пересечение между полигональными моделями отсутствует. Кро-
ме того, использование ОПВ позволяет модернизировать алгоритм широкой
фазы, а именно: расчеты в широкой фазе выполняются не только до момента
пересечения ОП ОМ и ЗУМ, но и после состоявшегося пересечения этих ОП.
Основанием для перехода к узкой фазе служит факт обнаружения в ОПВ
вершин многогранников поверхностей и ОМ, и ЗУМ.
Анализ существующих методов и алгоритмов узкой фазы.
В узкой фазе
определения пересечения поверхностей объектов с использованием их полиго-
нальных моделей чаще всего используются алгоритмы, базирующиеся на методе
Gilbert — Johnson — Keerthi (GJK) [5], которые определяют характеристики пе-
ресечения полигонов поверхностей путем анализа разности Минковского для
векторов, описывающих полигоны, и алгоритмы, опирающиеся на расчет вза-
имного расположения областей Вороного фрагментов многогранников: алго-
ритм Lin — Canny [6] и алгоритм V-Clip [7].
В работе [7] приводится сравнение быстродействия алгоритмов GJK,
Lin — Canny и V — Clip. Показано, что скорость определения пересечения объ-
ектов алгоритма V — Clip значительно больше скорости других алгоритмов.
Алгоритм V — Clip используется во многих физических движках — компью-
терных программах, моделирующих в виртуальной среде поведение объектов
реального мира. В качестве примера можно привести Bullet Physics Library [8] и