Introduction to Graphics

Overview

The course is structured around the Visual Computing Pipeline, which describes how visual information flows between the physical world, computers, and human observers:

Pipeline Stages

1. Scene Description

The mathematical model of the 3D scene:

• Geometry (objects, shapes, surfaces)
• Materials (surface properties, textures)
• Lighting (light sources, intensities)
• Camera (viewpoint, projection)

2. Computer Graphics (Rendering)

The process of generating a digital image from the 3D scene description:

• Input: Scene description
• Output: 2D array of pixel values
• Methods: Ray tracing, rasterisation

3. Image Display

Converting the digital image in memory into physical light output:

• Monitor (CRT, LCD, OLED)
• Projector
• Print

4. Visual Perception

How the human eye and brain capture and process the displayed light to perceive the scene:

• Photoreceptor response
• Neural processing
• Cognitive interpretation

5. Image Analysis and Computer Vision

The inverse of rendering: extracting a 3D scene description or understanding from digital images:

• Object recognition
• Depth estimation
• Scene understanding

Forward vs Inverse Problems

Forward (Graphics): Scene → Image

• Well-defined mathematical process
• Rendering algorithms solve this

Inverse (Vision): Image → Scene

• Ill-posed problem
• Multiple scenes can produce the same image

Summary

• The visual computing pipeline describes the flow from scene to perception
• Computer graphics solves the forward problem (scene to image)
• Computer vision solves the inverse problem (image to understanding)
• Understanding the whole pipeline helps design better rendering algorithms

What is a Digital Image?

A digital image can be understood from two perspectives:

• Computing perspective: A 2D array of pixels stored in memory
• Mathematical perspective: A 2D function $I(x, y)$ giving intensity at any coordinate

The Pixel

A pixel (Picture Element) is:

• In computing: A triple of values for red, green, and blue channels, typically stored as bytes (0-255)
• In mathematics: A point sample with no dimension or area

Important: A pixel is not a box, disk, or tiny light. It is a sample point.

Why This Matters

A pixel as a point sample means:

• No inherent size or shape
• Represents the value at an exact location
• Can be resampled to any output resolution

Image as a 2D Function

Mathematically, an image can be viewed as: $I: \mathbb{R}^2 \rightarrow \mathbb{R}^3$

mapping spatial coordinates $(x, y)$ to a colour vector $(r, g, b)$.

For greyscale: $I: \mathbb{R}^2 \rightarrow \mathbb{R}$

mapping to a single intensity value.

Resolution

Spatial resolution: The number of pixels in each dimension (width × height).

Example: A 1920 × 1080 image has 2,073,600 pixels.

Summary

• A digital image is a 2D array of pixel samples
• Pixels are point samples with no area, not little squares
• Images can be viewed mathematically as 2D functions
• Resolution determines the sampling density

Past Paper Questions

2024 Paper 3 Question 4: Explain why a pixel should be considered a point sample rather than a small square. What implications does this have for image processing operations?

Storing Images in Memory

A 2D image array must be stored in linear (1D) memory. The mapping from 2D coordinates to 1D memory index uses strides.

Row-Major vs Column-Major Order

Row-Major Order (Most Common)

Elements in the same row are stored contiguously: $i(x, y) = x + y \cdot n_{\text{cols}}$

Column-Major Order

Elements in the same column are stored contiguously: $i(x, y) = x \cdot n_{\text{rows}} + y$

Interleaved Colour Storage

For colour images with 3 channels (RGB), interleaved row-major: $i(x, y, c) = x \cdot 3 + y \cdot 3 \cdot n_{\text{cols}} + c$

where $c \in \{0, 1, 2\}$ for the R, G, B channels.

General Stride Formula

The most general formula for any memory layout: $i(x, y, c) = i_{\text{start}} + x \cdot s_x + y \cdot s_y + c \cdot s_c$

where:

• $i_{\text{start}}$ is the starting offset
• $s_x$, $s_y$, $s_c$ are the strides for each dimension

Common Stride Configurations

Padded Images

Sometimes images are padded with extra pixels for operations that need neighbourhood access (e.g., convolution).

The stride $s_y$ is larger than the image width to account for padding.

Regions of Interest (ROI)

A region of interest is a rectangular subset of an image. An ROI borrows the parent’s data array without copying:

• $i_{\text{start}}$ = offset to ROI origin
• Strides are inherited from parent

Summary

• Row-major order stores rows contiguously; column-major stores columns contiguously
• Strides define the step size for each dimension
• Interleaved RGB alternates channels; planar separates them
• ROIs share parent memory without copying

Past Paper Questions

2023 Paper 3 Question 4: Design an ExImage class that supports ROIs. What constructor parameters are needed?

Continuous to Discrete

The physical world is continuous, but computers work with discrete values. Two processes convert between them:

Sampling

Sampling maps a continuous function to a discrete one:

• Spatial coordinates: continuous → discrete pixel positions
• A continuous image $I(x, y)$ becomes samples $I[i, j]$

Sampling an Image

$I_{\text{sampled}}[i,j] = I(x_i, y_j)$

where $(x_i, y_j)$ are the discrete sample positions on a rectangular grid.

Sampling Rate

The sampling rate (or spatial frequency) determines how densely the continuous signal is sampled:

• Higher rate: more samples, better representation of detail
• Lower rate: fewer samples, risk of aliasing

Quantisation

Quantisation maps continuous values to discrete ones:

• Intensity values: continuous → discrete levels
• Each colour channel typically quantised to 8 bits (256 levels)

Quantisation Levels

For $b$ bits per channel, there are $2^b$ discrete levels:

• 8 bits: 256 levels (0-255)
• 10 bits: 1024 levels
• 12 bits: 4096 levels

Relationship Between Sampling and Quantisation

Both contribute to image quality and file size.

Summary

• Sampling discretises spatial coordinates
• Quantisation discretises intensity values
• Higher sampling rate captures more detail
• More quantisation levels capture smoother gradients

Past Paper Questions

2023 Paper 3 Question 3: What is meant by “sampling an image”? How does it differ from quantisation?

Pixel Formats

Common pixel formats determine how colour information is stored:

Why Bit Depth Matters

Storage Requirements

Each colour channel typically uses 8 bits (values 0-255). A 5-megapixel uncompressed truecolour image requires: $5 \times 10^6 \times 3 = 15 \text{ MB}$

Why 8 Bits Suffice

Gamma encoding makes the 8-bit scale perceptually uniform. Without gamma:

• Perceptible banding in smooth gradients
• At least 12 bits per channel needed

Colour Banding

