Graphics Notes

Introduction

There are three main disciplines of graphics: modeling shape and appearance, animation, and rendering.

Modeling

Raster (bitmap) graphics have a fixed array of pixels with values, and a fixed resolution. Vector graphics are driven by display commands. It has a scalable resolution, which makes it ideal for typography and animation.

Rendering

The main question rendering aims to answer is: how do we make a 3D picture appear on a 2D plane?

There are two ways to think about the problem:

For every point on the paper, determine which object appears at the point
For every object in the scene, determine which points on the paper it covers

These two approaches correspond to two major classes of rendering algorithms: raytracing and rasterization.

Raytracing and rasterization

Raster Graphics

Images and Pixels

An image is a 2D grid of cells called pixels, where each pixel holds some set of values. A pixel (picture + element) is a unit with some kind of value. A pixel value can represent intensity (grayscale), color (RGB), opacity, or depth.

In the grayscale image below, each pixel requires only one value to encode its intensity. By convention, 0 is the lowest intensity (black) and 1 is the highest intensity (white).

Grayscale image

In a RGBA image, each pixel has four distinct values, which each represents red, green, blue, and alpha. Each value ranges from 0 to 255.

RGBA image

An RGB value of (255, 0, 0) gives us red, (0, 255, 0) gives us green, and (0, 0, 255) gives us blue. Surprisingly, an RGB value of (255, 255, 255) gives us pure white. This is because we are working with light from the computer screen rather than pigment from paint. This gives us additive color rather than subtractive color.

Datatypes and Memory

Notice that intensity is represented with a float64, while color is represented with a uint8. The reason we use uint8 for RGB images is that float64 takes up a lot of storage. If we used floats for RGBA images, each pixel would require 16 bytes, and a 1000 x 1000 image would take up 16 MB of memory.

Most displays today use 24-bit true color, which is 8 bits per color channel. Since each color channel has $2^8 = 256$ distinct values, we generate $256^4 \approx 17$ million different RGB colors. The human eye can discriminate only around 10 million colors, so this is generally sufficient. However, humans are fairly good at noticing uneven changes in color in color banding, which can be undesirable.

There are multiple ways to store images in memory:

Array of structs (AoS), where each struct represents an RGB value
Struct of arrays (SoA), where each array represents a R, G, or B channel Different memory organizations affect cache locality.

It is also common to store 2D arrays of data in 1D data structures. There are two common ways of doing this: (1) row-major ordering and (2) column-major ordering.

Row and column major ordering

References:

Vector Graphics

Pipeline

To create a 2D vector graphic:

Define object geometry
Transform object (translate, rotate, scale)
Define "window" on the world
Render into raster graphics

In each of the steps of this pipeline, there are many different coordinate systems:

Object space is the local coordinate system in which a single object is defined
World space is the global coordinate system for the scene
Camera space is the coordinate system defined by the camera through which the scene is viewed

Why use multiple coordinate systems?

We want to keep different layers modular, so we can modify each independently. For example, we may want to scale or rotate individual objects. If all objects are defined in terms of world space, then there may not be a linear matrix transformation to do this.

Also, at higher levels of abstraction, we don't want to think about specific device coordinates to draw to. We may have to later consider the resolution of the device (normalized device coordinates) and the viewport of the OS window that the application runs in (screen space).

Transformations

Vectors

A vector transforms a scalar into another scalar. Below, we transform the scalar $(x, y)$ by shifting it $a$ units right and $b$ units up.

(x, y) + \begin{bmatrix} a \\ b \end{bmatrix} = (x + a, y + b)

The dot product is a scalar representation of how similar two vectors are to each other.

\begin{bmatrix} a \\ b \end{bmatrix} \cdot \begin{bmatrix} c \\ d \end{bmatrix} = ac + bd

Geometric interpretations of the dot product:

