TinyRenderer笔记0：画线和三角以及面剔除

kirito 收录于类别 program

2022-01-01 2022-07-03 约 2660 字预计阅读 6 分钟次阅读条评论

这篇是自己学习tinyrenderer的笔记，不务正业系列。

tinyrenderer教程地址：https://github.com/ssloy/tinyrenderer/wiki

作者教程是用cpp实现的，我用rust来学，列一下用到的库：

image - 这是个图片库，充当画布，控制每个像素的颜色，生成图片
obj-rs - 解析obj文件的库，关于obj文件可以看Wavefront OBJ文件格式，里面存的是一些模型顶点
glm - 数学库，比如坐标表示，计算向量点乘、叉乘，矩阵运算

准备画布

用image库操作图片的每个像素，生成图片：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


use image::{imageops::flip_vertical_in_place, ImageBuffer, Rgba};

const WHITE: Rgba<u8> = Rgba([255, 255, 255, 255]);
const RED: Rgba<u8> = Rgba([255, 0, 0, 255]);

fn main() {
    let (width, height) = (400, 400);
    let mut image = ImageBuffer::<Rgba<u8>, _>::from_pixel(width, height, BLACK);

    for x in 0..200 {
        for y in 0..200 {
            image.put_pixel(x, y, RED);
        }
    }

    flip_vertical_in_place(&mut image); // 垂直反转，因为默认坐标原点在左上角，反转后在左下角
    image.save("a.png").unwrap();
}

画线

画线比较简单，思路是对于线段ab，从a出发到b一路画点，x坐标每次移动一个像素，然后计算y坐标应该移动多少，还有一些细节直接看代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


fn line<I: GenericImage>(mut a: glm::IVec2, mut b: glm::IVec2, image: &mut I, color: I::Pixel) {
    let mut steep = false;
    if (a.x - b.x).abs() < (a.y - b.y).abs() {
        // 如果这条线是陡峭的，就交换x，y让它躺平
        swap(&mut a.x, &mut a.y);
        swap(&mut b.x, &mut b.y);
        steep = true;
    }
    if a.x > b.x {
        // make it left−to−right
        swap(&mut a, &mut b);
    }
    let dx = b.x - a.x;
    let dy = b.y - a.y;
    let derror = (dy as f64 / dx as f64).abs();
    let mut error = 0.0;
    let mut y = a.y;
    for x in a.x..=b.x {
        if steep {
            image.put_pixel(y as u32, x as u32, color);
        } else {
            image.put_pixel(x as u32, y as u32, color);
        }
        error += derror;
        if error > 0.5 {
            y += if b.y > a.y { 1 } else { -1 };
            error -= 1.0;
        }
    }
}

如果这条线很陡峭，那么x坐标移动一个像素，对应的y坐标可能要移动好几个像素，画出来不连续，所以让它躺平。

然后我们从左到右画，dy/dx算出斜率，比如斜率是0.5，那么x移动一个像素，y应该移动0.5个像素。

因为像素不能分割，所以按照四舍五入的方式，y的变化积攒到一定量再移动一个单位。

看着已经很完美了，但是里面有浮点数，可以根据简单的代换，消除浮点数：我们让derror = derror' * 2dx = 2dy，那么error > 0.5变成error > dx，error -= 1.0变成error -= 2dx，这样一来就全是整数计算：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


fn line<I: GenericImage>(mut a: glm::IVec2, mut b: glm::IVec2, image: &mut I, color: I::Pixel) {
    let mut steep = false;
    if (a.x - b.x).abs() < (a.y - b.y).abs() {
        // if the line is steep, we transpose the image
        swap(&mut a.x, &mut a.y);
        swap(&mut b.x, &mut b.y);
        steep = true;
    }
    if a.x > b.x {
        // make it left−to−right
        swap(&mut a, &mut b);
    }
    let dx = b.x - a.x;
    let dy = b.y - a.y;
    let derror = dy.abs() * 2;
    let mut error = 0;
    let mut y = a.y;
    for x in a.x..=b.x {
        if steep {
            image.put_pixel(y as u32, x as u32, color);
        } else {
            image.put_pixel(x as u32, y as u32, color);
        }
        error += derror;
        if error > dx {
            y += if b.y > a.y { 1 } else { -1 };
            error -= dx * 2;
        }
    }
}

随便画几条

能画线，就能画三角形框了，把作者提供的obj文件画出来：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


fn main() {
    let (width, height) = (800, 800);
    let mut image = ImageBuffer::<Rgba<u8>, _>::from_pixel(width, height, BLACK);

    let input = BufReader::new(File::open("a.obj").unwrap());
    let model: obj::Obj = obj::load_obj(input).unwrap();
    for arr in model.indices.chunks(3) {
        for i in 0..3 {
            let v0 = model.vertices.get(arr[i] as usize).unwrap().position;
            let v1 = model
                .vertices
                .get(arr[(i + 1) % 3] as usize)
                .unwrap()
                .position;
            let x0 = ((v0[0] + 1.0) * (width - 1) as f32 / 2.0) as i32;
            let y0 = ((v0[1] + 1.0) * (height - 1) as f32 / 2.0) as i32;
            let x1 = ((v1[0] + 1.0) * (width - 1) as f32 / 2.0) as i32;
            let y1 = ((v1[1] + 1.0) * (height - 1) as f32 / 2.0) as i32;
            draw::line(glm::ivec2(x0, y0), glm::ivec2(x1, y1), &mut image, WHITE);
        }
    }

    flip_vertical_in_place(&mut image);
    image.save("a.png").unwrap();
}

详细代码见这里9f1f2564d8400ed296a5ee6ce9cb23e44203fd3c

填充三角形

扫描线

扫描线填充三角形的方式和这个方法的名字一样，一行一行的画直线，首先把三角形的三个点按y坐标从低到高排序，最高点和最低点连线是红色，中间点和其他两个点连线是绿色：

这样中间点就将三角形分为了上下两部分，分别画出两部分，就得到了一个完整的三角形：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


pub fn triangle<I: GenericImage>(
    mut t0: glm::Vec2,
    mut t1: glm::Vec2,
    mut t2: glm::Vec2,
    image: &mut I,
    color: I::Pixel,
) {
    if t0.y == t1.y && t0.y == t2.y {
        return;
    }

    // 按y坐标排序，从低到高 t0 t1 t2
    if t0.y > t1.y {
        swap(&mut t0, &mut t1);
    }
    if t0.y > t2.y {
        swap(&mut t0, &mut t2);
    }
    if t1.y > t2.y {
        swap(&mut t1, &mut t2);
    }

    let total_height = t2.y - t0.y;

    // 下半部分
    // y in t0.y -> t1.y
    for y in t0.y as i32..=t1.y as i32 {
        let segment_height = t1.y - t0.y + 1.;
        let alpha = (y as f32 - t0.y) as f32 / total_height as f32;
        let beta = (y as f32 - t0.y) as f32 / segment_height as f32; // be careful with divisions by zero

        let mut a = t0 + (t2 - t0) * alpha;
        let mut b = t0 + (t1 - t0) * beta;
        if a.x > b.x {
            swap(&mut a, &mut b);
        }
        for j in a.x as i32..=b.x as i32 {
            image.put_pixel(j as u32, y as u32, color);
        }
    }

    // 上半部分
    for y in t1.y as i32..=t2.y as i32 {
        let segment_height = t2.y - t1.y + 1.;
        let alpha = (y as f32 - t0.y) / total_height;
        let beta = (y as f32 - t1.y) / segment_height;
        let mut a = t0 + (t2 - t0) * alpha;
        let mut b = t1 + (t2 - t1) * beta;
        if a.x > b.x {
            swap(&mut a, &mut b);
        }
        for j in a.x as i32..=b.x as i32 {
            image.put_pixel(j as u32, y as u32, color);
        }
    }
}

将代码整理一下，同时画出两部分：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


pub fn triangle<I: GenericImage>(
    mut t0: glm::Vec2,
    mut t1: glm::Vec2,
    mut t2: glm::Vec2,
    image: &mut I,
    color: I::Pixel,
) {
    if t0.y == t1.y && t0.y == t2.y {
        return;
    }

    // 按y坐标排序
    if t0.y > t1.y {
        swap(&mut t0, &mut t1);
    }
    if t0.y > t2.y {
        swap(&mut t0, &mut t2);
    }
    if t1.y > t2.y {
        swap(&mut t1, &mut t2);
    }

    let total_height = t2.y - t0.y;
    // 同时画两部分
    for i in 0..=total_height as i32 {
        let second_half = if i > (t1.y - t0.y) as i32 || t1.y == t0.y {
            true
        } else {
            false
        };
        let segment_height = if second_half {
            t2.y - t1.y
        } else {
            t1.y - t0.y
        };
        let alpha = i as f32 / total_height as f32;
        let beta =
            (i as f32 - if second_half { t1.y - t0.y } else { 0. }) as f32 / segment_height as f32; // be careful with divisions by zero

        let mut a = t0 + (t2 - t0) * alpha;
        let mut b = if second_half {
            t1 + (t2 - t1) * beta
        } else {
            t0 + (t1 - t0) * beta
        };
        if a.x > b.x {
            swap(&mut a, &mut b);
        }
        for j in a.x as i32..=b.x as i32 {
            image.put_pixel(j as u32, (t0.y + i as f32) as u32, color);
        }
    }
}

