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

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

2、形稱為圖形基元。圖形基元的選擇可以有不同的方法，但是通常都會把線段、圓和多邊形選為圖形基元。本章將通過MFC編程的方式實現(xiàn)線段、圓和多邊形的掃描轉換算法，并創(chuàng)建一個MFC應用程序項目來演示這些掃描轉換算法的結果。為了能夠更好的演示掃描轉化算法的結果，我們創(chuàng)建一個MFC應用程序項目（除了選擇單文檔外，其它選項使用默認選擇），項目名稱為ScanarithDemo，然后創(chuàng)建一個普通類CDraw，我們在該類中實現(xiàn)掃描轉換算法。為視圖類CScanarithDemoView添加WM_LBUTTONDOWN（鼠標左鍵按下）消息、WM_LBUTTONDBLCLK（鼠標左鍵雙擊）消息、WM_MOUSEMOVE（

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

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

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

6、yi+1 = yi + 1時，xi+1 = xi + 1/m。根據(jù)此思想，可以寫出DDA直線掃描轉換算法的實現(xiàn)函數(shù)。在CDraw類中添加如下成員函數(shù)用于實現(xiàn)DDA直線掃描轉換算法：public:/DDA直線掃描轉換算法void DDALine(CDC* pDC, int x1, int y1, int x2,int y2,COLORREF color);其中參數(shù)x1、y1、x2、y2是要繪制的直線段的兩個端點的坐標；參數(shù)pDC是設備環(huán)境對象指針，我們需要繪制像素點；參數(shù)color為繪制直線段的顏色。實現(xiàn)代碼如下：/DDA直線掃描轉換算法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;中點畫線法的實現(xiàn)中點畫線法的基本原理如下：假定直線斜率在0和1之間，如圖3.1(1)所示。此時直線在y值方向上的變化要小于x值方向上的變化，所以在x

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

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

