跟我一起學圖形編程
作者：姚明 聯系方式：alanvincentmail@gmail.com 2011年1月26日 17:42:15
點，線，面,我們這節課學學面的填充和生成。千萬不要忽略這節課的重要性，我們平時看到的3維圖形，一般是由三角網格構成，比如，一個人，一座山，一張桌子。網格被填充了顏色后，就是我們看到的栩栩如生的樣子。但是，它們不是被簡單的填充單一的顏色，被填充的顏色是經過紋理，光照，材質等運算后得到的結果，這是一個復雜的過程，專業術語稱其為象素著色。這些內容，以后的課程我們慢慢深入學習。在這里，我們只用隨機顏色的線條簡單的填充整個多邊形表面。
理論：
填充的算法大概分為兩種思路，第一種，掃描線法，想象一下，從一個封閉多邊形外面一點開始，畫一直線，與多邊形相交，通過檢測掃描線上每點的狀態，就能區分出，多邊形外部和內部的點。第二種，種子算法，先取多邊形內部任意一點做種子，由這個種子，向左右，上下擴散，最終填充整個多邊形內部。我認為，掃描線算法適用于，多邊形各頂點值已知，即邊界已知情況下的填充。種子算法適用于，邊界未知情況，例如，屏幕上有多個多邊形重疊區域的填充。詳細的算法細節請參考點擊下載的相關章節。下面給出掃描線算法的實現代碼。
內容：
1
//-----------------------------------------------------------------------------------------------
2// 功能: 填充多邊形
3//
4// 參數: lpPoints: 指向頂點坐標數組的指針，數組類型為POINT，多邊形由它們順次封閉連接得到
5// nCount: 頂點的個數
6// nColor: 填充的顏色 默認為黑色
7// DC: 設備句柄
8//
9// 返回: 無返回值
10//
11// 說明: 可以是邊相交的多邊形
12//
13// 創建(修改): 2011-1-13 16:31 姚明
14//-----------------------------------------------------------------------------------------------
15
void FillPolygon(LPPOINT lpPoints, int nCount, int nColor /**//*=0*/,HDC &DC)
16
{
17
// 邊結構數據類型
18 typedef struct Edge
19
{
20 int ymax; // 邊的最大y坐標
21 float x; // 與當前掃描線的交點x坐標
22 float dx; // 邊所在直線斜率的倒數
23 struct Edge *pNext; // 指向下一條邊
24
} Edge, *LPEdge;
25
26 int i = 0, j = 0, k = 0;
27 int y0 = 0, y1 = 0; // 掃描線的最大和最小y坐標
28 LPEdge pAET = NULL; // 活化邊表頭指針
29 LPEdge *pET = NULL; // 邊表頭指針
30
31 pAET = new Edge; // 初始化表頭指針，第一個元素不用
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 // 初始化邊表，第一個元素不用
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; // 組成邊的下一點
57 if (lpPoints[i].y != lpPoints[j].y)
58 // 如果該邊不是水平的則加入邊表
59 {
60 LPEdge peg; // 指向該邊的指針
61 LPEdge ppeg; // 指向邊指針的指針
62
63 // 構造邊
64 peg = new Edge;
65 k = (lpPoints[i].y > lpPoints[j].y) ? i : j;
66 peg->ymax = lpPoints[k].y; // 該邊最大y坐標
67 k = (k == j) ? i : j;
68 peg->x = (float)lpPoints[k].x; // 該邊與掃描線焦點x坐標
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 // 該邊斜率的倒數
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的節點從活邊表刪除并把每個節點的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; //把每個節點的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; //窗口最小化后結束繪制
4 hdc = GetDC (hwnd) ;
5 hdcMem = CreateCompatibleDC(NULL); //創建內存設備環境
6 hBitmap = CreateCompatibleBitmap(hdc,
7 rect.right, rect.bottom); //創建內存設備環境相關的位圖
8 SelectObject(hdcMem, hBitmap); //選擇位圖對象到內存設備環境
9
10 for(int i=0;i<12;i++) // 循環次數必須是偶數，否則最后一根線無法形成閉合區域
11 {
12// COLORREF crColor = RGB(rand()%256,rand()%256,rand()%256); //隨機產生點的顏色值
13// SetPixel (hdc, x, y, crColor) ; //在顯示設備環境中繪制點
14// SetPixel (hdcMem, x, y, crColor) ;//在內存設備環境中繪制點
15
16 static int xTemp = -1;
17 static int yTemp = -1;
18
19 x = rand()%rect.right; //隨機產生點的X坐標
20 y = rand()%rect.bottom; //隨機產生點的Y坐標
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]; //填充區域的3個頂點
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); //將內存設備環境中的數據傳到顯示設備環境顯示
48 DeleteObject(hBitmap); //釋放位圖對象
49 DeleteDC (hdcMem) ; //釋放內存設備環境
50 ReleaseDC (hwnd, hdc) ; //釋放顯示設備環境
51 return 0 ;
posted on 2011-01-26 17:34
姚明 閱讀(1790)
評論(0) 編輯 收藏 引用 所屬分類:
原創教程