Our Goal

Let's make the problem explicit by giving names to some quantities. We are given four 2D screen coordinates ${\text{s}}_i=\left[\begin{array}{ccc}{X}_i& Y_i& 1\end{array}\right]$ and four 2D texture coordinates ${\text{t}}_i=\left[\begin{array}{ccc}{U}_i& V_i& 1\end{array}\right]$, and we want to find the 3 × 3 homogeneous transformation M_st that maps one to the other so that

${\text{s}}_i{\text{M}}_{st}=w_i{\text{t}}_i$

See Figure 13.1. Note that we are not given the w_i values. Their participation in Equation (13.1) acknowledges the fact that even though the original input and output points are nonhomogeneous (their third component is 1), the output of the matrix multiplication will be homogeneous. We will have to solve for the w values as a side effect of solving for the elements of M_st.

The Conventional Solution

The conventional way to solve this goes as follows. First, using the names a … j for the elements of M_st, we can rewrite Equation (13.1) explicitly as

$\left[\begin{array}{ccc}{X}_i& Y_i& 1\end{array}\right]\left[\begin{array}{ccc}a& d& g\\ b& e& h\\ c& f& j\end{array}\right]=w_i\left[\begin{array}{ccc}{U}_i& V_i& 1\end{array}\right]$

Multiplying out and equating each component gives us three equations:

$\begin{array}{l}a{X}_i+b{Y}_i+c=w_i{U}_i\\ d{X}_i+e{Y}_i+f=w_i{V}_i\\ g{X}_i+h{Y}_i+j=w_i\end{array}$

Plug the last equation for w_i into the first two and move everything to the left of the equal sign:

$\begin{array}{l}a{X}_i+b{Y}_i+c-g{X}_i{U}_i-h{Y}_i{U}_i-j{U}_i=0\hfill \\ d{X}_i+e{Y}_i+f-g{X}_i{V}_i-h{Y}_i{V}_i-j{V}_i=0\hfill \end{array}$

Write this as yet another matrix equation in terms of what we are solving for, a … j:

$\left[\begin{array}{ccccccccc}{X}_i& Y_i& 1& 0& 0& 0& -X_i{U}_i& -Y_i{U}_i& -U_i\\ 0& 0& 0& X_i& Y_i& 1& -X_{i}V& -Y_i{V}_i& -V_i\end{array}\right]\left[\begin{array}{c}a\\ b\\ c\\ d\\ e\\ f\\ g\\ h\\ j\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right]$

Each input point gives us two more 9-element rows; four points gives us an 8 × 9 matrix. Since this is a homogeneous system, that's all we need to solve for the nine values a … j (with an arbitrary global scale factor). One way to calculate each of these nine values is to find the determinant of the 8 × 8 matrix formed by deleting the matching column of the 8 × 9 matrix, so … nine determinants of 8 × 8 matrices. This is doa ble but obnoxious. Looking at all those lovely zeros and ones on the left makes us suspect that there is a better way.

Heckbert's Improvement

In his 1989 master's thesis, Paul Heckbert¹ made a great leap by splitting the transformation into two separate matrices. He first used one matrix to map the input points to a canonical unit square (with vertices [0, 0], [1, 0], [1, 1], [0, 1]) and then mapped that square into the output points with another matrix. See Figure 13.2.

Each of these matrices will be individually easier to calculate than the complete transformation since the arithmetic is so much simpler. In fact, the arithmetic turns out to be simplest for the second of these transformations, so we will solve that one explicitly. Naming points in the unit-square space q, we want to find M_qt in the equation

${\text{qM}}_{qt}=w_t\text{t}$

Let's explicitly write out all components for all four input/output (q/t) point pairs. I'll recycle the names a … j and w₀ … w₃ for use in this subcomputation, so be aware that their values are different from those I used in the “conventional” solution:

$\left[\begin{array}{ccc}0& 0& 1\\ 1& 0& 1\\ 1& 1& 1\\ 0& 1& 1\end{array}\right]\left[\begin{array}{ccc}a& d& g\\ b& e& h\\ c& f& j\end{array}\right]=\left[\begin{array}{ccc}{w}_0{U}_0& w_0{V}_0& w_0\\ w_1{U}_1& w_1{V}_1& w_1\\ w_2{U}_2& w_2{V}_2& w_2\\ w_3{U}_3& w_3{V}_3& w_3\end{array}\right]$

