計算機圖形學課程設計任務書

1、課程設計(論文)任務書 軟 件 學 院 學院 專業(yè) 班 一、課程設計(論文)題目 區(qū)域填充算法演示系統(tǒng) 二、課程設計(論文)工作自 2015 年 6 月 8 日起至 2015 年 6 月 12 日止。三、課程設計(論文) 地點: 軟 件 學 院 實 訓 中 心 四、課程設計(論文)內(nèi)容要求：1本課程設計的目的計算機圖形學課程設計是計算機圖形學課程中的知識、技術和技能的一個綜合應用， 是培養(yǎng)圖形軟件開發(fā)能力的綜合訓練。通過課程設計，使學生更深入地理解和掌握計算機圖形學理論與相關算法，鞏固課內(nèi)所學的知識、技術和技能，進一步提高圖形軟件開發(fā)的能力。為畢業(yè)設計和畢業(yè)后從事計算機繪圖、計算機輔助設計、輔

2、助教學、輔助工程、圖形處理等打下基礎。2課程設計的任務及要求1）課程設計任務：（1)能實現(xiàn)區(qū)域填充光柵化算法的原理性演示。（算法過程的可視化及動畫演示）（2)要求有算法參數(shù)輸入窗口和算法的圖形化結果顯示窗口。人機交互必須友好。 (3)將象素網(wǎng)格表現(xiàn)出來，建立網(wǎng)格坐標系。（4) 如果采用種子填充算法實現(xiàn)填充，用鼠標選擇種子點（也可以通過參數(shù)輸入窗口輸入種子），用表格的形式顯示堆棧存儲的象素，象素出?；蛉霔５倪^程要顯示出來。關鍵是要將象素填充的順序表現(xiàn)出來。2）創(chuàng)新要求：實現(xiàn)對多邊形的填充3）課程設計論文編寫要求（1）課程設計任務及要求（2）設計思路-工作原理、功能規(guī)劃（3）詳細設計-數(shù)據(jù)分析、算

3、法思路、功能實現(xiàn)（含程序流程圖、主要代碼及注釋）、界面等。（4）運行調(diào)試與分析討論-給出運行屏幕截圖，分析運行結果，有何改進想法等。（5）設計體會與小結-設計遇到的問題及解決辦法，通過設計學到了哪些新知識，鞏固了哪些知識，有哪些提高。（6）參考文獻（必須按標準格式列出，可參考教材后面的參考文獻格式）（7）報告按規(guī)定排版打印，要求裝訂平整，否則要求返工；（8）課設報告的裝訂順序如下：封面-任務書-中文摘要-目錄-正文-附錄(代碼及相關圖片)（9）嚴禁抄襲，如有發(fā)現(xiàn)，按不及格處理。4）課程設計評分標準： （1）學習態(tài)度：10分；（2）系統(tǒng)設計：20分；（3）編程調(diào)試：20分；（4）回答問題：20分

4、；（5）論文撰寫：30分。5）參考文獻：（1）陸楓 何云峰. 計算機圖形學基礎（第2版）M. 電子工業(yè)出版社（2）張曦煌 杜俊俐. 計算機圖形學M. 北京郵電大學出版社（3）孫家廣. 計算機圖形學M. 清華大學出版社. 6）課程設計進度安排1準備階段（4學時）：選擇設計題目、了解設計目的要求、查閱相關資料2程序模塊設計分析階段（4學時）：程序總體設計、詳細設計3代碼編寫調(diào)試階段（8學時）：程序模塊代碼編寫、調(diào)試、測試4撰寫論文階段（4學時）：總結課程設計任務和設計內(nèi)容，撰寫課程設計論文學生簽名： 2015 年 6 月 8 日課程設計(論文)評審意見（1）學習態(tài)度（10分）：優(yōu)（）、良（）、中（

5、）、一般（）、差（）； （2）系統(tǒng)設計（20分）：優(yōu)（ ）、良（）、中（）、一般（）、差（）； （3）編程調(diào)試（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）回答問題（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5）論文撰寫（30分）：優(yōu)（）、良（）、中（）、一般（）、差（）； 評閱人： 職稱： 講師 2015 年 6 月 日中文摘要摘要 ：圖形通常由點、線、面、體等幾何元素和灰度、色彩、線型、線寬等非幾何屬性組成。從處理技術上來看，圖形主要分為兩類，一類是基于線條信息表示的，如工程圖、等高線地圖、曲面的線框圖等，另一類是明暗圖，也就是通常所說的真實感圖形。計算機圖形學一

