Assignment 1 Lecture Notes

The following will act as lecture notes to help you review the material from lecture for the assignment. You can click on the links below to get directed to the appropriate section.

• Section 1: Geometric Transformations
• Section 2: World Space to Camera Space
• Section 3: Perspective Projection
• Section 4: Line Rasterization

Section 1: Geometric Transformations

Geometric transformations are ubiquitous in computer graphics. The three main geometric transformations that we use are translation, rotation, and scaling. We find it convenient to implement these transformations as matrix operations. This requires us to work with homogeneous coordinates instead of the usual Cartesian coordinates. For a given point $p$ in three dimensional space with Cartesian coordinates $\left(X,Y,Z\right)$, we express it in homogeneous coordinates $\left(x,y,z,w\right)$ where $w$ is known as the homogeneous component. The following shows the general mapping between Cartesian and homogeneous coordinates for three dimensions:

$$\left(X,Y,Z\right)\to \left(x,y,z,w\right)\left\{\begin{array}{c}X=\frac{x}{w}\hfill \\ Y=\frac{y}{w}\hfill \\ Z=\frac{z}{w}\hfill \end{array}\right.$$

Homogeneous coordinates allow us to represent geometric transformations in matrix form and their operation on points as simple matrix multiplications. Consider the translation operation. In Cartesian coordinates, the translation of a point $p$ at position $\left(x,y,z\right)$ by a vector $v=\left(v_x,v_y,v_z\right)$ shifts it to the new position $\left(x+v_x,y+v_y,z+v_z\right)$. We can implement this operation as a matrix multiplication by expressing translation in the following matrix form:

$$T=\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill v_x\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill v_y\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill v_z\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]$$

and then multiplying the translation matrix with the homogeneous representation of $p$ (letting the $w$ component equal 1):

$$\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill v_x\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill v_y\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill v_z\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill z\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill x+v_x\hfill \\ \hfill y+v_y\hfill \\ \hfill z+v_z\hfill \\ \hfill 1\hfill \end{array}\right]$$

As you can see, our result is the homogeneous representation of the new position with the homogeneous $w$ component equal to 1.

Rotation and scaling are achieved similarly. The following matirx is the rotation matrix for rotating about an axis in the direction of the unit vector $u=\left(u_x,u_y,u_z\right)$ counterclockwise by an angle $\theta$:

$$R=\left[\begin{array}{cccc}\hfill u_x^2+\left(1-u_x^2\right)cos\theta \hfill & \hfill u_x{u}_y\left(1-cos\theta \right)-u_{z}sin\theta \hfill & \hfill u_x{u}_z\left(1-cos\theta \right)+u_{y}sin\theta \hfill & \hfill 0\hfill \\ \hfill u_y{u}_x\left(1-cos\theta \right)+u_{z}sin\theta \hfill & \hfill u_y^2+\left(1-u_y^2\right)cos\theta \hfill & \hfill u_y{u}_z\left(1-cos\theta \right)-u_{x}sin\theta \hfill & \hfill 0\hfill \\ \hfill u_z{u}_x\left(1-cos\theta \right)-u_{y}sin\theta \hfill & \hfill u_z{u}_y\left(1-cos\theta \right)+u_{x}sin\theta \hfill & \hfill u_z^2+\left(1-u_z^2\right)cos\theta \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]$$

And the following is the scaling matrix for scaling the coordinates of a point by the vector $v=\left(v_x,v_y,v_z\right)$:

$$S=\left[\begin{array}{cccc}\hfill v_x\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill v_y\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill v_z\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]$$

And of course, consecutive transformations can be combined into a single matrix representation. For instance, a scaling by vector $s=\left(s_x,s_y,s_z\right)$ followed by a translation by vector $t=\left(t_x,t_y,t_z\right)$ of a point at $\left(x,y,z\right)$ can be given as:

$$\left[\begin{array}{cccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill t_x\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill t_y\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill t_z\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{cccc}\hfill s_x\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill s_y\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill s_z\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill z\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{cccc}\hfill s_x\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill t_x\hfill \\ \hfill 0\hfill & \hfill s_y\hfill & \hfill 0\hfill & \hfill t_y\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill s_z\hfill & \hfill t_z\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill z\hfill \\ \hfill 1\hfill \end{array}\right]$$

Section 2: World Space to Camera Space

Rendering in computer graphics is all about turning a mathematical model of a scene into an image that we can perceive. We refer to the coordinate space containing the points in our scene as the world space. Figure 1 shows the world space axes. Note that the coordinate axes here differ slightly from the traditional 3D axes in mathematics.

In order to obtain an image of our scene, we need to specify in world space a viewing location and angle from which we look. Consider Figure 2:

Let the face mesh shown above be centered at the origin of our world space. Our default viewing location is at the origin and our default viewing angle causes us to look straight ahead in the direction of the negative z-axis. We can consider the image on the left as what we would see after moving or translating to some point along the positive z-axis. The image on the right would be what we see after we first rotate ourselves 90 degrees clockwise about the y-axis and then translate to some point along the negative x-axis.

We refer to our viewing location as the camera position and the viewing angle as the camera orientation - i.e. we consider ourselves to be looking at our scene through a camera. From the above example, we can see that it would be intuitive to specify the camera position with a translation vector and the camera orientation with a rotation axis and angle. Hence, whenever we set up a camera, we always rotate it by a specified angle about a specified axis and then translate it to a specified point.

Denote the translation matrix for the camera position as $T_c$ and the rotation matrix for the camera orientation as $R_c$. Then let $C=T_c{R}_c$ be the matrix describing the overall transformation for the camera. Suppose that after we set up the camera, we want to transform the entire world space into a new space with the camera at the origin and in its default orientation. This new space, which we call the camera space, provides some advantages that we will see in the next section. We can intuitively see that in order to go from world space to camera space, we apply the inverse camera transform, $C^{-1}$, to every point in world space.

Note that the terms eye position, eye orientation, and eye space are sometimes used instead of their respective camera counterparts. Their usage is just a terminology preference, and there are no differences in the meanings. For this class, we will use the camera terms, but we should also be aware that the eye terms exist.

Section 3: Perspective Projection

When we look at a scene in real life with our eyes, objects further in the distance appear smaller than objects close by. The technical term for this effect is perspective. We want to reproduce this effect when we render scenes in computer graphics to make them look realistic. We can do so with the following process. We first surround our scene in camera space with a sideways frustum, which, when upright, is the bottom half of a square pyramid that has been cut in two along a plane perpendicular to the axis connecting the tip of the pyramid and the center of the square base. We map every point in the sideways frustum to a cube with what is called a perspective projection. A visual of the mapping is provided in Figure 3.

The key idea here is that all of the frustum beyond the smaller base (outlined in red in Figure 3) must shrink in order to form the cube. For the frustum to shrink, points in the frustum must be clustered closer together. The further away a set of points is from the smaller base of the frustum, the closer together the points are clustered. This clustering causes the objects that those points form to shrink and get rendered smaller than their actual size, creating the desired perspective effect.

The cube resides in its own coordinate system known as normalized device coordinates or NDC for short. Note that this coordinate system has an inverted z-axis. This is due to convention.

We specify a perspective projection with parameters for the dimensions of the frustum. $l,r,t,b$ stand for left, right, top, bottom and provide the dimensions for the smaller base of the frustum, which we will now call the near plane or projection plane. $n$ stands for near and specifies in camera space the magnitude of the negative z-coordinate of where the frustum begins. $f$ stands for far and specifies in camera space the magnitude of the negative z-coordinate of where the frustum ends.

We will now do a quick derivation of the perspective projection matrix, which transforms points from camera space into NDC given $l,r,t,b,n,$ and $f$. We first look at just the $x$ and $y$ coordinate mappings. Let $\left(x_c,y_c,z_c,1\right)$ be the position of a point in our camera space and $\left(x_{ndc},y_{ndc},z_{ndc},w_{ndc}\right)$ be the same position in homogeneous NDC.

Recall that the projection plane of the frustum is mapped directly to the front of the cube. Since the $x_c\to x_{ndc}$ and $y_c\to y_{ndc}$ mappings do not need to take depth (i.e. the z-coordinate) into account, we can consider them as first mapping pairs of $\left(x_c,y_c\right)$ onto the projection plane, and then mapping the projection plane onto a cube face. Let $x_p$ and $y_p$ be the corresponding $x$ and $y$ coordinates on the projection plane. Figure 4 shows a visual of $x_c\to x_p$. A similar idea is used for $y_c\to y_p$.

The values of $x_p$ and $y_p$ are determined using ratios of similar triangles:

$$\begin{array}{ccc}\frac{x_p}{x_c}=\frac{-n}{z_c}\hfill & \hfill ,\hfill & \frac{y_p}{y_c}=\frac{-n}{z_c}\hfill \end{array}$$

This gives us $x_c\to x_p=-\frac{n}{z_c}{x}_c$ and $y_c\to y_p=-\frac{n}{z_c}{y}_c$. We then get the direct mappings for $x_p\to x_{ndc}$ and $y_p\to y_{ndc}$ by solving the linear equations for $\left[l,r\right]\to \left[-1,1\right]$ and $\left[b,t\right]\to \left[-1,1\right]$.

$$\begin{array}{ccc}{x}_{ndc}=\frac{1-\left(-1\right)}{r-l}{x}_p+{\beta }_x\hfill & \hfill ,\hfill & x_p=r\to x_{ndc}=1\hfill \end{array}$$

$$\begin{array}{ccc}{y}_{ndc}=\frac{1-\left(-1\right)}{t-b}{y}_p+{\beta }_y\hfill & \hfill ,\hfill & y_p=t\to y_{ndc}=1\hfill \end{array}$$

where ${\beta }_x$ and ${\beta }_y$ are constants that we need to solve for. Solving the above equations and substituting in $x_p=-\frac{n}{z_c}{x}_c$ and $y_p=-\frac{n}{z_c}{y}_c$ yields:

$$\begin{array}{ccc}{x}_c\to x_{ndc}=\frac{\left(\frac{2n}{r-l}{x}_c+\frac{r+l}{r-l}{z}_c\right)}{-z_c}\hfill & \hfill ,\hfill & y_c\to y_{ndc}=\frac{\left(\frac{2n}{t-b}{y}_c+\frac{t+b}{t-b}{z}_c\right)}{-z_c}\hfill \end{array}$$

Recall that we are working in homogeneous coordinates, hence our perspective projection matrix is going to need to accommodate for the $w$ component. What we can do is take advantage of the fact that both $x_{ndc}$ and $y_{ndc}$ have a division by $-z_c$ and make $w_{ndc}=-z_c$ while making $x_{ndc}$ and $y_{ndc}$ equal to just their respective numerator portions from the above equations. We then have:

$$\left[\begin{array}{c}\hfill x_{ndc}\hfill \\ \hfill y_{ndc}\hfill \\ \hfill z_{ndc}\hfill \\ \hfill w_{ndc}\hfill \end{array}\right]=\left[\begin{array}{cccc}\hfill \frac{2n}{r-l}\hfill & \hfill 0\hfill & \hfill \frac{r+l}{r-l}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \frac{2n}{t-b}\hfill & \hfill \frac{t+b}{t-b}\hfill & \hfill 0\hfill \\ \hfill .\hfill & \hfill .\hfill & \hfill .\hfill & \hfill .\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_c\hfill \\ \hfill y_c\hfill \\ \hfill z_c\hfill \\ \hfill 1\hfill \end{array}\right]$$

For the third row, we use the fact that $z$ does not depend on $x$ or $y$ to write:

$$\left[\begin{array}{c}\hfill x_{ndc}\hfill \\ \hfill y_{ndc}\hfill \\ \hfill z_{ndc}\hfill \\ \hfill w_{ndc}\hfill \end{array}\right]=\left[\begin{array}{cccc}\hfill \frac{2n}{r-l}\hfill & \hfill 0\hfill & \hfill \frac{r+l}{r-l}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \frac{2n}{t-b}\hfill & \hfill \frac{t+b}{t-b}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill A\hfill & \hfill B\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_c\hfill \\ \hfill y_c\hfill \\ \hfill z_c\hfill \\ \hfill 1\hfill \end{array}\right]$$

for coefficients $A$ and $B$. We then have:

$$\frac{z_{ndc}}{w_{ndc}}=\frac{A{z}_c+B}{-z_c}$$

Using the mappings $-n\to -1$ and $-f\to 1$ and doing some algebra gives us $A$ and $B$ and:

$$P=\left[\begin{array}{cccc}\hfill \frac{2n}{r-l}\hfill & \hfill 0\hfill & \hfill \frac{r+l}{r-l}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \frac{2n}{t-b}\hfill & \hfill \frac{t+b}{t-b}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \frac{-\left(f+n\right)}{f-n}\hfill & \hfill \frac{-2fn}{f-n}\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right]$$

as the perspective projection matrix. This is the transformation matrix we use to transform a point in camera space to the homogeneous NDC. To go from homogeneous NDC to Cartesian NDC, we would divide our $x_{ndc},y_{ndc},$ and $z_{ndc}$ terms by $w_{ndc}=-z_c$.

Note that sometimes the frustum we specify does not capture our entire scene, in which case, the points that were outside our frustum in camera space are mapped to the outside of the cube in NDC. These points are outside our field of view and should not be considered for rendering. Hence, when we later render what we see, we need to check for whether a given point is outside the cube. If it is, then we do not render the point.

Section 4: Line Rasterization

We render our 3D scene by mapping all of its points in NDC onto a 2D grid of square pixels that we then display onto the screen. This process is known as rasterization. For each point in NDC, we map its $x$ and $y$ coordinates to a row (r) and column (c) ordered pair with $x\to c$ and $y\to r$. We then fill the pixel at $\left(r,c\right)$ to show the point in the display. The $z$ coordinate of our point is used for depth buffering and backface culling, which we will cover on the next assignment. Sometimes, the coordinates for the grid are referred to as screen coordinates.

In this section, we will talk specifically about line rasterization. In order to rasterize a line with a grid of pixels, we must decide which squares around the line form the best approximation of the line when filled. Figure 5 shows a visual of this in action:

The fastest and simplest algorithm that does this is Bresenham’s line algorithm.

The basic Bresenham’s algorithm only works in one octant of the 2D coordinate plane, but it can be generalized to account for the other octants. The generalization will be left as an exercise in the assignment. For now, we will restrict ourselves to discussing the algorithm in just the first octant - i.e. line slopes are in the range $0\le m\le 1$. Since it is more natural to talk about lines in terms of $x$ and $y$, we are going to use $x$ to refer to the column values and $y$ to refer to the row values of our grid.

So we wish to connect two points $\left(x_0,y_0\right)$ and $\left(x_1,y_1\right)$ in the first octant of our grid with an approximation of a line. Let us decide to iterate over the x-coordinate. Then during our routine, if we had just filled in the pixel for some integral point $\left(x,y\right)$ for $x_0\le x\le x_1$ and $y_0\le y\le y_1$, then the next pixel we fill in will have to be either at $\left(x+1,y\right)$ or $\left(x+1,y+1\right)$. We must decide which one of these points results in a better approximation of the line.

Let $\epsilon$ denote the error between $y$ of the integral point $\left(x,y\right)$ and the true $y$ in the actual line. The true $y$ is then equal to $y+\epsilon$. When moving from $x$ to $x+1$, we increase the true $y$ by the slope $m$. Consider the case where $y+\epsilon +m$ is less than the midpoint of $y$ and $y+1$ - i.e. $y+\epsilon +m<y+0.5$. If that is the case, then the next point in our line is closer to the pixel at $\left(x+1,y\right)$ than the pixel at $\left(x+1,y+1\right)$. Hence, the next pixel that we would want to fill is at $\left(x+1,y\right)$. We would then update $\epsilon$ as $\epsilon \leftarrow \left(y+\epsilon +m\right)-y$. However, if $y+\epsilon +m\ge y+0.5$, then the next pixel should be at $\left(x+1,y+1\right)$ and we would update $\epsilon$ as $\epsilon \leftarrow \left(y+\epsilon +m\right)-\left(y+1\right)$. This leads us to the following algorithm:

We can optimize this algorithm by eliminating any dependence on floating point values. Consider the following manipulations on the inequality:

$$\epsilon +m<0.5$$

$$\epsilon +\frac{y_1-y_0}{x_1-x_0}<0.5$$

$$\epsilon +\frac{dy}{dx}<0.5$$

$$2\epsilon dx+2dy<dx$$

Let ${\epsilon }^{\prime }\leftarrow \epsilon dx$. Our inequality becomes:

$$2\left({\epsilon }^{\prime }+dy\right)<dx$$

And we can express $\epsilon \leftarrow \epsilon +m$ and $\epsilon \leftarrow \epsilon +m-1$ as ${\epsilon }^{\prime }\leftarrow {\epsilon }^{\prime }+dy$ and ${\epsilon }^{\prime }\leftarrow {\epsilon }^{\prime }+dy-dx$ respectively. This leads us to an algorithm with operations that involve only integers:

Note how the only operations in this algorithm are simple (and fast) arithmetic operations between integers. In addition, the multiplication by 2 can be implemented using a bit-shift. Hence, we end up with a fast and efficient line drawing algorithm for the first octant. The generalization to all octants will also maintain the simplicity and efficiency. As we mentioned before, the generalization will be left as an exercise in the assignment.