Создание программы, реализующей алгоритм удаления невидимых линий и поверхностей методом Z-буфер (стр. 2 из 2)

Значит, глубина треугольника в любой его точке задается уравнением z = -(3x + у - 120)/4.

Для последовательных пикселов, лежащих на сканирующей строке z1 = z - 3/4.

Вычисление пересечений сторон треугольника со сканирующими строками развертки с учетом соглашения о половине интервала между соседними сканирующими строками дает следующие пары координат (25.2, 24.5), (25.5, 23.5), (25.8, 22.5), (26.2, 21.5), (26.5, 20.5), (26.8, 19.5), (27.2, 18.5), (27,5, 17.5), (27.8, 16.5), (28.2, 15.5), (28.5, 14.5), (28.8, 13.5), (29.2, 12.5), (29.5, 11.5), (29.8, 10.5) для строк от 24 до 10. Напомним, что активируется тот пиксел, у которого центр лежит внутри или на границе треугольника, то есть при x1 <= x <= x2. Преобразование в растровую форму и сравнение глубины каждого пиксела со значением z-буфера дает новое состояние буфера кадра:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 2 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 2 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 2 2 2 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 2 1 1 1 1 2 2 2 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 1 1 1 2 2 2 2 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 2 2 2 2 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 0 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 2 2 0 0

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

После обработки треугольника состояние z-буфера таково:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 6 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 6 5 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 11 10 10 10 10 10 6 5 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 12 11 10 10 10 10 10 6 6 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 13 12 11 10 10 10 10 10 7 6 5 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 14 13 12 11 11 10 10 10 10 7 6 5 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 15 14 13 12 12 11 10 10 10 10 7 6 6 0 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 14 13 13 12 11 10 10 10 10 7 7 6 5 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 12 11 11 10 10 10 8 7 6 5 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 8 7 6 6 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 8 7 7 6 5 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 6 5 0 0 0

0 0 0 0 0 0 0 0 0 0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Для примера рассмотрим пиксел (20, 15). Оценка z в центре этого пиксела дает

z = -[(3), (20.5) + 15.5 - 120]/4 = 43/4 = 10.75.

Сравнивая его со значением z-буфера в точке (20, 15) после обработки прямоугольника, видим, что треугольник здесь расположен перед прямоугольником. Поэтому значение буфера кадра в точке (20, 15) заменяется на 2. Поскольку в нашем примере z-буфер состоит лишь из 4 битовых плоскостей, он может содержать числа только в диапазоне от 0 до 15. Поэтому значение z округляется до ближайшего целого числа. В результате в ячейку (20, 15) z-буфера заносится число 11.

Линия пересечения треугольника с прямоугольником получается при подстановке z = 10 в уравнение плоскости, несущей треугольник. Результат таков:

3x + y - 80 = 0.

Пересечения этой прямой с ребрами треугольника происходят в точках (20, 20) и (22.5, 12.5). Линия пересечения, на которой треугольник становится видимым, хорошо отражена в буфере кадра.

Алгоритм, использующий z-буфер, можно также применить для построения сечений поверхностей. Изменится только оператор сравнения:

z(x, y) > Zбуфер(x, y) and z(x, y) <= Zсечения

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

2.2 УДАЛЕНИЕ НЕВИДИМЫХ ЧАСТЕЙ

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

Поскольку камера видит только то, что перед ней находится, все те точки, для которых z < -dist, рисовать не надо. То есть, каждую грань надо обрезать плоскостью z = -dist. Принципиально различных случаев расположения грани относительно этой плоскости может быть всего четыре; когда перед камерой находятся соответственно 0, 1, 2 или 3 вершины. Первый и последний случаи тривиальны - если перед камерой находится 0 вершин, то грань просто не видна и рисовать ее не надо; если 3 вершины, то грань видна целиком и полностью и ее достаточно просто взять и нарисовать. Рассмотрим оставшиеся два случая.

Случай первый, когда перед камерой находится только одна вершина:

В этом случае перед камерой находится только треугольник CDE. Его и надо будет нарисовать вместо грани.

Случай второй, когда перед камерой находятся две вершины:

Здесь уже надо будет нарисовать трапецию DABE; она разбивается на два треугольника, DAB и DBE. Их и рисуем вместо грани.

Координаты и текстурные координаты для точек D, E считаются совсем просто: с одной стороны, D лежит на AC, с другой стороны, D.z = -dist. Для точки D как лежащей на AC любая величина t (вместо t подставляем x/y/u/v) считается следующим образом:

D.t = A.t + (C.t - A.t) * (D.z - A.z) / (C.z - A.z) = A.t + (C.t - A.t) * (-dist - A.z) / (C.z - A.z)

