計算機(jī)圖形學(xué)實習(xí)指導(dǎo)

1、第三章 圖形填充一、掃描線填充算法1、 操作說明為了顯示圖形效果，先在屏幕上用鼠標(biāo)繪制一個封閉圖形。具體操作是：用鼠標(biāo)左鍵依次點擊確定多邊形的頂點，系統(tǒng)同時繪制相鄰頂點之間的邊；然后點擊右鍵表示選點結(jié)束，系統(tǒng)繪制最后的頂點與第一個頂點之間的邊，完成封閉多邊形。在封閉多邊形完成后，系統(tǒng)運用掃描線填充算法完成封閉多邊形的填充。2、編程實現(xiàn)1）菜單響應(yīng)函數(shù)建立.打開工程項目，選定菜單項“掃描線填充算法”，在菜單屬性窗口將屬性項(Name)的屬性值改為“ScanLineFill”。雙擊菜單項“掃描線填充算法”，系統(tǒng)建立一個空的菜單響應(yīng)函數(shù)。在該函數(shù)中加入如下語句：private void ScanLi

2、neFill_Click(objecder, EventArgs e)ID = 31; Prum = 0;在窗口類 Form1 中增加一個數(shù)組 group 用來存放圖形頂點。因為其它的算法也需要這樣的數(shù)組，因此將其增設(shè)在 Form1 類成員中。public sic Form myf = new MyForm();Po posgroup=new Po4;/創(chuàng)建一個有 4 個點的點數(shù)組Po group=new Po100;/創(chuàng)建一個能放 100 個點的點數(shù)組在 Form1_MouseClick 函數(shù)中，增加菜單指示變量ID 為 31（即開始掃描線填充算法）時的程序操作語句如下：if (ID = 3

3、1)/掃描線填充Graphics g = CreateGraphics();/創(chuàng)建圖形設(shè)備if (e.Button = MouseButtons.Left)/如果按左鍵，存頂點groupPreum.X=e.X;groupPreum.Y=e.Y;if (Preum 0)/依次畫多邊形邊g.DrawLine(Pens.Red, groupPreum-1, groupPreum);Preum+;/這里，Preum了多邊形頂點數(shù)if (e.Button = MouseButtons.Right)/如果按右鍵，結(jié)束頂點，開始填充g.DrawLine(Pens.Red, groupPreum-1,grou

4、p0);/最后一條邊ScanLineFill1();/調(diào)用填充算法，開始填充ScanLineFill1 函數(shù)是用來實現(xiàn)算法的函數(shù)，到現(xiàn)在為止還沒實現(xiàn)。系統(tǒng)一個還沒實現(xiàn)的函數(shù)被使用，因此會提示錯誤。為了消除錯誤，立即建立一個空函數(shù)如下：private void ScanLineFill1()按 F5 鍵編譯執(zhí)行，可以用鼠標(biāo)在窗口中畫出封閉多邊形。但在畫下一個多邊形時，它與第一個多邊形糾結(jié)在一起，這是因為下一個多邊形的頂點數(shù)沒有初始化。這也提醒，ScanLineFill1 函數(shù)的最后一句應(yīng)該如下所示，以便順利開啟下一個多邊形的填充。private void ScanLineFill1()Preum

5、 = 0;現(xiàn)在來實現(xiàn)掃描線算法。首先，應(yīng)該建立邊結(jié)構(gòu)，邊結(jié)構(gòu)中保留了每一條非水平邊的信息。一條邊基本信息是兩個端點，但為了后續(xù)算法順利進(jìn)行，將信息組織為上端的 Y 坐標(biāo)，下端點的 X 坐標(biāo)，斜率的倒數(shù)。下端點的 Y 坐標(biāo)暗含在 ET 表中，為了方便，將下端點的 Y坐標(biāo)也建立在邊結(jié)構(gòu)中。因此，在 Form1 類中建立如下結(jié)構(gòu)數(shù)據(jù)類型：publicID, Preum,X,Y,R,XL,XR,YU,YD;public struct EdgeInfoymax, ymin;/Y 的上下端點float k,xmin;/斜率倒數(shù)和 X 的下端點/為四個變量設(shè)置的公共變量，方便外界存取數(shù)據(jù)publicYMax

