Оптимальная 2D-расстановка виртуальных объектов в физическом пространстве для приложений дополненной реальности

Введение. Известная задача приложений дополненной реальности (augmented reality, AR) — размещение виртуальных объектов в реальном физическом пространстве. Ряд исследований [1–3] фокусируются на интерактивности, слиянии реальной и виртуальной сфер. Изучаются также вопросы физических свойств виртуальных объектов.

Недостаточно проработана задача такого размещения объектов, которое одновременно было бы свободным и оптимальным, учитывало не только геометрические размеры объектов, но и зоны комфортности вокруг них. В [6] отмечена внешняя схожесть этой задачи с известной задачей об упаковке в прямоугольный контейнер [5]. Однако есть существенная разница. В исследуемом случае недостаточно обеспечить максимально плотную упаковку. При размещении виртуальных объектов нужно учесть не только их жесткие размеры, которые нельзя нарушать, но и дополнительные области — зоны комфортности. Их занимать нежелательно. Эти дополнительные области позволяют приблизиться к объекту и выполнить с ним какие-то действия.

Целями представленной работы являются создание, реализация и оценка 2D-алгоритма оптимального размещения виртуальных объектов в физическом пространстве.

Материалы и методы. Ранее [4] авторы определили, что такое комфортное размещение виртуальных объектов, ввели понятие функции комфортности k(x). Она монотонно возрастает от 0 до 1 при 0≤x≤1 и равна 1 при х>1, где x = X/D, X — расстояние от края объекта до ближайшего препятствия, D — размер зоны комфортности. Для каждого измерения у объекта есть две односторонние зоны комфортности D– и D+. Комфортность с каждой стороны вычисляется отдельно.

В [6] показано, что задача одномерного размещения n виртуальных объектов в свободной области пространства протяженностью L сводится к системе линейных уравнений, не зависящих от вида функции комфортности k(x):

Здесь

— расстояние первого объекта от левого края области встраивания;

— расстояние между объектами с номерами i и (i – 1);

и — левая и правая зоны комфортности соответственно;

l⁽ⁱ⁾ — размер объекта;

,

i = 1,2,…, (n – 1).

Матрица системы (1) сильно разрежена, поэтому можно избежать использования не самых быстрых универсальных методов и достаточно просто найти решение. Например, в первых (n – 1) равенствах можно в каждом i-м уравнении выразить через , затем подставить это в последнее уравнение и получить линейное уравнение относительно . После этого от первого уравнения к (n – 1)-му последовательно определяются значения . Авторы реализовали данный 1D-алгоритм размещения объектов с помощью численных методов. Он показал высокую скорость и эффективность. Этот 1D-алгоритм стал основой для научных изысканий, описанных в представленной работе. Авторы предложили 2D-алгоритм оптимальной расстановки виртуальных объектов. Его реализовали в виде программного кода на языке C# с использованием игрового движка Unity, который широко используется для создания мобильных приложений дополненной реальности [8]. В ходе эксперимента на устройстве пользователя, работающего в режиме пиковой нагрузки, запускался алгоритм для 5, 10, 15, 20, 25, 35, 40, 45 и 50 объектов. Замеряли время, затраченное на вычисления (в миллисекундах). Каждый расчет повторяли 10 раз во избежание аномальных значений. Всего в эксперименте участвовали 1,8 тыс. устройств, с них собрали и проанализировали около 77 тыс. событий с результатами.

Фильтрация аномалий с помощью z-оценки позволила выявить значения, которые можно определить как выбросы [9]. Авторы стандартизировали данные и вычислили z-оценку для каждого значения. Аномальными сочли те, у которых z-оценка оказалась больше 3 или меньше –3. Их исключили и сосредоточились на типичных и репрезентативных данных.

Результаты исследования. Итак, на плоскости X, Z есть прямоугольная область с шириной и длиной Ее следует заполнить некоторым количеством виртуальных объектов. Каждый объект помимо своих размеров (где i — номер объекта) характеризуется еще зонами комфортности . На рис. 1 представлена блок-схема описываемого алгоритма.

В данной работе используется левосторонняя система координат: ось X обозначает горизонтальный вектор размещения, ось Z направлена вперед от пользователя и является вектором глубины или фронтальным измерением [7]. Объекты размещаются в горизонтальной плоскости (например, на полу, столешнице и пр.), поэтому вертикальная ось Y не рассматривается, а все иллюстрации предполагают вид сверху на получившуюся композицию.

