【正文】 )。 a=5， b=2， twob=4， twoab=6， ( |k|1 )， d2(初始 d0)=1 i 1 0 1 2 3 4 (xi+1， yi+1) (1， 2) (1， 3) (2， 4) (2， 5) (3， 6) (3， 7) di+1 1 3 3 1 5 1 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 20 Bresenham 畫 線算法 是計算機圖形學(xué)領(lǐng)域中應(yīng)用最廣泛的直線掃描轉(zhuǎn)換算法。 (1)直線斜率 0 ＜ k ＜ 1 情形 x的變化率比 y的變化率大，約定每次 x方向變化一個象素單位，相應(yīng) y方向的變化量為 0或1個象素單位?，F(xiàn)在要決定下一個像素是S(xi+1,yi),還是 T(xi+1,yi+1)? 若 st, 則 S靠近直線 , 應(yīng)該選擇 S。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 22 計算判別式 : 理論直線上點 Q坐標(biāo)為 y= k(xi+1)+b。 t=(yi+1)y=(yi+1)k(xi+1)b 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 23 st=2k(xi+1)2yi+2b1 由于 k=△ y／ △ x, △ x=x2x1,△ y=y2y1, 代入 ， 記di=△ x(st),得到 di =2△ yyi+(2△ y△ x+2b△ x) (311) 因為△ x＞ 0, 故 di與 (st)同號 。為得到 di的增量形式 , 以 i+1代式 (311)的 i， 得 di+1=2△ yyi+1+(2△ y△ x+2b△ x) (312) 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 24 將 (312)減去 (311),且 xi+1=xi+1， 得 di+1=di+2△ y2△ x(yi+1yi) (313) 其中 , yi+1yi=0或 1 取決于判別因子 di值的符號 。該算法不僅適用于光柵圖形顯示器顯示圖元，還適用于數(shù)字繪圖儀的圖元輸出。?y=8。 因為圓的對稱特性。 圓生成算法 中點畫圓算法 X Y 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 28 P(xi,yi) S(xi+1,yi) T(xi+1,yi1) M 設(shè)與圓弧最近的 x=xi處的當(dāng)前像素為 P(xi,yi),下一個像素是其正右方的 S(xi+1,yi),還是右下方的 T(xi+1,yi1)更接近圓弧 ? 定義函數(shù) : F(x,y)=x2+y2r2 ＞ 0時 ,點 (x,y)在圓邊界外 則 F(x,y) = 0時 ,點 (x,y)在圓邊界上 ＜ 0時 ,點 (x,y) 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 29 S、 T的中點 M(xi+1,)處求值 ,并令判別式 : di=F(M)=F(xi+1,)=(xi+1)2+()2r2 di＞ 0: M在圓外 ， 取與圓弧更近的右下方像素 T； di=0 : M在圓上 ,任取 T或 S, 約定取右下方像素 T。 當(dāng) di＜ 0時 ,取正右方的下一個像素 ,得下一個判別式 : di+1=F(xi+2,)=di+2xi+3 (317) 若 di≥0, T為下一個像素 。 e為整數(shù) ， e＜ e＜ 0。再把光柵化所得像素位置作逆平移變換 . 圖 311算法中 , 先計算中心 (xc,yc)不在坐標(biāo)原點的 1/8圓弧像素點 ,再利用對稱性 , 完成整圓畫法 。 x++。 x++。} /* 取當(dāng)前像素的右下方像素 */ circlepoints(xc,yc,x,y,color)。 2x0=0。 A B C D E P(xi,yi) S(xi+1,yi) T(xi+1,yi1) 理論圓弧與侯選像素 S、 T之間的關(guān)系存在五種 (從 A到 E)可能情況 。否則 ,選像素 S。 分析五種情形可知 : (320)式的 di值符號可由 (321)式等價表示 : di=D(S)+D(T) (321) 為簡化 di計算 , 推導(dǎo) di的增量形式 : ? ? ? ? ? ?2 2 22 2 21 1 1i i i i id x y r x y r? ? ? ? ? ? ? ? ?《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 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) 當(dāng) i=0， (xi,yi)=(0,r),初始值為 d0=32r (324) 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 36 該算法只包含整數(shù)運算 ， 運算速度很快 。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 37 思考 ： ?幾種算法的共同點，給予我們什么啟發(fā)？ ?遞推； ?避免乘除運算、用整數(shù)運算； ?硬件實現(xiàn)方法； ?算法的應(yīng)用領(lǐng)域。 glVertex*()。 glBegin(GL_POINTS)。 glVertex2i(75,150)。 glEnd()。 int point2[]={75,150}。 glBegin(GL_POINTS)。 glVertex2iv(point2)。 glEnd()。 glVertex3f(,)。 glEnd()。 glVertex2iv(p1)。 glVertex2iv(p3)。 glVertex2iv(p5)。 int p2[]={100,100}。 int p4[]={50,50}。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 41 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 42 多邊形 ?First, the edges of OpenGL polygons can39。t be described. 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 43 glBegin(GL_POLYGON)。 glVertex2f(, )。 glVertex2f(, )。 glEnd()。 在區(qū)域內(nèi)，生成某一屬性的實心或圖案的過程稱為 區(qū)域填充 。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 46 掃描線多邊形填充算法 按順序計算掃描線與多邊形的相交區(qū)域，用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 47 填充算法四個步驟： P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) (1) 求交： 計算掃描線與多邊形每個邊的交點。 (3) 交點配對： 第一與第二，第三與第四等等，每對交點代表掃描線與多邊形的一個相交區(qū)域。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 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)。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 49 1個交點 0個交點，不填充 2個交點，填充 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 50 （ 2）多邊形邊界上的象素的取舍問題。 但為使算法在處理問題時保持一致 ， 將 前述的頂點計數(shù)方法用于多邊形水平邊的頂點 ， 該水平邊界線是否填充取決于兩頂點的計數(shù)結(jié)果 。 算法保證 多邊形填充時邊界 “ 下閉上開 ” ,同理規(guī)定多邊形邊界 “ 左閉右開 ” ；避免多邊形在填充前后因邊界上像素的取舍而導(dǎo)致形狀和面積的改變 。 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 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 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é)點存放對應(yīng)邊的有關(guān)信息： x當(dāng)前掃描線與邊的交點； ?x從當(dāng)前掃描線到下一條掃描線之間的 x增量 ymax邊所交的最高掃描線號 P2(5,1) P1(2,2) P3(11,3) P4(11,8) P6(2,7) P5(5,5) 2 4 6 8 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 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 為了方便活性邊表的建立和修改，還需建立一張新邊表。 多邊形定義 polydef。 把 ymin＝ i 的邊放進新邊表 NET[i]。 } } 此邊不再與 掃描線相交 求下一條掃描 線與邊的交點 Ymax=i+1 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 57 基本思想 : 從區(qū)域內(nèi)部已定義新值的某像素 (種子 )開始 ,搜索與該種子相鄰且位于區(qū)域內(nèi)的像素 ,該像素為新的種子；不斷地遞歸搜索 ,逐個像素填充所需顏色 ,直到填充完區(qū)域邊界內(nèi)的所有像素為止。 《圖形學(xué)與虛擬環(huán)境》 鄭州大學(xué)信息工程學(xué)院 趙新燦 58 區(qū)域分 四連通 區(qū)域和 八連