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

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:40

Thêm vào BST

Báo xấu

58
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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=2dydx} e_inc := e dx; {2dxdy} for x := xa to xb do {voøng laëp chính} begin SetPixel(x, y, col_val); if e
Các trường hợp khác Giải thuật Bresenham giả sử xa > xb và 0 1 (đổi vai trò của x và y) ª Độ dốc âm: 1
Biểu diễn vòng tròn trong frame buffer ª Bài toán: Xác định các pixel biểu diễn vòng tròn y2 = R2 – x2 “tốt” nhất – tùy thuộc vào cách định nghĩa sai số ª Giải quyết – Do đối xứng, chỉ cần khảo sát cách vẽ khi 0 x sao cho y(x) x tức là cung AB. – Sinh các pixel bằng phương pháp tăng dần (incremental).
Đối xứng trên vòng tròn ª Giảm phí tổn tính toán bằng cách dùng phép đối xứng trên vòng tròn – Chỉ cần xác định các pixel tương ứng với một cung là 1/8 vòng tròn, ở đây chọn cung AB. y ( x, y) (x, y) A B ( y, x) (y, x) x ( y, x) (y, x) ( x, y) (x, y)
Sai số khi chọn pixel ª Giả sử có pixel tốt nhất tại bước thứ i 1 là Pi 1 = (xi 1, yi 1) ª Định nghĩa Si = (xi 1 + 1, yi 1) Ti = (xi 1 + 1, yi 1 1) ª Định nghĩa sai số Pi 1 Si yi 1 e(P) = (x2 + y2) R2 Ti ª Định nghĩa hàm số quyết định di = e(Si) + e(Ti) xi 1 xi
Qui tắc chọn pixel xấp xỉ tốt cung vòng tròn Nếu di