目录

[WIP]TinyRenderer笔记0:画线和三角

这篇是自己学习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 > dxerror -= 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();
}

填充三角形

扫描线

重心坐标

扫描线是为单线程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) $$