1. Rasterization

Rasterization is the process of converting geometric primitives (like lines, polygons) into pixels on a display screen.

• It is a fundamental step in rendering 2D and 3D graphics.
• The goal is to determine which pixels on the screen should be illuminated to best represent a line, circle, or polygon.
• For lines, we need efficient algorithms to decide pixel positions along the line path.

2. Line Drawing

Problem

• A line is defined by endpoints $(x_0, y_0)$ and $(x_1, y_1)$.
• On a raster display, we need to select discrete pixel positions to approximate the line.
• Simple slope-based methods may require floating-point operations and can be slow.

3. Bresenham’s Line Drawing Algorithm

Bresenham’s Algorithm is an efficient integer-based line rasterization algorithm.

• Uses only integer addition, subtraction, and comparison (no floating-point arithmetic).
• Ideal for fast and accurate line drawing in raster displays.

Algorithm Concept

1. Consider a line with slope $0 \le m \le 1$ (general case; other slopes are handled similarly).
2. Start at pixel $(x_0, y_0)$.
3. Move one step in x each iteration.
4. Decide whether to keep y the same or increment y by 1 based on a decision parameter $p$.

Steps

Initialization

• $p_0$ is the initial decision parameter.

Iterative Step

For each $x_k$ from $x_0$ to $x_1$:

1. Plot pixel at $(x_k, y_k)$

2. If $p_k < 0$:

   • Next pixel: $(x_{k+1}, y_k)$
   • Update decision parameter:

3. Else:

   • Next pixel: $(x_{k+1}, y_{k}+1)$
   • Update decision parameter:

• Repeat until reaching $(x_1, y_1)$.

Advantages

• Uses integer calculations only → fast and suitable for hardware implementation.
• Produces accurate and visually continuous lines.
• Works for all line slopes with minor modifications.

Example

Line from $(2, 3)$ to $(10, 7)$:

1. $\Delta x = 8, \Delta y = 4$
2. Initial decision parameter: $p_0 = 2 \cdot 4 - 8 = 0$
3. Start at $(2, 3)$, update pixel coordinates based on $p_k$ for each x-step.

5. Summary

Key Points:

• Rasterization converts continuous geometry to discrete pixels.
• Bresenham’s algorithm is efficient, integer-based, and widely used for line drawing.
• Variants exist for steep slopes, negative slopes, and 3D lines.