Department of Applied Mathematics and Computational Sciences University of Cantabria UC-CAGD Group

2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

COMPUTER-AIDED GEOMETRIC DESIGN AND COMPUTER GRAPHICS:

LINE DRAWING ALGORITHMS

Andrs Iglesias e-mail: iglesias@unican.es Web pages: http://personales.unican.es/iglesias http://etsiso2.macc.unican.es/~cagd

Line Drawing Algorithms

The lines of this object appear continuous

However, they are made of pixels

2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

Line Drawing Algorithms

We are going to analyze how this process is achieved.

Some useful definitions

Rasterization: Process of
determining which pixels provide the best approximation to a desired line on the screen. lines.
2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

General requirements
Straight lines must appear as straight

? ? ? ?

Scan Conversion: Combination

of rasterization and generating the picture in scan line order.

They must start and end accurately Lines should have constant brightness along their length Lines should drawn rapidly

Line Drawing Algorithms

For horizontal, vertical and 45 lines, the choice of raster elements is obvious. This lines exhibit constant brightness along the length:
2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

For any other orientation the choice is more difficult:

? ?

? ?

? ? ? ?

Line Drawing Algorithms

Rasterization of straight lines.

? ?

? ?

or

Rasterization yields uneven brightness: Horizontal and vertical lines appear brighter than the 45 lines.
For fixing so, we would need: 1. Calculation of square roots (increasing CPU time) 2. Multiple brigthness levels

Compromise:

=>

1. Calculate only an approximate line 2. Use integer arithmetic 3. Use incremental methods
2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

Line Drawing Algorithms

The equation of a straight line is given by: y=m.x+b

Algorithm 1: Direct Scan Conversion

1. Start at the pixel for the left-hand endpoint x1 2. Step along the pixels horizontally until we reach the right-hand end of the line, xr 3. For each pixel compute the corresponding y value 4. round this value to the nearest integer to select the nearest pixel } x = xl;
2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

while (x <= xr){ ytrue = m*x + b; y = Round (ytrue); PlotPixel (x, y); /* Set the pixel at (x,y) on */ x = x + 1;

The algorithm performs a floating-point multiplication for every step in x. This method therefore requires an enormous number of floating-point multiplications, and is therefore expensive.

Line Drawing Algorithms Algorithm 2: Digital Differential Analyzer (DDA)

The differential equation of a straight line is given by: y2 - y1 y dy = constant or = dx x x2 - x1
2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

The solution of the finite difference approximation is: xi+1 = xi + x yi+1 = yi + y2 - y1 x2 - x1 1 We need only compute m once, as the start of the scan-conversion. The DDA algorithm runs rather slowly because it requires real arithmetic (floating-point operations). y 1 DDA uses repeated addition

Line Drawing Algorithms

DDA algorithm for lines with -1 < m < 1 x = xl; ytrue = yl; while (x <= xr){ ytrue = ytrue + m; y = Round (ytrue); PlotPixel (x, y); x = x + 1; }
-8 -7

Example: Third quadrant

-6 -5 -4 -3 -2 -1 0 0 -1 -2 -3 -4

2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

Switching the roles of x and y when m>1

Reverse the roles of x and y using a unit step in y, and 1/m for x.

Gaps occur when m > 1

Line Drawing Algorithms Algorithm 3: Bresenhams algorithm (1965)

Bresenham, J.E. Algorithm for computer control of a digital plotter, IBM Systems Journal, January 1965, pp. 25-30.

This algorithm uses only integer arithmetic, and runs significantly faster.

Y (1,1) (0,1)

2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

Key idea: distance between the actual line and the nearest 1/2 m 1 grid locations (error).

Plot (1,1) 1/2 0 m 1/2 Plot (1,0) (0,0)

Initialize error: e=-1/2 Error is given by: e=e+m Reinitialize error: when e>0

?
(1,0)

 2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

Line Drawing Algorithms

Example: m=3/8

If e<0 below else above

below Error 0

below

above

above

Reinitialize error: e = 1/4 -1 = -3/4

Error: e=e+m
Initial value: e = - 1/2 e = -1/2+3/8 =-1/8 e = -1/8+3/8 = 1/4 e = -3/4+3/8 = -3/8

Line Drawing Algorithms

However, this algorithm does not lead to integer arithmetic. Scaling by: 2* dx
void Bresenham (int xl, int yl, int xr, int yr) { int x,y; /* coordinates of pixel being drawn */ int dy, dx; int ne; /* integer scaled error term */ x = xl; y = yl; /* start at left endpoint */ ie = 2 * dy - dx; /* initialize the error term */ while (x <= xr){ /* pixel-drawing loop */ PlotPixel (x,y); /* draw the pixel */ if (ie > 0) { y = y + 1; ne = ne - 2 * dx; /* replaces e = e - 1 */ } x = x + 1; ne = ne + 2 * dy; /* replaces e = e + m */ } }

2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

Line Drawing Algorithms

Bresenhams algorithm also applies for circles.
Bresenham, J.E. A linear algorithm for incremental digital display of circular arcs Communications of the ACM, Vol. 20, pp. 100-106, 1977.

Key idea: compute the initial octant only

0 1 1 0 2 Reflect first octant about y=x

Reflect first quadrant about x=0 -1 0 0 1

1 3 4 4 2 1

Generate first octant

( )

2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

Reflect upper semicircle about y=0

( )
1 0 0 -1

Line Drawing Algorithms

Bresenhams incremental circle algorithm.

Example: circle of radius 8 Bright pixels: initial pixel (0,8) (1,8) (2,8) (3,7) (4,7) (5,6) (6,5) (7,4) (7,3) (8,2) (8,1) end pixel (8,0)

9 8
2001 Andrs Iglesias. See: http://personales.unican.es/iglesias

7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9