appendix-e.html

java game programming e-book

<P>The resulting vector is either pointing upward, as in the definition, or downward. <B>U</B> in the definition is a normalized vector that specifies the direction of the result. The direction is decided by how <I>V1</I> and <I>V2</I> are placed in relation to each other.</P>
<P>If the smallest rotation that takes <I>V1</I> and places it &#147;on top&#148; of <I>V2</I> is counterclockwise, then the result is positive, or &#147;upward,&#148; pointing out from the paper toward you, as shown in Figure E-17.</P>
<P><A NAME="Fig17"></A><A HREF="javascript:displayWindow('images/ape-17.jpg',348,275 )"><IMG SRC="images/ape-17t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-17.jpg',348,275)"><FONT COLOR="#000077"><B>Figure E-17</B></FONT></A>&nbsp;&nbsp;Vectors with positive orientation</P>
<P>If this is not the case and the smallest rotation is clockwise, then the result is negative, or &#147;downward&#148; into the paper, as Figure E-18 shows.
</P>
<P><A NAME="Fig18"></A><A HREF="javascript:displayWindow('images/ape-18.jpg',349,577 )"><IMG SRC="images/ape-18t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-18.jpg',349,577)"><FONT COLOR="#000077"><B>Figure E-18</B></FONT></A>&nbsp;&nbsp;Vectors with negative orientation</P>
<P><B>Characteristics of Cross Product</B></P>
<DL>
<DD><B>&#149;</B>&nbsp;&nbsp;The cross product is not commutative. What this means is that <I>V1xV2</I> does not produce the same result as <I>V2xV1</I>. Looking at Figure E-19, it can be deduced that <I>V1xV2=-V2xV1</I>. This &#147;feature&#148; can be used to determine the orientation of a polygon, for example.
<P><A NAME="Fig19"></A><A HREF="javascript:displayWindow('images/ape-19.jpg',263,25 )"><IMG SRC="images/ape-19t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-19.jpg',263,25)"><FONT COLOR="#000077"><B>Figure E-19</B></FONT></A>&nbsp;&nbsp;Cross product is not commutative</P>
<DD><B>&#149;</B>&nbsp;&nbsp;If both <I>V1</I> and <I>V2</I> are normalized, then the result will be a normalized vector also. The resulting vector is the normal to the plane that <I>V1</I> and <I>V2</I> make, as seen in Figure E-20. This &#147;feature&#148; will be used to calculate the normal of a polygon.
<P><A NAME="Fig20"></A><A HREF="javascript:displayWindow('images/ape-20.jpg',193,25 )"><IMG SRC="images/ape-20t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-20.jpg',193,25)"><FONT COLOR="#000077"><B>Figure E-20</B></FONT></A>&nbsp;&nbsp;Calculating the normal of a plane</P>
</DL>
<P><B>The Value of Cross Product</B></P>
<P>Cross product is in fact very related to dot product. It can be used to calculate the normal of a polygon, determine the orientation of a polygon, compose transformation matrixes, and so on.
</P>
<P><FONT SIZE="+1"><B><I>Matrixes</I></B></FONT></P>
<P>A matrix is a rectangular array of numbers or expressions called the elements of the matrix. Matrixes are used as a means of expressing mathematical operations in a compact way. The matrix below, for example, is a 4x3 matrix, which means that there are four rows and three columns.
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-07d.jpg"></P>
<P>Most of the arithmetic operations that can be applied on &#147;normal&#148; numbers (scalars) are also defined for matrixes. But with matrixes, the operations tend to get very nasty, very fast.
</P>
<P><B>Addition and Subtraction of Matrixes</B></P>
<P>The simplest operations between two matrixes are probably addition and subtraction. Matrix addition can only be done between matrixes of the same size; otherwise, it is not even defined.
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-08d.jpg"></P>
<P>Elements with the same index, or the same position, are added, making a resulting matrix that has the same size as the operands.
</P>
<P><B>Multiplication of a Matrix with a Vector</B></P>
<P>This is one of the most important operations involving matrixes and 3D math and will be heavily used throughout this appendix. It is done in the following way:
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-09d.jpg"></P>
<P>The result of this operation is a vector of the same size as the operand. There is another way of looking at this operation, though. Suppose that the rows in the matrix are seen as individual vectors. Then we could express the multiplication as three individual dot products. Looking at the first element in the resulting vector, you should observe that it is the dot product of <B>(a<SUB>11</SUB>,a<SUB>12</SUB>,a<SUB>13</SUB>)x(x,y,z)</B>. The second element is the dot product of <B>(a<SUB>21</SUB>,a<SUB>22</SUB>,a<SUB>23</SUB>)x(x,y,z)</B>. The third element is calculated in the same manner.</P>
<P><B>Matrix Multiplication with a Vector</B></P>
<P>Those of you who simply don&#146;t want to know how matrixes work internally and simply want to use them for the math-magic that they produce could think of a matrix as a &#147;black box&#148; that contains a certain transform, as Figure E-21 demonstrates.
</P>
<P><A NAME="Fig21"></A><A HREF="javascript:displayWindow('images/ape-21.jpg',509,347 )"><IMG SRC="images/ape-21t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-21.jpg',509,347)"><FONT COLOR="#000077"><B>Figure E-21</B></FONT></A>&nbsp;&nbsp;Math-magic with a black box</P>
<P><B>Multiplication of Two Matrixes</B></P>
<P>This operation is extremely time-consuming. It is only defined when the number of columns in the left operand matrix equals the number of rows in the right operand.
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-10d.jpg"></P>
<P>Even if this operation seems to be complicated, it is very similar to multiplying a matrix with a vector. In fact, multiplying a matrix with a vector is a special case of matrix multiplication in which the second operand (the vector) is a matrix with one column.
</P>

