Bresenham Line - Computer Graphics Step by Step

Rasterize a shallow line with an integer decision variable, avoiding rounding at each pixel.

bresenham-line Naive DDA steps along a line and rounds to pixels. Bresenham keeps an integer error value instead, so each step decides whether the next pixel stays level or moves up.

Example

Use an integer decision variable to choose line pixels without rounding each step.

highlighted = computed this step

Step 1 — Set up

Set up the integer error values.

dx=5,\ dy=3,\ D=1

Step 2 — Pixel A

Set this line pixel and update the error.

\begin{array}{c|c|c|c|c}x&y&D&\text{test}&D_{\text{next}}\\1&1&1&D>0&-3\end{array}\quad \text{pixel }\hlmath{(1,1)}

Step 3 — Pixel B

Set this line pixel and update the error.

\begin{array}{c|c|c|c|c}x&y&D&\text{test}&D_{\text{next}}\\2&2&-3&D\le 0&3\end{array}\quad \text{pixel }\hlmath{(2,2)}

Step 4 — Pixel C

Set this line pixel and update the error.

\begin{array}{c|c|c|c|c}x&y&D&\text{test}&D_{\text{next}}\\3&2&3&D>0&-1\end{array}\quad \text{pixel }\hlmath{(2,3)}

Step 5 — Pixel D

Set this line pixel and update the error.

\begin{array}{c|c|c|c|c}x&y&D&\text{test}&D_{\text{next}}\\4&3&-1&D\le 0&5\end{array}\quad \text{pixel }\hlmath{(3,4)}

Step 6 — Pixel E

Set this line pixel and update the error.

\begin{array}{c|c|c|c|c}x&y&D&\text{test}&D_{\text{next}}\\5&3&5&D>0&1\end{array}\quad \text{pixel }\hlmath{(3,5)}

Step 7 — Pixel F

Set this line pixel and update the error.

\begin{array}{c|c|c|c|c}x&y&D&\text{test}&D_{\text{next}}\\6&4&1&\text{done}&1\end{array}\quad \text{pixel }\hlmath{(4,6)}

Step 8 — Result

The ordered line pixel set is complete.

\text{line pixels complete}