Geometry and Algebra for 3D Applications

Why linear algebra specifically?

First, in any 3D application we inevitably encounter vectors and rotations. Vector, Matrix — everyone has heard these terms. We move objects, rotate them by certain angles, and extract all sorts of useful information along the way for further calculations… That's why the ability to work with them quickly and efficiently, bypassing unnecessary trigonometry where it isn't needed, is extremely important!

Second, even after working in geodesic coordinates, everything eventually reduces to ordinary three-dimensional Euclidean space. That's how rendering works: simple, not curved. So knowing linear algebra is the foundation of a 3D developer's life!

And besides, many people's math knowledge is fragmentary. We need to fill in the gaps!

What is a 3D engine's math library made up of?

Game engines usually have 3 groups:

1. Vectors. Can be a point, a radius vector, a direction (normal), linear velocity, angular velocity, or angles in degrees or radians (Euler angles).

A point vector is simply a position in space. A radius vector means its origin is at 0 relative to the coordinate origin. A direction is a normalized vector, which can be called a radius vector of fixed (unit) length. Linear velocity and angular velocity are responsible for dynamics. We'll examine Euler angles in detail in the second lesson.

1. Matrices. Translation matrix, rotation matrix, scaling matrix, transformation matrix (TRS), projection matrices (perspective, orthographic), systems of linear algebraic equations, the Jacobian matrix and inertia tensor, and the homography matrix.

The homography matrix is used in cameras for correct projection from different viewing angles.

1. Quaternions. Rotation expressed in quaternions.

What can be used to represent an object's orientation?

1. 3x3 rotation matrix (Matrix 3x3). To get a rotation, it's enough to multiply the rotation matrix by a vector or by a transformation matrix. But problems arise when you need to smoothly rotate an object from one set of angles to another — this can't be done with simple methods. In addition, rounding errors easily accumulate when a matrix is multiplied many times. As a result, the object becomes skewed (rhomboid).

1. Euler Angles. Consist of Roll, Pitch, and Yaw. This is easy to understand and easy to visualize. Interpolation around a single axis is also easy to do, but interpolation across two axes won't follow the shortest path — it will follow an S-shaped curve. In addition, it's convenient for limiting joint rotation in degrees. The main drawback is gimbal lock (more on that later).

1. Axis – Angle. A simple method with simple interpolation and convenient rotation limiting. However, it's inconvenient for combining several rotations together to get a single rotation object.

1. Quaternions (Quaternion). Can be represented as a point on the surface of a unit-radius 3-sphere in four-dimensional space. Rotations combine easily, and interpolation follows the shortest path. There's no such drawback as gimbal lock. Simple to limit rotation. However, they're difficult to read. In addition, they accumulate error with repeated multiplication — they need to be normalized periodically.

1. Exponential Map. Resembles Axis-Angle. Easy to combine rotations. Has fewer degrees of freedom, so it's only suitable as rotation dynamics.

1. 6D Representation. Often obtained incidentally at the end of calculations. Frequently used in neural networks. Essentially, it's two axes: Forward and Up. Used as a basis for constructing a 3x3 matrix.

By the way…

For x you need to take the cos of the angle, and for y — the sin of the angle. You can also use the atan2 function, which operates in the range from -π to π.

A few words about the performance of math functions

Addition (plus), subtraction (minus), multiplication (mult), and division (div) take roughly the same amount of time. For example, computing a square root (sqrt) is about 3.6 times slower. The slowest are: arccosine (acos), arcsine (asin), arctangent (atan), and rounding (round).

Conclusions:

1. Trigonometry is very slow. Especially the functions that return angles.

2. Taking a square root (sqrt) is about as fast as 6 multiplications (6_mult).

3. Computing the maximum element (max) and rounding (round) are, surprisingly, very slow.

Vector operations in 2D

The basic ones: vector addition, vector subtraction, multiplying a vector by a scalar, and vector normalization. Under the hood, they have simple code with simple normalization and length calculation.

Example. There's a character standing at the origin who wants to run to a tree. In this example, all 4 basic operations can be used:

vec2 pos = vec2(2,2); // character position
vec2 tree = vec2(6,4); // tree position
vec2 distance = tree - pos // radius vector
vec2 direction = distance.normalize(); // normalized unit vector

vec2 new_pos = pos + direction * IFps // take the old position and multiply the vector by a scalar

dot product — the dot product of vectors

This is an operation on two vectors whose result is a scalar:

float dot(vec2 v0, vec2 v1) { v0.x * v1.x + v0.y * v1.y; // 2 multiplications, 1 addition }

1. Equal to the product of the lengths of the vectors times the cosine of the angle between them:

dot(a,b) = |a||b|cos(angle_rad)

1. The dot product is > 0 if the vectors point in the same direction, 0 — if the vectors are perpendicular, and < 0 if they point in opposite directions.

2. It is the length of the projection of an arbitrary vector onto a normalized vector:

proj_length = dot(a, normal)

1. The dot product of a vector with itself is the square of the vector's length:

dot(a,a) == length2(a)

1. The projection vector can be obtained like this:

proj_point = b*dot(a,b)/dot(b,b)

1. dot(a,b) == dot(b,a)

Where else is dot used?

So how do you find a perpendicular?

In 2D it's simple: swap (x,y) and flip the sign of one of the components. For example, for clockwise rotation you need to put a minus on the second component, and for counterclockwise — on the first.

What if you combine dot and finding a perpendicular?

There's an operation for this called skew product. This is an operation on two vectors whose result is a pseudoscalar:

float skew(vec2 v0, vec2 v1) { v0.x * v1.y - v0.y * v1.x; // 2 multiplications, 1 subtraction }

In UNIGINE this operation is called cross.

Where else is skew used?

Vector operations in 3D

Working with vectors in 3D differs little from 2D. You could say that if you've solved a problem in 2D, you've solved it in 3D as well. So, for example, the dot product of vectors, discussed below, works the same way in 2D and 3D.

But in 3D there's an additional operation, the cross product — the vector product of vectors. We'll talk about it at the end of the chapter.

Where else is dot used in 3D?

In shaders. Everywhere. For example, let's look at the simplest lighting model, Lambert's (Lambert, Lambertian Reflectance, or Diffuse Light):

We have a model with a set of normals and a light source somewhere.

We simply compute the angle between the light source and the surface normal. The smaller the angle, the brighter the pixel.

Here's what the algorithm looks like:

1. Get the normal vector of the current pixel — NormalVector.

2. Get the direction vector of the light relative to the current pixel — LightVector.

3. Normalize the vectors.

4. Compute the angle between them — dot.

5. Multiply the final color by this coefficient and the attenuation coefficient.

float diffuse = max(dot( LightVector, NormalVector ), 0.0);
float attenuation = saturate(1.0 - DistanceToLight / LightRadius);

FragColor = color * diffuse * attenuation;

cross product — the vector product of vectors

The cross product appears in 3D space. This is an operation on two vectors whose result is a vector perpendicular to the original two:

vec3 cross(const vec3 &v0, const vec3 &v1)
{
    vec3 ret;
    ret.x = v0.y * v1.z - v0.z * v1.y;
    ret.y = v0.z * v1.x - v0.x * v1.z;
    ret.z = v0.x * v1.y - v0.y * v1.x;
    return ret; // 6 multiplications, 3 subtractions
}

1. The length of the resulting vector equals the area of the parallelogram formed by the original vectors.

2. The length of the result is also |a||b|sin(angle_rad)

3. The perpendicular is constructed using the "right-hand" rule.

4. Not commutative. That is: cross(a,b) != cross(b,a)

If you're curious how this result can then be used to rotate a body:

vec3 torque; // torque
quat rotation; // current body rotation

// qnew = q0 + 0.5 * w * q0
quat q = (rotation + quat(torque * ifps) * rotation * 0.5f).normalize();

Of course, the tank problem can also be solved via:

vec3 rel_pos =
    inverse(tank_transform_mat4) * vec3_target_position;

If the inverse matrix is known, this approach will be roughly comparable in speed to the dot(cross) combination.

But… We don't always have the inverse matrix on hand. We might be in the process of changing direction. And there isn't always a matrix as such to begin with.

Fun fact: Remember the problem of finding a reflected vector? Knowing this, you can easily do the same thing via dot (and it will even work faster!):

vec3 new_dir = dir - 2 * dot(dir, normal) * normal;

dot(cross()) — scalar triple product, the mixed product

The dot product of vector a with the cross product of vectors b and c

float scalar_triple(const vec3 &a, const vec3 &b, const vec3 &c)
{
    // 9 multiplications, 5 additions
    return dot(a, cross(b, c));
}

1. The absolute value of the scalar triple product is numerically equal to the volume of the parallelepiped formed by vectors a, b, c.

2. dot(a,cross(b,c)) == dot(cross(a,b),c)

3. Equal to the determinant of the matrix composed of vectors a, b, c. Including in terms of performance.

4. The 3D analog of skew.