详细代码见这里37bc2e71b0fe47a37da314987c69f43caf9027c1

重心坐标

扫描线是为单线程CPU编程设计的老式方法，显卡有很多核心，这种方式发挥不了显卡的威力。更好的方式是对于每个像素，直接判断其是否属于三角形内部。

首先需要了解什么是重心坐标，可以看这个文章，总结来讲：

如果点P再三角形ABC内部，必定唯一存在三个数w1,w2,w3，满足：

w1+w2+w3=1 且 w1,w2,w3非负数（负数说明不在内部）

P=w1*A+w2*B+w3*C （即P表示成A,B,C的线性组合）

则(w1,w2,w3)就称为此三角形上P点的（归一化）重心坐标。

计算的话，教程里的更好理解些，w1,w2,w3表示成(1-u-v,u,v)：

$$ \begin{aligned} P &= (1-u-v)A + uB + vC \\ &= A + u(B-A) + v(C-A) \\ &= A + u\overrightarrow{AB} + v\overrightarrow{AC} \end{aligned} $$

然后再把P移过去，就得到：

$$ u\overrightarrow{AB} + v\overrightarrow{AC} + \overrightarrow{PA} = 0 $$

再把向量展开成坐标值表示：

$$ \begin{cases} u\overrightarrow{AB}_x + v\overrightarrow{AC}_x + \overrightarrow{PA}_x &= 0\\ u\overrightarrow{AB}_y + v\overrightarrow{AC}_y + \overrightarrow{PA}_y &= 0\\ \end{cases} $$

然后作者上面的式子写成了矩阵的形式：

$$ \begin{cases} \begin{bmatrix} u & v &1 \end{bmatrix} \begin{bmatrix} \overrightarrow{AB}_x \\ \overrightarrow{AC}_x \\ \overrightarrow{PA}_x \end{bmatrix} &= 0 \\ \\ \begin{bmatrix} u & v &1 \end{bmatrix} \begin{bmatrix} \overrightarrow{AB}_y \\ \overrightarrow{AC}_y \\ \overrightarrow{PA}_y \end{bmatrix} &= 0 \end{cases} $$

其实不转换成矩阵也行，这一步无所谓。观察上面的式子，如果把参与计算的数值看作三维坐标，就会变得很简单，高中知识就够了：

$$ \begin{aligned} (u,v,1)\ &*\ (x_1,x_2,x_3) &= 0\\ (u,v,1)\ &*\ (y_1,y_2,y_3) &= 0 \end{aligned} $$

这不就两个向量的点积么，复习一下：

向量$A*B=|A||B|\cos\theta$，什么时候结果为零呢：当两个向量垂直的时候结果为0

回到式子, (u,v,1)和(x1,x2,x3)、(y1,y2,y3)必须同时垂直。换句话说，给定(x1,x2,x3)、(y1,y2,y3)两向量，找到同时垂直他们的向量即可。

继续高中知识就足够了，回忆下两个向量的叉积：

对两个向量做叉积能得到一个新的向量，这个向量同时垂直ab且方向与ab的位置有关。

所以，求(u,v,1)的值，只需要：

$$ (\overrightarrow{AB}_x , \overrightarrow{AC}_x , \overrightarrow{PA}_x) \times (\overrightarrow{AB}_y , \overrightarrow{AC}_y , \overrightarrow{PA}_y) $$

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 求重心坐标
fn barycentric(a: glm::IVec2, b: glm::IVec2, c: glm::IVec2, p: glm::IVec2) -> glm::Vec3 {
    let ab = b - a;
    let ac = c - a;
    let pa = a - p;

    let u = glm::cross(
        glm::vec3(ab.x as f32, ac.x as f32, pa.x as f32),
        glm::vec3(ab.y as f32, ac.y as f32, pa.y as f32),
    );

    // 因为传入坐标都是整数，所以z小于1就意味着z是0，这种情况是因为三角形三个顶点在一条直线上，不是合法三角形
    // 这种情况返回一个负值
    if u.z.abs() < 1. {
        return glm::vec3(-1., 1., 1.);
    }

    // vec(x,y,z)/z -> (u,v,1) -> (1-u-v, u, v)
    return glm::vec3(1. - ((u.x + u.y) / u.z) as f32, u.x / u.z, u.y / u.z);
}

