【文章內(nèi)容簡介】 S。 分析五種情形可知 : (320)式的 di值符號可由 (321)式等價表示 : di=D(S)+D(T) (321) 為簡化 di計算 , 推導 di的增量形式 : ? ? ? ? ? ?2 2 22 2 21 1 1i i i i id x y r x y r? ? ? ? ? ? ? ? ?《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 35 再以 i+1代 i， 得 di+1=(xi+1+1)2+yi+12r2+(xi+1+1)2+(yi+11)2r2 若 di＜ 0,選 S,即有 xi+1=xi+1, yi+1=yi, di+1=di+4xi+6 (322) 若 di≥0,選 T, xi+1=xi+1, yi+1=yi1, di+1=di+4(xiyi)+10 (323) 當 i=0， (xi,yi)=(0,r),初始值為 d0=32r (324) 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 36 該算法只包含整數(shù)運算 ， 運算速度很快 。 Bresenhem畫圓算法的程序形式類似圖 311的中點畫圓算法 ， 只要將后者中的 d初始值和條件中的兩個“ d+”語句的內(nèi)容作相應修改 。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 37 思考 ： ?幾種算法的共同點，給予我們什么啟發(fā)？ ?遞推； ?避免乘除運算、用整數(shù)運算； ?硬件實現(xiàn)方法； ?算法的應用領域。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 38 OpenGL 畫點函數(shù) glBegin(GL_POINTS)。 glVertex*()。 glEnd()。 glBegin(GL_POINTS)。 glVertex2i(50,100)。 glVertex2i(75,150)。 glVertex2i(100,200)。 glEnd()。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 39 int point1[]={50,100}。 int point2[]={75,150}。 int point3[]={100,200}。 glBegin(GL_POINTS)。 glVertex2iv(point1)。 glVertex2iv(point2)。 glVertex2iv(point3)。 glEnd()。 glBegin(GL_POINTS)。 glVertex3f(,)。 glVertex3f(,188,34)。 glEnd()。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 40 OpenGL 畫線函數(shù) glBegin(GL_LINES)。 glVertex2iv(p1)。 glVertex2iv(p2)。 glVertex2iv(p3)。 glVertex2iv(p4)。 glVertex2iv(p5)。 glEnd() int p1[]={50,100}。 int p2[]={100,100}。 int p3[]={100,50}。 int p4[]={50,50}。 int p5[]={150,100}。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 41 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 42 多邊形 ?First, the edges of OpenGL polygons can39。t intersect ?Second, OpenGL polygons must be convex ?polygons with holes can39。t be described. 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 43 glBegin(GL_POLYGON)。 glVertex2f(, )。 glVertex2f(, )。 glVertex2f(, )。 glVertex2f(, )。 glVertex2f(, )。 glEnd()。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 44 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 45 區(qū)域填充 區(qū)域 是指一組相鄰而又連通、并具有相同屬性的像素集。 在區(qū)域內(nèi)，生成某一屬性的實心或圖案的過程稱為 區(qū)域填充 。 光柵系統(tǒng)有 兩種區(qū)域填充算法 ： 一種是 掃描線填充算法 ， 主要用于填充多邊形 、 圓 、 橢圓以及其它簡單曲線所圍成的封閉區(qū)域； 另一種是 種子填充算法 ， 適用于具有復雜形狀邊界的區(qū)域填充 。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 46 掃描線多邊形填充算法 按順序計算掃描線與多邊形的相交區(qū)域，用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。 P3(11,3) P4(11,8) P2(5,1) P1(2,2) P6(2,7) P5(5,5) 例如， y=6的掃描線與多邊形有四個交點，顯然，第 1與第 第 3與第 4間的區(qū)域落在多邊形內(nèi)，這些區(qū)間的像素填充預期的顏色。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 47 填充算法四個步驟： P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) (1) 求交： 計算掃描線與多邊形每個邊的交點。 (2) 排序： 把所求出的交點按 x遞增（減）的順序排序。 (3) 交點配對： 第一與第二，第三與第四等等，每對交點代表掃描線與多邊形的一個相交區(qū)域。 (4) 區(qū)間填色： 把相交區(qū)域內(nèi)的象素設置成多邊形的顏色，把相交區(qū)域外的象素設置成背景色 。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 48 （ 1） 掃描線過頂點時 ,如何確定交點個數(shù)？ P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) 2 4 6 8 幾個特殊問題 多邊形頂點的計數(shù)方法 ：任取一頂點 ,取過該頂點兩條邊的另外兩個端點的 yi(i=1,2)。計算 yiy(y為該頂點的坐標值 )，按大于 0的次數(shù)確定該頂點是計零次、一次，還是兩次。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 49 1個交點 0個交點，不填充 2個交點，填充 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 50 （ 2）多邊形邊界上的象素的取舍問題。 P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) 2 4 6 8 幾個特殊問題 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 51 掃描線與水平邊界線重合時： 理論上 ,邊界線不用考慮填充 ,也無需求交 。 但為使算法在處理問題時保持一致 ， 將 前述的頂點計數(shù)方法用于多邊形水平邊的頂點 ， 該水平邊界線是否填充取決于兩頂點的計數(shù)結(jié)果 。 按上述頂點計數(shù)方法 ， 多邊形上方的水平邊界線將不被填充；多邊形非水平邊的局部最高的頂點計數(shù)為零次不被填充 。 算法保證 多邊形填充時邊界 “ 下閉上開 ” ,同理規(guī)定多邊形邊界 “ 左閉右開 ” ；避免多邊形在填充前后因邊界上像素的取舍而導致形狀和面積的改變 。 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 52 (3)算法的效率 活性邊和活性邊表： 把與當前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點 x坐標遞增的順序存儲在一個鏈表中，稱此鏈表為活性邊表。 P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) 2 4 6 8 y=6 活性邊表 y=7 活性邊表 P6P1 P5P6 P4P5 P3P4 P4P5 P3P4 2 0 7 7 7 2 8 11 0 8 9 2 8 8 0 11 ?x ymax x 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 53 y=6 活性邊表 y=7 活性邊表 P6P1 P5P6 P4P5 P3P4 P4P5 P3P4 2 0 7 7 7 2 8 11 0 8 9 2 8 8 0 11 ?x ymax x 邊的連貫性和掃描線的連貫性： 活性邊表的每個結(jié)點存放對應邊的有關(guān)信息： x當前掃描線與邊的交點； ?x從當前掃描線到下一條掃描線之間的 x增量 ymax邊所交的最高掃描線號 P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) 2 4 6 8 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 54 0 1 2 3 4 5 6 7 8 P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) 2 4 6 8 5 3 2 P1P2 5 3 3 P2P3 2 0 7 P1P6 11 0 8 P3P4 5 2 8 P4P5 5 7 P5P6 為了方便活性邊表的建立和修改，還需建立一張新邊表。 邊的 y的最小值對應的 x值，x的增量， y的最大值 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 55 Polygonfill(polydef,color) int color。 多邊形定義 polydef。 { for(各條掃描線 i） { 初始化新邊表表頭指針 NET[i]。 把 ymin＝ i 的邊放進新邊表 NET[i]。 } y＝ 最低掃描線號； 初始化活性邊表 AET為空； 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 56 for(各條掃描線 i） { 把新邊表 NET[i]中的邊結(jié)點用插入排序法插入 AET 表，使其按 x坐標升序排列； 遍歷 AET表，把配對的交點之間的區(qū)域（左閉右開）上的 象素（ x,y)， 用 drawpiexl(x,y,color)改寫象素顏色； 遍歷 AET表，把 Ymax=i的結(jié)點從 AET表中 刪除 ， 并把 Ymaxi 結(jié)點的 x值遞增 ?x。 } } 此邊不再與 掃描線相交 求下一條掃描 線與邊的交點 Ymax=i+1 《圖形學與虛擬環(huán)境》 鄭州大學信息工程學院 趙新燦 57 基本思想 : 從區(qū)域內(nèi)部已定義新值的某像素 (種子 )開始 ,搜索與該種子相鄰且位于區(qū)域內(nèi)的像素 ,該像素為新的種子；不斷地遞歸搜索 ,逐個像素填充所需顏色 ,直到填充完區(qū)域邊界內(nèi)的所有像素為止。 種子填充算法 (1) 邊界填充算法 如果采用邊界定義區(qū)域 ， 邊