Đồ hoạ máy tính - Các thuật toán tô màu

ù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 ky = baét ñaàu caét moät caïnh, nghóa laø Minyk ≥ , 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ø Maxyk > , 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 : ( )( ) m kk m xx kk 1111 =−+=−+ hay m xx kk 1 1 +=+ . y=k+1 y=k xk xk+1 ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 5/16 Ñeàà xuaáát caááu truùùc döõõ lieääu cuûûa moäät caïïnh (EDGE) • Miny : giaù trò tung ñoä nhoû nhaát trong 2 ñænh cuûa caïnh. • txInter sec : 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 Maxy . Luùc naøy ñieàu kieän Maxyk > trôû thaønh 0≤deltaY . • Giaù trò txInter sec ñöôïc khôûi gaùn ban ñaàu laø hoaønh ñoä cuûa ñænh coù tung ñoä laø Miny , vaø giaù trò deltaY ñöôïc khôûi gaùn ban ñaàu laø 1+− MinMax yy . yMin xIntersect y=k deltaY ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 6/16 Giaûûi quyeáát tröôøøng hôïïp doøøng queùùt ñi qua ñænh • Tính moät giao ñieåm neáu chieàu cuûa hai caïnh keà cuûa ñænh ñoù coù xu höôùng taêng hay giaûm. • Tính hai giao ñieåm neáu chieàu cuûa hai caïnh keà cuûa ñænh ñoù coù xu höôùng thay ñoåi, nghóa laø taêng-giaûm hay giaûm-taêng. • Khi caøi ñaët ñeå khoûi phaûi xeùt ñieàu kieän naøy cho phöùc taïp, khi xaây döïng döõ lieäu cho moãi caïnh tröôùc khi ñöa vaøo ET, ngöôøi ta seõ xöû lí caùc caïnh coù ñænh tính hai giao ñieåm baèng caùch loaïi ñi moät pixel treân cuøng cuûa moät trong hai caïnh. (a) (b) Pi Pi-1 Pi+1 Pi Pi-1 Pi+1 Pi-1 Pi-1Pi+1 Pi+1 Pi Pi y=k Pi-1 Pi Pi+1 y=k-1 Pi+1 y=k Pi+1 Pi Pi-1 y=k-1 Pi-1 Pi* Pi* Pi-1 Pi+1 ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 7/16 Minh hoïïa thuaäät toaùùn • Ban ñaàu : ♦ ET : AB*, AI, H*G, BC, G*F, DC, EF. (loaïi IH vaø DE) ♦ AET : NULL. • Khi doøng queùt ñaït y=yA ♦ ET : H*G, BC, G*F, DC, EF. (chuyeån AB*, AI sang AET) ♦ AET : AB*, AI. • Khi doøng queùt ñaït y=yH* ♦ ET : BC, G*F, DC, EF. (chuyeån H*G sang AET) ♦ AET : AB*, H*G. (loaïi AI vì khoâng coøn caét doøng queùt) Top F ED C B G HI A Bottom yB yG*=yG+1 yB*=yB-1 yG yH*=yH+1 yH ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 8/16 • Khi doøng queùt ñaït y=yB ♦ ET : G*F, DC, EF. (chuyeån BC sang AET) ♦ AET : BC, H*G. (loaïi AB*, saép xeáp laïi H*G vaø BC) • Khi doøng queùt ñaït y=yG* ♦ ET : DC, EF. (chuyeån G*F sang AET) ♦ AET : BC, G*F. (loaïi H*G vì khoâng coøn caét doøng queùt) • Khi doøng queùt ñaït y=yD ♦ ET : NULL. (chuyeån DC, EF sang AET) ♦ AET : BC, DC, EF, G*F. (saép xeáp laïi BC, GF*, DC, EF) • Khi doøng queùt ñaït y=yC+1 ♦ ET : NULL. ♦ AET : EF, G*F. (loaïi BC, DC vì khoâng coøn caét doøng queùt) • Khi doøng queùt ñaït y=yF+1 ♦ ET : NULL. ♦ AET : NULL. (loaïi EF, G*F vì khoâng coøn caét doøng queùt). • Thuaät toaùn döøng taïi ñaây. ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 9/16 Löu ñoà thuaät toaùn toâ maøu theo doøng queùt Begin Taïo danh saùch taát caû caùc caïnh ET i<TopScan i=BottomScan Yes No Caäp nhaät danh saùch caùc caïnh kích hoaït AET Tìm hoaønh ñoä giao ñieåm vaø saép xeáp theo thöù töï taêng daàn Toâ maøu caùc ñoaïn giao ñöôïc taïo bôûi töøng caëp hoaønh ñoä keá tieáp nhau Caäp nhaät laïi thoâng tin cuûa caùc caïnh ñeå söû duïng cho doøng queùt keá tieáp i=i+1 End ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 10/16 Moäät soáá höôùùng daããn caøøi ñaëët #define MAXVERTEX 20 #define MAXEDGE 20 #define TRUE 1 #define FALSE 0 typedef struct { int x; int y; }POINT; typedef struct{ int NumVertex; POINT aVertex[MAXVERTEX]; }POLYGON; typedef struct { int NumPt; float xPt[MAXEDGE]; }XINTERSECT; typedef struct { int yMin; // Gia tri y nho nhat cua 2 dinh float xIntersect; // Hoanh do giao diem cua canh & dong quet float dxPerScan; // Gia tri 1/m int DeltaY; }EDGE; typedef struct { int NumEdge; EDGE aEdge[MAXEDGE]; }EDGELIST; ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 11/16 void PutEdgeInList(EDGELIST &EdgeList, POINT p1, POINT p2, int NextY) { EDGE EdgeTmp; EdgeTmp.dxPerScan = float(p2.x-p1.x)/(p2.y-p1.y); // 1/m if(p1.y < p2.y) { /* Truong hop dong quet di ngang qua dinh la giao diem cua 2 canh co huong y cung tang */ if(p2.y < NextY) { p2.y--; p2.x -= EdgeTmp.dxPerScan; } EdgeTmp.yMin = p1.y; EdgeTmp.xIntersect= p1.x; EdgeTmp.DeltaY = abs(p2.y-p1.y)+1; } // if else { /* Truong hop dong quet di ngang qua dinh la giao diem cua 2 canh co huong y cung giam */ if(p2.y > NextY) { p2.y++; p2.x+= EdgeTmp.dxPerScan; } EdgeTmp.yMin = p2.y; EdgeTmp.xIntersect= p2.x; EdgeTmp.DeltaY = abs(p2.y-p1.y)+1; }//else // xac dinh vi tri chen int j = EdgeList.NumEdge; while((j>0) && (EdgeList.aEdge[j-1].yMin>EdgeTmp.yMin)) { EdgeList.aEdge[j] = EdgeList.aEdge[j-1]; j--; } // tien hanh chen dinh moi vao canh EdgeList.NumEdge++; EdgeList.aEdge[j] = EdgeTmp; } // PutEdgeInList ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 12/16 /* Tim dinh ke tiep sao cho khong nam tren cung duong thang voi dinh dang xet */ int FindNextY(POLYGON P, int id) { int j = (id+1)%P.NumVertex; while((j<P.NumVertex)&&(P.aVertex[id].y == P.aVertex[j].y)) j++; if(j<P.NumVertex) return (P.aVertex[j].y); return 0; } // FindNextY // Tao danh sach cac canh tu polygon da cho void MakeSortedEdge(POLYGON P, EDGELIST &EdgeList, int &TopScan, int &BottomScan) { TopScan = BottomScan = P.aVertex[0].y; EdgeList.NumEdge = 0; for(int i=0; i<P.NumVertex; i++) { // Truong hop canh khong phai la canh nam ngang if(P.aVertex[i].y != P.aVertex[i+1].y) PutEdgeInList(EdgeList, P.aVertex[i], P.aVertex[i+1], FindNextY(P, i+1)); // Xu li truong hop canh nam ngang else if(P.aVertex[i+1].y > TopScan) TopScan = P.aVertex[i+1].y; } BottomScan = EdgeList.aEdge[0].yMin; } //MakeSortedEdge // Cap nhat lai hai con tro FirstId, LastId cho biet danhsach cac canh active void UpdateActiveEdgeList(EDGELIST EdgeList, int yScan, int &FirstId, int &LastId) { while((FirstId<EdgeList.NumEdge-1) &&(EdgeList.aEdge[FirstId].DeltaY == 0)) FirstId++; while((LastId<EdgeList.NumEdge-1) &&(EdgeList.aEdge[LastId+1].yMin<=yScan)) LastId++; } // UpdateActiveEdgeList ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 13/16 Thuaäät toaùùn toââ maøøu theo ñöôøøng bieâân • Baøi toaùn ñaët ra : Caàn toâ maøu vuøng toâ neáu bieát ñöôïc maøu cuûa ñöôøng bieân vuøng toâ vaø moät ñieåm naèm beân trong vuøng toâ. • Yù töôûng : Baét ñaàu töø ñieåm naèm beân trong vuøng toâ, kieåm tra caùc ñieåm laân caän cuûa noù ñaõ ñöôïc toâ hay coù phaûi laø ñieåm coù maøu truøng maøu bieân hay khoâng, neáu khoâng phaûi thì ta seõ toâ ñieåm ñoù. Quaù trình naøy ñöôïc laëp laïi cho tôùi khi khoâng coøn toâ ñöôïc nöõa thì döøng. ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 14/16 • Coù hai quan ñieåm veà caùch toâ naøy, ñoù laø duøng 4 ñieåm laân caän (hình a) hay 8 ñieåm laân caän (hình b). • Caøi ñaët minh hoïa thuaät toaùn toâ maøu theo ñöôøng bieân void BoundaryFill(int x, int y, int FillColor, int BoundaryColor) { int CurrenColor; CurrentColor = getpixel(x,y); if((CurrentColor!=BoundaryColor)&&CurrentColor!= FillColor)) { putpixel(x,y,FillColor); BoundaryFill(x-1, y, FillColor, BoundaryColor); BoundaryFill(x, y+1, FillColor, BoundaryColor); BoundaryFill(x+1, y, FillColor, BoundaryColor); BoundaryFill(x, y-1, FillColor, BoundaryColor); } } // Boundary Fill • Moät soá nhaän xeùt ♦ Thuaät toaùn coù theå hoaït ñoäng khoâng chính xaùc khi coù moät soá ñieåm naèm trong vuøng toâ coù maøu laø maøu caàn toâ cuûa vuøng. ♦ Vieäc thöïc hieän ñeä qui laøm thuaät toaùn khoâng theå duøng cho vuøng toâ lôùn. (a) (b) ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 15/16 • Moät caûi tieán nhoû : nhaän xeùt raèng vieäc goïi thöïc hieän ñeä qui thuaät toaùn cho 4 ñieåm laân caän cuûa ñieåm hieän haønh khoâng quan taâm tôùi moät trong 4 ñieåm ñoù ñaõ ñöôïc xeùt ôû böôùc tröôùc hay chöa. Ví duï khi ta xeùt 4 ñieåm laân caän cuûa (x, y), thì khi goïi thöïc hieän ñeä qui vôùi ñieåm hieän haønh laø moät trong 4 ñieåm treân, (x, y) vaãn ñöôïc xem laø ñieåm laân caän cuûa chuùng vaø ñöôïc goïi thöïc hieän laïi. void BoundaryFillEnhanced(int x, int y, int F_Color, int B_Color) { int CurrenColor; CurrentColor = getpixel(x,y); if((CurrentColor!=B_Color)&&CurrentColor!= F_Color)) { putpixel(x,y,F_Color); FillLeft(x-1, y, F_Color, B_Color); FillTop(x, y+1, F_Color, B_Color); FillRight(x+1, y, F_Color, B_Color); FillBottom(x, y-1, F_Color, B_Color); } } // BoundaryFillEnhanced void FillLeft(int x, int y, int F_Color, int B_Color) { int CurrenColor; CurrentColor = getpixel(x,y); if((CurrentColor!=B_Color)&&CurrentColor!= F_Color)) { putpixel(x,y,F_Color); FillLeft(x-1, y, F_Color, B_Color); FillTop(x, y+1, F_Color, B_Color); FillBottom(x, y-1, F_Color, B_Color); } } // FillLeft ÑOÀ HOÏA MAÙY TÍNH Döông Anh Ñöùc, Leâ Ñình Duy Caùc thuaät toaùn toâ maøu 16/16 • Moät caûi tieán khaùc : khoâng caøi ñaët ñeä qui maø toâ theo töøng doøng.