0%

OpenGL绘图实例三之种子填充算法

综述

博主研究了一下午加一晚上,终于把种子填充算法实现出来并把机器人填充完毕,路途很艰辛,不过也学到了很多,在此和大家一起分享。

吐槽

与我不是同学的小伙伴,请自动忽略,我是来吐槽教材的。 在此不得不吐槽一下,不得不说教材实在太坑爹了。对于种子填充算法的后半部分,下一个种子点的寻找过程中,从 while(x<=xright)开始,我实在无法搞懂它里面的神逻辑,最初我认为它是对的,后来按照它的思路实现之后,填充基本上是错误的,比如圆角矩形下方的部分,它就无法正常填充。根本原因还是它的下一步种子点找错了,而博主依然在固执地 DeBug,看看是不是我哪里编码有问题。后来,干脆放弃了书上的逻辑了,自己改写了搜寻下一个种子点的算法,最后终于成功。 另外,教材上的这些伪代码写得也是太伪,算了,这不是重点,言归正传。

基本梳理

在博主的研究过程中,遇到了许许多多的小问题,在这里统一做一下总结,也希望大家少走弯路,吸取我的经验教训。

1.点的定义

在这里我们避免不了要使用点,一个点包括了 2 个元素,一个是横坐标一个是纵坐标,所以我们可以直接把它定义为一个结构体。

1
2
3
4
5
struct Point
{
int x;
int y;
};

这样的话,我们就可以直接声明一个 Point 类型的变量使用了,既方便又直观。

2.栈的使用

对于种子填充算法,肯定避免不了使用栈的,在这里博主分享一下一些使用心得。 栈的引入 C++代码中,可以直接用下面的代码来导入

1
2
#include <stack>
using namespace std;

注意,这里一定记得加上 using namespace std 这句话,否则会出现 stack 未定义的错误,哈哈哈,深有体会。 栈的定义 引入了栈之后,我们就可以直接来声明一个栈了

1
stack<Point> pixelStack;

其中,需要加一个尖括号,尖括号中声明了 Point 类型,这样我们就可以使用它了 取栈顶元素 C++中取栈顶元素是很坑的,有一个 top 方法,还有一个 pop 方法。 其中 top 方法是只取得栈顶的元素而不移除它,pop 方法是直接移除栈顶元素,没有返回值。 所以我们要想取出栈顶元素并移除的话,就要分别调用这两个方法

1
2
3
4
//获取最顶端的元素
Point tempPoint=pixelStack.top();
//删除最顶端的元素
pixelStack.pop();

是不是不友好?不友好的话,那就自己去定义一个新方法吧,我就先不这么干啦。 判断栈非空 判断当前的栈是否已经为空,只需要调用 empty 方法就可以了

1
2
3
while(!pixelStack.empty()){
//code
}

这里是一个 while 循环,如果栈为非空的话不断循环。 关于栈置空 教材中的种子填充算法中用到了栈置空,不过我感觉没有必要这么做,因为在方法最前面是新声明的栈变量,它一定是空的。不过如果非要置空的话,可以利用下面的代码

1
2
3
while(!pixelStack.empty()){
pixelStack.pop();
}

如果栈不为空,就一直取元素,就可以把它置空啦。

3.关于 glColor3b 和 glColor3ub

这的确也是坑得博主不浅,之前一直在用 glColor3b 这个方法来定义颜色,奇怪的是 glColor3b(255,0,0) 竟然不是红色,而是黑色!就是因为这个颜色问题,导致我在比对颜色的过程中走了很多弯路。在这里做一下说明 glColor3b()需要传入的是 byte 类型,它的数值范围是-128-127,也就是有符号数,我传入 255,由于越界了,255 这个数就相当于-128,难怪不变红啊。 glColor3ub()需要传入的是 unsigned byte 类型,范围是 0-255,无符号数,那么在这里我们传入 255,0,0 这三个数,就变成红色了。

4.取得某像素颜色

我想说的是,这也是个深坑啊,一下午的 Debug 全归它身上了。 获取某个像素的这个函数是

1
void glReadPixels(GLint x,GLint y,GLsizesi width,GLsizei height,GLenum format,GLenum type,GLvoid *pixel);

函数说明如下:

该函数总共有七个参数。前四个参数可以得到一个矩形,该矩形所包括的像素都会被读取出来。(第一、二个参数表示了矩形的左下角横、纵坐标,坐标以窗口最左下角为零,最右上角为最大值;第三、四个参数表示了矩形的宽度和高度) 第五个参数表示读取的内容,例如:GL_RGB 就会依次读取像素的红、绿、蓝三种数据,GL_RGBA 则会依次读取像素的红、绿、蓝、alpha 四种数据,GL_RED 则只读取像素的红色数据(类似的还有 GL_GREEN,GL_BLUE,以及 GL_ALPHA)。如果采用的不是 RGBA 颜色模式,而是采用颜色索引模式,则也可以使用 GL_COLOR_INDEX 来读取像素的颜色索引。目前仅需要知道这些,但实际上还可以读取其它内容,例如深度缓冲区的深度数据等。 第六个参数表示读取的内容保存到内存时所使用的格式,例如:GL_UNSIGNED_BYTE 会把各种数据保存为 GLubyte,GL_FLOAT 会把各种数据保存为 GLfloat 等。 第七个参数表示一个指针,像素数据被读取后,将被保存到这个指针所表示的地址。注意,需要保证该地址有足够的可以使用的空间,以容纳读取的像素数据。例如一幅大小为 256*256 的图象,如果读取其 RGB 数据,且每一数据被保存为 GLubyte。

好了,那么重点来了,这个方法的坐标基准点是在画布的左下角!!而我们绘图的基准点是在画布的正中心!!所以我在获取某个点的颜色的时候一直都是错误的结果,这样的话在使用的时候我们的 xy 坐标值就要加上画布宽高的一半才能正常获取到像素的颜色,希望大家一定注意!! 那么我们如何来使用呢?实例如下,首先定义 GLByte 的数组

1
GLubyte iPixel[3];

另外还有画布的宽度高度的一半变量

1
int halfWidth,halfHeight;

我们可以调用如下的方法来获取(x,y)这个点像素的值

1
glReadPixels(x+halfWidth,y+halfHeight,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);

在这里第五个参数我们定义了 GL_RGB,第六个参数我们定义了 GL_UNSIGNED_BYTE,最后是传入了数组的引用。 所以在调用这个方法之后,iPixel 数组里面的三个值就已经赋值为了该点的 RGB 值,可以拿来做下一步的判断。 比如我们边界可以定义为

1
GLubyte oldColor[3]={255,255,255};

在比较的时候就可以用下面的判别式

1
iPixel[0]!=borderColor[0]&&iPixel[1]!=borderColor[1]&&iPixel[2]!=borderColor[2]

这里我们是依次比较了三个 RGB 值是否与边界的 RGB 值相等,不过,有意思的是,识别颜色的这个方法,黑色的 RGB 值会识别成 1,1,1,而有时候在我调试的时候会识别为 0,1,1。我在想是不是系统计算误差问题,如果真是的话,因为这个小小的误差就影响了我们的判别条件岂不是亏大了?那么在这里我就定义了一个方法,允许一定的误差,这个误差姑且就称为 PS 里面的容差吧。

1
2
3
4
5
6
7
8
9
10
//传入两个颜色的RGB值,比较是否相同,容差为dis
bool sameColor(int r1,int g1,int b1,int r2,int g2,int b2){
//容差度
int dis = 10;
if(abs(r1-r2)<=dis&&abs(g1-g2)<=dis&&abs(b1-b2)<=dis){
return true;
}else{
return false;
}
}

那么我们的判定条件就改为了

1
!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])

这样系统误差便不会影响了。

5.下一个种子点的选取

教材上的种子点选取算法有点搞不懂,我按照上面的思路实现出来,在填充的时候出现了一系列问题。后来干脆放弃了教材中的方法,自己改写了一下。 思路大体上是这样的。

在填充完一行后,这一行最左边的像素点我们定义为(xLeft,y),最右边的像素我们定义为(xRight,y),扫描上一行找寻下一个种子点,这里 y 就要增加 1,如果(xRight,y+1)这个点不是边界不是已经填充的点,那么这个点就可以作为种子点压入堆栈。如果这个点是边界或者是已经填充的点,那么就继续往左搜索,如果找到既不是边界又未填充的点,那么这个点就是种子点,压入堆栈。如果一直往左找到 xLeft 还是没有找到的话,就不存在下一个种子点了。下一行扫描线也是同样的原理,y 要在这个基础上减去 2 即可。

恩,不知道大家有没有看懂,这是我自己想出来的方法,不敢保证完全正确,在此仅供参考。 如果大家真的可以按照教材中的方法实现成功的话,希望告诉我一下,感激不尽。

方法实现

恩,重要的地方都已经点明了,下面就直接附上我的种子填充算法吧!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//种子填充算法
void zzFill(int startX,int startY,int r,int g,int b){
stack<Point> pixelStack;
//x,y是给定的种子像素点,rgb就是要填充的颜色的RGB值
Point point = {startX,startY};
pixelStack.push(point);
int saveX;
int xRight,xLeft;
int x,y;
//如果栈不为空
while(!pixelStack.empty()){
//获取最顶端的元素
Point tempPoint=pixelStack.top();
//删除最顶端的元素
pixelStack.pop();
saveX=tempPoint.x;
x=tempPoint.x;
y=tempPoint.y;
glReadPixels(x+halfWidth,y+halfHeight,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
//如果没有到达右边界,就填充
while(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])){
glPoint(x,y,r,g,b);
x=x+1;
glReadPixels(x+halfWidth,y+halfHeight,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
}
xRight=x-1;
x=saveX-1;
glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
//如果没有到达左边界,就填充
while(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])){
glPoint(x,y,r,g,b);
x=x-1;
glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
}
//保存左端点
xLeft=x+1;
//从右边的点开始
x=xRight;
//检查上端的扫描线
y=y+1;
while(x>=xLeft){
glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
if(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])&&!sameColor(iPixel[0],iPixel[1],iPixel[2],r,g,b)){
//如果上方的点不是边界点,直接压入
Point p={x,y};
pixelStack.push(p);
//压入之后停止循环
break;
}else{
x--;
glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
}
}
//检查下端的扫描线
y=y-2;
//从右边的点开始
x=xRight;
while(x>=xLeft){
glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
if(!sameColor(iPixel[0],iPixel[1],iPixel[2],borderColor[0],borderColor[1],borderColor[2])&&!sameColor(iPixel[0],iPixel[1],iPixel[2],r,g,b)){
//如果上方的点不是边界点,直接压入
Point p={x,y};
//压入之后停止循环
pixelStack.push(p);
break;
}else{
x--;
glReadPixels(x+halfWidth,y+halfWidth,1,1,GL_RGB,GL_UNSIGNED_BYTE,&iPixel);
}
}
}
}

以上便是我实现的种子填充算法,仅供参考 在这里我们用到了 glPoint 画点的方法,这是我们定义的,方法如下,为了便于调试,每画一个点刷新一下,这样我们就可以看到绘制的全部动态效果。

1
2
3
4
5
6
7
8
9
//画点
void glPoint(int x,int y,int r,int g,int b){
glColor3ub (r,g,b);
glPointSize(1);
glBegin(GL_POINTS);
glVertex2i(x,y);
glEnd();
glFlush();
}

以上便是画点的函数

方法使用

种子填充算法肯定要在我们绘制完机器人之后使用,任意选取某个四连通区域的点,传入 xy 坐标值还有要填充的颜色的 RGB 值,就可以成功实现填充。 在上一篇机器人的基础上,我们在画机器人的方法最后加入下面的代码,即可实现填充。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//灰色:195,195,195
//黄色:255,243,0
//红色:237,28,36
//深灰色:126,126,126
//脖子
zzFill(0,70,195,195,195);
//头
zzFill(-50,110,195,195,195);
zzFill(0,93,195,195,195);
//肚子
zzFill(-50,0,195,195,195);
//耳朵
zzFill(-80,115,126,126,126);
zzFill(80,115,126,126,126);
//肚子三角
zzFill(-20,-10,255,243,0);
//肚子红色圆
zzFill(0,0,237,28,36);
//zzFill(-50,0,128,255,33);
//大臂
zzFill(-90,30,126,126,126);
zzFill(90,30,126,126,126);
//小臂
zzFill(-90,-20,126,126,126);
zzFill(90,-20,126,126,126);
//手
zzFill(-75,40,195,195,195);
zzFill(75,40,195,195,195);
//手
zzFill(-95,-47,195,195,195);
zzFill(95,-47,195,195,195);
//大腿连接处
zzFill(-40,-64,195,195,195);
zzFill(40,-64,195,195,195);
//大腿
zzFill(-40,-100,126,126,126);
zzFill(40,-100,126,126,126);
//脚踝
zzFill(-40,-121,195,195,195);
zzFill(40,-121,195,195,195);
//脚掌
zzFill(-40,-130,126,126,126);
zzFill(40,-130,126,126,126);
system("pause");

注意,有个很奇怪地方是绘制完了之后机器人就不见了,所以在这里加入了 system(“pause”)方法来暂停一下就好啦。 其他的代码基本都是上一篇中的了,大家自行整理。

运行结果

运行结果截图如下 20150419015002 恩,就是这样!

总结

以上便是博主利用种子填充算法来实现的机器人的颜色填充,在此分享给大家,希望对大家有帮助! 如有问题和错误,欢迎大家给予我批评和指正,谢谢!