c++圖形學(xué)實(shí)驗(yàn)教程：第三章 圖形基元掃描轉(zhuǎn)換算法的實(shí)現(xiàn)

1、圖形基元掃描轉(zhuǎn)換算法的實(shí)現(xiàn)目前，我們最常用的圖形顯示設(shè)備是光柵掃描式圖形顯示器，簡(jiǎn)稱光柵顯示器。光柵顯示器是一種畫(huà)點(diǎn)設(shè)備，它可以看作是一個(gè)像素點(diǎn)矩陣，每個(gè)像素可以用一種或多種的顏色顯示，分別稱為單色顯示器或彩色顯示器。在光柵顯示器上顯示的任何一種圖形，實(shí)際上都是一些具有一種或多種顏色的像素的集合。例如，光柵顯示器不能直接從像素矩陣中的一個(gè)像素畫(huà)一條直線到另一個(gè)像素，只能用盡可能的靠近這條直線路徑上的像素點(diǎn)集合來(lái)近似的表示這條直線。將要顯示在光柵顯示器上的圖形描述轉(zhuǎn)換成用像素點(diǎn)集合來(lái)表示的過(guò)程稱為掃描轉(zhuǎn)換。為了降低圖形掃描轉(zhuǎn)換的復(fù)雜度，我們往往將復(fù)雜圖形分解成一些基本的簡(jiǎn)單圖形的組合，這些基本圖

2、形稱為圖形基元。圖形基元的選擇可以有不同的方法，但是通常都會(huì)把線段、圓和多邊形選為圖形基元。本章將通過(guò)MFC編程的方式實(shí)現(xiàn)線段、圓和多邊形的掃描轉(zhuǎn)換算法，并創(chuàng)建一個(gè)MFC應(yīng)用程序項(xiàng)目來(lái)演示這些掃描轉(zhuǎn)換算法的結(jié)果。為了能夠更好的演示掃描轉(zhuǎn)化算法的結(jié)果，我們創(chuàng)建一個(gè)MFC應(yīng)用程序項(xiàng)目（除了選擇單文檔外，其它選項(xiàng)使用默認(rèn)選擇），項(xiàng)目名稱為ScanarithDemo，然后創(chuàng)建一個(gè)普通類CDraw，我們?cè)谠擃愔袑?shí)現(xiàn)掃描轉(zhuǎn)換算法。為視圖類CScanarithDemoView添加WM_LBUTTONDOWN（鼠標(biāo)左鍵按下）消息、WM_LBUTTONDBLCLK（鼠標(biāo)左鍵雙擊）消息、WM_MOUSEMOVE（

3、鼠標(biāo)移動(dòng)）消息和WM_KEYDOWN（鍵盤按鍵按下）消息的處理函數(shù)，這樣我們可以更靈活的決定圖形基元的形狀，然后調(diào)用相應(yīng)的掃描轉(zhuǎn)換函數(shù)進(jìn)行繪制。為了能夠選擇不同的掃描轉(zhuǎn)換函數(shù)，我們?cè)贑ScanarithDemoView類中添加如下成員變量，并在構(gòu)造函數(shù)中設(shè)置它們的初始值為0：public:/選擇繪制哪種圖形基元int m_SelectDraw;/選擇使用哪種掃描轉(zhuǎn)換算法int m_SelectArithmetic;再在CScanarithDemoView類中添加如下成員變量：public:/節(jié)點(diǎn)列表CArray m_PointsList;CArray是MFC封裝的列表類，其對(duì)象聲明方式與CLi

4、st相同，上面的聲明表示列表中存放的是CPoint對(duì)象。而其使用方法與CObArray類似，具有類似的成員函數(shù)。該對(duì)象的作用是存儲(chǔ)線段和多邊形的節(jié)點(diǎn)，或者是用來(lái)控制圓的形狀?，F(xiàn)在我們已經(jīng)做好了演示程序的準(zhǔn)備工作，下面開(kāi)始介紹圖形基元掃描轉(zhuǎn)換算法的實(shí)現(xiàn)和演示。 直線掃描轉(zhuǎn)換算法的實(shí)現(xiàn)直線掃描算法的任務(wù)是根據(jù)傳入的線段的兩個(gè)端點(diǎn)的坐標(biāo)，求出構(gòu)成該線段的所有像素點(diǎn)的坐標(biāo)。常用的直線掃描轉(zhuǎn)換算法有DDA直線掃描轉(zhuǎn)換算法、中點(diǎn)畫(huà)線法和Bresenham畫(huà)線算法。DDA直線掃描轉(zhuǎn)換算法的實(shí)現(xiàn)數(shù)值微分分析器（Digital Differential Analyzer，簡(jiǎn)稱DDA）直線掃描轉(zhuǎn)換算法的基本思想是

5、：設(shè)要繪制的直線段的兩個(gè)端點(diǎn)為(x1, y1)和(x2, y2)，根據(jù)直線方程y = mx + b，可得：m = (y2 y2)/(x2 x1)，b = (x2y1 x1y2)/(x2 x1)當(dāng)|m|1時(shí)，對(duì)x每增1取允許的各整數(shù)y值（根據(jù)直線方程計(jì)算出y值后取整），當(dāng)|m|1時(shí)，對(duì)y每增1取允許的各整數(shù)x值。因?yàn)閷?duì)于直線來(lái)說(shuō)，數(shù)值微分為：m = y/x = (yi+1 - yi)/(xi+1 xi)所以當(dāng)|m|1時(shí)，yi+1 = yi + m(xi+1 xi)，于是當(dāng)xi+1 = xi + 1時(shí)，yi+1 = yi + m；當(dāng)|m|1時(shí)，xi+1 = xi + (yi+1 yi)/m，于是當(dāng)

