Размещено на http://www.allbest.ru/

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

“ВЫСШАЯ ШКОЛА ЭКОНОМИКИ”

Факультет компьютерных наук

Департамент программной инженерии

Выпускная квалификационная работа

на тему “IOS приложение для построения моделей объектов на основе 3D триангуляции Делоне в дополненной реальности”

по направлению подготовки 09.03.04 “Программная инженерия”

Научный руководитель

Доцент департамента программнои? инженерии, канд. техн. наук Р.З. Ахметсафина

Выполнила

студентка группы БПИ152

4 курса бакалавриата

образовательной программы “Программная инженерия” В.О. Рылина

Москва 2019

Реферат

В настоящее время нет бесплатной возможности с помощью обычного мобильного устройства перенести объект реального мира в виртуальный мир в виде объемной цифровой модели. Цель данной выпускной квалификационной работы - предложить решение в виде iOS приложения, которое по облаку точек реального объекта, просканированного через камеру мобильного устройства, на основе 3D триангуляции Делоне строит модель этого объекта. Полученную модель можно просмотреть в дополненной реальности и сохранить в OBJ файл.

В работе описан способ получения облака точек реального объекта с помощью фреймворка ARKit; подробно описаны шаги алгоритма 3D триангуляции Делоне gFlip3D, выполняемого на графическом процессоре, и его реализация.

Данная работа содержит 42 страница, 3 главы, 20 рисунков, 2 таблицы, 14 источников и 4 приложения.

Ключевые слова: iOS, GPU, 3D триангуляция Делоне, gFlip3D, AR.



Abstract

Currently, there is no free opportunity to transfer a real-world object to virtual world in form of a three-dimensional digital model using just a mobile phone. The goal of this work is to propose a solution to the existing problem as an iOS application that will scan point cloud of a real object using camera of the mobile phone and then build a model of this object based on 3D Delaunay triangulation of its point cloud. The resulting model can be viewed in augmented reality and saved to a OBJ file.

The work will describe a method of obtaining a point cloud of a real object using ARKit framework and also algorithm of 3D Delaunay triangulation called gFlip3D and its implementation using GPU will be described in detail.

This work contains 42 pages, 3 chapters, 20 figures, 2 tables, 14 sources and 4 applications.

Key words: iOS, GPU, 3D Delaunay triangulation, gFlip3D, AR.



Оглавление

• Основные определения, термины и сокращения
• Введение
• Глава 1. Обзор
• 1.1 Обзор iOS приложений для построения 3D моделей реальных объектов
• 1.2 Проблема вычислительной мощности мобильного устройства
• 1.3 Выбор алгоритма 3D триангуляции Делоне на GPU
• Выводы по главе
• Глава 2. Описание алгоритма и логики реализации основного функционала приложения
• 2.1 Получение облака точек реального объекта
• 2.2 Тест ориентации и тест на нахождение точки в сфере
• 2.3 Описание gFlip3D
• 2.3.1 Параллельная вставка точек
• 2.3.1.1 Выбор точки для вставки
• 2.3.1.2 Вставка точки
• 2.3.2 Параллельный флиппинг
• 2.3.2.1 Проверка выполнения условия Делоне
• 2.3.2.2 Проверка на наличие конфигурации тетраэдров для флипа
• 2.3.2.3 Параллельное выполнение флиппинга
• Выводы по главе
• Глава 3. Технологии, инструменты разработки и детали реализации приложения
• 3.1 Инструменты разработки
• 3.2 Использование GPU
• 3.3 Обмен данными между GPU и CPU
• 3.4 Ядро
• 3.5 Структуры данных
• 3.6 Краткое описание основных классов
• 3.7 Сохранение модели в OBJ файл
• 3.8 Получение облака точек
• 3.9 Взаимодействие с объектом в AR
• Заключение
• Список источников

триангуляция алгоритм тератэдр флип



Основные определения, термины и сокращения

CPU (англ. central processing unit) - это центральный процессор компьютера.

GPU (англ. graphics processing unit) - это процессор, расположенный на видеокарте, который выполняет обработку 2D или 3D графики.

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

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

