二維填充圖元的生成

1、1,第4章 二維填充圖元的生成,2,本章目標(biāo),掌握如何繪制填充圖元（矩形、多邊形等）掃面轉(zhuǎn)換算法（掃描線算法）填充算法學(xué)會(huì)使用OpenGL的繪制函數(shù),3,主要內(nèi)容,填充圖元掃描轉(zhuǎn)換矩形掃描轉(zhuǎn)換多邊形掃描轉(zhuǎn)換扇形區(qū)域區(qū)域填充以圖像填充區(qū)域字符的表示與輸出OpenGL相關(guān)函數(shù),4,4.1 填充圖元,填充（Filling）矩形(Rectangle)多邊形(Polygon)扇形(Ellipse Arc)步驟確定

2、那些像素位于填充圖元的內(nèi)部用指定顏色繪制這些像素兩類方法掃描轉(zhuǎn)換（Scan Converting）: 參數(shù)－>點(diǎn)陣填充（Filling） : 點(diǎn)陣－>點(diǎn)陣,,,,,,,,5,4.2 掃描轉(zhuǎn)換矩形,含義用指定顏色填充矩形內(nèi)部區(qū)域定義矩形的參數(shù)左下角坐標(biāo)(xmin, ymin)右上角坐標(biāo)(xmax, ymax),void FillRectangle(Rectangle *rect,int color){ in

3、t x,y; for(y = rect->ymin; y ymax; y++) for(x = rect->xmin; x xmax; x++) SetPixel(x, y, color);}/*end of FillRectangle() */,,(xmin, ymin),(xmax, ymax),6,4.2 掃描轉(zhuǎn)換矩形,問(wèn)題矩形是簡(jiǎn)單的多邊形，那么為什么要單獨(dú)處理矩形？比一般多邊形可簡(jiǎn)化

4、計(jì)算應(yīng)用非常多，如窗口系統(tǒng)共享邊界如何處理？原則：左閉右開(kāi)，下閉上開(kāi),,,,屬于誰(shuí)？,7,4.3 掃描轉(zhuǎn)換多邊形,多邊形的表示方法頂點(diǎn)表示頂點(diǎn)序列P0P1P2…Pn點(diǎn)陣表示掃描轉(zhuǎn)換多邊形：將頂點(diǎn)表示形式轉(zhuǎn)換成點(diǎn)陣表示形式三種方法：逐點(diǎn)判斷法；掃描線算法；邊緣填充法多邊形分類（只考慮：簡(jiǎn)單多邊形，即多邊形邊不自相交）凸多邊形(convex)：內(nèi)角小于180度凹多邊形(concave)：存在內(nèi)角大于180度,8,

5、4.3 掃描轉(zhuǎn)換多邊形,如何識(shí)別多邊形的凸凹性方法1：觀察多邊形邊的延長(zhǎng)線是否劃分頂點(diǎn)在兩側(cè)方法2：向量的叉積每條邊建立一個(gè)向量，測(cè)試相鄰邊的叉積z坐標(biāo)的正負(fù)（1）如果叉積同號(hào)，那么是凸多邊形（2）如果叉積不同號(hào)，那么是凹多邊形,(E1×E2 )z > 0(E2×E3 )z > 0(E3×E4 )z 0(E5×E6 )z > 0(E6×E1 )z &

6、gt; 0,9,4.3 掃描轉(zhuǎn)換多邊形,向量叉積（Cross Product of Two Vector）,當(dāng)a與b為二維向量時(shí)，a×b 矢量中x，y 分量為0,10,4.3.1 逐點(diǎn)判斷法,基本原理判斷繪圖窗口內(nèi)的像素是否位于多邊形內(nèi)，若是，則用指定顏色繪制該像素問(wèn)題如何判斷點(diǎn)在多邊形的內(nèi)外關(guān)系？射線法累計(jì)角度法*編碼法*,,(xmin, ymin),(xmax, ymax),11,4.3.1 逐點(diǎn)判斷法,算

7、法假設(shè)判斷點(diǎn)是否在多邊形內(nèi)的函數(shù)為IsInside（）,void FillPolygon(Polygon *P, int polygonColor){ int x,y; for(y = ymin;y <= ymax;y++) for(x = xmin;x <= xmax;x++)if(IsInside(P,x,y)) SetPixel(x, y, polygonColor);el

8、se SetPixel(x,y,backgroundColor);}/*end of FillPolygonPbyP()*/,#define MAX 100typedef struct { // 多邊形頂點(diǎn)個(gè)數(shù) int PolygonNum; //多邊形頂點(diǎn)數(shù)組 Point vertexces[MAX]} Polygon; // 多邊形結(jié)構(gòu),12,4.3.1 逐點(diǎn)判斷法,

9、判斷點(diǎn)是否在多邊形內(nèi)－射線法 步驟從待判別點(diǎn) v 發(fā)出射線求與多邊形交點(diǎn)個(gè)數(shù) kk 的奇偶性決定了點(diǎn)與多邊形的內(nèi)外關(guān)系偶數(shù)：外奇數(shù)：內(nèi),v2,13,4.3.1 逐點(diǎn)判斷法,判斷點(diǎn)是否在多邊形內(nèi)－射線法 奇異情況射線在邊上：無(wú)數(shù)個(gè)點(diǎn) 判斷是否與邊同線交點(diǎn)為頂點(diǎn)：算幾個(gè)？異側(cè)：1個(gè)同側(cè)：2個(gè),14,4.3.1 逐點(diǎn)判斷法,逐點(diǎn)判斷掃描轉(zhuǎn)換方法特點(diǎn)程序簡(jiǎn)單測(cè)試點(diǎn)是否在多邊形內(nèi)的算法速度太慢，

10、效率低改進(jìn)逐點(diǎn)判斷法孤立考慮各個(gè)像素與多邊形的內(nèi)外關(guān)系利用內(nèi)部點(diǎn)的連續(xù)性,15,4.3.1 逐點(diǎn)判斷法,思考題 下圖是某油田油井分布圖，已知每口油井的位置（x, y坐標(biāo)值）和產(chǎn)油量，如何求任意多邊形（虛線所示）中的總產(chǎn)油量？,,利用射線法判斷油井是否在多邊形內(nèi)？,16,4.3.2 掃描線算法,英文：Scan-Line Algorithm目標(biāo)利用相鄰像素之間的連貫性，提高算法效率處理對(duì)象：簡(jiǎn)單多邊形非自交多邊形 （邊與

11、邊之間除了頂點(diǎn)外無(wú)其它交點(diǎn)）掃描線(Scanning Line)平行于坐標(biāo)軸的直線一般取平行于X軸區(qū)間：掃描線與邊的交點(diǎn)間的線段,17,4.3.2 掃描線算法,連貫性(Coherence)邊的連貫性(Edge Coherence)某條邊與當(dāng)前掃描線相交，也可能與下一條掃描線相交掃描線的連貫性(Scan-line Coherence)當(dāng)前掃描線與各邊的交點(diǎn)順序與 下一條掃描線與各邊的交點(diǎn)順序可能相同或類似區(qū)間的連貫性(S

12、pan Coherence)同一區(qū)間上的像素取同一顏色屬性,18,4.3.2 掃描線算法,基本原理將整個(gè)繪圖窗口內(nèi)掃描多邊形的問(wèn)題分解到一條條掃描線，只要完成每條掃描線的繪制就實(shí)現(xiàn)了多邊形的掃描轉(zhuǎn)換一條掃描線與多邊形的邊有偶數(shù)個(gè)交點(diǎn)，每2個(gè)點(diǎn)形成一區(qū)間步驟(對(duì)于每一條掃描線)(1)計(jì)算掃描線與邊的交點(diǎn)(2)交點(diǎn)按x坐標(biāo)從小到大排序(3)交點(diǎn)兩兩配對(duì)，填充區(qū)間,19,4.3.2 掃描線算法,計(jì)算交點(diǎn)分類第一類交點(diǎn)：位于

13、同一條邊上的后繼交點(diǎn)--(P2, P4)第二類交點(diǎn)：新出現(xiàn)的邊與掃描線的交點(diǎn)--(P3)計(jì)算：由掃描線y＝e與多邊形的交點(diǎn)遞推計(jì)算掃描線 y＝e＋1的交點(diǎn)第一類交點(diǎn)：x’＝x＋1/m第二類交點(diǎn)： 線段的下端點(diǎn)即為交點(diǎn),P3,P4,P0,P2,P1,20,4.3.2 掃描線算法,計(jì)算交點(diǎn)（續(xù)）交點(diǎn)取整規(guī)則：要求：使生成的像素全部位于多邊形之內(nèi)用于線畫(huà)圖元掃描轉(zhuǎn)換

14、的四舍五入原則導(dǎo)致部分像素位于多邊形之外，從而不可用,掃描轉(zhuǎn)換,位于多邊形內(nèi),21,4.3.2 掃描線算法,取整規(guī)則假定非水平變與掃描線 y=e 相交，交點(diǎn)的橫坐標(biāo)為x規(guī)則1 X為小數(shù)，即交點(diǎn)落于掃描線上兩個(gè)相鄰像素之間 (a)交點(diǎn)位于左邊之上，向右取整 (b)交點(diǎn)位于右邊之上，向左取整,22,4.3.2 掃描線算法,規(guī)則2落在右上邊界的像素不予填充。 具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交

