Part B - Direct3D

Two-Dimensional Mathematics

Describe mathematical concepts for tracking motion
Introduce vectors and operations on them
Introduce trigonometry and trigonometric functions
Introduce matrices and operations on them and vectors

Mathematics is a universal language for describing quantities, spatial relations, and changes to them systematically.  The branches of mathematics that provide the tools for depicting motion include linear algebra and trigonometry.  Linear algebra helps identify the position and orientation and changes to position and orientation.  Central to linear algebra are the concepts of coordinate system, vector, matrix, and angle.  Trigonometry is the branch that covers angular properties of triangles and is useful in converting angular measures into linear spatial ones.

Coordinate systems provide frames of reference for describing position and orientation.  Defining a coordinate system for a scene enables us to associate a unique set of scalar values with every point in that scene.

A vector describes the position of a point in space with respect to another in the same space.  By associating the reference point of a vector with a point in a coordinate system, we can describe the position of any other point in the coordinate system in terms of a vector.  By defining a set of reference directions in a coordinate system, we can use a vector to describe a direction with respect to the coordinate system.  We call the reference point of a coordinate system the system's origin and the reference directions its axes.

Matrices describe transformations transformations of vectors into other vectors.  These new vectors describe new positions and orientations in space.  Transformations include translations, rotations, and scalings.

In this chapter, we describe the coordinate system, vectors, matrices, and angles used in a two-dimensional game.  We restrict our presentation to two dimensions for simplicity and clarity.  We extend our two-dimensional definitions to three-dimensional ones in the following chapter.

Coordinate System

A coordinate system in two-dimensional space defines a frame of reference on a boundless plane.  The system can be:

• rectangular (Cartesian) - uses two distance measures in perpendicular directions
• cylindrical - uses one distance measure and one angle measure

The rectangular system is optimal for rectangular screens.  Two mutually perpendicular axes cross one another at a point, which we call the origin.  We label them the x and y axes.  We draw the x axis horizontally to the right and the y axis at an angle of 90 degrees counter-clockwise from the x axis as shown below.  We identify points along the x axis by their distance from the origin, with positive values increasing to the right and negative values increasing to the left.  Similarily, we identify points along the y axis by their distance from the origin, with positive values increasing upwards and negative values increasing downwards. We identify a point within the coordinate system by specifying its distance from the origin along each of the two axes.  The pair [px, py] uniquely identifies point P as illustrated in the figure below.  We call the two scalar values the x and y coordinates of point P. Vectors

A vector is a simple geometric entity with a direction and a finite length.  We depict a vector by a directed line segment with an arrowhead.  We call the farthest point along its direction its head and the farthest point in the opposite direction its tail.  The vector's magnitude is the distance from its tail to its head (or vice versa).  We draw the arrowhead at the vector's head pointed away from its tail. We adopt boldface lowercase notation to denote a vector.

 ` p`

We use normal face lowercase notation to denote a scalar and distinguish it from a vector.  A scalar has magnitude but no direction.

Vectors Operations

The reverse of a vector is the vector with its head and tail exchanged; that is, with its direction switched.  We use a negative sign to denote reversal.

 ``` r = -p ``` Multiplying a vector by a positive-valued scalar changes its length without changing its direction.

 ` r = sp` Adding a vector to another vector produces a third vector.  We depict this third vector by attaching the tail of the added vector to the head of the reference vector.  The third vector extends from the tail of the reference vector to the head of the added vector.  In other words, addition to a reference vector translates its head to the head of the added vector.  For adding vectors, we use the same notation that we use for adding scalars:

 ``` r = p + q ``` Subtracting a vector from another vector also produces a third vector.  We depict this third vector by attaching the tail of the subtracting vector to the tail of the reference vector.  The third vector extends from the head of the subtracting vector to the head of the reference vector.  In other words, subtraction translates the tail of the reference vector by the subtracting vector.  For subtracting vectors, we use the same notation that we use for subtracting scalars:

 ``` r = p - q ``` Free Vectors

Our description of a vector is a relative description.  A vector defines the position of its head with respect to its tail.  It does not define the position of its head or its tail absolutely.  That is, a vector is not fixed in space: its head and tail can translate together without changing the vector itself.  We refer to such vectors as free vectors.  Physical examples include displacement, velocity, and acceleration.  In other words, a free vector represents any vector from the set of all possible vectors that share the same magnitude and the same direction. Each vector is the same as every other vector in the collection.  We express this identity by the equality relation:

 ``` r = q = p ```

