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

Алгоритм, использующий 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 Анализ и выбор алгоритма определения освещенности

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

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

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

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

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

Отражение;

Рассеяние;

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

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

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

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

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

Данная техника позволяет создавать трехмерные образы, но при этом не видны такие эффекты, как тени, рефракция и рефлексия. Чтобы воссоздать перечисленные эффекты, мы должны принять в рассмотрение специальные вторичные лучи, которые

исходят из точек пересечения. Это все делается рекурсивно до достижения некоторого уровня детализации. Затем полученные по всем лучам результаты складываются, и соответствующему пикселю присваивается вычисленный цвет.

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

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

Краткое описание упрощенного алгоритма.

Освещение создаётся при помощи точечного источника. При рендеринге в режиме "без освещения" все объекты считаются освещёнными и теней не отбрасывают.

В случае рендеринга с освещением для каждой прорисовываемой точки выполняется процедура расчета освещения её источником света. Сначала проверяется наличие, пересечения луча из точки в источник света с любым другим объектом из сцены. Если такое пересечение было найдено, то точка не освещена данным источником. Иначе, точка получает прирост освещённости по цвету и интенсивности, зависящий от источника и угла между отрезком и нормалью к треугольнику, которому принадлежит рассматриваемая точка (см. рис.1). Таким образом, создаются тени - области без дополнительного освещения. Для усиления теней рекомендуется выбирать в качестве базовых цветов модели тёмные оттенки, а для источников освещения - более яркие.

Рис. 3. Освещенность точки.

P - рассматриваемая точка

N - нормаль к поверхности

Z - вектор, ведущий от рассматриваемой точки к источнику освещения.

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

Алгоритм трассировки лучей позволяет получить наиболее реалистичные изображения объектов сцены. Одним из свойств алгоритмов трассировки лучей заключается в большой зависимости скорости работы от разрешения экрана. Одним из главных последствий существования этой зависимости стала невозможность осуществления трассировки лучей в реальном времени на старых персональных компьютерах, оснащённых процессорами PentiumII и ниже. Эта константа даже на маленьких разрешениях - 400х300 - полностью съедала всю мощность процессора. Но сейчас этот барьер пройден. [3] Для обеспечения резкого ускорения скорости работы алгоритма необходимо использовать специальные библиотеки арифметических вычислений, оптимизированные под команды SSE. Например, уже достаточно давно доступна библиотека Small Matrix Library от компании Intel. В ней реализован класс матрица и класс вектор. По данным iXBT [3] время выполнения вычислений с учетом использования данной библиотеки на PIII 800EB выглядит следующим образом:

Операция	SSE/FPU	Время выполнения (в тактах процессора)
3x3 * 3x1	FPU	31
3x3 * 3x1	SSE	29
Transpose (3x3) * 3x1	SSE	23
4x4 * 4x1	FPU	53
4x4 * 4x1	SSE	31
Transpose (4x4) * 4x1	SSE	27
3x3 * 3x3	FPU	79
3x3 * 3x3	SSE	59
4x4 * 4x4	FPU	172
4x4 * 4x4	SSE	90
6x6 * 6x1	FPU	113
6x6 * 6x1	SSE	60
6x6 * 6x6	FPU	652
6x6 * 6x6	SSE	307
4x4 * 4x4 (general case)	SSE	529
Inverse 4x4	FPU	392
Inverse 4x4	SSE	209
Inverse 6x6	FPU	1118
Inverse 6x6	SSE	600

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