Локально Делоне грань. В триангуляции из , грань, f ? , называется локально Делоне, если сфера, описанная около тетраэдра, содержащего f, не содержит другие вершины. В противном случае грань называется локально не Делоне. Если все грани из являются локально Делоне, то ? [3].

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

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

Двусторонний флип в 3D представлен двумя флипами: флип 2-3 и флип 3-2; (см. рис. 1а). Первый флип производит преобразование двух тетраэдров {acde, bcde} в три {abcd, abce, abde}, а второй обратное - три в два [1].

Unflippable конфигурация - такая конфигурация тетраэдров, когда объем тетраэдров изменится после флипа (см. рис. 1б) или в результате какого-либо из двустороннего флипа будет образован плоский тетраэдр [1].

Рисунок 1. (а) Двусторонний флип в 3D и (б) unflippable конфигурация [1]

Star splaying подход - четырехмерный алгоритм, который принимает на входе не Делоне триангуляцию, а на выходе выдает полную Делоне триангуляцию.

Звездой вершины v в алгоритме Star splaying является множество симплексов триангуляции, имеющих v в качестве вершины; (см. рис. 2a). [2] В алгоритме все вершины, входящие в звезду, из 3D (x, y, z) преобразуются в 4D (x, y, z, x² + y² + z²). На рис. 2б изображено аналогичное преобразование из 2D в 3D.



Рисунок 2. (а) Звезда вершины v и (б) преобразование вершин из 2D в 3D [2]



Введение

Дополненная реальность (AR - augmented reality) - одна из самых перспективных технологий XXI века, хотя ее история началась еще в далеком 1961 году. С каждым годом AR дополняется все большими опциями, из-за чего ее возможности растут вместе и со сферами ее применения. Так, на сегодняшний день дополненная реальность используется в полиграфии, игровых аркадах, интерактивных учебных пособиях, медицине, в планировке квартир и домов, а также во многом другом.

Для начала дадим определение технологии дополненной реальности. Ее корни уходят в схожее понятие - виртуальную реальность (VR - virtual reality), однако суть они имеют разную. VR - это полное погружение в виртуальный, программно созданный мир, состоящий только из виртуальных объектов. Для такого погружения используются стационарные очки или шлем виртуальной реальности, а взаимодействие с этим миром обеспечивают особые датчики и сенсоры движения. Данная технология нашла массовое применение в игровой индустрии. Вернемся к дополненной реальности, AR - это добавление нереальных, виртуальных объектов в реальный мир. Но чтобы увидеть данную картину, нужен всего лишь смартфон или планшет со встроенной камерой. AR-приложение отображает на экране мобильного устройства картинку, полученную с камеры, с добавлением одного или нескольких виртуальных, возможно анимированных объектов в 3D. Взаимодействовать с этими объектами можно посредством касания экрана устройства. Стандартными действиями с виртуальными объектами в AR являются изменение размера объекта, его вращение и перемещение.

Первые AR-приложения создавались для смартфонов как с операционной системой Android, так и с операционной системой iOS. Однако компания Apple, являющаяся производителем мобильных телефонов под управлением iOS, в отличии от других технологических компаний, первой заметила большую перспективность данной технологии, и в 2017 году была выпущена целая платформа для разработки приложений дополненной реальности, названная ARKit. Фреймворк ARKit быстро завоевал популярность и темпы развития AR технологии не угасают именно с выпуском данной платформы. Также нужно отметить, что в настоящее время ARKit является единственным решением для создания AR приложений для iPhone, а в сравнении с существующими решениями для Android, работает лучше и одинаково для всех мобильных устройств под управлением iOS, что делает его фаворитом для создания AR приложений среди iOS разработчиков [6].

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

Цель данной выпускной квалификационной работы - предложить решение в виде iOS приложения, которое по облаку точек реального объекта, просканированного через камеру мобильного устройства, на основе 3D триангуляции Делоне будет строить модель этого объекта. Полученную модель можно будет просмотреть в дополненной реальности.

Для достижения данной цели были сформулированы следующие задачи:

1. Изучить способ получения облака точек реального объекта с помощью фреймворка ARKit и реализовать его.

2. Получить достаточное количество точек реального объекта.

3. Проанализировать проблему вычислительной мощности мобильного телефона.

