直线的光栅化算法

导读：计算机图形学介绍了直线生成的三种算法，DDA算法、中点画线法、Bresenham算法的Python语言实现和绘图。编码时被象限问题困扰很久，后来想到参考值可以用abs转化到第一象限，一下解决所有问题。

三种算法的本质都是增量算法。通俗的讲，直线的光栅化就是把矢量图转化成点阵图，要求产生的点阵尽可能真实地渲染出实际直线。

实际上三种算法的思想都差不多，主要考虑的是算法的耗时（主要表现为浮点数，浮点数计算很费事，三种算法在逐渐消除浮点数计算和比较），因为实际应用时，绘制直线操作用的非常多，如果时间消耗太多肯定不行。

DDA算法

DDA算法利用了一条直线的斜率是一个常量这一事实，因此每步增量附加上去，另一个坐标轴上也产生相应增量。得到的点用四舍五入的方法处理，即得到所画直线的点阵表示。

需要注意的是选取的步长为1的增量坐标轴，为了说清，取第一象限，假设斜率 k 大于 1，若此时选择 x 轴作为步进方向，每次步进 1 单位，则 y 轴会步进超过 1 个单位，后果就是画出的 “直线” 根本连不到一起。因此需要分类讨论。

def DDALine():
    curX = 0    # 当前x
    curY = 0    # 当前y
    ex = -640   # 直线终点 x
    ey = 320    # 直线终点 y
    deltaX = ex-curX    # x偏移量
    deltaY = ey-curY    # y偏移量
    eps = abs(deltaY) if abs(deltaX) > abs(deltaY) else abs(deltaX) # 决定增量方向
    x_incre = deltaX/eps # 增量都是1，主要看符号，这里没写好，实际上可以不用除法的
    y_incre = deltaY/eps
    gl.glBegin(gl.GL_POINTS)
    k = 0
    while k < eps:
        gl.glColor3f(1.0,0.0,0.0)
        gl.glVertex2d(int(curX)/SCREEN_WIDTH, int(curY)/SCREEN_HEIGHT)
        curX += x_incre
        curY += y_incre
        k += 1
    gl.glColor3f(0.0,1.0,0.0)
    gl.glVertex2d(ex/SCREEN_WIDTH, ey/SCREEN_HEIGHT)
    gl.glEnd()
    gl.glFlush()

中点画线法

思路是把直线与网格的交点、直线跨越的单位网格的中点作差比较，如果直线与网格交点在相应网格中点以上，则选择上面的点绘制，否则选择下面的点绘制。简单的说，就是根据中点，画出离交点最近的像素点。

​x
def medianLine():
    curX = 120
    curY = 30
    ex = 120
    ey = -350
    deltaX = ex-curX
    deltaY = ey-curY
​
    eps = abs(deltaX)
    gl.glBegin(gl.GL_POINTS)
    i = 0
​
    sx = 1 if deltaX > 0 else -1
    sy = 1 if deltaY > 0 else -1
    
    deltaX = abs(deltaX)
    deltaY = abs(deltaY)
​
    if abs(deltaY) >= abs(deltaX):
        # Y Incre
        d = deltaX - 2 * deltaY
        eps = abs(deltaY)
        while i < eps:
            gl.glColor3f(1.0,0.0,0.0)
            gl.glVertex2d(curX/SCREEN_WIDTH, curY/SCREEN_HEIGHT)
            curY += sy
            if d >= 0:
                d = d - 2*deltaX
            else:
                d = d + 2*deltaY - 2*deltaX
                curX += sx
            i += 1
    else:
        # X Incre
        d = deltaX - 2 * deltaY
        eps = abs(deltaX)
        while i < eps:
            gl.glColor3f(1.0,0.0,0.0)
            gl.glVertex2d(curX/SCREEN_WIDTH, curY/SCREEN_HEIGHT)
            curX += sx
            if d >= 0:
                d = d - 2*deltaY
            else:
                d = d + 2*deltaX - 2*deltaY
                curY += sy
            i += 1
    gl.glColor3f(0.0,1.0,0.0)
    gl.glVertex2d(ex/SCREEN_WIDTH, ey/SCREEN_HEIGHT)
    gl.glEnd()
    gl.glFlush()

Bresenham算法

此算法的原理是：以第一象限为例，设直线与网格的交点A，离A点最近的上部网格点为Upper，离A点最近的下部网格点为Lower，若 d = Upper-Lower > 0，说明A离下面的像素点近，选择下面的点绘制，否则选择上面的像素点绘制。

为了彻底消灭浮点数计算，下面的代码用到了几次优化过程。

第一次，设变量 d 表示A距离下端最近网格线的垂直距离，d 每次增加 k（设 x 增量1，y 增量就是 k），若 d 大于 0.5 则说明 y 方向要产生增量（因为在中点上方，这里用到了中点画线法的思想），y += 1 且 d -= 1。但出现了与 0.5 的比较，这不是我们想要的。

第二次，用 e 代替 d - 0.5。这样一来 0.5 就变成了 0，消除了浮点数 0.5，但仍存在浮点数 k。

第三次，用 e = 2Δx 代替原来的 e。因为 k = Δy / Δx，这样做直接消除了式中的Δx，浮点数 k 因此被消除了。

最终得到的相关表达式：

xxxxxxxxxx
def bresenhamLine():
    curX = 0
    curY = 0
    ex = 320
    ey = -160
    deltaX = ex-curX
    deltaY = ey-curY
    p = 0
    sx = 1 if deltaX > 0 else -1
    sy = 1 if deltaY > 0 else -1
    gl.glBegin(gl.GL_POINTS)
    if abs(deltaX) > abs(deltaY):
        # X Incre
        e = -2*abs(deltaX)
        eps = abs(deltaX)
        while p<eps:
            gl.glColor3f(1.0,0.0,0.0)
            gl.glVertex2d(int(curX)/SCREEN_WIDTH, int(curY)/SCREEN_HEIGHT)
            p += 1
            e += 2*abs(deltaY)
            if e > 0:
                e -= 2*abs(deltaX)
                curY += sy
            curX += sx
    else:
        # Y Incre
        e = -2*abs(deltaY)
        eps = abs(deltaY)
        while p<eps:
            gl.glColor3f(1.0,0.0,0.0)
            gl.glVertex2d(int(curX)/SCREEN_WIDTH, int(curY)/SCREEN_HEIGHT)
            p += 1
            e += 2*deltaX
            if e > 0:
                e -= 2*abs(deltaY)
                curX += sx
            curY += sy
    gl.glColor3f(0.0,1.0,0.0)
    gl.glVertex2d(ex/SCREEN_WIDTH, ey/SCREEN_HEIGHT)
    gl.glEnd()
    gl.glFlush()