A Different Perspective


This one time at band camp
back in the mid 70′s, someone had a copy of National Lampoon‘s 3D issue.  It was one of the most wonderful things I’d seen.  I assume that the magazine’s owner didn’t think his parents would approve of it, so he gave it to me.  I must not have seen very many anaglyphs before this because they made a big impression on me.  I’m sure the naked women interested me a lot too, but I was hooked on 3D images.

Using blue and red pencils I learned to draw things that looked like they stuck out of the page and things that looked like they were behind the plane of the paper.  I remember spending hours drawing with the red/blue glasses on so that when I took them off persistence of vision would make the eye with the red lens see things as blue and the blue eye see things as red for many minutes afterwards.

I found books with old style stereoscope images.  I taught myself to view cross-eyed view and parallel view stereograms.  I drew some of those as well.  Mostly my drawings were simple geometric shapes since those are by far the easiest to draw.

Years went by and although I still found 3D images fascinating I didn’t do much with them.  Then in 1985 the Amiga came out.  It had much better graphics abilities than any other computer I’d used up to that point.  While I’d played with 3D graphics back on my original Commodore PET it didn’t have color graphics so I had only been able to do side by side stereograms.  Also, doing much in the way of animations was difficult on the PET because of it’s low resolution and tiny memory.


Back in high school I figured out how to make simple perspective calculations without using trigonometry or anything else that the microprocessors of the 1970s and 1980s didn’t have built in.  Even though the Amiga had a 68000 instead of a 6502 *, it was still very limited when it came to doing math quickly.  Luckily geometry gives us the concept of similar triangles.  If you don’t remember about this from high school and you’d rather not try to figure out the Wikipedia page, all it says is that if you have two triangles with the same angles than the ratio of the lengths of the sides will be the same.

In the picture above the weird thing on the far left is supposed to be an eye.  The blue vertical line is the computer monitor, the big robot on the right is the thing you are trying to render on the monitor and the little robot in the middle is the image of the robot with perspective applied.  The thin horizontal line that hits the eye is perpendicular to the screen and where it hits the eye is our origin; at the origin X, Y and Z are all zero.

Z is the distance from the eye to the big robot.
Z’ is the distance from the eye to the screen.
Y is the height of the robot above the origin.
Y’ is the height of the robot we are going to draw on the screen.  It’s the value we are trying to figure out.

What that all comes down to is this:

The program I wrote using this was an adaptation of the game breakout or brick out.  Instead of having multiple layers of bricks I covered four of the interior walls of a cube with tiles.  The floor had another tile which acted as your paddle.  The “front” of the cube was the plane of the monitor screen and was the other side of the cube with no tiles.  A ball would bounce around inside the cube.  Each time it hit a tile the tile would disappear and you would get another point.  Your job was to get rid of all the cubes.

Here is a reference to it (page 97.)  As several reviewers noted the game was too easy and didn’t get any harder as you went along.  In that respect it was not a very good game.  On the other hand it was my first major C program.  Up until that point the largest C program I had written had been just a few lines for experimentation purposes.  In addition to the poor game design, the code was far less efficient than it could have been.  I no longer have the source for it, so I can’t be very specific, but I think I duplicated a lot of code that should have been functions.

On the other hand I did do a lot of things right.  I used fixed point math; floating point is very slow on integer microprocessors.  If you look at the equation above you can see that Z’/Z requires a division.  This is also a really slow operation on simple microprocessors.  Since I was working with a grid, the same value Z’/Z was used repeatedly I calculated that first to cut down on the number of divisions.  I rewrote all of the slow parts in assembly language.  I used an 8-bit color map that allowed me to have 16 grey levels for each the left and the right eye and treat the single frame buffer as though it were two separate frame buffers.

It was a fun project and I got a lot of feedback from people all over the world.  This was in the days before widespread e-mail, so I got actual letters in the mail.  Since I released this as shareware most of the envelopes had money in them.  The whole project was great, but the best part was knowing that a lot of people had enjoyed it.

Perplexing Permutations

Back in the days of yore when I was first learning to program, I would often lay awake in bed thinking about coding issues.  There was one algorithm that kept me up for many nights.   I really wanted to figure out how to generate all the permutations of a set.  It wasn’t that I had any real use for it and no one had ever asked me about it.  I knew how many there should be: n! (n factorial) where n is the number of items in the set.  It seemed like it should be an easy problem too, but my typical hack-around-until-you-find-an-answer technique wasn’t yielding results.

I fell back on another technique that I use to this day: moving my fingers around (coins or pencil dots work just as well.)  I used my fingers as the members of the set.  I slid them around on the wall beside my bed changing their order and trying to come up with a simple pattern that I could extend to any number of members.  There was a nightlight at the end of my attic bedroom.  It kept me from falling down the stairs in the middle of the night and cast long distorted shadows from my fingers.

I don’t remember how long it took me, but I remember solving the problem.  I got out of bed and wrote a working version of the program right then.  When I went back to bed I was so excited I could hardly go to sleep.