4. Изучить существующие алгоритмы 3D триангуляции Делоне на GPU и выбрать один из них.

5. Реализовать выбранный алгоритм 3D триангуляции Делоне на GPU.

6. Реализовать перенос полученной триангулированной модели в дополненную реальность.

7. Реализовать сохранение 3D модели в файл.

8. Разработать техническую документацию.

В первой главе приведен обзор аналогов; описана проблема вычислительной мощности мобильного устройства; рассмотрены существующие алгоритмы 3D триангуляции Делоне, подходящие для работы на мобильном телефоне, и произведен выбор алгоритма.

Во второй главе описан способ получения облака точек с помощью фреймворка ARKit; подробно описаны шаги выбранного алгоритма 3D триангуляции Делоне.

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

В заключении перечислены основные полученные результаты и пути дальнейшей работы.

В приложениях представлена программная техническая документация, разработанная в соответствии с ГОСТ 19.



Глава 1. Обзор

1.1 Обзор iOS приложений для построения 3D моделей реальных объектов

В настоящее время существует несколько iOS приложений для построения 3D моделей реальных объектов, однако принцип работы этих приложений заключается в использовании особой технологии 3D-сканирования - фотограмметрии, которая реконструирует объект в 3D из двухмерных изображений. По определению, фотограмметрия -- это “наука проведения измерений по фотографиям”, но в случае трехмерного сканирования фотограмметрия создает трехмерные модели путем подачи изображений в вычислительную модель. Пользователь делает несколько снимков объекта под разными углами (обычно 360 ° вокруг объекта) с помощью iOS приложения для 3D-сканирования. Затем приложение обрабатывает эти изображения, локально или через облачный сервис, и “сшивает” их вместе, чтобы сформировать трехмерную модель. Затем 3D модель может быть доступна для экспорта, что дает возможность ее редактирования с использованием дополнительного программного обеспечения.

Условно, существующие мобильные приложения можно разделить на две группы [7]:

1) приложения 3D-сканирования, не требующие какого-либо оборудования в дополнение к смартфону;

2) приложения 3D-сканирования, которые требуют дополнительного оборудования.

Приложения, относящиеся к первой группе:

Qlone

Чтобы пользователь мог использовать Qlone, необходимо напечатать специальный черно-белый бумажный коврик (аналог QR-кода), на котором будет размещен объект для 3D-сканирования. Qlone предлагает полезную систему навигации; серый купол окружает объект и позволяет пользователю узнать, какой угол ему нужно захватить следующим. Приложение генерирует результаты локально и практически в режиме реального времени. Однако все, что можно бесплатно сделать в приложении - это отсканировать объект и тут же посмотреть на полученную модель в AR. Экспорт модели в Sketchfab (площадка для продажи 3D моделей) или Shapeways (сервис 3D печати) стоит $ 0,99.

Scandy Pro

Scandy Pro -- это бесплатное приложение для 3D-сканирования, которое превращает iPhone (X, XS, XS Max или XR) в полноцветный 3D-сканер. В приложении пользователи могут редактировать полученные 3D модели с помощью инструментов, которыми можно обрезать или сглаживать модель. Кроме того, 3D модели легко экспортировать (.PLY, .OBJ или .STL) и / или загружать непосредственно в Sketchfab. Пользователям каждую неделю предоставляется возможность одного бесплатного сохранения модели, однако они могут купить либо отдельные сохранения, либо платную подписку с неограниченным количеством сохранений.

Приложение, относящееся ко второй группе:

3DSizeME

3DSizeME -- это приложение для 3D-сканирования тела человека, разработанное канадской компанией TechMed3D. Это бесплатное приложение для 3D-сканирования работает со структурным датчиком (стоимостью $379) и предназначено для целевых и профессиональных медицинских клиник. Приложение 3DSizeME обеспечивает точные измерения тела, а компания-производитель TechMed3D может настроить приложение под конкретные варианты использования и профессиональные нужды.

Таким образом, были рассмотрены три iOS приложения для построения 3D моделей реальных объектов, однако каждое из них имеет ряд недостатков и серьезных различий с проектируемым в рамках ВКР iOS приложением. Начнем с недостатков каждого из них.

