Math Magician: Much Ado About 3D Math

Illustration of the right-hand rule for the cr...
Image via Wikipedia

You know what irks me? Going online to look up something simple, like Dot Product or Cross Product, and getting nailed in the face with calculus proofs and discrete mathematics on why this and that happens, but never getting a simplified answer on what I’m looking up!

Well, I have a website, and now it’s time I delivered the simple answers. Open wide for a study guide.

Vector

  • Defined as a direction and magnitude. Most people would say it’s a point in space, but that is incorrect: that’s just called a… point. As explained in an example on Simple English Wikipedia:  If you ask for directions, and a person says “Walk one kilometer towards North”, that’s a vector.
  • Magnitude: the “length,” or size, of the vector. Also called the “norm.” A magnitude is usually represented, using vector A as an example, as ||A||. A magnitude is calculated as:
    float Magnitude(Vector3 v)
    {
         // The square root of The Pythagorean theorem
         // (a^2 + b^2 + c^2)
         return sqrt(pow(v.x, 2) + pow(v.y,2) + pow(v.z,2));
    }
  • Normalized Vector: or Unit Vector, is a vector with direction and a magnitude of 1. To normalize a vector, you would divide all of its components by the magnitude:
    vector3* Normalize(vector3 in, vector3* out)
    {
         float magnitude = Magnitude(in);
         out->x = in.x/magnitude;
         out->y = in.y/magnitude;
         out->z = in.z/magnitude;
         return out;
    }

Dot Product

  • The dot product is the product of two vectors, which results in a scalar value. This can be calculated 2 ways:
  • X•Y = |X||Y|cos(Θ), Theta (Θ) being the angle between the vectors. If we don’t have the angle, use:
  • X•Y = X.x * Y.x + X.y * Y.y + X.z * Y.z.
  • In code, these look like:
    float DotProduct(vector3 X, vector3 Y, float theta)
    {
         return (Magnitude(Y) * Magnitude(Y) * cos(theta));
    }float DotProduct(vector3 X, vector3 Y)
    {
         return (X.x * Y.x + X.y * Y.y + X.z * Y.z);
    }
  • Can be used to find the angle between vectors, by finding the arcosine of the dot product.
  • Can be used to preform a Half-Space Test, using a test point as X, and a point on a plane as Y. If the dot product is positive, X is in front of the plane. If it is negative, the point is behind the plane. A zero value would mean it is on top of the plane.

Cross Product

  • A math operation performed when 2 vectors love each other very much
  • Produces a vector that is perpendicular to both vectors, limiting this operation to only be performed in 3D space.
  • Function looka likea this:
    vector3* CrossProduct(vector3* out, vector3 A, vector3 B)
    {
         out->x = A.y * B.z - A.z * B.y; // Y to Z minus Z to Y
         out->y = A.z * B.x - A.x * B.z; // Z to X minus X to Z
         out->z = A.x * B.y - A.y * B.z; // X to Y minus Y to X
         return out;
    }
  • Used in many algorithms, always handy to have.

cos(θ) is the scalar projection of A onto B.

Component & Projection

  • Component requires 2 vectors, U and V, and returns a scalar value. When we apply the function, we say we’re getting the Component of U onto V.
  • The function looks like so:
    float Component(vector3 U, vector3 V)
    {
         return (DotProduct(U, &Normalize(V)));
    }
  • Aside from Components’ many use, it’s a primary function in calculating Projection. Projection also utilizes vectors U and V, and uses the scalar value returned from Component to project U onto V.
  • Here’s the function:
    vector3 Projection(vector3 U, vector3 V)
    {
         return (Component(U,V) * Normalize(V));
    }
  • Like Component, there are many uses, the big one of which (to me, at least) is orthonormalization. And with that, the auto-correct on my Google Chrome just learned a new badass word.
Reflection
  • Coming soon!

Matrix

  • Simply stated, a Matrix is a table of numbers, comprised of rows and columns. Matrices can have multiple dimensions, and the common one used for 3D space is a 4-by-4 matrix.
  • A matrix can be viewed as such:
  • Elements in a matrix are usually referenced (Row, Column), or in the images’ case, (Component, Axis).
  • Why a 4-by-4 matrix for 3D? The extra W Padding contains the positional data of the matrix in a 3D world, and the math used requires that the matrix has the same number of columns and rows.

