計(jì)算機(jī)圖形學(xué)chp3_Line1

1、計(jì)算機(jī)圖形學(xué)計(jì)算機(jī)圖形學(xué)吳 偉計(jì)算機(jī)學(xué)院E-mail: wuwei_第三講 二維圖元生成算法所謂 的生成，是指完成圖元的參數(shù)表示形式（由圖形軟件包的使用者指定）到點(diǎn)陣表示形式（光柵顯示系統(tǒng)刷新時(shí)所需的表示形式）的轉(zhuǎn)換。通常也稱圖元。 計(jì)算機(jī)圖形學(xué)課程計(jì)算機(jī)圖形學(xué)課程Computer Graphics Course要求(1/2)要求（2/2) 3.1 二維線畫(huà)圖元的生成第第3講講二維圖元生成算法二維圖元生成算法 掃描轉(zhuǎn)換直線段 1 , 1m第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成001245313245yx線的光柵表示線的數(shù)學(xué)表示象素掃描線6 掃描轉(zhuǎn)換直線段) 1, 1()0, 0(10y

2、xPyxP01, 01yyyxxxxyk/Bxky1,110iinxxxxx其中Bxkyiiniiiyx0),(niriiyx0,),()5 . 0(int)()(,iiriyyroundy第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成 掃描轉(zhuǎn)換直線段kykBxkBxkBxkyiiiii) 1(11第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成 掃描轉(zhuǎn)換直線段中點(diǎn)算法中點(diǎn)算法 1 , 0k第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成) 1, 1()0, 0(10yxPyxP 掃描轉(zhuǎn)換直線段第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成 掃描轉(zhuǎn)換直線段PP2P1第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維

3、線畫(huà)圖元的生成 掃描轉(zhuǎn)換直線段PP2P1第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成判別式的定義判別式的定義d=F(M)=F(Xp+1,Yp+0.5) d的初始值的初始值ld0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b 因(X0,Y0)在直線上，F(xiàn)(X0，Y0)=0,所以，d0=a+0.5bd的增量（a，a+b) 都是整數(shù)，只有初始值包含小數(shù)，可以用2d代替d, 2a改寫(xiě)成a+a。u算法中只有整數(shù)變量，不含乘除法，可用硬件實(shí)現(xiàn)。 掃描轉(zhuǎn)換直線段第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成判別式的定義判別式的定義d=F(M)=F(Xp+1,Yp+0.5) 掃描轉(zhuǎn)換直線段中

4、點(diǎn)畫(huà)線法程序中點(diǎn)畫(huà)線法程序第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成舉例：（0,0) (5,2) Bresenham Bresenham畫(huà)線法畫(huà)線法(1/2)(1/2)P2 d+k-1 d+k d P P1第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成BresenhamBresenham畫(huà)線法畫(huà)線法(2/2)(2/2)n若令若令e = d - 0.5，則判斷，則判斷e符號(hào)即可符號(hào)即可 當(dāng)e = 0時(shí)，取P2，且e = e+k-1; 當(dāng)e =0時(shí), 取P2，且e=e+2*y-2*x;當(dāng)e 0時(shí)，取P1，且e = e+2*y;第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成BresenhamBr

5、esenham畫(huà)線法畫(huà)線法程序程序第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成舉例：（0,0) (5,2) 掃描轉(zhuǎn)換圓弧n處理對(duì)象：圓心在原點(diǎn)的圓弧處理對(duì)象：圓心在原點(diǎn)的圓弧n圓的八對(duì)稱性圓的八對(duì)稱性第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成離散點(diǎn): 離散角度:u開(kāi)根，三角函數(shù)運(yùn)算，計(jì)算量大，不可取。 ),(,22222riiiiiyxxRyxRyx，（利用隱函數(shù)方程取整)sin(),cos(sincosiiRroundRroundRyRx利用參數(shù)方程 兩種直接離散方法第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成 掃描轉(zhuǎn)換圓弧掃描轉(zhuǎn)換圓弧n圓弧的正負(fù)劃分性圓弧的正負(fù)劃分性0),(222

6、RyxyxF圓弧外的點(diǎn)：F(X，Y)0圓弧內(nèi)的點(diǎn)：F(X，Y)0第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成 中點(diǎn)畫(huà)圓法(1/4)PP1P2第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成 中點(diǎn)畫(huà)圓法(2/4)P2P1P中點(diǎn)畫(huà)圓法(3/4)P2P1P 中點(diǎn)畫(huà)圓法(4/4)中點(diǎn)畫(huà)圓法的程序第第1節(jié)節(jié)二維線畫(huà)圖元的生成二維線畫(huà)圖元的生成舉例：圓心在原點(diǎn)，r=8(x,y)d(0,8)-7(1,8)-5(2,8)0(3,7)-7(4,7)2(5,6)1(6,5)4Bresenham畫(huà)圓法（1/2)Bresenham畫(huà)圓法(2/2)nDH到圓弧距離的平方為到圓弧距離的平方為： H = (x + 1)2

