計算機(jī)圖形學(xué)課程設(shè)計-有效邊表填充算法的實現(xiàn)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：27 大?。?06.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩26頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　設(shè)計題目改進(jìn)的有效邊表算法對多邊形的填充 　　目錄　　一、設(shè)計內(nèi)容與要求3　　1.1設(shè)

2、計題目3　　1.2 設(shè)計內(nèi)容3　　1.3 設(shè)計目標(biāo)3　　二、總體設(shè)計3　　2.1 多邊形的表示3　　2.2 x-掃描線算法4　　2.3 改

3、進(jìn)的有效邊表算法4　　2.3.1 改進(jìn)的有效邊表算法4　　2.3.2 有效邊表5　　2.3.3 邊表6　　三、詳細(xì)設(shè)計8　　3.1 改進(jìn)的有效邊表算法的實現(xiàn)8

4、　　3.2 有效邊表算法程序流程圖9　　四、測試結(jié)果9　　五、總結(jié)15　　六、源代碼15　　參考文獻(xiàn)26<

5、;/b>　　一、設(shè)計內(nèi)容與要求　　設(shè)計題目　　用改進(jìn)的有效邊表算法實現(xiàn)多邊形的填充　　1.2 設(shè)計內(nèi)容　　使用

6、OpenGL實現(xiàn)用改進(jìn)的有效邊表算法填充多邊形　　1.3 設(shè)計目標(biāo)　　參照課本上改進(jìn)的有效邊表算法的思想，實現(xiàn)該算法的C語言代碼，并用該算法搭配OpenGL以像素點(diǎn)的方式繪制出給定頂點(diǎn)坐標(biāo)的多邊形。　　二、總體設(shè)計

7、　　2.1 多邊形的表示　　在計算機(jī)圖形學(xué)中，多邊形有2種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。　　頂點(diǎn)表示用多邊形的頂點(diǎn)序列來刻畫多邊形，這種方法直觀、幾何意義強(qiáng)，占用內(nèi)存少，應(yīng)用普遍，但它沒有明確指出哪些像素在多邊形內(nèi)，故不能直接用于面著色。　　點(diǎn)陣表示用位于多邊形內(nèi)的像素的集合來刻畫多邊形。

8、這種表示法雖然失去了許多重要的幾何信息，但便于運(yùn)用幀緩存表示圖形，是面著色所需要的圖形表示形式。　　大多數(shù)圖形應(yīng)用系統(tǒng)采用頂點(diǎn)序列表示多邊形，而頂點(diǎn)表示又不能直接用于顯示，那么就必須有從多邊形的頂點(diǎn)表示到點(diǎn)陣表示的轉(zhuǎn)換，這種轉(zhuǎn)換稱為多邊形的掃描轉(zhuǎn)換或多邊形的填充。即從多邊形的頂點(diǎn)信息出發(fā)，求出位于其內(nèi)部的各個像素，并將其顏色值寫入幀緩存的相應(yīng)單元中。

9、　2.2 x-掃描線算法　　x-掃描線算法的基本思想是，按照掃描線的順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。區(qū)間的端點(diǎn)可以通過計算掃描線與多邊形邊界線的交點(diǎn)獲得。根據(jù)此原理，x-掃描線算法可以填充凸的、凹的或帶有孔的多邊形區(qū)域。　　x-掃描線的算法步驟如下：　　確定多

10、邊形頂點(diǎn)的最小和最大y值(ymin和ymax)，得到多邊形所占有的最大掃描線數(shù)。　　從y=ymin到y(tǒng)=ymax，每次用一條掃描線填充。每一條掃描線填充的過程分為4個步驟：　　求交。計算掃描線與多邊形所有邊的交點(diǎn)。　　排序。把所有交點(diǎn)按x坐標(biāo)遞增的順序進(jìn)行排序。　　交點(diǎn)配

