8

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

 1 year ago
source link: https://www.kirito.info/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.

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

 2022-01-01  约 2660 字   预计阅读 6 分钟 

这篇是自己学习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

详细代码见这里9f1f2564d8400ed296a5ee6ce9cb23e44203fd3c

填充三角形

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

line-sweeping-0.png

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

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

line-swepping-1.png

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

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编程设计的老式方法，显卡有很多核心，这种方式发挥不了显卡的威力。更好的方式是对于每个像素，直接判断其是否属于三角形内部。

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

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​) 
// 求重心坐标
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);
}

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

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

line-sweeping-2.png

详细代码见这里a1d23998dccac6a3f42130e3d57f21c399fab0d7

渲染阴影以及面剔除

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

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,
        ]),
    );
}
shadow-0.png

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

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

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

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: 模型文件中三角形的坐标是有顺序的，一般顺时针或逆时针排列，从而方便我们计算面向

shadow-1.png

详细代码见这里990567294a9b58fb4a66a65704640ff0710bd522


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK