基本变量定义
P1, P2 为要画线段的起终点，P1 = (x1, y1),P2 = (x2, y2)
∆x = x2-x1, ∆y = y2-y1,
m代表直线斜率0<m<1, m = ∆y/∆x
直线议程 y = mx+b
Bresenham 推导过程
假
设
当
前
已
经
画
到
点
P
c
(
x
k
,
y
k
)
,
则
下
一
个
点
只
有
2
种
可
能
(
x
k
+
1
,
y
k
)
或
(
x
k
+
1
,
y
k
+
1
)
y
是
直
线
上
x
k
+
1
所
对
应
实
际
的
坐
标
y
=
m
(
x
k
+
1
)
+
b
令
d
u
p
p
e
r
=
y
k
+
1
−
y
=
y
k
+
1
−
m
(
x
k
+
1
)
−
b
d
l
o
w
e
r
=
y
−
y
k
=
m
(
x
k
+
1
)
+
b
−
y
k
d
l
o
w
e
r
−
d
u
p
p
e
r
=
2
m
(
x
k
+
1
)
−
2
y
k
+
2
b
−
1
p
k
是
决
策
参
数
令
p
k
=
∆
x
(
d
l
o
w
e
r
−
d
u
p
p
e
r
)
,
由
于
m
=
∆
y
/
∆
x
,
代
入
式
子
p
k
=
2
∆
y
(
x
k
+
1
)
−
2
∆
x
∗
y
k
+
2
∆
x
∗
b
−
∆
x
=
2
∆
y
∗
x
k
−
2
∆
x
∗
y
k
+
2
∆
y
+
∆
x
(
2
b
−
1
)
当
p
k
<
0
时
，
说
明
y
k
离
y
更
近
，
就
取
y
k
;
否
则
，
y
k
+
1
离
y
更
近
，
取
y
k
+
1.
假设当前已经画到点 Pc(x_k, y_k), 则下一个点只有2种可能(x_k+1, y_k) 或(x_k+1, y_k+1)\\ y 是直线上x_k+1 所对应实际的坐标\\y=m (x_k+1)+b\\ 令d_{upper} = y_k+1 - y = y_k+1-m(x_k+1)-b\\d_{lower} = y-y_k = m (x_k+1)+b-y_k \\ d_{lower}-d_{upper} = 2m(x_k+1)-2y_k+2b-1\\ p_k是决策参数 \\ 令p_k = ∆x(d_{lower}-d_{upper}), 由于m = ∆y/∆x , 代入式子\\p_k = 2∆y(x_k+1)-2∆x*y_k+2∆x*b-∆x \\ = 2∆y*x_k-2∆x*y_k+2∆y+∆x(2b-1)\\当p_k<0时，说明y_k离y更近，就取y_k; 否则，y_k+1离y更近，取y_k+1.
假设当前已经画到点Pc(xk,yk),则下一个点只有2种可能(xk+1,yk)或(xk+1,yk+1)y是直线上xk+1所对应实际的坐标y=m(xk+1)+b令dupper=yk+1−y=yk+1−m(xk+1)−bdlower=y−yk=m(xk+1)+b−ykdlower−dupper=2m(xk+1)−2yk+2b−1pk是决策参数令pk=∆x(dlower−dupper),由于m=∆y/∆x,代入式子pk=2∆y(xk+1)−2∆x∗yk+2∆x∗b−∆x=2∆y∗xk−2∆x∗yk+2∆y+∆x(2b−1)当pk<0时，说明yk离y更近，就取yk;否则，yk+1离y更近，取yk+1.
到此为止我们已经得到下一个点的决策参数。只要依次计算就可以得到所线上的坐标。但是pk的计算中有很多乘法，比较耗时，我们可以通过步进法将其转化成加法来做。具体如下：
将
x
k
+
1
,
y
k
+
1
代
入
式
子
，
可
得
到
p
k
+
1
=
2
∆
y
(
x
k
+
1
)
−
2
∆
x
∗
y
k
+
1
+
2
∆
x
∗
b
−
∆
x
x
k
+
1
=
x
k
+
1
则
p
k
+
1
−
p
k
=
2
∆
y
−
2
∆
x
(
y
k
+
1
−
y
k
)
移
项
得
p
k
+
1
=
p
k
+
2
∆
y
−
2
∆
x
(
y
k
+
1
−
y
k
)
,
这
样
我
们
就
得
到
p
k
的
递
推
式
。
p
k
+
1
=
p
k
+
2
∆
y
+
{
−
2
∆
x
,
p
k
>
=
0
0
,
p
k
<
0
上
述
算
法
中
2
∆
x
,
2
∆
y
都
可
以
事
先
算
好
，
后
续
只
要
用
到
加
法
即
可
将x_{k+1}, y_{k+1}代入式子，可得到\\p_{k+1}=2∆y(x_{k+1})-2∆x*y_{k+1}+2∆x*b-∆x \\ x_{k+1}=x_k+1则p_{k+1}-p_k = 2∆y-2∆x(y_{k+1}-y_k) \\移项得 p_{k+1} =p_k+ 2∆y-2∆x(y_{k+1}-y_k), \\ 这样我们就得到p_k的递推式。\\ p_{k+1} =p_k+ 2∆y+\begin{cases} -2∆x, p_k>=0\\ 0, p_k<0\end{cases}\\上述算法中2∆x, 2∆y都可以事先算好，后续只要用到加法即可
将xk+1,yk+1代入式子，可得到pk+1=2∆y(xk+1)−2∆x∗yk+1+2∆x∗b−∆xxk+1=xk+1则pk+1−pk=2∆y−2∆x(yk+1−yk)移项得pk+1=pk+2∆y−2∆x(yk+1−yk),这样我们就得到pk的递推式。pk+1=pk+2∆y+{−2∆x,pk>=00,pk<0上述算法中2∆x,2∆y都可以事先算好，后续只要用到加法即可
p0计算
将
(
x
0
,
y
0
)
代
入
p
k
表
达
式
得
：
p
0
=
2
∆
y
∗
x
0
−
2
∆
x
∗
y
0
+
2
∆
y
+
∆
x
(
2
b
−
1
)
又
因
为
y
0
=
m
∗
x
0
+
b
=
∆
y
/
∆
x
∗
x
0
+
b
,
代
入
上
式
得
：
p
0
=
2
∆
y
∗
x
0
−
2
∆
x
∗
(
∆
y
/
∆
x
∗
x
0
+
b
)
+
2
∆
y
+
∆
x
(
2
b
−
1
)
=
2
∆
y
∗
x
0
−
2
∆
y
∗
x
0
−
2
∆
x
∗
b
+
2
∆
y
+
∆
x
(
2
b
−
1
)
=
2
∆
y
−
∆
x
将(x_0,y_0)代入p_k表达式得：\\ p_0 = 2∆y*x_0-2∆x*y_0+2∆y+∆x(2b-1) \\ 又因为 y_0 = m*x_0+b= ∆y/∆x*x_0+b, 代入上式得：\\ p_0 = 2∆y*x_0-2∆x*(∆y/∆x*x_0+b)+2∆y+∆x(2b-1) \\=2∆y*x_0-2∆y*x_0-2∆x*b+2∆y+∆x(2b-1)\\ = 2∆y-∆x
将(x0,y0)代入pk表达式得：p0=2∆y∗x0−2∆x∗y0+2∆y+∆x(2b−1)又因为y0=m∗x0+b=∆y/∆x∗x0+b,代入上式得：p0=2∆y∗x0−2∆x∗(∆y/∆x∗x0+b)+2∆y+∆x(2b−1)=2∆y∗x0−2∆y∗x0−2∆x∗b+2∆y+∆x(2b−1)=2∆y−∆x
上述只是讲了0<m<1的算法，对于-1<m<0可以直接对称过去。
对于|m|>1的情况可以把x,y 互换。
对于m=0, 无穷大的情况也适用。
代码实现
#include "glew/2.2.0_1/include/GL/glew.h"
#include "glfw/3.3.4/include/GLFW/glfw3.h"
#include <iostream>
using namespace std;
void key_callback(GLFWwindow* window, int key, int scancode, int action, int mode)
{
//如果按下ESC，把windowShouldClose设置为True，外面的循环会关闭应用
if(key==GLFW_KEY_ESCAPE && action == GLFW_PRESS)
glfwSetWindowShouldClose(window, GL_TRUE);
std::cout<<"ESC"<<mode;
}
class Point {
public:
int x, y;
Point(int xx, int yy):x(xx), y(yy){}
};
void setPixel(Point p) {
// cout<<p.x<<","<<p.y<<endl;
glBegin(GL_POINTS);
glVertex2i(p.x, p.y);
glEnd();
glFlush();
}
/*
* 简单Bresenham 算法
* 只处理|m|>1
*/
void LineBres_2(Point p1, Point p2) {
// 保持从下往上画
if(p2.y<p1.y) {
Point t = p2;
p2=p1;
p1=t;
}
int deltaX = abs(p2.x-p1.x), deltaY = abs(p2.y-p1.y);
int p0 = 2*deltaX-deltaY;
int twDeltaX = 2*deltaX, twDeltaXmTwoDeltaY = 2*deltaX-2*deltaY;
int step = 0;
if(deltaX>0) step = (p2.x-p1.x) / deltaX;
setPixel(p1);
for (; p1.y < p2.y;) {
p1.y++;
if(p0<0) {
p0+=twDeltaX;
} else {
p0+=twDeltaXmTwoDeltaY;
p1.x+=step;
}
setPixel(p1);
cout<<p1.x<<","<<p1.y<<endl;
}
}
/*
* 简单Bresenham 算法
* 只处理|m|<=1
*/
void LineBres_1(Point p1, Point p2) {
// 保持从左到右画
if(p2.x<p1.x) {
Point t = p2;
p2=p1;
p1=t;
}
int deltaX = abs(p2.x-p1.x), deltaY = abs(p2.y-p1.y);
if(deltaX<deltaY) {
LineBres_2(p1, p2);
return;
}
int p0 = 2*deltaY-deltaX;
int twDeltaY = 2*deltaY, twDeltaYmTwoDeltaX = 2*deltaY-2*deltaX;
int step = 0;
if(deltaY>0) step = (p2.y-p1.y) / deltaY;
setPixel(p1);
for (; p1.x < p2.x;) {
p1.x++;
if(p0<0) {
p0+=twDeltaY;
} else {
p0+=twDeltaYmTwoDeltaX;
p1.y+=step;
}
setPixel(p1);
cout<<p1.x<<","<<p1.y<<endl;
}
}
int main(void) {
//初始化GLFW库
if (!glfwInit())
return -1;
//创建窗口以及上下文
GLFWwindow *window = glfwCreateWindow(400, 400, "hello world", NULL, NULL);
if (!window) {
//创建失败会返回NULL
glfwTerminate();
}
//建立当前窗口的上下文
glfwMakeContextCurrent(window);
glfwSetKeyCallback(window, key_callback); //注册回调函数
//glViewport(0, 0, 400, 400);
gluOrtho2D(-200, 200.0, -200, 200.0);
//循环，直到用户关闭窗口
cout<<123<<endl;
while (!glfwWindowShouldClose(window)) {
/*******轮询事件*******/
glfwPollEvents();
// cout<<456<<endl;
//选择清空的颜色RGBA
glClearColor(0, 0, 0, 1);
glClear(GL_COLOR_BUFFER_BIT);
// glColor3f(0,0, 0);
glMatrixMode(GL_PROJECTION);
LineBres_1(Point(0,0),Point(100,70));
LineBres_1(Point(0,0),Point(100,-70));
LineBres_1(Point(0,0),Point(70,100));
LineBres_1(Point(0,0),Point(-70,100));
LineBres_1(Point(0,0),Point(-100,70));
LineBres_1(Point(0,0),Point(-70,-100));
LineBres_1(Point(0,0),Point(-100,-70));
LineBres_1(Point(0,0),Point(70,-100));
LineBres_1(Point(0,0),Point(0,100));
LineBres_1(Point(0,0),Point(0,-100));
LineBres_1(Point(0,0),Point(100,0));
LineBres_1(Point(0,0),Point(-100,0));
LineBres_1(Point(0,0),Point(0,0));
/******交换缓冲区，更新window上的内容******/
glfwSwapBuffers(window);
//break;
}
glfwTerminate();
return 0;
}
未完待续。。。。