Xử lý các trường hợp đặc biệt trong bài toán tô màu đa giác bằng thuật toán Scanline

Xử lý các trường hợp đặc biệt trong bài toán tô màu đa giác bằng 
thuật toán Scanline
Trong đồ họa máy tính có khá nhiều thuật toàn tô màu (Scanline, tô loang...) cho 1 vùng kín (đặc) như các đa giác, các đường tròn... Xong mỗi thuật toán lại tỏ ra có những ưu việt và hạn chế riêng đối với từng bài toán cụ thể. Với thuật toán tô màu theo dòng quét (Scanline), khi tô màu cho một vùng kín đôi khi cần phải xác định cho được các trường hợp đặc biệt của bài toán để sao cho kết quả trả về sẽ tô được những vùng cần thiết như mong muốn.
Song, trong thực tiễn để làm được điều này nhiều lúc cũng gặp phải khá nhiều khó khăn trong việc xử lý các trường hợp đặc biệt đó.Bài viết này nhằm xác định các trường hợp đặc biệt của bài toán tô màu đa giác cũng như cách xử lý chúng để cho kết quả tô chính xác bằng thuật toán Scanline.
I.Ý tưởng.
-Duyệt qua tất cả các đỉnh của đa giác để xác định YMAX,YMIN.
-Xác định các giao điểmcủa từng dòng quét với tất cả các cạnh của đa giác ( đường viền đa giác ) trong phạm vi YMAX, YMIN đó.
-Bật sáng các Pixel bên trong đa giác bằng cách di chuyển con trỏ giữa các giao điểm cho thích hợp.
II.Phân tích.
II.1.Hình minh họa các trường hợp đặc biệt.
II.2.Các trường hợp đặc biệt.
Ta cần xây dựng các thủ tục (TT) mà mỗi TT đó phải xử lý được một trường hợp đặc biệt của bài toán.
TH1: Dòng quét L1cắt đa giác một lần ,tạiđỉnhthấpnhấtcủa đa giác .Taphải xây dựng mộtTT bỏ qua dòng L1 ( còn đỉnh của đa giácnày tất nhiên sẽ được sáng cùng với đường viền của nó).
TH2: DòngL2cắtđa giáctại 2điểm ( trong đó có1 đỉnh) . Mọi Pixel nằm giữa B1, B2 sẽ được sáng lên ; giao điểm với đỉnh nàykhông được bỏ qua. Do đó phải xây dựng mộtTT có khả năng xác định được khi nào 1 giao điểm với đỉnh có thể hoặc không thể bỏ qua.
TH3: Dòng L3 cắt đa giáctại 3 điểm ; mọi Pixelgiữa C1 và C2 sẽ sáng lên nênTT sẽ bỏ qua điểm C’.
TH4: DòngL4trùngvớicạnhnằm ngang S . Mọi pixel giữa D1,D2 sẽ sáng lên .Phải xây dựng mộtTTcoi cạnh S là không tồn tại ( không bật sáng các Pixel nằm trên S) . Đồng thời các pixel giữa D2 và D3 sẽ không sáng lên và các Pixel giữa D3, D4 lại được sáng lên.
II.3.Chi tiết.
Kiểm tra tính chất các giao điểm
Để kiểm tra tính chất của một đường quét có cắt 1 cạnh không? Ta thực hiện việc so sánh tung độ của dòng quét (yscan) với tung độ y của các điểm mút của mỗi cạnh.
II..1.Nếu tung độ của 2 điểm mút đều lớn hơn hay nhỏ hơn YSCAN thì không cógiao điểm nào .
II.3.2.Nếu tung độ y của mỗi điểm mút bằng YSCAN thì giao điểm tại đỉnh đó.
II.3.3.Nếu tung độ của cả 2 điểm mút đều bằng YSCAN thì đó là cạnh nằm ngang.
II.3.4.Cuối cùng , nếu 1 tung độ bé hơn YSCANcòn tung độ kia lớn hơn
YSCANthì dòng quét cắt cạnh đó.
II.4.Xử lý các trường hợp đặc biệt.
II.4.1. Nếu cạnh bị cắt là nằm ngang thì chỉ việc bỏ qua cạnh đó và chuyển sangduyệt cạnh tiếp theo.
II.4.2.Nếu giao điểmtrùng với 1 đỉnh thì kiểm tra các tung độ ngay trước và ngay sau đỉnh đó . Nếu cả 2 tung độ đều lớn hơn/nhỏ hơn YSCAN thì cả 2 cạnh đangxét đều nằm về 1 phía so với dòng quét ( giống đỉnh C’)nên bỏ qua.
còn lại thì không được bỏ qua
II.4.3.Nếu trường hợp dòng quét cắt 1 cạnh thì ta phải xác định tọađộ giao điểm( x =?, yscan)
III. Các thủ tục xử lý các trường hợp đặc biệt.
III.1.Hàm xác định cạnh nằm ngang.
Gía trị trả về của hàm là True khi cạnh đang xét là cạnh nằm ngang , ngược lại giá trị trả về là False.
Function Canhngang(Var ys:Integer; y0,y1:Integer):Boolean;
Begin
If (ys=y0) and (ys=y1 ) Then canhngang:=True
Else canhngang:=False;
End;
III.2.Thủ tục xác định giao điểm tại một đỉnh
Procedure Giao1dinh(Var ys:Integer;y0,y1:Integer;Var i:Integer);
Var pt1,pt2,k:Integer;
Begin
If (ys=y0) or (ys=y1) Then
Begin
If ys=y0 Then k:=i-1 Else k:=i;
pt1:=Y[(k-1+N) mod N];
pt2:=Y[(k+1) mod N];
If ((pt1ys)) or (( pt1>ys) and (pt2 
Begin
j:=j+1;
Xgd[j]:=X[k mod N];{ Gan hoanh do cho giao diem}
End;
End;
End;
III.3.Thủ tục xác định khi dòng quét cắt một cạnh của đa giác.
Procedure Toadogiao(Var ys:Integer;y0,y1,x0,x1:Integer);
Var m,b:real;
Begin
If ((ys>y0) and (ysy1)) Then
Begin
j:=j+1;
If x0=x1 Then Xgd[j]:=x0{ Neula canh thang dung }
Else Begin
m:=((y1-y0)/(x1-x0));
b:=(-m*x0+y0);
Xgd[j]:=round((ys-b)/m);
End;
End;
End;
IV.VẼ
IV.1 . Thuật khử điểm.
Để có thể vẽ được một cách chính xác , ta phải áp dụng một kỹ thuật khử một số điểm đặc biệt để sao cho tổng số giao điểm trên một dòng quét bao giờ cũng là số chẵn.
Khi đó mỗi dòng quét sẽ làm sáng các Pixel từ một điểm mang chỉ số lẻ sang một điểm mang chỉ số chẵn .
IV.2 Thuật truy xuất tới 1 dỉnh hay cạnh liền sau (một đỉnh hay mộtcạnh) hiện thời.
Ở đây ta xây dựng cho được một TT phải có khả năng tìm đến 1 cạnh hay đỉnh theo nghĩa là “trước” và “sau”.
Theo cách đánh số thông thường , tức là dùng chỉ số i để đánh số cạnh đang xét , cạnh tiếp theo là i+1 và cạnh trước đó là i-1 sẽ không thể áp dụng được mà gây ra lỗi đối với cạnh cuối cùng hoặc cạnh đầu tiên.
VD: Cạnh số 5 của 1 ngũ giác chẳng hạn , đứng trước bởi cạnh 5-1=4 nhưng không thể đứng sau cạnh có chỉ số 5+1=6 (vì cạnh này không tồn tại). Vì lẽ đó , ta dùng cách đánh dấu sau:
Nếu đa giác có n cạnh thì cạnh thứ i có các đỉnh có ký hiệu ((i-1) mod n) và (i mod n).
Đỉnh thứ k được ký hiệu bởi (k mod n).Nó đứng sau bởi 1 đỉnh có ký hiệu là ((k-1+n) mod n)vàđứng trước bởi 1 đỉnh có ký hiệu là ((k+1) mod n).
V.Kết quả tô màu.
C. CHƯƠNG TRÌNH CÀI ĐẶT
Một số thủ tục và hàm được viết trong mục IVkhông được viết lại trong chương trình cài đặt này và sẽ được gọi trong thủ tục Procedure Tomau.
ProgramScanLine;
Uses Graph,mouse,crt;
Const Max=100;
x1=190; x2=631; y1=52;y2=471;
Var
Xgd: array[1..100] of integer;{Mang luu cac hoanh do giao diem}
X,Y: array[0..100] of integer;
n:integer;{ So dinh cua Da giac }
i,j:Word;
{-----------------------------------------------------------------}
Procedure Thietlap_Dohoa;
Var gd,gm,gr,Grok:integer;
Begin
detectgraph(gd,gm);
Grok:=0;
initgraph(gd,gm,'c: pgi');
gr:=graphresult;
If grgrok ThenWriteln('loi Do hoa',grapherrormsg(gr));
End;
{----------------------------------------------------------------------}
Procedure Desktop;
Begin
SetBKColor(4);
SetFillStyle(1,GetMaxColor);
Bar(2,2,637,3);
Bar(2,476,637,477);
Bar(636,2,637,477);
Bar(188,51,633,473);
SetFillStyle(1,4);
Bar(x1,y1,x2,y2);
Bar(6,6,633,47);
x:=20;Y:=12;
End;
Procedure Nhap;
Var i:integer;
Begin
Write('So dinhN='); Readln(n);
Writeln(' --- Nhap toa Do: ----:');
For i:=0 to n-1 Do
Begin
Write(' X[',i,']=');Readln(X[i]);
Write(' Y.Do[',i,']=');Readln(Y[i]);
End;
End;
{--------------------------------------------------------------------------}
Function ymax:integer;{ y top }
Var max,i:integer;
Begin
max:=Y[0];
For i:=1 to n-1 Do
If max 
ymax:=max;
End;
{--------------------------------------------------------------------------}
Function ymin:integer;{ y bottom }
Var min,i:integer;
Begin
min:=Y[0];
For i:=1 to n-1 Do
If min>Y[i] Then min:=Y[i];
ymin:=min;
End;
{--------------------------------------------------------------------------}
Procedure Sapxep(j:integer);
Var tg,k:integer;
Begin
For k:=1 to j-1 Do
For i:=k+1 to j Do
Begin
If Xgd[k]>Xgd[i] Then
Begin
tg:=Xgd[k];
Xgd[k]:=Xgd[i];
Xgd[i]:=tg;
End;
End;
End;
Procedure Loaibo(Var j:integer);
Var i:integer; 
Begin
k:=2;
For i:=2 to j Do
Begin
If Xgd[i-1] 
Begin
Xgd[k]:=Xgd[i];
k:=k+1;
End;
End;
End;
Procedure Quet(k,ys:integer);
Begin
j:=1;
while j 
Begin
Moveto(Xgd[j],ys);
putpixel(Xgd[j],ys,14);
For i:=Xgd[j] to Xgd[j+1] Do putpixel(i,ys,14);
j:=j+2;
End;
End;
Procedure Tomau;
Var ys,i,k,j0,x0,x1,y0,y1:integer;
pt1,pt2,tg:integer;
m,b:real;
Begin
For ys:=ymin to ymax Do
Begin
j:=0;
For i:=1 to n Do{ Chay CT cho tung canh }
Begin
y0:=Y[(i-1) mod n]; y1:=Y[i mod n];
If not(canhngang(ys,y1,y0)) Then
Begin
x0:=X[(i-1) mod n];
x1:=X[i mod n];
If (ys=y0) or (ys=y1) Then giao1dinh(ys,y0,y1,i)
elseToadogiao(ys,y0,y1,x0,x1);
End;
End;
Sapxep(j);
Loaibo(j);
Quet(k,ys);
End;
End;
Procedure ve;
Var i:integer;
Begin
For i:=0 to n-2 Do
Begin
Delay(20000);
Moveto(X[i],Y[i]);
Lineto(X[i+1],Y[i+1]);
End;
Moveto(X[n-1],Y[n-1]);
Delay(20000);
Lineto(X[0],Y[0]);
End;
{----------------------------------------------------------------------------}
Procedure wait;
Begin
Delay(2000);
End;
{----------------------------------------------------------------------------}
BEGIN
Thietlap_Dohoa;
Desktop;
Outtextxy(300,20,' ScanLine Program');
Nhap;
Write('Ve da giac!'#7);
Ve;
Writeln(#7'Please Wait!');
Wait; Write('To mau!');
Tomau; Readln;
END.
{-----------------------------------------------------------------------------}