Kü thuËt §å ho¹ m¸y tÝnh
28
intr($10,R);
End;
Procedure write_color_reg(index: Integer;color: RGB_COLOR_TYP);
Begin
port[COLOR_REG_WR]:=index;
port[COLOR_DATA]:=color.red;
port[COLOR_DATA]:=color.green;
port[COLOR_DATA]:=color.blue;
End;
Var
VIDEO_BUFFER : Word;
gm,index,n: integer;
color: RGB_COLOR_TYP;
Begin
clrscr;
VIDEO_BUFFER:=$A000;
gm:=$13;
set_mode(gm);
index:=0;
n:=2;
Repeat
n:=n+b;
color.red:=n;
color.green:=0;
color.blue:=n;
write_color_reg(index,color);
Delay(150);
If n>60 Then b:=-1;
If n<4 Then b:=1;
Until KeyPressed;
gm:=3; (* Text Mode *)
set_mode(gm);
End.
$3. C¸c thuËt to¸n vÏ ®o¹n th¼ng,
®−êng trßn
I. VÏ ®o¹n th¼ng :
Kü thuËt §å ho¹ m¸y tÝnh
29
Gi¶ sö ta cÇn vÏ ®o¹n th¼ng ®i qua 2 ®iÓm (x1, y1) vµ (x2, y2), th× hÖ sè gãc cña nã
lµ m=dy/dx, trong ®ã dy=y2-y1; dx=x2-x1 vµ ph−¬ng tr×nh ®−êng th¼ng sÏ lµ
y=m.x+b víi b=y1-m.x1;
1. VÏ ®o¹n th¼ng b»ng c¸ch lµm trßn sè :
a. Tr−êng hîp x1=x2 :
trong tr−êng hîp nµy ®o¹n th¼ng lµ ®−êng song song víi trôc tung
b. Tr−êng hîp y1=y2 :
trong tr−êng hîp nµy ®o¹n th¼ng lµ ®−êng song song víi trôc hoµnh
c. Trong tr−êng hîp 0<|m|<=1 :
Tr−êng hîp nµy lµ tr−êng hîp gi¸ trÞ tuyÖt ®èi cña hÖ sè gãc nhá h¬n 1 th× ta vÏ
®o¹n th¼ng b»ng c¸ch cho x ch¹y tõ x1 ®Õn x2 tÝnh y=Round(m.x+b) vµ vÏ ®iÓm
(x,y)
d. Trong tr−êng hîp |m|>1 :
Tr−êng hîp nµy lµ tr−êng hîp gi¸ trÞ tuyÖt ®èi cña hÖ sè gãc lín h¬n 1 ta viÕt l¹i
ph−¬ng tr×nh ®−êng ®Ó cho gi¸ trÞ tuyÖt ®èi cña hÖ sè gãc nhá h¬n 1 : x=(1/m)y-
b/m th× ta vÏ ®o¹n th¼ng b»ng c¸ch cho y ch¹y tõ y1 ®Õn y2 tÝnh
x=Round((1/m)y-b/m) vµ vÏ ®iÓm (x,y)
Ch−¬ng tr×nh trªn ch¹y chËm v× ph¶i tÝnh to¸n víi c¸c sè thùc.
Bµi tËp : LËp ch−¬ng tr×nh vÏ ®o¹n th¼ng theo thuËt to¸n trªn
2. ThuËt to¸n vÏ ®o¹n th¼ng cña Bresanham
Ta b¾t ®Çu b»ng c¸ch xÐt ®−êng th¼ng cã hÖ sè gãc n»m trong kho¶ng (0,1] v× c¸c
®iÓm trªn mµn h×nh ®−îc biÓu diÔn bëi c¸c to¹ ®é nguyªn nªn ta cho x t¨ng theo
b−íc nh¶y ®¬n vÞ tõ x1 ®Õn x2. Gi¶ sö trªn h×nh vÏ ®iÓm (x[i],y[i]) lµ ®iÓm n»m trªn
®o¹n th¼ng ®· ®−îc vÏ vµ cho x[i] t¨ng thªm 1 ®Ó vÏ ®iÓm tiÕp theo vµ gi¸ trÞ cña y
øng víi x[i]+1 ta nªn chän lµ y[i] hay y[i]+1, gi¸ trÞ ®óng cña y=m(x[i]+1)+b nh−
vËy ta sÏ tuú xem y[i] hay y[i]+1 gÇn y(=m(x[i]+1)+b) h¬n th× ta sÏ chän gi¸ trÞ ®ã.
Ta xÐt c¸c kho¶ng c¸ch :
Kho¶ng c¸ch gi÷a y vµ y[i] : d1=y-y[i]=m(x[i]+1)+b-y[i]
Kü thuËt §å ho¹ m¸y tÝnh
30
Kho¶ng c¸ch gi÷a y[i]+1 vµ y : d2=y[i]+1-y=y[i]+1-m(x[i]+1)-b
HiÖu gi÷a hai kho¶ng c¸ch nµy lµ : d1-d2=2m(x[i]+1)-2y[i]+2b-1
thay m=dy/dx ta cã d1-d2=2(dy/dx)(x[i]+1)-2y[i]+2b-1
nªn p[i]=dx(d1-d2)=2dy.x[i]+2dy-2dx.y[i]+2dx.b-dx
=2dy.x[i]-2dx.y[i]+2dy+dx(2b-1)
Hay p[i]=2dy.x[i]-2dx.y[i]+c víi c=2dy+dx(2b-1) (1)
thay i=1 ta cã p[1]=2dy.x1-2dy.y1+c=2dy-dx
NÕu p[i]<0 nghÜa lµ y[i] gÇn ®−êng th¼ng h¬n y[i]+1 vµ ta chän y[i+1]=y[i] ng−îc
l¹i ta chän y[i+1]=y[i]+1
C«ng thøc (1) cã thÓ ®−îc gi¶n l−îc b»ng c¸ch liªn hÖ víi ®iÓm
(x[i+1],y[i+1]) tiÕp theo, khi ®ã p[i+1]=2dy.x[i+1]-2dx.y[i+1]+c (2)
Trõ (2) cho (1) ta cã :
p[i+1]-p[i]=2dy(x[i+1]-x[i])-2dx(y[i+1]-y[i]) mµ x[i+1]=x[i]+1 nªn
p[i+1]=p[i]+2dy-2dx(y[i+1]-y[i])
Mµ nÕu p[i]<0 th× y[i+1] tiÕp theo sÏ ®−îc chän lµ y[i], nghÜa lµ y[i+1]=y[i] nªn
p[i+1]=p[i]+2dy=p[i]+const1 víi const1=2dy ng−îc l¹i chän y[i+1]=y[i]+1 nªn
p[i+1]=p[i]+2(dy-dx)=p[i]+const2 víi const2=2(dy-dx)
Vµ thuËt to¸n vÏ ®−êng th¼ng cña Presenham trong tr−êng hîp hÖ sè gãc n»m
trong kho¶ng (0,1] nh− sau :
1. NÕu x1>x2 Th× ta ho¸n vÞ 2 ®iÓm (x1,y1) vµ (x2,y2)
2. §Æt dx:=Abs(x2-x1); dy:=Abs(y2-y1);
p:=2*dy-dx; const1:=2*dy; const2:=2*(dy-dx);
3. §Æt x:=x1; y:=y1;
4. vÏ ®iÓm(x,y);
5. T¨ng x lªn 1 ®¬n vÞ
6. NÕu p<0 Th× p:=p+const1 vµ gi÷ nguyªn y
ng−îc l¹i p:=p+const2 va t¨ng y lªn 1 ®¬n vÞ;
7. KiÓm tra xem x cßn <= x2 kh«ng nÕu cßn quay lªn b−íc 4 ng−îc l¹i kÕt thóc
8. KÕt thóc
Vµ thñ tôc vÏ ®−êng th¼ng lµ :
Procedure Line_(x1,y1,x2,y2 : Integer);
Var
x,y,tg,dx,dy,const1,const2,p : Integer;
mau : Byte;
Begin
If x1>x2 Then
Begin
tg:=x1; x1:=x2; x2:=tg;
tg:=y1; y1:=y2; y2:=tg;
End;
dx:=Abs(x2-x1); dy:=Abs(y2-y1);
p:=2*dy-dx; const1:=2*dy;
const2:=2*(dy-dx);
mau:=GetColor;
Kü thuËt §å ho¹ m¸y tÝnh
31
x:=x1; y:=y1;
While x<=x2 Do
Begin
Putpixel(x,y,mau);
Inc(x);
If p<0 Then p:=p+const1
Else
Begin Inc(y); p:=p+const2; End;
End;
End;
Bµi tËp :
1. VÏ s¬ ®å khèi minh ho¹ thuËt to¸n vÏ ®o¹n th¼ng cña Bresenham
2. Hoµn thiÖn ch−¬ng tr×nh vÏ ®o¹n th¼ng theo thuËt to¸n cña Bresenham trong
tÊt c¶ c¸c tr−êng hîp tr−êng hîp
II. VÏ ®−êng trßn :
§Ó vÏ ®−êng trßn chóng ta còng ph¶i tiÕn hµnh chän nh÷ng ®iÓm cã to¹ ®é
nguyªn ®Ó vÏ mµ ®iÓm ®ã n»m gÇn ®−êng trßn thùc nhÊt
Gi¶ sö ®−êng trßn cÇn ph¶i vÏ cã ph−¬ng tr×nh lµ x2+y2=R2, ë ®©y ®Ó ®¬n gi¶n ta
xÐt t©m cña ®−êng trßn lµ t¹i gèc to¹ ®é sau ®ã ®Ó vÏ ®−êng trßn ta chi cÇn tÞnh
tiÕn theo vector (x0,y0) lµ t©m
Cã thÓ tham sè ho¸ ch−¬ng tr×nh trªn thµnh x=R*cos(T); y=R*sin(T)
víi 0<=T<=2*pi
Nh− vËy ta cã thÓ vÏ ®−êng trßn b»ng c¸ch cho gãc T ch¹y tõ 0 cho ®Õn 2*pi víi
b−íc t¨ng lµ 1/R ®Ó lÊy x:=Round(R*cos(T)) y:=Round(R*sin(T)) vµ vÏ ®iÓm
(x,y) nh−ng lµm nh− vËy l¹i ph¶i tÝnh sin vµ cos vµ do ®ã ch−¬ng tr×nh sÏ kh«ng
ch¹y nhanh nªn ta sÏ c¶i tiÕn b»ng c¸c ph−¬ng ph¸p sau :
1. VÏ ®−êng trßn b»ng ph−¬ng ph¸p xÊp xØ :
nh− ta biÕt x=R*cos(T); y=R*sin(T), lÊy ®¹o hµm theo T ta cã :
x'=-R*sin(T)=-y; y'=R*cos(T)=x (1)
cho T ch¹y tõ 0 ®Õn 2*pi víi b−íc lµ h=1/R th× ®iÓm thø i sÏ cã to¹ ®é lµ
x[ih]=R*cos(ih); y[ih]=R*sin(ih)
Theo 1 ta cã :
-y[ih]=x'[ih] b»ng ®¹o hµm tr¸i t¹i ®iÓm T=ih xÊp xØ (x[(i+1)h]-x[ih])/h (h cµng nhá
th× ®é chÝnh x¸c cµng lín), nªn -h.y[ih]=x[(i+1)h]-x[ih] =>
x[(i+1)h]=x[ih]-h.y[ih] (2)
Vµ x[(i+1)h]=y'[(i+1)h] b»ng ®¹o hµm ph¶i t¹i ®iÓm T=(i+1)h xÊp xØ (y[ih]-
y[(i+1)h])/-h (h cµng nhá th× ®é chÝnh x¸c cµng lín), nªn
-h.x[(i+1)h]=y[ih]-y[(i+1)h] => y[(i+1)h]=h.x[(i+1)h]+y[ih] (3)
Tõ (2) vµ (3) ta cã
x[(i+1)h]=x[ih]-h.y[ih]
y[(i+1)h]=h.x[(i+1)h]+y[ih]
Víi gi¸ trÞ ban ®Çu khi T=0 lµ x0=R.cos(0)=R, y0:=R.sin(0)=0;
Ta cã thÓ viÕt gän l¹i víi b−íc h=1/R :
Kü thuËt §å ho¹ m¸y tÝnh
32
x[i+1]=x[i]-hy.[i]
y[i+1]=h.x[i+1]+y[i]
Víi gi¸ trÞ ban ®Çu lµ x0=R, y0=0
Vµ thñ tôc ®Ó vÏ ®−êng trßn theo ph−¬ng ph¸p nµy lµ :
Procedure Circle_(x1,y1,r : Integer);
Var
mau : Byte;
d: LongInt;
x,y,h: Real;
Begin
mau:=GetColor;
h:=1/r; d:=0;
x:=r; y:=0;
Repeat
Putpixel(x1+Round(x),y1+Round(y),mau);
x:=x-h*y;
y:=h*x+y;
Inc(d);
Until d*h>2*pi;
End;
2. ThuËt to¸n vÏ ®−êng trßn cña Bresenham
ThuËt to¸n trªn vÏ ®−êng trßn vÉn cßn chËm v× ph¶i tÝnh to¸n liªn quan víi c¸c sè
thùc. T−¬ng tù nh− víi ®−êng th¼ng, thuËt to¸n vÏ ®−êng trßn cña Bresanham chØ
thùc hiÖn trªn c¸c sè nguyªn nªn ch¹y nhanh h¬n rÊt nhiÒu :