6、個主要的目的就是要利用計算機產(chǎn)生令人賞心悅目的真實感圖形。為此，必須建立圖形所描述的場景的幾何表示，再用某種光照模型，計算在假想的光源、紋理、材質(zhì)屬性下的光照明效果。關鍵詞 ：計算機圖形學、區(qū)域填充、掃描線算法目錄一、課程設計任務及要求1二、需求分析2三、設計思路3四、詳細設計4五、運行調(diào)試與分析討論5六、設計體會與小結6七、參考文獻7一、課程設計任務及要求1)能實現(xiàn)區(qū)域填充光柵化算法的原理性演示。（算法過程的可視化及動畫演示）2）要求有算法參數(shù)輸入窗口和算法的圖形化結果顯示窗口。人機交互必須友好。3）將象素網(wǎng)絡表現(xiàn)出來，建立網(wǎng)格坐標系。4）如果采用種子填充算法實現(xiàn)填充，用鼠標選擇種子點（也可

7、以通過參數(shù)輸入窗口輸入點），用表格的形式顯示堆棧存儲的象素，象素出棧或入棧的過程要顯示出來。關鍵是要將象素填充的順序表現(xiàn)出來。二、需求分析在計算機中重現(xiàn)真實世界的場景叫做真實感繪制。真實感繪制的主要任務是模擬真實物體的物理屬性，簡單的說就是物體的形狀、光學性質(zhì)、表面的紋理和粗糙程度，以及物體間的相對位置、遮擋關系等等。實時的真實感繪制已經(jīng)成為當前真實感繪制的研究熱點，而當前真實感圖形實時繪制的兩個熱點問題則是物體網(wǎng)格模型的面片簡化和基于圖象的繪制（IBR Image Based Rendering）。網(wǎng)格模型的面片簡化，就是指對網(wǎng)格面片表示的模型，在一定誤差的精度范圍內(nèi)，刪除點、邊、面，從而簡

8、化所繪制場景的復雜層度，加快圖形繪制速度。IBR完全摒棄傳統(tǒng)的先建模，然后確定光源的繪制的方法。它直接從一系列已知的圖象中生成未知視角的圖象。這種方法省去了建立場景的幾何模型和光照模型的過程，也不用進行如光線跟蹤等極費時的計算。該方法尤其適用于野外極其復雜場景的生成和漫游。主要任務是實現(xiàn)多邊形區(qū)域掃描線填充的有序邊表算法，設計相關的數(shù)據(jù)結構（如鏈表結構、結點結構等），并將實現(xiàn)的算法應用于任意多邊形的填充，區(qū)域填充,指的是在輸出平面的閉合區(qū)域內(nèi)完整地填充某種顏色或圖案。以下所述及的區(qū)域填充算法或相關程序,主要針對顯示平面內(nèi)的區(qū)域而言。區(qū)域填充的問題一般分兩大類,一是多邊形填充；一是種子填充；種子

9、填充在學生掌握了“?！边@一抽象數(shù)據(jù)類型的實現(xiàn)方法的前提下,比較容易完成。而邊標志填充算法卻是介于這兩類之間,部分地具有它們的痕跡,算法思想巧妙,實現(xiàn)起來更容易。多邊形填充有一定難度，我們主要對多邊形的掃描線算法填充做一些探討，具體將以五角星為實例。掃描線填充算法一般包括四個步驟：求交、排序、交點配對、區(qū)域填充。正確求得掃描線與區(qū)域填內(nèi)外輪廓線的交點是算法成敗的關鍵問題。另一方面，采用合適的數(shù)據(jù)結構又可以簡化操作、提高算法的效率。本論文由于采用鏈表結構記錄輪廓線和交點，無需焦點排序的過程，因而提高了算法效率。掃描線來源于光柵顯示器的顯示原理：對于屏幕上所有待顯示像素的信息，將這些信息按從上到下、

10、自左至右的方式顯示。掃描線多邊形區(qū)域填充算法是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。區(qū)間的端點可以通過計算掃描線與多邊形邊界線的交點獲得。對于一條掃描線，多邊形的填充過程可以分為四個步驟： （1）求交：計算掃描線與多邊形各邊的交點； （2）排序：把所有交點按x值遞增順序排序； （3）配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊形的一個相交區(qū)間; （4）填色：把相交區(qū)間內(nèi)的象素置成多邊形顏色;三、總體設計1） 分析多邊形區(qū)域掃描線填充算法的原理，確定算法流程 初始化：構造邊表ET，置AET表為空； 將第一個不空的ET表

