Bài giảng đồ họa : Các thuật toán vẽ đường part 2

Gọi (x i + 1, y) là điểm thuộc đoạn thẳng. Ta có: y = m(x i + 1) + b . • Đặt d = ( y + 1) − y 2 i • Xét tất cả các vị trí tương đối của y so với yi và y i + 1 , việc chọn điểm ( xi +1 , yi+1 ) là S hay P phụ thuộc vào việc so sánh d1 và d2 hay dấu của d1 − d2 :♦ Nếu d1 − d2
Nội dung trích xuất từ tài liệu:
Bài giảng đồ họa : Các thuật toán vẽ đường part 2 ÑOÀ HOÏA MAÙY TÍNHThuaä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 Bresenhamvoid LineBres (int x1, int y1, int x2, int y2){ int Dx, Dy, p, Const1, Const ...