光栅化直线生成算法(DDA、MidPoint、Bresenham)的原理与实现

这两天用空闲时间实现了光栅化直线常用的三种生成算法(DDA、MidPoint、Bresenham),图形学真的有趣!

下面是一些通用的函数,分别是画格点与像素点方块的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
from matplotlib.lines import Line2D

def add_grid(size_x, size_y):
major_ticks = np.arange(0, size_x + 1, 5)
minor_ticks = np.arange(0, size_y + 1, 1)
ax.set_xticks(major_ticks)
ax.set_xticks(minor_ticks, minor=True)
ax.set_yticks(major_ticks)
ax.set_yticks(minor_ticks, minor=True)
ax.grid(which='minor', alpha=0.2)
ax.grid(which='major', alpha=0.5)

def pixel_plot(x, y, c):
rect = Rectangle((x, y), 1, 1, color=c, alpha=0.5)
ax.add_patch(rect)

数值微分法(DDA算法)

先算出直线的斜率$k = \Delta y / \Delta x$,然后$x$每增加1,$y$增加$k$。只适用于$|k| \leq 1$的情形,当$k$的绝对值超过1时必须把$x$与$y$的地位交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def dda_line(x1, y1, x2, y2, c):
if abs(y1 - y2) > abs(x1 - x2):
if y1 > y2:
x1, y1, x2, y2 = x2, y2, x1, y1
x = x1
k = (x2 - x1) / (y2 - y1)
for y in range(y1, y2 + 1):
pixel_plot(int(x + 0.5), y, c)
x += k
else:
if x1 > x2:
x1, y1, x2, y2 = x2, y2, x1, y1
y = y1
k = (y2 - y1) / (x2 - x1)
for x in range(x1, x2 + 1):
pixel_plot(x, int(y + 0.5), c)
y += k

中点画线法

首先假定直线斜率在0、1之间,$F(x, y) = ax + by + c - 0$,其中$a = y_1 - y_2, b = x_2 - x_1, c = x_1y_2 - x_2y_1$。假设$(x_p, y_p)$已确定,那么下一个与直线最近的像素只能是$(x_p + 1, y_p)$或$(x_p + 1, y_p + 1)$,用$M = (x_p + 1, y_p + 0.5)$表这两个点的中点。$d = F(M) = F(x_p + 1, y_p + 0.5) = a(x_p + 1) + b(y_p + 0.5) + c$,若$d < 0$则$M$在直线下方,此时应取$(x_p + 1, y_p + 1)$,否则应取$(x_p + 1, y_p)$。

为了避免每次计算浮点数乘法,我们采用增量的形式:当在$d \geq 0$时,再判断下一个像素的位置,应计算$d_1 = F(x_p + 2, y_p + 0.5) = a(x_p + 2) + b(y_p + 0.5) + c = d + a$,增量为$a$;当在$d < 0$时,再判断下一个像素的位置,应计算$d_2 = F(x_p + 2, y_p + 1.5) = a(x_p + 2) + b(y_p + 1.5) + c = d + a + b$,增量为$a + b$。又$d_1 = F(x_1 + 1, y_1 + 0.5) = F(x_1, y_1) + a + 0.5b = a + 0.5b$,$d$的增量都是正数,只有$d_1$包含小数,所以我们可以用$2d$代替$d$来摆脱小数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def mid_point_line(x1, y1, x2, y2, c):
if abs(y1 - y2) > abs(x1 - x2):
if y1 > y2:
x1, y1, x2, y2 = x2, y2, x1, y1
a = y1 - y2
b = x2 - x1
delta1 = 2 * b
x, y = x1, y1
pixel_plot(x, y, c)
if x1 < x2:
d = 2 * b + a
delta2 = 2 * (a + b)
while y < y2:
y += 1
if d > 0:
x += 1
d += delta2
else:
d += delta1
pixel_plot(x, y, c)
else:
d = 2 * b - a
delta2 = 2 * (b - a)
while y < y2:
y += 1
if d < 0:
x -= 1
d += delta2
else:
d += delta1
pixel_plot(x, y, c)
else:
if x1 > x2:
x1, y1, x2, y2 = x2, y2, x1, y1
a = y1 - y2
b = x2 - x1
delta1 = 2 * a
x, y = x1, y1
pixel_plot(x, y, c)
if y1 < y2:
d = 2 * a + b
delta2 = 2 * (a + b)
while x < x2:
x += 1
if d < 0:
y += 1
d += delta2
else:
d += delta1
pixel_plot(x, y, c)
else:
d = 2 * a - b
delta2 = 2 * (a - b)
while x < x2:
x += 1
if d > 0:
y -= 1
d += delta2
else:
d += delta1
pixel_plot(x, y, c)

Bresenham算法

$y$每增加1,误差项$d$增加$k$,一旦$d \geq 1$就将其减去,保证其位于0、1之间。当$d \geq 0.5$时,取$(x + 1, y + 1)$,否则取$(x + 1, y)$。然后可以将$d$的初值设为-0.5,然后与0比较即可。由于是与0进行比较,甚至进一步可以将其乘上$2dx$,将其全部变为整数运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def brese_line(x1, y1, x2, y2, c):
if abs(y2 - y1) > abs(x2 - x1):
if y1 > y2:
x1, y1, x2, y2 = x2, y2, x1, y1
dx = x2 - x1
dy = y2 - y1
e = -dy
sdx = np.sign(dx)
dx_ = abs(dx)
x = x1
for y in range(y1, y2 + 1):
pixel_plot(x, y, c)
e += 2 * dx_
while e >= 0:
x += sdx
e -= 2 * dy
else:
if x1 > x2:
x1, y1, x2, y2 = x2, y2, x1, y1
dx = x2 - x1
dy = y2 - y1
e = -dx
sdy = np.sign(dy)
dy_ = abs(dy)
y = y1
for x in range(x1, x2 + 1):
pixel_plot(x, y, c)
e += 2 * dy_
while e >= 0:
y += sdy
e -= 2 * dx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
x = []
y = []
x.append(1); y.append(1); x.append(35); y.append(20);
x.append(1); y.append(1); x.append(20); y.append(35);
x.append(10); y.append(35); x.append(20); y.append(5);
x.append(10); y.append(20); x.append(35); y.append(10);

fig, ax = plt.subplots(figsize=(10, 10))
add_grid(50, 50)
for i in range(4):
ax.add_line(Line2D((x[i * 2] + 0.5, x[i * 2 + 1] + 0.5), (y[i * 2] + 0.5, y[i * 2 + 1] + 0.5), linewidth=2, color='blue'))
dda_line(x[i * 2], y[i * 2], x[i * 2 + 1], y[i * 2 + 1], 'gray')
plt.show()

fig, ax = plt.subplots(figsize=(10, 10))
add_grid(50, 50)
for i in range(4):
ax.add_line(Line2D((x[i * 2] + 0.5, x[i * 2 + 1] + 0.5), (y[i * 2] + 0.5, y[i * 2 + 1] + 0.5), linewidth=2, color='blue'))
mid_point_line(x[i * 2], y[i * 2], x[i * 2 + 1], y[i * 2 + 1], 'gray')
plt.show()

fig, ax = plt.subplots(figsize=(10, 10))
add_grid(50, 50)
for i in range(4):
ax.add_line(Line2D((x[i * 2] + 0.5, x[i * 2 + 1] + 0.5), (y[i * 2] + 0.5, y[i * 2 + 1] + 0.5), linewidth=2, color='blue'))
brese_line(x[i * 2], y[i * 2], x[i * 2 + 1], y[i * 2 + 1], 'gray')
plt.show()

png

png

png

如果您觉得这篇文章对您有帮助,请随意打赏。