CS184 Summer 2025 Homework 1 Write-Up

The top-left and bottom-right corners of the bounding box around a triangle are simply the minimum and maximum x and y values out of the three vertices:

// bounding box coordinates
Vector2D boxmin(floor(min({ x0, x1, x2 })), floor(min({ y0, y1, y2 })));
Vector2D boxmax(floor(max({ x0, x1, x2 })), floor(max({ y0, y1, y2 })));
				

First thing we'll do is check that the vertices were passed in CCW order; this is important for the inside() function. As was shown in Discussion 2, winding order can be checked by picking a vertex to be the origin and taking the cross product of the vectors formed by the other 2 vertices:

Vector2D v1(x1 - x0, y1 - y0);
Vector2D v2(x2 - x0, y2 - y0);

// store vectors around triangle CCW (using cross product)
if (cross(v1, v2) < 0) {
	float tempX = x1;
	float tempY = y1;
	x1 = x2;
	y1 = y2;
	x2 = tempX;
	y2 = tempY;
}
				

Since these are 2D vectors, their cross product will be a scalar, which will tell us the winding direction: If it's negative (CW winding order) we want to switch the points.

For convenience we compute vectors representing the edge of the triangles (see below for inside()).

array<Vector2D, 6> edges = {
	Vector2D(x1 - x0, y1 - y0),
	Vector2D(x0, y0),
	Vector2D(x2 - x1, y2 - y1),
	Vector2D(x1, y1),
	Vector2D(x0 - x2, y0 - y2),
	Vector2D(x2, y2),
};
				

We iterate over all pixels in the bounding box.

Easy: our algorithm is the one that checks each sample within the bounding box of the triangle!

for (int x = boxmin.x; x <= boxmax.x; x++) {
	for (int y = boxmin.y; y <= boxmax.y; y++) {
		...
	}
}
				

Quick check to make sure we're even on the screen,

for (int x = boxmin.x; x <= boxmax.x; x++) {
	for (int y = boxmin.y; y <= boxmax.y; y++) {
		if (x < 0 || x >= width || y < 0 || y >= height) {
			continue;
		}
		...
	}
}
				