15、區(qū)間左閉右開(kāi),23,4.3.2 掃描線算法,規(guī)則3 掃描線與多邊形的頂點(diǎn)相交時(shí)，采用上開(kāi)下閉及右開(kāi)左閉取交點(diǎn)，保證交點(diǎn)正確配對(duì)。 檢查兩相鄰邊在掃描線的哪一側(cè)。 只要檢查頂點(diǎn)的兩條邊的另外兩個(gè)端點(diǎn)的Y值，兩個(gè)Y值中大于交點(diǎn)Y值的個(gè)數(shù)是0，1，2，來(lái)決定取0，1，2個(gè)交點(diǎn),24,4.3.2 掃描線算法,計(jì)算交點(diǎn)（續(xù)）水平邊不考慮排序掃描線連貫性采用插入排序交點(diǎn)兩兩配對(duì)與區(qū)間繪制區(qū)間連續(xù)性連續(xù)繪制區(qū)

16、間上的像素,,25,4.3.2 掃描線算法,算法實(shí)現(xiàn)－數(shù)據(jù)結(jié)構(gòu)（1）邊的分類表ET （Edge Table）（又稱新邊表）按照邊的下端點(diǎn) y 坐標(biāo)，對(duì)非水平邊進(jìn)行分類的鏈表下端點(diǎn) y 坐標(biāo)值等于i 的邊屬于第i類作用：避免盲目求交,26,4.3.2 掃描線算法,ET定義每條掃描線，對(duì)應(yīng)一個(gè)鏈表鏈表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu),typedef struct {int ymax; float x, deltax; Edge *ne

17、xtEdge; }Edge;,ET的結(jié)點(diǎn)信息：ymax: 邊的上端點(diǎn)的y坐標(biāo)值x：邊的下端點(diǎn)的 x 坐標(biāo)deltax：邊的斜率的倒數(shù)nextEdge: 下一條邊的指針,27,4.3.2 掃描線算法,結(jié)點(diǎn)結(jié)構(gòu)解釋,typedef struct {int ymax; float x, deltax; Edge *nextEdge; }Edge;,float x, deltax; 用于遞推計(jì)算交點(diǎn) x’＝x＋1/m,int

18、 ymax；當(dāng)掃描線 y = e+1 == ymax，說(shuō)明下一條掃描線與此邊不相交,28,4.3.2 掃描線算法,（2）活性邊表AEL(Active Edge List) 存放活性邊的順序鏈表，且按交點(diǎn) x 的值從小到大排序 活性邊：與當(dāng)前掃描線相交的邊 邊結(jié)構(gòu)定義：,typedef struct {int ymax; float x, deltax; Edge *nextEdge; }Edge;,

19、AEL 的結(jié)點(diǎn)信息：ymax: 所交邊的最高掃描線號(hào)x：當(dāng)前掃描線與邊的交點(diǎn)的x坐標(biāo)deltax：邊的斜率的倒數(shù)nextEdge: 下一條邊的指針,29,4.3.2 掃描線算法,實(shí)例,(a) Y=6對(duì)應(yīng)的活性邊表,(b) Y=7對(duì)應(yīng)的活性邊表,30,4.3.2 掃描線算法,算法(Scan-Line Algorithm)1、建立ET；2、將掃描線縱坐標(biāo)y的初值置為ET中非空 元素的最小序號(hào)，如圖中，y=1；3

20、、置AEL為空；4、執(zhí)行下列步驟直至ET和AEL都為空．4.1、如ET中的第y類非空，則將其中的所有 邊取出并插入AEL中；4.2、如果有新邊插入AEL，則對(duì)AEL中各邊排序；4.3、對(duì)AEL中的邊兩兩配對(duì)，（1和2為一對(duì)，3和4為一對(duì)，…），將每對(duì)邊中x坐標(biāo)按規(guī)則取整，獲得有效的填充區(qū)段，再填充．4.4、將當(dāng)前掃描線縱坐標(biāo) y 值遞值1；4.5、將AEL中滿足y = ymax邊刪去（因?yàn)槊織l邊被看作下閉上開(kāi)的）

21、；4.6、對(duì)AEL中剩下的每一條邊的x遞增deltax，即x = x+deltax．,31,4.3.2 掃描線算法,4.3.2 掃描線算法,例子,y=5 y=6 y=7 y=8,AET:y=1 y=2 y=3 y=4,4 4 -1,5 33/4 5/4 ^,5 19/2 5/4 ^,4 3 -1

22、,8 2 0,,,,,,,,,,5 43/4 5/4 ^,8 2 0,8 2 0,8 2 0,11 12 0 ^,11 12 0 ^,8 7 -5,11 7 5/4,11 12 0 ^,11 33/4 5/4,11 12 0 ^,32,4.3.2 掃描線算法,思考問(wèn)題算法如何體現(xiàn)連貫性？對(duì)凸多邊形而言，算法是否可以簡(jiǎn)化？如何簡(jiǎn)化？對(duì)三角形而言，算法如何簡(jiǎn)化？,

