Введение 3
Постановка задачи 3
Часть 1. Анализ проблемы и теоретические основы 5
Формулировка общего случая задачи текстурирования 5
Постановка базовой конфигурации входных данных 5
Формулировка задачи упаковки 6
Анализ реализованных алгоритмов 7
Часть 2. Исследование реализации алгоритма в библиотеке xatlas 9
Представление чартов и проверка пересечения 9
Расположение единственного чарта 10
Расположение совокупности чартов 11
Часть 3. Усовершенствования реализации и результаты 12
Методы оптимизации без изменения результатов 12
Параллелизация 12
Coarse-to-Fine схема 13
Альтернативные способы представления чартов в памяти 21
Реализация алгоритма на видеокарте 22
Методы оптимизации с изменением результатов 24
Гибридное использование методов упаковки 24
Компенсация сокращения домена поиска 25
Прореживание домена поиска 26
Поворот чартов 27
Часть 4. Оценка результатов оптимизации 28
Материалы для замеров 30
Заключение 31
Список литературы 32
Приложение. Таблица с результатами замеров 33
Трёхмерное моделирование является относительно современным направлением развития компьютерных наук. Трёхмерные объекты могут создаваться для разных задач, в числе которых визуализация данных и цифровое воспроизведение реальных объектов. Одним из способов реализации последнего является фотограмметрия - дисциплина, позволяющая определять формы и положения физических объектов и окружения при помощи фотографий. Вне зависимости от источника данных, трёхмерная модель представляется преимущественно в текстурированном виде. В настоящее время технологии позволяют использовать текстуры высокого качества, что особенно важно в случае задачи фотограмметрии. Несмотря на это, исследуемые средства для построения текстур занимают значительное время для своей работы, в том числе из-за устаревших подходов к упаковке. Реализация инструментов упаковки, компенсирующих растущие требования к размерам текстур, позволит эффективно распределять ресурсы при работе с данными и поможет как в исследовательских, так и в производственных задачах.
Постановка задачи
Целью данной работы является оптимизация работы одного из существующих в открытом доступе инструментов для упаковки текстур на наборах данных, предполагающих большие размеры результирующей текстуры. Для достижения цели работы требуется выполнить следующие задачи:
• Исследовать существующие реализации алгоритмов и выбрать одну из них для оптимизации;
• Проанализировать работу алгоритма в выбранной реализации и обнаружить части алгоритма, требующие оптимизации;
• Продумать методы, при помощи которых будет осуществляться оптимизация;
• Реализовать данные методы и убедиться в их эффективности.
В части 1 данной работы представлены необходимые термины, постановка задачи и краткий анализ существующих реализаций; часть 2 содержит анализ алгоритмов, реализованных в библиотеке xatlas, которая использовалась в качестве основы для улучшения, а также критерии, согласно которым следует вносить изменения в свободно распространяемую реализацию алгоритма; в части 3 описаны методы, с помощью которых производится оптимизация алгоритма; в части 4 представлено сравнение улучшенного алгоритма с оригинальным.
В результате работы получена новая версия библиотеки xatlas, позволяющая быстрее упаковывать чарты для текстур высокого разрешения. Эффективность полученных алгоритмов проверена на наборе данных «Real World Textured Things», содержащем модели, полученные при помощи фотограмметрии. В момент написания работы данная версия используется в коммерческом ПО Agisoft Metashape.
