Bresenham 直线绘制算法

本文介绍著名的Bresenham 直线绘制算法
由于现在的屏幕是由一个个像素点构成的,所以在计算机中绘制的直线也就是只能是由离散的点构成,Bresenham直线绘制算法可以在屏幕上绘制任何直线。并且它只需要使用整除运算,完全不需要浮点运算,从而具有超高的性能。
接下来介绍我理解的Bresenham算法流程,并在最后贴出我实现的C++代码。(为了介绍的容易理解,这里只举斜率为0到1之间的直线)
如下图所示,离散化直线的本质是已知(xi,yi)点时确定下一个点(xi+1,yi+1)的位置:只有两种可能,一种是(xi+1,yi),另一种是(xi+1,yi+1)
1665406210210
Bresenham算法的核心就是x相同时观察直线到拟合直线的距离(图中的D),距离D超过中点也就是0.5时,拟合曲线就把自己的y值加一,也就是图中移上去一格,从而始终保持D小于等于0.5。
伪代码就是

D=0
for each x in (x0,x1) 
  DrawPoint(x,y) 
  D+=k 
  if(D>0.5) 
    y++   
    D-=1 //y移上去之后距离也要更新 

这个版本已经可以画任意直线了但是需要浮点运算(比如计算k值,D值)。我们想要更好的性能,于是就有了下面一个优化版本:
首先,我们不想将D与0.5比较(浮点数比较),可以先将D变大一倍不影响结果,此时伪代码变成:

D1=0 //用D1表示新的拟合直线与原直线距离
for each x in (x0,x1) 
  DrawPoint(x,y) 
  D1+=2*k 
  if(D1>1) 
    y++  
    D1-=2  

由于k=dy/dx,dy=y1-y0,dx=x1-x0,且dy,dx都是整数(输入在屏幕上的点坐标x0,y0,x1,y1一定是整数),于是我们将D扩大dx倍,去掉计算D时候的浮点加法运算,此时伪代码变成:

D2=0 //用D2表示新的拟合直线与原直线距离
for each x in (x0,x1) 
  DrawPoint(x,y) 
  D2+=2*dy//整数运算! 
  if(D2>dx) 
    y++  
    D2-=2*dx  

于是,我们就得到了一个全部都是整数运算的直线绘制算法!于是它就可以在我之前做的没有浮点运算器的计算机中绘制直线!用Nexys4 DDR 制作一台计算机系列
以下是完整C++代码:

void DrawLine_Bresenham(int x0, int y0, int x1, int y1, const Color& color)
{
	if (x1 < x0) {
		int tempX, tempY;
		tempX = x0;
		x0 = x1;
		x1 = tempX;
		tempY = y0;
		y0 = y1;
		y1 = tempY;
	}
	if (x1 == x0) {
		for (int y = min(y0, y1); y <= max(y0, y1); y++) {
			DrawPoint(x0, y, color);
		}
		return;
	}

	//k=0
	if (y1==y0) {
		for (int x = x0; x < x1; x++) {
			DrawPoint(x, y0, color);
		}
		return;
	}
	int dx = x1 - x0, dy = y1 - y0;
	bool kSign = ((y1 - y0) >= 0 && (x1 - x0) >= 0) ? true : false; //true => positive false =>negative
	bool kGreaterThenOne = (abs(y1 - y0) > abs(x1 - x0)) ? true : false;

	int d = 0;
	// 0<k<=1
	if (kSign == true && kGreaterThenOne == false) {
		int y = y0;

		for (int x = x0; x < x1; x++) {
			DrawPoint(x, y, color);
			d += 2 * dy;
			if (d > dx) {
				d -= 2 * dx;
				y++;
			}
		}
	}
	//k>1
	else if (kSign == true && kGreaterThenOne == true) {
		int x = x0;

		for (int y = y0; y < y1; y++) {
			DrawPoint(x, y, color);
			d += 2 * dx;
			if (d > dy) {
				d -= 2 * dy;
				x++;
			}
		}
	}
	//-1<k<=0
	else if(kSign==false&&kGreaterThenOne==false){
		int y = y0;

		for (int x = x0; x < x1; x++) {
			DrawPoint(x, y, color);
			d += -2 * dy;
			if (d > dx) {
				d -= 2 * dx;
				y--;
			}
		}
	}
	//k<-1
	else if (kSign == false && kGreaterThenOne == true) {
		int x = x0;

		for (int y = y0; y > y1; y--) {
			DrawPoint(x, y, color);
			d += 2 * dx;
			if (d > -dy) {
				d -= -2 * dy;
				x++;
			}
		}
	}
	
}

附上用Bresenham直线绘制算法画的兔子
20221011212023

展示评论