第03部分計(jì)算機(jī)圖形學(xué)直線段掃描轉(zhuǎn)換課件

直線段的掃描轉(zhuǎn)換Rayray@李輝副教授直線段的掃描轉(zhuǎn)換Ray李輝副教授1內(nèi)容光柵圖形直線的掃描轉(zhuǎn)換數(shù)值微分法(DDA)中點(diǎn)畫線法Bresenham算法第3部分直線段的掃描轉(zhuǎn)換內(nèi)容光柵圖形第3部分直線段的掃描轉(zhuǎn)換光柵圖形光柵圖形光柵顯示器上顯示的圖形，稱之為光柵圖形光柵顯示器可以看作是一個象素矩陣，在光柵顯示器上顯示的任何一個圖形，實(shí)際上都是一些具有一種或多種顏色和灰度象素的集合。對一個具體的光柵顯示器來說，象素個數(shù)是有限的，象素的顏色和灰度等級也是有限的，象素是有大小的，所以光柵圖形只是近似的實(shí)際圖形。如何使光柵圖形最完美地逼近實(shí)際圖形，便是光柵圖形學(xué)要研究的內(nèi)容。

第3部分直線段的掃描轉(zhuǎn)換光柵圖形光柵圖形第3部分直線段的掃描轉(zhuǎn)換圖形的掃描轉(zhuǎn)換確定最佳逼近圖形的象素集合，并用指定的顏色和灰度設(shè)置象素的過程稱為圖形的掃描轉(zhuǎn)換或光柵化。

光柵化問題對于一維圖形，在不考慮線寬時，用一個象素寬的直線或曲線來顯示圖形。二維圖形的光柵化必須確定區(qū)域?qū)?yīng)的象素集，將各個象素設(shè)置成指定的顏色和灰度，也稱之為區(qū)域填充。第3部分直線段的掃描轉(zhuǎn)換圖形的掃描轉(zhuǎn)換第3部分直線段的掃描轉(zhuǎn)換圖形光柵化后，顯示在屏幕上的一個窗口里，超出窗口的部分不予顯示。確定一個圖形的哪些部分在窗口內(nèi)，必須顯示；哪些部分落在窗口之外，不予顯示，這需要對圖形進(jìn)行裁剪。在光柵圖形中，非水平和垂直的直線用象素集合表示時，會呈鋸齒狀，這種現(xiàn)象稱之為走樣；用于減少或消除走樣的技術(shù)稱為反走樣。第3部分直線段的掃描轉(zhuǎn)換圖形光柵化后，顯示在屏幕上的一個窗口里，超出窗口的部分不予顯直線的掃描轉(zhuǎn)換直線數(shù)學(xué)上的直線是沒有寬度、由無數(shù)個點(diǎn)構(gòu)成的集合。光柵顯示器只能近似地顯示直線。直線的掃描轉(zhuǎn)換當(dāng)我們對直線進(jìn)行光柵化時，需要在顯示器有限個象素中，確定最佳逼近該直線的一組象素，并且按掃描線順序，對這些象素進(jìn)行寫操作，這個過程稱為直線的掃描轉(zhuǎn)換。數(shù)值微分法（DDA）中點(diǎn)畫線法Bresenham算法第3部分直線段的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換直線第3部分直線段的掃描轉(zhuǎn)換數(shù)值微分法（DDA）分析設(shè)過端點(diǎn)P0(x0

,y0)、P1(x1

,y1)的直線段為L(P0

,P1)，斜率L的起點(diǎn)P0的橫坐標(biāo)x0向L的終點(diǎn)P1的橫坐標(biāo)x1步進(jìn)，取步長=1(個象素)，用L的直線方程y=kx+b計(jì)算相應(yīng)的y坐標(biāo)，并取象素點(diǎn)(x,round(y))作為當(dāng)前點(diǎn)的坐標(biāo)。第3部分直線段的掃描轉(zhuǎn)換數(shù)值微分法（DDA）分析第3部分直線段的掃描轉(zhuǎn)換yi+1=kxi+1+b

