Introduction
计算机图形学课上介绍了一个由两点所决定的直线的算法——Bresenham 算法 ;
这个算法用到了快速的整数加法,减法和位元移位,是计算机图形里面描绘直线的较为快速的算法。
首先来介绍一下,绘制直线的基本方法:
假设我们需要由(x0, y0)这一点,绘画一直线至右下角的另一点(x1, y1),x,y分别代表其水平及垂直坐标,并且x1 - x0 > y1 - y0。
因为像素点需要的x及y皆为整数,但并非每一点x所对应的y皆为整数,因此没有必要去计算每一点x所对应之y值。反之由于此线的斜率介乎于1至0之间,因此我们只需要找出当x到达那一个数值时,会使y上升1,若x尚未到此值,则y不变。至于如何找出相关的x值,则需依靠斜率。斜率之计算方法为。由于此值不变,故可于运算前预先计算,减少运算次数。
Problem
但这里遇到了一个问题,由于计算机图形学对速度要求较高,而上面提到的算法中用到了大量的浮点运算;而且,经过大量的浮点运算,误差会被大量积累。因此为了避免这种情况发生,应该将浮点运算转换为整数运算。
因此就引入了这种算法:Bresenham's line algorithm
- 首先来看这张图:
- 由此可见,每次xi增加时,yi都有两个选择:y(i+1) =yi or y(i+1) =yi
+ 1;因此我们需要比较d1和d2的大小:
- y = m(xi + 1) + b
- d1 = y - yi
- d2 = yi + 1 - y
- If d1-d2 > 0,then y(i+1)=yi + 1,else yi+1 = yi
- y = m(xi + 1) + b
- 根据上面的式子和m = dy/dx (dy = y1 - y0;dx = x1 -
x0),我们可以计算得:
- d1-d2= 2y - 2yi - 1= 2dy/dxxi + 2dy/dx + 2b - 2yi - 1*
- 关键点来了,为了避免浮点数运算,我们在两边乘以dx;假设
dx*(d1-d2) = Pi:
- Pi = 2xidy - 2yidx + 2dy + (2b-1)dx
- 同理:P(i+1) = 2x(i+1)dy - 2y(i+1)dx + 2dy + (2b-1)dx
这时,当Pi > 0,下一个y取 yi + 1,否则还是yi;
- 因此我们可以得到一个增量函数:P(i+1) = Pi+2dy-2(y(i+1)-yi)dx;
- 既然是增量函数:我们要求起始P0:
- 由上面的式子,P0 = 2x0dy - 2y0dx + 2dy + (2b-1)dx;
- 两边除以dx,得到 P0/dx = 2x0m - 2y0 + 2m + (2b-1);
- 结合: 2x0m - 2y0 + 2b = 0,得到P0 = 2mdx - dx = 2dy - dx ;
以上就是,我们对此算法的推导,通过整数运算,移位等,根据Pi的正负,即可快速描绘出直线;
Pseudocode
1 | function line(x0, x1, y0, y1)//假设x0 < x1; y0 < y1 |
至于线段方向改变等问题,则只要交换x和y即可;