11、對。配對第一與第二、第三與第四個交點(diǎn)等，每對交點(diǎn)代表一個填充區(qū)間。　　區(qū)間填色。把這些相交區(qū)間內(nèi)的像素置成不同于背景色的填充色。　　x-掃描線算法在處理每條掃描線時，需要與多邊形的所有邊求交，這樣處理效率非常低。因為一條掃描線往往只與少數(shù)幾條邊相交，甚至與整個多邊形都不相交。因此，有必要對算法進(jìn)行改進(jìn)。　　2.3

12、改進(jìn)的有效邊表算法　　2.3.1 改進(jìn)的有效邊表算法　　將x-掃描線算法加以改進(jìn)可以得到改進(jìn)的有效邊表算法，也稱y連貫算法。改進(jìn)可以從三個方面進(jìn)行：首先，在處理一條掃描線時，僅對與它相交的多邊形的邊（有效邊）求交；其次，利用掃描線的連貫性，考慮到當(dāng)前掃描線與各邊的交點(diǎn)順序與下一條掃描線與各邊的交點(diǎn)順序很可能相同或非常相似，因此在當(dāng)前掃描線處理完畢之后，

13、不必為下一條掃描線從頭開始構(gòu)造交點(diǎn)信息；最后，利用多邊形的連貫性，認(rèn)為若某條邊與當(dāng)前掃描線相交，則它很可能也與下一條掃描線相交且其交點(diǎn)與上一次的交點(diǎn)相關(guān)。如下圖所示，設(shè)直線的斜率為k，若y=yi時，x=xi；則當(dāng)y=yi+1時，有xi+1=xi+1/k。　　2.3.2 有效邊表　　有效邊（Active Edge）是指與當(dāng)前掃描線相交的多邊形的邊，也稱活性

14、邊。把有效邊按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個鏈表中，此鏈表稱為有效邊表（Active Edge Table， AET）。有效邊表的每個結(jié)點(diǎn)存放對應(yīng)邊的如下信息：　　其中，x為當(dāng)前掃描線與有效邊交點(diǎn)的x坐標(biāo)；ymax是有效邊所在的最大掃描線值，通過它可以知道何時才能“拋棄”該邊；1/k是邊斜率的倒數(shù)；next是下一個結(jié)點(diǎn)的指針。　　如下圖所示的多邊

15、形P0P1P2P3P4P5P6，其頂點(diǎn)表示為：　　P0(7，8)，P1(3，12)，P2(1，7)，P3(3，1)，P4(6，5)，P5(8，1)，P6(12，9)。　　當(dāng)y=8時的有效邊表如下圖所示：　　2.3.3 邊表　　有效邊表

16、給出了掃描線和有效邊交點(diǎn)坐標(biāo)的計算方法，但是沒有給出新邊出現(xiàn)的位置坐標(biāo)。為了方便有效邊表的建立與更新，就需要構(gòu)造一個邊表（Edge Table， ET），用以存放掃描線上多邊形各條邊的信息。由于水平邊的1/k為∞，并且水平邊本身就是掃描線，所以在建立邊表時不予考慮。　　邊表的構(gòu)造分為4個步驟：　　首先構(gòu)造一個縱向鏈表，鏈表的長度為多邊形占有的最大掃描線數(shù)

17、，鏈表的每個結(jié)點(diǎn)，稱為一個桶，對應(yīng)多邊形覆蓋的每一條掃描線。　　將每條邊的信息裝入與該邊最小y坐標(biāo)(ymin)相對應(yīng)的桶中。也就是說，若某邊的較低端點(diǎn)為ymin，則該邊就放在相應(yīng)的y=ymin的掃描線桶中。　　每條邊的數(shù)據(jù)形成一個結(jié)點(diǎn)，內(nèi)容包括該掃描線與該邊的初始交點(diǎn)x(即較低端點(diǎn)的x坐標(biāo)值)，該邊最大y坐標(biāo)值ymax，以及斜率的倒數(shù)1/k和下一個邊結(jié)點(diǎn)

18、的指針next:　　同一桶中若干條邊按x|ymin由小到大排列，若x|ymin相等，則按1/k由小到大排序。　　從上面可以看出，邊表是有效邊表的特例，有效邊表和邊表可以使用同一個數(shù)據(jù)結(jié)構(gòu)來表示。　　對于多邊形P0P1P2P3P4P5P6，它的邊表結(jié)構(gòu)如下圖所示：<b

