АЛГОРИТМ АПРИОРНОГО ОБНАРУЖЕНИЯ СТОЛКНОВЕНИЙ ДЛЯ СИСТЕМ ВИРТУАЛЬНОЙ РЕАЛЬНОСТИ С ТАКТИЛЬНОЙ ОБРАТНОЙ СВЯЗЬЮ

Алайцев И.К.¹, Данилова Т.В.², Мантуров А.О.³, Мареев Г.О.⁴, Мареев О.В.⁵

¹ORCID: 0000-0003-4657-2701, Аспирант,

Саратовский государственный технический университет имени Гагарина Ю.А.

²ORCID: 0000-0003-1986-2244, Кандидат физико-математических наук, доцент,

Саратовский государственный технический университет имени Гагарина Ю.А.

³ORCID: 0000-0002-1341-171X, Кандидат физико-математических наук, доцент,

Саратовский государственный технический университет имени Гагарина Ю.А.

⁴Доктор медицинских наук, доцент, Саратовский государственный университет имени В.И.Разумовского

⁵Доктор медицинских наук, профессор, Саратовский государственный университет имени В.И.Разумовского

АЛГОРИТМ АПРИОРНОГО ОБНАРУЖЕНИЯ СТОЛКНОВЕНИЙ ДЛЯ СИСТЕМ ВИРТУАЛЬНОЙ РЕАЛЬНОСТИ С ТАКТИЛЬНОЙ ОБРАТНОЙ СВЯЗЬЮ

Аннотация

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

Ключевые слова: виртуальная реальность, тактильная обратная связь, симуляция, виртуальная хирургия, гаптик-устройства.

Alaytsev I.K.¹, Danilova T.V.², Manturov A.O.³, Mareev G.O.⁴, Mareev O.V.⁵

¹ORCID: 0000-0003-4657-2701, Postgraduate student, Yuri Gagarin Saratov State Technical University

²ORCID: 0000-0003-1986-2244, PhD in Physics and Mathematics, Associate professor,

Yuri Gagarin Saratov State Technical University

³ORCID: 0000-0002-1341-171X, PhD in Physics and Mathematics, Associate professor,

Yuri Gagarin Saratov State Technical University

⁴MD, Associate professor, Saratov State Medical University named after V. I. Razumovsky

⁵MD, Professor, Saratov State Medical University named after V. I. Razumovsky

A PRIORY COLLISION DETECTION ALGORITHM FOR 3-DOF HAPTIC RENDERING

Abstract

Simulation systems application is a modern way for students training in surgery. Most of the existing approaches require specific consumables that are destroyed during training. Thus, the training becomes quite expensive while not providing standardization of training process and making it difficult to rate the quality of skills trained. Exploitation of virtual reality provides much better education standardization capabilities while eliminating the need for consumables and making it possible to semiautomatic rating of training results. Collision detection is one of the key components of any haptic rendering algorithm. Most of the existing approaches to haptic rendering are based on a posteriori collision detection. An exploitation of a priory collision detection may drastically increase quality of haptic rendering. This paper describes a priory collision detection algorithm that may be effectively used by 3-DOF haptic rendering implementations.

Keywords: virtual reality, haptic feedback, simulation, virtual surgery, haptic devices.

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

При разработке хирургических симуляторов с тактильной обратной связью применяются специализированные алгоритмы обнаружения столкновений [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-вычисления.

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

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.

Список литературы на английском языке / References in English

1. Morris, D. Haptics and Physical Simulation for Virtual Bone Surgery: PHD thesis / Morris Dan. - Stanford: Stanford University. 2006. - 213 p.
2. Petersik, A. [et. al.] Method for the simulation of the haptic of an interaction of a guided object with a virtual three-dimensional object // US Patent. - 2013. - 10 p.
3. Mareev, G.O. [et. al.] Osnovnye printsipy sozdaniya virtual'nogo voksel'nogo mira i realizatsii taktil'noy obratnoy svyazi v khirurgicheskikh simulyatorakh [Basic principles of creation of voxelized virtual world in virtual surgery simulation systems] / G.O. Mareev, I.K. Alaytsev, I.Y. Ermakov, T.V.Danilova, A.O.Manturov // Byulleten' meditsinskikh Internet-konferentsiy [Bulletin of Medical Internet Conferences]. - 2016. - № 5 (6). - P. 768–771.