Note that the absolute spatial position of a free vector is undefined because of the lack of a referential coordinate system.

Vectors in a Coordinate System

Once we introduce a coordinate system, we can associate a unique vector with each point in the system.  We do so by attaching the vector's tail to the system's origin and the vector's head to the point.  We describe the point in vector terms.  We refer to such vectors as bound vectors (instead of free vectors).  Physical examples include position and orientation. The scalar values that identify the point in the coordinate system define the bound vector completely.  We express this definition in column format as follows:

 ``` | px | p = | | | py | ```

We call px and py the vector's x and y components.  Since we have arranged them in columnar form, we call p a column vector.

We could also have arranged the vector's components in row form:

 ``` pT = [px py] ```

In this case, we call the vector a row vector and use the notation pTT denotes transpose.  Transpose simply means rows and columns interchanged without any change in component values.  The transpose of a column vector is a row vector with the component values preserved.  The transpose of a row vector is a column vector with the component values preserved.  The transpose of the transpose of any vector is the original vector.

We can describe a free vector in a coordinate values by subtracting the tail bound vector from the head bound vector; that is, by subtracting their coordinate values:

 ``` p = [hx - tx hy - ty]T ```

where [tx, ty] identifies the tail and [hx, hy] identifies the head.  We are free to change the tail coordinates of a free vector provided that we change its head coordinates by the same amounts, thereby preserving the differences between the head and tail coordinates.  For instance,

 ``` p = [hpx - tpx hpy - tpy]T = q = [hqx - tqx hqy - tqy]T = r = [hrx - trx hry - try]T ```

The length or magnitude of a vector is the distance from its tail to its head.  The formula for its magnitude follows from Pythagoras' theorem.  In a two-dimensional system:

 ``` ||p|| = √[(px)2 + (py)2] = √[(hx - tx)2 + (hy - ty)2] ```

We use the double bar symbol to denote magnitude.

Reversing a vector multiplies its components by minus one:

 ``` r = -p = [-px -py]T = [tx - hx ty - hy]T ```

The magnitude of a reversed vector is the same as the magnitude of the original vector.

Multiplying a vector by a scalar applies the multiplier to each component:

 ``` r = sp = [spx spy]T ```

Adding one vector to another vector produces a third vector with components equal to the sum of the components of the contributing vectors:

 ``` r = p + q = [px py]T + [qx qy]T = [px + qx py + qy]T ```

If the tail of the added vector coincides with the head of the reference vector, the result of the addition is a vector from the tail of the reference vector to the head of the added vector:

 ``` r = p + q = [hpx - tpx hpy - tpy]T + [hqx - hpx hqy - hpy]T = [hpx - tpx + hqx - hpx hpy - tpy + hqy - hpy]T = [hqx - tpx hqy - tpy]T ```

Subtracting one vector from another vector produces a third vector with components equal to the difference of the components of the contributing vectors:

 ``` r = p - q = [px py]T - [qx qy]T = [px - qx py - qy]T ```

If the tails of the two vectors coincide, then the result of the subtraction is a vector from the head of the subtracted one to the head of the reference one

 ``` r = p - q = [hpx - tpx hpy - tpy]T - [hqx - tpx hqy - tpy]T = [hpx - tpx - (hqx - tpx) hpy - tpy - (hqy - tpy)]T = [hpx - hqx hpy - hqy]T ```

The product of a row vector and a column vector is the sum of the product of the first column coefficient of the row vector with the first row coefficient of the column vector and the product of the second column coefficient of the row vector with the second row coefficient of the column vector:

 ``` [a b]| c | = ac + bd | d |```

Multiplying a row vector by a column vector produces a scalar value called the scalar or dot product of the two vectors.  The value is given by

 ``` s = p∙q = pTq | qx | = [px py] | | | qy | = pxqx + pyqy ```

The dot product of a vector with itself is the square of the vector's magnitude:

 ``` s = p∙p = pTp | px | = [px py] | | | py | = (px)2 + (py)2 = ||p||2 ```

The norm of the vector is a vector of unit magnitude with the same direction:

 ``` n = p / ||p|| = p / (p ∙ p)1/2 ```