When there are insufficient bits to represent smooth colour gradients, banding artefacts appear.

Causes

• Limited bit depth
• Dark regions where gamma encoding compresses values
• Smooth gradients across large areas

Visual Illusions That Exacerbate Banding

Mach band illusion: The visual system exaggerates perceived intensity differences at edges, making band steps more visible.

Chevreul illusion: Similar edge enhancement effect.

Solutions

• Dithering: Add controlled noise to break up visible bands
• Higher bit depth: 10-bit or 12-bit encoding
• Avoid smooth gradients in design where possible

Deep Colour

For HDR content and professional workflows:

• 10-bit: 1024 levels per channel (used in HDR video)
• 12-bit: 4096 levels per channel
• 16-bit float: Per-channel floating-point precision

Summary

• Truecolour (24-bit) is standard for most applications
• 8 bits per channel suffices because gamma encoding makes it perceptually uniform
• Insufficient bit depth causes visible banding
• Dithering can reduce visible banding artefacts

The Pinhole Camera

Ray tracing is based on the pinhole camera model, where:

• Light passes through a single point (the pinhole/aperture)
• An image is formed on the image plane behind the pinhole
• Each point on the image corresponds to a unique ray from the scene

In Ray Tracing

In the computational model:

• The camera origin (eye point) corresponds to the pinhole aperture
• The screen plane (image plane) is where the image is formed
• Rays are traced from the eye through each pixel into the scene

Pinhole Camera Properties

• No depth of field: All distances are equally sharp (infinite depth of field)
• Perfect focus: No lens effects
• Point aperture: All rays diverge from a single point

Finite Aperture Camera

A real camera with a finite aperture (lens):

• Distributes rays over a lens disc
• Produces blur for out-of-focus objects (depth of field)
• Objects at the focus distance appear sharp

Summary

• The pinhole camera is the fundamental model for ray tracing
• The camera origin corresponds to the pinhole aperture
• All rays originate from a single point through the image plane
• Finite aperture cameras model depth of field effects

Past Paper Questions

2025 Paper 3 Question 3(a): Explain what a pinhole camera model is and what the camera origin in ray tracing corresponds to in the pinhole model. [2 marks]

Basic Algorithm

The ray tracing algorithm traces rays from the eye through each pixel:

select an eye point and a screen plane
FOR every pixel in the screen plane
    determine the ray from the eye through the pixel's centre
    FOR each object in the scene
        IF the object is intersected by the ray
            IF the intersection is the closest (so far) to the eye
                record intersection point and object
            END IF
        END IF
    END FOR
    calculate colour for the closest intersection point (if any)
END FOR

Time Complexity

Standard RGB Rendering

Assuming:

• $n_p$ pixels in the image
• $n_o$ objects in the scene
• $n_l$ light sources (Phong shading, no recursion)

Time complexity: $O(n_p \cdot n_o \cdot n_l)$

Breakdown:

• $O(n_p \cdot n_o)$ for finding ray-object intersections
• $O(n_l)$ per intersection to compute shading (3 channels RGB)

Spectral Rendering (2025 Paper 3 Question 3(f))

To compute physically realistic colour, we simulate the full visible spectrum instead of just RGB:

• Divide the visible spectrum (380-730 nm) into $n_\lambda$ discrete wavelength bins
• For each pixel, trace rays as usual but evaluate illumination at every wavelength

Time complexity: $O(n_p \cdot n_o \cdot n_l \cdot n_\lambda)$

The factor of $n_\lambda$ replaces the constant 3 (RGB channels).

The Outer Loop

The pixel loop is the outermost loop:

• Each pixel produces one ray (or multiple for anti-aliasing)
• The intersection test loops over all objects
• The shading calculation loops over all lights

Optimisation Techniques

• Spatial data structures: BVH, octrees reduce intersection tests from $O(n_o)$ to $O(\log n_o)$
• Early termination: Whitted-style recursion bounds
• Parallel processing: Pixels are independent, ideal for GPU

Summary

• Ray tracing traces one ray per pixel (or more for anti-aliasing)
• Time complexity is $O(n_p \cdot n_o \cdot n_l)$ for basic Phong shading
• Spectral rendering adds a factor of $n_\lambda$ for wavelength sampling
• Spatial data structures can dramatically improve performance

Past Paper Questions

2025 Paper 3 Question 3(b): Assuming a Phong shading model and no recursion, what is the time complexity of a ray tracing algorithm and why? [5 marks]

2025 Paper 3 Question 3(f): How would you compute an approximate full spectrum of colours instead of RGB values for each pixel? What is the time complexity? [4 marks]

Ray Representation

A ray is represented parametrically as: $\mathbf{P}(s) = \mathbf{O} + s\mathbf{D}, \quad s \geq 0$

where:

• $\mathbf{O}$ is the ray origin (starting point)
• $\mathbf{D}$ is the direction vector (typically normalised)
• $s$ is the parameter measuring distance along the ray

Properties

• For $s = 0$: $\mathbf{P}(0) = \mathbf{O}$ (origin)
• For $s > 0$: Points along the ray in direction $\mathbf{D}$
• Negative $s$ values are invalid (behind the origin)

Constructing Rays from Camera

For a pixel at screen coordinates $(x, y)$:

1. Compute the world-space position of the pixel on the image plane
2. Direction: $\mathbf{D} = \frac{\mathbf{P}_{\text{pixel}} - \mathbf{O}_{\text{camera}}}{|\mathbf{P}_{\text{pixel}} - \mathbf{O}_{\text{camera}}|}$

Why Parametric?

The parametric form is ideal for intersection testing:

• Substitute $\mathbf{P}(s)$ into the surface equation
• Solve for $s$ (the distance to intersection)
• IF $s \geq 0$, the intersection is in front of the ray origin

Summary

• A ray is defined by origin $\mathbf{O}$ and direction $\mathbf{D}$
• The parameter $s$ gives distance along the ray
• Parametric form enables algebraic intersection calculations

Intersection Testing

Finding where a ray hits geometric objects is fundamental to ray tracing.

Ray-Sphere Intersection

Given:

• Ray: $\mathbf{P}(s) = \mathbf{O} + s\mathbf{D}$
• Sphere: $(\mathbf{P} - \mathbf{C}) \cdot (\mathbf{P} - \mathbf{C}) = r^2$

Substituting the ray equation: $(\mathbf{O} + s\mathbf{D} - \mathbf{C}) \cdot (\mathbf{O} + s\mathbf{D} - \mathbf{C}) = r^2$

This is a quadratic in $s$: $as^2 + bs + c = 0$

where:

• $a = \mathbf{D} \cdot \mathbf{D}$
• $b = 2\mathbf{D} \cdot (\mathbf{O} - \mathbf{C})$
• $c = (\mathbf{O} - \mathbf{C}) \cdot (\mathbf{O} - \mathbf{C}) - r^2$

Discriminant

The discriminant $d = b^2 - 4ac$ determines intersection type:

• $d < 0$: No intersection (miss)
• $d = 0$: Tangent (one intersection)
• $d > 0$: Two intersections (enter and exit)

Solutions

$s_1 = \frac{-b + \sqrt{d}}{2a}, \quad s_2 = \frac{-b - \sqrt{d}}{2a}$

The closest valid intersection is the smallest positive $s$.

Ray-Plane Intersection

Given:

• Ray: $\mathbf{P}(s) = \mathbf{O} + s\mathbf{D}$
• Plane: $\mathbf{P} \cdot \mathbf{N} + d = 0$

where $\mathbf{N}$ is the plane normal and $d$ is the distance offset.

Substituting: $s = \frac{-d - \mathbf{N} \cdot \mathbf{O}}{\mathbf{N} \cdot \mathbf{D}}$

Valid if:

• $s \geq 0$ (intersection in front of origin)
• $\mathbf{N} \cdot \mathbf{D} \neq 0$ (ray not parallel to plane)

Ray-Polygon Intersection

For a polygon:

1. Intersect the ray with the plane containing the polygon
2. Check if the intersection point lies inside the polygon (2D geometry test)

For a disc: Check if distance from centre is less than radius.

Ray-Cone Intersection (2022 Paper 3 Question 3)

For a cone with apex at origin, base radius $r$, height $h$, axis along $y$:

Implicit equation: $x^2 + z^2 - \left(\frac{r}{h}\right)^2 y^2 = 0$

Intersection Method

1. Base: Intersect ray with plane $y = h$; accept if $x^2 + z^2 \leq r^2$
2. Side: Substitute ray into implicit equation, solve quadratic in $s$

Normal Calculation

For a point $(x, y, z)$ on the cone side, the normal is proportional to: $\mathbf{N} \propto \left(2x, -2\left(\frac{r}{h}\right)^2 y, 2z\right)$

The normal is the gradient of the implicit function $f(x, y, z) = 0$.

Transformed Objects

For an object transformed by matrix $\mathbf{M}$:

1. Transform the ray by $\mathbf{M}^{-1}$
2. Intersect with the canonical (untransformed) object
3. Transform the intersection point back by $\mathbf{M}$
4. Transform the normal by $(\mathbf{M}^{-1})^\top$

Summary

• Ray-sphere intersection reduces to a quadratic equation
• Ray-plane intersection is a simple division
• Polygon intersections require inside/outside tests
• Cone normals are computed from the implicit gradient
• Transformed objects require transforming the ray by the inverse matrix

Past Paper Questions

2022 Paper 3 Question 3: Derive the ray-cone intersection. Find the normal at an intersection point.

What are Shadow Rays?

After finding an intersection, shadow rays determine whether the point is illuminated by each light source.

$\mathbf{P}_{\text{shadow}} = \mathbf{P}_{\text{hit}} + \epsilon \mathbf{L}_{\text{to\_light}}$

where $\epsilon$ is a small offset to avoid self-intersection with the surface.

Shadow Ray Algorithm

FOR each light source
    cast shadow ray from hit point towards light
    IF shadow ray intersects any object before reaching light
        point is in shadow for this light
    ELSE
        point is illuminated by this light
END FOR

Hard Shadows

A point is either:

• Fully illuminated: Shadow ray reaches light unblocked
• Fully in shadow: Shadow ray blocked by an object

This produces sharp shadow boundaries.

Soft Shadows

Area light sources create penumbrae (partial shadows):

• Multiple shadow rays distributed over the light surface
• Average the visibility results
• Partially blocked points receive partial illumination

Colour in Shadow

If a point is in shadow for a light source:

• The diffuse and specular components for that light are zero
• Only ambient illumination contributes

For multiple lights, shadows are computed per-light:

• A point may be illuminated by some lights but shadowed from others

Self-Intersection Problem

A shadow ray starting exactly on the surface may hit the same surface due to floating-point precision:

• Solution: Offset the ray origin by a small $\epsilon$ along the surface normal

Summary

• Shadow rays determine if intersection points are illuminated
• Hard shadows use one ray per light (sharp edges)
• Soft shadows use multiple rays over area lights (penumbra)
• Points in shadow only receive ambient illumination

Past Paper Questions

2025 Paper 3 Question 3(c): Explain shadow rays. What is the colour of a pixel if it is in shadow? [3 marks]

Recursive Ray Tracing

At an intersection point, we can spawn additional rays:

• Reflection rays for mirrors
• Refraction rays for transparent materials

Reflection

For mirror-like surfaces, a reflected ray is spawned:

$\mathbf{R} = \mathbf{D} - 2(\mathbf{D} \cdot \mathbf{N})\mathbf{N}$

where $\mathbf{D}$ is the incoming ray direction and $\mathbf{N}$ is the surface normal.

Reflection Direction Derivation

The reflection is the incident direction mirrored about the normal:

• Component parallel to $\mathbf{N}$: reversed
• Component perpendicular to $\mathbf{N}$: unchanged

Refraction (Transparency)

Transparent objects bend light according to Snell’s law:

$n_1 \sin\theta_1 = n_2 \sin\theta_2$

where $n_1$ and $n_2$ are refractive indices.

Refracted Direction

$\mathbf{T} = \frac{n_1}{n_2}\mathbf{D} + \left(\frac{n_1}{n_2}\cos\theta_1 - \cos\theta_2\right)\mathbf{N}$

Total Internal Reflection

When light travels from a denser to less dense medium:

• If incident angle exceeds critical angle: No refraction, only reflection
• Critical angle: $\theta_c = \arcsin(n_2/n_1)$

Fresnel Effect

At glancing angles, more light is reflected; at normal incidence, more is refracted:

• Approximate with Schlick’s approximation
• Important for realistic glass and water

Combining Effects

The final colour combines:

• Local shading (Phong)
• Reflected colour (weighted by reflectivity)
• Refracted colour (weighted by transparency)

$I = I_{\text{local}} + k_r I_{\text{reflected}} + k_t I_{\text{refracted}}$

Summary

• Reflection rays use the mirror direction formula
• Refraction follows Snell’s law
• Total internal reflection occurs above the critical angle
• Combined colour blends local, reflected, and refracted contributions

The Aliasing Problem

Shooting a single ray through each pixel’s centre causes aliasing artefacts:

• Jagged edges (stair-step patterns)
• Small or thin objects missed entirely
• Moire patterns in fine detail

Super-Sampling Methods

Regular Grid Sampling

Divide each pixel into an $N \times N$ grid and shoot rays through each sub-pixel centre.

• Problem: Can still produce noticeable patterns
• Average all results

Random Sampling

Shoot $N$ rays at random positions within each pixel.

• Replaces structured aliasing with noise
• The eye tolerates noise better than patterns

Jittered (Stratified) Sampling

Divide pixel into $N$ sub-regions (strata) and shoot one random ray per region.

• Combines benefits of regular and random
• Good approximation to Poisson disc
• Each region is guaranteed one sample

Poisson Disc Sampling

Random samples with a minimum distance constraint.

• Best quality
• Hardest to implement correctly
• Requires Poisson distribution generation

Adaptive Super-Sampling

Shoot a few rays per pixel. If the variance of results is high, shoot more rays.

Benefits:

• Concentrates effort where needed (edges, detail)
• Saves computation in smooth regions

Distributed Ray Tracing

Extend super-sampling to multiple dimensions simultaneously:

Each effect requires averaging multiple samples per pixel.

Summary

• Single ray per pixel causes aliasing
• Super-sampling replaces aliasing with less objectionable noise
• Jittered sampling is a good balance of quality and simplicity
• Distributed ray tracing adds realistic effects beyond anti-aliasing

The Phong Model

The complete Phong shading model combines three reflection components:

$I = I_a k_a + \sum_{\text{lights}} I_l k_d \max(0, \mathbf{N} \cdot \mathbf{L}) + \sum_{\text{lights}} I_l k_s \max(0, \mathbf{R} \cdot \mathbf{V})^n$

Components

Symbols

Reflection Direction

$\mathbf{R} = 2(\mathbf{L} \cdot \mathbf{N})\mathbf{N} - \mathbf{L}$

Or equivalently: $\mathbf{R} = 2\cos\theta \mathbf{N} - \mathbf{L}$

Per-Channel Computation

The shading equation is computed for each RGB channel separately:

• Different $k_d$ values for each channel give surface colour
• Specular highlights often use light colour (white for plastics)

Clamping

• $\max(0, \cdot)$ prevents negative contributions (light behind surface)
• Without clamping, surfaces can become incorrectly dark

Summary

• Phong shading = ambient + diffuse + specular
• Ambient approximates global illumination
• Diffuse is view-independent (Lambertian)
• Specular is view-dependent (highlights)
• The $\max(0, \cdot)$ prevents negative values from light behind surfaces

Diffuse Surfaces

Diffuse surfaces scatter light equally in all directions. Matte surfaces like paper, chalk, and unpolished wood.

Lambert’s Cosine Law

The reflected intensity depends only on the angle between the surface normal and light direction:

$I_{\text{diffuse}} = I_l k_d \cos\theta = I_l k_d (\mathbf{N} \cdot \mathbf{L})$

where:

• $I_l$ is the light source intensity
• $k_d$ is the diffuse reflection coefficient (surface colour)
• $\mathbf{N}$ is the surface normal (unit vector)
• $\mathbf{L}$ is the direction to the light (unit vector)
• $\theta$ is the angle between $\mathbf{N}$ and $\mathbf{L}$

Physical Interpretation

$\mathbf{N} \cdot \mathbf{L} = \cos\theta$ represents:

• Projected area: A surface receives less light energy when tilted
• At glancing angles ($\theta \approx 90°$), the same energy spreads over a larger area
• At perpendicular angles ($\theta = 0°$), maximum energy per unit area

View Independence

Diffuse reflection is view-independent:

• The surface appears equally bright from any viewing angle
• Light scatters uniformly in all directions
• Only depends on $\mathbf{N}$ and $\mathbf{L}$, not on $\mathbf{V}$

When Diffuse is Zero

Diffuse is zero when:

• $\mathbf{N} \cdot \mathbf{L} \leq 0$: Light is behind or tangent to the surface
• $k_d = 0$: Surface has zero diffuse reflectance (pure mirror)

One-Sided vs Two-Sided Surfaces

One-sided surfaces: Only illuminate the side in direction of $\mathbf{N}$. If $\cos\theta < 0$, render black.

Two-sided surfaces: If $\cos\theta < 0$, use $|\cos\theta|$ (or flip $\mathbf{N}$) to illuminate the back.

Summary

• Diffuse reflection follows Lambert’s cosine law
• Intensity proportional to $\cos\theta$ = $\mathbf{N} \cdot \mathbf{L}$
• View-independent: same brightness from any angle
• Zero when light is behind the surface

Past Paper Questions

2025 Paper 3 Question 3(d): In the Phong shading model, explain when the diffuse component becomes zero. [Part of 4 marks]

Specular Highlights

Specular reflection models shiny surfaces that reflect light in a preferred direction, creating bright highlights.

Phong Specular Term

$I_{\text{specular}} = I_l k_s \cos^n\alpha = I_l k_s (\mathbf{R} \cdot \mathbf{V})^n$

where:

• $k_s$ is the specular reflection coefficient
• $\mathbf{R}$ is the perfect reflection direction of the light
• $\mathbf{V}$ is the direction to the viewer
• $\alpha$ is the angle between $\mathbf{R}$ and $\mathbf{V}$
• $n$ is the Phong exponent (shininess)

Reflection Direction

$\mathbf{R} = 2(\mathbf{L} \cdot \mathbf{N})\mathbf{N} - \mathbf{L}$

Effect of Shininess $n$

Higher $n$ concentrates the highlight around the mirror direction.

When Specular is Zero

Specular reflection is zero when:

• $\mathbf{R} \cdot \mathbf{V} \leq 0$: Viewer is on wrong side of reflection lobe
• $\mathbf{N} \cdot \mathbf{L} \leq 0$: Light behind surface (no illumination at all)
• $k_s = 0$: Surface has zero specular reflectance

View Dependence

Specular reflection is view-dependent:

• Highlight moves as the camera moves
• Must be recomputed every frame for animations
• Cannot be cached if camera changes

Physical Approximation

The Phong model is an approximation:

• Does not conserve energy
• Not physically based (BRDF is ad-hoc)
• But computationally efficient and produces plausible results

Summary

• Specular creates shiny highlights
• Intensity depends on angle between reflection and viewer
• Shininess $n$ controls highlight size
• View-dependent: must recompute if camera moves

Past Paper Questions

2025 Paper 3 Question 3(e): How does the specular highlight differ from diffuse reflection in the Phong shading model? [2 marks]

