Past exam question: 2082 Kartik (Back), Q2(a)
Open in the Padhaiko appHow 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:
- Quadrant I:
- Quadrant II:
- Quadrant III:
- Quadrant IV:
For an ellipse centered at , the four symmetric points plotted on the raster display are , , , and .
Vital Significance in Raster Graphics:
- 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).
- 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:
- Region 1: , which occurs when . The curve is flatter; we step along the -axis in unit increments () and choose between and .
- Region 2: , which occurs when . The curve is steeper; we step along the -axis in unit decrements () and choose between and .
Midpoint Ellipse Algorithm Derivation for Region 1: Starting at the top vertex : The midpoint between candidate pixels and is evaluated in :
At each step :
- If : choose (midpoint is inside curve).
- If : choose (midpoint is outside or on curve).
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 :
- If : choose (midpoint is outside curve).
- If : choose (midpoint is inside or on curve).
Continue until .
Complete Algorithmic Steps:
- Input center coordinates and semi-axes .
- Initialize starting point in Region 1: .
- Compute initial parameter: .
- While :
- Plot 4 symmetric points: .
- .
- If : .
- Else: ; .
- Initialize Region 2 using last :
- While :
- Plot 4 symmetric points: .
- .
- If : .
- Else: ; .
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