Для сканирования объекта с помощью Qlone мало того, что необходимо печатать специальный черно-белый бумажный коврик, так еще и полученную в результате модель бесплатно можно только посмотреть в AR. Экспорт модели платный.

Scandy Pro предназначен для работы лишь на новых iPhone, имеющих инновационную систему камер, названную TrueDepth, включающую в себя 7-мегапиксельную фронтальную камеру, инфракрасную камеру, проектор точек и инфракрасный излучатель. Можно сказать, что такая система камер уже представляет собой 3D-сканер. Получается, что для более старых iPhone данное приложение не работает, хотя AR поддерживается на iPhone, начиная с модели 6s (то есть также на 7, 7+, 8, 8+). Более того, приложение не полностью бесплатное, экспортировать полученные 3D модели бесплатно можно только один раз в неделю и только одну. Приложение 3DSizeME, во-первых, использует дополнительный дорогостоящий структурный датчик, во-вторых, используется в медицинских целях и только для сканирования тела человека. Несмотря на то, что вышеперечисленные приложения выполняют ту же самую функцию - создание 3D модели реального объекта, они используют совершенно другую технологию как сканирования объекта, так и создания модели (фотограмметрия). В проектируемом в рамках ВКР iOS приложении модель объекта создается на основе алгоритма 3D триангуляции Делоне, применяемом на облаке точек реального объекта, которые, в свою очередь, могут быть получены с помощью фреймворка ARKit, предоставляющего такую возможность. Таким образом, получается, что полного аналога данной выпускной квалификационной работы нет, хотя даже те iOS приложения, что были описаны выше, уступают проектируемому приложению по ряду пунктов.



1.2 Проблема вычислительной мощности мобильного устройства

Существует большое количество алгоритмов 3D триангуляции Делоне, но общей характеристикой данных алгоритмов является их вычислительная сложность. Вне зависимости от решений, которые применяются в этих алгоритмах, ни один из них не позволит достичь адекватной скорости вычислений на мобильном устройстве из-за того, что эти алгоритмы являются однопоточными. Это означает, что каждый шаг алгоритма выполняется последовательно один за другим, а если брать в расчет полученное количество точек реального объекта и многократный рост количества операций при вставке каждой последующей точки в триангуляцию, то количество таких последовательных шагов будет крайне велико. Мощность центрального процессора (CPU) мобильного устройства не позволяет выполнять такие вычисления за приемлемое время. Таким образом, возникает необходимость в выборе многопоточного алгоритма, работающего на графическом процессоре (GPU), что позволит задействовать максимальное количество доступных вычислительных ресурсов iPhone. Наличие большого количества операций, которые не будут зависеть друг от друга, позволяет выполнять их параллельно в многопоточном режиме - на GPU. [4]

1.3 Выбор алгоритма 3D триангуляции Делоне на GPU

В настоящее время существует четыре алгоритма 3D триангуляции Делоне на GPU, описанных в [5]: gFlip3D, gStar4D, gDel3D, gReg3D.

Многопоточный алгоритм gFlip3D был создан из однопоточного классического алгоритма 3D триангуляции Делоне. Его суть в том, что была распараллелена вставка точек в триангуляцию, и распараллелены последующие после вставки точек флипы, направленные на восстановление условия Делоне для граней новообразованных тетраэдров. Однако результатом работы алгоритма является не полная Делоне триангуляция, а лишь близкая к ней. Такой результат объясняется тем, что при параллельном флиппинге с малой долей вероятности возникают неудовлетворяющие условию Делоне конфигурации тетраэдров, которые к тому же никак нельзя исправить флиппингом (unflippable конфигурации), но результат все равно является внушительным, поскольку лишь менее 0,05% граней не являются локально Делоне. Тем не менее, этот алгоритм принято считать полноценным алгоритмом 3D триангуляции Делоне.

