Computer Graphics

Projective Coordinates

Computer graphics relies on \keyword{projective (homogeneous) coordinates} for efficiently transforming geometry. As the name suggests, projective coordinates represent geometry in $\setR^n$ as the projection of higher dimensional geometry in $\setR^{n+1}$, in a way like hands making shadow puppets on a wall.

A position vector $\r \in \setR^3$ can be represented as a column vector of $3$ coordinates w.r.t the standard basis. Equivalently it can be represented in projective coordinates as a column vector in $\setR^4$ with the same $3$ coordinates and the last equal to $1$ $$ \boxed{ \r = \begin{bmatrix} x \\ y \\ z \end{bmatrix} \Leftrightarrow \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} } . $$

Projective position vectors are defined to be similar if they are scalar multiples $$ \boxed{ \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} \sim \begin{bmatrix} h x \\ h y \\ h z \\ h \end{bmatrix} = \begin{bmatrix} x' \\ y' \\ z' \\ h' \end{bmatrix} \quad \text{for} \quad h \ne 0 . } $$

Direction vector $\vec{n} \in \setR^3 - \{\vec{0}\}$ can also be represented in projective coordinates by setting the last coordinate to $0$ $$ \boxed{ \vec{n} = \begin{bmatrix} n_x \\ n_y \\ n_z \\ \end{bmatrix} \Leftrightarrow \begin{bmatrix} n_x \\ n_y \\ n_z \\ 0 \\ \end{bmatrix} \sim \begin{bmatrix} h n_x \\ h n_y \\ h n_z \\ 0 \\ \end{bmatrix} = \begin{bmatrix} n_x' \\ n_y' \\ n_z' \\ 0 \\ \end{bmatrix} \quad \text{for} \quad h \ne 0, \quad \vec{n} \in \mathbb{R}^3 - \cc{\vec{0}} } $$ Projective coordinates make explicit the difference between position and direction vectors.

Transformations

The most general linear transformation from projective coordinates to projective coordinates is the linear system of equations $$ \begin{cases} x' = M_{11} x + M_{12} y + M_{13} z + M_{14} h \\ y' = M_{21} x + M_{22} y + M_{23} z + M_{24} h \\ z' = M_{31} x + M_{32} y + M_{33} z + M_{34} h \\ h' = M_{41} x + M_{42} y + M_{43} z + M_{44} h \end{cases}. $$ In matrix notation this is written as matrix multiplying vector $$ \begin{bmatrix} x' \\ y' \\ z' \\ h' \end{bmatrix} = \begin{bmatrix} M_{11} & M_{12} & M_{13} & M_{14} \\ M_{21} & M_{22} & M_{23} & M_{24} \\ M_{31} & M_{32} & M_{33} & M_{34} \\ M_{41} & M_{42} & M_{43} & M_{44} \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ h \end{bmatrix} $$ or more compactly as $$ \r' = \mat{M} \r $$ where $$ \boxed{ \mat{M} = \begin{bmatrix} M_{11} & M_{12} & M_{13} & M_{14} \\ M_{21} & M_{22} & M_{23} & M_{24} \\ M_{31} & M_{32} & M_{33} & M_{34} \\ M_{41} & M_{42} & M_{43} & M_{44} \end{bmatrix} }. $$

Matrix $\mat{M}$ can transform many vectors at once by multiplying an augmented matrix constructed from those vectors $$ \boxed{ \begin{bmatrix} \r_1' & \r_1' & \ldots & \r_n' \end{bmatrix} = \mat{M} \begin{bmatrix} \r_1 & \r_2 & \ldots & \r_n \end{bmatrix} } . $$

Normal vectors are vectors orthogonal to a plane. They are represented by projective direction vectors, but transform differently than position vectors. Consider a plane such that position vector $\r$ is in the plane and normal vector $\vec{n}$ is orthogonal to the plane $$ \label{eqn:graphics-normal_condition} \vec{r} \dot \vec{n} = 0. $$ When $\vec{r}$ is transformed by matrix $\mat{M}$, $\vec{n}$ must be transformed by matrix $\mat{N}$ to ensure the transformed tangent and normal spaces stay orthogonal $$ [\mat{M} \vec{r}] \dot [\mat{N} \vec{n}] = 0 $$ or in matrix notation $$ [\mat{N} \vec{n}]^T [\mat{M} \vec{r}] = \vec{n}^T \mat{N}^T \mat{M} \vec{r} = 0. $$ Assuming $\mat{M}$ is invertible, this is satisfied when $\mat{N}^T = \mat{M}^{-1}$ because of Eq. \eqref{eqn:graphics-normal_condition}. Thus when position vectors are transformed by matrix $\mat{M}$, normal vectors are transformed by matrix $\mat{N} = [\mat{M}^{-1}]^T$ $$ \label{eqn:graphics-normal_transform} \boxed{ \vec{n}' = \mat{N} \vec{n} \quad \text{where} \quad \mat{N} = [\mat{M}^{-1}]^T }. $$

Transformation Library

Only a small number of linear transformations on projective coordinates are needed to synthesize a computer graphics pipeline; scaling, rotation, and translation transformations are useful for posing geometry; windowing transformations map between axis-aligned rectangular regions; and orthographic and perspective transformations determine the camera model. Complicated linear transformation can be synthesized by composing these basic transformations. When this is impossible, a general linear transformation can always be supplied.

The following sections are derived for projective position vectors, but the results also apply to projective direction vectors. Projective normal vectors transform per \eqref{eqn:graphics-normal_transform}

Scaling

Scaling transformations scale (stretch/compress) axis-aligned coordinates. This is useful to specify the size of things. The matrix representation is easy to work out $$ \begin{bmatrix} S_x x \\ S_y y \\ S_z z \\ 1 \end{bmatrix} = \begin{bmatrix} S_x & 0 & 0 & 0 \\ 0 & S_y & 0 & 0 \\ 0 & 0 & S_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} $$ where the scaling factors $S_x, S_y, S_z$ scale their respective coordinates $x, y, z$. Isolating the transformation matrix define the projection scaling matrix $$ \boxed{ \mat{M}_{\mathrm{scale3D}}(S_x, S_y, S_z) \equiv \begin{bmatrix} S_x & 0 & 0 & 0 \\ 0 & S_y & 0 & 0 \\ 0 & 0 & S_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} } . $$ This matrix is invertible if the scaling factors are non-zero.

Rotation

Rotation transformations rotate coordinates about an axis through the origin. There are a variety of ways to parameterize a rotation in matrix notation. Regardless of the parameterization, the rotation matrix elements can always be written as $$ \mat{R} = \begin{bmatrix} R_{11} & R_{12} & R_{13} \\ R_{21} & R_{22} & R_{23} \\ R_{31} & R_{32} & R_{33} \end{bmatrix} \quad \text{where} \quad \det(\mat{R}) = 1 $$ therefore the projective rotation matrix is of the form $$ \begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix} = \begin{bmatrix} R_{11} & R_{12} & R_{13} & 0 \\ R_{21} & R_{22} & R_{23} & 0 \\ R_{31} & R_{32} & R_{33} & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} $$

