Система генерации ландшафта лабиринта с улучшенным визуальным реализмом [перевод статьи Jinmo Kim]

Привет, Хабр!

В этой публикации я расскажу о статье автора Jinmo Kim: "Maze Terrain Authoring System in Immersive Virtual Reality for New Visual Realism". Она была опубликована 4.04.2019. Полный текст статьи можно посмотреть здесь.

Краткое описание системы

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

Предложенная система генерации ландшафта лабиринта состоит из трех основных функций:

• функция автоматической генерации сетки лабиринта различных размеров и узоров, реализованная с помощью классического алгоритма генерации лабиринта;
• функция генерации кругового лабиринта;
• функция преобразования лабиринта из ручного эскиза в 3D объект с помощью алгоритма обработки изображений.

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

Почему виртуальная реальность?

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

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

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

Виртуальная реальность погружения

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

Исследования виртуальной реальности погружения проводились с использованием различных подходов:

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

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

Улучшение визуального реализма

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

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

Система создания ландшафта лабиринта

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

Генерация прямолинейного шаблона лабиринта

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

Алгоритм конечной генерации лабиринта Ли и др., — это способ, который начинается с процессов: (1) установки стартовой позиции и (2) случайной установки ячейки дороги из окружающих ячеек. Затем (3) алгоритм исследует четыре ячейки вокруг направления (определяя структуру слоев ячеек, после добавления в коллекцию этих четырех окружающих ячеек в качестве ячеек стен). Затем алгоритм повторяет процессы (4, 5), чтобы найти одну из записанных ячеек стены, а затем создает дорогу.

На рисунках ниже показан процесс построения шаблона прямолинейного лабиринта. Пользователь устанавливает размер шаблона лабиринта, и при нажатии на кнопку “Лабиринт”, автоматически рассчитывается и генерируется шаблон лабиринта.

Если пользователь хочет отредактировать шаблон автоматически созданного лабиринта, то выбирается режим “Редактирование”. Пользователь редактирует мышью в поле представления шаблона лабиринта, путем нажатия на ячейку, после чего она автоматически преобразуется из стены в дорогу или из дороги в стену. После того, как шаблон лабиринта сгенерирован, у пользователя есть возможность просмотреть полученный лабиринт в формате 3D.

Просмотр лабиринта в формате 3D

Метод создания кругового лабиринта

Вторая функция предлагаемой авторской системы создания ландшафта лабиринта — это метод генерации кругового лабиринта. Этот метод автоматически создает круговые лабиринты различных размеров и узоров и является хорошим дополнением к функции генерирования узоров лабиринта в виде прямоугольной сетки. Таким образом, этот метод расширяет визуальный опыт пользователей в виртуальной реальности. Процесс создания и установки стен и дорожных ячеек в основном идентичен. Но для кругового лабиринта входными характеристиками являются радиус лабиринта и количество входов в лабиринт.

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

Ячейки, которые станут начальными для входа во внешнем круге, выбираются произвольно столько раз, сколько должно получиться входов в лабиринт. Затем в выбранной ячейке выбирается ячейка стены, у которой длина совпадает с интервалом (ns) между круговыми стенками, и она вращается ровно настолько, чтобы касаться внутренней круговой стенки.
Наконец, когда встречается ячейка стены в положении, в котором она повернута и касается внутренней круговой стенки, то вышеописанный алгоритм повторяется.

1:  nr ← радиус кругового лабиринта.
2:  ne ← количество входов в лабиринт.
3:  procedure СПОСОБ СОЗДАНИЯ КРУГОВОГО ЛАБИРИНТА (nr, ne)
4:     ns ← интервал между стенами лабиринта для дороги пользователя.
5:     while nr > ns do
6:        определить ячейку стены с помощью алгоритма рисования круга Брезенхэма.
7:        nr = nr - ns.
8:     end while
9:     nc ← количество кругов для рисования.
10:    Arre[ne] ← входные ячейки, количество ne выбранных из ячеек стены внешнего круга.
11:    for i = nc, 0 do: генерировать проходы в каждом круге.
12:        for j = 0, ne do
13:            выделить ячейки с длиной ns в массиве ячеек (Arre[j]).
14:            повернуть выбранные ячейки.
15:            обновить Arre[j], найдя ячейку, которая соответствует внутреннему кругу после поворота.
16:        end for
17:    end for
18: end procedure

nr ← radius of the circular maze.
ne ← number of maze entrances.
procedure CIRCULAR MAZE GENERATION PROCESS(nr, ne)
    ns ← interval between maze for user road.
    while nr > ns do
        define wall cell by using Bresenham’s circle drawing algorithm.
        nr = nr - ns.
    end while
    nc ← number of drawing circles.
    Arre[ne] ← as many entrance cells as ne are selected from wall cell of the outermost circle.
    for i = nc, 0 do: generate passages in every circle.
        for j = 0, ne do
            select cells with length of ns in entrance cell (Arre[j]).
            rotate selected cells.
            renew Arre[j] by finding a cell that meets the inner circle after rotation.
        end for
    end for
end procedure

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

Лабиринт на основе эскиза

Последняя функция системы создания лабиринта в этой работе — это генерация лабиринта на основе эскиза. Шаблоны прямолинейного и кругового лабиринтов являются однородными лабиринтами. Однако, в большинстве случаев, парк лабиринта, с которым мы можем столкнуться в повседневной жизни, имеет неправильную форму. Поэтому, в этой работе предложена функция, которая из нарисованного вручную эскизного изображения пользователя, может легко создавать естественную поверхность лабиринта, а также шаблон лабиринта в электронном виде. Эта функция позволяет использовать участки лабиринта в различных приложениях, таких как системы для поиска пути или виртуальные парки.

Предложенная функция генерации лабиринта позволяет пользователю использовать рисунок лабиринта, нарисованный с помощью графического программного обеспечения, такого как Photoshop, или отсканированный эскиз, нарисованный от руки на листе бумаги. Изображение загружается в систему, в которой применяется алгоритм обработки изображений, за счет чего изображение преобразуется в карту текстур лабиринта. Этот процесс осуществляется в три этапа.

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

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

Генерация лабиринта из эскиза пользователя

Экспериментальные результаты и анализ

Предлагаемая система создания ландшафта лабиринта была реализована с использованием Microsoft Visual Studio 2013, OpenCV 2.4.11 и DirectX SDK 9.0c. Кроме того, движок Unity 2017.3.1f1 (64-битный) использовался для создания ландшафта лабиринта, доработанного с помощью графической работы, на основе карты текстур лабиринта, автоматически генерируемой с помощью авторской системы создания лабиринта. Для проверки этого ландшафта и просмотра результата в виртуальной реальности, система была интегрирована с помощью устройства Oculus Rift CV1 HMD и Oculus SDK (ovr_unity_utilities 1.22.0) с движком Unity3D. Наконец, ПК, используемый для эксперимента и реализации, имел характеристики Intel Core i7-6700, 16 ГБ ОЗУ (оперативное запоминающее устройство) и графический процессор Geforce 1080.

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

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

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