跟我一起學圖形編程

                              作者：姚明           聯系方式：alanvincentmail@gmail.com     2011年1月25日 21:16:15

從本課開始，我們才真正接觸到圖形學的相關算法，前面教程只是在搭建環境，從這節課開始，我們可以把精力集中在算法上，再不需要了解太多的系統函數。上節課，我們感受到了“點”的魅力，要知道，世界上所有的畫面都是由點組成的，包括我們上節課例子程序中隨機生成的圖像，從某種意義上說，那些圖像每時每刻都是一副獨一無二的畫，但是，為什么我們不覺得它是真正的畫呢？那是因為，它的每個像素都是隨機產生的，像素與像素之間沒有規律，沒有聯系，所以，我們也無法從中獲取信息，換句話說，那些都是不包含任何信息的畫面。現在，我們試圖讓象素和象素之間產生關系，其中最常見的一種就是直線。有了它，我們就可以在畫面中表達信息了。

我不打算具體的描述算法細節，因為有很多書，都寫得很詳細，易懂，甚至配有動畫效果，例如：點擊下載。每個人的時間和精力有限，不能把寶貴的時間用在重復的發明輪子上，另外，把飯端到嘴邊，再用勺子喂飯的事情，那是一種失敗。我更愿意充當一名向導的角色，指引著大家如何學？怎么學？學什么？同時激起大家的興趣和想象力，跟著我共同提高。

理論：

數學告訴我們連續和離散的概念，在計算機中，我們接觸到的往往是離散的事物，例如，我們現在看到的顯示屏，就是由離散的象素點，排列組成的。每個像素都用X和Y兩個整數表達位置。現在問題出現了，我們畫的線是個連續量，所以，有的象素X和Y的位置不一定是整數，有可能產生小數，出現小數時，我們必須取整才能和屏幕上的象素對應，這個過程就有精度的缺失，所以我們屏幕上得到的結果是離散后的近似值。DDA算法是用微分方程得到斜率k,注意k是小數而且用除法算出來的，所以，計算機中運算效率不高。要知道，直線是組成任何畫面的基礎元素，在直線算法中，效率提高1分，有可能讓整個場景效率提高100分，因此，DDA很快就被其它算法取代，其中Bresenham算法比較優秀，它用一個判別式做決策，決定下一點的位置，判別式中沒有小數運算，雖然，有乘2運算，但乘2可以用移位運算代替，所以效率極高。

