計(jì)算機(jī)圖形學(xué)第二章

1、第二章 直線掃描轉(zhuǎn)換算法n1.光柵圖形學(xué)n2.逐點(diǎn)畫(huà)線算法n3.DDA畫(huà)線算法n4.BRESENHAM畫(huà)線算法n5.關(guān)于線寬線型n6.Visual C+中基本繪圖函數(shù) 2.1 光柵圖形學(xué)n計(jì)算機(jī)圖形學(xué)已成為計(jì)算機(jī)技術(shù)中發(fā)展最快的領(lǐng)域，計(jì)算機(jī)圖形軟件也相應(yīng)得到快速發(fā)展。計(jì)算機(jī)繪圖顯示有屏幕顯示、打印機(jī)打印圖樣和繪圖機(jī)輸出圖樣等方式，其中用屏幕顯示圖樣是計(jì)算機(jī)繪圖的重要內(nèi)容。n計(jì)算機(jī)上常見(jiàn)的顯示器為光柵圖形顯示器，光柵圖形顯示器可以看作像素的矩陣。像素是組成圖形的基本元素，一般稱為“點(diǎn)”。通過(guò)點(diǎn)亮一些像素，滅掉另一些像素，即在屏幕上產(chǎn)生圖形。在光柵顯示器上顯示任何一種圖形必須在顯示器的相 應(yīng)像素點(diǎn)

2、上畫(huà)上所需顏色，即具有一種或多種顏色的像素集合構(gòu)成圖形。確定最佳接近圖形的像素集合，并用指定屬性寫(xiě)像素的過(guò)程稱為圖形的掃描轉(zhuǎn)換或光柵化。對(duì)于一維圖形，在不考慮線寬時(shí)，用一個(gè)像素寬的直、曲線來(lái)顯示圖形。二維圖形的光柵化必須確定區(qū)域?qū)?yīng)的像素集，并用指定的屬性或圖案進(jìn)行顯示，即區(qū)域 填充。n什么是光柵圖形學(xué)？ 光柵顯示器 圖形光柵化、 光柵化圖形的處理n光柵顯示器上顯示的圖形，稱之為光柵圖形。光柵顯示器可以看作是一個(gè)象素矩陣，在光柵顯示器上顯示的任何一個(gè)圖形，實(shí)際上都是一些具有一種或多種顏色和灰度象素的集合。由于對(duì)一個(gè)具體的光柵顯示器來(lái)說(shuō)，象素個(gè)數(shù)是有限的，象素的顏色和灰度等級(jí)也是有限的，象素是有

3、大小的，所以光柵圖形只是近似的實(shí)際圖形。如何使光柵圖形最完美地逼近實(shí)際圖形，便是光柵圖形學(xué)要研究的內(nèi)容。以后，我們提到“顯示器”時(shí)，如未特別聲明，均指光柵顯示器。 光柵圖形學(xué)算法特點(diǎn)n1.要充分考慮屏幕像素，光柵的特性，如何逼近真實(shí)圖形，如何減小這個(gè)誤差，如何提高圖形處理速度是圖形學(xué)算法的追求。n2.編寫(xiě)計(jì)算機(jī)圖形學(xué)算法，最好還要具備計(jì)算方法的基礎(chǔ)知識(shí)，了解計(jì)算機(jī)是如何求解方程，了解求解過(guò)程與實(shí)際人思維的不同，也就是把人思維的計(jì)算方法翻譯到機(jī)器，這就是計(jì)算方法研究的內(nèi)容。光柵圖形學(xué)的研究?jī)?nèi)容直線段的掃描轉(zhuǎn)換算法圓弧的掃描轉(zhuǎn)換算法多邊形的掃描轉(zhuǎn)換與區(qū)域填充字符裁剪反走樣消隱n直線段是最基本的圖形

4、，因此直線段生成的質(zhì)量好壞與速度快慢將直接影響整個(gè)圖形生成的質(zhì)量和速度。所以直線段生成算法在圖形軟件設(shè)計(jì)中起著關(guān)鍵的作用。n如果已知屏幕中直線段的二個(gè)端點(diǎn)，可以有多種不同的數(shù)學(xué)方法來(lái)決定應(yīng)改變?cè)诙它c(diǎn)之間的哪些像素的亮度值才能顯示出二點(diǎn)間的直線，生成直線段的算法之間區(qū)別主要是判別和生成x，y增量過(guò)程和方法不同，所能適應(yīng)的設(shè)備環(huán)境也不同。下面介紹三種基本的畫(huà)線算法。光柵圖形中點(diǎn)的表示(x,y)坐標(biāo)地址線性表地址線性表1D表示顯示屏幕顯示屏幕2D表示像素由其左下角坐標(biāo)表示像素由其左下角坐標(biāo)表示光柵圖形中點(diǎn)的表示xyxmaxxminymaxymin地址地址 = (xmax-xmin) * (y-ym

5、in) + (x-xmin) + 基地址基地址每行像素點(diǎn)數(shù)每行像素點(diǎn)數(shù)行數(shù)行數(shù)行中位置行中位置n在光柵顯示器的熒光屏上生成一個(gè)對(duì)象，實(shí)質(zhì)上是往幀緩存寄存器的相應(yīng)單元中填入數(shù)據(jù)。畫(huà)一條從（x1, y1）到（x2, y2）的直線，實(shí)質(zhì)上是一個(gè)發(fā)現(xiàn)最佳逼近直線的象素序列，并填入色彩數(shù)據(jù)的過(guò)程。這個(gè)過(guò)程也稱為直線光柵化。 直線掃描轉(zhuǎn)換的本質(zhì)n直線的掃描轉(zhuǎn)換確定最佳逼近于該直線的一組象素按掃描線順序，對(duì)這些象素進(jìn)行寫(xiě)操作，對(duì)一維圖形，不考慮線寬，則用一個(gè)像素寬的直線來(lái)顯示圖形。任何圖形的光柵化，必須顯示在一個(gè)窗口內(nèi)，否則不予顯示。即確定一個(gè)圖形的哪些部分在窗口內(nèi)，哪些在窗口外，即裁剪。n圖形顯示前需要：

