Defining our drawing area

First of all, let us add a new Topology type to represent triangles:

const Topology = {
    LINES: 0,
    TRIANGLES: 1
};

Lines were represented by two consecutive vertices in the attribute array. Triangles will use three.

We will start of by finding the area on the screen, where the triangle could possibly be. The simplest such shape is a rectangle.

This rectangle consists of the minumum and maximum coordinates of the triangle. These can be found by finding the minimum and maximum values per coordinate of all points making up the triangle. To maybe reuse this, we will write a helper function that computes these values for an array of points.

Additionally, we don't want to run into the same issue as with the lines: Going outside the image. Luckily, when we have the minimum and maximum points, we can make sure that our rectangle is inside, with the following two conditions:

• Take the he minimum of the maximum point and the viewport maximum
• Take the maximum of the minimum point and the viewport minimum

The rectangle could be fully outside though. It is fully outside, if either

• Any coordinate of the maximum point is smaller than the corresponding viewport origin
• Any coordinate of the minimum point is larger or equal to the viewport maximum

With this, we can implement iterating over all pixels that could potentially be covered by a triangle. We will do it in a standalone way here and integrate it afterwards into the rasterizer, which is only a formality at that point.

Exercise:

• Compute the bounds of an array of points in compute_screen_bounds

  • Go through all points
  • The minimum is the minimum of all points (per coordinate)
  • The maximum is the maximum of all points (per coordinate)
  • You can do it by hand or use the cwiseMin and cwiseMax functions. Just be careful, that both inputs need to have the same size

• Handle all cases in the fill_triangle_area function

  • Use the viewport dimension and the computed triangle dimensions to handle the cases in draw.js

    • Constrain the object bounds to the viewport as described above
    • If any of the minimum coordinates are greater than the maximum viewport or any of the maximum coordinates are less than zero, you can return, since the triangle is fully outside
    • Otherwise do a double loop through the triangle region and call img.set(vec4(1,0,0,1),x,y); for each of those points x,y.

Solution:

Now we have the area in which a triangle could potentially be. How does that help us? The basic idea is, that we will check every of the covered pixels to see if they are inside of the triangle. We will see how to do that in the next section and put it all together after that.

Is this point part of the triangle?

In the literature, you will often see the term Edge function. This term is absolutely justified, but when we arrive at chapter 06, the values will have a pretty intuitive interpretation anyways, so why not start there directly?

This part has a bit more text than usual, so if your are only interested in what to implement, you can just skip to the end and see the final formulas.

We start with a simple 2D triangle, defined by three vertices $\mathbf{v}_0,\mathbf{v}_1,\mathbf{v}_2$.

While there is no "correct" way to order the vertices, in general we use a counter-clockwise order, although in the following, we will use a variant that does not care for the order.

From the vertices, we define the two edges from the first vertex:

$$\begin{align*} \mathbf{e}_{01} &= \mathbf{v}_1 - \mathbf{v}_0 \\ \mathbf{e}_{02} &= \mathbf{v}_2 - \mathbf{v}_0 \end{align*}$$

From the properties of the cross product, we know, that $||\mathbf{a} \times \mathbf{b}||$ is the area of the parallelogram spanned by the two vectors or twice the area of the triangle subtended by them! We will now use that fact for our case. Our vectors are in 2D though. To use them with the 3D cross product is pretty easy though! Just add a third dimension and think of the vectors as lying in the $xy$-plane, with $z=0$.

$$\begin{align*} \mathbf{e}_{01} &= \begin{pmatrix}e_{01,x} \\ e_{01,y} \\ 0 \end{pmatrix}\\ \mathbf{e}_{02} &=\begin{pmatrix} e_{02,x} \\ e_{02,y} \\ 0 \end{pmatrix} \end{align*}$$

We also have:

$$\mathbf{a} \times \mathbf{b} = \begin{pmatrix} a_y b_z - a_z b_y \\ a_z b_x - a_x b_z \\ a_x b_y - a_y b_x \end{pmatrix}$$

If you look at the components, the resulting $x$ and $y$ terms all have a multiplication with a $z$ component of the inputs in them. As in our case that coordinate is $0$, only the $z$ component will survive in $\mathbf{e}_{01} \times \mathbf{e}_{01}$. To stay consistent with other resources, we will call this quantity $\operatorname{E}$.

$$\begin{align*} \operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{v}_2) &= (\mathbf{e}_{01} \times \mathbf{e}_{01})_z \\ &= e_{01,x} e_{02,y} - e_{01,y} e_{02,x} \\ &= (v_{1,x} - v_{0,x})(v_{2,y} - v_{0,y}) - (v_{1,y} - v_{0,y})(v_{2,x} - v_{0,x}) \end{align*}$$

$||\mathbf{e}_{01} \times \mathbf{e}_{01}||$ gives us twice the area of the triangle, so $\operatorname{E}$ will give us that as well, since it is the only non-zero part of the cross product. But it does have a sign! This is important and is basically why it is often called edge function. Here is a quick intution about this other way to think about it.

The normal of a vector $\mathbf{a}$ in 2D is just:

$$\mathbf{n}(\mathbf{a}) = \begin{pmatrix}-a_y \\ a_x\end{pmatrix}$$

You can check that it is perpendicular to $\mathbf{a}$ with $\mathbf{n}(\mathbf{a}) \cdot \mathbf{a} = -a_y a_x + a_x a_y = 0$. There are of course infinitely more normals (all multiples). If we fix the length to be the same as the original vector, there will still be two: The one we chose and the inverted vector. The one we chose is the usual one, as it corresponds to a rotation of $90^\circ$ in the positive mathematical direction (counter-clockwise). You can check that for example the equation will turn the $x$-axis into the $y$-axis, as one might expect. The negative direction is also sometimes used, just make sure to be consistent!

Now, from the properties of the dot product, when $\mathbf{a} \cdot \mathbf{b}$ is positive, then both vectors point in the same half space, if it is negative they point in opposite ones.

Putting the 2D normal and this fact together we get:

$$\begin{align*} \mathbf{n}(\mathbf{e}_{01}) & = \begin{pmatrix}-e_{01,y} \\ e_{01,x}\end{pmatrix} \\ \mathbf{n}(\mathbf{e}_{01}) \cdot \mathbf{e}_{02} &= -e_{01,y} e_{01,x} + e_{01,x}e_{02,y} \\ &= e_{01,x}e_{02,y}-e_{01,y} e_{01,x} \\ &= \operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{v}_2) \end{align*}$$

So we get a positive value, if $\mathbf{e}_{02}$ points above (the same direction as the normal) of $\mathbf{e}_{01}$ and a negative one otherwise.

Now, if we plug in a generic third point $\mathbf{p}$, instead of the third triangle vertex, we get:

$$\operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{p}) = (v_{1,x} - v_{0,x})(p_{y} - v_{0,y}) - (v_{1,y} - v_{0,y})(p_{x} - v_{0,x})$$

This value will accordingly be positive, if $\mathbf{p}$ is above (inside) or below (outside) the triangle edge $\mathbf{n}(\mathbf{e}_{01})$.

This is where we have the "Edge function" interpretation. We can now define a triangle as all points, for which the three edge functions $\operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{p}), \operatorname{E}(\mathbf{v}_1,\mathbf{v}_2,\mathbf{p}), \operatorname{E}(\mathbf{v}_2,\mathbf{v}_0,\mathbf{p})$ agree, that the point is inside (all have positive or zero value)! We could implement the triangle rasterization with this alone, but just to keep later code smaller, we directly modify this.

With our original interpretation, $\operatorname{E}$ giving us twice the area of the triangle spanned by the parameters, we can still use the insight of the edge function. The "area" will get a positive sign, if the triangle is counter-clockwise and a negative sign otherwise!

