静觅 崔庆才的个人站点 - Python爬虫教程

0%

OpenGL绘图实例二之直线和圆弧的绘制

作者 发表于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

综述

在上一篇文章我们介绍了利用类库来完成一个机器人绘制的过程，这里我们一起来看一下怎样直接利用直线和圆弧生成算法来进行图形的绘制。 P.S. 本篇文章针对《计算机图形学》张彩明 版来探讨学习。关于书中的详细算法不会再赘述。 P.P.S. 本篇文章算法扩展思路及代码实现为博主原创内容，如存在纰漏和错误，希望大家指正。

直线生成算法

1.DDA 算法

DDA 算法是最基本的一种直线生成算法了，代码实现简单，不过缺点是计算量比较大，画一个点要两次加法，两次取整运算。另外，DDA 算法还包括了除法运算。不仅算法复杂，而且硬件实现上有一定的难度。优点就是程序简单易懂，在这里实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
//画直线的DDA算法
void dda(int x1,int y1,int x2,int y2){
	int k,i;
	float x,y,dx,dy;
	//使k等于横纵坐标差值的较大者
	k = abs(x2-x1);
	if(abs(y2-y1)>k)
		k = abs(y2-y1);
	//直线被划分为每一小段的长度
	dx = float(x2-x1)/k;
	dy = float(y2-y1)/k;
	x = float(x1);
	y = float(y1);
	for(i = 0;i<k;i++){
		//此处先加0.5再取整的作用是四舍五入
		gl_Point((int)(x+0.5),(int)(y+0.5));
		//x和y分别增加相应的单位
		x = x+dx;
		y = y+dy;
	}
}

解释一下这里的 gl_Point 方法，这个方法并不是直接调用类库的方法，而是我们自己来实现的画点的方法。

1
2
3
4
5
6
 
//画点
void gl_Point(int x,int y){
	glBegin(GL_POINTS);
	glVertex2i(x,y);
	glEnd();
}

用来画点的话，我们必须要在 glBegin 方法传入 GL_POINTS 参数，然后利用类库中画点的方法来绘制点。

2.正负法

在教材中只讨论了斜率在 0-1 之间的情况，代码的实现也是仅仅只有 0-1 一种情况，对于斜率大于 1，斜率在-1 和 0 之间以及斜率小于-1 的情况没有加以讨论。 如果我们直接拿来教材中的代码来用，我们会发现只能绘制出 0-1 斜率的直线，对于其他的情况，均绘制错误。 所以我们需要分四种情况来讨论，直线方程 F(x,y)=ax+by+c=0，其中 a=ys-ye，b=xe-xs 设直线的斜率为 k，讨论分类如下 （1）k∈[0,1) 此时有 a<0，b>0 d=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c 当 d>=0 时，Q 在 M 点下方，取右下方的点，d1=F(x+2,y+0.5)=a(x+2)+b(y+0.5)+c=d+a 当 d<0 时，Q 在 M 点上方，取右上方的点，d2=F(x+2,y+1.5)=a(x+2)+b(y+1.5)+c=d+a+b 此时 d 的初始值 d0=F(xs+1,ys+0.5)=a+0.5b **（2）k∈[1,+∞]** 此时有 a<0，b>0 d=F(M)=F(x+0.5,y+1)=a(x+0.5)+b(y+1)+c 当 d>=0 时，Q 在 M 点右侧，取右上方的点，d1=F(x+1.5,y+2)=a(x+1.5)+b(y+2)+c=a+b+d 当 d<0 时，Q 在 M 点左侧，取左上方的点，d2=F(x+0.5,y+2)=b+d 此时 d 的初始值 d0=F(xs+0.5,ys+1)=0.5a+b **（3）k∈[-1,0)** 此时有 a>0，b>0 d=F(M)=F(x+1,y-0.5)=a(x+1)+b(y-0.5)+c 当 d>=0 时，Q 在 M 点下方，取右下方的点，d1=F(x+2,y-1.5)=a(x+2)+b(y-1.5)+c=a-b+d 当 d<0 时，Q 在 M 点上方，取右上方的点，d2=F(x+2,y-0.5)=a(x+2)+b(y-0.5)+c=a+d 此时 d 的初始值 d0=F(xs+1,ys-0.5)=a-0.5b **（4）k∈[-∞,-1)** 此时有 a>0，b>0 d=F(M)=F(x+0.5,y-1)=a(x+0.5)+b(y-1)+c 当 d>=0 时，Q 在 M 点左方，取左下方的点，d1=F(x+0.5,y-2)=a(x+0.5)+b(y-2)+c=d-b 当 d<0 时，Q 在 M 点右方，取右下方的点，d2=F(x+1.5,y-2)=a(x+1.5)+b(y-2)+c=a-b+d 此时 d 的初始值 d0=F(xs+0.5,ys-1)=0.5a-b 注意：上面的 a 和 b 的符号，是在默认起点在终点的左侧来看待的 所以，如果我们传入参数时，第二个点在第一个点的左侧时，我们可能就不会得到正确的结果。所以当我们发现第二个点不在第一个点右侧时，就需要把二者的横纵坐标交换。 代码实现如下，此实现仅供参考，未经优化。

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
 
//画直线的正负法
void midPointLine(int xs,int ys,int xe,int ye){
	if(xs>xe){
		swap(xs,xe);
		swap(ys,ye);
	}
	float a,b,dt1,dt2,d,x,y;
	a=ys-ye;
	b=xe-xs;
	float k =(float)(ye-ys)/(xe-xs);
	if(k>=0&&k<1){
		d=2*a+b;
		dt1=2*a;
		dt2=2*(a+b);
	}else if(k>=1){
		d=a+2*b;
		dt1=2*(a+b);
		dt2=2*b;
	}else if(k<0&&k>=-1){
		d=2*a-b;
		dt1=2*(a-b);
		dt2=2*a;
	}else if(k<-1){
		d=a-2*b;
		dt1=-2*b;
		dt2=2*(a-b);
	}
	x=xs;y=ys;
	gl_Point(x,y);
	if(k>=0&&k<1){
		while(x<xe){
			if(d<0){
				x++;y++;d+=dt2;
			}else{
				x++;d+=dt1;
			}
			gl_Point(x,y);
		}
	}else if(k>=1){
		while(y<ye){
			if(d<0){
				y++;d+=dt2;
			}else{
				y++;x++;d+=dt1;
			}
			gl_Point(x,y);
		}
	}else if(k<0&&k>=-1){
		while(x<xe){
			if(d<0){
				x++;d+=dt2;
			}else{
				x++;y--;d+=dt1;
			}
			gl_Point(x,y);
		}
	}else if(k<-1){
		while(y>ye){
			if(d<0){
				y--;x++;d+=dt2;
			}else{
				y--;d+=dt1;
			}
			gl_Point(x,y);
		}
	}
}

在一开始我们用到了 swap 方法，是用来交换两个数字的，实现如下

1
2
3
4
5
6
 
//交换两个数字
void swap(int &x1,int &x2){
	int temp = x2;
	x2=x1;
	x1=temp;
}

以上便是正负法的实现，代码仅供参考。

3.Bresenham 算法

在教材中，同样是只针对斜率在 0-1 之间讨论。对于教材中的程序，我们也只能绘制斜率为 0-1 的直线，所以我们需要对另外三种情况进行扩充。 分类讨论如下 （1）k∈[0,1) 即教材中的讲解方法 （2）k∈[1,+∞] 需要把 x 和 y 互换即可 （3）k∈[-1,0) x 不变，y 换为-y （4）k∈[-∞,-1) x 换为-y，y 换为 x 程序实现如下

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
 
//画直线的Bresenham方法
void bresen(int x1,int y1,int x2,int y2){
	if(x2<x1){
		swap(x1,x2);
		swap(y1,y2);
	}
	float dx=x2-x1;
	float dy=y2-y1;
	float k=dy/dx;
	float m,e;int i;
	float x=x1,y=y1;
	if(k>=0&&k<1){
		//斜率为0到1
		m=dy/dx;
		e=m-0.5;
		for(i=0;i<dx;i++){
			gl_Point(x,y);
			if(e>=0){
				y+=1;e-=1;
			}
			x+=1;e+=m;
		}
	}else if(k>=1){
		//x换为y,y换为x
		m=dx/dy;
		e=m-0.5;
		for(i=0;i<dy;i++){
			gl_Point(x,y);
			if(e>=0){
				x+=1;e-=1;
			}
			y+=1;e+=m;
		}
	}else if(k<0&&k>=-1){
		//x不变，y换为-y
		m=-dy/dx;
		e=m+0.5;
		for(i=0;i<dx;i++){
			gl_Point(x,y);
			if(e<=0){
				y-=1;e+=1;
			}
			x+=1;e-=m;
		}
	}else{
		//将x换为-y,y换为x
		m=-dx/dy;
		e=m+0.5;
		for(i=0;i<-dy;i++){
			gl_Point(x,y);
			if(e<=0){
				x+=1;e+=1;
			}
			y-=1;e-=m;
		}
	}
}

以上便是 Bresenham 算法，经测试通过。

圆弧生成算法

1.正负法

教材中只讨论了圆弧在第一象限的情况，不过有趣的是，圆是具有对称性的，在绘制圆形时，我们如果把 x 换为-x，就可以绘制第二象限的图形，把 y 换为-y，就可以绘制第四象限的图形，代码也不需要改动很多。只需要在 gl_Point 上面下功夫即可。 另外，教材中圆弧生成算法中没有指定圆的中心点的坐标，我们可以把它当做参数来传递进来，然后传入 gl_Point 绘图函数即可，相当方便。 注：此方法不需要再繁琐地分类讨论。 在这里给出博主写出的两种方法，一种是如上所介绍的思路，利用对称性，另一种是分类讨论的思想。 （1）利用对称性实现

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
 
//正负法画圆
void pnarcArc(int radius,int centerX,int centerY,int area){
	int x,y,f;
	x=0;y=0+radius;f=0;
	while(y>0){
		switch(area){
		case 1:
			gl_Point(x+centerX,y+centerY);
			break;
		case 2:
			gl_Point(-x+centerX,y+centerY);
			break;
		case 3:
			gl_Point(-x+centerX,-y+centerY);
			break;
		case 4:
			gl_Point(x+centerX,-y+centerY);
			break;
		}
		if(f>0){
			f=f-2*y+1;
			y=y-1;
		}else{
			f=f+2*x+1;
			x=x+1;
		}
	}
	if(y==centerY){
		gl_Point(x,y);
	}
}

（2）分类讨论思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
//正负法画圆3
void pnarcArc(int radius,int centerX,int centerY,int area){
	int x,y,f;
	int tag[4]={1,1,-1,-1};
	int tagX[4]={1,-1,-1,1};
	int tagY[4]={-1,-1,1,1};
	x=0;y=tag[area-1]*radius;f=0;
	while(tag[area-1]*y>0){
		gl_Point(x+centerX,y+centerY);
		if(f>0){
			f=f+tagY[area-1]*2*y+1;
			y=y+tagY[area-1];
		}else{
			f=f+tagX[area-1]*2*x+1;
			x=x+tagX[area-1];
		}
	}
	if(y==centerY){
		gl_Point(x,y);
	}
}

在上面的代码中，我们传入了 centerX 和 centerY 以及 area 参数。其中 centerX 和 centerY 是圆弧中心点的坐标，area 是所在的象限，传入的参数需要是 1,2,3,4 中的一个数字，如果传入其他数字则不会绘制出任何图形。 注：此方法只能一次性绘制一个四分之一圆弧，局限性比较大，如果要融入弧度，改动量比较大。

2.Bresenham 算法

和上面方法类似，我们的实现同样非常简单，即使教材中只讨论了八分之一圆，我们可以利用对称的思想来实现画圆。另外我们添加了圆弧中心点坐标已经所在的区块。 从（π/4,π/2）这个区块开始，编号为 1，角度为 45°，顺时针旋转（0,π/4）的编号为 2，以此类推，参数变量为 area 代码实现如下

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
 