有了求重心坐标的函数后，只需要枚举坐标，用当前坐标与三角形顶点算重心坐标，如果重心坐标中任意一个值为负数，说明当前坐标不在三角形中，反之则说明该坐标在三角形内：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


pub fn triangle_with_barycentric<I: GenericImage>(
    t0: glm::IVec2,
    t1: glm::IVec2,
    t2: glm::IVec2,
    image: &mut I,
    color: I::Pixel,
) {
    let bboxmin = glm::ivec2(t0.x.min(t1.x).min(t2.x), t0.y.min(t1.y).min(t2.y));
    let bboxmax = glm::ivec2(t0.x.max(t1.x).max(t2.x), t0.y.max(t1.y).max(t2.y));
    let a = t0[1];

    for px in bboxmin.x..=bboxmax.x {
        for py in bboxmin.y..=bboxmax.y {
            let bc_screen = barycentric(t0, t1, t2, glm::ivec2(px, py));

            if bc_screen.x < 0. || bc_screen.y < 0. || bc_screen.z < 0. {
                continue;
            }
            image.put_pixel(px as u32, py as u32, color);
        }
    }
}

详细代码见这里a1d23998dccac6a3f42130e3d57f21c399fab0d7

渲染阴影以及面剔除

把作者给的obj模型的每个三角形画出来，首先将obj文件里给的坐标转换为屏幕坐标，并随机给一个颜色：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


for arr in model.indices.chunks(3) {
    let (a, b, c) = (
        model.vertices.get(arr[0] as usize).unwrap().position,
        model.vertices.get(arr[1] as usize).unwrap().position,
        model.vertices.get(arr[2] as usize).unwrap().position,
    );
    let (a, b, c) = (
        glm::vec3(a[0], a[1], a[2]),
        glm::vec3(b[0], b[1], b[2]),
        glm::vec3(c[0], c[1], c[2]),
    );
    let (sa, sb, sc) = (
        glm::ivec2(
            (((a.x + 1.) * (width - 1) as f32) / 2.) as i32,
            (((a.y + 1.) * (height - 1) as f32) / 2.) as i32,
        ),
        glm::ivec2(
            (((b.x + 1.) * (width - 1) as f32) / 2.) as i32,
            (((b.y + 1.) * (height - 1) as f32) / 2.) as i32,
        ),
        glm::ivec2(
            (((c.x + 1.) * (width - 1) as f32) / 2.) as i32,
            (((c.y + 1.) * (height - 1) as f32) / 2.) as i32,
        ),
    );

    draw::triangle_with_barycentric(
        sa,
        sb,
        sc,
        &mut image,
        Rgba([
            rand::random::<u8>() % 255,
            rand::random::<u8>() % 255,
            rand::random::<u8>() % 255,
            255,
        ]),
    );
}

这里有一个问题，模型中的每个三角形都被画出来了，正常来讲只有面对我们的三角形才应该被画出来，这就涉及到了面剔除，接下来给模型打上光照，同时进行面剔除。

首先看光照，把一束光看作一个向量，然后再求出一个三角形的面向（三角形两条边做叉积，能得到方向垂直于两条边的向量）。面向与光照方向越接近，光照强度就越大。

把面向和光照两个向量再做点积，点积如果是负的，说明该面向背对光源，如果光源方向是我们屏幕外向屏幕内，那么这个面我们是看不见的，应该被剔除。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


let n = glm::cross(c - a, b - a); // 计算三角形面向
let n = glm::normalize(n);

let intensity = glm::dot(light_dir, n);

if intensity > 0. {
    // 既是光照强度，也能当面剔除用，小于0说明背对我们
    draw::triangle_with_barycentric(
        sa,
        sb,
        sc,
        &mut image,
        Rgba([
            (255. * intensity) as u8,
            (255. * intensity) as u8,
            (255. * intensity) as u8,
            255,
        ]),
    );
}

note: 模型文件中三角形的坐标是有顺序的，一般顺时针或逆时针排列，从而方便我们计算面向

详细代码见这里990567294a9b58fb4a66a65704640ff0710bd522

目录

TinyRenderer笔记0：画线和三角以及面剔除

准备画布

画线

填充三角形

扫描线

重心坐标

渲染阴影以及面剔除