$\begin{bmatrix} a \\ b \end{bmatrix}^2 = a^2 + b^2$ is the squared length of the vector
$\begin{bmatrix} a \\ b \end{bmatrix} \cdot \begin{bmatrix} c \\ d \end{bmatrix} = 0$ when the vectors are perpendicular
$v \cdot w = |v||w|\cos(\theta)$ , where $\theta$ is the angle between the arrows

The cross product takes in two vectors and produces a vector that is mutually perpendicular to both vectors. By convention, the direction that $a \times b$ points in is determined by the right-hand rule.

a \times b = \begin{bmatrix} a_2b_3 - a_3b_2 \\ a_3b_1 - a_1b_3 \\ a_1b_2 - a_2b_1 \end{bmatrix}

Geometric interpretations of the cross-product:

$a \times b = |a||b| \sin(\theta)$
$a \times b$ also gives the area of the parallelogram with $a$ and $b$ as edges. Half of this area gives us the triangle with $a$ and $b$ as edges.

Matrices

The identity matrix is a matrix such that $MI = IM = M$ for all matrices $M$ . The 2x2 identity matrix is:

\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

If we have two matrices $M$ and $K$ such that $MK = I$ , then we say that $K$ is the inverse of $M$ . Not all matrices have an inverse. For a 2x2 matrix, we have:

\begin{bmatrix} a & b \\ c & d \end{bmatrix} \frac{1}{ad - bc} \begin{bmatrix} d & -c \\ -b & a \end{bmatrix} = I

Transformations

A transformation $T$ is a function that acts on space.

A linear transformation respects the property $T(a\hat{u} + b\hat{v}) = aT(\hat{u}) + bT(\hat{v})$
A matrix transformation is any transformation that can be written in terms of multiplying a matrix and a vector
Every linear transformation is a matrix transformation

Note that matrix transformations can compose. For example, applying $M$ then $K$ to vector $v$ is equivalent to $K(Mv) = (KM)v$ .

We can build matrix transformations using basis vectors. To find a matrix $M$ that sends:

\begin{equation*} e_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \text{to} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \quad\mathrm{and}\quad e_2 = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \text{to} \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \end{equation*}

We need to find a matrix that satisfies:

\begin{equation*} \begin{bmatrix} a & b \\ c & d\end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \quad\mathrm{and}\quad \begin{bmatrix} a & b \\ c & d\end{bmatrix}\begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \end{equation*}

Arithmetically, this matrix is

\begin{bmatrix} x_1 & y_1 \\ x_2 & y_2\end{bmatrix}

To reverse the transformation, we can simply calculate the inverse of $M$ .

Thus, to send

\begin{equation*} \begin{bmatrix} a_1 \\ a_2 \end{bmatrix} \text{to} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \quad\mathrm{and}\quad \begin{bmatrix} b_1 \\ b_2 \end{bmatrix} \text{to} \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \end{equation*}

We can simply calculate the matrix $M$ that sends

\begin{equation*} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \text{to} \begin{bmatrix} a_1 \\ a_2 \end{bmatrix} \quad\mathrm{and}\quad \begin{bmatrix} 0 \\ 1 \end{bmatrix} \text{to} \begin{bmatrix} b_1 \\ b_2 \end{bmatrix} \end{equation*}

And the matrix $K$ that sends

\begin{equation*} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \text{to} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \quad\mathrm{and}\quad \begin{bmatrix} 0 \\ 1 \end{bmatrix} \text{to} \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} \end{equation*}

And then calculate $K(M^{-1})$ .

Scale, Rotate, and Translate

Both scale and rotate are linear transformations and can be represented by matrix transformations.

To scale by $s_x$ in the x-axis and scale by $s_y$ in the y-axis, apply the matrix:
$\begin{bmatrix} s_x & 0 \\ 0 & s_y \\ \end{bmatrix}$
To rotate by $\theta$ counterclockwise, apply the matrix:
$\begin{bmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \\ \end{bmatrix}$

Translation is not a linear transformation; it is an affine transformation. In order to represent it as a matrix transformation, we add another dimension to it. This is called homogeneous coordinates.

$w$ is $1$ if the value is a scalars and $0$ if the value is a vector
$w$ does not affect subtraction of two scalars (which produces a vector), addition of a vector and a scalar (which produces a scalar), or dot product (which is mostly between two vectors)
$w$ also does not affect the linearity of scaling and rotation $\begin{equation*} \begin{bmatrix} a & b \\ c & d\end{bmatrix} \quad\rightarrow\quad \begin{bmatrix} a & b & 0 \\ c & d & 0 \\ 0 & 0 & 1\end{bmatrix} \end{equation*}$

To translate $dx$ in the x-axis and $dy$ in the y-axis, apply the matrix:

\begin{bmatrix} 1 & 0 & dx \\ 0 & 1 & dy \\ 0 & 0 & 1\end{bmatrix}

Algorithmically, this works to out be:

\begin{bmatrix} 1 & 0 & dx \\ 0 & 1 & dy \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} x \\ y \\ 1\end{bmatrix} = \begin{bmatrix} x + dx \\ y + dy \\ w\end{bmatrix}

Note that the order of the transformations matters. The most widely used ordering is TRS, which means to scale, rotate, and then translate.

References:

CSCI 1230 Lab 3

Non-Axis Aligned 3D Rotation

Scaling and translation in 3D is similar to that in 2D. Rotations are more complicated because we can now rotate around an arbitrary axis. There are several ways to do this: Euler angles, axis-angles, and quaternions.

Euler angles are a composition of rotations around the x, y, and z axes.

The rotation matrices for each axis, by angle $\theta$ , are:

R_x(\theta) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos\theta & -\sin\theta \\ 0 & \sin\theta & \cos\theta \end{bmatrix}

R_y(\theta) = \begin{bmatrix} \cos\theta & 0 & \sin\theta \\ 0 & 1 & 0 \\ -\sin\theta & 0 & \cos\theta \end{bmatrix}

R_z(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}

A full Euler angle rotation is the composition $R = R_z(\theta_z) R_y(\theta_y) R_x(\theta_x)$ , applied right to left.

There are several problems with Euler angles. First, they don't trace the shortest rotational path because they don't follow the geodesic. To fix that, we can linearly interpolate each angle independently with some correction factor. However, this does not produce an even angular velocity. Also, when two rotation axes become parallel, we lose a degree of freedom, leading to odd behavior at the point.

Axis-angle rotations involve decomposing a point $x$ into two parts relative to the axis $r$ :

$x_\parallel$ is the part parallel to $r$ ; rotation does not change it
$x_\perp$ is the part perpendicular to $r$ ; it rotates like a 2D point in a plain perpendicular to $r$

To calculate it, we need:

x' = x_\parallel + x\vdash\sin(\theta) + x_\perp\cos(\theta)

Which can be expanded to:

x' = (\hat{r}(\hat{r} \cdot x)) + (\hat{r} \times x)\sin(\theta) + (-\hat{r} \times (\hat{r} \times x))\cos(\theta)

The formula for the cross product can be represented as a matrix, so this entire equation can be rewritten in matrix form. Unfortunately, axis-angle rotations also do not sweep the shortest path between two points.

Quaternions are the only rotation method that can correctly do linear interpolation. A quaternion represents a rotation as a point on the surface of a 4D hypersphere. Because we are moving along the sphere, we get shortest path and constant angular velocity.

References: Visualizing quaternions

Views

View Volume

A view volume contains everything the camera sees

A conical volume approximates what the eyes can see
A frustrum is a rectangular pyramid which approximates the conical view volume
A parallel volume doesn't stimulate the eye or camera

The 3D is projected onto the view plane sitting in world space. It should be perpendicular and centered around the look vector. It should also be located somewhere between the eye and the scene.

The parameters of the view volume are:

Position
Look vector
Orientation (often represented by up vector)
Aspect ratio
View angle

