Fundamental Drawing Algorithms

Chapter 5: Fundamental Drawing Algorithms

To render shapes on a raster display, we need algorithms that determine which pixels should be "on" to represent a geometric primitive. This process is called scan conversion or rasterization.

Line Drawing Algorithms

A line connects two points: (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2). The equation of a line is y=mx+cy = mx + c, where mm is the slope (m=y2−y1x2−x1m = \frac{y_2 - y_1}{x_2 - x_1}).

DDA (Digital Differential Analyzer)

The DDA algorithm is a simple incremental method for scan conversion of lines.

  1. Calculate dx=x2−x1dx = x_2 - x_1 and dy=y2−y1dy = y_2 - y_1.
  2. The number of steps is steps=max⁡(∣dx∣,∣dy∣)steps = \max(|dx|, |dy|).
  3. Calculate the increment for each step: xinc=dxstepsx_{inc} = \frac{dx}{steps} and yinc=dystepsy_{inc} = \frac{dy}{steps}.
  4. In each step, increment xx and yy and plot round(x), round(y).
  • Pros: Simple to implement.
  • Cons: Requires floating-point operations and rounding, which are slower than integer arithmetic.

Bresenham's Line Algorithm

Bresenham's algorithm is a more efficient line-drawing method that uses only integer arithmetic. It determines the pixel coordinates by considering the error between the true line and the discrete pixel positions.

For a slope 0<m<10 < m < 1:

  1. Initialize x=x1x = x_1, y=y1y = y_1, dx=x2−x1dx = x_2 - x_1, dy=y2−y1dy = y_2 - y_1.
  2. The decision parameter P0=2dy−dxP_0 = 2dy - dx.
  3. For each xkx_k from x1x_1 to x2x_2:
    • If Pk<0P_k < 0: The next pixel is (xk+1,yk)(x_k + 1, y_k) and Pk+1=Pk+2dyP_{k+1} = P_k + 2dy.
    • Else: The next pixel is (xk+1,yk+1)(x_k + 1, y_k + 1) and Pk+1=Pk+2dy−2dxP_{k+1} = P_k + 2dy - 2dx.
  • Pros: Fast, integer-only, highly efficient for hardware implementation.
Bresenham's Integer Approximation

Circle Drawing Algorithms

Drawing a circle is more complex because it's non-linear. The equation is x2+y2=R2x^2 + y^2 = R^2.

Midpoint Circle Algorithm

This algorithm uses the symmetry of a circle. We only need to calculate the points for one octant (45°) and then reflect them across the other seven.

  1. Initialize x=0x = 0, y=Ry = R.
  2. Initial decision parameter P0=54−RP_0 = \frac{5}{4} - R (or 1−R1 - R for integer-only).
  3. While x<yx < y:
    • Plot (x,y)(x, y) in all 8 octants.
    • If Pk<0P_k < 0: xk+1=xk+1x_{k+1} = x_k + 1, yk+1=yky_{k+1} = y_k, Pk+1=Pk+2xk+1+1P_{k+1} = P_k + 2x_{k+1} + 1.
    • Else: xk+1=xk+1x_{k+1} = x_k + 1, yk+1=yk−1y_{k+1} = y_k - 1, Pk+1=Pk+2xk+1+1−2yk+1P_{k+1} = P_k + 2x_{k+1} + 1 - 2y_{k+1}.
Calculated Octant

Ellipse Drawing Algorithm

The Midpoint Ellipse Algorithm is similar to the circle algorithm but more complex because an ellipse has two radii (RxR_x and RyR_y) and no 8-way symmetry (only 4-way).

  1. The algorithm is divided into two regions based on the slope of the curve.
  2. Region 1: The slope is less than 1. We increment xx and decide whether to decrement yy.
  3. Region 2: The slope is greater than 1. We decrement yy and decide whether to increment xx.

Summary

Algorithms like DDA and Bresenham's are the "foundation stones" of 2D graphics. While modern GPUs handle these tasks in hardware, understanding the underlying math is crucial for anyone working in low-level graphics or specialized rendering systems. Bresenham's focus on integer-only operations remains a hallmark of efficient computer graphics design.

PreviousNext Chapter