This generates 12 equations:

$\begin{array}{ccc}c=w_0{U}_0& f=w_0{V}_0& j=w_0\\ a+c=w_1{U}_1& d+f=w_1{V}_1& g+j=w_1\\ a+b+c=w_2{U}_2& d+e+f=w_2{V}_2& g+h+j=w_2\\ b+c=w_3{U}_3& e+f=w_3{V}_3& h+j=w_3\end{array}$

Substituting the right column of equations into the left two columns gives us

$\begin{array}{cc}c=j{U}_0& f=j{V}_0\\ a+c=(g+j)U_1& d+f=(g+j)V_1\\ a+b+c=(g+h+j)U_2& d+e+f=(g+h+j)V_2\\ b+c=(h+j)U_3& e+f=(h+j)V_3\end{array}$

Then substituting the equations in rows 1, 2, and 4 into the third row gives the two equations

$\begin{array}{l}(g+j)U_1+(h+j)U_3-j{U}_0=(g+h+j)U_2\hfill \\ (g+j)V_1+(h+j)V_3-j{V}_0=(g+h+j)V_2\hfill \end{array}$

We juggle this into

$\begin{array}{l}g\left(U_1-U_2\right)+h\left(U_3-U_2\right)=j\left(U_0-U_1+U_2-U_3\right)\hfill \\ g\left(V_1-V_2\right)+h\left(V_3-V_2\right)=j\left(V_0-V_1+V_2-V_3\right)\hfill \end{array}$

Heckbert's original solution did the “without loss of generality” trick and assumed that j = 1. This works since we can only expect to solve for the matrix elements up to some global scalar multiple, and since j cannot be zero if point 0 is not at infinity. He then solved for g and h and got something that looked like

$g=\frac{\det \left[{\mathrm{stuff}}_0\right]}{\det \left[{\mathrm{stuff}}_2\right]}h=\frac{\det \left[{\mathrm{stuff}}_1\right]}{\det \left[{\mathrm{stuff}}_2\right]}$

I don't really like the j = 1 assumption though since it leads to these nasty divisions. And we really don't need it if we think homogeneously. We can instead write Equation (13.3) as

$\left[\begin{array}{ccc}g& h& j\end{array}\right]\left[\begin{array}{cc}{U}_1-U_2& V_1-V_2\\ U_3-U_2& V_3-V_2\\ -U_0+U_1-U_2+U_3& -V_0+V_1-V_2+V_3\end{array}\right]=\left[\begin{array}{cc}0& 0\end{array}\right]$

And just say that the vector [g h j] is the cross product of the two columns of the above matrix. This gives us, after a little simplification

$\begin{array}{l}g=\left(U_3-U_2\right)\left(V_1-V_0\right)-\left(U_1-U_0\right)\left(V_3-V_2\right)\\ h=\left(U_3-U_0\right)\left(V_1-V_2\right)-\left(U_1-U_2\right)\left(V_3-V_0\right)\\ j=\left(U_1-U_2\right)\left(V_3-V_2\right)-\left(U_3-U_2\right)\left(V_1-V_2\right)\end{array}$

Once we have these, it's a simple matter to get a through f using Equation (13.2):

$\begin{array}{cccc}c& =j{U}_0\hfill & f& =j{V}_0\hfill \\ a& =(g+j)U_1-c\hfill & d& =(g+j)V_1-f\hfill \\ b& =(h+j)U_3-c\hfill & e& =(h+j)V_3-f\hfill \end{array}$

Now that we have M_qt, the same simple arithmetic will give us the mapping from the canonical square to the input points. This will be the matrix that satisfies:

${\text{qM}}_{qs}=w_s\text{s}$

Invert that (or, better, take its adjoint) and multiply to get our desired net matrix:

${\text{M}}_{st}={\left[{\text{M}}_{qs}\right]}^{\ast }{\text{M}}_{qt}$

Olynyk's Improvement