10、P1作為下一像素。當d0時，取P2(xp+1,yp+1)為下一像素，此時要判斷下一個像素取哪個，應計算：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)為下一像素，要判斷下一個像素應取哪個，應計算：d2 = F(xp+2, yp+0.5) = a(xp+2) + b(yp+0.5) + c = d + a故d的增量為a。最后看d的初始值。顯然，第一個像素應取(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因為(x0, y0)在直線上，所以F(x0, y0) = 0。因此d的初始值為d0 = a + 0.5b。為了擺脫小數(shù)，可以取2d來代替d，此時初始值d0 = 2a + b，當d0時，增量為2(a+b)，否則，增量為2a。使用相同方法可以確定其它三種情況下的d0以及d的增量。第(2)種情況，斜率大于1，此時直線在y值方向上的變化大于x值方向上的變化，下一個像素可以為P1(xp, yp+1)或P2(xp+1, yp+1)。此時判別式為：d = F(xp+0.5, yp+1) = a(xp+0.5) +

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

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

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

15、d0 = a 2b，當d0時，增量為2(ab)，否則，增量為2b。至此我們可以寫出中點畫線法的實現(xiàn)函數(shù)，在CDraw類中添加如下成員函數(shù)：public:/中點畫線法void MidpointLine(CDC* pDC, int x0, int y0, int x1, int y1, COLORREF color);參數(shù)x0、y0、x1、y1為直線段的兩個端點的坐標；參數(shù)pDC是設備環(huán)境對象指針；參數(shù)color為繪制直線段的顏色。實現(xiàn)代碼如下：/中點畫線法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;/傳入端點坐標x值相等if (x0 = x1)if (y0 y1)for (int i=y0;iSetPixel(x0,i,color);elsefor (int i=y1;iSetPixel(x0,i,color);return;/斜率判斷，斜率絕對值大于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);/斜率絕對值小于等于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);/斜率絕對值大于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情況下進行處理，不滿足此條件時停止處理。第(2)種情況是在y增量為1的情況下判斷x的取值，所以在y y1（此時y0 y1（此時y1 0，則下一個像素點取P2(xp+1,yp+1

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

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

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

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

23、or)int x,y,dx,dy,p;/傳入端點坐標x值相等if (x1 = x2)if (y1 y2)for (int i=y1;iSetPixel(x1,i,color);elsefor (int i=y2;iSetPixel(x1,i,color);return;/斜率判斷，斜率絕對值大于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;/斜率絕對值小于等于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);/斜率絕對值大于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();/捕捉鼠標/設置開始點和終止點，此時為同一點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/當處于繪圖狀態(tài)，并且已經有了至少一個節(jié)點時if (m_SelectDraw != 0 & m_PointsList.GetSize() != 0)/繪制橡皮線CClientDC dc(this);/構造設備環(huán)境對象dc.SetROP2(R2_NOTXORPEN);/設置繪圖模式為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();/釋放鼠標/使用DDA直線掃描轉換算法繪制直線段if (m_SelectDraw = 1 & m_SelectArithmetic = 1)/節(jié)點數(shù)超過1，連接每個節(jié)點成為折線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畫線算法繪制直線段draw.BresenhamLine(pDC,p1.x,p1.y,p2.x,p2.y,RGB(0,0,255);ReleaseDC(pDC);/清空節(jié)點列表，以便下次繪制m_PointsList.RemoveAll();CView:OnLButtonDblClk(nFlags, point);運行應用程序，我們按F1鍵表示用DDA掃描轉換算法繪制直線段，按F2鍵表示用中點畫線法繪制直線段，按F3鍵表示用Br

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

31、種直線掃描轉換算法的運行效率在OnKeyDown函數(shù)中添加如下代碼：/按F4鍵，比較三種直線掃描轉換算法的效率if (nChar = VK_F4)DWORD t1,t2,t3,t4;CClientDC dc(this);CString s1,s2,s3;/獲得當前系統(tǒng)已運行的毫秒數(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;/獲得當前設備環(huán)境對象的背景色COLORREF bk = pDC-GetBkColor();for (int i=1;i=e;i+)/繪制點的序號除以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、過修改了DDA直線掃描轉換算法來完成繪制虛線線型的直線段。在繪制像素點時，當要繪制的像素點的序號除以10的余數(shù)小于5時，用傳入的顏色繪制像素點，否則用當前的背景色繪制像素點，這樣繪制出的直線段就表現(xiàn)為虛線。我們來看一下演示結果。在OnKeyDown函數(shù)中添加如下代碼：/按F5鍵，用DDA掃描轉換算法繪制虛線線型的直線段if (nChar = VK_F5)m_SelectDraw = 1;m_SelectArithmetic = 4;CClientDC dc(this);dc.Rectangle(0,0,800,26);dc.TextOut(10,2,用DDA掃描轉換算法繪制虛線線型的直線段);

34、在OnLButtonDblClk函數(shù)中添加如下代碼：/使用DDA直線掃描轉換算法繪制虛線線型直線段if (m_SelectDraw = 1 & m_SelectArithmetic = 4)/節(jié)點數(shù)超過1，連接每個節(jié)點成為折線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;/獲得當前設備環(huán)境對象的背景色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;在繪制像素點時，根據(jù)指定的線寬繪制額外的像素點就可以使直線段變寬。讓我們看一下演示結果。在OnKeyDown函數(shù)中添加如下代碼：/按F7鍵，用DDA掃描轉換算法繪制線寬為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掃描轉換算法繪制線寬為5的直線段);在OnLButtonDblClk函數(shù)中添加如下代碼：/使用DDA直線掃描轉換算法繪制線寬為5的直線段if (m_SelectDraw = 1 & m_SelectArithmetic = 5)/節(jié)點數(shù)超過1，連接每個節(jié)點成為折線if (m_PointsList.GetSize() 1)CDC* pDC = this-GetDC();for (int i=0;i 0；而對于圓內的點，F(xiàn)(x, y) 0。假設x坐標為xp的像素中與該段圓弧的最接近的像

37、素點已經確定，為(xp, yp)，那么下一個像素點只能是正右方的P1(xp+1, yp)或者右下方的P2(xp+1,yp-1)二者之一。假設M是P1和P2的中點，即M = (xp+1, yp 0.5)。那么當F(M) 0，M在圓外，說明P2離圓弧更近，應取P2作為下一像素點；若F(M) = 0，則說明兩點距圓弧距離一樣，可以任選一點，我們約定選擇P2。同中點畫線法一樣，構造如下判別式：d = F(M) = F(xp + 1, yp 0.5) = (xp + 1)2 + (yp 0.5)2 R2如果d 0，則取P1(xp+1, yp)作為下一個像素點，而再下一個像素點的判別式為：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)作為下一個像素點，而再下一個像素點的判別式為：d2 = F(xp + 2, yp 1.5) = (xp + 2)2 + (yp 1.5)2 R2 = d + 2xp 2yp + 5所以d的增量為2(xp yp) + 5。因為該段圓弧的第一個像素點為(0, R)，所以d的初始值為：d0 = F(1, R 0.5) = 1 + (R 0.5)2 R2 = 1.25 R為了擺脫浮點數(shù)，使用e = d 0.25來代替d。此時

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

40、ORREF color);其中參數(shù)x0、y0為要繪制的圓的圓心坐標；參數(shù)R為圓的半徑；參數(shù)pDC為設備環(huán)境對象指針；參數(shù)color為繪制圓的顏色。函數(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);/獲得列表中最后兩個點，前一個為圓心，后一個用于計算半徑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);/使用中點畫圓法繪制圓draw.MidpointCircle(pDC,p0.x,p0.y,

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

44、p)或者右下方的P2(xp+1,yp-1)二者之一。此時兩點距圓心的平方差為：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計算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當pp 0時，選P1(xp+1, yp)作為下一個像素點，此時yp+1 = yp，所以pp+1 = pp +

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

46、color為繪制圓的顏色。函數(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);/獲得列表中最后兩個點，前一個為圓心，后一個用于計算半徑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畫圓算法繪制圓draw.BresenhamCircle(pDC,p0.x,p0.y,R,RGB(0,0,255);ReleaseDC(pDC);/清空節(jié)點列表，以便下次繪制m_Poin

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

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

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

52、。根據(jù)以上說明，可以編寫B(tài)resenham畫橢圓算法的實現(xiàn)函數(shù)。在CDraw類中添加下面的成員函數(shù)：public:/Bresenham畫橢圓算法void BresenhamEllipse(CDC *pDC, int x0, int y0, int a, int b, COLORREF color);其中參數(shù)x0、y0為橢圓的圓心；參數(shù)a、b為橢圓的長短軸長度；參數(shù)pDC為設備環(huán)境對象指針；參數(shù)color為繪制橢圓的顏色。實現(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)/繪制對稱的四個點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+;需要注意，兩部分都要將對稱的四個點繪制出來。來看一下演示。修改OnKeyDown函數(shù)，添加如下代碼：/按F11鍵，用Bresenham畫橢圓算法繪制橢圓if (nChar = VK_F11)m_SelectD

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

56、nt mode = pDC-SetROP2(R2_NOTXORPEN);for (int i=0;iSetROP2(mode);/獲得列表中最后兩個點，前一個為圓心，后一個用于計算長短軸CPoint p0 = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-2);CPoint pr = (CPoint)m_PointsList.GetAt(m_PointsList.GetSize()-1);/使用Bresenham畫橢圓算法繪制橢圓/兩點的x坐標值差的絕對值為長軸長/兩點的y坐標值差的絕對值為短軸長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é)點列表，以便下次繪制運行應用程序，按F11鍵，可以繪制橢圓，結果如圖3.11所示。 區(qū)域填充算法的實現(xiàn)區(qū)域填充算法的任務是找到封閉區(qū)域內的所有像素點，然后設置像素點為指定的顏色。區(qū)域填充算法可以分為以像素為基礎的和以多邊形為基礎的兩種。以像素為基礎的區(qū)域填充算法通過像素的顏色來定義區(qū)域的內部和邊界，算法通過對像素顏色的判斷來完成填充。以多邊形為基礎的區(qū)域填充算法，用多邊形擬合區(qū)域的邊界，

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

59、方法是指出區(qū)域內部所有像素的顏色，此時區(qū)域內部所有像素具有一個原顏色oldvalue，區(qū)域邊界上的所有像素不具有該顏色。另外一種是邊界定義區(qū)域，定義方法是指出區(qū)域邊界像素所具有的顏色boundaryvalue，此時要求區(qū)域邊界應該是封閉的。這兩種區(qū)域定義方法定義的區(qū)域都可以使用種子填充算法進行填充。算法思想是：給出區(qū)域內部的一個像素點，該像素稱為種子，填充時，從種子出發(fā)，遍歷光柵像素網格，找出從種子出發(fā)可以到達而又不穿過邊界的所有像素。種子填充算法最簡單的實現(xiàn)方法是采用遞歸的方式。比如下面的函數(shù)即可完成對一個內定義區(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是種子點坐標；參數(shù)oldvalue是區(qū)域內部像素具有的