跟我一起学图形编程
作者：姚明 联系方式：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
姚明 阅读(1730)
评论(0) 编辑 收藏 引用 所属分类:
原创教程