7、+ y2 - R2 ; D = (x + 1)2 + (y - 1)2 - R2 ; 比較 |H| 與 | D |的大?。喝魘H | = | D |, 取H；否則取Dn D 0時(shí)時(shí)，取D或H； 令 DH HD2D + 2y - 1，則： DH = 0時(shí)， |H | 0時(shí)， |H | | D |, 取D;n D 0時(shí)時(shí)，D和H都在圓外，取D； D可用增量法計(jì)算：可用增量法計(jì)算： H: (x, y) = (x+1, y) , D = D + 2x +1 D: (x, y) = (x+1, y-1), D = D + 2x 2y 2 Bresenham畫(huà)圓法 程序/取D/取H/取D/取H/取D橢圓的

8、掃描轉(zhuǎn)換(1/6)n橢圓方程橢圓方程: F(x, y)=b2x2 + a2y2 a2b2 = 0； a, b為xy軸長(zhǎng)短半軸長(zhǎng)；n橢圓的對(duì)稱性，只考慮第一象限橢圓弧生成，分橢圓的對(duì)稱性，只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為上下兩部分，以切線斜率為-1-1的點(diǎn)作為分界點(diǎn)。的點(diǎn)作為分界點(diǎn)。 區(qū)域1 dy/dx-1區(qū)域2 dy/dx-1M1M2(Xp1，Yp-0.5)(Xp+0.5，Yp-1)PPdy/dx=-1l斜率dy/dx = -b2x/a2yl移出區(qū)域1的條件：dy/dx=-1, 即 橢圓的掃描轉(zhuǎn)換(2/6)l先討論橢圓弧的上部分先討論橢圓弧的上部分(Xp，Yp)中點(diǎn)(Xp+

9、1,Yp-0.5) 橢圓的掃描轉(zhuǎn)換(3/6)n根據(jù)d1的符號(hào)來(lái)決定下一像素是取正右方(Xp+1,Yp)，還是右下方(Xp+1,Yp-1)。 d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量為的增量為 b2(2Xp+3) d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量為的增量為 b2(2Xp+3)+a2(-2Yp+2)d1=F(Xp+1,Yp-0.5) = b2(Xp+1)2+a2(Yp-0.5)2-a2b2橢圓的掃描轉(zhuǎn)換(4/6)nd1的初始條件：橢圓弧起點(diǎn)為(0，b)，第一個(gè)中點(diǎn)為(1,b-0.5) n初始判別式： d1

10、0=F(1,b-0.5)=b*b+a*a(-b+0.25)d1=F(Xp+1,Yp-0.5) = b2(Xp+1)2+a2(Yp-0.5)2-a2b2橢圓的掃描轉(zhuǎn)換 直線,圓,橢圓的算法小結(jié)n中點(diǎn)畫(huà)線法中點(diǎn)畫(huà)線法, 畫(huà)圓法畫(huà)圓法,畫(huà)橢圓法畫(huà)橢圓法 構(gòu)造中點(diǎn)判別式構(gòu)造中點(diǎn)判別式,利用中點(diǎn)與圖形的關(guān)利用中點(diǎn)與圖形的關(guān)系系(上下上下,內(nèi)外內(nèi)外)nBresenham畫(huà)線法畫(huà)線法,畫(huà)圓法畫(huà)圓法 與整數(shù)網(wǎng)格系的下一個(gè)交點(diǎn)更接近于與整數(shù)網(wǎng)格系的下一個(gè)交點(diǎn)更接近于哪個(gè)坐標(biāo)點(diǎn)哪個(gè)坐標(biāo)點(diǎn)?并行畫(huà)線與畫(huà)圓n將順序算法中的計(jì)算平衡分割到各個(gè)處將順序算法中的計(jì)算平衡分割到各個(gè)處理器上理器上;n線線: 分段分段,段數(shù)由處

11、理器個(gè)數(shù)段數(shù)由處理器個(gè)數(shù)Np決定決定;起始起始x坐標(biāo)坐標(biāo) Xk = X0 + k Xp Xp = ( X + Np -1)/Np n圓圓: 分成等長(zhǎng)子圓弧分成等長(zhǎng)子圓弧(建立初始建立初始y值值,初始判別式初始判別式)幀緩沖器的裝載 n用增量方法計(jì)算幀緩沖器地址 addr(x, y) = addr(0,0) + y(xmax+1) + x沿掃描線移動(dòng)沿掃描線移動(dòng): addr(x+1, y) = addr(x,y)+1 沿對(duì)角方向沿對(duì)角方向: addr(x+1, y+1) = addr(x,y)+xmax+2Xmax0(x,y)ymax像素編址和物體的幾何表示n象素在數(shù)學(xué)上一個(gè)無(wú)限小的點(diǎn)象素在數(shù)學(xué)上一個(gè)無(wú)限小的點(diǎn),但是在屏幕上但是在屏幕上是一個(gè)