Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Лабораторная работа №4. Удаление невидимых поверхностей с помощью алгоритма Z-буфер

Цель: Научиться строить параметрически заданные простейших трехмерных объектов, и осуществлять их визуализацию с удалением невидимых поверхностей с помощью алгоритма Z-буфер.

Задача: На основе исходных параметров построить полигональную поверхностную модель трехмерного объекта, и визуализировать полученную сцену, используя параллельное и перспективное проецирования и удаление невидимых поверхностей с помощью алгоритма Z-буфер.

Результат: программа формирования визуального представления заданной трехмерной сцены. Отчет в печатном виде, оформленный в соответствии с приложением 1.

 

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

 

Закраска произвольного треугольника, (алгоритм 1)

 

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

 


Рис 4.2. Попиксельное представление закрашенного треугольника

 

Будем отрисовывать треугольник последовательно, точка за точкой сверху вниз и слева направо. Для этого надо пройти по всем строкам экрана, которые пересекают треугольник, (т.е от минимального до максимального значения y- координат вершин треугольника) и нарисовать соответствующие горизонтальные отрезки.

 

Рис. 4.3. Последовательная закраска треугольника.

 

Для этого, сначала отсортируем вершины треугольника так, чтобы А была верхней а С – нижней. Тогда, , а , и нам нужно пройтись по всем строкам от до . Рассмотрим некоторую строку . Если то эта строка пересекает стороны AB и AC. Если то строка пересекает BC и AC.

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

Рассмотрим подробно нахождение точки пересечения прямой и стороны треугольника, например AB. Для этого напишем уравнение прямой АВ в виде :

Подставим в него известное значение :

Для других сторон точки пересечения ищутся аналогично. Так для BC:

Для AC:

Необходимо отслеживать случаи , и , поскольку будет происходить деление на 0.

 

Закраска произвольного треугольника (алгоритм 2)

 

Рассмотренный ранее алгоритм позволяет закрасить любой треугольник, однако его быстродействие оставляет желать лучшего. В этом повинны как поточечное рисование на поверхности окна (поскольку оно чрезвычайно медленное), так и использование операций с плавающей точкой над вещественными числами. От поточечного рисования нам избавиться не удастся, поскольку необходимо иметь возможность задавать значение цвета для каждой точки треугольника. Однако API Windows предлагает метод, при использовании которого, поточечное рисование может быть ускорено в несколько раз.

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

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

 

Graphics::TBitmap *pBitmap=new Graphics::TBitmap(); //Создаем экземпляр TBitmap

pBitmap->Width=MainForm->ClientWidth; //Задаем ширину битовой карты

pBitmap->Height=MainForm->ClientHeight; //Задаем высоту битовой карты

pBitmap->PixelFormat=pf32bit; //Устанавливаем глубину цвета равную 32 бита.

 

Поточечное рисование на битовой карте осуществляется с помощью строк сканирования. Вся битовая карта представляется как одномерный массив горизонтальных строк, называемых строками сканирования. Каждая из этих строк представляет собой одномерный массив, каждый элемент которого для глубины цвета 32 бита, содержит значение цвета соответствующей точки. Это значение представляет собой 32 разрядное целое число, в котором первый байт задает интенсивность синего цвета, второй байт – зеленого, третий байт – красного, а четвертый – значение прозрачности (канал альфа).

Чтобы работать со строкой сканирования с глубиной цвета 32 бита необходимо:

1. Завести переменную – указатель на целое число ( int *scl;).

2. Получить необходимую строку сканирования ( scl=(int*)pBitmap->ScanLine[i];
где iy-координата соответствующей строки);

3. Задать новые значения цветов точкам строки сканирования (scl[j]=NewColor;
где jx-координата необходимой точки, а NewColor – новое значение цвета этой точки типа int).

После того, как изображение будет полностью сформировано на битовой карте, его необходимо перенести на поверхность окна. Для этого необходимо использовать функцию Draw свойства Canvas окна.

 

Canvas->Draw(0,0,pBitmap);

 

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

После того, как необходимость в битовой карте пропадет, необходимо уничтожить ее экземпляр.

 

delete pBitmap;

 

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

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


Сначала представим стороны треугольника в виде отрезков прямых линий (см. рис. 4.4.).

 
 

 

 


Рис. 4.4. Представление сторон треугольника в виде набора отрезков.

 

Поскольку изображение на экране состоит из совокупности точек, то и изображения этих отрезков также будет состоять из точек.

Если рассмотреть с увеличением окрестность вершины А, можно увидеть примерно следующую картину (см. рис.4.5.).

 
 

 


Рис. 4.5. Вид окрестности точки А.

 

Значит, если мы сможем разработать алгоритм последовательного нахождения координат точек отрезков А B, A С, B C, то сможем нарисовать закрашенный треугольник просто рисуя горизонтальные отрезки соединяющие точки двух сторон с одинаковыми координатами y (см. рис. 4.6.).

       
 
   
Текущий закрашиваемый горизонтальный отрезок
 

 

 

 


Рис. 4.6. Попиксельная закраска треугольника.

 


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

Вначале зададим x=AX и y=AY. В цикле будем задавать приращение 1 для переменной y и будем оставлять x либо неизменным, либо также увеличивать на 1. При этом последний выбор будем осуществлять так, чтобы новая точка сетки (x, y) располагалась как можно ближе к прямой линии, проходящей через точки А и С (см. рис.4.7.).

 
 

 


Рис. 4.7. Выбор точек отрезка АС.

 

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

Введем переменную d для обозначения этого расстояния. Потребуем, чтобы .

Последнее неравенство обеспечивает условие для определения необходимости давать приращение переменной x.

Теперь можно написать первый вариант реализации функции нахождения координат точек между A и С:

{

int x, y,x1;

float t; //коэффициент наклона

float d; //отклонение

 

t=(float)(CX-AX)/(float)(CY-AY);

d=0;

x=AX;

for (y=AY; y<=CY; y++)

{

x1=x; //координата x очередной точки на прямой AC

d+=t;

if (d>0.5) {x++; d--;}

}

}

Отклонение, вначале устанавливается равным нулю и изменяется на каждом шаге цикла. Поскольку оно показывает, насколько левее точной прямой линии лежит вычисленная точка, то значение d увеличивается на значение наклона, если y увеличивается на 1 и x остается без изменения. Это условие не выполняется, если значение d превышает 0.5. В этот момент нужно увеличить значение x на 1. Соответственно, и отклонение d должно быть уменьшено на единицу.

Теперь посмотрим, как можно избавиться от вещественных значений переменных t и d.

Значение переменной t вычисляется следующим образом:

где числитель и знаменатель представляют собой целые числа.

Величина d вычисляется как конечная сумма элементов, каждый из которых равен либо t, либо -1. Поэтому d также можно записать в виде частного со знаменателем равным .

Значит, можно перейти к целочисленным переменным t и d, путем умножения на значение знаменателя. Также просто избавиться от константы 0.5. Для этого нужно дополнительно умножить значение знаменателя на 2. Таким образом , где lx=CX-AX.

Теперь условный оператор в нашей функции можно заменить на:

if (d>ly) {x++; d-=ds;},

где ds=2ly=2(CY-AY).

 

Таким образом, получаем новый вариант нашей функции:

{

int x, y, t, d, lx, ly, ds;

lx=CX-AX;

ly=CY-AY;

ds=ly << 1; //ds=2*ly;

t=lx << 1; //t=2*lx;

x=AX;

for (y=AY; y<=CY; y++)

{

x1=x; //координата x очередной точки на прямой AC

if (d > ly) {x++;d -= ds;}

}

}

 

Однако наша функция будет правильно работать только для случая, когда , и просто поменять местами x и y в противном случае нам не удастся (треугольник должен отрисовываться последовательно сверху – вниз).

 

Рассмотрим следующий рисунок:

 
 

 

 


Рис. 4.8. Случай, когда lx>ly.

 

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

{

int x, y, t, d, lx, ly, ds;

lx=CX-AX;

ly=CY-AY;

ds=ly << 1; //ds=2*ly;

t=lx << 1; //t=2*lx;

if (x!=CX)

while (d > ly)

{

x++;

d-=ds;

}

x1=x; // нашли координату х очередной точки

}

Для других сторон треугольника координаты точек прямых линий ищутся аналогично.

 

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...