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

Компьютерная графика - одно из популярных и наиболее развивающихся направлений в компьютерных науках. Популярность компьютерной графики обусловлена тем, что виртуальные среды предоставляют возможность моделировать ситуации и объекты, не беспокоясь о последствиях, стоимости и других параметрах, которые в реальной жизни либо недоступны, либо ограничены в объемах. Так, например, архитекторы могут строить модели домов, не прилагая больших усилий в черчении, пилоты могут учиться управлять самолетами без риска для жизни, биохимики могут моделировать сложные молекулярные структуры и изучать их, а существующие пользовательские взаимодействия, такие как вращение и масштабирование, используются для лучшего обзора и анализа структуры. Но, конечно, наибольшее распространение в области компьютерной графики получила разработка игр, как сфера, наиболее востребованная у множества конечных пользователей, поскольку не является узкоспециализированной и нацеленной только на определенную группу людей специалистов.
Однако, никаких графических приложений не было бы, если бы не было алгоритмов, позволяющих преобразовывать SD-графику для отображения в двухмерном пространстве и строить реалистичные изображения.
Удаление невидимых линий и поверхностей
Для построения реалистичного изображения нам необходимо знать какие грани являются видимыми, а какие скрыты от нас за другими, так появилась задача удаления невидимых линий и поверхностей. Необходимость определения видимости граней можно проиллюстрирована на рисунке 1. Здесь изображена реберная сцена куба, однако мы можем интерпретировать его положение по-разному, в зависимости от угла обзора и положения наблюдателя.
Сложность задачи привела к появлению большого числа различных способов ее решения. Большинство из них ориентированы на специализированные приложения. Однако наилучшего решения обшей задачи удаления невидимых линий и поверхностей не существует.

Рисунок 1 - Зависимость положения вида куба от угла обзора и положения наблюдателя

Для моделирования процессов в реальном времени требуются быстрые алгоритмы, с помощью которых можно достигнуть частоты видео 30 кадров в секунду. Для машинной мультипликации, требуются алгоритмы, которые могут генерировать сложные реалистические изображения с тенями, различными фактурами, прозрачностью, а также необходимо учитывать эффекты отражения и преломления цвета. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов.
Стоит заметить, что учет эффектов прозрачности, фактуры, отражения и прочего не входит в задачу удаления невидимых поверхностей, однако они могут быть встроены в эти алгоритмы.
Рассматриваемые нами алгоритмы можно классифицировать по способу выбора пространства в котором они работают. Выделяют три класса алгоритмов удаления невидимых линий и поверхностей.
Алгоритмы, работающие в объектном пространстве. Они работают в системе координат объектов и получают результаты, точность которых ограничена лишь точностью вычислений. В результате получаются хорошо масштабируемые изображения.
Алгоритмы, работающие в пространстве изображения (экрана). Такие алгоритмы работают в системе координат экрана, на котором объекты визуализируются, а значит точность вычислений ограничены разрешающей способностью экрана.
Алгоритмы, формирующие список приоритетов. Являются комбинацией предыдущих двух методов и работают путем определения элементов сцены по удаленности от наблюдателя. А далее объекты выводятся на экран от дальнего к ближнему.
В данной работе будут детально рассмотрены и реализованы алгоритмы, относящиеся к классу формирующих списки приоритетов, а именно: алгоритм художника, как самый элементарный и интуитивно понятный, и двоичное разбиение пространства (Binary Space Partition или BSP- дерево), считающийся точным и быстрым. В процессе их реализации будут выявлены их слабые и сильные стороны, а также проведен анализ и сравнение их скорости и точности.
Стоит заметить, что с момента появления первых игр от первого лица и до настоящего времени используется такое решение как двоичное разбиение пространства. Оно было впервые реализовано Джоном Кармаком при разработке движка Doom, использовавшегося в одноименной игре от первого лица. Это решение до сих пор так или иначе применяется в игровой индустрии, поскольку его применение значительно упрощает решение проблемы видимости, а предварительное построение дерева для статичной сцены уменьшает в будущем время на обработку всех её элементов. Кроме того, с момента их первой реализации и использования лишь в качестве определения порядка полигона было обнаружено много других полезных свойств, которыми пользуются и по сей день.

Купить

В данной работе были реализованы два алгоритма для построения списка приоритетов полигонов на сцене: алгоритм художника и двоичного разбиения пространства. Были решены главные проблемы алгоритма двоичного разбиения пространства, такие как выбор оптимальной разделяющей плоскости, определения положения точки и полигона относительно плоскости, а также деление полигона плоскостью.
В процессе реализации этих алгоритмов обнаружены достоинства и недостатки каждого из них, проведен сравнительный анализ как по качеству изображения сцены, так и по времени работы алгоритма. Установлено, что точность и правильность сцены присуща двоичному разбиению пространства, за исключением некоторых особенностей. Для небольших простых, но изменяющихся сцен алгоритм художника выигрывает по времени реализации, а для статичных сцен имеет смысл использовать BSP-дерево, которое строится один раз для всей сцены, а далее проводится лишь процедура обхода методом back-to-front.

Купить