The axis-angle representation is developed here for its robustness and simplicity. Consider the Rodrigues rotation formula, which describes the rotation of point $\r \in \setR^3$ about unit vector $\uvec{n}$ by angle $\theta$ with the coordinate-free equation $$ \r' = \r_\parallel + \r_\perp \cos\theta + \un \cross \r_\perp \sin\theta $$ where $\r$ has been decomposed into components parallel and orthogonal to the axis. The parallel component $\r_\parallel$ in terms of the dot product is $$ \r_\parallel = \un (\un \dot \r) = \un \un^T \r $$ while the orthogonal component $\r_\perp$ is $$ \r_\perp = \r - \r_\parallel = \r - \un \un^T \r = (\mat{1} - \un \un^T) \r . $$ The cross product (a bilinear operation) is linear if one of the vectors is held constant, and thus a cross product by this constant vector can be written as a matrix equation $$ \vec{u} \cross \vec{v} = \begin{bmatrix} u_y v_z - u_z v_y \\ u_z v_x - u_x v_z \\ u_x v_y - u_y v_x \end{bmatrix} = \begin{bmatrix} 0 & -u_z & u_y \\ u_z & 0 & -u_x \\ -u_y & u_x & 0 \end{bmatrix} \vec{v} = \mat{M}_{\vec{u} \cross} \vec{v} . $$ The rotation formula in matrix notation is thus $$ \r' = \un \un^T \r + (\mat{1} - \un \un^T) \r \cos\theta + \mat{M}_{\un \cross} (\mat{1} - \un \un^T) \r . \sin\theta $$ Grouping the terms $$ \r' = (\un \un^T (1 - \cos\theta) + \mat{1} \cos\theta + \mat{M}_{\un \cross} \sin\theta + \mat{0}) \r $$ and explicitly write out the matrix elements $$ \mat{R} = \begin{bmatrix} n_x n_x & n_x n_y & n_x n_z \\ n_y n_x & n_y n_y & n_y n_z \\ n_z n_x & n_z n_y & n_z n_z \end{bmatrix} (1 - \cos\theta) + \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \cos\theta + \begin{bmatrix} 0 & -n_z & n_y \\ n_z & 0 & -n_x \\ -n_y & n_x & 0 \end{bmatrix} \sin\theta $$ and combine terms to get a rotation matrix function parameterized by an axis specified by a normal vector and an angle $\theta$ to rotate by $$ \mat{R}(\un, \theta) = \begin{bmatrix} n_x^2 C + \cos\theta & n_x n_y C - n_z \sin\theta & n_x n_z C + n_y \sin\theta \\ n_y n_x C + n_z \sin\theta & n_y^2 C + \cos\theta & n_y n_z C - n_x \sin\theta \\ n_z n_x C - n_y \sin\theta & n_z n_y C + n_x \sin\theta & n_z^2 C + \cos\theta \\ \end{bmatrix} $$ $$ \boxed{ C = 1 - \cos\theta } $$ Embedding the 3D rotation matrix into a 4D matrix, define $$ \boxed{ \mat{M}_{\mathrm{rot3D}}(\un, \theta) = \begin{bmatrix} n_x^2 C + \cos\theta & n_x n_y C - n_z \sin\theta & n_x n_z C+ n_y \sin\theta & 0\\ n_y n_x C + n_z \sin\theta & n_y^2 C + \cos\theta & n_y n_z C - n_x \sin\theta & 0\\ n_z n_x C- n_y \sin\theta & n_z n_y C+ n_x \sin\theta & n_z^2 C + \cos\theta & 0\\ 0 & 0 & 0 & 1 \end{bmatrix} } $$

