Linear Algebra: Basics

Today with my math teacher I went over some of the basics of linear algebra. The two topics I went over included solving for the intersection of two lines in 3D space, and finding the angle between two vectors. The rest of the mathematical topics I'll try to cover in the near future include: finding a vector orthogonal to two other vectors in 3D space; finding the time T during the intersection of ray between a circle of sphere; using a matrix to rotate a vector by an arbitrary angle. I found these topics, as well as an entire survival guide for DigiPen students, at this site here. Hopefully by explaining the math I went over today I can solidify my own understanding.

First off: solving for the intersection of two lines in 3D space. I know how to do this in matrix form, as it is easiest and simplest in matrix form. Here is a matrix of the x y and z coordinates for a point in 3D space: [x, y, z]. An equation for a vector in 3D space consists of a point on a line, and the direction vector of a line multiplied by a magnitude. This magnitude represents the length of the line, whereas the timestep, or t, represents a constant.

Here is an equation for a line in 3D space: L1 = [2, 4, -1] + t[-1, 2, 3]. I just chose these numbers at random because they really don't matter. The first matrix is a point on the line. The second matrix is the rise, run, and the z equivalent to rise or run (just like two dimensional lines). You need a point on the line, otherwise the direction vector (rise//run//zrun) could sit anywhere in space. Without the direction vector for your line, you line could be facing in any direction as long as it sits on your point. The t is the magnitude of the direction vector, and these could be used as something to define the distance something traveled over time of t. t is just a constant.

In order to solve for the intersection of two lines, I'll quickly show the process with some variables. Here are the two lines: L1 = [a, b, c] + t[d, e, f]; L2 = [g, h, i] + r[j, k, l]. Now since these two equations each represent a line, the point of intersection is going to be a point that can be used to satisfy either of the equations. You just set both of the equations equal to each other, one variable at a time (x, y and z) and solve for each one. To solve for the x coordinate of the intersection you would use a + td = g + rj. You do this for variable a through c corresponding to d through f. Then using substitution, if need be, you can solve for t and then solve for the rest of the variables, thus getting a final matrix of [x, y, z].

The second thing I learned today was finding the angle between two vectors. Luckily, you only need the direction vectors of the line equations. This makes sense because no matter where the lines are in space, they will have the same angle of intersection as long as the direction of the lines face in stays constant. To do this, you use the equation of:

Theta, the zero thingy on the left, is the angle you are solving for. a and b both represent matrices that represent direction vectors, like the direction vectors in the line equations earlier in this post. Arccos is cos^-1. The a and b on the top half of the right side of the equation is pronounced as a dot b. The dot is the operator for the dot product. The dot product is used to find the scalar projection of a onto b, and vise versa. I honestly don't fully understand what exactly the dot product does yet (read last paragraph, I understand it now), but for now I just need it for equations like this one, and it returns a scalar value. To use the dot product on two 1x3 matrices, you would do this: [a, b, c] dot [d, e, f] = ((a x d) + (b x e) + (c x f). The |a| represents the magnitude of a, which is the length of a. If the direction vector of a line is representing velocity vectors, then the magnitude of a would be the speed of the direction vector. To find the magnitude of a 1x3 matrix you do this: |M| = |[a, b, c]| = sqrt(a^(2) + b^(2) + c^(2)). Does that look familiar? It should; it's basically the Pythagorean Theorem in 3D. It takes the rise, run, and zrun and converts the three into a length value, just like the Pythagorean Theorem does with two lines, except this is with three.


Now once you find a dot b, and magnitude of a times magnitude of b, you then divide a dot by magnitude of a times magnitude of b, then arccos that value which results in your angle!


Dot product explained: Okay! I so I did a bit of research and asked a couple people some questions and now I understand what the value returned by the dot product does. It projects a vector onto another vector and returns the length. A dot B also equals B dot A, which makes sense because multiplication itself is commutative, and the formula for the dot product is just multiplication of three values. Here is a picture to help visualize this:

The blue line would be the dot product of A and B. This is very useful for collision in programming, and transforming vectors from one grid space to another. Here is a good example of using the dot product for 2D collision detection of convex polygons:

The red and blue are both one dimensional projections of the objects onto a line. The dotted line is perpendicular one side length of one of the objects. In the diagram is looks like it is perpendicular to both, which is fine, but it is important to understand that the dotted line is normal to one of the sides of one of the polygons. Once you find a dotted line that is perpendicular to a side of one of the shapes, you use the dot product on a two dimensional matrix and project both of the shapes onto the normal to the dotted line. You can then compare the two projections to see if they overlap. If the two projections overlap, you then try the entire process over for a different side of one of the polygons. Once you try this algorithm over each of the sides of each object and no collision vector was detected (a collision vector would be the length of overlap formed by overlapping projections) in at least one of the iterations, then the two objects are not colliding with one another.


Sources:
http://www.mvps.org/directx/articles/math/dot/index.htm
http://en.wikipedia.org/wiki/Dot_product
http://www.gamedev.net/reference/programming/features/verletPhys/page2.asp