6、掃描轉(zhuǎn)換+裁剪n裁剪-掃描轉(zhuǎn)換：最常用，節(jié)約計(jì)算時(shí)間。n掃描轉(zhuǎn)換-裁剪：算法簡(jiǎn)單；2.2 逐點(diǎn)畫(huà)線算法n在數(shù)學(xué)上，理想的直線是沒(méi)有寬度在數(shù)學(xué)上，理想的直線是沒(méi)有寬度的，由無(wú)數(shù)個(gè)點(diǎn)構(gòu)成的集合。當(dāng)我的，由無(wú)數(shù)個(gè)點(diǎn)構(gòu)成的集合。當(dāng)我們對(duì)直線進(jìn)行光柵化時(shí)，只能在顯們對(duì)直線進(jìn)行光柵化時(shí)，只能在顯示器所給定的有限個(gè)像素中，確定示器所給定的有限個(gè)像素中，確定最佳逼近于該直線的一組像素。用最佳逼近于該直線的一組像素。用寫(xiě)點(diǎn)方式對(duì)像素進(jìn)行寫(xiě)操作，這就寫(xiě)點(diǎn)方式對(duì)像素進(jìn)行寫(xiě)操作，這就是通常所說(shuō)的用顯示器繪制直線，是通常所說(shuō)的用顯示器繪制直線，或直線的掃描轉(zhuǎn)換或直線的掃描轉(zhuǎn)換 逐點(diǎn)畫(huà)線算法(1/19)n逐點(diǎn)比較法算法的

7、基本思想是：在繪制直線的過(guò)程中，每繪制一個(gè)點(diǎn)就與原直線進(jìn)行比較，根據(jù)比較的結(jié)果決定下一步的走向，這樣一步一步逼近直線，逐點(diǎn)比較法的執(zhí)行過(guò)程如下：偏差判別開(kāi)始X方向移動(dòng)終點(diǎn)判別是結(jié)束偏差計(jì)算否Y方向移動(dòng)逐點(diǎn)畫(huà)線算法(2/19)n逐點(diǎn)比較法是針對(duì)筆式繪圖機(jī)提出的。根據(jù)繪圖機(jī)的結(jié)構(gòu)原理及數(shù)字控制原理， 繪圖機(jī)的筆架可能的移動(dòng)方向(稱為走步方向)有八個(gè)：+X、 -X、+Y、-Y、+X+Y、-X+Y、-X-Y、+X-Y。 其中+X、-X、+Y、-Y四個(gè)走步方向是一般繪圖機(jī)都提供的，稱為基本走步方向?？梢?jiàn)，繪圖機(jī)的基本繪圖元素是與走步方向相對(duì)應(yīng)的小直線段。繪圖機(jī)所畫(huà)的一般直線和曲線，實(shí)際上是由許多小直線段

8、所組成的折線來(lái)逼近的。逐點(diǎn)畫(huà)線算法(3/19) 根據(jù)所畫(huà)圖線的已知條件(如直線兩個(gè)端點(diǎn)坐標(biāo)等)計(jì)算畫(huà)圖所需要的一系列中間點(diǎn)(即折線的端點(diǎn))的坐標(biāo)，稱為插補(bǔ)運(yùn)算。插補(bǔ)運(yùn)算可用軟件或硬件實(shí)現(xiàn)，不少繪圖機(jī)采用插補(bǔ)器(或稱線發(fā)生器、弧發(fā)生器)來(lái)完成插補(bǔ)運(yùn)算，目的在于提高圖線生成速度。逐點(diǎn)比較法可用于插補(bǔ)運(yùn)算。 逐點(diǎn)畫(huà)線算法(4/19)逐點(diǎn)畫(huà)線算法(5/19)n若畫(huà)第一象限的直線OA，如上頁(yè)圖所示，起點(diǎn)為O(0，0)， 終點(diǎn)為A(xa, ya)，設(shè)繪圖筆當(dāng)前的位置為K(xk,yk)，這里坐標(biāo)均為局部坐標(biāo)。點(diǎn)K相對(duì)于直線OA的位置有三種情況：點(diǎn)K在OA上方，點(diǎn)K在OA上以及點(diǎn)K在OA下方。為判斷點(diǎn)K與OA

9、的相對(duì)位置，引入偏差函數(shù)F(k)。 nF(k)=x(a)y(k)-x(k)y(a)當(dāng)K在OA上時(shí)，F(xiàn)(k)=0; K在OA上方時(shí)，F(xiàn)(k)0; K在OA下方時(shí)，F(xiàn)(k)0。 逐點(diǎn)畫(huà)線算法(6/19)n對(duì)第一象限內(nèi)直線的生成規(guī)定如下：n 當(dāng)F(k)0時(shí)，繪圖筆從當(dāng)前位置沿+X方向走一步，記作+x； 當(dāng)F(k)0時(shí)，繪圖筆從當(dāng)前位置沿+Y方向走一步，記作+y；在繪圖筆到達(dá)新的位置時(shí)，應(yīng)計(jì)算出新位置的偏差，為判斷繪圖筆下一步走向作準(zhǔn)備。n 繪圖筆走+x時(shí)，新點(diǎn)坐標(biāo)為nX(k+1)=x(k)+1, y(k+1)=y(k)n這時(shí)新點(diǎn)偏差為nF(k+1)=x(a)y(k+1)-x(k+1)y(a)=x(a

10、)y(k)-x(k)y(a)-y(a)=F(k)-y(a)逐點(diǎn)畫(huà)線算法(7/19)n繪圖筆走+y時(shí)，新點(diǎn)坐標(biāo)為nX(k+1)=xk, y(k+1)=y(k)+1n這時(shí)新點(diǎn)偏差為nF(k+1)=x(a)y(k+1)-x(k+1)y(a)=x(a)y(k)+x(a)-x(k)y(a)=F(k)+x(a) 根據(jù)新偏差F(k+1)的正、負(fù)號(hào)再確定繪圖筆的下一步走向，這樣逐步進(jìn)行，直到繪圖筆到達(dá)直線的終點(diǎn)為止。終點(diǎn)判斷可由X及Y向總走步數(shù)J(J=|x(a)|+|y(a)|)來(lái)控制，每走一步J減去1，當(dāng)J=0 時(shí)即到達(dá)終點(diǎn)。 逐點(diǎn)畫(huà)線算法(8/19)n對(duì)其他象限內(nèi)直線段生成計(jì)算走步方向的規(guī)定如下圖所示。偏