19、>　　三、詳細(xì)設(shè)計　　3.1 改進(jìn)的有效邊表算法的實現(xiàn)　　改進(jìn)的有效邊表算法具體實現(xiàn)過程如下：　　初始化邊表ET。　　為了方便邊表的建立，可以定義sort()函數(shù)對多邊形的邊進(jìn)行排序，保證邊表中每個桶中的邊是

20、有序的。同時定義一個creat_edge_table()函數(shù)，該函數(shù)需要多邊形的頂點(diǎn)信息作為參數(shù)傳入，并返回一個邊表指針。　　初始化有效邊表AET。從ET表中取出第一個不為空的桶與AET表合并。　　為了初始化AET表，可以定義一個init_active_table()函數(shù)，該函數(shù)傳入邊表指針作為形參，返回一個有效邊表指針。<

21、p>　　從AET表中取出交點(diǎn)進(jìn)行填充。　　填充時設(shè)置一個布爾值b（初值為假），令指針從有效邊表的第一個結(jié)點(diǎn)（也就是掃描線與有效邊的交點(diǎn)）開始遍歷。每訪問一個結(jié)點(diǎn)，把b取反一次。若b為真，則把從當(dāng)前結(jié)點(diǎn)的x值開始（設(shè)為x1）到下一結(jié)點(diǎn)的x值結(jié)束(設(shè)為x2)的區(qū)間[x1, x2]用多邊形色填充。填充時為了避免多邊形區(qū)域擴(kuò)大化，需要對區(qū)間邊界進(jìn)行如下處理：

22、;　　若x是整數(shù)，則按“左閉右開”的原則處理，即左邊界上的x（x1）不變，右邊界上的x（x2）減1；若x不是整數(shù)，左邊界上的x（x1）向右取整，右邊界上的x（x2）向左取整。　　更新AET表。　　設(shè)當(dāng)前AET表中掃描線為y，首先更新掃描線為y=y+1，然后刪除AET表中所有ymax=y的邊結(jié)點(diǎn)；再根據(jù)xi+1=xi+

23、1/k計算并修改AET表中各邊結(jié)點(diǎn)的x坐標(biāo)，同時合并ET表對應(yīng)于掃描線y的桶中的邊，按次序插入到AET表中，形成新AET表。此步驟滿足多邊形的“下閉上開”原則。　　此過程用到自定義的函數(shù)delete_edge()、add_edge()、update_active_table()。　　判斷AET表是否為空。若為空，則結(jié)束；否則轉(zhuǎn)到③

24、　　3.2 有效邊表算法程序流程圖　　四、測試結(jié)果　　為了便于觀察多邊形的填充，本程序?qū)⑾袼攸c(diǎn)進(jìn)行放大處理，400 x 300的分辨率投影到20 x 15，并繪制出網(wǎng)格，使用OpenGL畫出多邊形的邊框。使用了Sleep()函數(shù)來延時生成像素點(diǎn)，并且每填充一個像素點(diǎn)刷新一次，給人動態(tài)直觀的感受。&l

25、t;/p>　　在不處理邊界的情況下，如下圖所示，多邊形的區(qū)域可能會擴(kuò)大化。　　對邊界進(jìn)行處理后，結(jié)果如下：　　為了驗證改進(jìn)的有效邊表填充算法，現(xiàn)將本程序的像素大小恢復(fù)為1：1，按比例擴(kuò)大多邊形的頂點(diǎn)坐標(biāo)，測試結(jié)果如下：　　從上圖可以看出填充過后的多邊形與原多邊形P0P1P2P3P4P5

26、P6的形狀一致，該算法驗證通過。　　測試其他多邊形　　長方形：　　三角形：　　五角星：<p

