Checkout our technical report! https://cs184-firesim.github.io/final-report/

# Path Tracing Pt 2

# Path-Tracing

# Overview

This is a CS184 Project. This time, it’s just the bare minimum rubric items because I’m a little swamped by work. You can still find pretty images peppered within the post though, if those interest you : )

In this project, I implemented a ray generation routine that starts with input coordinates from the image space and generates a ray with coordinates in the world space. I also implemented the ray-intersection routines for two types of primitives: spheres and triangles. Then, I implemented both direct and indirect lighting to achieve global illumination. Finally, I implemented an adaptive sampling feature so the program can intelligently decide when to stop sampling.

# Bezier Curves and the Half Edge Data Structure

This is a CS184 Project. For graders, if you are looking for a list of rubric items and their locations within this post, please scroll to the bottom of the page. For everyone else, please read on.

# Overview

In this post, we are going to talk about Bezier Curves and the Half Edge Data Structure. Technically, those two are completely distinct topics that should belong to two posts, but CS184 made them into one project, so here we are.

Bezier curves are widely used in programs like PhotoShop to draw smooth curves. It is the default curve type for the pen tool in PhotoShop. In this post, we’ll explore how Bezier curves can be generated programmatically using the de Casteljau method. We’ll also briefly explore the 2D generalization of Bezier curves - Bezier surfaces.

The half edge data structure is one way to represent 3D meshes that are composed of triangles. It is powerful because it allows operations such as neighbor lookup in `O(n)`

time, where `n`

is the number of neighbors of a vertex, edge, or face. In a naive data structure where simply store a list of triangles, the same operation takes `O(N)`

, where `N`

is the total number of triangles.

# Bezier Curves and the de Casteljau method

A Bezier Curve is defined by two or more control points. A Bezier curve of degree `n`

is defined by `(n+1)`

control points. The typical Bezier curve we see in various graphic processing programs is of degree `3`

, because it is relatively easy to predict how the curve would change once we manipulate the control points and is also very expressive. The first and the last control points define where the curve start and end, and all the control points contribute to the curvature of the curve. For example, here’s a curve I drew in PhotoShop (it is of degree `3`

):

*Unfortunately there's some very apparent aliasing*

# Rasterizer

This is a CS184 Project. For graders, if you are looking for a list of rubric items and their locations within this post, please scroll to the bottom of the page. For everyone else, please read on.

# Overview

Rasterization is a method of taking in mathematical descriptions of a scene and turning it into pixel values that we can display on a screen. As a simple example, imagine if we have a triangle defined by three vertices: $(0, 0), (5, 0), (5, 5)$. Since most of our screens consist of a grid of pixels, then in order to display this triangle, we will need to fill in the framebuffer at each point on the grid with a color. This process is called rasterization. Although the objects being rasterized are most commonly triangles, rasterization can be applied to other shapes as well.

In this project, we implement a CPU rasterizer that has multiple mipmap modes, multiple pixel sampling modes, multiple levels of supersampling, the ability to render texture, and the ability to render affine transforms.

# Rasterizing single-colored triangles

In this part, we implement a simple CPU rasterizer that draws a triangle with a single color.

1 | void RasterizerImp::rasterize_triangle(float x0, float y0, |

The first step is to calculate the bounding box of the triangle. After all, we wouldn’t want to loop through the whole pixel buffer if our triangle only occupies a small portion of it. This is achieved by taking the minimum and maximum of the coordinates to obtain two diagonal corners of the bounding box.

The second step is to loop through each sample point in our bounding box, checking whether they land within the triangle. To do this, we’ll use some maths.

We will first assume the winding order of the triangle to be counter-clockwise. That is, the vertices $(x0, y0), (x1, y1), (x2, y2)$ enclose the triangle in a counter-clockwise order. In the end, we’ll generalize our result to any arbitrary winding order.

# Hello World

Welcome to my blog! My name is Ziyao (Mark) Zhang, and I am excited to share my thoughts with you in the coming months (years?). This is not the first time I attempted at maintaining a blog, not even the second time, but let’s hope this attempt stays around for longer.

As a start, I will be periodically sharing computer graphics related posts from CS184, with intermittent articles on random stuff. This blog will be mostly tech related, but I’ll be posting whatever I want.

So stay tuned?