Summary of "Bresenham's Circle Drawing Algorithm - Computer Graphics"

This lecture explains Bresenham's Circle Drawing Algorithm, a fundamental method in Computer Graphics for efficiently drawing circles on pixel-based screens using integer arithmetic. The key concepts, problems with naive methods, and the detailed derivation of the algorithm are covered, along with example code and execution tracing.

Main Ideas and Concepts

Screen Coordinates and Pixel Representation
- The origin (0,0) is at the top-left corner of the screen.
- X-axis increases to the right; Y-axis increases downwards (unlike traditional graph paper).
- Pixels are discrete units with integer coordinates.
- To draw a circle, pixels on the circumference must be "glowed" or activated.
Drawing Circles Using Polar Coordinates
- Polar Coordinates use \(x = r \cos \theta\), \(y = r \sin \theta\) for \(\theta = 0^\circ\) to \(360^\circ\).
- Problems:
  - Generates floating-point values requiring rounding or truncation, causing gaps and jagged circles.
  - Floating-point operations are computationally expensive, slowing the algorithm.
- Hence, a need for an integer-only algorithm arises.
Coordinate Systems: Quadrants and Octants
- Traditional Cartesian Coordinate System has four quadrants.
- Screen coordinates correspond to the fourth quadrant (positive x and y).
- Circles are symmetric in eight parts (octants).
- By calculating points in just one octant, the full circle can be drawn by symmetry.
Mathematical Foundation: Pythagoras Theorem
- Circle equation: \(x^2 + y^2 = r^2\).
- Define a function \(f(x,y) = x^2 + y^2 - r^2\).
  - \(f(x,y) = 0\) means the point lies exactly on the circle.
  - \(f(x,y) < 0\) means inside the circle.
  - \(f(x,y) > 0\) means outside the circle.
Sampling X and Deciding Y
- Since one equation cannot solve for two unknowns \(x\) and \(y\), sample \(x\) values from 0 to \(r\).
- For each \(x_k\), decide whether \(y_k\) stays the same or decrements by 1.
- \(x\) always increments by 1; \(y\) either stays or decrements.
Decision Variable \(D_k\)
- To decide whether to decrement \(y\), calculate a Decision Variable \(D_k = f(\text{next north pixel}) + f(\text{next south pixel})\).
- North pixel: \((x_k + 1, y_k)\) — y unchanged.
- South pixel: \((x_k + 1, y_k - 1)\) — y decremented.
- If \(D_k < 0\), choose north pixel (y unchanged).
- If \(D_k \geq 0\), choose south pixel (y decremented).
Deriving the Recursive Formula for \(D_{k+1}\)
- \(D_{k+1}\) can be computed from \(D_k\) by adding a simple expression.
- When \(D_k < 0\): \(D_{k+1} = D_k + 4x_k + 6\).
- When \(D_k \geq 0\): \(D_{k+1} = D_k + 4(x_k - y_k) + 10\).
Initial Values
- Start with \(x = 0\), \(y = r\).
- Initial Decision Variable: \(D_0 = 3 - 2r\).
Algorithm Outline (Pseudocode)
- Initialize \(x=0\), \(y=r\), \(D=3-2r\).
- While \(x \leq y\):
  - Plot the 8 symmetric pixels corresponding to \((x,y)\) using Octant Symmetry.
  - If \(D < 0\):
    - \(D = D + 4x + 6\)
  - Else:
    - \(D = D + 4(x - y) + 10\)
    - \(y = y - 1\)
  - \(x = x + 1\)
Plotting 8 Pixels Using Octant Symmetry
- From one point \((x,y)\), derive other points by:
  - \((x, y)\), \((y, x)\), \((-x, y)\), \((-y, x)\), \((-x,