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

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

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$的地位交换。

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$来摆脱小数。

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$,将其全部变为整数运算。

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
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()