PadhaikoAll subjects

Rasterizing Points & Lines: DDA and Bresenham

Computer Graphics and Visualization (ENCT 201)

Open in the Padhaiko app

2.1 Rasterizing a Point

Rasterization (or scan conversion) is the fundamental process in computer graphics that converts continuous geometric primitives defined in mathematical coordinate spaces into discrete sets of illuminated pixels within a raster frame buffer.

A mathematical point occupies an infinitesimal location with continuous real-valued coordinates . In contrast, a physical raster display consists of a finite, discrete rectangular matrix of addressable picture elements (pixels) indexed by integer coordinates .

Continuous Math Plane               Discrete Pixel Matrix
        y                                  Y_p
        │                                  ┌───┬───┬───┬───┐
        │   • P(2.4, 3.7)               4  │   │   │ ■ │   │  Pixel (2, 4)
        │                                  ├───┼───┼───┼───┤
        │                               3  │   │   │   │   │
        └─────────────── x                 └───┴───┴───┴───┘
                                             0   1   2   3  X_p
Definition

Point Rasterization and Frame Buffer Addressing

To rasterize a continuous 2D point , its floating-point coordinates are mapped to the nearest discrete pixel center using half-up integer rounding:

In a raster graphics architecture, the frame buffer is organized as a linear, contiguous block of physical memory. For a screen of resolution pixels with bytes per pixel, the memory address of the pixel at coordinate is computed using row-major order:

where is the pitch (byte width of one complete horizontal scan line).

The low-level graphics driver executes a putpixel(X_p, Y_p, color) primitive that writes the binary color code directly into the calculated memory offset of the frame buffer.

2.2 Rasterizing a Straight Line: DDA & Bresenham Line Algorithms

A mathematical straight line segment connecting two endpoints and satisfies the standard slope-intercept Cartesian equation:

where the slope and vertical intercept are defined by:

Criteria for High-Quality Line Rasterization

An optimal raster line-drawing algorithm must satisfy four fundamental criteria:

  1. Straightness and Spatial Fidelity: The sequence of plotted pixels must approximate the continuous mathematical line as closely as possible, minimizing perpendicular deviation.
  2. Visual Continuity (No Gaps): The plotted pixels must form an unbroken chain across the display surface. Adjacent pixels must share at least edge or corner contact (8-connectivity: horizontally, vertically, or diagonally adjacent).
  3. Uniform Brightness: The apparent luminous intensity of the line must remain constant regardless of its slope or spatial orientation.
  4. Endpoint Order Invariance: Drawing a line from to must activate the exact same sequence of pixel addresses as drawing from to .
  5. Algorithmic Efficiency: The inner rasterization loop must execute at maximum speed, avoiding computationally expensive operations like floating-point division, multiplication, or trigonometric functions.

The Digital Differential Analyzer (DDA) Algorithm

The Digital Differential Analyzer (DDA) is an incremental scan-conversion method based on evaluating differential increments along either the or coordinate axis.

Theorem

Digital Differential Analyzer (DDA) Formulation

The differential equation of a straight line is:

Depending on the magnitude of the slope , one coordinate axis acts as the primary driving axis, advancing by unit increments (), while the secondary axis advances by an incremental fractional step:

  1. Gentle Slope (): Horizontal displacement exceeds vertical displacement (). The -axis serves as the driving axis:

At each successive step :

The plotted pixel address is .

  1. Steep Slope (): Vertical displacement exceeds horizontal displacement (). If we were to step in , the calculated coordinates would jump by , leaving visible disconnected gaps. Therefore, the -axis serves as the driving axis:

At each successive step :

The plotted pixel address is .

In a generalized implementation, the total number of discrete steps is:

The per-step coordinate increments are then computed as:

Limitations of the DDA Algorithm

While conceptually simple, the DDA algorithm suffers from two key engineering disadvantages:

Bresenham's Line Algorithm

To overcome the performance and precision penalties of DDA, Jack E. Bresenham developed an exact, highly efficient line rasterization algorithm that operates entirely using pure integer addition, subtraction, and bit-shifts.

Mathematical Derivation for Gentle Slope ( with )

Consider a line with gentle positive slope traversed from left to right (). Assume that at step , the algorithm has determined that the optimal pixel is . Because , stepping means the true line coordinate satisfies:

Therefore, the next pixel can only be one of two candidates:

        y_k + 1 ───────────────• NE (x_k + 1, y_k + 1)
                               │  ▲
                               │  │ d_2
                               │──┼─── True line: y = m(x_k + 1) + c
                               │  │ d_1
                               │  ▼
            y_k ───•───────────• E (x_k + 1, y_k)
                 (x_k, y_k)   x_k + 1

The true vertical mathematical position along the line at is:

We compute the vertical distances from candidate pixels and to the true line:

The difference between these two separation distances is:

Substituting :

To eliminate fractions while preserving the sign of , we multiply the entire expression by . This defines the decision parameter :

where is a constant independent of pixel coordinates.

Decision Rule

Incremental Recursive Parameter Update

At step , the decision parameter is:

Subtracting from :

Since , we have :

This yields two simple incremental updates:

  1. If (chose , so ):
  1. If (chose , so ):

Initial Decision Parameter ()

At the first endpoint , the vertical intercept satisfies . Substituting into the definition of :

Generalization to All Eight Octants

To draw arbitrary line segments across all directions and slopes, the algorithm evaluates coordinate differences and signs:

  1. Calculate absolute deltas and directional signs:
  1. Determine the Driving Axis:
    • Case A: Gentle Slope (, Octants 1, 4, 5, 8): is the driving axis. Step by at every iteration.

If : remains unchanged; . If : steps by ; .

If : remains unchanged; . If : steps by ; .

AspectDigital Differential Analyzer (DDA)Bresenham's Line Algorithm
Arithmetic TypeFloating-point additions and runtime rounding operations.Pure integer addition, subtraction, and arithmetic shifts.
Computational SpeedSlower; floating-point operations require more CPU cycles.Extremely fast; inner loop uses minimal integer additions.
Error AccumulationCumulative round-off errors accumulate over long lines.Exact; zero cumulative drift from the mathematical line.
Hardware CompatibilityPoor on low-end microcontrollers lacking a floating-point unit.Ideal for microcontrollers, GPUs, and custom ASIC pipelines.
Pixel Set PlottedCan vary slightly based on floating-point rounding precision.Strictly deterministic and identical across all compliant systems.

Worked Examples

Example 1

DDA Line Rasterization from (2, 3) to (10, 7)

Rasterize a straight line segment from to using the Digital Differential Analyzer (DDA) algorithm. Show:

  1. The calculation of coordinate differences, slope, and step count.
  2. The complete step-by-step trace table listing floating-point coordinates and rounded plotted pixels.

Slope and Increment Calculations: Given endpoints:

Coordinate differences:

The slope is:

Since , the -axis is the driving axis. The total number of steps is:

The incremental updates per step are:

Step-by-Step DDA Trace: Starting at , we increment by and by at each step :

DDA Line Trace from (2, 3) to (10, 7)Generated by running the algorithm
kxyplot
023(2,3)
DDA Line (2, 3) to (10, 7) 2 3 4 5 6 7 8 9 10 3 4 5 6 7
DDA Line (2, 3) to (10, 7)
Answer:

The DDA line algorithm completes in steps, generating the pixel sequence:

Example 2

Bresenham Line Rasterization from (20, 10) to (30, 18)

Rasterize a straight line from to using Bresenham's line algorithm. Show:

  1. Determination of driving axis, initial decision parameter , and recursive update constants.
  2. Complete iteration table showing step , decision parameter , and chosen pixel .

Initial Conditions and Parameter Computation: Given endpoints:

Coordinate deltas:

Since (), the -axis is the primary driving axis. The constant increment terms are:

The initial decision parameter is:

Bresenham Iteration Trace: Starting at initial point , the algorithm performs iterations:

Bresenham Line Trace from (20, 10) to (30, 18)Generated by running the algorithm
kpxy
062111
Bresenham Line (20, 10) to (30, 18) 20 21 22 23 24 25 26 27 28 29 30 10 11 12 13 14 15 16 17 18
Bresenham Line (20, 10) to (30, 18)
Answer:

The Bresenham algorithm generates the exact integer pixel sequence:

Example 3

Bresenham Steep Line (|m| > 1) from (1, 2) to (5, 9)

Rasterize a straight line from to using Bresenham's line algorithm. Explain why the roles of and must be swapped, and provide the complete trace of decision parameters and generated pixels.

Steep Slope Analysis and Parameter Setup: Given endpoints:

Deltas:

The slope is .

Because , vertical displacement exceeds horizontal displacement. Stepping by would cause to increase by per step, leaving unplotted pixel gaps along the line. Thus, the roles of and are swapped:

  • The -axis serves as the primary driving axis ( steps by at every iteration).
  • The decision parameter selects whether remains unchanged or steps by .

The initial decision parameter is:

The incremental update constants are:

Steep Slope Bresenham Trace: At each step :

  • If : choose ; then .
  • If : choose ; then .
Bresenham Steep Line from (1, 2) to (5, 9)Generated by running the algorithm
kpxy
0123
Bresenham Steep Line (1, 2) to (5, 9) 1 2 3 4 5 2 3 4 5 6 7 8 9
Bresenham Steep Line (1, 2) to (5, 9)
Answer:

Because , stepping along prevents pixel gaps. The algorithm outputs steps:


Exercises

Point & Line Rasterization Exercises