An even better solution recently came from my colleague Kirk Olynyk here at Microsoft Research. His basic idea was to use barycentric coordinates, rather than a unit square, as the intermediate system. Barycentric coordinates represent an arbitrary point in the plane as the weighted sum of three basis points, for example, the first three of our output points. This would represent an arbitrary texture coordinate t as

${\tau }_0{\text{t}}_0+{\tau }_1{\text{t}}_1+{\tau }_2{\text{t}}_2=\text{t}$

with the constraint that the barycentric coordinates sum to one: ${\tau }_0+{\tau }_1+{\tau }_2=1$. Similarly, we can represent an arbitrary input point in barycentric coordinates as

${\sigma }_0{\text{s}}_0+{\sigma }_1{\text{s}}_1+{\sigma }_2{\text{s}}_2=\text{s}$

Kirk then related the two barycentric coordinate systems by coming up with a mapping from $\left[\begin{array}{ccc}{\sigma }_0& {\sigma }_1& {\sigma }_2\end{array}\right]$ to $\left[\begin{array}{ccc}{\tau }_0& {\tau }_1& {\tau }_2\end{array}\right]$ that has the property that the barycentric coordinates of all four input points map to the barycentric coordinates of their respective output points. That is,

$\begin{array}{ccc}[\begin{array}{ccc}1& 0& 0\end{array}]& \mapsto & [\begin{array}{ccc}1& 0& 0\end{array}]\\ [\begin{array}{ccc}0& 1& 0\end{array}]& \mapsto & [\begin{array}{ccc}0& 1& 0\end{array}]\\ [\begin{array}{ccc}0& 0& 1\end{array}]& \mapsto & [\begin{array}{ccc}0& 0& 1\end{array}]\\ \left[{\tilde{\sigma }}_0{\tilde{\sigma }}_1{\tilde{\sigma }}_2\right]& \mapsto & \left[{\tilde{\tau }}_0{\tilde{\tau }}_1{\tilde{\tau }}_2\right]\end{array}$

(The two points in the fourth mapping above are the barycentric coordinates of the fourth input/output point pair.) To get the desired mapping, simply multiply each σ_i, componemt of an arbitrary input point by ${\tilde{\tau }}_i/{\tilde{\sigma }}_i$. Then renormalize to a valid barycentric coordinate by dividing by the sum of the components. You can see that this algorithm leaves the coordinates of the first three points intact while properly changing those of the fourth point.

So how do we get the barycentric coordinates of the fourth input/output pair? Start with the matrix formulation of the barycentric coordinates of an arbitrary point. Here's the one for output points:

$\left[\begin{array}{ccc}{\tau }_0& {\tau }_1& {\tau }_2\end{array}\right]\left[\begin{array}{ccc}{U}_0& V_0& 1\\ U_1& V_1& 1\\ U_2& V_2& 1\end{array}\right]=\text{t}$

Note that if ${\tau }_0+{\tau }_1+{\tau }_2=1$, this guarantees that the w (homogeneous) component of t will be 1 also. Anyway, plugging in t = t₃ and moving the matrix over the equal sign gives us

$\left[\begin{array}{ccc}{\tilde{\tau }}_0& {\tilde{\tau }}_1& {\tilde{\tau }}_2\end{array}\right]=\left[\begin{array}{ccc}{U}_3& V_3& 1\end{array}\right]{\left[\begin{array}{ccc}{U}_0& V_0& 1\\ U_1& V_1& 1\\ U_2& V_2& 1\end{array}\right]}^{-1}$

This is nice, but it's not ideal. A full-on matrix inversion requires division by the determinant of the matrix. Likewise, the normalization to unit-sum barycentric coordinates requires division by the sum of the coordinates. Kirk dislikes divisions even more than I do, so in his implementation he removed them by homogeneously scaling them out symbolically after the fact. In thinking about this solution, though, I realized that there is a different way of deriving it that better shows its relation to the Heckbert solution.

Another Interpretation

Heckbert used a unit square as an intermediate coordinate system, and Olynyk used barycentric coordinates. Let's look at this problem anew and try to pick an intermediate coordinate system (call it b) that will minimize our arithmetic as much as possible when we solve for M_bt in the equation

${\text{bM}}_{bt}=w\text{t}$

We want four points b_i in our new coordinate system that have as many zeros as possible as components. The four simplest (homogeneous) points I can imagine are [1 0 0], [0 1 0], [0 0 1], and [1 1 1]. It doesn't matter that two of these are points at infinity. All that matters is that no three of these points are collinear. I show this new two-stage transformation in Figure 13.3, although it might be a bit confusing (and unnecessary) to try to make a closed quadrilateral out of the four b points.

The b coordinate system is like “homogeneous barycentric coordinates” (with the restriction relaxed that the sum of the components equals one) but is further scaled so that the components of the fourth point are equal.

So let's solve for M_bt Being extremely ecological, I will again recycle the names a … j for the matrix elements and w₀ … w₃ for the (as yet) unknown homogeneous factors. Our four points generate

$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 1& 1& 1\end{array}\right]\left[\begin{array}{ccc}a& d& g\\ b& e& h\\ c& f& j\end{array}\right]=\left[\begin{array}{ccc}{w}_0{U}_0& w_0{V}_0& w_0\\ w_1{U}_1& w_1{V}_1& w_1\\ w_2{U}_2& w_2{V}_2& w_2\\ w_3{U}_3& w_3{V}_3& w_3\end{array}\right]$

We could solve this by doing the same sort of substitutions that we did in the Heckbert solution, but there's an easier way. Looking at the top three rows on each side, we immediately realize that we have M_bt already staring us in the face; it's just the first three rows of Equation (13.5). Let's write it in factored form:

${\text{M}}_{bt}=\left[\begin{array}{ccc}a& d& g\\ b& e& h\\ c& f& j\end{array}\right]=\left[\begin{array}{ccc}{w}_0& 0& 0\\ 0& w_1& 0\\ 0& 0& w_2\end{array}\right]\left[\begin{array}{ccc}{U}_0& V_0& 1\\ U_1& V_1& 1\\ U_2& V_2& 1\end{array}\right]$

We only need to find w₀, w₁, and w₂, and we are home free. To get these, we take the bottom row of Equation (13.5):

$\begin{array}{l}\left[\begin{array}{ccc}1& 1& 1\end{array}\right]{\text{M}}_{bt}=\left[\begin{array}{ccc}{w}_3{U}_3& w_3{V}_3& w_3\end{array}\right]\\ \end{array}$

and combine it with Equation (13.6) and write

$\left[\begin{array}{ccc}1& 1& 1\end{array}\right]\left[\begin{array}{ccc}{w}_0& 0& 0\\ 0& w_1& 0\\ 0& 0& w_2\end{array}\right]\left[\begin{array}{ccc}{U}_0& V_0& 1\\ U_1& V_1& 1\\ U_2& V_2& 1\end{array}\right]=w_3\left[\begin{array}{ccc}{U}_3& V_3& 1\end{array}\right]$

We can hop the UV matrix over the equal sign by inverting it to get

$\left[\begin{array}{ccc}{w}_0& w_1& w_2\end{array}\right]=w_3\left[\begin{array}{ccc}{U}_3& V_3& 1\end{array}\right]{\left[\begin{array}{ccc}{U}_0& V_0& 1\\ U_1& V_1& 1\\ U_2& V_2& 1\end{array}\right]}^{-1}$

Comparing Equation (13.7) with Equation (13.4), we can see the relationship

$\left[\begin{array}{ccc}{w}_0& w_1& w_2\end{array}\right]=w_3\left[\begin{array}{ccc}{\tilde{\tau }}_0& {\tilde{\tau }}_1& {\tilde{\tau }}_2\end{array}\right]$

In other words, our w₀ … w₂ values are just a homogeneous scaling of the pure barycentric coordinates of the fourth point. Note also that the right-hand column of Equation (13.5) tells us that

$w_0+w_1+w_2=w_3$

Remember that we can determine the w's only up to a homogeneous scale factor, so let's pick something nice for, say, w₃. How about using the determinant of the matrix we are inverting? This can never be zero if the three points t₀, t₁, and t₂ aren't collinear. Letting w₃ equal this matrix determinant would pleasantly turn the matrix inverse into a matrix adjoint and we have

$\left[\begin{array}{ccc}{w}_0& w_1& w_2\end{array}\right]=\left[\begin{array}{ccc}{U}_3& V_3& 1\end{array}\right]{\left[\begin{array}{ccc}{U}_0& V_0& 1\\ U_1& V_1& 1\\ U_2& V_2& 1\end{array}\right]}^{\ast }$

So … that's half of our final answer. Now for the other half, the matrix M_sb. We get the inverse of M_sb by doing the same calculation using the four input coordinate points. First calculate the three homogeneous scale factors, which I'll call z, by analogy with Equation (13.9):

$\left[\begin{array}{ccc}{z}_0& z_1& z_2\end{array}\right]=\left[\begin{array}{ccc}{X}_3& Y_3& 1\end{array}\right]{\left[\begin{array}{ccc}{X}_0& Y_0& 1\\ X_1& Y_1& 1\\ X_2& Y_2& 1\end{array}\right]}^{\ast }$

And then, by analogy with Equation (13.6):

${\text{M}}_{bs}=\left[\begin{array}{ccc}{z}_0& 0& 0\\ 0& z_1& 0\\ 0& 0& z_2\end{array}\right]{\left[\begin{array}{ccc}{X}_0& Y_0& 1\\ X_1& Y_1& 1\\ X_2& Y_2& 1\end{array}\right]}^{\ast }$

To arrive at our ultimate goal of M_st, we need the adjoint of M_bs. One very nice feature of the factored form of the matrix that I've written here is that it's arithmetically simpler to adjointify than a general matrix. I'll write it out explicitly:

$\begin{array}{l}{\left[{\text{M}}_{bs}\right]}^{\ast }=\\ \left[\begin{array}{ccc}{Y}_1-Y_2& Y_2-Y_0& Y_0-Y_1\\ X_2-X_1& X_0-X_2& X_1-X_0\\ X_1{Y}_2-X_2{Y}_1& X_2{Y}_0-X_0{Y}_2& X_0{Y}_1-X_1{Y}_0\end{array}\right]\left[\begin{array}{ccc}{z}_1{z}_2& 0& 0\\ 0& z_0{z}_2& 0\\ 0& 0& z_0{z}_1\end{array}\right]\end{array}$

Put 'em all together and we get our gigantic punch line:

${\text{M}}_{st}={\left[{\text{M}}_{bs}\right]}^{\ast }{\text{M}}_{bt}$

Now it's time to name some of the matrices I've been laboriously writing out for so long (actually, I've been cutting and pasting). Up to this point, I've felt that explicitly writing them out has been more informative since it allows comparisons with other parts of the equation. I will name the following matrices:

$\text{T}\equiv \left[\begin{array}{ccc}{U}_0& V_0& 1\\ U_1& V_1& 1\\ U_2& V_2& 1\end{array}\right]\text{S}\equiv \left[\begin{array}{ccc}{X}_0& Y_0& 1\\ X_1& Y_1& 1\\ X_2& Y_2& 1\end{array}\right]$

Finally, let's rewrite our final answer slightly to give a nice comparison of this technique with (a homogenized version of) Kirk's original solution:

${\text{M}}_{st}={\text{S}}^{\ast }\left[\begin{array}{ccc}{w}_0{z}_1{z}_2& 0& 0\\ 0& z_0{w}_1{z}_2& 0\\ 0& 0& z_0{z}_1{w}_2\end{array}\right]\text{T}$

The matrix S* takes us from screen space to (homogeneous) barycentric coordinates. The w and z diagonal matrices combine to give one diagonal matrix whose elements are just homogeneous scalings of the ${\tilde{\tau }}_i/{\tilde{\sigma }}_i$ quantities that Kirk used to go from the screen barycentric system to the texture barycentric system. Matrix T then takes us to texture coordinates. This form is almost the simplest we can do arithmetically. But let's not give up yet.

Geometric Interpretations

As Equations (13.9) and (13.10) indicate, we need the adjoints of matrices T and S to calculate the w and z values to plug into Equation (13.12). The adjoint S* also shows up in Equation (13.12), but we only use T* to calculate the w's. Let's look at this w calculation, then, to see if there's some way we can save ourselves some work. While this investigation is initially motivated by performance avarice, it will actually point out some geometric relationships that I think are the most interesting results of this whole problem. In other words, greed is good.

First, let's use the definition in Equation (13.9) to explicitly write out the calculation of w₀:

$w_0=U_3\left(V_1-V_2\right)+V_3\left(U_2-U_1\right)+\left(U_1{V}_2-U_2{V}_1\right)$

What does this mean? Well, each row of matrix T is a point, one of t₀, t₁ or t₂. According to the definition of the adjoint, each column of T* is the cross product of two rows (points) of T. This means that each column of T* is a homogeneous line. For example, column 0 of T*represents the line connecting points t₁ and t₂. The process of multiplying an arbitrary point t by the matrix T* just takes its dot product with the three lines t₁t₂, t₂t₀, and t₀t₁. In other words, it measures the distance from the point to the three lines. That's the essential meaning of barycentric coordinates. In any event, we can now rewrite Equation (13.13) as

$w_0={\text{t}}_3\cdot {\text{t}}_1\times {\text{t}}_2$

This common algebraic expression has a standard geometric interpretation. Thinking of t₁, t₂, and t₃ as 3D vectors, it's the volume of the parallelepiped they define. Thinking, however, of the three points as homogeneous 2D vectors, there's another interpretation: w₀ equals twice the area of the triangle t₃t₂t₁. We can verify this algebraically by comparing the definition of w₀ from Equation (13.13) with twice the integral under the three triangle edges:

$\begin{array}{l}{w}_0=\left(U_1-U_2\right)\left(V_1+V_2\right)\\ +\left(U_2-U_3\right)\left(V_2+V_3\right)\\ +\left(U_3-U_1\right)\left(V_3+V_1\right)\end{array}$

But there's another way to calculate triangle areas: as (half) the length of a cross product. We can rewrite our expression for w₀ so that it looks like a cross product of two vectors along the edges of the triangle. For example, taking the third component of the cross product of the vectors (t₁ − t₃) and (t₁ − t₂) gives us

$w_0=\left(U_1-U_3\right)\left(V_2-V_3\right)-\left(U_2-U_3\right)\left(V_1-V_3\right)$

Now let's calculate w₁ (which is half the area of triangle t₃t₀t₂) and w₂ (half the area of triangle t₃t₁t₀). We only need one more vector difference: (t₀ − t₃). This gives the simplest way I've found to calculate all the W's:

$\begin{array}{l}{w}_0=\left(U_1-U_3\right)\left(V_2-V_3\right)-\left(U_2-U_3\right)\left(V_1-V_3\right)\\ w_1=\left(U_2-U_3\right)\left(V_0-V_3\right)-\left(U_0-U_3\right)\left(V_2-V_3\right)\\ w_2=\left(U_0-U_3\right)\left(V_1-V_3\right)-\left(U_1-U_3\right)\left(V_0-V_3\right)\end{array}$

Again, you can verify algebraically that these expressions equal those from Equation (13.9), but the geometric arguments make it seem a bit less magical. Also, you can look at Figure 13.4 for some more geometric inspiration.

One more Thin Little mint

There's one last little bit of juice we can squeeze out of this. This, again, came from Kirk, but he found it purely algebraically. I'm going to motivate it by an even more interesting geometric observation. It turns out that there is a magical relationship between the z_i values and the bottom row of S*. So we have to switch gears and start talking, not about U, V,w but about X,Y,z. I'll write the analog to Equation (13.14) and, for good measure, throw in a formula for z₃, which is, by analogy with Equation (13.8), the sum of the first three:

$\begin{array}{l}{z}_0=\left(X_1-X_3\right)\left(Y_2-Y_3\right)-\left(X_2-X_3\right)\left(Y_1-Y_3\right)\\ z_1=\left(X_2-X_3\right)\left(Y_0-Y_3\right)-\left(X_0-X_3\right)\left(Y_2-Y_3\right)\\ z_2=\left(X_0-X_3\right)\left(Y_1-Y_3\right)-\left(X_1-X_3\right)\left(Y_0-Y_3\right)\\ z_3=\left(X_1-X_0\right)\left(Y_2-Y_0\right)-\left(X_2-X_0\right)\left(Y_1-Y_0\right)\end{array}$

We can now see the missing link: the geometric interpretation of the value z₃. It's the area of triangle s₀s₁s₂. To see this, look at Figure 13.5 and note that z₀ plus z₂ equals the area of the whole quadrilateral. Now look at z₁. Since its edge vectors sweep clockwise, that area is negative and subtracts from the quadrilateral to get triangle s₀s₁s₂.

One side note: the area of the whole quadrilateral is

$\begin{array}{l}{z}_0+z_2=-z_1+z_3=\left(X_1-X_3\right)\left(Y_2-Y_0\right)-\left(X_2-X_0\right)\left(Y_1-Y_3\right)\\ \end{array}$

This reminds us that the area of the quadrilateral is (twice) the cross product of its diagonals (with appropriate care in algebraic sign).

Now let's take a look at the bottom row of S* (inside Equation (13.11)). Again, these look like areas of some sort. In fact, they are the areas of the three triangles connecting the three edges of triangle t₀t₁t₂ with the origin. (If this isn't immediately clear, try temporarily imagining point 3 at the origin.) The sum of these areas also equals z₃, so we have the following identity, which you can also verify algebraically:

${\text{S}}^{*}{}_{20}+{\text{S}}^{*}{}_{21}+{\text{S}}^{*}{}_{22}=z_3$

This means that

${\text{S}}^{*}{}_{20}+{\text{S}}^{*}{}_{21}+{\text{S}}^{*}{}_{22}=z_0+z_1+z_2$

So we can calculate one of the z's in terms of the others. This can, for example, turn the calculation

$z_0{\text{=X}}_3{\text{S}}^{*}{}_{00}+Y_3{\text{S}}^{*}{}_{10}+{\text{S}}^{*}{}_{20}$

into

$z_0{=\text{S}}^{*}{}_{20}+{\text{S}}^{*}{}_{21}{+\text{S}}^{*}{}_{22}-z_1-z_2$

It turns two multiplications into two additions. This may, or may not, be a particularly big deal with current processors.

Code

// Calculate elements of matrix Mst

// From 4 coordinate pairs

// (Ui Vi), (Xi Yi)

U03 = U0-U3; V03 = V0-V3;

U13 = U1-U3; V13 = V1-V3;

U23 = U2-U3; V23 = V2-V3;

w0 = U13*V23 - U23*V13;

wl = U23*V03 - U03*V23;

w2 = U03*V13 - U13*V03;

Sa00 = Y1-Y2; Sa10 = X2-X1;

Sa01 = Y2-Y0; Sa02 = Y0-Y1;

Sa11 = X0-X2; Sa12 = X1-X0;

Sa20 = X1*Y2 - X2*Y1;

Sa21 = X2*Y0 - X0*Y2;

Sa22 = X0*Y1 - X1*Y0;

z1 = X3*Sa01 + Y3*Sa11 + Sa21;

z2 = X3*Sa02 + Y3*Sa12 + Sa22;

z0 = Sa20+Sa21+Sa22 - z1 - z2;

d0 = w0*zl*z2;

d1 = wl*z2*z0;

d2 = w2*z0*z1;

Sa00*=d0; Sa10*=d0; Sa20*=d0;

Sa01*=d1; Sa11*=d1; Sa21*=d1;

Sa02*=d2; Sa12*=d2; Sa22*=d2;

M00 = Sa00*U0 + Sa01*U1 + Sa02*U2;

M10 = Sa10*U0 + Sa11*U1 + Sa12*U2;

M20 = Sa20*U0 + Sa21*U1 + Sa22*U2;

M01 = Sa01*V0 + Sa01*Vl + Sa02*V2;

M11 = Sa11*V0 + Sa11*V1 + Sa12*V2;

M21 = Sa21*V0 + Sa21*V1 + Sa22*V2;

M02 = Sa00  + Sa01   + Sa02;

M12 = Sa10  + Sa11  + Sa12;

M22 = Sa20  + Sa21  + Sa22;

Down a Dimension

As a mental exercise, let's look at this problem in one dimension. Suppose we want to find a single function relating X and U of the form

$U=\frac{aX+b}{cX+d}$

In matrix notation, this would be

$\left[\begin{array}{cc}X& 1\end{array}\right]\left[\begin{array}{cc}a& c\\ b& d\end{array}\right]=w\left[\begin{array}{cc}U& 1\end{array}\right]$

Here, each input/output pair (X_i and U_i) gives us one row in the expression

$\left[\begin{array}{cccc}{X}_i& 1& -X_i{U}_i& -U_i\end{array}\right]\left[\begin{array}{c}a\\ b\\ c\\ d\end{array}\right]=0$

Three input/output pairs generate enough rows on the left to make this a fully determined system. Solving for a … d requires the determinants of four 3 × 3 matrices. But applying our 2D trick to the 1D problem, we can get the same result by the calculation

$\begin{array}{cc}[\begin{array}{cc}{w}_0& w_1\end{array}]& =\left[(U_1-U_2)(U_2-U_0)\right]\hfill \\ [\begin{array}{cc}{z}_0& z_1\end{array}]& =\left[(X_1-X_2)(X_2-X_0)\right]\hfill \\ \left[\begin{array}{cc}a& c\\ b& d\end{array}\right]& =\left[\begin{array}{cc}1& -1\\ -X_1& X_0\end{array}\right]\left[\begin{array}{cc}{z}_1{w}_0& 0\\ 0& z_0{w}_1\end{array}\right]\left[\begin{array}{cc}{U}_0& 1\\ U_1& 1\end{array}\right]\hfill \end{array}$

Tediously multiplying this out gives the following:

$\begin{array}{l}a=U_0{X}_0\left(U_2-U_1\right)+X_1{U}_1\left(U_0-U_2\right)+X_2{U}_2\left(U_1-U_0\right)\\ b=X_0{X}_1{U}_2\left(U_1-U_0\right)+X_1{X}_2{U}_0\left(U_2-U_1\right)+X_2{X}_0{U}_1\left(U_0-U_2\right)\\ c=X_0\left(U_2-U_1\right)+X_1\left(U_0-U_2\right)+X_2\left(U_1-U_0\right)\\ d=X_0{X}_1\left(U_1-U_0\right)+X_1{X}_2\left(U_2-U_1\right)+X_2{X}_0\left(U_0-U_2\right)\end{array}$

The patterns in these expressions explicitly show something that we expect and implicitly assumed: the transformation will come out the same if we permute the indices of the input/output point pairs.

We will use this 3-point to 3-point transformation to great effect in the next few chapters.

Up a Dimension

Now, close your eyes and stretch your mind in the other direction. Imagine input/output pairs in homogeneous 3D space. Each pair, connected by a 4 × 4-element matrix multiplication, gives four equations. The fourth equation gives an expression for w_i Plug it into the other three and rearrange to get three equations that can be written as three rows of stuff times a 16-element column of matrix elements a … p. Since this has a zero on the right side, we need one less than 16 equations to solve the homogeneous system. Hmm, 16 minus 1 gives 15, and we get three per input/ output pair. That means that we can nail down a 3D homogeneous perspective transform with five input/output pairs. The conventional solution requires a truly excruciating 16 determinants of 15 × 15 matrices. Opening your eyes in shock, you discover that this exercise in imagination allowed me to get the idea across without making the typesetter hate me.

But now we know better how to solve this. The answer is a fairly straightforward generalization of Equations (13.6) and (13.9) into 4 × 4 matrices and 4-element vectors like so:

$\begin{array}{l}{\text{M}}_{bt}=\left[\begin{array}{cccc}{w}_0& 0& 0& 0\\ 0& w_1& 0& 0\\ 0& 0& w_2& 0\\ 0& 0& 0& w_3\end{array}\right]\left[\begin{array}{cccc}{U}_0& V_0& T_0& 1\\ U_1& V_1& T_1& 1\\ U_2& V_2& T_2& 1\\ U_3& V_3& T_3& 1\end{array}\right]\\ \left[\begin{array}{cccc}{w}_0& w_1& w_2& w_3\end{array}\right]=\left[\begin{array}{cccc}{U}_4& V_4& T_4& 1\end{array}\right]{\left[\begin{array}{cccc}{U}_0& V_0& T_0& 1\\ U_1& V_1& T_1& 1\\ U_2& V_2& T_2& 1\\ U_3& V_3& T_3& 1\end{array}\right]}^{\ast }\end{array}$

The details and arithmetic optimization tricks are left as an exercise for you to do (meaning I haven't gotten around to doing it myself).