Q1Computer Graphics and Multimedia
Question
4 marks
Explain the Mid-Point Circle Drawing Algorithm.
Answer
The Mid-Point Circle Drawing Algorithm uses a decision parameter to select the closest pixel to the true circle path, using 8-fold symmetry.
The Mid-Point Circle Drawing Algorithm (also called Bresenham's Circle Algorithm) efficiently rasterizes a circle of radius r centered at origin using integer arithmetic and the circle's 8-fold symmetry. It evaluates the circle equation f(x,y) = x² + y² - r² at midpoints between candidate pixels.
- Initialize: x = 0, y = r, p = 1 - r (initial decision parameter).
- Plot all 8 symmetric points: (±x, ±y) and (±y, ±x).
- Increment x by 1 each step.
- If p < 0: y stays same, p = p + 2x + 3.
- If p ≥ 0: y decreases by 1, p = p + 2x - 2y + 5.
- Continue until x ≥ y (completes one octant).
Example for r=5: Start: x=0, y=5, p=1-5=-4. Step 1: p<0, plot(1,5), p=-4+2+3=1. Step 2: p≥0, y→4, plot(2,4), p=1+4-8+5=2. Step 3: p≥0, y→3, plot(3,3) — done (x=y). The 8-fold symmetry plots all octants simultaneously, requiring only ⅛ of the work.