Table of Contents
Goal
This time, we will further enhance our small GUI program to draw two solid triangles and manage occlusion by using Z-buffering. Furthermore, we will apply a simple super-sampling technique to achieve softer edges.
Triangle
Last time, our Triangle class didn't do much except hold our triangle information. But this time, we will add some utilities related to triangles.
Transform
First, our transform will be applied triangle-wise. So, we need to move the mvp_transform and viewport_transform to the Triangle class.
This function will accept mvp and viewport matrices from the rasterizer and generate a new Triangle instance.
pub fn apply_transform(&mut self, mvp: &Mat4, viewport: &Mat4) -> Self {
let vertices:Vec<Vec4> = self
.vertices
.iter()
.map(|vertex:&Vec4| {
let vertex: Vec4 = Self::mvp_transform(mvp, &vertex);
let vertex:Vec4=vertex/vertex.w; // normalization
Self::viewport_transform(viewport, &vertex)
})
.collect();
let color = self.color;
Self {vertices,color}
}
Axis-aligned minimum bounding box (AABB)
When we try to iterate over pixels to check if each pixel is inside the triangle, we can use an axis-aligned minimum bounding box to bypass some unused pixels. This function is simply finding the minimum and maximum x and y values.
pub fn aabb(&mut self) -> (usize, usize, usize, usize) {
// use first vertex to init
let mut min_x = self.vertices[0].x as usize;
let mut max_x = min_x;
let mut min_y = self.vertices[0].y as usize;
let mut max_y = min_y;
// check rest vertices
for vertex in &self.vertices[1..] {
let x = vertex.x as usize;
let y = vertex.y as usize;
if x < min_x {
min_x = x;
}
if x > max_x {
max_x = x;
}
if y < min_y {
min_y = y;
}
if y > max_y {
max_y = y;
}
}
(min_x, max_x, min_y, max_y)
}
Inside Checker
We also need a function that can check if a point inside the triangle.
The calculation is simple; we just need to obtain three vectors from the point to each vertex and check whether the cross products of those vectors have the same sign.
// check if point in triangle
pub fn is_point_inside(&mut self, p: &Vec4) -> bool {
// vectors
let pa = vec3(
self.vertices[0].x - p.x,
self.vertices[0].y - p.y,
self.vertices[0].z - p.z,
);
let pb = vec3(
self.vertices[1].x - p.x,
self.vertices[1].y - p.y,
self.vertices[1].z - p.z,
);
let pc = vec3(
self.vertices[2].x - p.x,
self.vertices[2].y - p.y,
self.vertices[2].z - p.z,
);
// cross product
let cross0: Vec3 = cross(&pa, &pb);
let cross1: Vec3 = cross(&pb, &pc);
let cross2: Vec3 = cross(&pc, &pa);
// if same sign
cross0.z.signum() == cross1.z.signum() && cross1.z.signum() == cross2.z.signum()
}
Barycentric Interpolation
Here we need to implement a barycentric function. This function calculate the Barycentric Coordinates. The barycentric coordinates represent the weights of the three vertices. When calculating the z-value of a point in the triangle, we can use these weights to interpolate.
pub fn barycentric_coordinates(&mut self, p: &Vec4) -> (f32, f32, f32) {
let v0: Vec4 = self.vertices[1] - self.vertices[0];
let v1: Vec4 = self.vertices[2] - self.vertices[0];
let v2: Vec4 = p - self.vertices[0];
let d00 = dot(&v0, &v0);
let d01 = dot(&v0, &v1);
let d11 = dot(&v1, &v1);
let d20 = dot(&v2, &v0);
let d21 = dot(&v2, &v1);
let denom = d00 * d11 - d01 * d01;
let v = (d11 * d20 - d01 * d21) / denom;
let w = (d00 * d21 - d01 * d20) / denom;
let u = 1.0 - v - w;
(u, v, w)
}
pub fn interp_depth(&mut self, u: f32, v: f32, w: f32) -> f32 {
u * self.vertices[0].z + v * self.vertices[1].z + w * self.vertices[2].z
}
Rasterizer
Now, back to the rasterizer, first, we need to add a few more parameters, some frame information, and a depth_buffer.
pub struct Rasterizer {
...
depth_buffer: Vec<f32>,
frame_width: usize,
frame_height:usize,
color_num: usize,
}
And since we are looking in the minus-z direction, the higher the depth information, the closer the object is to our camera. Therefore, we can initialize the depth buffer with -f32::INFINITY.
Then, we should add a rasterize_triangle function, as we are handling a group of triangles.
fn rasterize_triangle(&mut self, frame: &mut [u8], triangle: &mut Triangle, is_depth:bool) {
// calculate pixels to iter
let (mut min_x, mut max_x,mut min_y,mut max_y) = triangle.aabb();
max_x = min(self.frame_width,max_x);
max_y = min(self.frame_height, max_y);
// iter through pixel and find if current pixel in inside triangle
for x in min_x..=max_x {
for y in min_y..=max_y {
let p: Vec4 = Vec4::new(x as f32, y as f32, 0.0, 0.0);
let pixel_index = x + y * self.frame_width;
let bit_index = pixel_index * self.color_num;
if triangle.is_point_inside(&p) {
// inside triangle, then check depth
let (u, v, w) = triangle.barycentric_coordinates(&p);
let z = triangle.interp_depth(u, v, w);
if z > self.depth_buffer[pixel_index] {
// this pixel is more close to screen, so render it
if is_depth{
// draw depth image
frame[bit_index..bit_index + self.color_num]
.copy_from_slice(&[(z*255f32) as u8,(z*255f32) as u8,(z*255f32) as u8,255]);
}
else {
// render color image
frame[bit_index..bit_index + self.color_num]
.copy_from_slice(&triangle.color);
}
// update depth buffer
self.depth_buffer[pixel_index] = z;
}
};
}
}
}
In this function, we first use AABB to determine the valid pixel range, then iterate through all the pixels.
For each pixel, we use is_point_inside to check if this pixel should be rendered as part of the object.
Then, we use barycentric_coordinates and interp_depth to obtain the z-value. We test the z-value against the depth_buffer to see if it is occluded.
Antialiasing
When rasterizing the triangle, we use whole pixels to fill in the color and perform z-buffering. This can cause severe aliasing.
So, we can use simple super-sampling for anti-aliasing.
Since we are super-sampling, we cannot process each triangle separately and iterate over pixels. So, let's make a slight change to the rasterize_triangle function:
fn rasterize_triangle(
&mut self,
frame: &mut [u8],
triangle_group: &mut [Triangle],
is_depth: bool,
) {
// init AABB
let mut global_min_x = self.frame_width;
let mut global_max_x = 0;
let mut global_min_y = self.frame_height;
let mut global_max_y = 0;
for triangle in &mut *triangle_group {
let (min_x, max_x, min_y, max_y) = triangle.aabb();
// update AABB
global_min_x = min(global_min_x, min_x);
global_max_x = max(global_max_x, max_x);
global_min_y = min(global_min_y, min_y);
global_max_y = max(global_max_y, max_y);
}
// safe bound
global_max_x = min(self.frame_width, global_max_x + 1);
global_max_y = min(self.frame_height, global_max_y + 1);
let step = 1.0 / self.super_sample as f32;
let super_power = self.super_sample*self.super_sample;
// iter through pixel and find if current pixel in inside triangle
for x in global_min_x..global_max_x {
for y in global_min_y..global_max_y {
// super sampling
let mut samples_z = vec![-f32::INFINITY;super_power]; // sub depth
let mut sample_colors = vec![vec![0u8; 4]; super_power]; // sub color init with background
for sub_x in 0..self.super_sample {
for sub_y in 0..self.super_sample {
let sub_pixel_x = x as f32 + sub_x as f32 * step + step / 2.0;
let sub_pixel_y = y as f32 + sub_y as f32 * step + step / 2.0;
let sample_index:usize = sub_x + sub_y * self.super_sample;
let p: Vec4 = Vec4::new(sub_pixel_x as f32, sub_pixel_y as f32, 0.0, 1.0);
for triangle in &mut *triangle_group {
// test for all triangles
if triangle.is_point_inside(&p) {
// inside triangle, then check depth
let (u, v, w) = triangle.barycentric_coordinates(&p);
let z = triangle.interp_depth(u, v, w);
if z > samples_z[sample_index] {
// z-test for subpixel
sample_colors[sample_index] = if is_depth {
vec![
(z * 255f32) as u8,
(z * 255f32) as u8,
(z * 255f32) as u8,
255,
]
} else {
triangle.color.to_vec()
};
// update depth
samples_z[sample_index] = z;
}
};
}
}
}
// average color
let avg_color = sample_colors.iter().fold([0, 0, 0, 0], |acc, color| {
[
(acc[0] as f32 + color[0] as f32 / super_power as f32) as u8,
(acc[1] as f32 + color[1] as f32 / super_power as f32) as u8,
(acc[2] as f32 + color[2] as f32 / super_power as f32) as u8,
255,
]
});
let pixel_index = x + y * self.frame_width;
let bit_index = pixel_index * self.color_num;
frame[bit_index..bit_index + 4].copy_from_slice(&avg_color);
}
}
}
This time, we pass the entire transformed triangle_group into the rasterizer function. Then, we find the global AABB by iterating over each triangle.
Next, we iterate over pixels. For each pixel, we will loop through sub_pixels and perform the same z-interpolation and z-buffer test on each sub-pixel buffer.
Finally, we can average the pixel color and fill the drawing buffer.
When we use 4x4 super-sampling, our animation will look pretty smooth.
