Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Група:
КН-11
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота №7
З курсу:
«Комп’ютерна графіка»
Тема: Алгоритм Брезенхема для генерації кола.
Мета: Освоїти алгоритм побудови кола засобами комп’ютерної графіки
ТЕОРЕТИЧНІ ОСНОВИ
Один з найбільш ефективних і простих для розуміння алгоритмів генерації кола належить Брезенхему. Для початку відмітимо, що необхідно згенерувати тільки одну восьму частину кола. Інші його частини можуть бути отримані послідовними відображеннями, як це показано на рис. 5.1. Якщо згенерований перший октант (від 0 до 45° проти годинникової стрілки), то другий октант можна отримати дзеркальним відображенням відносно прямої y=х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х=0 для отримання відповідної частини кола в другому квадранті. Верхнє півколо відбивається відносно прямої y=0 для завершення побудови. На рис.5.1 наведені двовимірні матриці відповідних перетворень.
Рис.5.1. Генерація повного кола з дуги в першому октанті.
Для виведення алгоритму розглянемо першу чверть кола з центром у початку координат. Помітимо, що якщо робота алгоритму починається в точці х=0, у=R, то при генерації кола за годинниковою стрілкою в першому квадранті у є монотонно спадною функцією аргумента х (рис.5.2). Аналогічно, якщо вихідною точкою є у=0, х=R, то при генерації кола проти годинникової стрілки х буде монотонно спадною функцією аргументу у. У нашому випадку вибирається генерація за годинниковою стрілкою з початком у точці х=0, у=R. Передбачається, що центр кола і початкова точка знаходяться точно в точках растра.
Для будь-якої заданої точки на колі при генерації за годинниковою стрілкою існує тільки три можливості вибрати наступний піксел, що щонайкраще наближає коло: горизонтально вправо, по діагоналі вниз і вправо, вертикально вниз. На рис.5.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|
Рис. 5.2. Коло у першому квадранті.
Рис.5.3. Вибір пікселів у першому квадранті.
Обчислення можна спростити, якщо зауважити, що в околі точки (xi, yi) можливі тільки п'ять типів перетинів кола і сітки растра, наведених на рис.5.4.
Рис. 5.4. Перетини кола і сітки растра.
Різниця між квадратами відстаней від центра кола до діагонального піксела (xi+1, уi-1) і від центра до точки на колі R2 дорівнює
Di=(xi+1)2+(yi-1)2-R2
Як і в алгоритмі Брезенхема для відрізка, для вибору відповідного піксела бажано використовувати тільки знак похибки, а не її величину.
При Di<0 діагональна точка (xi+1, уi-1) знаходиться всередині реального кола, тобто це випадки 1 або 2 на рис. 5.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, коли відстань від кола до обох пікселів однакова, вибираємо горизонтальний крок.
. Підіб'ємо підсумок отриманих результатів:
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
Реалізація алгоритму Брезенхема на псевдокоді для кола наводиться нижче.
Текст программного коду:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, ExtCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Image1: TImage;
Label2: TLabel;
Edit1: TEdit;
procedure Button1Click(Sender: TObject);
procedure koord();
procedure draw_P(x_k,y_k:integer);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
x0,y0,delta:integer;
implementation
procedure TForm1.koord();
var delta_p,x1,x2,x3,x4,y1,y2,y3,y4,i:integer;
begin
x0:=round(image1.Width/2);
y0:=round((image1.Height)/2);
with image1.Canvas do
begin
if (image1.Width-x0)>(image1.Height-y0) then
delta:=round((image1.Height-y0)/10)
else
delta:=round((image1.Width-x0)/10);
x1:=x0;
x2:=x0;
x3:=x0;
x4:=x0;
y1:=y0;
y2:=y0;
y3:=y0;
y4:=y0;
for i:=0 to 30 do begin
delta_p:=delta;
MoveTo(x0,y1);
LineTo(x0,y1-delta_p);
moveto(x0-2,y1-delta_p);
LineTo (x0+2,y1-delta_p);
y1:=y1-delta_p;
MoveTo(x0,y2);
LineTo(x0,y2+delta_p);
moveto(x0-2,y2+delta_p);
LineTo (x0+2,y2+delta_p);
y2:=y2+delta_p;
MoveTo(x3,y0);
LineTo(x3+delta_p,y0);
moveto(x3+delta_p,y0-2);
LineTo (x3+delta_p,y0+2);
x3:= x3+delta_p;
MoveTo(x4,y0);
LineTo(x4-delta_p,y0);
moveto(x4-delta_p,y0-2);
LineTo (x4-delta_p,y0+2);
x4:= x4-delta_p;
end;
x1:=x0;
x2:=x0;
x3:=0;
x4:=x0;
y1:=Image1.Height;
y2:=y0;
y3:=y0;
y4:=y0;
for i:=0 to 30 do begin
delta_p:=delta;
pen.Style:=psDot;
moveto(0,y1-delta_p);
LineTo (image1.Width,y1-delta_p);
moveto(x3+delta_p,0);
LineTo (x3+delta_p,image1.Height);
y1:=y1-delta_p;
x3:= x3+delta_p;
end;
end;
end;
procedure TForm1.draw_P(x_k,y_k:integer);
var xx,yy,col:integer;
begin
with image1.Canvas do
begin
pen.Color:=clblack;
pen.Width:=7;
xx:=x0+x_k*delta;
yy:= y0-y_k*delta;
MoveTo(xx,yy);
LineTo(xx,yy);
pen.Width:=1;
TextOut(x0+x_k*delta,y0+7,inttostr(x_k));
TextOut(x0+7,y0-y_k*delta,inttostr(y_k));
pen.Style:=psSolid;
end;
end;
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
i,j,l,x_t,y_t,R,D,dm:integer;
begin
image1.Canvas.FillRect(Rect(0,0,image1.Width,image1.Height));
image1.Transparent:=true;
koord();
R:=strtoint(Edit1.Text);
x_t:=0;
y_t:=R;
image1.Canvas. pen.Color:=clblue;
image1.Canvas. pen.Width:=1;
image1.Canvas.Arc(x0+r*delta,y0+r*delta,x0-r*delta,y0-r*delta,x0,y0+r*delta,x0-1,y0+r*delta-1);
while y_t>=0 do begin
D:=sqr(x_t+1)+sqr(y_t-1)-sqr(r);
draw_P(x_t,y_t);
draw_P(-x_t,y_t); //v 1 okt (-1 0 0 1)
draw_P(-x_t,-y_t); //v 4 okt (-1 0 0 -1)
draw_P(x_t,-y_t); //v 3 okt (-1 0 0 -1)
if D<0 then begin
dm:=abs(sqr(x_t+1)+sqr(y_t)-sqr(r))- abs(sqr(x_t+1)+sqr(y_t-1)-sqr(r));
if dm<=0 then
x_t:=x_t+1
else begin
x_t:=x_t+1;
y_t:=y_t-1;
end;
end;
if D>0 then begin
dm:=abs(sqr(x_t+1)+sqr(y_t-1)-sqr(r))- abs(sqr(x_t)+sqr(y_t-1)-sqr(r));
if dm<=0 then begin
y_t:=y_t-1;
x_t:=x_t+1 ;
end
else begin
y_t:=y_t-1;
end;
end;
if D=0 then begin
y_t:=y_t-1;
x_t:=x_t+1 ;
end;
end;
end;
end.
Результати роботи програми:
Висновок: На даній лабораторній роботі був освоєний алгоритм алгоритм Брезенхема для побудови кола засобами комп’ютерної графіки.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора