PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q2(a)

Computer Graphics and Visualization · 7 marks

Open in the Padhaiko app

Topic: Mid-Point Circle & Ellipse Algorithms

Question

How is the symmetric property vital while drawing an ellipse? Write an algorithm to draw ellipse in raster graphics system.

Solution

Four-Quadrant Symmetry of an Ellipse: An ellipse centered at origin with semi-major axis and semi-minor axis is described by the implicit equation:

Because only even powers of and appear in the equation, . Thus, any point on the ellipse generates three symmetrical points across the coordinate axes:

  1. Quadrant I:
  2. Quadrant II:
  3. Quadrant III:
  4. Quadrant IV:

For an ellipse centered at , the four symmetric points plotted on the raster display are , , , and .

Vital Significance in Raster Graphics:

  1. Computational Reduction: Instead of scanning all around the perimeter, the algorithm only computes pixel coordinates in the first quadrant (). This reduces trigonometric/incremental floating-point evaluations by 75% (a speedup).
  2. Memory and Cache Efficiency: Fewer calculations allow inner rasterization loops to execute with minimal integer additions and shifts.

Division into Regions by Curve Slope: In the first quadrant, the tangent slope of the ellipse is:

The quadrant is partitioned into two distinct sampling regions:

Midpoint Ellipse Algorithm Derivation for Region 1: Starting at the top vertex : The midpoint between candidate pixels and is evaluated in :

At each step :

Continue while .

Midpoint Ellipse Algorithm Derivation for Region 2: At the boundary between Region 1 and Region 2 with last position , the initial decision parameter for Region 2 is:

At each step :

Continue until .

Complete Algorithmic Steps:

  1. Input center coordinates and semi-axes .
  2. Initialize starting point in Region 1: .
  3. Compute initial parameter: .
  4. While :
    • Plot 4 symmetric points: .
    • .
    • If : .
    • Else: ; .
  5. Initialize Region 2 using last :
  1. While :
    • Plot 4 symmetric points: .
    • .
    • If : .
    • Else: ; .
Answer:

Four-quadrant symmetry allows computing only the first quadrant () and reflecting to the other three quadrants, cutting computational workload by . The Midpoint Ellipse algorithm segments the first quadrant into Region 1 (, stepping ) and Region 2 (, stepping ), updating integer decision parameters and incrementally.

All past exam questions for Computer Graphics and Visualization