Bresenham's Circle Drawing Algorithm & DDA Line Algorithm Trace [10 marks]

---

Part A: Bresenham's Circle Drawing Algorithm

Bresenham's Circle Drawing Algorithm is an efficient scan-conversion method that uses only integer arithmetic to determine the closest pixel positions along a circle's circumference, exploiting the eight-way symmetry of a circle.

Key Idea:

The algorithm calculates pixels for only one-eighth of the circle (from 0° to 45°) and uses symmetry to plot the remaining seven octants simultaneously.

Eight-Way Symmetry:

For a point $(x, y)$ on the circle, the following 8 points are also on the circle:

$(x,y),\ (-x,y),\ (x,-y),\ (-x,-y),\ (y,x),\ (-y,x),\ (y,-x),\ (-y,-x)$

Algorithm Steps:

• a. Input the radius $r$ and circle center $(x_c, y_c)$
• b. Set starting point: $x = 0$, $y = r$
• c. Calculate initial decision parameter: $p_0 = 3 - 2r$
• d. At each $x_k$ position, check the decision parameter $p_k$:
  • If $p_k < 0$: Next point is $(x_{k}+1,\ y_k)$ and $p_{k+1} = p_k + 4x_k + 6$
  • If $p_k \geq 0$: Next point is $(x_{k}+1,\ y_k - 1)$ and $p_{k+1} = p_k + 4(x_k - y_k) + 10$
• e. Plot the symmetric points in all eight octants (translate by adding $x_c, y_c$)
• f. Repeat steps d–e until $x \geq y$

Advantages:

• Uses only integer addition and subtraction — no multiplication or trigonometry
• Very fast and efficient for hardware implementation
• Produces smooth, symmetric circles

---

Part B: DDA Algorithm Trace — Line from (2, 2) to (6, 6)

DDA (Digital Differential Analyzer) is a line drawing algorithm that uses incremental floating-point calculations to find successive pixel positions along a line.

Given:

• Start point: $(x_1, y_1) = (2, 2)$
• End point: $(x_2, y_2) = (6, 6)$

Step-by-step Calculation:

$$dx = x_2 - x_1 = 6 - 2 = 4$$

$$dy = y_2 - y_1 = 6 - 2 = 4$$

$$steps = \max(|dx|, |dy|) = \max(4, 4) = 4$$

$$x_{inc} = \frac{dx}{steps} = \frac{4}{4} = 1$$

$$y_{inc} = \frac{dy}{steps} = \frac{4}{4} = 1$$

Iteration Table:

Step	$x$	$y$	Pixel Plotted $(\text{round}(x), \text{round}(y))$
0	2	2	(2, 2)
1	3	3	(3, 3)
2	4	4	(4, 4)
3	5	5	(5, 5)
4	6	6	(6, 6)

Explanation: Since the line has a slope of $m = \frac{dy}{dx} = \frac{4}{4} = 1$ (45° line), both x and y increment by exactly 1 at each step, producing a perfect diagonal line.

---

Conclusion: Bresenham's circle algorithm is preferred over parametric methods due to its integer-only arithmetic and efficiency. The DDA algorithm is simple and works well for lines of any slope by choosing the larger of dx/dy as the number of steps, ensuring smooth pixel placement.