內容：

  1/**//*------------------------------------------------------------------------
  2  LINES.CPP – 在窗口客戶區繪制直線的動畫效果
  3
  4                 (c) 姚明, 2010 
  5-----------------------------------------------------------------------*/ 
  6#include <windows.h>
  7#include <math.h>
  8
  9#define ID_TIMER    1
 10
 11LRESULT CALLBACK WndProc (HWND, UINT, WPARAM, LPARAM) ;
 12BOOL  Bresenham(int nX1, int nY1, int nX2, int nY2, HDC    &DC);
 13 
 14int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,
 15                   PSTR szCmdLine, int iCmdShow)
 16{
 17static TCHAR szAppName[] = TEXT ("lines") ;
 18    HWND   hwnd ;
 19    MSG    msg ;
 20    WNDCLASS    wndclass ;
 21    wndclass.style        = CS_HREDRAW | CS_VREDRAW ;
 22    wndclass.lpfnWndProc  = WndProc ;
 23    wndclass.cbClsExtra   = 0 ;
 24    wndclass.cbWndExtra   = 0 ;
 25    wndclass.hInstance    = hInstance ;
 26    wndclass.hIcon        = LoadIcon (NULL, IDI_APPLICATION) ;
 27    wndclass.hCursor      = LoadCursor (NULL, IDC_ARROW) ;
 28    wndclass.hbrBackground= (HBRUSH) GetStockObject (BLACK_BRUSH) ;
 29    wndclass.lpszMenuName = NULL ;
 30    wndclass.lpszClassName= szAppName ;
 31    RegisterClass (&wndclass);        
 32    hwnd = CreateWindow( szAppName,      // window class name
 33                   TEXT ("draw lines"),   // window caption
 34                   WS_OVERLAPPEDWINDOW,  // window style
 35                   CW_USEDEFAULT,         // initial x position
 36                   CW_USEDEFAULT,         // initial y position
 37                   CW_USEDEFAULT,         // initial x size
 38                   CW_USEDEFAULT,         // initial y size
 39                   NULL,                 // parent window handle
 40                NULL,                     // window menu handle
 41                hInstance,                 // program instance handle
 42                NULL) ;                     // creation parameters
 43    ShowWindow (hwnd, iCmdShow) ;
 44    UpdateWindow (hwnd) ;
 45    while (GetMessage (&msg, NULL, 0, 0))
 46    {
 47          TranslateMessage (&msg) ;
 48          DispatchMessage (&msg) ;
 49    }
 50    return msg.wParam ;
 51}
 52LRESULT CALLBACK WndProc (HWND hwnd, UINT message, WPARAM wParam, LPARAM lParam)
 53{
 54    HDC            hdc ;
 55    HDC            hdcMem;                          //內存設備句柄
 56    PAINTSTRUCT     ps ;
 57    RECT          rect ;
 58    int                x,y;
 59    HBITMAP        hBitmap;
 60
 61    switch (message)
 62    {
 63    case   WM_CREATE:
 64            SetTimer (hwnd, ID_TIMER, 100, NULL) ; //創建定時器,每10微妙產生一個WM_TIMER消息
 65            return 0 ;
 66
 67     case WM_TIMER:
 68             GetClientRect (hwnd, &rect) ;
 69            if(rect.right <=0 || rect.bottom<=0) return 0; //窗口最小化后結束繪制
 70            hdc = GetDC (hwnd) ;
 71            hdcMem = CreateCompatibleDC(NULL);    //創建內存設備環境
 72            hBitmap = CreateCompatibleBitmap(hdc, 
 73                rect.right, rect.bottom);          //創建內存設備環境相關的位圖
 74            SelectObject(hdcMem, hBitmap);          //選擇位圖對象到內存設備環境
 75
 76            for(int i=0;i<100;i++)
 77            {
 78//                COLORREF crColor = RGB(rand()%256,rand()%256,rand()%256); //隨機產生點的顏色值
 79//                SetPixel (hdc, x, y, crColor) ;      //在顯示設備環境中繪制點
 80//                SetPixel (hdcMem, x, y, crColor) ;//在內存設備環境中繪制點
 81
 82                x = rand()%rect.right;              //隨機產生點的X坐標
 83                y = rand()%rect.bottom;              //隨機產生點的Y坐標
 84
 85                Bresenham(rect.right/2,rect.bottom/2,x,y,hdcMem);
 86            }
 87
 88            BitBlt(hdc,0, 0, rect.right, rect.bottom, hdcMem, 0, 0, SRCCOPY); //將內存設備環境中的數據傳到顯示設備環境顯示
 89            DeleteObject(hBitmap);                  //釋放位圖對象
 90            DeleteDC (hdcMem) ;                      //釋放內存設備環境
 91            ReleaseDC (hwnd, hdc) ;                  //釋放顯示設備環境
 92            return 0 ;
 93    case   WM_DESTROY:
 94            KillTimer (hwnd, ID_TIMER) ;          //銷毀定時器
 95            PostQuitMessage (0) ;
 96            return 0 ;
 97    }
 98  return DefWindowProc (hwnd, message, wParam, lParam) ;
 99}
