12 / 18
А.Г. Лесков, Е.В. Селиверстова
108
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 6
то пересечения нет, устанавливается факт отсутствия контакта между ОМ и
звеном ЗУМ на текущем шаге моделирования.
Если одно или несколько условий не выполняются, то в ОП выделяется об-
ласть потенциального взаимодействия. Она формируется границами OBB, в СК
которого осуществлялся перевод, а также плоскостями, заданными координа-
тами вершин второго OBB, при проверке которых условия не выполнялись, и
нормалями, соответствующими ортам осей СК первого OBB, по которым усло-
вия не были выполнены (см. рис. 3,
а
).
Затем устанавливется факт наличия в ОПВ вершин полигональной модели
соответствующего объекта. Если ни одна из вершин не располагается внутри
ОПВ, делается вывод, что на текущем шаге моделирования контакт между ОМ и
звеном ЗУ отсутствует. В этом случае вычисления продолжаются в широкой
фазе.
Если же в ОПВ обоих ОП находятся вершины полигональных моделей обо-
их объектов
1
, ...,
,
f
P p p
P P
и
1
, ...,
,
g
Q q q
Q Q
(см. рис. 3,
б
), в рам-
ках широкой фазы делается вывод о возможном наличии пересечения, и для
этого шага моделирования выполняется узкая фаза определения пересечения,
которая выявляет факт наличия или отсутствия пересечения, а также при выяв-
лении пересечения рассчитывает точки, лежащие на поверхности пересечения,
соответствующие им глубины и нормали проникания.
Узкая фаза алгоритма обнаружения пересечения объектов.
Использова-
ние расстояния между точками
i
p
и
j
q
в качестве функции близости вершин
проще в реализации и понимании, чем использование угла между векторами
i j
p q
и
v
. Очевидно, что угол между векторами
i j
p q
и
v
будет наименьшим, если
проекции вершин
i
p
и
j
q
на плоскость, заданную вектором
v
в качестве вектора
нормали и проходящую через точку
1
p
вдоль направления относительного
движения
v
,
будут ближайшими соседями с точки зрения расстояния между
ними. Проецирование множеств точек
P
и
Q
дает два множества точек —
1
, ...,
f
P p p
и
1
, ...,
,
g
Q q q
элементы которых удовлетворяют равенствам:
1
1
1
2
2
2
,
x ix
x
y iy
y
z iz
z
i
i
x
y
z
v p p v p p v p p
p p v
v v v
1, ..., ,
i
f
1
1
1
2
2
2
,
x jx
x
y jy
y
z jz
z
j
j
x
y
z
v q p v q p v q p
q q v
v v v
1, ..., .
j
g
Для решения задачи поиска ближайшего соседа для множеств
P
и
Q
стро-
ятся VP-деревья. Построение VP-дерева является рекурсивной процедурой —
на каждой итерации алгоритма статистически [13] выбирается опорная точка и
вычисляется среднее расстояние от нее до всех остальных точек — радиус обла-
сти узла
R
. Затем остальные точки делятся на два подмножества, называемых