Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Кафедра інформаційних технологій видавничої справи
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки
Предмет:
Комп'ютерна графіка
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КОМП’ЮТЕРНА ГРАФІКА
МЕТОДИЧНІ ВКАЗІВКИ
до виконання лабораторної роботи № 7
Алгоритм Брезенхема для генерації кола
для студентів бакалаврського рівня підготовки спеціальності
«Комп‘ютерні науки» та «Видавничо-поліграфічна справа»
Затверджено на засіданні кафедри
Інформаційні технології видавничої справи
Протокол № 5-11/12 від 23 грудня 2011 р.
Львів – 2012
Алгоритм Брезенхема для генерації кола: Методичні вказівки до лабораторної роботи № 7 з курсу “Комп’ютерна графіка” для студентів «Видавничо-поліграфічна справа» (шифр - 0927) та “Комп‘ютерні науки” (шифр - 0804) / Укл.: О.Я. Різник - Львів: Видавництво Національного університету “Львівська політехніка”, 2012 - 14 с.
Укладач: Різник О.Я., к.т.н., доц.
Відповідальний за випуск: Різник О. Я., к. т. н., доц.
Рецензент: Рашкевич Ю.М., д.т.н., проф.
ЛАБОРАТОРНА РОБОТА № 7
АЛГОРИТМ БРЕЗЕНХЕМА ДЛЯ ГЕНЕРАЦІЇ КОЛА
Мета роботи: Освоїти алгоритми побудови кола засобами комп’ютерної графіки
ТЕОРЕТИЧНІ ВІДОМОСТІ
У растр розкладають не тільки лінійні, але й інші, більш складні функції. Розкладанню конічних перетинів, тобто кіл, еліпсів, парабол, гіпербол було присвячено значне число робіт. Найбільша увага, зрозуміло, приділена колу. Один з найбільш ефективних і простих для розуміння алгоритмів генерації кола належить Брезенхему. Для початку відзначимо, що необхідно згенерувати тільки одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на рис. 7.1. Якщо згенерований перший октант (від 0 до 45° проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої y=х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х=0 для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої y=0 для завершення побудови. На рис.7.1 наведені двовимірні матриці відповідних перетворень.
Рис.7.1. Генерація повного кола з дуги в першому октанті
Для виведення алгоритму розглянемо першу чверть кола з центром у початку координат. Помітимо, що якщо робота алгоритму починається в точці х=0, у=R, то при генерації кола за годинниковою стрілкою в першому квадранті у є монотонно спадною функцією аргумента х (рис.5.2). Аналогічно, якщо вихідною точкою є у=0, х=R, то при генерації кола проти годинникової стрілки х буде монотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці х=0, у=R. Передбачається, що центр кола і початкова точка знаходяться точно в точках растра.
Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, що щонайкраще наближає коло: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. На рис.7.3 ці напрямки позначені відповідно mH, mD, mV. Алгоритм вибирає піксел, для якого мінімальний квадрат відстані між одним з цих положень і колом, тобто мінімум з
mH=|(xi+1)2+(yi)2-R2|
mD=|(xi+1)2+(yi-1)2-R2|
mV=|(xi)2+(yi-1)2-R2|
Рис. 7.2. Коло у першому квадранті Рис.7.3. Вибір пікселів у першому квадранті
Обчислення можна спростити, якщо зауважити, що в околі точки (xi, yi) можливі тільки п’ять типів перетинів кола і сітки растра, наведених на рис.7.4.
Рис. 7.4. Перетини кола і сітки растра
Різниця між квадратами відстаней від центра кола до діагонального піксела (xi+1, уi-1) і від центра до точки на колі R2 дорівнює:
Di=(xi+1)2+(yi-1)2-R2
Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного піксела бажано використовувати тільки знак похибки, а не її величину.
При Di<0 діагональна точка (xi+1, уi-1) знаходиться всередині реального кола, тобто це випадки 1 або 2 на рис. 7.4. Ясно, що в цій ситуації варто вибрати або піксел (xi+1, уi), тобто mH, або піксел (xi+1, уi-1), тобто mD. Для цього спочатку розглянемо випадок 1 і перевіримо різницю квадратів відстаней від кола до пікселів у горизонтальному і діагональному напрямках:
d=|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|.
При d<0 відстань від кола до діагонального піксела більша, ніж до горизонтального. Навпаки, якщо d>0, відстань до горизонтального піксела більша. Таким чином,
при d<=0 вибираємо mH (xi+1, уi)
при d>0 вибираємо mD (xi+1, уi-1).
При d=0, коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок.
Кількість обчислень, необхідних для оцінки величини d, можна скоротити, якщо помітити, що у випадку 1:
(xi+1)2+(yi)2-R2>=0
(xi+1)2+(yi-1)2-R2<0,
тому що діагональний піксел (xi+1, уi-1) завжди лежить всередині кола, а горизонтальний (xi+1, уi) - поза ним. Таким чином, d можна обчислити за формулою:
d=(xi+1)2+(yi)2-R2+(xi+1)2+(yi-1)2-R2.
Доповнення до повного квадрата члена (yi)2 за допомогою додавання і віднімання - 2yi+1 дає:
d=2[(xi+1)2+(yi-1)2-R2]+2yi-1.
У квадратних дужках стоїть по визначенню Di і його підстановка
d=2(Di+yi)-1,
що значно спрощує вираз.
Розглянемо випадок 2 на рис.7.4 і помітимо, що тут повинен бути обраним горизонтальний піксел (xi+1, уi), тому що у є монотонно спадною функцією. Перевірка компонентів d показує, що:
(xi+1)2+(yi)2-R2<0
(xi+1)2+(yi-1)2-R2<0
оскільки у випадку 2 горизонтальний (xi+1, уi) і діагональний (xi+1, уi-1) піксели лежать усередині кола. Отже, d<0, і при використанні того ж самого критерію, що й у випадку 1, вибирається піксел (xi+1, уi).
Якщо Di>0, то діагональна точка (xi+1, уi-1) знаходиться поза колом, тобто це випадки 3 і 4 на рис.7.4. У даній ситуації ясно, що потрібно вибрати піксел (xi+1, уi-1), або (xi, уi -1). Аналогічно розгляду попереднього випадку критерій вибору можна отримати, розглядаючи спочатку випадок 3 і перевіряючи різницю між квадратами відстаней від кола до діагонального mD і
вертикального mV пікселів, тобто:
d’=|(xi+1)2+(yi-1)2-R2|-|(xi)2+(yi-1)2-R2|.
При d’<0 відстань від кола до вертикального піксела (xi, уi -1) більша і варто вибрати діагональний крок до піксела (xi+1, уi-1). Навпаки, у випадку d’>0 відстань від кола до діагонального піксела більша і варто вибрати вертикальний рух до піксела (xi, уi-1). Таким чином,
при d’<=0 вибираємо mD (xi+1, уi-1)
при d’>0 вибираємо mV (xi, уi-1)
Тут для випадку d’=0, тобто коли відстані рівні, обраний діагональний крок.
Перевірка компонентів d’ показує, що
(xi)2+(yi-1)2-R2>=0
(xi+1)2+(yi-1)2-R2<0,
оскільки для випадку 3 діагональний піксел (xi+1, уi-1) знаходиться поза колом, тоді як вертикальний піксел (xi, уi-1) лежить всередині кола. Це дозволяє записати d’ у вигляді:
d’=(xi+1)2+(yi-1)2-R2+(xi)2+(yi-1)2-R2
Доповнення до повного квадрата члена (xi)2 за допомогою додавання і віднімання 2xi+1 дає:
d’=2[(xi+1)2+(yi-1)2-R2]-2xi-1
Використання визначення Di приводить вираз до вигляду
d’=2(Di-xi)-1.
Тепер, розглядаючи випадок 4, знову зауважимо, що варто вибрати вертикальний піксел (xi, уi-1), тому що y є монотонно спадною функцією від х.
Перевірка компонентів d’ для випадку 4 показує, що
(xi+1)2+(yi-1)2-R2>0
(xi)2+(yi-1)2-R2>0
оскільки обидва піксели знаходяться поза колом. Отже, d’>0 і при використанні критерію, розробленого для випадку 3, відбувається вірний вибір mV.
Залишилося перевірити тільки випадок 5 на рис.7.4, який зустрічається, коли діагональний піксел (xi+1, уi-1) лежить на колі, тобто Di=0. Перевірка компонентів d показує, що
(xi+1)2+(yi)2-R2>0
(xi+1)2+(yi-1)2-R2=0
Отже, d>0 і вибирається діагональний піксел (xi+1, уi-1). Аналогічним чином оцінюємо компоненти d’:
(xi+1)2+(yi-1)2-R2=0
(xi+1)2+(yi-1)2-R2<0
і d’<0, що є умовою вибору правильного діагонального кроку до (xi+1, уi-1). Таким чином, випадок Di=0 підлягає тому ж критерію, що і випадок Di<0 чи Di>0. Оцінимо результати:
Di<0
d<=0 вибираємо піксел (xi+1, уi)-mH
d>0 вибираємо піксел (xi+1, уi-1)-mD
Di>0
d’<=0 вибираємо піксел (xi+1, уi-1)- mD
d’>0 вибираємо піксел (xi, уi-1)-mV
Di=0 вибираємо піксел (xi+1, уi-1)-mD
Покроковий алгоритм Брезенхема для генерації 1/8 кола
Усі змінні - цілі, R- радіус кола.
xi=0
yi=R
1: while yi >=0 do
Di=(xi+1)2+(yi-1)2-R2
Plot (xi, yi)
if Di<0 then 2
if Di>0 then 3
if Di=0 then 4
визначення випадку 1 чи 2
2: d=|(xi+1)2+(yi)2-R2|-|(xi+1)2+(yi-1)2-R2|
if d<=0 then
хi=хi+1
else
begin
xi=хi+1
y i=yi-1
end;
goto 1
3: d’=|(xi+1)2+(yi-1)2-R2|-|(xi)2+(yi-1)2-R2|.
If d’<=0 then
begin
xi=хi+1
yi=yi-1
end else
yi=yi-1
goto 1
4: xi=хi+1
yi=yi-1
goto 1
end {while}
finish
Цей алгоритм будує 1/8 кола, для чого це потрібно, оскільки промальовка великого кола таким методом, займає багато часу і ресурсів. Тому краще промалювати 1/8 кола, а потім методами відображення та поворотів, цю 1/8 кола відобразити, тим самим зекономити час та ресурси.
ПОРЯДОК ВИКОНАННЯ РОБОТИ
Ознайомитися з алгоритмом Брезенхема для генерації кола.
Розробити графічний інтерфейс у вигляді пікселів, котрі будуть підсвічуватися при генерації кола.
Здійсніть генерацію кола за алгоритмом Брезенхема, у якому би підсвічувалися піксели, або ж клітинки сітки.
Проаналізуйте результати.
ЗМІСТ ЗВІТУ
Назва роботи.
Мета роботи.
Короткий теоретичний вступ.
Завдання до лабораторної роботи.
Тексти розроблених і відлагоджених программ.
Малюнки з реалізацією програми.
Висновки.
ПРИКЛАД ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
unit Unit1;
interface
uses
StdCtrls, Controls, ExtCtrls, Spin, Classes,forms,graphics,SysUtils;
type
b=array[1..2,1..2] of real;
TForm1 = class(TForm)
p: TPaintBox;
Label1: TLabel;
Label2: TLabel;
SpinEdit1: TSpinEdit;
Panel1: TPanel;
Panel2: TPanel;
r1: TRadioButton;
r2: TRadioButton;
procedure pPaint(Sender: TObject);
procedure pMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure pMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
procedure pMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure SpinEdit1Change(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Panel2Click(Sender: TObject);
procedure Panel1Click(Sender: TObject);
procedure r2Click(Sender: TObject);
end;
var
Form1: TForm1;
pos:b;
DR:boolean=false;
temp_x,temp_y:real;
dx:integer;
lab:byte=6;
implementation
{$R *.DFM}
procedure draw_7;
var x,y,di,d,R:real;
i:byte;
begin
x:=0;
y:=pos[2,2]-pos[1,2];
r:=y;
while y>=0 do
begin
di:=sqr(x+1)+sqr(y-1)-sqr(R);
form1.p.Canvas.Pen.Mode:= pmCopy;
for i:=1 to 4 do
begin
if x<0 then x:=-x;
if y<0 then y:=-y;
case i of
1: x:=-x;
2: y:=-y;
3: begin
x:=-x;
y:=-y;
end;
end;
if form1.r2.Checked then
begin
form1.p.Canvas.brush.Color:=cllime;
form1.p.Canvas.Rectangle(round((x+pos[1,1]) *dx),round((y+pos[1,2])*dx),
round((x+pos[1,1])*dx)+dx, round((y+pos[1,2])*dx)+dx);
form1.p.Canvas.brush.Color:=clblack
end
else
begin
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width+10;
form1.p.Canvas.MoveTo(round((x+pos[1,1])*dx), round((y+pos[1,2])*dx));
form1.p.Canvas.LineTo(round((x+pos[1,1])*dx), round((y+pos[1,2])*dx));
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width-10;
end;
end;
if di<0 then
begin //1
d:=Abs(sqr(x+1)+sqr(y)-sqr(R))-Abs(sqr(x+1)+sqr(y-1)-sqr(R));
if d<=0 then
begin //2
x:=x+1;
end //2
else
begin //3
x:=x+1;
y:=y-1;
end //3
end //2
else
if di>0 then
begin //1a
d:=Abs(sqr(x+1)+sqr(y-1)-sqr(R))-Abs(sqr(x)+sqr(y-1)-sqr(R));
if d<=0 then
begin //2a
x:=x+1;
y:=y-1;
end //2a
else
begin //3a
y:=y-1;
end // 3a
end //1a
else
if di=0 then
begin //1z
x:=x+1;
y:=y-1;
end //1z
end;
end;
procedure draw_6;
var pos_x,pos_y,pos_xx,pos_yy:real;
i:integer;
Dy,Dxx,l:real;
delta:boolean;
begin
form1.p.Canvas.Brush.Style:=bssolid;
if abs(pos[2,1]-pos[1,1])>=abs(pos[2,2]-pos[1,2]) then
L:=abs((pos[2,1]-pos[1,1])) else L:=abs(pos[2,2]-pos[1,2]) ;
dxx:=((pos[2,1]-pos[1,1])/l)*dx;
dy:=((pos[2,2]-pos[1,2])/l)*dx;
pos_x:=((pos[1,1]*dx));
pos_y:=((pos[1,2]*dx));
i:=1; form1.p.Canvas.Brush.Color:=cllime;
if form1.r2.Checked then
form1.p.Canvas.Rectangle(round(pos_x), round(pos_y),
round(pos_x+dx),round(pos_y+dx))
else
begin
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width+10;
form1.p.Canvas.MoveTo(round(pos_x), round(pos_y));
form1.p.Canvas.LineTo(round(pos_x), round(pos_y));
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width-10;
end;
form1.p.Canvas.Brush.Color:=clblack;
while i<=l do
begin
pos_xx:=0;
pos_yy:=0;
delta:=false;
pos_x:=(pos_x+dxx);
pos_y:=(pos_y+dy);
form1.p.Canvas.Brush.Style:=bssolid;
form1.p.Canvas.Brush.Color:=cllime;
begin
if (round(pos_y) mod dx) <>0 then
begin
pos_yy:=round((pos_y) / dx);
if ((pos_Y-(pos_yy*DX))> dx/2) or ((pos_Y-(pos_yy*DX))*-1> (dx/2)) then
delta:=true;
if delta then
pos_yy:=pos_yy+1;
pos_yy:=pos_yy*dx;
pos_xx:=pos_x;
delta:=false;
end else pos_yy:=pos_y;
if (round(pos_x) mod dx) <>0 then
begin
pos_xx:=round((pos_x) / dx);
if ((pos_x-(pos_xx*DX))> dx/2) or ((pos_x-(pos_xx*DX))*-1> (dx/2)) then
delta:=true;
if delta then
pos_xx:=pos_xx+1;
pos_xx:=pos_xx*dx;
pos_yy:=pos_y;
delta:=false;
end else pos_xx:=pos_x; end;
if form1.r1.Checked then
begin
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width+10;
form1.p.Canvas.MoveTo(round(pos_xx), round(pos_yy));
form1.p.Canvas.LineTo(round(pos_xx), round(pos_yy));
form1.p.Canvas.Pen.Width:= form1.p.Canvas.Pen.Width-10;
end else
form1.p.Canvas.Rectangle(round(pos_xx), round(pos_yy),
round(pos_xx+dx),round(pos_yy+dx));
form1.p.Canvas.Brush.Color:=clblack;
inc(i);
end;
end;
procedure TForm1.pPaint(Sender: TObject);
var i:integer;
begin
p.Canvas.FillRect(clientrect); i:=0;
p.Canvas.Pen.Color:=clgray;
while i<=p.Width do
begin
p.Canvas.moveto(i,0);
p.Canvas.lineto(i,p.Height);
inc(i,dx);
end; i:=0;
while i<=p.height do
begin
p.Canvas.moveto(0,i);
p.Canvas.lineto(p.width,i);
inc(i,dx);
end;
end;
procedure TForm1.pMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
ppaint(form1);
DR:=true;
pos[1,1]:=x;
pos[1,2]:=y;
temp_x:=pos[1,1];
temp_y:=pos[1,2];
end;
procedure TForm1.pMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
begin
if dr then
begin
p.Canvas.Pen.Mode:=pmxor;
p.Canvas.MoveTo(round(pos[1,1]), round(pos[1,2]));
p.Canvas.lineTo(round(temp_x), round(temp_y));
p.Canvas.Pen.Color:=clyellow;
pos[2,1]:=x;
pos[2,2]:=y;
form1.Canvas.Font.Color:=cllime;
label1.Caption:=’X = ‘+IntToStr(Round(pos[2,1]/dx))+#10+#13+’Y = ‘+IntToStr(Round(pos[2,2]/dx));
p.Canvas.MoveTo(round(pos[1,1]), round(pos[1,2]));
p.Canvas.lineTo(round(x),round(y));
temp_x:=x;
temp_y:=y;
end;
end;
procedure TForm1.pMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var i:byte;
begin
i:=0;
if round(pos[1,1]) mod dx <>0 then
while round(pos[1,1]-i) mod dx <>0 do
inc(i);
pos[1,1]:=pos[1,1]-i;
i:=0;
if round(pos[1,2]) mod dx <>0 then
while round(pos[1,2]-i) mod dx <>0 do
inc(i);
pos[1,2]:=pos[1,2]-i ;
i:=0;
if round(x) mod dx <>0 then
while round(x-i) mod dx <>0 do
inc(i);
pos[2,1]:=x-i;
i:=0;
if round(y) mod dx <>0 then
while round(y-i) mod dx <>0 do
inc(i);
pos[2,2]:=y-i ;
pos[2,1]:=pos[2,1] / dx;
pos[2,2]:=pos[2,2] / dx;
pos[1,1]:=pos[1,1] / dx;
pos[1,2]:=pos[1,2] / dx;
dr:=false;
if (pos[1,1]<>pos[2,1])or(pos[2,2]<>pos[1,2]) then
case lab of
6:draw_6;
7:draw_7;
end
end;
procedure TForm1.SpinEdit1Change(Sender: TObject);
begin
if SpinEdit1.Value>0 then
dx:=SpinEdit1.Value;
ppaint(form1);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
SpinEdit1.Value:=50;
dx:=SpinEdit1.value;
end;
procedure TForm1.Panel2Click(Sender: TObject);
begin
panel2.BevelOuter:=bvLowered;
panel2.Color:=clActiveBorder;
panel1.BevelOuter:=bvRaised;
panel1.Color:=clBtnFace;
form1.Caption:=’LAB 7';
lab:=7;
end;
procedure TForm1.Panel1Click(Sender: TObject);
begin
panel1.BevelOuter:=bvLowered;
panel1.Color:=clActiveBorder;
panel2.BevelOuter:=bvRaised;
panel2.Color:=clBtnFace;
form1.Caption:=’LAB 6';
lab:=6;
end;
procedure TForm1.r2Click(Sender: TObject);
begin
case lab of
6:draw_6;
7:draw_7;
end;
end;
end.
НАВЧАЛЬНЕ ВИДАННЯ
КОМП’ЮТЕРНА ГРАФІКА
МЕТОДИЧНІ ВКАЗІВКИ
до виконання лабораторної роботи № 7
Алгоритм Брезенхема для генерації кола
для студентів бакалаврського рівня підготовки спеціальності
«Комп‘ютерні науки» та «Видавничо-поліграфічна справа»
Укладач: Різник Олег Яремович
Комп’ютерне складання та верcтання: Скрибайло-Леськів Даніель Юрієвич
13.04.2014 21:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора