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

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

2、neFill_Click(objecder, EventArgs e)ID = 31; Prum = 0;在窗口類(lèi) Form1 中增加一個(gè)數(shù)組 group 用來(lái)存放圖形頂點(diǎn)。因?yàn)槠渌乃惴ㄒ残枰@樣的數(shù)組，因此將其增設(shè)在 Form1 類(lèi)成員中。public sic Form myf = new MyForm();Po posgroup=new Po4;/創(chuàng)建一個(gè)有 4 個(gè)點(diǎn)的點(diǎn)數(shù)組Po group=new Po100;/創(chuàng)建一個(gè)能放 100 個(gè)點(diǎn)的點(diǎn)數(shù)組在 Form1_MouseClick 函數(shù)中，增加菜單指示變量ID 為 31（即開(kāi)始掃描線填充算法）時(shí)的程序操作語(yǔ)句如下：if (ID = 3

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

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

5、 = 0;現(xiàn)在來(lái)實(shí)現(xiàn)掃描線算法。首先，應(yīng)該建立邊結(jié)構(gòu)，邊結(jié)構(gòu)中保留了每一條非水平邊的信息。一條邊基本信息是兩個(gè)端點(diǎn)，但為了后續(xù)算法順利進(jìn)行，將信息組織為上端的 Y 坐標(biāo)，下端點(diǎn)的 X 坐標(biāo)，斜率的倒數(shù)。下端點(diǎn)的 Y 坐標(biāo)暗含在 ET 表中，為了方便，將下端點(diǎn)的 Y坐標(biāo)也建立在邊結(jié)構(gòu)中。因此，在 Form1 類(lèi)中建立如下結(jié)構(gòu)數(shù)據(jù)類(lèi)型：publicID, Preum,X,Y,R,XL,XR,YU,YD;public struct EdgeInfoymax, ymin;/Y 的上下端點(diǎn)float k,xmin;/斜率倒數(shù)和 X 的下端點(diǎn)/為四個(gè)變量設(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ù)，這里用來(lái)初始化結(jié)構(gòu)變量public EdgeInfo(x1,y1,x2,y2)/(x1,y1):下端點(diǎn)；(x2,y2):上端點(diǎn)ymax = y2; ymin = y1; xmin = (float)x1; k = (float)(x1

7、 - x2) /(float)(y1 - y2); /p = -1;Po group=new Po100;/創(chuàng)建一個(gè)能放 100 個(gè)點(diǎn)的點(diǎn)數(shù)組Po posgroup=new Po4;/創(chuàng)建一個(gè)有 4 個(gè)點(diǎn)的點(diǎn)數(shù)組public Form1()ponent();填充算法中，根據(jù) Group 數(shù)組中存放的多邊形建立各邊的邊結(jié)構(gòu)。為此，設(shè)立一個(gè)邊結(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;/將第一點(diǎn)為數(shù)組最后一點(diǎn)for(i=0;i groupi + 1.Y)/下端點(diǎn)，上端點(diǎn)在后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)行掃描線填充，因此，編程實(shí)現(xiàn)方法可以直接建立 AEL 表。必須解決的一個(gè)問(wèn)題是算法的結(jié)束條件。按照算法，當(dāng) ET 表和 AEL 表均為空時(shí)，算法結(jié)束，現(xiàn)在沒(méi)有 ET 表了，如何結(jié)束？分析算法整個(gè)過(guò)程，對(duì)于一個(gè)圖形的填充，掃描線的有效范圍是從圖形的最低點(diǎn)到圖形的最高點(diǎn)，因此，對(duì)于存在于 Group 數(shù)組中的圖形，只要找到了圖形的這兩個(gè)點(diǎn)，掃描線運(yùn)動(dòng)范圍就確定了。為此，要設(shè)置兩個(gè)變量，確定算法操作范圍。如下：

10、private void ScanLineFill1()EdgeInfo edgelist=new EdgeInfo100;j = 0,yu=0,yd=1024;/活化邊的掃描范圍從 yd 到 yugroupPreum = group0;/將第一點(diǎn)為數(shù)組最后一點(diǎn)for(i=0;i yu) yu = groupi.Y;/找出圖形最高點(diǎn)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;/開(kāi)始選AEL表操作的第二步就

12、是倆倆配對(duì)，畫(huà)線。為此，要設(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)/兩兩配對(duì)，畫(huà)線if (flag = 0)/第一點(diǎn)，不畫(huà)X =)(item.XMin+0.5); flag+;else/第二點(diǎn)，畫(huà)g.DrawLine(Pens.Blue, ( flag = 0;)(item.XMin+0.5), y,X-1, y);AEL 表操作的最后一步就是修改邊結(jié)構(gòu)中的 x 值，如下：foreach (var item in sorted)/兩兩配對(duì)，畫(huà)線if