會(huì)計(jì)學(xué)1DDA算法Bresenham算法和畫(huà)家算法直線DDA算法描述設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點(diǎn)和終點(diǎn)坐標(biāo)，由直線的微分方程得=m=直線的斜率(2－1)可通過(guò)計(jì)算由x方向的增量△x引起y的改變來(lái)生成直線：xi+1=xi+△x(2－2)yi+1=yi+△y=yi+△x·m(2－3)也可通過(guò)計(jì)算由y方向的增量△y引起x的改變來(lái)生成直線：yi+1=yi+△y(2－4)xi+1=xi+△x=xi+△y/m(2－5)式(2－2)至(2－5)是遞推的。第1頁(yè)/共25頁(yè)直線DDA算法思想1、選定x2－x1和y2－y1中較大者作為步進(jìn)方向(假設(shè)x2－x1較大)，取該方向上的增量為一個(gè)象素單位(△x=1)，2、利用式(2－1)計(jì)算另一個(gè)方向的增量(△y=△x·m=m)。通過(guò)遞推公式(2－2)至(2－5)，把每次計(jì)算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。之所以取x2－x1和y2－y1中較大者作為步進(jìn)方向，是考慮沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。另外，算法實(shí)現(xiàn)中還應(yīng)注意直線的生成方向，以決定Δx及Δy是取正值還是負(fù)值。第2頁(yè)/共25頁(yè)第3頁(yè)/共25頁(yè)直線DDA算法實(shí)現(xiàn)1、已知直線的兩端點(diǎn)坐標(biāo)：(x1，y1)，(x2，y2)

2、已知畫(huà)線的顏色：color

3、計(jì)算兩個(gè)方向的變化量：dx=x2－x1

dy=y2－y1

4、求出兩個(gè)方向最大變化量的絕對(duì)值：

steps=max(|dx|，|dy|)

5、計(jì)算兩個(gè)方向的增量(考慮了生成方向)：

incx=dx/steps

inxy=dy/steps

6、設(shè)置初始象素坐標(biāo)：x=x1,y=y1

7、用循環(huán)實(shí)現(xiàn)直線的繪制：

for(i=1；i<=steps；i++)

{draw_pixel(x，y，color)；/*在(x，y)處，以color色畫(huà)點(diǎn)*/

x=x+incx；

y=y+incy；

}第4頁(yè)/共25頁(yè)直線DDA算法特點(diǎn)該算法簡(jiǎn)單，實(shí)現(xiàn)容易，但由于在循環(huán)中涉及實(shí)型數(shù)的運(yùn)算，因此生成直線的速度較慢。第5頁(yè)/共25頁(yè)Bresenham算法由直線的斜率確定選擇在x方向或y方向上每次遞增（減）1個(gè)單位，另一變量的遞增（減）量為0或1，它取決于實(shí)際直線與最近光柵網(wǎng)格點(diǎn)的距離，這個(gè)距離的最大誤差為0.5。

Bresenham算法是計(jì)算機(jī)圖形學(xué)典型的直線光柵化算法,可以有效地避免使用浮點(diǎn)運(yùn)算。算法原理：

算法特點(diǎn)：第6頁(yè)/共25頁(yè)Bresenham算法基本原理假定直線斜率k在0~1之間。此時(shí)，只需考慮x方向每次遞增1個(gè)單位，決定y方向每次遞增0或1。設(shè)

直線當(dāng)前點(diǎn)為(xi,y)

直線當(dāng)前光柵點(diǎn)為(xi,yi)則

下一個(gè)直線的點(diǎn)應(yīng)為(xi+1,y+k)

下一個(gè)直線的光柵點(diǎn)為右光柵點(diǎn)(xi+1,yi)（y方向遞增量0）

或?yàn)橛疑瞎鈻劈c(diǎn)(xi+1,yi+1)（y方向遞增量1）第7頁(yè)/共25頁(yè)

記直線與它垂直方向最近的下光柵點(diǎn)的誤差為d，有：d=(y+k)–yi，且

0≤d≤1

當(dāng)d<0.5：下一個(gè)象素應(yīng)取右光柵點(diǎn)(xi+1,yi)

當(dāng)d≥0.5：下一個(gè)象素應(yīng)取右上光柵點(diǎn)(xi+1,yi+1)Bresenham算法第8頁(yè)/共25頁(yè)如果直線的（起）端點(diǎn)在整數(shù)點(diǎn)上，誤差項(xiàng)d的初值：d0＝0，

