Các đối tượng đồ họa cơ sở

Thuật toán tô màu dựa theo dòng quét

Giả sử vùng tô được cho bởi một đa giác N đỉnh : . Đa giác này có thể là đa giác lồi, đa giác lõm, và cả đa giác tự cắt, …

Hình 2.18 sau minh họa ý tưởng chính của thuật toán. Với mỗi dòng quét, ta sẽ xác định phần giao của đa giác và dòng quét rồi tô màu các pixel thuộc đoạn giao đó. Để xác định các đoạn giao ta tiến hành việc tìm giao điểm của dòng quét với các cạnh của đa giác, sau đó các giao điểm này sẽ được sắp theo thứ tự tăng dần của hoành độ giao điểm. Các đoạn giao chính là các đoạn thẳng được giới hạn bởi từng cặp giao điểm một, ví dụ như (0,1), (2,3), ….

Hình 2.18 – Thuật toán scan-line với một dòng quét nào đó

Ta có thể tóm bắt các bước chính của thuật toán :

• Tìm , lần lượt là giá trị lớn nhất, nhỏ nhất của tập các tung độ của các đỉnh của đa giác đã cho , .
• Ứng với mỗi dòng quét , với k thay đổi từ đến , lặp :

• Tìm tất cả các hoành độ giao điểm của dòng quét với các cạnh của đa giác.
• Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x₀, x₁, …
• Tô màu các đoạn thẳng trên đường thẳng lần lượt được giới hạn bởi các cặp .

Nếu chỉ dừng ở mức này và chuyển sang cài đặt, chúng ta sẽ gặp một số vấn đề sau :

• Nhận xét rằng, ứng với mỗi dòng quét, không phải lúc nào tất cả các cạnh của đa giác cũng tham gia cắt dòng quét. Do đó để cải thiện tốc độ cần phải có một cách nào đó để hạn chế được số cạnh cần tìm giao điểm ứng với mỗi dòng quét.
• Việc tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ gặp các phép toán phức tạp như nhân, chia, … trên số thực nếu ta dùng cách giải hệ phương trình tìm giao điểm. Điều này sẽ làm giảm tốc độ thuật toán khi phải lặp đi lặp lại nhiều lần thao tác này khi dòng quét quét qua đa giác.
• Nếu số giao điểm tìm được giữa các cạnh đa giác và dòng quét là lẻ thì việc nhóm từng cặp giao điểm kế tiếp nhau để hình thành các đoạn tô có thể sẽ không chính xác. Điều này chỉ xảy ra khi dòng quét đi ngang qua các đỉnh của đa giác. Nếu tính số giao điểm tại đỉnh dòng quét đi ngang qua là hai thì có thể sẽ cho kết quả tô không chính xác như trong trường hợp của hình 2.19. Ngoài ra, việc tìm giao điểm của dòng quét với các cạnh nằm ngang là một trường hợp đặc biệt cần phải có cách xử lí thích hợp.

Để giải quyết các vấn đề trên, cần phải xây dựng một cấu trúc dữ liệu và thuật toán thích hợp đối với chúng.

Hình 2.19 – Dòng quét y=k₂ đi ngang qua đỉnh có thể sẽ cho kết quả tô không chính xác so với dòng quét y=k₁

Danh sách các cạnh kích hoạt AET (Active Edge Table)

Để hạn chế số cạnh cần tìm giao điểm ứng với mỗi dòng quét, ta xây dựng một số cấu trúc dữ liệu như sau :

Cạnh đa giác (EDGE)

Mỗi cạnh của đa giác được xây dựng từ hai đỉnh kề nhau và gồm các thông tin sau :

• : giá trị tung độ nhỏ nhất trong 2 đỉnh của cạnh.
• xIntersect : hoành độ giao điểm của cạnh với dòng quét hiện đang xét.
• DxPerScan : giá trị 1/m (m là hệ số góc của cạnh).
• deltaY : khoảng cách từ dòng quét hiện hành tới đỉnh .

Danh sách các cạnh kích hoạt AET

Danh sách này dùng để lưu các tập cạnh của đa giác có thể cắt ứng với dòng quét hiện hành và tập các điểm giao tương ứng. Nó có một số đặc điểm :