11、差的遞推計(jì)算均按以下兩式進(jìn)行：n 當(dāng)沿X方向走步時(shí)， F(k+1)=F(k)-|y(a)|；n 當(dāng)沿Y方向走步時(shí)，F(xiàn)(k+1)=F(k)+|x(a)|。 XYFk0Fk0Fk0Fk0Fk0Fk0Fk0Fk0O逐點(diǎn)畫(huà)線算法(9/19)01234512LINE(0,0)TO(5,2) 畫(huà)點(diǎn) (0,0)F(0)=0 (1,0)F(1)0 (2,1)F(3)0 (3,1)F(4)0 (4,2)F(6)0 (5,2)逐點(diǎn)畫(huà)線算法(10/19)n優(yōu)點(diǎn)： 整個(gè)算法實(shí)現(xiàn)可以使用整數(shù)，沒(méi)有使用浮點(diǎn)數(shù)運(yùn)算，沒(méi)有乘除運(yùn)算，所以適合硬件實(shí)現(xiàn)，大多數(shù)繪圖儀使用這個(gè)算法。n缺點(diǎn)： 逐點(diǎn)畫(huà)線法一次只能位移一步，所以畫(huà)出來(lái)的

12、直線粗細(xì)不均勻。逐點(diǎn)畫(huà)線算法(11/19)n逐點(diǎn)畫(huà)線算法VC源代碼（不包含交互內(nèi)容，直接內(nèi)置畫(huà)線段的起始點(diǎn)，并且沒(méi)有實(shí)現(xiàn)F(k)計(jì)算的遞推工作）nvoid CMyView:OnPointline() n n CDC *pDC=GetDC();nCOLORREF color=RGB(255,0,0);/ 前面四句就是設(shè)備環(huán)境，當(dāng)然表現(xiàn)形式可以不一樣逐點(diǎn)畫(huà)線算法(12/19)n int a1=30;n int b1=30;n int b2=800;n int a2=600; /我們實(shí)現(xiàn)最簡(jiǎn)單的畫(huà)線算法，二點(diǎn)已經(jīng)確定/后面我們?cè)僦v如何交互n int x1,y1,x2,y2; /起始點(diǎn)坐標(biāo)n int

13、itype; /畫(huà)線不同循環(huán)類型n int i;n int xx,yy;逐點(diǎn)畫(huà)線算法(13/19)nif (a1a2&b1a2&b1b2)n n n x1=a2;n y1=b2;n x2=a1;n y2=b1;n itype=1;n 逐點(diǎn)畫(huà)線算法(14/19)nif (a1b2)n n x1=a1;n y1=b1;n x2=a2;n y2=b2;n itype=2;n n if (a1a2&b1b2)n n x1=a2;n y1=b2;n x2=a1;n y2=b1;n itype=2;n 逐點(diǎn)畫(huà)線算法(15/19)n/前面的代碼具有我自己的風(fēng)格，因?yàn)閂C的工作區(qū)坐標(biāo)的

14、特性，我們分析以后，畫(huà)線存在二個(gè)類型，即把理論中的分四個(gè)象限畫(huà)線情況歸結(jié)為二類，畫(huà)線起點(diǎn)和始點(diǎn)我們靈活變化一下，簡(jiǎn)化編程。nint k=abs(x2-x1)+abs(y2-y1); / 書(shū)上的終點(diǎn)判別不是這么求的 xx=x1; n yy=y1; n switch (itype)n 逐點(diǎn)畫(huà)線算法(16/19)ncase 1 :n n xx=x1; n yy=y1; n for (i=0;iSetPixel(xx,yy,color); n if (x2-x1)*(yy-y1)-(xx-x1)*(y2-y1)=0)n xx=xx+1; n elsen yy=yy+1; n n return;逐點(diǎn)畫(huà)線

15、算法(17/19)ncase 2 :n nxx=x1; n yy=y1; nfor (i=0;iSetPixel(xx,yy,color);n if (x2-x1)*(y1-yy)-(xx-x1)*(y1-y2)=0)n xx=xx+1; n elsen yy=yy-1; n nnreturn; n nn注意：從一個(gè)理論上的算法提煉到具體一個(gè)編譯器可以運(yùn)行編譯的程序，可能會(huì)有多種不同的編寫(xiě)程序方法，但執(zhí)行效果是一樣的，都能體現(xiàn)算法的精髓。 上面的逐點(diǎn)畫(huà)線算法沒(méi)有實(shí)現(xiàn)計(jì)算誤差中 F(K)的遞推工作，效率可能會(huì)低點(diǎn)，同學(xué)們可以考慮把這個(gè)可執(zhí)行無(wú)誤算法改進(jìn)一下。 優(yōu)秀的程序不僅要求無(wú)誤執(zhí)行，還要有良