The concept is pretty simple.  I’ve demonstrated it in the picture with the colored dots above.  The top row has the four items in their original positions.  The second row shows the position of the items after one step of the algorithm.  As you head down the image you continue with the output from the algorithm and pass through all 24 permutations of the four objects.

Here is my attempt at a verbal description of the algorithm:
Take the first item in the set, the red dot, and swap it with the item to it’s right.  Repeat this until the red dot reaches the end of the line. Now move it back to the beginning and swap the second item, the yellow dot, with the item to it’s right.  Do the red dot to the and then back to the beginning again.  Swap the second item with the next item.  Red dot swap.  Repeat this until the yellow dot reaches the end.  Put the yellow dot back to the second position, then do the same thing with the third item, the green dot, while repeating the red and yellow dot swaps just like above.  Hopefully if you look at the picture you can see the pattern.

This algorithm works with any number of items to generate all of the permutations.   If you want to generate only distinct permutations you can add a test to ensure that swaps only occur between different values.  If the values are the same, the item being moved should be returned to it’s original position.  In the example program below it is a one line change.

At the time I originally implemented the algorithm I only knew BASIC.  It is a great language for string manipulation and this algorithm works very well with string based item manipulation.  I once wrote this algorithm in two lines of BASIC to win a bet.  I doubt I could do it today.

Here is a recursive C version:

#include <stdio.h>

char array[] = "RYGB";
#define length (sizeof(array)-1)

void swap( char* p, int i )
{
    int j = i;
    char t;
    while ( p[j] )
    {
        if ( i )
        {
            swap(p, i - 1);
        }
        j++;
        if ( p[j] )
        {
            // move our character 1 position right
            t = p[j-1];
            p[j-1] = p[j];
            p[j] = t;
            printf("%s\n", p);
        }
    }

    // restore the array to its original state
    t = p[j-1];
    for ( j--; j > i; j-- )
    {
        p[j] = p[j-1];
    }
    p[j] = t;
}

int main (int argc, char *argv[])
{
    printf("%s\n", array);
    swap( array, length - 1 );
    return(0);
}

I’ve successively built this with GCC and Visual Studio. Let me know if you have any problems with it.

The Right Answer

When I was first learning to program, my teacher assigned a homework problem: write a program to sort an array of numbers.  This was back in the 1970s.  I had no access to computer books and didn’t know anyone who knew anything about computers, so I came up with the best solution I could overnight with a week of experience under my belt.  Since this was a BASIC class the program below only represents the algorithm I came up with, not the actual code.  It’s not a very efficient routine, but it does get the job done.

#include <stdio.h>

int sortMe[] = { 190, 57, 16, 48, 51, 3, 2, 57, 95 };
#define length (sizeof(sortMe)/sizeof(int))

int main (int argc, char *argv[])
{
    int i;
    int j;
    int weights[length]; // number of other numbers in the
                         // array that are smaller than the
                         // element of sortMe[] with the same
                         // index

    // compare all the elements of sortMe[] to each other
    for ( i = 0; i < length; i++ )
    {
        weights[i] = 0;
        for ( j = 0; j < length; j++ )
         {
            if ( sortMe[i] > sortMe[j] )
            {
                weights[i]++;
            }
        }
    }

    // run through all the weights and print the associated sortMe[]
    // values
    for ( i = 0; i < length; i++ )
    {
        for ( j = 0; j < length; j++ )
        {
            if ( weights[j] == i )
            {
               printf( "%d\n", sortMe[j] );
            }
        }
    }
    return(0);
}

My teacher wasn’t impressed.  It was wrong.  Here is the right answer (again, not the real BASIC code, just my memory of the algorithm.)

#include <stdio.h>

int sortMe[] = { 190, 57, 16, 48, 51, 3, 2, 57, 95 };
#define length (sizeof(sortMe)/sizeof(int))

int main (int argc, char *argv[])
{
    int i;
    int j;

    for ( i = 0; i < length - 1; i++ )
    {
        for ( j = i + 1; j < length; j++ )
         {
            if ( sortMe[i] > sortMe[j] )
            {
                int t = sortMe[j];
                sortMe[j] = sortMe[i];
                sortMe[i] = t;
            }
        }
    }
    for ( i = 0; i < length - 1; i++ )
    {
        printf("%d\n", sortMe[i]);
    }
    return(0);
}

Obviously the only correct answer is a bubble sort.  Why?  Because Mr. Young said so!

No Content (almost)

I noticed that a few people actually came here to look at my blog.  Thank you people!  How embarrassing that I didn’t even have a single entry.  I’m notoriously bad at keeping up with blogs; I don’t think I’ve had a single one that went past three entries.  So if this is the only entry I ever write here at least I wrote something.

I created this WordPress account primarily so I could comment on Makezine.com without using a Facebook account.  However, I suppose it does give me a place to rant about things.  I’ll consider that.

Follow

Get every new post delivered to your Inbox.