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