FREE COMPUTER SCIENCE STACK LEVEL · 18 OF 20

Graphics & simulation

How do numerical models produce images and simulated worlds?

The question this layer answers

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.

Geometry becomes images and motion

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.

What you will work through

1. Coordinate systems and affine transformations

Track points through scale, rotation, and translation in the correct order. Distinguish points from direction vectors. Compose affine transformations. Explain why transformation order matters.

2. Perspective projection and clipping

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.

3. Triangles, barycentric coordinates, and visibility

Turn geometric coverage into reproducible pixel decisions. Compute barycentric weights. Interpolate vertex attributes. Explain depth testing and edge conventions.

4. Sampling, filtering, and linear-light color

Connect image artifacts to the signals and units being processed. Explain spatial aliasing. Distinguish encoded values from light intensity. Use premultiplied alpha consistently.

5. Numerical integration and simulation stability

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.

Before you begin

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.

Evidence of understanding

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.

Continue beyond the guided lessons

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.

Free Graphics & simulation lessons

Practice lab: Rasterize a right triangle by hand

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.

  1. List covered sample centers.
  2. Compute weights for (0.5,0.5) and (1.5,1.5).
  3. Assign vertex values 0,4,8 and interpolate both samples.
Hint

Coverage requires x>=0, y>=0, and x+y<=4.

Worked solution

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.

  • List all ten covered centers.
  • Weights sum to one and reproduce each point.
  • Explain the shared-edge limitation.

Change one assumption

Change the boundary rule to x+y<4. Which centers change coverage?

Trace the image from geometry to sampled pixels

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

Translation and rotation do not commute

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.

Get a starting hint

The rightmost matrix acts first. A normal must remain perpendicular to every transformed tangent.

Compare your reasoning with the worked solution

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.

Check your reasoning

  • State and follow the column-vector convention.
  • Distinguish points from directions.
  • Derive normal transformation from orthogonality.

2. Geometry and interpolation · allow 45 minutes

Divide after clipping, then interpolate correctly

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?

Get a starting hint

Solve A+t(B−A) at z=1. For perspective correction interpolate u/w and 1/w, then divide.

Compare your reasoning with the worked solution

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.

Check your reasoning

  • Clip in the specified camera space before division.
  • Compute numerator and denominator separately.
  • Explain shared-edge ownership and numerical consistency.

3. Sampling and color calculation · allow 40 minutes

A midpoint in encoded color is not half the light

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.

Get a starting hint

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.

Compare your reasoning with the worked solution

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.

Check your reasoning

  • Compute the linear-light midpoint and encoded result.
  • Explain aliasing as information loss, not only blur.
  • Test sampling phase and state filtering assumptions.

4. Derive and test · allow 40 minutes

A stable physical system can have an unstable update

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.

Get a starting hint

Study the multiplier's magnitude and sign separately. The continuous solution remains positive even when a numerical sequence alternates.

Compare your reasoning with the worked solution

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.

Check your reasoning

  • Separate magnitude stability from sign behavior.
  • Compare at equal physical times.
  • Explain error propagation and the step-size restriction.

Study the underlying methods

Section project: Write a software triangle renderer

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.

Milestones

  1. Specify coordinate, transform, viewport, sample, and depth conventions with a worked point calculation.
  2. Implement transformations and triangle bounding-box traversal clipped to image dimensions.
  3. Implement coverage, barycentric color interpolation, and degenerate-triangle handling.
  4. Add depth testing and diagnostic image fixtures.
  5. Compare pixel-level results with hand-computed sample points and document shared-edge behavior.

Acceptance criteria

  • A known transformed vertex lands at the hand-calculated image coordinate under the published matrix convention.
  • Barycentric weights at covered nondegenerate samples sum to one within a stated tolerance.
  • Reversing triangle winding preserves its visible result when back-face culling is disabled.
  • Two overlapping triangles show the nearer surface regardless of input order, except for the explicitly documented equal-depth tie rule.
  • Two triangles forming a rectangle cover its interior without cracks under the shared-edge convention.
  • Degenerate or fully off-screen triangles cause neither division by zero nor out-of-bounds writes.

Add perspective projection with homogeneous clipping and perspective-correct attribute interpolation, using a checkerboard scene to expose incorrect interpolation.

Practise Graphics & simulation free →