This chapter links to the course’s interactive demos and uses MathJax for its formulas. Read it through the course website (or download the file and open it in a browser); a Canvas inline preview will reach neither the demos nor the math. All chapters.

Vectors: Dot and Cross Products, Lines and Planes

Modern vector notation, with the dot product, the cross product and the del operator, was developed independently by Josiah Willard Gibbs and Oliver Heaviside in the 1880s. Gibbs, Elements of Vector Analysis, 1881–84; Heaviside, Electromagnetic Theory, 1893

A vector is a displacement: a direction with a length, not a place. Two operations on vectors carry the whole of this course. The dot product answers “how aligned are these?” and yields angles, projections and which-side tests; the cross product answers “what is perpendicular to both?” and yields normals, areas, volumes and coordinate frames. Lines and planes are then a point plus a direction, or a point plus a normal, and every question about them, including where a ray meets a plane and where a point sits inside a triangle, is one of the two products again. One pair of vectors, \(\mathbf{a} = (2, 1, 0)\) and \(\mathbf{b} = (1, 2, 1)\), runs through every worked example and through the live demo, so the numbers on the page and the numbers on the screen agree to the last digit. The chapter closes with the arithmetic itself: what single-precision floating point does to a dot product between nearly parallel vectors, and which formula to use instead.

1 · Vectors are displacements

Two different things wear the same three numbers \((x, y, z)\). A position is a place, measured from the origin. A displacement is how to get from one place to another: an arrow with a direction and a length, which you may pick up and put down anywhere. A position is the special displacement from the origin, and that is the only reason a point and a vector look alike. The distinction returns with force in the affine chapter, where a translation moves points and leaves displacements alone.

1.1 Bases and coordinates

The three numbers of a vector are its coefficients in a basis: \(\mathbf{v} = v_x\hat{\mathbf{x}} + v_y\hat{\mathbf{y}} + v_z\hat{\mathbf{z}}\), a linear combination of the three axis vectors. Any three vectors that do not lie in a common plane can serve as a basis, and the same displacement then has different coordinates. The useful case is an orthonormal basis, three mutually perpendicular unit vectors \(\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3\), because then the coordinates need no equation solving:

2 · The dot product

Three questions, one number: how aligned are two directions, how much of one points along the other, and is a thing in front of me or behind me.

2.1 Projection: split a vector along and across a direction

“How much of \(\mathbf{a}\) points along \(\mathbf{b}\)?” Decompose \(\mathbf{a}\) into a piece along \(\mathbf{b}\) and a piece perpendicular to it:

The scalar \((\mathbf{a}\cdot\mathbf{b})/(\mathbf{b}\cdot\mathbf{b})\) is how many copies of \(\mathbf{b}\) fit in the shadow of \(\mathbf{a}\). When \(\mathbf{b}\) is a unit vector the denominator is 1 and \(\mathbf{a}\cdot\hat{\mathbf{b}}\) is directly the shadow’s length, positive or negative. This split is the move behind reflection (the illumination chapter builds the mirror direction from it), Rodrigues’ rotation formula in the rotation chapter, and the frame construction of Section 4.

2.2 The sign is a decision

If \(\mathbf{a}\) is the way the drone faces and \(\mathbf{b}\) points toward the target, \(\mathbf{a}\cdot\mathbf{b} > 0\) means the target is ahead. Section 6 reuses this sign verbatim as the which-side-of-a-plane test, and Lambert’s law clamps exactly this sign to decide whether a surface faces a light.

3 · The cross product

The dot gives a number; sometimes a direction is needed: which way a triangle faces, a third axis given two, the size of the parallelogram two edges span.

The component formula has a cyclic pattern (the \(x\) component uses \(y\) and \(z\), the \(y\) component uses \(z\) and \(x\), the \(z\) component uses \(x\) and \(y\)), which is how to remember it. It exists only in three dimensions; in two, the single number \(a_x b_y - a_y b_x\) plays its part, and that number is the edge function of the rasterization chapter.

