GIÁO TRÌNH ĐỒ HỌA MÁY TÍNH_CÁC THUẬT TOÁN VẼ ĐƯỜNG

Chia sẻ: Tranthi Kimuyen | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

310
lượt xem 88
download

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

Tham khảo tài liệu 'giáo trình đồ họa máy tính_các thuật toán vẽ đường', công nghệ thông tin, đồ họa - thiết kế - flash phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: GIÁO TRÌNH ĐỒ HỌA MÁY TÍNH_CÁC THUẬT TOÁN VẼ ĐƯỜNG

ÑOÀ HOÏA MAÙY TÍNH Caùc thuaät toaùn veõ ñöôøng Daãn nhaäp • Giaû söû toïa ñoä caùc ñieåm nguyeân sau khi xaáp xæ ñoái töôïng thöïc laàn löôït laø (x i , yi ), i = 0,... . Ñaây laø caùc ñieåm nguyeân seõ ñöôïc hieån thò treân maøn hình. • Baøi toaùn ñaët ra laø neáu bieát ñöôïc (x i , y i ) laø toïa ñoä nguyeân xaùc ñònh ôû böôùc thöù i, ñieåm nguyeân tieáp theo (x i+1 , yi+1 ) seõ ñöôïc xaùc ñònh nhö theá naøo. • Ñoái töôïng hieån thò treân löôùi nguyeân ñöôïc lieàn neùt, caùc ñieåm maø (x i+1 , yi+1 ) coù theå choïn chæ laø moät trong taùm ñieåm ñöôïc ñaùnh soá töø 1 ñeán 8 trong hình sau (ñieåm ñen chính laø (x i , yi ) ).Hay noùi caùch khaùc : (xi+1 , yi+1 ) = (xi ± 1, yi ± 1) . 4 3 2 5 1 6 7 8 • Daùng ñieäu cuûa ñöôøng seõ cho ta gôïi yù khi choïn moät trong taùm ñieåm treân. Caùch choïn caùc ñieåm nhö theá naøo seõ tuøy thuoäc vaøo töøng thuaät toaùn treân cô sôû xem xeùt tôùi vaán ñeà toái öu toác ñoä. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 1/22
ÑOÀ HOÏA MAÙY TÍNH Thuaät toaùn veõ ñöôøng thaúng • Xeùt ñoaïn thaúng coù heä soá goùc 0 < m < 1 vaø Dx > 0 . • Vôùi caùc ñoaïn thaúng daïng naøy, neáu (x i , y i ) laø ñieåm ñaõ xaùc ñònh ñöôïc ôû böôùc thöù i (ñieåm maøu ñen) thì ñieåm caàn choïn (x i+1 , y i+1 ) ôû böôùc thöù (i+1) seõ laø moät trong hai tröôøng hôïp nhö hình veõ sau :  x i +1 = x i + 1   yi+1 ∈ {yi , yi + 1} (xi+1, yi+1) 2 yi (xi+1, yi) 1 xi • Vaán ñeà coøn laïi, laø caùch choïn moät trong hai ñieåm treân nhö theá naøo ñeå coù theå toái öu veà maët toác ñoä. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 2/22
ÑOÀ HOÏA MAÙY TÍNH Thuaät toaùn DDA (Digital Differential Analyzer) • Vieäc quyeát ñònh choïn yi +1 laø yi hay yi + 1 , döïa vaøo phöông trình cuûa ñoaïn thaúng y = mx + b . Nghóa laø, ta seõ tính toïa ñoä cuûa ñieåm (x i + 1, y) thuoäc veà ñoaïn thaúng thöïc. Tieáp ñoù, yi+1 seõ laø giaù trò sau khi laøm troøn giaù trò tung ñoä y. y = m( x i + 1) + b • Nhö vaäy : y = Round ( y) i +1 (xi+1, Round(y)) (xi+1, y) (xi, yi) • Neáu tính tröïc tieáp giaù trò thöïc y ôû moãi böôùc töø phöông trình y = mx + b thì phaûi caàn moät pheùp toaùn nhaân vaø moät pheùp toaùn coäng soá thöïc. Ñeå caûi thieän toác ñoä, ngöôøi ta tính giaù trò thöïc cuûa y ôû moãi böôùc theo caùch sau ñeå khöû pheùp tính nhaân treân soá thöïc : y sau = mx i +1 + b = m(x i + 1) + b • Nhaän xeùt raèng : y tröôùc = mx i + b ⇒ y sau = y tröôùc + m Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 3/22
ÑOÀ HOÏA MAÙY TÍNH Löu ñoà thuaät toaùn DDA Begin m=Dy/Dx; x=x1; y=y1; putpixel(x, Round(y), c); x
ÑOÀ HOÏA MAÙY TÍNH • Ví duï : Cho A(12, 20) vaø B(22, 27), ta coù m= 0.7 i xi yi y 0 12 20 20 1 13 21 2 0 .7 2 14 21 2 1 .4 3 15 22 2 2 .1 4 16 5 17 6 18 7 19 8 20 9 21 10 22 27 • Caøi ñaët minh hoïa thuaät toaùn DDA #define Round(a) int(a+0.5) int Color = GREEN; void LineDDA (int x1, int y1, int x2, int y2) { int x = x1; float y = y1; float m = float(y2-y1)/(x2-x1); putpixel(x, Round(y), Color); for(int i=x1; i
ÑOÀ HOÏA MAÙY TÍNH Thuaät toaùn Bresenham (xi+1, y) yi+1 P d2 y d1 yi S xi xi+1 • Goïi (x i + 1, y) laø ñieåm thuoäc ñoaïn thaúng. Ta coù: y = m(x i + 1) + b . d1 = y − y i • Ñaët d = ( y + 1) − y i 2 • Xeùt taát caû caùc vò trí töông ñoái cuûa y so vôùi yi vaø y i + 1 , vieäc choïn ñieåm ( xi +1 , yi+1 ) laø S hay P phuï thuoäc vaøo vieäc so saùnh d1 vaø d2 hay daáu cuûa d1 − d2 : ♦ Neáu d1 − d2 < 0 , ta seõ choïn ñieåm S, töùc laø yi +1 = y i . ♦ Ngöôïc laïi, neáu d1 − d2 ≥ 0 , ta seõ choïn ñieåm P, töùc laø yi+1 = yi + 1 • Xeùt pi = Dx(d1 − d2 ) = Dx(2 y − 2 yi − 1) ⇒ p i = Dx[2(m(x i + 1) + b) − 2 y i − 1] Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 6/22
ÑOÀ HOÏA MAÙY TÍNH Dy m= • Thay vaøo phöông trình treân ta ñöôïc : Dx pi = 2Dyxi − 2 Dxyi + c , vôùi c = 2 Dy + (2b − 1)Dx . • Nhaän xeùt raèng neáu taïi böôùc thöù i ta xaùc ñònh ñöôïc daáu cuûa pi thì xem nhö ta xaùc ñònh ñöôïc ñieåm caàn choïn ôû böôùc (i+1). • Ta coù : pi +1 − pi = (2 Dyxi+1 − 2 Dxyi +1 + c) − (2 Dyxi − 2 Dxyi + c) ⇔ pi +1 − pi = 2 Dy(x i +1 − x i ) − 2 Dx( yi +1 − yi ) ⇔ pi+1 − pi = 2 Dy − 2 Dx( yi+1 − yi ), do xi+1 = xi + 1 • Töø ñaây ta coù theå suy ra caùch tính pi+1 töø pi nhö sau : pi < 0 thì pi+1 = pi + 2 Dy do ta choïn yi+1 = y i . ♦ Neáu ♦ Ngöôïc laïi, neáu pi ≥ 0 , thì p i +1 = p i + 2 Dy − 2 Dx , do y i +1 = y i + 1 . ta choïn • Giaù trò p0 ñöôïc tính töø ñieåm veõ ñaàu tieân (x 0 , y0 ) theo coâng thöùc : p0 = 2Dyx0 − 2Dxy0 + c = 2Dyx0 − 2 Dxy0 + 2Dy − (2b − 1)Dx (x 0 , y 0 ) • Do laø ñieåm nguyeân thuoäc veà ñoaïn thaúng Dy neân ta coù y0 = mx0 + b = Dx x 0 + b . Theá vaøo phöông trình treân ta suy ra : p0 = 2 Dy − Dx . Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 7/22
ÑOÀ HOÏA MAÙY TÍNH Löu ñoà thuaät toaùn Bresenham Begin p=2Dy-Dx; Const1=2Dy; Const2=2(Dy-Dx); x=x1; y=y1; putpixel(x, y, c); x
ÑOÀ HOÏA MAÙY TÍNH • Ví duï : Cho A(12, 20) vaø B(22, 27), • Ta coù ♦ Dx = 22-12 = 10, Dy=27-20=7 ♦ Const1 = 2Dy = 14, Const2 = 2(Dy – Dx) = -6 ♦ p0 = 2Dy – Dx = 14-10 = 4 i xi yi pi 0 12 20 4 1 13 21 -2 2 14 21 12 3 15 22 6 4 16 23 0 5 17 24 -6 6 18 24 8 7 19 25 2 8 20 26 -4 9 21 26 10 10 22 27 4 • Nhaän xeùt ♦ Thuaät toaùn Bresenham chæ laøm vieäc treân soá nguyeân vaø caùc thao taùc treân soá nguyeân chæ laø pheùp coäng vaø pheùp dòch bit (pheùp nhaân 2) ñieàu naøy laø moät caûi tieán laøm taêng toác ñoä ñaùng keå so vôùi thuaät toaùn DDA. YÙ töôûng chính cuûa pi thuaät toaùn naèm ôû choã xeùt daáu ñeå quyeát ñònh ñieåm keá tieáp, vaø söû duïng coâng thöùc truy hoài pi +1 − pi ñeå tính pi baèng caùc pheùp toaùn ñôn giaûn treân soá nguyeân. ♦ Thuaät toaùn naøy cho keát quaû töông töï nhö thuaät toaùn DDA. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 9/22
ÑOÀ HOÏA MAÙY TÍNH • Caøi ñaët minh hoïa thuaät toaùn Bresenham void LineBres (int x1, int y1, int x2, int y2) { int Dx, Dy, p, Const1, Const2; int x, y; Dx = x2 - x1; Dy = y2 - y1; p = 2*Dy - Dx; // Dy
ÑOÀ HOÏA MAÙY TÍNH Thuaät toaùn MidPoint • Thuaät toaùn MidPoint ñöa ra caùch choïn yi+1 laø yi hay y i + 1 baèng caùch so saùnh ñieåm thöïc Q (x i + 1, y ) vôùi ñieåm MidPoint laø trung ñieåm cuûa S vaø P. Ta coù : ♦ Neáu ñieåm Q naèm döôùi ñieåm MidPoint, ta choïn S. ♦ Neáu ñieåm Q naèm treân ñieåm MidPoint ta choïn P. Q(xi+1, y) yi+1 P MidPoint yi S xi xi+1 • Ta coù daïng toång quaùt cuûa phöông trình ñöôøng thaúng : Ax + By + C = 0 vôùi A = y2 − y1 , B = −(x 2 − x1 ), C = x 2 y1 − x1 y2 • Ñaët F (x, y) = Ax + By + C , ta coù nhaän xeùt : < 0, neáu (x, y ) naèm phía treân ñöôøng thaúng  F (x, y)= 0, neáu (x, y ) thuoäc veà ñöôøng thaúng > 0, neáu (x, y ) naèm phía döôùi ñöôøng thaúng.  Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 11/22
ÑOÀ HOÏA MAÙY TÍNH • Luùc naøy vieäc choïn caùc ñieåm S, P ôû treân ñöôïc ñöa veà  1 pi = 2 F (MidPoint ) = 2 F  xi + 1, yi +  . vieäc xeùt daáu cuûa  2 ♦ Neáu pi < 0 , ñieåm MidPoint naèm phía treân ñoaïn thaúng. Luùc naøy ñieåm thöïc Q naèm döôùi ñieåm MidPoint neân ta y i +1 = y i . choïn S, töùc laø ♦ Ngöôïc laïi, neáu pi ≥ 0 , ñieåm MidPoint naèm phía döôùi ñoaïn thaúng. Luùc naøy ñieåm thöïc Q naèm treân ñieåm MidPoint neân ta choïn P, töùc laø yi +1 = yi + 1 . • Maët khaùc : 1 1   pi +1 − pi = 2 F  x i +1 + 1, y i +1 +  − 2 F  x i + 1, y i +  2 2   1 1       ⇔ pi+1 − pi = 2 A(xi+1 + 1) + B yi+1 +  + C − 2 A(xi + 1) + B yi +  + C 2 2       ⇔ pi+1 − pi = 2 A + 2 B( yi+1 − yi ) = 2 Dy − 2 Dx( yi +1 − yi ) • Nhö vaäy : pi+1 = pi + 2 Dy , neáu pi < 0 do ta choïn yi +1 = yi . ♦ pi ≥ 0 pi +1 = pi + 2 Dy − 2 Dx , neáu do ta choïn ♦ y i +1 = y i + 1 . • Ta tính giaù trò p0 öùng vôùi ñieåm ban ñaàu (x 0 , y0 ) , vôùi nhaän xeùt raèng (x 0 , y0 ) laø ñieåm thuoäc veà ñoaïn thaúng, töùc laø coù : Ax0 + By0 + C = 0 1 1     p0 = 2 F  x 0 + 1, y0 +  = 2 A(x 0 + 1) + B y0 +  + C  2 2     ⇒ p0 = 2( Ax0 + By0 + C ) + 2 A + B = 2 A + B = 2 Dy − Dx Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 12/22
ÑOÀ HOÏA MAÙY TÍNH Caâu hoûi kieåm tra • Xeùt thuaät toaùn Bresenham, vôùi caùch ñaët d1 vaø d2 nhö treân, coù khi naøo d1 hay d2 aâm hay khoâng ? Cho ví duï minh hoïa. • Taïi sao phaûi so saùnh giaù trò pi vôùi 0 trong caùc thuaät toaùn MidPoint vaø Bresenham, baûn chaát cuûa vieäc so saùnh naøy laø gì ? • Taïi sao phaûi nhaân F(MidPoint) vôùi 2 khi gaùn cho pi theo coâng thöùc pi=2*F(MidPoint) ? Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 13/22
ÑOÀ HOÏA MAÙY TÍNH • Caøi ñaët thuaät toaùn cho tröôøng hôïp 0 ≤ m ≤ 1, Dx0 ñaõ caøi ñaët coäng theâm moät soá thay ñoåi sau : ♦ Thay bieåu thöùc x=x+1 baèng x=x-1 vaø y=y+1 baèng y=y-1 vì trong tröôøng hôïp naøy x vaø y ñeàu giaûm daàn. ♦ Nhaän xeùt raèng khi p0 vaø thay ñoåi moät soá ñieåm sau : v Neáu Dx
ÑOÀ HOÏA MAÙY TÍNH Veõ ñöôøng troøn baèng thuaät toaùn MidPoint • Do tính ñoái xöùng cuûa ñöôøng troøn (C) neân ta chæ caàn veõ cung (C1/8) laø cung 1/8 ñöôøng troøn, sau ñoù laáy ñoái xöùng. Cung (C1/8) ñöôïc moâ taû nhö sau (cung cuûa phaàn toâ xaùm trong hình veõ) :  2 0 ≤ x ≤ R 2   2   2 ≤ y≤R R  (-x,y) (x,y) (y,x) (-y,x) R 2 (-y,-x) (y,-x) (-x,-y) (x,-y) • Nhö vaäy neáu coù (x, y) ∈ (C1/8) thì caùc ñieåm : (y, x), (y,- x), (x,-y), (-x,-y), (-y,-x), (-y,x), (-x,y) seõ thuoäc (C). Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 15/22
ÑOÀ HOÏA MAÙY TÍNH • Choïn ñieåm baét ñaàu ñeå veõ laø ñieåm (0,R). • Döïa vaøo hình veõ, neáu ( x i , yi ) laø ñieåm nguyeân ñaõ tìm ñöôïc ôû böôùc thöù i, thì ñieåm (x i+1 , yi +1 ) ôû böôùc thöù (i+1) laø söï löïa choïn giöõa S vaø P.  x i +1 = x i + 1 • Nhö vaäy :  yi +1 ∈ {yi , yi − 1}  Q(xi+1, y) yi S MidPoint yi-1 P xi xi+1 • Ñaët F (x, y) = x + y − R , ta coù : 2 2 2 < 0, neáu (x, y ) naèm trong ñöôøng troøn  F (x, y)= 0, neáu (x, y ) naèm treân ñöôøng troøn > 0, neáu (x, y ) naèm ngoaøi ñöôøng troøn.  Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 16/22
ÑOÀ HOÏA MAÙY TÍNH 1  pi = F (MidPoint ) = F  x i + 1, y i −  . Ta coù : Xeùt • 2  ♦ Neáu pi < 0 , ñieåm MidPoint naèm trong ñöôøng troøn. Luùc naøy ñieåm thöïc Q gaàn S hôn neân ta choïn S, töùc y i +1 = y i . laø ♦ Ngöôïc laïi, neáu pi ≥ 0 , ñieåm MidPoint naèm ngoaøi ñöôøng troøn. Luùc naøy ñieåm thöïc Q gaàn P hôn neân ta choïn P, töùc y i +1 = y i − 1 . laø • Maët khaùc : 1 1   pi +1 − pi = F  x i+1 + 1, yi +1 −  − F  x i + 1, y i −  2 2   2 2    1 1   − pi = (xi+1 + 1) +  yi+1 −  − R  − (xi + 1) +  yi −  − R2  2 2 ⇔ pi+1 2 2 2         ( ) ⇔ pi+1 − pi = 2xi + 3 + yi2+1 − yi2 − ( yi+1 − yi ) • Vaäy : pi +1 = pi + 2 x i + 3 , neáu pi < 0 do ta choïn yi+1 = yi . ♦ pi ≥ 0 pi+1 = pi + 2 x i − 2 yi + 5 , neáu do ta choïn ♦ y i +1 = y i − 1 . p 0 öùng vôùi ñieåm ban ñaàu (x 0 , y0 ) = (0, R ) . • 1 1 5   p0 = F  x 0 + 1, y0 −  = F  1, R −  = − R 2 2 4   Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 17/22
ÑOÀ HOÏA MAÙY TÍNH Löu ñoà thuaät toaùn MidPoint veõ ñöôøng troøn Begin p=5/4-R; x=0; y=R; Put8Pixel(x, y, c); x
ÑOÀ HOÏA MAÙY TÍNH Caøi ñaët minh hoïa thuaät toaùn MidPoint veõ ñöôøng troøn void CircleMidPoint (int R) { int x, y; x = 0; y = R; Put8Pixel(x, y); p = 1 - R; // 5/4-R while (x < y) { if (p < 0) p + = 2* x + 3; else { p += 2*(x -y) + 5; y--; } x++; Put8Pixel(x, y); } } // CircleMidPoint Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn veõ ñöôøng 19/22
ÑOÀ HOÏA MAÙY TÍNH • Ví duï : Veõ ñöôøng troøn taâm I(0,0), baùn kính R=15. i xi yI pi Delta1 Delta2 0 0 15 -14 1-15 3 -25 1 1 15 -11 -14+2*(0)+3 5 -23 2 2 15 -6 -11+2*(1)+3 7 -21 3 3 15 1 -6+2*(2)+3 9 -19 4 4 14 -18 1+2*(3-15)+5 11 -15 5 5 14 -7 -18+2*(4)+3 13 -13 6 6 14 6 -7+2*(5)+3 15 -11 7 7 13 -5 6+2(6-14)+5 17 -7 8 8 13 12 -5+2(7)+3 19 -5 9 9 12 7 12+2(8-13)+5 21 -1 10 10 11 6 7+2(9-12)+5 23 3 11 11 10 9 6+2(10-11)+5 25 7 Nhaän xeùt : • Neáu ñaët Delta1 = 2*x+3, Delta2 = 2*(x-y)+5 thì ♦ Do moãi böôùc ñeàu taêng x neân sau moãi laàn laëp giaù trò Delta1 luoân taêng 2. ♦ Do y bò giaûm 1 khi gaëp p≥0 vaø giöõ nguyeân giaù trò trong tröôøng hôïp ngöôïc laïi neân neáu laàn laëp tröôùc giaù trò p≥0 thì giaù trò Delta2 seõ ñöôïc taêng 4 vaø neáu laàn laëp tröôùc giaù trò p