16、好的性能，茁壯性（出錯(cuò)處理好）等要求。逐點(diǎn)畫(huà)線算法(18/19)n 上面這個(gè)程序還有些bug，那就是不能繪制水平或豎直的直線，還有未能實(shí)現(xiàn)F(k)的遞推工作，這些留給同學(xué)們?nèi)プ?，可以在程序中加入一些代碼來(lái)解決這個(gè)問(wèn)題。同學(xué)們還可以根據(jù)自己對(duì)算法的理解重新編寫(xiě)代碼，不用和我編寫(xiě)的思路一樣。比如實(shí)現(xiàn)四象限方向畫(huà)圖，判斷F(k)的正負(fù)，如果為正，分四種象限情況走步，如果為負(fù)，分四種象限情況走步。逐點(diǎn)畫(huà)線算法(19/19)逐點(diǎn)法編程另一個(gè)思路n坐標(biāo)變換的思想 坐標(biāo)變換的思想對(duì)后面的曲線曲面編程很有幫助 根據(jù)一開(kāi)始上課推導(dǎo)的最簡(jiǎn)單的逐點(diǎn)法繪制直線，從第一象限原點(diǎn)出發(fā)到第一象限的一個(gè)點(diǎn)得到的算法，利用坐標(biāo)

17、變換來(lái)把其他的相當(dāng)于其他象限的直線繪制映射到第一象限的最簡(jiǎn)直線繪制中來(lái)。void CMyView:OnLine1() CDC *pDC=GetDC();COLORREF color=RGB(255,0,0);int x1=0,y1=0;int x2=500,y2=200;int i;int f=0; int x=x1,y=y1;最簡(jiǎn)第一象限逐點(diǎn)法繪制源碼 pDC-SetPixel(x1,y1,color); int k=abs(x2-x1)+abs(y2-y1); for (i=0;i0) y=y+1; f=f-x2; pDC-SetPixel(x,y,color);else x=x+1; f

18、=f+y2; pDC-SetPixel(x,y,color); 最簡(jiǎn)第一象限逐點(diǎn)法繪制源碼 CDC *pDC=GetDC(); COLORREF color=RGB(255,0,0); int a1=3; int b1=3; int b2=800; int a2=600; int x1,y1,x2,y2; /起始點(diǎn)坐標(biāo) int itype; /畫(huà)線不同循環(huán)類型 int i; int f1=0; int f2=0; int k=abs(a2-a1)+abs(b2-b1);坐標(biāo)變換映射逐點(diǎn)法繪制源碼 if (a1a2&b1a2&b1b2) x1=a1; y1=b1; x2=abs(

19、a1-a2); y2=abs(b1-b2); itype=1; 坐標(biāo)變換映射逐點(diǎn)法繪制源碼 if (a1b2) x1=a1; y1=b1; x2=abs(a1-a2); y2=abs(b1-b2); itype=2; if (a1a2&b1SetPixel(x1,y1,color);坐標(biāo)變換映射逐點(diǎn)法繪制源碼 switch (itype) case 1 : for (i=0;i0) y=y+1; f1=f1-x2; pDC-SetPixel(x1-x,y1-y,color); else x=x+1; f1=f1+y2; pDC-SetPixel(x1-x,y1-y,color); br

20、eak;坐標(biāo)變換映射逐點(diǎn)法繪制源碼 case 2 : for (i=0;i0) yy=yy+1; f2=f2-x2; pDC-SetPixel(x1+xx,y1-yy,color); else xx=xx+1; f2=f2+y2; pDC-SetPixel(x1+xx,y1-yy,color); return; （本程序也沒(méi)考慮水平豎直線）坐標(biāo)變換映射逐點(diǎn)法繪制源碼n數(shù)值微分法（Digital Differential Analyzer）是一種基于直線微分方程來(lái)生成直線的方法。n回顧一下數(shù)值微分的幾何意義，一階數(shù)值微分反應(yīng)的是變化率，表達(dá)瞬時(shí)變化趨勢(shì)和快慢的量。2.3 DDA畫(huà)線算法 DDA畫(huà)

21、線算法(1/14)n已知線段端點(diǎn)：P0(x0,y0), P1(x1,y1)n直線方程 y=kx+b (xi, yi), i=0,.n.n浮點(diǎn)數(shù)取整 : yi=round(yi)=(int)(yi+0.5)用到浮點(diǎn)數(shù)的乘法、加法和取整運(yùn)算 DDA畫(huà)線算法(2/14)n增量算法yi+1=kxi+1+b=k(xi+1)+b=yi+k(xi,yi)(xi+1,yi+k)n缺點(diǎn)：有浮點(diǎn)數(shù)取整運(yùn)算不利于硬件實(shí)現(xiàn)效率低僅適用于k 1的情形:x每增加1,y最多增加1。當(dāng) k 1時(shí)，必須把x，y互換。 DDA畫(huà)線算法(3/14)n思考：如何改進(jìn)算法更適合于編程實(shí)現(xiàn)呢？n基本思想用數(shù)值方法解微分方程 dy/dt

22、= xdy/dt = y xn+1 = xn + x yn+1 = yn + y 如何選取如何選?。?DDA畫(huà)線算法(4/14)n對(duì)稱的DDA取=2-n使 2n-1max(|x |,|y|)2nn簡(jiǎn)單的DDA取= 1/max(|x |,|y|)使 |x |, |y|中必有一個(gè)是單位步長(zhǎng)x為最大時(shí)， x =1, x =ky為最大時(shí)， y =1, y =1/k 簡(jiǎn)單DDA法是按x, y絕對(duì)值較大的方向走步的，在這個(gè)方向上，每步走一個(gè)像素，然后再確定另一個(gè)方向的走步。 簡(jiǎn)單DDA法生成直線的精度同對(duì)稱DDA法，但它在求一個(gè)點(diǎn)時(shí)要做兩次除法以決定坐標(biāo)增量值。簡(jiǎn)單DDA法不適合硬件實(shí)現(xiàn)，只適合于軟件處理

23、。 DDA畫(huà)線算法(5/14)n【例】用對(duì)稱DDA法在起點(diǎn)A(2，1)和終點(diǎn)B(12，7)之間生成一段直線。n 求解的第一步是計(jì)算初值x, y, n。這里x=10, y=6, n=4。n 第二步按遞推公式循環(huán)計(jì)算點(diǎn)的坐標(biāo)，并取整顯示。表是本例的循環(huán)計(jì)算過(guò)程。 圖是其屏幕顯示結(jié)果。DDA畫(huà)線算法(6/14)DDA畫(huà)線算法(7/14)DDA畫(huà)線算法(8/14)AB753124681012 對(duì)稱DDA法生成的直線比較精確，像點(diǎn)位置偏離直線不超過(guò)半個(gè)像素。邏輯上也比較簡(jiǎn)單，用 2 的負(fù)指數(shù)冪作為，意味著把存放x和y的寄存器通過(guò)移位操作就可得到點(diǎn)與點(diǎn)之間的坐標(biāo)增量x、y，而不用除法計(jì)算，計(jì)算直線上每一點(diǎn)

24、只用兩次加法即可實(shí)現(xiàn)。對(duì)稱DDA法適合用硬件來(lái)實(shí)現(xiàn)， 當(dāng)然也可用軟件來(lái)實(shí)現(xiàn)。 DDA畫(huà)線算法(9/14)DDA畫(huà)線算法(10/14)n/簡(jiǎn)單的DDA畫(huà)線算法，繪制線段的起始點(diǎn)也是內(nèi)置的，沒(méi)有加入交互過(guò)程。這是DDA的基本算法，希望同學(xué)們好好體會(huì)算法，從理論上的算法到具體程序的過(guò)程。nvoid CMyView:OnDdaline() nnCDC *pDC=GetDC();nCOLORREF color=RGB(255,0,0);n/設(shè)備環(huán)境DDA畫(huà)線算法(11/14)n int x1=30;n int y1=600;n int x2=180;n int y2=200;n int i;n floa

25、t xincrement,yincrement,xx,yy;n int k=abs(x2-x1);n if(abs(y2-y1)k) k=abs(y2-y1);n xincrement=(float)(x2-x1)/k;n yincrement=(float)(y2-y1)/k;DDA畫(huà)線算法(12/14)n xx=(x1+0.5);n yy=(y1+0.5);n/為什么加0.5？因?yàn)槲覀儗?duì)像素要取整，xx本為浮點(diǎn)數(shù)，但后面繪制圖形時(shí)候要取整n for (i=0;iSetPixel(int)xx,(int)yy,color);nxx=xx+xincrement;nyy=yy+yincremen

