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.

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:

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.

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.

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.

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.

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.

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:

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

Order#

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

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.

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.

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.

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.

Projection#

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

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:

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, where it goes down. That one line is where the two conventions meet.

Foreshortening#

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

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.

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 turns these screen positions into pixels: which triangles face away, and what to do when two land on the same pixel.