2025 Paper 3 Question 3(d): Explain when the specular component becomes zero. [Part of 4 marks]

Caching for Animation

When rendering animations, we can cache certain Phong shading components depending on what is moving in the scene.

Component Cacheability

Ambient Term

Always cacheable:

• Constant per surface (independent of camera, lights, objects)
• Compute once and reuse across all frames

Diffuse Term

Cacheable if:

• Lights are static
• Objects are static

Cannot cache if:

• Lights move (changes $\mathbf{L}$)
• Objects move/rotate (changes $\mathbf{N}$)

View-independent: unaffected by camera motion.

Specular Term

Never cacheable if camera moves:

• Depends on $\mathbf{V}$ (viewer direction)
• Must recompute every frame

Could cache if:

• Camera is static
• Lights and objects are static
• (Rare: only useful for walk-through with fixed viewpoint)

Summary

• Ambient: always cacheable
• Diffuse: cacheable if lights and objects are static
• Specular: never cacheable if camera moves (depends on $\mathbf{V}$)

Past Paper Questions

2023 Paper 3 Question 3(a)(iv): In the Phong shading model, which terms can be cached in an animation? Explain why.

Microfacet Model

Surface reflection can be understood through the microfacet model: surfaces are composed of tiny mirrors (facets) with varying orientations.

Facet Distributions

Diffuse Surfaces

Facets randomly oriented in all directions:

• Light hits facets at all angles
• Light scatters uniformly
• No preferred reflection direction

Result: View-independent reflection (Lambertian).

Imperfect Specular Surfaces

Facets mostly aligned with the macro-surface normal, but with some angular spread:

• Most light reflects near the mirror direction
• Some spread creates a broad highlight
• Higher alignment = higher shininess $n$

Result: Phong-like specular with finite highlight size.

Perfect Specular Surfaces

All facets perfectly co-planar with the surface:

• All light reflects in exactly one direction
• No diffuse component
• Mirror-like reflection

Result: $n \to \infty$, perfect mirror.

Physical Insight

The microfacet model explains why:

• Metals have coloured specular ($k_s$ takes metal colour)
• Plastics have white specular ($k_s$ is light colour)
• Rough surfaces have broad, dim highlights
• Polished surfaces have sharp, bright highlights

Summary

• Microfacets model surfaces as collections of tiny mirrors
• Facet orientation distribution determines reflection properties
• Random facets → diffuse; aligned facets → specular
• Phong exponent $n$ models the spread of facet orientations

Why Transformations?

Transformations allow us to:

• Place predefined objects at arbitrary locations, orientations, and sizes
• Build complex scenes from simple primitives
• Animate objects over time

Basic Transformations

Scale (about origin, factor $m$)

$x' = mx, \quad y' = my$

Rotate (about origin, angle $\theta$)

$x' = x\cos\theta - y\sin\theta$ $y' = x\sin\theta + y\cos\theta$

Translate (by vector $(x_o, y_o)$)

$x' = x + x_o, \quad y' = y + y_o$

Shear (parallel to x-axis, factor $a$)

$x' = x + ay, \quad y' = y$

Matrix Representation

2×2 matrices work for scale, rotate, and shear, but not translation.

Scale: $\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} m & 0 \\ 0 & m \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

Rotate: $\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

Identity: $\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$

The Translation Problem

Translation cannot be represented as 2×2 matrix multiplication: $\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} x \\ y \end{bmatrix} + \begin{bmatrix} x_o \\ y_o \end{bmatrix}$

This breaks uniformity—other transforms are multiplicative.

Summary

• Scale, rotate, and shear can be expressed as matrix multiplication
• Translation requires an additive term (not multiplicative)
• This motivates homogeneous coordinates

The Problem

Translation cannot be represented as a 2×2 matrix multiplication on 2D vectors. We need an additive term.

The Solution

Add a third coordinate $w$:

$\text{2D point } (x, y) \equiv \text{Homogeneous } (x, y, 1)$

More generally: $(x, y, w) \equiv \left(\frac{x}{w}, \frac{y}{w}\right)$

Properties

An infinite number of homogeneous coordinates map to each 2D point:

• $(1, 2, 1) \equiv (2, 4, 2) \equiv (3, 6, 3)$

When $w = 0$: Point at infinity (direction vector).

Transformation Matrices

Scale (factor $m$)

$\begin{bmatrix} x' \\ y' \\ w' \end{bmatrix} = \begin{bmatrix} m & 0 & 0 \\ 0 & m & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ w \end{bmatrix}$

Rotate (angle $\theta$)

$\begin{bmatrix} x' \\ y' \\ w' \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ w \end{bmatrix}$

Translate (by $(x_o, y_o)$)

$\begin{bmatrix} x' \\ y' \\ w' \end{bmatrix} = \begin{bmatrix} 1 & 0 & x_o \\ 0 & 1 & y_o \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ w \end{bmatrix}$

Shear (factor $a$)

$\begin{bmatrix} x' \\ y' \\ w' \end{bmatrix} = \begin{bmatrix} 1 & a & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ w \end{bmatrix}$

3D Homogeneous Coordinates

A 3D point $(x, y, z)$ is represented as $(x, y, z, w)$: $(x, y, z, w) \equiv \left(\frac{x}{w}, \frac{y}{w}, \frac{z}{w}\right)$

Points vs Vectors

Vectors represent directions and should not be translated.

Summary

• Homogeneous coordinates add $w$ to represent translation as matrix multiplication
• Points: $w = 1$; Vectors: $w = 0$
• All affine transforms are now uniform matrix multiplications

Identity

$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Scale (uniform, factor $m$)

$\begin{bmatrix} m & 0 & 0 & 0 \\ 0 & m & 0 & 0 \\ 0 & 0 & m & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

For non-uniform scaling, use different values on the diagonal.

Translate (by $(t_x, t_y, t_z)$)