23、三角形廣泛應(yīng)用于物體建模,33,思考題,思考問(wèn)題 如何高效計(jì)算平面上 n 條線段的交點(diǎn)？,利用掃描線和邊的連貫性，時(shí)間復(fù)雜性m×n’ （m為掃描線條數(shù), n’為與掃描線相交邊的平均條數(shù)， n’ << n）,一般方法：兩兩求交點(diǎn)，時(shí)間復(fù)雜性 n2,34,4.3.3 邊緣填充算法*,寫(xiě)像素的邏輯操作主要包括：拷貝、異或（求余）等寫(xiě)模型：像素的顏色與源像素及像素當(dāng)前顏色相關(guān),35,4.

24、3.3 邊緣填充算法*,求余運(yùn)算假定A為一個(gè)正整數(shù)，則 M 的余定義為 A – M, 記為 求余運(yùn)算可用異或邏輯運(yùn)算實(shí)現(xiàn)例性質(zhì),36,4.3.3 邊緣填充算法*,求余運(yùn)算（續(xù)）應(yīng)用：光標(biāo)移動(dòng)、橡皮筋線和加亮菜單等操作如：交互繪制線段時(shí)的橡皮筋線,交互方式：（1）點(diǎn)擊鼠標(biāo)左鍵輸入線段的一個(gè)端點(diǎn)（2）點(diǎn)擊右鍵（或左鍵）輸入另一端點(diǎn)（3）鼠標(biāo)移動(dòng)過(guò)程中繪制瞬時(shí)線段,注意：不能采用直接繪制（復(fù)制、拷貝）方法

25、,37,4.3.3 邊緣填充算法*,邊緣填充算法光柵圖形中，如果某區(qū)域已著上值為M的顏色值后，做偶數(shù)次求余運(yùn)算，該區(qū)域顏色不變；而做奇數(shù)次求余運(yùn)算，則該區(qū)域顏色變?yōu)橹禐?的顏色這一規(guī)律應(yīng)用于多邊形掃描轉(zhuǎn)換，稱為邊緣填充算法。算法基本思想對(duì)于每條掃描線和每條多邊形邊的交點(diǎn)，將該掃描線上交點(diǎn)右方的所有像素取余M為填充色，A為當(dāng)前背景色,38,4.3.3 邊緣填充算法*,算法1（以掃描線為中心的邊緣填充算法）1、將當(dāng)前掃

26、描線上的所有像素著上值為 顏色；2、求余： for(i=0; i<=m; i++) 在當(dāng)前掃描線上，從橫坐標(biāo)為xi的交點(diǎn)向右求余；,圖中次序：x0, x1, x2, x3,次序可以任意,39,4.3.3 邊緣填充算法*,算法2（以邊為中心的邊緣填充算法）1、將繪圖窗口的背景色置為 ；2、對(duì)多邊形的每一條非水平邊做：從該邊上的每個(gè)像素開(kāi)始向右求余,40,特點(diǎn)適合用于具有幀緩存的圖形系

27、統(tǒng)。處理后，按掃描線順序讀出幀緩存的內(nèi)容，送入顯示設(shè)備優(yōu)點(diǎn)：算法簡(jiǎn)單缺點(diǎn)：對(duì)于復(fù)雜圖形，每一像素可能被訪問(wèn)多次，輸入/輸出的量比掃描線算法大得多,4.3.3 邊緣填充算法*,41,扇形區(qū)域的描述圓的半徑R起始角度：?1終止角度：?2原理：同掃描轉(zhuǎn)換多邊形對(duì)每條掃描線，首先計(jì)算與扇形區(qū)域邊界的交點(diǎn)，再用指定顏色繪制繪制配對(duì)交點(diǎn)間的像素問(wèn)題如何確定掃描線與直線段和圓弧段的交點(diǎn)及相交順序？,4.4 掃描轉(zhuǎn)換扇形區(qū)域,42,方

28、法：分類按點(diǎn) P1(x, y) 和P2(x, y) 點(diǎn)所處象限的不同，需要將扇形區(qū)域分成4×4=16種情況 假設(shè) P1 點(diǎn)落在第一象限 掃描線和區(qū)域邊界只有2個(gè)交點(diǎn)扇形區(qū)域的掃描轉(zhuǎn)換分四種情況(1) P2落在第一象限區(qū)域：OP1A和AP1P2,4.4 掃描轉(zhuǎn)換扇形區(qū)域,43,(2)P2落在第二象限，此時(shí)又分為兩種情況 當(dāng) 時(shí)三個(gè)區(qū)域： OAP1、AP1BP2和P2BC當(dāng)