A view angle determines the amount of perspective distortion in the picture. It is equivalent to a photographer choosing a specific type of lens (e.g. wide-angle or telephoto lens). In a frustrum, there is both a height angle and a width angle.

View angle

Camera Space

The position, look vector, and up vector are enough to define the camera coordinate system. The equivalent of $x$ , $y$ , and $z$ world coordinate axes in camera space are unit vectors $u$ , $v$ , and $w$ .

$w$ is in the opposite direction of the look vector
$v$ is the component of the up vector that is perpendicular to the look vector
$u$ is the vector perpendicular to both $w$ and $v$

w = \frac{-look}{\|look\|} \qquad v = \frac{up - (up \cdot w)w}{\|up - (up \cdot w) w\|} \qquad u = v \times w

Camera vector and axes

Having a camera coordinate system allows us to change the orientation of the camera:

Roll: rotate camera around look
Yaw: rotate camera around $v$
Pitch: rotate camera around $u$

Roll, yaw, and pitch

The canonical camera space is one where the camera sits at the origin, looks down at $-z$ , and is oriented such that $y$ is up. The view matrix transforms objects from world space into camera space.

View matrix

Suppose that the camera is in position $P$ in world space. The view matrix is made from a translation that moves the world by $-P$ , followed by a rotation that aligns $u$ , $v$ , $w$ with $x$ , $y$ , $z$ .

Note that a matrix $A$ with columns [ $u$ , $v$ , $w$ ] transforms the $x$ , $y$ , $z$ axes to $u$ , $v$ , $w$ directions. The inverse of $A$ does the opposite. As it turns out, because $A$ is a orthonormal matrix, the inverse of $A$ is just its transpose.

M_{\text{translate}} = \begin{bmatrix} 1 & 0 & 0 & -P_x \\ 0 & 1 & 0 & -P_y \\ 0 & 0 & 1 & -P_z \\ 0 & 0 & 0 & 1 \end{bmatrix}

M_{\text{rotate}} = \begin{bmatrix} u_x & u_y & u_z & 0 \\ v_x & v_y & v_z & 0 \\ w_x & w_y & w_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}

By putting the rotation and translation together, we get one matrix for transforming other objects into the camera's coordinate system.

M_{\text{view}} = M_{\text{rotate}}M_{\text{translate}}

Note that the view matrix does translation first and then rotation. This is because the matrix that transforms the camera to world space is composed of a rotation first and then a translation. The view matrix is the inverse of this matrix, so we must reverse the order of multiplication.

Scenes

Graphics applications typically represent scenes with a DAG which stores:

Objects
Attributes (color, texture)
Transformations

To get the cumulative transformation matrix of an object, simply multiple the transforms along the path from the object node to the root. For example, to transform Object 1 to world space, first apply transformation A then C.

Scene graph example

To generalize a bit, each of the vertices building pointing up to the world root are model matrices which transform the object from object space to world space. The final matrix is a view matrix that transforms any object from world space to camera space. The inverses of these matrices provide the transformation of the opposite direction.

Model and view matrices

Raytracing

Raytracing takes the 3D objects we see at each point in camera space and projects them onto a view plane.

For each pixel, we need to solve two problems:

What object appears in the pixel?
What color should the pixel be?

To determine what object appears in the pixel, we trace a ray from the camera, through the middle of the pixel, and solve for the first point of intersection in the scene.

There are two types of rays:

Primary rays start from the camera and determine which parts of the scene are visible from the window.
Secondary rays starts at points in the scene, where the primary rays hit, and are traced to other parts of the scene. They are used to compute light effects.

Primary Rays

A primary ray should take the form $P + td$ , where $P$ is the origin of the ray and $d$ is the direction vector.

$P$ should be set to the camera's coordinates $(p_x, p_y, p_z)$ in world space.

To find the direction of the ray, we need to find the coordinates of a pixel on the view plane. If that coordinate is $(u, v, k)$ , then $d$ is simply $(p_x, p_y, p_z) - (u, v, k)$ .

