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

Алгоритм работает в пространстве изображения.

Буфер кадра (регенерации) используется для заполнения атрибутов (интенсивности) каждого пикселя в пространстве изображения.

Для него требуется буфер регенерации, в котором запоминаются значения яркости, а также Z-буфер (буфер глубины), куда можно помещать информацию о координате z для каждого пикселя. Вначале в Z-буфер заносятся максимально возможные значения z, а буфер регенерации заполняется значениями пикселя, описывающими фон. Затем каждый многоугольник преобразуется в растровую форму и записывается в буфер регенерации, при этом, однако, не производится начального упорядочения.

Достоинства

1. Простота. Сцены могут быть любой сложности
2. Элементы сцены не нужно сортировать

Недостатки

1. Большой объём памяти
2. Трудоёмкость устранения лестничного эффекта
3. Трудоёмкость реализации эффектов прозрачности

Алгоритм

1. Заполнение буфера кадра фоновый значением интенсивности (цвета).
2. Заполнение Z - буфера минимальным значением Z .
3. Преобразование каждого многоугольника в растровую форму в произвольном порядке.
4. Вычисление для каждого пикселя с координатами (x, y), принадлежащего многоугольнику, его глубины Z(x, y).
5. Сравнение глубины Z(x, y) со значением Zбуф(x, y), хранящимся в Z-буфере для пикселя теми же координатами(x, y). Если Z(x, y)>Zбуф(x, y), то записать атрибут очередного многоугольника в буфер кадра и Zбуф(x, y) заменить на значение Z(x, y).

Замечание
Алгоритм, использующий Z -буфер, можно применять для построения разрезов поверхностей. В этом случае изменяется только операция сравнения глубины пикселя со значением, занесенным в буфер: [Z(x, y) > Zбуф (x, y)] и (Z(x, y <= Zразр), где Zразр - глубина искомого разреза.

Алгоритм, использующий список приоритетов (алгоритм Художника)

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

Алгоритм

1. Отсортировать многоугольники сцен в кадре в порядке возрастания Z
2. Построить самый дальний многоугольник, если он не экранирует другие другие многоугольники (Zmax(A)<Zmin(B))
3. Проверить, экранирует ли многоугольник P многоугольник Q при Zmax(P)>Zmin(Q). Если на один из тестов даётся + ответ, P заносится в буфер кадра (P не экранирует Q). Если все -, то P и Q меняются местами, позиция Q помечается, тесты повторяются снова. Если вновь попытка менять местами, то P разрезается плоскостью, несущей Q, исходный многоугольник удаляется из списка, а его части заносятся в список. Тесты повторяются снова.
1. верно ли, что прямоугольные объемлющие оболочки P и Q не перекрываются по X? по Y?
2. верно ли, что P целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения
3. верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая расположена ближе к точке наблюдения
4. верно ли, что проекции P и Q не перекрываются

Для 3,4 можно проверять функцией f=Ax+By+Cz+D, где A, B, C – коэффициенты пробной плоскости U. В f подставляются координаты вершин испытуемого многоугольника W. Если знаки f для вершин совпадают и + или =0, то W находится с дальней стороны от плоскости U. Если знаки совпадают и отрицательны или равны 0, то W расположен с ближней стороны от U.

Алгоритм построчного сканирования, использующий Z буфер. Интервальные методы построчного сканирования (основные предпосылки).

Алгоритмы Варнока, Z-буфера и строящего список приоритетов обрабатывают элементы сцены в порядке, который не связан с процессом визуализации. Алгоритмы построчного сканирования обрабатывают сцену в порядке прохождения сканирующей строки.

Алгоритм

1. Подготовка информации
   a) Для каждого многоугольника определить самую верхнюю сканирующую строку, которую он пересекает.
   b) Занести многоугольник в группу y, соответствующую этой сканирующей строке
   c) Запомнить для каждого многоугольника: Δy – число строк, пересекающих этот многоугольник, список рёбер многоугольника, коэффициенты A, B, C, D уравнения плоскости многоугольника, визуальные атрибуты многоугольника
2. Решение задачи удаления невидимых поверхностей
   a) Инициализировать буфер кадра дисплея
   b) Для каждой сканирующей строки
   
   
1. Инициализировать буфер кадра размером с одну сканирующую строку, заполнив его фоновым изображением
2. Инициализировать Z-буфер размером с одну сканирующую строку значением Zmin
3. Проверить необходимость добавления в список активных многоугольников (САМ)
   новых многоугольников
4. Если было добавление многоугольника в САМ, то добавить в САР соответствующие рёбра новых многоугольников
5. Если произведено удаление какого-либо элемента из пары рёбер САР, то проверить необходимость удаления всего многоугольника из САМ. Если он остаётся, то проверить необходимость удаления другого ребра из этой пары – если его удалять не нужно, то доукомлектовать пару (добавив недостающее левое или правое ребро)
   c) В САР должна храниться следующая информация:
   1) Xл – пересечение левого ребра с текущей сканирующей строкой
   2) ΔXл – приращение Xл в интервале между соседними сканирующими строками
   3) ΔYл – число сканирующих строк, пересекаемых левым ребром
   4) Xп, ΔXп, ΔYп
   5) ΔZх=-A/C для C≠0 (иначе ΔZх=0) – приращение по Z вдоль сканирующей строке
   6) ΔZy=-B/C для C≠0 (иначе ΔZy=0) – приращение по Z в интервале между соседними сканирующими строками
   d) Для каждой пары ребёр многоугольника из САР выполнить:
   1) Извлечь
   2) Инициализировать Z значением Zл
   3) Для каждого пикселя Xл≤X≤Xп вычислить Z(x,y=const). Z1=Zл, ..., Zk=Zk-1+ ΔZх
   4) Если Z()>Zбуф(), то Zбуф=Z и занести атрибуты многоугольника в буфер кадра
   e) Записать буфер кадра сканирующей строки в буфер кадра дисплея
   f) Скорректировать САР
   1) ΔYл--, ΔYп--
   2) Xл=Xл+ΔXл, Xп=Xп+ΔXп
   3) Zл=Zл+ΔZхΔX+ΔZy
   4) Если ΔYл<0 или ΔYп<0, то удалить соответствующее ребро из списка, пометив положение обоих рёбер в списке и породивший их многоугольник
   g) Скорректировать САМ
   1) ΔY--
   2) Если ΔY<0, то удалить многоугольник из САМ

Интервальные методы построчного сканирования
В алгоритме построчного сканирования с использованием Z-буфера глубина многоугольника вычисляется для каждого пикселя на сканирующей строке. Количество вычислений можно сократить, если использовать понятие интервалов. Решение задачи удаления невидимых поверхностей сводится к выбору видимых отрезков в каждом интервале, полученном путём деления сканирующей строки проекциями точек пересечения ребёр

1. Изобразить фон
2. Изобразить атрибуты многоугольника, соответствующие этому отрезку
3. Изобразить атрибуты многоугольника, соответствующие отрезку с MAX Z
4. sign (z1m-z2m)≠ sign (z1k-z2k) – разбить интервал точкой пересечения

 

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

---

Дата добавления: 2019-01-14; просмотров: 388; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!