4

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

 2 years ago
source link: https://www.kirito41dd.cn/tinyrenderer-note-0/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

 2022-01-01  约 1520 字   预计阅读 4 分钟 

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

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

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

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

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

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();
}

huabu.png

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

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，这样一来就全是整数计算：

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;
        }
    }
}

随便画几条

line_0.png

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

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();
}
line_obj.png

填充三角形

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

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

abcp.png

如果点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)：

P=(1−u−v)A+uB+vC=A+u(B−A)+v(C−A)=A+uAB→+vAC→ \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​=(1−u−v)A+uB+vC=A+u(B−A)+v(C−A)=A+uAB+vAC​
然后再把P移过去，就得到：
uAB→+vAC→+PA→=0 u\overrightarrow{AB} + v\overrightarrow{AC} + \overrightarrow{PA} = 0 uAB+vAC+PA=0
再把向量展开成坐标值表示：
{uAB→x+vAC→x+PA→x=0uAB→y+vAC→y+PA→y=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} {uABx​+vACx​+PAx​uABy​+vACy​+PAy​​=0=0​
然后作者上面的式子写成了矩阵的形式：
{[uv1][AB→xAC→xPA→x]=0[uv1][AB→yAC→yPA→y]=0 \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} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​[u​v​1​]⎣⎢⎢⎢⎡​ABx​ACx​PAx​​⎦⎥⎥⎥⎤​[u​v​1​]⎣⎢⎢⎢⎡​ABy​ACy​PAy​​⎦⎥⎥⎥⎤​​=0=0​
其实不转换成矩阵也行，这一步无所谓。观察上面的式子，如果把参与计算的数值看作三维坐标，就会变得很简单，高中知识就够了：
(u,v,1)∗(x1,x2,x3)=0(u,v,1)∗(y1,y2,y3)=0 \begin{aligned} (u,v,1)\ &*\ (x_1,x_2,x_3) &= 0\\ (u,v,1)\ &*\ (y_1,y_2,y_3) &= 0 \end{aligned} (u,v,1) (u,v,1) ​∗ (x1​,x2​,x3​)∗ (y1​,y2​,y3​)​=0=0​

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

vec-dot-product.gif

向量A∗B=∣A∣∣B∣cos⁡θA*B=|A||B|\cos\thetaA∗B=∣A∣∣B∣cosθ，什么时候结果为零呢：当两个向量垂直的时候结果为0

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

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

vec-vector-product.png

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

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

(AB→x,AC→x,PA→x)×(AB→y,AC→y,PA→y) (\overrightarrow{AB}_x , \overrightarrow{AC}_x , \overrightarrow{PA}_x) \times (\overrightarrow{AB}_y , \overrightarrow{AC}_y , \overrightarrow{PA}_y) (ABx​,ACx​,PAx​)×(ABy​,ACy​,PAy​)

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK