A Different Perspective, part III

by Stephen Judd --- sjudd@nwu.edu
George Taylor --- aa601@cfn.cs.dal.ca

Whew! What a busy time it's been -- research to get done, conferences, classes... between getting things done and blowing other things off, I one day reflected for a moment and realized that I had three days left to get the next article together for C=Hacking! So everything has been slapped together at the last minute, and I hope you'll forgive any bugs or unclear concepts.

>>> ANECDOTE ALERT <<<
And that reminds me: I just got JiffyDOS and an FD-2000 drive -- what a wonderful device. I have a 1.6 megabyte disk formatted into three partitions. The first contains my Merlin 128 assembler, the second is some 4000 blocks large and I use it for all my various versions of code while debugging, and the third is maybe 1000 blocks, and contains only finished code -- no more swapping disks, no more deleting old versions that I hope I don't need to make room on the disk. Also, when I installed JiffyDOS I found a serious bug in my 128D -- a cricket, dead among the IC's.

This time we will cover a lot of ground which isn't so much cutting-edge as it is very useful. Let's face it: cubes are getting more than a little dull. A worthy end goal is to have a completely general routine for plotting a series of polygons -- that is, you supply a list of (x,y,z) coordinates from which the program can form a list of polygons. These polygons may then be displayed in 2D, rotated, magnified, filled, etc. And, much to my three-day astonishment, that is exactly what we are going to do.

But first, a little excursion. One thing we are of course always thinking about is optimization possibilities: in the shower, while sleeping/dreaming, out on dates, etc. So, where to begin? The biggest cycle hogs in the program are line drawing and face filling -- well, filling faces is pretty straightforward. What about line drawing?

Well, one downer of the routine is that every single pixel is plotted. But as we know, on a computer any given line is made up of several smaller vertical and horizontal lines -- wouldn't it be neat if we could think of a way to plot these line chunks all at once, instead of a pixel at a time?

Heck yes it would! So here we go:

Neat-o Enhanced Chunky Line Drawing Routine

First we need to be in the right mindframe. Let's say you're drawing a line where you move three pixels in x before it's time to take a step in y. Instead of plotting all three pixels it would of course be much more efficient to just stick a number like %00011100 in the drawing buffer. But somehow we need to keep track of a) how large the chunk needs to be, and b) where exactly the chunk is.

In the above example, we started at a particular x-value:

        %00010000
and we want to keep adding ones to the right of the starting point; three, to be exact. Hmmm... we need to somehow rotate the starting bit in a way that leaves a trail of ones behind it. Maybe rotate and ORA with the original bit? But what happens when you take a step in Y?

No, we need something far sneakier. Let's say that instead of %00010000 we start with

        x = %00011111
Now, with each step in the x direction, we do an arithmetic shift on x. So after one step we have

        x = %00001111
and after two steps

        x = %00000111
and at the third step of course

        x = %00000011
Now it is time to take a step in Y. But now look: if we EOR x with its original value xold = %00011111, we get

        x EOR xold = %00011100
which is exactly the chunk we wanted. Moreover, x still remembers where it is, so we don't have to do anything special each time a step is taken in the y-direction.

So here is the algorithm for drawing a line in the x-direction:

        initialize x, dx, etc.
        xold = x
        take a step in x: LSR X
        have we hit the end of a column?  If so, then plot and check on y
        is it time to take a step in y?
        if not, take another step in x
        if it is, then let a=x EOR xold
                       plot a into the buffer
                       let xold=x
        keep on going until we're finished
This simple modification gives us a substantial speed increase -- on the old filled hires cube3d program, I measured a gain of one frame per second. Not earth-shattering, but not bad either! When faces are not filled, the difference is of course much more noticable.

There are a few things to be careful of. There was a bug in the old routine when the line was a single point. In that case dx=dy=0, and the program would draw a vertical line on the screen. There are probably some other things to be careful of, but since I wrote this part of the code three months ago I really don't remember any of them!

This takes care of horizontal line chunks -- what about vertical chunks? Well, because of the way points are plotted there is nothing we can do about them. But, as we shall soon see, if we use an EOR-buffer to fill faces we will be forced to take care of the vertical chunks!

General Polygon Routine

