图形学自问自答1——直线光栅化

作者: 太刀 | 来源:发表于2021-01-28 00:09 被阅读0次

《底特律变人》角色卡拉

如何在屏幕上画线段

光栅化是一个连续数据离散化的过程，而最简单的一个连续数据离散化的过程是如何将一条线段在屏幕中画出来

注：为简化分析和处理，本文只考虑斜率 $k>=0$ 的直线，对于 $k<0$ 的情形，可以很容易添加对应的代码进行处理。

1. 直接计算算法

直接根据直线的斜率表达式 $y=kx+b$ 来计算，若在水平方向的变化更大，则针对每个x计算对应的y，否则针对每个y计算对应的x，然后绘制像素即可。代码如下：

    // 暴力算法
    public void DrawLineSimple(Vector2 start, Vector2 end, Color color)
    {
        int startX = Mathf.RoundToInt(start.x);
        int endX = Mathf.RoundToInt(end.x);
        int startY = Mathf.RoundToInt(start.y);
        int endY = Mathf.RoundToInt(end.y);

        // 无法计算斜率k的情况
        if (startX == endX)
        {
            int x = Mathf.RoundToInt(start.x);
            for (int i = startY; i <= endY; i++)
            {                
                screen.SetPixel(x, i, color);
            }
        }
        else
        {
            float k = (end.y - start.y) / (end.x - start.x);
            float b = end.y - k * end.x;
            
            if (0<k && k<1) // 只考虑这个斜率范围，其它情况修改参数可以很简单实现
            {
                for (int i = startX; i <= endX; i++)
                {
                    int y = Mathf.RoundToInt(i * k + b);
                    screen.SetPixel(i, y, color);
                }
            }            
        }
    }

2. DDA 算法

在上面的直接计算算法中，应用公式 $y=kx+b$ 考虑在对x进行行进时，有 $y_{n+1}=kx_{n+1}+b=k(x_n+1)+b=kx_n+b+k=y_n+k$ 也就是
$y_{n+1}=y_n+k$ 将乘法消灭了，算法只剩下加法，代码如下：

    // DDA 算法
    public void DrawLineDDA(Vector2 start, Vector2 end, Color color)
    {
        int startX = Mathf.RoundToInt(start.x);
        int endX = Mathf.RoundToInt(end.x);
        int startY = Mathf.RoundToInt(start.y);
        int endY = Mathf.RoundToInt(end.y);

        // 无法计算斜率k的情况
        if (startX == endX)
        {
            int x = Mathf.RoundToInt(start.x);
            for (int i = startY; i <= endY; i++)
            {           
                screen.SetPixel(x, i, color);
            }
        }
        else
        {
            float k = (end.y - start.y) / (end.x - start.x);
            float b = end.y - k * end.x;
            if (0 < k && k < 1) // 只考虑这个斜率范围，其它情况修改参数可以很简单实现
            {
                float y = start.y;
                for (int i = startX; i <= endX; i++)
                {
                    y += k;
                    screen.SetPixel(i, Mathf.RoundToInt(y), color);
                }
            }
        }
    }

3. 中点画线算法

画线示意

考虑图中的直线，假设目前已经把紫色点像素画出来了，假如最近一个绘制的紫色像素坐标为 $(x,y)$ ，下一个绘制的像素是两个黄色二选一，坐标分别为 $(x+1,y+1)$ 和 $(x+1,y)$ ，那么如何来确定该绘制哪一个呢？考虑两个黄色像素坐标的中点 $(x+1,y+0.5)$ 也就是图中黑圈的位置和直线的关系，可以得到如下结论：

若中点在直线上方，则画 $(x+1,y)$
否则画 $(x+1,y+1)$

如何判定一个点与直线的关系呢？我们已经知道直线的斜率公式为 $y=kx+b$ 定义函数 $f(x,y)=kx-y+b$ 考虑 $0<k<1$ 的情况，当 $f(x,y)=0$ 时点 $(x,y)$ 在落在直线中，当 $f(x,y)>0$ 时点在直线上方， $f(x,y)<0$ 时点在直线下方。在确定画 $(x+1,y)$ 还是 $(x+1,y+1)$ 时，我们把中点 $(x+1,y+0.5)$ 代入 $f(x,y)$ 中计算，根据结果进行选择即可。代码如下：