Multiplication

  • This may also be referred to as Pain.
  • Looks like a dot product from Hell.
  • Essentially it’s like this: For every element in the product of the multiplication, it’s a dot product of a Axis from one matrix and a Component of the other. For instance: if we wanted to multiply matrix A with matrix B, to calculate the new Xx, it would be the dot product of B.X_Axis and A.X_Component.
  • Cue the WTFunction:
    matrix4* Multiply(matrix4* out, matrix4 A, matrix4 B)
    {
         out->Xx = DotProduct(B.X_Axis, A.X_Component);
         out->Xy = DotProduct(B.Y_Axis, A.X_Component);
         out->Xz = DotProduct(B.Z_Axis, A.X_Component);
         out->Xw = DotProduct(B.W_Axis, A.X_Component);
    
         out->Yx = DotProduct(B.X_Axis, A.Y_Component);
         out->Yy = DotProduct(B.Y_Axis, A.Y_Component);
         out->Yz = DotProduct(B.Z_Axis, A.Y_Component);
         out->Yw = DotProduct(B.W_Axis, A.Y_Component);
    
         out->Zx = DotProduct(B.X_Axis, A.Z_Component);
         out->Zy = DotProduct(B.Y_Axis, A.Z_Component);
         out->Zz = DotProduct(B.Z_Axis, A.Z_Component);
         out->Zw = DotProduct(B.W_Axis, A.Z_Component);
    
         out->Wx = DotProduct(B.X_Axis, A.W_Component);
         out->Wy = DotProduct(B.Y_Axis, A.W_Component);
         out->Wz = DotProduct(B.Z_Axis, A.W_Component);
         out->Ww = DotProduct(B.W_Axis, A.W_Component);
         return out;
    }

Transpose

  • Basically, you take your matrix, and flip all the rows into columns.
  • Symbolized by a small ‘t’ or ‘T’ next to the matrix variable name
    • Due to the limitations of WordPress, lets use Mt.
  • For Internet users, the formula looks like this for Matrix M
    • Mt = M ︵ \(°□°)\ = Σ
  • The formula, actually, is pretty intuitive. Take a look at Matrix M:
    M = [ a b c ]
        [ d e f ]
        [ g h i ]
  • Now, swapping the rows for the columns, here’s the transposed matrix M, now knows as Mt:
    Mt = [ a d g ]
         [ b e h ]
         [ c f i ]
  • Literally, it’s just a swap. You can pretty much do this in your head, but to code it out, it can be a bit more advanced (as with most things when you try to go from “Head to Code”)
  • Here is a code example from Daniweb (while ignoring the little “war” going on – never straight-out call a programmer wrong until you’ve tested):
    for (int i = 0; i < 4; i++) 
    {
      for (int j = i + 1; j < 4; j++) 
      {
        int save = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = save;
      }
    }
  • Now, this little swap here (can obviously be optimized, and) can only work on Square Matrices (see below). Specifically, this loop would only work on 4×4 Matrices.

Determinant

    • Used only on Square Matrices (see below).
  • Think of it as the “Dot Product for Matrices.” This calculation takes a single matrix and calculates a scalar product.
  • In mathematics, usually symbolized (for a matrix called ‘A’) by |A| or (A).
  • Determinants tell us certain properties about the matrix that are useful for solving other equations.
  • Determinants are relatively easy to compute for 2×2 matrices, however they become more and more difficult to calculate as the number of rows and columns increase (in which case, it starts turning into Determinant Inception™).
  • Here’s how to calculate a determinant for a 2×2 matrix:
    A = [ a b ]
        [ c d ]
    
    |A| = ad - bc
  • Pretty simple, right? Hang on. Here’s the determinant for a 3×3 matrix:
    A = [ a1 b1 c1 ]
        [ a2 b2 c2 ]
        [ a3 b3 c3 ]
    
    |A| = a1(b2c3 - c2b3) - a2(b1c3 -c1b3) + a3(b1c2 - c1b2)
  • WTF. Essentially, we broke down the 3×3 matrix into 3 separate 2×2 determinants and multiplied them by a scalar value, determined by the first column, crossing b and c on the 2 rows that are not the same row as our scalar. Yeah.
  • Lastly, here’s a 4×4:
    A = [ a1 b1 c1 d1 ]
        [ a2 b2 c2 d2 ]
        [ a3 b3 c3 d3 ]
        [ a4 b4 c4 d4 ]

    No way am I going to put one MASSIVE line or calculations here, so I’m going to break this down into 4 3×3 matrices. Our first column is going to be our scalars, and everything else will make up our matrices, following the pattern from before.

    A1 = [ b2 c2 d2 ]
         [ b3 c3 d3 ]
         [ b4 c4 d4 ]
    
    |A1| = b2(c3d4 - d3c4) - b3(c2d4 -d2c4) + b4(c2d3 - d2c3)
    
    A2 = [ b1 c1 d1 ]
         [ b3 c3 d3 ]
         [ b4 c4 d4 ]
    
    |A2| = b1(c3d4 - d3c4) - b3(c1d4 -d1c4) + b4(c1d3 - d1c3)
    
    A3 = [ b1 c1 d1 ]
         [ b2 c2 d2 ]
         [ b4 c4 d4 ]
    
    |A3| = b1(c2d4 - d2c4) - b2(c1d4 -d1c4) + b4(c1d2 - d1c2)
    
    A4 = [ b1 c1 d1 ]
         [ b2 c2 d2 ]
         [ b3 c3 d3 ]
    |A4| = b1(c2d3 - d2c3) - b2(c1d3 -d1c3) + b4(c1d2 - d1c2)

    And Finally:

    |A| = a1(A1) - a2(A2) + a3(A3) - a4(A4)
  • Facts about the return values from determinants:
    • If the determinant is 0, the matrix is considered singular. Anything else is considered nonsingular
    • If the determinant is 1, the matrix is unimodular, a word that clearly never gets used often.

