Tài liệu Bài giảng chi tiết về đồ họa máy tính

ÑOÀ HOÏA MAÙY TÍNH Hieån thò ñoái töôïng hai chieàu Moät soá khaùi nieäm • Cöûa soå (window) laø moät vuøng ñöôïc choïn ñeå hieån thò trong heä toïa ñoä theá giôùi thöïc. • Vuøng quan saùt (viewport) laø vuøng ñöôïc choïn treân thieát bò hieån thò ñeå caùc ñoái töôïng ôû trong cöûa soå aùnh xaï vaøo. • Cöûa soå xaùc ñònh caùi gì ñöôïc thaáy treân thieát bò hieån thò, coøn vuøng quan saùt xaùc ñònh nôi naøo noù seõ ñöôïc hieån thò. • Quaù trình aùnh xaï moät vuøng ñònh nghóa trong heä toïa ñoä theá giôùi thöïc vaøo moät vuøng trong heä toïa ñoä thieát bò ñöôïc goïi laø pheùp bieán ñoåi heä quan saùt (viewing transformation). Window Viewport ywmax yvmax yvmin ywmin xwmin Döông Anh Ñöùc, Leâ Ñình Duy xwmax xvmin xvmax Hieån thò ñoái töôïng hai chieàu 1/7 ÑOÀ HOÏA MAÙY TÍNH Qui trình hieån thò ñoái töôïng hai chieàu • Tröôùc tieân, caùc ñoái töôïng seõ ñöôïc moâ taû baèng caùc ñoái töôïng ñoà hoïa cô sôû vaø caùc thuoäc tính cuûa chuùng trong töøng heä toïa ñoä cuïc boä (modeling coordinates - MC) nhaèm ñôn giaûn hoùa vaø taän duïng caùc ñaëc tröng rieâng cuûa töøng loaïi. • Sau ñoù, chuùng ta seõ duøng caùc pheùp bieán ñoåi heä toïa ñoä ñeå chuyeån caùc moâ taû töø caùc heä toïa ñoä cuïc boä naøy sang moät heä toïa ñoä theá giôùi thöïc (world coordinates WC) duy nhaát chöùa toaøn boä caùc ñoái töôïng thaønh phaàn. Pheùp chuyeån ñoåi naøy ñöôïc goïi laø pheùp chuyeån ñoåi moâ hình (modeling coordinates transformation). • Tieáp theo, chuùng ta seõ ñònh moät heä toïa ñoä quan saùt (viewing coordinates - VC), laø heä toïa ñoä moâ taû vò trí cuûa ngöôøi quan saùt ñoái töôïng. Nhôø vieäc söû duïng heä toïa ñoä naøy maø cuøng moät moâ taû, caùc ñoái töôïng coù theå ñöôïc quan saùt ôû nhieàu goùc ñoä vaø vò trí khaùc nhau. • Sau khi chuyeån caùc moâ taû ñoái töôïng töø heä toïa ñoä theá giôùi thöïc sang heä toïa ñoä quan saùt, chuùng ta seõ ñònh nghóa cöûa soå trong heä toïa ñoä naøy, ñoàng thôøi ñònh nghóa vuøng quan saùt trong heä toïa ñoä thieát bò chuaån (normalized device coordinates - NDC) coù toïa ñoä caùc chieàu thay ñoåi trong khoaûng töø 0 ñeán 1. • Sau khi thöïc hieän pheùp aùnh xaï töø cöûa soå sang vuøng quan saùt, taát caû caùc phaàn cuûa ñoái töôïng naèm ngoaøi vuøng quan saùt seõ bò xeùn (clip) vaø toaøn boä nhöõng gì naèm trong vuøng quan saùt seõ ñöôïc aùnh xaï sang heä toïa ñoä thieát bò (device coordinates - DC). Döông Anh Ñöùc, Leâ Ñình Duy Hieån thò ñoái töôïng hai chieàu 2/7 ÑOÀ HOÏA MAÙY TÍNH • Vieäc ñöa ra heä toïa ñoä thieát bò chuaån nhaèm giuùp cho vieäc töông thích deã daøng vôùi nhieàu loaïi thieát bò hieån thò khaùc nhau. • Baèng caùch thay ñoåi vò trí cuûa vuøng quan saùt chuùng ta coù theå quan saùt caùc ñoái töôïng taïi caùc vò trí khaùc nhau treân maøn hình hieån thò, ñoàng thôøi, baèng caùch thay ñoåi kích thöôùc cuûa vuøng quan saùt, chuùng ta coù theå thay ñoåi kích thöôùc vaø tính caân xöùng cuûa caùc ñoái töôïng ñöôïc hieån thò. • Chuùng ta coù theå thöïc hieän caùc hieäu öùng thu phoùng baèng caùch aùnh xaï caùc cöûa soå coù kích thöôùc khaùc nhau vaøo vuøng quan saùt coù kích thöôùc coá ñònh. Khi caùc cöûa soå ñöôïc thu nhoû, phaàn naèm trong cöûa soå seõ ñöôïc phoùng to giuùp chuùng ta deã daøng quan saùt caùc chi tieát maø khoâng theå thaáy ñöôïc trong caùc cöûa soå lôùn hôn. MC Chuyeån ñoåi töø heä toïa ñoä cuïc boä sang heä toïa ñoä theá giôùi thöïc WC Chuyeån ñoåi töø heä toïa ñoä theá giôùi thöïc sang heä toïa ñoä quan saùt Döông Anh Ñöùc, Leâ Ñình Duy VC Chuyeån ñoåi töø heä toïa ñoä quan saùt sang heä toïa ñoä thieát bò chuaån NDC AÙnh xaï töø heä toïa ñoä thieát bò chuaån sangheä toïa ñoä thieát bò DC Hieån thò ñoái töôïng hai chieàu 3/7 ÑOÀ HOÏA MAÙY TÍNH Heä toïa ñoä quan saùt • Heä toïa ñoä quan saùt : ♦ Choïn ñieåm P0 (x 0 , y0 ) trong heä toïa ñoä theá giôùi thöïc laøm goác toïa ñoä. ♦ Vector V moâ taû höôùng quan saùt ñeå ñònh höôùng cho truïc tung yv cuûa heä toïa ñoä. Vector V ñöôïc goïi laø view-up vector. • Töø V chuùng ta coù theå tính ñöôïc caùc vector ñôn vò v = (v x , v y ) vaø u = (u x , u y ) töông öùng cho caùc truïc tung yv vaø truïc hoaønh x v cuûa heä toïa ñoä. Caùc vector ñôn vò naøy seõ ñöôïc duøng ñeå taïo thaønh hai doøng ñaàu tieân cuûa ma traän quay M R ñeå ñöa caùc truïc x v y v truøng vôùi caùc truïc x w yw cuûa heä truïc toïa ñoä theá giôùi thöïc. • Ma traän cuûa pheùp chuyeån moät ñieåm trong heä toïa ñoä theá giôùi thöïc sang heä toïa ñoä quan saùt : M WC ,VC = M T M R , vôùi MT laø pheùp tònh tieán goác toïa ñoä heä quan saùt veà goác toïa ñoä heä toïa ñoä theá giôùi thöïc. yworld yworld yview yv iew y0 T xview x0 xworld xworld R xv iew (a) Döông Anh Ñöùc, Leâ Ñình Duy (b) Hieån thò ñoái töôïng hai chieàu 4/7 ÑOÀ HOÏA MAÙY TÍNH Heä toïa ñoä thieát bò chuaån • Do caùch ñònh nghóa cuûa caùc heä toïa ñoä thieát bò khaùc nhau neân moät hình aûnh hieån thò ñöôïc treân thieát bò naøy chöa chaéc hieån thò chính xaùc treân thieát bò kia. Chính vì vaäy caàn phaûi xaây döïng heä toïa ñoä thieát bò chuaån ñaïi dieän chung cho caùc thieát bò ñeå coù theå moâ taû caùc hình aûnh cuûa theá giôùi thöïc maø khoâng phuï thuoäc vaøo baát cöù thieát bò naøo. • Trong heä toïa ñoä naøy, caùc toïa ñoä x, y seõ ñöôïc gaùn caùc giaù trò trong khoaûng töø 0 ñeán 1. Nhö vaäy, vuøng khoâng gian cuûa heä toïa ñoä thieát bò chuaån chính laø hình vuoâng ñôn vò coù goùc traùi döôùi laø (0,0) vaø goùc phaûi treân (1,1). y 1 (1,1) 1 Döông Anh Ñöùc, Leâ Ñình Duy x Hieån thò ñoái töôïng hai chieàu 5/7 ÑOÀ HOÏA MAÙY TÍNH Chuyeån ñoåi töø cöûa soå sang vuøng quan saùt • Pheùp chuyeån ñoåi töø cöûa soå sang vuøng quan saùt bao goàm 3 pheùp bieán ñoåi : ♦ Pheùp tònh tieán ñeå dòch chuyeån goùc traùi döôùi veà goác toïa ñoä (hình a) ♦ Pheùp bieán ñoåi tæ leä ñeå chænh kích thöôùc cuûa cöûa soå veà cuøng kích thöôùc cuûa vuøng quan saùt (hình b, hình c) ♦ Pheùp tònh tieán dòch chuyeån veà goùc traùi döôùi cuûa vuøng quan saùt (hình d). y y v v (xmax,ymax) (umax,vmax) (xmin,ymin) (umin,vmin) x x (a) (b) u (c) u (d) • Ta coù ma traän cuûa pheùp bieán ñoåi : u − u min vmax − vmin M WV = M TW (− x min ,− y min )M S  max , x − x min y max − y min  max     =    − x min  u max − u min x max − x min 0 0 u max − u min + u min x max − x min Döông Anh Ñöùc, Leâ Ñình Duy   M TV (u min , vmin )   − y min vmax y max vmax y max − vmin − y min − vmin + vmin − y min  0   0   1  Hieån thò ñoái töôïng hai chieàu 6/7 ÑOÀ HOÏA MAÙY TÍNH • Nhö vaäy neáu P (x, y) laø ñieåm trong cöûa soå thì noù seõ coù toïa ñoä trong vuøng quan saùt laø: (sx(x − x min ) + umin , sy( y − ymin ) + vmin ) u − u min vmax − vmin sx = max , sy = y − y . vôùi x max − x min max min • sx, sy laø caùc heä soá tæ leä cuûa caùc kích thöôùc cuûa cöûa soå vaø vuøng quan saùt. Khi sx = sy = 1 , caùc ñoái töôïng qua pheùp chuyeån ñoåi seõ ñöôïc giöõ nguyeân hình daùng vaø tính caân xöùng. Döông Anh Ñöùc, Leâ Ñình Duy Hieån thò ñoái töôïng hai chieàu 7/7 ÑOÀ HOÏA MAÙY TÍNH ÑOÀ HOÏA 3 CHIEÀU Döông Anh Ñöùc, Leâ Ñình Duy Giôùi thieäu veà ñoà hoïa 3 chieàu 1/8 ÑOÀ HOÏA MAÙY TÍNH Daãn nhaäp • Caùc ñoái töôïng trong theá giôùi thöïc phaàn lôùn laø caùc ñoái töôïng 3 chieàu coøn thieát bò hieån thò chæ 2 chieàu. • Muoán coù caùc hình aûnh 3 chieàu ta caàn giaû laäp. • Chieán löôïc cô baûn laø chuyeån ñoåi töøng böôùc. Hình aûnh seõ ñöôïc hình thaønh töø töø, ngaøy caøng chi tieát hôn. • Qui trình hieån thò: Modeling Transformation Trivial Rejection Illumination Bieán ñoåi töø heä toaï ñoä ñoái töôïng sang heä toaï ñoä theá giôùi thöïc Loaïi boû caùc ñoái töôïng khoâng nhìn thaáy ñöôïc Chieáu saùng ñoái töôïng Viewing Transformation Chuyeån töø world space sang eye space Clipping Loaïi boû phaàn naèm ngoaøi viewing frustum Projection Chieáu töø eye space xuoáng screen space Rasterization Display Döông Anh Ñöùc, Leâ Ñình Duy Chuyeån ñoái töôïng sang daïng pixel Hieån thò ñoái töôïng Giôùi thieäu veà ñoà hoïa 3 chieàu 2/8 ÑOÀ HOÏA MAÙY TÍNH Caùc vaät theå 3D ñöôïc bieåu dieãn nhö theá naøo ? • Point • Vector • Line • Ray • Triangle • Polygon • Quadric curve • Spline • Quadric solid • Curved surface • v.v… Ñieåm trong khoâng gian 3 chieàu • Moâ taû moät vò trí trong khoâng gian typedef struct{ Coordinate x ; Coordinate y ; Coordinate z ; }Point3D ; (x,y,z) 3D vector • Moâ taû moät höôùng vaø bieân ñoä (magnitude) ♦ Xaùc ñònh bôûi 3 toaï ñoä dx, dy, dz _ ♦ Magnitude V = dx 2 + dy 2 + dz2 ♦ Khoâng coù vò trí trong khoâng gian • Tích voâ höôùng cuûa 2 vector ♦ V1 • V2 = dx 1 dx 2 + dy 1 dy 2 + dz1 dz 2 ♦ V1 • V2 = V1 V1 cos(Θ ) Döông Anh Ñöùc, Leâ Ñình Duy typedef struct { Coordinate dx; Coordinate dy; Coordinate dz; }Vector; Giôùi thieäu veà ñoà hoïa 3 chieàu 3/8 ÑOÀ HOÏA MAÙY TÍNH Ñoaïn thaúng trong khoâng gian 3 chieàu • Bieåu dieãn toå hôïp tuyeán tính cuûa 2 ñieåm. ♦ Bieåu dieãn daïng tham soá cuûa ñoaïn thaúng P = P1 + t (P2 - P1 ), (0 ≤ t ≤ 1) typedef struct { Point P1; Point P2; }Segment; P2 P1 Tia (Ray) • Laø moät ñoaïn thaúng vôùi moät ñaàu naèm ôû voâ cöïc. ♦ Bieåu dieãn daïng tham soá cuûa tia P = P1 + t V, (0 ≤ t < ∞) typedef struct { Point P1; Vector V; }Ray; P V Ñöôøng thaúng (Line) • Laø moät ñoaïn thaúng vôùi caû hai ñaàu naèm ôû voâ cöïc. ♦ Bieåu dieãn daïng tham soá cuûa ñöôøng thaúng P = P1 + t V, (-∞ < t < ∞) typedef struct { Point P1; Vector V; }Line; Döông Anh Ñöùc, Leâ Ñình Duy P V Giôùi thieäu veà ñoà hoïa 3 chieàu 4/8 ÑOÀ HOÏA MAÙY TÍNH Maët phaúng (Plane) • Laø moät ñoaïn thaúng vôùi caû hai ñaàu naèm ôû voâ cöïc. ♦ Bieåu dieãn cuûa maët phaúng P.N + d = 0 hoaëc ax + by + cz + d = 0 typedef struct { Vector N; Distance d; }Plane; Ña giaùc (Polygon) • Laø moät vuøng giôùi haïn bôûi daõy caùc ñieåm ñoàng phaúng. ♦ Tam giaùc, ♦ Töù giaùc, ♦ Ña giaùc loài, ♦ Ña giaùc loõm, ♦ Ña giaùc töï caét, ♦ Ña giaùc coù loã typedef struct { Point *Points; int nPoints; }Polygon; ♦ Caùc ñieåm ñöôïc cho theo thöù töï ngöôïc chieàu kim ñoàng hoà Döông Anh Ñöùc, Leâ Ñình Duy Giôùi thieäu veà ñoà hoïa 3 chieàu 5/8 ÑOÀ HOÏA MAÙY TÍNH Modeling transformation • Bieán ñoåi töø Heä toïa ñoä ñoái töôïng sang Heä toïa ñoä theá giôùi thöïc. • Moãi ñoái töôïng ñöôïc moâ taû trong moät heä toïa ñoä rieâng ñöôïc goïi laø Heä toïa ñoä ñoái töôïng. z 5 10 4 9 3 8 1 6 2 1 x 1 7 1 y • Coù hai caùch moâ hình hoùa ñoái töôïng : ♦ Solid modeling: moâ taû caùc vaät theå (keå caû beân trong) ♦ Boudary representation: chæ quan taâm ñeán beà maët ñ/tg • Caùc ñoái töôïng coù theå ñöôïc bieåu dieãn baèng moâ hình WireFrame • Nhaän xeùt ♦ Khi bieåu dieãn ñoái töôïng, ta coù theå choïn goác toïa ñoä vaø ñôn vò ño löôøng sao cho vieäc bieåu dieãn thuaän lôïi nhaát. Thöôøng thì ngöôøi ta chuaån hoùa kích thöôùc cuûa ñoái töôïng khi bieåu dieãn. ♦ Boudary representation cho pheùp xöû lyù nhanh coøn silid modeling cho hình aûnh ñaày ñuû vaø xaùc thöïc hôn. Döông Anh Ñöùc, Leâ Ñình Duy Giôùi thieäu veà ñoà hoïa 3 chieàu 6/8 ÑOÀ HOÏA MAÙY TÍNH Trivial Rejection • Loaïi boû caùc ñoái töôïng hoaøn toaøn khoâng theå nhìn thaáy trong caûnh. • Thao taùc naøy giuùp ta löôïc boû bôùt caùc ñoåi töôïng khoâng caàn thieát hieån thò giaûm chi phí xöû lyù. Illumination • Gaùn cho caùc ñoái töôïng maøu saéc döïa treân caùc ñaëc tính cuûa caùc chaát taïo neân chuùng vaø caùc nguoàn saùng toàn taïi trong caûnh. • Coù nhieàu moâ hình chieáu saùng vaø taïo boùng : constantintensity, interpolate (Gouraud), phong, …. Viewing transformation • Thöïc hieän moät pheùp bieán ñoåi heä toïa ñoä ñeå ñaët vò trí quan saùt (viewing position) veà goác toïa ñoä vaø maët phaúng quan saùt (viewing plane) veà moät vò trí mong öôùc. • Hình aûnh hieån thò phuï thuoäc vaøo vò trí quaùn saùt vaø goùc nhìn. • Heä qui chieáu coù goác ñaët taïi vò trí quan saùt vaø phuø hôïp vôùi höôùng nhìn seõ thuaän lôïi cho caùc xöû lyù nhaát. Döông Anh Ñöùc, Leâ Ñình Duy Giôùi thieäu veà ñoà hoïa 3 chieàu 7/8 ÑOÀ HOÏA MAÙY TÍNH Clipping • Thöïc hieän vieäc xeùn (clip) caùc ñoái töôïng trong caûnh ñeå caûnh naèm goïn trong moät phaàn khoâng gian hình choùp cuït giôùi haïn vuøng quan saùt maø ta goïi laø viewing frustum. • Viewing frustum coù truïc truøng vôùi tia nhìn, kích thöôùc y=top x=left y z VCS z=-near z=-far x y=bottom x=right giôùi haïn bôûi vuøng ta muoán quan saùt. Projection • Thöïc hieän vieäc chieáu caûnh 3 chieàu töø khoâng gian quan saùt xuoáng khoâng gian maøn hình. • Coù hai phöông phaùp chieáu: ♦ Chieáu song song ♦ Chieáu phoái caûnh • Khi chieáu ta phaûi tieán haønh vieäc khöû maët khuaát ñeå coù theå nhaän ñöôïc hình aûnh trung thöïc. • Khöû maët khuaát cho pheùp xaùc ñònh vò trí (x,y) treân maøn hình thuoäc veà ñoái töôïng naøo trong caûnh. Döông Anh Ñöùc, Leâ Ñình Duy Giôùi thieäu veà ñoà hoïa 3 chieàu 8/8 ÑOÀ HOÏA MAÙY TÍNH Caùc thuaät toaùn toâ maøu Daãn nhaäp • Moät vuøng toâ thöôøng ñöôïc xaùc ñònh bôûi moät ñöôøng kheùp kín naøo ñoù goïi laø ñöôøng bieân. Daïng ñöôøng bieân ñôn giaûn thöôøng gaëp laø ña giaùc. • Coù hai daïng vuøng toâ thöôøng gaëp : toâ baèng moät maøu thuaàn nhaát (solid fill) vaø toâ theo moät maãu toâ (fillpattern) naøo ñoù. • Vieäc toâ maøu thöôøng ñöôïc chia laøm hai coâng ñoaïn : ♦ Xaùc ñònh vò trí caùc ñieåm caàn toâ maøu. ♦ Quyeát ñònh toâ caùc ñieåm treân baèng maøu naøo. Coâng ñoaïn naøy thöïc söï phöùc taïp khi ta caàn toâ theo moät maãu toâ naøo ñoù chöù khoâng phaûi toâ thuaàn moät maøu. • Coù hai caùch tieáp caän chính : toâ maøu theo doøng queùt vaø toâ maøu döïa theo ñöôøng bieân. ♦ Phöông phaùp toâ maøu döïa theo doøng queùt seõ xaùc ñònh phaàn giao cuûa caùc doøng queùt keá tieáp nhau vôùi ñöôøng bieân cuûa vuøng toâ, sau ñoù seõ tieán haønh toâ maøu caùc ñieåm thuoäc phaàn giao naøy. Caùch naøy thöôøng ñöôïc duøng ñeå toâ maøu ña giaùc, ñöôøng troøn, ellipse vaø moät soá ñöôøng cong ñôn giaûn khaùc. ♦ Phöông phaùp toâ maøu döïa theo ñöôøng bieân seõ baét ñaàu töø moät ñieåm beân trong vuøng toâ vaø töø ñoù loang daàn ra cho ñeán khi gaëp ñieåm bieân. Caùch naøy thöôøng ñöôïc duøng cho caùc daïng ñöôøng bieân phöùc taïp. Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 1/16 ÑOÀ HOÏA MAÙY TÍNH Thuaät toaùn toâ theo doøng queùt Baøi toaùn ñaët ra : Caàn toâ maøu moät ña giaùc cho bôûi N ñænh Pi (x i , y i ), i = 0,... N − 1 . Ña giaùc naøy coù theå laø ña giaùc loài, ña giaùc loõm, vaø caû ña giaùc töï caét, … Toùm taét caùc böôùc chính cuûa thuaät toaùn • Tìm y top , ybottom laàn löôït laø giaù trò lôùn nhaát, nhoû nhaát cuûa taäp caùc tung ñoä cuûa caùc ñænh cuûa ña giaùc ñaõ cho: y top = max {y i , (x i , y i ) ∈ P} , ybottom = min{yi , (x i , yi ) ∈ P} . • ÖÙng vôùi moãi doøng queùt y = k , vôùi k thay ñoåi töø ybottom ñeán y top , laëp : ♦ Tìm taát caû caùc hoaønh ñoä giao ñieåm cuûa doøng queùt y = k vôùi caùc caïnh cuûa ña giaùc. ♦ Saép xeáp caùc hoaønh ñoä giao ñieåm theo thöù töï taêng daàn : x0 , x1 , x2 ,..., ♦ Toâ maøu caùc ñoaïn thaúng treân ñöôøng thaúng y = k laàn löôït ñöôïc giôùi haïn bôûi caùc caëp (x 0 , x1 ), (x1 , x 2 ),..., (x 2 k , x 2 k +1 ) . y ytop 0 1 2 3 ybottom O Döông Anh Ñöùc, Leâ Ñình Duy x Caùc thuaät toaùn toâ maøu 2/16 ÑOÀ HOÏA MAÙY TÍNH Caùc vaán ñeà ñaët ra • Haïn cheá ñöôïc soá caïnh caàn tìm giao ñieåm öùng vôùi moãi doøng queùt vì öùng vôùi moãi doøng queùt, khoâng phaûi luùc naøo taát caû caùc caïnh cuûa ña giaùc cuõng tham gia caét doøng queùt. • Xaùc ñònh nhanh hoaønh ñoä giao ñieåm vì neáu laëp laïi thao taùc tìm giao ñieåm cuûa caïnh ña giaùc vôùi moãi doøng queùt baèng caùch giaûi heä phöông trình seõ toán raát nhieàu thôøi gian. • Giaûi quyeát tröôøng hôïp soá giao ñieåm öùng vôùi tröôøng hôïp doøng queùt ñi ngang qua ñænh : Neáu soá giao ñieåm tìm ñöôïc giöõa caùc caïnh ña giaùc vaø doøng queùt laø leû thì vieäc nhoùm töøng caëp giao ñieåm keá tieáp nhau ñeå hình thaønh caùc ñoaïn toâ coù theå seõ khoâng chính xaùc. Ñieàu naøy chæ xaûy ra khi doøng queùt ñi ngang qua caùc ñænh cuûa ña giaùc. • Ngoaøi ra, vieäc tìm giao ñieåm cuûa doøng queùt vôùi caùc caïnh naèm ngang laø moät tröôøng hôïp ñaëc bieät caàn phaûi coù caùch xöû lí thích hôïp y=k2 0 1,2 3 y=k1 0 Döông Anh Ñöùc, Leâ Ñình Duy 1,2 3 4 Caùc thuaät toaùn toâ maøu 3/16 ÑOÀ HOÏA MAÙY TÍNH Toå chöùc caáu truùc döõ lieäu vaø thuaät toaùn • Danh saùch caùc caïnh (Edge Table – ET) : chöùa toaøn boä caùc caïnh cuûa ña giaùc (ñaõ loaïi ñi caùc caïnh naèm ngang) ñöôïc saép theo thöù töï taêng daàn cuûa y Min . • Danh saùch caùc caïnh kích hoaït (Active Edge Table – AET) : chöùa caùc caïnh cuûa ña giaùc coù theå caét öùng vôùi doøng queùt hieän haønh, caùc caïnh naøy ñöôïc saép theo thöù töï taêng daàn cuûa hoaønh ñoä giao ñieåm giöõa caïnh vaø doøng queùt. • Khi doøng queùt ñi töø bottom ñeán top, caùc caïnh thoûa ñieàu kieän seõ ñöôïc di chuyeån töø ET sang AET: ♦ Khi doøng queùt y = k baét ñaàu caét moät caïnh, nghóa laø k ≥ y Min , caïnh naøy seõ ñöôïc chuyeån töø ET sang AET. ♦ Khi doøng queùt khoâng coøn caét caïnh naøy nöõa, nghóa laø k > yMax , caïnh naøy seõ bò loaïi ra khoûi AET. ♦ Khi khoâng coøn caïnh naøo trong ET hay AET nöõa, quaù trình toâ maøu keát thuùc. • Ñeå tìm giao ñieåm giöõa caïnh ña giaùc vaø doøng queùt hieän haønh nhanh, ta coù nhaän xeùt : x k +1 − x k = 1 ((k + 1) − k) = 1 hay x k+1 = x k + 1 . m m m y=k+1 xk+1 y=k xk Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 4/16 ÑOÀ HOÏA MAÙY TÍNH Ñeà xuaát caáu truùc döõ lieäu cuûa moät caïnh (EDGE) deltaY y=k xIntersect yMin • y Min : giaù trò tung ñoä nhoû nhaát trong 2 ñænh cuûa caïnh. • xInter sec t : hoaønh ñoä giao ñieåm cuûa caïnh vôùi doøng queùt hieän haønh. • DxPerScan : giaù trò 1/m (m laø heä soá goùc cuûa caïnh). • deltaY : khoaûng caùch töø doøng queùt hieän haønh tôùi ñænh y Max . Luùc deltaY ≤ 0 . naøy ñieàu kieän k > yMax trôû thaønh • Giaù trò xInter sec t ñöôïc khôûi gaùn ban ñaàu laø hoaønh ñoä cuûa ñænh coù tung ñoä laø y Min , vaø giaù trò deltaY ñöôïc khôûi gaùn ban ñaàu laø y Max − y Min + 1 . Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 5/16