Системы упрощения триангуляционной сетки для методов трехмерной реконструкции

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Дальневосточный федеральный университет»

 

ШКОЛА ЕСТЕСТВЕННЫХ НАУК

 

Кафедра прикладной математики, механики, управления

и программного обеспечения

Тимошишина Алина Дмитриевна

 

 

СИСТЕМЫ УПРОЩЕНИЯ ТРИАНГУЛЯЦИОННОЙ СЕТКИ ДЛЯ МЕТОДОВ ТРЕХМЕРНОЙ РЕКОНСТРУКЦИИ

 

ДИПЛОМНАЯ РАБОТА по основной образовательной программе подготовки специалистов по направлению 010400 – прикладная математика и информатика

 

 

Студент гр. Б8426         ________________                                                                      (подпись) Научный руководитель ____ к.т.н.       ____                                                                     (должность,  ученое звание) _______________       _____А.П.Кудряшов_               (подпись)                                               (и.о.ф) «______»________________ 20    г.
Защищена в ГАК с оценкой ______________   Секретарь ГАК ____________     _________________            подпись                              И.О.Фамилия   «_____» ________________ 20   г.		«Допустить к защите» Заведующий кафедрой _д.ф.-м.н., профессор                                                                        ( ученое звание) ______________    ____А.А. Буренин_______               (подпись)                                                (и.о.ф) «______»________________ 20   г

 

 

 

г. Владивосток

20  _

 

Оглавление

 

0. Введение…………………………………………………………….………….2
1. Глава 1. Обзор, основные положения………………………..……..….…....6

1.1. Анализ проблемы………………………………………………….….…..6

1.2. Особенности и проблемы триангуляции………………………….…..11

1.3. Выводы по главе…………………………………………………….…...14

2. Глава 2. Рассмотрение существующих методов оптимизации……..……16

2.1. Упрощение триангуляции…………………………………………..…..16

1. Алгоритмы триангуляции……………………………………….....16
2. Структуры данных триангуляции………………………………....21

2.2. Метод квадратичной ошибки Гарланда и Хекберта…………………..24

2.2.1. Основной алгоритм……..……………………………………….....24

2.2.2. Квадратичная ошибка…..……………………………………….....25

2.2.3. Интерпретация квадриков……………………………………........27

2.3. Выводы по главе………………………………………………………...28

0. Глава 3. Практическая часть…………………………………………………29

3.1. Вводная часть…………………………………………………………….29

 3.2. Постановка задачи……………………………………………................29

 3.3. Оптимизация данных…………………………….………….………….31

 3.4. Методика упрощения триангуляционной сетки……………….…….33

 3.5. Пример оптимизации и упрощения…………………………….……..37

3.6. Выводы по главе………………………………………………….……..40

1. Заключение…………………………….….……………………..….….…….41
2. Литература……………………………………………………………………42

 

 

 

 

 

 

 

 

Введение

 

Актуальность работы

 

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

 

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

 

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

 

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

 

Цель работы

 

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

 

Для достижения указанной цели решаются следующие задачи:

 

• Анализ существующих методов и алгоритмов оптимизации 

     триангуляционной  сетки

•  Разработка методики структурирования  и оптимизации 

     полученных  данных сетки

•  Разработка методики упрощения ранее структурированной сетки

     полигонального  объекта

•  Программная реализация методов и алгоритмов

 

 

 

 

 

Структура и объём работы

 

Приведённая работа состоит из введения, 3 глав, заключения и списка литературы. Содержание работы изложено на 38 страницах. Список литературы включает 15 наименований. В работе содержится 18 рисунков и 2 таблицы.

 

Глава 1. ОБЗОР, ОСНОВНЫЕ ПОЛОЖЕНИЯ, ТРЕБОВАНИЯ

 

1.1 Анализ проблемы

 

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

 

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

 

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

 

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

 

 

 

Рис. 1.1. Общая схема пассивной реконструкции трехмерных объектов

 

Рассмотрим пункты более подробно.

 

 

 

Получение изображений

 

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

 

Отслеживание точечных особенностей

 

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

 

Калибровка изображений

 

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

 

Вычисление трехмерных координат

 

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

 

 

Триангуляция

 

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

 

Рис. 1.2. Триангуляция 100 точек на плоскости

 

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

 

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

 

 

 

 

Построение трехмерной модели

 

Полученная трехмерная модель обычно представляется в виде триангуляционной сетки[13]. Но существуют также и другие способы представления, например: восстановленными точечными особенностями в виде вокселей в трехмерном пространстве сцены, сгруппированными восстановленными трехмерными линиям или может быть интерактивно смоделирована полуавтоматическим подбором геометрических примитивов (параллелепипеды, плоскости, пирамиды и т.д.). Но, поскольку эти способы построения выходят за рамки задачи, решаемой в данной работе, здесь они не рассматриваются.

 