//Bresenham画圆算法
void bresenhamArc(int R,int centerX,int centerY,int area){
	int x,y,d;
	x=0;y=R;d=3-2*R;
	while(x<y){
		switch(area){
		case 1:
			gl_Point(x+centerX,y+centerY);
			break;
		case 2:
			gl_Point(y+centerX,x+centerY);
			break;
		case 3:
			gl_Point(y+centerX,-x+centerY);
			break;
		case 4:
			gl_Point(x+centerX,-y+centerY);
			break;
		case 5:
			gl_Point(-x+centerX,-y+centerY);
			break;
		case 6:
			gl_Point(-y+centerX,-x+centerY);
			break;
		case 7:
			gl_Point(-y+centerX,x+centerY);
			break;
		case 8:
			gl_Point(-x+centerX,y+centerY);
			break;
		}
		if(d<0){
			d=d+4*x+6;
		}else{
			d=d+4*(x-y)+10;
			y=y-1;
		}
		x=x+1;
	}
	if(x==y){
		gl_Point(x,y);
	}
}

此段代码亲测可用，仅供参考。

终极目标

上一节我们实现了用类库的方法和 sin，cos 方法来定位坐标绘制机器人，在这一节我们就利用上述的直线和圆弧生成算法，对上一篇中的机器人进行绘制。 在这里只贴出最核心的部分，那就是绘画的函数了，只是简单地传入坐标点然后调用刚才实现的一些方法，比较繁琐，但是比较简单，核心代码如下

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
//myDisplay函数用来画图
void myDisplay(void){
	//清除。GL_COLOR_BUFFER_BIT表示清除颜色，glClear函数还可以清除其它的东西
	glClear(GL_COLOR_BUFFER_BIT);
	//设置黑色颜色
	glColor3f (0.0f, 0.0f, 0.0f);
	//中心的圆圈，四个象限，半径为10
	pnarcArc(10,0,0,1);
	pnarcArc(10,0,0,2);
	pnarcArc(10,0,0,3);
	pnarcArc(10,0,0,4);
	//肚子中三角形，利用了DDA绘制
	dda(-30,-15,30,-15);
	dda(-30,-15,0,28);
	dda(0,28,30,-15);
	//肚子，四条直线
	midPointLine(-60,60,60,60);
	midPointLine(-60,-60,60,-60);
	midPointLine(-74,46,-74,-46);
	midPointLine(74,46,74,-46);
	//肚子，四个半圆
	pnarcArc(14,60,46,1);
	pnarcArc(14,-60,46,2);
	pnarcArc(14,-60,-46,3);
	pnarcArc(14,60,-46,4);
	//脖子,两条直线
	bresen(-25,76,-25,60);
	bresen(26,76,25,60);
	//脸，四条直线
	midPointLine(-54,150,54,150);
	midPointLine(-54,76,54,76);
	midPointLine(-64,140,-64,86);
	midPointLine(64,140,64,86);
	//脸，四个圆弧
	pnarcArc(10,54,140,1);
	pnarcArc(10,-54,140,2);
	pnarcArc(10,-54,86,3);
	pnarcArc(10,54,86,4);
	//眼睛，两个正圆
	pnarcArc(10,-30,111,1);
	pnarcArc(10,-30,111,2);
	pnarcArc(10,-30,111,3);
	pnarcArc(10,-30,111,4);
	pnarcArc(10,30,111,1);
	pnarcArc(10,30,111,2);
	pnarcArc(10,30,111,3);
	pnarcArc(10,30,111,4);
	//嘴巴，两个八分之一圆
	bresenhamArc(20,0,111,4);
	bresenhamArc(20,0,111,5);
	//天线
	dda(-35,150,-35,173);
	dda(35,150,35,173);
	//右耳朵，四条直线
	bresen(88,98,88,131);
	bresen(67,98,67,131);
	bresen(70,95,85,95);
	bresen(70,134,85,134);
	//右耳朵，四个圆弧
	pnarcArc(3,85,131,1);
	pnarcArc(3,70,131,2);
	pnarcArc(3,70,98,3);
	pnarcArc(3,85,98,4);
	//左耳朵，四条直线
	bresen(-88,98,-88,131);
	bresen(-67,98,-67,131);
	bresen(-70,95,-85,95);
	bresen(-70,134,-85,134);
	//左耳朵，四个圆弧
	pnarcArc(3,-70,131,1);
	pnarcArc(3,-85,131,2);
	pnarcArc(3,-85,98,3);
	pnarcArc(3,-70,98,4);
	//左胳膊衔接处
	bresen(-73,25,-80,25);
	bresen(-73,43,-80,43);
	//右胳膊衔接处
	bresen(73,25,80,25);
	bresen(73,43,80,43);
	//左大臂
	dda(-108,45,-108,0);
	dda(-81,45,-81,0);
	dda(-108,45,-81,45);
	dda(-108,0,-81,0);
	//右大臂
	dda(108,45,108,0);
	dda(81,45,81,0);
	dda(108,45,81,45);
	dda(108,0,81,0);
	//左中臂
	bresen(-101,0,-101,-4);
	bresen(-88,0,-88,-4);
	//右中臂
	bresen(101,0,101,-4);
	bresen(88,0,88,-4);
	//左小臂
	dda(-108,-4,-108,-37);
	dda(-81,-4,-81,-37);
	dda(-108,-4,-81,-4);
	dda(-108,-37,-81,-37);
	//右小臂
	dda(108,-4,108,-37);
	dda(81,-4,81,-37);
	dda(108,-4,81,-4);
	dda(108,-37,81,-37);
	//左手
	pnarcArc(10,-95,-47,1);
	pnarcArc(10,-95,-47,2);
	pnarcArc(10,-95,-47,3);
	pnarcArc(10,-95,-47,4);
	//右手
	pnarcArc(10,95,-47,1);
	pnarcArc(10,95,-47,2);
	pnarcArc(10,95,-47,3);
	pnarcArc(10,95,-47,4);
	//左腿衔接处
	dda(-43,-62,-43,-69);
	dda(-25,-62,-25,-69);
	//右腿衔接处
	dda(43,-62,43,-69);
	dda(25,-62,25,-69);
	//左大腿，四条直线
	bresen(-47,-69,-21,-69);
	bresen(-47,-117,-21,-117);
	bresen(-51,-70,-51,-113);
	bresen(-17,-70,-17,-113);
	//左大腿，四条圆弧
	pnarcArc(4,-21,-73,1);
	pnarcArc(4,-47,-73,2);
	pnarcArc(4,-47,-113,3);
	pnarcArc(4,-21,-113,4);
	//右大腿，四条直线
	bresen(47,-69,21,-69);
	bresen(47,-117,21,-117);
	bresen(51,-70,51,-113);
	bresen(17,-70,17,-113);
	//右大腿，四条圆弧
	pnarcArc(4,47,-73,1);
	pnarcArc(4,21,-73,2);
	pnarcArc(4,21,-113,3);
	pnarcArc(4,47,-113,4);
	//左脚踝
	dda(-43,-118,-43,-125);
	dda(-25,-118,-25,-125);
	//右腿衔接处
	dda(43,-118,43,-125);
	dda(25,-118,25,-125);
	//左脚
	bresen(-59,-125,-8,-125);
	bresen(-59,-137,-8,-137);
	bresen(-59,-125,-59,-137);
	bresen(-8,-125,-8,-137);
	//右脚
	bresen(59,-125,8,-125);
	bresen(59,-137,8,-137);
	bresen(59,-125,59,-137);
	bresen(8,-125,8,-137);
	//刷新机器人
	glFlush();
}

其他的部分不再赘述，都十分基础。

运行结果

直接贴图如下 QQ截图20150413005949 嘿嘿，我们直接用生成算法绘制的图形是不是更好看一些呢？

总结

本节介绍了各种直线生成算法和圆弧生成算法，以及利用该算法重新绘制机器人，希望对大家有帮助！