6、 getreturn ymax; set ymax = value; publicYMin getreturn ymin; set ymin = value; public float XMin get return xmin; set xmin = value; public float K get return k; set k = value; /構(gòu)造函數(shù)，這里用來初始化結(jié)構(gòu)變量public EdgeInfo(x1,y1,x2,y2)/(x1,y1):下端點；(x2,y2):上端點ymax = y2; ymin = y1; xmin = (float)x1; k = (float)(x1

7、 - x2) /(float)(y1 - y2); /p = -1;Po group=new Po100;/創(chuàng)建一個能放 100 個點的點數(shù)組Po posgroup=new Po4;/創(chuàng)建一個有 4 個點的點數(shù)組public Form1()ponent();填充算法中，根據(jù) Group 數(shù)組中存放的多邊形建立各邊的邊結(jié)構(gòu)。為此，設(shè)立一個邊結(jié)構(gòu)數(shù)組 edgelist，然后從 Group 數(shù)組中依次取出每一條邊，生成邊結(jié)構(gòu)，存入邊結(jié)構(gòu)數(shù)組。如下所示：private void ScanLineFill1()EdgeInfo edgelist=new EdgeInfo100;/建立邊結(jié)構(gòu)數(shù)組group

8、Preum = group0;/將第一點為數(shù)組最后一點for(i=0;i groupi + 1.Y)/下端點，上端點在后edgelistj+ = new EdgeInfo(groupi + 1.X, groupi +1.Y, groupi.X, groupi.Y);elseedgelistj+ = new EdgeInfo(groupi.X, groupi.Y,groupi+1.X, groupi+1.Y);Preum = 0;按照算法，下面要建立 ET 表和 AEL 表，并隨著掃描線的不斷上移，將 ET 表中的邊逐步AEL 表，并按算法改變邊結(jié)構(gòu)中的數(shù)據(jù)。如果嚴(yán)格按照算法執(zhí)行，編程難度很大。

9、分析算法可知，AEL 表由 ET 表中與掃描線相交的邊（即 ymin=yymax）組成，只要根據(jù)當(dāng)前掃描線位置 y 從邊結(jié)構(gòu)數(shù)組中找出所有與掃描線相交的邊結(jié)構(gòu)，就得到當(dāng)前 AEL 表，就可以進(jìn)行掃描線填充，因此，編程實現(xiàn)方法可以直接建立 AEL 表。必須解決的一個問題是算法的結(jié)束條件。按照算法，當(dāng) ET 表和 AEL 表均為空時，算法結(jié)束，現(xiàn)在沒有 ET 表了，如何結(jié)束？分析算法整個過程，對于一個圖形的填充，掃描線的有效范圍是從圖形的最低點到圖形的最高點，因此，對于存在于 Group 數(shù)組中的圖形，只要找到了圖形的這兩個點，掃描線運動范圍就確定了。為此，要設(shè)置兩個變量，確定算法操作范圍。如下：

10、private void ScanLineFill1()EdgeInfo edgelist=new EdgeInfo100;j = 0,yu=0,yd=1024;/活化邊的掃描范圍從 yd 到 yugroupPreum = group0;/將第一點為數(shù)組最后一點for(i=0;i yu) yu = groupi.Y;/找出圖形最高點if (groupi.Y groupi + 1.Y)edgelistj+ = new EdgeInfo(groupi + 1.X, groupi + 1.Y,groupi.X, groupi.Y);elseedgelistj+ = new EdgeInfo(grou

11、pi.X, groupi.Y,groupi+1.X, groupi+1.Y);for(y=yd;yyu;y+)/AEL 表操作Preum = 0;AEL 表操作的第一步就是從結(jié)構(gòu)數(shù)組 edgelist 中選出與掃描線 y 相交的邊結(jié)構(gòu)，并排序。C#的 Linq 技術(shù)為提供了方法，如下：for(y=yd;yyu;y+)var sorted=/定義存放選擇結(jié)果的集合from item in edgelist /從edgelist中選where y=item.Ymin /選擇條件orderby item.XMin,item.K /集合元素排序條件select item;/開始選AEL表操作的第二步就

12、是倆倆配對，畫線。為此，要設(shè)置圖形設(shè)備，如下：Graphics g = CreateGraphics();/創(chuàng)建圖形設(shè)備for(y=yd;yyu;y+)var sorted=from item in edgelist/選出與當(dāng)前掃描線相交的邊結(jié)構(gòu)、排序where y=item.YMin orderby item.XMin,item.Kselect item; flag = 0;foreach (var item in sorted)/兩兩配對，畫線if (flag = 0)/第一點，不畫X =)(item.XMin+0.5); flag+;else/第二點，畫g.DrawLine(Pens.Blue, ( flag = 0;)(item.XMin+0.5), y,X-1, y);AEL 表操作的最后一步就是修改邊結(jié)構(gòu)中的 x 值，如下：foreach (var item in sorted)/兩兩配對，畫線if