64 Explorer:

64 EXPLORER

Larry Isaacs

In this column I will show how to create line drawings on a bitmapped display. In addition, we will look at an example written in BASIC and begin converting it to machine language routines which you can use in your programs. For the line-drawing routine to be really effective, conversion to machine language is required. The BASIC routine is much too slow.

There are a number of different methods for drawing lines in machine language. One way appeared in the August 1981 issue of BYTE magazine. In the article (page 414), Mike Higgins presented an algorithm which requires only in-teger adds and subtracts to generate the point along a line specified by two end points. The algorithm was an improvement on one presented in the book Principles of Interactive Computer Graphics by Newman and Sproull, which is widely known in the field of computer graphics.

Basically, the method involves setting up a loop which will compute each point along the line. Since we would expect to generate one point each time through the loop, the number of points in the line gives us the number of times the loop should be executed. Remember that the display coordinates are always integer values. The horizontal or vertical step between adjacent dots is always 1. To calculate the number of points in the line, simply take the absolute value of the larger of the differences between the X coordinates and the Y coordinates.

The Primary Axis

To identify the axis with the larger difference in a general way, we will call it the primary axis. For example, if we were drawing a line from 0,0 to 100,50, the X axis has the larger difference and would be the primary axis. The number of points in the line, after plotting the first one, would be 100.

Since there are two possibilities for the primary axis, we will need two loops. At this point, we could write some of the statements that will be required in our BASIC line-drawing routine:

        <plot first point>
        DX = XI - X0-:DY = Yl - Y0
        IF ABS(DX) < ABS(DY) THEN <1>
        FORI = 1TOABS(DX)
        …
        NEXT
        <1> FOR I = 1 TO ABS(DY)
        …
        NEXT

where X0, Y0 is the starting point, XI, Y1 is the ending point, and <1> is a symbolic replacement for an appropriate line number. The first point must be plotted first since the loops generate successive points based on the preceding one.

Setting The Increment

Since the number of points is equal to the coordinate difference on the primary axis, that coordinate should be incremented by one each time through the loop. The coordinate for the other axis, which has a smaller difference, is in-cremented at a rate smaller than one. If the differences along each axis are the same, either axis can be used as the primary axis, and both coordinates are incremented by one each time through the loop.

The next step in implementing our drawing routine is to come up with a method of properly incrementing the nonprimary axis. We'll want the loop to generate integer values for both Y and X. The loop could be written:

        X = X0:Y = Y0:SX = l:R = .5*SX
        FOR I = 1 TO ABS(DX)
        X = X + 1
        R = R + DY/DX*SX
        IF R> = SX THEN Y = Y + 1:R = R-SX
        PLOT X,Y
        NEXT

Easier Conversion

In this version of the loop, I have the variable SX to show where the X increment of 1 is involved in the incrementing of Y. The variable R is initialized to .5 so that rounding will occur as it is incremented by DY/DX. It is also important to note that Y will be properly incremented even if SX isn't the normal value of 1. The very handy im-provement Mike Higgins suggested was, in effect, to replace SX with DX. When you do this, note what happens to the loop.

        X = X0:Y = Y0:R = DX/2
        FOR I = 1 TO ABS(DX)
        X = X + 1
        R= R + DY
        IF R> = DX THEN Y = Y + 1:R = R-DX
        PLOT X, Y
        NEXT

Only addition and subtraction are required within the loop, making it much more suitable for conversion to machine language. The only division is a division by 2, which is also easily done in machine language. Naturally, a similar loop could be written to handle the case when Y is the primary axis.

Now that we have a routine for calculating the points along a line, we need a routine to plot these points. There are a number of books which discuss this in detail: the Commodore 64 Programmer's Reference Guide, and two recent releases from COMPUTE!, COMPUTE!'s Reference Guide to Commodore 64 Graphics and COMPUTE!'s First Book of Commodore 64 Sound and Graphics.

The Plotting Routine

Before getting into a short discussion of the point-plotting routine, we will have to decide whether we will be plotting points in the hi-res bitmap mode or the multicolor bitmap mode, or both. To help simplify the discussions, I will be looking at just the hi-res bitmap mode. In next month's column, I will tie up loose ends from this article and include discussion of the multicolor mode.

Briefly, the point-plotting routine must calculate the byte address and the bit within the byte for the point to be plotted. The address of the byte will be dependent on the location of the bit-mapped graphics RAM and the X,Y coordinates of the point. Once the byte and bit have been identified, there are three things we can do with the point.

First, we can set the bit to a 1, causing the point on the screen to take on the foreground color. Second, we can set the bit to a 0, causing the point on the screen to take on the background color. This is equivalent to erasing the point. Third, we can change the bit to the opposite of its current state. This is called "flipping" the point. Applying these to line drawing, we can get three drawing modes, DRAW, ERASE, and FLIP.

Erasing With FLIP

For those who have not encountered FLIP mode before, it has a couple of unique properties. First, lines drawn in FLIP mode are always visible. If a line is drawn through an area that is already set to the foreground color, you can still see the path of the line because that portion of the line will be set to the background color. Second, if a line drawn in FLIP mode is redrawn in FLIP mode, the line will be erased. The screen will be exactly the same as if the line had never been drawn.

The disadvantage of FLIP mode is that gaps appear where lines intersect. FLIP mode is probably most useful when the object being drawn will undergo editing. Once the editing is complete, the screen can be redrawn in the normal DRAW mode, filling the gaps in the lines.

Also described in the books mentioned above are the details on how to initialize the bitmap RAM and the associated screen memory. Program 1 illustrates what we have discussed so far. There is one slight addition to the drawing loop which was shown last. For ERASE and FLIP mode drawing to be most effective, it is desirable that a given line be drawn the same way regardless of which end is its starting point.

To this end, the line-drawing subroutine at line 1000 always draws from left to right. The X increment will always be +1 with the Y increment being +1 or -1, depending on the sign of DY. Also, the point-plotting routine at line 800 does not handle changing the foreground or background colors when plotting a point. This could be easily added if desired. Unfortunately, changing the colors for one point changes the colors for all points within that bitmap cell.

Selecting The Commands

In the example program, the drawing mode is specified by the variable M. If M = 0, ERASE mode is selected. M = 1 selects DRAW mode, and M = 2 selects FLIP mode. The main routine at line 2000 is a simple loop which performs commands specified by DATA statements. Each command consists of a command number followed by one or two argument numbers. A command number of 1 performs a move to the X,Y coordinates specified by the two arguments which follow. Command number 2 performs a draw to the X,Y coordinates specified by the two arguments which follow.

Command number 3 sets the drawing mode to the value of the number that follows. Command number 0 terminates execution of the commands. The graphics display will remain on the screen until a key is pressed. Running this example program should make it clear that BASIC isn't suited for the task of drawing lines. For iterative tasks which require many calculations, the fact that BASIC is interpreted will severely slow up the task.

Conversion To Machine Language

Now we are ready to begin the conversion to machine language. First we will need two routines to replace the BASIC subroutines at lines 100 and 900, which save and restore the text screen, respectively. These will be called SVSCRN and RSSCRN. Next come the BASIC subroutines at lines 200, 300, 400, and 700 which set up the bitmap display. We will combine these into a single routine called GRSCRN to enable the graphics screen.

Since we are working with machine language, we can place the bitmapped memory under the OS ROM and screen memory just below where the DOS Wedge goes, at $E000 and $C800, respectively. This way no user memory is lost from BASIC. Also, the text screen will not be disturbed by drawing in the graphics screen. A slight disadvantage of this arrangement is that interrupts must be turned off while the OS ROM is disabled. This will cause the 64 clock timer to be slightly off.

The final routine we will look at this month will be the one which clears the bitmap and screen memories. This will replace the BASIC subroutines at lines 500 and 600 and will be called CLRSCR. Actually, this routine will rely on another routine called FILL to do the clearing. Rather than fetch arguments from BASIC, this routine fills the screen memory with a constant. This constant sets the background to white and the foreground to red. Next month we'll upgrade this routine to accept arguments specifying the colors.

The result of this set of machine language routines is shown in Program 2. As written, these routines would assemble at location $C000. Like the location of the graphics RAM, this doesn't reduce BASIC user RAM. It also won't interfere with the DOS Wedge. This may conflict with some other machine language routines you find handy, but finding locations which don't conflict has become impossible.

A Jump Table

There are a couple of things worth noting in the machine language listing. First, a jump table is placed at the beginning. This table will contain JMP instructions to each of the routines that will be called from BASIC. Even though the starting locations of the various routines may change, the jump table and the locations to SYS to will stay put. To call one of the routines from BASIC, simply set a variable equal to $C000 (49152), then SYS to this variable plus the appropriate offset. For example: TB = 49152:SYS TB + 9 would call the CLRSCR routine.

Second, you may want to take a look at the FILL routine. Its function is to fill an area of memory with a specified byte. This function could have been implemented a number of different ways. For example, it could have been written a little more simply by using a single loop. Instead I implemented it using two loops, one to fill whole pages (groups of 256 bytes) and the other to fill the final partial page. By doing this, the core loops can be written with just STA, INY, and BNE instructions, making them very fast. It would be difficult to make the routine much faster without increasing its size quite a bit and making it more complex.

When implementing almost any routine, you will usually be faced with trade-offs between size, simplicity, and speed. Here I tried to maximize speed without sacrificing size and simplicity too much.

Next month we'll continue with the conversions of the point-plotting and line-drawing routines, and look into the multicolor bitmap mode. I want to provide information you can put to some use. Please write me with any comments or suggestions concerning topics you would like to see discussed.