Rasterizing Points & Lines: DDA and Bresenham
Open in the Padhaiko app2.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
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:
- Straightness and Spatial Fidelity: The sequence of plotted pixels must approximate the continuous mathematical line as closely as possible, minimizing perpendicular deviation.
- 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).
- Uniform Brightness: The apparent luminous intensity of the line must remain constant regardless of its slope or spatial orientation.
- Endpoint Order Invariance: Drawing a line from to must activate the exact same sequence of pixel addresses as drawing from to .
- 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.
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:
- Gentle Slope (): Horizontal displacement exceeds vertical displacement (). The -axis serves as the driving axis:
At each successive step :
The plotted pixel address is .
- 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:
- Floating-Point Arithmetic: Calculating and requires continuous floating-point additions and runtime rounding operations (), which degrade performance on embedded processors or hardware without dedicated floating-point units.
- Cumulative Round-Off Drift: Repeatedly accumulating floating-point approximations over hundreds of iterations causes numerical round-off errors to compound, causing the plotted path to drift away from the true mathematical line over long distances.
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:
- Pixel East (E): (horizontal step)
- Pixel North-East (NE): (diagonal step)
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
- If : Then , meaning the true line is closer to the lower pixel .
- We choose .
- If : Then , meaning the true line is closer to (or equidistant from) the upper pixel .
- We choose .
Incremental Recursive Parameter Update
At step , the decision parameter is:
Subtracting from :
Since , we have :
This yields two simple incremental updates:
- If (chose , so ):
- 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:
- Calculate absolute deltas and directional signs:
- 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 ; .
- Case B: Steep Slope (, Octants 2, 3, 6, 7): is the driving axis. Step by at every iteration.
If : remains unchanged; . If : steps by ; .
| Aspect | Digital Differential Analyzer (DDA) | Bresenham's Line Algorithm |
|---|---|---|
| Arithmetic Type | Floating-point additions and runtime rounding operations. | Pure integer addition, subtraction, and arithmetic shifts. |
| Computational Speed | Slower; floating-point operations require more CPU cycles. | Extremely fast; inner loop uses minimal integer additions. |
| Error Accumulation | Cumulative round-off errors accumulate over long lines. | Exact; zero cumulative drift from the mathematical line. |
| Hardware Compatibility | Poor on low-end microcontrollers lacking a floating-point unit. | Ideal for microcontrollers, GPUs, and custom ASIC pipelines. |
| Pixel Set Plotted | Can vary slightly based on floating-point rounding precision. | Strictly deterministic and identical across all compliant systems. |
Worked Examples
DDA Line Rasterization from (2, 3) to (10, 7)
Rasterize a straight line segment from to using the Digital Differential Analyzer (DDA) algorithm. Show:
- The calculation of coordinate differences, slope, and step count.
- 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 :
| k | x | y | plot |
|---|---|---|---|
| 0 | 2 | 3 | (2,3) |
| 1 | 3 | 3.5 | (3,4) |
| 2 | 4 | 4 | (4,4) |
| 3 | 5 | 4.5 | (5,5) |
| 4 | 6 | 5 | (6,5) |
| 5 | 7 | 5.5 | (7,6) |
| 6 | 8 | 6 | (8,6) |
| 7 | 9 | 6.5 | (9,7) |
| 8 | 10 | 7 | (10,7) |
The DDA line algorithm completes in steps, generating the pixel sequence:
Bresenham Line Rasterization from (20, 10) to (30, 18)
Rasterize a straight line from to using Bresenham's line algorithm. Show:
- Determination of driving axis, initial decision parameter , and recursive update constants.
- 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:
| k | p | x | y |
|---|---|---|---|
| 0 | 6 | 21 | 11 |
| 1 | 2 | 22 | 12 |
| 2 | -2 | 23 | 12 |
| 3 | 14 | 24 | 13 |
| 4 | 10 | 25 | 14 |
| 5 | 6 | 26 | 15 |
| 6 | 2 | 27 | 16 |
| 7 | -2 | 28 | 16 |
| 8 | 14 | 29 | 17 |
| 9 | 10 | 30 | 18 |
The Bresenham algorithm generates the exact integer pixel sequence:
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 .
| k | p | x | y |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
| 1 | -5 | 2 | 4 |
| 2 | 3 | 3 | 5 |
| 3 | -3 | 3 | 6 |
| 4 | 5 | 4 | 7 |
| 5 | -1 | 4 | 8 |
| 6 | 7 | 5 | 9 |
Because , stepping along prevents pixel gaps. The algorithm outputs steps:
Exercises
Point & Line Rasterization Exercises
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 |
The DDA line algorithm generates the sequence of 8 pixels:
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.
Bresenham's algorithm yields the pixel coordinates:
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 :
The initial decision parameter is . At each step, if , ; if , .
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.
The plotted pixel path for the negative slope line is:
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.
The steep line rasterization yields 10 pixels:
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.
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.