6、yi+1 = yi + 1時(shí)，xi+1 = xi + 1/m。根據(jù)此思想，可以寫(xiě)出DDA直線掃描轉(zhuǎn)換算法的實(shí)現(xiàn)函數(shù)。在CDraw類中添加如下成員函數(shù)用于實(shí)現(xiàn)DDA直線掃描轉(zhuǎn)換算法：public:/DDA直線掃描轉(zhuǎn)換算法void DDALine(CDC* pDC, int x1, int y1, int x2,int y2,COLORREF color);其中參數(shù)x1、y1、x2、y2是要繪制的直線段的兩個(gè)端點(diǎn)的坐標(biāo)；參數(shù)pDC是設(shè)備環(huán)境對(duì)象指針，我們需要繪制像素點(diǎn)；參數(shù)color為繪制直線段的顏色。實(shí)現(xiàn)代碼如下：/DDA直線掃描轉(zhuǎn)換算法void CDraw:DDALine(CDC* pDC,

7、int x1, int y1, int x2, int y2, COLORREF color)double dx,dy,e,x,y;dx = x2 -x1;dy = y2- y1;e = (fabs(dx) fabs(dy) ? fabs(dx):fabs(dy);dx/=e;dy/=e;x = x1;y = y1;for (int i=1;iSetPixel(int)(x+0.5),(int)(y+0.5),color);x+=dx;y+=dy;中點(diǎn)畫(huà)線法的實(shí)現(xiàn)中點(diǎn)畫(huà)線法的基本原理如下：假定直線斜率在0和1之間，如圖3.1(1)所示。此時(shí)直線在y值方向上的變化要小于x值方向上的變化，所以在x

8、方向上增加一個(gè)單位（像素），則在y方向上的增量只能在0和1之間。假設(shè)x坐標(biāo)為xpi的各像素點(diǎn)中，與直線最接近的已經(jīng)確定，為(xp, yp)。那么下一個(gè)與直線最接近的像素只能是正右方的P1(xp+1, yp)或右上方的P2(xp+1,yp+1)兩者之一。則兩點(diǎn)之間的中點(diǎn)為(xp+1, yp+0.5)。又設(shè)Q為理想直線與垂直線x = xp +1的交點(diǎn)。顯然，若中點(diǎn)在Q下方，則P2離直線近，應(yīng)取為下一個(gè)像素；否則取P1為下一像素點(diǎn)。其它情況可參照此原理進(jìn)行處理。對(duì)空間任意一直線段，假設(shè)端點(diǎn)為(x0, y0)和(x1, y1)。則直線方程為：F(x, y) = ax + by + c = 0其中，a

9、= y0 y1，b = x1 x0，c = x0y1 x1y0。對(duì)于直線上的點(diǎn)，F(xiàn)(x, y) = 0；對(duì)于直線下方的點(diǎn)，F(xiàn)(x, y) 0。所以要判斷前述Q在中點(diǎn)的上方或下方，只要把中點(diǎn)坐標(biāo)代入F(x, y)并判斷其符號(hào)即可。如果保證x0 x1，則按照中點(diǎn)畫(huà)線法的原理可分為圖3.1中所示的四種情況進(jìn)行處理：第(1)種情況是我們介紹中點(diǎn)畫(huà)線法基本原理時(shí)的情況。此時(shí)斜率處于0和1之間，可構(gòu)造判別式為：d = F(xp+1, yp+0.5) = a(xp+1) + b(yp+0.5) + c當(dāng)d0時(shí)，應(yīng)取P1(xp+1, yp)作為下一個(gè)像素；當(dāng)d=0時(shí)，兩者同樣合適，可以任取一個(gè)，我們可以約定取

10、P1作為下一像素。當(dāng)d0時(shí)，取P2(xp+1,yp+1)為下一像素，此時(shí)要判斷下一個(gè)像素取哪個(gè)，應(yīng)計(jì)算：d1 = F(xp+2, yp+1.5) = a(xp+2) + b(yp+1.5) + c = d + a + b故d的增量為a+b。否則，取P1(xp+1, yp)為下一像素，要判斷下一個(gè)像素應(yīng)取哪個(gè)，應(yīng)計(jì)算：d2 = F(xp+2, yp+0.5) = a(xp+2) + b(yp+0.5) + c = d + a故d的增量為a。最后看d的初始值。顯然，第一個(gè)像素應(yīng)取(x0, y0)，則有：d0 = F(x0+1, y0+0.5) = a(x0+1) + b(y0+0.5) + c =

11、 ax0 + by0 + c + a + 0.5b = F(x0, y0) + a + 0.5b因?yàn)?x0, y0)在直線上，所以F(x0, y0) = 0。因此d的初始值為d0 = a + 0.5b。為了擺脫小數(shù)，可以取2d來(lái)代替d，此時(shí)初始值d0 = 2a + b，當(dāng)d0時(shí)，增量為2(a+b)，否則，增量為2a。使用相同方法可以確定其它三種情況下的d0以及d的增量。第(2)種情況，斜率大于1，此時(shí)直線在y值方向上的變化大于x值方向上的變化，下一個(gè)像素可以為P1(xp, yp+1)或P2(xp+1, yp+1)。此時(shí)判別式為：d = F(xp+0.5, yp+1) = a(xp+0.5) +

12、 b(yp+1) + c當(dāng)d0時(shí)，取P1(xp, yp+1)作為下一像素，此時(shí)有：d1 = F(xp+0.5, yp+2) = a(xp+0.5) + b(yp+2) + c = d + b否則，取P2(xp+1, yp+1)作為下一像素，此時(shí)有：d2 = F(xp+1.5, yp+2) = a(xp+1.5) + b(yp+2) + c = d + a + b取2d作為判別式時(shí)，有初始值d0 = a + 2b，當(dāng)d0時(shí)，增量為2b，否則，增量為2(a+b)。第(3)種情況，斜率處于0與-1之間，此時(shí)直線在y值方向上的變化要小于x值方向上的變化，但是y值是在不斷減小，而不是前兩種情況的不斷增大

13、。下一個(gè)像素可以為P1(xp+1, yp)或P2(xp+1, yp1)。此時(shí)判別式為：d = F(xp+1, yp0.5) = a(xp+1) + b(yp0.5) + c當(dāng)d0時(shí)，取P1(xp+1, yp)作為下一像素，此時(shí)有：d1 = F(xp+2, yp0.5) = a(xp+2) + b(yp0.5) + c = d + a否則，取P2(xp+1, yp1)作為下一像素，此時(shí)有：d2 = F(xp+2, yp1.5) = a(xp+2) + b(yp1.5) + c = d + a b取2d作為判別式時(shí)，有初始值d0 = 2a b，當(dāng)d0時(shí)，增量為2a，否則，增量為2(ab)。第(4)

