Rasterization

Bresenham Line

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

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=1dx=5,\ dy=3,\ D=1
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345

Step 2 — Pixel A

Set this line pixel and update the error.

xyDtestDnext111D>0−3pixel (1,1)\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)}
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345A

Step 3 — Pixel B

Set this line pixel and update the error.

xyDtestDnext22−3D≤03pixel (2,2)\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)}
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345AB

Step 4 — Pixel C

Set this line pixel and update the error.

xyDtestDnext323D>0−1pixel (2,3)\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)}
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345ABC

Step 5 — Pixel D

Set this line pixel and update the error.

xyDtestDnext43−1D≤05pixel (3,4)\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)}
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345ABCD

Step 6 — Pixel E

Set this line pixel and update the error.

xyDtestDnext535D>01pixel (3,5)\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)}
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345ABCDE

Step 7 — Pixel F

Set this line pixel and update the error.

xyDtestDnext641done1pixel (4,6)\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)}
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345ABCDEF

Step 8 — Result

The ordered line pixel set is complete.

line pixels complete\text{line pixels complete}
Bresenham line pixelsLine pixels are added in Bresenham order.01234567012345ABCDEF
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.