12-08 07:55 阅读 254

关注

Bresenham 线生成算法(bresenham算法计算步骤)

详述 Bresenham 线生成算法

给定直线的起始点和结束点，在显示设备上绘制该线段是计算机图形学中最基本的操作之一。本文将介绍的 Bresenham Line Drawing Algorithm 即为执行该操作的其中一个较为优化的算法。

计算机显示设备是由一个个像素组成的，该算法的目的即为“点亮”由起始像素点 (x_0, x_0)(x0,x0) 至结束像素点 (x_1, y_1)(x1,y1) 的线段上的像素点，当分辨率足够大，像素点足够小，看起来就会像一条直线。

举例：

为简化后续讨论，设置如下限定条件：

1. 起始点在结束点左下方；

2. x_0<x_1x0<x1 且 y_0<=y_1y0<=y1 ；

3. 线段的斜率 0\le k\le 10≤k≤1 ；

4. 对于区间 [x_0,x_1][x0,x1] 内的所有 xx ，该位置仅存在一个像素点。

设置以上限定条件之后，我们可以得到一个十分粗糙的算法：

def easyway(x0,y0,x1,y1):   m = (y2-y1)/(x2-x1)   for x in range(x0, x1+1, 1):     # find y (integer)     y = round(mx+b)     colorify(x,y) 复制代码

该算法是可行的，但在循环的每一步都需要计算 mx+bmx+b，执行速度较慢，因此，我们需要寻找一个快速得到 yy 值的方法。

推导

由于线段的斜率在0到1之间，因此对于点 (x_k,y_k)(xk,yk) ，下个点只可能是 (x_k+1,y_k)(xk+1,yk) 或 (x_k+1,y_k+1)(xk+1,yk+1) ，其中 kk 表示横坐标 xx 移动的次数，如图所示。

因此，我们需要从 y_kyk 和 y_k+1yk+1 中获取离线段较近的值，假设直线方程为 y = mx + by=mx+b ，设 yy 为直线上实际的值，d_1(k)d1(k) 和 d_2(k)d2(k) 分别为距离 y_kyk 和 y_k+1yk+1 的距离，则有：

y = m(x_k+1)+b \\ d_1(k) = y-y_k \\ d_2(k) = (y_k+1) - yy=m(xk+1)+bd1(k)=y−ykd2(k)=(yk+1)−y

比较 d_1(k)d1(k) 和 d_2(k)d2(k) 的值，即可判断下个点的具体位置：

1. 若 d_1(k) \le d_2(k)d1(k)≤d2(k) ，认为下个点应为 (x_k+1, y_k)(xk+1,yk)

2. 反之，认为下个点应为 (x_k+1, y_k+1)(xk+1,yk+1)

因此，我们只需要判断 d_1(k) - d_2(k)d1(k)−d2(k) 的正负性即可：

\begin{aligned} d_1(k) - d_2(k) &= (y-y_k) - ((y_k+1)-y) \\ & = 2y - y_k - y_k -1 \\ & = 2(m(x_k+1)+b) - 2y_k - 1 \\ & = 2m(x_k+1) - 2y_k + 2b - 1 \\ \end{aligned}d1(k)−d2(k)=(y−yk)−((yk+1)−y)=2y−yk−yk−1=2(m(xk+1)+b)−2yk−1=2m(xk+1)−2yk+2b−1

同时，我们有：

b = y_0 - mx_0b=y0−mx0

m = \frac{y_1-y_0}{x_1-x_0} = \frac{dy}{dx}m=x1−x0y1−y0=dxdy

因此，进一步简化得到：

\begin{aligned} d_1(k) - d_2(k) &= 2\frac{dy}{dx}(x_k+1) - 2y_k+2(y_0-\frac{dy}{dx}x_0) -1 \\ &=2\frac{dy}{dx}x_k-2y_k+c \end{aligned}d1(k)−d2(k)=2dxdy(xk+1)−2yk+2(y0−dxdyx0)−1=2dxdyxk−2yk+c

其中 c = 2\frac{dy}{dx}+2y_0-2\frac{dy}{dx}-1c=2dxdy+2y0−2dxdy−1 。

设 p(k) = d_1(k) - d_2(k)p(k)=d1(k)−d2(k)，则:

\begin{aligned} p(0) &= d_1(0)-d_2(0) \\ & = 2\frac{dy}{dx}(x_0+1)-2y_0+2(y_0-\frac{dy}{dx}x_0)-1 \\ & = 2\frac{dy}{dx}-1 \end{aligned}p(0)=d1(0)−d2(0)=2dxdy(x0+1)−2y0+2(y0−dxdyx0)−1=2dxdy−1

对 p(k+1)p(k+1) 推导如下：

\begin{aligned} p(k+1) &= 2\frac{dy}{dx}x_{k+1}-2y_{k+1}+c\\ &= 2\frac{dy}{dx}(x_k+1)-2y_{k+1}+c \end{aligned}p(k+1)=2dxdyxk+1−2yk+1+c=2dxdy(xk+1)−2yk+1+c

所以：

\begin{aligned} p(k+1) - p(k) & = 2\frac{dy}{dx} - 2(y_{k+1}-y_k) \end{aligned}p(k+1)−p(k)=2dxdy−2(yk+1−yk)

因此：

1. 当 p_k \le 0pk≤0 即 d_1(k) \le d_2(k)d1(k)≤d2(k) 时，y_{k+1} = y_kyk+1=yk，则 p(k+1) = p(k)+2\frac{dy}{dx}p(k+1)=p(k)+2dxdy

2. 反之，p(k+1) = p(k) + 2\frac{dy}{dx}-2p(k+1)=p(k)+2dxdy−2

因此，综合以上，我们的代码即为:

def pk(x0,y0,x1,y1):   dy = y1-y0   dx = x1-x0   p = 2*dy/dx - 1   base_increment = 2*dy/dx   colorify(x0,y0)   while x0 <= x1:     x0 += 1     if p > 0:       y0 += 1       p -= 2     p += base_increment     colorify(x0,y0) 复制代码

整数化

上述算法仍然涉及浮点数的计算，下面我们考虑如何彻底取消浮点相关操作。

观察 p(k)p(k) 的表达式，涉及浮点操作的仅为\frac{dy}{dx}dxdy，因此，考虑将等式两侧同乘 dxdx，注意 dx>0dx>0，因此 P(k)P(k) 与 p(k)p(k) 正负性相同，有：

P(k) = dx * p(k) = 2dy * x_k-2dx * y_k+c \\ P(0) = 2dy - dx \\ P(k+1)-P(k) = 2dy - 2dx*(y_{k+1}-y_k)P(k)=dx∗p(k)=2dy∗xk−2dx∗yk+cP(0)=2dy−dxP(k+1)−P(k)=2dy−2dx∗(yk+1−yk)

同样的：

1. 当 P_k \le 0Pk≤0 即 d_1(k) \le d_2(k)d1(k)≤d2(k) 时，y_{k+1} = y_kyk+1=yk，则 P(k+1) = P(k)+2dyP(k+1)=P(k)+2dy

2. 反之，P(k+1) = P(k) + 2dy-2dxP(k+1)=P(k)+2dy−2dx

代码即变为：

def pk(x0,y0,x1,y1):   dy = y1-y0   dx = x1-x0   p = 2*dy - dx   base_increment = 2*dy   colorify(x0,y0)   while x0 <= x1:     x0 += 1     if p > 0:       y0 += 1       p -= 2*dx          p += base_increment     colorify(x0,y0) 复制代码

一般化

之前的讨论是基于文首给出的限定条件的：

1. 起始点在结束点左下方；

2. x_0<x_1x0<x1 且 y_0<=y_1y0<=y1 ；

3. 线段的斜率 0\le k\le 10≤k≤1 ；

4. 对于区间 [x_0,x_1][x0,x1] 内的所有 xx ，该位置仅存在一个像素点。

下面我们将该算法一般化。

垂直线

当 x_0 = x_1x0=x1 时，线段的斜率不存在，此时只需要使纵坐标 yy 每次递增单位长度，然后染色即可。

if dx == 0:   while y1!=y2:     y1 += stepy     colorify(x1,y1) 复制代码

dy<0, dx<0

当 dy<0 时，如下图：

此时我们将点 (x_1,y_1)(x1,y1) 映射为 (x_1,y_1')(x1,y1′)，其中虚线为两条线段的垂直平分线，那么 y_1'-y_0 = y_0 - y_1y1′−y0=y0−y1，接着我们对虚线上侧的线段按上述算法计算需要绘制的点即可，但在实际绘制时，对需要递增 yy 的情况，我们递减 yy，则可以对称的绘制出原需要绘制的直线。

同理，当 dx < 0 时，如下图：

同样的，此时我们将点 (x_1,y_1)(x1,y1) 映射为 (x_1',y_1)(x1′,y1)，其中虚线为两条线段的垂直平分线，那么 x_1'-x_0 = x_0 - x_1x1′−x0=x0−x1，接着我们对虚线右侧的线段按上述算法计算需要绘制的点即可，但在实际绘制时，对需要递增 xx 的情况，我们递减 xx，则可以对称的绘制出原需要绘制的直线。

当 dx 和 dy 均小于0时，需要对原线段作两次变换。

dx = x1-x0 dy = y1-y0 if dy < 0:     dy = -dy     stepy = -1 else:     stepy = 1 if dx < 0:     dx = -dx     stepx = -1 else:     stepx = 1 #  .... while x0 != x1:     x0 += stepx     if p >= 0:         y0 += stepy         # ....          # .... # .... 复制代码

m > 1

当直线斜率大于 1 时，即 dy>dx，原直线方程为 y=mx+by=mx+b ，可以变换为 x = \frac{1}{m}y-\frac{b}{m}x=m1y−mb，则 \frac{1}{m} < 1m1<1，因此只需要对该新直线应用上述算法即可。

Put it together

def bresenham(p1,p2):     x0, y0 = p1     x1, y1 = p2     dx = x1-x0     dy = y1-y0     if dy < 0:         dy = -dy         stepy = -1     else:         stepy = 1     if dx < 0:         dx = -dx         stepx = -1     else:         stepx = 1     dy <<= 1     dx <<= 1     colorify(x0, y0)     if dx == 0:         while y0 != y1:             y0 += stepy             colorify(x0, y0)     if dx > dy:         fraction = dy-(dx >> 1)         while x0 != x1:             x0 += stepx             if fraction >= 0:                 y0 += stepy                 fraction -= dx             fraction += dy             colorify(x0, y0)     else:         fraction = dx - (dy >> 1)         while y0 != y1:             if fraction >= 0:                 x0 += stepx                 fraction -= dy             y0 += stepy             fraction += dx             colorify(x0, y0) 复制代码

时间复杂度为 O(x_2-x_1)O(x2−x1)，空间复杂度为 O(1)O(1)

实际应用

使用 python 中的 matplotlib 模块对该算法进行可视化。

(1,1) -> (2,10)： 

(1,1) -> (10,1)：

(10,8) -> (1,1)：

源码