画线和画三角形方法

本文最后更新于：2025年4月17日下午

画线算法

DDA画线

直线方程表示为 $y = kx + b$

当 $\lVert k \rVert <= 1$时，$x$ 每递增$1$，$y$ 递增$k$。

当 $\lVert k \rVert \geq 1$时，$x$ 每递增$1/k$，$y$ 递增$1$。

因为光栅化不能绘制半个像素点，所以求出的值需要进行四舍五入即加 0.5 后再进行取整。

DDA 算法是一个增量算法，它直观且容易实现，然而 $x$ 和 $y$ 都必须用浮点值表示，而且每一步都需要对 $y$ 进行舍入取整，不利于硬件实现。

void DrawLine_DDA(int x1,int y1,int x2,int y2){
    int dx = x2 - x1;
    int dy = y2 - y1;

    int step = 0;
    if(Math.Abs(dy) > Math.Abs(dx)){
        step = Math.Abs(dy);
    }
    else{
        step = Math.Abs(dx);
    }

    float stepX = 1.0f * dx / step;
    float stepY = 1.0f * dy / step;

    int i = 0;
    float x = x1;
    float y = y1;
    DrawPoint((int)x, (int)y);
    while ((i++)<step){
        x += stepX;
        y += stepY;
        DrawPoint((int)x, (int)(y+0.5f));
    }
}

Bresenham画线

Bresenham 算法只用 int 类型的加减和比较来绘制直线，大大降低了需要的计算资源。

它的思路是：水平直线、竖直直线单独处理，剩余的部分等分为 8 个区域，然后从最简单的斜率大于 0 小于 1 的部分开始，剩下的 7 个部分稍作修改即可。

当斜率大于 0 小于 1 时，起始点为 ($x_0$, $y_0$)，终点为 ($x_1$, $y_1$)，我们遍历横坐标，找出每个横坐标对应的纵坐标。$x_{0+i}$ 对应的纵坐标应该为 $y_0 + i \times slope$，四舍五入获得的像素坐标为：int($y_0 + i \times slope + 0.5$)

由于斜率大于 0 小于 1，相邻横坐标对应的纵坐标最多加 1。比如 $x_{0+1}$ 处的纵坐标要么还是 $y_0$，要么是 $y_{0+1}$。绝不可能是 $y_{0+2}$

然而 Bresenham 算法是想避免 float 类型的运算和比较。以 $x_{0+1}$ 为例：

$1 \times slope < 0.5$ 则四舍，$1 \times slope \geq 0.5$ 则五入。然而实际判断 $1 \times slope < 0.5$ 等价于 $2 \times slope < 1$，等价于 $2 \times \Delta y < \Delta x$，等价于 $2 \times \Delta y - \Delta x < 0$，这时则完全没有 float 类型计算和比较了。($\Delta y = y_1 - y_0, \Delta x = x_1 - x_0$)。

若 $2 \times \Delta y - \Delta x < 0$，则 $y(x_{0+1}) = y_0$，

否则 $y(x_{0+1}) = y_{0+1}$

接着再考虑 $x_{0+2}$ 处，

若前一个像素自右上方衍生出，需要比较 $2 \times slope < 1.5$，等价于 $4 \times \Delta y - 3 \times \Delta x < 0$，注意 $4 \times \Delta y - 3 \times \Delta x = 2 \times \Delta y - \Delta x + (2 \times \Delta y - 2 \times \Delta x)$

若前一个像素自右方衍生出，需要比较 $2 \times slope < 0.5$，等价于 $4 \times \Delta y - \Delta x < 0$，注意 $4 \times \Delta y - \Delta x = 2 \times \Delta y - \Delta x + (2 \times \Delta y)$

同样的思路可以一直推下去直到线段的末尾。

public void DrawLine_Bresenham(int x0, int x1, int y0, int y1)
{
    bool steep = false;
    if(Math.Abs(x0 - x1) < Math.Abs(y0 - y1))
    {
        TempSwap(ref x0, ref y0);
        TempSwap(ref x1, ref y1);
        steep = true;
    }

    if(x0 > x1)
    {
        TempSwap(ref x0, ref x1);
        TempSwap(ref y0, ref y1);
    }

    int dx = x1 - x0;
    int dy = y1 - y0;

    int derror = Math.Abs(dy) * 2;
    int error = 0;
    int y = y0;

    for(int x = x0; x <= x1; x++)
    {
        if (steep)
        {
            DrawPoint(y, x);
        }
        else
        {
            DrawPoint(x, y);
        }

        error += derror;
        
        if (error > dx)
        {
            y += (y1 > y0 ? 1 : -1);
            error -= dx * 2;
        }
    }
}