Алгоритм gStar4D основывается на распараллеленном построении цифровой диаграммы Вороного, построенной на наборе входных точек. Цифровая диаграмма Вороного в трехмерном пространстве не может быть преобразована в 3D триангуляцию Делоне, которая является геометрически или топологически верной, хотя в двухмерном пространстве это сделать возможно. Вместо этого алгоритм gStar4D использует информацию о соседних точках, доступную на цифровой диаграмме Вороного. Информация о соседстве необходима для многопоточного создания звезд каждой вершины, поднятой до 4D. Применение подхода Star splaying, который также выполняется параллельно, приводит к окончательному завершению построения 3D триангуляции Делоне, полностью реализованной на GPU.

Алгоритм gDel3D состоит из двух частей. В первой части, исполняемой на GPU, выполняется алгоритм gFlip3D, результатом которого является около-Делоне триангуляция. Вторая же часть алгоритма gDel3D, так же, как и в алгоритме gStar4D, использует подход Star splaying, способный исправить возникшие после первой части нефлипабельные конфигурации тетраэдров, для получения конечной 3D триангуляции Делоне. Однако на этом шаге алгоритм выполняется последовательно на CPU, что не приводит к потере эффективности в силу малого количества операций.

Алгоритм gReg3D представляет собой немного переработанный алгоритм gStar4D. Первые два этапа алгоритма такие же, как в gStar4D, и выполняются с весом входных точек, равным нулю. В остальной части алгоритма используются четырехмерные ориентационные тесты, учитывающие вес точек. Создание звезд также похоже на создание в gStar4D с одним исключением, состоящим в изменении поведения вставляемых в звезду точек. Таким образом, будет построена 3D триангуляция Делоне, полностью вычисленная на графическом процессоре.

Алгоритмы gStar4D и gReg3D, основой которых является построение не особо предпочтительной для реализации 3D триангуляции Делоне цифровой диаграммы Вороного, уступают по скорости алгоритмам gFlip3D и gDel3D. Таким образом, встает выбор между двумя алгоритмами: gFlip3D и gDel3D. Несмотря на то, что результатом gFlip3D является около Делоне триангуляция, где лишь менее 0,05% граней не являются локально Делоне, этот алгоритм намного предпочтительнее gDel3D за счет того, что во втором алгоритме неоправданной сложностью является использование подхода Star splaying. Данный подход использует гиперплоскость и поднятые до четырехмерного пространства вершины, что позволяет облегчить количество необходимых вычислений, чем если бы они производились в трехмерном пространстве, но усложняет понимание и визуальное восприятие алгоритма и значительно усложняет его реализацию и отладку. Таким образом, gDel3D является намного более сложным в реализации, однако итоговый результат не слишком будет отличаться от результата, полученного с помощью алгоритма gFlip3D. И при этом стоит заметить, что разница в сложности реализации этих алгоритмов абсолютно несопоставима с разницей в получаемых с помощью них результатов. Поэтому было принято решение выбрать для реализации алгоритм gFlip3D, так как для создания 3D модели объекта нет необходимости избавляться от этих 0,05% локально не Делоне граней из-за того, что большая часть полученной триангуляции и ее структура нас не интересует - важна лишь оболочка полученной триангуцляции.



Выводы по главе

В первой главе был проведен обзор и анализ iOS приложений для построения 3D моделей реальных объектов - аналогов по основной выполняемой функции приложения, но не по способу создания 3D модели объекта - применения алгоритма 3D триангуляции Делоне, указанной в теме ВКР. Также была описана проблема вычислительной мощности смартфона и сделан вывод о том, что алгоритм триангуляции Делоне должен быть реализован на графическом процессоре. Помимо этого, были рассмотрены и проанализированы существующие алгоритмы 3D триангуляции Делоне, работающие на GPU; обоснован выбор алгоритма gFlip3D.

В следующей главе будет описан способ получения облака точек и подробно описаны шаги алгоритма gFlip3D.



Глава 2. Описание алгоритма и логики реализации основного функционала приложения

2.1 Получение облака точек реального объекта

Для получения облака точек объекта, которое будет триангулировано, используется фреймворк ARKit, являющийся частью операционной системы iOS, начиная с версии 11.0. ARKit реализует функционал дополненной реальности (AR - Augmented Reality). ARKit 2.0, который поддерживается, начиная с версии iOS 12.0, позволяет получать информацию об облаке точек пространства, которое видимо камерой iPhone в текущий момент времени. ARKit использует эти точки для создания карты окружающего мира, определения плоскостей, а также вычисления положения и ориентации устройства относительно видимого камерой окружающего пространства. Таким образом, используя функционал фреймворка ARKit 2.0, можно получить облако точек конкретного объекта и далее построить на этих точках 3D триангуляцию Делоне по алгоритму gFlip3D. Реализация получения облака точек подробнее описана в Главе 3.

