Rasterisation Algorithm

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})$