Trigonometry

Trigonometry deals with triangles, the relationships between their sides and the angles between adjacent sides.  We use it to describe orientations and changes in them.

Angles are measured in either degrees or radians, where a circle contains 360 degrees or 2π radians.  To convert from degrees to radians, we multiply by π/180:

 ``` θ (in radians) = ( π / 180 ) * θ (in degrees) ```

Interactive Example

Trigonometric Functions

Consider the right-angled triangle shown below.  Its longest side - the one opposite the right-angle - we call the hypoteneuse.  Let the hypoteneuse in our example be of unit length.  Let θ (theta) denote the angle between the hypoteneuse and the side that subtends this angle.  We call that side the adjacent side and the third side the opposite side.  The length of the adjacent side is given by

 ``` cos θ ```

cos is a trigonometric function. The length of the opposite side is given by

 ``` sin θ ```

sin is another trigonometric function. From Pythagoras' theorem, we have the following trigonometric identity:

 ``` cos2 θ + sin2 θ = 1 ```

The values for sin θ and cos θ for common values of θ are listed in the table below:

 θ (degrees) θ (radians) sin θ cos θ 0 0 0 1 30 π/6 1/2 (√3)/2 45 π/4 (√2)/2 (√2)/2 60 π/3 (√3)/2 1/2 90 π/2 1 0 120 2π/3 (√3)/2 -1/2 135 3π/4 (√2)/2 -(√2)/2 150 5π/6 1/2 -(√3)/2 180 π 0 -1 210 7π/6 -1/2 -(√3)/2 225 5π/4 -(√2)/2 -(√2)/2 240 4π/3 -(√3)/2 -1/2 270 3π/2 -1 0 300 5π/3 -(√3)/2 1/2 315 7π/4 -(√2)/2 (√2)/2 330 11π/6 -1/2 (√3)/2

We call the ratio of the length of the opposite side to the length of the adjacent side the tangent of the angle.  It is given by the ratio of the sin of the angle to the cos of the angle

 ``` tan θ = sin θ / cos θ ```

tan is another trigonometric function.

We call the inverse of the tangent of an angle its cotangent

 ``` cot θ = 1 / tan θ ```

cot is another trigonometric function.

We use all of these functions in this chapter and the following one.

Matrices

Matrices are the format that we use to express transformations of vector quantities.  We can change any free vector into another free vector by rotating and scaling it.  We can change a bound vector into another bound vector by rotating, scaling, and translating it.  Matrx format enables us to describe these transformations in a simple to calculate notation.

Rotation

Rotating a vector changes its direction without changing its magnitude.  We describe any rotation with respect to some fixed point; in the case of a bound vector, that point is the coordinate system's origin.

To derive the formulas for transforming a vector through a rotation, let us introduce the vector q, which is rotated by 90 degrees counter-clockwise from the vector p as shown below.  The tail of p is at the origin. Now consider the rotation of p into p' illustrated in the figure below.  The tail of the rotated vector p' remains at the origin and its head is the same distance from the origin as the head of p.  The rotated vector p' is the sum of two components: a component parallel to p and a component parallel to q, where the magnitude of each component is trigonometrically related to the angle of rotation (θ). In terms of the components of p and q, we can write the expression for p' as:

 ``` | px | | - py | p' = |   | cos θ + |   | sin θ | py | | px | | pxcos θ | | - pysin θ | = |   | + |   | | pycos θ | | pxsin θ | | pxcos θ - pysin θ | = |     | | pycos θ + pxsin θ | | pxcos θ - pysin θ | = |     | | pxsin θ + pycos θ | ```

In terms of the components of p', we write:

 ``` p'x = cos θ * px - sin θ * py p'y = sin θ * px + cos θ * py ```

Rewriting this pair of equations in column vector form yields:

 ``` | p'x | | cos θ -sin θ | | px | |   | = | | |   | | p'y | | sin θ cos θ | | py | ```

The column vectors contain 2 rows each.  We call the table with 2 rows and 2 columns a 2 x 2 matrix.

In more compact vector-matrix-vector notation, we write:

 ``` p' = R p ```

R is the rotation matrix given by

 ``` | cos θ -sin θ | R = | | | sin θ cos θ | ```

