Brensenham直线算法？

概述

给两个点，画出两点之间的直线。在电脑屏幕上，一个个排列整齐的像素点，怎么确定由哪些像素点来组成直线？已知起点(xs,ys)和终点(xe,ye),当然，这些点是指像素块中心的那个点；现在怎么搞？不积硅步，无以至千里；怎么迈出第一步？怎么得到（x0,y0）的下一个像素位置？先讨论最简单的情况：终点在起点的右上方；那么起点就需要向右选择下一个像素点；现在起点的像素点右边就有两个选项，向右还是向右上方的像素；不妨将这几个像素（包括像素中心的点）和起止点之间的直线在纸上先画出来，再套上一个笛卡尔坐标系，使用数学工具来瞧瞧这个问题；

图-1

算法思路

看到上图，Brensenham提出，我们现在就可以将d0和d1做差，用结果来判断应该取上面的像素还是下面的，取距离那条我们抽象的数学直线近的像素作为直线部分，这样的视觉效果好。

计算

由于知道起止点坐标，所以我们可以得到确定直线的斜率值 k=Δy/Δx；那条我们抽象的数学直线就可以表示为 y = kx + b; (b未知) 结合上图，我们假设点(xi,yi)是确定的; 那么数学直线过xi+1的y值就可以表示为 k(xi+1)+b ; 这就是上面的d0=yi+1-k(xi+1)-b; d1=k(xi+1)+b-yi 的由来; 好了，前提都已就绪，下面开始计算d1-d0的差值: d1-d0 = k(xi+1)+b-yi - yi+1-k(xi+1)-b; 简化一下就可以得到d1-d0=2k(xi+1)-2yi+2b-1; 现在还存在一个k=Δy/Δx,为了可以用整数表示，我们在等式两边乘以Δx，于是得到：Δx(d1-d0)=2Δy·xi+2Δx·yi+(2Δy+2Δx·b-Δx); Brensenham突然从床上蹦起，说：我们现在就可以用这个来判断”下一个”像素的纵向取y+1还是继续使用y。但是数学很差的我反驳到，里面不是还有个b是未知的吗？你怎么确定？ Brensenham微微一笑，说：现在我赐予你一个点 (x1,y1),你自己代入看看；我不信邪的将点代入得到： 2Δy·x1-2Δx·y1+(2Δy+2Δx·b-Δx); 哦，我再将y1用Δy/Δx · x1 + b表示，于是又得到： 2Δy·x1-2Δx·(Δy/Δx · x1 + b)+(2Δy+2Δx·b-Δx);简化一下得到： 2Δy-Δx 哇!!!!!!!!!! 所以说，第一个点只要代入，它下一个像素点该怎么取的这个判断条件都可以用2Δy-Δx来表示，当这个值>0，也就是d1>d0，也就是上边的像素距离理想的直线近，于是就用y+1的这个像素来组成直线的一部分。原来如此，Brensenham大师真是handsome啊。但是，但是，那下下一个点又怎么判断呢？还是用2Δy-Δx>0吗？怎么证明？ Brensenham大师说，那就看一下他们之间的关系；谁？就是那个p=2Δy·xi+2Δx·yi+(2Δy+2Δx·b-Δx)和下一个点的判断式之间是否存在某种联系。怎么确定他们之间的联系呢？Brensenham大师说不妨还是做个差，p(i+1)-pi;其中我们先看p(i+1) = 2Δy·(xi+1)+2Δx·y(i+1)+(2Δy+2Δx·b-Δx); 那么p(i+1)-pi就是。。。等等，这个(2Δy+2Δx·b-Δx)是个常量，太长，干脆用m代换一下, m = (2Δy+2Δx·b-Δx)；好的，现在p(i+1)-pi = 2Δy·xi+2Δy-2Δx·y(i+1)+m - (2Δy·xi+2Δx·yi+m) 简化一下得到： p(i+1)-pi = 2Δy-2Δx(y(i+1)-yi); Brensenham大师再次崩到天花板上说，这就是他们的迭代关系；下一个像素(判断过后)的下一个像素的判断条件P=pi+2Δy-2Δx(y(i+1)-yi),其中pi和y(i+1)和yi都是已知的，而且y(i+1)-yi的差值要么是1要么是0，也就是说P=pi+2Δy-2Δx 或 P=pi+2Δy (灰常地beautiful)；我不慌不忙，整理了一下：起点的下一个像素判断条件是p=2Δy-Δx; 它的下下一个像素的判断条件是 P=pi+2Δy-2Δx 或 P=pi+2Δy; 这个逻辑足以在代码中实现，往下看。

总结

图-2

Brensenham直线算法的代码实现

#include "raster.h"

Raster::Raster() {}

Raster::~Raster() {}

void Raster::rasterizeLine(
	std::vector<Point>& results,
	const Point& v0,
	const Point& v1) {

	Point start = v0;
	Point end = v1;

	//1 保证x方向是从小到大的
	if (start.x > end.x) {
		auto tmp = start;
		start = end;
		end = tmp;
	}

	results.push_back(start);

	//2 保证y方向也是从小到大，如果需要翻转，必须记录
	bool flipY = false;
	if (start.y > end.y) {
		start.y *= -1.0f;
		end.y *= -1.0f;
		flipY = true;
	}

	//3 保证斜率在0-1之间，如果需要调整，必须记录
	int deltaX = static_cast<int>(end.x - start.x);
	int deltaY = static_cast<int>(end.y - start.y);

	bool swapXY = false;
	if (deltaX < deltaY) {
		std::swap(start.x, start.y);
		std::swap(end.x, end.y);
		std::swap(deltaX, deltaY);
		swapXY = true;
	}

	//4 brensenham
	int currentX = static_cast<int>(start.x);
	int currentY = static_cast<int>(start.y);

	int resultX = 0;
	int resultY = 0;

	Point currentPoint;
	int p = 2 * deltaY - deltaX;

	for (int i = 0; i < deltaX; ++i) {
		if (p >= 0) {
			currentY += 1;
			p -= 2 * deltaX;
		}

		currentX += 1;
		p += 2 * deltaY;

		//处理新xy，flip and swap

		resultX = currentX;
		resultY = currentY;
		if (swapXY) {
			std::swap(resultX, resultY);
		}

		if (flipY) {
			resultY *= -1;
		}

		//产生新顶点
		currentPoint.x = resultX;
		currentPoint.y = resultY;

		interpolantLine(start, end, currentPoint);//插值算法，见下一节

		results.push_back(currentPoint);
	}

}