PadhaikoAll subjects

Mid-Point Circle & Ellipse Algorithms

Computer Graphics and Visualization (ENCT 201)

Open in the Padhaiko app

2.3 Rasterizing a Circle and an Ellipse: Midpoint Circle & Ellipse Algorithms

Rasterizing second-order planar curves (conic sections such as circles and ellipses) introduces non-linear geometric properties that do not exist in line-drawing. A continuous circle of radius centered at origin is defined by the implicit Cartesian equation:

Inefficiencies of Direct Formulation Methods

Two direct analytical methods might initially be considered for rasterizing a circle, but both possess severe computational drawbacks:

  1. Explicit Cartesian Equation ():
    • Stepping in unit increments from to requires computing a square root and multiplication at every step:
  1. Polar Parametric Equations ():
    • Stepping the angle from to at step size produces relatively uniform pixel spacing.
    • However, evaluating trigonometric sine and cosine functions at each step requires floating-point calculations or large trigonometric look-up tables, making the method too slow for real-time graphics pipelines.

The optimal engineering solution is the Midpoint Circle Algorithm, an incremental, integer-only rasterization method based on evaluating an implicit decision parameter.

Eight-Way Symmetry of a Circle

A circle centered at the origin exhibits eight-fold reflectional symmetry across four lines: the horizontal axis (), the vertical axis (), and the two diagonal axes ( and ).

                      y
                      │  (x, y)  Octant 1 (90° to 45°)
           (-y, x)    │    •
              •       │       • (y, x)
                      │
   ───────────────────┼─────────────────── x
                      │
              •       │       • (y, -x)
           (-y, -x)   │    •
                      │  (x, -y)
Definition

Eight-Way Symmetry

Because of 8-way symmetry, we only need to compute the pixel coordinates for one octant of the circle—specifically the first octant in the first quadrant, extending from to (an angular span from down to , where the slope ranges from to ).

For any calculated point in this octant, the remaining seven symmetric points on the circle are obtained directly by sign inversion and coordinate transposition:

For a circle centered at an arbitrary point , the eight symmetric screen pixels are obtained by translation:

This property reduces the computational workload of circle generation by (an reduction).

Mathematical Derivation of the Midpoint Circle Algorithm

Consider the circle centered at origin with radius . The implicit circle function is:

This function evaluates the position of any arbitrary point relative to the circular boundary:

Candidate Pixel Selection

We begin rasterization at the top apex and move clockwise through the first octant. In this region, the slope of the curve satisfies . At each step , having plotted pixel , advancing by means the true circle boundary lies between two candidate pixels:

        y_k ──────────────────• E (x_k + 1, y_k)
                              │
                              x M (x_k + 1, y_k - 1/2)  <-- Midpoint
                              │
    y_k - 1 ──────────────────• SE (x_k + 1, y_k - 1)
                              x_k + 1

The algorithm evaluates the implicit circle function at the exact geometric midpoint between these two candidate pixels:

The decision parameter is defined as:

Decision Rule

Incremental Parameter Updates

At step , the decision parameter evaluated at the next midpoint is:

Subtracting from :

Using :

  1. Case 1 (, chose pixel , so ):
  1. Case 2 (, chose pixel , so ):

Adding these terms:

Initial Decision Parameter ()

Starting at the initial apex , the first midpoint is evaluated at :

Bresenham's Circle Drawing Algorithm

Historically, Bresenham formulated a circle rasterization algorithm based on minimizing the difference between the squared distances of candidate pixels to the circle center.

Theorem

Bresenham's Circle Algorithm Formulation

Starting at , the initial decision parameter is:

At each step :

Iterate until .

AspectMidpoint Circle AlgorithmBresenham's Circle Algorithm
Initial Parameter (integer form of )..
Update when ..
Update when ..
Mathematical Relationship (or ).Exactly double the midpoint parameter scale.
Plotted PixelsIdentical pixel sequence for any given radius .Identical pixel sequence for any given radius .

Midpoint Ellipse Algorithm

An ellipse centered at origin with semi-major axis and semi-minor axis is defined by the implicit equation:

Four-Way Symmetry

Because only even powers of and appear in , an origin-centered ellipse possesses four-way symmetry across the coordinate axes:

For center , the four symmetric screen pixels are:

Division into Two Sampling Regions

Differentiating the implicit equation yields the tangent slope along the ellipse:

