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à x
2
+y
2
=R
2
, ở đâ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 (x
0
,y
0
) 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) nhng 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à x
0
=R.cos(0)=R, y
0
:=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à x
0
=R, y
0
=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 :


Kỹ thuật Đồ hoạ máy tính

33
Cũng nh trên ta xét tâm ở gốc toạ độ, với chú ý rằng cứ một điểm thuộc đờng tròn
thì bằng cách đối xứng qua các trục toạ độ, qua các đờng chéo ta có thể xác định
đợc 8 điểm thuộc đờng tròn (nh hình vẽ). Do đó ta chỉ cần xét 1/8 cung tròn bắt
đầu từ x=0,y=R và kết thúc khi x=y.
Ta viết lại phơng trình đờng tròn thành y
2
=R
2
-x
2


Giả sử điểm (x[i], y[i]) là điểm thuộc đờng tròn, vị trí của điểm kế tiếp cần vẽ sẽ là
(x[i]+1,y[i]) hoặc (x[i]+1,y[i]-1) và giá trị đúng của y sẽ đợc xét bằng phơng trình
y
2
=R
2
-(x[i+1])
2

Ta xét 2 độ dài : d1=(y[i])
2
-y
2
=(y[i])
2
-R
2

+(x[i]+1)
2

Và d2=y
2
-(y[i]-1)
2
=R
2
-(x[i]+1)
2
-(y[i]-1)
2

Do đó hiệu giữa d1 và d2 là : p[i]=d1-d2=2(x[i]+1)
2
+(y[i])
2
+(y[i]-1)
2
-2R
2

Cũng giống nh đoạn thẳng nếu p[i] âm ta chọn y[i],
ngợc lại chọn y[i]-1
Tăng i lên 1 đơn vị ta có
p[i+1]=d1-d2=2(x[i+1]+1)
2
+(y[i+1])
2

+(y[i+1]-1)
2
-2R
2

Nên p[i+1]=p[i]+4x[i]+6+2((y[i+1])
2
-(y[i])
2
)-2(y[i+1]-y[i])
mà y[i+1] hoặc bằng y[i] hoặc bằng y[i]-1
Nếu y[i+1]=y[i] thì p[i+1]=p[i]+4x[i]+6
Nếu y[i+1]=y[i]-1 thì p[i+1]=p[i]+4(x[i]-y[i])+10
Có thể tóm tắt các bớc nh sau :
1. Đặt x:=0; y:=r; p:=3-2*r;
2. Nếu x>y kết thúc nếu không thực hiện bớc 3
3. Vẽ 8 điểm (x, y); (-x, y); (x, -y); (-x, -y); (y, x); (-y, x); (y, -x); (-y, -x);
4. Nếu p<0 thì p:=p+4*x+6
Ngơc lại p:=p+4*(x-y)+10; và giảm y 1 đơn vị
5. Tăng x lên 1 đơn vị
Kỹ thuật Đồ hoạ máy tính
34
6. Quay lại bớc 2
Và thủ tục để vẽ đờng tròn theo thuật toán Bresenham là :
Procedure Circle_(x1,y1,r : Integer);
Var
mau : Byte;
x,y,p: Integer;
Procedure Put_Pixels(x,y: Integer);
Begin

Putpixel(x1+x,y1+y,mau);
Putpixel(x1-x,y1+y,mau);
Putpixel(x1+x,y1-y,mau);
Putpixel(x1-x,y1-y,mau);
Putpixel(x1+y,y1+x,mau);
Putpixel(x1-y,y1+x,mau);
Putpixel(x1+y,y1-x,mau);
Putpixel(x1-y,y1-x,mau);
End;
Begin
mau:=GetColor;
x:=0; y:=r; p:=3-2*r;
While x<=y Do
Begin
Put_pixels(x,y);
If p<0 Then p:=p+4*x+6
Else
Begin
p:=p+4*(x-y)+10;
Dec(y);
End;
Inc(x);
End;
End;
Bài tập :
1. Lập chơng trình vẽ đờng tròn theo phơng pháp xấp xỉ
2. Lập thiện chơng trình vẽ đờng tròn theo thuật toán của Bresenham
3. Lập chơng trình vẽ đờng tròn theo tham số
4. Lập chơng trình vẽ Elip theo tham số
5. Tơng tự nh vẽ đờng tròn lập chơng trình vẽ Elip theo thuật toán của

Bresenham