26、t;nnDDA畫(huà)線算法(13/14)n 上面是簡(jiǎn)單DDA算法的實(shí)現(xiàn)，如果要改成對(duì)稱的DDA算法，只要更改k的取值就好，不過(guò)對(duì)于k值的選取需要計(jì)算一下。同學(xué)們?yōu)榱梭w驗(yàn)算法，可以實(shí)現(xiàn)基本的DDA畫(huà)線算法，就是前面介紹的增量算法k 1的情形:(xi,yi)(xi+1,yi+k)當(dāng) k 1時(shí)，必須把x，y互換。DDA畫(huà)線算法(14/14)2.4 BRESENHAM畫(huà)線算法nBresenhamBresenham算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域中使用算法是計(jì)算機(jī)圖形學(xué)領(lǐng)域中使用最廣泛的直線掃描轉(zhuǎn)換算法。該算法最初最廣泛的直線掃描轉(zhuǎn)換算法。該算法最初是為數(shù)字繪圖儀設(shè)計(jì)的。由于它也適用于是為數(shù)字繪圖儀設(shè)計(jì)的。由于它也適

27、用于光柵圖形顯示器，所以后來(lái)被廣泛用于直光柵圖形顯示器，所以后來(lái)被廣泛用于直線的掃描轉(zhuǎn)換與其他一些應(yīng)用。為了討論線的掃描轉(zhuǎn)換與其他一些應(yīng)用。為了討論方便，學(xué)習(xí)的開(kāi)始也假定直線的斜率在方便，學(xué)習(xí)的開(kāi)始也假定直線的斜率在0 0、l l之間。其他情況可類似處理。之間。其他情況可類似處理。過(guò)各行、 各列像素中心構(gòu)造一組虛擬網(wǎng)格線, 按直線從起點(diǎn)到終點(diǎn)的順序計(jì)算直線與各垂直網(wǎng)格線的交點(diǎn), 然后確定該列像素中與該交點(diǎn)最近的像素。 yyk+1yykxkxk+1xP2P1d2d10BRESENHAM畫(huà)線算法(2/16)BRESENHAM畫(huà)線算法(3/16)n最大位移方向每次走一步k1時(shí)，x為最大位移方向ny方

28、向走步與否取決于誤差e值的大小n誤差計(jì)算n初值：e0= y/ xn當(dāng)e0.5時(shí)，最接近P2(xi+1,yi+1)y方向走一步n當(dāng)e0.5時(shí)，最接近P1(xi+1,yi)y方向不走步eP1P2PeeP1P2PeBRESENHAM畫(huà)線算法(4/16)n為方便與0比較，設(shè)e=e-0.5ne0=y/ x-0.5n當(dāng)e0時(shí)，最接近P2(xi+1,yi+1)y方向走一步n當(dāng)e0時(shí)，最接近P1(xi+1,yi)y方向不走步n有除法，不宜硬件實(shí)現(xiàn)eP1P2PeeP1P2PeBRESENHAM畫(huà)線算法(5/16)n如何改進(jìn)算法，去掉這個(gè)除法運(yùn)算呢？n分析這個(gè)像素增量算法，我們發(fā)現(xiàn)每次我們判斷走步的依據(jù)僅僅是e的