=kxi+b+kDx

=yi+kDx當(dāng)Dx=1時yi+1

=yi+k。也就是說，當(dāng)x每遞增1，y遞增k(即直線斜率)。

第3部分直線段的掃描轉(zhuǎn)換yi+1=kxi+1+b第3部分直線段的掃描轉(zhuǎn)換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；x<x1；x++){drawpixel(x,int(y+0.5),color);y=y+k;}第3部分直線段的掃描轉(zhuǎn)換DDA畫線算法程序第3部分直線段的掃描轉(zhuǎn)換舉例連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段

xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5第3部分直線段的掃描轉(zhuǎn)換舉例xint(y+0.5)y+0.5000100.4+0.5算法分析上述分析的算法僅適用于|k|≤1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng)

|k|>1時，必須把x，y地位互換，y每增加1，x相應(yīng)增加1/k。在這個算法中，y與k必須用浮點(diǎn)數(shù)表示，而且每一步都要對y進(jìn)行四舍五入后取整，這使得它不利于硬件實(shí)現(xiàn)。

第3部分直線段的掃描轉(zhuǎn)換算法分析第3部分直線段的掃描轉(zhuǎn)換中點(diǎn)畫線法分析假定直線斜率k在0~1之間，當(dāng)前象素點(diǎn)為（xp,yp），則下一個象素點(diǎn)有兩種可選擇點(diǎn)P1（xp+1,yp）或P2（xp+1,yp+1）。設(shè)P1與P2的中點(diǎn)（xp+1,yp+0.5）稱為M，Q為直線與x=xp+1垂線的交點(diǎn)。當(dāng)M在Q的下方時，則取P2應(yīng)為下一個象素點(diǎn)；當(dāng)M在Q的上方時，則取P1為下一個象素點(diǎn)。第3部分直線段的掃描轉(zhuǎn)換中點(diǎn)畫線法分析第3部分直線段的掃描轉(zhuǎn)換過點(diǎn)(x0,y0)、(x1,y1)的直線段L的方程式為F(x,y)=ax+by+c=0其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0，欲判斷中點(diǎn)M在Q點(diǎn)的上方還是下方，只要把M代入F（x，y），并判斷它的符號即可。為此，我們構(gòu)造判別式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當(dāng)d<0時，M在L(Q點(diǎn))下方，取P2為下一個象素；當(dāng)d>0時，M在L(Q點(diǎn))上方，取P1為下一個象素；當(dāng)d=0時，選P1或P2均可，約定取P1為下一個象素。第3部分直線段的掃描轉(zhuǎn)換過點(diǎn)(x0,y0)、(x1,y1)的直線段L的方程式為第3d是xp,yp的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。若當(dāng)前象素處于d>=0情況，則取正右方象素P1(xp+1,yp),要判再下一個象素位置，應(yīng)計(jì)算

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a增量為a若d<0時，則取右上方象素P2(xp+1,yp+1)。要判斷再下一象素，則要計(jì)算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b增量為a＋b第3部分直線段的掃描轉(zhuǎn)換d是xp,yp的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。第畫線從(x0,y0)開始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b因?yàn)?/p>

