計(jì)算機(jī)圖形學(xué)課件第2講直線及圓生成算法

直線及圓生成算法光柵圖形學(xué)DisplayFrameVideoMonitorprocessorbufferController2光柵圖形學(xué)x012...012...y3光柵圖形學(xué)4二維圖形的顯示

是指完成圖元的參數(shù)表示形式到點(diǎn)陣表示形式的轉(zhuǎn)換。通常也稱掃描轉(zhuǎn)換圖元(ScanConversion)

參數(shù)表示形式由圖形軟件包的開發(fā)者指定

點(diǎn)陣表示形式是光柵顯示系統(tǒng)刷新時(shí)所需的表示形式參數(shù):p0,p1點(diǎn)圖示法區(qū)域圖示法5二維圖形的顯示

像素操作函數(shù)（畫像素和讀像素）

最基本的繪圖函數(shù)

畫（寫）像素:SetPixel(x,y,color)

讀像素:GetPixel(x,y,*pixel)

注意：(1)具體的語言環(huán)境使用的函數(shù)名可能不同，這里的函數(shù)名僅用于課堂教學(xué)坐標(biāo)原點(diǎn)(2)屏幕坐標(biāo)系統(tǒng)（GDI默認(rèn)）為了方便表Y示，課堂上使用常用坐標(biāo)系統(tǒng)。XOOpenGL中的課堂采用坐標(biāo)系統(tǒng)可變化。6二維圖元的顯示用OpenGL實(shí)現(xiàn)讀/寫像素函數(shù)voidSetPixel(GLintx,GLinty,GLubyter,GLubyteg,GLubyteb){glColor3ub(r,g,b);glBegin(GL_POINTS)glVertex2i(x,y);glEnd();}GLubyte*GetPixel(GLintx,GLinty){GLubyte*rgb=newGLubyte[3];glReadPixels(x,y,1,1,GL_RGB,GL_UNSIGNED_BYTE,rgb);returnrgb;}7掃描轉(zhuǎn)換直線

掃描轉(zhuǎn)換直線

求與直線段充分接近的像素集，并以此像素集替代原連續(xù)直線段在屏幕上顯示

約束

像素間均勻網(wǎng)格

整型坐標(biāo)系

幾點(diǎn)假設(shè)P1

直線段為：PP0(x0,y0),P1(x1,y1)x0x10

直線段的寬度為1

直線段的斜率k[0,1]8直線生成算法

數(shù)值微分法（DDA）

中點(diǎn)畫線算法

Bresenham畫線算法9數(shù)值微分法（DDA）

算法實(shí)質(zhì)：用數(shù)值方法微分方程，同時(shí)對(duì)x和y各增加一個(gè)小增量來計(jì)算下一步的x,y值。已知過端點(diǎn)P0(x0,y0),P1(x1,y1)的直線段L：y=kx+b直線斜率為：y1y0x1x0k10數(shù)值微分法（DDA）

微分：dy=kdx

實(shí)現(xiàn)：dx=？

y=kdx=111數(shù)值微分法（DDA）intx1=…,x2=…,y1=…,y2=…;//Givenintx;floaty=y1,y=(y2-y1)/(x2-x1);for(x=x1;xx2;++x){setPixel(x,round(y));y=y+y;}13中點(diǎn)畫線算法假設(shè)x坐標(biāo)為xp的各像素點(diǎn)中，與直線最近者已確定為P(xp,yp)，那么，下一個(gè)與直線最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2(xp+1,yp+1)兩者之一。問題：P1orP2?M15中點(diǎn)畫線算法

令M為P1和P2的中點(diǎn)，易知M的坐標(biāo)為(xp+1,yp+0.5)。設(shè)Q是理想直線與垂直線x=xp+1的交點(diǎn)。顯然，若M在Q的下方，則P2離直線近，應(yīng)取為下一個(gè)像素；否則應(yīng)P1。16中點(diǎn)畫線算法