The triangle area interpretation is nice, since it leads us to another very useful tool: Barycentric coordinates.

For a triangle, barycentric coordinates assign three coordinates $u,v,w$ to any point. Each weight corresponds to a point on the triangle and represent how much "influence" they have. The sum $u+v+w$ equals $1$, which means, that the "total weight" of the points will always be $1$, that is, we do not add or remove weight.

Now, how to compute barycentric coordinates? With our area interpretation, we are already nearly there. Think about a point $\mathbf{p}$ inside the triangle. Connect it to the three triangle points. Now you have three new triangles! Of course, if you sum their areas, we get the total area of the triangle. In other words, if we divide each of the subtriangle areas by the total area, those values sum to $1$. So we have already found the barycentric coordinates!

It makes sense, that the weight of a point is $1$ (the full weight) the point itself. We used the definition $\operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{p})$ with the third point being variable and the first two fixed. So it makes sense, that the triangle point that is not fixed is the one associated with the barycentric weight, as it will get stronger, if $\mathbf{p}$ moves away from the edge (towards the last point). So $\operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{p})$ is associated to the missing point $\mathbf{v}_2$. $\operatorname{E}$ gives twice the area for the subtriangles, as well as the full triangles. In their ratio, the factor $2$ cancels out and thus corresponds to the ratio of the subtriangle to the triangle!

So we get the three barycentric weights:

$$\begin{align*} 2A &= \operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{v}_2) \\ u = \operatorname{weight}(\mathbf{v}_0) &= \frac{\operatorname{E}(\mathbf{v}_1,\mathbf{v}_2,\mathbf{p})}{2A}\\ v = \operatorname{weight}(\mathbf{v}_1) &= \frac{\operatorname{E}(\mathbf{v}_2,\mathbf{v}_0,\mathbf{p})}{2A}\\ w = \operatorname{weight}(\mathbf{v}_2) &= \frac{\operatorname{E}(\mathbf{v}_0,\mathbf{v}_1,\mathbf{p})}{2A}\\ \end{align*}$$

Since the coordinates sum to $1$ you only need to calculate two of them, for example $v$ and $w$ and compute the third one as $1 - v - w$.

We only need to worry about one thing: A zero triangle area. In that case, we would divide by $0$. This is easy to handle though, if the area is zero, we just don't draw the triangle

The fun thing is, that this works, even if $\mathbf{p}$ is outside of the triangle! In those cases, the sign of at least one of the subtriangles will get the opposite sign of the full triangle (due to the property of the edge function which signifies the side of an edge)! The remaining weights will become greater than $1$ to balance that out. So just as with the edge functions, we can check, if any of the weights gets negative, if it does, then the point is outside of the triangle. In contrast to the pure edge function, this works regardless of whether the triangle is clock or counter-clockwise (the division by the signed area takes care of that).

Here you can see a visualization of the whole thing.

With all of that, we can finally calculate the barycentric weights for any point and decide if the point is part of the triangle. For now, we will put this in the last bit of code. In the next step, we will add this to the full rasterizer, as it needs just a bit of extra busywork, but it will nicely allow us to draw both any number of lines as well as triangles together!

Down below you can run the solution.

Exercise:

• Implement the signed_tri_area_doubled function according to $(v_{1,x} - v_{0,x})(v_{2,y} - v_{0,y}) - (v_{1,y} - v_{0,y})(v_{2,x} - v_{0,x})$

• Implement the containment test in compute_screen_bounds

  • Follow the instructions in code

Solution:

For some interesting things to try out you can do the following:

• Instead of the fixed red color, write out $u,v,w$ as rgb colors (the first 3 entries in the vec4 written into the image)
• Don't continue, if a coordinate is negative. Make sure, the rgb values written out stay in the range [0,1] (Remember, that barycentric coordinates can get negative and larger than 1 in absolute value outside of the triangle!)