# Foundations: vectors, matrices, and the transform pipeline

The screen is flat, so something must decide where a point in space
lands on it. That is the **transform pipeline**: vectors, one 4x4
matrix, and the order operations compose in. Built here in plain Perl,
because every later chapter uses the vocabulary.

```{index}
single: handedness
single: coordinate system; handedness
single: right-handed coordinate system
```

## Handedness

Point your right thumb along x and index finger along y; your middle
finger points along z. That is a **right-handed** system, used by OpenGL
and by most mathematics: with x right and y up, **z comes out of the
screen**, so things in front of the camera have *negative* z. DirectX
and Unity are left-handed, with z going into the screen.

Both appear in files you load. Getting it wrong renders a scene inside
out or mirrors a model; it does not produce an error.

The cross product encodes the handedness, so it is where to check:

```perl
my $x = [1, 0, 0];
my $y = [0, 1, 0];
print join ", ", @{ v_cross($x, $y) };    # 0, 0, 1
```

x cross y gives +z. `0, 0, -1` means a left-handed convention has crept
in somewhere.

```{index}
single: vector
single: vector; normalising
single: dot product
single: cross product
```

## Vectors

Three numbers, as an array reference. Either a **position** or a
**direction** depending on context; the two behave differently under
translation, so it is worth tracking which you have.

```perl
sub v_add   { my ($a, $b) = @_; return [ map { $a->[$_] + $b->[$_] } 0 .. 2 ] }
sub v_sub   { my ($a, $b) = @_; return [ map { $a->[$_] - $b->[$_] } 0 .. 2 ] }
sub v_scale { my ($a, $s) = @_; return [ map { $_ * $s } @$a ] }

sub v_dot {
    my ($a, $b) = @_;
    return $a->[0]*$b->[0] + $a->[1]*$b->[1] + $a->[2]*$b->[2];
}

sub v_cross {
    my ($a, $b) = @_;
    return [ $a->[1]*$b->[2] - $a->[2]*$b->[1],
             $a->[2]*$b->[0] - $a->[0]*$b->[2],
             $a->[0]*$b->[1] - $a->[1]*$b->[0] ];
}

sub v_len  { my ($a) = @_; return sqrt(v_dot($a, $a)) }

sub v_norm {
    my ($a) = @_;
    my $l = v_len($a);
    return $l == 0 ? [0, 0, 0] : v_scale($a, 1 / $l);
}
```

Two of these carry meaning; the rest is bookkeeping.

**Dot product: alignment.** Zero when perpendicular, positive when
aligned, negative when opposed. Divided by both lengths it is the cosine
of the angle. Every lighting calculation in this guide is one dot
product.

```perl
print v_dot([1,0,0], [0,1,0]);            # 0, so perpendicular
print v_len([3, 4, 0]);                   # 5
print join ", ", @{ v_norm([3, 4, 0]) };  # 0.6, 0.8, 0
```

**Cross product: a vector perpendicular to both inputs.** Gives a
triangle's *normal* from two of its edges, and a camera's axes from a
view direction. It does not commute; swapping the arguments flips the
sign.

**Normalising** scales to length 1. Formulas that take directions assume
it, and an unnormalised one scales the result silently rather than
failing.

```{index}
single: matrix; 4x4
single: homogeneous coordinates
single: column-major order
single: transformation matrix
```

## The 4x4 matrix

Rotation and scale fit a 3x3 matrix. Translation does not, because
moving a point is an addition. Add a fourth component `w`, set it to 1
for positions, and use a 4x4: translation occupies the last column and
one multiply does all three. Coordinates carrying that component are
**homogeneous**. `w` is used again at the perspective divide below.

Storage is **column-major**, the layout OpenGL expects: element
`m[col * 4 + row]`, putting translation in elements 12, 13, 14.

