第三章二維線畫圖元的生成

1、計算機圖形學1第3 3章章 二維線畫圖元的生成二維線畫圖元的生成2本章目標l掌握繪制簡單線畫圖元（點、線、圓等）的方法掌握繪制簡單線畫圖元（點、線、圓等）的方法3主要內(nèi)容l3.1 二維圖形顯示二維圖形顯示l3.2 掃描轉(zhuǎn)換直線段掃描轉(zhuǎn)換直線段l3.3 掃描轉(zhuǎn)換圓弧掃描轉(zhuǎn)換圓弧l3.4 線畫圖元的屬性線畫圖元的屬性43.1 二維圖形顯示l圖元的生成圖元的生成n是指完成圖元的參數(shù)表示形式到點陣表示形式的轉(zhuǎn)換。是指完成圖元的參數(shù)表示形式到點陣表示形式的轉(zhuǎn)換。通常也稱通常也稱掃描轉(zhuǎn)換圖元掃描轉(zhuǎn)換圖元( (Scan Converter) ) n參數(shù)表示形式由圖形軟件包的開發(fā)者指定參數(shù)表示形式由圖形軟件包

2、的開發(fā)者指定n點陣表示形式是光柵顯示系統(tǒng)刷新時所需的表示形式點陣表示形式是光柵顯示系統(tǒng)刷新時所需的表示形式點圖示法點圖示法區(qū)域圖示法區(qū)域圖示法參數(shù)參數(shù): p0, p1點陣：點陣：p0p1p0p1圖形的掃描轉(zhuǎn)換 圖形的掃描轉(zhuǎn)換（光柵化）：確定一個像素集合，圖形的掃描轉(zhuǎn)換（光柵化）：確定一個像素集合，用于顯示一個圖形的過程。步驟如下：用于顯示一個圖形的過程。步驟如下：l確定有關(guān)像素確定有關(guān)像素l用圖形的顏色或其它屬性，對像素進行寫操作。用圖形的顏色或其它屬性，對像素進行寫操作。 對一維圖形，若不考慮線寬，則用一個像素寬的對一維圖形，若不考慮線寬，則用一個像素寬的直線來顯示圖形。二維圖形的光柵化，即