29、正負(fù)，與e的本身數(shù)值大小沒(méi)關(guān)系。BRESENHAM畫(huà)線算法(6/16)n設(shè)e=e2xne0=2y - x n當(dāng)e0時(shí)，最接近P2(xi+1,yi+1)y方向走一步n當(dāng)e0時(shí)，最接近P1(xi+1,yi)y方向不走步n分析這個(gè)新算法，其實(shí)并沒(méi)有改變什么ne0=y/ x-0.5n當(dāng)e0時(shí)，最接近P2(xi+1,yi+1)y方向走一步n當(dāng)e0時(shí)，最接近P1(xi+1,yi)y方向不走步n有除法，不宜硬件實(shí)現(xiàn)BRESENHAM畫(huà)線算法(7/16)n下一步誤差的計(jì)算n當(dāng)e0時(shí)，y方向走一步e=2y/ x - 1 =e + y/ x - 1 e=e + 2y - 2xn當(dāng)e=0) s1=1; else s

30、1=-1;nif(y2-y1=0) s2=1; else s2=-1;n/考慮到八個(gè)方向問(wèn)題BRESENHAM畫(huà)線算法(13/16)nif(deltaydeltax)nn temp=deltax;n deltax=deltay;n deltay=temp;n interchange=1;nn else interchange=0;n/考慮到是否斜率大于1交換x，y問(wèn)題n/這是一種編程實(shí)現(xiàn)上的技巧BRESENHAM畫(huà)線算法(14/16)n int f=2*deltay-deltax; n for(i=0;iSetPixel(x,y,color);n if(f=0)nn x+=s1;n y+=s2

31、; n f=f+2deltay-2*deltax;n BRESENHAM畫(huà)線算法(15/16)n elsenn if(interchange=1) y+=s2;n else x+=s1;n pDC-SetPixel(x,y,200);n f=f+2*deltay;nn nBRESENHAM畫(huà)線算法(16/16)n程序說(shuō)明：n（1）以上程序已經(jīng)考慮到所有象限直線的生成。n（2）Bresenham算法的優(yōu)點(diǎn)如下：n 不必計(jì)算直線的斜率，因此不做除法。n 不用浮點(diǎn)數(shù)，只用整數(shù)。n 只做整數(shù)加減運(yùn)算和乘2運(yùn)算，而乘2運(yùn)算可以用移位操作實(shí)現(xiàn)。n Bresenham算法的運(yùn)算速度很快。 2.5 關(guān)于線寬線

32、型 前面我們編程實(shí)現(xiàn)的畫(huà)圖算法都是一個(gè)像素寬度的連續(xù)的直線（逐點(diǎn)畫(huà)線法畫(huà)出來(lái)的線粗細(xì)步均勻），實(shí)際使用中我們經(jīng)常還需要用到各種寬度不同的線，實(shí)線，還有虛線來(lái)表達(dá)不同的含義。常用商業(yè)軟件都提供了類似的功能，比如word，autocad等等軟件。 要產(chǎn)生具有寬度的線，可以順著掃描所生成的單像素線條軌跡， 移動(dòng)一把具有一定寬度的“刷子”來(lái)獲得，“刷子”的形狀可以是一條線段或一個(gè)正方形。也可以采用區(qū)域填充的辦法間接地產(chǎn)生有寬度的線(如AutoCAD系統(tǒng)即是)。關(guān)于線寬線型(/)（1）垂直線刷子：假設(shè)直線斜率在1，1之間，把刷子放置成垂直方向，刷子中點(diǎn)對(duì)準(zhǔn)直線一端點(diǎn)，然后讓刷子中心往直線的另一端移動(dòng)，即

33、可“刷出”具有一定寬度的線。關(guān)于線寬線型(/)n實(shí)現(xiàn)方法：在直線的掃描轉(zhuǎn)換中，計(jì)算出與直線最近的像素點(diǎn)后，在繪制點(diǎn)的同時(shí)，分別向上和向下多繪制幾個(gè)點(diǎn)，即可實(shí)現(xiàn)垂直刷的寬度線。關(guān)于線寬線型(/)（2）水平線刷子：直）水平線刷子：直線斜率不在線斜率不在1，1之間，可以把刷子之間，可以把刷子放置成水平方向，放置成水平方向，刷子中點(diǎn)對(duì)準(zhǔn)直刷子中點(diǎn)對(duì)準(zhǔn)直線線端點(diǎn)并往直線端點(diǎn)并往直線的另一端移動(dòng)，可的另一端移動(dòng)，可“刷出刷出”具有一定具有一定寬度的線。寬度的線。 關(guān)于線寬線型(/)n實(shí)現(xiàn)方法：在直線的掃描轉(zhuǎn)換中，實(shí)現(xiàn)方法：在直線的掃描轉(zhuǎn)換中，計(jì)算出與直線最近的像素點(diǎn)后，在計(jì)算出與直線最近的像素點(diǎn)后，在繪制

34、點(diǎn)的同時(shí)，分別向左和向右多繪制點(diǎn)的同時(shí)，分別向左和向右多繪制幾個(gè)點(diǎn)，即可實(shí)現(xiàn)水平刷的寬繪制幾個(gè)點(diǎn)，即可實(shí)現(xiàn)水平刷的寬度線。度線。 關(guān)于線寬線型(/)n（3）方形刷子：把邊寬為指定線寬的正方）方形刷子：把邊寬為指定線寬的正方形的中心沿直線作平行移動(dòng)，即可獲得具形的中心沿直線作平行移動(dòng)，即可獲得具有線寬的線條。有線寬的線條。 關(guān)于線寬線型(/)n實(shí)現(xiàn)正方形刷子最簡(jiǎn)單的辦法是，實(shí)現(xiàn)正方形刷子最簡(jiǎn)單的辦法是，把方形中心對(duì)準(zhǔn)單像素寬的線條上把方形中心對(duì)準(zhǔn)單像素寬的線條上各個(gè)像素，并把方形內(nèi)的像素全部各個(gè)像素，并把方形內(nèi)的像素全部置成線條顏色。這種簡(jiǎn)單方法將會(huì)置成線條顏色。這種簡(jiǎn)單方法將會(huì)重復(fù)地寫(xiě)像素。這

35、是因?yàn)閷?duì)應(yīng)于相重復(fù)地寫(xiě)像素。這是因?yàn)閷?duì)應(yīng)于相鄰兩像素的方形一般會(huì)重疊許多像鄰兩像素的方形一般會(huì)重疊許多像素。素。關(guān)于線寬線型(/)關(guān)于線寬線型(/)n線刷子的優(yōu)缺點(diǎn)： 算法簡(jiǎn)單、效率高是線刷子的優(yōu)點(diǎn)。但是，線的始末端總是水平或垂直的。因此，當(dāng)線寬較大時(shí)，看起來(lái)很不自然。當(dāng)比較接近水平的線與比較接近垂直的線匯合時(shí)，匯合處外角將有缺口，如圖 所示。n生成具有寬度的線條還可以采用區(qū)域填充的算法。先算出線條各角點(diǎn)，再用直線段把相鄰角點(diǎn)連接起來(lái)，最后調(diào)用多邊形填充算法把所得的四邊形進(jìn)行填色，即得到具有寬度的線條。 用這種方法還可以生成兩端粗細(xì)不一樣的線條。關(guān)于線寬線型(/) 在繪圖應(yīng)用中常用到不同線型的

