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

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ả
Nội dung trích xuất từ tài liệu:
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õ ñöôøngDaã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ÍNHThuaä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(in ...