中点画线

如下图

其中，
$$
\begin{aligned}
P &= p_0 + (P_1 - P_0)t\
&= P_0 - tP_0 + tP_1\
&= (1 - t)P_0 + tP_1
\end{aligned}
$$

那么
$$
f(x) = (1 - t) \times f(x_0) + t \times f(x_1)
$$

直线隐函数方程为：
$$
F(x, y) = y - kx - b = 0
$$

假设已经确定了要显示的点 ($x_i$, $y_i$)，那么需要确定下一个点绘制的位置，这里需要用到中点误差项。

$$
d_i = F(x_i + 1, y_i + 0.5) = y_i + 0.5 - k(x_i + 1) - b
$$

$$
y_{i+1} = \begin{cases}
y_i + 1, (d_i < 0)\
y_i,\quad(d_i \geq 0)
\end{cases}
$$

当 $d_i < 0$ 时，
$$
\begin{aligned}
d_{i+1} &= F(x_i + 2, y_i + 1.5)\
&= y_i + 1.5 - k(x_i + 2) - b\
&= y_i + 0.5 - k(x_i + 1) - b + 1 - k\
&= d_i + 1 - k
\end{aligned}
$$

当 $d_i \geq 0$ 时，
$$
\begin{aligned}
d_{i+1} &= F(x_i + 2, y_i + 0.5)\
&= y_i + 0.5 - k(x_i + 2) - b\
&= y_i + 0.5 - k(x_i + 1) - b - k\
&= d_i - k
\end{aligned}
$$

当 $d_i < 0$ 时，$d_{i+1} = d_i + 1 - k$，当 $d_i \geq 0$ 时，$d_{i+1} = d_i - k$

中点误差项初始值为：
$$
\begin{aligned}
d_0 &= F(x_0 + 1, y_0 + 0.5)\
&= y_0 + 0.5 - k(x_0 + 1) - b\
&= y_0 - kx - b - k + 0.5\
&= 0.5 - k
\end{aligned}
$$

接下来，我们需要进行整数化处理：

令 $d$ 乘以 $2\Delta x$ 得到 $e$，误差项正负值不变，不会影响 $y$ 的增量
$$
e = 2d\Delta x
$$
此时误差项初始值为：
$$
e_0 = 2d_0\Delta x = 2(0.5 - k)\Delta x = \Delta x - 2\Delta y
$$

此时误差项的递推公式为：
$$
\begin{aligned}
e < 0, e &= 2(d + 1 - k)\Delta x = 2d\Delta x + 2\Delta x - 2k\Delta x = e + 2\Delta x - 2\Delta y\
e \geq 0, e &= 2(d - k)\Delta x = 2d\Delta x - 2k\Delta x = e - 2\Delta y
\end{aligned}
$$

$$
e_{i+1} = \begin{cases}
e_i + 2\Delta x - 2\Delta y, (e < 0)\
e_i - 2\Delta y,\quad(e \geq 0)
\end{cases}
$$

那么此时进行画线操作，从 $P_0$ 开始到 $P_1$ 点沿 $x$ 轴方向，判断 $e$ 的符号来绘制点 ($x$, $y$)，若 $e < 0$，将点更新为 ($x+1$, $y+1$)，$e = e + 2\Delta x - 2\Delta y$；否则将点更新为 ($x+1$, $y$)，$e = e - 2\Delta y$

void DrawLine_MidPoint(int x0,int y0,int x1,int y1)
{
    bool bInterchange = false;

	int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int signx = x0 < x1 ? 1: -1;
    int signy = y0 < y1 ? 1: -1;

    if(dy > dx){
        int temp = dy;
        dy = dx;
        dx = temp;
        bInterchange = true;
    }
	
    int e = dx - 2 * dy;
    int x = x0;
    int y = y0;
    for(int i = 1; i <= dx; i++){
        DrawPoint(x, y);
        if(bInterchange){
            y += signy;
        }else{
            x += signx;
        }

        if(e < 0){
            if(bInterchange){
                x += signx;
            }else{
                y += signy;
            }
            e += 2 * dx - 2 * dy;
        }else{
            e -= 2 * dy;
        }
    }
	 
}

