Dim4: A Mind Expanding Experience

          by Stephen L. Judd (sjudd@nwu.edu)


 Introduction

The last question I cannot answer, but this little writeup, along with some pedantically well-documented code, can clear up the first two, I think. This will not be a very dense writeup, honest! Look to the code for more detail, and any equations below can be skipped without problem.

In case you didn't know, dim4 was my entry into the recently held 4k demo contest. For more info on the contest, as well as the other entries (17 entries in all), seek ye the Driven home page at http://soho.ios.com/%7ecoolhnd/

First, very briefly, the keypresses have the following actions:

   4   -- Turbo mode
   D   -- Normal mode (4D + 3D rotations, and nice and casual)
   F4  -- 4D-mode.  All "3D" rotations are halted
   R/S -- 3D-mode.  All "4D" rotations are halted
   .   -- Dotted line toggle
   Space  advances to the next object.

The first object is a 4D cube, often called a hypercube. You can see a small cube inside of and connected to a larger cube. If you look a little closer, you may notice that in-between the two cubes are some more cubes. (When you slice a 3D cube, you get a 2D cube -- a square. When you take a slice of the hypercube, you get a 3D cube). As it rotates along its fourth coordinate, the cube folds in upon itself. One way to look at it is that the cubes start to change positions -- after 180 degrees of rotation the inside cube is on the outside and the outside cube is on the inside. The hypercube has literally turned inside-out.

The program works fine in PAL and NTSC, although PAL folks will get the tune playing at the wrong speed and transposed into a different key.

Oh yes, one thing I really like is the background on the second object-- on my 1084 it looks like rope. This is a consequence of the way VIC generates colors -- extra colors outside of the normal 16 are being generated, because two hires colors are being placed next to each other. If you look at it on a black and white monitor, you will just see thick diagonal lines. This very much surprised me when I first saw it! Find the March 1985 IEEE Spectrum article for more information on why VIC behaves this way.

Finally, you may notice some little glitches from time to time in drawing the 4D objects. That is my safety valve and keeps the program from literally destroying itself, in sometimes spectacular fashion. Oh well.

A Handy Glossary

   Polygon: A rectilinear closed plane figure of any number of sides.

   Vector: A directed line segment having magnitude and direction.

Thus, I plead with the community to not refer to polygons as vectors and filled polygons as filled vectors. Polygons need your help, and have been discriminated against for too long now. Just one small donation on your part of a correct mathematical reference can help save the lives of one, ten, even hundreds of polygons, both abroad and here at home. Individuals wanting to contribute more may sponsor individual polygons; a kit will be sent to you containing the name of the polygon and at regular intervals a picture of the polygon will be sent to you, so you may monitor the progress of your particular polygon. Some polygons are created unclosed, and some do not get the necessary ink or programming skill to properly fill them, but be it a quadrilateral or decagon, trapezium or parallelogram, with your help we can eventually make all polygons closed and full, for a better, more civilized world. Thank you for your time, and God bless all the little geometrical constructions, no matter their dimension or configuration.

The Idea

This program displays a representation of some four-dimensional objects -- four 4D objects, as a matter of fact, each one of them a 4D analog of a three-dimensional object. Each screen contains four symmetry-related 3D objects and one 4D analog of the object, rotated and projected from 4D into 2D.

To describe the four-dimensional objects is not so tough. The 4D cube (the hypercube) is the first to be displayed, and it is the starting point for the later objects. It is also, I think, the easiest to see what is going on with. There is nothing really special about four dimensions -- with a 3D object each point is defined by three coordinates, say (x,y,z). A 4D point has four coordinates, say (w,x,y,z). The 3D cube has eight vertices at:

   (+/-1, +/-1, +/-1)

   (+/-1, +/-1, +/-1, +/-1)

   (1, +/-1, +/-1, +/-1)
   (-1,+/-1, +/-1, +/-1)

This is demonstrated when the code first starts up -- the program "grows" a cube from 0D -> 1D -> 2D -> 3D -> 4D. At the 4D stage there is a smaller cube inside of a larger cube, with cubes in-between the two. (If you are curious as to how I did the "growing", see the code description below for a few details).

Next, as the cube begins to rotate, it "folds in" on itself (or, if you like, it unfolds!). Rotations are no different than they have always been. To do a 3D rotation, recall that the object is rotated in the x-y plane, the y-z plane, and the x-z plane. To rotate in the x-y plane by an angle phi:

   xnew = x*cos(phi) - y*sin(phi)
   ynew = x*sin(phi) + y*cos(phi)

   wnew = w*cos(phi) - x*sin(phi)
   xnew = w*sin(phi) + x*cos(phi)