Все это сводится в следующий алгоритм отрисовки грани:

выясняем, сколько вершин лежит перед камерой; то есть - какой из случаев мы имеем;

ставим точки A, B, C в соответствие с вершинами (то есть, если вершина v0 находится перед камерой, а вершины v1, v2 - нет, то имеем первый случай, где C = v0, A = v1, B = v2);

считаем, если нужно, координаты D, E;

рисуем (или добавляем в список отрисовки) полученные треугольники.

Осталось только добавить, что обрезание на самом деле надо проводить не плокостью z = -dist, а плоскостью z = -dist + smallvalue, smallvalue > 0, чтобы избежать проблем при проецировании.

3. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

Дадим словесное описание алгоритма z-буфера.

Заполнить буфер кадра фоном, а z-буфер памяти — числом zmin.

Преобразовать многогранник в растровую форму:

ax + by + cz + d = 0 — плоскость.

(x1, y1, z1)

(x2, y2, z2)

...

(xn, yn, zn)

a = S(yi - yi+1) * (zi + zi+1)

b = S(zi - zi+1) * (xi + xi+1)

c = S(xi - xi+1) * (yi + yi+1)

z = -(ax + by + d)/c. Выражаем изменение плоскости вдоль одной из осей.

z - z' = -(ax1 + d)/c + (ax + d)/c = a(x - x1)/c

z1 = z - (a/c)Dx, но Dx = 1, поэтому

z1 = z - (a/c), где z1 — новая координата, а z — старая координата.

Вычислить для каждой точки (x, y) многоугольника значение z(x, y) — глубины нахождения в прямоугольнике.

Сравнить полученное z с соответствующим zбуфера, полученным по координатам в буфере.

Если вычисленное z меньше zбуфера, то изображение помещаем в буфер кадра, а zбуфера присваиваем z.

4. Список функций процедур программы.

procedure StartMainAlgoritmClick(Sender: TObject);

Главная процедура. Удаляет невидимые линии методм z-буфера.

procedure FormCreate(Sender: TObject);

Процедура инициализации формы.

procedure StepBtnClick(Sender: TObject);

Добавляет фигуру к сцене.

procedure ResetBtnClick(Sender: TObject);

Очищает экран.

procedure ExitBtnClick(Sender: TObject);

Выход из приложения

procedure InitZbuffer;

Создаёт z-буфер.

procedure InitScreenBuffer;

Создаёт пустой буфер экрана.

procedure DrawScreenBuffer;

Выводит на экран содержимое буфера.

function InitFigure:TFigures;

Возвращает случайную фигуру.

procedure MainAlgoritm(fig:TFigures);

Процедура реализующая метод z-буфера.

5. ОПИСАНИЕ ПРОГРАММЫ

5.1. Системные требования.

Для нормальной работы программы необходимо:

Процессор Intel 8086/88 или любые более поздние модели

Операционная система Windows

Монитор любой цветной

5.2. Руководство пользователя

Навигации по программе осуществляется с помощью панели управления, имеющей простой и понятный интерфейс:

5.3. Листинг программы

unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls, ComCtrls;type TPoints = record x:integer; y:integer; z:integer; end; TFigures = record P:array[1..3]of TPoints; MinX,MinY,MaxX,MaxY:Word; A,B,C,D:integer; color:TColor; end; type TForm1 = class(TForm) Image: TImage; pb: TProgressBar; GroupBox1: TGroupBox; Label1: TLabel; CountEdit: TEdit; StartMainAlgoritm: TButton; StepBtn: TButton; ResetBtn: TButton; ExitBtn: TButton; GroupBox2: TGroupBox; procedure StartMainAlgoritmClick(Sender: TObject); procedure FormCreate(Sender: TObject); procedure StepBtnClick(Sender: TObject); procedure ResetBtnClick(Sender: TObject); procedure ExitBtnClick(Sender: TObject); procedure AboutBtnClick(Sender: TObject); private { Private declarations }procedure InitZbuffer;procedure InitScreenBuffer;procedure DrawScreenBuffer;function InitFigure:TFigures; public { Public declarations } end; var Form1: TForm1; MaxX,MaxY:Word; MinDepth:byte; Screenbuffer:array[1..400,1..400] of TColor; Zbuffer:array[1..400,1..400]of Byte; fig:TFigures; implementation {$R *.dfm}uses Unit2,Unit3; procedure TForm1.FormCreate(Sender: TObject);beginRandomize;MaxX:=Image.Width;MaxY:=Image.Height;MinDepth:=0;InitZbuffer;InitScreenBuffer;Image.Canvas.Refresh;end; procedure MainAlgoritm(fig:TFigures);vari,j:integer;z:Byte;color:TColor;beginfor j:=1 to MaxY dobegin for i:=1 to MaxX do begin color:=Form1.Image.Canvas.Pixels[i,j]; if(color=fig.color)then begin z:=round(-(fig.A*i + fig.B*j + fig.D)/fig.C); if(z>Zbuffer[i,j])then begin Zbuffer[i,j]:=z; Screenbuffer[i,j]:=color; end; end; end;end; end; procedure TForm1.StartMainAlgoritmClick(Sender: TObject);vari:integer;Count:integer;beginimage.Canvas.TextOut(150,150,'Пожалуйста подождите');try Count:=Strtoint(CountEdit.Text); pb.Max:=Strtoint(CountEdit.Text);except on EConvertError do begin MessageDlg('Введите правильное число!',mtWarning,[mbOK], 0); exit; end;end;pb.Position:=1; for i:=1 to Count do begin fig:=InitFigure; MainAlgoritm(fig); DrawScreenBuffer; pb.Position:=i+1; end; pb.Position:=0;end; procedure TForm1.StepBtnClick(Sender: TObject);begin pb.Max:=1; pb.Position:=1; fig:=InitFigure; MainAlgoritm(fig); DrawScreenBuffer; pb.Position:=0;end; procedure TForm1.ResetBtnClick(Sender: TObject);beginInitZbuffer;InitScreenBuffer;DrawScreenBuffer;end; procedure TForm1.AboutBtnClick(Sender: TObject);beginForm3.ShowModal;end; procedure TForm1.ExitBtnClick(Sender: TObject);beginClose;end; end. procedure InitZbuffer;vari,j:integer;beginfor i:=1 to MaxX dobegin for j:=1 to MaxY do begin Zbuffer[i,j]:=MinDepth; end;end;end; procedure InitScreenBuffer;vari,j:integer;beginfor i:=1 to MaxX dobegin for j:=1 to MaxY do begin ScreenBuffer[i,j]:=clWhite; end;end;end; procedure DrawScreenBuffer;vari,j:integer;beginwith Form1.Image.Canvas dobegin for i:=1 to MaxX do begin for j:=1 to MaxY do begin Pixels[i,j]:=Screenbuffer[i,j]; end; end;end;end; procedure Plane(var fig:TFigures);beginwith fig dobegin A:=p[1].y*(p[2].z-p[3].z) + p[2].y*(p[3].z-p[1].z) + p[3].y*(p[1].z-p[2].z); B:=p[1].z*(p[2].x-p[3].x) + p[2].z*(p[3].x-p[1].x) + p[3].z*(p[1].x-p[2].x); C:=p[1].x*(p[2].y-p[3].y) + p[2].x*(p[3].y-p[1].y) + p[3].x*(p[1].y-p[2].y); D:=-( p[1].x*(p[2].y*p[3].z - p[3].y*p[2].z) + p[2].x*(p[3].y*p[1].z - p[1].y*p[3].z) + p[3].x*(p[1].y*p[2].z - p[2].y*p[1].z) );end;end; procedure BorderPoints(var fig:TFigures);begin with fig do begin MinX:=Min(Min(p[1].x,p[2].x),p[3].x); MinY:=Min(Min(p[1].y,p[2].y),p[3].y); MaxX:=Max(Max(p[1].x,p[2].x),p[3].x); MaxY:=Max(Max(p[1].y,p[2].y),p[3].y); end;end; function InitFigure:TFigures;vari:byte;fig:TFigures;poligon:array[1..3]of TPoint;beginfor i:=1 to 3 dobegin fig.P[i].x:=Random(MaxX);poligon[i].X:=fig.P[i].x; fig.P[i].y:=Random(MaxY);poligon[i].Y:=fig.P[i].y; fig.P[i].z:=Random(254)+1; end;Plane(fig);BorderPoints(fig);fig.color:=Random($FFFFFF);Form1.Image.Canvas.Brush.Color:=fig.color;Form1.Image.Canvas.Pen.Color:=fig.color;Form1.Image.Canvas.Polygon(poligon);Result:=fig;end; end.

6. ЛИТЕРАТУРА

1. П. В. Вельтмандер. Учебное пособие «Основные алгоритмы компьютерной графики».

2. А. В. Казанцев. Тексты специального курса лекций «Основы компьютерной графики»

3. А. Ю. Дёмин, А.В. Кудинов. Учебное пособие «Компьютерная графика».

4. Ньюмен. У., Спрулл Р. «Основы интерактивной машинной графики»

5. Котов И. И. «Алгоритмы машинной графики»