Использование выпуклых многогранников

Что это за алгоритм Lin-Canny?

рис. 1 Диаграмма Вороного для треугольника

Область Вороного формирует область пространства снаружи многогранника, "прилежащую" к ближайшему фрагменту и также является выпуклым многогранником, хотя и незамкнутым. Набор областей Вороного для всех фрагментов многогранника называется диаграммой Вороного  На рис.1 представлен пример диаграммы Вороного для плоского треугольника. Разумеется, для трехмерных многогранников область Вороного ограничивается не линиями, а плоскостями.

В качестве структур данных для областей Вороного используются ячейки, в которых хранятся плоскости, ограничивающие область Вороного с ссылками на соседние ячейки (с которыми граничат плоскости).

Смысл всего этого в следующем - чтобы найти фрагмент многогранника, ближайший к определенной точке, нужно найти область Вороного, которой принадлежит эта точка. Иначе говоря, если точка P объекта A лежит внутри области Вороного фрагмента f_B объекта B, то f_B является ближайшим фрагментом к точке P.

Собственно алгоритм работает следующим образом - берутся по одному фрагменту каждого многогранника и определяются ближайшие точки этих фрагментов, если найденная точка фрагмента первого объекта находится в области Вороного фрагмента второго объекта и точка фрагмента второго объекта находится в области Вороного фрагмента первого объекта, то эти точки являются ближайшими точками многогранников. Если же эти условия не выполняются, то алгоритм переходит к соседним фрагментам для одного или обоих объектов и повторяет проверку. Причем поскольку многогранники выпуклые, каждая следующая проверка будет гарантированно находить более близкие фрагменты, чем предыдущая. Учитывая, что положение объектов от кадра к кадру меняется не слишком значительно, очередные ближайшие точки вероятнее всего будут найдены с первой или со второй попытки.

Теперь рассмотрим проверку попадания точки в область Вороного фрагмента многогранника. Существуют три основных комбинации - точка-вершина, точка-линия и точка-фейс.

Точка-Вершина

Если вершина V многогранника B является ближайшим фрагментом к точке P многогранника A, то точка P должна лежать внутри области Вороного вершины V, ограниченной плоскостями, перпендикулярными линиям, касающимся V (рис. 2). 

Если же точка находится вне области Вороного и лежит с другой стороны одной из ограничивающих плоскостей, то это означает, что по крайней мере одна из соседних линий ближе к точке P, чем вершина V. В этом случае алгоритм возьмет соответствующую линию и проверит, является ли она ближайшей к фрагменту, содержащему точку P.

Точка-Линия

Если линия E многогранника B является ближайшим фрагментом к точке P многогранника A, то точка P должна лежать внутри области Вороного линии E, ограниченной четырьмя плоскостями, две из которых перпендикулярны линии E и проходят через ее концы, и две содержат линию E и параллельны нормалям прилегающих к ней фейсов. (рис. 3)

Если точка находится вне области Вороного и лежит с другой стороны одной из ограничивающих плоскостей, проходящих через концы линии (это означает, что одна из соседних вершин ближе к точке P, чем линия E) или одной из ограничевающих плоскостей, параллельных нормалям прилегающих фейсов (это означает, что один из соседних фейсов ближе к точке P, чем линия E), то алгоритм возьмет соответствующую вершину или фейс и проверит, является ли этот фрагмент ближайшим к фрагменту, содержащему точку P.

Точка-Фейс

Если фейс F многогранника B является ближайшим фрагментом к точке P многогранника A, то точка P должна лежать внутри области Вороного фейса F, ограниченной плоскостями, перпендикулярными фейсу и проходящими через ограничивающие фейс линии. (рис. 4)

Если точка находится вне области Вороного и лежит с другой стороны одной из ограничивающих плоскостей - это означает, что одна из соседних линий ближе к точке P, чем фейс F и алгоритм возьмет соответствующую линию и проверит, является ли она ближайшей к фрагменту, содержащему точку P.

рис. 2 Точка-Вершина

рис. 3 Точка-Линия

рис. 4 Точка-Фейс

Далее необходимо проверить, чтобы точка лежала над плоскостью, проходящую через фейс F, т.к. в противном случае точка может находиться внутри многогранника. 
В ситуации, когда точка находится внутри многогранника, алгоритм не может определить ближайшие точки многогранников и зацикливается. 

Для решения этой проблемы предлагается использовать псевдо-области Вороного, которые разбивают пространство внутри многогранника. Псевдо-области Вороного строятся плоскостями, проходящими через линии многогранника и его центр (рис. 5). Так что если точка находится под плоскостью нужно проверить попадает ли она в соответстующую псевдо-область Вороного, и если это так, значит многогранники столкнулись. Также как и в обычной области Вороного, в псевдо-области хранятся ссылки на соседние ячейки, что позволяет определить следующего претендента на проверку, если точка не попадает в данную псевдо-область Вороного.

рис. 5 Псевдо-области Вороного

Следующая сложность проявляется при попытке определить ближайшие точки фрагментов многогранников. Всего возможно 6 вариантов сочетаний фрагментов - вершина-вершина, вершина-линия, вершина-фейс, линия-линия, линия-фейс, фейс-фейс. Определить ближайшие точки в первых четырех комбинациях в общем труда не представляет, но вот в вариантах линия-фейс и фейс-фейс возможно возникновение неоднозначностей, особенно когда линии и/или фейсы параллельны (довольно запутанный субалгоритм, с помощью которого можно определить ближайшие точки в комбинациях линия-фейс и фейс-фейс я здесь приводить не буду).

Из плюсов алгоритма можно отметить достаточно высокую скорость работы и меньшую чувствительность к ошибкам округления по сравнению с GJK, из минусов - большое количество дополнительной информации (предварительно определенные области Вороного) и сложности при определении ближайших точек (эта проблема решена в алгоритме V-Clip).

Более подробно об алгоритме Lin-Canny можно прочитать здесь:
Efficient Collision Detection for Animation and Robotics by Ming C. Lin, 1993 (~820 Кб)