The R/S key goes into 3D mode by zeroing out the angle increment for the w-x plane. In effect, the 4D rotation is frozen. The F4 key zeros out the x-y, y-z, and x-z angle increments, leaving only the w-x rotation. F4 followed by R/S will therefore freeze the image completely -- use D or 4 to get it going again.

There is still the issue of visualizing a 4D object. This should not be surprising -- after all, we have all seen 3D objects drawn on a 2D computer screen (or a 2D piece of paper). If we can get from 3D to 2D then we ought to be able to get from 4D to 3D (and from there into 2D). Recall that a 3D projection draws a light ray from the object, through a little pinhole located at the origin, and finds the intersection with a piece of film located at z=d, a constant:

   L = t * (x1,y1,z1) is my light ray, so t=d/z1 gives the
                      intersection with the film of a ray from
                      the point (x1,y1,z1) passing through the
                      origin.

   L = t * (w1,x1,y1,z1)  let t=d/w1

   -> L3 = (d, d/w1 * x1, d/w1 * y1, d/w1 * z1)

Now, what is the 4D analog of a tetrahedron, or an octahedron? I reasoned them out by trying to think of what 3D objects I could derive starting from a cube. That is, taking a cube, and cutting away pieces of it. For instance, to do the 14-sided guy, simply take the midpoint of each line segment on the cube -- this has the effect of cutting off the corners of the cube. By defining things in this way, it is fairly straightforward to extend the objects into four dimensions. (I was happiest to realize how to do a tetrahedron). See the file objects.s for more details on the individual objects. Naturally each has some similarity to the cube: there is an inner object(e.g. a tetrahedron) and an outer. The two are connected, and each set of connections forms another object, so that, for instance, there are tetrahedrons in-between the inner and outer tetrahedrons.

Finally, to help in visualizing the objects, I stuck a dotted line capability in. The dotted lines in general connect the "inner" and "outer" 3D objects -- turning them off lets you then see the two objects interact. (The third object was mighty impressive-looking before I added these guys! :)

The Code

Now, it is my considered opinion that the code is awfully well documented, so there isn't too much to say, but a few general things are worth mentioning.

"Growing" the points is really easy -- simply start each coordinate at zero, and gradually increase it out to its final value. By doing this first with the x-coordinates, then the y-coords, then z, then w, the cube grows a dimension at each step. I don't do anything fancy with the other objects -- all coordinates are grown equally, so the objects grow outwards from the origin (as opposed to some sort of zoom effect).

Each 4D character is a 12x12 character grid, which gives a 96x96 pixel drawing area, and takes up the first 144 characters. Each 3D character uses a 5x5 character grid, giving 40x40, and taking up the next 4*25=100 characters, for a total of 244 so far. In eight of the remaining 12 characters are four patterns and their EOR #$FF complements, which are used in the background tilings and are used indirectly in the pattern fills.

Since the final x-y coordinates can range from -48..48, this places a restriction on the initial values for the coordinates. For purposes of accuracy and such coordinates must of course be scaled, so that while a coordinate like (1,1,1,1) is convenient for thinking, a coordinate like (16,16,16,16) is much better suited to the implementation -- that is, the original coordinate scaled by a factor of sixteen or so. The table range restricts this scaling factor: the 4D coordinate with largest length that I use is (1,1,1,1), which has length 2. Thus, after rotation, it is possible that it will lie on an axis with coordinate, say (2,0,0,0). Since coordinates must not exceed 48 in the implementation, this suggests a scaling factor of 24.

As a practical point, the points never really hit this maximum, so in principle a larger scaling factor could be used. Alternatively the projection routine can pick up the slack, which is what dim4 uses.

The first smart thing I did was to ditch the old method of computing rotations. Instead of calculating a big rotation matrix, I calculate some big tables of f_x (s) = x*sin(s), and let the angle s range from 0-127. To get a table of cos(s) I simply periodically extend the sine table by copying the first 32 bytes of the table into the 128-159 positions -- cos(s) is thus sin(s+32). (I take advantage of the fact that sin(s) and cos(s) are related by a factor of pi/2. Were I smart I would have taken advantage of the reflection symmetry of sin/cos, and saved another 64 bytes. Oh well.)

This then leaves 96 bytes for a projection table, which is just what I need for the 4D object. Thus I can mash tables of x*sin(s), x*cos(s), and my projection table of f_x(z)=d*(z-z0) * x into a single page. This page is then extended from $6000 to $C000, i.e. giving 96 tables, for a total of 24k. Accessing the tables is now trivial: store x+$60 in the high byte of a zero page pointer, the low byte contains the offset into the table (0 for the sine table, 32 for the cosine table, and 160 for the projection table), and do an LDA (ZP),Y to get the right value.

