跟我一起學(xué)圖形編程
作者：姚明 聯(lián)系方式：alanvincentmail@gmail.com 2011年1月25日 21:16:15
從本課開始，我們才真正接觸到圖形學(xué)的相關(guān)算法，前面教程只是在搭建環(huán)境，從這節(jié)課開始，我們可以把精力集中在算法上，再不需要了解太多的系統(tǒng)函數(shù)。上節(jié)課，我們感受到了“點(diǎn)”的魅力，要知道，世界上所有的畫面都是由點(diǎn)組成的，包括我們上節(jié)課例子程序中隨機(jī)生成的圖像，從某種意義上說，那些圖像每時每刻都是一副獨(dú)一無二的畫，但是，為什么我們不覺得它是真正的畫呢？那是因為，它的每個像素都是隨機(jī)產(chǎn)生的，像素與像素之間沒有規(guī)律，沒有聯(lián)系，所以，我們也無法從中獲取信息，換句話說，那些都是不包含任何信息的畫面?，F(xiàn)在，我們試圖讓象素和象素之間產(chǎn)生關(guān)系，其中最常見的一種就是直線。有了它，我們就可以在畫面中表達(dá)信息了。
我不打算具體的描述算法細(xì)節(jié)，因為有很多書，都寫得很詳細(xì)，易懂，甚至配有動畫效果，例如：點(diǎn)擊下載。每個人的時間和精力有限，不能把寶貴的時間用在重復(fù)的發(fā)明輪子上，另外，把飯端到嘴邊，再用勺子喂飯的事情，那是一種失敗。我更愿意充當(dāng)一名向?qū)У慕巧敢蠹胰绾螌W(xué)？怎么學(xué)？學(xué)什么？同時激起大家的興趣和想象力，跟著我共同提高。
理論：
數(shù)學(xué)告訴我們連續(xù)和離散的概念，在計算機(jī)中，我們接觸到的往往是離散的事物，例如，我們現(xiàn)在看到的顯示屏，就是由離散的象素點(diǎn)，排列組成的。每個像素都用X和Y兩個整數(shù)表達(dá)位置。現(xiàn)在問題出現(xiàn)了，我們畫的線是個連續(xù)量，所以，有的象素X和Y的位置不一定是整數(shù)，有可能產(chǎn)生小數(shù)，出現(xiàn)小數(shù)時，我們必須取整才能和屏幕上的象素對應(yīng)，這個過程就有精度的缺失，所以我們屏幕上得到的結(jié)果是離散后的近似值。DDA算法是用微分方程得到斜率k,注意k是小數(shù)而且用除法算出來的，所以，計算機(jī)中運(yùn)算效率不高。要知道，直線是組成任何畫面的基礎(chǔ)元素，在直線算法中，效率提高1分，有可能讓整個場景效率提高100分，因此，DDA很快就被其它算法取代，其中Bresenham算法比較優(yōu)秀，它用一個判別式做決策，決定下一點(diǎn)的位置，判別式中沒有小數(shù)運(yùn)算，雖然，有乘2運(yùn)算，但乘2可以用移位運(yùn)算代替，所以效率極高。
內(nèi)容：
1
/**//*------------------------------------------------------------------------
2
LINES.CPP – 在窗口客戶區(qū)繪制直線的動畫效果
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; //內(nèi)存設(shè)備句柄
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) ; //創(chuàng)建定時器,每10微妙產(chǎn)生一個WM_TIMER消息
65 return 0 ;
66
67 case WM_TIMER:
68 GetClientRect (hwnd, &rect) ;
69 if(rect.right <=0 || rect.bottom<=0) return 0; //窗口最小化后結(jié)束繪制
70 hdc = GetDC (hwnd) ;
71 hdcMem = CreateCompatibleDC(NULL); //創(chuàng)建內(nèi)存設(shè)備環(huán)境
72 hBitmap = CreateCompatibleBitmap(hdc,
73 rect.right, rect.bottom); //創(chuàng)建內(nèi)存設(shè)備環(huán)境相關(guān)的位圖
74 SelectObject(hdcMem, hBitmap); //選擇位圖對象到內(nèi)存設(shè)備環(huán)境
75
76 for(int i=0;i<100;i++)
77 {
78// COLORREF crColor = RGB(rand()%256,rand()%256,rand()%256); //隨機(jī)產(chǎn)生點(diǎn)的顏色值
79// SetPixel (hdc, x, y, crColor) ; //在顯示設(shè)備環(huán)境中繪制點(diǎn)
80// SetPixel (hdcMem, x, y, crColor) ;//在內(nèi)存設(shè)備環(huán)境中繪制點(diǎn)
81
82 x = rand()%rect.right; //隨機(jī)產(chǎn)生點(diǎn)的X坐標(biāo)
83 y = rand()%rect.bottom; //隨機(jī)產(chǎn)生點(diǎn)的Y坐標(biāo)
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); //將內(nèi)存設(shè)備環(huán)境中的數(shù)據(jù)傳到顯示設(shè)備環(huán)境顯示
89 DeleteObject(hBitmap); //釋放位圖對象
90 DeleteDC (hdcMem) ; //釋放內(nèi)存設(shè)備環(huán)境
91 ReleaseDC (hwnd, hdc) ; //釋放顯示設(shè)備環(huán)境
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); //隨機(jī)產(chǎn)生點(diǎn)的顏色值
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}
最典型的兩個數(shù)據(jù)交換的代碼，A，B通過臨時變量C交換數(shù)據(jù)值。能不能不用臨時變量C，就能交換兩個數(shù)據(jù)值的方法呢？答案是肯定的?？聪旅?span lang=EN-US>
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算法的具體實(shí)現(xiàn)：
BOOL Bresenham(int nX1, int nY1, int nX2, int nY2, HDC &DC)
nX1,nY2是起始點(diǎn)坐標(biāo),nX2,nY2是終點(diǎn)坐標(biāo),DC是繪制設(shè)備環(huán)境
{
int nDx = abs(nX2 - nX1);
計算△X,abs是取絕對值函數(shù)
int nDy = abs(nY2 - nY1);
計算△Y
bool bYDirection = false;
初始化步進(jìn)方向為X
if (nDx < nDy)
{
如果斜率大于1，設(shè)置Y為步進(jìn)方向，并交換起始點(diǎn)和終點(diǎn)的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;
設(shè)置起點(diǎn)值
int nTwoDY = 2 * nDy;
int nTwoDyDx = 2 * (nDy - nDx);
int nIniD = 2 * nDy - nDx;
計算步進(jìn)決策判別式初始值
COLORREF crColor = RGB(rand()%256,rand()%256,rand()%256);
隨機(jī)產(chǎn)生點(diǎn)的顏色值
while (nCurX != nX2)
{
開始循壞繪制象素
if(nIniD < 0)
{
判斷結(jié)果為負(fù)數(shù)
nIniD += nTwoDY;
Y值保持不變
}
else
{
否則，判斷結(jié)果為正數(shù)
nCurY += nIncreY;
Y值改變
nIniD += nTwoDyDx;
}
if (bYDirection)
{
如果Y是步進(jìn)方向
SetPixel(DC, nCurY, nCurX, crColor);
交換X,Y位置繪制象素
}
else
{
否則,按正常繪制象素
SetPixel(DC, nCurX, nCurY, crColor);
}
nCurX += nIncreX;
}
return TRUE;
}
運(yùn)行演示程序時候，注意仔細(xì)觀察斜率偏低或偏高時產(chǎn)生的鋸齒現(xiàn)象。
posted on 2011-01-25 21:02
姚明 閱讀(548)
評論(0) 編輯 收藏 引用 所屬分類:
原創(chuàng)教程