27、>　　從以上結(jié)果來看，該算法基本得到完美實現(xiàn)。而程序的執(zhí)行時間來看，生成邊表的時間（包括分配內(nèi)存、對桶中的結(jié)點(diǎn)進(jìn)行排序等）遠(yuǎn)比填充像素點(diǎn)的時間要長。因此，該算法的效率雖然很高，但對于表的維護(hù)和排序開銷太大，它適合軟件實現(xiàn)而不適合硬件實現(xiàn)。　　五、總結(jié)　　通過本次課程設(shè)計，我掌握了多邊形的填充算法，了解了Open

28、GL的運(yùn)行結(jié)構(gòu)，熟悉了很多OpenGL的函數(shù)，對OpenGL編程也產(chǎn)生的濃厚的興趣。同時也鞏固了對計算機(jī)圖形學(xué)知識的掌握，鍛煉了我對手實驗的能力，看清了自己的水平，認(rèn)識到了自己的不足。　　在本次課程設(shè)計中，存在一些不足之處。比如對邊界的處理，課本上的說法模糊不清，在網(wǎng)上也沒有找到相應(yīng)的解答，我只能根據(jù)自己的理解來試著解決；這方面也存在沒有及時和老師溝通的原因。從這一點(diǎn)上，我認(rèn)識到理論和實踐的差別

29、，我們應(yīng)該多實踐才能真正掌握理論。　　還有就是完全填充后的多邊形，邊緣有“鋸齒”現(xiàn)象，不知道是我程序的原因還是算法的問題。或許對于多邊形的填充算法還應(yīng)該處理“鋸齒”。　　六、源代碼　　//源代碼僅包含文件PolygonFilling.cpp<p&

30、gt;　　#include <stdio.h>　　#include <malloc.h>　　#include <gl/glut.h>　　#include <Windows.h>　　#define EPSILON 0.0000

31、01 //最小浮點(diǎn)數(shù)　　//點(diǎn)結(jié)構(gòu)體　　struct Point　　{　　int x; //x坐標(biāo)　　int y;

32、//y坐標(biāo)　　};　　//線結(jié)構(gòu)體　　struct Line　　{　　Point high_point;

33、 //高端點(diǎn)　　Point low_point; //低端點(diǎn)　　int is_active; //是否為有效邊，水平邊（0），非水平邊（1）　　double inverse_k; //斜率k的倒數(shù)　　}

34、;　　//邊結(jié)點(diǎn)　　struct EdgeNode　　{　　double x; //掃描線與邊交點(diǎn)的x坐標(biāo)（邊的低端點(diǎn)的x坐標(biāo)）

35、　　int y_max; //邊的高端點(diǎn)的y坐標(biāo)ymax　　double inverse_k; //斜率k的倒數(shù)　　EdgeNode *next; //下一個邊結(jié)點(diǎn)的指針　　};<

36、;p>　　//有效邊表　　struct ActiveEdgeTable　　{　　int y; //掃描線y　　EdgeNode *head; /

37、/邊鏈表的頭指針　　};　　//桶結(jié)點(diǎn)　　typedef struct Bucket　　{　　int y;

38、 //掃描線y　　EdgeNode *head; //邊鏈表的頭指針　　Bucket *next; //下一個桶的指針　　} EdgeTable;　　int compare(Point p1, Point p2);</

39、p>　　Line* create_lines(Point points[], int n);　　Point get_lowest_point(Line lines[], int n);　　Point get_highest_point(Line lines[], int n);　　vo

40、id swap(Line &l1, Line &l2);　　void sort(Line lines[], int n);　　EdgeTable* create_edge_table(Line lines[], int n);　　ActiveEdgeTable* init_active_table

41、(EdgeTable *edge_table);　　void delete_edge(ActiveEdgeTable *active_table, int y_max);　　void add_edge(ActiveEdgeTable *active_table, EdgeNode edge);　　ActiveEd

42、geTable* update_active_table(ActiveEdgeTable *active_table, EdgeTable *edge_table);　　void DrawPolygon(Point points, int n);　　void DrawGrid(int x, int y);　　vo

43、id Fill(Point points[], int n);　　void Initial();　　void Display();　　int main(int argc, char* argv[])　　{<

44、;p>　　glutInit(&argc, argv);　　glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);　　glutInitWindowSize(400, 300);　　glutInitWindowPosition(100, 120);

