Ray Tracing Algorithm | Introduction to Graphics

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]