電腦圖形教程——基本圖形生成算法.ppt

1、第三章 輸出圖元,學(xué)習(xí)要點(diǎn),OpenGL的輸出圖元。 實(shí)現(xiàn)輸出圖元的設(shè)備級(jí)算法基本圖形生成算法。,輸出圖元,圖形軟件包中用來(lái)描述各種圖形元素的函數(shù)。 選定坐標(biāo)系統(tǒng)指定一個(gè)圖形的幾何要素觀察函數(shù)（投影）將對(duì)象映射到視頻監(jiān)視器實(shí)現(xiàn)對(duì)象的顯示。,坐標(biāo)系統(tǒng)（1/2）,描述圖形的坐標(biāo)系世界坐標(biāo)系。 存儲(chǔ)對(duì)象的坐標(biāo)幀緩存中的整數(shù)象素位置。 顯示圖形的坐標(biāo)屏幕坐標(biāo)（與幀緩存中的整數(shù)象素位置對(duì)應(yīng)）。 設(shè)置象素的顏色值（ setPixel(x,y) ）。,坐標(biāo)系統(tǒng)(2/2),OpenGL中指定二維世界坐標(biāo)系統(tǒng) glMatrixMode (GL_PROJECTION); glLoadIdentity(); glu

2、Ortho2D(xmin,xmax,ymin,ymax);,OpenGl畫(huà)點(diǎn)函數(shù),glVertex234sifdv(TYPE coords)。 glVertex*()函數(shù)必須在glBegin()和glEnd()函數(shù)之間。 glBegin()的參數(shù)是GL_POINTS。 glVertex*()中的參數(shù)可以是坐標(biāo)值、矩陣、C類(lèi)或結(jié)構(gòu)（struct）。,OpenGL畫(huà)線(xiàn)函數(shù),在glBegin()和glEnd()之間調(diào)用多個(gè)glVertex*()函數(shù)實(shí)現(xiàn)畫(huà)多個(gè)線(xiàn)段。 三個(gè)OpenGL符號(hào)常量指定線(xiàn)段類(lèi)型。 GL_LINES GL_LINE_STRIP GL_LINE_LOOP,畫(huà)線(xiàn)算法基本圖形生成算法

3、,圖元掃描轉(zhuǎn)換 直線(xiàn)段掃描轉(zhuǎn)換 圓弧掃描轉(zhuǎn)換 多邊形 實(shí)區(qū)域填充 字符 圖形反走樣,光柵圖形中點(diǎn)的表示,像素由其左下角坐標(biāo)表示,光柵圖形中點(diǎn)的表示,地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址,每行像素點(diǎn)數(shù),行數(shù),行中位置,光柵圖形中點(diǎn)的表示,Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 = k1 + k2y + x,Address(x1,y) = k1 + k2y + (x1) = Address(x,y) 1,Address(x,y1) = k1 + k2(y 1) + x = Ad

4、dress(x,y) k2,Address(x1,y1) = k1 + k2(y 1) + (x1) = Address(x,y) k2 1,對(duì)像素連續(xù)尋址時(shí)，如何減少計(jì)算量？,增量法的優(yōu)點(diǎn)？,圖形顯示的幾種方式,圖形顯示前需要：掃描轉(zhuǎn)換+裁剪 裁剪掃描轉(zhuǎn)換：最常用，節(jié)約計(jì)算時(shí)間 掃描轉(zhuǎn)換裁剪：算法簡(jiǎn)單,直線(xiàn)段掃描轉(zhuǎn)換,假設(shè) 像素間均勻網(wǎng)格，整型坐標(biāo)系，直線(xiàn)段斜率0m1 對(duì)m1，x、y互換,直線(xiàn)段的掃描轉(zhuǎn)換算法,直線(xiàn)的掃描轉(zhuǎn)換 確定最佳逼近于該直線(xiàn)的一組象素 按掃描線(xiàn)順序，對(duì)這些象素進(jìn)行寫(xiě)操作 三個(gè)常用算法： 1數(shù)值微分法（DDA） 2中點(diǎn)畫(huà)線(xiàn)法 3Bresenham算法。,數(shù)值微分(DDA)