45、　　glutCreateWindow("Polygon Filling");　　glutDisplayFunc(Display);　　Initial();　　glutMainLoop();　　return 0;&l

46、t;/b>　　}　　//比較2個點(diǎn)的高度　　int compare(Point p1, Point p2)　　{　　if (p1.y > p2

47、.y)　　return 1;　　else if (p1.y == p2.y)　　return 0;　　return -1;　　}<

48、/b>　　//由點(diǎn)數(shù)組生成線段數(shù)組　　Line* create_lines(Point points[], int n)　　{　　Line *lines = (Line*)malloc(n * sizeof(Line));<

49、;/p>　　for (int i = 0; i < n; ++i)　　{　　Point p1 = points[i];　　Point p2 = points[(i + 1) % n];　　int re

50、sult = compare(p1, p2);　　if (result == 0)　　lines[i].is_active = 0;　　else　　lines[i].is_active = 1;

51、;　　lines[i].high_point = result > 0 ? p1 : p2;　　lines[i].low_point = result < 0 ? p1 : p2;　　lines[i].inverse_k = (double)(p2.x - p1.x) / (double)(p2.y - p1.y);&

52、lt;p>　　}　　return lines;　　}　　//獲取線數(shù)組中最低的端點(diǎn)　　Point get_lowest_point(Line lines[], int n)

53、;　　{　　Point lowest_point = lines[0].low_point;　　for (int i = 1; i < n; ++i)　　{　　Poin

54、t low_point = lines[i].low_point;　　if (compare(lowest_point, low_point) > 0)　　lowest_point = low_point;　　}　　return

55、 lowest_point;　　}　　//獲取線數(shù)組中最高的端點(diǎn)　　Point get_highest_point(Line lines[], int n)　　{<p

56、>　　Point highest_point = lines[0].high_point;　　for (int i = 1; i < n; ++i)　　{　　Point high_point = lines[i].high_point;&l

57、t;p>　　if (compare(highest_point, high_point) < 0)　　highest_point = high_point;　　}　　return highest_point;<b&g

58、t;　　}　　//交換2個Line對象　　void swap(Line &l1, Line &l2)　　{　　Line temp = l1;

59、;　　l1 = l2;　　l2 = temp;　　}　　//對線數(shù)組進(jìn)行排序　　void sort(Line lines[], int n)　　{<

60、/b>　　//先按低端點(diǎn)的y坐標(biāo)進(jìn)行升序排序　　for (int i = 0; i < n; ++i)　　{　　int min_index = i;　　for (int j = i

61、 + 1; j < n; ++j)　　{　　if (lines[j].low_point.y < lines[min_index].low_point.y)　　min_index = j;　　}</

62、b>　　swap(lines[i], lines[min_index]);　　}　　//再將有序數(shù)組按低端點(diǎn)的x坐標(biāo)升序排列，若x坐標(biāo)相等，按inverse_k升序　　for (int i = 0; i < n; ++i)

63、　　{　　int min_index = i;　　for (int j = i + 1; lines[j].low_point.y == lines[i].low_point.y; ++j)　　{

64、　　if (lines[j].low_point.x < lines[min_index].low_point.x)　　min_index = j;　　}　　swap(lines[i], lines[min_index]);&l

65、t;/p>　　if (i > 0 && lines[i].low_point.x == lines[i - 1].low_point.x)　　{　　if (lines[i].is_active == 1 && lines[i - 1].is_activ

66、e == 1)　　{　　if (lines[i].inverse_k < lines[i - 1].inverse_k)　　swap(lines[i], lines[i - 1]);　　}&

67、lt;/p>　　}　　}　　}　　//創(chuàng)建一個邊表　　EdgeTable* create_e