```perl
sub m_identity { return [1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1] }

sub m_mul {                                   # returns a * b
    my ($a, $b) = @_;
    my @out = (0) x 16;
    for my $c (0 .. 3) {
        for my $r (0 .. 3) {
            my $s = 0;
            $s += $a->[$_ * 4 + $r] * $b->[$c * 4 + $_] for 0 .. 3;
            $out[$c * 4 + $r] = $s;
        }
    }
    return \@out;
}

sub m_translate {
    my ($tx, $ty, $tz) = @_;
    my $m = m_identity();
    @$m[12, 13, 14] = ($tx, $ty, $tz);
    return $m;
}

sub m_scale {
    my ($sx, $sy, $sz) = @_;
    my $m = m_identity();
    @$m[0, 5, 10] = ($sx, $sy, $sz);
    return $m;
}

sub m_rotate_y {
    my ($rad) = @_;
    my ($c, $s) = (cos $rad, sin $rad);
    return [ $c,0,-$s,0,  0,1,0,0,  $s,0,$c,0,  0,0,0,1 ];
}
```

Applying one to a point, with `w` carried along:

```perl
sub xform {
    my ($m, $p) = @_;                         # $p is [x, y, z, w]
    my @o;
    for my $r (0 .. 3) {
        $o[$r] = $m->[$r] * $p->[0] + $m->[4 + $r] * $p->[1]
               + $m->[8 + $r] * $p->[2] + $m->[12 + $r] * $p->[3];
    }
    return \@o;
}

my $t = m_translate(5, 0, 0);
print join ", ", @{ xform($t, [1, 2, 3, 1]) };     # 6, 2, 3, 1
```

```{index}
single: matrix multiplication; order
```

### Order

Matrix multiplication does not commute. A translate and a scale give
two different transforms depending on which side each sits:

```perl
my $ts = m_mul(m_translate(5,0,0), m_scale(2,2,2));
print join ", ", @{ xform($ts, [1, 2, 3, 1]) };    # 7, 4, 6, 1

my $st = m_mul(m_scale(2,2,2), m_translate(5,0,0));
print join ", ", @{ xform($st, [1, 2, 3, 1]) };    # 12, 4, 6, 1
```

Read a chain **right to left**. In `m_mul($translate, $scale)` the scale
runs first: `(1,2,3)` scales to `(2,4,6)`, then moves 5 along x, giving
`(7,4,6)`. The other order scales the translation too, putting x at 12.
An object that orbits the origin instead of spinning in place has this
backwards.

```{index}
single: transform pipeline
single: model space
single: world space
single: view space
single: clip space
single: normalised device coordinates
```

## The pipeline: five spaces

A vertex starts in a model file and ends as a pixel position, through a
fixed sequence.

1. **Model space.** Coordinates as authored, relative to the object's
   own origin.
2. **World space**, after the *model matrix*: where the object sits in
   the scene.
3. **View space**, after the *view matrix*: the scene re-expressed with
   the camera at the origin looking down -z. The camera never moves; the
   world moves the opposite way around it.
4. **Clip space**, after the *projection matrix*. Perspective applied
   but not divided out; `w` holds the depth the divide will use.
5. **Normalised device coordinates**, after dividing by `w`. Everything
   visible lies in a cube from -1 to +1. A scale maps that to pixels.

```{index}
single: view matrix
single: camera; look-at
```

### The camera

`m_look_at` builds the view matrix from an eye position, a target, and
an up hint, by constructing the camera's axes with cross products.

```perl
sub m_look_at {
    # $up must NOT be parallel to ($target - $eye): the cross product
    # below then has no perpendicular to find and the matrix degenerates.
    my ($eye, $target, $up) = @_;
    my $f = v_norm(v_sub($target, $eye));     # forward
    my $s = v_norm(v_cross($f, $up));         # right
    my $u = v_cross($s, $f);                  # true up, re-squared
    return [ $s->[0], $u->[0], -$f->[0], 0,
             $s->[1], $u->[1], -$f->[1], 0,
             $s->[2], $u->[2], -$f->[2], 0,
             -v_dot($s, $eye), -v_dot($u, $eye), v_dot($f, $eye), 1 ];
}

my $view = m_look_at([0, 0, 5], [0, 0, 0], [0, 1, 0]);
print join ", ", @{ xform($view, [0, 0, 0, 1]) };   # 0, 0, -5, 1
```