100
101//交換兩個整形變量
102void SwapInt(int &nTempA, int &nTempB)   
103{   
104    int nTemp = nTempA;   
105    nTempA = nTempB;   
106    nTempB = nTemp;   
107}   
108BOOL  Bresenham(int nX1, int nY1, int nX2, int nY2, HDC    &DC)
109{    
110    int nDx = abs(nX2 - nX1);   
111    int nDy = abs(nY2 - nY1);   
112    bool bYDirection = false;   
113  
114    if (nDx < nDy)   
115    {   
116        // y direction is step direction     
117        SwapInt(nX1, nY1);   
118        SwapInt(nDx, nDy);   
119        SwapInt(nX2, nY2);     
120        bYDirection = true;   
121    }   
122  
123    // calculate the x, y increment   
124    int nIncreX = (nX2 - nX1) > 0  ? 1 : -1;   
125    int nIncreY = (nY2 - nY1) > 0  ? 1 : -1;   
126  
127    int nCurX = nX1;   
128    int nCurY = nY1;   
129    int nTwoDY = 2 * nDy;   
130    int nTwoDyDx = 2 * (nDy - nDx);   
131    int nIniD = 2 * nDy - nDx;   
132  
133    COLORREF crColor = RGB(rand()%256,rand()%256,rand()%256); //隨機產生點的顏色值
134
135    while (nCurX !=  nX2)  // nCurX == nX2 can not use in bitmap    
136    {   
137        if(nIniD < 0)   
138        {   
139            nIniD += nTwoDY;     
140            // y value keep current state   
141        }   
142        else  
143        {   
144            nCurY += nIncreY;   
145            nIniD += nTwoDyDx;   
146        }
147
148        if (bYDirection)   
149        {   
150            SetPixel(DC, nCurY, nCurX, crColor);            
151        }   
152        else  
153        {   
154            SetPixel(DC, nCurX, nCurY, crColor);            
155        }   
156        nCurX += nIncreX;   
157    }   
158    return TRUE;   
159}

分析：

1//交換兩個整形變量
2void SwapInt(int &nTempA, int &nTempB)   
3{   
4    int nTemp = nTempA;   
5    nTempA = nTempB;   
6    nTempB = nTemp;   
7}   

最典型的兩個數據交換的代碼，A，B通過臨時變量C交換數據值。能不能不用臨時變量C，就能交換兩個數據值的方法呢？答案是肯定的。看下面

1//交換兩個整形變量
2void SwapInt(int &nTempA, int &nTempB)   
3{   
4    If(nTempA  == nTempB) return;
5    nTempA = nTempA ^ nTempB;   
6    nTempB = nTempA ^ nTempB; 
7    nTempA = nTempA ^ nTempB;  
8}

接下來是Bresenham算法的具體實現：

BOOL  Bresenham(int nX1, int nY1, int nX2, int nY2, HDC   &DC)

nX1,nY2是起始點坐標,nX2,nY2是終點坐標,DC是繪制設備環境

{   

int nDx = abs(nX2 - nX1);  

計算△X,abs是取絕對值函數

int nDy = abs(nY2 - nY1);

計算△Y

bool bYDirection = false;

初始化步進方向為X

    if (nDx < nDy)  

{  

如果斜率大于1，設置Y為步進方向，并交換起始點和終點的X,Y值和△X,△Y值

        SwapInt(nX1, nY1);  

        SwapInt(nDx, nDy);  

        SwapInt(nX2, nY2);    

        bYDirection = true;  

    }  

    int nIncreX = (nX2 - nX1) > 0  ? 1 : -1;  

    int nIncreY = (nY2 - nY1) > 0  ? 1 : -1;  

       計算X和Y方向的增量

    int nCurX = nX1;  

int nCurY = nY1; 

設置起點值

    int nTwoDY = 2 * nDy;  

    int nTwoDyDx = 2 * (nDy - nDx);  

    int nIniD = 2 * nDy - nDx;  

    計算步進決策判別式初始值

         COLORREF crColor = RGB(rand()%256,rand()%256,rand()%256);

隨機產生點的顏色值

    while (nCurX !=  nX2)    

{  

開始循壞繪制象素

        if(nIniD < 0)  

        {  

判斷結果為負數

            nIniD += nTwoDY;

     Y值保持不變

        }  

        else 

        {  

      否則，判斷結果為正數

            nCurY += nIncreY;  

      Y值改變

            nIniD += nTwoDyDx;  

        }

        if (bYDirection)  

        {  

          如果Y是步進方向

            SetPixel(DC, nCurY, nCurX, crColor);

      交換X,Y位置繪制象素

        }  

        else 

        {

      否則,按正常繪制象素  

            SetPixel(DC, nCurX, nCurY, crColor);           

        }  

        nCurX += nIncreX;  

    }  

return TRUE;  

}