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

 

Каждый полигон представляет собой плоскость, которая удовлетворяет уравнению , где - единичный вектор нормали, а d – постоянная. Квадрат расстояния от вершины к этой плоскости будет:

 

Это квадратичная форма плюс линейный член плюс константа. Мы можем легко представить D2 , используя квадрик Q:

 

 

 

 

Требуется десять чисел, чтобы заполнить симметричную 3х3 матрицу А, 3-вектор b и скалярную величину С.

 

Добавление квадрика может быть задано покомпонентно:

 

,

где   .

 

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

 

 

 

 

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

 

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

 

Рис.2.7. Результат упрощения модели кролика. Зеленные центрированные вокруг каждой вершины эллипсоиды – изоповерхности квадриков

 

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

Глава 3. ПРАКТИЧЕСКАЯ ЧАСТЬ

 

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

 

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

 

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

 

Исходные данные сетки мы получаем из файла «3d_structure.x». В интересующих нас известных величинах  есть: количество вершин, три координаты для каждой вершины, количество треугольников, порядковые номера точек, образующих треугольник, сгруппированные по три. Организация записи этих данных в файле формата «.х» проиллюстрирована на Рис.3.1.

 

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

 

Рис.3.1. Организация данных в .х файле

 

Следовательно, необходимо оптимизировать исходные данные и перезаписать файл.

 

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

 

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

 

Наглядный пример исходной нумеровки вершин проиллюстрирован на Рис.3.2. При применяемой системе нумерации, количество вершин на рисунке будет равно 18, хотя на самом деле вершин здесь всего 7.

 

 

Рис.3.2. Нумеровка вершин в исходных данных

 

 

Для экономии времени обработки данных и снижения веса файла целесообразнее будет удалить повторы и сделать правильную нумерацию (Рис. 3.3)

Рис.3.3. Корректная нумерация вершин.

 

Алгоритм удаления одинаковых вершин довольно примитивен. Запоминаем вершину (её номер - i), пробегаем по всем ранее не проверенным вершинам (номер j) и сравниваем их координаты с координатами i-вершины. Если координаты совпали, то удаляем j-вершину. После удаления каждой j-вершины, нужно также перезаписать номер j на номер i в том треугольнике, куда входила эта j-вершина. После всех преобразований, наши исходные данные (Рис.3.4.а.1, Рис.3.4.а.2) примут новый вид (Рис.3.4.б.1, Рис.3.4.б.2)

 

 

 

     а.1)              б.1)

    а.2)                            б.2)                 .

 

Рис.3.4. Преобразование данных

 

Рисунок 3.4.б.1. демонстрирует скорректированную запись вершин, а рисунок 3.4.б.2. скорректированную запись треугольников.

 

 

 

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

 

Получив корректные данные, мы можем перейти к упрощению триангуляции.

 

Создаем структуры triangle и point для треугольников и точек соответственно (Рис.3.5.). Triangle – вектор номеров треугольников. Каждый треугольник содержит три номера вершин, которые в него входят. Point – вектор номеров вершин. Каждая вершина содержит три вещественных числа – её координаты. Считываем данные из файла и записываем их в структуры.

 

Рис.3.5. Структуры для треугольников и вершин.

 

 

Далее создаем массив, который будет хранить информацию о полигонах (Рис.3.6.).

 

 

 

Рис.3.6.Массив для полигонов.

 

Строка j=0: 0-отмечаем, что полигон не удален, 1-отмечаем, что полигон не является линией (вырожденный), 2 – отмечаем, что у полигона нет соседей линий. Строка j=1: для номеров соседей 1 порядка – полигонов, имеющих 2 общие точки с данным. Строка j=2: для соседей 2 порядка – полигонов, имеющих одну общую точку с данным.

 

Далее осуществляется поиск соседей для полигонов по следующему алгоритму:

1. Берем i треугольник.

2. Проверяем, не является ли он линией.

3. Берем j треугольник

4. Проверяем, не является  ли j треугольник линией.

5. Проверяем, не совпадает  ли какая-нибудь из координат i треугольника с координатами j треугольника. Если совпала 1 или 2 координаты, то присваиваем j треугольнику статус соседа 2 или 1 порядка соответственно.

 

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

 

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

Тогда строим определитель

 

 

 

Раскладываем его:

 

 

 

 

 

 

Обозначим разности в скобках, как x0, y0, z0 соответственно :

 

 

 

 

 

Тогда уравнение плоскости Ax+Bx+Cx+D=0 у нас будет с коэффициентами:

 

 

 

 

 

 

 

