计算机图形学笔记——画直线算法

@(计算机图形学)[学习笔记]

[TOC]

画线算法主要用来解决如下问题：对于某个直线方程，已知起点重点，计算机如何绘制出这个线段。计算机绘制线段其实就是绘制一系列的像素点。

DDA算法

思路: 对于直线方程 \(y = kx + b\)， 在一个坐标轴以单位长度步进，并计算得到另一坐标轴的步进，之后根据起点+步进得到一个点的坐标，这个点就是需要绘制的点。为了保证绘制的精度，选择步进较大的坐标轴为基础坐标轴，例如每次步进​$\Delta x > \Delta y $, 那么以x轴为单位长度步进的坐标轴。

实现代码：

    //四舍五入 
    inline int round(float a) {return int(a+0.5f)}  

    void lineDDA(int startX, int startY, int endX, int endY)
    {
        float dx = endX - startX;
        float dy = endY - startY;
        float steps = fabs(dx) > fabs(dy) ? fabs(dx) : fabs(dy);
        float incX = dx / steps;
        float incY = dy / steps;

        for (int i = 0; i <= steps; i++)
        {
            float newX = (float)startX + (float)(i) * incX;
            float newY = (float)startY + (float)(i) * incY;
            drawPixel(round(newX), round(newY)); //画像素点
        }
    }

通过代码也可以看到，运算使用了浮点运算,取整，不利于用硬件实现。

Bresenham算法

同DDA算法一样选择步进坐标轴，我们假设步进坐标轴为\(x\)轴，即斜率 \(|k| < 1\), 因为绘制的像素点坐标必须是整数， 那么对于\((x_n, y_n)\)的下一个点\((x_{n+1}, y_{n+1})\)，有\(x_{n+1} = x_n + 1\), \(y_{n+1} < 1\) , 该点绘制的像素坐标会是\((x_n + 1, y_n)\)， \((x_n + 1, y_n+1)\)中的一个。

每次绘制下一个点时，我们期望有这样一个变量\(p_n\), 如果\(p_n > 0\)下一个点的坐标为 \((x_n + 1, y_n+1)\)，否则下一个点的坐标为\((x_n + 1, y_n)\)。

我们期望绘制的像素点离实际的坐标点距离越小越好，那么两个候选的像素坐标到实际坐标的距离分别为： \(d_{upper}​\) = \(y_n+1 - y_{n+1}​\)
\(d_{lower}​\) = \(y_{n+1} - y_n​\)

对于直线方程\(y = kx + b\)：
\(\Delta d = d_{lower} - d_{upper} = 2y_{n+1} - 2y_n -1 = 2(kx_{n+1} + b) - 2y_n -1\)

其中\(x_{n+1} = x_n + 1​\), 推导可得： \(\Delta d = 2(kx_n - y_n) + 2k + 2b - 1​\) 注意：不能再继续用\(y_n = kx_n + b​\)代如上式推导下去了，因为点\((x_n, y_n)​\)不一定精确地在直线上。

如果\(\Delta d > 0​\), 那么下个点取\((x_n + 1, y_n+1)​\)会准确一些，反之亦然，但\(\Delta d​\)还不能作为变量\(p_n​\)使用，因为计算还存在浮点运算和除法。

到这一步的式子中，为了消除\(k\)这个存在除法运算的变量，我们可以用\(k = \frac{X_{end} - X_{start}}{ Y_{end} - Y_{start}} = \frac{\Delta y}{\Delta x}\) 代如上式, 然后等式两边同时乘以\(\Delta x\)可得：

\(\Delta x \Delta d = 2(\Delta y x_n - \Delta x y_n) + 2\Delta y + 2b\Delta x - \Delta x = 2(\Delta y x_n - \Delta x y_n) + c​\)

因为\(\Delta x​\)在我们的设定中始终大于0， 这样我们就得到了需要的变量\(p_n = \Delta x \Delta d​\)，计算该变量无需浮点运算和除法。

进一步，我们可以通过\(p_n​\) 和\(p_{n+1}​\)的关系来继续简化运算：

\(p_{n+1} - p_n = 2(\Delta y(x_{n+1} - x_n) - \Delta x(y_{n+1} - y_n)) = 2(\Delta y - \Delta x(y_{n+1} - y_n))​\)

其中\(y_n+1\), \(y_n\)是我们要话的两个像素点，它们的差为\(0\)或者\(-1\), 得到：

其中： \(p_0 = 2(\Delta y x_n - \Delta x y_n) + c = 2(\Delta y x_n - \Delta x (\frac{\Delta y}{\Delta x} x_0 + b)) + c = 2\Delta y - \Delta x​\)

下面给出斜率\(|k| < 1\)的代码：

    void lineBresenham(int startX, int startY, int endX, int endY)
    {
        int x = startX;
        int y = startY;
        if (x > endX) //保证dx > 0
        {
            x = endX;
            endX = startX;
            y = endY;
            endY = startY;
        }

        int dx = endX - x;
        int dy = endY - y;
        int p = 2*dy - dx;

        drawPixel(x, y);

        while(x < endX)
        {
            x++;
            if (p > 0)
            {
                y++;
                p += 2 * (dy - dx);
            }
            else
            {
                p += 2 * dy;
            }
            drawPixel(x, y);
        }
    }

当\(|k|>1\)时，选择y方向的步进即可，对于一些特殊斜率，如0， 1， 无穷大，直接使用特殊处理会更简单。