問題：判斷距離理想直線最近的下一個(gè)像素點(diǎn)

已知：線段兩端點(diǎn)(x0,y0)，(x1,y1)

直線方程：F(x,y)=ax+by+c=0

a=y0-y1

b=x1-x0

c=x0y1-x1y0P2QM

F(x,y)=0點(diǎn)位于直線上F(x,y)>0點(diǎn)在直線上方F(x,y)<0點(diǎn)在直線下方P=(xp,yp)P1

判斷交點(diǎn)Q在中點(diǎn)M的上方還是下方，只要把M的坐標(biāo)代入F(x,y)中，并判斷F(x,y)的符號(hào)17中點(diǎn)畫線算法

中點(diǎn)？

構(gòu)造判別式：d=F(M)=F(Xp+1,Y

由d＞0，d＜0可判定下一個(gè)象素p+0.5)

當(dāng)d<0，M在L(Q點(diǎn))下方，取右上方P2為下一個(gè)象素；

當(dāng)d>=0，M在L(Q點(diǎn))上方，取右方P1為下一個(gè)象素；M18中點(diǎn)畫線算法

若Yp+1=Yp+1d=F(Xp+2,Yp+1+0.5)-F(Xp+1,Yp+0.5)=a(Xp+2)+b(Yp+1+0.5)+c-a(Xp+1)+b(Yp+0.5)+c=a+b

若Yp+1=Ypd=F(Xp+2,Yp+1+0.5)-F(Xp+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c-a(Xp+1)+b(Yp+0.5)+c=a20中點(diǎn)畫線算法

增量算法intx1=…,x2=…,y1=…,y2=…;//Givenintx;floaty=y1,d=0.5*b;floatd1=a+b,d2=a;for(x=x1;xx2;++x){setPixel(x,y);if(d<0){y=y+1.0;d=d+d2;}else{d=y+d1;}只有加法浮點(diǎn)運(yùn)算}21中點(diǎn)畫線算法

增量算法intx1=…,x2=…,y1=…,y2=…;//Givenintx;inty=y1,d=b;intd1=(a+b)<<1,d2=a<<1;for(x=x1;xx2;++x){if(d<0){d02abdi2adi0y=y+1;d=d+d2;di1

}else{di2a2bdi0yidi0yi1di0d=y+d1;}setPixel(x,y);yi1

}xi1xi122中點(diǎn)畫線算法例：利用中點(diǎn)畫線算法繪制一條直線：兩端點(diǎn)分別為P0(0,0)、P1(5,2)。解：首先計(jì)算斜率k=0.4,因?yàn)樾甭蔾小于1，故適用推導(dǎo)。a=y0-y1=-2,b=x1-x0=5,d0=b=5d1=2a=-4,d2=2(a+b)=6首先繪制初始點(diǎn)(0,0)，并確定沿線路徑的其余像素位置為：x012345y0011222d1-33-15123中點(diǎn)畫線算法優(yōu)點(diǎn)：

只有整數(shù)運(yùn)算，不含乘除法

適于硬件實(shí)現(xiàn)24Bresenham畫線算法

使用最廣泛

與中點(diǎn)畫線法的思想類似

由誤差項(xiàng)符號(hào)決定下一個(gè)象素取正右方像素還是右上方像素25Bresenham畫線算法

工作原理：

過各行各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn)，然后確定該列像素中與此交點(diǎn)最近的像素。26Bresenham畫線算法

如何確定d

增量算法

設(shè)初始d=0

di+1=y(x+1)-yi+1=k

y(x)=kx+b

yi+1=yi

若d>=0.5

yi+1=yi+1

更新d=d-1

若d<0.5

yi+1=yi+127Bresenham畫線算法例：利用Bresenham畫線算法，繪制一條端點(diǎn)為P0(0,0)和P1(5,2)的直線。解：首先計(jì)算斜率k=0.4,d=0首先繪制初始點(diǎn)(0,0)，并確定沿線路徑的其余像素位置為：x12345y01122d0.4-0.20.2-0.4028Bresenham畫線算法intx1=…,x2=…,y1=…,y2=…;//Givenintx,y=y1;intdx=x2–x1,dy=y2–y1;floaterror=0.0for(x=x1;xx2;++x){setPixel(x,y);error=error+dy;if(error>=0.5*dx){++y;error=error-dx;}}29Bresenham畫線算法intx1=…,x2=…,y1=…,y2=…;//Givenintx,y=y1,floaterror=0.0,y=(y2-y1)/(x2-x1);for(x=x1;xx2;++x){setPixel(x,y);error=error+y;if(error>=0.5){++y;error=error-1.0;}}與DDA極為相似30Bresenham畫線算法intx1=…,x2=…,y1=…,y2=…;//Givenintx,y=y1,floaterror=0.0,y=(y2-y1)/(x2-x1);for(x=x1;xx2;++x){setPixel(x,y);error=error+y;if(error>=0.5){++y;error=error-1.0;}}只有加法浮點(diǎn)運(yùn)算32斜率的問題

當(dāng)斜率k>1,DDA,Bresenham算法：34斜率的問題

規(guī)則化：x每增加1，y最多增加1

交換x←→y,x0←→x0,y0←→y1區(qū)域|dx|>|dy|?xy1a1b2a2b3a3b4a4bTrue1k1k12b1bFalse1/k2a1aTrue-13a4aFalse-1/k3b4bTrue-1-k-1-k-1False-1/kTrue1False1/k35直線算法在GIS中的應(yīng)用

柵矢轉(zhuǎn)換36直線算法在GIS中的應(yīng)用

空間分析（三維地形上的通視分析）P1P2DEM37掃描轉(zhuǎn)換圓弧

處理對(duì)象：圓心在原點(diǎn)的圓弧

其它情況如何考慮?平移到原點(diǎn)，掃描轉(zhuǎn)換后再平移到原位置

圓的八對(duì)稱性

只需要掃描轉(zhuǎn)換八分之一圓弧即可38掃描轉(zhuǎn)換圓弧

兩種直接計(jì)算方法

離散點(diǎn)利用隱函數(shù)方程x2y2R2(xi,yiR2xi2)取整（xi，yi,r)

離散角度xRcosyRsin利用參數(shù)方程(round(Rcosi),round(Rsini))

缺點(diǎn)：開平方，三角函數(shù)運(yùn)算，計(jì)算量大，不可取40圓的生成算法

中點(diǎn)畫圓算法

Bresenham畫圓算法41中點(diǎn)畫圓法

假設(shè)中心在原點(diǎn)，半徑為整數(shù)R的圓的1b區(qū)域的1/8圓部分，如何從x=0到x=y順時(shí)針確定離理想圓弧最近的像素集合假設(shè)x坐標(biāo)為xp的各像素點(diǎn)中，與該圓弧最近者已確定，為P（xp,yp），那么，下一個(gè)與圓弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2(xp+1,yp-1)兩者之一。42中點(diǎn)畫圓法

令M為P1和P2的中點(diǎn)，易知M的坐標(biāo)為（xp+1,yp-0.5）。顯然，若M在圓內(nèi)，則P1離圓弧近，應(yīng)取為下一個(gè)像素；否則應(yīng)取P2。

F(x,y)=x2+y2-R2=0

將M點(diǎn)的坐標(biāo)（xp+1,yp-0.5）代入圓方程，得到判別式d：d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2–R243中點(diǎn)畫圓法

可知：d≥0點(diǎn)在圓外應(yīng)取P2作為下一個(gè)像素d<0點(diǎn)在圓內(nèi)應(yīng)取P1作為下一個(gè)像素

d的增量表達(dá)：

在d≥0的情況下，取右下方像素P2，而且再下一個(gè)象素的判別式為：d'=F