11、中的邊插入AET表； 由AET表取出交點進行配對（奇偶）獲得填充區(qū)間，依次對這些填充區(qū)間著色； y=yi+1時，根據(jù)x=xi+1/k修改AET表所有結點中交點的x坐標。同時如果相應的ET表不空，則將其中的結點插入AET表，形成新的AET表； AET表不空，則轉(zhuǎn)（3），否則結束。2） 編程實現(xiàn) 首先確定多邊形頂點和ET/AET表中結點的結構 編寫鏈表相關操作（如鏈表結點插入、刪除和排序等） 根據(jù)1）中的算法結合上述已有的鏈表操作函數(shù)實現(xiàn)多邊形區(qū)域掃描線填充的主體功能 編寫主函數(shù)，測試該算法3）算法描述：void polyfill (多邊形 polygon, 顏色 color) for (各條掃描

12、線i )  初始化新邊表頭指針NET i；把ymin = i 的邊放進邊表NET i;      y = 最低掃描線號；   初始化活性邊表AET為空；   for (各條掃描線i )    把新邊表NETi中的邊結點用插入排序法插入AET表，使之按x坐標遞增順序排列；      遍歷AET表，把y max= i 的結點從AET表中刪除，并把y max > i結點的x值遞增D x；   &#

13、160;  若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序；      遍歷AET表，把配對交點區(qū)間(左閉右開)上的象素(x, y)，用drawpixel (x, y, color) 改寫象素顏色值；     /* polyfill */四、詳細設計1.用掃描線算法實現(xiàn)五角星填充 以（50,0），（60,30），（90,30），（70,45），（80,90），（50,60），（20,90），（30,45），（10,30），（40,30）這十個點作為五角星的十個點，利用掃描線算法將這個五

14、角星進行填充。根據(jù)掃描線的算法步驟，可將其算法過程描述如下：畫五角星圖形(1)五角星圖形圖3.1 五角星圖形(2)五角星的邊表構造ET表算法描述如下：void CreatET(Edge *et,struct pointtype p) /*根據(jù)頂點數(shù)組構造ET表*/ int i,lasty,lastx,nextx,nexty,ymax,cy,cx; Edge *pe; for(i=0;i<EDGEMAX;i+) cy=pi.y; cx=pi.x; /*確定上一點的坐標及下一點的坐標，考慮數(shù)組的首尾點。*/ if(0=i) lasty=pEDGEMAX-1.y; lastx=pEDGEMAX

15、-1.x; else lasty=pi-1.y; lastx=pi-1.x; if(EDGEMAX-1=i) nexty=p0.y; nextx=p0.x; else nexty=pi+1.y; nextx=pi+1.x; 圖3.2 五角星的邊的分類表(3)相對應活化邊表（a）y=0對應的活化邊表(b)y=3對應的活化邊表 （c）y=6對應的活化邊表 圖3.3 活化邊表(4) 描述邊算法的數(shù)據(jù)結構定義為：typedef struct int ymax; float x,delta; struct Edge *nextEdge;Edge;void CreatET(Edge *et,struct

16、pointtype p); /*根據(jù)頂點數(shù)組構造ET表*/void EdgeInAel(Edge *ael,Edge *edge); /*ET表中某邊edge插入至AEL表中，并排序，x相同時用下一點x+delta判斷*/void EdgeOutAel(Edge *ael,int y); /*刪除AEL中y=ymax的邊，并同時修改每邊的delta值*/(5) 頂點交點的計數(shù)問題 （6）對AEL中的邊兩兩配對，（1和2為一對，3和4為一對，）配對算法描述如下：void EdgeDraw(Edge *ael,int y); /*按AEL中的1，2配對，3,4配對然后x按規(guī)則去整后填充*/（7）如

17、果ET中的第y類非空，則將其中的結點插入AET表，形成新的AET表，算法描述如下：void EtInAel(Edge *et,Edge *ael,int y); /*找出ET中對應Y非空的邊并且排序進入AEL活化邊表*/（8）實現(xiàn)五角星主要算法：void main() int gd=DETECT,gm; int i,y,ymax; struct pointtype pEDGEMAX=50,0,60,30,90,30,70,45,80,90,50,60,20,90,30,45,10,30,40,30,50,0; Edge *etETMAX=0; Edge *ael; ael->nextEd

18、ge=NULL; initgraph(&gd,&gm,""); CreatET(et,p); for(i=0;i<ETMAX;i+) if(eti!=NULL) y=i; break; /*確定y的最小序號*/ ymax=p0.y; for(i=0;i<EDGEMAX;i+) if(pi.y>ymax) ymax=pi.y; /*確定ymax*/ while(y<=ymax) EtInAel(et,ael,y); EdgeDraw(ael,y); y+; EdgeOutAel(ael,y); 填充算法如下：void EdgeDraw(Edge *ael,int y) /*按AEL中的1，2配對，3,4配對然后x按規(guī)則去整后填充*/ int counter=1; /*奇偶計數(shù)器*/ int color,maxcolor; Edge *pmove; float