Разработка системы моделирования наблюдения за группировкой кораблей

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

Иногда, для устранения лестничного

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

При помощи изложенного алгоритма можно удалить либо невидимые линии, либо невидимые поверхности. Однако простота критерия разбиения, а также негибкость способа разбиения приводят к тому, что количество подразбиений оказывается велико. Можно повысить эффективность этого алгоритма, усложнив способ и критерий разбиения. На рис.5.17, а показан другой общий способ разбиения и дано его сравнение с изложенным ранее жестким способом, представленным на рис.2.

Рис.2. Способы разбиения окна

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

Алгоритм, использующий Z – буфер.

Впервые он был предложен Кэтмулом. Работает этот алгоритм в пространстве изображения. Идея z-буфера является простым обобщением идеи о буфере кадра. Буфер кадра используется для запоминания атрибутов (интенсивности) каждого пикселя в пространстве изображения, z-буфер - это отдельный буфер глубины, используемый для запоминания координаты Z или глубины каждого видимого пикселя в пространстве изображения. В процессе работы глубина или значение Z каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в z-буфер. Если это сравнение показывает, что новый пиксел расположен впереди пикселя, находящегося в буфере кадра, то новый пиксел заносится в этот буфер и, кроме того, производится корректировка z-буфера новым значением Z. Если же сравнение дает противоположный результат, то никаких действий не производится. По сути, алгоритм является поиском по Х и у наибольшего значения функции Z (X, у).

Более формальное описание алгоритма z-буфера таково:

Заполнить буфер кадра фоновым значением интенсивности или цвета.

Заполнить Z - буфер минимальным значением Z.

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

Для каждого Пиксель (x,y) в многоугольнике вычислить его глубину Z (x,y).

Сравнить глубину z (х, у) со значением Z-буфер (х, у), хранящимся в z-буфере в этой же позиции.

Если z (х, у) > Z-буфер (х, у), то записать атрибут этого многоугольника (интенсивность, цвет и т.п.) в буфер кадра и заменить Z-буфер (х, у) на z (х, у).

В противном случае никаких действий не производить.

Преимущества:

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

Недостатки:

Основной недостаток алгоритма - большой объем требуемой памяти.

Другой недостаток алгоритма z-буфера состоит в трудоемкости и высокой стоимости устранения лестничного эффекта, а также реализации эффектов прозрачности и просвечивания. Однако процесс сглаживание лестного эффекта в данное время переносится на уровень шейдерных микропрограмм, для обеспечения одновременной работы технологии High Dynamic Range Imaging (HDRI) и сглаживания изображения (Anti-aliasing). Поскольку алгоритм заносит пиксели в буфер кадра в произвольном порядке, то нелегко получить информацию, необходимую для методов устранения лестничного эффекта, основывающихся на предварительной фильтрации. При реализации эффектов прозрачности и просвечивания, пиксели могут заноситься в буфер кадра в некорректном порядке, что ведет к локальным ошибкам.

Обоснование выбора алгоритма.

Для реализации был выбран алгоритм Z - буфера. Он широко применяется в современных 3D движках. Алгоритм очень эффективен и практически не имеет недостатков, если реализуется аппаратно. Данный алгоритм позволяет получить представление об особенностях современных аппаратных компонентов компьютеров. Одновременно с неоценимым опытом он позволяет достичь необходимой скорости в условиях данного проекта. В дальнейшем, путем переноса некоторых вычислений с программного на аппаратный уровень можно добиться значительно увеличения производительности. Особенно с учетом особенностей современного развития компьютерных вычислений, нацеленного на перенос некоторых операций с CPU на GPU. Видеокарты от ATI серии выше Xx00 и Nvidia 8х00 позволяют реализовать данный перенос.

1.1.3 Анализ и выбор алгоритма определения освещенности

Алгоритм трассировки лучей.

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

множество проблем. Этот алгоритм может выполнять следующие действия:

Удаление невидимых поверхностей;

Перемещение;

Отражение;

Рассеяние;

Окружающее освещение;

Точечное освещение;

Наложение теней.

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

Чтобы воспользоваться трассировкой лучей для создания натуральных образов, нам придется использовать миллиарды световых лучей из источника света, а затем рассматривать каждый из них, надеясь, что он попадет в план наблюдения и примет участие в создании образа. Возникает вопрос - а зачем трассировать каждый возможный луч? На самом деле, нас интересуют только те лучи, которые достигают плана просмотра. Что же будет, если трассировать лучи в обратном направлении? Проследим движение лучей для каждого из пикселей на экране, а затем посмотрим, где эти лучи пересекаются с планом просмотра. Отметив пересечение, мы останавливаемся и окрашиваем соответствующий пиксель в нужный цвет. Это называется первичной трассировкой лучей.

 Скачать реферат