Alternatively, we can write this same pair of equations in row-vector form

 ``` | cos θ sin θ | [ p'x p'y ] = [ px py ] | | | -sin θ cos θ | ```

and represent it in more compact vector-vector-matrix notation

 ``` p'T = pT RT ```

The transpose (T) of a matrix is the matrix with its rows and columns exchanged.  To obtain RT from R, we exchange the rows and columns of R

 ``` | cos θ sin θ | RT = | | | -sin θ cos θ |```

The vector-matrix-vector form and the vector-vector-matrix form describe the same physical rotation.  The values within the two matrices are identical, but arranged in an order suitable for subsequent vector multiplication.

A column vector that is the product of a matrix and a column vector with coefficients that are the sum of the products of the row coefficients of the matrix with the column coefficients of the vector:

 ``` |c d| |a| |ca + db| | | |b| = | | |e f| |ea + fb|```

A row vector that is the product of a row vector and a matrix with coefficients that are the sum of the products of the row coefficients of the vector and the column coefficients of the matrix:

 ``` [a b] | c e | = [ac + bd ae + bf] | d f |```

Scaling

Scaling a vector changes its magnitude and possibly its direction.  The matrix for a scaling transformation that magnifies distances in the x-axis direction by a factor sx and distances in the y-axis direction by a factor of sy is given by

 ``` | sx 0 | S = | | | 0 sy | ```

For example, the scaling transformation described by

 ``` | 3 0 | S = | | | 0 1.8 | ```

and applied to the bound vector [1 1] yields the result shown in the figure below: A scaling transformation with identical scaling factors in each direction changes the magnitude but not the direction and can be reduced to a scalar multiplication of a vector

 ``` | a | | s 0 || a | | 1 0 || a | | a | | sa | S | | = | || | = s | || | = s | | = | | | b | | 0 s || b | | 0 1 || b | | b | | sb | ```

Note the matrix between the second and third equality signs with 1's along its diagonal.

Identity

We call a transformation represented by a square matrix that has components of 1 along its diagonal and 0 elsewhere the identity transformation.  An identity transformation leaves everything unchanged.

Translation

A translation transformation displaces the head of a bound vector.

Since it is impossible to describe rotation, scaling, and translation in 2 dimensional space using 2 x 2 matrices, mathematicians introduced 3 by 3 matrix representations to accommodate translations.  The top-left 2 x 2 part of a translation matrix is the identity matrix, while the added column specifies the translation.  The added row does not describe any transformation.  We call a 3 by 3 matrix that includes rotation, scaling, and translation components a homogeneous matrix.

The translation matrix for a head displacement of [∆x ∆y] is:

 ``` | 1 0 ∆x | T = | 0 1 ∆y | | 0 0 1 | ```

where ∆x and ∆y denote the translations along the x and y axes respectively.

To enable vector-matrix multiplication with a 3 by 3 matrix, we expand our two-component description of a vector to a three-component one, with the third component, by definition, unity:

 ``` p = [px py 1] ```

We write the translation transformation in more compact vector-matrix-vector form as

 ``` p' = T p ```

Alternatively, we can write the translation transformation as

 ``` [p'x p'y 1] = [px py 1]| 1 0 0 | | 0 1 0 | | ∆x ∆y 1 | ```

or in more compact vector-vector-matrix form as

 ``` p'T = pT TT ```

Compatible 3 x 3 Form

Let us rewrite the rotation and scaling matrices in 3 x 3 matrix form for compatibility with the translation matrix.

 ``` | cos θ -sin θ 0 | R = | sin θ cos θ 0 | | 0 0 1 | ```
 ``` | cos θ sin θ 0 | RT = | -sin θ cos θ 0 | | 0 0 1 | ```
 ``` | sx 0 0 | S = | 0 sy 0 | = ST | 0 0 1 | ```

Concatenating Transformations

Expressing rotation, scaling, and translation transformations in 3 x 3 matrix form enables the compression of a sequence of successive transformations into one equivalent transformation.

Consider the transformation of vector p into vector p' in vector-matrix-vector and vector-vector-matrix form respectively

 ``` p' = X p p'T = pT XT ```

where X denotes a rotation, scaling or translation transformation.  Consider a subsequent transformation

 ``` p" = Y p' p"T = p'T YT ```

