《圖形顯示軟件》PPT課件

《《圖形顯示軟件》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、計(jì)算機(jī)圖形顯示技術(shù)2第十一講圖形軟件Bresenham畫線算法圓的生成算法Bresenham畫圓法中點(diǎn)畫圓法區(qū)域填充算法掃描線填充算法邊界填充算法3圖形軟件——Bresenham畫線算法AboutBresenhamE.JackBresenham——ProfessorofComputerSciencePh.D.,StanfordUniversity,1964MSIE,StanfordUniversity,1960BSEE,UniversityofNewMexico,1959Retiredfrom27yearsse

2、rviceatIBMasaSeniorTechnicalStaffMemberin1987.Havetaught10yearsatWinthrop.Holderoffivepatents.4圖形軟件——Bresenham畫線算法Bresenham算法該算法由Bresenham在1965年提出，是目前使用較為廣泛的一種掃描轉(zhuǎn)換算法，可用于直線、圓弧等圖元的掃描轉(zhuǎn)換。5圖形軟件——Bresenham畫線算法Bresenham畫線算法基本思想過各行各列像素中心構(gòu)造一組假想的柵格按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直

3、網(wǎng)格線的交點(diǎn)，然后根據(jù)誤差項(xiàng)的符號(hào)確定該列象素中與此交點(diǎn)最近的象素6圖形軟件——Bresenham畫線算法Bresenham畫線算法設(shè)直線從起點(diǎn)（x1,y1）到終點(diǎn)（x2,y2）設(shè)直線方程為：y=kx+b其中b=y1-k*x17圖形軟件——Bresenham畫線算法Bresenham畫線算法若直線斜率k∈[0,1]且x2>x1的情況（1a象限）根據(jù)即DDA算法的討論有：xi+1=xi+1(1)yi+1=yi+k(2)在1a象限里，當(dāng)直線光柵化時(shí)，x每次都增加1個(gè)單元：xi+1=xi+18圖形軟件——Bresen

4、ham畫線算法Bresenham畫線算法由于k不一定是整數(shù)，因此由(2)式求出的y也不一定是整數(shù)。所以要用最靠近y的整數(shù)yi來代替y假設(shè)直線上第i個(gè)像素坐標(biāo)為(xi,yi)，那么，它的下一個(gè)點(diǎn)的像素點(diǎn)的可能位置為(xi+1,yi)或(xi+1,yi+1)。如圖：9圖形軟件——Bresenham畫線算法Bresenham畫線算法若直線斜率k∈[0,1]且x2>x1的情況（1a象限）如上圖在x=xi+1處，直線上y的值y=k(xi+1)+b該點(diǎn)距離點(diǎn)(xi+1,yi)和點(diǎn)(xi+1,yi+1)的距離分別為d1和d2

5、：d1=y-yi=k(xi+1)+b-yid2=yi+1-y=yi+1-k(xi+1)-b因此，這兩個(gè)距離的差為：d1-d2=2k(xi+1)-2yi+2b-1(1)10圖形軟件——Bresenham畫線算法Bresenham畫線算法根據(jù)（1）式，作如下討論分析：當(dāng)d1-d2>0時(shí)，說明直線上的理論點(diǎn)距離(xi+1,yi+1)較近，因此下一個(gè)直線像素點(diǎn)應(yīng)取(xi+1,yi+1)。當(dāng)d1-d2<0時(shí)，說明直線上的理論點(diǎn)距離(xi+1,yi)較近，因此下一個(gè)直線像素點(diǎn)應(yīng)取(xi+1,yi)。當(dāng)d1-d2=0時(shí)，說明

6、直線上的理論點(diǎn)距離上、下兩個(gè)像素點(diǎn)的距離相等，因此規(guī)定取(xi+1,yi+1)作為下一個(gè)直線像素點(diǎn)11圖形軟件——Bresenham畫線算法Bresenham畫線算法若直線斜率k∈[0,1]且x2>x1的情況（1a象限）因此，利用（d1-d2）的符號(hào)就可以決定下一個(gè)像素點(diǎn)的選擇然而含有變量xi、yi，不利于計(jì)算。為此，我們構(gòu)造一個(gè)新的判別式：pi=?x*(d1-d2)=2xi?y-2yi?x+c（2）其中：?x=(x2-x1)>0，因此pi與(d1-d2)符號(hào)相同；?y=y2-y1；c=2?y+?x(2b-1)

7、12圖形軟件——Bresenham畫線算法Bresenham畫線算法若直線斜率k∈[0,1]且x2>x1的情況（1a象限）①以i+1代入式(2)中的i，得：pi+1=?x*(d1-d2)=2xi+1?y-2yi+1?x+c（3）②將式(3)減去式(2)，并由xi+1=xi+1可得：pi+1=pi+2?y-2?x(yi+1-yi)（4）③假設(shè)直線上的初始端點(diǎn)恰好是其像素點(diǎn)的坐標(biāo)，則將x1,y1和b代入式（2）中的xi,yi可到pi的初始值p1=2x1?y-2y1?x+2?y+?x[2(y1-kx1)-1]=2?y

8、-?x（5）13圖形軟件——Bresenham畫線算法Bresenham畫線算法若直線斜率k∈[0,1]且x2>x1的情況（1a象限）利用上面構(gòu)造的誤差判別變量，可得第1a象限內(nèi)的直線Bresenham算法：p1=2?y-?xxi+1=xi+1yi+1=yi+1,pi+1=pi+2(?y-?x)當(dāng)pi≥0時(shí)yi+1=yi,pi+1=pi+2?y當(dāng)pi<0時(shí)14圖形軟件——Bresenh