<TABLE BORDER="2" BORDERCOLOR="#0000" ALIGN="CENTER">
<TR><TD><FONT SIZE="+1"><B>Warning!</B></FONT>
<P>Multiplication between matrixes is not commutative. This means that M1&#183;M2 will not produce the same result as M2&#183;M1.
</P>
</TABLE>

<P><FONT SIZE="+1"><B>Matrixes in 3D Transformations</B></FONT></P>
<P>All basic 3D operations can be expressed as a multiplication between a matrix and a vector. The resulting vector would be some sort of transformation of the operand vector. What the transformation would be depends on the content of the matrix, as in the black box example in Figure E-21. It will be shown that all rotations, scaling, translation, shearing, and so on can be expressed in a conveniently compact way by using a matrix. In the first section of this appendix you saw how to rotate a 3D point in an informal way without using matrixes. You are now about see how to do it formally.
</P>
<P><FONT SIZE="+1"><B><I>Identifying the Basic Rotation Matrixes</I></B></FONT></P>
<P>Let&#146;s look at part of a listing from the previous section that rotated a point in the x-y plane (or about the z-axis, if you wish).
</P>
<!-- CODE SNIP //-->
<PRE>
//-- rotate the point in x-y-plane and store the result in
//-- Xa,ya,Za.
Xa = X*Math.cos(a)-Y*Math.sin(a);
Ya = X*Math.sin(a)&#43;Y*Math.cos(a);
Za = Z; //-- z coordinate is not affected by this rotation
</PRE>
<!-- END CODE SNIP //-->
<P>If all the Java-specific notations are removed and rewritten in a mathematically &#147;clean&#148; way, the calculations above would be represented in this form:
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-11d.jpg"></P>
<P>How could these operations be expressed in a matrix? Let&#146;s look at the definition of multiplication between a matrix and a vector again.
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-12d.jpg"></P>
<P>The goal is to substitute the elements in the matrix in such a way that <I>v</I><TT>&#146;</TT> would be a rotation of the <I>v</I>. Let&#146;s look at the first component in the resulting vector and try to get <I>x</I><TT>&#146;</TT> right.</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-13d.jpg"></P>
<P>Let&#146;s make the following substitutions for the first row in the matrix and see what happens:
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-14d.jpg"></P>
<P>The <I>x</I> component in <I>v</I><TT>&#146;</TT> is exactly the same as <I>x</I><TT>&#146;</TT> in the mathematical expression. This means that the first row in the matrix is correct. Let&#146;s look at the second.</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-15d.jpg"></P>
<P>Let&#146;s make the following substitutions for the second row in the matrix and see what happens:
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-16d.jpg"></P>
<P>Making the similar substitutions to the remaining row, we find out that the 3x3 matrix for rotating a point about the z-axis is
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-17d.jpg"></P>
<P><FONT SIZE="+1"><B><I>Using Matrixes to Rotate Vectors</I></B></FONT></P>
<P>How can this matrix be used? First of all, any vector multiplied with this matrix will be rotated by <I>a</I> degrees about the z-axis. The black box example illustrates this in an intuitive way in Figure E-22.</P>
<P><A NAME="Fig22"></A><A HREF="javascript:displayWindow('images/ape-22.jpg',61,35 )"><IMG SRC="images/ape-22t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-22.jpg',61,35)"><FONT COLOR="#000077"><B>Figure E-22</B></FONT></A>&nbsp;&nbsp;Using the black box to rotate 3D points</P>
<P>The other rotations can be deduced in the exact same way by identifying the elements in the matrix with the informal expressions.
</P>
<P><FONT SIZE="+1"><B><I>Scaling</I></B></FONT></P>
<P>Another important transform that can be expressed in a 3x3 matrix is scaling. Scaling (see Figure E-23) is the same as multiplying the components of a vector by a factor. Expressed in the form of a matrix multiplication with a vector, it would be
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-18d.jpg"></P>
<P><A NAME="Fig23"></A><A HREF="javascript:displayWindow('images/ape-23.jpg',349,274 )"><IMG SRC="images/ape-23t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-23.jpg',349,274)"><FONT COLOR="#000077"><B>Figure E-23</B></FONT></A>&nbsp;&nbsp;Scaling four points</P>
<P>Before we move on, we should acquaint ourselves with the four rotation matrixes given in Table E-1.
</P>
<TABLE WIDTH="100%"><B>Table E-1</B> Rotation matrixes
<TR>
<TD WIDTH="10%">
<TH WIDTH="90%" ALIGN="LEFT">Matrix
</TABLE>
<P ALIGN="CENTER"><IMG SRC="images/ape-19d.jpg"></P>
<P><FONT SIZE="+1"><B><I>Packing Several Rotations into a Single Matrix</I></B></FONT></P>
<P>As you have seen in the previous section, rotations can be expressed in a formal way by using matrixes and vectors. The real power of a matrix is that it can contain several transforms. Until now we have only looked at matrixes containing a single rotation. To understand how we could make several rotations by simply multiplying a matrix with a vector, we need to do a little math.
</P>
<P>Let&#146;s say that we have a vector <I>v</I> that we would like to rotate about the z-, y-, and x-axes, in that order. Doing one transformation at a time with the matrixes in previous section, we could express this operation mathematically in the following way:</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-20d.jpg"></P>
<P>What does this tell us? First of all, the matrixes <I>Rx</I>, <I>Ry</I>, and <I>Rz</I> can be multiplied into a single matrix that we can call <I>R</I>. The expression is now simplified to a multiplication between a matrix and a vector.</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-21d.jpg"></P>
<P>In Figure E-24, you can look at the black box example again and view this operation in an informal way.
</P>
<P><A NAME="Fig24"></A><A HREF="javascript:displayWindow('images/ape-24.jpg',348,275 )"><IMG SRC="images/ape-24t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-24.jpg',348,275)"><FONT COLOR="#000077"><B>Figure E-24</B></FONT></A>&nbsp;&nbsp;Using the black box to rotate a 3D point about all axes</P>
<P>What about the three-matrix multiplication? As we saw earlier, that kind of an adventure would take a massive amount of calculations. Using symbolic math, the matrix containing all three rotations can be precalculated and then built in one shot without doing any matrix operations. The result will be the same, though. Without going into the details, here is the matrix that will rotate a vector about all three axes. The previously calculated matrix does the following transforms:
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-22d.jpg"></P>
<P ALIGN="CENTER"><IMG SRC="images/ape-23d.jpg"></P>