29、 時(shí)三個(gè)區(qū)域： OAP2、AP1BP2和P1BC,4.4 掃描轉(zhuǎn)換扇形區(qū)域,44,(3) P2 落在第三象限三個(gè)區(qū)域： P1CA、BOP1A和P2OB(4) P2落在第四象限三個(gè)區(qū)域： AP1D、BOP1 A、 CP2OB和CEP2,4.4 掃描轉(zhuǎn)換扇形區(qū)域,45,遺留問(wèn)題：當(dāng) P1 落在其它區(qū)域時(shí)?P1 落在第二、三、四象限時(shí)，將扇形區(qū)域繞坐標(biāo)原點(diǎn)順時(shí)針旋轉(zhuǎn)90度

30、（180，270），使 P1 落在第1象限掃描轉(zhuǎn)換再逆時(shí)針旋轉(zhuǎn)90度（180，270）,4.4 掃描轉(zhuǎn)換扇形區(qū)域,46,區(qū)域：點(diǎn)陣表示的圖形，像素集合表示方法：內(nèi)點(diǎn)表示、邊界表示內(nèi)點(diǎn)表示枚舉出區(qū)域內(nèi)部的所有像素內(nèi)部的所有像素為同一個(gè)顏色邊界像素與內(nèi)部像素的顏色不同邊界表示枚舉出邊界上所有的像素邊界上的所有像素為同一顏色內(nèi)部像素與邊界像素的顏色不同,4.5 區(qū)域填充,47,種子填充法對(duì)區(qū)域重新著色的過(guò)程

31、 將指定的顏色從種子點(diǎn)開(kāi)始擴(kuò)展到整個(gè)區(qū)域區(qū)域填充算法要求區(qū)域是連通的,4.5 區(qū)域填充,48,連通性4連通區(qū)域：區(qū)域中任意兩點(diǎn)可通過(guò)上下左右四個(gè)方向互相 到達(dá)8連通區(qū)域：區(qū)域中任意兩點(diǎn)可通過(guò)上下左右和對(duì)角線八 個(gè)方向互相到達(dá),4.5 區(qū)域填充,49,4.5 區(qū)域填充,4連通與8連通區(qū)域的區(qū)別連通性： 4連通可看作8連通區(qū)域，但對(duì)邊界有要求不同依據(jù)區(qū)域內(nèi)點(diǎn)能否訪問(wèn)到區(qū)域外的點(diǎn)，對(duì)邊界的要求是4連通區(qū)域，邊界只要

32、8連通即可8連通區(qū)域，邊界必須是4連通例：如左圖（1）4連通區(qū)域，邊界為 像素（2）8連通區(qū)域，邊界為 和 像素,,,,50,4.5.1 種子填充法,種子填充算法（泛濫填充：flood-fill） （1）內(nèi)點(diǎn)表示的4連通區(qū)域種子P(x,y)，原色oldColor，新顏色newColor方法：先判斷P(x, y)的顏色，若其值不等于oldColor，說(shuō)明該像素位于區(qū)域外，或已設(shè)置為newC

33、olor，算法結(jié)束；否則，置像素顏色為newColor，再對(duì)其相鄰的上下左右四個(gè)像素分別作為種子作上述遞歸處理。,void FloodFill4(int x,int y,int oldColor,int newColor){ if(GetPixel(x,y) == oldColor) { SetPixel(x,y,newColor); FloodFill4(x,y+1,oldColor,newColor);

34、 FloodFill4(x,y-1,oldColor,newColor); FloodFill4(x-1,y,oldColor,newColor); FloodFill4(x+1,y,oldColor,newColor); }}/*end of FloodFill4()*/,51,,4.5.1 種子填充法,①FloodFill4(x, y+1, oldColor, newColor);②FloodFill

35、4(x, y-1, oldColor, newColor);③FloodFill4(x-1, y, oldColor, newColor);④FloodFill4(x+1, y, oldColor, newColor);,52,（2）邊界表示的4連通區(qū)域,4.5.1 種子填充法,void BoundaryFill4(int x, int y, int oldColor, int newColor){//oldColor邊界像素顏色

36、 int color; color = GetPixel(x, y); if((color != oldColor) && (color != newColor)) { SetPixel(x, y, newColor); BoundaryFill4(x,y+1,oldColor,newColor); BoundaryFill4(x,y-1,oldColor,ne

37、wColor); BoundaryFill4(x-1,y,oldColor,newColor); BoundaryFill4(x+1,y,oldColor,newColor); }}/*end of BoundaryFill4( ) */,53,缺點(diǎn)有些像素需要重復(fù)判斷，降低算法效率棧結(jié)構(gòu)占空間遞歸執(zhí)行，算法簡(jiǎn)單，但效率不高，區(qū)域內(nèi)每一像素都引起一次遞歸，進(jìn)/出棧，費(fèi)時(shí)費(fèi)內(nèi)存改進(jìn)減少遞歸次數(shù)，提高效

38、率方法之一使用掃描線填充算法,4.5.1 種子填充法,54,4.5.2 掃描線算法*,掃描線算法目標(biāo)：減少遞歸層次適用于內(nèi)點(diǎn)表示的4連通區(qū)域基本過(guò)程：當(dāng)給定種子點(diǎn)時(shí)，首先填充種子點(diǎn)所在的掃描線上的位于給定區(qū)域的一個(gè)區(qū)段，然后確定與這一區(qū)段相通的上下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來(lái)。反復(fù)這個(gè)過(guò)程，直到填充結(jié)束,55,4.5.2 掃描線算法*,算法步驟1、初始化 ：將種子區(qū)段壓入堆棧2、出棧：如果堆棧為空，

39、則算法結(jié)束；否則取棧頂元素(x,y)作為種子點(diǎn)3、區(qū)段填充：從種子點(diǎn)(x, y)開(kāi)始沿縱坐標(biāo)為y的掃描行向左右兩個(gè)方向逐個(gè)像素填色，直到邊界為止4、定范圍：以 [xLeft, xRight]為(3)得到的區(qū)段 5、進(jìn)棧：分別在與當(dāng)前掃描線相鄰的上下掃描線上，確定位于區(qū)間[xLeft, xRight]內(nèi)的區(qū)段。如果區(qū)段內(nèi)的像素顏色值為newColor或boundaryColor，則轉(zhuǎn)到（2）區(qū)段壓入堆棧，轉(zhuǎn)到（2）,56,例,

40、4.5.2 掃描線算法*,像素中的序號(hào)標(biāo)指它所在區(qū)段位于堆棧中的位置,57,多邊形掃描轉(zhuǎn)換與區(qū)域填充方法比較基本思想不同前者：頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示后者：只改變區(qū)域內(nèi)填充顏色，沒(méi)有改變表示方法對(duì)邊界的要求不同前者：掃描線與多邊形邊界交點(diǎn)個(gè)數(shù)為偶數(shù)后者：區(qū)域封閉，防止遞歸填充跨界基本的條件不同前者：從邊界頂點(diǎn)信息出發(fā)后者：區(qū)域內(nèi)種子點(diǎn),4.5.3 掃描轉(zhuǎn)換與區(qū)域填充的比較,58,填充方式（1）均勻著色（2）位圖不透明(

41、3)位圖透明(4)像素圖填充在確定區(qū)域內(nèi)的像素后，查詢它對(duì)應(yīng)的位圖或圖像中的單元，再以該單元的值按填充方式的不同顯示該像素方法(1)均勻著色方法：將圖元內(nèi)部像素置成同一顏色(2)位圖不透明：若像素對(duì)應(yīng)的位圖單元為1，則以前景色顯示該像素；若為0，則以背景色顯示該像素；(3)位圖透明：若像素對(duì)應(yīng)的位圖單元為1，則以前景色顯示該像素；若為0，則不做任何處理。(4)像素圖填充：以像素對(duì)應(yīng)的像素圖單元的顏色值顯示該像素。,4.6 以

42、圖像填充區(qū)域,59,基本問(wèn)題建立區(qū)域與圖像間的對(duì)應(yīng)關(guān)系方法1：建立整個(gè)繪圖空間與圖像空間的1-1映射,4.6 以圖像填充區(qū)域,圖像（紋理）,,,繪圖空間,60,例 適用：動(dòng)畫(huà)中漫游圖像，如透過(guò)車(chē)窗看外景,4.6 以圖像填充區(qū)域,61,方法2：建立區(qū)域局部坐標(biāo)空間與圖像空間的1-1映射,4.6 以圖像填充區(qū)域,適用：圖像作為區(qū)域表面屬性的情況，例如，桌面與其上的木紋,62,字符集ASCII碼：128個(gè)字符GB23

43、12－80：漢字6763個(gè)，682個(gè)圖形符號(hào)點(diǎn)陣字體存儲(chǔ)（壓縮與非壓縮）顯示：檢索與寫(xiě)緩沖矢量字體表示：筆畫(huà)組成曲線（參數(shù)）掃描轉(zhuǎn)換：參數(shù)到點(diǎn)陣顯示：1、由編碼檢索 2、掃描轉(zhuǎn)換存儲(chǔ)：空間少 （windows下的仿宋體庫(kù)： SIMFANG.TTF 為3904K）,4.7 字符的表示與輸出,63,4.8 OpenGL相關(guān)函數(shù),區(qū)域函數(shù)（填充作用）矩形函數(shù)：glRect[i|s|f|d]{v}()glBegin()

44、中的參數(shù) GL_POLYGON、GL_TRIANGLES、 GL_TRIANGLE_STRIP、 GL_TRIANGLE_FAN三角形的三種繪制參數(shù),int p1[]={20,100},p2[]={50,50};int p3[]={110,50},p4[]={140,100};int p5[]={110,150},p6[]={50,150};glBegin(GL_TRIANGLES); glVertex2i

45、v(p1); glVertex2iv(p2); glVertex2iv(p3); glVertex2iv(p4); glVertex2iv(p5); glVertex2iv(p6);glEnd();,GL_TRIANGLE_STRIP,,,GL_TRIANGLES,GL_TRIANGLE_FAN,,p1,p1,p1,64,菜單函數(shù)int glutCreateMenu(void (*func)(int value));//

46、創(chuàng)建菜單void glutAddMenuEntry(char *name, int value);//添加菜單項(xiàng)void glutAddSubMenu(char *name, int menu);//添加子菜單glutAttachMenu(int button);例：,4.8 OpenGL相關(guān)函數(shù),void MenuInit(){ int sub_menu1 = glutCreateMenu(objectMenu);

47、 glutAddMenuEntry("直線",11); glutAddMenuEntry("多邊形",12); glutCreateMenu(topMenu); glutAddSubMenu("圖形",sub_menu1); glutAddMenuEntry("退出",2); glutAttachMenu(GL

48、UT_RIGHT_BUTTON);},void objectMenu(int id){ if (id==11) GraphicsType = 11; else if (id==12) GraphicsType = 12; else GraphicsType = 0;}void topMenu(int id){ if (id==2) exit(0);},65,線框圖與填充圖函數(shù)：glPloygonMode(f

49、ace，displayMode)face：指定前后面?？蛇x值：GL_FRONT、GL_BACK和GL_FRONT_AND_BACKdisplayMode：GL_FILL和GL_LINE,4.8 OpenGL相關(guān)函數(shù),void display (void){ glClearColor (1.0, 1.0, 1.0, 0.0); glClear (GL_COLOR_BUFFER_BIT); glPolygonMode

50、(GL_FRONT, GL_LINE); glBegin(GL_POLYGON); glColor3f(1.0,0,0); glVertex2f(0.5,0); glVertex2f(-0.5,0.5); glVertex2f(-0.5,-0.5); glVertex2f(0.6,-0.5); glEnd(); glFlush();},前向面：

51、頂點(diǎn)序列逆時(shí)針順序排列,66,顏色插值模式函數(shù)：glShadeModel(mode)Mode: GL_FLAT和GL_SMOOTH例：,4.8 OpenGL相關(guān)函數(shù),void display (void){ glClearColor (1.0, 1.0, 1.0, 0.0); glClear (GL_COLOR_BUFFER_BIT); glShadeModel(GL_FLAT);//默認(rèn)為GL_SMO

52、OTH glBegin(GL_POLYGON); glColor3f(1,0,0); glVertex2f(-0.5,0.5); glColor3f(0,1,0); glVertex2f(-0.5,-0.5); glColor3f(0,0,1); glVertex2f(0.5,-0.5); glColor3f(1,1,1); glVertex2f(0.5,0.5); glEnd();

53、 glFlush();},GL_FLAT方式下以第1個(gè)點(diǎn)顏色填充,67,頂點(diǎn)數(shù)組原因：復(fù)雜圖形需要很多坐標(biāo)描述，導(dǎo)致函數(shù)調(diào)用量大增，影響程序的執(zhí)行效率采用頂點(diǎn)數(shù)組減少函數(shù)調(diào)用方法調(diào)用函數(shù)glEnableClientState(GL_VERTEX_ARRAY), 激活頂點(diǎn)數(shù)組特性調(diào)用glVertexPointer指定頂點(diǎn)坐標(biāo)的位置和數(shù)據(jù)格式使用與數(shù)組相關(guān)的函數(shù)繪制圖形,4.8 OpenGL相關(guān)函數(shù),68,例：glCl

54、ear (GL_COLOR_BUFFER_BIT);glColor3f (1.0, 0.0, 0.0);vertex2 pt[]={{20,100},{50,50},{110,50},{140,100},{110,150},{50,150}};glEnableClientState(GL_VERTEX_ARRAY);glVertexPointer(2,GL_INT,0,pt);GLubyte vertIndex[]={0

55、,1,2,3,4,5};glDrawElements(GL_TRIANGLES,24,GL_UNSIGNED_BYTE, vertIndex); glFlush ( );,4.8 OpenGL相關(guān)函數(shù),69,4.8 OpenGL相關(guān)函數(shù),寫(xiě)像素模式16種，默認(rèn)方式為GL_COPY模式改變時(shí)，需要調(diào)用glEnable（GL_COLOR_LOGIC_OP）設(shè)置模式：glLogicOp（GL_XOR）例：異或模式,背景,

56、正方形,70,4.8 OpenGL相關(guān)函數(shù),填充圖案函數(shù)啟用函數(shù)：glEnable（GL_POLYGON_STIPPLE）關(guān)閉函數(shù)：glDisable（ GL_POLYGON_STIPPLE）設(shè)置掩模（mask）：glPolygonStipple（fillPattern） 注意：filePattern類型為GLubyte，大小為32×32,GLubyte fillPattern[]=

