Thứ Ba, 24 tháng 5, 2011

Giải·thuật Bresenham vẽ đoạn·thẳng



Người·dịch: Nguyễn·Tiến·Hải

Cập·nhật: ngày 30 tháng 05 năm 2011.

Bài dịch từ http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Giải·thuật vẽ đoạn·thẳng của Bresenham (tiếng Anh: Bresenham's line algorithm) là giải·thuật xác·định các điểm raster hai chiều cần phải vẽ (chấm điểm), để nhận được xấp·xỉ của  đoạn·thẳng có hai điểm đầu·mút cho trước. Đây là một trong những giải·thuật được phát·triển sớm nhất trong lĩnh·vực đồ·họa máy·tính. Giải·thuật này đã được Jack E. Bresenham thiết·kế vào năm 1962 tại công·ti IBM. Giải·thuật Bresenham thường được dùng để vẽ các đoạn·thẳng trên màn·hình máy·vi·tính, vì nó chỉ sử·dụng các lệnh cộng trừ số·học và các lệnh trên pixel, ngoài ra nó có chi·phí rẻ và thích·hợp với kiến·trúc sơ·khai của máy·tính. Người·ta đã mở·rộng giải·thuật này thành giải·thuật vẽ các đường·cong bậc 2.

Mặc·dù các giải·thuật khác, ví·dụ như giải thuật Xiaolin_Wu cũng thường được sử·dụng trong đồ·họa máy·tính hiện·đại vì chúng có tính·năng khử răng·cưa (tiếng Anh: antialiasing), nhưng tốc·độ và sự·đơn·giản của giải·thuật Bresenham khiến nó vẫn giữ vai·trò quan·trọng. Giải·thuật được tích·hợp trên phần·cứng như plotter hay chip đồ·họa của những card đồ·họa hiện·đại. Cũng có·thể tìm·thấy nó trong nhiều phần·mềm thư·viện đồ·họa. Bởi·vì giải·thuật Bresenham cực·kì đơn·giản, nên nó thường được thực·hiện cả trong firmware và cả trong phần·cứng của những card đồ·họa hiện·đại.

Ngày·nay, cái·tên "Bresenham" được gán cho cả họ giải·thuật biến·đổi hoặc mở·rộng giải·thuật Bresenham nguyên·thủy. Xin hãy xem thêm phần tham·khảo phía  dưới.
  
1 Giải·thuật Bresenham 
Minh·họa kết·quả thực·hiện của giải·thuật Bresenham trong đó (0,0) là điểm trên cùng bên trái.

Cần vẽ đoạn·thẳng nối hai điểm (x0, y0) và (x1, y1), trong đó x0, x1 là các tọa·độ cột, còn y0,y1 là các tọa·độ hàng, xi và yi có chỉ·số i tăng dần từ trái sang phải và từ trên xuống dưới tương·ứng.

Trước hết, ta chỉ trình·bày giải·thuật cho trường·hợp góc·phần·tám, trong đó đoạn·thẳng cần vẽ hướng xuống và sang phải (x0≤x1 và y0≤y1), và hình·chiếu ngang của nó x1 − x0 dài hơn hình·chiếu đứng y1 − y0 (đường·thẳng có hệ·số góc nhỏ hơn 1 và lớn hơn 0), hay góc nghiêng của đường·thẳng so với phương ngang nhỏ hơn 45 độ. Trong góc·phần·tám này, với mỗi cột x nằm giữa x0 và x1, có đúng một hàng y (y được tính bởi giải·thuật) chứa một pixel của đường·thẳng, trong khi đó mỗi hàng nằm giữa y0 và y1 có thể chứa nhiều pixel đã được raster·hóa.

Phương·trình tổng·quát của đường·thẳng đi qua hai điểm:


Vì chúng·ta đã biết cột bằng x, nên hàng của pixel, tức y, được tính bằng·cách làm·tròn giá·trị sau đây đến số nguyên gần nhất:


Tuy·nhiên, tính giá·trị chính·xác của biểu·thức này là không cần·thiết, cần chú·ý rằng y tăng từ y0 và sau mỗi bước chúng·ta thêm vào x một đơn·vị và thêm vào y giá·trị của hệ·số góc s = (y1 − y0) / (x1 − x0). Hệ·số góc s chỉ phụ·thuộc vào các tọa·độ điểm mút nên có·thể tính trước được s. Hơn·nữa, ở mỗi bước chúng·ta phải chọn làm một trong hai việc: hoặc là giữ·nguyên y, hoặc là tăng y lên 1 đơn vị.

Có·thể giải·quyết việc·lựa·chọn này bằng·cách lần·theo giá·trị sai·số. Giá·trị sai·số là khoảng·cách giữa giá·trị y hiện·tại và giá·trị y chính·xác đối·với x hiện·tại. Mỗi lần khi chúng·ta tăng x, chúng·ta sẽ tăng thêm vào giá·trị sai·số một đại·lượng s, s là hệ·số góc nói ở trên. Nếu sai·số vượt quá 0.5, phép·raster·hóa sẽ tăng y thêm 1 (điểm tiếp theo của đoạn·thẳng cần vẽ nằm trên hàng raster kế bên dưới) và sai·số giảm·đi 1.0.

Trong mẫu mã giả dưới đây,  plot(x,y) vẽ một điểm và abs trả về giá·trị tuyệt·đối:


 function line(x0, x1, y0, y1)
     int deltax := x1 · x0
     int deltay := y1 · y0
     real error := 0
     real deltaerr := abs (deltay / deltax)    // Giả định deltax != 0
         //(tức đường·thẳng không có phương thẳng·đứng),
         //Chú·ý: phép·chia này cần được thực·hiện sao·cho
         //nó có·thể giữ lại phần thập·phân    

int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if error ≥ 0.5 then
             y := y + 1
             error := error · 1.0

2 Tổng·quát·hóa

Phiên·bản giải·thuật nêu trên chỉ kiểm·soát được việc·vẽ đoạn·thẳng hướng từ trên xuống dưới về phía phải. Tất·nhiên mong·muốn của chúng·ta là có·thể vẽ được mọi đoạn·thẳng. Trường·hợp đầu·tiên cho·phép chúng·ta vẽ các đường dốc xuống dưới nhưng có đầu nằm ở hướng đối diện. Việc này rất đơn giản nhờ việc tráo các điểm khởi tạo nếu x0 > x1. Việc khó hơn là cần xác·định làm cách nào để có·thể vẽ các đường đi lên. Để làm việc này, chúng·ta sẽ kiểm·tra xem y0 ≥ y1 có đúng không; nếu đúng vậy, chúng·ta sẽ thay·đổi bước y bởi ·1 thay vì 1. Sau·cùng, chúng·ta vẫn cần phải tổng·quát·hóa giải·thuật để có·thể vẽ các đường trong mọi hướng. Cho đến lúc này, chúng·ta chỉ có·thể vẽ các đường có hệ·số góc nhỏ hơn 1. Để có thể vẽ các đường có hệ·số góc lớn hơn (đường dốc hơn), chúng·ta tận·dụng thực·tế là một đường dốc có·thể được phản·xạ qua đường·thẳng y=x để nhận·được một đường có hệ·số góc (độ dốc) nhỏ. Hiệu·ứng này là tráo·đổi các biến x và y khắp nơi, bao·gồm luôn việc·tráo·đổi các tham·số để plot (vẽ, chấm điểm). Mã chương·trình có·thể giống như sau:


 function line(x0, x1, y0, y1)
     boolean steep := abs(y1 · y0) > abs(x1 · x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 · x0
     int deltay := abs(y1 · y0)
     real error := 0
     real deltaerr := deltay / deltax
     int ystep
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := ·1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error + deltaerr
         if error ≥ 0.5 then
             y := y + ystep
             error := error · 1.0

Bây·giờ thì hàm đã có·thể kiểm·soát được việc·vẽ tất·cả các đường và thực·hiện giải·thuật Bresenham một·cách trọn·vẹn.

3 Tối·ưu·hóa

Phương·pháp này có vấn·đề ở chỗ các máy·tính hoạt·động tương·đối chậm trên các số thập·phân như error và deltaerr; hơn·nữa, các sai·số có·thể được tích·lũy qua nhiều phép·cộng số thực (floating·point addition). Làm việc với số nguyên vừa nhanh hơn vừa chính·xác hơn. Thủ·thuật chúng·ta sử·dụng ở đây là nhân tất·cả các số thập·phân ở trên (kể·cả hằng·số 0.5) với deltax, việc này cho·phép chúng·ta biểu·diễn chúng như các số nguyên. Vấn·đề duy·nhất còn lại đó là hằng·số 0.5— để giải·quyết việc này, chúng·ta thay·đổi việc·khởi·tạo biến error, và ta sẽ bắt·đầu giảm dần từ 0.5 tới 0 thay vì tăng dần từ 0 tới 0.5. Chương·trình mới sẽ như sau:


 function line(x0, x1, y0, y1)
     boolean steep := abs(y1 · y0) > abs(x1 · x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 · x0
     int deltay := abs(y1 · y0)
     int error := deltax / 2
     int ystep
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := ·1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error · deltay
         if error < 0 then
             y := y + ystep
             error := error + deltax

Chú·ý: Nếu bạn cần kiểm·soát các điểm theo thứ·tự xuất·hiện của chúng (ví·dụ để in nhiều đường gạch·gạch (dashed line) liên·tiếp) bạn sẽ phải đơn·giản·hóa mã này bằng·cách bỏ·qua phép·tráo (swap) thứ hai:


function line(x0, x1, y0, y1)
     boolean steep := abs(y1 · y0) > abs(x1 · x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     int deltax := abs(x1 · x0)
     int deltay := abs(y1 · y0)
     int error := deltax / 2
     int ystep
     int y := y0

     int inc REM added
     if x0 < x1 then inc := 1 else inc := ·1 REM added

     if y0 < y1 then ystep := 1 else ystep := ·1
     for x from x0 to x1 with increment inc REM changed
         if steep then plot(y,x) else plot(x,y)
         REM ở đây, ta thực·hiện cộng·thêm vào một biến
            nhằm để kiểm·soát tiến·trình vẽ đường
         error := error · deltay
         if error < 0 then
             y := y + ystep
             error := error + deltax

4 Lịch·sử

Giải·thuật Bresenham do Jack E. Bresenham phát·triển vào năm 1962 tại công·ti  IBM. Vào năm 2001, Bresenham viết:[1]

"
Lúc ấy, tôi đang làm việc trong một phòng lab tính toán tại bộ·phận Lab phát triển San Jose của IBM. Có một máy·vẽ Calcomp plotter được người·ta gắn vào máy·tính IBM 1401 qua console typewriter 1407. Vào mùa·hè năm 1962, cũng có·thể trước hoặc sau đó một tháng thì giải·thuật của tôi được áp·dụng vào sản xuất . Các chương·trình ngày ấy có·thể được trao·đổi tự·do giữa các công·ti nên Calcomp (Jim Newland và Calvin Hefte) đã có các bản copy. Khi tôi trở về Stanford vào mùa·thu năm 1962, tôi đã để lại trong thư·viện trung·tâm Stanford comp một bản copy. Một bản miêu·tả đoạn chương·trình (routine) vẽ đường đã được chấp·thuận trình·bày ở hội·nghị quốc·gia ACM năm 1963 ở Denver, Colorado. Năm đó không có tập công·trình nghiên·cứu nào được công·bố mà chỉ có chương·trình nghị·sự của các diễn·giả và các đề·tài được xuất·bản trong một ấn·phẩm  Truyền·thông ACM (Communications of the ACM). Sau khi tôi trình·bày xong, một người đến từ tạp·chí IBM Systems Journal đã hỏi tôi rằng liệu tôi có·thể cho·phép xuất· bản bài·báo đó được hay không. Tôi đã sung·sướng đồng·ý, và thế là họ đã in nó vào năm 1965. 

"

—Bresenham


Giải·thuật Bresenham sau đó được biến·đổi để tạo ra các đường·tròn, đôi·khi nó còn được biết đến với tên gọi "giải·thuật Bresenham  vẽ đường·tròn" hay giải·thuật điểm giữa đường·tròn (tiếng Anh: midpoint circle algorithm).

5 Các giải·thuật tương·tự

Có·thể hiểu Giải·thuật Bresenham là phép biến·đổi nhỏ của thuật·toán DDA (trong đó sử·dụng ngưỡng sai·số là 0.5 thay·vì 0, số 0 cần·thiết cho phép raster·hóa đa·giác không·chồng·chập).

Nguyên·tắc sử·dụng sai·số tăng thay cho phép·tính chia còn có các ứng·dụng khác trong đồ·họa. Kĩ·thuật này có·thể dùng để tính các tọa·độ U, V trong quá·trình quét raster của kết·cấu đa·giác ánh·xạ (texture mapped polygon). Các lõi phần· mềm dựng hình heightmap voxel tìm·thấy trong các trò·chơi máy·tính cũng đã sử·dụng nguyên·tắc này.

Bresenham cũng đã công·bố giải·thuật tính·toán Run·Slice (trái·ngược với Run·Length).

 Alan Murphy ở công·ti IBM  đã phát·minh ra một giải·thuật là mở·rộng của giải·thuật Bresenham dùng để điều·khiển các đường có bề·dày.

6 Xem thêm
7 Tham·khảo
  1. ^ Paul E. Black. Dictionary of Algorithms and Data Structures,NIST. http://www.nist.gov/dads/HTML/bresenham.html

8 Đọc thêm

9 Liên·kết ngoài
Được đăng bởi vào lúc
Nhãn: , , ,

Không có nhận xét nào:

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)