2.2 Тест ориентации и тест на нахождение точки в сфере

Алгоритм gFlip3D использует два основных теста, описанные в [7] - тест ориентации и тест на нахождение точки в сфере. Оба этих теста могут быть реализованы как вычисление определителя матрицы. Тест ориентации четырех точек a, b, c, d (1) проверяет взаимное расположение точки d и плоскости, проходящей через точки a, b, c.

(1)



,

где det - определитель матрицы.

Если результат теста ориентации (a, b, c, d) положительный, то точка d лежит выше плоскости abc, а если отрицательный - ниже. Если результат равен нулю, d лежит на этой плоскости.

Тест на нахождение точки в сфере (2) вычисляется следующим образом:

(2)

Если результат теста на нахождение точки e в сфере, проходящей через точки a, b, c, d, отрицательный, то точка e лежит вне сферы, если положительный - внутри. Если результат равен нулю, то е лежит на поверхности сферы.

Тест на нахождение точки в сфере используется алгоритмом для проверки выполнения условия Делоне для двух соседних тетраэдров.

Эти тесты на вычисление детерминанта относительно надежны, однако существует две потенциальные проблемы, которые маловероятны, но не исключены.

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

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

2.3 Описание gFlip3D

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

На рис. 3 кратко описаны шаги алгоритма gFlip3D. Процедура PointInsert выполняет параллельную вставку точек в триангуляцию, а процедура FlipTri выполняет параллельный флиппинг модифицированной после вставки точек триангуляции. Процедура PointInsert повторяется до тех пор, пока в наборе всех точек S не останется больше точек, которые не были вставлены. Процедура FlipTri выполняет многократные циклы флиппинга до тех пор, пока не останется больше флипов, которые могли бы быть исполнены. Результатом работы алгоритма является триангуляция T, очень близкая к Делоне. Мы рассмотрим детали алгоритма в этом разделе и детали реализации в следующих разделах.



Рисунок 3. Алгоритм gFlip3D [5]

Параллельная вставка точек

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

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

Параллельное обновление соседства между тетраэдрами имеет некоторые нюансы, о них мы поговорим в Разделе 2.3.1.2.

Параллельный флиппинг

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

2.3.1 Параллельная вставка точек

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

2.3.1.1 Выбор точки для вставки

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

Связь точки с содержащим ее тетраэдром

Каждая невставленная точка должна знать, в каком тетраэдре она находится. Для этого параллельно, в количество потоков равное , где k - количество невставленных точек и n - количество тетраэдров в триангуляции, производится 8 тестов ориентации для каждой точки с каждым тетраэдром. Пусть p - невставленная точка, а abcd - тетраэдр, для которого проверяется, содержит он точку p или нет. Производятся следующие тесты ориентации: bcd с p и a, acd с p и b, abd с p и c, abc с p и d. Считается, что грань видна из точки p, если p и вторая точка, с которой производится тест ориентации с этой же гранью, лежат по разные стороны от этой грани, иначе - грань не видна из точки p. Если точка p лежит с той же стороны каждой грани, что и четвертая точка тетраэдра, не входящая в эту грань, то p лежит внутри тетраэдра, в противном случае - вне. Иначе говоря, если из точки p не видна ни одна лицевая грань тетраэдра abcd, то она лежит внутри него.

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

Зачем выбирать только одну точку?

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

Какую точку выбрать?

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

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

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

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

Вычисление расстояния

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

Выбор точки

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

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

2.3.1.2 Вставка точки

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

Разделение тетраэдров

Каждый тетраэдр вставкой точки в него разделяется на четыре новых тетраэдра. Этот процесс осуществляется параллельно, по одному потоку на тетраэдр, в который вставляется точка. Для этого считываем исходный тетраэдр t₀ и его точку для вставки и генерируем четыре новых тетраэдра {t₁, t₂, t₃, t₄}, которые создаются путем флипа 1-4.

