Bài giảng Chương 10: Các giải thuật nâng cao

Bài giảng Chương 10: Các giải thuật nâng cao trình bày về Frame buffer và thiết bị hiển thị; truy cập vào frame buffer; giải thuật DD_Line; thuật toán Bresenham; biểu diễn đoạn thẳng trong frame buffer; quy tắc chọn pixel xấp xỉ tốt đoạn thẳng thực và một số nội dung khác.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương 10: Các giải thuật nâng cao Chương 10:  Các giải thuật nâng cao Scan conversion ª Scan conversion: quá trình biểu diễn một đối tượng hình học (đoạn  thẳng, vòng tròn,...) trong bộ đệm ảnh đơn (frame buffer) của hệ  thống đồ họa quét raster. ª vận hành (drive) the frame buffer thông qua các thủ tục – SetPixel( ) – GetPixel( ) Frame buffer và thiết bị hiển thị ª Mô hình chức năng của frame buffer C B y R làm tươi ảnh x Màn hình • B=1 •(value=0) => (pixel off) black •(value=1) => (pixel on) white Truy cập vào frame buffer  ª Mô hình lập trình – Mô hình cho frame buffer – Các thao tác lên frame buffer. const {moät ví duï} MaxColumn = 639; {= C ­ 1} MaxRow MaxRow = 479; {= R ­ 1} MaxColor = 255; {= soá caùc maøu ­ 1} type 2 col = 0..MaxColumn; 1 row = 0..MaxRow; 0 0 1 2 MaxColumn color = 0..MaxColor; procedure SetPixel(c : col, r : row, value : color); {load frame buffer} function    GetPixel(c : col, r : row) : color;   {read frame buffer} procedure SetPixelWord(c : col, r : row, value : word); function    GetPixel(c : col, r : row) : word;    Thuật toán vẽ đoạn thẳng ª Yêu cầu – Đi qua 2 điểm đầu mút của đoạn thẳng – Độ sáng đồng đều, trơn – Đường thẳng có độ dốc khác nhau phải có độ sáng như nhau – Giải thuật phải có tính lặp lại (dùng để xóa đường thẳng) – Không phụ thuộc vào các chọn điểm bắt đầu vẽ Giải thuật DD_Line ª Procedure DD_Line(row1,col1,row2,col2,color:integer);      {Giaû söû ñoä doác naèm giöõa [­1,1], col1 Thuật toán Bresenham ª Những hạn chế của giải thuật DD_Line – Chậm vì sử dụng hàm Round – Không chính xác khi khoảng cách giữa 2 điểm đầu mút lớn – Độ sáng không đồng đều ª Thuật toán Bresenham – Chỉ dùng số nguyên – Thuộc vào lớp giải thuật incremental (xác định tọa độ của điểm  hiện hành dựa vào tọa độ của điểm trước) Biểu diễn đoạn thẳng trong frame buffer ª Cho đoạn thẳng nối hai điểm (xa , ya) và (xb , yb), – các tọa độ đều là số nguyên (tọa độ trong frame buffer)  ª Biểu diễn tường minh của đường thẳng: y = m(x   xa) + ya y – Độ dốc:                   , v ới m x y = yb   ya x = xb   xa ª Bài toán: Xác định các pixel biểu diễn đoạn thẳng “tốt” nhất – tùy thuộc vào cách định nghĩa sai số ª Wlog (without loss of generality), xa  Sai số khi chọn pixel ª Sinh các pixel bằng phương pháp tăng dần ª Định nghĩa sai số e(Ti) = y*   yi  1 e(Si) = (yi  1   1)   y* Đoạn thẳng lý tưởng Si y* yi   1 Ti xi   1 xi Quy tắc chọn pixel xấp xỉ tốt đoạn thẳng thực ª Quy tắc chọn pixel Chọn Ti nếu và chỉ nếu e(Ti) ­ e(Si)  Kiểm tra tính đúng đắn của quy tắc chọn pixel ª Trường hợp đoạn thẳng lý tưởng đi qua giữa Si và Ti Đoạn thẳng lý tưởng Si y* yi   1 Ti xi   1 xi e(Ti) = y* ­ yi ­ 1 e(Si) = (yi ­ 1 + 1) ­ y* Kiểm tra tính đúng đắn của quy tắc chọn pixel  (tiếp) ª Các trường hợp còn lại đoạn thẳng lý tưởng đoạn thẳng lý tưởng đi qua phía trên Si và Ti đi qua phía dưới Si và Ti Si Si Ti yi   1 yi   1 Ti xi   1 xi xi   1 xi e(Ti) >= 0 e(Ti)  Tính sai số một cách hữu hiệu ª Từ  ei = 2( y)(xi   xa) + 2( x)(ya   yi  1)    x suy ra ei + 1 = 2(Dy)(xi + 1 ­ xa) + 2(Dx)(ya ­ yi ) ­ Dx   Từ trên, ei + 1 = ei + 2(Dy)(xi + 1 ­ xi) ­ 2(Dx)(yi ­ yi ­ 1 )   Theo quy tắc chọn pixel, – nếu ei  Giải thuật của Bresenham ª Biểu diễn đoạn thẳng trong frame buffer – Giải thuật bắt đầu như thế nào? ª x0 = xa, y0 = ya ª Từ (*) có e1 = 2(Dy) ­ Dx (dùng x1 ­ xa = 1) procedure Bresenham(xa, xb : col; ya, yb : row; col_val : color); {veõ ñoaïn thaúng coù maøu laø col_val töø (xa, ya) ñeán (ya, yb)} {wlog, xa < xb vaø 0 < ñoä doác cuûa ñoaïn thaúng < 1} var x : col; y : row; dx, dy, e_inc, {thay ñoåi cuûa sai soá khi y taêng} e_noinc, {thay ñoåi cuûa sai soá khi y khoâng taêng} e : integer; {sai soá hieän thôøi} Giải thuật của Bresenham (tiếp) begin y := ya; dx := xb ­ xa; dy := yb ­ ya; e_noinc := dy + dy; {2dy} e := e_noinc ­ dx;    {e1=2dy­dx} e_inc := e ­ dx; {2dx­dy} for x := xa to xb do {voøng laëp chính} begin SetPixel(x, y, col_val); if e  ...