Line drawing routines for the TRS-80. Richard Wagner; Frederick Wagner.
Despite its many good features, the TRS-80 is rather unfriendly about drawing lines on its display screen. Many other home computers have nifty graphics commands in Basic. They compute and plot line segments with lightning speed. About the best you can do with Level II TRS-80 Basic is SET (turn on) and RESET (turn off) individual points or pixels.
The TRS-80 user is thus forced to write special programs or routines for plotting lines. Such programs can be complicated as well as slow.
If the TRS-80 had good built-in line drawing routines you could easily put borders around text output, do simple stick figure animation, draw large or specially-shaped letters, and even draw maps or dungeon rooms for an adventure game. Take heart! The accompanying Basic program incorporates a machine language routine that provides excellent line drawing capabilities.
First, we will discuss the problem of plotting lines in general. The principles involved are essentially the same for all computers that plot lines as a series of individual points on a rectangular display. Our goal will be to compute and plot a string of points representing a desired line, such that:
* The line accurately connects the endpoints, with no gaps between individual pixels (This objection is fairly easy to meet).
* Te line appears to be straight and to have uniform density with no bunched-up points (This one is harder, unless the pixel size is very small--hardly the case with the TRS-80).
When we try to satisfy these goals we run into the problem of display screen resolution. That is, we may find few pixel positions on the display screen that fall exactly on the true (calculated) path path of the line. In fact, truly straight lines are impossible to draw unless one of two conditions applies:
* The line is horizontal or vertical.
* The endpoint separation (in pixels) in both the horizontal and vertical directions is the game.
Thus, most diagonal lines exhibit a "stair step" effect.
This becomes increasingly apparent with larger pixel sizes, and TRS-80 pixels are pretty large. Figure 1 illustrates the problem, and Figure 2 shows what happens if poor line drawing methods are used. (The technical name for the stair step appearance is "aliasing." It can occur whenevr the display screen resolution is less than that of the object being displayed. Sophisticated display screen hardware can compensate by "ramping" or smotthing out the steps.)
Please note that our diagrams ignore another unpleasant fact about TRS-80 graphics. That is the fact that the horizontal and vertical scales are quite different, so that the individual pixels aren't square. However, this does not affect the way in which lines are plotted. Bresenham's Algorithm
There are several point plotting methods that do a fairly good job.
One of them, Bresenham's algorithm, is very useful in assembly language programming. Only integer arithmetic is used, and there are no divides. The only multiplies are by 2, implemented by simple SHIFT operations.
Listing 1 is a Basic program derived from Bresenham's line drawing algorithm. It runs slowly, taking one or two seconds to plot each line, but does help to expose the workings of the algorithm.
Bresenham's method draws fairly presentable lines by ensuring that the stair steps in diagonal lines are evenly spaced. It does this by maintaining an "error term" (variable E) which is initialized with a negative value. E is a measure of the distance between a plotted pixel and the exact parth of the line. The plotted position must, of course, fall on an exact display screen coordinate position, whereas the true path of the line may rarely do so (see Figure 3).
The error term E is initialized at a value related to the horizontal and vertical distances involved. An increment value EI and a decrement value ED are also computed. All these values are adjusted in a proportional manner so as to avoid having to use fractional values. (Fractional values would require use of single-precision numbers instead of integers, greatly slowing up the calculations.)
Assume we are plotting a line from point (X1, Y1) to (X2, Y2) and that the distance to plot is greater in the horizontal or X direction. The unit change in X (variable IX) is set to 1 unless X1 is larger than X2 in whcih case it is set to -1. The value of IY is determined in the same manner. As each point (X,Y) is plotted, the current value of E is tested; if it is greater than zero, Y is incremented by IY and E is decremented by ED back to a negative value. Otherwise E is incremented by EI.
X is always incremented by IX after each point is plotted. With properly computed values for EI and Ed we are assured of evenly spaced steps in the plotted line. When the distance to plot is greater in the vertical direction (Y) the procedure works in a similar manner, substituting Y for X, IY for IX, etc. Fastdraw-80
Listing 2, Fastdraw-80, is a Basic program that builds and executes an assembly language implementation of Bresenham's algorithm. It both draws and erases lines. Various tests are included to ensure that plotting stays within the display screen boundaries. We shall call the assembly language routine Quikplot for convenience, since it can be used independently of the Basic program that builds it. Fastdraw-80 demonstrates a simple method one of us (Frederick) developed to encode assembly language routines within Basic programs.
The assembly language routine is developed with the aid of a standard Z80 reference book, and, if available, an Editor-Assembler program. The hex code for the routine is entered as the values of one or more string variables (lines 1010-1050). An initialization routine (lines 1060-1080) is called to convert the hex characters into integers and to POKE them into reserved memory. (A more conventional but far less user-friendly method is to load the assembly language programs from separate files before loading the Basic program. Frederick's method requires only a single LOAD or RUN command.)
Fastdraw-80 requires 32K RAM, and should work on either the Model I or Model III TRS-80. The program can be used with either regular Level II or disk Basic. For non-disk Basic, the USR function call must be changed as described in the remarks of Listing 2.
A demonstration routine is included in Fastdraw-80. It will verify that you have coded the program correctly, and show some of the potential of Quikplot. The demonstration includes a moving pattern and shows how to use the erase feature to draw black lines on a white background. I must admit I was surprised at how fast lines are drawn and with the neat animation effects; who ever thought our TRS-80 could do such tricks?
The Quikplot routine expects to find the number of lines to draw and the coordinates of their endpoints in a two-dimensional array. The memory location of the array is obtained by the VARPTR function and passed to Quikplot via the USR call.
One array dimension is used to specify the picture number P (identifying a set of lines to be displayed in one call to Quikplot). The other dimension holds the specification of the set of lines.
The endpoints of lines are identified in the usual TRS-80 manner, with X ranging from 0 to 127 and Y ranging from 0 to 47. Point (0,0) is at the upper left corner of the display screen. A subroutine (line 2000) is provided to format and transfer the list of end points in the array; the source of the endpoint values can be DATA statements, runtime computations, or interactive input. The demonstration program uses runtime computations.
The array setup routine automatically counts the number of lines to be drawn; this value is entered by the routine in Z(O,P). The size of array Z determines the number of lines that can be drawn in a singl call to the plotting routine. Two array elements are needed per line. Fastdraw-80 sets up Z with dimensions 300 by 10, so it can hold up to 11 pictures, each with up to 150 lines. You can, of course, change the dimensions of Z or even use a different array name. Don't forget that the variable used for the array name must be defined as integer by a DEFINT statement.
True animation effects are easy to achieve. Simply keep the number of lines in each set fairly small, and call the Quikplot routine inside a lopp (using P as the loop variable).
You can also generate a set of picture lines more than once during a program run. Just set Z(O,P) to 0 before calling GOSUB 2000 for the first line of each new picture. Otherwise, the new lines will simply be added to the existing set. The mainline routine in Listing 3 will create and flash an endless series of random designs on your display screen.
To plot a point, simply set the end coordinates equal to the beginning coordinates equal to the beginning coordinates. Frederick has created some impressive "warp drive" animation effects using arrays of point data.
How fast is Quikplot? We ran several timing tests for lines up to the maximum length of 128 prixels. We found that for relatively short lines (10 to 20 pixels) Quikplot calculates and plots about 50 lines per second. In a worst case example, you can "white out" the entire display screen with 48 lines of 128 pixels each in about three seconds. In comparison with using A Basic routine to SET or RESET points, Quikplot is 10 to 20 times faster. Notes
* If you have TRSDOS and a disk drive you may wish to save the compledted routine by use of the command DUMP <your file name> (START=0C00, END=0C300). Then you can reload the executable code with the Disk Basic command CMD "L", "<your file name>/CMD."
* If your TRS-80 has 48K you can usually omit the setting of MEMORY SIZE when running Quikdraw-80. This is due to the location of the Quikdraw-80. This is due to the location of the Quikplot routine in the "no man's land" between the bottom of variable storage and the top of string space. You may find you can do the same with your application if string assignments are minimal.