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

Введение. Научные и прикладные работы о размещении виртуальных объектов в реальном пространстве чаще всего фокусируются на вопросах интерактивности, интеграции реальности и виртуальности, физических свойствах виртуальных элементов. Однако недостаточно проработана задача одновременно свободного и оптимального размещения объектов с учетом их размеров и окружающей зоны комфортности вокруг них. В литературе можно найти описание схожей задачи - об упаковке в прямоугольный контейнер. В нашем случае цель не ограничивается максимально плотным размещением. Следует учесть два условия: жесткие размеры объектов (их запрещено нарушать) и дополнительные области - зоны комфортности (их нежелательно занимать). Цель работы - создание и реализация такого 2D-алгоритма размещения объектов в физическом пространстве, который будет учитывать обозначенные выше ограничения.Материалы и методы. Используя аппарат численных методов, авторы задействовали созданный ранее 1D-алгоритм размещения объектов. Расчеты основываются на системе линейных уравнений. В одномерном случае оптимальное размещение виртуальных объектов сводится к задаче, не зависящей от вида функции комфортности. Элементы такой системы - размеры объектов, дистанции между ними, а также расстояния до края области встраивания, зоны комфортности. Предлагаемый 2D-алгоритм оптимальной расстановки виртуальных объектов реализовали в виде программного кода на языке C# с использованием известного игрового движка Unity. Решение тестировали на гаджетах в режиме пиковой нагрузки для 5, 10, 15, 20, 25, 35, 40, 45 и 50 объектов. Для опытов задействовали 1,8 тыс. устройств. Проанализировали около 77 тыс. событий. Чтобы исключить нерепрезентативные значения, каждый расчет повторяли 10 раз, и для каждого значения провели z-оценку. Аномальные (больше 3 и меньше -3) исключили.Результаты исследования. В работе создан алгоритм 2D-расстановки, который реализует заполнение прямоугольной области виртуальными объектами. У каждого из них есть размер и еще одна характеристика - зона комфортности. Авторы составили блок-схему реализации данного алгоритма в заданной двумерной левосторонней системе координат. Показано, в частности, на каком этапе объекты сортируются по длине, когда формируются их партии и выполняются расстановки по двум осям. Первая - горизонтальная, вторая направлена вперед от пользователя (это вектор глубины, или фронтальное измерение). Алгоритм 1D-размещения для сформированного ряда позволяет оптимально расположить объекты вдоль оси X на основе рассчитанного коэффициента комфортности К. Выполнены расчеты и составлены схемы с целью достичь определенных показателей комфортности. Для каждого объекта первой линии смещение по оси Z от края плоскости определяется так, чтобы комфортность спереди равнялась комфортности по X. Начиная со 2-го ряда для вычисления отступа проверяется наличие потенциальных соседей, которые находятся на ряд выше и имеют общие участки по X с обрабатываемым объектом. Каждый элемент строки устанавливается по оси Z так, чтобы его комфортность сверху была максимальной из односторонних горизонтальных комфортностей в данной и предыдущей строках. Принцип расчета координаты Z для объекта строки представлен в виде блок-схемы.Исходными данными для реализации этого алгоритма были 7 объектов с 14 разными размерами и 28 зонами комфортности. После программной реализации работу описанного 2D-алгоритма проверили на практике - в мобильном приложении дополненной реальности. Записали аналитические данные пользовательских сессий. Рассчитали среднее время выполнения. Возникшую в ходе работы гипотезу о квадратичной зависимости проверили на персональном компьютере. С этой целью провели аналогичный эксперимент для диапазона [10-10000] объектов. Гипотеза подтвердилась. Алгоритму можно присвоить сложность O(n2). Для сравнения скорости вычисления задействовали 10 самых популярных моделей пользовательских устройств. Результаты представили в виде диаграммы. Минимальное зарегистрированное время выполнения - 0,093 мс, максимальное - 0,146 мс. Расчеты показали высокую эффективность двумерного алгоритма. Дополнительно визуализировали схемы расстановки для разного количества и параметров объектов.Обсуждение и заключение. Предлагаемый алгоритм двумерного размещения позволяет работать с набором виртуальных объектов с разными размерами и зонами комфортности. Показаны достаточно высокие производительность и стабильность. В среднем алгоритм реализуется за доли миллисекунды даже при больших партиях объектов. Возможные будущие направления работы:- расширение подхода для построения 3D моделей и алгоритмов;- включение в алгоритм вращения объектов для большей гибкости их расположения и лучшего использования пространства.Итоги работы могут представлять интерес для инженеров и дизайнеров интерфейсов. В перспективе следует изучить пользовательский опыт и возможности включения дополнительных ограничений на позиционирование.