36、線條，以便區(qū)分各種不同的意義。如采用實(shí)線表示立體線框圖中可見(jiàn)的輪廓線，用虛線表示不可見(jiàn)的輪廓線， 用點(diǎn)劃線表示中心線等等。關(guān)于線寬線型(/) 線型可以用一個(gè)布爾值的序列來(lái)存放。例如，用一個(gè) 32 位整數(shù)可以存放 32 個(gè)布爾值。用這樣的整數(shù)存放線型定義時(shí)，線型必須以 32 個(gè)像素為周期進(jìn)行重復(fù)?？砂聪率稣Z(yǔ)句寫(xiě)像素： if(位串i%32)drawpixel(x, y,color)； 其中i為循環(huán)變量，在掃描轉(zhuǎn)換算法的內(nèi)循環(huán)中，每處理一個(gè)像素就遞增 1，然后除以 32 取余。 關(guān)于線寬線型(/) 用這種簡(jiǎn)單辦法實(shí)現(xiàn)的線型有個(gè)毛病。因?yàn)槊课粚?duì)應(yīng)于算法的一個(gè)迭代步驟而不是線條上一個(gè)長(zhǎng)度單位，因此線型中

37、的筆劃長(zhǎng)度與直線長(zhǎng)度有關(guān)，斜線上的筆劃長(zhǎng)度比橫向或豎向上的筆劃更長(zhǎng)。對(duì)于工程圖，這種變化是不能接受的。這時(shí)，每個(gè)筆劃應(yīng)該作為與角度無(wú)關(guān)的線段進(jìn)行計(jì)算并掃描轉(zhuǎn)換。粗線的線型計(jì)算為實(shí)的或透明的正方形，其頂點(diǎn)位置根據(jù)線型要求進(jìn)行準(zhǔn)確計(jì)算。然后對(duì)正方形進(jìn)行掃描轉(zhuǎn)換，對(duì)于垂直或水平的粗線線型，可以用寫(xiě)方塊的簡(jiǎn)單辦法進(jìn)行。 關(guān)于線寬線型(/)n在我們選用的教材上（P32），使用了一種最靈活的方式畫(huà)虛線，通過(guò)定義實(shí)線和虛線的距離來(lái)選擇繪圖像素點(diǎn)。n這種方法有個(gè)缺點(diǎn)，那就是直線段的總長(zhǎng)度可能不是實(shí)線部分加上虛線部分距離的整數(shù)倍，可能會(huì)造成繪制虛線二頭端點(diǎn)為空的情況。n還有個(gè)缺點(diǎn)，那就是大量的除法計(jì)算效果不太好

38、。關(guān)于線寬線型(/)n實(shí)際利用Visual C+中編制圖形程序，可以利用圖形學(xué)算法自己動(dòng)手編制基本圖形程序，作為圖形程序的基類，當(dāng)然還可利用系統(tǒng)中已提供的圖形基類。下面簡(jiǎn)單介紹Visual C+提供的常用繪制圖形函數(shù)。2.6 Visual C+中基本繪圖函數(shù)n1點(diǎn)n畫(huà)點(diǎn)是最基本的繪圖操作，在繪圖中，畫(huà)點(diǎn)是通過(guò)調(diào)用CDC:SetPixel()或CDC SetPixelV()函數(shù)來(lái)實(shí)現(xiàn)的，原型如：n（1）COLORREF SetPixel(int x, int y, COLORREF crColor);n（2）COLORREF SetPixel(POINT point, COLORREF crCo

39、lor);n（3）BOOL SetPixelV(int x, int y, COLORREF crColor);n（4）BOOL SetPixelV(POINT point, COLORREF crColor);Visual C+中基本繪圖函數(shù)(1/18)n2畫(huà)筆n一般格式：Cpen( ) Cpen(int nPenStyle, int nWidth, CORLORREF crColor);n各屬性意義：nPenStyle設(shè)置畫(huà)筆的式樣，式樣有：PS_SOLID（實(shí)線），PS_DASH（虛線）、PS_DASHDOT（點(diǎn)劃線）、PS_DASHDOTDOT（雙點(diǎn)劃線）、PS_DOT（點(diǎn)線）、PS_

