畫直線算法專業(yè)知識講座市公開課金獎市賽課一等獎課件

第二講直線生成圖形掃描轉換（光柵化）：確定一個像素集合，用于顯示一個圖形過程。步驟以下：1、確定相關像素2、用圖形顏色或其它屬性，對像素進行寫操作。對一維圖形，若不考慮線寬，則用一個像素寬直線來顯示圖形。二維圖形光柵化，即區(qū)域填充：確定像素集，填色或圖案。任何圖形光柵化，必須顯示在一個窗口內，不然不予顯示。即確定一個圖形哪些部分在窗口內，哪些在窗口外，即裁剪。 第1頁本講內容直線段掃描轉換算法：數(shù)值微分法DDA算法中點畫線法Bresenham畫線算法第2頁直線段掃描轉換算法直線掃描轉換:確定最正確迫近于該直線一組象素，而且按掃描線次序，對這些象素進行寫操作。在介紹三個慣用算法前，先介紹一個最輕易想到算法：直接計算法！第3頁0直接計算法

假定直線起點、終點分別為：（x0,y0),(x1,y1)，且都為整數(shù)。計算出斜率k=(y1-y0)/(x1-x0),在Y軸截距b=y0-k*x0

(Xi+1,kXi+1+b)(Xi,Yi)(Xi,Yi)柵格交點表示象素點位置。。。。第4頁

直接計算法

這么一來，只要給定x值，依據(jù)解析式馬上能夠計算出對應y值，然后輸出(x,round(y)).

這種方法直觀，但效率太低，因為每一步需要一次浮點乘法、一次浮點加法和一次舍入運算。(Xi+1,kXi+1+b)(Xi,Yi)(Xi,Yi)。。。。第5頁1數(shù)值微分法（ＤＤＡ）

假定直線起點、終點分別為：（x0,y0),(x1,y1)，且都為整數(shù)。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)。。。。第6頁數(shù)值微分(DDA)法基本思想已知過端點P0(x0,y0),P1(x1,y1)直線段Ly=kx+b直線斜率為考慮當x從xixi+1時y改變規(guī)律：設x=xi+1-xixi+1=xi+x第7頁數(shù)值微分(DDA)法計算yi+1=kxi+1+b=k (xi+x)+b =kxi+b+kx =yi+kx當x=1; yi+1=yi+k即：當x每遞增1，y遞增k(即直線斜率)；注意上述分析算法僅適合用于k

≤1情形。在這種情況下，x每增加1,y最多增加1。當k

1時，必須把x，y地位交換第8頁數(shù)值微分(DDA)法增量算法：在一個迭代算法中，假如每一步x、y值是用前一步值加上一個增量來取得，則稱為增量算法。DDA算法就是一個增量算法。第9頁數(shù)值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)

intx； floatdx,dy,y,k; dx,=x1-x0,dy=y1-y0; k=dy/dx,y=y0; for(x=x0;xx1,x++)

drawpixel(x,int(y+0.5),color); y=y+k;

第10頁數(shù)值微分(DDA)法例：畫直線段P0(0,0)--P1(5,2)k=0.4xyint(y+0.5) 0 0 0 0.4 0 0.81 3 1.21 4 1.6 2 5 2.0 2 第11頁數(shù)值微分(DDA)法缺點：在此算法中，y、k必須是float，且每一步都必須對y進行舍入取整，不利于硬件實現(xiàn)。第12頁2中點畫線法原理：假定直線斜率0<K<1，且已確定點亮象素點P（Xp

,Yp

）,則下一個與直線最靠近像素只能是P1點或P2點。設M為中點，Q為交點現(xiàn)需確定下一個點亮象素。第13頁中點畫線法當M在Q下方->P2離直線更近更近->取P2。M在Q上方->P1離直線更近更近->取P1M與Q重合，P1、P2任取一點。問題：怎樣判斷M與Q點關系？第14頁中點畫線法由常識知：若y=kx+b;F(x,y)=y-kx-b;則有第15頁中點畫線法假設直線方程為：ax+by+c=0(y=(-a/b)x-c/b)經(jīng)過兩點不能唯一確定a,b,c,取a=y0-y1,b=x1-x0,c=x0y1-x1y0F(x,y)=ax+by+c=b(y-(-a/b)x-c/b);則有∴欲判斷M點是在Q點上方還是在Q點下方，只需把M代入F(x,y),并檢驗它符號。第16頁中點畫線法結構判別式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當d<0，M在直線(Q點)下方，取右上方P2；當d>0，M在直線(Q點)上方，取右方P1；當d=0，選P1或P2均可，約定取P1；能否采取增量算法呢？第17頁中點畫線法若d0---->M在直線上方->取P1;此時再下一個象素判別式為d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量為a第18頁中點畫線法若d<0------>M在直線下方->取P2;此時再下一個象素判別式為d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量為a＋b第19頁中點畫線法畫線從(x0,y0)開始，d初值 d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b因為只用d符號作判斷，為了只包含整數(shù)運算,能夠用2d代替d來擺脫小數(shù)，提升效率。第20頁中點畫線法voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/第21頁中點畫線法例：用中點畫線法P0(0,0)P1(5,2)a=y0-y1=-2b=x1-x0=5d0=2a+b=1d1=2a=-4d2=2(a+b)=6i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 4 2 5