57、 {0x96,0x96,0x96,0x96, 0x84,0x84,0x84,0x84, 0x48,0x48,0x48,0x48, 0x20,0x20,0x20,0x20, 0x10,0x10,0x10,0x10, 0x10,0x10,0x10,0x10, 0x18,0x18,0x18,0x18, 0x64,0

58、x64,0x64,0x64, 。。。。(重復(fù)3次) },71,4.8 OpenGL相關(guān)函數(shù),OpenGL位圖函數(shù)void glRasterPos{234}{SIFD}[V](TYPE x, TYPE y, TYPE z, TYPE w);設(shè)置當(dāng)前所畫(huà)位圖或圖像的原點(diǎn)glBitmap(width, height, x0,y0,xO

59、ffset,yOffset,bitShape)設(shè)定當(dāng)前光柵位置該函數(shù)顯示二值位圖。bitShape中的元素值為0或1，當(dāng)為1時(shí)，用設(shè)定的顏色繪制對(duì)應(yīng)的像素，否則對(duì)應(yīng)像素不受影響位圖的存儲(chǔ)模式：字節(jié)glPixelStorei (GL_UNPACK_ALIGNMENT, 1 ) ;,72,4.8 OpenGL相關(guān)函數(shù),程序,void display(){ // 最好放在初始化函數(shù)中 glPixelStorei (GL_

60、UNPACK_ALIGNMENT, 1); glColor3f (0.0, 0.0, 0.0); glRasterPos2i (100, 200); glBitmap (8, 12, 0.0, 0.0, 20.0, 20.0, rasters); glColor3f (1.0, 0.0, 0.0); glRasterPos2i (120, 220); glBitmap (8, 12,

61、 0.0, 0.0, 0.0, 0.0, rasters); glColor3f (0.0, 0.0, 1.0); glRasterPos2i (150, 200); glBitmap (8, 12, 0.0, 0.0, 0.0, 0.0, rasters); glFlush ( );},,,,,,,,,,rasters,73,4.8 OpenGL相關(guān)函數(shù),繪制字符OpenGL基本庫(kù)：位圖方法，

62、需要自己創(chuàng)建字庫(kù)GLUT工具包：位圖和輪廓字體位圖字符函數(shù)：glutBitmapCharacter(font, character)font:指定字型，常量（如GLUT_BITMAP_8_BY_13）Character：字符的ASCII碼值輪廓字符函數(shù)：glutStrokeCharacter(font, character)font:指定字型，常量（如GLUT_STROKE_ROMAN）Character：字符的ASCII

63、碼值位圖和輪廓字符比較前者速度快，后者放大縮小不變形,74,4.8 OpenGL相關(guān)函數(shù),程序,void display(){ glColor3f (1.0, 0.0, 0.0); glRasterPos2i (50, 50); glutBitmapCharacter (GLUT_BITMAP_9_BY_15,66); glRasterPos2i (80, 50); glutBitmapCharact

64、er (GLUT_BITMAP_TIMES_ROMAN_10,66); glColor3f (0.0, 0.0, 1.0); glPushMatrix(); glTranslatef(50,100,0);glScalef(0.2,0.2,1); glutStrokeCharacter(GLUT_STROKE_ROMAN,66); glPopMatrix(); glTranslatef(100,1

65、00,0); glScalef(0.6,0.6,1); glutStrokeCharacter(GLUT_STROKE_ROMAN,66); glutSwapBuffers();},75,小結(jié),多邊形的掃描轉(zhuǎn)換點(diǎn)是否在區(qū)域內(nèi)的判斷方法（射線法）掃描線算法（思想、步驟和算法實(shí)現(xiàn)）多邊形的區(qū)域填充種子填充（連通性）扇形區(qū)域的掃描轉(zhuǎn)換字符的繪制方法OpenGL函數(shù),76,作業(yè),1 、多邊形掃描轉(zhuǎn)換的

66、掃描線算法利用了掃描線的連貫性和邊的連貫性，在數(shù)據(jù)結(jié)構(gòu)和算法中各體現(xiàn)在何處？2、一個(gè)多邊形的頂點(diǎn)坐標(biāo)如下圖所示。 （a）寫(xiě)出邊的分類表 （b）說(shuō)明掃描線y＝6，7，8，9和10時(shí)，哪些邊是活性邊。并給出活性邊表。,77,作業(yè),3、內(nèi)點(diǎn)表示的區(qū)域和邊界表示的區(qū)域在填充時(shí)有什么不同？4、根據(jù)三角形的特殊性，如何簡(jiǎn)化掃描轉(zhuǎn)換三角形的掃描線算法。,78,上機(jī)題1：補(bǔ)充,添加填充圖元的功能填充多邊形多邊形交互輸入、顏色定義和填