40、NULL（空筆不畫(huà)線）；nWidth設(shè)置線的寬度，默認(rèn)值為1（1個(gè)像素寬）；crColor表示顏色，可用DWOR表示，也可用RGB(r, g, b)表示。Visual C+中基本繪圖函數(shù)(2/18)n3畫(huà)刷n用于指定填充的特征，畫(huà)刷創(chuàng)建的格式如下：n（1）CBrush CBrush（創(chuàng)建一個(gè)空的畫(huà)刷對(duì)象），可用GreateSolidBrush()，Greateha- tchBrush()，GreatehatchBrushIndrect()，GreatePatternBrush()，GreateDIBPatternBrush()建立畫(huà)刷。n（2）CBrush CBrush()建立單一顏色的畫(huà)刷，

41、用次畫(huà)刷畫(huà)出的圖形內(nèi)部將會(huì)填充指定顏色。Visual C+中基本繪圖函數(shù)(3/18)n（3）CBrush CBrush（int nIndex, COLORREF crColor）；構(gòu)建名為hatch的畫(huà)刷，特點(diǎn)為畫(huà)出的多邊形內(nèi)部將填充nrColor指定的線條格式，nrColor有HS_BDIAGONAL（45左下右上的斜線）、HS_CROSS（垂直線和水平線）、HS_DIAGCROSS（45左上右下、左上右下的相交斜線）、HS_HDLAGNAL（45左上右下的斜線）、HS_HORIZONAL（水平線）、HS_VERTICAL（垂直線）。Visual C+中基本繪圖函數(shù)(4/18)n（4）CBr

42、ush CBrush（Cbitmap *pBitmap）中pBitmap指向Cbitmap對(duì)象的指針，這一位圖對(duì)象包含用做畫(huà)刷圖案的位圖，此位圖必須為88大小，否則將對(duì)原位圖進(jìn)行裁剪。n創(chuàng)建畫(huà)刷和畫(huà)筆后，還要用CDC類選中畫(huà)筆和畫(huà)刷，用CPaintDC，CClientDC或CWindowDC來(lái)選中、繪圖及撤銷對(duì)象。Visual C+中基本繪圖函數(shù)(5/18)nCClientDC對(duì)象代表客戶程序區(qū)域的繪圖畫(huà)面只能在窗口的客戶區(qū)域中畫(huà)圖。若需處理整個(gè)畫(huà)面（包括客戶程序區(qū)域和非客戶程序區(qū)）設(shè)備上下文的調(diào)用和釋放可用CWindowDC。Visual C+中基本繪圖函數(shù)(6/18)n4繪制直線函數(shù)n（1

43、）MoveTo()函數(shù)用來(lái)設(shè)置當(dāng)前的x，y的位置，創(chuàng)建的格式如下：nCPoint MoveTo(int x, int y)；nCPoint MoveTo(POINT point)；n其中x，y用于定義新位置的坐標(biāo)，point指定新位置，可為其傳遞一個(gè)POINT對(duì)象。n功能：將線的起點(diǎn)從當(dāng)前位置移到新位置（x,y），并且只移動(dòng)點(diǎn)不畫(huà)線。Visual C+中基本繪圖函數(shù)(7/18)n（2）LineTo()用于繪制起點(diǎn)坐標(biāo)到終點(diǎn)直線，創(chuàng)建的格式如下：nBOOL LineTo(int x, int y)；nBOOL LineTo(POINT point)；n其中x，y用于定義線的終點(diǎn)坐標(biāo)，point指

44、定線段端點(diǎn)位置，可為其傳遞一個(gè)POINT結(jié)構(gòu)或POINT對(duì)象。n功能：從當(dāng)前的位置到新位置（x，y）畫(huà)線（不包括此端點(diǎn)）。Visual C+中基本繪圖函數(shù)(8/18)n5橢圓函數(shù)n創(chuàng)建的格式如下：nBOOL Ellipse(int x1, int y1 , int x2, int y2)；nBOOL Ellipse(LPCRECT lpRect)；n說(shuō)明：x1, y1為限定橢圓范圍的矩形左上角坐標(biāo)，x2, y2為限定橢圓范圍的矩形右下角坐標(biāo)。nLpRect指定橢圓的限定矩形，可為其傳遞一個(gè)CRect對(duì)象。Visual C+中基本繪圖函數(shù)(9/18)n6函數(shù)繪制一段橢圓弧Arc()n創(chuàng)建的格式如

45、下：nBOOL Arc(int x1, int y1 , int x2, int y2, int x3, int y3 , int x4, int y4)；nBOOL Ellipse(LPCRECT lpRect)；nx1, y1為限定橢圓弧范圍的矩形左上角坐標(biāo)；x2, y2為限定橢圓弧范圍的矩形右下角坐標(biāo)。x3, y3為起點(diǎn)坐標(biāo)；x4, y4為終點(diǎn)坐標(biāo)。 Visual C+中基本繪圖函數(shù)(10/18)n7矩形函數(shù)n創(chuàng)建的格式如下：nBOOL Rectangle(int x1, int y1, int x2, int y2)；nx1, y1為矩形左上角坐標(biāo)，x2, y2為矩形右下角坐標(biāo)。n功能：使用當(dāng)前畫(huà)筆畫(huà)一矩形。Visual C+中基本繪圖函數(shù)(11/18)n8連續(xù)畫(huà)線函數(shù)n創(chuàng)建的格式如下：n（1）BOOL PolyLine(LPPOIN