// 中点划线算法
    public void DrawLineMidline(Vector2 start, Vector2 end, Color color)
    {
        int startX = Mathf.RoundToInt(start.x);
        int endX = Mathf.RoundToInt(end.x);
        int startY = Mathf.RoundToInt(start.y);
        int endY = Mathf.RoundToInt(end.y);

        // 无法计算斜率k的情况
        if (startX == endX)
        {
            int x = Mathf.RoundToInt(start.x);
            for (int i = startY; i <= endY; i++)
            {
                screen.SetPixel(x, i, color);
            }
        }
        else
        {
            float k = (end.y - start.y) / (end.x - start.x);
            float b = end.y - k * end.x;

            if (0 < k && k < 1) // 只考虑这个斜率范围，其它情况修改参数可以很简单实现
            {
                screen.SetPixel(startX, startY, color);
                int y = startY;
                for (int i = startX; i < endX; i++)
                {
                    float value = this.GetLineValue(i, startY + 0.5f, k, b);
                    if (value < 0)
                    {
                        y = y + 1;                        
                    }
                    screen.SetPixel(i, Mathf.RoundToInt(y), color);
                }
            }
        }
    }

    private float GetLineValue(float x, float y, float k, float b)
    {
        return y - k * x + b;
    }

4. Bresenham 算法

中点划线算法中，频繁调用 $f(x,y)$ 的计算，比较消耗。我们可以对直线对一般表达式 $f(x,y)$ 进行一番推导，在 $0<k<1$ 的斜率范围内，我们是从起点开始，对 $x$ 递增计算对应的 $y$ 坐标来确定要绘制的像素，将起点 $(x_0,y_0)$ 和终点 $(x_1,y_1)$ 带入，可以得到 $k=\frac {(y_1-y_0)}{(x_1-x_0)}$ 和 $b=y_1-x_1\frac{(y_1-y_0)}{(x_1-x_0)}$
从斜率公式 $y=kx+b$ 很容易得到直线的一般表示 $f(x,y)=kx-y+b$ 将 $k$ 和 $b$ 带入上式，不难推导出 $f(x,y)=(y_0-y_1)x+(x_1-x_0)y+x_0y_1-x_1y_0$
那么就可以得到 $f(x+1,y)=f(x,y)+(y_0-y_1)$ $f(x+1,y+1)=f(x,y)+(y_0-y_1)+(x_1-x_0)$ 算法只需要计算出 $f(x+1,y+0.5)$ ，后续不再需要乘法，只要加上相应对量就可以了，得到算法

public void DrawLineBresenham(Vector2 start, Vector2 end, Color color)
    {
        int startX = Mathf.RoundToInt(start.x);
        int endX = Mathf.RoundToInt(end.x);
        int startY = Mathf.RoundToInt(start.y);
        int endY = Mathf.RoundToInt(end.y);

        // 无法计算斜率k的情况
        if (startX == endX)
        {
            int x = Mathf.RoundToInt(start.x);
            for (int i = startY; i <= endY; i++)
            {
                screen.SetPixel(x, i, color);
            }
        }
        else
        {
            float k = (end.y - start.y) / (end.x - start.x);
            float b = end.y - k * end.x;

            if (0 < k && k < 1) // 只考虑这个斜率范围，其它情况修改参数可以很简单实现
            {
                screen.SetPixel(startX, startY, color);
                float d = GetLineValue(startX, startY + 0.5f, k, b);
                int y = startY;
                for (int i = startX; i < endX; i++)
                {
                    if (d < 0)
                    {
                        d += (endX - startX) + (startY - endY);
                        y = y + 1;
                    }
                    else
                    {
                        d += (startY - endY);
                    }
                    
                    screen.SetPixel(i, Mathf.RoundToInt(y), color);
                }
            }
        }
    }

图形学自问自答1——直线光栅化

如何在屏幕上画线段

1. 直接计算算法

2. DDA 算法

3. 中点画线算法

4. Bresenham 算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读