画三角形方法

利用线性插值画三角形

让我们假设三角形的三个点 t0，t1, t2，通过 y 坐标的大小排序成升序。那么，边界 A 在是 t0 和 t2 之间的线段，边界 B 是 t0 和 t1 之间线段，最后的在 t1 和 t2 之间的线段。以高度差作为循环控制变量，从左到右对相同高度的像素进行着色。

void DrawTriangle1(Point t0, Point t1, Point t2)
{
    //三角形的三个点y值相同，面积为0
    if (t0.y == t1.y && t1.y == t2.y) return;
    //根据y值大小对坐标进行排序
    if (t0.y > t1.y)
    {
        TempSwap(ref t0, ref t1);
    }
    if (t0.y > t2.y)
    {
        TempSwap(ref t0, ref t2);
    }
    if (t1.y > t2.y)
    {
        TempSwap(ref t1, ref t2);
    }

    int total_height = t2.y - t0.y;
    //以高度差作为循环控制变量，此时不需要考虑斜率，因为着色完后每行都会被填充
    for (int i = 0; i < total_height; i++)
    {
        bool second_half = i > t1.y - t0.y || t1.y == t0.y;

        int segment_height = second_half ? t2.y - t1.y : t1.y - t0.y;
        float alpha = (float)i / total_height;
        float beta = (float)(i - (second_half ? t1.y - t0.y : 0)) / segment_height;
        //计算A，B两点的坐标
        Point A = t0 + (t2 - t0) * alpha;
        Point B = second_half ? t1 + (t2 - t1) * beta : t0 + (t1 - t0) * beta

        if (A.x > B.x)
        {
            TempSwap(ref A, ref B);
        }

        for (int j = A.x; j <= B.x; j++)
        {
            float phi = B.x == A.x ? 1f : (float)(j - A.x) / (float)(B.x - A.x);
            Point P = A + (B - A) * phi;
            DrawPoint(P.x, P.y);
        }
    }
}

利用叉乘画三角形

对于三角形 $\triangle ABC$ 来说，把三条边看作 $\overset{\longrightarrow}{AB}$、$\overset{\longrightarrow}{BC}$、$\overset{\longrightarrow}{CA}$ 三条首尾相连的向量，平面内有一个点 $P$，我们通过向量叉乘来判断相对位置。

对二维向量叉乘做一个定义：

假设有两个二维向量 $\vec{a}$ 和 $\vec{b}$，我们把它们视为三维向量，$z$ 轴补 0，那么这个时候的 $\vec{a}$ 和 $\vec{b}$ 叉乘的结果为 $\vec{c}$，$\vec{c}$ 的 $x$ 值为 0， $y$ 值为 0， $z$ 值为 $a.x \times b.y - b.x \times a.y$，这个时候可以吧二维向量的叉乘定义为得到一个值，即为 $\vec{c}$ 的 $z$ 值。

如果 $z$ 值大于 0，表示 $\vec{b}$ 在 $\vec{a}$ 的左侧
如果 $z$ 值小于 0，表示 $\vec{b}$ 在 $\vec{a}$ 的右侧
如果 $z$ 值等于 0，表示 $\vec{b}$ 与 $\vec{a}$ 共线

$\overset{\longrightarrow}{AB} \times \overset{\longrightarrow}{AP}$，值为正，则 $P$ 在 $AB$ 左侧
$\overset{\longrightarrow}{BC} \times \overset{\longrightarrow}{BP}$，值为正，则 $P$ 在 $BC$ 左侧
$\overset{\longrightarrow}{CA} \times \overset{\longrightarrow}{CP}$，值为正，则 $P$ 在 $AC$ 左侧

综合以上三个条件，我们可以判断 $P$ 在 $\triangle ABC$ 内。如果三个计算中有值为负的情况，说明 $P$ 在 $\triangle ABC$ 外。如果有值为 0 的情况，说明 $P$ 在 $\triangle ABC$ 的边或顶点上。


