Bresenham 直线算法

来自tinyrenderer的第一课，目标是能够画出网格

常见的画线算法除了Bresenham算法，还有数值微分法(每次运算都需要一个浮点乘法和舍入运算)和中点画线法

算法介绍

在屏幕上直线是由一个像素一个像素小块儿组成的因此没法像现实世界中在纸张上那样直接连线，只是由于像素小块在屏幕上足够多，而看起来像直线。Bresenham算法主要目的便是处理画线。

算法思路

这里先默认斜率在0-1之间，直线指向第一象限

  1. 假设斜率k在0-1之间
    1. 在x的变化上，每一次都是递增1
    2. y要么保持不变要么递增1
    3. 我们通过一个参数 d，d的范围也在0-1之间，通过这个参数来确定y的变化。
  2. d的初始值为0，每一次变化相应的增加直线的斜率值，即 d=d+k。
    1. 当d>1的时候就前去1，保证d始终在0-1之间变换。
    2. 若d>=0.5，那么与垂直网格的交点更加接近，则取当前像素右上方的像素(x+1, y+1)
    3. 若d<0.5，那么取(x+1, y)

误差项的优化

  1. 由于d在与0.5比较，因此假设 e = d-0.5，那么每次只需判定e>=0即可
  2. 但是上述的计算需要用到小数和除法的计算，为了方便硬件计算假设 e’=2*e*dx
  3. 最终化简得到误差项 p = 2dy-dx

扩展到所有情况

刚才只讨论了斜率在0-1，指向第一象限的情况，那么扩展到所有情况便有，斜率>1和在不同象限

  1. 对于斜率的变化，在同一象限中是关于y=x对称的，因此将代码中x和y对调位置，例如p=2dy-dx就变成p=2dx-dy
  2. 对于不同象限则调整符号，使其转移到第一象限进行计算。例如, 对于第二象限 dx < 0, dy > 0, 那么就取其关于y轴对称的点 (-x1, y1) (-x2, y2)应用Bresenham算法计算, 但是最后输出的点仍然是 (x1, y1) 而不是 (-x1, y1)

所有情况汇总：

若dx > 0, dy > 0, 0< m < 1:

xi = x1, yi = y1

第一项: pi = 2dy -dx

若pi < 0: pi = pi + 2dy, yi = yi

若pi > 0: pi = pi + 2dy - 2dx, yi = yi + 1

xi = xi + 1

输出: (xi, yi)

若dx > 0, dy > 0, m > 1:

xi = x1, yi = y1

第一项: pi = 2dx -dy

若pi < 0: pi = pi + 2dx, xi = xi

若pi > 0: pi = pi + 2dx - 2dy, xi = xi + 1

yi = yi + 1

输出: (xi, yi)

若dx > 0, dy < 0, 0< m < 1:

xi = x1, yi = -y1

第一项: pi = 2dy -dx

若pi < 0: pi = pi + 2dy, yi = yi

若pi > 0: pi = pi + 2dy - 2dx, yi = yi + 1

xi = xi + 1

输出: (xi, -yi)

若dx > 0, dy < 0, m > 1:

xi = x1, yi = -y1

第一项: pi = 2dx -dy

若pi < 0: pi = pi + 2dx, xi = xi

若pi > 0: pi = pi + 2dx - 2dy, xi = xi + 1

yi = yi + 1

输出: (xi, yi)

若dx < 0, dy > 0, 0< m < 1:

xi = -x1, yi = y1

第一项: pi = 2dy -dx

若pi < 0: pi = pi + 2dy, yi = yi

若pi > 0: pi = pi + 2dy - 2dx, yi = yi + 1

xi = xi + 1

输出: (-xi, yi)

若dx < 0, dy > 0, m > 1:

xi = -x1, yi = y1

第一项: pi = 2dx -dy

若pi < 0: pi = pi + 2dx, xi = xi

若pi > 0: pi = pi + 2dx - 2dy, xi = xi + 1

yi = yi + 1

输出: (-xi, yi)

若dx < 0, dy < 0, 0< m < 1:

xi = -x1, yi = -y1

第一项: pi = 2dy -dx

若pi < 0: pi = pi + 2dy, yi = yi

若pi > 0: pi = pi + 2dy - 2dx, yi = yi + 1

xi = xi + 1

输出: (-xi, -yi)

若dx < 0, dy < 0, m > 1:

xi = -x1, yi = -y1

第一项: pi = 2dx -dy

若pi < 0: pi = pi + 2dx, xi = xi

若pi > 0: pi = pi + 2dx - 2dy, xi = xi + 1

yi = yi + 1

输出: (-xi, -yi)

实现

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
void line(Vec2i p0, Vec2i p1, TGAImage& image, TGAColor color) {
	bool steep = false;
	// 判断斜率>1还是在0到1之间
	if (std::abs(p0.x - p1.x) < std::abs(p0.y - p1.y))
	{
		std::swap(p0.x, p0.y);
		std::swap(p1.x, p1.y);
		steep = true;
	}

	if (p0.x > p1.x)
	{
		std::swap(p0.x, p1.x);
		std::swap(p0.y, p1.y);
	}

	int dx = p1.x - p0.x;
	int dy = p1.y - p0.y;

	// 优化后的误差项
	// 将误差项变成e*2*dx
	float derror = std::abs(dy)*2;
	float error = 0;
	int y = p0.y;
	// 优化判断的计算
	if (steep)
	{
		for (int x = p0.x; x <= p1.x; x++)
		{
			// 斜率>1结果需交换x和y
			image.set(y, x, color);
			error += derror;
			if (error > dx)
			{
				// 根据上升还是下降对y进行取值
				y += (p1.y > p0.y ? 1 : -1);
				error -= dx * 2;
			}
		}
	}
	else
	{
		for (int x = p0.x; x <= p1.x; x++)
		{
			image.set(x, y, color);
			error += derror;
			if (error > dx)
			{
				y += (p1.y > p0.y ? 1 : -1);
				error -= dx*2;
			}
		}
	}
}