Output Primitives and Scan Conversion
Output primitives are the basic geometric shapes—points, lines, circles, ellipses, and polygons—that graphics systems use to build more complex images. Because raster displays represent images as grids of pixels, the continuous mathematical definition of a primitive must be converted into a discrete set of pixels through a process called scan conversion or rasterization. The efficiency of these algorithms has a direct impact on the performance of any graphics application.
Point and Line Drawing
Drawing a point means setting the colour of a single pixel at integer coordinates (x, y). Drawing a line from (x1, y1) to (x2, y2) requires choosing pixels that best approximate the mathematical line segment. A naïve approach uses the direct slope–intercept form y = mx + b, computing y for each integer x. While correct, it involves floating-point multiplication per pixel, which is slow.
Digital Differential Analyzer (DDA) Algorithm
The DDA algorithm improves efficiency by incrementally computing each successive point. Starting from (x1, y1), it steps one unit along the longer axis (either x or y) and increments the other coordinate by the slope. Each new point is rounded to the nearest integer and plotted. DDA eliminates multiplication but still uses floating-point addition and rounding, introducing round-off errors over long lines.
Bresenham's Line Algorithm
Bresenham's algorithm uses only integer arithmetic and decision variables to plot the best-fitting pixels. For a line with slope between 0 and 1, it maintains a decision parameter p initialised as p = 2dy − dx. At each step, if p < 0 the next pixel is (x+1, y) and p is updated to p + 2dy; otherwise the pixel is (x+1, y+1) and p is updated to p + 2(dy − dx). The algorithm generalizes to all octants by mirroring or swapping coordinates. Its efficiency and numerical stability have made it the standard for line drawing in hardware and software.
Circle Drawing
A circle of radius r centred at the origin satisfies x² + y² = r². Drawing a circle pixel by pixel by solving this equation is expensive. The midpoint circle algorithm, derived from the same principles as Bresenham's line algorithm, exploits the eight-way symmetry of a circle to plot all octants from a single computed octant. It maintains a decision parameter based on the implicit function f(x, y) = x² + y² − r² and updates it using only integer additions.
Ellipse Drawing
The ellipse algorithm extends the midpoint approach to the equation (x/a)² + (y/b)² = 1. Because an ellipse exhibits only four-way symmetry, the algorithm must consider two regions with different gradient behaviours. Transitions between regions are detected when the magnitude of the y gradient exceeds that of the x gradient, a condition evaluated using integer arithmetic.
Filled-Area Primitives
Besides outlines, graphics systems must fill areas with colour. The scanline polygon-fill algorithm intersects each horizontal scanline with the polygon edges, sorts the intersection points, and fills the pixels between alternate pairs. Special care is taken at vertices to avoid double-counting. The flood-fill and boundary-fill algorithms start from a seed pixel and expand outward using a stack or queue. Flood fill replaces all pixels of a specified interior colour, while boundary fill stops at pixels of a specified boundary colour.
Antialiasing
Scan conversion of a continuous primitive produces stair-step artefacts known as aliasing. Antialiasing mitigates these artefacts by varying the intensity of boundary pixels in proportion to the area covered by the primitive. Supersampling renders at a higher resolution and downsamples, while analytic methods compute exact coverage. Modern GPUs provide multi-sample antialiasing (MSAA) with hardware support.
Attributes of Output Primitives
Each primitive may have attributes such as colour, line style (solid, dashed, dotted), line width, pen type, fill pattern, and character font. These attributes are maintained in the graphics state and applied during rasterization. Careful management of state is crucial in libraries like OpenGL where state changes have performance implications.
Summary
Scan conversion algorithms are the bridge between continuous geometry and discrete pixels. Algorithms such as Bresenham's, the midpoint circle algorithm, and scanline polygon fill remain foundational because of their efficiency and accuracy. Antialiasing techniques further improve visual quality by smoothing the inherent discretization of raster displays.