В левом нижнем углу каждого виртуального объекта обозначим опорную точку (pivot). Она будет определять конечные координаты размещения объекта. Далее набор объектов сортируется в порядке убывания по — габаритной длине объектов с учетом зон комфортности, расположенных спереди и сзади в соответствии с рассматриваемой осью координат. После сортировки объекты, занимающие больше пространства по глубине, располагаются дальше от пользователя (или выше для схемы, представленной в горизонтальной проекции). Блок-схема формирования партии из объектов представлена на рис. 2.

Затем из упорядоченного множества объектов формируются отдельные строки или партии (batch). В каждую строку включается минимальное количество объектов, сумма ширины которых вместе с зонами комфортности превосходит ширину заполняемой области . Если при добавлении следующего объекта вычисленная занимаемая ширина превысит горизонтальный размер доступного пространства внутри прямоугольника, партия считается завершенной. Таким образом, каждая партия может быть размещена в виде линии в пределах области. Ряды чередуются слева направо и справа налево для смешивания крупных и мелких объектов. Это можно назвать «челночным ходом» (рис. 3).

Для сформированного ряда применяется алгоритм 1D-размещения, который позволяет оптимально расположить ряд объектов вдоль оси X на основе рассчитанного коэффициента комфортности К, одинакового для всех объектов ряда. Для каждого объекта первой линии смещение по оси Z от края плоскости определяется таким образом, чтобы комфортность спереди равнялась комфортности по X:

.

Начиная со 2-го ряда для вычисления отступа Z₊ проверяется наличие потенциальных соседей сверху из вышележащего ряда, имеющих с текущим обрабатываемым объектом общие участки по координате X. При этом каждый объект размещаемой строки устанавливается по оси Z таким образом, чтобы его комфортность сверху была максимальной из односторонних горизонтальных комфортностей в данной и предыдущей строках. Алгоритм расчета координат Z представлен на рис. 4.

Из блок-схемы видно, что отступ вычисляется аналогично для всех трех возможных сценариев:

• отступ от края плоскости для установки объекта;
• отступ от соседа сверху;
• при отсутствии соседа в предыдущей строке берется самый близкий по Z объект из всех предыдущих строк.

Новые партии формируются до тех пор, пока всем объектам не присвоят ряд или пока не закончится физическое пространство.

Исходные данные к описанному алгоритму систематизированы в таблице 1. Объекты рассортированы по их вертикальным размерам.

Таблица 1 соответствует рис. 5, демонстрирующему размещение объектов.

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

Напомним, что в данную модель входит понятие функции комфортности k(x). От нее не зависит полученная система уравнений (1), а значит и оптимальное размещение объектов. А вот значения односторонних комфортностей объектов определяются и их размещением, и видом функции k(x). Приведем два примера:

• в случае линейной функции k(x) односторонние комфортности объектов верхнего ряда рис. 5 оказываются равными 0,6;
• для зависимости — значение 0,9.

После программной реализации описанного 2D-алгоритма его внедрили в мобильное приложение с дополненной реальностью и записали аналитические данные пользовательских сессий. Сгруппировали информацию по каждой уникальной модели устройства, по каждому количеству расставляемых объектов в диапазоне [10–50]. Рассчитали среднее время выполнения (рис. 6).

На указанном диапазоне невозможно сразу определить точную сложность вычисления алгоритма. Как видно из рис. 6, данные близки к линейной и квадратичной аппроксимации. С помощью метода остаточной суммы квадратов рассчитана количественная оценка обеих аппроксимаций и получены значения 0,00035 и 0,00021 соответственно [10].

Сопоставили время выполнения на разных пользовательских устройствах. Отобрали 10 самых популярных моделей и по результатам вычислений построили диаграмму (рис. 8).

Минимальное зарегистрированное время выполнения — 0,093 мс, максимальное — 0,146 мс. Для данной выборки корреляция между моделью устройства и временем выполнения — всего 0,177. Это довольно низкое значение.

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

На рис. 9 представлены дополнительные визуализации схем расстановки для разного количества объектов и их параметров.

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

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

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

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

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

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

Предложенная технология размещения объектов в 2D позволяет оптимально позиционировать виртуальный контент для улучшения пользовательского опыта в дополненной реальности. Автоматизированный расчет расположения сокращает ручную работу и дает возможность сосредоточиться на полноценном взаимодействии с AR.

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

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

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