画线算法

CG computer graphics

Created At : 2021-06-05 17:31

Comment:

直线方程
DDA(Digital Differential Analyzer 数值微分分析器)
1. 实现
2. Bresenham算法

参考
- 绘制直线的光栅化算法
- 计算机图形学(第四版) Computer Graphics with OpenGL Fourth Edition
我们需要根据一条直线(屏幕上代指线段)的两个端点$(x_{0},y_{0}),(x_{1},y_{1}),x_{0} < x_{1}$,绘制中间的像素点.

直线方程
斜截式
- $y = kx + b$
  - 根据两个端点可以计算k和b
    - $k = \frac{y_{0} -y_{1}}{x_{0} - x_{1}}$
    - $b = y_{0} - kx_{0}$
按照直觉的方法,就是通过遍历所有的x的值,计算y的值来得到直线上每一个像素的位置.但是由于其涉及乘法,对性能损耗大.需要尽可能的不适用乘法.

DDA(Digital Differential Analyzer 数值微分分析器)

采用增量的思想,$\delta_{x}$为x方向的增量,$\delta_{y}$为y方向的增量
- $y_{i+1} = kx_{i+1} + b= k(x_{i} + \delta_{x}) + b= kx_{i} + b + k\delta_{x} = y_{i} + k\delta_{x}$
这样，每个纵坐标的值都是在前一个纵坐标的基础上加上斜率k.

问题1:当斜率过大时,直线过于稀疏
- 当0 < |k| <= 1时, x方向遍历,$y_{i+1} = y_{i} + k$
- 当|k| > 1时,y方向遍历,$x_{i+1} = y_{i} + 1/k$
问题2:效率仍然比较低
- 此方法用到了浮点数,浮点数加减法效率仍无法满意

实现

输入线段的端点值,计算水平和垂直方向差值dx,dy,绝对值大的值用于确定step值(确定哪个方向增量为1)
从$(x_{0},y_{0})$开始,每次在x和y方向上增加相应的增加,并绘制像素

#include <stdlib.h>
#include <math.h>

inline int round (const float a) {return int(a+0.5)}

void lineDDA(int x0,int y0,int x1,int y1)
{
    int dx = x1 - x0,dy = y1 - y0,steps,k;
    float xIncrement,yIncrement,x=x0,y=y0;

    if(fabs(dx) > fabs(dy))
        step = fabs(dx);
    else
        step = fabs(dy);
    xIncrement = float (dx)/ float (steps);
    yIncrement = float (dy)/ float (steps);

    setPixel(round(x),round(y));
    for(k = 0; k < steps; ++k)
    {
        x += xIncrement;
        y += yIncrement;
        setPixel(round(x),round(y));
    }
}

Bresenham算法

参考:【十天自制软渲染器】DAY 02：画一条直线（DDA 算法 & Bresenham’s 算法

对于任意斜率在[0,1)的直线,其端点为(x1,y1),(x2,y2),其斜率为k(0<=k<1)
- 第一个点是$(x_{1},y_{1})$.
- 对于第二个点可能是$(x_{1}+1,y_{1}+1)$,也有可能是$(x_{1}+1,y_{1})$;
  - 我们通过计算$y_{1}+k$可以得到第二个点的实际位置,此时我们只需比较$y_{1}+k$和$y_{1}+0.5$的大小即可.
    - $y_{1}+k >= y_{1}+0.5$,直线在这个像素中心的上方,取$y_{1}+1$.
    - $y_{1}+k < y_{1}+0.5$,直线在这个像素中心的下方,取$y_{1}$.
  - 我们将把$y_{1}+k 和 y_{1}+0.5$考虑成误差形式
    - 假设初始误差$\epsilon=0$(假设两端点的值都为整数)
    - 则我们只需比较$\epsilon + k 和 0.5$的大小
- 然后我们必须更新新的误差值$\epsilon$让参与第三个点的计算
  - 若第二点为$(x_{1}+1,y_{1}+1)$,那么$\epsilon \leftarrow y + \epsilon + k - (y+1) = \epsilon + k -1$
  - 若第二点为$(x_{1}+1,y_{1})$,那么$\epsilon \leftarrow y + \epsilon + k - (y) = \epsilon + k$
- 之后一直按上述规则更新.

//伪代码
EPS = 0
y = y1
for x from x1 to x2 do
    draw point at (x,y)
    if((EPS + k) < 0.5)
        EPS = EPS+k
    else
        EPS = EPS+k-1
        y = y +1
    end if
end for

上述方法涉及浮点运算,对效率有影响,我们对误差判断的不等式做如下变换 $\epsilon + k < 0.5$ $\epsilon + \Delta y / \Delta x < 0.5$ $2\epsilon\Delta x + 2\Delta y < \Delta x$ $2(\epsilon'+ \Delta y) < \Delta x,\epsilon' = \epsilon\Delta x$
因此,我们构建初始误差值$\epsilon’$,每次加上$\Delta y$.然后每次用2$(\epsilon’+\Delta y)$和$\Delta x$进行判断即可.
对于误差值的更新,我们做如下变换
- $\epsilon = \epsilon + k \leftrightarrow \epsilon\Delta x = \epsilon\Delta x + \Delta y \leftrightarrow \epsilon’ = \epsilon’ + \Delta y$
- $\epsilon = \epsilon + k - 1 \leftrightarrow \epsilon\Delta x = \epsilon\Delta x + \Delta y - \Delta x \leftrightarrow \epsilon’ = \epsilon’ + \Delta y - \Delta x$

//伪代码
EPS_PRIM = 0
y = y1
for x from x1 to x2 do
    draw point at (x,y)
    if(2(EPS_PRIM + dy) < dx)
        EPS_PRIM = EPS_PRIM + dy
    else
        EPS_PRIM = EPS_PRIM + dy - dx
        y = y +1
    end if
end for

c++实现

void line(Screen &s,
  int x1, int y1,
  int x2, int y2,
  TGAImage &image, TGAColor color) {
  int y = y1;
  int eps = 0;
  int dx = fabs(x2 - x1);
  int dy = fabs(y2 - y1);

  for (int x = x1; x <= x2; x++) {
    image.set(x, y, color);
    eps += dy;
    // 这里用位运算 <<1 代替 *2
    if((eps << 1) >= dx)  {
      y++;
      eps -= dx;
    }
  }
}

上述算法在使用于斜率的绝对值在[0,1)的直线,并且x1 < x2的直线,对于其他情况,可以通过交换xy的遍历方式解决.

画线算法

直线方程

DDA(Digital Differential Analyzer 数值微分分析器)

实现

Bresenham算法