F(x0,y0)=0，所以d0=a+0.5b由于我們使用的只是d的符號，而且d的增量都是整數(shù)，只是初始值包含小數(shù)。因此，可以用2d代替d來擺脫小數(shù)。第3部分直線段的掃描轉(zhuǎn)換畫線從(x0,y0)開始，d的初值第3部分直線段的掃描轉(zhuǎn)中點(diǎn)畫線法算法程序：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*/第3部分直線段的掃描轉(zhuǎn)換中點(diǎn)畫線法算法程序：第3部分直線段的掃描轉(zhuǎn)換舉例用中點(diǎn)畫線方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。xyd00110-321331-1425第3部分直線段的掃描轉(zhuǎn)換舉例xyd00110-321331-1425第3部分直線段Bresenham算法分析設(shè)直線方程為yi+1=yi+k(xi+1-xi)+k下一個象素的列坐標(biāo)為xi＋1，而行坐標(biāo)要么為yi，要么遞增1為yi＋1。誤差項(xiàng)d的初值d0＝0，x坐標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即d＝d＋k。是否增1取決于誤差項(xiàng)d的值。第3部分直線段的掃描轉(zhuǎn)換Bresenham算法分析第3部分直線段的掃描轉(zhuǎn)換一旦d≥1，就把它減去1，這樣保證d在0、1之間。當(dāng)d≥0.5時，直線與垂線x=xi＋1交點(diǎn)最接近于當(dāng)前象素(xi，yi)的右上方象素(xi＋1，yi＋1)當(dāng)d<0.5時，更接近于右方象素(xi＋1，yi)。為方便計(jì)算，令e＝d－0.5，e的初值為－0.5，增量為k。當(dāng)e≥0時，取當(dāng)前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而當(dāng)e<0時，取(xi，yi)右方象素(xi＋1，yi)。第3部分直線段的掃描轉(zhuǎn)換一旦d≥1，就把它減去1，這樣保證d在0、1之間。第3部分Bresenham畫線算法程序：voidBresenhamline(intx0,inty0,intx1,inty1,intcolor){intx,y,dx,dy；

floatk,e;

dx=x1-x0；dy=y1-y0；k=dy/dx；

e=-0.5；x=x0；y=y0；

for(i=0；i<dx；i++)

{drawpixel(x,y,color);

x++；e+=k;

if(e>=0)

{y++；e=e-1;}

}}第3部分直線段的掃描轉(zhuǎn)換Bresenham畫線算法程序：第3部分直線段的掃描轉(zhuǎn)換舉例用Bresenham方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。

xye00-0.510-0.121-0.731-0.342-0.952-0.5第3部分直線段的掃描轉(zhuǎn)換舉例xye00-0.510-0.121-0.731-0.34改進(jìn)前面的Bresenham算法在計(jì)算直線斜率與誤差項(xiàng)時用到小數(shù)與除法?？梢愿挠谜麛?shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號，因此可將誤差項(xiàng)替換為： 2*e*dx

第3部分直線段的掃描轉(zhuǎn)換改進(jìn)第3部分直線段的掃描轉(zhuǎn)換改進(jìn)后的Bresenham算法程序voidInterBresenhamline(intx0,inty0,intx1,inty1,intcolor){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){y++;e=e-2*dx;}

}}第3部分直線段的掃描轉(zhuǎn)換改進(jìn)后的Bresenham算法程序第3部分直線段的掃描轉(zhuǎn)換直線段的掃描轉(zhuǎn)換Rayray@李輝副教授直線段的掃描轉(zhuǎn)換Ray李輝副教授24內(nèi)容光柵圖形直線的掃描轉(zhuǎn)換數(shù)值微分法(DDA)中點(diǎn)畫線法Bresenham算法第3部分直線段的掃描轉(zhuǎn)換內(nèi)容光柵圖形第3部分直線段的掃描轉(zhuǎn)換光柵圖形光柵圖形光柵顯示器上顯示的圖形，稱之為光柵圖形光柵顯示器可以看作是一個象素矩陣，在光柵顯示器上顯示的任何一個圖形，實(shí)際上都是一些具有一種或多種顏色和灰度象素的集合。對一個具體的光柵顯示器來說，象素個數(shù)是有限的，象素的顏色和灰度等級也是有限的，象素是有大小的，所以光柵圖形只是近似的實(shí)際圖形。如何使光柵圖形最完美地逼近實(shí)際圖形，便是光柵圖形學(xué)要研究的內(nèi)容。