68、dge_table(Line lines[], int n)　　{　　EdgeTable *edge_table = (EdgeTable*)malloc(sizeof(EdgeTable));　　edge_table->head = NULL;

69、　　edge_table->next = NULL;　　sort(lines, n);　　Point lowest_point = get_lowest_point(lines, n);　　Point highest_point = get_highest_point(lines, n);

70、　　EdgeTable *s = edge_table;　　for (int i = lowest_point.y; i <= highest_point.y; ++i)　　{　　Bucket *bucket = (Bucket

71、*)malloc(sizeof(Bucket));　　bucket->y = i;　　bucket->next = NULL;　　bucket->head = (EdgeNode*)malloc(sizeof(EdgeNode));　　bucket-&g

72、t;head->next = NULL;　　EdgeNode *p = bucket->head;　　for (int j = 0; j < n; ++j)　　{　　if (lines[j].is_active ==

73、 0)　　continue;　　if (lines[j].low_point.y == i)　　{　　EdgeNode *q = (EdgeNode*)malloc(sizeof(EdgeNode

74、));　　q->x = lines[j].low_point.x;　　q->y_max = lines[j].high_point.y;　　q->inverse_k = lines[j].inverse_k;　　q->next = NULL;<

75、;/p>　　p->next = q;　　p = q;　　}　　}　　s->next = bucket;</p&g

76、t;　　s = bucket;　　}　　return edge_table;　　}　　//從邊表中取出第一個不為空的桶初始化有效邊表

77、　　ActiveEdgeTable* init_active_table(EdgeTable *edge_table)　　{　　ActiveEdgeTable *active_table = (ActiveEdgeTable*)malloc(sizeof(ActiveEdgeTable));&

78、lt;p>　　active_table->y = edge_table->next->y;　　active_table->head = (EdgeNode*)malloc(sizeof(EdgeNode));　　active_table->head->next = NULL;<p&g

79、t;　　EdgeNode *p = edge_table->next->head;　　EdgeNode *q = active_table->head;　　while (p->next != NULL)　　{

80、　EdgeNode *s = (EdgeNode*)malloc(sizeof(EdgeNode));　　s->x = p->next->x;　　s->y_max = p->next->y_max;　　s->inverse_k = p->next->inver

81、se_k;　　s->next = NULL;　　q->next = s;　　q = s;　　p = p->next;　　}</p&

82、gt;　　return active_table;　　}　　//從有效邊表中刪除指定y_max的邊結(jié)點(diǎn)　　void delete_edge(ActiveEdgeTable *active_table, int y_max)<

83、p>　　{　　EdgeNode *p = active_table->head;　　while (p->next != NULL)　　{　　EdgeNode *q = p->

84、;next;　　if (q->y_max == y_max)　　{　　p->next = q->next;　　free(q);<b

85、>　　}　　else　　p = p->next;　　}　　}　　//將一個邊結(jié)點(diǎn)按次

86、序添加到有效邊表中　　void add_edge(ActiveEdgeTable *active_table, EdgeNode edge)　　{　　EdgeNode *t = (EdgeNode*)malloc(sizeof(EdgeNode));&

87、lt;p>　　t->x = edge.x;　　t->y_max = edge.y_max;　　t->inverse_k = edge.inverse_k;　　t->next = NULL;　　EdgeNode *p = active_tabl

88、e->head;　　while (p->next != NULL)　　{　　EdgeNode *q = p->next;　　if ((edge.x < q->x) || (edge.x == q->

89、x && edge.inverse_k < q->inverse_k))　　{　　p->next = t;　　t->next = q;　　return;&l

90、t;/p>　　}　　p = p->next;　　}　　p->next = t;　　}<p

91、>　　//更新有效邊表，并與邊表中對應(yīng)的桶合并　　ActiveEdgeTable* update_active_table(ActiveEdgeTable *active_table, EdgeTable *edge_table)　　{　　//更新掃描

92、線y　　++active_table->y;　　//刪除y=ymax的邊　　delete_edge(active_table, active_table->y);　　//更新邊結(jié)點(diǎn)的數(shù)據(jù)　　Edge

93、Node *p = active_table->head->next;　　while (p != NULL)　　{　　p->x += p->inverse_k;　　p = p->next;</p&g

94、t;　　}　　//找到邊表中對應(yīng)的桶　　EdgeTable *q = edge_table;　　while ((q = q->next) != NULL && q->y != active_table->y);</

