1. Coordinate systems and affine transformations
Track points through scale, rotation, and translation in the correct order.
FREE COMPUTER SCIENCE STACK LEVEL · 18 OF 20
How do numerical models produce images and simulated worlds?
How do numerical models produce images and simulated worlds?
Geometry becomes images and motion. This layer connects Transforms, Projection, Rasterization, Sampling, Integration to the rest of the computing stack.
Follow a point from coordinate systems to covered samples, then follow a physical state through a numerical time step. Test geometric invariants, representation assumptions, and numerical error.
How do numerical models produce images and simulated worlds?
This section is a sequence of worked studies. Each study asks you to reconstruct an example, solve a new problem, and check the assumptions behind your answer. Keep your derivations and code so you can revisit them without looking at the solution.
Track points through scale, rotation, and translation in the correct order. Distinguish points from direction vectors. Compose affine transformations. Explain why transformation order matters.
Explain why distant objects shrink and why division needs a valid domain. Calculate a pinhole projection. Distinguish perspective from orthographic projection. Explain clipping before perspective division.
Turn geometric coverage into reproducible pixel decisions. Compute barycentric weights. Interpolate vertex attributes. Explain depth testing and edge conventions.
Connect image artifacts to the signals and units being processed. Explain spatial aliasing. Distinguish encoded values from light intensity. Use premultiplied alpha consistently.
Explain how a correct force law can still produce an unstable animation. Step a motion model numerically. Distinguish discretization error from model error. Test convergence and conservation.
Vectors and matrix multiplication. Each lesson names any additional prerequisites. Revisit the mathematics and programming sections whenever a calculation or execution trace becomes a barrier.
Build a tiny software renderer or particle simulator. Publish numerical reference cases, an image or trace, and an error analysis that separates model assumptions from implementation defects. A correct multiple-choice answer is only one kind of evidence. Preserve the intermediate steps, test an edge case, and explain why an attractive alternative fails.
The primary readings provide fuller treatments and additional exercises. Work the section project after the guided problems, then return to a problem a few days later without notes. Use a failed attempt to identify the specific definition, assumption, or step that needs more practice.
Track points through scale, rotation, and translation in the correct order.
Explain why distant objects shrink and why division needs a valid domain.
Turn geometric coverage into reproducible pixel decisions.
Connect image artifacts to the signals and units being processed.
Explain how a correct force law can still produce an unstable animation.
About 35 minutes. Coordinates and barycentric weights.
Triangle vertices are (0,0), (4,0), (0,4). Test the centers of a 4×4 pixel grid at (i+0.5,j+0.5), where i,j are 0 through 3. Include all boundary samples for this isolated-triangle exercise.
Coverage requires x>=0, y>=0, and x+y<=4.
Covered rows contain 4,3,2,1 centers, totaling 10. At (0.5,0.5), weights are (0.75,0.125,0.125), giving 1.5. At (1.5,1.5), weights are (0.25,0.375,0.375), giving 4.5. Including every boundary is acceptable for one isolated triangle but double-counts a shared edge when adjacent triangles use the same rule. A mesh needs a consistent ownership rule.
Change the boundary rule to x+y<4. Which centers change coverage?
Use explicit coordinate conventions, numerical models, and color spaces. A plausible picture is not proof that the computation is correct.
1. Matrix trace · allow 35 minutes
Use column vectors in 2D homogeneous coordinates. Let T translate by (3,1) and R rotate counterclockwise by 90 degrees. Write both 3×3 matrices. For point p=(2,0,1), compute TRp and RTp. Transform direction d=(2,0,0). Explain why a normal under a nonuniform linear scale uses the inverse transpose rather than the same matrix as a tangent.
The rightmost matrix acts first. A normal must remain perpendicular to every transformed tangent.
T=[[1,0,3],[0,1,1],[0,0,1]] and R=[[0,−1,0],[1,0,0],[0,0,1]]. Rp=(0,2,1), so TRp=(3,3,1). Tp=(5,1,1), so RTp=(−1,5,1). Their difference demonstrates that transform order changes the result. For the direction, Td=d because its homogeneous coordinate is zero; both TRd and RTd equal (0,2,0).
If nᵀt=0 and a nonsingular linear transform sends tangent t to Mt, choose n′=M⁻ᵀn. Then n′ᵀMt=nᵀM⁻¹Mt=nᵀt=0. Applying M directly to both vectors does not generally preserve perpendicularity under nonuniform scaling. Renormalize the transformed normal when unit length is required. Singular transforms have no inverse and need separate treatment; the formula cannot be applied blindly to a scale that collapses an axis.
2. Geometry and interpolation · allow 45 minutes
Use a camera looking along positive z with projection x′=x/z, y′=y/z and near plane z=1. A segment runs from A=(0,0,0.5) to B=(2,0,2). Find its near-plane intersection before projection. A screen-space triangle has barycentric weights (1/2,1/4,1/4), vertex attributes u=(0,1,0), and clip w values (1,2,4). Compare naive interpolation with perspective-correct interpolation. Why must coverage rules agree along shared triangle edges?
Solve A+t(B−A) at z=1. For perspective correction interpolate u/w and 1/w, then divide.
The segment has z=0.5+1.5t, so t=1/3. The intersection is (2/3,0,1), which projects to (2/3,0). Clipping avoids treating geometry behind or too close to the camera as ordinary projected points; dividing near zero can produce unbounded coordinates and incorrect visibility.
Naive u is 1/4. Perspective-correct u is [Σλᵢuᵢ/wᵢ]/[Σλᵢ/wᵢ]=(1/8)/(1/2+1/8+1/16)=(1/8)/(11/16)=2/11≈0.1818. The screen-space weights are not the original surface's affine weights after perspective division. Depth interpolation follows the pipeline's defined representation and must not be confused with arbitrary attribute interpolation.
Two adjacent triangles should assign a sample on their shared edge consistently, usually to exactly one primitive under a documented fill rule. If both exclude it, a crack appears; if both include it, blending or stencil effects may double-count it. Numerical precision, winding, and edge rules must agree across the implementation.
3. Sampling and color calculation · allow 40 minutes
Average equal areas of black and white. Compare averaging their sRGB encoded values directly with averaging linear light then encoding. Use the sRGB encoding function E(L)=12.92L for L≤0.0031308, otherwise E(L)=1.055L^(1/2.4)−0.055. Explain why a one-sample-per-pixel checkerboard can alias and why increasing contrast after rendering cannot restore information lost during sampling.
Black and white correspond to linear values zero and one. A pixel estimates an area or filtered integral, not necessarily the color at its center.
Direct encoded averaging gives 0.5. Linear-light averaging gives L=0.5, then E(0.5)≈0.73536. An encoded value of 0.5 decodes to roughly 0.21404 linear light, substantially darker than half the light. The correct operation depends on what is being combined, but physical light contributions and ordinary radiometric filtering should be handled in an appropriate linear representation before display encoding.
A high-frequency checkerboard can place every pixel-center sample on the same color or produce a low-frequency pattern unrelated to the true area average. Different continuous images can generate identical point samples, so a later contrast adjustment cannot recover the discarded distinctions. Use suitable prefiltering or multiple well-distributed samples to estimate the pixel footprint, with reconstruction choices matched to the signal and display. More samples reduce some errors but do not remove every bias or guarantee a sharp alias-free result at arbitrary resolution. Test phase shifts of the pattern, not just one conveniently aligned image.
4. Derive and test · allow 40 minutes
For dx/dt=−2x with x(0)=1, forward Euler gives xₙ₊₁=(1−2h)xₙ. Determine the positive step sizes for decay in magnitude, nonnegative monotone decay, and instability. Compute the first four updates for h=0.25 and h=1.1. Compare with the exact x(t)=exp(−2t). Explain why a smaller local error does not by itself prove long-run stability for every differential equation.
Study the multiplier's magnitude and sign separately. The continuous solution remains positive even when a numerical sequence alternates.
Magnitude decays when |1−2h|<1, giving 0<h<1. Nonnegative monotone decay occurs for 0<h≤0.5; at h=0.5 the method reaches zero in one step, which is stable but not the exact positive solution. For 0.5<h<1 it alternates sign while shrinking. At h=1 the magnitude stays constant and the sign alternates, so it does not reproduce physical decay. For h>1 the magnitude grows.
At h=0.25 the sequence after each update is 0.5,0.25,0.125,0.0625, at times 0.25,0.5,0.75,1. The exact value at time one is exp(−2)≈0.13534. At h=1.1 the multiplier is −1.2 and the first four values are −1.2,1.44,−1.728,2.0736, while the exact solution rapidly decays. Local truncation error describes a single step started from the exact state; global behavior also depends on propagation of errors and the method's stability region. Stiff systems can require impractically small explicit steps even when the desired solution changes slowly.
6 to 8 hours. Implement a small CPU renderer that writes a PPM image without graphics libraries. Input is a JSON scene containing three-dimensional vertices, triangle indices, per-vertex colors, and model and view transformations. Begin with orthographic projection onto a fixed image plane so perspective clipping does not obscure the central ideas. Define coordinate handedness, matrix multiplication order, viewport mapping, pixel-center locations, and the depth convention. Transform vertices, reject degenerate triangles, rasterize using edge functions or barycentric coordinates, interpolate colors, and resolve visibility with a depth buffer. Specify a consistent shared-edge coverage rule to avoid cracks or double ownership. Output the rendered image plus counters for triangles, covered samples, and depth passes. Create diagnostic scenes for overlapping triangles, opposite winding, off-screen geometry, and shared edges. Use standard-library Python arithmetic and file writing; the renderer should run entirely on the CPU. Explain which pipeline stages are implemented and which, such as lighting, perspective-correct interpolation, and clipping against a full view frustum, remain extensions. Save a tiny image fixture whose relevant pixel colors and depths can be inspected numerically. Visual plausibility alone cannot distinguish a correct rasterizer from one with consistent coordinate or interpolation errors.
Add perspective projection with homogeneous clipping and perspective-correct attribute interpolation, using a checkerboard scene to expose incorrect interpolation.