How do you draw a really fast line?
If you’re into 3D computer graphics this is usually the first question you’ll be challenged with. Drawing a line is easy. But how do you do it quickly?
DRAWING PRIMITIVES
Every object no matter how complete in design can always be represented by the basic drawing elements. The most fundamental of these is the line. From the basic line we can create arcs, circles, rectangles and many more basic shapes. This chapter deals with the basic drawing elements and lists various algorithms to produce them, from which you can choose to use the best for your graphics program.
LINE ALGORITHMS
The line is probably the most fundamental element in any graphics system. From this basic element, you can create any of the more complex elements. So it is imperative that your line routine is accurate and also quick. In a Computer Aided Design (CAD) system for instance any given image could contain thousands of lines. So by deduction, any slowness in your line algorithm will slow your CAD program immensely.
In effect, there are two areas of the line algorithm you must be aware of. The first is the setup section, where you perform setup calculations before drawing pixels. In this section, you can get away with some slower code as this will only be executed once per line.
The second section, actually drawing the line pixels is the most time-intensive. Writing each pixel one at a time and then recalculating the position of the new pixel is quite time-consuming. These calculations are performed each time you draw a pixel so any overhead here will drastically slow down your line routine. It is in this area you should concentrate on speed increases. One of the fastest line routines developed is the Bresenham Line Algorithm. It is extremely quick due to the fact that it is integer-based and does not require any complex mathematical calculations. Jack Bresenham of IBM first devised this algorithm in 1965.
The Bresenham algorithm is by far the best of the general-purpose line algorithms. You can however produce faster algorithms by using specific line routines. For example, in a Horizontal line, there is no need to perform any Vertical calculations so this code can be eliminated. It is possible to have a line routine for each possible combination of line, Horizontal, Vertical, or Diagonal. In fact, you could develop line routines for different types of Diagonal lines. This is the technique used in quite a lot of 3D Computer Games today.
There are in fact eight different types of Diagonal lines that can be drawn depending on the slope of the line. Each Octant has its own particular characteristics as follows:-
BASIC INCREMENTAL LINE ALGORITHM
Any given line between two points x1,y1 and x2,y2 can be represented by solving the general equation y = mx + b
where
m = dy/dx
where m is the slope of the line and b is the offset, or by the equation
Ax + By + C = 0
where
A = y2 -y1
B = – (x2-x1)
C = – (x1 * A + y1 * B)
SAMPLE ‘C’ CODE
Adjust to your own compiler.
//Sign
#define Sign(x) ((x) > 0 ? 1: ((x) == 0 ? 0: (-1)))
//Incremental Line Algorithm
// Draws a line between the points x1,y1 and x2,y2.
void Line ( x1, y1, x2, y2)
int x1, y1, x2, y2;
{
int Dx, Dy, Sx, Sy;
int ADx, ADy;
int x, y, temp;
int Ptx, Pty;
x = y = 0;
Dx = x2 - x1;
Dy = y2 - y1;
ADx = abs(Dx);
ADy = abs(DY);
Sx = Sign(Dx); Sy = Sign(Dy);
Ptx = x1; Pty = y1;
if (ADx >= ADy) {
for (temp = 0; temp <= ADx; temp ++) { y += ADy; if (y >= ADx) {
y -= ADx;
Pty += Sy;
}
Pixel(Ptx, Pty);
Ptx += Sx;
}
}
else {
for (temp = 0; temp <= ADy; temp ++) { x += ADx; if (x >= ADy) {
x -= ADy;
Ptx += Sx;
}
Pixel(Ptx, Pty);
Pty += Sy;
}
}
BRESENHAMS LINE ALGORITHM ‘C’ CODE
This is by far one of the fastest and most efficient general line algorithms available.
//Bresenhams Line Algorithm
// Draws a line between the points xstart,ystart and xend,yend;
void BresLine ( xstart, ystart, xend, yend)
int xstart, ystart, xend, yend;
{
int x,y; //current x,y
int d; //Storage variable
int a,b; //Displacement x,y
int dx_diag; //Diagonal X Step
int dy_diag; //Diagonal Y Step.
int dx_nondiag; //No diagonal x Step for next pixel.
int dy_nondiag;
int diag_inc; //
int nondiag_inc; //
int swap, i; // Temporary variables.
x = xstart;
y = ystart;
//Which direction?
a = xend-xstart;
b = yend-ystart;
//Determine if ending point lies to right or left of start point
if ( a < 0 ) {
a = -a;
dx_diag = -1;
}
else {
dx_diag = 1;
}
if ( b < 0 ) {
b = -b;
dy_diag = -1;
}
else {
dy_diag = 1;
}
if ( a < b ) //Identify Octant containing end point {
swap = a;
a = b;
b = swap;
dx_nondiag = 0;
dy_nondiag = dy_diag;
}else {
dx_nondiag = dx_diag;
dy_nondiag = 0;
}
d = b + b -a; //2*b-a;
nondiag_inc = b + b - a - a;
for ( i = 0; i <= a; a++ ) {
Pixel( x, y);
if (d < 0 ) {
x += dx_nondiag;
y += dy_nondiag;
d += nondiag_inc;
} else {
x += dx_diag;
y += dy_diag;
d += diag_inc;
}
}
}
BRESENHAMS LINE ALGORITHM 'C' CODE
This is by far one of the fastest and most efficient general line algorithms available.
//Bresenhams Line Algorithm
// Draws a line between the points xstart,ystart and xend,yend;
void BresLine ( xstart, ystart, xend, yend)
int xstart, ystart, xend, yend;
{
int x,y; //current x,y
int d; //Storage variable
int a,b; //Displacement x,y
int dx_diag; //Diagonal X Step
int dy_diag; //Diagonal Y Step.
int dx_nondiag; //No diagonal x Step for next pixel.
int dy_nondiag;
int diag_inc; //
int nondiag_inc; //
int swap, i; // Temporary variables.
x = xstart;
y = ystart;
//Which direction?
a = xend-xstart;
b = yend-ystart;
//Determine if ending point lies to right or left of start point
if ( a < 0 ) {
a = -a;
dx_diag = -1;
}
else {
dx_diag = 1;
}
if ( b < 0 ) {
b = -b;
dy_diag = -1;
}
else {
dy_diag = 1;
}
if ( a < b ) //Identify Octant containing end point {
swap = a;
a = b;
b = swap;
dx_nondiag = 0;
dy_nondiag = dy_diag;
}else {
dx_nondiag = dx_diag;
dy_nondiag = 0;
}
d = b + b -a; //2*b-a;
nondiag_inc = b + b - a - a;
for ( i = 0; i <= a; a++ ) {
Pixel( x, y);
if (d < 0 ) {
x += dx_nondiag;
y += dy_nondiag;
d += nondiag_inc;
} else {
x += dx_diag;
y += dy_diag;
d += diag_inc;
}
}
}
HORIZONTAL LINE ALGORITHM 'C' CODE
One area worth considering is tailoring an algorithm to fit your specific display hardware. When considering line algorithms we always seem to think in terms of pixel writes. With some display types that use BitPlanes you can easily write Horizontal runs of pixels by inserting Byte values thus writing 8 pixels at a time. This is by far one of the quickest methods of displaying
Horizontal lines. Displaying Horizontal lines in this way can dramatically increase draw speed in say a polygon fill routine. There are however some small problems to overcome.
Firstly not all lines will start on byte boundaries. Your line may start or end somewhere in the middle of a byte. So your algorithm has to be altered slightly. The basic method for a Horizontal line routine based on this algorithm is.
· Identify how many Real pixels to write to reach a byte boundary.
· Identify how many bytes to write to reach the byte end of our line.
· Identify how many Real pixels are required to reach the end of the line from the last byte boundary.
So your new quick Horizontal Line Algorithm becomes.
//Horizontal Line Algorithm
//Note this routine only writes single 1/0 value pixels, based on a //Black/White display. You should modify the mask values for your own
//display to introduce color.
void QuickHorizontalLine ( x, y, xlen )
int x, y, xlen;
{
char far *Scr_address = ...Calculate Screen address of first Byte (x,y)
...For PC.
...=Screen address + (x / 8) + (y*screen width)
int xend; //End point.
int numbytes; //Number of bytes to write.
BYTE leftmask; //The byte mask to the right number of left pixels
BYTE rightmask; //The byte mask for the remaining right pixels.
BYTE bytemask; //The mask to write to all intermediate pixels.
register i; //Count of bytes to write.
//Calculate last pixel.
xend = x + xlen;
//Calculate number of bytes to write.
numbytes = (xend >>3) - (x>>3); // (xend/8) - (x/8)
//Produce Left and Right Masks.
leftmask = 0xFF >> (x & 7) //00001111 type Mask.
rightmask = ~( 0xFF >> (xend & 7) ) //Inverse mask creating
//11110000 type mask.
bytemask = 0xFF; //11111111 all pixel mask.
if (numbytes == 0) //Problem if all in single byte
{
leftmask &= rightmask; // 00111100 type mask.
*Scr_address |= leftmask; //Write pixels.
return;
}
*Scr_address++ |= leftmask; //Write Left pixels
for (i = 0; i<= numbytes; i++) *Scr_address ++ = bytemask; //Write bytes. if ( (numbytes>0) && (rightmask!=0) )
*Scr_address |= rightmask; // Final pixels.
}
CIRCLE DRAWING ALGORITHM
There are a variety of ways in which one can draw a circle. The simplest method is to solve the general equation for a circle using the Sin and Cos commands. A variety of techniques are available but here we shall show three basic routines. When drawing circles you need to decide whether you require a small or fast algorithm. The routine BasicCircle is by far the shortest and simplest method for drawing circles and is used by most programmers. However, Bresenhams' method is probably the fastest drawing method but is a lot more complex. The faster circle routines take advantage of the symmetry of circles. A Circle contains eight octant points each of which can be calculated by reflection from one of the other octants. So when calculating our circles' points we need only work with a single octant, working through 45 degrees. The circle octants can be represented by the following graph:
Given the eight-point symmetry of a circle, we need only calculate the first octant and then plot the correct points in the other octants. This method leads to an extremely fast circle algorithm. Now to the examples.
BASIC CIRCLE ALGORITHM
By far the simplest Circle Algorithm is that produced solving for trigonometric values of Sin and Cos. This algorithm produces a circle based on calculating certain key points around the circle surface and drawing the connecting lines between them to produce the full image.
In using this method you can easily specify the number of angles to use to produce an even surface.
For most purposes, you can easily achieve a good representation of a circle using anything above 70. In the example we calculate points at every 1-degree radians, to give as smooth a circle as possible using 360 points. The only optimization we use is that we do not calculate the first point as this should always be (x + r, y), being the furthest right-side point on the circle's radius. There are a few methods to increase the speed of this algorithm. Firstly we can limit the number of angles we use to produce the circle outline. We could easily produce a good circle by using steps of 2 or 3 degrees instead of 1. Depending on the screen resolution you use this may vary for you. Secondly, you will notice that the routine must calculate values for Sin and Cos for each angle. One method around this is to have your software produce Sin and Cos tables and your routine can take the values accordingly for each angle. If you then made the variable 'i' an integer varying from 1 to 360 you could easily rewrite the code as
for (i = 0; i < 360; i += step) { xt = xc + radius * CosTable [ i ]; yt = yc + radius * SinTable [ i ]; ...... } This method is quite efficient and will give very good improvements in speed.
//
//BasicCircle Algorithm
//
//This routine draws a given circle with center xc, yc and radius r.
//It assumes that we draw in steps of 1 degree radians.
//
//Definitions for both 1 and 360 degree radians.
#define degree_1 0.017
#define degree_360 6.28
void Circle( xc, yc, r )
int xc, yc; int r;
{
double xs,ys;
double xt,yt;
double i;
double radius = r;
xs = xc + radius; //+R*Cos ( 0 ) => R*1 =>R
ys = yc; //+R*Sin ( 0 ) => R*0 => 0
moveto(xs,ys); //Move graphics cursor to first point.
for (i = degree_1; i < degree_360; i += degree_1) //360 radians
{
xt = xc + radius * Cos ( i );
yt = yc + radius * Sin ( i );
lineto ( xt, yt ); //Draw a line to next point.
}
}
CIRCLE POINTS SYMMETRY ALGORITHM
//
// CirclePoints Algorithm
//
// Given any given point x,y on a circle circumference, plot the symmetric points in
// each of the circles' octants.
//
void CirclePoints( xc, yc, x, y)
int xc, yc;
int x, y;
{
Pixel(xc+x,yc+y);
Pixel(xc+y,yc+x);
Pixel(xc+y,yc-x);
Pixel(xc+x,yc-y);
Pixel(xc-x,yc-y);
Pixel(xc-y,yc-x);
Pixel(xc-y,yc+x);
Pixel(xc-x,yc+y);
}
BRESENHAM INTEGER CIRCLE ALGORITHM
//
// BresCircle
//
// Draw a given circle using only Integer variables.
//
void BresCircle( int xc, int yc, int radius)
{
int x,y,d;
x=0;
y=radius;
d=2*(1-radius);
while (y>x) {
CirclePoints(xc, yc, x,y);
if (d+y>0) {
y=y-1;
d=d-2*y+1;
}
if (x>d) {
x=x+1;
d=d+2*x+1;
}
}
}
More:
Read more on our Arc Drawing Algorithms
Advertising