3、區(qū)域的直線來顯示圖形。二維圖形的光柵化，即區(qū)域的填充：確定像素集，填色或圖案。填充：確定像素集，填色或圖案。 563.1 二維圖形顯示l像素操作函數(shù)（畫像素和讀像素）像素操作函數(shù)（畫像素和讀像素）n最基本的繪圖函數(shù)最基本的繪圖函數(shù)n畫（寫）像素畫（寫）像素: SetPixel ( int x, int y, int color )n讀像素讀像素: int GetPixel ( int x, int y)n注意：注意：(1)具體的語言環(huán)境使用的函數(shù)名可能不同，這里的具體的語言環(huán)境使用的函數(shù)名可能不同，這里的函數(shù)名僅用于課堂教學函數(shù)名僅用于課堂教學(2)屏幕坐標系統(tǒng)屏幕坐標系統(tǒng)(GDI 默認）默認

4、）坐標坐標原點原點 為了方便表為了方便表示，課堂上使示，課堂上使用常用坐標系用常用坐標系統(tǒng)。統(tǒng)。 OpenGL中的中的坐標系統(tǒng)可變坐標系統(tǒng)可變化?；?。OYX課堂課堂采用采用73.1 二維圖形顯示l用用OpenGL實現(xiàn)讀實現(xiàn)讀/寫像素函數(shù)寫像素函數(shù)void SetPixel(int x, int y, float r, float g, float b ) glColor3f(r,g,b); glBegin(GL_POINTS) glVertex2i(x,y); glEnd();float* GetPixel(int x, int y) float *rgb= new float3; glRea

5、dPixels(x,y,1,1,GL_RGB,GL_FLOAT,rgb); return rgb;83.2 掃描轉(zhuǎn)換直線段l掃描轉(zhuǎn)換直線掃描轉(zhuǎn)換直線n求與直線段充分接近的像素集，并以此像素集替代原連求與直線段充分接近的像素集，并以此像素集替代原連續(xù)直線段在屏幕上顯示續(xù)直線段在屏幕上顯示l約束約束n像素間均勻網(wǎng)格像素間均勻網(wǎng)格n整型坐標系整型坐標系n幾點假設(shè)幾點假設(shè)u直線段為：直線段為：u直線段的寬度為直線段的寬度為1u直線段的斜率直線段的斜率10111000),(),(xxyxPyxPP0P1 1 , 0m93.2.1 直線方程法l基本思想基本思想n根據(jù)直線的幾何方程確定線段路徑上的像素位置根

6、據(jù)直線的幾何方程確定線段路徑上的像素位置l直線方程直線方程nM 表示斜率，表示斜率，b 表示表示 y 軸截距軸截距l(xiāng)方法方法n劃分區(qū)間劃分區(qū)間x0, x1: k0, k1, kn, ki+1=xi+1, 其中其中k0 = x0, kn= x1n計算縱坐標計算縱坐標y：yi = mki + bn取整：取整：bmxy0101,yyyxxx00/mxybxymniiiyk0),(niriiyk0,),()5 . 0(int)()(,iiriyyroundy主要運算：主要運算： 乘法乘法+ +加法加法+ +取整取整 浮點運算浮點運算103.2.2 DDA算法l數(shù)字差分分析法數(shù)字差分分析法DDA (Di

7、gital Differential Analyzer)n方法方法n程序：程序：p45n主要運算主要運算 加法加法+取整取整 浮點運算浮點運算11 (1) iiiiiym xbmxbm xbmym113.2.2 DDA算法nDDA算法代碼算法代碼 void LineDDA(int x0,int y0,int x1,int y1,int color) int x; float dx, dy, y, m; dx = x1 - x0; dy = y1 - y0; m = dy / dx; y = y0; for(x = x0; x = x1; x+) y = (int)(y + 0.5); SetP

8、ixel(x, y, color); y += m; 123.2.3 中點算法l目標目標n消除消除DDA算法中的浮點運算算法中的浮點運算浮點數(shù)取整運算，不利于硬件實現(xiàn)；浮點數(shù)取整運算，不利于硬件實現(xiàn)； DDA算法效率低算法效率低l隱式方程隱式方程 F(x, y) = ax + by + c = 0 式中式中 a = y0-y1= - y, b = x1-x0 = x, c = x0*y1 - x1*y0l直線的正負劃分性直線的正負劃分性n直線上方的點：直線上方的點：F(x, y) 0n直線下方的點：直線下方的點：F(x, y) 0n直線直線 上的點：上的點： F(x, y) 0133.2.3

9、中點算法l問題：如何判斷距直線最近的下一個像素點問題：如何判斷距直線最近的下一個像素點（xp+1，？）？，？）？n根據(jù)可能所取點間的中點在直線的位置根據(jù)可能所取點間的中點在直線的位置n構(gòu)造判別式：構(gòu)造判別式：d = F(M) = F(xp+1, yp+0.5) 由由 d 的正和負可判定下一個像素。其中（的正和負可判定下一個像素。其中（xp , yp）為當前點）為當前點坐標坐標: d 0，取，取NE；否則取；否則取Eyi 表示實際坐標；表示實際坐標；yi, r 表示取整后的坐標；表示取整后的坐標；M是中點是中點p143.2.3 中點算法l如何判定再下一個像素（如何判定再下一個像素（xp+2，？）

10、，？）1）若）若d0，取正右方像素，取正右方像素E，則判定再下一個像素的，則判定再下一個像素的d為為 d1 = F(xp+2, yp+0.5) = a(xp+2) + b(yp+0.5) + c = d + a， d的增量是的增量是a(即即- y)2）若）若d0，取右上方像素，取右上方像素NE，則判定再下一個像素的，則判定再下一個像素的d為為 d2 = F(xp+2, yp+1.5) = d + a+b ， d的增量為的增量為a+b (即即-( y- x)d0，中點中點M在線段上方在線段上方，取取Ed 0，中點中點M在線段下方在線段下方，取取NEp計算計算 d 需要整數(shù)乘法需要整數(shù)乘法153.

11、2.3 中點算法l增量增量d的初始值的初始值nd0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5bn因因(x0, y0)在直線上，在直線上，F(xiàn)(x0, y0)=0, 所以，所以，d0 = a + 0.5bl增量增量d的遞推公式的遞推公式n優(yōu)化優(yōu)化: 增量都是整數(shù)，只有初始值包含小數(shù)，可以用增量都是整數(shù)，只有初始值包含小數(shù)，可以用2d代替代替d， 2a改寫成改寫成a + an特點：算法中只有整數(shù)變量，不含乘除法，可用硬件實現(xiàn)特點：算法中只有整數(shù)變量，不含乘除法，可用硬件實現(xiàn)005 . 010iiiiiddbadaddbad00222210iiiiiddbadaddbad2d代替

12、代替d163.2.3 中點算法l遞推公式遞推公式l程序程序10010022221110iiiiiiiiiiiixxddyyyddbadaddbadMidpointLine(int x0,int y0, int x1,int y1,int color)/*x0 x1,y0y1,0=m=1*/ int a,b,d1,d2,d,x,y; a = y0 - y1; b = x1 x0; d = a + a + b; d1 = a + a; d2 = (a + b) + ( a + b); x = x0; y = y0; SetPixel(x, y, color); while (xx1) if (d1

13、0m-1m10m-1m-1XYm為無窮大0022220110iiiiiddadbaddbadm002222110iiiiiddbadbddbadm213.3 掃描轉(zhuǎn)換圓弧l處理對象：圓心在原點的圓弧處理對象：圓心在原點的圓弧n其它情況如何考慮其它情況如何考慮?平移到原點，掃描轉(zhuǎn)換后再平移到原位置平移到原點，掃描轉(zhuǎn)換后再平移到原位置l圓的八對稱性圓的八對稱性n只需要掃描轉(zhuǎn)換八只需要掃描轉(zhuǎn)換八分之一圓弧即可分之一圓弧即可223.3 掃描轉(zhuǎn)換圓弧l兩種直接計算方法兩種直接計算方法n離散點離散點n離散角度離散角度n缺點：開平方，三角函數(shù)運算，計算量大，不可取缺點：開平方，三角函數(shù)運算，計算量大，不可取

14、),(,22222riiiiiyxxRyxRyx，（利用隱函數(shù)方程取整 )sin(),cos(sincosiiRroundRroundRyRx利用參數(shù)方程233.3.1 圓弧的中點算法l圓弧的正負劃分性圓弧的正負劃分性0),(222RyxyxF圓弧外的點圓弧外的點：F(x，y)0圓弧內(nèi)的點圓弧內(nèi)的點：F(x，y)0圓弧上的點圓弧上的點：F(x，y)0243.3.1 圓弧的中點算法l第二個八分圓第二個八分圓n特點：特點：第一象限的八分之一圓弧中第一象限的八分之一圓弧中x 的變化大于的變化大于y的變化，的變化，即圓弧上的切矢量斜率在即圓弧上的切矢量斜率在0 . -1間間253.3.1 圓弧的中點算

15、法l問題：如何判斷距圓弧最近的下一個像素點？問題：如何判斷距圓弧最近的下一個像素點？l隱函數(shù)隱函數(shù) F(x , y) = x2 + y2 - R2 = 0 切線斜率切線斜率 -1 m 0l基本原理基本原理n點點(xp, yp)下一點所取可能點間線段的中點下一點所取可能點間線段的中點 M = (xp+1, yp - 0.5)n當當F(M)0時，時，M在圓內(nèi)，說明在圓內(nèi)，說明E距離圓弧更近，取距離圓弧更近，取E；n當當F(M)0時，時， M在圓外，在圓外， 取取SEp263.3.1 圓弧的中點算法l構(gòu)造判別式構(gòu)造判別式nd = F(M) = F(xp+1, yp-0.5) = (xp+1)2+(y

16、p-0.5)2-R2n若若d 0，取，取SE， 再下一個像素的判別式為：再下一個像素的判別式為： d2 = F(xp+2, yp-1.5) = d+(2xp+3)+(-2yp+2) 沿右下方向，沿右下方向，d 的增量為的增量為2(xp-yp)+5p273.3.1 圓弧的中點算法ld 的初始值的初始值(在第一個像素在第一個像素(0, R)處處)nd0 = F(1, R-0.5) = 1.25 - Rn算法中有浮點數(shù)，用算法中有浮點數(shù)，用h=4dnH054Rl遞推公式遞推公式l程序：程序：p515210010020)(8128*451110iiiiiiiiiiiiiiixxHHyyyHHyxHxH

17、HRH283.3.1 圓弧的中點算法l消除乘法運算消除乘法運算P0020)(8128*4510iiiiiiiiHHyxHxHHRH令20)(8128iiiiiyxSExE遞推公式01608 20)(88812812)1(81111iiiiiiiiiiiHSEHSEyxSEExxE293.3.1 圓弧的中點算法 變量關(guān)系變量關(guān)系初始值初始值RyxSExEiii82020)(81212800 xyHESEx=x+1H0y-1H+SEE+8SE+16303.3.2 圓弧的多邊形逼近法l兩種方法兩種方法n正內(nèi)接多邊形迫近法正內(nèi)接多邊形迫近法n等面積正多邊形迫近法等面積正多邊形迫近法l特點特點n多邊形邊

18、數(shù)足夠多時接近圓多邊形邊數(shù)足夠多時接近圓n誤差控制邊數(shù)誤差控制邊數(shù)n顯示多邊形的邊可用掃描轉(zhuǎn)換直線段的中點算法來實顯示多邊形的邊可用掃描轉(zhuǎn)換直線段的中點算法來實現(xiàn)現(xiàn)313.3.2 圓弧的多邊形逼近法1、正內(nèi)接多邊形迫近法、正內(nèi)接多邊形迫近法n圓：圓：x2 + y2 = R2n內(nèi)接多邊形頂點集：內(nèi)接多邊形頂點集： 令令 pi 的幅角為的幅角為 ，邊的圓心角為，邊的圓心角為 則有則有10),(niiiiyxpi 是常數(shù)，是常數(shù)， ， 只在開始時計算一次所以，一個頂只在開始時計算一次所以，一個頂點只需點只需4 4次乘法，共次乘法，共4 4n次乘法，外加直線段的中點算法的計算量次乘法，外加直線段的中點

19、算法的計算量)sin()cos(sincos11iiiiiiiiRyRxRyRxiiiiiiyxRRyxcossinsincos)sin()cos(11sincos323.3.2 圓弧的多邊形逼近法問題：多少條邊合適？問題：多少條邊合適？n給定最大逼近誤差（最大給定最大逼近誤差（最大 距離）距離） d ，如何確定多邊形的，如何確定多邊形的邊數(shù)邊數(shù)n或或a？R Rcos(a/2) = (R d)/R a bF(x,y)0F(x,y)=040l先討論橢圓弧的上部分先討論橢圓弧的上部分n(xp, yp)下一個點所取兩點連線的下一個點所取兩點連線的中點坐標為中點坐標為(xp +1, yp-0.5)nd

20、1=F(xp +1, yp-0.5) = b2(xp +1)2+a2(yp-0.5)2a2b2n根據(jù)根據(jù)d1的符號來決定下一像素是取正右方的那個，還是右下方的那的符號來決定下一像素是取正右方的那個，還是右下方的那個。個。n若若d10,中點在橢圓內(nèi)，取正右方象素，判別式更新為：中點在橢圓內(nèi)，取正右方象素，判別式更新為：d1=F(xp +2, yp-0.5)= d1 +b2(2 xp +3)d1的增量為的增量為b2(2 xp +3)n當當d10，中點在橢圓外，取右下方象素，更新判別式：，中點在橢圓外，取右下方象素，更新判別式：d1=F(xp +2, yp-1.5)= d1 +b2(2 xp +3)

21、+a2(-2yp+2)d1的增量為的增量為b2(2 xp +3)+a2(-2 yp +2)3.3.3 橢圓的中點算法*41ld1的初始條件的初始條件n橢圓弧起點為橢圓弧起點為(0，b)，第一個中點為，第一個中點為(1,b-0.5) n初始判別式：初始判別式：d10=F(1,b-0.5)=b*b+a*a(-b+0.25)l橢圓弧的下部分橢圓弧的下部分n下部分，下一象素可能是一正下方或右下方下部分，下一象素可能是一正下方或右下方(x發(fā)生變化發(fā)生變化)nd2 = F(xp+0.5, yp-1) = b2(xp+0.5)2+a2(yp-1)2-a2b2 若若d2 =0,則則d2 = F(xp+0.5,

22、 yp-2) = d2 + a2(-2yp+3)nd2 0 = F(X+0.5,Y-1) = b2(X+0.5)2+a2(Y-1)2-a2b2n下半部分弧的終止條件為下半部分弧的終止條件為 y = 03.3.3 橢圓的中點算法*42l程序程序3.3.3 橢圓的中點算法*MidpointEllipe(int a, int b, int color) int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); SetPixel(x,y,color); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3);