На рис. 4 показан тетраэдр abcd и точка p, которая вставляется в него путем разделения исходного тетраэдра на новые. Получившиеся четыре тетраэдра - abcp, abdp, adcp и bcdp.



Рисунок 4. Флип 1-4 вставляет точку p в тетраэдр abcd

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

Обновление смежностей для каждого тетраэдра

После того, как параллельно по одной точке было вставлено в каждый подходящий тетраэдр, новообразованные тетраэдры могут не удовлетворять условию Делоне. Нужно отметить, что один тетраэдр имеет четыре грани, следовательно, имеет четыре соседних тетраэдра, по одному на каждую грань. Итак, поскольку следующим шагом алгоритма идет проверка новых тетраэдров на выполнение условия Делоне и в противном случае выполнение флипа, то перед этим каждый тетраэдр должен знать его четырех соседей, чтобы понимать, с кем именно нужно выполнить проверку и произвести флип. Для определения смежностей необходимо параллельно, в количестве потоков равном n², где n - количество существующих тетраэдров, проверять, являются ли каждый тетраэдр триангуляции с каждым смежными, то есть имеют ли они три общие вершины. Если имеют, то поток записывает информацию о найденном соседе в обрабатываемый тетраэдр.

2.3.2 Параллельный флиппинг

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

2.3.2.1 Проверка выполнения условия Делоне

Новые тетраэдры, созданные вставкой точки в последней итерации или флипом, должны быть проверены на выполнение условия Делоне. Такие тетраэдры называются активными тетраэдрами. В [8] было доказано, что достаточно проверить, являются ли грани, противолежащие вставленной точке p, локально Делоне. Также необходимо проверить все грани, противолежащие точке р, вновь созданных после флипа тетраэдров.

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

Рисунок 5. а) Успех и б) неудача теста на нахождение точки e в сфере, описанной около abcd

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

2.3.2.2 Проверка на наличие конфигурации тетраэдров для флипа

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

Конфигурация для флипа 2-3

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

Например, на рис. 6 поток, обрабатывающий тетраэдр abcd, обнаружил, что грань abc не является локально Делоне, потому что точка e соседнего по грани abc тетраэдра находится внутри описанной сферы около тетраэдра abcd. Перед тем, как делать флип 2-3, поток должен проверить, является ли шестигранник, образованный склеиванием abcd и abce, выпуклым.



Рисунок 6. a) Конфигурация для флипа 2-3 и б) результат выполнения флипа 2-3

Для этого достаточно определить, сколько лицевых граней тетраэдра abcd видно из точки e. Чтобы это сделать, нужно проверить, лежит ли точка тетраэдра abcd по разные стороны от грани, противолежащей этой точке, с точкой e (в таком случае грань видна из точки e). Для этого нужно выполнить тесты ориентации abc с d и e, bcd с a и e, acd с b и e, abd с c и e. Если по итогам теста видна только одна грань, то флип 2-3 может быть выполнен. В случае на риc. 6, единственной гранью, видной из точки e, является общая грань - abc. Таким образом, шестигранник aebcd является выпуклым и может быть выполнен флип 2-3, если ни один из тетраэдров, созданных в результате флипа, не будет плоским. Чтобы проверить, является ли тетраэдр плоским, нужно провести тест ориентации с любой его точкой и противолежащей ей гранью. Если тест вернет значение 0, то тетраэдр - плоский.

Конфигурация для флипа 3-2

Конфигурация с флипом 3-2 требует трех тетраэдров, разделяющих одно общее ребро и образующих выпуклый многогранник. Это общее ребро должно быть невыпуклым ребром шестигранника aebcd. Например, на рис. 7, если общее ребро bc является невыпуклым для abcd и abce, то для флипа 3-2 должен существовать тетраэдр bcde.



Рисунок 7. a) Конфигурация для флипа 3-2 и б) результат выполнения флипа 3-2