95、p>　　//如果找到，則進(jìn)行合并　　if (q != NULL)　　{　　EdgeNode *s = q->head;　　while ((s = s->next) != NULL)</p&

96、gt;　　{　　add_edge(active_table, *s);　　}　　}　　return active_table;</

97、p>　　}　　//畫出多邊形的邊框　　void DrawPolygon(Point points[], int n)　　{　　glBegin(GL_LINE_LOOP)

98、;　　for (int i = 0; i < n; ++i)　　glVertex2i(points[i].x, points[i].y);　　glEnd();　　}&

99、lt;p>　　//畫出x * y的網(wǎng)格　　void DrawGrid(int x, int y)　　{　　glBegin(GL_LINES);　　//橫線<p&

100、gt;　　for (int i = 0; i <= y; ++i)　　{　　glVertex2d(0, i);　　glVertex2d(x, i);　　}&l

101、t;p>　　//豎線　　for (int i = 0; i <= x; ++i)　　{　　glVertex2d(i, 0);　　glVertex2d(i, y);

102、　　}　　glEnd();　　}　　//用指定的像素大小填充多邊形　　void Fill(Point points[], int n)&l

103、t;/p>　　{　　Line *lines = create_lines(points, n);　　EdgeTable *edge_table = create_edge_table(lines, n);　　ActiveEdgeTable *act

104、ive_table = init_active_table(edge_table);　　while (active_table->head->next != NULL)　　{　　EdgeNode *p = active_table->head;</p&

105、gt;　　int b = -1;　　while (p->next != NULL)　　{　　if (b > 0)　　{

106、　int left = p->x;　　int right = p->next->x;　　//如果不是局部最低點(diǎn)，則進(jìn)行邊界處理　　if (!(p->x - p->next->x >= -EPSILON && p->x - p->next->

107、;x <= EPSILON))　　{　　//處理左邊界　　if (!(p->x - left >= -EPSILON && p->x - left <= EPSILON))

108、　　left += 1;　　//處理右邊界　　if (p->next->x - right >= -EPSILON && p->next->x - right <= EPSILON)　　right -=

109、 1;　　}　　for (int i = left; i <= right; ++i)　　{　　glBegin(GL_POINTS);　　glVer

110、tex2d(i, active_table->y);　　glEnd();　　glFlush();　　Sleep(50);　　}

111、}　　p = p->next;　　b = -b;　　}　　active_table = update_active_table(active_table, edge_ta

112、ble);　　}　　}　　//初始化窗口，x和y指定窗口的坐標(biāo)大小　　void Initial()　　{</p

113、>　　glClearColor(1.0f, 1.0f, 1.0f, 1.0f);　　glMatrixMode(GL_PROJECTION);　　gluOrtho2D(0.0, 20.0, 0.0, 15.0);　　}<

114、p>　　//窗口的顯示回調(diào)函數(shù)　　void Display()　　{　　//使用當(dāng)前背景色填充窗口　　glClear(GL_COLOR_BUFFER_BIT);　　//使用灰色畫出網(wǎng)格線

115、　　glColor3f(0.75f, 0.75f, 0.75f);　　DrawGrid(20, 14);　　glFlush();　　//多邊形的頂點(diǎn)坐標(biāo)　　Point points[] = { { 3, 1 },{ 6, 5 },

116、{ 8, 1 },{ 12, 9 },{ 7, 8 },{ 3, 12 },{ 1, 7 } };　　//計算頂點(diǎn)個數(shù)　　int n = sizeof(points) / sizeof(Point);　　//使用黑色畫出多邊形的邊框

117、　glColor3f(0.0f, 0.0f, 0.0f);　　DrawPolygon(points, n);　　glFlush();　　//指定點(diǎn)大小　　glPointSize(6.0f);

118、　　//使用紅色填充多邊形　　glColor3f(1.0f, 0.0f, 1.0f);　　Fill(points, n);　　glFlush();　　}　　參考文獻(xiàn)</

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

計算機(jī)圖形學(xué)課程設(shè)計-有效邊表填充算法的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

計算機(jī)圖形學(xué)課程設(shè)計-有效邊表填充算法的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載