第3部分直線段的掃描轉(zhuǎn)換光柵圖形光柵圖形第3部分直線段的掃描轉(zhuǎn)換圖形的掃描轉(zhuǎn)換確定最佳逼近圖形的象素集合，并用指定的顏色和灰度設(shè)置象素的過程稱為圖形的掃描轉(zhuǎn)換或光柵化。

光柵化問題對于一維圖形，在不考慮線寬時，用一個象素寬的直線或曲線來顯示圖形。二維圖形的光柵化必須確定區(qū)域?qū)?yīng)的象素集，將各個象素設(shè)置成指定的顏色和灰度，也稱之為區(qū)域填充。第3部分直線段的掃描轉(zhuǎn)換圖形的掃描轉(zhuǎn)換第3部分直線段的掃描轉(zhuǎn)換圖形光柵化后，顯示在屏幕上的一個窗口里，超出窗口的部分不予顯示。確定一個圖形的哪些部分在窗口內(nèi)，必須顯示；哪些部分落在窗口之外，不予顯示，這需要對圖形進(jìn)行裁剪。在光柵圖形中，非水平和垂直的直線用象素集合表示時，會呈鋸齒狀，這種現(xiàn)象稱之為走樣；用于減少或消除走樣的技術(shù)稱為反走樣。第3部分直線段的掃描轉(zhuǎn)換圖形光柵化后，顯示在屏幕上的一個窗口里，超出窗口的部分不予顯直線的掃描轉(zhuǎn)換直線數(shù)學(xué)上的直線是沒有寬度、由無數(shù)個點(diǎn)構(gòu)成的集合。光柵顯示器只能近似地顯示直線。直線的掃描轉(zhuǎn)換當(dāng)我們對直線進(jìn)行光柵化時，需要在顯示器有限個象素中，確定最佳逼近該直線的一組象素，并且按掃描線順序，對這些象素進(jìn)行寫操作，這個過程稱為直線的掃描轉(zhuǎn)換。數(shù)值微分法（DDA）中點(diǎn)畫線法Bresenham算法第3部分直線段的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換直線第3部分直線段的掃描轉(zhuǎn)換數(shù)值微分法（DDA）分析設(shè)過端點(diǎn)P0(x0

,y0)、P1(x1

,y1)的直線段為L(P0

,P1)，斜率L的起點(diǎn)P0的橫坐標(biāo)x0向L的終點(diǎn)P1的橫坐標(biāo)x1步進(jìn)，取步長=1(個象素)，用L的直線方程y=kx+b計(jì)算相應(yīng)的y坐標(biāo)，并取象素點(diǎn)(x,round(y))作為當(dāng)前點(diǎn)的坐標(biāo)。第3部分直線段的掃描轉(zhuǎn)換數(shù)值微分法（DDA）分析第3部分直線段的掃描轉(zhuǎn)換yi+1=kxi+1+b

=kxi+b+kDx

=yi+kDx當(dāng)Dx=1時yi+1

=yi+k。也就是說，當(dāng)x每遞增1，y遞增k(即直線斜率)。

第3部分直線段的掃描轉(zhuǎn)換yi+1=kxi+1+b第3部分直線段的掃描轉(zhuǎn)換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；x<x1；x++){drawpixel(x,int(y+0.5),color);y=y+k;}第3部分直線段的掃描轉(zhuǎn)換DDA畫線算法程序第3部分直線段的掃描轉(zhuǎn)換舉例連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段

xint(y+0.5)y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5第3部分直線段的掃描轉(zhuǎn)換舉例xint(y+0.5)y+0.5000100.4+0.5算法分析上述分析的算法僅適用于|k|≤1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng)

|k|>1時，必須把x，y地位互換，y每增加1，x相應(yīng)增加1/k。在這個算法中，y與k必須用浮點(diǎn)數(shù)表示，而且每一步都要對y進(jìn)行四舍五入后取整，這使得它不利于硬件實(shí)現(xiàn)。