第22頁斜率不在[0,1]直線處理設起點和終點分別為(x0,y0)和(x1,y1)若k>1則(y0,x0)和(y1,x1)所確定直線斜率k€[0,1]，適合用于前面討論情形。對(y0,x0)和(y1,x1)所確定直線進行掃描轉換，每確定一組(x,y)，輸出(y,x)。(x0,y0)(y1,x1)(x1,y1)(y0,x0)第23頁斜率不在[0,1]直線處理若-1<k<0先對(x0,-y0)和(x1,-y1)所確定直線進行掃描轉換，每確定一組(x,y)，輸出(x,-y)。(x0,y0)(x1,-y1)(x1,y1)(x0,-y0)第24頁斜率不在[0,1]直線處理若k<-1對(-y0,x0)和(-y1,x1)所確定直線進行掃描轉換，每確定一組(x,y)，輸出(y,-x)。(x0,y0)(x1,-y1)(x1,y1)(x,-y0)(-y0,x0)(-y1,x1)第25頁3Bresenham算法(教材上介紹)假定直線段0≤k≤1基本原理：Bresenham算法原理第26頁誤差項d計算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1第27頁算法步驟：1.輸入直線兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、d=0、x=x0、y=y0。3.繪制點(x,y)。4.d更新為d+k，判斷d值。若d>0.5，則(x,y)更新為(x+1,y+1)，同時將d更新為d-1；不然(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。不然結束。第28頁改進1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1第29頁算法步驟為：1.輸入直線兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、e=-0.5、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+k，判斷e符號。若e>0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-1；不然(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。不然結束。第30頁改進2：用2e△x來替換ee初=-△x，每走一步有e=e+2△y。if(e>0)thene=e-2△xe=e+ke=e+△y/△x△xe=△xe+△ye=-0.52e=-1第31頁算法步驟：1.輸入直線兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、e=-△x、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+2△y，判斷e符號。若e>0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-2△x；不然(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。不然結束。第32頁Bresenham畫線算法BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy,e;dx=x1-x0;dy=y1-y0;e=-dx;x=x0;y=y0;for(i=0;i<=dx;i++){drawpixel(x,y,color);x++;e=e+2*dy;if(e>=0){e=e-2*dx;y++;}}}第33頁舉例：用Bresenham方法掃描轉換連接

兩點P0（0,0）和P1（5,2）直線段。

xyee0=-5;dx=5;dy=200-1103(-7)21-3311(-9)42-5

52-1Bresenham算法第34頁Bresenham畫線算法

在直線生成算法中Bresenham算法是最有效算法之一。令k=Δy/Δx，就0≤k≤1情況來說明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)因為k不一定是整數(shù)，由此式求出yi也不一定是整數(shù)，所以要用坐標為（xi,yir）象素來表示直線上點，其中yir表示最靠近yi整數(shù)。第35頁

設圖中xi列上已用（xi,yir）作為表示直線點，又設B點是直線上點，其坐標為（xi+1,yi+1），顯然下一個表示直線點（xi+1,yi+1,r）只能從圖中C或者D點中去選。設A為CD邊中點。若B在A點上面則應取D點作為（xi+1,yi+1,r），不然應取C點。xiXi+1Yi,rYi+1,rCDBAε(x)幾何意義為能確定B在A點上面或下面，令ε(xi+1)=yi+1-yir-0.5(2)若B在A下面，則有ε(xi+1)<0，反之，則ε(xi+1)>0。由圖可知yi+1,r=yir+1，若ε(xi+1)≥0(3)yi+1,r=yir，若ε(xi+1)≤0第36頁Bresenham畫線算法由式（2）和式（3）可得到ε(xi+2)=yi+2-yi+1,r-0.5=yi+1+k-yi+1,r-0.5（4）=yi+1-yir-0.5+k-1,當ε(xi+1)≥0=yi+1-yir-0.5+k,當ε(xi+1)≤0ε(xi+2)=ε(xi+1)+k-1,當ε(xi+1)≥0ε(xi+2)=ε(xi+1)+k,當ε(xi+1)≤0由式（1）和式（2）可得到ε(x1)=y0+1–y0r-0.5=y1–y0-0.5=k-0.5(5)第37頁程序以下：

BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;dx=x1-x0;dy=y1-y0;k=dy/dx;e=k-0.5;x=x0;y=y0;drawpixel(x,y,color);for(i=1;i<=dx;i++){x++;if(e>0){e=e-1;y++;}drawpixel(x,y,color);e=e+k;}}第38頁程序以下：

BresenhamLine(x0,y0,x1,y1,color)intx0,y0,x1,y1,color;{intx,y,dx,dy;floatk,e;