Midpoint Ellipse Algorithm & 4-Way Symmetry

Two-Region Conic Rasterization

An ellipse is an altered conic section defined by two radii: a semi-major axis $r_x$ and a semi-minor axis $r_y$. Because the curvature of an ellipse varies non-uniformly across its perimeter, simple 8-way octant symmetry cannot be applied; instead, rasterization relies on 4-way quadrant symmetry. Furthermore, because the tangent slope $dy/dx$ varies from $0$ to $-\infty$ within a single quadrant, the scan conversion domain must be bifurcated into two distinct operational regions separated by the boundary where $|dy/dx| = 1$. In this article, we rigorously analyze the Midpoint Ellipse Algorithm, derive both region decision parameters, and examine its integer implementation.

1. Implicit Ellipse Function & 4-Way Symmetry

An ellipse centered at the origin $(0, 0)$ with horizontal semi-major radius $r_x$ and vertical semi-minor radius $r_y$ satisfies the standard implicit algebraic form:

F(x, y) = r_y^2 \cdot x^2 + r_x^2 \cdot y^2 - r_x^2 \cdot r_y^2 = 0

In an ellipse, reflection across both coordinate axes yields 4-way quadrant symmetry:

(x, y) \iff (-x, y) \iff (-x, -y) \iff (x, -y)

Thus, rasterizing the first quadrant from $(0, r_y)$ to $(r_x, 0)$ completely determines all four quadrants through coordinate negation.

2. Two-Region Boundary Condition

Calculating the implicit derivative $\frac{dy}{dx}$ gives:

\frac{dy}{dx} = -\frac{2 r_y^2 x}{2 r_x^2 y}

The quadrant is partitioned into two regions based on the absolute slope $|dy/dx|$:

Region 1: $|dy/dx| < 1$

Condition: $2 r_y^2 x < 2 r_x^2 y$. The curve is flatter. We step along the $x$-axis in unit increments: $\Delta x = +1$. The candidate pixels are East $(x_k + 1, y_k)$ and South-East $(x_k + 1, y_k - 1)$.

Region 2: $|dy/dx| \ge 1$

Condition: $2 r_y^2 x \ge 2 r_x^2 y$. The curve is steeper. We step along the $y$-axis in unit decrements: $\Delta y = -1$. The candidate pixels are South $(x_k, y_k - 1)$ and South-East $(x_k + 1, y_k - 1)$.

3. Region 1 Decision Parameter Formulation

Evaluating the implicit ellipse function at the midpoint $M = (x_k + 1, y_k - \frac{1}{2})$:

P1_k = F\left(x_k + 1, y_k - \frac{1}{2}\right) = r_y^2 (x_k + 1)^2 + r_x^2 \left(y_k - \frac{1}{2}\right)^2 - r_x^2 r_y^2

At the starting point $(x_0, y_0) = (0, r_y)$, the initial decision parameter for Region 1 is:

P1_0 = r_y^2 - r_x^2 r_y + \frac{1}{4} r_x^2

If $P1_k < 0$: Midpoint is inside. Select East $(x_k + 1, y_k)$.
P1_{k+1} = P1_k + 2 r_y^2 x_{k+1} + r_y^2
If $P1_k \ge 0$: Midpoint is outside. Select South-East $(x_k + 1, y_k - 1)$.
P1_{k+1} = P1_k + 2 r_y^2 x_{k+1} - 2 r_x^2 y_{k+1} + r_y^2

4. Region 2 Decision Parameter Formulation

In Region 2, the midpoint is $M = (x_k + \frac{1}{2}, y_k - 1)$. The decision parameter is:

P2_k = F\left(x_k + \frac{1}{2}, y_k - 1\right) = r_y^2 \left(x_k + \frac{1}{2}\right)^2 + r_x^2 (y_k - 1)^2 - r_x^2 r_y^2

The initial parameter $P2_0$ is evaluated at the last point $(x_e, y_e)$ calculated in Region 1:

P2_0 = r_y^2 \left(x_e + \frac{1}{2}\right)^2 + r_x^2 (y_e - 1)^2 - r_x^2 r_y^2

If $P2_k > 0$: Midpoint is outside. Select South $(x_k, y_k - 1)$.
P2_{k+1} = P2_k - 2 r_x^2 y_{k+1} + r_x^2
If $P2_k \le 0$: Midpoint is inside. Select South-East $(x_k + 1, y_k - 1)$.
P2_{k+1} = P2_k + 2 r_y^2 x_{k+1} - 2 r_x^2 y_{k+1} + r_x^2