Translation

Translation transformations translate coordinates. A major benefit of homogeneous coordinates is the ability to encode translations with linear transformations. Translations take the form $$ \begin{bmatrix} x + \Delta x \\ y + \Delta y \\ z + \Delta z \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & \Delta x \\ 0 & 1 & 0 & \Delta y \\ 0 & 0 & 1 & \Delta z \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} $$ Isolating the transformation matrix, define $$ \boxed{ \mat{M}_{\mathrm{trans3D}}(\Delta x, \Delta y, \Delta z) \equiv \begin{bmatrix} 1 & 0 & 0 & \Delta x \\ 0 & 1 & 0 & \Delta y \\ 0 & 0 & 1 & \Delta z \\ 0 & 0 & 0 & 1 \end{bmatrix} } $$

Windowing

Windowing transformations map one axis-aligned rectangular region to another axis-aligned rectangular region. This transformation is used to build projection matrices, and map output to pixels.

The windowing transformation is constructed from a sequence of simpler transformations; first translate the starting region to the origin, then scale the region to reshape it, and finally translate the region to the final position. Specifically (in 2D) $$ \mat{M}_{\mathrm{win2D}} = \mat{M}_{\mathrm{trans2D}}(x_0', y_0') \mat{M}_{\mathrm{scale2D}}\pp{\q{x_1' - x_0'}{x_1 - x_0}, \q{y_1' - y_0'}{y_1 - y_0}} \mat{M}_{\mathrm{trans2D}}(-x_0, -y_0) $$ Expanding the matrix definitions and simplifying $$ \mat{M}_{\mathrm{win2D}} = \begin{bmatrix} 1 & 0 & x_0' \\ 0 & 1 & y_0' \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \q{x_1' - x_0'}{x_1 - x_0} & 0 & 0 \\ 0 & \q{y_1' - y_0'}{y_1 - y_0} & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & - x_0 \\ 0 & 1 & - y_0 \\ 0 & 0 & 1 \end{bmatrix} $$ $$ \mat{M}_{\mathrm{win2D}} = \begin{bmatrix} 1 & 0 & x_0' \\ 0 & 1 & y_0' \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \q{x_1' - x_0'}{x_1 - x_0} & 0 & -x_0 \q{x_1' - x_0'}{x_1 - x_0} \\ 0 & \q{y_1' - y_0'}{y_1 - y_0} & -y_0 \q{y_1' - y_0'}{y_1 - y_0} \\ 0 & 0 & 1 \end{bmatrix} $$ $$ \mat{M}_{\mathrm{win2D}} = \begin{bmatrix} \q{x_1' - x_0'}{x_1 - x_0} & 0 & x_0' - x_0 \q{x_1' - x_0'}{x_1 - x_0} \\ 0 & \q{y_1' - y_0'}{y_1 - y_0} & y_0' - y_0 \q{y_1' - y_0'}{y_1 - y_0} \\ 0 & 0 & 1 \end{bmatrix} $$ results in $$ \mat{M}_{\mathrm{win2D}} = \begin{bmatrix} \q{x_1' - x_0'}{x_1 - x_0} & 0 & \q{x_0' x_1 - x_0 x_1'}{x_1 - x_0} \\ 0 & \q{y_1' - y_0'}{y_1 - y_0} & \q{y_0' y_1 - y_0 y_1'}{y_1 - y_0} \\ 0 & 0 & 1 \end{bmatrix} $$ Generalizing to 3D, define $$ \boxed{ \mat{M}_{\mathrm{win3D}}(x_0, x_1, y_0, y_1, z_0, z_1, x_0', x_1', y_0', y_1', z_0', z_1') \equiv \begin{bmatrix} \q{x_1' - x_0'}{x_1 - x_0} & 0 & 0 & \q{x_0' x_1 - x_0 x_1'}{x_1 - x_0} \\ 0 & \q{y_1' - y_0'}{y_1 - y_0} & 0 & \q{y_0' y_1 - y_0 y_1'}{y_1 - y_0} \\ 0 & 0 & \q{z_1' - z_0'}{z_1 - z_0} & \q{z_0' z_1 - z_0 z_1'}{z_1 - z_0} \\ 0 & 0 & 0 & 1 \end{bmatrix} } $$

