7 / 18
Расчет областей пересечения поверхностей захватных устройств манипуляторов…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
103
верхность тела
B.
Проецирование осуществляется в направлении вектора
v
(см.
рис. 5). Тогда, если вектор
,
i i
p p
связывающий соответствующие элементы из мно-
жеств
P
и
,
P
сонаправлен с вектором
v
, то вершина
i
p
тела
A
находится в контак-
те с телом
B
, т. е. является граничной точкой области пересечения. Глубина про-
никновения для нее в направлении вектора
v
равна модулю вектора
,
i i
p p
а вектор,
вдоль которого отсчитывается глубина проникновения, сонаправлен с
.
i i
p p
Для нахождения проекции
,
i
p
соответствующей вершине
i
p
, предлагается
из
i
p
провести прямую, параллельную вектору
v
, и определить из множества
полигонов тела
B
тот, который эта прямая пересекает. Координаты точки пере-
сечения будут соответствовать проекции
.
i
p
При решении задачи поиска полигона, на котором будет располагаться проек-
ция
,
i
p
примем во внимание тот факт, что одна вершина (обозначим ее
j
q
) из
множества вершин полигональной модели
1
, ...,
m
Q q q
тела
B
обладает таким
свойством, что угол между векторами
i j
p q
и
v
будет наименьшим среди углов меж-
ду
i
p
и любым другим вектором
.
k
q Q
Данное свойство вытекает из того, что чем
меньше угол
,
i i j
p p q
тем меньше расстояние между
i
p
и
.
j
q
Тогда, отыскав эту па-
ру вершин
i
p
и
,
j
q
можно избежать перебора всех полигонов тела
B
в поисках
проекции
i
p
и осуществлять поиск только среди полигонов, в которых
j
q
является
одной из вершин, что существенно сократит время расчетов.
Таким образом, необходимо решить задачу поиска ближайшего соседа, ко-
торая заключается в отыскании среди множества элементов, расположенных в
некотором метрическом пространстве, элементов, близких к заданному, соглас-
но некоторой функции близости, определяющей это метрическое пространство.
Полигональная модель в этом случае может рассматриваться как замкнутое
метрическое пространство.
Среди алгоритмов поиска ближайших соседей можно выделить алгоритм
разбиения пространства с помощью диаграммы Вороного [10], поиск в kD-
деревьях [11], поиск в BSP-деревьях [12], поиск в VP-деревьях [13]. Сравнение
перечисленных методов по таким параметрам, как вычислительная сложность,
скорость поиска, сложность реализации, применимость в многомерном про-
странстве и адаптированность к замкнутым пространствам, показало, что
наиболее применимым к решению задачи поиска ближайшего соседа в узкой
фазе определения столкновения является алгоритм поиска в VP-деревьях.
Временнáя сложность алгоритма узкой фазы при использовании алгоритма
поиска по VP-дереву вместо алгоритма Lin — Canny или V — Clip одинакова.
Однако реализация алгоритма поиска по VP-дереву значительно проще. Кроме
того, введение ОПВ сокращает время моделирования, так как в узкой фазе рас-
чет проводится только для вершин, находящихся в ОПВ, а не для всех вершин
полигональной модели.
Реализация алгоритма обнаружения пересечения объектов.
На основе
предложенного алгоритма разработано программное обеспечение, с помощью