Computer Graphics Algorithms for Lines, Circles, and Curves

In computer graphics, output primitives are the basic geometric structures used to describe and construct images. The simplest primitives are Points and Lines. Before these primitives can be displayed on a screen, they must undergo scan conversion—the process of digitizing a continuous geometric shape into a discrete grid of screen pixels.

Points and Lines

Points

A point is a zero-dimensional geometric object. In a digital system, a point is represented by an ordered pair of coordinates (X, Y). To display a point, the graphics control system locates the corresponding row and column address in the frame buffer and sets its intensity or color value.

Lines

A line is a one-dimensional geometric object defined by two endpoints: (X₁, Y₁) and (X₂, Y₂). The ideal mathematical equation of a straight line is:

y = mx + c

Where:

• m is the slope of the line: m = (Y₂ - Y₁) / (X₂ - X₁) = ΔY / ΔX
• c is the Y-intercept: c = Y₁ - m · X₁

Because screen pixels are arranged in an integer grid, a line-drawing algorithm must figure out which discrete pixels best approximate the true path of the ideal mathematical line.

DDA Line Drawing Algorithm

The DDA (Digital Differential Analyzer) Algorithm is an incremental conversion method. It calculates pixel positions by utilizing the step variations ΔX or ΔY from the previous pixel coordinate.

The Logic

Depending on the slope m of the line, we increment one coordinate by 1 unit and calculate the corresponding fractional increment for the other coordinate:

• Case 1: If |m| < 1 (Line is closer to horizontal)
  We step through X by 1 unit increments (ΔX = 1), and calculate the next Y value as: Y_k+1 = Y_k + m
• Case 2: If |m| > 1 (Line is closer to vertical)
  We step through Y by 1 unit increments (ΔY = 1), and calculate the next X value as: X_k+1 = X_k + 1/m

DDA Algorithm Steps

1. Input the two endpoints (X₁, Y₁) and (X₂, Y₂).
2. Calculate ΔX = X₂ - X₁ and ΔY = Y₂ - Y₁.
3. Determine the number of steps required: Steps = max(|ΔX|, |ΔY|).
4. Calculate the incremental step sizes for both coordinates: X_inc = ΔX / Steps and Y_inc = ΔY / Steps.
5. Put the initial pixel on the screen by rounding to the nearest integer: draw_pixel(round(X), round(Y)).
6. Loop for the total number of steps:
   • X = X + X_inc
   • Y = Y + Y_inc
   • draw_pixel(round(X), round(Y))

Limitation of DDA: It requires floating-point additions and a time-consuming round() operation at every single step, making it computationally expensive for real-time graphics hardware.

Bresenham’s Line Algorithm

Bresenham’s Line Algorithm is a highly efficient scan-conversion method. It avoids floating-point math completely, relying solely on integer addition, subtraction, and bit-shifting, which can be executed directly at the hardware layer.

The Logic

For a line with a slope 0 < m < 1, the algorithm increments X by 1 at each step. To determine the next Y coordinate, it tests whether the ideal line is closer to the current pixel level (Y_k) or the upper level (Y_k + 1). This choice is governed by a Decision Parameter (P_k).

Bresenham’s Algorithm Steps (for 0 < m < 1)

1. Input the two endpoints (X₁, Y₁) and (X₂, Y₂), and ensure X₁ < X₂.
2. Plot the first point (X₁, Y₁).
3. Calculate constants: ΔX = X₂ - X₁, ΔY = Y₂ - Y₁, 2ΔY, and 2ΔY - 2ΔX.
4. Calculate the initial decision parameter P₀ = 2ΔY - ΔX.
5. At each X_k along the line, starting at k = 0, perform the following test:
   • If P_k < 0: The next pixel to plot is (X_k + 1, Y_k) and P_k+1 = P_k + 2ΔY.
   • If P_k ≥ 0: The next pixel to plot is (X_k + 1, Y_k + 1) and P_k+1 = P_k + 2ΔY - 2ΔX.

Circle Drawing Algorithms

A circle is defined by the geometric equation: (X - X_c)² + (Y - Y_c)² = R², where (X_c, Y_c) is the center position and R is the radius. To make drawing efficient, algorithms calculate pixel positions for a circle centered at the origin (0,0) and then shift the coordinates by adding X_c and Y_c.

The Polynomial Method

The Polynomial Method uses the standard algebraic equation of a circle to solve for Y at each integer step of X.

The Logic

For a circle centered at (0,0), we solve for Y: Y = ±√(R² - X²). We step X from 0 to R in unit increments and calculate the corresponding integer value for Y.

Limitations

• Heavy Calculations: Requires a square root and squaring operations at every single step, making it extremely slow.
• Uneven Pixel Spacing: As X approaches R, the slope of the circle approaches infinity. This leaves wide, un-plotted vertical gaps between pixels along the sides of the circle, creating an uneven look.

Bresenham’s Circle Algorithm (Midpoint Method)

Bresenham’s circle algorithm avoids floating-point operations and square roots entirely by working incrementally. It leverages eight-way symmetry. If we calculate the coordinates for just one octant (a 45° slice from X = 0 to X = Y), we can instantly plot the pixels for the remaining seven octants by swapping signs and positions.

Mathematical Derivation

Assuming we just plotted pixel (X_k, Y_k) in the first octant, our next pixel choice is between:

• East pixel: E = (X_k + 1, Y_k)
• South-East pixel: SE = (X_k + 1, Y_k - 1)

We evaluate the midpoint between these two choices: M = (X_k + 1, Y_k - 1/2). We plug this midpoint into the circle function f(X,Y) = X² + Y² - R² to get our Decision Parameter (P_k):

• If P_k < 0: The midpoint lies inside the true circle boundary, meaning the East pixel (E) is closer. Select Y_k+1 = Y_k and P_k+1 = P_k + 2X_k+1 + 1.
• If P_k ≥ 0: The midpoint lies outside or on the boundary, meaning the South-East pixel (SE) is closer. Select Y_k+1 = Y_k - 1 and P_k+1 = P_k + 2X_k+1 + 1 - 2Y_k+1.

Initial Decision Parameter

Starting at the top of the circle (0, R), the initial decision parameter evaluates directly to: P₀ = 5/4 - R (or 1 - R for integer simplification).

Curves in Computer Graphics

When drawing smooth, complex, non-linear shapes that cannot be described by simple circles or lines, we turn to spline curves.

Parametric Representation of Cubic Curves

Using an explicit equation like Y = f(X) falls short for complex curves because it cannot easily handle vertical lines or self-overlapping loops. Instead, computer graphics relies on parametric equations, where both X and Y are computed independently as functions of a parameter u that ranges from 0 to 1.

A Cubic Polynomial Curve uses a third-degree polynomial expression because it provides enough flexibility to create smooth, winding shapes while keeping calculation costs reasonable. In matrix notation, a 3D point vector along the curve is expressed as: P(u) = U · C, where U = [u³ u² u 1] and C is the algebraic coefficient matrix.

Bézier Curves

Developed by Pierre Bézier for automotive design, Bézier Curves are foundational tools in modern digital vector graphics. Instead of forcing a curve to pass through points directly, it is shaped by Control Points (P₀, P₁, ..., P_n). The curve acts like a flexible string pulled toward these points, forming a convex hull.

Mathematical Formulation

The path of a Bézier curve of degree n is defined as the weighted sum of its control points multiplied by Bernstein Polynomials, which act as blending functions.

Cubic Bézier Curves (n = 3)

The most widely used variation handles four control points:

• P₀: The exact starting vertex point of the curve (u=0).
• P₁, P₂: Intermediate steering points that guide the directional tangent vectors.
• P₃: The exact termination vertex point of the curve (u=1).

Key Properties of Bézier Curves

1. Convex Hull Property: The entire curve is guaranteed to lie completely inside the polygon formed by its control points, making collision detection efficient.
2. Affine Invariance: If you scale, rotate, or translate the control points, the resulting curve transforms uniformly without needing recalculation.
3. Variation Diminishing Property: The curve is smooth and well-behaved; it will never oscillate more times than the straight lines connecting its control polygon points.