• Các cạnh trong danh sách được sắp theo thứ tự tăng dần của các hoành độ giao điểm để có thể tô màu các đoạn giao một cách dễ dàng.
• Thay đổi ứng với mỗi dòng quét đang xét, do đó danh sách này sẽ được cập nhật liên tục trong quá trình thực hiện thuật toán. Để hỗ trợ cho thao tác này, đầu tiên người ta sẽ tổ chức một danh sách chứa toàn bộ các cạnh của đa giác gọi là ET (Edge Table) được sắp theo thứ tự tăng dần của , rồi sau mỗi lần dòng quét thay đổi sẽ di chuyển các cạnh trong ET thỏa điều kiện sang AET.
• Một dòng quét chỉ cắt một cạnh của đa giác khi và chỉ khi . Chính vì vậy mà với cách tổ chức của ET (sắp theo thứ tự tăng dần của ) điều kiện để chuyển các cạnh từ ET sang AET sẽ là ; và điều kiện để loại một cạnh ra khỏi AET là .

Hình 2.20 – Thông tin của một cạnh

Công thức tìm giao điểm nhanh

Nếu gọi , lần lượt là các hoành độ giao điểm của một cạnh nào đó với các dòng quét và , ta có :

hay .

Như vậy nếu lưu hoành độ giao điểm ứng với dòng quét trước lại, cùng với hệ số góc của cạnh, ta có thể dễ dàng xác định hoành độ giao điểm ứng với dòng quét kế tiếp một cách đơn giản theo công thức trên. Điều này rút gọn đáng kể thao tác tìm giao điểm của cạnh ứng với dòng quét. Chính vì vậy mà trong thông tin của một cạnh chúng ta có hai biến DxPerScan và xIntersect.

Hình 2.21 – Công thức tìm giao điểm nhanh

Giải quyết trường hợp dòng quét đi ngang qua đỉnh

Người ta đưa ra quy tắc sau để tính số giao điểm khi dòng quét đi ngang qua đỉnh :

• Tính một giao điểm nếu chiều của hai cạnh kề của đỉnh đó có xu hướng tăng hay giảm.
• Tính hai giao điểm nếu chiều của hai cạnh kề của đỉnh đó có xu hướng thay đổi, nghĩa là tăng-giảm hay giảm-tăng.

Hình 2.22 – Quy tắc tính một giao điểm (a) và hai giao điểm (b)

Khi cài đặt để khỏi phải xét điều kiện này cho phức tạp, khi xây dựng dữ liệu cho mỗi cạnh trước khi đưa vào ET, người ta sẽ xử lí các cạnh có đỉnh tính hai giao điểm bằng cách loại đi một pixel trên cùng của một trong hai cạnh như hình 2.23 :

Hình 2.23 – Cạnh được lưu trong ET chỉ là

Cài đặt minh họa sau sử dụng chung một danh sách EDGELIST cho cả ET và AET. AET được quản lí nhờ vào hai con trỏ FirstId và LastId.

Cài đặt minh họa thuật toán tô màu scan-line

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<graphics.h>

#include<dos.h>

#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;

/*

Dat 1 canh vao danh sach canh.

Cac canh duoc sap theo thu tu giam dan cua yMin (yMin la gia tri y lon nhat cua 2 dinh 1 canh)

Xu li luon truong hop dong quet di ngang qua dinh ma tai do chi tinh 1 diem giao

*/