Now we can begin thinking about a general polygon routine. First we need a list of sets of points, where each set corresponds to a polygon. The first number in a set could be the number of (x,y,z) points in that set, and the points could then follow. So a triangle could be given by the data set:

        3 -1 0 0 0 1 0 1 0 0
This would be a triangle with vertices at (-1,0,0), (0,1,0), and (1,0,0). We can mash a bunch of these sets together, but somehow we have to know when we've hit the end -- for this we can use a zero, since we don't want to plot polygons with zero points in them.

For that matter, how many points should there be in a polygon? There must be at least three, otherwise it makes no sense. Since we want our polygons to be closed, the computer should be smart enough to connect the last point to the first point -- in our triangle above, the computer would join (-1,0,0) to (0,1,0), (0,1,0) to (1,0,0), and (1,0,0) to (-1,0,0).

Now that we have a polygon, we want to rotate it. You will recall that we have calculated a rotation matrix M, which acts on points. So we need apply our rotation transform to each of the points in the polygon, i.e. multiply M times each point of the polygon. Furthermore, we need to project each of these points.

Uh-oh: matrix multiplication. In the past we have avoided this issue by putting the vertices of our cube at 1 or -1. So we need to use our multiplication routine from last time. But wait! As you recall, the last program used a specially modified multiplication table. To get a wider range of numbers to multiply we will need another set of multiplication tables -- no big whoop.

Now, if you review the multiplication routine from last time, it adds two numbers and subtracts two numbers. What kinds of numbers will we be dealing with? The matrix elements vary between -64..64. This then fixes our range of polygon coordinates from -64..64. Why? If the matrix element is 64, and we multiply it by 64, the multiplication routine will add 64 and 64 and get 128, which is right on the edge of our multiplication table.

Can we improve this rotation process in any way? In fact, we can cut down on the number of multiplications (i.e. do eight or even seven instead of nine multiplications). However, there is a fair amount of overhead involved in doing so, and our multiply routine is fast enough that the extra overhead and complexity really gain us very little in all but the most complicated of polygons. In other words, I didn't bother.

What about hidden faces? Again, from last time you may recall that a method was described which used the cross-product of the projected vectors. How do we implement this in the program? Well, if we take the first three points of the polygon, we have two vectors. Let's say these points are P1 P2 and P3. Then V1=P1-P2 and V2=P3-P2 are two vectors in the plane of the polygon which are connected at the point P2 (this analysis will of course only work if the polygon lies in some plane). Depending on how we take the cross product, the sign will be positive or negative, and this will tell us if the polygon is visible.

Depending on how we take the cross product? Absolutely. v1 x v2 = -v2 x v1. What it really boils down to is how you define the points in your polygon. Specifically, what order they are in. Points that are specified in a clockwise manner will give a face pointing in the opposite direction of a polygon with the same points specified in a counter-clockwise order. In my program, the polygons must be entered in counter-clockwise order (with you facing the polygon) for hidden faces to work the way you want them to ;-).

One other neat thing to have is the ability to zoom in and out. We know from the very first article that zooming corresponds to multiplying the projected points by a number, so that's what we'll do. The multiplication routine returns A=A*Y/64, so a zoom factor of 64 would be like multiplying the point by one. All the program does is multiply the projected points by a number zoom, unless zoom=64, in which case the program skips the zoom multiply. Be warned! No checks of any sort are made in the program, so you can zoom at your own risk!

The important things to remember are: when entering polygons, make sure the numbers range from -64 to 64, and that you enter points in counterclockwise. Our triangle example above really should have been entered as, say,

        3 -64 0 0 64 0 0 0 64 0

Filled Faces -- Using an EOR buffer

Well we still have one thing left, which was alluded to in the previous article: using EOR to make a filled face. Some possible difficulties were raised, but when you plot a single polygon at a time, the problem becomes vastly simplified.

First I should perhaps remind you what exclusive-or is: either A or B, but not both. So 1 EOR 0 = 1, as does 0 EOR 1, but 0 EOR 0 = 0 and 1 EOR 1 = 0. As a simple introduction to using this for filling faces, consider the following piece of the drawing buffer:

        00001011 M1
        00000000 M2
        00000001 M3
        00001010 M4
