Алгоритм априорного обнаружения столкновений для систем виртуальной реальности с тактильной обратной связью

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Алгоритм априорного обнаружения столкновений для систем виртуальной реальности с тактильной обратной связью

Одной из ключевых задач, которые необходимо решить при реализации системы с тактильной обратной связью является обнаружение столкновений инструмента с моделируемым объектом.

При разработке хирургических симуляторов с тактильной обратной связью применяются специализированные алгоритмы обнаружения столкновений [1] [2]. Это обусловлено тем, что обнаружение столкновений, вычисление силы обратной связи и отправка результатов на устройство тактильного ввода-вывода должны происходить с частотой порядка 1000 Гц. Другой причиной разработки специализированных алгоритмов является тот факт, что данные в хирургических симуляторах, направленных на обучение обработки твёрдых объектов, например, костных структур, как правило представлены в виде массивов вокселей, а традиционные подходы к реализации обнаружения столкновений в большинстве случаев предполагают полигональное представление объектов.

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

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

Типичная картина, наблюдаемая при применении апостериорного определения столкновений приведена на рис 1.: инструмент частично проник сквозь поверхность моделируемого объекта.

Обозначенных недостатков лишён априорный подход к обнаружению столкновений, при котором столкновения обнаруживаются до того, как произойдёт взаимное пересечение взаимодействующих объектов.

Авторами предлагается алгоритм, реализующий априорное обнаружение столкновений с использованием карт оккупации пространства вокселями моделируемого объекта и инструмента. Применение карт оккупации давно известно, однако применяется для апостериорного обнаружения столкновений, при котором факт столкновения фиксируется после того, как произойдёт взаимное проникновение объектов.

Рис. 1. Апостериорное обнаружение столкновений:

1 - инструмент, 2 - поверхность моделируемого объекта

Рис. 2. Априорное обнаружение столкновений

хирургия алгоритм тактильный

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

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

На каждой итерации обработки данных с гаптик-устройства производятся следующие действия (Рис. 2):

1. Фиксируется начальное положение инструмента, определяемое, как положение инструмента в конце предыдущей итерации (точка А).

2. Фиксируется желаемое положение инструмента, определяемой, как положение контрольной точки гаптик-устройства в виртуальном пространстве (точка Б).

3. Производится поиск нового положения инструмента по следующему алгоритму:

1. Определяются направления, перемещение в которых приведёт к уменьшению расстояния между текущим положением инструмента и точкой Б. Потенциальные направления смещения помещаются в список и упорядочиваются в порядке увеличения расстояния между инструментом и точкой Б при смещении в этом направлении на один воксель.

2. Для каждого из выбранных направлений проверяется, что при смещении образа инструмента в этом направлении на один воксель не произойдёт проникновения инструмента в поверхность моделируемого объекта.

3. Если при смещении в выбранном направлении на один воксель происходит проникновение инструмента в поверхность моделируемого объекта, то выбирается следующее направление из списка.

4. Если при смещении в выбранном направлении на один воксель не происходит проникновения инструмента в поверхность моделируемого объекта, то фиксируется новое положение инструмента и осуществляется переход к шагу 3.

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

5. Вычисление вектора силы обратной связи.

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

Использование предлагаемого способа требует представления моделируемого объекта и инструмента в виде массива вокселей - равномерно распределённых в пространстве кубов крайне малого объёма, для каждого из которых известны его координаты в пространстве и материал, заключённый в его объёме [3]. Построение таких массивов может быть произведено как предварительно, например, с использованием данных компьютерной томографии в случае хирургических симуляторов, так и происходить в реальном времени. При этом инструмент и объект представлены вокселями, причём разрешение воксельной сетки одинаково для инструмента и моделируемого объекта. Применение предлагаемого подхода позволяет выполнить аппроксимацию поверхностей инструмента и объекта наиболее оптимальным для произведения обнаружения столкновений способом.

За счёт априорного обнаружения столкновений обеспечивается гарантия невозможности пронзания моделируемого объекта виртуальным инструментом при приложении значительного усилия к устройству ввода. В случае, если сопротивление устройства ввода будет преодолено пользователем, виртуальный инструмент всё равно продолжит жёстко следовать по поверхности моделируемого объекта.

Было произведено сравнение описанного метода с аналогичными методами [1] [2]. По результатам сравнения были выявлены следующие преимущества:

1. Пронзание объекта инструментом невозможно, в отличие от рассмотренных методов [1] [2], где при быстром перемещении инструмента возможно пронзание поверхности объекта.

2. Описанный авторами способ гарантирует, что, независимо от сложности рельефа поверхности объекта и формы инструмента, столкновение будет обнаружено. Кроме того, в отличие от рассмотренных способов [1] [2], сложная геометрия моделируемого объекта не сказывается негативно на ощущаемой пользователем жёсткости объекта, не возникает вероятности пронзания моделируемого объекта при взаимодействии с углублениями и каналами в нём.

3. При размещении инструмента в узких проходах и отверстиях не возникает вибраций, которые наблюдаются при использовании способов, реализующих апостериорное обнаружение столкновений [1] [2], поскольку не происходит выталкивание инструмента - генерируемая сила обратной связи воздействует только на пользователя, смещение же инструмента невозможно, поскольку ограничено естественным образом. Это достигается благодаря применению априорного обнаружения столкновений: при попытке смещения объекта в направлении стенки канала при априорном обнаружении столкновений сразу фиксируется факт невозможности смещения инструмента, в результате чего виртуальный инструмент остаётся на месте, а на гаптик устройство подаётся команда на генерацию силы, достаточной для противодействия давлению, оказываемому пользователем. В случае применения апостериорного обнаружения столкновений в данном случае возникает ситуация, когда после каждой новой попытки смещения инструмента в направлении стенки канала происходит отталкивание инструмента и он сразу же пересекается с противоположной стенкой канала.

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

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

Другим важным аспектом практической реализации описанного алгоритма является возможность распараллеливания вычислений. Алгоритм построен таким образом, чтобы достаточно легко было возможно применять SIMD-вычисления.

Список литературы

хирургия алгоритм тактильный

1. Morris, D. Haptics and Physical Simulation for Virtual Bone Surgery: PHD thesis / Morris Dan. - Stanford: Stanford University. 2006. - 213 c.

2. Petersik, A. [и др.] Method for the simulation of the haptic of an interaction of a guided object with a virtual three-dimensional object // US Patent. - 2013. - 10 с.

3. Мареев, Г.О. [и др.] Основные принципы создания виртуального воксельного мира и реализации тактильной обратной связи в хирургических симуляторах / Г.О. Мареев, И.К. Алайцев, И.Ю. Ермаков, Т.В. Данилова, А.О. Мантуров // Бюллетень медицинских Интернет-конференций. - 2016. - №5 (6). - C. 768-771.

Размещено на Allbest.ru