Ch ả
ươ i thu t
ng 10: ậ nâng cao
Các gi
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((cid:0) ) – GetPixel((cid:0) )
ế ị ể
ị
Frame buffer và thi
t b hi n th
ª Mô hình ch c năng c a frame buffer
ủ ứ
B C
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
MaxRow
MaxColumn = 639; {= C 1} = 479; {= R 1} MaxRow = 255; {= soá caùc maøu 1} MaxColor
= 0..MaxColumn;
2 1 0
0
1 2
MaxColumn
{moät ví duï}
type col row = 0..MaxRow; color = 0..MaxColor;
{read frame buffer}
procedure SetPixel(c : col, r : row, value : color); {load frame buffer} function GetPixel(c : col, r : row) : color; 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ầ
ẳ ạ ủ đo n th ng
ơn ộ ố
ậ ặ ạ
ụ ư nhau ộ đ sáng nh ờ ẳ đư ng th ng) ẽ – Đi qua 2 đi m ể đ u mút c a ầ – Đ sáng đ ng ồ ề ộ đ u, tr – Đư ng th ng có ẳ ờ – Gi ả ả i thu t ph i có tính l p l – Không ph thu c vào các ch n ộ ả đ d c khác nhau ph i có ể đ xóa ắ đ u vầ i (dùng ể ọ đi m b t
ả
ậ
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<= col2}
var
dx, dy, y, m: real; x: integer;
begin
dx:= col2col1; dy:= row2 – row1; m:= dy/dx; y:= row1; for x:=col1 to col2 do begin
SetPixel(x, Round(y),color); y:= y + m;
end;
end;
ậ
Thu t toán Bresenham
ậ ả ữ i thu t DD_Line ạ ª Nh ng h n ch c a gi
ậ
ữ ớ đi m ể đ u mút l n ầ
ộ ả đ uề
ậ
ố ỉ
ộ ị ế ủ – Ch m vì s d ng hàm Round ử ụ – Không chính xác khi kho ng cách gi a 2 – Đ sáng không đ ng ồ ª Thu t toán Bresenham – Ch dùng s nguyên – Thu c vào l p gi ả đ nh t a ọ đ c a ộ ủ đi m ể
ệ ể ớ ự hi n hành d a vào t a ậ i thu t incremental (xác ư c)ớ ộ ủ đi m tr ọ đ c a
ể
ễ
ạ
ẳ
Bi u di n đo n th ng trong frame buffer
ố ể xa , ya) và (xb , yb),
ố
ẳ ạ ª Cho đo n th ng n i hai đi m ( ọ ộ ề ễ ườ ọ ộ ẳ ng th ng:
(cid:0) (cid:0)
– các t a đ đ u là s nguyên (t a đ trong frame buffer) ủ ườ ể y = m(x (cid:0) xa) + ya ng minh c a đ ª Bi u di n t y – Đ d c: , v i ớ ộ ố m (cid:0) x (cid:0) y = yb (cid:0) ya (cid:0) x = xb (cid:0) xa ị ể ễ ạ ẳ ố ấ t” nh t
ª Bài toán: Xác đ nh các pixel bi u di n đo n th ng “t ị ª Wlog (without loss of generality), xa < xb và 0 < m < 1
ố ộ – tùy thu c vào cách đ nh nghĩa sai s
a ừ đ n bế
– X tăng t – X tăng nhanh hơn y – M i l n x t ỗ ầ ăng lên 1, y không tăng ho c tặ ăng lên 1
ố
ọ
Sai s khi ch n pixel
ª
ầ Sinh các pixel b ng ph
ª Đ nh nghĩa
(cid:0) 1 1) (cid:0) y*
ị ằ sai số
ươ ng pháp tăng d n e(Ti) = y* (cid:0) yi (cid:0) (cid:0) 1 (cid:0) e(Si) = (yi (cid:0)
ạ ưở ẳ Đo n th ng lý t ng
Si
y* yi (cid:0) 1
Ti
xi xi (cid:0) 1
ấ ỉ ố
ọ
ắ
ạ
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) < 0
(cid:0) 1) (cid:0) 1
Tính e(Ti) (cid:0) e(Si) = 2m(xi (cid:0) xa) + 2(ya (cid:0) yi (cid:0)
ể ỉ ị
(*) ớ ố ừ T trên, đ ch tính v i s nguyên, đ nh nghĩa ei = Dx(cid:0) (e(Ti) e(Si)) = 2(Dy)(xi xa) + 2(Dx)(ya yi 1) Dx
ế N u ế ei < 0 thì ch n ọ yi = yi 1 , n u không thì ch n ọ yi = yi 1 + 1
ắ ủ ể ầ ắ C n ki m tra tính đúng đ n c a quy t c trên!
ọ
ể
ắ
ắ ủ 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 (cid:0) 1
Ti
xi xi (cid:0) 1
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
đi qua phía d ẳ đo n th ng lý t ng đi qua phía trên Si và Ti ưở i ướ Si và Ti
Si Si Ti yi (cid:0) 1 yi (cid:0) 1
Ti xi xi xi (cid:0) 1 xi (cid:0) 1
e(Ti) >= 0 e(Si) <= 0 i: e(Ti) <= 0 e(Si) >= 0
ắ ạ e(Ti) = y* yi 1 Nh c l e(Si) = (yi 1 + 1) y*
ố ộ
ữ
ệ
Tính sai s m t cách h u hi u
ª T ừ
(cid:0) 1) (cid:0) (cid:0) x
suy ra
ừ T trên, ei = 2((cid:0) y)(xi (cid:0) xa) + 2((cid:0) x)(ya (cid:0) yi (cid:0) ei + 1 = 2(Dy)(xi + 1 xa) + 2(Dx)(ya yi ) Dx ei + 1 = ei + 2(Dy)(xi + 1 xi) 2(Dx)(yi yi 1 )
ei + 1 = ei + 2Dy ế – n u không thì ch n
ọ ắ Theo quy t c ch n pixel, – n u ế ei < 0 thì ch n ọ yi = yi 1
ei + 1 = ei + 2Dy 2Dx
ọ yi = yi 1 + 1
ả
ậ ủ
Gi
i thu t c a Bresenham
ẳ ª Bi u di n đo n th ng trong frame buffer
ư ế ễ i thu t b t đ u nh th nào? ể – Gi
ừ ạ ậ ắ ầ ả ª 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
{thay ñoåi cuûa sai soá khi y taêng} {thay ñoåi cuûa sai soá khi y khoâng taêng}
x : col; y : row; dx, dy, e_inc, e_noinc, e : integer; {sai soá hieän thôøi}
ả
ậ ủ
ế
Gi
i thu t c a Bresenham (ti p)
begin
{2dxdy}
y := ya; dx := xb xa; dy := yb ya; e_noinc := dy + dy; {2dy} e := e_noinc dx; {e1=2dydx} e_inc := e dx; for x := xa to xb do {voøng laëp chính} begin
SetPixel(x, y, col_val); if e < 0 then e := e + e_noinc; else begin
y := y + 1; e := e + e_inc
end;
end;
end; {Bresenham}
ườ
Các tr
ợ ng h p khác
ả s ế i quy t các ả ử xa > xb và 0 < m < 1. Gi
ª
ả ườ ạ
ầ đ u mút)
ậ i thu t Bresenham gi Gi ợ i: ng h p còn l tr ổ ị xa > xb (đ i v trí hai ủ ổ
ộ ố ằ
m < 0 (thay dy b ng –dy) ằ ủ ổ đ i vai trò c a x và y)
ª m > 1 (đ i vai trò c a x và y) ª Đ d c âm: 1 < ª m < 1 (thay dx b ng –dx, ạ ª Đo n th ng đ ng và đo n th ng n m ngang
ứ ằ ẳ ẳ ạ
ể
ễ
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
ả
(cid:0) ộ ế i quy t ố ứ ỉ ầ ẽ ả – Do đ i x ng, ch c n kh o sát cách v khi 0 x sao cho y(x) (cid:0) x
AB. ứ t c là cung
ằ ươ – 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 ng ng v i m t cung là 1/8 vòng
ố ứ ộ ươ ứ ớ – Ch c n xác đ nh các pixel t
ỉ ầ ở ị ọ đây ch n cung tròn, AB. y
((cid:0) x, y) (x, y)
A
B
(y, x) ((cid:0) y, x)
x
((cid:0) y, (cid:0) x) (y, (cid:0) x)
((cid:0) x, (cid:0) y) (x, (cid:0) 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
Pi (cid:0) 1
Si
ị
ª Đ nh nghĩa
Si = (xi 1 + 1, yi 1) Ti = (xi 1 + 1, yi 1 1) ị yi (cid:0) 1
Ti
sai số e(P) = (x2 + y2) R2
ª Đ nh nghĩa
ị ế ị hàm s quy t đ nh
ố di = e(Si) + e(Ti)
xi xi (cid:0) 1
ỉ ố
ắ
ấ
ọ
Qui t c ch n pixel x p x t
t cung vòng tròn
Pi (cid:0) 1
Si
ế N u ế di < 0 thì ch n ọ Si còn n u không thì ch n ọ Ti
Ti
yi (cid:0) 1
xi xi (cid:0) 1
ắ ủ ể ầ ắ C n ki m tra tính đúng đ n c a quy t c trên!
ể
ắ
ọ
ắ ủ Ki m tra tính đúng đ n c a quy t c ch n pixel
ª Nh c l
ª Tr
Si
Si
Si
Ti
Ti
Ti
ắ ạ di = e(Si) + e(Ti) ườ ờ ng h p: ơn) i: ợ di < 0 (Si g n ầ đư ng tròn h
e(Si) > 0 e(Ti) < 0 e(Si) < 0 e(Ti) < 0
e(Si) > 0 e(Ti) > 0 Không th !ể OK!
(cid:0) ơ ng tròn h n OK, vì di < 0 ầ ườ Si g n đ
ắ ủ
ể
ế
ắ
ọ
Ki m tra tính đúng đ n c a quy t c ch n pixel (ti p)
ª Nh c l
ª Tr
Si
Si
Si
Ti
Ti
Ti
ắ ạ di = e(Si) + e(Ti) ườ ờ ng h p: ơn) i: ợ di (cid:0) 0 (Ti g n ầ đư ng tròn h
e(Si) > 0 e(Ti) > 0
e(Si) < 0 e(Ti) < 0 Không th !ể OK!
(cid:0) e(Si) > 0 e(Ti) < 0 0 ầ ườ ơ ng tròn h n OK, vì di (cid:0) Ti g n đ
ế ị
ữ
ệ
ố
ộ
Tính hàm s quy t đ nh m t cách h u hi u
ắ ạ e(P) = (x2 + y2) R2
ª Nh c l i: ể ứ ª Có th ch ng minh đ
ượ
2) 2(yi yi 1)
ậ c (bài t p): 2 yi 1
di + 1 = di + 4 xi 1 + 6 ế
di + 1 = di + 4 xi 1 + 6 + 2(yi ọ ắ Theo quy t c ch n pixel – n u ế di < 0 thì ta có yi = yi 1 , do đó ch n ọ Ti
di + 1 = di + 4(xi 1 yi 1) + 10
– n u không thì yi = yi 1 1, do đó ch n ọ Si
ª Gi
ư ế i thu t b t đ u nh th nào?
ả ậ ắ ầ x0 = 0, y0 = R do đó S1 = (1, R) và T1 = (1, R 1), v yậ d1=e(S1) + e(T1) =(12+R2R2)+(12+(R1)2R2)=3 2R
ả
ậ ủ
Gi
i thu t c a Michener
ª Bi u di n vòng tròn trong frame buffer
ễ ể
procedure MichCirc(xc : col; yc : row; Rad : integer; value : color); {Veõ voøng troøn coù taâm (xc, yc), baùn kính Rad, vaø maøu value} var
x : col; y : row; d : integer;
begin
x := 0; y := Rad; d := 3 2*Rad;
ả
ậ ủ
ế
Gi
i thu t c a Michener (ti p)
while x <= y do begin
{update error term}
SetPixel(xc + x, yc + y, value); {draw 8 points } SetPixel(xc x, yc + y, value); {based on (x, y)} SetPixel(xc + x, yc y, value); SetPixel(xc x, yc y, value); SetPixel(xc + y, yc + x, value); SetPixel(xc y, yc + x, value); SetPixel(xc + y, yc x, value); SetPixel(xc y, yc x, value); if d < 0 then d := d + 4*x + 6 else begin
d := d + 4*(x y) + 10; y := y 1
end; x := x + 1
end
end; {MichCirc}
ị
Đ nh nghĩa vùng
ằ ằ
ị ị
ª Đ nh nghĩa vùng b ng pixel ª Đ nh nghĩa vùng b ng
đa giác
ằ
ị
Đ nh nghĩa vùng b ng pixel
ự
ị
ế ố
ể ả
ế ố ế
ề
ằ
ề
ể ả
ế ố ế
– 8connected: 2 đi m nh đ
c xem là k t n i n u ọ chúng n m k nhau theo chi u ngang hay chi u d c c xem là k t n i n u
ủ ª D a trên màu c a các pixel ª Hai cách đ nh nghĩa tính k t n i: – 4connected: 2 đi m nh đ ượ ề ượ ề
ề
ề
ọ
chúng n m k nhau theo chi u ngang, chi u d c hay ườ đ
ở
ằ ng chéo ị ª Hai cách xác đ nh vùng b i:
ể ả
– T t c các đi m nh trong vùng có cùng 1 màu, có
ỗ ố ượ
ể ả
ở
ị
ỗ ố
ể
ấ ả ể th có l – Vùng đ ủ ườ c a đ có màu bao, có th có l
tr ng (hole) bên trong. c xác đ nh b i các đi m nh có cùng màu ể ả ng bao quanh, các đi m nh bên trong không tr ng bên trong
Ví dụ
ả
ệ
ậ
Gi
i thu t tô màu tràn đ qui
ề
ắ ầ
ể
ằ
ố
ồ ọ ầ ª Dùng trong các ph n m m đ h a ở ª Vùng xác đ nh b i 1 màu và 4connected ạ ở ª B t đ u b ng b i 1 đi m h t gi ng (seed) n m bên trong
ắ ầ ừ ể
ổ ừ
}
màu int_color sang new_color
đi m (x,y), đ i t
ị ằ vùng c n tôầ procedure FloodFill(x : col; y : row; int_color, new_color : color); {b t đ u t begin
if GetPixel(x, y) = int_color then begin
SetPixel(x, y, new_color); FloodFill(x – 1, y, int_color, new_color); FloodFill(x + 1, y, int_color, new_color); FloodFill(x, y + 1, int_color, new_color); FloodFill(x, y – 1, int_color, new_color);
end end;
ả
ệ
ậ
Gi
i thu t tô màu tràn đ qui (
tt.)
ắ ầ
ở ở
ể
ằ
ố
ª Vùng xác đ nh b i 1 màu và 8connected ạ ª B t đ u b ng b i 1 đi m h t gi ng (seed) n m bên trong
ị ằ vùng c n tôầ
ª Thêm:
. Nh
ề ầ i nhi u l n
FloodFill(x – 1, y – 1, int_color, new_color); FloodFill(x – 1, y + 1, int_color, new_color); FloodFill(x + 1, y + 1, int_color, new_color); FloodFill(x + 1, y – 1, int_color, new_color); ể ượ c đi m: ị ặ ạ b l p l ễ ị d b tràn stack
ả
ệ
ậ
Gi
i thu t tô màu tràn đ qui (
tt.)
ắ ầ
ể
ằ
ố
ở ở
ª Vùng xác đ nh b i màu bao và 4connected ạ ª B t đ u b ng b i 1 đi m h t gi ng (seed) n m bên trong
ị ằ vùng c n tôầ
ắ ầ ừ ể
ổ ừ
}
màu int_color sang new_color
đi m (x,y), đ i t
procedure FloodFill(x : col; y : row; int_color, new_color : color); {b t đ u t begin
if (GetPixel(x, y) >< bound_color) and (GetPixel(x, y) >< new_color) then begin
SetPixel(x, y, new_color); FloodFill(x – 1, y, int_color, new_color); FloodFill(x + 1, y, int_color, new_color); FloodFill(x, y + 1, int_color, new_color); FloodFill(x, y – 1, int_color, new_color);
end end;
Run of Pixels
ả ả
ª Gi ª Gi
ế thi t các pixel là 4connected ậ i thu t
Push address of seed pixel on the stack; while stack not empty do
Pop the stack to provide the next seed; Fill in the run defined by the seed; Examine the row above for runs reachable from this run; Push the address of the rightmost pixels of each such run; Do the same for the row below the current run; end;
Ví dụ
Ví dụ
D
C
Ví dụ
J I
G F C
Tô màu vùng đa giác
ừ ộ ệ
ớ ấ ả ạ t c các c nh c a đa giác
ế ắ ầ ị
ª Xét t ng dòng ngang trên b đ m màn hình: – Tìm các giao đi m c a dòng v i t ủ ể ủ – S p x p các giao đi m theo chi u tăng d n giá tr x ề ể – Tô các đi m nh n m gi a các c p giao đi m ữ ằ
ể ả ể ặ
Tô màu vùng đa giác
ạ ầ ả ử
ự ả không còn đúng khi ị đi m mút không ph i là c c tr
ươ
ị ộ ạ ủ ế ể ầ ố i quy t: d ch đi m đ u mút c a m t c nh xu ng 1
ằ ª C nh n m ngang không c n ph i x lý ở ể ẵ ẻ ª Tính ch n l ị ng. đ a ph – Cách gi ả pixel
Tô màu vùng đa giác
ª Active Edge List (AEL) l
ợ ụ ậ ủ ạ
i d ng tính lân c n c a c nh ẽ ắ ở ữ ắ ở
ª
ể ự ố ạ ủ ướ ể ị c
– nh ng c nh c t b i scanline y s c t b i scanline y+1 – giá tr x c a giao đi m cĩ th d đ n tr type
edge_ptr = ^edge_info edge_info = record
y_upper : row; x_int : real; recip_slope : real; next : egde_ptr;
end;
Tô màu vùng đa giác
ª update AEL cho scanline y+1 ấ ả ữ
ạ ằ
ộ
ạ ể
ả ắ
ể ị
ộ
– xĩa t t c nh ng c nh cĩ y_upper < new_y – thay đ i x_value b ng cách c ng thêm recip_slope ổ – cĩ th thêm vào c nh m i cĩ y_lower = new_y ớ ể – th t ứ ự ủ c a giao đi m cĩ th b xáo tr n, nên ph i s p ế ạ i x p l
Tô màu vùng đa giác
ả
ạ
ª Xây d ng b ng c nh: edge_table:
