FoundationConcept & Pseudocode EntryAI Reviewed (ai-reviewed)

Bresenham's Line Algorithm

Rasterizes a continuous 2D or 3D line segment onto a discrete integer pixel grid using only integer addition and error accumulation.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Rendering
Difficulty: Beginner
Family: Rasterization & Scan Conversion
Tier: Foundation
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 2
Relationships: 2
Code example: Not ready
Visualization: Ready
Aliases: Bresenham Line Rasterization, Midpoint Line Algorithm

Overview

Bresenham's Line Algorithm steps along the major axis of a line segment between (x0, y0) and (x1, y1), maintaining an integer decision variable (midpoint error term) that determines when to step the minor axis without floating-point division or multiplication.

Core Concepts

integer error accumulatoroctant symmetryscan conversionpixel rasterization

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(max(|dx|, |dy|))

Average

O(max(|dx|, |dy|))

Worst

O(max(|dx|, |dy|))

Space

O(1) auxiliary

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Bresenham's Line Algorithm across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(max(|dx|, |dy|))

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops

Est. Worst-Case TimeO(max(|dx|, |dy|))

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops

Est. Working MemoryO(1) auxiliary

128 B

L2/L3 Cache FriendlyN=100,000

When to Use

Integer-only incremental 2D/3D line rasterization algorithm that plots discrete grid pixels between two endpoints using midpoint error accumulation without floating-point operations.
Use Bresenham's Line Algorithm when you need fast, deterministic, integer-only line drawing on a 2D pixel grid or tilemap.
Use it for grid line-of-sight or ray-march stepping when floating-point drift is undesirable.

When Not to Use

Avoid plain Bresenham when smooth anti-aliased subpixel line edges are required; use anti-aliased coverage blending instead.

What It Does

With dx = 4, dy = -2, and initial err = dx + dy = 2, step 0 has e2 = 4 <= dx so both x and y advance to (1, 1) (upper tie-breaking on exact midpoint; using strict e2 < dx produces [(0, 0), (1, 0), (2, 1), (3, 1), (4, 2)]).
Evaluates `dx = |x1 - x0|, dy = -|y1 - y0|` (Octant deltas) using O(1) auxiliary auxiliary storage.

Use Cases

Integer-only incremental 2D/3D line rasterization algorithm that plots discrete grid pixels between two endpoints using midpoint error accumulation without floating-point operations.
Use Bresenham's Line Algorithm when you need fast, deterministic, integer-only line drawing on a 2D pixel grid or tilemap.

Inputs

Integer start pixel (x0, y0) and end pixel (x1, y1)

Outputs

Ordered list of integer grid coordinates (x, y) along the rasterized line

Key Formulas (2)

Octant deltas

dx = |x₁ − x₀|, dy = −|y₁ − y₀|

dx = |x1 - x0|, dy = -|y1 - y0|

Signed integer deltas for all-octant Bresenham stepping.

Decision variable

err = dx + dy, e₂ = 2 · err

err = dx + dy, e2 = 2 * err

Integer midpoint error doubled to avoid fractional arithmetic.

Pseudocode

1.Compute dx = abs(x1 - x0), sx = +1 if x0 < x1 else -1
2.Compute dy = -abs(y1 - y0), sy = +1 if y0 < y1 else -1
3.Initialize err = dx + dy
4.Loop:
5. Plot pixel (x0, y0); if x0 == x1 and y0 == y1, break
6. e2 = 2 * err
7. If e2 >= dy: err += dy; x0 += sx
8. If e2 <= dx: err += dx; y0 += sy

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Compute dx = abs(x1 - x0), sx = +1 if x0 < x1 else -1
Compute dy = -abs(y1 - y0), sy = +1 if y0 < y1 else -1
Initialize err = dx + dy
Loop:
Plot pixel (x0, y0); if x0 == x1 and y0 == y1, break
e2 = 2 * err
If e2 >= dy: err += dy; x0 += sx
If e2 <= dx: err += dx; y0 += sy

Canonical Example

Input: (x0, y0) = (0, 0), (x1, y1) = (4, 2)
Output: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2)]
Explanation: With dx = 4, dy = -2, and initial err = dx + dy = 2, step 0 has e2 = 4 <= dx so both x and y advance to (1, 1) (upper tie-breaking on exact midpoint; using strict e2 < dx produces [(0, 0), (1, 0), (2, 1), (3, 1), (4, 2)]).

Implementation Notes

Use the unified all-octant formulation with dx = abs(x1 - x0), dy = -abs(y1 - y0), and err = dx + dy.
Check 2 * err against dy and dx simultaneously on each step to advance x and/or y.

Common Pitfalls

Handling only shallow positive slopes (0 <= dy <= dx) and failing to generalize across all 8 octants via abs(dx), -abs(dy), and sign steps sx, sy.
Off-by-one termination before plotting the final endpoint (x1, y1).