Question 1

Rasterize a straight line from to using the Digital Differential Analyzer (DDA) algorithm. Show coordinate differences, slope, step count, and a table of intermediate floating-point coordinates and plotted pixel positions.

Slope and Delta Calculations: Given:

The slope is:

Since , the -axis is the driving axis. Total steps:

Increments:

Tabulating Intermediate Coordinates: Starting at :

Rounded Plotted Pixel
0
1
2
3
4
5
6
7
Answer:

The DDA line algorithm generates the sequence of 8 pixels:

Question 2

Rasterize a straight line from to using Bresenham's line algorithm. Show all decision parameter values, candidate choices, and the final pixel path.

Parameter Initialization: Given:

Since (), is the driving axis. Constants:

Initial decision parameter:

Step-by-Step Bresenham Iterations: Starting at :

  • : plot ;
  • : plot ;
  • : plot ;
  • : plot ;
  • : plot ;
  • : plot ;
  • : plot ;
  • : plot ; termination.
Answer:

Bresenham's algorithm yields the pixel coordinates:

Question 3

Derive the decision parameter , its initial value , and the recursive update equations for Bresenham's line algorithm for a line with slope .

Distance Difference Formulation: Let the line equation be . At step with current pixel , advancing by gives two candidate pixels: and . The true vertical coordinate is . Vertical distances:

Eliminating Fractions to Define pk: Substituting and scaling by :

where . Since , . If , (choose ); if , (choose ).

Recursive Update and Initial Parameter: Evaluating the successive difference :

  • If : .
  • If : .

At the starting endpoint , using :

Answer:

The initial decision parameter is . At each step, if , ; if , .

Question 4

Rasterize a straight line with negative slope from to using Bresenham's line algorithm. Show how the algorithm adapts its step directions and decision updates for .

Deltas and Directional Signs: Given endpoints and :

Since (, ), is the driving axis. Because , whenever a vertical change is required, decrements by . The constants evaluated with absolute values are:

Initial decision parameter:

Iterations for Negative Slope: Starting at :

  • : decrement ; plot ;
  • : keep ; plot ;
  • : decrement ; plot ;
  • : keep ; plot ;
  • : decrement ; plot ;
  • : keep ; plot ;
  • : decrement ; plot ; termination.
Answer:

The plotted pixel path for the negative slope line is:

Question 5

Rasterize a steep line from to using Bresenham's line algorithm. Explain why the driving axis must be changed to , and tabulate all decision parameters.

Steep Line Classification: Given endpoints:

Because , stepping along would cause to increment by per step, leaving unilluminated gaps in the raster line. To guarantee continuous 8-connectivity, must serve as the primary driving axis, advancing by at every step, while advances conditionally. Constants:

Initial parameter:

Step-by-Step Iterations along Y: Starting at :

  • : keep ; plot ;
  • : step ; plot ;
  • : keep ; plot ;
  • : step ; plot ;
  • : keep ; plot ;
  • : step ; plot ;
  • : keep ; plot ;
  • : step ; plot ;
  • : keep ; plot ; termination.
Answer:

The steep line rasterization yields 10 pixels:

Question 6

Provide an in-depth comparative analysis between the DDA algorithm and Bresenham's algorithm. Discuss computational architecture, floating-point vs. integer arithmetic, error accumulation, and hardware suitability.

Computational Foundations and Data Types: The DDA algorithm solves the continuous differential equation by adding floating-point increments () at every step, requiring a runtime type conversion or rounding function to determine integer pixel coordinates. Bresenham's algorithm is formulated purely on integer arithmetic. By scaling the distance difference by , it derives an integer decision parameter whose sign directly dictates the pixel selection, requiring only integer additions and subtractions.

Error Accumulation and Precision: In the DDA algorithm, accumulating finite-precision floating-point numbers over long trajectories introduces cumulative round-off error. Over thousands of pixels, this causes the plotted raster path to drift away from the true mathematical line. Bresenham's algorithm does not accumulate round-off errors. At every single step, the decision parameter evaluates the exact midpoint relative to the true line, ensuring that the chosen pixel is always the closest candidate without numerical drift.

Hardware Suitability and Speed: Bresenham's algorithm is universally favored for real-time graphics pipelines, GPU rasterizers, and embedded display controllers because integer operations execute in a single clock cycle and do not require a floating-point unit (FPU). DDA is predominantly reserved for educational demonstrations or software contexts where floating-point math is already subsidized.

Answer:

Bresenham's algorithm is superior to DDA because it uses pure integer arithmetic, avoids floating-point round-off drift, executes in fewer clock cycles, and is ideally suited for hardware rasterization engines.

Past exam questions for Computer Graphics and Visualization

← Graphics Software, Viewing Pipelines & ApplicationsMid-Point Circle & Ellipse Algorithms →