x坐標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即：d＝d+k。

一旦d≥1，就把它減去1，保證d的相對(duì)性，且在0-1之間。Bresenham算法第9頁(yè)/共25頁(yè)Bresenham算法令e=d-0.5，關(guān)于d的判別式和初值可簡(jiǎn)化成：

e的初值e0=-0.5，增量亦為k;

e<0時(shí)，取當(dāng)前象素(xi,yi)的右方象素(xi+1,yi)；

e>0時(shí)，取當(dāng)前象素(xi,yi)的右上方象素(xi+1,yi+1)；

e=0時(shí)，可任取上、下光柵點(diǎn)顯示。Bresenham算法的構(gòu)思巧妙：它引入動(dòng)態(tài)誤差e，當(dāng)x方向每次遞增1個(gè)單位，可根據(jù)e的符號(hào)決定y方向每次遞增0或1。

e<0，y方向不遞增

e>0，y方向遞增1

x方向每次遞增1個(gè)單位，e=e+k因?yàn)閑是相對(duì)量，所以當(dāng)e>0時(shí)，表明e的計(jì)值將進(jìn)入下一個(gè)參考點(diǎn)（上升一個(gè)光柵點(diǎn)），此時(shí)須：e=e-1第10頁(yè)/共25頁(yè)Bresenham算法

通過(guò)(0,0)的所求直線的斜率大于0.5，它與x=1直線的交點(diǎn)離y=1直線較近，離y=0直線較遠(yuǎn)，因此取光柵點(diǎn)(1,1)比(1,0)更逼近直線；

如果斜率小于0.5，則反之；

當(dāng)斜率等于0.5，沒(méi)有確定的選擇標(biāo)準(zhǔn)，本算法選擇(1,1)1)Bresenham算法的實(shí)施——Rogers版第11頁(yè)/共25頁(yè)Bresenham算法x=x1

y=y1

dx=x2–x1

dy=y2–y1

//初始化誤差e

Error=dy/dx-0.5

//beginthemainloop

fori=1todx

WritePixel(x,y,value)

if(Error≥0)then//判斷斜率是否大于0.5

y=y+1

Error=Error-1

endif

x=x+1

Error=Error+dy/dx

nexti

finish1)Bresenham算法的實(shí)施——Rogers版第12頁(yè)/共25頁(yè)Bresenham算法2)整數(shù)Bresenham算法

上述Bresenham算法在計(jì)算直線斜率和誤差項(xiàng)時(shí)要用到浮點(diǎn)運(yùn)算和除法，采用整數(shù)算術(shù)運(yùn)算和避免除法可以加快算法的速度。由于上述Bresenham算法中只用到誤差項(xiàng)（初值Error=dy/dx-0.5）的符號(hào)因此只需作如下的簡(jiǎn)單變換：

NError=2*Error*dx即可得到整數(shù)算法，這使本算法便于硬件（固件）實(shí)現(xiàn)。第13頁(yè)/共25頁(yè)Bresenham算法x=x1

y=y1

dx=x2–x1

dy=y2–y1

//initializeetocompensateforanonzerointercept

NError=2*dy-dx

//Error=dy/dx-0.5;NError=2*Error*dx

//beginthemainloop

fori=1todx

WritePixel(x,y)

if(NError>=0)then

y=y+1

NError=NError–2*dx

//Error=Error-1

endif

x=x+1

NError=NError+2*dy

//Error=Error+dy/dx

nexti

finish第14頁(yè)/共25頁(yè)Bresenham算法3)一般Bresenham算法

要使上面的Bresenham算法適用于一般直線，只需對(duì)以下2點(diǎn)作出改造：

a、當(dāng)直線的斜率|k|>1時(shí)，改成y的增量總是1，再用Bresenham誤差判別式確定x變量是否需要增加1；