voidPutEdgeInList(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

/*

Tim dinh ke tiep sao cho khong nam tren cung duong thang voi dinh dang xet

*/

intFindNextY(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

voidMakeSortedEdge(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));

//else Xu li truong hop canh nam ngang

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

voidUpdateActiveEdgeList(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

voidSortOnX(XINTERSECT & aIntersectPt)

{

for(int i=0; i<aIntersectPt.NumPt-1; i++)

{

int Min = i, t;

for(int j=i+1; j<aIntersectPt.NumPt; j++)

if( aIntersectPt.xPt[j]< aIntersectPt.xPt[Min])

Min = j;

t = aIntersectPt.xPt[Min];

aIntersectPt.xPt[Min]= aIntersectPt.xPt[i];

aIntersectPt.xPt[i]= t;

}

} // SortOnX

/*

Tim cac hoanh do giao diem cua cac canh cua da giac voi dong quet yScan. Sau khi tim cac hoanh do giao diem, ta sap xep lai theo chieu tang cua x

*/

voidFindXIntersection(EDGELIST EdgeList, XINTERSECT &aIntersectPt,int FirstId,int LastId)

{

aIntersectPt.NumPt = 0;

for(int i=FirstId; i<=LastId; i++)

{

if(EdgeList.aEdge[i].DeltaY>0)

{

aIntersectPt.xPt[aIntersectPt.NumPt]= EdgeList.aEdge[i].xIntersect;

aIntersectPt.NumPt++;

}

}

SortOnX(aIntersectPt);

} //FindXIntersection

#define Round(x)int(x+0.5)

voidFillLine(XINTERSECT aIntersectPt,int yScan)

{

for(int i=0; i<aIntersectPt.NumPt; i+=2)

line(Round(aIntersectPt.xPt[i]), yScan, Round(aIntersectPt.xPt[i+1]), yScan);

} // FillLine

voidUpdateEdgeList(EDGELIST &EdgeList,int FirstId,int LastId)

{

for(int i=FirstId; i<=LastId; i++)

{

if(EdgeList.aEdge[i].DeltaY>0)

{

EdgeList.aEdge[i].DeltaY--;

EdgeList.aEdge[i].xIntersect += EdgeList.aEdge[i].dxPerScan;

}

}

} //FillLine

void ScanLineFill(POLYGON P)

{

EDGELIST EdgeList;

XINTERSECT aIntersectPt;

int TopScan, BottomScan, FirstId, LastId;

MakeSortedEdge(P, EdgeList, TopScan, BottomScan);

FirstId = LastId = 0;

for(int i=BottomScan; i<=TopScan; i++)

{

// Cap nhat lai danh sach cac canh active - tuc la cac canh cat dong quet i

UpdateActiveEdgeList(EdgeList, i, FirstId, LastId);

// Tim cac hoanh do giao diem cua dong quet voi cac canh cua da giac va sap xep lai cac hoanh do giao diem truc tiep tren EdgeList

FindXIntersection(EdgeList, aIntersectPt, FirstId, LastId);

FillLine(aIntersectPt, i);

UpdateEdgeList(EdgeList, FirstId, LastId);

}

} //ScanLineFill

Lưu đồ thuật toán tô màu theo dòng quét

Thuật toán tô màu dựa theo đường biên

Khác với thuật toán tô màu dựa theo dòng quét, đường biên của vùng tô được xác định bởi tập các đỉnh của một đa giác, đường biên trong thuật toán được mô tả bằng một giá trị duy nhất đó là màu của tất cả các điểm thuộc về đường biên.

Bắt đầu từ điểm nằm bên trong vùng tô, ta sẽ kiểm tra các điểm lân cận của nó đã được tô màu hay có phải là điểm biên hay không, nếu không phải là điểm đã tô và không phải là điểm biên ta sẽ tô màu nó. Quá trình này được lặp lại cho tới khi nào không còn tô được điểm nào nữa thì dừng. Bằng cách này, toàn bộ các điểm thuộc vùng tô được kiểm tra và sẽ được tô hết.

Hình 2.24 – Thuật toán tô màu dựa theo đường biên

Có hai quan điểm về cách tô này, đó là dùng bốn điểm lân cận hay tám điểm lân cận đối với điểm đang xét được tô bằng màu trắng (xem hình 2.25).

Hình 2.25 – 4 điểm lân cận (a) và 8 điểm lân cận (b)

Đoạn chương trình sau minh họa cài đặt thuật toán tô màu dựa theo đường biên sử dụng phương pháp tô 4 điểm lân cận.

Cài đặt minh họa thuật toán tô màu dựa theo đường biên

voidBoundaryFill(int x,int y,int FillColor,int BoundaryColor)

{

int CurrentColor;

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

Nhận xét

• Thuật toán này có thể sẽ không hoạt động chính xác khi có một số điểm nằm trong vùng tô có màu là màu cần tô của vùng (FillColor). Để khắc phục điều này, trước khi tô màu cần phải đảm bảo rằng toàn bộ các điểm thuộc về vùng tô có màu khác màu tô.
• Nhận xét rằng trong cài đặt thuật toán ở trên, việc gọi thực hiện đệ quy thuật toán cho bốn điểm lân cận của điểm hiện hành không quan tâm tới một trong bốn điểm đó đã được xét ở bước trước hay chưa. Ví dụ khi ta xét bốn điểm lân cận của điểm hiện hành (x,y), thì khi gọi thực hiện đệ quy với điểm hiện hành là một trong bốn điểm lân cận trên, (x,y) vẫn được xem là điểm lân cận của chúng và lại được gọi thực hiện lại. Ta sẽ đưa ra một cải tiến nhỏ để khắc phục điểm này, bằng cách mỗi lần xét điểm hiện hành (x,y) ta sẽ gọi 4 thủ tục riêng để tô các điểm lân cận và trong 4 thủ tục này ta sẽ tránh gọi lại việc xét điểm (x,y).

voidBoundaryFillEnhanced(int x,int y,int F_Color,int B_Color)

{

int CurrentColor;

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

voidFillLeft(int x,int y,int F_Color,int B_Color)

{

int CurrentColor;

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

voidFillTop(int x,int y,int F_Color,int B_Color)

{

int CurrentColor;

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);

}

} // FillTop

voidFillRight(int x,int y,int F_Color,int B_Color)

{

int CurrentColor;

CurrentColor = getpixel(x,y);

if((CurrentColor!=B_Color)&&CurrentColor!= F_Color))

{

putpixel(x,y,F_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);

}

} // FillRight

voidFillBottom(int x,int y,int F_Color,int B_Color)

{

int CurrentColor;

CurrentColor = getpixel(x,y);

if((CurrentColor!=B_Color)&&CurrentColor!= F_Color))

{

putpixel(x,y,F_Color);

FillLeft(x-1, y, F_Color, B_Color);

FillRight(x+1, y, F_Color, B_Color);

FillBottom(x, y-1, F_Color, B_Color);

}

} // FillBottom

Thuật toán này có tính đệ quy, do đó khi cài đặt thường gây lỗi tràn bộ nhớ khi vùng tô khá lớn, do đó để cải tiến chúng ta sẽ tiến hành loang dần và lần lượt tô từng đoạn giao theo dòng quét ngang thay vì tô theo 4 điểm lân cận. Như vậy chúng ta chỉ cần lưu lại thông tin của điểm bắt đầu mỗi đoạn giao của dòng quét ngang thay vì phải lưu hết tất cả các điểm lân cận chưa được tô của điểm hiện hành. Chúng ta sẽ cho các dòng quét loang từ điểm bắt đầu theo hướng lên biên trên, sau khi đã tô xong, các dòng quét còn lại theo hướng xuống biên dưới sẽ được tô. Ứng với mỗi dòng quét ngang, ta sẽ loang và tìm pixel trái nhất (có hoành độ nhỏ nhất) để lưu lại. Trong hình 2.26, đoạn giao đầu tiên chứa điểm bắt đầu (tô màu trắng) sẽ được tô trước. Sau đó các vị trí 1, 2 ứng với các đoạn giao của các dòng quét kế tiếp sẽ được lưu lại (hình 2.26a). Bước tiếp theo, điểm ứng với vị trí 2 sẽ được lấy ra và tiến hành tô màu bằng cách loang từ điểm này ra theo chiều ngang, sau đó pixel ứng vị trí 3 của dòng quét kế tiếp sẽ được lưu lại (hình 2.26b). Sau khi dòng quét ứng với điểm 3 đã được xử lí tương tự như trên xong, stack lưu các vị trí của các điểm “hạt giống” cho các dòng quét kế tiếp như trong hình 2.26c. Hình 2.26d minh họa khi thuật toán đã tô được toàn bộ một phần vùng phía trên bên phải của vùng tô. Khi pixel ứng với vị trí 5 được xử lí xong, ta có phần còn lại phía trên bên trái sẽ được tô. Sau đó pixel ứng với vị trí 4 sẽ được xử lí, các dòng quét phía dưới sẽ được tô tiếp theo.

Hình 2.26 – Thuật toán tô màu theo dòng quét cải tiến