thumbnail

Drawing Single-Color Triangles

Simple Rasterization

Our first objective for sampling a triangle is to check if a point exists inside the bounds of a triangle. How can we achieve this mathematically?

We can simplify our objective by checking if the point exists on one side of a line. We can do this by defining the right vectors on a line \(\bar{AB}\) with point \(\textbf{p}\):

\[\frac{\sqrt{10 \pm x^7}}{2 - \alpha}\]

\(x + y = 2\)

katex.render("c = \\pm\\sqrt{a^2 + b^2}", , {
    throwOnError: false
});

\[ \begin{align*} \text{Perp}(\textbf{B} - \textbf{A}) \cdot (\textbf{p} - \textbf{A}) = \textbf{N} \cdot \textbf{V}\\ L_{AB} (\textbf{p}) = \begin{cases} \text{one side} \quad \textbf{N} \cdot \textbf{V} < 0\\ \text{other side} \quad \textbf{N} \cdot \textbf{V} > 0\\ \text{on line} \quad \textbf{N} \cdot \textbf{V} = 0\\ \end{cases} \end{align*} \]

We can now do this for all three edges of the triangle and if they are on the same side, we’ll know that \(\textbf{p}\) is inside the triangle.

\[ L_{AB} \text{ and } L_{BC} \text{ and } L_{CA} \text{ are the same side} \] Now to compute our triangle, we can draw a box around the triangle and start iterating all the pixels within. Each pixel location is at the center of the pixel so we have a \((+0.5, +0.5)\) offset with the corners.

Optimized Solution

As you can probably, tell iterating every pixel within the bounds of the box can be redundant. We can further optimize this by only iterating over the bounds of the triangle.

Antialiasing by Supersampling

From figure 1 above, we can see that there are jaggies (rough edges). Super sampling is useful because its basically calculating detail at a higher level and averaging/distilling it to a lower-res to get a more accurate picture, leading to less jaggies.

The only difference here is that we divide each pixel into ‘subpixels’, calculate using the same rasterization process as above. Then, we average the values of the subpixels for the value of the overall pixel. To do this, we had to increase the size of the sample_buffer to accommodate the subpixels. Later, we calculate the averages.

With a higher samplerate, we get softer edges and less “jumps” between values. Hence, the lines look more pleasing to the eye.

Transforms

We tried to transform our robot such that it is waving while the right hand hangs down.

Barycentric coordinates

Barycentric coordinates essentially smoothly interpolate between the vertices of a triangle.

More formally, given triangle \(\Delta ABC\), the barycentric coordinate is some linear combination of the vertices:

\[\begin{align} \textbf{r} &= \alpha \textbf{A} + \beta \textbf{B} + \gamma \textbf{C}\\ 1 &= \alpha + \beta + \gamma \end{align}\] \[\begin{align*} \alpha &= \frac{L_{BC}(x,y)}{L_{BC}(x_A, y_A)}\\ \beta &= \frac{L_{CA}(x,y)}{L_{CA}(x_B, y_B)}\\ \gamma &= 1 - \alpha - \beta \end{align*}\]

This is useful as \(\alpha, \beta, \gamma\) can interpolate other properties such as RGB colors, pixels on a texture, or better our triangle rasterization algorithm through equation (1).

“Pixel sampling” for texture mapping

Say we want to sample points from an image to display on our screen. How can we best do this to prevent artifacts?

Nearest sampling

In this technique, we map our \(xy\) coordinates into \(uv\) coordinates and scale it towards the dimensions of the image / texture, then sample the closest pixel in the image / texture.

In layman’s terms, we are essentially (using barycentric coordinates) remapping our screen coordinates onto the texture, then finding the pixel coordinates closest to it.

Bilinear sampling

In this technique, we do the same, except linearly interpolate the nearest four pixels in the image. As a result, we achieve smoother results.

So we remap our screen coordinates onto the texture, then find the

“Level sampling” with mipmaps for texture mapping

Sometimes, we don’t want an even layer of texture mapping. For example, if we are texture mapping over a flat plane, pixels further away will develop jaggies. Instead, we can use mipmap– lower resolution versions of the image for areas that contain more “warping.” Intuitively, if there’s a lot of warping, we’ll just use a “lower frequency” version of the image so that the “important” information passes through.

While it does solve aliasing, speed and memory are heavily impacted. We’ll start calculating the Jacobian matrix which requires calculating two more barycentric points.

Creative Art!

The following Sierpinski Triangle was rendered with our rasterizer (with the sampling algorithm for triangles)

drawing

Generated with the following code:

def draw_triangle(x, y, s, level):
    if level == 0:
        x1, y1 = x, y
        x2, y2 = x + s, y
        x3, y3 = x + s/2, y - (s * math.sqrt(3)/2)
        svg_lines.append(f'<polygon points="{x1},{y1} {x2},{y2} {x3},{y3}" />')
    else:
        s_half = s/2
        draw_triangle(x, y, s_half, level-1)
        draw_triangle(x + s_half, y, s_half, level-1)
        draw_triangle(x + s_half/2, y - (s_half * math.sqrt(3)/2), s_half, level-1)

draw_triangle(0, h, size, depth)