跟我一起學(xué)圖形編程
作者：姚明 聯(lián)系方式：alanvincentmail@gmail.com 2011年1月26日 17:42:15
點(diǎn)，線，面,我們這節(jié)課學(xué)學(xué)面的填充和生成。千萬不要忽略這節(jié)課的重要性，我們平時(shí)看到的3維圖形，一般是由三角網(wǎng)格構(gòu)成，比如，一個(gè)人，一座山，一張桌子。網(wǎng)格被填充了顏色后，就是我們看到的栩栩如生的樣子。但是，它們不是被簡單的填充單一的顏色，被填充的顏色是經(jīng)過紋理，光照，材質(zhì)等運(yùn)算后得到的結(jié)果，這是一個(gè)復(fù)雜的過程，專業(yè)術(shù)語稱其為象素著色。這些內(nèi)容，以后的課程我們慢慢深入學(xué)習(xí)。在這里，我們只用隨機(jī)顏色的線條簡單的填充整個(gè)多邊形表面。
理論：
填充的算法大概分為兩種思路，第一種，掃描線法，想象一下，從一個(gè)封閉多邊形外面一點(diǎn)開始，畫一直線，與多邊形相交，通過檢測掃描線上每點(diǎn)的狀態(tài)，就能區(qū)分出，多邊形外部和內(nèi)部的點(diǎn)。第二種，種子算法，先取多邊形內(nèi)部任意一點(diǎn)做種子，由這個(gè)種子，向左右，上下擴(kuò)散，最終填充整個(gè)多邊形內(nèi)部。我認(rèn)為，掃描線算法適用于，多邊形各頂點(diǎn)值已知，即邊界已知情況下的填充。種子算法適用于，邊界未知情況，例如，屏幕上有多個(gè)多邊形重疊區(qū)域的填充。詳細(xì)的算法細(xì)節(jié)請(qǐng)參考點(diǎn)擊下載的相關(guān)章節(jié)。下面給出掃描線算法的實(shí)現(xiàn)代碼。
內(nèi)容：
1
//-----------------------------------------------------------------------------------------------
2// 功能: 填充多邊形
3//
4// 參數(shù): lpPoints: 指向頂點(diǎn)坐標(biāo)數(shù)組的指針，數(shù)組類型為POINT，多邊形由它們順次封閉連接得到
5// nCount: 頂點(diǎn)的個(gè)數(shù)
6// nColor: 填充的顏色 默認(rèn)為黑色
7// DC: 設(shè)備句柄
8//
9// 返回: 無返回值
10//
11// 說明: 可以是邊相交的多邊形
12//
13// 創(chuàng)建(修改): 2011-1-13 16:31 姚明
14//-----------------------------------------------------------------------------------------------
15
void FillPolygon(LPPOINT lpPoints, int nCount, int nColor /**//*=0*/,HDC &DC)
16
{
17
// 邊結(jié)構(gòu)數(shù)據(jù)類型
18 typedef struct Edge
19
{
20 int ymax; // 邊的最大y坐標(biāo)
21 float x; // 與當(dāng)前掃描線的交點(diǎn)x坐標(biāo)
22 float dx; // 邊所在直線斜率的倒數(shù)
23 struct Edge *pNext; // 指向下一條邊
24
} Edge, *LPEdge;
25
26 int i = 0, j = 0, k = 0;
27 int y0 = 0, y1 = 0; // 掃描線的最大和最小y坐標(biāo)
28 LPEdge pAET = NULL; // 活化邊表頭指針
29 LPEdge *pET = NULL; // 邊表頭指針
30
31 pAET = new Edge; // 初始化表頭指針，第一個(gè)元素不用
32 pAET->pNext = NULL;
33
34 // 獲取y方向掃描線邊界
35 y0 = y1 = lpPoints[0].y;
36 for (i = 1; i < nCount; i++)
37 {
38 if (lpPoints[i].y < y0)
39 y0 = lpPoints[i].y;
40 else if (lpPoints[i].y > y1)
41 y1 = lpPoints[i].y;
42 }
43 if (y0 >= y1)
44 return ;
45
46 // 初始化邊表，第一個(gè)元素不用
47 pET = new LPEdge[y1 - y0 + 1];
48 for (i = 0; i <= y1 - y0; i++)
49 {
50 pET[i] = new Edge;
51 pET[i]->pNext = NULL;
52 }
53
54 for (i = 0; i < nCount; i++)
55 {
56 j = (i + 1) % nCount; // 組成邊的下一點(diǎn)
57 if (lpPoints[i].y != lpPoints[j].y)
58 // 如果該邊不是水平的則加入邊表
59 {
60 LPEdge peg; // 指向該邊的指針
61 LPEdge ppeg; // 指向邊指針的指針
62
63 // 構(gòu)造邊
64 peg = new Edge;
65 k = (lpPoints[i].y > lpPoints[j].y) ? i : j;
66 peg->ymax = lpPoints[k].y; // 該邊最大y坐標(biāo)
67 k = (k == j) ? i : j;
68 peg->x = (float)lpPoints[k].x; // 該邊與掃描線焦點(diǎn)x坐標(biāo)
69 if (lpPoints[i].y != lpPoints[j].y)
70 peg->dx = (float)(lpPoints[i].x - lpPoints[j].x) / (lpPoints[i].y -
71 lpPoints[j].y);
72 // 該邊斜率的倒數(shù)
73 peg->pNext = NULL;
74
75 // 插入邊
76 ppeg = pET[lpPoints[k].y - y0];
77 while (ppeg->pNext)
78 ppeg = ppeg->pNext;
79 ppeg->pNext = peg;
80 } // end if
81 } // end for i
82
83 // 掃描
84 for (i = y0; i <= y1; i++)
85 {
86 LPEdge peg0 = pET[i - y0]->pNext;
87 LPEdge peg1 = pET[i - y0];
88 if (peg0)
89 // 有新邊加入
90 {
91 while (peg1->pNext)
92 peg1 = peg1->pNext;
93 peg1->pNext = pAET->pNext;
94 pAET->pNext = peg0;
95 }
96
97 // 按照x遞增排序pAET
98 peg0 = pAET;
99 while (peg0->pNext)
100 {
101 LPEdge pegmax = peg0;
102 LPEdge peg1 = peg0;
103 LPEdge pegi = NULL;
104
105 while (peg1->pNext)
106 {
107 if (peg1->pNext->x > pegmax->pNext->x)
108 pegmax = peg1;
109 peg1 = peg1->pNext;
110 }
111 pegi = pegmax->pNext;
112 pegmax->pNext = pegi->pNext;
113 pegi->pNext = pAET->pNext;
114 pAET->pNext = pegi;
115 if (peg0 == pAET)
116 peg0 = pegi;
117 }
118
119 // 遍歷活邊表，畫線
120 peg0 = pAET;
121 while (peg0->pNext)
122 {
123 if (peg0->pNext->pNext)
124 {
125 Bresenham((int)peg0->pNext->x, i, (int)peg0->pNext->pNext->x, i, DC);
126 peg0 = peg0->pNext->pNext;
127 }
128 else
129 break;
130 }
131
132 // 把ymax=i的節(jié)點(diǎn)從活邊表刪除并把每個(gè)節(jié)點(diǎn)的x值遞增dx
133 peg0 = pAET;
134 while (peg0->pNext)
135 {
136 if (peg0->pNext->ymax < i + 2)
137 {
138 peg1 = peg0->pNext;
139 peg0->pNext = peg0->pNext->pNext; //刪除
140 delete peg1;
141 continue;
142 }
143 peg0->pNext->x += peg0->pNext->dx; //把每個(gè)節(jié)點(diǎn)的x值遞增dx
144 peg0 = peg0->pNext;
145 }
146 }
147
148 // 刪除邊表
149 for (i = 0; i < y1 - y0; i++)
150 if (pET[i])
151 delete pET[i];
152
153 if (pAET)
154 delete pAET;
155 if (pET)
156 delete []pET;
157
}
分析：
以下是被修改后的WM_TIMER消息代碼
1 case WM_TIMER:
2 GetClientRect (hwnd, &rect) ;
3 if(rect.right <=0 || rect.bottom<=0) return 0; //窗口最小化后結(jié)束繪制
4 hdc = GetDC (hwnd) ;
5 hdcMem = CreateCompatibleDC(NULL); //創(chuàng)建內(nèi)存設(shè)備環(huán)境
6 hBitmap = CreateCompatibleBitmap(hdc,
7 rect.right, rect.bottom); //創(chuàng)建內(nèi)存設(shè)備環(huán)境相關(guān)的位圖
8 SelectObject(hdcMem, hBitmap); //選擇位圖對(duì)象到內(nèi)存設(shè)備環(huán)境
9
10 for(int i=0;i<12;i++) // 循環(huán)次數(shù)必須是偶數(shù)，否則最后一根線無法形成閉合區(qū)域
11 {
12// COLORREF crColor = RGB(rand()%256,rand()%256,rand()%256); //隨機(jī)產(chǎn)生點(diǎn)的顏色值
13// SetPixel (hdc, x, y, crColor) ; //在顯示設(shè)備環(huán)境中繪制點(diǎn)
14// SetPixel (hdcMem, x, y, crColor) ;//在內(nèi)存設(shè)備環(huán)境中繪制點(diǎn)
15
16 static int xTemp = -1;
17 static int yTemp = -1;
18
19 x = rand()%rect.right; //隨機(jī)產(chǎn)生點(diǎn)的X坐標(biāo)
20 y = rand()%rect.bottom; //隨機(jī)產(chǎn)生點(diǎn)的Y坐標(biāo)
21
22 Bresenham(rect.right/2,rect.bottom/2,x,y,hdcMem);
23
24 if(xTemp != -1 && yTemp != -1)
25 {
26 Bresenham(x,y,xTemp,yTemp,hdcMem);
27
28 POINT pts[3]; //填充區(qū)域的3個(gè)頂點(diǎn)
29 pts[0].x = rect.right/2;
30 pts[0].y = rect.bottom/2;
31 pts[1].x = x;
32 pts[1].y = y;
33 pts[2].x = xTemp;
34 pts[2].y = yTemp;
35 FillPolygon(pts , 3 , 0 ,hdcMem);
36
37 xTemp = -1;
38 yTemp = -1;
39
40 }else
41 {
42 xTemp = x;
43 yTemp = y;
44 }
45 }
46
47 BitBlt(hdc,0, 0, rect.right, rect.bottom, hdcMem, 0, 0, SRCCOPY); //將內(nèi)存設(shè)備環(huán)境中的數(shù)據(jù)傳到顯示設(shè)備環(huán)境顯示
48 DeleteObject(hBitmap); //釋放位圖對(duì)象
49 DeleteDC (hdcMem) ; //釋放內(nèi)存設(shè)備環(huán)境
50 ReleaseDC (hwnd, hdc) ; //釋放顯示設(shè)備環(huán)境
51 return 0 ;
posted on 2011-01-26 17:34
姚明 閱讀(1823)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
原創(chuàng)教程