The camera sits 5 along z; the world origin lands at `z = -5`, five
units in front of a camera looking down -z. `up` is only a hint, which
is why `$u` is recomputed from the other two axes. An `up` parallel to
the view direction breaks it: the cross product has no perpendicular to
find.

```{index}
single: projection matrix
single: perspective projection
single: perspective divide
```

### Projection

The projection matrix puts view-space depth into `w`, so the divide that
follows shrinks distant things.

```perl
sub m_perspective {
    my ($fovy_deg, $aspect, $near, $far) = @_;
    my $pi = 4 * atan2(1, 1);
    my $half = $fovy_deg * $pi / 360;
    my $f = cos($half) / sin($half);          # cot(fovy / 2)
    return [ $f / $aspect, 0, 0, 0,
             0, $f, 0, 0,
             0, 0, ($far + $near) / ($near - $far), -1,
             0, 0, 2 * $far * $near / ($near - $far), 0 ];
}
```

The `-1` in the third column is the mechanism: it copies view-space z
into the output `w`. The rest scales to the field of view and squeezes
depth into the cube.

One point, all the way through:

```perl
my $proj = m_perspective(60, 4/3, 0.1, 100);
my $clip = xform($proj, xform($view, [0, 0, 0, 1]));
# clip = 0.000, 0.000, 4.810, 5.000      <- w is 5, the distance

my @ndc = map { $_ / $clip->[3] } @{$clip}[0 .. 2];
# ndc = 0.000, 0.000, 0.962

my ($W, $H) = (800, 600);
my $sx = ($ndc[0] * 0.5 + 0.5) * $W;
my $sy = (1 - ($ndc[1] * 0.5 + 0.5)) * $H;
# screen = (400.0, 300.0)
```

Dead centre of an 800x600 window. The `1 -` in the y line is the flip
between NDC, where y goes up, and the screen's
[top-left origin](../graphics/foundations), where it goes down. That one
line is where the two conventions meet.

```{index}
single: foreshortening
```

### Foreshortening

Nothing above special-cases distance, yet distant things shrink, because
`w` grows with depth and everything is divided by it:

```perl
for my $z (1, 2, 4, 8) {
    my $c = xform($proj, xform($view, [1, 0, -$z, 1]));
    printf "z=%-2d  ndc.x = %.3f   w = %.2f\n", -$z, $c->[0] / $c->[3], $c->[3];
}
# z=-1   ndc.x = 0.217   w = 6.00
# z=-2   ndc.x = 0.186   w = 7.00
# z=-4   ndc.x = 0.144   w = 9.00
# z=-8   ndc.x = 0.100   w = 13.00
```

The same point, one unit off the axis, drifts toward the centre as it
recedes. Perspective is a division, not an effect applied on top.

```{index}
single: rotation; Euler angles versus quaternions
single: Euler angles
single: gimbal lock
single: quaternion
```

## Rotations

**Euler angles**: three numbers, one per axis. Readable, so this is what
a user interface should show. Two failures: **gimbal lock**, where at
certain orientations two axes align and a degree of freedom is lost, and
poor interpolation, taking curved paths between orientations.

**Quaternions**: four numbers encoding an axis and angle together. No
gimbal lock, compose by multiplication, interpolate smoothly. Not
readable by inspection.

Store quaternions, expose Euler angles, convert at the edges.

## Next

The [rasteriser](software-rasteriser) turns these screen positions into
pixels: which triangles face away, and what to do when two land on the
same pixel.