Explain Bresenham’s Line drawing algorithm

2.C] Explain Bresenham’s Line drawing algorithm.

Apply Bresenham’s Line drawing algorithm to digitize the line segment with endpoints (20,10) and (30,18) having a slope of 0.8.

Answer:-

Bresenham’s Line Drawing Algorithm

Bresenham’s Line Drawing Algorithm is a method used in computer graphics to draw a straight line between two points on a grid (such as a pixelated screen) using only integer calculations, which makes it very fast. The algorithm works by choosing the closest pixel to the theoretical line at each step, ensuring that the drawn line looks as close to the actual line as possible.

Cases for Bresenham’s Algorithm

1. Case 1: Slope m < 1

When the slope m is less than 1, the line is more horizontal.

• Primary axis of movement: The x-coordinate increases at each step.
• Decision parameter: Determines whether to move the y-coordinate up by 1 or keep it the same.

Steps for m < 1:

1. Calculate Δx and Δy:
   • Δx = x₂ – x₁
   • Δy = y₂ – y₁
2. Initial Decision Parameter:
   • p₀ = 2Δy – Δx
3. Iteration:
   • Start from the first point (x₁, y₁).
   • For each step:
     • If p ≥ 0, move diagonally (increment both x and y).
     • If p < 0, move horizontally (increment x only).
   • Update the decision parameter for the next step.

2. Case 2: Slope m ≥ 1

When the slope m is greater than or equal to 1, the line is more vertical.

• Primary axis of movement: The y-coordinate increases at each step.
• Decision parameter: Determines whether to move the x-coordinate by 1 or keep it the same.

Steps for m ≥ 1:

1. Calculate Δx and Δy:
   • Δx = x₂ – x₁
   • Δy = y₂ – y₁
2. Initial Decision Parameter:
   • p₀ = 2Δx – Δy
3. Iteration:
   • Start from the first point (x₁, y₁).
   • For each step:
     • If p ≥ 0, move diagonally (increment both y and x).
     • If p < 0, move vertically (increment y only).
   • Update the decision parameter for the next step.

Example: Digitizing the Line Segment from (20, 10) to (30, 18) with m = 0.8

Given:

• Start Point: (20, 10)
• End Point: (30, 18)
• Slope m = 0.8 (which is less than 1)

Steps:

1. Calculate Δx and Δy:
   • Δx = 30 – 20 = 10
   • Δy = 18 – 10 = 8
2. Initial Decision Parameter:
   • p₀ = 2Δy – Δx = 2(8) – 10 = 16 – 10 = 6
3. Plotting Points:

Step	xi	yi	pi	Next Point	Updated pi
1	20	10	6	(21, 11)	4
2	21	11	4	(22, 12)	2
3	22	12	2	(23, 13)	0
4	23	13	0	(24, 14)	-2
5	24	14	-2	(25, 14)	14
6	25	14	14	(26, 15)	12
7	26	15	12	(27, 16)	10
8	27	16	10	(28, 17)	8
9	28	17	8	(29, 18)	6
10	29	18	6	(30, 18)	–

Summary

The algorithm effectively determines which pixels to activate on the grid to represent the line. For this specific case (m = 0.8), the algorithm first increments the x-coordinate and adjusts the y-coordinate based on the decision parameter. When the slope m ≥ 1, the primary axis of movement becomes the y-axis, and the algorithm adjusts the x-coordinate accordingly.

In simple Explanation:-