Компьютерная геометрия и графика. Лекция 8

План занятия: Задача удаления невидимых линий c с использованием Z-буфера Алгоритм Художника

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

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

Создание Z-буфера: в начале в матрицу записываем очень большие значения. Потом берем точки поверхности и проверяем условие: If (ZB [XX,YY]>ZZ) { putpixel (XX,YY,1); ZB[XX,YY]=ZZ; }

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

1. Работая со всем экраном, делить его на части и рассматривать кусками. Но при таком способе увеличивается время работы алгоритма, во столько раз, на сколько частей делим экран.

2. Можно считать не все точки, а, например, через 4 пикселя. Остальные вычисляются как среднее арифметическое. Происходит плавная смена цветов, но точность изображения падает. Также возникает проблема размытых границ. Естественно, что чем меньше пикселей мы будем рассматривать, тем менее качественной будет картинка.

3. Можно использовать внешний носитель. Берем какой-то кусок экрана и создаем для него Z-буфер. Потом берем точку, которую мы хотим поставить и проверяем - находится ли она в этом куске экрана. Если нет, то существующую Z-матрицу записываем на диск и создаем новую для того куска экрана, в котором находится данная точка.

Как рассчитывать координаты? Точки в проекции нужно брать настолько близко, чтобы точки на самой поверхности отличались не более чем на 1. Возникает проблема дырявой поверхности, то есть частичная видимость невидимых границ сквозь дырки на видимых. То есть надо брать достаточно много точек по Х, и достаточно много точек по Y (больше чем пикселов на экране) и считать по этим координатам функцию - но в результате мы получим одно большое пятно на экране. ?

Можно, конечно, рассчитывать только конкретные точки, взяв свое разбиение (либо просто экран 640*480), а затем смотреть разницу между получившимися значениями функции. Сделать таким образом динамическую длину шага: Х+ какая-то величина Y+ какая-то величина

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

Цвет каждой точки не вычисляем отдельно, а используем уже вычисленный нами ZZ: чем больше ZZ, тем цвет ближе к 15, а чем меньше, тем он ближе к нулю. Можно чтобы цвет зависел от значений функции Z, а не от ZZ, тогда будет эффект топографической карты - изображение будет легко распознаваемо.

Эффект сетки.

Это изображение функции в виде сетки (для того, чтобы функция не была похожа на сплошное пятно) Допустим функция задана на множестве [x1,x2][y1,y2]. Введем величину разбиения, расстояние между узлами сетки по оси Ox: X1 X2 Y1 Y2 Dx

Для каждого X поверхности мы проверяем дробную часть выражения: Если она близка к нулю, то есть само выражение почти целое число, то рисуем одним цветом (цветом самой сетки), иначе другим (цвет поверхности). Аналогично для Y. X1 X2 Y1 Y2

Удаление невидимых линий методом сортировки по глубине. (Алгоритм Художника)

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

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

Алгоритм должен уметь: ХРАНИТЬ каждый из тех кусочков, на которые мы разбили объекты. СОРТИРОВАТЬ эти кусочки по дальности расположения. ИЗОБРАЖАТЬ их на экране.

Очень важно, чтобы в этом алгоритме сортировка была очень быстрая.

Чтобы хранить в памяти меньше информации о каждом из кусочков разбиения можно сделать так: А А Например мы храним информацию о четырех кусочках разбиения. Во все четыре входит одна и та же информация - координаты точки А. Как избежать этого четырехкратного повторения? ?

Это решается легко:можно информацию о каждом фрагменте хранить в матрице. Каждый фрагмент имеет свой индекс Например в ячейке матрицы М [ 1 ][ 2 ] хранится информация об удаленности выделенного на рисунке кусочка. Если мы захотим его нарисовать, то по индексу мы можем легко установить его координаты.

Допустим у нас есть область [X1,X2]х[Y1,Y2]. Мы разбиваем поверхность на N*N прямоугольников. Вычисляем размер каждого: (X1+ X,Y1) (X1,Y1+ Y)(X1+ X,Y1+ Y) (X1,Y1) Теперь зная одну координату в каждом фрагменте мы можем легко восстановить другие:

Получается, что в памяти мы будем хранить только 1. НОМЕР ФРАГМЕНТА ПО Х 2. НОМЕР ФРАГМЕНТА ПО Y 3. УДАЛЕННОСТЬ ОТ НАС

Получается, что после разбиения объекта на фрагменты, для достижения результата, мы должны осуществить следующие действия: Сортировать фрагменты по УДАЛЕННОСТИ от нас по убыванию. Восстановить координаты каждого фрагмента. Нарисовать фрагменты один за другим на экран.

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

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

КОНЕЦ