计算机图形学05：中点BH算法对任意斜率的直线扫描转换方法

2023-03-14

算法计算机图形学

作者：非妃是公主专栏：《计算机图形学》博客地址：https://blog.csdn.net/myf_666个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩文章目录专栏推荐专栏系列文章序一、问题提出二、算法原理三、OpenGL代码实现四、效果展示theend……专栏推荐专栏名称专栏地址软件工

作者：非妃是公主
专栏：《计算机图形学》
博客地址：https://blog.csdn.net/myf_666
个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩

文章目录

专栏推荐
专栏系列文章
序
一、问题提出
二、算法原理
三、OpenGL代码实现
四、效果展示
the end……

专栏推荐

专栏名称	专栏地址
软件工程	专栏——软件工程
计算机图形学	专栏——计算机图形学
操作系统	专栏——操作系统
软件测试	专栏——软件测试
机器学习	专栏——机器学习
数据库	专栏——数据库
算法	专栏——算法

专栏系列文章

文章名称	文章地址
直线生成算法(DDA算法)	计算机图形学01——DDA算法
中点BH算法绘制直线	计算机图形学02——中点BH算法
改进的中点BH算法	计算机图形学03——改进的中点BH算法
中点Bresenham画椭圆	计算机图形学04——中点BH绘制椭圆
中点BH算法绘制任意斜率直线	计算机图形学05——中点BH算法绘制任意斜率的直线
中点Bresenham画圆	计算机图形学06——中点BH算法画圆
有效边表法的多边形扫描转换	计算机图形学07——有效边表法绘制填充多边形
中点BH算法绘制抛物线 $100x = y^2$	计算机图形学08——中点BH绘制抛物线
二维观察之点的裁剪	计算机图形学09——二维观察之点裁剪
二维观察之线的裁剪	计算机图形学10——二维观察之线裁剪
二维观察之多边形的裁剪	计算机图形学11——二维观察之多边形裁剪
二维图形的几何变换	计算机图形学12——二维图形几何变换
三维图形的几何变换	计算机图形学13——三维图形几何变换
三维图形的投影变换	计算机图形学14——三维图形投影变换

序

计算机图形学（英语：computer graphics，缩写为CG）是研究计算机在硬件和软件的帮助下创建计算机图形的科学学科，是计算机科学的一个分支领域，主要关注数字合成与操作视觉的图形内容。虽然这个词通常被认为是指三维图形，事实上同时包括了二维图形以及影像处理。

一、问题提出

前几篇文章中已经提到了中点BH算法绘制直线（计算机图形学02：中点BH算法绘制直线、计算机图形学03：改进的中点BH算法）。

但在这两篇文章种，都只讨论了斜率大于 0 小于 1 的情况（即： $0 <= k <= 1$ ）,如果要扩展到任意斜率怎么办呢？

其实也很简单秩序要将斜率分成 4 类，然后分情况讨论即可，具体的算法原理及推导如下。

二、算法原理

将斜率分为4种情况，分别为：

$0 <= k <= 1$
$k >= 1$
$- 1 <= k < 0$
$k < - 1$

然后针对每种情况进行求解，得到d、x和y的更新表达式，如下：

详细推导可见直线的中点Bresenham算法的实现

三、OpenGL代码实现

OpenGL实现如下：

// 中点Bresenham算法绘制直线段(k任意)
void  MidBhline2(int  x0, int  y0, int  x1, int  y1) {
int  dx, dy, d, UpIncre, DownIncre, x, y;
if (x0 > x1) {// x0为起始点，x1为终止点
x = x1; x1 = x0; x0 = x; y = y1; y1 = y0; y0 = y;
}
x = x0; y = y0; dx = x1 - x0; dy = y1 - y0; 
// 0 <= k <= 1
if (dy >= 0 && dy < dx) {
d = dx - 2 * dy;// d的初始值
UpIncre = 2 * dx - 2 * dy;// 2dx*(1 + k)
DownIncre = -2 * dy;// 2dx(-k)
glBegin(GL_POINTS);// 开始绘制点
while (x <= x1) {
glVertex2i(x, y);// 画点
x++;// 更新x
if (d < 0) {// 根据d的符号更新d和y
y++;
d += UpIncre;
}
else
d += DownIncre;
}
glEnd();// 结束绘制点
}
// k > 1
else if (dy >= 0 && dy > dx) {
d = - dy + 2 * dx;// d的初始值
UpIncre = 2 * dx;// 2dx*(1)
DownIncre = 2 * dx - 2 * dy;// 2dx*(1-k)
glBegin(GL_POINTS);// 开始绘制点
while (x <= x1) {
glVertex2i(x, y);// 画点
y++;// 更新y
if (d < 0) {// 根据d的符号更新d和x
d += UpIncre;
}
else {
x++;
d += DownIncre;
}

}
glEnd();
}

// -1 <= k < 0
else if (dy < 0 && dy >= -dx) {
d = -dx - 2 * dy;// d的初始值
UpIncre = -2 * dy;// 2dx*(1)
DownIncre = -2 * dx - 2 * dy;// 2dx*(1-k)
glBegin(GL_POINTS);// 开始绘制点
while (x <= x1) {
glVertex2i(x, y);// 画点
x++;// 更新y
if (d < 0) {// 根据d的符号更新d和x
d += UpIncre;
}
else {
y--;
d += DownIncre;
}

}
glEnd();
}
// k < -1
else if (dy < 0 && dy < -dx) {
d = -2 * dx - dy;// d的初始值
UpIncre = -2 * dx - 2 * dy;// 2dx*(1)
DownIncre = -2 * dx;// 2dx*(1-k)
glBegin(GL_POINTS);// 开始绘制点
while (x <= x1) {
glVertex2i(x, y);// 画点
y--;// 更新y
if (d < 0) {// 根据d的符号更新d和x
x++;
d += UpIncre;
}
else {
d += DownIncre;
}

}
glEnd();
}
}
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