Lets say we move down memory, EORing as we go. Let M2 = M1 EOR M2. Then let M3 = M2 EOR M3. Then let M4 = M3 EOR M4. Our little piece of memory is now:

        00001011 M1
        00001011 M2
        00001010 M3
        00000000 M4
What just happened? Imagine that the original memory was a series of pieces of line segments. We have just filled in the area between the two line segments, like magic!

If you still aren't getting it, draw a large section of memory, and then draw an object in it, like a triangle, or a trapazoid, and EOR the memory by hand, starting from the top and moving downwards.

EOR flips bits. If you start with a zero, it stays zero until it hits a one. It will then stay one until it hits another one. So you can see that if you have an object bounded by ones, EORing successive memory locations will automagically fill the object.

Right? Well, we have to be careful. One major problem is a vertical line:

        1                       1
        1       goes to         0
        1                       1
        1                       0
Not only is the resultant line dashed, but if there are an odd number of points in the line segment, the last one will happily move downwards in memory, and give you a much longer vertical line than you expected! Since any line with slope greater than one is made up of a series of line segments, this is a major consideration.

Another problem arises with single points: a one just sitting all by itself will also generate a nice streak down your drawing area.

If you think about it, what we ideally want to have is an object that at any given value of x there are exactly two points, one defining the top of the object, and the other defining the bottom. This gives us the insight to solve the above two problems.

First let's think about vertical lines. In principle we could plot the first and last endpoints of each vertical line chunk, but that is exactly what we don't want! Remember that these are closed polygons, which means that there are _two_ lines we need to think about. If I plot just a single point in each vertical line segment, there must be another point somehwere, either above or below it, from another line segment, which will close the point to EOR-filling. Remember, we want exactly two points at each value of x: one will come from the line, and the other will come from the other line which must lie above or below the current one.

Furthermore, with any convex polygon there are exactly two lines which come together at each vertex of the polygon. This means that there are only certain cases which we need to worry about. For instance, two lines might join in any of the following ways:

        \                  /    \    /
         \                /      \  /
          \_____    _____/        \/  etc.
If you draw out the different cases involving vertical lines, you can see that you have to be careful about plotting the lines. One tricky one is where two vertical lines with different slopes overlap at the point of intersection.

So after staring at these pictures for a while, you can find a consistent method which solves these difficulties. As long as you follow the following rules, the problems all disappear; the line routine needs to be modified slightly:

  1. When plotting a vertical line (i.e. big steps in Y direction), don't plot the endpoints (i.e. x1,y1 and x2,y2).
  2. When plotting a vertical line, consistently plot either the first part of each chunk or the last part of each chunk (excluding the endpoints of course). In other words, only plot a point when you take a step in x, and then plot one and only one point.

Now I deduced these by staring at pictures for a few hours and trying different things like top/bottom of chunk, left/right, first/last, etc. You can see that in some cases this ensures that only one point appears on a given line segment. But to me the only way to convince yourself that this really does work is to draw a bunch of pictures, and try it out! You have cases where two vertical lines intersect, and where a vertical line intersects a horizontal line.

But there is still one thing which we have forgotten -- the case of a single point. This can happen in, for instance, a pointy triangle, pointing in the x-direction. How do we fix this? By simply avoiding the point: in the line drawing routine, use EOR to plot the points instead of ORA. Since vertical lines skip the endpoints, vertical-horizontal intersections are OK. Horizontal- horizontal intersections will force the point of intersection to be zero.

Uh-oh, what about intersections like -----*------. Quite frankly I just thought of it, and I think my program will fail on intersections like these. Drat. Well, that just gives us something for next time!

One other thing needs to be mentioned: for EOR-filling to be useful you need to draw the polygon in a special buffer, and then EOR this buffer into the main display buffer. If you try to EOR the display buffer directly you are going to have a whole heap of trouble, such as the concerns raised last time.

Finally, this gives a simple way of filling with patterns instead of boring monocolor. Instead of EOR (EORBUF),Y : ORA (DRAWBUF),Y you can use EOR (EORBUF),Y : AND PATTERN,Y : ORA (DRAWBUF),Y (as long as you preserve the original EOR (EORBUF),Y).

Well I am extremely tired and I hope Craig hasn't sent out C=Hacking without me! I hope you have fun playing with the program, and I would be very interested in seeing any neat geometric shapes you might design!

Program notes: