第六章 实现图元及属性的算法

计算机图形学

---

6.1 画线算法

6.1.1 直线方程

直线的笛卡尔斜率截距式方程为

$$y = m\cdot x + b \tag{6.1} m为斜率，b为截距$$

给定两个端点$(x_0,y_0),(x_{end},y_{end})$,可以计算斜率$m$和截距$b$

$$\begin{align} m &= \frac{y_{end}-y_0}{x_{end}-x_0} \tag{6.2} \\ b &= y_0 - m \cdot x_0 \tag{6.3} \end{align}$$
显示直线的算法是以(6.1),(6.2),(6.3)式为基础的.
给出$x$轴或$y$轴上的一个偏移量$\delta x$或者$\delta y$,可以计算相应的另一个坐标轴上的偏移量
$$\begin{align} \delta y & = m \cdot \delta x \tag{6.4}\\ \delta x & = \frac {\delta y}{m} \tag{6.5} \end{align}$$

6.1.2 DDA算法

数字微分分析仪(digital differential analyzer,DDA)方法
依照式(6.4),(6.5)进行递推计算。

算法过程如下：
1. 输入线段两个端点的位置
2. 端点位置间水平和垂直的插值赋给参数$dx$和$dy$。
3. 绝对值大的参数确定参数$steps$的值。该值是在即将划出的的这条线段的上的像素数目
4. 按照这个数值，沿线段路径计算每一步的下一个像素位置

#include<stdlib.h>
#include<math.h>
inline int round (const float a) {return int (a + 0.5); }
void lineDDA (int x0, int y0, int xEnd, int yEnd ){
    int dx = xEnd - x0, dy = yEnd - y0 , steps, k;
    float xIncrement, yIncrement, x = x0, y = y0;
    if(fabs (dx) > fabs (dy))
        steps = fabs (dx);
    else
        steps = fabs (dy);
    xIncrement = float (dx) / float (steps);
    yIncerment = float (dy) / float (steps);
    setPixel (round (x), round (y));
    for (k = 0; k < steps; k++){
        x += xIncrement;
        y += yIncrement;
        setPixel (round(x), round(y));
    }
}

DDA方法计算比直接使用方程（6.1）计算的速度快。它利用光栅特性消除了直线方程中的乘法，二在x或y方向使用合适的增量，从而沿线路径逐步得到个像素的位置。但在浮点增量的连续叠加中，取整误差的积累使得对于较长线段所计算的像素位置偏离实际线段。而且算法中所采用的浮点数计算和取整操作都较费时。我们可以将增量m和1/m分离成整数和小数部分，从而使所有的计算都化简为整数操作来改善DDA算法的性能。

6.1.3 Bresenham画线算法

Bresenham 算法仅使用增量整数计算。

Bresenham 算法思想描述。
从给定的 $(x_0,y_0)$处开始，逐步处理每个后继列(x位置),并在其扫描线y值最接近线段的像素上绘出一点。假如已经决定要显示的像素在$(x_k,y_k)$,那么下一步需要确定在列$x_{k+1} = x_k + 1$上绘制哪个像素，是在位置$(x_k-1, y_k)$,还是在位置$(x_k+1,y_k+1)$。

在取样位置x_k + 1, 我们使用$d_{lower}$和$d_{upper}$来标识两个像素与数学上线路径的垂直便宜，在像素列位置$x_k + 1$处的直线上的y坐标可计算为:

$$y = m (x_k + 1) + b;$$
那么
$$\begin{align} d_{lower} & = y - y_k \notag \\ & = m(m_k + 1) + b - y_k \tag{6.12} \end{align}$$
下一步确定哪一个像素更接近路径，测试这两个像素偏移的差：
$$d_{lower} - d_{upper} = 2m(x_k + 1) - 2y_k + 2b - 1 \tag{6.13}$$
重新安排上式，得到画线算法第k步的决策参数$p_k$,从而可以仅使用整数进行计算。
设$\Delta x和\Delta y$分别是两端点的垂直和水平偏移量，令$m = \frac{\Delta y }{\Delta x}$,决定参数定义为
$$\begin{align} p_k & = \Delta x(d_{lower} - d_{upper} ) \notag \\ & = 2 \Delta y \cdot x_k - 2 \Delta \cdot y_k + c \tag{6.14} \\ 其中 \notag \\ c & = 2 \Delta y + \Delta x (2b - 1) \notag \end{align}$$
在k+1步，决策参数可以从式(6.14)计算得出:
$$p_{k+1} = 2 \Delta y \cdot x_{k+1} - 2 \Delta x \cdot y_{k+1} + c$$
上式减去式(6.14)得到
$$p_{k+1} - p_k = 2 \Delta y (x_{k+1} - x_k) - 2 \Delta (y_{y+1} - y_k)$$
但是 $x_{k+1} = x_k + 1$,因而得到
$$p_{k+1} = p_k + 2 \Delta y - 2 \Delta x(y_{k+1} - y_k)$$
其中$y_{k+1} - y_k$取值0或1，取决于参数$p_k$的符号

决策参数的递归计算从线段左端点开始的每个整数x位置进行。起始像素位置$(x_0,y_0)$的第一个参数$p_0$通过方程(6.14) 及$m = \Delta y / \Delta x$计算得出

$$p_0 = 2 \Delta y - \Delta x$$

$|m|\lt 1$时的Bresenham画线算法:
1. 输入线段的两个端点，并将做端点存储在$(x_0,y_0)$中
2. 将$(x_0,y_0)$装入帧缓存，画出第一个点
3. 计算常量$\Delta x、\Delta y、2\Delta y - 2 \Delta x$,并得到决策参数的第一个值:

$$p_0 = 2 \Delta y - \Delta x$$
4. 从 $k = 0$开始，在沿线段庐江的每个$x_k$处，进行下列检测：
如果$p_k \lt 0$，下一个要绘制的点是$(x_k + 1, y_k)$，并且
$$p_{k+1} = p_k + 2 \Delta y$$
否则，下个要绘制的点是$(x_k + 1, y_k + 1)$,并且
$$p_{k+1} = p_k + 2 \Delta y - 2 \Delta x$$
5. 重复步骤4，共$\Delta x - 1$ 次

上述算法第四步一共执行 $\Delta x$ 次

下面程序给出了斜率为0 < m < 1.0 的 Bresenham 画线算法的实现。首先将线段的端点像素位置输入程序，然后从左到右端点绘制像素。

#include<stdlib.h>
#include<math.h>
/*Bresenham line_drawing procedure for |m| < 1.0 */
void lineBres(int x0, int y0, int xEnd, int yEnd){
    int dx = fabs (xEnd - x0), dy = fabs (yEnd - y0);
    int p = 2 * dy - dx;
    int twoDy = 2 * dy , twoDyMinusDx = 2 * (dy - dx);
    int x, y;
    if ( x0 > xEnd) {
        x = xEnd;
        y = yEnd;
        xEnd = x0;
    }
    else {
        x = x0;
        y = y0;
    }
    setPixel (x, y);
    while(x < xEnd){
        x++;
        if (p < 0)
            p += twoDy;
        else{
            y++;
            p += twoDyMinusDx;
        }
        setPixel (x,  y);
    }
}

6.1.4 显示折线

通过n-1次调用画线函数实现折线的显示。

6.2 平行画线法