Matrix Types
Square Matrix

  • Simply put: A matrix that has the same number of rows and columns. 2×2, 3×3, 4×4, etc.
  • This matrix is more commonly used because it has a lot to do with orientation in a 3D world, and performing special operations and having certain properties other matrices do not.

Identity Matrix

  • A special kind of Square Matrix.
  • It’s unimodular! (I’m gonna use that word everywhere now).
  • It’s made up of almost all zeros, except diagonally from the top left to the bottom right contains ones.
  • A 4×4 Identity Looks like:
    [ 1 0 0 0 ]
    [ 0 1 0 0 ]
    [ 0 0 1 0 ]
    [ 0 0 0 1 ]
  • Multiplying any matrix by an Identity matrix always returns the original matrix. So A * I = A.

Inverse Matrix

  • Works only iff (iff: mathematical term, means “if and only if”) the matrix is square and has a non-zero determinant.
  • Symbolized usually by Aˉ¹
  • If you take matrix A, invert it, and multiplied AAˉ¹ = Identity matrix.
  • Inverting a matrix is simple, as I’ve told you everything you needed for it already:
    Aˉ¹ = (1/Determinant(A)) * Transpose(A)
  • See? You already knew it! This method is computationally expensive once you get into doing the Determinant and Transpose, but, hey, you know the algorithm now in case you need it!

Rotation Matrix

  • Rotation Matrices are… fun, to say the least. We can represent a rotation on each axis in our matrix (The variable A used in the examples below represent the Angle rotated on that axis):
    • X Axis:
      [1       0       0       0       ]
      [0       cos(A)  -sin(A) 0       ]
      [0       sin(A)  cos(A)  0       ]
      [0       0       0       1       ]
    • Y Axis:
      [cos(A)  0       sin(A)  0      ]
      [0       1       0       0      ]
      [-sin(A) 0       cos(A)  0      ]
      [0       0       0       1      ]
    • Z Axis:
      [cos(A)  -sin(A) 0       0      ]
      [sin(A)  cos(A)  0       0      ]
      [0       0       1       0      ]
      [0       0       0       1      ]
  • In order to combine these rotations into one matrix, you would simply multiply the matrices together in the order you want to preform the rotations.

Translation Matrix

  • Coming soon!

Scale Matrix

  • Coming soon!

Orthonormalization

  • Coming soon!

Quaternions

  • http://www.virtualshackles.com/48
  • Yes, they’re exactly like that.
  • They’re the reason God made rainbows.
  • Essentially, they’re 4-dimensional vectors, however the elements do not represent coordinates. A quaternion, as a whole, represents a rotation in 3D space.
    • The ins-and-outs are pretty complex (√-1 and such), and that’s what bloats most of the other websites. What’s important here is that you know how to use, when to use, and why to use quaternions.
  • Here is our quaternion structure that we’ll be using for the examples:
    struct quaternion
    {
         float i;
         float j;
         float k;
         float a;
    };
  • You can think of i, j and k as the { x, y, z } axes, and a as the angle. They’re much more complex than that, but for simplicity’s sake, we won’t get into all of that.
  • Pros For using a Quaternion:
    • Uses less memory than a 4 x 4 Matrix
    • Eliminates Gimbal Lock
  • Cons for using a Quaternion:
    • Computationally expensive
    • Complex usage
    • Does not replace matrices; only optimizes rotation.
  • Coming soon!

Rotation

  • Coming soon!

References

Advertisements

2 thoughts on “Math Magician: Much Ado About 3D Math

  1. Geof June 25, 2012 / 5:34 AM

    Can you add some more info to the coming soon parts, especially showing rotations using Quaternions.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s