14、種情況，斜率小于-1，此時(shí)直線在y值方向上的變化大于x值方向上的變化，y值不斷減小。下一個(gè)像素可以為P1(xp, yp1)或P2(xp+1, yp1)。此時(shí)判別式為：d = F(xp+0.5, yp1) = a(xp+0.5) + b(yp1) + c當(dāng)d0時(shí)，取P2(xp+1, yp1)作為下一像素，此時(shí)有：d1 = F(xp+1.5, yp2) = a(xp+1.5) + b(yp2) + c = d + a b否則，取P1(xp, yp1)作為下一像素，此時(shí)有：d2 = F(xp+0.5, yp2) = a(xp+0.5) + b(yp2) + c = d b取2d作為判別式時(shí)，有初始值

15、d0 = a 2b，當(dāng)d0時(shí)，增量為2(ab)，否則，增量為2b。至此我們可以寫(xiě)出中點(diǎn)畫(huà)線法的實(shí)現(xiàn)函數(shù)，在CDraw類中添加如下成員函數(shù)：public:/中點(diǎn)畫(huà)線法void MidpointLine(CDC* pDC, int x0, int y0, int x1, int y1, COLORREF color);參數(shù)x0、y0、x1、y1為直線段的兩個(gè)端點(diǎn)的坐標(biāo)；參數(shù)pDC是設(shè)備環(huán)境對(duì)象指針；參數(shù)color為繪制直線段的顏色。實(shí)現(xiàn)代碼如下：/中點(diǎn)畫(huà)線法void CDraw:MidpointLine(CDC *pDC, int x0, int y0, int x1, int y1, COLOR

16、REF color)int a,b,delta1,delta2,d,x,y;/傳入端點(diǎn)坐標(biāo)x值相等if (x0 = x1)if (y0 y1)for (int i=y0;iSetPixel(x0,i,color);elsefor (int i=y1;iSetPixel(x0,i,color);return;/斜率判斷，斜率絕對(duì)值大于1，則m為false，否則為trueBOOL m = (fabs(y1-y0)x1)d=x0;x0=x1;x1=d;d=y0;y0=y1;y1=d;a = y0 - y1;b = x1 - x0;x = x0;y = y0;pDC-SetPixel(x,y,colo

17、r);/斜率絕對(duì)值小于等于1if (m)/第一種情況，y值遞增if (y0 = y1)d = 2 * a +b;delta1 = 2 * a;delta2 = 2 * (a + b);while (x x1)if (d SetPixel(x,y,color);/第三種情況，y值遞減elsed = 2 * a -b;delta1 = 2 * a;delta2 = 2 * (a - b);while (x x1)if (d SetPixel(x,y,color);/斜率絕對(duì)值大于1else/第二種情況，y值遞增if (y0 = y1)d = a + 2 * b;delta1 = 2 * b;del

18、ta2 = 2 * (a + b);while (y y1)if (d SetPixel(x,y,color);/第四種情況，y值遞減elsed = a - 2 * b;delta1 = -2 * b;delta2 = 2 * (a - b);while (y y1)if (d SetPixel(x,y,color);需要注意四種情況下的循環(huán)條件：第(1)和第(3)種情況是在x增量為1的情況下判斷y的取值，所以在x x1情況下進(jìn)行處理，不滿足此條件時(shí)停止處理。第(2)種情況是在y增量為1的情況下判斷x的取值，所以在y y1（此時(shí)y0 y1（此時(shí)y1 0，則下一個(gè)像素點(diǎn)取P2(xp+1,yp+1

19、)；若d0，故pp與d同號(hào)，可以作為判別量。下面看如何從pp計(jì)算pp+1。將上式中的p換成p+1，有：pp+1 = 2yxp+1 2xyp+1 + c因?yàn)閤p+1 = xp + 1，可知：pp+1 pp = 2y 2x (yp+1 yp)當(dāng)p0，為簡(jiǎn)便運(yùn)算引入新的判別量pp：pp = yd = y(d1 d2) = 2xyp 2yxp + c其中，x = x2 x1，y = y2 y1，c = 2x(1 b) y。下面看如何從pp計(jì)算pp+1。將上式中的p換成p+1，則：pp+1 = 2xyp+1 2yxp+1 + c因?yàn)閥p+1 = yp + 1，可知：pp+1 pp = 2x 2y (xp

20、+1 xp)當(dāng)p0，為簡(jiǎn)便運(yùn)算引入新的判別量pp：pp = xd = x(d1 d2) = 2xyp 2yxp + c其中，x = x2 x1，y = y2 y1，c =x(1 2b) 2y。下面看如何從pp計(jì)算pp+1。將上式中的p換成p+1，有：pp+1 = 2xyp+1 2yxp+1 + c因?yàn)閤p+1 = xp + 1，可知：pp+1 pp = 2x (yp+1 yp) 2y當(dāng)p0，為簡(jiǎn)便運(yùn)算引入新的判別量pp：pp = -yd = -y(d1 d2) = 2yxp 2xyp + c其中，x = x2 x1，y = y2 y1，c = 2x(1 + b) + y。下面看如何從pp計(jì)算p

21、p+1。將上式中的p換成p+1，有：pp+1 = 2yxp+1 2xyp+1 + c因?yàn)閥p+1 = yp 1，可知：pp+1 pp = 2x + 2y (xp+1 xp)當(dāng)p0時(shí)，取P1(xp, yp1)，此時(shí)xp+1 = xp，所以pp+1 = pp + 2x；否則，取P2(xp+1,yp1)，此時(shí)xp+1 = xp + 1，所以pp+1 = pp + 2(x + y)。計(jì)算判別量p1的初始值時(shí)，因?yàn)榫€段上第一個(gè)像素點(diǎn)可以取起點(diǎn)(x1, y1)，所以有：p1 = 2yx1 - 2xy1 + 2x(1 + b) + y因?yàn)閥1 = (y /x)x1 + b，可計(jì)算出：p1 = 2x + y現(xiàn)