Given a coordinate of a pixel $(i, j)$ on the view plane, we want to find the $(u, v, k)$ point corresponding to its center. This should be given by

(i, j) \mapsto \left(\frac{i + 0.5}{W} - 0.5, \frac{j + 0.5}{H} - 0.5\right)

Each coordinate is first shifted $0.5$ so that it is centered on the pixel. Then it is normalized by the dimensions of the scene plane so that it becomes a one-by-one grid. Finally, it is shifted by $(0.5)$ so that the center of the grid is at the origin $(0, 0)$ .

Ray-Object Intersections

Most production raytracers model shapes using triangles, but this is fairly complicated.

Ray-object intersections are easier to calculate with implicit objects. An implicit object is an object that can be definited by a function $f$ , where $f(Q) = 0$ iff $Q$ is a point on the service.

To find where a ray $P + td$ , we intersects an object, we just need to solve for the values of $t$ such that $f(P + td) = 0$ . There may be multiple values of $t$ that satisfies the equation, but we just care about the smallest, nonnegative value of $t$ .

Note that these objects are usually sitting in world space, but the implicit equations are defined in terms of object space. When solving for ray-object intersections, it is much easier to transform the ray into object space rather than transform the equation into world space.

Implicit Object Equations

A 2D circle of radius $R$ at the origin at the origin has the equation:

x^2 + y^2 - R^2 = 0

An infinite plane with a normal vector $(A, B, C)$ that is distance $D$ away from $(0, 0, 0)$ has the equation:

Ax + By + Cz + D = 0

A sphere of radius $R$ at the origin at the origin has the equation:

x^2 + y^2 + z^2 - R^2 = 0

An infinite cylinder of unit radius running along the y-axis has the equation:

x^2 + z^2 - 1 = 0

Usually, it's more useful to work with a finite object, and define bounds on the truncated unit cylinder:

x^2 + z^2 - 1 = 0,\, -0.5 \leq y \leq 0.5

We should also define the implicit equations for the top and the bottom circles making up the cylinder:

x^2 + y^2 - 1 \leq 0,\, y \in \{-0.5, 0.5\}

Lighting

Lighting is the simulation of how light interacts with objects. Because accurately simulating lighting is very hard, we usually used simplified lighting models.

Direct illumination is light striking a surface directly from a light source. Indirect illumination light bouncing off other objects toward the surface element. It is a much more difficult to simulate than direct illumination, but we can often approximate indirect illumination with direct illumination.

Light Sources

In graphics, there are three common models of light sources:

Type	Description	Parameters
Point light	A point that emits light equally in all directions	Position $p$ and light intensity $I$
Spot light	A point that emits light in a finite cone of directions	Position $p$ , light intesity $l$ , light direction $d$ , and cutoff angle $\theta$
Directional light	A light that shines in a particular direction; good for modeling the sun	Direction $d$ and light intensity $I$

Light Attenuation

Light attenuation is the idea that the amount of light illuminating an object should decrease with the square of distance. Thus, to be physically correct, when lighting a point that is distance $d$ away from a light source with intensity $I$ , we should attenuate the intensity as $I_\text{att} = \frac{I}{d^2}$ .

The problem is that this produces a very harsh lighting effect because there is no indirect illumination. Instead, we can use this hack:

I_\text{att} = f_\text{att} \cdot I = \min\left\{\frac{1}{c_1 + c_2d + c_3d^2}, 1\right\}I

Where $c_1$ , $c_2$ , and $c_3$ are experimentally defined constants.

Surface Normal Vectors

For illumination, we want to find the normal vector at the point $(x, y, z)$ . We can find this normal vector by taking the gradient at that point:

n = \nabla(x, y, z) = \left( \frac{\partial f}{\partial x}(x, y, z), \frac{\partial f}{\partial y}(x, y, z), \frac{\partial f}{\partial z}(x, y, z) \right)

Once we have calculated the normal vector in object space, we need to transform the normal vector into world space.

