任意斜率下的Bresenham算法实现

80 阅读 0 评论 53 点赞

我是靠谱客的博主笨笨毛豆，最近开发中收集的这篇文章主要介绍任意斜率下的Bresenham算法实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本书3.5.3介绍了Bresenham算法，并给出代码。但是，这个代码只适用于斜率m在0<m<1.0的情况（而非书中说的|m|<1），并且只能用于从左向右画线（从右到左时依靠强制调换两点的方法，不自然，有潜在麻烦）。
结合习题，我们可以讨论其他情况（-1.0<m<0及从右向左画），并看看能否把多种情况整合到统一的过程里。使用书中的方法推导决策参数p（可以使用上下点之差，或者中点决策法），可以对|m|<0时总结下面四种情况：

      1) 0<m<1.0，从左向右画。这是书中给出的情况，关键数据如下：
           p(0) = 2Δy-Δx
           p(k)<0: p(k+1) = p(k)+2Δy，下一点(x(k)+1, y(k))
           p(k)>0: p(k+1) = p(k)+2Δy-2Δx，下一点(x(k)+1, y(k)+1)

       2) 0<m<1.0，从右向左画。
           p(0) =  Δx-2Δy
           p(k)<0: p(k+1) = p(k)-2Δy，下一点(x(k)-1, y(k))
           p(k)>0: p(k+1) = p(k)-2Δy+2Δx，下一点(x(k)-1, y(k)-1)
           注意，此处Δx，Δy均为负值，与1)相比较，p(k)的实际值完全一样。不一样处只是下一点的选取。
 
 
       3) -1.0<m<0，从左向右画。
           p(0) = -Δx-2Δy
           p(k)<0: p(k+1) = p(k)-2Δy，下一点(x(k)+1, y(k))
           p(k)>0: p(k+1) = p(k)-2Δy-2Δx，下一点(x(k)+1, y(k)-1)
           为了与前面判断情况尽量保持一致，3)对中p(k)的推导中乘以了-1。此处Δx为正，Δy为负。
 
 
       4)  -1.0<m<0，从右向左画。
           p(0) = 2Δy+Δx
           p(k)<0: p(k+1) = p(k)+2Δy，下一点(x(k)-1, y(k))
           p(k)>0: p(k+1) = p(k)+2Δy+2Δx，下一点(x(k)-1, y(k)+1)
           为了与前面判断情况尽量保持一致，4)对中p(k)的推导中乘以了-1。此处Δx为负，Δy为正。

       总结：结合以上四种情况中Δx，Δy的正负和p的表达式：
           p(0)=2|Δy|-|Δx|
           p(k)<0: p(k+1) = p(k)+2|Δy|
           p(k)>0: p(k+1) = p(k)+2|Δy|-2|Δx|

       可见其内部是完全统一的。对点的选取其实也不难处理，下一点是+1还是-1，与Δx，Δy的正负是一致的，这样就好办了。
       最后，利用对称性对|m|>1的情况的处理，我使用了递归，在递归中将x，y位置调换，并在画点的时候将二者再调换后来即可。为效率与代码安全起见，斜率为1和0时的情况单独处理。斜率为无穷大时在递归中等同于斜率为0。

void Bresenham(GLint x0, GLint y0, GLint x1, GLint y1)
{
	int static converse = 0;
	GLint const dy = y1 - y0, dx = x1 - x0;
	GLint const dxAbs = abs(dx);
	GLint const dyAbs = abs(dy);
	GLint const twoDyAbs = dyAbs * 2, twoDyMinusDxAbs = 2 * (dyAbs - dxAbs);
	GLint const stepX = ((dx == 0) ? 0 : dx / dxAbs);
	GLint const stepY = ((dy == 0) ? 0 : dy / dyAbs);
	GLfloat pk = twoDyAbs - dxAbs;
	GLint x = x0, y = y0;
	int i;


	if (dxAbs < dyAbs){
		converse = 1;
		Bresenham(y0, x0, y1, x1);
		converse = 0;
		return;
	}
	/*first, draw the initial point, it's MUST-DO*/
	if (converse == 1)
		setPixel(y, x);
	else
		setPixel(x, y);


	/*horizontal line and 45-slope-line are represented specifically for effeciency.*/
	if (dyAbs == dxAbs || dyAbs == 0 || dxAbs == 0){
		for (i = 0 ; i < dxAbs ; i++)
			if (converse == 1)
				setPixel (y += stepY, x += stepX);
			else
				setPixel (x += stepX, y += stepY);
		return;
	}


	/*Bresenham algrithm*/
	for (i = 0; i < dxAbs; i++, x += stepX){
		if (pk < 0){
			pk += twoDyAbs;
		}else {
			y += stepY;
			pk += twoDyMinusDxAbs;
		}
		if (converse == 1)
			setPixel(y, x);
		else
			setPixel(x , y);
	}
}