Orthographic Projection

Orthographic projection is a special windowing transformation that maps an axis-aligned rectangular region of world space to the unit cube $$ \mat{M}_{\mathrm{ortho}} = \mat{M}_{\mathrm{win3D}}(l, r, b, t, n, f, -1, 1, -1, 1, -1, 1) $$ Evaluating this equation, define $$ \boxed{ \mat{M}_{\mathrm{ortho}}(l, r, b, t, n, f) \equiv \begin{bmatrix} \q{2}{r - l} & 0 & 0 & -\q{r + l}{r - l} \\ 0 & \q{2}{t - b} & 0 & -\q{t + b}{t - b} \\ 0 & 0 & \q{2}{f - n} & -\q{f + n}{f - n} \\ 0 & 0 & 0 & 1 \end{bmatrix} } $$

Perspective Projection

Perspective projection models a pinhole camera.

Consider 2D where $z$ is depth. In this case, $x$ needs to be divided by $z$. $$ \begin{cases} x_s = \q{n x_r}{z_r} \\ z_s = A + \q{B}{z_r} \\ h_s = 1 \\ \end{cases} $$ $$ \begin{cases} n = A + \q{B}{n} \\ f = A + \q{B}{f} \\ \end{cases} $$ $$ f = A + \q{B}{f} = \bb{n - \q{B}{n}} + \q{B}{f} = n + B \bb{\q{1}{f} - \q{1}{n}} = n + B \q{n - f}{n f} $$ $$ B = -n f $$ $$ A = n + f $$ $$ \begin{cases} x_s = \q{n x_r}{z_r} \\ z_s = n + f - \q{n f}{z_r} \\ h_s = 1 \end{cases} $$ $$ \begin{cases} x_q = n x_r \\ z_q = z_r [n + f] - n f \\ h_q = z_r \end{cases} $$ $$ \begin{bmatrix} x_s \\ z_s \\ 1 \end{bmatrix} = \begin{bmatrix} \q{x_q}{h_q} \\ \q{z_q}{h_q} \\ 1 \end{bmatrix} \sim \begin{bmatrix} x_q \\ z_q \\ h_q \end{bmatrix} = \begin{bmatrix} n & 0 & 0 \\ 0 & n + f & -n f \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} x_r \\ z_r \\ 1 \end{bmatrix} $$ $$ \vec{s} \sim \vec{q} = \mat{M}_{\mathrm{perspect2D}} \r $$ $$ \mat{M}_{\mathrm{frustum2D}} = \mat{M}_{\mathrm{ortho2D}}(l, r, n, f) \mat{M}_{\mathrm{perspect2D}}(n, f) $$ $$ \mat{M}_{\mathrm{frustum2D}} = \begin{bmatrix} \q{2}{r - l} & 0 & -\q{r + l}{r - l} \\ 0 & \q{2}{f - n} & -\q{f + n}{f - n} \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} n & 0 & 0 \\ 0 & n + f & -n f \\ 0 & 1 & 0 \end{bmatrix} $$ $$ \mat{M}_{\mathrm{frustum2D}} = \begin{bmatrix} \q{2 n}{r - l} & -\q{r+l}{r-l} & 0 \\ 0 & \q{f + n}{f - n} & -\q{2 n f}{f - n} \\ 0 & 1 & 0 \end{bmatrix} $$ $$ \boxed{ \mat{M}_{\mathrm{frustum}}(l, r, b, t, n, f) \equiv \begin{bmatrix} \q{2 n}{r - l} & 0 & -\q{r+l}{r-l} & 0 \\ 0 & \q{2 n}{t - b} & -\q{t+b}{t-b} & 0 \\ 0 & 0 & \q{f + n}{f - n} & -\q{2 n f}{f - n} \\ 0 & 0 & 1 & 0 \end{bmatrix} } $$

Transformation Stack

Scaling, rotation, and translation transformations (in that order) are commonly used to specify the pose (position and orientation) of spaces and geometry. $$ \mat{M}_{\mathrm{pose3D}} = \mat{M}_{\mathrm{trans3D}} \mat{M}_{\mathrm{rot3D}} \mat{M}_{\mathrm{scale3D}} $$ matrix stack $$ \mat{M} = \mat{M}_\mathrm{windowing} \mat{M}_\mathrm{projection} \mat{M}_\mathrm{modelview} $$

1. apply modelview
2. compute lighting in eye coordinates
3. apply projection

Clipping

$$ \un \dot \vec{q} = d $$ give algorithm on how to cut triangle up. can either be pass, fail, one vertex passes, or two vertices pass per face

Barycentric Coordinates

Let $B = \cc{\r_0, \dots, \r_N}$ be an affinely independent set of $N+1$ vectors in $\setR^M$. Consider $$ \r = \sum_{i=0}^N \r_i \beta_i \quad\text{where}\quad \sum_{i=0}^N \beta_i = 1 $$ Use the constraint to eliminate $\beta_0$ from the linear combination. First solve for $\beta_0$ $$ \beta_0 = 1 - \sum_{i=1}^N \beta_i $$ then insert this result into the linear combination $$ \r = \r_0 \bb{1 - \sum_{i=1}^N \beta_i} + \sum_{i=1}^N \r_i \beta_i $$ and simplify to get $$ \r - \r_0 = \sum_{i=1}^N \bb{\r_i - \r_0} \beta_i . $$ The sum has the form of matrix-vector multiplication $$ \r - \r_0 = \mat{M} \vec{\beta} $$ where the columns of matrix $\mat{M}$ are the affine basis vectors $$ \mat{M} = \begin{bmatrix} \r_1 - \r_0 & \r_2 - \r_0 & \ldots & \r_N - \r_0 \end{bmatrix} $$ and the elements of column vector $\vec{\beta}$ are the barycentric coefficients $$ \vec{\beta} = \begin{bmatrix} \beta_1& \beta_2& \ldots& \beta_N \end{bmatrix}^T . $$ In the case where $N = M$, affine independence guarantees matrix $\mat{M}$ is invertible, thus $\mat{\beta}$ has the unique solution $$ \vec{\beta} = \mat{M}^{-1} [\r - \r_0] . $$ The case of $N = M = 2$ is of primary importance in this work and fully expanded here. Matrix $\mat{M} \in \setR^{2\times2}$ $$ \mat{M} = \begin{bmatrix} \r_1 - \r_0 & \r_2 - \r_0 \end{bmatrix} . $$ The inverse of a 2x2 matrix is $$ \mat{M}^{-1} = \q{1}{\det(\mat{M})} \begin{bmatrix} M_{22} & -M_{12} \\ -M_{21} & M_{11} \end{bmatrix} $$ so the solution to the matrix equation is $$ \small \begin{bmatrix} \beta_1 \\ \beta_2 \end{bmatrix} = \q{1}{(x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0)} \begin{bmatrix} y_2 - y_0 & -(x_2 - x_0) \\ -(y_1 - y_0) & x_1 - x_0 \end{bmatrix} \begin{bmatrix} x - x_0 \\ y - y_0 \end{bmatrix} . $$ The constraint on the coefficients gives $\beta_0$ $$ \boxed{ \beta_0 = 1 - \beta_1 - \beta_2 } $$ while applying the inverse matrix gives the equations for $\beta_1$ $$ \boxed{ \beta_1 = \q{(x - x_0)(y_2 - y_0) - (x_2 - x_0)(y - y_0)}{(x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0)} } $$ and $\beta_2$ $$ \boxed{ \beta_2 = \q{-(x - x_0)(y_1 - y_0) + (x_1 - x_0)(y - y_0)}{(x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0)} } . $$

Barycentric coordinates linearly interpolate the properties of vertices. Geometrically the vector sum equals the linear interpolation of the vertex points $$ \boxed{ \mathrm{lerp2}(p_0, p_1, p_2, \beta_1, \beta_2) \equiv p_0 (1 - \beta_1 - \beta_2) + p_1 \beta_1 + p_2 \beta_2 } $$

Perspective Interpolation

Efficient rasterization requires iterating over pixels in screen coordinates. Transforming vertices into screen coordinates and performing linear interpolation with barycentric coordinates is part of rasterization. $$ \vec{r} = \sum_i \vec{r}_i \beta_i $$ Apply the transformation matrix $\mat{M}$ to this equation $$ \mat{M} \vec{r} = \sum_i \mat{M} \vec{r}_i \beta_i $$ to get clip coordinates $$ \vec{q} = \sum_i \vec{q}_i \beta_i . $$ Clip coordinates are transformed vertices before the projective divide.

Clip coordinates are similar to screen coordinates by the projective divide $$ \q{\vec{q}}{h} = \q{\sum_i \vec{q}_i \beta_i}{\sum_i h_i \beta_i} $$ screen coordinates $$ \vec{s} = \sum_i \vec{s}_i \beta'_i $$ $$ \q{\sum_i \vec{q}_i \beta_i}{\sum_i h_i \beta_i} = \sum_i \vec{s}_i \beta'_i $$ $$ \sum_i \vec{q}_i \beta_i = \sum_i h_i \beta_i \sum_i \vec{s}_i \beta'_i $$ $$ \sum_i \vec{s}_i h_i \beta_i = \sum_i h_i \beta_i \sum_i \vec{s}_i \beta'_i $$

Screen space barycentric coordinates. Consider the world-space linear interpolation of property $p$ $$ p = p_0 + t (p_1 - p_0) $$ The line is defined by $$ \r = \r_0 + t (\r_1 - \r_0) $$ $$ \mat{M} \r = \mat{M} \r_0 + t (\mat{M} \r_1 - \mat{M} \r_0) $$ $$ \vec{q} = \vec{q}_0 + t (\vec{q}_1 - \vec{q}_0) $$ $$ \q{\vec{q}}{h} = \q{\vec{q}_0 + t (\vec{q}_1 - \vec{q}_0)}{h_0 + t (h_1 - h_0)} $$ $$ \vec{s} = \vec{s}_0 + u (\vec{s}_1 - \vec{s}_0) $$ $$ \q{\vec{q}_0 + t (\vec{q}_1 - \vec{q}_0)}{h_0 + t (h_1 - h_0)} = \vec{s}_0 + u (\vec{s}_1 - \vec{s}_0) $$ $$ \vec{q}_0 + t (\vec{q}_1 - \vec{q}_0) = (h_0 + t (h_1 - h_0)) (\vec{s}_0 + u (\vec{s}_1 - \vec{s}_0)) $$ $$ h_0 \vec{s}_0 + t (h_1 \vec{s}_1 - h_0 \vec{s}_0) = h_0 \vec{s}_0 + u h_0 (\vec{s}_1 - \vec{s}_0) + t (h_1 - h_0) \vec{s}_0 + t u (h_1 - h_0) (\vec{s}_1 - \vec{s}_0) $$ $$ t h_1 (\vec{s}_1 - \vec{s}_0) - t u (h_1 - h_0) (\vec{s}_1 - \vec{s}_0) = u h_0 (\vec{s}_1 - \vec{s}_0) $$ $$ t (h_1 - u(h_1 - h_0)) = u h_0 $$ $$ t = \q{u h_0}{h_1 + u (h_0 - h_1)} $$ $$ p = p_0 + t (p_1 - p_0) $$ $$ p = p_0 + \q{u h_0}{h_1 + u (h_0 - h_1)} (p_1 - p_0) $$ $$ p = \q{p_0 (h_1 + u (h_0 - h_1)) + u h_0 (p_1 - p_0)}{h_1 + u (h_0 - h_1)} $$ $$ p = \q{p_0 h_1 + u (p_1 h_0 - p_0 h_1)}{h_1 + u (h_0 - h_1)} $$ $$ p = \q{\q{p_0}{h_0} + u \pp{\q{p_1}{h_1} - \q{p_0}{h_0}}} {\q{1}{h_0} + u \pp{\q{1}{h_1} - \q{1}{h_0}}} $$ $u = \beta_1$ $$ \boxed{ p = \q{\mathrm{lerp}\pp{\q{p_0}{h_0}, \q{p_1}{h_1}, \beta_1}} {\mathrm{lerp}\pp{\q{1}{h_0}, \q{1}{h_1}, \beta_1}} } $$ $$ \boxed{ p = \q{\mathrm{lerp2}\pp{\q{p_0}{h_0}, \q{p_1}{h_1}, \q{p_2}{h_2}, \beta_1, \beta_2}} {\mathrm{lerp2}\pp{\q{1}{h_0}, \q{1}{h_1}, \q{1}{h_2}, \beta_1, \beta_2}} } $$

Face Rasterization

for (x in X) {
	for (y in $) {
		(alpha, beta) = Rect2ToBary2(r0, r1, r2, x, y);
		if(alpha in [0,1] and beta in [0,1]){
			p = lerp2(p0 / h0, p1 / h1, p2 / h2, alpha, beta);
			h = lerp2(1 / h0, 1 / h1, 1 / h2, alpha, beta);
			draw(x, y, p / h);
		}
	}
}

note: this algo doesn't try to fix double draw, and is also very simplistic

Rendering Pipeline

• apply $\mat{M}_\mathrm{modelview}$
• world space computation (e.g. light, ignored in current version of notes)
• apply $\mat{M}_\mathrm{perspective}$
• clip
• projective divide
• apply $\mat{M}_\mathrm{viewport}$
• rasterize

Mesh Data Structures

$$ \mat{V} = \begin{bmatrix} \r_0 & \r_1 & \ldots & \r_v \\ \end{bmatrix} $$ $$ \mat{F} = \begin{bmatrix} v_{00} & v_{01} & \ldots & v_{0f} \\ v_{10} & v_{11} & \ldots & v_{1f} \\ v_{20} & v_{21} & \ldots & v_{2f} \\ \end{bmatrix} $$ NOTE THAT VF MESH SUCKS AT SUBDIVISION!!