5、法(1/5),已知線(xiàn)段端點(diǎn)：P0(x0,y0), P1(x1,y1) 直線(xiàn)方程 y=kx+b (xi, yi), i=0,.n. 浮點(diǎn)數(shù)取整 : yi=round(yi)=(int)(yi+0.5) 用到浮點(diǎn)數(shù)的乘法、加法和取整運(yùn)算,數(shù)值微分(DDA)法(2/5),增量算法 yi+1=kxi+1+b=k(xi+1)+b=yi+k (xi,yi)(xi+1,yi+k) 缺點(diǎn)： 有浮點(diǎn)數(shù)取整運(yùn)算 不利于硬件實(shí)現(xiàn) 效率低 僅適用于k 1的情形:x每增加1,y最多增加1。當(dāng) k 1時(shí)，必須把x，y互換。,Example：draw segment x y int(y+0.5) 0 0 0 1 0+0.4

6、 0 2 0.4+0.4 1 3 0.8+0.4 1 4 1.2+0.4 2 5 1.6+0.4 2,round,數(shù)值微分(DDA)法(3/5),void lineDDA (int x0,int y0,int xend,int yend) int dx=x0-xend, dy=y0-yend, y, steps, k; float xIncrement, yIncrement, x=x0, y=y0; if (fabs(dx)=fabs(dy) steps=fabs(dx); else steps=fabs(dy); xIncrement=float(dx)/float(steps); yIn

7、crement=float(dy)/float(steps); setPixel (round(x),round(y); for (k=0; ksteps; k+) x+=xIncrement; y+=yIncrement; setPixel(round(x),round(y); ,數(shù)值微分(DDA)法(4/5),數(shù)值微分(DDA)法(5/5),缺點(diǎn)： 取整操作和浮點(diǎn)數(shù)運(yùn)算十分耗時(shí) 取整誤差的積累使象素位置偏離實(shí)際線(xiàn)段 不易硬件實(shí)現(xiàn),中點(diǎn)畫(huà)線(xiàn)法（1/4）,問(wèn)題：判斷距離理想直線(xiàn)最近的下一個(gè)象素點(diǎn) 已知：線(xiàn)段兩端點(diǎn)(x0,y0)，(x1,y1) 直線(xiàn)方程：F(x,y)=ax+by+c=0 a=y

8、0-y1 b=x1-x0 c=x0y1-x1y0,M,如何判斷M點(diǎn)在Q點(diǎn)上方還是在Q點(diǎn)下方？,M,P1,P2,P,直線(xiàn)上方點(diǎn)： F(x,y)0 直線(xiàn)下方點(diǎn): F(x,y)0 構(gòu)造判別式： d=F(M)=F(Xp+1,Yp+0.5) 由d0，d0可判定下一個(gè)象素,(Xp+1,Yp+0.5),中點(diǎn)畫(huà)線(xiàn)法（2/4）,分兩種情形考慮再一下個(gè)象素的判定： 若d0，中點(diǎn)M在直線(xiàn)上方，取正右方象素P1 (Xp+1,Yp) 再下一個(gè)象素的判別式為： d1=F(Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = d+a d的增量為a 若d0，中點(diǎn)M在直線(xiàn)下方，取右上方象素P2 (Xp+1

9、,Yp+1) 再下一個(gè)象素的判別式為： d2=F(Xp+1)+1,(Yp+1)+0.5)= a(Xp+2)+b(Yp+1.5)+c =d+a+b d的增量為a+b,d的初始值 d0=F(X0+1,Y0+0.5) =F(X0,Y0)+a+0.5 =a+0.5b 用2d代替d后，d0=2a+b d的增量都是整數(shù) 優(yōu)點(diǎn)： 只有整數(shù)運(yùn)算，不含乘除法 可用硬件實(shí)現(xiàn),因(X0,Y0)在直線(xiàn)上，所以F(X0,Y0)=0,中點(diǎn)畫(huà)線(xiàn)法（4/4）,Example：Midpoint ixiyid 1001 210-3 3213 431-1 5425,void MidpointLine (int x0,int y0,

10、int xend, int yend,int color) int a, b, incre_d1, incre_d2, d, x, y; a=y0-yend, b=xend-x0, d=2*a+b; incre_d1=2*a, incre_d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (xxend) if (d0) x+, y+, d+=incre_d2; else x+, d+=incre_d1; drawpixel (x, y, color); /* while */ /* mid PointLine */,Bresenham

11、畫(huà)線(xiàn)算法（1/7）,使用最廣泛 與中點(diǎn)畫(huà)線(xiàn)法的思想類(lèi)似 由誤差項(xiàng)符號(hào)決定下一個(gè)象素取正右方像素還是右上方像素,Bresenham畫(huà)線(xiàn)算法（2/7）,基本思想 比較從理想直線(xiàn)到位于直線(xiàn)上方的像素的距離d1和相鄰的位于直線(xiàn)下方的像素的距離d2 根據(jù)距離誤差項(xiàng)的符號(hào)確定與理想直線(xiàn)最近的象素,Bresenham畫(huà)線(xiàn)算法（3/7）,最大位移方向每次走一步 k1時(shí)，x為最大位移方向 y方向走步與否 取決于誤差e值的大小 誤差計(jì)算 初值：e0= y/ x 當(dāng)e0.5時(shí)，最接近P2(xi+1,yi+1) y方向走一步 當(dāng)e0.5時(shí)，最接近P1(xi+1,yi) y方向不走步,Bresenham畫(huà)線(xiàn)算法（4/7

12、）,為方便與0比較，設(shè)e=e-0.5 e0=y/ x-0.5 當(dāng)e0時(shí)，最接近P2(xi+1,yi+1) y方向走一步 當(dāng)e0時(shí)，最接近P1(xi+1,yi) y方向不走步 有除法，不宜硬件實(shí)現(xiàn),Bresenham畫(huà)線(xiàn)算法（5/7）,設(shè)e=e2x，不影響判斷的準(zhǔn)確性 e0=2y - x 當(dāng)e0時(shí)，最接近P2(xi+1,yi+1) y方向走一步 當(dāng)e0時(shí)，最接近P1(xi+1,yi) y方向不走步,Bresenham畫(huà)線(xiàn)算法（6/7）,下一步誤差的計(jì)算 當(dāng)e0時(shí)，y方向走一步 e=2y/ x - 1 =e + y/ x - 1 e=e + 2y - 2x 當(dāng)e0時(shí)，y方向不走步 e=2y/ x=

13、e + y/ x e=e + 2y,Bresenham畫(huà)線(xiàn)算法（7/7）,優(yōu)點(diǎn) 整數(shù)運(yùn)算，速度快 精度高 乘2運(yùn)算可用移位實(shí)現(xiàn)，適于硬件實(shí)現(xiàn),void BresenhamLine (int x0,int y0,int xend, int yend,int color) int dx,dy, incre_p1, incre_p2, p, x, y; dy=yend-y0, dx=xend-x0; incre_p1=2*dy, incre_p2=2* (dy-dx); x=x0, y=y0; p=2*dy-dx; drawpixel(x, y, color); while (xx1) if (p0

14、) x+, p+=incre_d1; else x+, y+,p+=incre_d2; drawpixel (x, y, color); /* while */ /* Bresenham */,圓弧的掃描轉(zhuǎn)換,圓的八對(duì)稱(chēng)性 只考慮第二個(gè)八分圓 假設(shè)圓心在原點(diǎn) x2+y2=R2,圓弧的掃描轉(zhuǎn)換,兩種直接離散生成方法 離散點(diǎn) 開(kāi)方運(yùn)算 離散角度 三角函數(shù)運(yùn)算 缺點(diǎn)： 計(jì)算量大 所畫(huà)像素位置間的間距不一致,中點(diǎn)畫(huà)圓法（1/2）,F(X,Y)=X2+Y2-R2=0 中點(diǎn) M=(Xp+1,Yp-0.5) 當(dāng)F(M)0時(shí)，M在圓內(nèi)，P1距離圓弧近，取P1 當(dāng)F(M)0時(shí)，M在圓外，P2距離圓弧近，取P2,

15、中點(diǎn)畫(huà)圓法（2/2）,若 d=0, 取P2為下一象素，再下一象素的判別式為 初始象素是（0,R），判別式d的初值為,P1(Xp+1,Yp),P2(Xp+1,Yp-1),MidPointCircle(int r int color) int x,y; float d; x=0; y=r; d=1.25-r; circlepoints (x,y,color); /draw (x,y) and other symmetric points while(x=y) if(d0) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; circlepoints (x,y,color);

16、,改進(jìn)：使用整數(shù)計(jì)算，即使用e=d-0.25代替d e0=1-R,MidPointCircle(int r int color) int x,y; float d; x=0; y=r; d=1-r; circlepoints (x,y,color); /draw (x,y) and other symmetric points while(x=y) if(d0) d+=2*x+3; else d+=2*(x-y)+5; y-; x+; circlepoints (x,y,color); ,DDA畫(huà)圓法（1/3）,圓的方程：f(x,y)=x2+y2-R2=0 全微分：df(x,y)=2xdx+2

17、ydy=0 微分方程：dy/dx=-x/y 遞推方程: (yn+1-yn)/ (xn+1-xn)=-xn/ yn xn+1 - xn = yn yn+1 - yn = -xn,實(shí)際畫(huà)出的曲線(xiàn)不是圓，而是螺旋線(xiàn)，為什么？,DDA畫(huà)圓法（2/3）,將遞推公式寫(xiě)成矢量形式： 構(gòu)造一個(gè)行列式值為1的矩陣 對(duì)應(yīng)的圓方程遞推關(guān)系為 xn+1 = xn + yn yn+1 = -xn +(1-2)yn= yn- xn+1,DDA畫(huà)圓法（3/3）,針對(duì)不同象限及順逆時(shí)針畫(huà)圓，賦給適當(dāng)?shù)姆?hào) 不同，圓形狀不同， 大近似橢圓,Bresenham畫(huà)圓算法（1/7）,順時(shí)針畫(huà)第一四分圓，下一步選擇哪個(gè)點(diǎn)？ 基本思想：

18、 通過(guò)比較像素與圓的距離平方來(lái)避免開(kāi)方運(yùn)算 下一像素有3種可能的選擇 mH=|(xi+1)2+yi2-R2| mD=|(xi+1)2+(yi-1)2-R2| mV=|xi2 +(yi-1)2-R2 | 選擇像素的原則 使其與實(shí)際圓弧的距離平方達(dá)到最小,Bresenham畫(huà)圓算法（2/7）,圓弧與點(diǎn)(xi,yi)附近光柵網(wǎng)格的相交關(guān)系有5種 右下角像素D (xi,yi)與實(shí)際圓弧的近似程度 i=(xi+1)2+(yi-1)2-R2 當(dāng)i0時(shí)，D在圓外， 當(dāng)i=0時(shí)，D在圓上，,Bresenham畫(huà)圓算法（3/7）,當(dāng)i0，則選D 若d=0，則選H,情形也適用,Bresenham畫(huà)圓算法（4/7）

19、,當(dāng)i0時(shí)，D在圓外， 情形，選mv ，mD 中最小者 d=mD - mV =|(xi+1)2+(yi-1)2-R2 | - |xi2+(yi-1)2-R2| =(xi+1)2+(yi-1)2-R2 + xi2+(yi-1)2-R2 =2 (i-xi)-1 若d0，則選V 若d=0，則選D,情形也適用,Bresenham畫(huà)圓算法（5/7）,當(dāng)i=0時(shí)，D在圓上， 按d判別，有d0，應(yīng)選D 按d判別，有d0，應(yīng)選D,Bresenham畫(huà)圓算法（6/7）,當(dāng)i0，選D 當(dāng)i0時(shí), 若d 0，選D 若d0，選V 當(dāng)i=0時(shí)，選D,Bresenham畫(huà)圓算法（7/7）,判別式的遞推關(guān)系 當(dāng)取H(xi+

20、1,yi)時(shí) i+1=(xi+1+1)2+(yi-1)2-R2= i+2(xi+1)+1 當(dāng)取V(xi,yi-1)時(shí) i+1=(xi+1)2+(yi-1-1)2-R2= i-2(yi-1)+1 當(dāng)取D(xi+1,yi-1)時(shí) i+1=(xi+1+1)2+(yi-1-1)2-R2= i+2(xi+1)-2(yi-1)+2,Bresenham_Circle(int r,int color) int x,y,delta1,delta2,direction; x=0;y=r; delta=2*(1-r); while(y=0) drawpixel(x,y,color); if(delta0) delt

21、a1=2*(delta+y)-1; if(delta1=0) direction=1; else direction=2; ,else if(delta0) delta2=2*(delta-x)-1; if(delta2=0) direction=2; else direction=3; else direction=2; switch(direction) case 1: x+l delta+=2*x+1; break;,case 2: x+; y-; delat+=2*(x-y+1); break; case 3: y-; delat+=(-2*y+1); break; /*switch*/ /*while*/ /*Bresenham_Circle*/,橢圓掃描轉(zhuǎn)換算法(1/8),橢圓方程 橢圓的性質(zhì)：對(duì)稱(chēng)性 掃描轉(zhuǎn)換算法 中點(diǎn)算法 Bresenham算法,橢圓方程和決策方程,橢圓掃描轉(zhuǎn)換算法(2/8),Derivation,橢圓掃描轉(zhuǎn)換算法(3/8),根據(jù)對(duì)稱(chēng)性考慮第一象限 A Dividing line Region 1 : unit ste