Title: Midpoint Ellipse Drawing Algorithm in Computer Graphics
Objective
To implement the Midpoint Ellipse Drawing Algorithm in computer graphics, enabling
efficient ellipse rendering using integer calculations and region-based decision
parameters.
Theory
In computer graphics, drawing ellipses requires careful calculation due to their non-
uniform curvature. The Midpoint Ellipse Drawing Algorithm divides the ellipse into two
regions to simplify the calculation process. Using decision parameters and symmetry, it
calculates pixel positions without floating-point arithmetic. The algorithm takes
advantage of the ellipse’s symmetry about both axes, allowing only one quadrant to be
calculated and mirrored into the others. It uses the general equation of an ellipse: (x²/a²) +
(y²/b²) = 1.
Algorithm
Step 1: Input center (xc, yc), and radii a (x-axis), b (y-axis).
Step 2: Initialize x = 0, y = b.
Step 3: Compute initial decision parameter for Region 1:
p1 = b² - a²b + (1/4)a²
Step 4: While (2b²x <= 2a²y), do:
- Plot symmetric points.
- If p1 < 0, x++, p1 = p1 + 2b²x + b²
- Else, x++, y--, p1 = p1 + 2b²x - 2a²y + b²
Step 5: Compute initial decision parameter for Region 2:
p2 = b²(x + 0.5)² + a²(y - 1)² - a²b²
Step 6: While (y >= 0), do:
- Plot symmetric points.
- If p2 > 0, y--, p2 = p2 - 2a²y + a²
- Else, x++, y--, p2 = p2 + 2b²x - 2a²y + a²
Step 7: Stop.
Code (C Language)
#include <stdio.h>
#include <graphics.h>
void drawEllipsePoints(int xc, int yc, int x, int y) {
putpixel(xc + x, yc + y, WHITE);
putpixel(xc - x, yc + y, WHITE);
putpixel(xc + x, yc - y, WHITE);
putpixel(xc - x, yc - y, WHITE);
}
void midpointEllipse(int xc, int yc, int rx, int ry) {
int x = 0;
int y = ry;
// Initial decision parameter of region 1
long long rxSq = (long long)rx * rx;
long long rySq = (long long)ry * ry;
long long twoRxSq = 2 * rxSq;
long long twoRySq = 2 * rySq;
long long px = 0;
long long py = twoRxSq * y;
// Region 1
long long p = rySq - (rxSq * ry) + (0.25 * rxSq);
while (px < py) {
drawEllipsePoints(xc, yc, x, y);
x++;
px += twoRySq;
if (p < 0) {
p += rySq + px;
} else {
y--;
py -= twoRxSq;
p += rySq + px - py;
}
delay(20);
}
// Region 2
p = rySq * (x + 0.5) * (x + 0.5) + rxSq * (y - 1) * (y - 1) - rxSq * rySq;
while (y >= 0) {
drawEllipsePoints(xc, yc, x, y);
y--;
py -= twoRxSq;
if (p > 0) {
p += rxSq - py;
} else {
x++;
px += twoRySq;
p += rxSq - py + px;
}
delay(20);
}
}
int main() {
int gd = DETECT, gm;
initgraph(&gd, &gm, NULL);
printf("Ellipse drawing alogrithm by lokesh yadav \n");
int xc, yc, rx, ry;
printf("Enter center of the ellipse (xc yc): ");
scanf("%d %d", &xc, &yc);
printf("Enter radius along x-axis (rx): ");
scanf("%d", &rx);
printf("Enter radius along y-axis (ry): ");
scanf("%d", &ry);
outtextxy( 20, 20,(char *) "Lokesh Yadav");
midpointEllipse(xc, yc, rx, ry);
delay(50000);
closegraph();
return 0;
}
Output
Discussion
The Midpoint Ellipse Drawing Algorithm was implemented to explore how complex
curves like ellipses can be drawn using basic integer arithmetic and logical control. By
dividing the ellipse into two regions based on the slope and leveraging its symmetry, the
algorithm simplifies calculations while ensuring efficient and accurate plotting.
While the algorithm is fast and suitable for real-time graphics due to its use of only
integer operations, the implementation faced challenges. A major limitation was the
reliance on the outdated graphics.h library, which requires legacy environments like
Turbo C++ or DOSBox to run. Additionally, the absence of anti-aliasing led to jagged
edges in the rendered ellipse.
Despite these issues, careful handling of the decision parameters and symmetry logic
helped maintain curve accuracy. The practical ultimately enhanced understanding of
pixel-based drawing techniques and emphasized the importance of transitioning to
modern graphics libraries for better performance and compatibility.
Conclusion
This program effectively demonstrates the use of the Midpoint Ellipse Drawing
Algorithm. By splitting the curve into two regions and applying decision-based plotting,
it produces a complete ellipse with minimal calculations. Despite using the older
`graphics.h` library, the algorithm remains a fundamental technique in understanding how
computer graphics handles complex shapes like ellipses.