The first quadrant is partitioned into two distinct sampling regions separated by the boundary where the tangent slope is ():

    y
    │  Region 1: |dy/dx| < 1  (Step x by +1)
r_y •────.
    │     \
    │      \  Boundary: 2 r_y² x = 2 r_x² y  (Slope = -1)
    │       \
    │        \  Region 2: |dy/dx| >= 1  (Step y by -1)
    │         \
    └──────────•──── x
              r_x

Region 1 Derivation

Starting at top vertex , we test the midpoint between and :

Initial parameter at :

Incremental updates:

Region 1 terminates when .

Region 2 Derivation

Let the last point determined in Region 1 be . In Region 2, we step by and choose between and . The midpoint is . The decision parameter is:

Initial parameter at :

Incremental updates:

Region 2 terminates when .


Worked Examples

Example 1

Midpoint Circle Rasterization with Radius r = 8

Rasterize a circle with radius and center at using the Midpoint Circle Algorithm.

  1. Determine the initial decision parameter .
  2. Compute the complete iteration table for the first octant until .
  3. Apply 8-way symmetry to map the octant points to the circle centered at .

Initial Decision Parameter Calculation: Given radius :

  • Initial point in the first octant: .
  • Initial decision parameter:

Iteration Table for First Octant: At each step :

  • If : choose , and .
  • If : choose , and .
Midpoint Circle Trace (r = 8)Generated by running the algorithm
kpxy
0-718

The loop terminates at step because . The origin-centered first-octant coordinates are:

Midpoint Circle (r = 8) -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
Midpoint Circle (r = 8)

Eight-Way Symmetry Translation to Center (15, 20): Adding to and :

  • Point
  • Point
  • Point
  • Point
  • Point
  • Point
Answer:
  1. Initial parameter: .
  2. Origin-centered first-octant pixels:
  1. Applying 8-way symmetry translated by generates all boundary pixels around the circle.
Example 2

Midpoint Ellipse Rasterization with rx = 8, ry = 6

Rasterize an ellipse centered at origin with semi-major axis and semi-minor axis using the Midpoint Ellipse Algorithm.

  1. Determine initial decision parameters and .
  2. Tabulate all iterations across Region 1 and Region 2.

Region 1 Setup and Initial Parameter: Given and :

Initial position at . Initial parameter for Region 1:

We step by while .

Midpoint Ellipse Trace across Region 1 and Region 2: The algorithm generates the following execution trace:

Midpoint Ellipse Trace (rx = 8, ry = 6)Generated by running the algorithm
regionkpxy2ry²x2rx²y
10-3321672768

Region 1 concludes at where . The initial parameter for Region 2 evaluated at is:

Region 2 decrements until , concluding at .

Midpoint Ellipse (rx = 8, ry = 6) -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6
Midpoint Ellipse (rx = 8, ry = 6)
Answer:
  1. Initial parameters: , .
  2. The first-quadrant pixel coordinates generated are:
Example 3

Bresenham Circle Drawing Algorithm with Radius r = 7

Rasterize a circle of radius centered at using Bresenham's circle drawing algorithm (). Tabulate all decision parameter calculations and compare the generated pixel path with the Midpoint Circle Algorithm.

Initial Decision Parameter: Given radius : Starting pixel: . Initial decision parameter:

Bresenham Iterations for First Octant: At each step :

  • If : choose , and .
  • If : choose , and .
Chosen Calculation
0 ()
1 ()
2 ()
3 ()
4 ()

The loop terminates because . The resulting first-octant pixels are:

Comparison with the Midpoint Circle Algorithm: Evaluating the Midpoint Circle Algorithm for :

  • .
  • Successive values: .
  • Pixels selected: .

The chosen pixel coordinates are identical in both algorithms. Bresenham's parameter values are exactly related to midpoint parameters by .

Answer:
  1. Initial parameter: .
  2. The generated first-octant pixels are:
  1. Both Bresenham's and Midpoint circle algorithms select the exact same pixel sequence.

Exercises

Midpoint Circle & Ellipse Algorithm Exercises

Question 1

Rasterize a circle of radius centered at using the Midpoint Circle Algorithm. Determine all origin-centered first-octant pixel coordinates, and map them to center using 8-way symmetry.

First Octant Calculations: Initial conditions for :

Iterating until :

  • : ;
  • : ;
  • : ;
  • : ;

Termination condition is reached. The first-octant points relative to origin are:

Applying 8-Way Symmetry and Translating to (5, 5): Adding to and :

Answer:

First-octant origin points are . Translating by using 8-way symmetry generates the complete circle raster boundary.

Question 2

Derive the Midpoint Circle Algorithm's initial decision parameter from the continuous midpoint evaluation . Explain why replacing with yields identical pixel selections.

Continuous Midpoint Evaluation: The implicit circle equation is . At the top apex , stepping to places the midpoint between and at . Evaluating :

Sign Equivalence for Integer Radii: In the Midpoint Circle Algorithm, the decision rule depends solely on whether is negative () or non-negative (). For any integer radius :

  • If : , while . Both choose .
  • If : , and . Both choose .

Since all incremental update terms ( and ) are strictly integers, the fractional part is never accumulated or altered. Setting shifts the continuous curve by exactly , which never crosses zero between any integer step evaluations. Thus, integer arithmetic is preserved without changing any pixel selection.

Answer:

tests whether the midpoint is inside the circle. For all integer radii , , guaranteeing identical integer decision paths.

Question 3

Apply the Midpoint Ellipse Algorithm for an ellipse with and centered at . Trace all iterations in Region 1 and identify the boundary point where the algorithm transitions into Region 2.

Region 1 Constants and Initial Parameter: Given :

Starting position: . Initial decision parameter:

Region 1 Iterations: Condition for Region 1: .

  • : (). . .
  • : (). . .
  • : (). . .
  • : (). . .
  • : (). . .
  • Check boundary condition at :

Since , Region 1 terminates.

Answer:

Region 1 generates pixels . The transition to Region 2 occurs at point where .

Question 4

Compare the 8-way symmetry of a circle with the 4-way symmetry of an ellipse. Explain why an ellipse cannot utilize 8-way symmetry to accelerate rasterization.

Symmetry Planes of a Circle: A circle centered at the origin is invariant under reflection across the coordinate axes () as well as the diagonal bisectors (). Swapping and preserves the equation:

Therefore, determining pixels in a single octant ( to ) is sufficient to generate the remaining seven octants.

Symmetry Planes of an Ellipse: An ellipse aligned with the coordinate axes satisfies . Because and appear as squared terms, , granting 4-way symmetry across the two principal axes. However, because , transposing coordinates alters the equation:

Reflecting across produces a point that lies on a rotated ellipse rather than the original curve. Thus, rasterization cannot be restricted to an octant and must evaluate the entire first quadrant.

Answer:

A circle is symmetric across diagonal lines because , allowing 8-way symmetry. An ellipse has unequal axes (), so reflection across diagonals changes the curve equation, restricting symmetry to the 4 quadrants.

Question 5

Trace Bresenham's circle drawing algorithm for a radius from to . Show initial parameter , decision tests, and all plotted coordinates.

Initial Conditions: Given radius : Starting point: . Initial decision parameter:

Step-by-Step Bresenham Iterations:

  • : plot ; .
  • : plot ; .
  • : plot ; .
  • : plot ; .
  • : plot ; .
  • : plot ; .
  • : plot ; termination because .
Answer:

The generated first-octant pixels are:

Question 6

Explain why the Midpoint Ellipse Algorithm must be partitioned into two distinct sampling regions. Derive the mathematical condition that dictates the transition from Region 1 to Region 2.

Slope Variation along the Ellipse Perimeter: In the first quadrant of an ellipse, the curve starts at with a horizontal tangent () and ends at with a vertical tangent ().

  • Where the curve is gentle (), stepping by ensures that changes by at most pixel, producing a continuous raster without gaps.
  • Where the curve becomes steep (), stepping by would cause to jump by more than unit, leaving visible unilluminated gaps in the rasterized ellipse.

Derivation of the Region Transition Boundary: Differentiating the implicit equation with respect to :

The transition between gentle and steep slope occurs where the magnitude of the slope equals :

  • Region 1: ( is driving axis; increments by ).
  • Region 2: ( is driving axis; decrements by ).
Answer:

Partitioning into two regions ensures continuous, gap-free rasterization by stepping along the coordinate axis with the smaller rate of change. The transition occurs at slope , corresponding to the condition .

Past exam questions for Computer Graphics and Visualization

← Rasterizing Points & Lines: DDA and BresenhamScan-Line, Boundary & Flood Fill →