where Y denotes a rotation, scaling or translation transformation.

Substituting the intermediate result for p' into this last pair of equations, we obtain

 ``` p" = Y X p p"T = pT XT YT ```

We can express this final result in terms of the original vector

 ``` p" = C p p"T = pT CT ```

where the composite transformation (C) is defined by

 ``` C = Y X CT = XT YT ```

The composite transformations are equivalent to the two transformations performed sequentially.  Note that the transformation order differs for matrix-vector products and vector-matrix products.

Generally, a composite transformation is the product of many individual transformations, where each successive transformation pre-multiplies or post-multiplies the result of the previous transformations:

 ``` C = Xi Xi-1 X... X1 X0 CT = (X0)T (X1)T (X...)T (Xi-1)T (Xi)T ```

In the untransposed form (for use with column vectors), the sequence is a pre-multiplication.  Each new transformation pre-multiplies the previous transformations.  In the transposed form (for use with row vectors), the sequence is a post-multiplication.  Each new transformation post-multiplies the previous transformations.

The untransposed form is common in scientific and engineering texts, where the observer tends to be at considerable distance from a scene.  The transposed form is more common with gaming applications, where the observer tends to be embedded within a scene.  Since some texts use the untransformed form in their theoretical presentation and the transformed form in coding, some care is warranted in determining which form applies.

For example, the composite transformation for a row vector describing

1. a scaling by a factor of 2 along each coordinate axis, followed by
2. a rotation through 30 degrees counter-clockwise, followed by
3. a translation of 1 unit to the right and 1 unit up

The second sequence applies for row vectors and is the post-multiplied product of three transposed matrices

 ``` scaling rotation translation | 2 0 0 | | (√3)/2 1/2 0 | | 1 0 0 | | 0 2 0 | | -1/2 (√3)/2 0 | | 0 1 0 | | 0 0 1 | | 0 0 1 | | 1 1 1 | ```

The rule for multiplying one matrix by another is a direct extension of the rule for multiplying a row vector by a matrix.  Element [i,j] is the sum of the products of element [i, k] in the left matrix with element [k, j] in the right matrix, where k = 0, ..., number of columns - 1.  In our example, element [1,0] is calculated as highlighted

 ``` scaling rotation translation | 2 0 0 | | (√3)/2 1/2 0 | | 1 0 0 | | 0 2 0 | | -1/2 (√3)/2 0 | | 0 1 0 | | 0 0 1 | | 0 0 1 | | 1 1 1 | = 0*((√3)/2) + 2*(-1/2) + 0*0 = -1 ```

Complete post-multiplication of the scaling matrix by the rotation matrix yields

 ``` composite translation | √3 1 0 | | 1 0 0 | | -1 √3 0 | | 0 1 0 | | 0 0 1 | | 1 1 1 | ```

Post-multiplication of the composite scaling-rotation matrix by the translation matrix yields

 ```final composite | √3 1 0 | | -1 √3 0 | | 1 1 1 | ```

Now consider the same three transformations but in a different order

1. a rotation through 30 degrees, followed by
2. a translation of 1 unit to the right and 1 unit up, followed by
3. a scaling by a common factor of 2

We express this set of transformations by the matrix product

 ``` rotation translation scaling | (√3)/2 1/2 0 | | 1 0 0 | | 2 0 0 | | -1/2 (√3)/2 0 | | 0 1 0 | | 0 2 0 | | 0 0 1 | | 1 1 1 | | 0 0 1 | ```

which reduces to

 ``` composite scaling | (√3)/2 1/2 0 | | 2 0 0 | | -1/2 (√3)/2 0 | | 0 2 0 | | 1 1 1 | | 0 0 1 | ```

and then to

 ```final composite | √3 1 0 | | -1 √3 0 | | 2 2 1 | ```

Note that, although the component matrices are identical in both sequences, the result of the second sequence differs from the result of the first.  That is, the order of the transformations affects the results.  We say that matrix multiplication is a non-commutative operation.

However, the order of evaluation of the same sequence of matrix multiplications has no effect on the outcome

 ``` Xi Xj Xk = (Xi Xj) Xk = Xi (Xj Xk) ```

We say that matrix multiplication is an associative operation.

Exercises

• Read the Wikipedia article on

 Designed by Chris Szalwinski Copying From This Site 