Thus rotations and projections are now very fast and very compact. Note that it isn't really necessary to generate a complete table of sines and cosines. For instance, 12k of tables (or 6k or whatever) could be used, and the final result simply multiplied by two, or four. Even though the final coordinates might range from -48..48, calculations don't need to be done using the full range.

The line routine is the good 'ol chunky line routine from the last cube3d program. It of course had to be modified to work with the two buffers and such. I removed a bunch of really redundant code that was in there (REALLY redundant), especially in the actual drawing part (macros XSTEP and YSTEP -- lines are commented out with a '*'). I also added a dotted-line capability (it only takes a few extra instructions), to make things easier to see.

Only a single 3D object is actually drawn -- the others are generated via symmetry (reflections through x=0 and y=0). Since the 3D objects are drawn on a much smaller grid, they need to be scaled down a bit. Instead of writing separate routines to deal with the 3D and 4D objects, I simply set the 4D coordinate of each point in the 3D object to some appropriate number. Recall that in a 3D projection, the farther away from you the object is, the smaller it gets. This is the same idea -- the object is pushed down the 4D axis, and this has the effect of shrinking the object upon projection.

You may have noticed that the 3D objects tend to avoid the center of the screen -- this is a consequence of the random number generator I coded up (and did not test for spectral properties or anything like that :). Originally I was going to place things in a random row and column, but then things just clumped along a diagonal line :). I will also say that the SPLAT routine caused me many days of headaches -- whose idea was it to put color memory so close to a CIA? :)

One thing I had to prune out was a routine which draws circles as the sine/cosine tables are being set up. It is kind of neat and gave me something to watch while the code was setting up, and also was a check that the trig tables were being set up correctly. Anyway, all it does is to draw concentric circles of progressively larger radii, for a sort of tunnelish-looking thing I suppose.

There is a little "failsafe" in the projection routine. If coordinates are out of range (greater than 96 or 40) after projection, they are set to the origin. At least one of the objects screws up from time to time (the octahedron is the main culprit I think), and I think what happens is that the line routine thinks it needs to draw a lot more points than it really needs to. So it happily moves along sticking bytes into the trig/projection tables, and even makes its way up to VIC, SID and the CIAs! Once, it actually started pegging the SID volume register or something, because there would be a periodic loud ticking from the speaker. Eventually the code just grinds to a halt or else completely hoses the system -- hence, the failsafe :).

Finally, the very first lines of the code redirect the BASIC vector at $0302/$0303 and JMPs to the NMI RS/RESTORE routine (although a BRK would probably have sufficed). This is the only way I could get the code to work with the cruncher -- without it, the program goes into "IRQ lock". Crossbow of Crest suggested that ABCruncher does not put a CLI at the end of its crunching routine, and that this can cause problems, most notably with the CIAs.

It took 10-15 hours to get things to crunch and work correctly. In hindsight, I can think of a bunch of things that could have been easily done to make it work, but at the time I was sure relieved when it finally got down to 4095 bytes. Moral: A little thinking early on saves massive time and effort down the road.

The Music

Finally, a word about the music. Originally I was going to construct a series of chords which I could modulate between in a fairly flexible way. I was then going to break up the chords in a nice way and move between them randomly. But then it occurred to me that I already knew a piece of music which was a series of broken chords and sounded infinitely more cool than anything I was going to accidentally write, so I used it instead. Even better, they are four-note "chords", broken into four groups of four notes each -- too good to pass up. Notes are looked up in a frequency table, thus on my PAL 64 the music gets transposed to a different key (in addition to playing at the wrong speed).

I do not necessarily recommend using the routine as a model for doing IRQ interrupts -- I had many problems with "IRQ lock", where an IRQ is continuously latched, and consequently is constantly running the routine. I still do not understand what is happening, nor do I have a solution.

Memory Map

   $0F00-$0FFF   Starting sine+projection table
   $1000-$2257   Code
   $3000-$4000   Character set
   $6000-$C0FF   Sine, cosine, and projection tables
   $C100-$CFFF   Misc. variables and tables


 Contents of dim4.lnx

   dim4             Submitted entry for 4k demo contest
   dim4.text        This file, in PETSCII format
   dim4readme-runme Obvious
   dim4.names       Linker name file to use with Merlin 128 
   main4.s          Main code for dim4
   objects.s        Code to define/set up objects
   graphics.s       Various graphics routines (lines, fills, etc.)
   music.s          Init and main IRQ music routine

Last Updated: 1997-03-11 by Jim Brain