Текстурирование

 

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

 

1.2 Особенности и проблемы триангуляции

 

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

 

 

Рис. 1.3. Объект городской сцены: 154,325 полигонов.

 

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

 

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

 

 

а)                б)

Рис. 1.4.  а) ~700 полигонов;  б) 24 полигона

 

Переход между уровнями детальности можно пронаблюдать на Рис 4. Хоть исходный объект (Рис. 1.4.а) и имеет неровную поверхность, можно заметить, что, в общем, он представляет собой куб. Поэтому, целесообразней будет понизить уровень детальности (Рис. 1.4.б)

 

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

 

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

 

Таким образом, мы приходим к следующим проблемам триангуляции:

 

• Неструктурированность сетки
• Огромное количество полигонов
• Ненужная детализация

 

 

 

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. РАССМОТРЕНИЕ СУЩЕСТВУЮЩИХ МЕТОДОВ ОПТИМИЗАЦИИ

 

2.1 Упрощение триангуляции

 

2.1.1. Методы упрощения

 

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

 

Существуют две стратегии алгоритмов упрощения. Алгоритмы стратегии «снизу-вверх» действуют следующим образом: на предварительном этапе рассчитывается потенциальная ошибка удаления/коллапса примитивов с образованием очереди, затем итеративно удаляют или коллапсируют примитивы с одновременным пересчетом потенциальных ошибок и перестроением очереди. Алгоритм работает до тех пор, пока не будет достигнуто требуемое разрешение.

 

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

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

 

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

 

Ниже представлены некоторые методы упрощения:

 

1. Слияние компланарных граней.

 

Компланарные или почти компланарные грани сливаются в один полигон, который затем ретриангулируется меньшим количеством граней.

 

2. Стягивание ребра (Рис.2.1.).

 

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

 

 

               Рис. 2.1. Стягивание ребра

 

 

 

3. Использование ограничивающих  поверхностей (Рис.2.2.).

 

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

 

 

                Рис.2.2. Ограничивающие поверхности

 

4. Контролируемое удаление вершин или граней (Рис.2.3.).

 

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

                Рис. 2.3. Удаление вершин

 

 

5. Перестроение.

 

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

 

6. Кластеризация вершин (Рис.2.4.).

 

Вершины группируются в кластеры, для каждого кластера рассчитывается новая представительная вершина.

 

               Рис.2.4. Кластеризация вершин.

 

 

 

7. Упрощение через промежуточное  иерархическое представление.

 

 Представление промежуточного дерева октантов [14] может быть адаптировано до автоматической генерации упрощенных представлений, потому что дерево октантов может быть очищено на различных уровнях и конвертировано в граничное (упрощенное) представление.

 

 

Критерий оптимальности

 

Важным моментом методов удаления является локальный геометрический критерий оптимальности. Ниже представлены некоторые критерии:

 

1. Ошибка приближения  точек.

 

Два кусочно-линейных объекта Mi и Mj являются ε-аппроксимацией друг друга, если каждая точка Mi находится не дальше, чем ε, от некоторой точки Mj и наоборот.

 

2. Разность угла.

 

Разность инцидентных углов и развернутого угла. Применяется в основном в методах, сохраняющих форму меша. Также существует множество производных критериев [15].

 

3. Классификация критических  точек на основе анализа Гессиана.

 

Применяется в основном в методах, сохраняющих топологию.

 

 

Оценка качества

 

Для оценки качества полученной при упрощении триангуляции применяют глобальные геометрические критерии оптимальности:

 

1. Ошибка приближения  основанная на ε -аппроксимации.

2. Ошибка приближения, основанная на среднеквадратичном отклонении.

3. Объем разности между  исходной и упрощенной триангуляцией.

 

Наиболее качественным для визуализации является второй критерий.

 

2.1.2. Структуры  данных триангуляции

 

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

 

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

 

1. Узлы с соседями (Рис.2.5.а.).

 

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

 

2. Двойные ребра (Рис.2.5.б.).

 

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

 

3. Узлы, ребра и треугольники (Рис.2.5.в).

 

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

 

4. Узлы и треугольники (Рис.2.5.г.).

 

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

а)

б)

в)

г)

 

Рис.2.5. Структуры данных: а) узлы с соседями;  б) двойные ребра;                 в) узлы, ребра и треугольники;  г) узлы и треугольники.

 

 

2.2 Метод квадратичной ошибки Гарланда и Хекберта

 

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

 

2.2.1 Основной алгоритм

 

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

 

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

1. Cдвинуть вершины V1 и V2 в позицию V

2. Заменить все примитивы V2 на V1

3. Удалить V2 и все вырождающиеся ребра.

 

Рис. 2.6. Сокращение ребра

 

Рис.2.6. иллюстрирует результат единичного сокращения ребра.

 

2.2.2. Квадратичная  ошибка

 

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