thuật toán vẽ đường thẳng
Xét đoạn thẳng có hệ số góc 0<m<=1 và deltax>0. Với các đoạn thẳng dạng này, nếu (x i , y i ) là điểm đã được xác định ở bước thứ i thì điểm kế tiếp (x i+1 , y i+1 ) ở bước thứ i+1 sẽ là một trong hai điểm sau (xem hình vẽ 1.4) : ...
Xét đoạn thẳng có hệ số góc 0<m<=1 và deltax>0. Với các đoạn thẳng dạng này, nếu (xi, yi) là điểm đã được xác định ở bước thứ i thì điểm kế tiếp (xi+1, yi+1) ở bước thứ i+1 sẽ là một trong hai điểm sau (xem hình vẽ 1.4) :
Hình 1.4 : Các điểm vẽ gần với điểm muốn vẽ.
Vấn đề đặt ra là chọn điểm vẽ như thế nào để đường thẳng được vẽ gần với đường thẳng muốn vẽ nhất và đạt được tối ưu hóa về mặt tốc độ ?
Thuật toán DDA (Digital DifferentialAnalyzer)
Là thuật toán tính toán các điểm vẽ dọc theo đường thẳng dựa vào hệ số góc của phương trình đường thẳng y=mx+b.
Trong đó
Nhận thấy trong hình vẽ 1.4 thì tọa độ của điểm x sẽ tăng 1 đơn vị trên mỗi điểm vẽ, còn việc quyết định chọn yi +1 là yi +1 hay yi sẽ phụ thuộc vào giá trị sau khi làm tròn của tung độ y. Tuy nhiên, nếu tính trực tiếp giá trị thực của y ở mỗi bước từ phương trình y=mx+b thì cần một phép toán nhân và một phép toán cộng số thực.
yi +1 = mxi +1 + b = m(xi + 1) + b = mxi + b + m
Để cải thiện tốc độ, người ta khử phép nhân trên số thực.
Ta có : yi = mxi + b
⇒ yi +1 = yi + m → int(yi +1)
Tóm lại khi 0<m<=1 :
xi +1 = xi + 1
yi +1 = yi + m → int(yi +1)
Trường hợp m>1: chọn bước tăng trên trục y một đơn vị.
xi +1 = xi + 1/m → int(xi +1)
yi +1 = yi + 1
Hai trường hợp này dùng để vẽ một điểm bắt đầu từ bên trái đến điểm cuối cùng bên phải của đường thẳng (xem hình 1.5). Nếu điểm bắt đầu từ bên phải đến điểm cuối cùng bên trái thì xét ngược lại :
0<m<=1: xi +1 := xi - 1
yi +1:= yi - m -> int(yi+1)
m>1: xi +1:= xi – 1/m -> int(xi+1)
yi +1:= yi – 1
Hình 1.5 : Hai dạng đường thẳng có 0<m<1 và m>1.
Tương tự, có thể tính toán các điểm vẽ cho trường hợp m<0: khi |m|<=1 hoặc |m|>1 (sinh viên tự tìm hiểu thêm).
Lưu đồ thuật toán DDA
Cài đặt minh họa thuật toán DDA
Procedure DDA ( x1, y1, x2, y2, color : integer );
Var dx, dy, step : integer;
X_inc, y_inc , x, y : real ;
Begin
dx:=x2-x1;
dy:=y2-y1;
if abs(dx)>abs(dy) then steps:=abs(dx)
else steps:=abs(dy);
x_inc:=dx/steps;
y_inc:=dy/steps;
x:=x1; y:=y1;
putpixel(round(x),round(y), color);
for k:=1 to steps do
begin
x:=x+x_inc;
y:=y+y_inc;
putpixel(round(x),round(y), color);
end;
end;
Thuật toán Bresenham
Hình 1.6 : Dạng đường thẳng có 0<=m<=1.
Gọi (xi +1,yi +1) là điểm thuộc đoạn thẳng (xem hình 1.6). Ta có y:= m(xi +1)+b.
Đặt d1 = yi +1 - yi
d2 = (yi +1) - yi +1
Việc chọn điểm (xi +1, yi +1) là P1 hay P2 phụ thuộc vào việc so sánh d1 và d2 hay dấu của d1-d2.
- Nếu d1-d2<0 : chọn điểm P1, tức là yi +1= yi
- Nếu d1-d2 ≥0 : chọn điểm P2, tức là yi +1= yi +1
Xét Pi = deltax (d1 - d2)
Ta có : d1 - d2 = 2 yi+1 - 2yi - 1
= 2m(xi+1) + 2b - 2yi - 1
⇒ Pi = deltax (d1 - d2) = deltax[2m(xi+1) + 2b - 2yi - 1]
= 2deltay(xi+1) - 2deltax.yi + deltax(2b - 1)
= 2deltay.xi - 2deltax.yi + 2deltay + deltax(2b - 1)
Vậy C = 2deltay + deltax(2b - 1) = Const
⇒ Pi = 2deltay.xi - 2deltax.yi + C
Nhận xét rằng nếu tại bước thứ i ta xác định được dấu của Pi thì xem như ta xác định được điểm cần chọn ở bước (i+1). Ta có :
Pi +1 - Pi = (2deltay.xi+1 - 2deltax.yi+1 + C) - (2deltay.xi - 2deltax.yi + C )
⇔ Pi +1 = Pi + 2deltay - 2deltax ( yi+1 - .yi )
- Nếu Pi < 0 : chọn điểm P1, tức là yi +1= yi và Pi +1 = Pi + 2deltay.
- Nếu Pi ≥ 0 : chọn điểm P2, tức là yi +1= yi +1 và Pi +1 = Pi + 2deltay - 2deltax
- Giá trị P0 được tính từ điểm vẽ đầu tiên (x0 ,y0 ) theo công thức :
P0 = 2deltay.x0 - 2deltax.y0 + C
Do (x0 ,y0 ) là điểm nguyên thuộc về đoạn thẳng nên ta có :
Thế vào phương trình trên ta được :
P0 = 2deltay - deltax
Lưu đồ thuật toán Bresenham
Cài đặt minh họa thuật toán Bresenham
Procedure Bres_Line (x1,y1,x2,y2 : integer);
Var dx, dy, x, y, P, const1, const2 : integer;
Begin
dx : = x2 - x1; dy : = y2 - y1;
P : = 2*dy - dx;
Const1 : = 2*dy ; const2 : = 2*(dy - dx) ;
x:= x1; y:=y1;
Putpixel ( x, y, Color);
while (x < x-2 ) do
begin
x : = x +1 ;
if (P < 0) then P : = P + const1
else
begin
y : = y+1 ;
P : = P + const2
end ;
putpixel (x, y, color) ;
end ;
End ;
Nhận xét :
Thuật toán Bresenham chỉ thao tác trên số nguyên và chỉ tính toán trên phép cộng và phép nhân 2 (phép dịch bit). Điều này là một cải tiến làm tăng tốc độ đáng kể so với thuật toán DDA.
Ý tưởng chính của thuật toán này là ở chổ xét dấu Pi để quyết định điểm kế tiếp, và sử dụng công thức truy hồi Pi +1 - Pi để tính Pi bằng các phép toán đơn giản trên số nguyên.
Tuy nhiên, việc xây dựng trường hợp tổng quát cho thuật toán Bresenham có phức tạp hơn thuật toán DDA.