Vector3 crossProduct(Point[] points, Point P)
{
    Vector2 AB = new Vector2(points[1].x - points[0].x, points[1].y - points[0].y);
    Vector2 BC = new Vector2(points[2].x - points[1].x, points[2].y - points[1].y);
    Vector2 CA = new Vector2(points[0].x - points[2].x, points[0].y - points[2].y);

    Vector2 AP = new Vector2(P.x - points[0].x, P.y - points[0].y);
    Vector2 BP = new Vector2(P.x - points[1].x, P.y - points[0].y);
    Vector2 CP = new Vector2(P.x - points[2].x, P.y - points[0].y);

    return new Vector3(AB.x * AP.y - AP.x * AB.y, BC.x * BP.y - BP.x * BC.y, CA.x * CP.y - CP.x * CA.y);
}

void DrawTriangle2(Point[] points)
{
    Vector2 bboxmin = new Vector2(float.MaxValue,float.MaxValue);
    Vector2 bboxmax = new Vector2(float.MinValue,float.MinValue);
    Vector2 clamp = new Vector2(canvas.Width - 1, canvas.Height - 1);

    for(int i = 0; i < 3; i++)
    {
        bboxmin.x = Math.Max(0f, Math.Min(bboxmin.x, points[i].x));
        bboxmin.y = Math.Max(0f, Math.Min(bboxmin.y, points[i].y));
        bboxmax.x = Math.Min(clamp.x, Math.Max(bboxmax.x, points[i].x));
        bboxmax.y = Math.Min(clamp.y, Math.Max(bboxmax.y, points[i].y));
    }

    Point p;
    for(p.x = (int)Math.Ceiling(bboxmin.x); p.x <= (int)Math.Floor(bboxmax.x); p.x++){
        for(p.y = (int)Math.Ceiling(bboxmin.y); p.y <= (int)Math.Floor(bboxmax.y); p.y++){
            Vector3 cross = crossProduct(points, p);
            if(cross.x < 0 || cross.y < 0 || cross.z < 0)
                continue;
            DrawPoint(p.x, p.y);
        }
    }
}

利用三角形重心画三角形

有关于三角形重心的介绍可以参考上一篇博文，下面给出代码

public Vector3 CrossProduct(Vector3 v1, Vector3 v2)
{
    return new Vector3(
        v1.y * v2.z - v1.z * v2.y,
        v1.z * v2.x - v1.x * v2.z,
        v1.x * v2.y - v1.y * v2.x);
}

public Vector3 Barycentric(Point A, Point B, Point C, Point P)
{
    Vector3 x = new Vector3(B.x - A.x, C.x - A.x, A.x - P.x);
    Vector3 y = new Vector3(B.y - A.y, C.y - A.y, A.y - P.y);
    Vector3 u = CrossProduct(x, y);

    if (Math.Abs(u.z) > float.Epsilon)
    {
        return new Vector3(1f - (u.x + u.y) / u.z, u.y / u.z, u.x / u.z);
    }
    return new Vector3(-1, 1, 1);

}

void DrawTriangle3(Point[] points)
{
    Vector2 bboxmin = new Vector2(float.MaxValue,float.MaxValue);
    Vector2 bboxmax = new Vector2(float.MinValue,float.MinValue);
    Vector2 clamp = new Vector2(canvas.Width - 1, canvas.Height - 1);

    for(int i = 0; i < 3; i++)
    {
        bboxmin.x = Math.Max(0f, Math.Min(bboxmin.x, points[i].x));
        bboxmin.y = Math.Max(0f, Math.Min(bboxmin.y, points[i].y));
        bboxmax.x = Math.Min(clamp.x, Math.Max(bboxmax.x, points[i].x));
        bboxmax.y = Math.Min(clamp.y, Math.Max(bboxmax.y, points[i].y));
    }

    Point p;
    for(p.x = (int)Math.Ceiling(bboxmin.x); p.x <= (int)Math.Floor(bboxmax.x); p.x++)
    {
        for(p.y = (int)Math.Ceiling(bboxmin.y); p.y <= (int)Math.Floor(bboxmax.y); p.y++)
        {
            Vector3 bc_screen = Barycentric(points[0], points[1], points[2], p);
            if (bc_screen.x < 0f || bc_screen.y < 0f || bc_screen.z < 0f) continue;
            DrawPoint(p.x, p.y);
        }
    }
}

Computer Graphics

#Math

画线和画三角形方法

http://example.com/posts/画线和画面算法/

作者

祭零小白

发布于

2022年9月4日

许可协议

LearnVim 上一篇

三角形重心坐标下一篇