A Little Night Mathematics

by George Michael
March 18, 2003

Let's be clear, immediately, that the two little mathematical procedures to be discussed here are very simple and basic. They are not now, nor were they ever, unique or profound, and I have no intention of suggesting any erudition in presenting them now. There is no question, when we first began using them some fifty years ago, there was a pleasure of finding how very neatly they fitted the usage we intended.

Computer usage began at the Lab in 1952 - before the Lab existed (That, you'll agree is something only a physicist could do.) The UNIVAC arrived at the Laboratory in April,1953 and it was expected to assist in the study of nuclear designs; that is, the study of partial differential equations. This was, at the time, largely an unprecedented application of computers. It was quickly obvious that solving the PDEs was only part of the job; one needed to present the results in an efficient way and in a form that was meaningful to the user. This is a fancy way of saying that the user responded better to pictures than to lists of numbers. Somehow, the capabilities of the CRT needed to be harnessed for these tasks. As noted by by N. Hardy, it is just now (this quarter)that the LCD has displaced the CRT as the dominant graphic output device for new computers. Few features of the computer have lasted so long.

As reported about many of the earliest computers, CRTs, normally used for engineering diagnostics, were being pressed into service as crude output printers. One can see, just by looking around, that the idea continues to be valid today. Indeed, these very words, sculpted out of light and its absence are being presented as the product of a display process that has gone on more or less independently from the other things the computer is doing. This is a common way that dialog is achieved between the computer (workstation, laptop, etc.) and a typical user and, of course, the communication is not restricted to text. Images are the more common way to pass information. Today, it is relatively easy to invoke this capability. It wasn't always this neat and tidy.

In the early days of computer usage, one problem was that it required too much of the computer's attention and memory to service a CRT display device. The priority was rightly biased toward solving problems (and printing the results off-line), not displaying the results.

Consider that results could be produced and then converted from the internal binary representation to the decimal number system and formatted for printing using using a program that executed possibly as many as 30,000 instructions per second and written to magnetic tape at a rate of approximately 15,000 characters per second. Not fast by today's standards, but plenty fast for all those old physicists who weren't interested in reading any faster. Alternatively, a display program might produce its image with as few as 5,000 instructions, but these would need to be executed as many as 50 times per second for many minutes so that the user could see and study the display. One alternative was to generate all the points for the entire picture, and store them in the memory. Initially, this was not always a good strategy, given that memory was in such short supply, did not have sufficient bandwidth to service the refresh requirement, and at something like $1 per bit, too expensive. Later as memory got more plentiful, faster and cheaper, it became possible to store the whole picture in the form of a raster in central memory. This turned out to be a seminal idea. This may be an oversimplification, but not by much.

Clearly, there was an avid search for efficient and accurate display hardware and procedures. [I do not intend this to be a detailed recitation of the evolution of display hardware. Some of that activity is covered in other essays. I will give at least two good references at the end of this essay; references that suitably cover certain parts of what we know today as Early Graphics Methods.]

The three display devices that we used starting in 1955 acted, willy nilly, as inspiration for the mathematics we will cover later.Initially, there were three models. In 1955, we had use of the Type 740 direct view and Type 780 photographable display attached to the IBM 704 computer. In 1961, we acquired a Type 30 direct-view display for use on a DEC PDP-1 and a Type 31 high-precision display for film recording. Interestingly, DEC was the only company that supplied, as a matter of policy, a direct-view display device on all its machines. The other graphical output device that served as a motivator for our work was known as a "Cal Comp" plotter; a digital ink-on-paper printer/plotter. (The slowness of the Cal Comp was tolerable because it was used, largely, as an off line device.)

All three devices operated in a Cartesian space known as a digital raster. Thus if x and x+1 are digitally adjacent places where the display can plot points, there is no point between these two that can be addressed by the display's addressing scheme. So, everything that one wishes to display must be built out of only those points available to the display device; all other places are digitally inaccessible. As it turns out, this is not a terrible limitation. Next, we compound the problem by noting that if the display is to be perceived as unblinking, it is necessary to refresh the display periodically. The way people are built, this implies a refresh need of approximately 40 times per second. There are some factors that will allow that number to vary, but there usually will always be some sort of a refresh demand. This places some constraints of the accuracy of the electronic hardware used within the CRT.

Finally, for these early computers, one could not be doing arithmetic and display refreshing simultaneously. In what follows, I will list the various performance values for these displays, but will concentrate on the Type 30 and what followed.

The total capabilities of the IBM 740/780 were as follows:

Move to a position (x, y) with 0 ≤ x,y ≤1023 and either unblank to plot a point, or do nothing, and do it at either high or low intensity.
From the point (x,y) draw a straight line to the right hand edge of the field of view. This line could only be horizontal, vertical, or at 45° relative to the horizontal. This capability was hardly ever used.
Advance the 35mm film one frame.

The time to move and plot a point was 151 msec. Frame advance was approximately 0.5 sec.

The total capabilities of the DEC Type 30 were as follows:

Move to a position (x, y) with -511 ≤ x,y ≤ +512 (this meant that the (0,0) point was in the center of the screen), and either unblank to plot a point, or do nothing, and do it in one of four intensities (the DEC Type 31 High Precision Display raster had (4096 x 4096 ) addressable points).
Advance the 35mm film one frame.

The time to move and plot a point was 50 msec. Frame advance was approximately 0.1 sec.

The total capabilities of the Cal Comp plotter were as follows:

From where the pen carriage is, one can only move one step left or right and/or move the paper up or down one step. Steps in any direction were 0.01 inches and speed was approximately one inch per second.
Raise or lower the pen. Obviously, if the pen is lowered and the plotter is told to move to a new point (x1, y1), it will trace out the path from (x,y) to (x1, y1), producing a reasonable approximation of a straight line (moving through a series of digitally admissible points), IF you've done things correctly.

All three devices were only capable of plotting points. Therefore, any and all other shapes were built from collections of points. If one had to draw a circle, even 100 points represented a lot of image generation. Complicating the procedure was the need for the CRTs to refresh the display many times per second so the user could see his images without flickering.

In other words, we were challenged to use as little of the computer's capability as possible to produce images that would be most meaningful to the user. Given that the value of such imagery was unquestioned, there was sufficient pressure to develop procedures that were the fastest and most accurate possible, and made the most efficient use of the computing resource..

We will discuss two basic structures in this section:

the circle

Plots a set of points {X,Y} obtained from
Y = [R²-X²]^(1/2)

and the straight line:

Plots a set of points {X,Y) obtained from
Y= ((Y2-Y1)/(X2-X1)) * (X-X1) + Y1

We can note two nasties. In the circle equation, one can see it is necessary to compute square root, and to compute a divide in the case of the straight line. These speed limiters will be removed. There are other problems hidden here, but square roots and divides are things that computers don't do fast or graciously. Also, since both procedures are not exact, one must decide how much accuracy a given application needs and, while you're at it, how dense the sequence of plotted points should be to yield an acceptable view.

The fundamental algorithm for drawing a circle or any portion thereof is attributed to Marvin Minsky of MIT and appears, incidentally, as a problem on a Cambridge University Tripos (Mathematics) exam. Glen Culler told us about a line-drawing algorithm that didn't need the divide operation. I am guilty for not having saved a suitable record from when we first implemented this algorithm - I had one, but it was lost as I was forced to move from one office to another several times.I am indebted to Robert Cralle for unearthing a workable copy from his Computist's Corner, a column featured regularly in the Lab's computer newsletter, The Tentacle. Starting with this, I was able to reconstruct the version that didn't use any form of divide.

Incidentally, it should be obvious that certain very simple changes will let the circle algorithm produce any segment of a conic section. This is demonstrated in the following derivation of the basic algorithm.

There are several ways by which the circle algorithm could be derived. Here, we make no pretense at mathematical rigor. Mainly, because of its brevity, we use a simple, quasi-rigorous derivation. There is no intention of hinting which is to be preferred.

Given a point on the circle, we start with the parametric and the difference equations for a circle:

X = R * Cos (T)
dX = -R * Sin(T) * dT
Y = R * Sin(T)
dY = R * Cos(T) * dT

and in difference form,

X _i+1 - X _i = - R * Sin(T)* dT = -Y_i * dT
Y _i+1 - Y _i = R * Cos(T) * dT =X _i+1 * dT

Notes:

If dT is taken to be some suitable power of two, instead of a multiply, one can do a shift. For example, if we wanted the circle to be defined by 32 points on its periphery we would set dT = k = 2 ^-5. Instead of multiplying by k, we get the equivalent by a right shift of Y_i (or X _i+1) 5 places.
Characteristic of most difference equations, the system is unstable unless the advanced value for X is used in the second equation.

The equations:

X _{i + 1} = X _i- Y _i * k
Y_{i + 1} = Y _i+ X_{i + 1} * k

can be used separately or as a part of something more elaborate. They produce a circle image that is adequate for viewing. If more accuracy is needed, more elaborate (and likely slower) algorithms would have to be used. It should be noted that any conic section (ellipses, parabolas, hyperbolae) can also be produced using slightly altered equations. Showing how to do this is left as a plaything for the reader.

Next, we wish to develop an algorithm for producing the pointalistic version of a straight line, given the two end points, P₁and P₂, out of those digital lattice points, P_k closest to the analog line P₂P₁ with the computation to run in the shortest time possible.

In an actual implementation, this algorithm, while mathematically correct, needs to be written in machine language specifically for each instantiation to achieve the fastest execution on a given computer. What is presented here makes use of no consistent algorithmic standards or notations. My goal here is to show how the algorithm works. Very likely there are better ways to express the algorithm. For one thing, having a specific computer in mind might remove certain ambiguities.

We show a slightly more elaborate version of the algorithm in FORTRAN, in which it is possible to avoid plotting every possible point. This is reasonable because adjacent points in a display overlap each other. Plotting say, every fourth point will generally produce an image that is solid appearing, even as we notice the algorithm is faster. This is true for the circle algorithm as well.

After some frustrating starts, I decided to use a "Pidgin" version of FORTRAN to express the algorithm and to show a slightly more elaborate version. One can show the flow control a bit more explicitly. The result is not good FORTRAN, but if the reader can see better how the algorithm behaves, the effort will be justified.


      SUBROUTINE LINE(x2, y2, x1,y1, p)
C.... the presence of C in the first column indicates a comment.
C.... p is a power of 2, and is used to control the line's density.
C.... SIGN (a,b) returns the sign of b attached to a.
      dx = x2 - x1
      dy = y2 - y1
      mx = MAX(ABS(dx), ABS(dy))
      mn = MIN(ABS(dx), ABS(dy))
      sx = SIGN(2**p, dx)
      sy = SIGN(2**p, dy)
      k  = INT(mx/p + 0.5)
C.... Note division by p is made by a right shift of p places
      m = mx/2
       
      do 10 n = 1, k
        Plot(x1, y1)
        if(dx >= dy) go to 2
        y1 = y1 + sy
        go to 7
   3    continue
        if(m + mm >= mx) go to 4
        go to 5
   7    continue
        if(m + mm >= mx) go to 8
        go to 5
   8    x1 = x1 + sx
        go to 6
   2    continue
        x1 = x1 + sx
        go to 3
   4    continue
        y1 = y1 + sy
        go to 6
   5    m = m + mm
        go to 10
   6    m = m + mm - mx
  10    continue
      return
      end

Added here is a flow chart of the algorithm:

A Final Disclaimer

It is something of an embarrassment to see that this essay is so lengthy, yet covers only two simple mathematical procedures. The only thing one can say is that when this material was being seen for the first time some fifty years ago, it wasn't considered simple, one way or another. The algorithms met our needs handsomely and that was good enough. Furthermore, as pointers to where computation, and computer graphics in particular began, there is a valid historical rationale for preserving such little triumphs from the past.

"Once a thing is known, whatever cleverness was involved, disappears."

References

Here are three fairly modern and usable references in computer graphics. All have copyrights well past the 1950s when computer graphics began, but they have useful collections of the stuff often used in the field.

Jim Blinn's Corner; A Trip Down the Graphics Pipeline, by Jim Blinn
A Programmer's Geometry, by Adrian Bowyer and John Woodwark
Principles of Interactive�Computer Graphics,�by William Newmnn and Robert Sproull