# 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

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.

## 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}
```

## 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.

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);

```
```

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