Разработка и исследование методов определения видимости полигонов в реальном времени при отрисовке трехмерных объектов

• Автор: Надолинский, Никита Александрович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Таганрог
• Количество страниц: 213 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ В РЕАЛЬНОМ ВРЕМЕНИ ПРИ ОТРИСОВКЕ ТРЕХМЕРНЫХ ОБЪЕКТОВ.

1.1. Анализ характеристик методов удаления невидимых поверхностей

1.1.1. Использование когерентных связей.

1.1.2. Соотношение визуализируемой части геометрии к общей

1.1.3. Количество перекрытий

1.2. Методы оптимизации

1.2.1. Отсечение нелицевых граней.

1.2.2. Ограничивающие тела

1.2.3. Разбиение пространства 1.

1.2.4. Иерархические структуры
1.3. Удаление невидимых поверхностей.
1.3.1. Метод трассировки лучей
1.3.2. Метод буфера.
1.3.3. Сортировка по глубине. Метод художника.
1.3.4. Метод построчного сканирования.
1.3.5. Метод Варнока
1.5. Выводы
2. ОРГАНИЗАЦИЯ ПОЛИГОНОВ В ОБЪЕКТНОМ ПРОСТРАНСТВЕ
2.1. Описание метода двоичного разбиения пространства
2.2. Построение дерева на основе пространственного разбиения граней
2.3. Механизм обхода двоичного дерева полигонов
2.4. Пространственное отсечение задних поверхностей и групп поверхностей .
2.6. Механизм отображения двоичного дерева полигонов.
2.7. Выводы
3. ОРГАНИЗАЦИЯ ПОЛИГОНОВ В ОТОБРАЖАЕМОМ ПРОСТРАНСТВЕ.
3.1. Описание метода двухпроходной растеризации на основе иерархического тайлинга полигонов
3.2. Механизм бинарных масок.
3.3. Механизм отсечений по границам экрана.
3.4. Механизм растеризации
3.5. Механизм текстурирования.
3.6. Выводы.
4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МОДЕЛИ СИСТЕМЫ ОПРЕДЕЛЕНИЯ ВИДИМОСТИ ПОЛИГОНОВ, ЕЕ ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ И СРАВНЕНИЕ С АНАЛОГАМИ.
4.1. Программные оптимизации
4.2. Экспериментальное исследование программной модели, сравнение с аналогами.
4.3. Выводы.
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ


Простейший вариант непрерывного подхода заключается в сравнении каждого объекта со всеми остальными, что дает временные затраты, пропорциональные и2, где п - количество объектов в сцене []. Однако следует иметь в виду, что непрерывные методы, как правило, достаточно сложны. Методы второго класса (point-sampling methods) дают приближенное решение задачи видимости, определяя видимость только в некотором наборе точек картинной плоскости - в точках растровой решетки. Они очень сильно привязаны к растровым свойствам картинной плоскости и фактически заключаются в определении для каждого пиксела той грани, которая является ближайшей к нему вдоль направления проектирования. Изменение разрешения приводит к необходимости полного перерасчета всего изображения []. Простейший вариант дискретного метода имеет временные затраты порядка С(п), где С - общее количество пикселов экрана, а п - количество объектов. Всем методам второго класса традиционно свойственны ошибки дискретизации (aliasing artifacts). Однако, как правило, дискретные методы отличаются известной простотой. Кроме этого существует довольно большое количество смешанных методов, использующих работу как в объектном пространстве, так и в картинной плоскости, методы, выполняющие часть работы с непрерывными данными, а часть - с дискретными [,,,]. Большинство алгоритмов удаления невидимых граней и поверхностей тесно связано с различными методами сортировки. Некоторые алгоритмы проводят сортировку явно, в некоторых она присутствует в скрытом виде. Приближенные методы отличаются < друг от друга фактически только порядком и способом проведения сортировки. Очень распространенной структурой данных в задачах удаления невидимых линий и поверхностей являются различные типы деревьев -двоичные (Binarytrees), четвертичные (Quadtrees), восьмеричные (Octtrees) и ДР [,]. Методы, практически применяющиеся в настоящее время, в большинстве являются комбинациями ряда простейших алгоритмов, неся в себе целый ряд разного рода оптимизаций. Крайне важная роль в повышении эффективности методов удаления невидимых линий и граней отводится использованию когерентности (от английского coherence - связность). Р, то скорее всего соседние пиксели также соответствуют точкам той же грани (рис. Рис. Рис. Использование когерентности позволяет заметно сократить количество возникающих проверок и заметно повысить быстродействие метода. В настоящее время ни один из применяемых на практике методов не использует все 3 типа описанных когерентных связей. Большинство методов использует в основном один из типов когерентности. Соотношение визуализируемой части геометрии к общей. Показателем быстроты того или иного метода является соотношение визуализируемой части геометрии к общей геометрии сцены [,,]. Результатом работы будет набор полигонов, включающий в себя всю видимую геометрию и, по возможности, небольшое количество невидимой геометрии. Целью методов удаления перекрываемых поверхностей является сведение стоимости визуализации сцены к сложности видимой части сцены. В идеальном случае, алгоритм должен быть чувствительным к выводу - то есть время его работы должно быть пропорционально объему видимой геометрии. Количество перекрытий - важный параметр, характеризующий сколько невидимых (но отображенных на экране) полигонов приходится на один видимый полигон в кадре [,,]. Очевидно, что чем меньше невидимых полигонов приходится на один видимый, тем эффективнее работает метод. Здесь следует учитывать топологию геометрии сцены. Количество перекрытий в открытых сценах практически всегда составляет до 3-х полигонов в независимости от используемого метода. В закрытых сценах количество перекрытий может достигать десятков, сотен и даже тысяч. Методы оптимизации. Отсечение нелицевых граней. Процесс отсечения нелицевых граней в компьютерной графике называется backface culling [, ]. Рассмотрим многогранник, для каждой грани которого задан единичный вектор внешней нормали (рис. Несложно заметить, что если вектор нормали грани п составляет с вектором 1, задающим направление проектирования, тупой угол (вектор нормали направлен от наблюдателя), то эта грань заведомо не может быть видна (рис.