第3部分直線段的掃描轉(zhuǎn)換算法分析第3部分直線段的掃描轉(zhuǎn)換中點(diǎn)畫線法分析假定直線斜率k在0~1之間，當(dāng)前象素點(diǎn)為（xp,yp），則下一個象素點(diǎn)有兩種可選擇點(diǎn)P1（xp+1,yp）或P2（xp+1,yp+1）。設(shè)P1與P2的中點(diǎn)（xp+1,yp+0.5）稱為M，Q為直線與x=xp+1垂線的交點(diǎn)。當(dāng)M在Q的下方時，則取P2應(yīng)為下一個象素點(diǎn)；當(dāng)M在Q的上方時，則取P1為下一個象素點(diǎn)。第3部分直線段的掃描轉(zhuǎn)換中點(diǎn)畫線法分析第3部分直線段的掃描轉(zhuǎn)換過點(diǎn)(x0,y0)、(x1,y1)的直線段L的方程式為F(x,y)=ax+by+c=0其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0，欲判斷中點(diǎn)M在Q點(diǎn)的上方還是下方，只要把M代入F（x，y），并判斷它的符號即可。為此，我們構(gòu)造判別式:d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當(dāng)d<0時，M在L(Q點(diǎn))下方，取P2為下一個象素；當(dāng)d>0時，M在L(Q點(diǎn))上方，取P1為下一個象素；當(dāng)d=0時，選P1或P2均可，約定取P1為下一個象素。第3部分直線段的掃描轉(zhuǎn)換過點(diǎn)(x0,y0)、(x1,y1)的直線段L的方程式為第3d是xp,yp的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。若當(dāng)前象素處于d>=0情況，則取正右方象素P1(xp+1,yp),要判再下一個象素位置，應(yīng)計(jì)算

d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a增量為a若d<0時，則取右上方象素P2(xp+1,yp+1)。要判斷再下一象素，則要計(jì)算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b增量為a＋b第3部分直線段的掃描轉(zhuǎn)換d是xp,yp的線性函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。第畫線從(x0,y0)開始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b因?yàn)?/p>

F(x0,y0)=0，所以d0=a+0.5b由于我們使用的只是d的符號，而且d的增量都是整數(shù)，只是初始值包含小數(shù)。因此，可以用2d代替d來擺脫小數(shù)。第3部分直線段的掃描轉(zhuǎn)換畫線從(x0,y0)開始，d的初值第3部分直線段的掃描轉(zhuǎn)中點(diǎn)畫線法算法程序：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*/第3部分直線段的掃描轉(zhuǎn)換中點(diǎn)畫線法算法程序：第3部分直線段的掃描轉(zhuǎn)換舉例用中點(diǎn)畫線方法掃描轉(zhuǎn)換連接兩點(diǎn)P0（0,0）和P1（5,2）的直線段。xyd00110-321331-1425第3部分直線段的掃描轉(zhuǎn)換舉例xyd00110-321331-1425第3部分直線段Bresenham算法分析設(shè)直線方程為yi+1=yi+k(xi+1-xi)+k下一個象素的列坐標(biāo)為xi＋1，而行坐標(biāo)要么為yi，要么遞增1為yi＋1。誤差項(xiàng)d的初值d0＝0，x坐標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即d＝d＋k。是否增1取決于誤差項(xiàng)d的值。第3部分直線段的掃描轉(zhuǎn)換Bresenham算法分析第3部分直線段的掃描轉(zhuǎn)換一旦d≥1，就把它減去1，這樣保證d在0、1之間。當(dāng)d≥0.5時，直線與垂線x=xi＋1交點(diǎn)最接近于當(dāng)前象素(xi，yi)的右上方象素(xi＋1，yi＋1)當(dāng)d<0.5時，更接近于右方象素(xi＋1，yi)。為方便計(jì)算，令e＝d－0.5，e的初值為－