Bresenham Line

Rasterization of lines is something that is very important in computer graphics. Line is one of the simplest primitives and we want to specify it by its endpoints. It is up to the computer to fill all the pixels between those endpoints that are visible.

Very efficient and known way of rasterizing lines is called the Bresenham's line algorithm. Idea behind it is that we will consider the slope of the line. Then we will move along one of the coordinates and accumulate the fractions of pixels a line should have moved in the other coordinate. If this fraction accumulates over 0.5, then we move 1 unit in the other coordinate and subtract 1.0 from the accumulator. Wikipedia has a good general explanation of it.

However, for this algorithm to be fast, different optimizations are considered. One of those is avoiding extra calculations like finding the sign inside the rasterization cycle. It might not seem much at first glance, but this algorithm needs to be ran millions of times per second. Even the Wikipedia says that the most optimized version of it only uses integer addition, subtraction and bit shifting.

;