РЕФЕРАТ
ВВЕДЕНИЕ 3
Удаление невидимых линий и поверхностей 3
1 Алгоритмы, формирующие списки приоритетов 6
1.1 Алгоритм художника 6
1.2 Двоичное разбиение пространства (Binary Space Partitioning) 7
2 Реализация алгоритмов 11
2.1 Классы, используемые для решения задачи 11
2.2 Реализация алгоритма художника 12
2.3 Реализация двоичного разбиения пространства 13
2.3.1 Определение положения точки относительно плоскости 13
2.3.2 Определение положения полигона относительно плоскости 15
2.3.3 Рассечение полигона плоскостью 16
2.3.4 Выбор оптимальной разделяющей плоскости 17
2.3.5 Построение BSP-дерева 18
3 Сравнительный анализ алгоритмов 22
3.1 Сравнение алгоритмов по качеству полученных изображений . .. 22
3.1.1 Алгоритм художника 22
3.1.2 Двоичное разбиение пространства 24
3.1.3 Вывод 27
3.2 Сравнение алгоритмов по времени выполнения 27
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 30
ПРИЛОЖЕНИЕ А Листинг программы 31
Компьютерная графика - одно из популярных и наиболее развивающихся направлений в компьютерных науках. Популярность компьютерной графики обусловлена тем, что виртуальные среды предоставляют возможность моделировать ситуации и объекты, не беспокоясь о последствиях, стоимости и других параметрах, которые в реальной жизни либо недоступны, либо ограничены в объемах. Так, например, архитекторы могут строить модели домов, не прилагая больших усилий в черчении, пилоты могут учиться управлять самолетами без риска для жизни, биохимики могут моделировать сложные молекулярные структуры и изучать их, а существующие пользовательские взаимодействия, такие как вращение и масштабирование, используются для лучшего обзора и анализа структуры. Но, конечно, наибольшее распространение в области компьютерной графики получила разработка игр, как сфера, наиболее востребованная у множества конечных пользователей, поскольку не является узкоспециализированной и нацеленной только на определенную группу людей специалистов.
Однако, никаких графических приложений не было бы, если бы не было алгоритмов, позволяющих преобразовывать SD-графику для отображения в двухмерном пространстве и строить реалистичные изображения.
Удаление невидимых линий и поверхностей
Для построения реалистичного изображения нам необходимо знать какие грани являются видимыми, а какие скрыты от нас за другими, так появилась задача удаления невидимых линий и поверхностей. Необходимость определения видимости граней можно проиллюстрирована на рисунке 1. Здесь изображена реберная сцена куба, однако мы можем интерпретировать его положение по-разному, в зависимости от угла обзора и положения наблюдателя.
Сложность задачи привела к появлению большого числа различных способов ее решения. Большинство из них ориентированы на специализированные приложения. Однако наилучшего решения обшей задачи удаления невидимых линий и поверхностей не существует.
Рисунок 1 - Зависимость положения вида куба от угла обзора и положения наблюдателя
Для моделирования процессов в реальном времени требуются быстрые алгоритмы, с помощью которых можно достигнуть частоты видео 30 кадров в секунду. Для машинной мультипликации, требуются алгоритмы, которые могут генерировать сложные реалистические изображения с тенями, различными фактурами, прозрачностью, а также необходимо учитывать эффекты отражения и преломления цвета. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов.
Стоит заметить, что учет эффектов прозрачности, фактуры, отражения и прочего не входит в задачу удаления невидимых поверхностей, однако они могут быть встроены в эти алгоритмы.
Рассматриваемые нами алгоритмы можно классифицировать по способу выбора пространства в котором они работают. Выделяют три класса алгоритмов удаления невидимых линий и поверхностей.
Алгоритмы, работающие в объектном пространстве. Они работают в системе координат объектов и получают результаты, точность которых ограничена лишь точностью вычислений. В результате получаются хорошо масштабируемые изображения.
Алгоритмы, работающие в пространстве изображения (экрана). Такие алгоритмы работают в системе координат экрана, на котором объекты визуализируются, а значит точность вычислений ограничены разрешающей способностью экрана.
Алгоритмы, формирующие список приоритетов. Являются комбинацией предыдущих двух методов и работают путем определения элементов сцены по удаленности от наблюдателя. А далее объекты выводятся на экран от дальнего к ближнему.
В данной работе будут детально рассмотрены и реализованы алгоритмы, относящиеся к классу формирующих списки приоритетов, а именно: алгоритм художника, как самый элементарный и интуитивно понятный, и двоичное разбиение пространства (Binary Space Partition или BSP- дерево), считающийся точным и быстрым. В процессе их реализации будут выявлены их слабые и сильные стороны, а также проведен анализ и сравнение их скорости и точности.
Стоит заметить, что с момента появления первых игр от первого лица и до настоящего времени используется такое решение как двоичное разбиение пространства. Оно было впервые реализовано Джоном Кармаком при разработке движка Doom, использовавшегося в одноименной игре от первого лица. Это решение до сих пор так или иначе применяется в игровой индустрии, поскольку его применение значительно упрощает решение проблемы видимости, а предварительное построение дерева для статичной сцены уменьшает в будущем время на обработку всех её элементов. Кроме того, с момента их первой реализации и использования лишь в качестве определения порядка полигона было обнаружено много других полезных свойств, которыми пользуются и по сей день.
В данной работе были реализованы два алгоритма для построения списка приоритетов полигонов на сцене: алгоритм художника и двоичного разбиения пространства. Были решены главные проблемы алгоритма двоичного разбиения пространства, такие как выбор оптимальной разделяющей плоскости, определения положения точки и полигона относительно плоскости, а также деление полигона плоскостью.
В процессе реализации этих алгоритмов обнаружены достоинства и недостатки каждого из них, проведен сравнительный анализ как по качеству изображения сцены, так и по времени работы алгоритма. Установлено, что точность и правильность сцены присуща двоичному разбиению пространства, за исключением некоторых особенностей. Для небольших простых, но изменяющихся сцен алгоритм художника выигрывает по времени реализации, а для статичных сцен имеет смысл использовать BSP-дерево, которое строится один раз для всей сцены, а далее проводится лишь процедура обхода методом back-to-front.