$\begin{bmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Rotation Matrices

Rotate about x-axis

$\mathbf{R}_x(\theta) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos\theta & -\sin\theta & 0 \\ 0 & \sin\theta & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Rotate about y-axis

$\mathbf{R}_y(\theta) = \begin{bmatrix} \cos\theta & 0 & \sin\theta & 0 \\ 0 & 1 & 0 & 0 \\ -\sin\theta & 0 & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Rotate about z-axis

$\mathbf{R}_z(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0 & 0 \\ \sin\theta & \cos\theta & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Mnemonic

The axis being rotated about has 1 on the diagonal and 0 in that row/column. The other entries form a 2D rotation matrix.

Non-Commutativity

3D rotations are non-commutative:

• $\mathbf{R}_x(90°) \cdot \mathbf{R}_z(90°) \neq \mathbf{R}_z(90°) \cdot \mathbf{R}_x(90°)$

Summary

• Translation uses the fourth column
• Rotation matrices are orthogonal (determinant = 1)
• 3D rotations are non-commutative

Concatenation

Multiple transformations combine by multiplying their matrices:

$\mathbf{M}_{\text{combined}} = \mathbf{M}_n \cdot \mathbf{M}_{n-1} \cdots \mathbf{M}_2 \cdot \mathbf{M}_1$

Transformations are applied right-to-left.

Standard Order: SRT

Scale → Rotate → Translate

Written as: $\mathbf{M} = \mathbf{T} \cdot \mathbf{R} \cdot \mathbf{S}$

The rightmost matrix ($\mathbf{S}$) is applied first.

Example: Shear then Scale

$\begin{bmatrix} x'' \\ y'' \\ w'' \end{bmatrix} = \begin{bmatrix} m & 0 & 0 \\ 0 & m & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & a & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ w \end{bmatrix} = \begin{bmatrix} m & ma & 0 \\ 0 & m & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ w \end{bmatrix}$

Non-Commutativity

Transformations generally do not commute.

Example: Scale by 2 along x, then rotate 45° $\neq$ Rotate 45°, then scale by 2 along x.

Transformations About Arbitrary Points

To transform about point $(x_o, y_o)$:

1. Translate $(x_o, y_o)$ to origin
2. Apply transformation
3. Translate back to $(x_o, y_o)$

Scale about $(x_o, y_o)$: $\mathbf{M} = \mathbf{T}(x_o, y_o) \cdot \mathbf{S}(m) \cdot \mathbf{T}(-x_o, -y_o)$

Efficiency

Concatenate matrices once, then apply to all vertices:

• One matrix multiplication per concatenated transform
• More efficient than applying each matrix sequentially

Summary

• Matrices multiply right-to-left
• Standard order: Scale, Rotate, Translate (SRT)
• Transformations are non-commutative
• Arbitrary pivots require translate-transform-translate

The Problem

Normal vectors transform differently from positions!

For transformation matrix $\mathbf{M}$ applied to positions, normals transform using: $\mathbf{N}' = (\mathbf{M}^{-1})^\top \mathbf{N}$

Derivation

The normal $\mathbf{N}$ is perpendicular to the tangent vector $\mathbf{T}$: $\mathbf{N} \cdot \mathbf{T} = 0$

After transformation, $\mathbf{T}' = \mathbf{M}\mathbf{T}$. We need $\mathbf{N}' \cdot \mathbf{T}' = 0$: $\mathbf{N}' \cdot (\mathbf{M}\mathbf{T}) = ((\mathbf{M}^{-1})^\top \mathbf{N}) \cdot (\mathbf{M}\mathbf{T}) = \mathbf{N}^\top \mathbf{M}^{-1} \mathbf{M}\mathbf{T} = \mathbf{N} \cdot \mathbf{T} = 0$

Simplifications

Pure Rotation

If $\mathbf{M}$ is orthogonal (rotation only): $\mathbf{M}^{-1} = \mathbf{M}^\top$

Therefore: $\mathbf{N}' = \mathbf{M}\mathbf{N}$

Normals use the same rotation matrix as positions.

Uniform Scale + Rotation

The scale factor cancels (normals are renormalised anyway): $\mathbf{N}' = \mathbf{R}\mathbf{N}$

Non-Uniform Scale or Shear

Must compute and apply $(\mathbf{M}^{-1})^\top$: $\mathbf{N}' = (\mathbf{M}^{-1})^\top \mathbf{N}$

Translation

Normals are unchanged by pure translations (direction vectors).

Why It Matters

Non-uniform scaling distorts normals:

• A sphere scaled to an ellipsoid needs transformed normals
• Using $\mathbf{M}$ directly would make normals point in wrong direction

Summary

• Normals transform with $(\mathbf{M}^{-1})^\top$, not $\mathbf{M}$
• Pure rotation: normals use same matrix as positions
• Uniform scale: scale cancels after renormalisation
• Non-uniform scale/shear: must compute inverse transpose
• Translation: no effect on direction vectors

Past Paper Questions

2025 Paper 3 Question 4(a)(ii): How would you obtain the transformation for the normal using scaling, rotation, and translation? Simplify if possible. [2 marks]

Problem (2025 Paper 3 Question 4(a)(i))

Transform a cylinder (radius 1, height 2, centred at origin, aligned along y-axis) to have:

• Radius 2
• Ends at $(1, 2, 3)$ and $(2, 4, 5)$

Solution

Order: Scale → Rotate → Translate

Compute Target Properties

• Axis vector: $\mathbf{v} = (2-1, 4-2, 5-3) = (1, 2, 2)$
• Length: $|\mathbf{v}| = \sqrt{1^2 + 2^2 + 2^2} = 3$
• Midpoint: $\mathbf{m} = \left(\frac{1+2}{2}, \frac{2+4}{2}, \frac{3+5}{2}\right) = (1.5, 3, 4)$

1. Scale

Original: radius 1, height 2. Target: radius 2, height 3.

• $s_x = 2$, $s_z = 2$ (double radius)
• $s_y = 1.5$ (height 3 from 2: $3/2 = 1.5$)

$\mathbf{S} = \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 1.5 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

2. Rotate

Align y-axis $(0,1,0)$ with target axis $(1, 2, 2)$.

Step A: Zero z-component. Rotate about x-axis by $\theta = 45°$.

Step B: Zero x-component. Rotate about z-axis by $\phi = \arcsin(1/3) \approx 19.47°$.

The rotation aligning the axis: $\mathbf{R}^{-1} = \mathbf{R}_x(-45°) \cdot \mathbf{R}_z(-\arcsin(1/3))$

3. Translate

Move origin to midpoint $(1.5, 3, 4)$: $\mathbf{T} = \begin{bmatrix} 1 & 0 & 0 & 1.5 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Overall Model Matrix

$\mathbf{M} = \mathbf{T} \cdot \mathbf{R}_x(-45°) \cdot \mathbf{R}_z(-\arcsin(1/3)) \cdot \mathbf{S}$

Summary

• Compute geometric properties first (axis, length, midpoint)
• Apply SRT order: Scale, Rotate, Translate
• Rotate by inverse of the rotation that aligns axis to canonical

Past Paper Questions

2025 Paper 3 Question 4(a)(i): Transform a cylinder to have specified radius and endpoints. [6 marks]

Definition

The view frustum is the region of space visible through the camera:

• A truncated pyramid (for perspective) or box (for orthographic)
• Contains everything that will be rendered

Six Clipping Planes

Frustum Culling

Objects entirely outside the frustum are not rendered:

• Test each object’s bounding volume against frustum planes
• If completely outside, skip rendering
• Important optimisation for large scenes

Field of View

The field of view (FOV) determines how much of the scene is visible:

• Vertical FOV: Angle from top to bottom of frustum
• Horizontal FOV: Derived from aspect ratio

Higher FOV: More visible (wide-angle). Lower FOV: Zoomed in (telephoto).

Aspect Ratio

The ratio of viewport width to height: $\text{aspect} = \frac{\text{width}}{\text{height}}$

Determines horizontal FOV from vertical FOV.

Summary

• The frustum defines the visible region of 3D space
• Bounded by six clipping planes
• Frustum culling removes non-visible objects
• FOV and aspect ratio define the frustum shape

How Perspective Works

Objects farther away appear smaller. Parallel lines converge to a vanishing point.

Geometry

For a camera at origin looking down $-z$, with image plane at distance $d$:

$x' = \frac{x \cdot d}{z}, \quad y' = \frac{y \cdot d}{z}$

Matrix Form

Perspective can be expressed with a matrix:

$\begin{bmatrix} x \cdot d \\ y \cdot d \\ z \cdot d \\ z \end{bmatrix} = \begin{bmatrix} d & 0 & 0 & 0 \\ 0 & d & 0 & 0 \\ 0 & 0 & d & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$

After dividing by $w = z$: correct projected coordinates.

Why Preserve $1/z$?

The $w$ component stores $z$, enabling:

• Z-buffer interpolation (interpolate $1/z$, not $z$)
• Perspective-correct texture mapping

Properties

• Realistic appearance
• Distant objects smaller
• Parallel lines converge
• Used in games, film, photography

Summary

• Perspective divides by $z$: $x' = xd/z$, $y' = yd/z$
• Preserves $1/z$ for correct depth interpolation
• Matches how cameras and eyes work

Parallel Projectors

All projectors (projection lines) are parallel to each other:

• No vanishing point
• Parallel lines remain parallel
• No perspective distortion

Mathematical Form

Simply discard the $z$ coordinate:

$(x, y, z) \rightarrow (x, y)$

Matrix Form

Orthographic projection maps a box to the NDC cube $[-1, 1]^3$:

$\mathbf{P}_{\text{ortho}} = \begin{bmatrix} \frac{2}{r-l} & 0 & 0 & -\frac{r+l}{r-l} \\ 0 & \frac{2}{t-b} & 0 & -\frac{t+b}{t-b} \\ 0 & 0 & \frac{2}{f-n} & -\frac{f+n}{f-n} \\ 0 & 0 & 0 & 1 \end{bmatrix}$

where $l, r, b, t, n, f$ are left, right, bottom, top, near, far planes.

Properties

• Preserves measurements (no perspective distortion)
• Parallel lines stay parallel
• Used in CAD, architecture, technical drawings
• Looks “flat” and unrealistic for natural scenes

When to Use

• Technical drawings where accuracy matters
• 2D games and UI
• Isometric view games
• Architectural plans

Summary

• Orthographic discards $z$: parallel projection
• No perspective: distant objects same size
• Preserves parallel lines and measurements
• Used for technical applications

Purpose

The view matrix transforms world coordinates to camera coordinates:

• Camera at origin
• Looking down $-z$ axis
• $+y$ up, $+x$ right

Standard Camera Assumptions

For uniform projection mathematics:

• Camera at origin $(0, 0, 0)$
• Screen centre at $(0, 0, -d)$
• Screen parallel to $xy$-plane

Look-At Construction

Given:

• Camera position $\mathbf{c}$
• Look-at point $\mathbf{l}$ (where camera points)
• Up direction $\mathbf{u}$ (which way is “up”)

Build Orthonormal Basis

1. Forward: $\hat{\mathbf{v}} = \frac{\mathbf{c} - \mathbf{l}}{|\mathbf{c} - \mathbf{l}|}$

2. Right: $\hat{\mathbf{r}} = \frac{\mathbf{u} \times \hat{\mathbf{v}}}{|\mathbf{u} \times \hat{\mathbf{v}}|}$

3. True up: $\hat{\mathbf{u}} = \hat{\mathbf{v}} \times \hat{\mathbf{r}}$

View Matrix

$\mathbf{V} = \begin{bmatrix} \hat{r}_x & \hat{r}_y & \hat{r}_z & -\mathbf{c} \cdot \hat{\mathbf{r}} \\ \hat{u}_x & \hat{u}_y & \hat{u}_z & -\mathbf{c} \cdot \hat{\mathbf{u}} \\ \hat{v}_x & \hat{v}_y & \hat{v}_z & -\mathbf{c} \cdot \hat{\mathbf{v}} \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Coordinate System Conventions

The projection matrix flips the handedness.

Summary

• View matrix places camera at origin, looking down $-z$
• Constructed from position, look-at point, and up vector
• Build orthonormal basis using cross products
• Translation to origin + rotation to align axes

Past Paper Questions

2024 Paper 3 Question 4(b): Derive the look-at view matrix for a camera at position $\mathbf{c}$, looking at point $\mathbf{l}$, with up vector $\mathbf{u}$.

Complete Transformation Pipeline

Object coords → World coords → View coords → Clip coords → NDC → Screen coords

The MVP Matrix

$\begin{bmatrix} x_s \\ y_s \\ z_s \\ w_s \end{bmatrix} = \mathbf{P} \cdot \mathbf{V} \cdot \mathbf{M} \begin{bmatrix} x \\ y \\ z \\ w \end{bmatrix}$

Model Matrix (M)

Object coordinates → World coordinates:

• Places object in the scene
• Applies scale, rotate, translate

View Matrix (V)

World coordinates → Camera coordinates:

• Positions camera at origin
• Orients camera to look down $-z$

Projection Matrix (P)

Camera coordinates → Clip coordinates:

• Projects 3D to 2D (perspective or orthographic)
• Maps frustum to NDC cube $[-1, 1]^3$

After Projection

1. Perspective division: Divide by $w$
2. Viewport transform: Map NDC to screen pixels
3. Rasterisation: Convert to fragments

Summary

• M: Places object in world
• V: Places camera at origin
• P: Projects to 2D and maps to NDC
• Combined: $\mathbf{P} \cdot \mathbf{V} \cdot \mathbf{M}$ applied to each vertex

Past Paper Questions

2024 Paper 3 Question 4: Explain the purpose of the model, view, and projection matrices. What coordinate system does each transform between?

Definition

A scene graph is a tree structure representing hierarchical relationships between objects in a scene.

Transformation Inheritance

Child objects inherit transformations from parent nodes:

• Each node has its own local transformation
• World transformation = product of all parent transformations

Traversal Pseudocode

traverse(node, T_parent):
    M = T_parent * node.T * node.E
    node.draw(M)
    for child in node.children:
        traverse(child, T_parent * node.T)

where:

• node.T: Transformation relative to parent
• node.E: Optional additional transformation (e.g., animation)

Example: Robot Arm

Body → Shoulder → UpperArm → Elbow → LowerArm → Hand

• Body: Positioned in world space
• Shoulder: Rotates relative to body
• Elbow: Rotates relative to upper arm
• Hand: Rotates relative to lower arm

Each transformation is relative to its parent.

Benefits

• Natural representation of articulated objects
• Easy animation (just modify local transforms)
• Efficient rendering (traverse tree, accumulate transforms)
• Supports instancing (same object under different parent nodes)

Summary

• Scene graphs organise objects hierarchically
• Children inherit parent transformations
• Traversal accumulates transformations down the tree
• Natural for articulated objects and animations

Past Paper Questions

2021 Paper 3 Question 4: Explain how scene graphs work. How are transformations accumulated?

Why Rasterisation?

Ray tracing produces high-quality images but is computationally expensive. Real-time applications need faster rendering.

Rasterisation is the dominant technique for real-time rendering:

• Model surfaces as meshes of polygons (usually triangles)
• Project vertices to screen coordinates
• Fill visible polygons

The Algorithm

Set model, view and projection (MVP) transformations
FOR every triangle in the scene
    transform its vertices using MVP matrices
    IF the triangle is within the view frustum
        clip the triangle to the screen border
        FOR each fragment (pixel candidate) in the triangle
            interpolate fragment position and attributes between vertices
            compute fragment colour
            IF the fragment is closer to the camera than any pixel drawn so far
                update the screen pixel with the fragment colour
            END IF
        END FOR
    END IF
END FOR

Fragments

A fragment is a candidate pixel within a triangle:

• Has a screen position, depth, and interpolated attributes
• May or may not become a final pixel (depending on depth test)

Complexity

Time complexity: $O(\text{triangles} + \text{fragments})$

For $n$ triangles and $p$ pixels:

• Transform: $O(n)$ for vertices
• Rasterise: $O(p \cdot \text{triangles per pixel})$

Generally: $O(n + p)$ with good clipping and culling.

Summary

• Rasterisation projects triangles and fills pixels
• Faster than ray tracing for real-time
• Fragments are pixel candidates with interpolated attributes
• Complexity: $O(\text{triangles} + \text{fragments})$

Planar Polygons

• A triangle (3 vertices) is always planar
• Polygons with >3 vertices may not be planar

Triangulation

Most GPUs are optimised for triangles. Polygons with more vertices are split into triangles.

Why triangles?

• Always planar
• Convex (easy to fill)
• Simple interpolation
• Hardware acceleration

Triangle Mesh Indexing

For efficient storage:

• Vertex array: Unique vertex positions
• Index array: Which vertices form each triangle

Example: A cube has 8 vertices but 12 triangles (36 indices with sharing, or 24 vertices without).

Summary

• Triangles are always planar; other polygons may not be
• GPUs are optimised for triangles
• Indexed meshes reuse vertices for efficiency

Definition

Barycentric coordinates $(\alpha, \beta, \gamma)$ express a point inside a triangle as a weighted combination of the vertices:

$\mathbf{P} = \alpha\mathbf{A} + \beta\mathbf{B} + \gamma\mathbf{C}$

where $\alpha + \beta + \gamma = 1$ and $\alpha, \beta, \gamma \geq 0$ for points inside the triangle.

Computing Barycentric Coordinates

Given triangle vertices $(x_A, y_A)$, $(x_B, y_B)$, $(x_C, y_C)$ and point $(x, y)$:

Define implicit line equation: $f_{AB}(x, y) = (y_A - y_B)x + (x_B - x_A)y + x_A y_B - x_B y_A$

Then: $\alpha = \frac{f_{BC}(x, y)}{f_{BC}(x_A, y_A)}$ $\beta = \frac{f_{AC}(x, y)}{f_{AC}(x_B, y_B)}$ $\gamma = 1 - \alpha - \beta$

Interpolating Attributes

Any attribute $Q$ (colour, normal, texture coordinates) can be interpolated:

$Q(x, y) = \alpha Q_A + \beta Q_B + \gamma Q_C$

Used for:

• Colour interpolation (Gouraud shading)
• Normal interpolation (Phong shading)
• Texture coordinate interpolation

Point-in-Triangle Test

A point is inside the triangle if and only if: $\alpha > 0 \text{ and } \beta > 0 \text{ and } \gamma > 0$

Summary

• Barycentric coordinates express points as vertex weights
• Sum to 1 inside triangle; all positive for interior points
• Enable smooth attribute interpolation across triangle

Past Paper Questions

2025 Paper 3 Question 4(b)(iv): What are barycentric coordinates, and where are they needed in the OpenGL rendering pipeline? [3 marks]

The Problem

Linear interpolation in screen space is only correct for parallel (orthographic) projection.

Under perspective projection, 3D properties are projected non-linearly onto 2D screen. Simply interpolating in screen space causes attributes like texture coordinates to distort.

The Solution

Interpolate quantities that are linear in screen space:

• Perspective-divided attribute $Q/z$
• Reciprocal depth $1/z$

The Formula

For pixel with barycentric coordinates $(\alpha, \beta, \gamma)$ and depths $z_A, z_B, z_C$:

1. Interpolate $Q/z$: $\left(\frac{Q}{z}\right)_{\text{interp}} = \alpha \frac{Q_A}{z_A} + \beta \frac{Q_B}{z_B} + \gamma \frac{Q_C}{z_C}$

2. Interpolate $1/z$: $\left(\frac{1}{z}\right)_{\text{interp}} = \alpha \frac{1}{z_A} + \beta \frac{1}{z_B} + \gamma \frac{1}{z_C}$

3. Reconstruct: $Q(x, y) = \frac{(Q/z)_{\text{interp}}}{(1/z)_{\text{interp}}}$

Why This Works

After perspective projection, $1/z$ varies linearly in screen space. Dividing attributes by $z$ before interpolation, then dividing by $1/z$ after, gives correct results.