Тогда алгоритм поиска и удаления следующий:

1. Берем i полигон.

2. Проверяем, не удален  ли он, не является ли он линией.

3. Считаем коэффициенты  плоскости полигона.

4. Считаем коэффициенты для плоскостей соседей 1 порядка(j полигон).

5. Считаем косинусы между плоскостями. Если критерий выполняется, переходим к удалению.

6. Проверяем соседей 1 порядка  у j полигона. (те же самые действия, что и в пунктах 4-5). Если критерий выполняется, то будем проверять, можно ли стягивать общее ребро у полигонов i и j.

7. Запоминаем совпавшие  номера общих соседей 2 порядка.

8. Повторяем пункты 4-5 для  i полигона и общих соседей 2 порядка. Если критерий выполняется, то будем стягивать общее ребро у полигонов i и j.

9. Считаем точку стягивания. Она будет посередине.

10. Меняем данные у соседей 1 порядка полигонов i и j.

     10.1. Вместо номеров i и j, ставим номера новых соседей.

     10.2. Меняем  координаты: вместо координат точек, лежавших на стягиваемом ребре, ставим координаты точки стягивания.

     10.3. Добавляем  новых соседей 2 порядка (взаимное  добавление).

11. Меняем данные у соседей 2 порядка полигонов i и j.

     11.1. Удаляем  у них номера i и j как соседей.

     11.2. Добавляем  номера новых соседей 2.

     11.3. Меняем  координату, лежащую на стягиваемом  ребре, на точку стягивания.

12. Помечаем i и j треугольники как удаленные.

 

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

 

Для проверки метода нам был дан такие объекты городской сцены, как отель Хёндай и близлежащие к нему дома (Рис3.7.). По исходным данным мы имеем 462975 вершин, образующих 154325 треугольников. После применения алгоритма оптимизации данных, вершин оказалось 82098. Т.е. количество записей вершин уменьшилось в 5.2 раза. Вес файла уменьшился с 43,4 Мб до 20,7 Мб, т.е. в 2,09 раз. После применения метода упрощения сетки, было сокращено порядка 60% полигонов – это чуть более 90000 треугольников. В итоге были получены примерно 60000 полигонов. Время, затрачиваемое на выполнение алгоритма сокращения сетки составило порядка 180 секунд.

Рис.3.7. Отель Хёндай

 

Сравнение с некоторыми существующими методами и алгоритмами.

 

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

 

 В таблице 3.1. представлены результаты (время) работы нескольких алгоритмов для 150000 вершин с сокращением полигонов на 70%. Первое значение для случайного равномерного распределения в параллелепипеде, второе значение для случайного распределения на полусфере

 

Алгоритм	Параллелепипед	Полусфера
Удаление  вершин	31	21
Коллапс ребер	7	48
Коллапс треугольников	42	36
Сокращение всех примитивов (снизу-вверх)	51	54
Сокращение всех примитивов (сверху-сниз)	16	420

 

 

Таблица 3.1. Время работы алгоритмов

 

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

 

Сравнение разработанного метода с методом Гарланда и Хекберта, произведено в таблице 3.2.

 

Алгоритм	Начальное количество полигонов	Полученное кол-во полигонов	Время (сек)
Гарланда  и Хекберта	1085634	20000	176
Разработанный	154325	61703	180

 

 

Таблица 3.2. Сравнение с алгоритмом Гарланда и Хекберта

 

Хоть время работы алгоритмов фактически одинаково, алгоритм Гарланда и Хекберта успел обработать в 7 раз больше начальных данных и сократить около 97% полигонов.

 

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

 

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

 

 

 

 

 

 

Заключение

 

В ходе выполнения дипломной работы:

 

1. Изучены и проанализированы существующие методы и алгоритмы упрощения триангуляционной сетки.

 

2. Разработан и программно реализован алгоритм оптимизации исходных данных сетки.

 

3. Разработан и программно реализован алгоритм упрощения триангуляции стягиванием ребер.

 

 

Области применения:

 

1. Моделирование рельефов по опорным точкам

 

2. Визуализация сложных поверхностей

 

 

Возможные дальнейшие направления:

 

1. Усовершенствование разработанного алгоритма

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

 

Литература

 

1. Галанин М.П., Щеглов  И.А. Разработка и реализация алгоритмов  трехмерной триангуляции сложных  пространственных областей: итерационные  методы. Препринт ИПМ им. М.В. Келдыша  РАН, 2006, в печати;