Note that we cannot just apply the transformation matrix $M$ because $Mn_o \neq n_w$ when there is scaling. Scaling distorts the normal in exactly the opposite sense of scale applied to a surface. For example, scaling $y$ by a factor of $2$ causes the normal to scale by $0.5$ .

The right equation is $n_w = (M^t)^{-1}n_o$ , unless the transformation includes a reflection (i.e. $\det(M) < 1$ ). The most foolproof equation is

n_w = \text{sign}(\det(M))(M^t)^{-1}n_o

BRDFs

Give a surface normal $n$ , an incoming light direction $\omega_i$ , and an outgoing light direction $\omega_o$ , the bidirectional reflectance distribution function (BRDF) describes how much incoming light is scattered in that outgoing direction:

f_r(\omega_i, \omega_o : \textbf{R}^3 \times \text{R}^3 \rightarrow [0, 1]

Some common types of BRDFs are:

Lambertian (diffuse): light scatters equally in all directions
Specular (glossy): light scatters more tightly around one direction
Mirror

The name of the Lambertian BRDF comes from Lambert's cosinne law, which states that light intensity falls off with the cosine of the angle between $\omega_i$ and $n$ : $\cos(\theta) = n \cdot \omega_i$ . Given $k_d$ as an RGB color, this gives us the Lambertian BRDF:

f_r(\omega_i, \omega_o) = k_d(n \cdot \omega_i)

Most materials are not perfectly Lambertian; most BRDFs are viewer dependent. This is where specular BRDFs. One of the most common Specular BRDFs is Phong BRDF:

f(\omega_i, \omega_o) = k_s(\cos \delta)^n = k_s(r \cdot \omega_o)^n

where:

$k_s$ is an RGB color
$\omega_o$ is the vector to the viewer
$r = 2(\omega_i \cdot n)n - \omega_i$
$\delta$ is the angle between $\omega_o$ and $r$
$n$ controls how tight the specular highlight is

Phong Illumination Model

The Phong illumination model combines what we know about modeling light sources and materials to define a way to light objects.

First, it breaks lighting into three components: 1. Ambient stands in for the effect of indirect light; it affects all surfaces equally 2. Diffuse is the effect of direct light on a surface with a dull or rough finish 3. Specular is the effect of direct light on a shiny surface when the vector to the eye is closely aligned to the light's reflected rays

Phong Lighting Model

The Phong illumination model has three terms:

\text{Color} = \text{Ambient} + \sum_{l \in \text{lights}} [\text{Diffuse} + \text{Specular}]

The full equation is:

I_\text{out} = k_a + \sum_{l \in L} f^{l}_\text{att} I^{l} k_d (n \cdot \omega^{l}_{i}) + \sum_{l \in L} f^{l}_\text{att} I^{l} k_s (r \cdot \omega_o)^n

where:

$L$ is the set of all lights in the scene
$\omega^{l}_{i}$ is the direction of light $l$
$I^l$ is the RGB intensity of light $l$
$f^l_\text{att}$ is the attenuation factor for light $l$

Note that the normal should point toward the viewer. You should check the dot product of normal with the view direction and flight the normal if it is negative.

Shading

We have to compute color for every pixel in our output image, but we don't necessarily have to evaluate the full Phong illumination equation at every equation.

Graphics systems often make the distinction between:

Lighting: what illumination model is evaluated and at what points
Shading: how every pixel is colored based on the lighting evaluations

This is mostly relevant for real-time graphics, with objects made out of polygons. With implicit objects, we usually just evaluate the exact equation at each pixel where an intersection occurs.

Common shaders include:

Flat shading: compute the normal (and lighting) once per face and apply that single color to all pixels in it
Gouraud shading: compute lighting at each vertex using the vertex normal, then linearly interpolate the resulting colors across the face
Phong shading: interpolate the normals themselves across the face, then run the lighting calculation per pixel using the interpolated normal

References:

Phong Illumination Laboratory