22、在我們可以寫(xiě)出Bresenham畫(huà)線算法的實(shí)現(xiàn)函數(shù)，在CDraw類中添加如下的成員函數(shù)：public:/Bresenham畫(huà)線算法void BresenhamLine(CDC* pDC, int x1, int y1, int x2, int y2, COLORREF color);參數(shù)x1、y1、x2、y2為直線段的兩個(gè)端點(diǎn)的坐標(biāo)；參數(shù)pDC是設(shè)備環(huán)境對(duì)象指針；參數(shù)color為繪制直線段的顏色。實(shí)現(xiàn)代碼如下：/Bresenham畫(huà)線算法void CDraw:BresenhamLine(CDC *pDC, int x1, int y1, int x2, int y2, COLORREF col

23、or)int x,y,dx,dy,p;/傳入端點(diǎn)坐標(biāo)x值相等if (x1 = x2)if (y1 y2)for (int i=y1;iSetPixel(x1,i,color);elsefor (int i=y2;iSetPixel(x1,i,color);return;/斜率判斷，斜率絕對(duì)值大于1，則m為false，否則為trueBOOL m = (fabs(y2-y1) x2)p=x1;x1=x2;x2=p;p=y1;y1=y2;y2=p;x = x1;y = y1;dx = x2 - x1;dy = y2 - y1;/斜率絕對(duì)值小于等于1if (m)/第一種情況，y遞增if (y1 = y

24、2)p = (dy1) - dx;while (x SetPixel(x,y,color);if (p 0)x+;p=p+ (dy1);elsex+;y+;p=p+(dy-dx)1);/第三種情況，y遞減elsep = dx (dy1);while (x SetPixel(x,y,color);if (p 0)x+;p=p-(dy1);elsex+;y-;p=p-(dy+dx)1);/斜率絕對(duì)值大于1else/第二種情況，y遞增if (y1 = y2)p = (dx1) - dy;while (y SetPixel(x,y,color);if (p 0)y+;p=p+(dx1);elsex+;

25、y+;p=p+(dx-dy)1);/第四種情況，y遞減elsep = (dx= y2)pDC-SetPixel(x,y,color);if (p 0)y-;p=p+(dx1);elsex+;y-;p=p+(dx+dy)SetCapture();/捕捉鼠標(biāo)/設(shè)置開(kāi)始點(diǎn)和終止點(diǎn)，此時(shí)為同一點(diǎn)m_StartPoint = point;m_EndPoint = point;CView:OnLButtonDown(nFlags, point);修改OnMouseMove函數(shù)，輸入如下代碼：void CScanarithDemoView:OnMouseMove(UINT nFlags, CPoint po

26、int) / TODO: Add your message handler code here and/or call default/當(dāng)處于繪圖狀態(tài)，并且已經(jīng)有了至少一個(gè)節(jié)點(diǎn)時(shí)if (m_SelectDraw != 0 & m_PointsList.GetSize() != 0)/繪制橡皮線CClientDC dc(this);/構(gòu)造設(shè)備環(huán)境對(duì)象dc.SetROP2(R2_NOTXORPEN);/設(shè)置繪圖模式為R2_NOTXORPENdraw.BresenhamLine(&dc,m_StartPoint.x,m_StartPoint.y,m_EndPoint.x,m_EndPoint.y,R

27、GB(200,200,200);draw.BresenhamLine(&dc,m_StartPoint.x,m_StartPoint.y,point.x,point.y,RGB(200,200,200);m_EndPoint = point;CView:OnMouseMove(nFlags, point);修改OnLButtonDblClk函數(shù)，輸入如下代碼：void CScanarithDemoView:OnLButtonDblClk(UINT nFlags, CPoint point) / TODO: Add your message handler code here and/or ca

28、ll defaultReleaseCapture();/釋放鼠標(biāo)/使用DDA直線掃描轉(zhuǎn)換算法繪制直線段if (m_SelectDraw = 1 & m_SelectArithmetic = 1)/節(jié)點(diǎn)數(shù)超過(guò)1，連接每個(gè)節(jié)點(diǎn)成為折線if (m_PointsList.GetSize() 1)CDC* pDC = this-GetDC();for (int i=0;i 1)CDC* pDC = this-GetDC();for (int i=0;i 1)CDC* pDC = this-GetDC();for (int i=0;i 2)CPoint p1 = (CPoint)m_PointsList.

29、GetAt(0);CPoint p2 = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-1);/使用Bresenham畫(huà)線算法繪制直線段draw.BresenhamLine(pDC,p1.x,p1.y,p2.x,p2.y,RGB(0,0,255);ReleaseDC(pDC);/清空節(jié)點(diǎn)列表，以便下次繪制m_PointsList.RemoveAll();CView:OnLButtonDblClk(nFlags, point);運(yùn)行應(yīng)用程序，我們按F1鍵表示用DDA掃描轉(zhuǎn)換算法繪制直線段，按F2鍵表示用中點(diǎn)畫(huà)線法繪制直線段，按F3鍵表示用Br

30、esenham畫(huà)線算法繪制直線段。鼠標(biāo)繪圖方面，本演示程序允許用戶繪制折線。鼠標(biāo)左鍵按下的點(diǎn)作為折線的一個(gè)節(jié)點(diǎn)，可以連續(xù)輸入多個(gè)節(jié)點(diǎn)，雙擊鼠標(biāo)表示設(shè)置節(jié)點(diǎn)結(jié)束，鼠標(biāo)左鍵雙擊的點(diǎn)是最后一個(gè)節(jié)點(diǎn)。演示程序在每?jī)蓚€(gè)連續(xù)節(jié)點(diǎn)之間用用戶選擇的直線掃描轉(zhuǎn)換算法繪制不同顏色的直線段。用DDA掃描轉(zhuǎn)換算法繪制的直線段為黑色，用中點(diǎn)畫(huà)線法繪制的直線段為紅色，用Bresenham畫(huà)線算法繪制的直線段為藍(lán)色。同時(shí)，當(dāng)選用Bresenham畫(huà)線算法時(shí)，如果節(jié)點(diǎn)數(shù)超過(guò)2，會(huì)連接最后一個(gè)節(jié)點(diǎn)和第一個(gè)節(jié)點(diǎn)，形成一個(gè)多邊形。在繪制橡皮線時(shí)，選擇使用Bresenham畫(huà)線算法。上面的代碼很容易理解，這里就不再詳細(xì)說(shuō)明了。比較三

31、種直線掃描轉(zhuǎn)換算法的運(yùn)行效率在OnKeyDown函數(shù)中添加如下代碼：/按F4鍵，比較三種直線掃描轉(zhuǎn)換算法的效率if (nChar = VK_F4)DWORD t1,t2,t3,t4;CClientDC dc(this);CString s1,s2,s3;/獲得當(dāng)前系統(tǒng)已運(yùn)行的毫秒數(shù)t1 = GetTickCount();for (int i=0;i1000;i+)draw.DDALine(&dc,100,100,300,200,RGB(0,0,0);t2 = GetTickCount();for (i=0;i1000;i+)draw.MidpointLine(&dc,100,100,300,2

32、00,RGB(0,0,0);t3 = GetTickCount();for (i=0;i fabs(dy) ? fabs(dx):fabs(dy);dx/=e;dy/=e;x = x1;y = y1;/獲得當(dāng)前設(shè)備環(huán)境對(duì)象的背景色COLORREF bk = pDC-GetBkColor();for (int i=1;i=e;i+)/繪制點(diǎn)的序號(hào)除以10的余數(shù)小于5if (i-1) % 10 SetPixel(int)(x+0.5),(int)(y+0.5),color);elsepDC-SetPixel(int)(x+0.5),(int)(y+0.5),bk);x+=dx;y+=dy;該函數(shù)通

33、過(guò)修改了DDA直線掃描轉(zhuǎn)換算法來(lái)完成繪制虛線線型的直線段。在繪制像素點(diǎn)時(shí)，當(dāng)要繪制的像素點(diǎn)的序號(hào)除以10的余數(shù)小于5時(shí)，用傳入的顏色繪制像素點(diǎn)，否則用當(dāng)前的背景色繪制像素點(diǎn)，這樣繪制出的直線段就表現(xiàn)為虛線。我們來(lái)看一下演示結(jié)果。在OnKeyDown函數(shù)中添加如下代碼：/按F5鍵，用DDA掃描轉(zhuǎn)換算法繪制虛線線型的直線段if (nChar = VK_F5)m_SelectDraw = 1;m_SelectArithmetic = 4;CClientDC dc(this);dc.Rectangle(0,0,800,26);dc.TextOut(10,2,用DDA掃描轉(zhuǎn)換算法繪制虛線線型的直線段);

34、在OnLButtonDblClk函數(shù)中添加如下代碼：/使用DDA直線掃描轉(zhuǎn)換算法繪制虛線線型直線段if (m_SelectDraw = 1 & m_SelectArithmetic = 4)/節(jié)點(diǎn)數(shù)超過(guò)1，連接每個(gè)節(jié)點(diǎn)成為折線if (m_PointsList.GetSize() 1)CDC* pDC = this-GetDC();for (int i=0;i fabs(dy) ? fabs(dx):fabs(dy);dx/=e;dy/=e;x = x1;y = y1;/獲得當(dāng)前設(shè)備環(huán)境對(duì)象的背景色COLORREF bk = pDC-GetBkColor();for (int i=1;i=e;i

35、+)/根據(jù)線寬，在要繪制的像素周圍繪制額外的像素for (int j=(1-width)/2;j=width/2;j+)for (int k=(1-width)/2;kSetPixel(int)(x+0.5) + j,(int)(y+0.5) + k,color);x+=dx;y+=dy;在繪制像素點(diǎn)時(shí)，根據(jù)指定的線寬繪制額外的像素點(diǎn)就可以使直線段變寬。讓我們看一下演示結(jié)果。在OnKeyDown函數(shù)中添加如下代碼：/按F7鍵，用DDA掃描轉(zhuǎn)換算法繪制線寬為5的直線段if (nChar = VK_F7)m_SelectDraw = 1;m_SelectArithmetic = 5;CClient

36、DC dc(this);dc.Rectangle(0,0,800,26);dc.TextOut(10,2,用DDA掃描轉(zhuǎn)換算法繪制線寬為5的直線段);在OnLButtonDblClk函數(shù)中添加如下代碼：/使用DDA直線掃描轉(zhuǎn)換算法繪制線寬為5的直線段if (m_SelectDraw = 1 & m_SelectArithmetic = 5)/節(jié)點(diǎn)數(shù)超過(guò)1，連接每個(gè)節(jié)點(diǎn)成為折線if (m_PointsList.GetSize() 1)CDC* pDC = this-GetDC();for (int i=0;i 0；而對(duì)于圓內(nèi)的點(diǎn)，F(xiàn)(x, y) 0。假設(shè)x坐標(biāo)為xp的像素中與該段圓弧的最接近的像

37、素點(diǎn)已經(jīng)確定，為(xp, yp)，那么下一個(gè)像素點(diǎn)只能是正右方的P1(xp+1, yp)或者右下方的P2(xp+1,yp-1)二者之一。假設(shè)M是P1和P2的中點(diǎn)，即M = (xp+1, yp 0.5)。那么當(dāng)F(M) 0，M在圓外，說(shuō)明P2離圓弧更近，應(yīng)取P2作為下一像素點(diǎn)；若F(M) = 0，則說(shuō)明兩點(diǎn)距圓弧距離一樣，可以任選一點(diǎn)，我們約定選擇P2。同中點(diǎn)畫(huà)線法一樣，構(gòu)造如下判別式：d = F(M) = F(xp + 1, yp 0.5) = (xp + 1)2 + (yp 0.5)2 R2如果d 0，則取P1(xp+1, yp)作為下一個(gè)像素點(diǎn)，而再下一個(gè)像素點(diǎn)的判別式為：d1 = F(x

38、p + 2, yp 0.5) = (xp + 2)2 + (yp 0.5)2 R2 = d + 2xp + 3所以d的增量為2xp + 3。如果d 0，取P2(xp+1,yp-1)作為下一個(gè)像素點(diǎn)，而再下一個(gè)像素點(diǎn)的判別式為：d2 = F(xp + 2, yp 1.5) = (xp + 2)2 + (yp 1.5)2 R2 = d + 2xp 2yp + 5所以d的增量為2(xp yp) + 5。因?yàn)樵摱螆A弧的第一個(gè)像素點(diǎn)為(0, R)，所以d的初始值為：d0 = F(1, R 0.5) = 1 + (R 0.5)2 R2 = 1.25 R為了擺脫浮點(diǎn)數(shù)，使用e = d 0.25來(lái)代替d。此時(shí)

39、初始的d0 = 1.25 R對(duì)應(yīng)e = 1 R，而d 0則對(duì)應(yīng)e -0.25?？梢杂胑代替算法中的d，因?yàn)閑的初始值為整數(shù)，且運(yùn)算過(guò)程中增量也為整數(shù)，所以e始終為整數(shù)，則e -0.25等同于e 0。同時(shí)我們注意到，e的增量是一個(gè)x、y的線性函數(shù)，每當(dāng)x遞增1，e遞增x = 2；每當(dāng)y遞減1，e遞增y = 2。因?yàn)槌跏枷袼攸c(diǎn)為(0, R)，所以x的初始值為3，y的初始值為-2R + 5?，F(xiàn)在我們可以編寫(xiě)中點(diǎn)畫(huà)圓法的實(shí)現(xiàn)函數(shù)，在CDraw類中添加下面的成員函數(shù)：public:/中點(diǎn)畫(huà)圓法void MidpointCircle(CDC* pDC, int x0, int y0, int R, COL

40、ORREF color);其中參數(shù)x0、y0為要繪制的圓的圓心坐標(biāo)；參數(shù)R為圓的半徑；參數(shù)pDC為設(shè)備環(huán)境對(duì)象指針；參數(shù)color為繪制圓的顏色。函數(shù)實(shí)現(xiàn)代碼如下：void CDraw:MidpointCircle(CDC *pDC, int x0, int y0, int R, COLORREF color)int x,y,dx,dy,d;x = 0; y = R; d = 1 - R;dx = 3;dy = 5 - (R1);while (x SetPixel(x + x0, y + y0, color);pDC-SetPixel(-x + x0, y + y0, color);pDC-S

41、etPixel(x + x0, -y + y0, color);pDC-SetPixel(-x + x0, -y + y0, color);pDC-SetPixel(y + x0, x + y0, color);pDC-SetPixel(-y + x0, x + y0, color);pDC-SetPixel(y + x0, -x + y0, color);pDC-SetPixel(-y + x0, -x + y0, color);if (d 1)/擦除橡皮線CDC* pDC = this-GetDC();int mode = pDC-SetROP2(R2_NOTXORPEN);for (in

42、t i=0;iSetROP2(mode);/獲得列表中最后兩個(gè)點(diǎn)，前一個(gè)為圓心，后一個(gè)用于計(jì)算半徑CPoint p0 = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-2);CPoint pr = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-1);int R = (int)sqrt(pr.x - p0.x)*(pr.x - p0.x) +(pr.y - p0.y) * (pr.y - p0.y);/使用中點(diǎn)畫(huà)圓法繪制圓draw.MidpointCircle(pDC,p0.x,p0.y,

43、R,RGB(255,0,0);ReleaseDC(pDC);/清空節(jié)點(diǎn)列表，以便下次繪制m_PointsList.RemoveAll();運(yùn)行應(yīng)用程序，按F8鍵，鼠標(biāo)畫(huà)的折線的最后兩個(gè)節(jié)點(diǎn)中的第一個(gè)是圓心，兩個(gè)節(jié)點(diǎn)間距離是半徑，結(jié)果如圖3.6所示。Bresenham畫(huà)圓算法的實(shí)現(xiàn)Bresenham畫(huà)圓算法和中點(diǎn)畫(huà)圓法一樣，也考慮從(0, R)到(R/2, R/2)的八分之一圓周。在此圓周上有|dy/dx| = |-x/y| 1，所以當(dāng)x增量為1時(shí)，y的遞減量小于1。假設(shè)x坐標(biāo)為xp的像素中與該段圓弧的最接近的像素點(diǎn)已經(jīng)確定，為(xp, yp)，那么下一個(gè)像素點(diǎn)只能是正右方的P1(xp+1, y

44、p)或者右下方的P2(xp+1,yp-1)二者之一。此時(shí)兩點(diǎn)距圓心的平方差為：d1 = (xp + 1)2 + yp2 R2d2 = R2 (xp + 1)2 (yp 1)2我們引入判別量pp：pp = d1 d2 = 2(xp + 1)2 + 2yp2 2yp 2R2 + 1下面看如何從pp計(jì)算pp+1，將上式中的p換為p+1，有：pp+1 = 2(xp+1 + 1)2 + 2yp+12 2yp+1 2R2 + 1可知：pp+1 pp = 2(yp+12 - yp2 yp+1 + y當(dāng)pp 0時(shí)，選P1(xp+1, yp)作為下一個(gè)像素點(diǎn)，此時(shí)yp+1 = yp，所以pp+1 = pp +

45、4xp + 6；否則，選P2(xp+1,yp-1)作為下一個(gè)像素點(diǎn)，此時(shí)yp+1 = yp 1，所以pp+1 = pp + 4(xp yp) + 10。因?yàn)?0, R)是該段圓周的起始點(diǎn)，所以判別式p的初始值為：p0 = 3 2R根據(jù)以上說(shuō)明可以編寫(xiě)B(tài)resenham畫(huà)圓算法的實(shí)現(xiàn)函數(shù)，在CDraw類中添加下面的成員函數(shù)：public:/Bresenham畫(huà)圓算法void BresenhamCircle(CDC *pDC, int x0, int y0, int R, COLORREF color);其中參數(shù)x0、y0為要繪制的圓的圓心坐標(biāo)；參數(shù)R為圓的半徑；參數(shù)pDC為設(shè)備環(huán)境對(duì)象指針；參數(shù)

46、color為繪制圓的顏色。函數(shù)實(shí)現(xiàn)代碼如下：void CDraw:BresenhamCircle(CDC *pDC, int x0, int y0, int R, COLORREF color)int x,y,p;x = 0;y = R;p = 3 - (R1);for (;xSetPixel(x + x0, y + y0, color);pDC-SetPixel(-x + x0, y + y0, color);pDC-SetPixel(x + x0, -y + y0, color);pDC-SetPixel(-x + x0, -y + y0, color);pDC-SetPixel(y +

47、x0, x + y0, color);pDC-SetPixel(-y + x0, x + y0, color);pDC-SetPixel(y + x0, -x + y0, color);pDC-SetPixel(-y + x0, -x + y0, color);if (p 0)p+=(x2) + 6);elsep+=(x-y) 1)/擦除橡皮線CDC* pDC = this-GetDC();int mode = pDC-SetROP2(R2_NOTXORPEN);for (int i=0;iSetROP2(mode);/獲得列表中最后兩個(gè)點(diǎn)，前一個(gè)為圓心，后一個(gè)用于計(jì)算半徑CPoint p0

48、= (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-2);CPoint pr = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-1);int R = (int)sqrt(pr.x - p0.x)*(pr.x - p0.x) +(pr.y - p0.y) * (pr.y - p0.y);/使用Bresenham畫(huà)圓算法繪制圓draw.BresenhamCircle(pDC,p0.x,p0.y,R,RGB(0,0,255);ReleaseDC(pDC);/清空節(jié)點(diǎn)列表，以便下次繪制m_Poin

49、tsList.RemoveAll();運(yùn)行應(yīng)用程序，按F9鍵，使用與演示中點(diǎn)畫(huà)圓法相同的方式來(lái)利用Bresenham畫(huà)圓算法繪制圓，運(yùn)行結(jié)果如圖3.7所示。Bresenham畫(huà)橢圓算法的實(shí)現(xiàn)按照類似的思想，我們可以修改Bresenham畫(huà)圓算法，使之可以繪制橢圓。設(shè)橢圓中心在(0, 0)點(diǎn)，長(zhǎng)軸和短軸分別為a和b，中心在其它點(diǎn)的橢圓可以通過(guò)移動(dòng)中心在(0, 0)點(diǎn)的橢圓來(lái)獲得。因?yàn)闄E圓的特點(diǎn)與圓不同，在使用Bresenham算法的時(shí)候不能夠像繪制圓那樣，只考慮繪制八分之一圓周，而應(yīng)當(dāng)根據(jù)橢圓本身的對(duì)稱性，考慮如何繪制四分之一橢圓，其余部分可以通過(guò)繪制已得到的四分之一橢圓上的對(duì)稱像素點(diǎn)來(lái)獲得。因

50、為橢圓中心在坐標(biāo)原點(diǎn)，所以考察如何繪制橢圓在第一象限中的部分，如圖3.8所示。已知橢圓方程為，即。橢圓在第一象限部分，隨著值的單調(diào)增加（從0到a），值單調(diào)減少（從b到0）。對(duì)橢圓方程求導(dǎo)得出。此時(shí)可在處將橢圓在第一象限的部分分成兩部分，如圖3.8所示。第 eq oac(,1)部分，此時(shí)取時(shí)，橢圓上對(duì)應(yīng)的值變化小于1；第 eq oac(,2)部分，此時(shí)取時(shí)，橢圓上對(duì)應(yīng)的值變化小于1。對(duì)于第 eq oac(,1)部分：在已知為橢圓上的像素點(diǎn)時(shí)，需要確定下一個(gè)橢圓上的像素點(diǎn)應(yīng)該是H還是D，如圖3.9所示。H點(diǎn)和D點(diǎn)離橢圓中心的平方差為：設(shè)判別量為：則計(jì)算得當(dāng)時(shí)，取D為下一個(gè)像素點(diǎn)，即此時(shí)當(dāng)時(shí)，取H為

51、下一個(gè)像素點(diǎn)，即此時(shí)因?yàn)槠鹗键c(diǎn)為橢圓與y軸的交點(diǎn)，所以，?？傻么瞬糠钟?jì)算應(yīng)滿足條件，即。對(duì)于第 eq oac(,2)部分：為了計(jì)算簡(jiǎn)便，我們從橢圓與x軸的交點(diǎn)開(kāi)始向上取點(diǎn)。即在已知為橢圓上的像素點(diǎn)時(shí)，需要確定下一個(gè)橢圓上的像素點(diǎn)應(yīng)該是H還是D，如圖3.10所示。H點(diǎn)和D點(diǎn)離橢圓中心的平方差為：仔細(xì)觀察這兩個(gè)值，我們會(huì)發(fā)現(xiàn)它們與計(jì)算第 eq oac(,1)部分時(shí)的和的差別就在于變成了，變成了，變成了，變成了。所以按此規(guī)則可以很容易的獲得其它各量的值。判別量為：則計(jì)算得當(dāng)時(shí)，取D為下一個(gè)像素點(diǎn)，即此時(shí)當(dāng)時(shí)，取H為下一個(gè)像素點(diǎn)，即此時(shí)因?yàn)槠鹗键c(diǎn)為橢圓與x軸的交點(diǎn)，所以，?？傻么瞬糠钟?jì)算應(yīng)滿足條件，即

