The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Because of various matters at school, along with reviewing for and taking exams, it has already been more than four months since I last updated the blog, and even longer since I last wrote a computer graphics post.

Summer vacation recently began, and I finally studied the entirety of GAMES101 after previously watching only the ray-tracing section. It was still a very pleasant surprise: after some time had passed, I gained new understandings of many concepts that I had not understood very clearly before, especially the mathematical ones. Because of the course’s time constraints, some material was not explained in much detail, so I am recording some of my own understanding here.

Three-Dimensional Rotation Matrices

I already wrote about this in the earlier RT: The Next Week article, but the previous explanation was rather… strange and verbose, and it did not explain the subject from the perspective of coordinate-system transformations. I will therefore write it again here (of course, I still have not studied linear algebra systematically, so the following content may still be rather dubious).

The three-dimensional rotation matrices around the three axes can respectively be written in the following forms:

Rx(θ)=[1000cos⁡θ−sin⁡θ0sin⁡θcos⁡θ]R_x(\theta) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta \\ 0 & \sin \theta & \cos \theta \end{bmatrix}

Rz(θ)=[cos⁡θ−sin⁡θ0sin⁡θcos⁡θ0001]R_z(\theta) = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix}

Ry(θ)=[cos⁡θ0sin⁡θ010−sin⁡θ0cos⁡θ]R_y(\theta) = \begin{bmatrix} \cos \theta & 0 & \sin \theta \\ 0 & 1 & 0 \\ -\sin \theta & 0 & \cos \theta \end{bmatrix} \\

It is not difficult to notice that, in the matrix for rotation around the y-axis, the positions of sin⁡θ\sin \theta and −sin⁡θ-\sin \theta seem to be reversed, which is very strange. In the original video, the rotation matrix is derived by selecting several special points. I feel that a coordinate-system transformation makes it easier to understand here (although Professor Yan thinks this approach is more complicated).

First consider rotation around the z-axis. This case is relatively simple and is basically the same as a two-dimensional rotation matrix:

Note that although I did not draw the z-axis here, the right-hand rule tells us that the z-axis points outward through the screen.

We can express the new x-axis (i^\hat i) and the new y-axis (j^\hat j) separately as vectors. Note that both vectors are unit vectors:

i^=[cos⁡θsin⁡θ0]\hat i = \begin{bmatrix} \cos \theta \\ \sin \theta \\ 0 \end{bmatrix} \\

Observe that the angle between j^\hat j and the original y-axis is θ\theta, so we can “reverse” the vector form of i^\hat i. One more point requires attention: the x-component of j^\hat j is negative:

j^=[−sin⁡θcos⁡θ0]\hat j = \begin{bmatrix} -\sin \theta \\ \cos \theta \\ 0 \end{bmatrix} \\

In fact, in any coordinate system, every coordinate is obtained by multiplying unit vectors by certain lengths. You can imagine this as moving a point a certain distance in a certain direction. For example, in a Cartesian plane, the coordinate (1,2)(1, 2) can be understood as moving a point 1 unit in the x direction and 2 units in the y direction.

Therefore, in the rotated coordinate system, the new coordinate of a point (x,y,z)(x, y, z) is (xi^,yj^,z)(x\hat i, y\hat j, z). This is equivalent to moving x units in the i^\hat i direction, y units in the j^\hat j direction, and z units in the original z direction. Although that direction was not transformed, we still denote it by k^\hat k here.

The new coordinate is therefore:

p=x[cos⁡θsin⁡θ0]+y[−sin⁡θcos⁡θ0]+z[001]p = x\begin{bmatrix} \cos \theta \\ \sin \theta \\ 0 \end{bmatrix} + y\begin{bmatrix} -\sin \theta \\ \cos \theta \\ 0 \end{bmatrix} + z\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}

Looking at the rotation-matrix formula given earlier, we can see that RzR_z indeed satisfies the expression above:

[cos⁡θ−sin⁡θ0sin⁡θcos⁡θ0001][xyz]=x[cos⁡θsin⁡θ0]+y[−sin⁡θcos⁡θ0]+z[001] \begin{bmatrix} \textcolor{red}{\cos \theta} & \textcolor{blue}{-\sin \theta} & \textcolor{green}{0} \\ \textcolor{red}{\sin \theta} & \textcolor{blue}{\cos \theta} & \textcolor{green}{0} \\ \textcolor{red}{0} & \textcolor{blue}{0} & \textcolor{green}{1} \end{bmatrix}\begin{bmatrix} x \\ y \\ z \\ \end{bmatrix} = x\textcolor{red}{\begin{bmatrix} \cos \theta \\ \sin \theta \\ 0 \end{bmatrix}} + y \textcolor{blue}{\begin{bmatrix} -\sin \theta \\ \cos \theta \\ 0 \end{bmatrix} } + z\textcolor{green}{\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}}

There is a rather interesting point here, marked with the different colors: the three columns of the rotation matrix correspond respectively to i^\hat i, j^\hat j, and k^\hat k, which are the directions of the three axes in the new coordinate system.

From the perspective of coordinate-system transformations, this makes it very easy to understand why the rotation matrix is written this way. We can directly put the directions of the three transformed axes into the three columns of the matrix, thereby obtaining the rotation matrix.

We can use the same method to analyze rotation around the y-axis—the matrix that appeared to be “reversed.”

Although this looks very similar to the preceding figure, notice that the labels in the diagram have changed. Again, the right-hand rule tells us that the y-axis now points outward through the screen.

With the preceding observation, we now need only find i^\hat i, j^\hat j, and k^\hat k in the current situation to write down the rotation matrix around the y-axis.

First, for the new z-axis, namely k^\hat k, we can draw an analogy with i^\hat i in the z-axis rotation. Its vector form is:

k^=[sin⁡θ0cos⁡θ]\hat k = \begin{bmatrix} \sin \theta \\ 0 \\ \cos \theta \end{bmatrix} \\

The reason the y-component is zero is obvious: we are considering rotation around the y-axis, so y certainly does not change.

Next, by analogy with j^\hat j in the z-axis rotation, we obtain the vector form of i^\hat i:

i^=[cos⁡θ0−sin⁡θ]\hat i = \begin{bmatrix} \cos \theta \\ 0 \\ -\sin \theta \end{bmatrix} \\

Because j^\hat j is unchanged from before, it can simply be written as:

j^=[010]\hat j = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \\

Combining these vectors that represent the new x, y, and z directions gives:

[i^ ∣ j^ ∣ k^]=[cos⁡θ0sin⁡θ010−sin⁡θ0cos⁡θ]\left[\hat i \ | \ \hat j \ | \ \hat k\right] = \begin{bmatrix} \cos \theta & 0 & \sin \theta \\ 0 & 1 & 0 \\ -\sin \theta & 0 & \cos \theta \end{bmatrix} \\

Barycentric Coordinates

As explained in the GAMES101 course, barycentric coordinates—especially those for triangles—are extremely useful in computer graphics. They make it convenient to interpolate information at a triangle’s vertices across the triangle’s surface.

When I first listened to the lecture, I still had many questions. For example, why must the three coefficients sum to 1 and all be nonnegative for a point to lie inside the triangle?

After thinking about it for some time, I felt that understanding the concept according to the literal meaning of its name was intuitive: understand it from the perspective of a center of mass.

Physical Perspective

Suppose there is a triangle whose three vertices have masses Ma,Mb,McM_a, M_b, M_c, respectively, while every region other than the vertices has mass 0. According to the definition of a center of mass, the triangle’s center of mass is:

center of mass=MaA+MbB+McCMa+Mb+Mc\text{center of mass} = \frac{M_aA + M_bB + M_cC}{M_a + M_b + M_c}

Separating these three terms gives:

AMaMa+Mb+Mc+BMbMa+Mb+Mc+CMcMa+Mb+McA\frac{M_a}{M_a + M_b + M_c} + B\frac{M_b}{M_a + M_b + M_c} + C\frac{M_c}{M_a + M_b + M_c}

This form is extraordinarily similar to the barycentric-coordinate expression αA+βB+γC\alpha A + \beta B + \gamma C: every term is a coefficient multiplied by a vertex coordinate.

Looking at a term of the form MaMa+Mb+Mc\frac{M_a}{M_a + M_b + M_c}, we find that the coefficients used to calculate the center of mass satisfy the barycentric-coordinate requirements exactly: α+β+γ=1\alpha + \beta + \gamma = 1, and no term is negative.

Thinking in terms of the physical center of mass, what exactly are we converting when we transform ordinary coordinates into barycentric coordinates?

Map the coefficients in the center-of-mass formula to those in barycentric coordinates, namely MaMa+Mb+Mc→α\frac{M_a}{M_a + M_b + M_c} \to \alpha. We can then see that these coefficients are actually the proportions of the triangle’s total mass assigned to each vertex.

In other words, during the conversion—suppose we convert point pp from Cartesian coordinates to barycentric coordinates—we are really solving this problem: how should weight be distributed among the triangle’s three vertices so that the triangle’s center of mass lies at point pp?

The converted coordinate (α,β,γ)(\alpha, \beta, \gamma) is precisely the proportion of weight assigned to each of the triangle’s three vertices.

This makes it easy to understand why the three numbers must sum to 1 and be nonnegative for a point to lie inside the triangle. First, from a physical perspective, if mass is nonnegative, the center of mass must lie inside the object. Second, to satisfy the definition of a center of mass, α\alpha, β\beta, and γ\gamma must sum to 1. Since they represent the proportions of the total mass at the three vertices, the three numbers necessarily sum to 1, corresponding to the total mass.

Of course, barycentric coordinates are a generalization of the physical definition, so a purely algebraic explanation may be more convincing.

Algebraic Perspective

We know that a triangle’s barycentric coordinates use a linear combination of its three vertices to represent a coordinate: p=αA+βB+γCp = \alpha A + \beta B + \gamma C. We can now try to explain algebraically why the three coefficients must sum to 1 and be nonnegative for the point to lie inside the triangle.

First, we can express point pp in another form that will help with the later derivation:

p=A+uAB→+vAC→p = A + u\overrightarrow{AB} + v\overrightarrow{AC}

Note that uu and vv have no relation to the three barycentric-coordinate coefficients here. This expression means that, starting from point A, we move uu units along the direction AB and then vv units along the direction AC to reach point pp.

First, one thing is certain if the point is to remain inside the triangle: uu and vv are nonnegative. Starting at A, moving any distance only in the direction BA→\overrightarrow{BA} or CA→\overrightarrow{CA} would immediately leave the triangle.

Rearranging the preceding expression slightly gives:

p−A=uAB→+vAC→pA→=uAB→+vAC→uAB→+vAC→−pA→=0p - A = u\overrightarrow{AB} + v\overrightarrow{AC} \\ \overrightarrow{pA} = u\overrightarrow{AB} + v\overrightarrow{AC} \\ u\overrightarrow{AB} + v\overrightarrow{AC} - \overrightarrow{pA} = {0}

This expression can be understood as follows: we move every point, including point pp, by −OA→-\overrightarrow{OA}. At this point, A must lie at the origin.

The expression then becomes intuitive. First, the vector uAB→+vAC→u\overrightarrow{AB} + v\overrightarrow{AC} takes us from the origin to point pp; then pA→\overrightarrow{pA} takes us from point pp back to A, which is the origin.

Because these two parts point in opposite directions and have the same magnitude—one travels from A to pp, and the other from pp to A—the sum of the two vectors must be 0.

Expanding and rearranging the expression gives:

u(B−A)+v(C−A)+A−p=0uB−uA+vC−vA+A−p=0A(1−u−v)+uB+vC−p=0(1−u−v)A+uB+vC=p\begin{align*} u(B - A) + v(C - A) + A - p &= 0 \\ uB - uA + vC - vA + A - p &= 0\\ A(1 - u - v) + uB + vC - p &= 0 \\ (1 - u - v)A + uB + vC &= p \end{align*}

This form is exactly the same as the barycentric-coordinate expression, so we can determine that α=1−u−v\alpha = 1 - u - v, β=u\beta = u, and γ=v\gamma = v.

Adding these quantities gives 1−u−v+u+v=11 - u - v + u + v = 1. Indeed, the three barycentric-coordinate coefficients necessarily sum to 1.

We already established that uu and vv are nonnegative, but if u+v>1u + v > 1, would that not make α\alpha negative?

Consider the following figure. AMAM is a perpendicular from AA to BCBC (MM is not the midpoint of BCBC; using a non-equilateral triangle might have made this clearer, but I was lazy):

Return to the original definition, p=A+uAB→+vAC→p = A + u\overrightarrow{AB} + v\overrightarrow{AC}. Here, uu and vv are respectively the distances traveled in the AB→\overrightarrow{AB} and AC→\overrightarrow{AC} directions.

The length of the projection of uAB→u\overrightarrow{AB} onto AM→\overrightarrow{AM} is therefore uAB→⋅AM→∣AM→∣u\overrightarrow{AB} \cdot \overrightarrow{AM} \over |\overrightarrow{AM}|.

The figure shows that if uu is 1—that is, if AB→\overrightarrow{AB} has its full length—the projection’s length must equal ∣AM→∣|\overrightarrow{AM}|. Likewise, if uu is 0, the projected length in the AM→\overrightarrow{AM} direction must also be 0.

Because projection, or equivalently the dot product, is a linear operation, if uu is 0.5, the projection’s length must be half of ∣AM→∣|\overrightarrow{AM}|.

We can therefore say that the length of the projection of AB→\overrightarrow{AB} onto AM→\overrightarrow{AM} is u∣AM→∣u|\overrightarrow{AM}|.

Similarly, the length of the projection of AC→\overrightarrow{AC} in the AM→\overrightarrow{AM} direction follows the same rule.

For point pp to remain inside the triangle, the length of the projection of the vector uAB→+vAC→u\overrightarrow{AB} + v\overrightarrow{AC} onto AM→\overrightarrow{AM} must be no greater than the length of AM→\overrightarrow{AM} itself. Otherwise, point pp would cross side BCBC and leave the triangle.

The projected length of AB→\overrightarrow{AB} onto AM→\overrightarrow{AM} is u∣AM→∣u|\overrightarrow{AM}|, while the projected length of AC→\overrightarrow{AC} onto AM→\overrightarrow{AM} is v∣AM→∣v|\overrightarrow{AM}|. Naturally, the projected length of the sum of the two vectors onto AM→\overrightarrow{AM} is (u+v)∣AM→∣(u + v)|\overrightarrow{AM}|.

As stated above, for point pp to stay inside the triangle, the projection of uAB→+vAC→u\overrightarrow{AB} + v\overrightarrow{AC} onto AM→\overrightarrow{AM} must be no longer than AM→\overrightarrow{AM} itself. That is, (u+v)∣AM→∣≤∣AM→∣(u + v)|\overrightarrow{AM}| \le |\overrightarrow{AM}|, so u+v≤1u + v \le 1.

Because α=1−u−v\alpha = 1 - u - v and u+v≤1u + v \le 1, we can show that α\alpha must also be nonnegative.

At this point, we have explained why a point inside a triangle must satisfy α+β+γ=1\alpha + \beta +\gamma = 1, with every coefficient nonnegative. Of course, converting a Cartesian coordinate into barycentric coordinates still requires some relatively complicated calculations. For this part, I think the first method described in this blog post is relatively easy to understand and quite ingenious; interested readers can take a look.