跟我一起学图形编程

                              作者：姚明           联系方式：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;  

}