/* line.c - Basic line drawing. * © Copyright 1999 John Halleck * All rights reserved */ /* Version of August 13th, 1999 */#include"errors.h" /* we use package standard error codes. */#include"line.h" /* * Draw a line between (x1, y1) and (x2, y2) * * The equation of the line is.. * | X Y 1 | * | x1 y1 1 | = 0 * | x2 y2 1 | * => * X*(y1-y2) - Y*(x1-x2) + x1*y2 - x2*y1 = 0 * * If you plug other points into this equation, you get a number other * than zero. This number is an (unnormalized) distance function. * This means that is distance multiplied by some constant. * (The constant is sqrt((y1-y2)**2+(x1-x2)**2) ) * since we are only going to compare magnitudes, we don't care * about the constant, and we don't bother to compute it. * * So... The distance (error) function we will use is this (unnormalized) * distance from the line. * * distance = X*(y1-y2) - Y*(x1-x2) + x1*y2 - x2*y1 * * This distance function has the nice property that it is positive * on one side of the line, and negative on the other. * * As the distance is zero at both endpoints, the cross product * terms are zero there. As the change as we move from grid point * to grid point can be computed from DX and DY, we do not need * to compute the cross product terms at all. * So, our simplified initial distance function is: * * distance = X * (y1-y2) - Y * (x1-x2) * * The idea of the line drawing algorithm is that for each step of the line, * one wants to pick the direction that takes one closest to the line being * drawn. This is equivalent, in the end, in trying to push us always * towards the line. Since the distance function is signed, the rule * reduces to going in the direction that makes it more positive if it * is negative, and in the direction that makes it more negative if it * is positive. This is a very clean test in most languages, and the * underlying hardware does it well on most machines. * * If it is the case that both directions would take you the same * distance from the line, you want to pick one in such a manner that * the same one is taken for each direction the line could be drawn. * * If you examine the algorithm carefully, you will note that the * choices of direction are either along an axis, or along a diagonal. * Moving in the one direction makes the distance more positive, and * moving in the other direction makes the distance more negative. * Based on the sign of the current distance, we always move in the * direction that makes the sign go more the other direction. * * There is also a version of this algorithm (that produces the same * results) based on looking at the result with modular arithmetic. * [Derived by LeRoy Eide <LeRoy.Eide@cc.utah.edu>] It can be used * to keep a consistent dot pattern across strips when you have to * make a plot in sections. It has a somewhat different setup, and * the same loop. */ /* External support routine needed */ extern error drawpoint (int x, int y); error line (int x1, int y1, int x2, int y2) { int axis, axisX, axisY, diag, diagX, diagY, bias; /* How far we step, and in what direction, for a step */ int dist, cX, cY, dX, dY; /* Unnormalized distance */ int numpnt, X, Y; /* Current location */ int Errors; /* Any problems we've had. */ /* Set up to know what direction we are going. */ dX = x2 - x1; if (dX<0) { cX = -dX; diagX = -1; } else { cX = dX; diagX = 1; } dY = y2 - y1; if (dY<0) { cY = -dY; diagY = -1; } else { cY = dY; diagY = 1; } /* Decide which axis we are using, make the other the diagonal */ if (cY <= cX) { axisX = diagX; axisY = 0; axis = cY; bias = cX; } else { axisX = 0; axisY = diagY; axis = cX; bias = cY; } /* Compute up the amount of change going each direction makes. */ diag = axis - bias; dist = - bias - 1; /* This line, see: Tran Thong, Tektronix Laboratories, September 19, 1980 * This line preserves the Tran Thong property in the resultant dots. * [Makes it chose exactly the same dots for lines drawn backwards.] * (Choice of diagX or diagY was arbitrary) * This line can be omitted without any change in line quality, * although I can't imagine why you'd want to get rid of it. */ if (diagX < 0) dist --; /* Bias line so that discontinuities are towards the middle * Imagine a line 20 in x and 1 in y. Somewhere it has to * make the leap between the one y value and the other. * This has to be near the middle if the correct properties * are to be observed. */ dist = axis + (dist >> 1); /* We have to start somewhere. */ numpnt = bias + 1; X = x1; Y = y1; /* ****************************************** */ /* FINALLY, here is the core loop. */ while (numpnt-- > 0) { /* Put out the current point */ if ((Errors = drawpoint (X, Y))) return Errors; /* Decide where to move, and update the distance function, * and the coordinates. */ if (dist < 0 ) { dist += axis; X += axisX; Y += axisY; } else { dist += diag; X += diagX; Y += diagY; } } return NoError; } /* -------------------------------------------------------------------------- */ /* ========================================================================== */ /* -------------------------------------------------------------------------- */ /* The observation has also been made that the dist (error) function * above can be used to make anti-aliased lines directly, by distributing * the line across the pixel's that straddle it. * * Basicly, if the line's error value is as far one way as it can be, * then the pixel on that side of the line is as far from the line * as it can get. It should get none of the line, and the other side * should get all. The same argument works the other way. * If it is, for example, on the line, the pixels on both sides should * get the line's value equally. And so on. * * That leads to the code below: */ /* Support routine needed. */ extern error drawspoint (int x, int y, double value); error sline (int x1, int y1, int x2, int y2) { /* (Comments and structure as above...) */ int axis, axisX, axisY, diag, diagX, diagY, bias; int dist, cX, cY, dX, dY; int numpnt, X, Y; error Errors; double shade, scale; /* This setup is the same as the previous routine, I'm not going to * repeat all that... But I'll comment places where they are different. */ dX = x2 - x1; if (dX<0) { cX = -dX; diagX = -1; } else { cX = dX; diagX = 1; } dY = y2 - y1; if (dY<0) { cY = -dY; diagY = -1; } else { cY = dY; diagY = 1; } if (cY <= cX) { axisX = diagX; axisY = 0; axis = cY; bias = cX; } else { axisX = 0; axisY = diagY; axis = cX; bias = cY; } diag = axis - bias; dist = - bias - 1; if (diagX < 0) dist --; /* The following is not needed (and in fact wrong) for anti-aliased * lines. So it is commented out here. */ /* dist = axis + (dist >> 1); */ /* anti aliased lines have no jumps */ /* The scale value is the inverse of the magnitude of the possible range * of values that the distance can take. */ scale = 1.0 / (float) (bias+1+axis); numpnt = bias + 1; X = x1; Y = y1; /* Core loop. */ while (numpnt-- > 0) { shade = scale * (float) (dist+bias+1); if (shade != 1.0) { Errors = drawspoint (X, Y, 1.0 - shade); if (Errors) return Errors; } if (shade != 0.0) { Errors = drawspoint (X+axisX, Y+axisY, shade); if (Errors) return Errors; } if (dist < 0 ) { dist += axis; X += axisX; Y += axisY; } else { dist += diag; X += diagX; Y += diagY; } } return NoError; }

This page is http://www.cc.utah.edu/~nahaj/cave/survey/code/c/line.c.html

© Copyright 2000 by John Halleck, All Rights Reserved.

This snapshot was last modified on August 23rd, 2000

And the underlying file was last modified on May 11th, 2000