Scan Conversion: Drawing a Straight Line

General Theory

The general problem of scan conversion is which pixels to turn on. For example, assume a line with positive slope in the first octant, i.e., 0.0 <= m <= 1.0.

and drawn from left to right: (X1, Y1) to (X2, Y2):

The problem is that as we increment xi to xi+1, do we turn on xi+1, yi or xi+1, yi+1?

The general goal is to minimize the stair-step effect (jaggies), have a uniform line density, and require the minimum drawing time. Remember, we must always round or truncate to integers since pixels are at integer positions.

Floating Point Algorithms

Digital Differential Analyzer (DDA) method

Bresenham (Decision Variable) method

Point and Line Drawing Commands

Demonstration Program for scan converting lines


Floating Point Algorithms

The equation for a straight line: y = m * x + b, where m is the slope (m = dy/dx) and b is the y intercept. So for a given x interval (dx) we can compute dy = m * dx, but this is a brute force real number computation and is very slow.

Alternative Method - Parametric Equations

For a line segment x1, y1 -> x2, y2:

x = x1 + t*dx with dx = x2 - x1 and 0.0 <= t <= 1.0

So start with t = 0 and increment to t = 1.0, e.g. t= .05, .10,.15, etc. This is still too slow but parametric equations are used for clipping, curve fitting, and ray tracing.

Return to menu


Digital Differential Analyzer (DDA) Method

The basis of the DDA method is to take unit steps along one coordinate and compute the corresponding values along the other coordinate. The unit steps are always along the coordinate of greatest change, e.g. if dx = 10 and dy = 5, then we would take unit steps along x and compute the steps along y.

Let us assume a line of positive slope and draw from x1, y1 to x2, y2.

{slope = m = dy/dx}

if m <= 1.0 then

  let x_step = 1 {dx = 1, dy = 0 or 1}
else {m > 1.0}
  let y_step = 1 {dy = 1, x_step = 0 or 1 }

Remember: always step along the longest delta.

{m <= 1.0} for x_step = 1, dy = m = yi+1 - yi -> yi+1 = yi + m

{m > 1} for y_step = 1 m = 1/dx => dx = 1/m => xi+1 = xi + 1/m

If, instead, we draw from x2 , y2 to x1, y1 then:
a.) dx = -1 yi+1 = yi -m or
b.) dy = -1 xi+1 = xi - 1/m

For a line with slopeslope < 0.0 and drawing from x1, y1 to x2, y2, i.e., left to right then:

if |m| < 1 then
 let dx = 1 and yi+1 = yi + m
else {|m|  1}
 let dy = -1 and xi+1 = xi -1/m
if draw from x2, y2 to x1, y1 (right to left) then:
 if |m| < 1 then let dx = -1 yi+1 = yi -m
else {|m|  1} dy = 1 xi+1 = xi + 1/m

Complete DDA Algorithm

procedure DDA( x1, y1, x2, y2: integer);
var
  dx, dy, steps: integer;
  x_inc, y_inc, x, y: real;
begin
  dx := x2 - x1; dy := y2 - y1;
  if abs(dx) > abs(dy) then
     steps := abs(dx); {steps is larger of dx, dy}
  else
     steps := abs(dy);
  x_inc := dx/steps; y_inc := dy/steps;
  {either x_inc or y_inc = 1.0, the other is the slope}
  x:=x1; y:=y1;
  set_pixel(round(x), round(y));
  for i := 1 to steps do
    begin
      x := x + x_inc;
      y := y + y_inc;
      set_pixel(round(x), round(y));
    end;
end; {DDA}

Return to menu


Bresenham (Decision Variable) Method

In this method, developed by Jack Bresenham, we look at just the center of the pixels. We determine d1 and d2 which is the "error", i.e., the difference from the " true line."

Steps in the Bresenham algorithm:

  1. Determine the error terms
  2. Define a relative error term such that the sign of this term tells us which pixel to choose
  3. Derive equation to compute successive error terms from first
  4. Compute first error term

now: y = m(xi+1) + b so

d1 = y - yi = m(xi+1) + b - yi
d2 = (yi+1) - y = yi+1 -m(xi+1) - b

then d1 - d2 = 2m(xi+1) - 2y + 2b -1

now define pi = dx(d1 - d2) = relative error of the two pixels.

note: pi < 0 if yi pixel is closer, pi >= 0 if yi+1 pixel is closer ( = 0 is our choice). Therefore we only need to know the sign of pi .

With m = dy/dx and substituting in for (d1 - d2) we get

(1) pi = 2 * dy * xi - 2 * dx * yi + 2 * dy + dx * (2 * b - 1), let C = 2 * dy + dx * (2 * b - 1)

Now look at the relation of p's for successive x terms.

pi+1 = 2dy * xi+1 - 2 * dx * y i+1 + C
pi+1 - pi = 2 * dy * (xi+1 - xi) - 2 * dx * ( yi+1 - yi)
with xi+1 = xi + 1 and yi+1= yi + 1 or yi

(2) pi+1 = pi + 2 * dy - 2 * dx(yi+1 -yi) Note: b = y - dy / dx * x

Now compute p1 (x1,y1) from (1)

p1 = 2dy * x1 - 2dx * y1 + 2dy + dx(2y1 - 2dy / dx * x1 - 1)
= 2dy * x1 - 2dx * y1 + 2dy + 2dx * y1 - 2dyx1 - dx
= 2dy - dx

if pi < 0 choose yi and pi+1 = pi + 2dy
else {pi 0} and choose yi+1 so pi+1 = pi + 2dy - 2dx

Bresenham Algorithm for 1st octant:

  1. Enter endpoints (x1, y1) and (x2, y2).
  2. Display x1, y1.
  3. Compute dx = x2 - x1 ; dy = y2 - y1 ; p1 = 2dy - dx.
  4. If p1 < 0.0, display x1 + 1, y1, else display x1+1, y1 + 1
  5. if p1 < 0.0, p2 = p1 + 2dy else p2 = p1 + 2dy - 2dx
  6. Repeat steps 4, 5 until reach x2, y2.

Note: Only integer Addition and Multiplication by 2. Notice we always increment x by 1.

For a generalized Bresenham Algorithm must look at behavior in different octants.

Return to menu


Standard Point and Line Drawing Commands

Polyline (n, x, y)

where n = # end points

x = array of x endpoints y = array of y endpoints

So for a single point: n := 1; x(1) := 300; y (1) = 100; polyline(n, x, y);

For a line segment: n := 2; x(1) := 300; y(1) := 100; x(2) := 400; y(2) := 150; polyline(n,x,y);

For a wireframe polygon (closed) the total number of points is the number of vertices plus 1 with the last point equal to the first. So for a triangle:

n := 4;

x(3) := 300; y(3) := 150;

x(4) := 300; y(4) := 100;

polyline(n, x, y);


Return to menu

 

Output Primitives menu
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org