b、x或y的增量可能是“+1”或“-1”，視直線所在的象限決定。第15頁(yè)/共25頁(yè)畫(huà)家算法一、畫(huà)家算法的基本思想：先將畫(huà)面中的物體按其距離觀察點(diǎn)的遠(yuǎn)近進(jìn)行排序，結(jié)果存放在一張線形表中。距觀察點(diǎn)遠(yuǎn)者稱其優(yōu)先級(jí)高，放在表頭，距觀察點(diǎn)近者稱其優(yōu)先級(jí)低，放在表尾，這張表稱為深度優(yōu)先級(jí)表。然后按照從表頭到表尾的順序逐個(gè)繪制物體。由于距觀察者近的物體在表尾最后畫(huà)出，它覆蓋了遠(yuǎn)處的物體，最終在屏幕上產(chǎn)生了正確的遮擋關(guān)系。畫(huà)家算法看起來(lái)十分簡(jiǎn)單，但關(guān)鍵是如何對(duì)畫(huà)面中各種不同情況下的多邊形按深度排序，建立深度優(yōu)先表。假設(shè)視點(diǎn)在z軸正向無(wú)窮遠(yuǎn)處，視線方向沿著z軸負(fù)向看過(guò)去。如果z值大，離觀察點(diǎn)近；而z值小，離觀察點(diǎn)遠(yuǎn)。第16頁(yè)/共25頁(yè)畫(huà)家算法二、多邊形優(yōu)先級(jí)的考慮1、首先對(duì)一個(gè)簡(jiǎn)單的畫(huà)面，如圖（a）所示可以直接建立一個(gè)確定的深度優(yōu)先表，排序可以一次完成，不會(huì)有任何的歧義。例如，多邊形可按其最大或最小值排序，都可以很容易地把它們按深度大小分開(kāi)。2、但是，當(dāng)畫(huà)面略微復(fù)雜一點(diǎn)，如圖（b）所示，卻無(wú)法按簡(jiǎn)單的z向排序建立確定的深度優(yōu)先表，以確定每一個(gè)多邊形的優(yōu)先級(jí)。例如，若按最小z坐標(biāo)值（zmin）對(duì)P、Q排序，則在深度優(yōu)先表中，P應(yīng)排在Q之前，如按此順序?qū)、Q寫(xiě)入幀緩沖器，則Q將部分地遮擋P。但實(shí)際上是P部分地遮擋Q。如果按最大z坐標(biāo)值（zmax）對(duì)P、Q排序，同樣也不能得到正確的消隱結(jié)果。第17頁(yè)/共25頁(yè)畫(huà)家算法三、交叉覆蓋和循環(huán)覆蓋多邊形的優(yōu)先級(jí)考慮對(duì)更復(fù)雜的情況，如圖所示，出現(xiàn)的困難更多。圖（a）、（b）均有交叉覆蓋或循環(huán)遮擋的情況。如在圖（a）中，P在Q的前面，Q在R的前面，而R反過(guò)來(lái)又在P的前面。在圖（b）中，P在Q的前面，而Q又在P的前面。對(duì)它們均無(wú)法直接建立確定的深度優(yōu)先表。第18頁(yè)/共25頁(yè)畫(huà)家算法四、解決深度優(yōu)先級(jí)沖突的排序算法假定視點(diǎn)在Z軸正向無(wú)窮遠(yuǎn)處，則該算法敘述如下：

1、計(jì)算多邊形最小深度值z(mì)min，并以此值的優(yōu)先級(jí)進(jìn)行排序，建立初步的深度優(yōu)先表。表中第一個(gè)元素是對(duì)應(yīng)有最小zmin值的多邊形，標(biāo)記為P，優(yōu)先級(jí)最高。表中第二個(gè)多邊形標(biāo)記為Q。

2、考察P和Q之間的關(guān)系：（1）若P上離視點(diǎn)最近的頂點(diǎn)Pzmax比Q上離視點(diǎn)最遠(yuǎn)的頂點(diǎn)Qzmin還遠(yuǎn)，Qzmin≥Pzmax則P不遮擋Q，將P寫(xiě)入幀緩沖區(qū)，見(jiàn)圖示。第19頁(yè)/共25頁(yè)畫(huà)家算法（2）若Qzmin＜Pzmax，那么P不但有遮擋Q的可能，而且還可能部分地遮擋表上Q之后的任一滿足Rzmin＜Pzmax的多邊形R。我們把所有這種有可能被P所遮擋的多邊形的全體記為{Q}。為了進(jìn)一步確定P是否真正遮擋{Q}中的多邊形，做以下逐步的測(cè)試，如果對(duì){Q}中每個(gè)Q，都能通過(guò)以下問(wèn)題中任一個(gè)，那么P不會(huì)遮擋{Q}，因而可將P寫(xiě)入幀緩沖區(qū)中去。第20頁(yè)/共25頁(yè)畫(huà)家算法所提出的問(wèn)題是：①P和Q的外接最小包圍盒在X方向不相交嗎？

②P和Q的外接最小包圍盒在Y方向不相交嗎？

③