52、。根據(jù)以上說(shuō)明，可以編寫(xiě)B(tài)resenham畫(huà)橢圓算法的實(shí)現(xiàn)函數(shù)。在CDraw類中添加下面的成員函數(shù)：public:/Bresenham畫(huà)橢圓算法void BresenhamEllipse(CDC *pDC, int x0, int y0, int a, int b, COLORREF color);其中參數(shù)x0、y0為橢圓的圓心；參數(shù)a、b為橢圓的長(zhǎng)短軸長(zhǎng)度；參數(shù)pDC為設(shè)備環(huán)境對(duì)象指針；參數(shù)color為繪制橢圓的顏色。實(shí)現(xiàn)代碼如下：void CDraw:BresenhamEllipse(CDC *pDC, int x0, int y0, int a, int b, COLORREF colo

53、r)int x,y,p;int aa=a*a,bb=b*b;/下面繪制第1部分x=0;y=b; p=2*bb+aa*(1-2*b);while (bb*xSetPixel(x+x0,y+y0,color);pDC-SetPixel(-x+x0,y+y0,color);pDC-SetPixel(x+x0,-y+y0,color);pDC-SetPixel(-x+x0,-y+y0,color);if(p=0)p+=4*aa*(1-y)+bb*(4*x+6);y-;elsep+= bb*(4*x+6);x+;/下面繪制第2部分x=a;y=0; p=2*aa+bb*(1-2*a);while (bb*

54、xaa*y)/繪制對(duì)稱的四個(gè)點(diǎn)pDC-SetPixel(x+x0,y+y0,color);pDC-SetPixel(-x+x0,y+y0,color);pDC-SetPixel(x+x0,-y+y0,color);pDC-SetPixel(-x+x0,-y+y0,color);if(p=0)p+=4*bb*(1-x)+aa*(4*y+6);x-;elsep+= aa*(4*y+6);y+;需要注意，兩部分都要將對(duì)稱的四個(gè)點(diǎn)繪制出來(lái)。來(lái)看一下演示。修改OnKeyDown函數(shù)，添加如下代碼：/按F11鍵，用Bresenham畫(huà)橢圓算法繪制橢圓if (nChar = VK_F11)m_SelectD

55、raw = 2;/畫(huà)橢圓m_SelectArithmetic = 3;/使用Bresenham畫(huà)橢圓算法CClientDC dc(this);dc.Rectangle(0,0,800,26);dc.TextOut(10,2,用Bresenham畫(huà)橢圓算法繪制橢圓);在OnLButtonDblClk函數(shù)中添加如下代碼：/使用Bresenham畫(huà)橢圓算法繪制橢圓if (m_SelectDraw = 2 & m_SelectArithmetic = 3)/節(jié)點(diǎn)數(shù)超過(guò)1，可以繪制橢圓if (m_PointsList.GetSize() 1)/擦除橡皮線CDC* pDC = this-GetDC();i

56、nt mode = pDC-SetROP2(R2_NOTXORPEN);for (int i=0;iSetROP2(mode);/獲得列表中最后兩個(gè)點(diǎn)，前一個(gè)為圓心，后一個(gè)用于計(jì)算長(zhǎng)短軸CPoint p0 = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-2);CPoint pr = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-1);/使用Bresenham畫(huà)橢圓算法繪制橢圓/兩點(diǎn)的x坐標(biāo)值差的絕對(duì)值為長(zhǎng)軸長(zhǎng)/兩點(diǎn)的y坐標(biāo)值差的絕對(duì)值為短軸長(zhǎng)draw.BresenhamEllipse(

57、pDC,p0.x,p0.y,abs(pr.x - p0.x),abs(pr.y - p0.y),RGB(0,0,255);ReleaseDC(pDC);m_PointsList.RemoveAll();/清空節(jié)點(diǎn)列表，以便下次繪制運(yùn)行應(yīng)用程序，按F11鍵，可以繪制橢圓，結(jié)果如圖3.11所示。 區(qū)域填充算法的實(shí)現(xiàn)區(qū)域填充算法的任務(wù)是找到封閉區(qū)域內(nèi)的所有像素點(diǎn)，然后設(shè)置像素點(diǎn)為指定的顏色。區(qū)域填充算法可以分為以像素為基礎(chǔ)的和以多邊形為基礎(chǔ)的兩種。以像素為基礎(chǔ)的區(qū)域填充算法通過(guò)像素的顏色來(lái)定義區(qū)域的內(nèi)部和邊界，算法通過(guò)對(duì)像素顏色的判斷來(lái)完成填充。以多邊形為基礎(chǔ)的區(qū)域填充算法，用多邊形擬合區(qū)域的邊界，

58、通過(guò)多邊形的頂點(diǎn)序列來(lái)計(jì)算獲得區(qū)域內(nèi)部的像素點(diǎn)，再進(jìn)行填充。常用的以像素為基礎(chǔ)的區(qū)域填充算法是種子填充算法，而常用的以多邊形為基礎(chǔ)的區(qū)域填充算法是多邊形掃描轉(zhuǎn)換算法。種子填充算法的實(shí)現(xiàn)以像素為基礎(chǔ)的區(qū)域填充主要是依據(jù)區(qū)域的連通性進(jìn)行。在光柵顯示器上，區(qū)域內(nèi)部的像素點(diǎn)是呈網(wǎng)格狀的。從其中一個(gè)像素出發(fā)，經(jīng)過(guò)連續(xù)的向上、下、左和右的四個(gè)相鄰像素移動(dòng)可以到達(dá)區(qū)域內(nèi)的任意另一像素，則稱區(qū)域是四連通的。如果除了向上、下、左和右的四個(gè)相鄰像素移動(dòng)，還需要經(jīng)過(guò)向左上、右上、左下和右下的相鄰像素的移動(dòng)，才能到達(dá)區(qū)域內(nèi)的任意另一個(gè)像素，則稱區(qū)域是八連通的。通過(guò)像素顏色定義區(qū)域通常有兩種方法。一種是內(nèi)定義區(qū)域，定義

59、方法是指出區(qū)域內(nèi)部所有像素的顏色，此時(shí)區(qū)域內(nèi)部所有像素具有一個(gè)原顏色oldvalue，區(qū)域邊界上的所有像素不具有該顏色。另外一種是邊界定義區(qū)域，定義方法是指出區(qū)域邊界像素所具有的顏色boundaryvalue，此時(shí)要求區(qū)域邊界應(yīng)該是封閉的。這兩種區(qū)域定義方法定義的區(qū)域都可以使用種子填充算法進(jìn)行填充。算法思想是：給出區(qū)域內(nèi)部的一個(gè)像素點(diǎn)，該像素稱為種子，填充時(shí)，從種子出發(fā)，遍歷光柵像素網(wǎng)格，找出從種子出發(fā)可以到達(dá)而又不穿過(guò)邊界的所有像素。種子填充算法最簡(jiǎn)單的實(shí)現(xiàn)方法是采用遞歸的方式。比如下面的函數(shù)即可完成對(duì)一個(gè)內(nèi)定義區(qū)域的種子填充：void CDraw:FloodFill(CDC *pDC, i

60、nt x, int y, COLORREF oldvalue, COLORREF newvalue)if (pDC-GetPixel(x,y) = oldvalue)pDC-SetPixel(x,y,newvalue);FloodFill(pDC,x,y-1,oldvalue,newvalue);FloodFill(pDC,x,y+1,oldvalue,newvalue);FloodFill(pDC,x-1,y,oldvalue,newvalue);FloodFill(pDC,x+1,y,oldvalue,newvalue);其中參數(shù)x，y是種子點(diǎn)坐標(biāo)；參數(shù)oldvalue是區(qū)域內(nèi)部像素具有的