3.1 The normal of a triangle

A face with corners \(P_0, P_1, P_2\) has edges \(\mathbf{e}_1 = P_1 - P_0\) and \(\mathbf{e}_2 = P_2 - P_0\), and its normal is \(\hat{\mathbf{n}} = \widehat{\mathbf{e}_1\times\mathbf{e}_2}\). Which side the normal points to is decided by the order of the corners, so a mesh whose faces are wound inconsistently has half its normals pointing inward. This single idea, normal equals normalized cross of two edges, reappears in meshes, lighting, and collision for the rest of the course.

3.2 The scalar triple product: volume and handedness

4 · From two vectors to a frame

A frame is a set of axes to measure along; it is orthonormal when each axis has unit length and each is perpendicular to the others, so that coordinates are plain dot products (Section 1.1). Given any two non-parallel vectors, one cross product gives an axis square to both and a second cross completes an orthonormal trio. This is exactly how a camera’s look-at basis is built in the viewing chapter:

4.1 Gram–Schmidt: a frame from any three vectors

The cross-product recipe is specific to three dimensions. The general recipe, which works in any dimension and is what a linear-algebra library uses, is Gram–Schmidt orthogonalization: take the vectors in order, and from each subtract its projections onto the axes already built, then normalize. The projection is Section 2.1’s split, applied once per finished axis.

5 · Lines and segments

The nearest point on a line to a query point \(P_t\) is a projection: dot the offset \(P_t - P_0\) against the unit direction \(\hat{\mathbf{d}}\) to get the distance \(t\) along the line, and step that far. For a segment, clamp \(t\) to the endpoints first. That clamp is the one line separating “the infinite line” from “the thing you can walk on”.

5.1 Distance to a line in three dimensions

The foot construction works in any dimension, but in three the cross product gives the distance in one step: the offset \(\mathbf{p} = P_t - P_0\) and the unit direction \(\hat{\mathbf{d}}\) span a parallelogram of base 1 and height equal to the distance, so \(\text{dist} = \|\mathbf{p}\times\hat{\mathbf{d}}\|\), while \(\mathbf{p}\cdot\hat{\mathbf{d}}\) is the distance along the line. The two are the legs of a right triangle whose hypotenuse is \(\|\mathbf{p}\|\).

5.2 The distance between two skew lines

In three dimensions two lines usually neither meet nor run parallel; such lines are called skew. The shortest segment between them is perpendicular to both, so it runs along \(\mathbf{d}_1\times\mathbf{d}_2\), and its length is the part of any connecting vector along that direction:

6 · Planes and signed distance

The which-side test needs no distance at all: the sign of \(\hat{\mathbf{n}}\cdot P - D\) is the in-front-of test of Section 2.2 with the plane’s constant subtracted. Frustum culling (skipping objects outside the camera’s view volume, a box bounded by six planes), back-face tests and portal visibility are this sign, evaluated many times. Under a transform a plane does not move like a point; the affine chapter’s Appendix gives the rule.

6.1 Projection onto a plane, and reflection

The projection split of Section 2.1, against the unit normal, gives the two other plane operations. Removing the part along the normal leaves the part that lies in the plane, and negating it mirrors the vector across the plane:

6.2 Where a ray meets a plane

7 · Barycentric coordinates in a triangle

A point in the plane of a triangle can be written as a weighted average of the corners, \(X = w_0 P_0 + w_1 P_1 + w_2 P_2\) with \(w_0 + w_1 + w_2 = 1\). The weights are the barycentric coordinates of \(X\), and they are ratios of areas, which the cross product supplies:

The rasterization chapter computes the same weights in two dimensions with edge functions and uses them for every interpolated attribute; the ray-tracing chapter uses the three-dimensional form above to decide whether a ray’s hit on a triangle’s plane lies within the triangle. (The name comes from barycenter, the center of mass: \(X\) is the balance point of masses \(w_0, w_1, w_2\) placed at the corners, and the centroid, the corners’ average, has equal weights.)

8 · What floating point does to all of this

A GPU and most of a game run in single precision (float32: 24 significant bits), whose relative resolution, the machine epsilon, is the gap between 1 and the next representable number, \(\varepsilon = 2^{-23} \approx 1.2\times10^{-7}\): a number near 1 can only be represented to about seven decimal digits. Most of the chapter is immune to that. Two operations are not.

The second hazard is normalizing a short vector. The length is a square root of a sum of squares, and squares underflow: in float32, \((10^{-20})^2\) is a denormal \(10^{-40}\) that still works, but \((10^{-25})^2\) is exactly 0, so a vector of length \(1.4\times10^{-25}\) normalizes to \(0/0\). A vector that small arises whenever a cross product is taken of nearly parallel inputs (the look-at failure of Exercise 4) or a difference of two nearly equal points. The guard is a length test before the divide. The course library’s normalize has none: normalize([0, 0, 0]) returns [NaN, NaN, NaN], so the test belongs to the caller. lookAtBasis makes it, throwing a RangeError when eye and at coincide or when up is parallel to the view direction (lengths below \(10^{-8}\)). What to return when the test fails is the caller’s decision, and the meshes chapter returns a fixed up vector for a degenerate normal.

Large coordinates have a third hazard: catastrophic cancellation (subtracting two nearly equal numbers cancels their leading digits, and what is left is mostly their rounding errors). float32 values near \(10^6\) are \(0.0625\) apart, so the points \(x_1 = 1000000.1\) and \(x_2 = 1000000.2\) are stored as \(1000000.125\) and \(1000000.1875\), and \(x_2 - x_1\) comes out \(0.0625\) instead of \(0.1\), 37.5 percent wrong; near the origin the same subtraction is right to eight digits. The subtraction is exact; the damage was done when the large numbers were stored. Positions far from the origin are the usual source (a world a million units across, a camera near the edge of it); the cure is to keep the numbers small, storing positions relative to a nearby origin (the camera, the object) before they become float32. Large-world games move the origin with the player (a floating origin).

9 · The same operations in code

The course’s library (lib/core/xform.js) and Unity’s Vector3 expose exactly the atoms above: components, magnitude, normalize, dot, cross. The implement-and-replace rule of the homework is to build the query from the atoms first, then check it against the engine call. The point-to-segment query of Section 5, with the library’s sub, dot and normalize and two one-line helpers:

const add = (p, q) => [p[0] + q[0], p[1] + q[1], p[2] + q[2]];
const scale = (p, s) => p.map((x) => x * s);
const d    = sub(P1, P0);              // segment direction
const p    = sub(Pt, P0);              // offset of the query point
const dHat = normalize(d);             // unit direction
const t    = dot(p, dHat);             // distance along the line
const foot = add(P0, scale(dHat, t));  // the foot of the perpendicular
const inside = t >= 0 && t <= Math.hypot(...d);   // the clamp test

Two habits keep this code honest. Normalize before you dot when you want a length, or the result is scaled by the direction’s magnitude. And test for zero-length vectors before calling normalize, which does not test for you: a zero vector has no direction, so its angle with anything is undefined, and the library’s divide by a zero length returns three NaNs that propagate into everything computed from them.

10 · Exercises

node -e "import('./lib/core/xform.js').then(x=>{const P=[[0,0,0],[2,0,0],[0,0,-2]],X=[1,0,-0.5];const n=x.cross(x.sub(P[1],P[0]),x.sub(P[2],P[0]));const nn=x.dot(n,n);console.log([0,1,2].map(i=>x.dot(x.cross(x.sub(P[(i+1)%3],X),x.sub(P[(i+2)%3],X)),n)/nn));})"