Алгоритм Варнока

Алгоритм Z-буфера и построчного сканирования

Вход: векторная модель (параметры сцены, расположение камеры) Выход: растр. Каждая грань рисуется модифицированным алгоритмом закраски многоугольника. Для каждого пикселя растрового изображения хранится ещё и z — расстояние от камеры до пикселя. Если проецирование ведётся на плоскость XY, а проецируемая грань (треугольник) лежит в плоскости {Ax + By + Cz + D = 0}, то в точку (x,y) экрана будет спроецирована точка (x, y, (– Ax – By – D) / C), причём последняя координата будет обозначать расстояние до камеры.

Изначально матрица значений Z (Z-буфер) инициализируется некоторым очень большим числом.

● Если Z рисуемого пикселя меньше соответствующего ему элемента в Z-буфере, то пиксель рисуется, и в Z-буфер заносится его значение Z.

● Иначе пиксель пропускается.

Для ускорения вычислений Z можно вычислять его только для одной вершины, а затем добавлять частные производные:

Достоинства:

● Простота реализации.

● Приемлемость для сцен любой сложности.

● Возможность распараллеливания (делим изображение на несколько частей, и каждую обрабатываем в отдельном потоке).

Недостатки:

● Большие объемы памяти

● Z — это вещественное число, вычисление производится с высокой точностью

● При реализации полупрозрачности требуется несколько z: z₁, z₂... ⇒ еще больше ресурсов. В этом случае можно рисовать сначала все непрозрачные объекты, а потом — все полупрозрачные

Алгоритм построчного сканирования(модификация предыдущего алгоритма).

Делаем полигон объектом, который имеет методы:

1 Init

2 GetCurrentY — на какой строке сейчас стоит алгоритм

3 DrawCurrentLine — рисует текущую часть объекта

4 bool next — существует ли следующая строка

В цикле по всем строкам изображения проверяем, пересекает ли текущая строка какой-нибудь полигон, и если да, то рисуется строка полигона (DrawCurrentLine и next) с использованием Z-буфера.

Достоинства:

● храним Z-буфер только для текущей сканируемой строки ⇒ экономия памяти.

Вход: векторная модель (параметры сцены, расположение камеры).

Выход: растр.

Для каждой грани вычисляются экранные координаты её вершин. Рассматривается множество многоугольников и прямоугольное окно.

Если все многоугольники внешние, то закрашиваем окно цветом фона.
Если только один многоугольник пересекается с окном, то выполняется его отсечение (окном) и рисуется только видимая часть.
Если с окном пересекается несколько многоугольников, но при этом самый ближний из них является охватывающим (окно целиком лежит внутри него), то окно закрашивается цветом этого многоугольника.
Если размер окна = 1 пиксель, то он закрашивается цветом ближайшего многоугольника и на этом работа алгоритма прекращается.	янезнаюкакэтонарисовать.jpg
Если с окном пересекается несколько многоугольников и ни один из них не является охватывающим, то окно делится на четыре части и для каждой части опять запускается алгоритм с начала.

Замечания

● Глубина рекурсии оказывается небольшой (при размерах 1024х1024 глубина = 10)

● Алгоритм может быть распараллелен.