(note: I actually forgot to do this until way later in this assignment, like after finishing Task 6, and it was causing segmentation faults and weird rendering artifacts until I realized I was trying to render in pixels that weren't on the screen)

Then check if our pixel is inside the triangle, using the inside() function. If it is, then draw it.

for (int x = boxmin.x; x <= boxmax.x; x++) {
	for (int y = boxmin.y; y <= boxmax.y; y++) {
		if (x < 0 || x >= width || y < 0 || y >= height) {
			continue;
		}
		if (inside(Vector2D(x, y), edges)) {
			fill_pixel(x, y, color);
		}
	}
}
				

The first thing we did was alter some functions in the rasterization pipeline to support supersampling. Like the HW 1 spec suggests, this includes RasterizerImp::set_sample_rate() and RasterizerImp::set_framebuffer_target().

In both functions, this was the original line for resizing the sample buffer:

this->sample_buffer.resize(width * height, Color::White);
				

We changed it to

this->sample_buffer.resize(width * height * sample_rate, Color::White);
				

Why? In the rasterization pipeline, the sample buffer is a C++ vector that stores sampling data in the form of Color objects. Originally, for single-pixel sampling, this was a vector of size width * height, meaning each index corresponded to a pixel on screen. In fact, in the original RasterizerImp::resolve_to_framebuffer(), the function simply took each index of RasterizerImp::sample_buffer and converted the Color into its RGB (0-255) components and stored them in the corresponding place in the framebuffer:

for (int k = 0; k < 3; ++k) {
    this->rgb_framebuffer_target[3 * (y * width + x) + k] = (&col.r)[k] * 255;
}
				

But when supersampling, each pixel now contains sample_rate samples, which means the sample buffer needs to be scaled appropriately.

Before we touch supersampling the triangle, we need to fix the way fill_pixel() works to support the new sample_buffer size. Originally, it just put the Color parameter c directly into the sample buffer at its corresponding (x,y) index,

sample_buffer[y * width + x] = c;
				

but now that we have scaled the sample buffer up we need to change this slightly. Plus, the intuition gained from fixing this function will help during triangle rasterization.

void RasterizerImp::fill_pixel(size_t x, size_t y, Color c) {
	// NOTE: You are not required to implement proper supersampling for points and lines
	// It is sufficient to use the same color for all supersamples of a pixel for points and lines (not triangles)
	// I did this ^^ -Walter

	int dp = sqrt(sample_rate); // samples per unit direction
	int startPos = (y * width * sample_rate) + (x * dp); // position of top left sample

	for (int i = 0; i < dp; ++i) {
		for (int j = 0; j < dp; ++j) {
			// fill dp x dp box with color c in sample_buffer
			int buffer_pos = startPos + (j * width * dp) + i;
			sample_buffer[buffer_pos] = c;
		}
	}
}	
				

Let's break down the code above. We know we have sample_rate samples per pixel, and we can assume this number is a square so the length and width of the sample space inside of a pixel is simply

int dp = sqrt(sample_rate); // samples per unit direction
				

From this, we can get the index of the top-left sample in our pixel (x,y) in the sample buffer, which I call startPos. We want to be at pixel row y. Each row in the sample buffer has width width * dp, and the row we want will be at y * dp. Additionally, once we have found the start of the yth row, we need to move over to our x position at x * dp. This looks like:

int startPos = (y * width * sample_rate) + (x * dp); // position of top left sample
				

Now we can iterate through all sample_rate subpixels and give them all the same color, since we don't have to supersample lines and points. Using the nested for iterators i, j, the position of subpixel (i,j) in the sample buffer was calculated similar to above.

int buffer_pos = startPos + (j * width * dp) + i;
				

So I had some trouble figuring out how to traverse the sample buffer properly (see above). After I took some time to read through rasterizer.cpp/h and the Task 2 spec it probably only took me around 15 minutes to write the code for it, however I then had to spend an additional hour debugging because I had the math wrong for indexing subpixels, but I didn't know that so I thought there was some problem with other parts of my code until I finally realized that I was off by a factor of dp in the indexing formula. I think God saw my Task 1 code run perfectly first try and decided that I needed some retribution.

Now that we've figured out indexing this part is easy. We're using mostly the same code as Task 1 in RasterizerImp::rasterize_triangle() but we now need to check multiple points inside each pixel instead of just 1. Originally, we simply checked if the center of the pixel was in the triangle:

if (inside(Vector2D(x + 0.5, y + 0.5), edges)) {
	fill_pixel(x, y, color);
}
				

But now we want to split the pixel into sample_rate subpixels and sample at their centers. This is done with the same code as in step 2 with fill_pixel(), but with the introduction of some additional variables dx, offset.

int dp = sqrt(sample_rate);
float dx = 1.0f / dp; // length of sample
float offset = dx / 2; // dist to center of sample

for (int i = 0; i < dp; ++i) {
	for (int j = 0; j < dp; ++j) {
		int startPos = (y * width * sample_rate) + (x * dp);

		if (inside(Vector2D(x + offset + i * dx, y + offset + j * dx), edges)) {
			sample_buffer[startPos + (j * width * dp) + i] = color;
		}
	}
}	
				

These two variables are used to get the center point of each subpixel (see figure below).

It's looking good, we have correct sample buffers now, but the RasterizerImp::resolve_to_framebuffer() function does not know how to handle our scaled sample buffer! To resolve this, we'll take all the color values in a pixel and average them out, effectively downsampling the subpixels into a single pixel once more.

Again, we'll use the same indexing formula from step 2/3.

void RasterizerImp::resolve_to_framebuffer() {
	for (int x = 0; x < width; ++x) {
		 for (int y = 0; y < height; ++y) {
		int dp = sqrt(sample_rate);
		int startPos = (y * width * sample_rate) + (x * dp);

		// sum color of all samples
		Color col;
		for (int i = 0; i < dp; ++i) {
			for (int j = 0; j < dp; ++j) {
				col += sample_buffer[startPos + (j * width * dp) + i];
			}
		}
		col *= (1.0f / sample_rate); // average color

		for (int k = 0; k < 3; ++k) {
			this->rgb_framebuffer_target[3 * (y * width + x) + k] = (&col.r)[k] * 255;
		}
	}
}
				

Translation creates a matrix that shifts the geometric shape that it is applied to by dx units horizontally and dy units vertically.

Function's Code:

Matrix3x3 translate(float dx, float dy) {
	// row0
	float a = 1, b = 0, c = dx;
	// row1
	float d = 0, e = 1, f = dy;
	// row2
	float g = 0, h = 0, i = 1;
	return Matrix3x3(a, b, c, d, e, f, g, h, i);
}
				

Scaling a geometric shape scales that object by sx in the x-direction and sy in the y-direction. Objects as a result can increase or decrease in size according to whether the values are above or below 1.

Function's Code:

Matrix3x3 scale(float sx, float sy) {
	// row 0
	float a = sx, b = 0, c = 0;
	// row 1
	float d = 0, e = sy, f = 0;
	// row 2
	float g = 0, h = 0, i = 1;

	return Matrix3x3(a, b, c, d, e, f, g, h, i);
}
				

The rotate function constructs a matrix that rotates a point or shape around the origin by an angle given in degrees as the input of the function. The matrix uses the standard rotation form rotating counterclockwise since we use positive angles in a right-handed coordinate system.

Function's Code:

// The input argument is in degrees counterclockwise
Matrix3x3 rotate(float deg) {
	float rad = deg * PI / 180;
	float co = cos(rad);
	float si = sin(rad);

	// row0
	float a = co, b = -si, c = 0;
	// row1
	float d = si, e = co, f = 0;
	// row2
	float g = 0, h = 0, i = 1;

	return Matrix3x3(a, b, c, d, e, f, g, h, i);
}
				

We want to define a map between coordinates in the scene (our 2D cartesian plane) to coordinates on some texture. It is a convention to use uv coordinates, where \((u,v) \in [0,1]^2\). This mapping will allow us to take some coordinate (x,y) and apply a color to it that corresponds to its (u,v) location on the texture.

Luckily for us, the uv coordinates were given as parameters to rasterize_textured_triangle() so the only thing we need to worry about is barycentric coordinates-- which we already have support for from Task 4!

Vector2D uv = weights.first * Vector2D(u0, v0) + weights.second * Vector2D(u1, v1) + gamma * Vector2D(u2, v2);
Color color;
// decide which sampling to use
if (psm == P_NEAREST) {
    color = tex.sample_nearest(uv);
}
else if (psm == P_LINEAR) {
    color = tex.sample_bilinear(uv);
}
sample_buffer[startPos + (j * width * dp) + i] = color;	
			

The barycentric coordinate weights can be used directly on the uv vertices to get (x,y) in uv coordinates, which is then passed to our sample functions.

We can either sample nearest or sample bilinearly. Firstly, we need to scale (u,v) to the size of the texture.

float u = uv[0] * (mip.width - 1);
float v = uv[1] * (mip.height - 1);
				

(Note: a very silly mistake I made was not subtracting 1 from the dimensions and getting segmentation faults!)

For nearest sampling, just round these values and index the map.

return mip.get_texel(round(uv[0] * (mip.width - 1)), round(uv[1] * (mip.height - 1)));	
				

For bilinear it's a little more complicated. We grab the four closest texels,

// coords of top-left texel
int x = floor(u);
int y = floor(v);

// interpolation weights
float s = u - x;
float t = v - y;

// top left texel
Color c00 = mip.get_texel(x, y);
// top right texel
Color c01 = mip.get_texel(x + 1, y);
// bottom left texel
Color c10 = mip.get_texel(x, y + 1);
// bottom right texel
Color c11 = mip.get_texel(x + 1, y + 1);
				

Then interpolate across the top and bottom rows, and once more between those two results (do we really have to call it lerping??):

// bilinear interpolation btwn top (c0) and bottom (c1) rows
Color c0 = c00 * (1 - s) + c10 * s;
Color c1 = c01 * (1 - s) + c11 * s;

// bilinear interpolation btwn both results
return c0 * (1 - t) + c1 * t;
				

First thing we want to know is what level of clarity we need from this texture in order for it to still look good. To do this, we need to calculate the correct mipmap level, which is given by some mathematical formulas (shown below). At its core, we are comparing how a differential (or in the discrete sense, single pixel) move in screen space corresponds to a move in uv space. For example, in the x-direction this is represented by \(\frac{du}{dx}, \frac{dv}{dx}\).

In the code we were gifted the SampleParams struct, which holds all the distance data we need to calculate mipmap levels. Thus, in RasterizerImp::rasterize_textured_triangle() we just fill it with the needed data.

SampleParams uv;
uv.psm = this->psm;
uv.lsm = this->lsm;
uv.p_uv = weights.first * Vector2D(u0, v0) + weights.second * Vector2D(u1, v1) + gamma * Vector2D(u2, v2);
pair<float, float> dx_weights = getBaryWeights(r + Vector2D(dx, 0), r0, r1, r2);
pair<float, float> dy_weights = getBaryWeights(r + Vector2D(0, dx), r0, r1, r2);
gamma = 1 - dx_weights.first - dx_weights.second;
uv.p_dx_uv = dx_weights.first * Vector2D(u0, v0) + dx_weights.second * Vector2D(u1, v1) + gamma * Vector2D(u2, v2);
gamma = 1 - dy_weights.first - dy_weights.second;
uv.p_dy_uv = dy_weights.first * Vector2D(u0, v0) + dy_weights.second * Vector2D(u1, v1) + gamma * Vector2D(u2, v2);
Color color = tex.sample(uv);
				

Where our differential length is not a single pixel, but length of variable dx since we're working in conjunction with supersampling. In the last line, we send all of this measurement data to the texture, where we will go next.

We just use the formula from step 1 to calculate the level D, which is returned from Texture::get_level().

float Texture::get_level(const SampleParams& sp) {
	Vector2D diff_dx = sp.p_dx_uv - sp.p_uv;
	Vector2D diff_dy = sp.p_dy_uv - sp.p_uv;

	Vector2D duv_dx(diff_dx[0] * (width - 1), diff_dx[1] * (height - 1));
	Vector2D duv_dy(diff_dy[0] * (width - 1), diff_dy[1] * (height - 1));

	float du_dx = duv_dx[0];
	float dv_dx = duv_dx[1];
	float du_dy = duv_dy[0];
	float dv_dy = duv_dy[1];

	float L = max(sqrt(pow(du_dx, 2) + pow(dv_dx, 2)), sqrt(pow(du_dy, 2) + pow(dv_dy, 2)));
	return log2(L);
}
				

Now we just need to make some changes to Texture::sample() to handle the level sampling settings. Firstly, we want to round D if we're using nearest level.

float D = 0;
if (sp.lsm != L_ZERO) {
    D = get_level(sp);
    if (sp.lsm == L_NEAREST) {
        D = round(D);
    }
    // somehow D can be negative/bigger than the mipmap size
    // so just account for that here
    if (D >= mipmap.size()) {
        D = mipmap.size() - 1;
    }
    else if (D < 0) {
        D = 0;
    }
}
				

Note that we also check that D is within our bounds; this fixes a bug where zooming too far in or out would cause problems.

Now we just make some additional changes to our sampling calls, using nested if loops to handle level sampling options.

Color color;
// decide which sampling to use
if (sp.psm == P_NEAREST) {
    color = sample_nearest(sp.p_uv, D);
    if (sp.lsm == L_LINEAR && D < mipmap.size() - 1) {
        float weight = D - floor(D);
        color *= 1 - weight;
        color += sample_nearest(sp.p_uv, D + 1) * weight;
    }
    
}
else if (sp.psm == P_LINEAR) {
    color = sample_bilinear(sp.p_uv, D);
    if (sp.lsm == L_LINEAR && D < mipmap.size() - 1) {
        float weight = D - floor(D);
        color *= 1 - weight;
        color += sample_bilinear(sp.p_uv, D + 1) * weight;
    }
    
}

return color;	
				

Since the sample_nearest/bilinear functions floor D to an int anyways, we can call them on D for all types of lsm and simply compute an additional linear interpolation if we're using bilinear (the code inside of the nested if).