<TABLE BORDER="2" BORDERCOLOR="#0000" ALIGN="CENTER">
<TR><TD><FONT SIZE="+1"><B>WARNING!</B></FONT>
<P>Since matrix multiplication is not commutative the order in which the rotations are made is important. A matrix that is composed of R<SUB>x</SUB>&#183;R<SUB>y</SUB>&#183;R<SUB>z</SUB> will not perform the same rotation as a matrix that is composed from R<SUB>z</SUB>&#183;R<SUB>y</SUB>&#183;R<SUB>x</SUB>.</P>
</TABLE>

<P><FONT SIZE="+1"><B><I>Moving to 4x4 Matrixes</I></B></FONT></P>
<P>The 3x3 matrixes that we have used so far can obviously rotate 3D vectors, but there is a major transform that has been overlooked up until now. That is translation, which simply means displacement. Figure E-25 demonstrates this.
</P>
<P><A NAME="Fig25"></A><A HREF="javascript:displayWindow('images/ape-25.jpg',347,277 )"><IMG SRC="images/ape-25t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-25.jpg',347,277)"><FONT COLOR="#000077"><B>Figure E-25</B></FONT></A>&nbsp;&nbsp;Translation of four points; all points were translated by (x,y)=(3,1) units</P>
<P>This transform cannot be expressed in a 3x3 matrix and would have to be implemented as a special &#147;feature,&#148; which would not be consistent with the math that we have looked at this far. What we would like at this point is to be able to express all transforms using matrixes, whether we are doing rotation or translation. Expanding the 3x3 matrixes to 4x4 offers some new possibilities. What we are doing is actually moving to the fourth dimension, but all calculations will be done in a single plane. Each plane in the 4D space is a 3D space. Think of a plane in 4D space as a 3D space where time stands still. Since all calculations are done in a single plane, we would still be in the third dimension. That was just some mathematical mumbo jumbo and is of no practical use to us at this point. What is important, though, is how this can be done practically and what the implications are.
</P>
<P>The implications are far less then one might expect, and the impact from moving to a 4x4 matrix is close to none. Let&#146;s begin by looking at how translation can be expressed in a 4x4 matrix.</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-24d.jpg"></P>
<P>What are the changes from the 3x3 matrix? First of all, the vector has one more element, which should always be 1. This has no implication, since in the implementation we will informally call a vector for a 3D point, ignoring the fact that there should be a 1 as the last element. Second, a row has been added to the matrix that should always be (0 0 0 1). Third, there is another column. It is the new column that offers the possibility to store more information in the matrix. Remember the black box? You could say that we are now using a smarter black box.
</P>
<P><B>Why Use a 4x4 Matrix Instead of a 3x3 Matrix?</B></P>
<P>Having a consistent way of expressing all transforms in a single matrix is in itself reason enough. The transforms that we have looked at this far have all been fairly simple. The most complicated one was probably the composed matrix that did three rotations in one shot, but in real life (and as you will see later on) a matrix can contain quite a few transforms, including translation and scaling. Table E-2 prepares us for the next step by showing basic 3D transform matrixes.
</P>
<TABLE WIDTH="100%"><CAPTION ALIGN=LEFT><B>Table E-2</B> The basic 3D transform matrixes
<TR>
<TH WIDTH="5%">
<TH WIDTH="35%" ALIGN="LEFT">Function
<TH WIDTH="60%" ALIGN="LEFT">Matrix
</TABLE>
<P ALIGN="CENTER"><IMG SRC="images/ape-25d.jpg"></P>
<P><B>Using 4x4 Matrixes</B></P>
<P>In order to show that a 4x4 matrix is not harder to work with than a 3x3 matrix, Figure E-26 shows an example of a set of transforms expressed in one matrix.
</P>
<P><A NAME="Fig26"></A><A HREF="javascript:displayWindow('images/ape-26.jpg',348,274 )"><IMG SRC="images/ape-26t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-26.jpg',348,274)"><FONT COLOR="#000077"><B>Figure E-26</B></FONT></A>&nbsp;&nbsp;Source and destination</P>
<P>As you can see, this transformation contains translation, scaling, and rotation. The order in which these transformations are made is important, though. Figure E-27 shows the procedure step by step. (All matrixes are referred to by their name in Table E-2.)
</P>
<P><A NAME="Fig27"></A><A HREF="javascript:displayWindow('images/ape-27.jpg',347,274 )"><IMG SRC="images/ape-27t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/ape-27.jpg',347,274)"><FONT COLOR="#000077"><B>Figure E-27</B></FONT></A>&nbsp;&nbsp;A set of transformations</P>
<P>The mathematical expression for this transform would be
</P>
<P ALIGN="CENTER"><IMG SRC="images/ape-26d.jpg"></P>
<P>Don&#146;t be fooled by the order in which the matrixes are written. It is not the leftmost matrix that is the first transform, but the one closest to the vector.
</P>
<P><FONT SIZE="+1"><B><I>Creating a Matrix Class</I></B></FONT></P>
<P>Now that we have put some of the math behind us, we can start looking at how all this can be implemented. Using a matrix class seems appropriate. The goal is to hide the calculations from the user and make it work like a black box. All matrix compositions should be made transparent. For starters we could use the class in Listing E-4, which contains the bare essentials. The complete fMatrix3d class can be found on the CD-ROM.
</P>
<P><B>Listing E-4</B> A simple matrix class</P>
<!-- CODE //-->
<PRE>
/**
 * A generic 3d matrix class that implements the rotation
 * about the principal axis, translation and scaling.
 */
class fGeneric3dMatrix extends Object &#123;
   double xx, xy, xz, xo;
   double yx, yy, yz, yo;
   double zx, zy, zz, zo;
   /**
    * Constructs the identity matrix.
    */
   public fGeneric3dMatrix()&#123;
      makeIdentity();
   &#125;
   /**