Guide to Computational Linear Algebra

[jemidiah]

PART 2: Basic Computer Graphics with Linear Algebra

2.1 Dot Products

The dot product lets us find angles between vectors easily. To be explicit, take the following example. Suppose we have a turret in a 2D game. Say that the turret can only turn through 90 degrees: 45 degrees left from its starting position, and 45 degrees right. We can remember which way the turret was pointing initially through the use of a unit vector (see Section 1.3), which would probably be set during level design. We can also get a vector pointing from the turret to an enemy easily with vector subtraction. Now, we need to know what the angle is between the starting position vector and the enemy, to see if the angle is too large. The dot product lets us find this angle easily without resorting to drawing out the situation to analyze with geometry and trigonometry.

The dot product of two vectors u and v of the same length is given as follows (the . should be centered in the middle vertically as well as horizontally, but a period is easier for typesetting this):
2D: u . v = <u.x*v.x, u.y*v.y>
3D: u . v = <u.x*v.x, u.y*v.y, u.z*v.z>
nD: u . v = <u.1*v.1, ..., u.n*v.n>

The defining property of the dot product can be derived from basic geometry and trigonometry. It relates the lengths of each of the input vectors and their dot product to the angle between the vectors. There are actually two angles between vectors--one small one and one large one, which add up to 360 degrees. The dot product deals with the smaller angle. This angle is traditionally called "theta", after the Greek letter. The relation between these quantities is, using the notation of Section 1.3:

u . v = |u|*|v|*cos(theta)

If vectors p and q are unit vectors, then by definition their lengths are 1, and the angle can be found very easily:

theta = arccos(p . q)

Using the turret example, the following pseudocode would tell us if the target was in range or not:

'Fire the turret, if enemy is within turning range. Return the new enemy health.
function TurretAttack(InitialDirection as Unit 2DVector, TurretPosition as 2DVector,
                       EnemyPosition as 2DVector, AttackStrength as Number,
                       EnemyHealth as Number) returns Number:

    'Use dot product to find angle from turret to enemy
    TurretToEnemy = unit(EnemyPosition - TurretPosition) 'see Section 1.3 for unit()
    theta = Math.acos(InitialDirection . TurretToEnemy)
    
    'Attack if possible
    If |theta| <= 45 degrees Then
        'In range
        return EnemyHealth - AttackStrength
    Else
        'Out of range
        return EnemyHealth
end function

2.2 Cross Products

The cross product is only defined in 3D (and, incidentally, 7D, though this description doesn't consider the 7D version, because honestly you likely couldn't care less). It lets us find a vector mutually perpendicular to two other vectors. This is mostly useful to find a vector normal to a surface in 3D.

As a motivating example, suppose you have three points in 3D which form a triangle. Take the points as the vectors p, q, and r. These points must be in some plane (the triangle is in that plane as well). We want a vector pointing directly out of this plane. Such a vector is useful, for instance, in collision physics, since it tells us in which direction an object bounces off the triangle.

The cross product takes two vectors that lie in a plane and returns a vector pointing directly out of that plane. In this example, two such vectors are u = (p-q) and v = (p-r) (see Section 1.3, vector subtraction, for more). Their cross product, which points out of the plane, is given by

u x v = <u.y*v.z-u.z*v.y, u.z*v.x-u.x*v.z, u.x*v.y-u.y*v.x>

There are a few edge cases to this example. If u and v point in the same (or directly opposite) direction, their cross product will be the zero vector. If either vector is the zero vector, their cross product is again the zero vector. Often, you only want direction information out of the cross product. By convention, a normal vector is usually normalized (see Section 1.3 and the unit() function). The length of the cross product does carry some information, though, and is similar to the dot product. The length of the input vectors and the angle theta between them is related to the length of their cross product by the following:

|u x v| = |u|*|v|*sin(theta)

This can be interpreted as the area of the parallelogram the two input vectors determine.