Существование трех тетраэдров, имеющих общее ребро, можно проверить с помощью информации о смежности между этими тетраэдрами. Смежные тетраэдры, противолежащие точке а, у тетраэдров abcd и abce на рис. 7 являются одним и тем же тетраэдром. Если обнаружено, что тетраэдры, противолежащие a, не являются одним общим тетраэдром, то это означает, что существует более трех тетраэдров, имеющих общее ребро bc, и флип 3-2 невозможен. Этот случай показан на рис. 8, где шесть тетраэдров имеют общее ребро bc. Отметим, что конфигурация тетраэдров abcd и abce на этом рисунке называется unflippable.

Рисунок 8. Unflippable конфигурация aebcd



Кроме того, многогранник, образованный склеиванием трех тетраэдров, должен быть выпуклым. Так же, как и в конфигурации для флипа 2-3, через 8 тестов ориентации проверяется, сколько граней тетраэдра abcd видно из точки e. Если видно ровно две грани, то флип 3-2 может быть выполнен при условии, что после флипа не образуется плоских тетраэдров. Также заметим, что если из точки e видно больше двух граней, то в таком случае не существует конфигураций тетраэдров, подходящих для выполнения любого вида двустороннего флипа.

Конфликты потоков при флипе

Как объяснялось ранее, после того как были выявлены активные тетраэдры, для которых не выполнилось условие Делоне, для них параллельно начинается поиск конфигураций для флипа 2-3 или 3-2. Таким образом, для каждого тетраэдра триангуляции становится известна конфигурация для флипа, в которой он участвует. Если тетраэдр не участвует ни в одной конфигурации, то его конфигурация является пустой. Однако сразу после того, как все подходящие конфигурации были найдены, нельзя приступать к параллельному выполнению флипов из-за возможных конфликтов потоков. Этому есть две возможные причины: во-первых, один тетраэдр может участвовать в более чем одной различной найденной конфигурации флипа, а во-вторых, потоки всех тетраэдров, участвующих в одной конфигурации, могут попытаться выполнить флип, который нужно выполнить всего один раз. Для разрешения этих конфликтов последовательно перебираются все тетраэдры, для которых была найдена непустая конфигурация, т. е. фактически перебираются найденные конфигурации. При переборе текущий тетраэдр и тетраэдр(ы) его конфигурации помечаются как используемые. Если какой-то из тетраэдров очередной конфигурации уже был помечен как используемый, то данная конфигурация для текущего тетраэдра заменяется пустой.

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

2.3.2.3 Параллельное выполнение флиппинга

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

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

При выполнении флипа новообразованные тетраэдры друг с другом будут удовлетворять условию Делоне. Однако их необщие грани могут быть локально не Делоне. Таким образом, новые тетраэдры помечаются как активные тетраэдры. И шаги алгоритма, такие как: проверка выполнения условия Делоне, поиск конфигураций тетраэдров для флипа, устранение конфликтов флипов и непосредственно выполнение самих флипов, будут выполняться до тех пор, пока триангуляция не станет Делоне или около Делоне. Заметим, что триангуляция около Делоне отличается от полной лишь наличием unflippable конфигураций, которые нельзя исправить с помощью флипа 2-3 и 3-2.

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

Выводы по главе

Во второй главе был описан способ получения облака точек - с помощью фреймворка ARKit 2.0, а также подробно описаны шаги алгоритма gFlip3D 3D триангуляции Делоне.

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



Глава 3. Технологии, инструменты разработки и детали реализации приложения

3.1 Инструменты разработки

В процессе разработки были использованы следующие инструменты:

· “Unity” - среда разработки игрового кроссплатформенного движка

· “Visual Studio for macOS” использовалась для написания кода на C# и вычислительного шейдера на HLSL.

· “Xcode” использовался только для сборки приложения под iPhone, проект для Xcode генерирует Unity.

3.2 Использование GPU

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

Проще говоря, вычислительный шейдер -- это программа, выполняемая на графическом процессоре, которая не должна работать с графическими данными. Она работает внутри пространства памяти OpenGL, DirectX или, в случае iOS устройства - Metal, и может оперировать данными в общих для всех потоков выполнения буферах.

Стоит отметить, что вычислительные шейдеры в Unity пишутся на языке HLSL, но Unity интерпретирует написанный на этом языке код в код шейдера на нативном для iOS устройств языке - Metal Shading Language [9].

...