Bresenham’s Line Drawing Algorithm

1. Line Drawing in Raster Graphics

Raster displays represent images as grids of pixels. Line drawing algorithms decide which pixels should be turned ON to represent a straight line.

• Pixel-based rendering
• Avoids gaps and overlaps
• Optimized for speed

2. What is Bresenham’s Algorithm?

Bresenham’s algorithm incrementally determines the next pixel to plot based on a decision parameter, using only integer calculations.

• No floating-point arithmetic
• Fast and efficient
• Ideal for hardware implementation

3. Basic Idea

At each step, the algorithm chooses between two possible pixels and selects the one closer to the true line using a decision parameter.

• Evaluates midpoint between pixels
• Updates decision parameter incrementally

4. Assumptions

• Slope |m| ≤ 1
• Line drawn from left to right
• Other cases handled by symmetry

5. Mathematical Formulation

dx = x2 - x1
dy = y2 - y1

Initial Decision Parameter:
p0 = 2dy - dx

6. Decision Parameter Update

If p < 0:
    p = p + 2dy
Else:
    p = p + 2dy - 2dx
    y = y + 1
x = x + 1

7. Steps of Bresenham’s Algorithm

• Input start and end points
• Calculate dx and dy
• Initialize decision parameter
• Plot starting pixel
• Iteratively plot next pixels

8. Example

To draw a line from (2, 2) to (10, 6):

• dx = 8, dy = 4
• p0 = 2×4 − 8 = 0
• Choose pixel based on p value

9. Advantages of Bresenham’s Algorithm

• Uses integer arithmetic only
• Very fast execution
• High accuracy

10. Disadvantages of Bresenham’s Algorithm

• More complex than DDA
• Initial slope assumptions required

11. DDA vs Bresenham Algorithm

DDA Algorithm               Bresenham Algorithm
-------------------------   ----------------------------
Floating-point arithmetic   Integer arithmetic only
Slower                      Faster
Simple logic                Slightly complex
Less accurate               More accurate

Practice Questions

1. What is Bresenham’s line algorithm?
2. Define decision parameter.
3. Explain steps of Bresenham’s algorithm.
4. Differentiate DDA and Bresenham.
5. Draw a line using Bresenham’s algorithm.

Practice Task