跟我一起學圖形編程
作者：姚明 聯系方式：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;
}
運行演示程序時候，注意仔細觀察斜率偏低或偏高時產生的鋸齒現象。
posted on 2011-01-25 21:02
姚明 閱讀(539)
評論(0) 編輯 收藏 引用 所屬分類:
原創教程