Trang 1
Đồ HỌA MÁY TÍNH C Ă C r í l ĩ r r ệ í :'ế Ỹ Ũ Ễ'' r ĩ V ( i n r r r r T ĩ g Ĩ.I1 ]j.J j.ệ .p • Giả sử tọa độ các điểm nguyên sau khi xấp xỉ đối tượng thực lần lượt là (Xi,yi),i =0,.... Đây là các điểm nguyên sẽ được hiển thị trê n m àn hình. • Bài toán đặt ra là nếu biết được ix i>yi) là tọa độ nguyên xác định ở bước thứ i, điểm nguyên tiếp theo (^H-iơi+ilsẽ được xác định như th ế nào. • Đối tượng hiển thị trê n lưới nguyên được liền nét, các điểm mà (Xi+1 J i+ i) có thể chọn chỉ là một trong tám điểm được đánh số từ 1 đến 8 trong hình sau (điểm đen chính là (x i*yi )).Hay nói cách khác : ( * i + i » y i + i ) = ( * i ± l , y í ± 1) . • Dáng điệu của đường sẽ cho ta gợi ý khi chọn một trong tám điểm trên. Cách chọn các điểm như th ế nào sẽ tùy thuộc vào từng th u ật toán trên cơ sở xem xét tới vấn đề tối Ưu tốc độ. ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 1/22
Trang 2
Đồ HỌA MÁY TÍNH I í ì r r ậ ĩ : Ĩ n ã ĩ ĩ v ã ( î n f f t î g i f î l r î g • Xét đoạn thẳng có hệ sô" góc 0 < ra < 1 và Dx > 0. • Với các đoạn thẳng dạng này, nếu là điểm đã xác định được ở bước thứ i (điểm màu đen) thì điểm cần chọn fc+iJ^j+i) ở bước thứ (i+1) sẽ là một trong hai trường hợp như hình vẽ sau : '*i+i = x i +1 y i+1 e {y¿>y¡ + !} • Vấn đề còn lại, là cách chọn một trong hai điểm trê n như th ế nào để có thể tối ưu về m ặt tốc độ. ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 2/22
Trang 3
Đồ HỌA MÁY TÍNH T h u ậ t to á n . (JJj.gj.taI JJj.ffereD.tj.aI A j3.sj.yzer) • Việc quyết định chọn 3//+1 là 3^ hay y* + 1 , dựa vào phương trìn h của đoạn thẳng y = + ố . Nghĩa là, ta sẽ tín h tọa độ của điểm (xi +l,;y) thuộc về đoạn thẳng thực. Tiếp đó, yi+1 sẽ là giá trị sau khi làm tròn giá trị tung độ y. y = m(xị + l) + b • Như vậy : y M = Round(y) ( X ị , V ị) • Nếu tín h trực tiếp giá trị thực y ở mỗi bước từ phương trìn h y = mx + bthì phải cần một phép toán nhân và một phép toán cộng sô" thực. Để cải thiện tốc độ, người ta tính giá trị thực của y ở mỗi bước theo cách sau để khử phép tín h nhân trên số thực : • N hận xét rằng : ysau = m xi+1 + b = m(xị + 1) + b ytrưóc = m x i + b => y Sau = y trước + rn ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 3/22
Trang 4
Đồ HỌA MÁY TÍNH Lưu đồ thuật toán DDA Begin ▼ m=Dy/Dx; x=x1 ; y=yi; putpixel(x, Round(y), c); No Yes L x=x+1; y=y+m; putpixel(x, Round(y),c); ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 4/22
Trang 5
Đồ HỌA MÁY TÍNH • Ví dụ : Cho A(12, 20) và B(22, 27), ta có m= 0.7 í Xi / 7 0 12 20 20 I 13 21 20,7 2 14 21 21.4 q 15 22 22,1 4 16 TT Q 17 6 18 7 19 8 20 9 21 10 22 27 • Cài đặt m inh họa thuật toán DDA #define Round(a) int(a+0.5) int Color = GREEN; void LineDDA (int x1, int y1, int x2, int y2) { int X = x 1 ; float y = y1; float m = float(y2-y1)/(x2-x1); putpixel(x, Round(ỵ), Color); for(int i=x1; i<x2; i++) { X + + ; ỵ+=m; putpixel(x, Round(y), Color); } }// LineDDA ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 5/22
Trang 6
Đồ HỌA MÁY TÍNH T h . u ẹ . t t o á n . J i r e i 3 6j j . b a . j j j . ( X ị + 1 , y ) yi+1 y Vi X; Xị+1 • Gọi (Xị+l,ỵ) là điểm thuộc đoạn thẳng. Ta có: y = m{xi +l)+ b di = y - V i Đ ặt d 2 = ( y i + l ) - y • Xét tấ t cả các vị trí tương đôi của y so với yi và yị +1, việc chọn điểm (xi+1,yi+i) là s hay p phụ thuộc vào việc so sánh d 1và d2 hay dấu của d ỵ - d 2 : ♦ Nếu d x - d 2 < 0 5ta sẽ chọn điểm s, tức là 3^+1 - . ♦ Ngược lại, nếu dị - d 2 > 0 ? ta sẽ chọn điểm p, tức là yi+i = y t +1 • Xét Pi = Dx(d! - d 2)= Dx{2y - 2yi - 1) => Pi = Dx[2(m(xi + ì ) + b ) - 2 y i - l] ThiNganHang.com
Trang 7
Đồ HỌA MÁY TÍNH • Thay 171- ß vào phương trìn h trê n ta được : Pị = 2DyXị - 2D xy¿+ c f với c = 2Dy + (26 - 1 )D x. • N hậ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ó : P i+1 - Pi = (2D y x i+1 - 2D x yi+! + c ) - { 2D y x i - 2D x y t + c ) P i +1 - P i = 2Đ y ( xi+1 - X i ) - 2D x ( y i+1 - y t ) <=>P/+1 - Pi = 2 íty - 2Dxịyi+1 - y ¿), do xi+1 =Xị +l • Từ đây ta có thể suy ra cách tính Pi+1 tư Pi như S8.U I ♦ Nếu Pi < 0 thì Pi+1 = Pi + do ta chọn y¿+i = J i . ♦ Ngược lại, nếu Pi —0 ? thì P i+1 = —2 D x f đo ta chọn y i+1 = J'i + 1 . • Giá trị Po được tính từ điểm vẽ đầu tiên (*0>y<>) theo công thức : p 0 = 2Dyxữ - 2Dxyữ +c = 2Dyx0 - 2Dxyữ+ 2Dy - (26 - l)zfoc • Do (*^0 J3^0 ) là điểm nguyên thuộc về đoạn thẳng D y nên ta có ^0 = m x 0 +b = xữ+b ' rpkg v£0 phương trìn h trê n ta suy ra : Po = 2Dy —D x. ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 7/22
Trang 8
Đồ HỌA MÁY TÍNH Lưu đồ thuật toán Bresenham ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 8/22
Trang 9
Đồ HỌA MÁY TÍNH • Ví dụ : Cho A(12, 20) và B(22, 27), • Ta có ♦ Dx = 22-12 = 10, Dy=27-20=7 ♦ C onstl = 2Dy = 14, Const2 = 2(Dy - Dx) = -6 ♦ Po = 2Dy - Dx = 14-10 = 4 í Xi / pi 0 12 20 1 Jí 13 21 -2 2 14 21 12 on 15 2 2 6 4 16 23 0 5 17 24 -6 6 18 24 8 7 19 25 2 8 20 26 ~/± 1 9 21 26 10 10 22 27 4 ■ • N hận xét ♦ Thuật toán Bresenham chỉ làm việc trên số nguyên và các thao tác trên số nguyên chỉ là phép cộng và phép dịch bit (phép nhân 2) điều này là một cải tiến làm tăng tốc độ đáng kể so với th u ật toán DDA. Ý tưởng chính của th u ật toán nằm ở 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. ♦ Thuật toán này cho k ết quả tương tự như th u ật toán DDA. ThiNganHang.com Dương Anh Đức, Lê Đình Duy Các thuột ỉoán vẽ dường 9/22
Trang 10
Đồ HỌA MÁY TÍNH • Cài đặt m inh họa thuật toán Bresenham void LineBres (int x1, int ỵ1, int x2, int y2) { int Dx, Dy, p, Constl, Const2; int X, y; Dx = x2 - x1 ; Dy = y2 - y1 ; p = 2*Dy - Dx; / / Dy « 1 - Dx Constl = 2*Dy; // Dy « 1 Const2 = 2*(Dy-Dx); // (Dy-Dx) « 1 X = x1 ; y = y1; putpixel(x, y, Color); for(i=x1 ; i<x2; i++) { if (p<0) p += Constl ; else { p += Const2; y++; } X + + ; putpixel(x, y, Color); } } // LineBres ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ dường 10/22
Trang 11
Đồ HỌA MÁY TÍNH T huật M íđPom t t o é . ỉ i • Thuật toán MidPoint đưa ra cách chọn 3^+1 là Ji hay Vi + 1 bằng cách so sánh điểm thực q (* ; +1>J/) với điểm MidPoint là trung điểm của s và p. Ta có : ♦ Nếu điểm Q nằm dưới điểm MidPoint, ta chọn s. ♦ Nếu điểm Q nằm trên điểm M idPoint ta chọn p. • Ta có dạng tổng quát của phương trìn h đường thẳng : Ax + By + C = 0 với A = y 2 - y , , B =~{x2 - x , ) , c =x 2y! - x , y 2 • Đặt F(x, y) =Ax +By + c t ta có nhận xét : < 0 ,n ếu (x?y )n ằ m p h ía tr ê n đường th ẳ n g F(x,;ỵ}Ị= 0, nếu (x,y) thuộc về đường th ẳ n g > 0, nếu (x, y ) n ằm p h ía dưới đường th ẳ n g . ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ đường 11/22
Trang 12
Đồ HỌA MÁY TÍNH Lúc này việc chọn các điểm s, p ở trê n được đưa về việc xét dấu của Pi = 2F(MidPoint) = 2F X ị +1, + — ♦ Nếu P i < 0 , điểm M idPoint nằm phía trên đoạn thẳng. Lúc này điểm thực Q nằm dưới điểm MidPoint nên ta chọn s, tức là y ị+1 = y ị . ♦ Ngược lại, nếu P i —0 , điểm MidPoint nằm phía dưới đoạn thẳng. Lúc Iiày điểm thực Q nằm trên điểm MidPoint nên ta chọn p, tức là 3^+1 —yi + 1 . • M ặt khác : Pi+1 - P i = 2F xi+1+1,yi+1+ -2F Xi +1,yi +■ ^ P i +1-Pi =2 A(xi+1+ l ) + B yi+1+ ị ^ + c - 2 Afa+l) +B x + l3 ^ 1 + c «=> P i+1 - P i = 2 A + 2B {yi+1 - y i ) = 2Đ y - 2D x { yi+1 - y . ) • Như vậy : ♦ Pi+1 = Pi + }nếu Pj < 0 do ta chọn = J i . ♦ Pi+1 = P i + 2Dy - 2D x, nếu P i - 0 do ta chọn yi+i = y i+ 1 ■ • Ta tín h giá trị Po ứng với điểm ban đầu (*o>.)'o), với nhận xét rằng (^o^o) là điểm thuộc về đoạn thẳng, tức là có :Ax0+By0+c = 0 Po = Xo+I,y0 + 2 2 A{x0+1) + B y0+—l+c = p0= 2(Ajc0+By0+c)+2A + B = 2A + B =2Z)v- ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ đường 12/22
Trang 13
Đồ HỌA MÁY TÍNH 'J8.u Jj.GI' 7 2 ' 7 _ ' ¿ ỉ Jtrs . • Xét th u ật toán Bresenham, với cách đặt di và (Ỉ2 như trên, có khi nào di hay d2 âm hay không ? Cho ví dụ m inh họa. • Tại sao phải so sánh giá trị Pi với 0 trong các thuật toán MidPoint và Bresenham, bản chất của việc so sánh này là gì ? • Tại sao phải nhân F(MidPoint) với 2 khi gán cho Pi theo công thức pi=2*F(MidPoint) ? ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ dường 13/22
Trang 14
Đồ HỌA MÁY TÍNH • Cài đ ặt th u ật toán cho trường hợp 0 < m < 1, Dx<0. Ta sử dụng th u ật toán với trường hợp 0 < m < 1, Dx>0 đã cài đặt cộng thêm một sô" thay đổi sau : ♦ Thay biểu thức x=x+l bằng x=x-l và y=y+l bằng y=y-l vì trong trường hợp này X và y đều giảm dần. ♦ N hận xét rằng khi p<0 ta gán p=p+Constl, như vậy để hướng đến sự cân bằng C onstl phải là m ột giá trị dương. Tương tự như vỆ3r, khi p>0 ta gán p=p+Const2, Const2 phải là giá trị âm. ♦ Từ nhận xét trên, trong các công thức ta sẽ thay Dx bằng abs(Dx), Dy bằng abs(Dy). • Mở rộng thuật toán trê n để vẽ đoạn thẳng trong trường hợp m bất kì. ♦ Trường hợp đặc biệt m=oo : Đoạn thẳng song song trục tung nên rấ t đơn giản khi vẽ. ♦ Trường hợp -1 < m < 1 : Sử dụng các công thức của thuật toán vẽ trong trường hợp 0< m < 1, Dx>0 và thay đổi một số điểm sau : ❖ Nếu Dx<0 thì bước nhảy của X sẽ thay bằng -1 . Tương tự nếu Dy<0, bước nhảy của y cũng sẽ là -1 . ❖ Thay Dx bằng abs(Dx), Dy=abs(Dy) trong tấ t cả các công thức có chứa Dx, Dy. ♦ Trường hợp m < -1 hay m > 1 : ❖ Thay đổi vai trò của X và y, nghĩa là thay X bằng y, y bằng X, Dx bằng Dy, Dy bằng Dx trong tấ t cả các công thức. ❖ Thực hiện nguyên tắc về bước nhảy, thay đổi công thức Dx, Dy như trong trường hợp - 1 < m < 1 ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ dường 14/22
Trang 15
Đồ HỌA MÁY TÍNH Vẽ dư ờng trò n , b ằ n g thuậ.t taán M id p o in t • Do tín h đôi xứng của đường tròn (C) nên ta chỉ cần vẽ cung (C1/8) là cung 1/8 đường tròn, sau đó lấy đối xứng. Cung (C1/8) được mô tả như sau (cung của phần tô xám trong hình vẽ) : o <X<R— < 2 R — < y < R . 2 • Như vậy nếu có (x, y) e (C1/8) th ì các điểm : (y, x), (y,- x), (x,-y), (-x,-y), (-y,-x), (-y,x), (-x,y) sẽ thuộc (C). ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ dường 15/22
Trang 16
Đồ HỌA MÁY TÍNH • Chọn điểm bắt đầu để vẽ là điểm (0,R). • Dựa vào hình vẽ, nếu (*¿>^1) là điểm nguyên đã tìm được ở bước thứ i, thì điểm f c + i J i + 1 ) ở bước thứ (i+1) là sự lựa chọn giữa s và p. x i+1 = x i + l • Như vậy : y i+i e b i , y, - 1} • Đặt F { x , y ) —X + y —R ; ta có : < 0, nếu (x, y) nằm trong đường tròn F(z,;y)|= 0, nếu (x, y) nằm trê n đường tròn > 0, nếu (x, y ) nằm ngoài đường tròn. ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ dường 1Ó/22
Trang 17
Đồ HỌA M ÁY TÍNH • Xét Pi =^ (MidPoint) = F( xi +1^ i1 1 . Ta có 9 V z y ♦ Nếu Pi < 0 , điểm MidPoint nằm trong đường tròn. Lúc này điểm thực Q gần s hơn nên ta chọn s, tức là 3^+1 = . ♦ Ngược lại, nếu Pi - 0 ì điểm M idPoint nằm ngoài đường tròn. Lúc này điểm thực Q gần p hơn nên ta chọn p, tức I à j i+1 = J i - 1 . • M ặt khác : P u 1 - P i = F *;+i + 1>yí+i 2 - F X ị + 1 , y , — / 1 2 / V V fe+1+ l)2+ yi+i f e + ự + - R 2 * 2 <=> A+1 - p, = 2x, + 3 + (yf+1 - y? ) - (ỵM - ỵ ) • Vậy : ♦ Pi+1 = P i + %x i + 3 } nếu P i < 0 ¿ 0 ị a chọn yi+ i — y t . ♦ Pi+1 = Pi + —2 y t + 5 } nếu Pị > 0 ¿0 ta chọn y*! = Vi - 1 . • Pữ ứng với điểm ban đầu (*o>yo) - (o,-R). Po = F *0+ l , y0- = F 1, R - = - - R 4 ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ đường 17/22
Trang 18
Đồ HỌA MÁY TÍNH Lưu đồ thuật toán MidPoint vẽ đường tròn ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ dường 18/22
Trang 19
Đồ HỌA MÁY TÍNH Cài đặt minh họa thuật toán MidPoint vẽ đường tròn void CircleMidPoint (int R) { int X, y; X = 0; y = R; Put8Pixel(x, y); P = 1 - R; / / 5/4-R while (x < y) { ¡1(p < 0) p += 2*x + 3; else { p += 2*(x -y) + 5; y--; } X + + ; Put8Pixel(x, y); } } // CircleMidPoint ThiNganHang.com Dương Anh Đức, Lê Đình Duy C ác thuột toán vẽ đường 19/22
Trang 20
DO HQA MAY TÎNH • VI du : Vë diiôing trôn tâm 1(0,0), ban kinh R=15. I Xi Pi Deltal Delt:a2 y -14 0 0 15 1-15 3 -25 J1 JI 15 - 1ij j -14+2*(0)+3 5 -23 2 2 15 -6 -11+2*(1)+3 7 -21 o o 15 1 -6+2*(2)+3 9 -19 vJ <J A- 4 14 -18 1+2"(3-15)+5 11 -15 •J rr 14 -7 -18+2*(4)+3 13 -13 IZ o 6 6 14 6 -7+2*(5)+3 15 -11 7 7 18 -5 6+2(6-14)+5 17 -7 8 8 18 12 -5+2(7)+3 19 9 9 12 7 12+2(8-13)+5 21 -1 10 10 j\ ji 6 7+2(S-12)+5 23 3 ji ij ji ij 10 S 6+2(10-11)+5 ntz / N hân xét : • Neu dat Deltal = 2*x+3, Delta2 = 2*(x-y)+5 thi ♦ Do moi butfc dêu tâng x nên sau môi làn lap giâ tri D eltal luôn tâng 2. ♦ Do y bi giâm 1 khi gâp p>0 và giüf nguyên giâ tri trong trtfcfng hç/p ngiiOc lai nên neu làn lap trirôc giâ tri p>0 thi giâ tri Delta2 së duoc tâng 4 và neu làn lap trirôc giâ tri p<0 thi giâ tri Delta2 së duiOc tâng 2 mà thôi. • Hây toi liu ho a cài dat thuât toân MidPoint vë diidng trôn tif nhân xét trên. ThiNganHang.com Dufdng Anh Dde, Lê Dinh Duy Câc thuât toân vê difàng 20/22
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!