計算機圖形學課件第2講直線及圓生成算法

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

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

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

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

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

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

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

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

注意：(1)具體的語言環(huán)境使用的函數(shù)名可能不同，這里的函數(shù)名僅用于課堂教學坐標原點(2)屏幕坐標系統(tǒng)（GDI默認）為了方便表Y示，課堂上使用常用坐標系統(tǒng)。XOOpenGL中的課堂采用坐標系統(tǒng)可變化。6二維圖元的顯示用OpenGL實現(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)格

整型坐標系

幾點假設(shè)P1

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

直線段的寬度為1

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

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

中點畫線算法

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

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

微分：dy=kdx

實現(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中點畫線算法假設(shè)x坐標為xp的各像素點中，與直線最近者已確定為P(xp,yp)，那么，下一個與直線最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2(xp+1,yp+1)兩者之一。問題：P1orP2?M15中點畫線算法

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

問題：判斷距離理想直線最近的下一個像素點

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

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

a=y0-y1

b=x1-x0

c=x0y1-x1y0P2QM

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

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

中點？

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

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

當d<0，M在L(Q點)下方，取右上方P2為下一個象素；

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

若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中點畫線算法

增量算法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;}只有加法浮點運算}21中點畫線算法

增量算法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中點畫線算法例：利用中點畫線算法繪制一條直線：兩端點分別為P0(0,0)、P1(5,2)。解：首先計算斜率k=0.4,因為斜率k小于1，故適用推導。a=y0-y1=-2,b=x1-x0=5,d0=b=5d1=2a=-4,d2=2(a+b)=6首先繪制初始點(0,0)，并確定沿線路徑的其余像素位置為：x012345y0011222d1-33-15123中點畫線算法優(yōu)點：

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

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

使用最廣泛

與中點畫線法的思想類似

由誤差項符號決定下一個象素取正右方像素還是右上方像素25Bresenham畫線算法

工作原理：

過各行各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后確定該列像素中與此交點最近的像素。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畫線算法，繪制一條端點為P0(0,0)和P1(5,2)的直線。解：首先計算斜率k=0.4,d=0首先繪制初始點(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;}}只有加法浮點運算32斜率的問題

當斜率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中的應用

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

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

處理對象：圓心在原點的圓弧

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

圓的八對稱性

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

兩種直接計算方法

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

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

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

中點畫圓算法

Bresenham畫圓算法41中點畫圓法

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

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

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

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

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

d的增量表達：

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