######## ################## ###### ###### ##### ##### #### #### ## ##### #### #### #### #### #### ##### ##### ## ## #### ## ## ## ### ## #### ## ## ## ##### ######## ## ## ## ##### ## ## ## ## ## ##### ## ## ######## ## ## ## ### ## ## #### ## ## ##### #### #### #### #### ##### #### #### #### #### #### ###### ##### ## ###### ###### Issue #16 ################## April 26, 1998 ######## ............................................................................... Knowledge is power. -- Nam et ipsa scientia potestas est. Francis Bacon, Meditationes Sacrae ............................................................................... BSOUT The number 16 is an important number for Commodore folks. Commodore's most famous computer is so named for having 2^16 bytes. I'm sure many of us were greatly influenced by Commodore as 16-year olds. And it was just a little over sixteen years ago that the Commodore 64 first became available. I want to convey to you what a remarkable fact this is. After sixteen years the Commodore 64 is not only still being used, but the entire community is still moving forwards. People are still using the machine seriously, new and innovative hardware and software is still being developed, and new and innovative uses for these old machines are still being found. I do not believe any other computer community can make this claim. How cool is that? Thus does issue #16 boldly stride forwards into the deep realms of the Commodore unknown, secure in the knowledge that the Commodore community will blaze brightly well into the future, and in eager anticipation of the undiscovered algorithms and schematics which lie just around the corner. And now a few words on the future of C=Hacking. As everyone knows, C=Hacking has been pining for the fjords for a while now. Now that it is once again displaying its beautiful plumage, I hope to keep new issues appearing reasonably regularly. My current thinking is that C=Hacking will appear on a "critical mass" basis: once enough articles have arrived, a new issue will be released. I will of course be meanwhile digging around for material and authors, and we'll see if four issues per year is too optimistic (one caveat: I will be trying to graduate soon, so you might have to wait a little bit longer than normal for the next issue or two). I also expect to slim the issues down somewhat. The focus will now be technical -- as Jim mentioned in issue #15, the nontechnical stuff will move to another mag. Instead of a behemoth magazine with tons of articles, I am going to try using a critical mass of 2-3 main articles plus some smaller articles. (This might also make it possible to release issues more often). The magazine now has four sections: Jiffies, The C=Hallenge, Side Hacking, and the main articles. Jiffies are just short, quickie and perhaps quirky programs, in the flavor of the old RUN "Magic" column, or "Bits & Pieces" from The Transactor. The C=Hallenge presents a challenge problem for readers to submit solutions to, to be published in future issues. Side Hacking is for articles which are too small to be main articles but nifty in their own right. Thus there is now room for articles of all sizes, from monstrous to a mere screenful. With the first two sections I am hoping to stimulate reader involvement, and we'll see if it works or not. In this issue I have included at least one of each type of article, to give a flavor of the different sections. Otherwise, things ought to be more or less the same. I'd like to thank Jim Brain for keeping C=Hacking going over the last few years, and also for the use of the jbrain.com web site. I'd also like to say that although this issue seems to be the "Steve and Pasi issue", there's no particular reason to expect that to be the case for future issues. And now... onwards! ....... .... .. . C=H ::::::::::::::::::::::::::::::::::: Contents :::::::::::::::::::::::::::::::::: BSOUT o Voluminous ruminations from your unfettered editor. Jiffies o Quick and nifty. The C=Hallenge o All is now clear. Side Hacking o "PAL VIC20 goes NTSC", by Timo Raita and Pasi 'Albert' Ojala . How to turn your PAL VIC20 into an NTSC VIC20. o "Starfields", by S. Judd . Making a simple starfield. o "Milestones of C64 Data Compression", by Pontus Berg . A short history of data compression on the 64. Main Articles o "Compression Basics", by Pasi 'Albert' Ojala . Part one of a two-part article on data compression, giving an introduction to and overview of data compression and related issues. o "3D for the Masses: Cool World and the 3D Library", by S. Judd . The mother of all 3d articles. .................................. Stuff .................................... Legalities ---------- Rather than write yet another flatulent paragraph that nobody will ever read, I will now make my own little contribution to dismantling the 30 years' worth of encrustation that has led to the current Byzantine US legal system: C=Hacking is a freely available magazine, involving concepts which may blow up your computer if you're not careful. The individual authors hold the copyrights on their articles. Rather than procedure and language, I therefore depend on common sense and common courtesy. If you have neither, then you probably shouldn't use a 64, and you definitely shouldn't be reading C=Hacking. Please email any questions or concerns to chacking-ed@mail.jbrain.com. General Info ------------ -For information on subscribing to the C=Hacking mailing list, send email to chacking-info@mail.jbrain.com -For general information on anything else, send email to chacking-info@mail.jbrain.com -For information on chacking-info@mail.jbrain.com, send email to chacking-info@mail.jbrain.com To submit an article: - Invest $5 in a copy of Strunk & White, "The Elements of Style". - Read it. - Send some email to chacking-ed@mail.jbrain.com Note that I have a list of possible article topics. If you have a topic you'd like to see an article on please email chacking@mail.jbrain.com and I'll see what I can do! ....... .... .. . C=H ................................... Jiffies .................................. Well folks, this issue's Jiffy is pretty lonely. I've given it a few friends, but I hope you will send in some nifty creations and tricks of your own. $01 From John Ianetta, 76703.4244@compuserve.com: This C-64 BASIC type-in program is presented here without further comment. 10 printchr$(147) 20 poke55,138:poke56,228:clr 30 a$="ibm":print"a$ = ";a$ 40 b$="macintosh" 50 print:print"b$ = ";b$ 60 print:print"a$ + b$ = ";a$+b$ 70 poke55,.:poke56,160:clr:list $02 I am Commodore, here me ROR! First trick: performing ROR on a possibly signed number. Don't blink! CMP #$80 ROR Second trick: performing a cyclical left shift on an 8-bit number. CMP #$80 ROL Oooohh! Aaaaahhh! Another method: ASL ADC #00 ........ .... .. . C=H ............................... The C=Hallenge ............................... The chacking challenge this time around is very simple: write a program which clears the screen. This could be a text screen or a graphics screen. Naturally ? CHR$(147) is awfully boring, and the point is to come up with an interesting algorithm -- either visually or code-wise -- for clearing the screen. The purpose here is to get some reader involvement going, so submit your solutions to chacking-ed@mail.jbrain.com and chances are awfully good that you'll see them in the next issue! (Source code is a huge bonus). And, if you have a good C=Hacking C=Hallenge problem, by all means please send it to the above address. ........ .... .. . C=H ................................ Side Hacking ................................ PAL VIC20 Goes NTSC by Timo Raita http://www.iki.fi/vic/ Pasi 'Albert' Ojala http://www.cs.tut.fi/~albert/ _________________________________________________________________ Introduction Recently Marko Mäkelä organized an order from Jameco's C= chip closeout sale, one of the items being a heap of 6560R2-101 chips. When we had the chips, we of course wanted to get some of our PAL machines running with these NTSC VIC-I chips. A couple of weeks earlier Richard Atkinson wrote on the cbm-hackers mailing list that he had got a 6560 chip running on a PAL board. He used an oscillator module, because he couldn't get the 14.31818 MHz crystal to oscillate in the PAL VIC's clock generator circuit. We checked the PAL and NTSC VIC20 schematic diagrams but couldn't notice a significant difference in the clock generator circuits. There seemed to be no reason why a PAL machine could not be converted into NTSC machine fairly easily by changing the crystal and making a couple of small changes. Adding a clock oscillator felt a somewhat desperate quick'n'dirty solution. Note that some old television sets require you to adjust their vertical hold knob for them to show 60 Hz (NTSC) frame rate. Some recent pseudo-intelligent televisions only display one frame rate (50 Hz in PAL-land). Multistandard television sets and most video monitors do display 60 Hz picture correctly. There is a very small chance that your display does not like the 60 Hz frame rate. Still, be careful if you haven't tried 60 Hz before. You should also note that PAL and NTSC machines use different KERNAL ROM versions, 901486-06 is for NTSC and 901486-07 is for PAL. However, the differences are small. In an NTSC machine with a PAL ROM the screen is not centered, the 60 Hz timer is not accurate and the RS-232 timing values are wrong. The Story Timo: At first I took a VIC20CR board (FAB NO. 251040-01) and just replaced the videochip and the crystal, and as you might suspect, it didn't work. I noticed that the two resistors in the clock generator circuit (R5 and R6) had a value of 470 ohms, while the schematics (both NTSC and PAL!) stated that they should be 330 ohms. I replaced those resistors, and also noticed the single 56 pF capacitor on the bottom side of the board. This capacitor was connected to the ends of the R5 resistor and was not shown in the schematics. As you might guess, the capacitor prevents fast voltage changes, and thus makes it impossible to increase the frequency. Is this capacitor present also on NTSC-board? Someone with such a board could check this out. I removed the capacitor, and now it works. I didn't test the board between these two modifications, but Pasi confirmed that you only need to remove the capacitor. Pasi: I first tried to convert my VIC20CR machine, because the clock circuit in it seemed identical to the one a newer NTSC machine uses, except of course the crystal frequency. Some of the pull-up resistors were different, but I didn't think it made any difference. Pull-up resistors vary a lot without any reason anyway. I replaced the video chip and the crystal, but I could not get it to oscillate. I first thought that the 7402 chip in the clock circuit just couldn't keep up and replaced it with a 74LS02 chip. There was no difference. The PAL crystal with a PAL VIC-I (6561) still worked. I turned my eyes to my third VIC20, which is an older model with all that heat-generating regulator stuff inside. It has almost the same clock circuit as the old NTSC schematic shows. There are three differences: 1. The crystal is 14.31818 MHz for NTSC, 8.867236 MHz for PAL. 2. Two NOR gates are used as NOT gates to drop one 74S04 from the design. 3. In PAL the crystal frequency is divided by two by a 7474 D-flipflop. I could either put in a 28.63636 MHz crystal or I could use the 14.31818 MHz crystal and bypass the 7474 clock divider. I didn't have a 28 MHz crystal, so I soldered in the 14.31818 MHz crystal and bent the pin 39 (phi1 in) up from the 6560 video chip so that it would not be connected to the divided clock. I then soldered a wire connecting this pin (6560 pin 39) and the 14.31818 MHz clock coming from the 7402 (UB9 pin 10). The machine started working. I just hadn't any colors. My monitor (Philips CM8833) does not show NTSC colors anyway, but a multistandard TV (all new Philips models at least) shows colors as long as the VIC-I clock is close enough to the NTSC color clock. The oscillator frequency can be fine-adjusted with the trimmer capacitor C35. Just remember that using a metallic unshielded screwdriver is a bad idea because it changes the capacitance of the clock circuit (unless the trimmer is an insulated model). Warming has also its effect on the circuit capacitances so let the machine be on for a while before being satisfied with the adjustment. With a small adjustment I had colors and was done with that machine. Then I heard from Timo that the CR model has a hidden capacitor on the solder side of the motherboard, probably to filter out upper harmonic frequencies (multiples of 4.433618 MHz). I decided to give the VIC20CR modification another try. I removed the 56 pF capacitor, which was connected in parallel with R5, and the machine still worked fine. I then replaced the crystal with the 14.31818 MHz crystal and inserted the 6560 video chip. The machine didn't work. I finally found out that it was because I had replaced the original 7402 with 74LS02. When I replaced it with a 74S02, the machine started working. I just could not get the frequency right and thus no colors until I added a 22 pF capacitor in parallel with the capacitor C50 and the trimmer capacitor C48 to increase the adjustment range from the original 5..25 pF to 27..47 pF. The trimmer orientation didn't have any visible effect anymore. I had colors and was satisfied. To check all possibilities, I also replaced the 74S02 with 7402 that was originally used in the circuit (not the same physical chip because I had butchered it while soldering it out). I didn't need the parallel capacitor anymore, although the trimmer adjustment now needed to be correct or I lost colors. As I really don't need two NTSC machines, I then converted this machine back to PAL. I made the modifications backwards. I replaced the crystal and video chip and then was stumped because the machine didn't work. I scratched my head for a while but then remembered the extra capacitor I had removed. And surely, the machine started working when I put it back. Obviously, the machine had only worked without the capacitor because it had 74LS02 at the time. 74S02 and 7402 won't work without it. So, if you are doing an NTSC to PAL conversion, you need to add this capacitor. Summary PAL VIC20 To NTSC This is the older, palm-heating VIC20 model with the two-prong power connector and the almost-cube power supply. 1. Replace the 8.867236 MHz crystal with a 14.31818 MHz crystal 2. If UB9 is 74LS02, replace it with a 7402 (or 74S02 if you only use NTSC) 3. Bend pin 39 from the 6560 video chip so that it does not go to the socket. 4. Add a jumper wire from UB9 pin 10 to the video chip pin 39. 5. Adjust the trimmer capacitor C35 so that your multistandard television shows colors. PAL VIC20CR To NTSC 1. Replace the 4.433618 MHz crystal with a 14.31818 MHz crystal 2. If your machine has a capacitor in parallel with R5, remove it (the parallel capacitor). The values in our machines were 56 pF. 3. If UB9 is 74LS02, replace it with a 7402 (or 74S02 if you only use NTSC) 4. If necessary, increase the clock adjustment range by adding a capacitor of 11..22 pF in parallel to C50 (15 pF in the schematics, 5 pF in my machine) and C48 (the trimmer capacitor 0..20 pF). With 7402 you can do with a smaller capacitor or with no additional capacitor at all. 5. Adjust C48 so that your multistandard television shows colors. Trouble-shooting * There is no picture + You have not removed (or added for NTSC) the 56 pF capacitor - Remove/Add the capacitor + Your clock crystal is broken - Find a working one + Your machine has a 74LS02 instead of 7402 (or 74S02) - Replace the 74LS02 with a 7402 + You forgot to replace the PAL video chip with the NTSC chip - Remove 6561 and insert 6560 + For older model: You forgot the clock wire and/or to turn up 6560 pin 39 - Connect 6560 pin 39 to UB9 pin 10 * There is picture, but it is scrolling vertically + Your monitor or television does not properly sync to 60 Hz frame rate - Adjust the monitor/TV's vertical hold setting * There is picture but no colors + Your monitor or TV does not understand the color encoding - Give up the color or get a better television + The color clock frequency is slightly off - Adjust the trimmer capacitor + The color clock frequency adjustment range is not enough - Add a 11-22 pF capacitor in parallel with the trimmer ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Starfields, by S. Judd If you've ever played Elite or Star Raiders you've experienced a starfield. The idea is to use stars to give a sense of motion while navigating through the universe. In this article we'll derive a simple algorithm for making a starfield -- the algorithm I used in Cool World. As usual, a good way to start is with a little thinking -- in this case, we first need to figure out what the starfield problem even is! Consider the motion of the stars. As we move forwards, the stars should somehow move past us -- over us, to the side of us, etc. (A star coming straight at us wouldn't appear to move at all). And something that moves needs a starting place and an ending place. Certainly they end at the screen boundaries, and since anything really far away looks like it's right in front of us they must start at (or near) the center of the screen. So far so good: stars start near the center of the screen and move outwards to the edges. What kind of path do they follow? Well it can't be a curve, right? If it were a curve, then all stars would have to curve in exactly the same way, since there is a rotation symmetry (just tilting your head won't alter the shape of the path of the stars). So it has to be a straight line. Since stars start at the center of the screen and move outwards, we know that, wherever a star might be on the screen right now, it started in the center. So, to get the path of the star's motion, we simply draw a line from the center of the screen through the star's current location, and move the star along that line. Drawing lines is easy enough. If the center of the screen is located at (xc, yc) then the equation of a line from the center to some point (x0, y0) is just (x,y) = (xc, yc) + t*(x0-xc, y0-yc) You should read a vector equation like the above as for t=blah to wherever step 0.0001 x = xc + t*(x0-xc) y = yc + t*(y0-yc) plot(x,y) next and you can see that when t=0 (x,y) = (xc, yc) i.e. the center of the screen and when t=1 (x,y) = (x0, y0) i.e. the current location. Thus, when t goes from 0 to 1 we hit all points in-between, and when t is a very small number (like 0.0001) we basically move from (xc,yc) to the point on the line right next to (xc,yc). Great, now we know the path the stars take. But _how_ do they move along that path? We know from experience that things which are far away appear to move slowly, but when we're up close they move really fast (think of a jet plane, or the moon). And we know that in this problem that stars which are far away are near the center of the screen, and stars which are nearby are out near the edges. So, stars near the center of the screen ought to move slowly, and as they move outwards they ought to increase in speed. Well, that's easy enough to do. We already have an easy measure of how far away we are from the center: dx = x0-xc dy = y0-yc But this is the quantity we need to compute to draw the line. All we have to do is move some fraction of (dx,dy) from our current point (x0,y0): x = x0 + dx/8 ;Note that we started at x0, not xc y = y0 + dy/8 where I just divided by 8 for the heck of it. Dividing by a larger number will result in slower motion, and dividing by a smaller number will result in faster motion along the line. But the important thing to notive in the above equations is that when a star is far away from the center of the screen, dx and dy are large and the stars move faster. Well alrighty then. Now we have an algorithm: draw some stars on the screen for each star, located at (x,y): erase old star compute dx = x-xc and dy = y-yc x = x + dx*velocity y = y + dy*velocity plot (x,y) keep on going! where velocity is some number like 1/8 or 1/2 or 0.14159 or whatever. This is enough to move us forwards (and backwards, if a negative value of velocity is used). What about moving up and down, or sideways? What about rotating? First and foremost, remember that, as we move forwards, stars always move in the same way: draw a straight line from the origin through the star, and move along that path. And that's the case no matter where the star is located. This means that to rotate or move sideways, we simply move the position of the stars. Then using the above algorithm they will just move outwards from the center through their new position. In other words, rotations and translations are pretty easy. Sideways translations are easy: just change the x-coordinates (for side to side translations) or y-coordinates (for up and down translations). And rotations are done in the usual way: x = x*cos(t) - y*sin(t) y = x*sin(t) + y*cos(t) where t is some rotation angle. Note that you can think of sideways motion as moving the center of the screen (like from 160,100 to 180,94). Finally, what happens when stars move off the screen? Why, just plop a new star down at a random location, and propagate it along just like all the others. If we're moving forwards, stars move off the screen when they hit the edges. If we're moving backwards, they are gone once they get near enough to the center of the screen. Now it's time for a simple program which implements these ideas. It is in BASIC, and uses BLARG (available in the fridge) to do the graphics. Yep, a SuperCPU comes in really handy for this one. Rotations are also left out, and I put little effort into fixing up some of the limitations of the simple algorithm (it helps to see them!). For a complete ML implementation see the Cool World source code. 10 rem starfield 15 mode16:gron16 20 dim x(100),y(100):a=rnd(ti) 25 xc=160:yc=100:n=12:v=1/8 30 for i=1 to n:gosub200:next 40 : 50 for i=1 to n 55 color0:plot x(i),y(i):color 1 60 dx=x(i)-xc:dy=y(i)-yc 65 x1=x(i)+v*dx+x0:y1=y(i)+v*dy+y0 67 x2=abs(x1-x(i)):y2=abs(y1-y(i)):if (x2+y2<3*abs(v)) then gosub 200:goto 60 70 if (x1<0) or (y1<0) or (x1>319) or (y1>199) then gosub 200:dx=0:dy=0:goto65 75 plot x1,y1:x(i)=x1:y(i)=y1 80 next 90 get a$ 100 if a$=";" then x0=x0-3:goto 40 110 if a$=":" then x0=x0+3:goto 40 120 if a$="@" then y0=y0-3:goto 40 130 if a$="/" then y0=y0+3:goto 40 133 if a$="a" then v=v+1/32 135 if a$="z" then v=v-1/32 140 if a$<>"q" then 40 150 groff:stop 200 x(i)=280*rnd(1)+20:y(i)=170*rnd(1)+15:return Line 200 just plops a new star down at a random position between x=20..300 and y=15..185. Lines 100-140 just let you "navigate" and change the velocity. The main loop begins at line 50: 55 erase old star 60 compute dx and dy 65 advance the star outward from the center of the screen 67 check if the star is too close to the center of the screen (in case moving backwards) 70 if star has moved off the screen, then make a new star And that's the basic idea. Easy! It's also easy to make further modifications -- perhaps some stars could move faster than others, some stars could be larger that others, or different colors, and so on. Starfields are fast, easy to implement, and make a nifty addition to many types of programs. :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Milestones of C64 Data Compression Pontus Berg, bacchus@fairlight.org One of the featured articles in this issue is on data compression. A very natural question to ask is: what about data compression on the C-64? The purpose of this article is therefore to gain some insight into the history of data compression on the 64. This article doesn't cover programs like ARC, which are used for storage/archiving, but instead focuses on programs which are compressed in executable format, i.e. decompress at runtime. The earliest instance of compression comes with all computers: the BASIC ROMs. As everyone knows, BASIC replaces keywords with one-byte tokens. This not only takes less memory, but makes the program run faster as well. Clearly, though, the BASIC interpreter is a very special situation. The general problem of 64 data compression is to *reversibly* replace one chunk of data with a different chunk of data which is shorter *on the average*. It won't always be shorter, simply because there are many more big chunks of data than there are small ones. The idea is to take advantage of any special structure in the data. The data in this case is 64 machine language programs, including graphics data, tables, etc. The early years didn't feature any compression, but then "packers" (RLE compression) were introduced. The first packer I used myself was flash packer, but I can't tell if it was an early one. The idea of RLE -- run length encoding -- is simply to replace repeated bytes with a single byte and the number of times to repeat it. For example, AAAAAA could be replaced by xA6, where x is a control character to tell the decompressor that the next two bytes represent a run. Then came the TimeCruncher, in 1986 or perhaps 1987. Basically, one can divide the world into compression before and after the TimeCruncher by Macham/Network. With TimeCruncher, Matcham introduced sequence crunching -- this is THE milestone in the evolution. The idea of sequencing is the same as LZ77: replace repeated byte sequences with a *reference* to earlier sequences. As you would imagine, short sequences, especially of two or three bytes, are very common, so methods of handling those cases tend to pay large dividends. See Pasi's article for a detailed example of LZ77 compression. It is worth noting that several 64 compression authors were not aware of LZ77 when designing their programs! Naturally the 64 places certain limitations on a compression algorithm. With typical 64 crunchers you define a scanning range, which is the range in which the sequence scanner looks for references. The sequence cruncher replaces parts of the codes with references to equal sequences in the program. References are relative: number of bytes away and length. Building this reference in a smart and efficient way is the key to success. References that are far away require more bits, so a "higher speed" (bigger search area) finds more sequences, but the references are longer. The next step of value was CruelCrunch, where Galleon (and to some extent Syncro) took the concept to where it could be taken. Following that, the next step was introducing crunchers which use the REU, where Antitrack took DarkSqeezer2 and modified it into a REU version. Actually this was already possible in the original Darksqeezer 3, but that was not available to ATT. Alex was pissing mad when it leaked out (rather soon) ;-). The AB Cruncher, followed by ByteBoiler, was really the first cruncher to always beat the old CruelCrunch. With the REU feature and public availablility, this took the real power of crunchers to all users. It should be noted that the OneWay line of crunchers (ByteBoiler and AB Crunch, which doesn't even require an REU) actually first scan the files and then optimize their algorithms to perform their best, rather than letting the user select a speed and see the results after each. Regarding compression times, a char/RLE packer typically takes the time it takes to read a file twice, as they usually feature two passes -- one for determining the bytes to use as controlbytes and one to create the packed file. Sequence crunchers like TimeCruncher typically took a few hours, and CruelCrunch as much as ten hours (I always let it work over night so I can't tell for sure - it's not something you clock while watching ;-). After the introduction of REU-based sequence crunchers (which construct tables of the memory contents and do a table lookup, rather than repeatedly scanning the data), and their subsequent optimization, the crunching times went down first to some 30 minutes and then to a few minutes. ByteBoiler only takes some two minutes for a full 200 block program, as I recall. The RLE packers and sequence crunchers are often combined. One reason was the historical time saving argument - a file packed first would be smaller upon entering the crunching phase which could hence be completed much faster. A very sophistocated charpacker is however a big waste as the result they produce - a block or so shorther at best - is almost always eaten up by worse crunching. Some argue that you could as well crucnh right away without first using the packer, but then again you have the other argument - a charpacker can handle a file of virtually any length (0029 to ffff is available) whereas normally a cruncher is slightly more limited. Almost any game or demofile (mixed contents of graphics, code, musicdata and player, etc.) normally packs into some 50-60% of its original size when using an RLE+sequence combination. The packer might compress the file by some 30%, depending on the number of controlbytes and such, and the cruncher can compress it an additional 10-20%. Minimising the size was the key motivation for the development of these programs -- to make more fit on the expensive disks and to make them load faster from any CBM device (we all know the speed of them ;-). For the crackers one could mention the levelcrunchers as well. This is a way to pack data and have it depack transparently while loading the data, as opposed to adding a depacker to be run upon execution. The very same crunching algorithms are used, and the same programs often come in a level- and filecrunching edition. ....... .... .. . C=H :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Featured Articles :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Compression Basics Pasi 'Albert' Ojala albert@cs.tut.fi http://www.cs.tut.fi/%7Ealbert/ _____________________________________________________________________ Introduction ============ Because real-world files usually are quite redundant, compression can often reduce the file sizes considerably. This in turn reduces the needed storage size and transfer channel capacity. Especially in systems where memory is at premium compression can make the difference between impossible and implementable. Commodore 64 and its relatives are good examples of this kind of a system. The most used 5.25-inch disk drive for Commodore 64 only holds 170 kB of data, which is only about 2.5 times the total random access memory of the machine. With compression, many more programs can fit on a disk. This is especially true for programs containing flashy graphics or sampled sound. Compression also reduces the loading times from the notoriously slow 1541 drive, whether you use the original slow serial bus routines or some kind of a disk turbo loader routine. Dozens of compression programs are available for Commodore 64. I leave the work to chronicle the history of the C64 compression programs to others and concentrate on a general overview of the different compression algorithms. Later we'll take a closer look on how the compression algorithms actually work and in the next article I will introduce my own creation: pucrunch. Pucrunch is a compression program written in ANSI-C which generates files that automatically decompress and execute themselves when run on a C64 (or C128 in C64-mode, VIC20, or C16/+4). It is a cross-compressor, if you will, allowing you to do the real work on any machine, like a cross-assembler. Our target environment (Commodore 64 and VIC20) restricts us somewhat when designing the 'ideal' compression system. We would like it to be able to decompress as big a program as possible. Therefore the decompression code must be located in low memory, be as short as possible, and must use very small amounts of extra memory. Another requirement is that the decompression should be relatively fast, which means that the arithmetic used should be mostly 8- or 9-bit which is much faster than e.g. 16-bit arithmetic. Processor- and memory-intensive algorithms are pretty much out of the question. A part of the decompressor efficiency depends on the format of the compressed data. Byte-aligned codes can be accessed very quickly; non-byte-aligned codes are much slower to handle, but provide better compression. This is not meant to be the end-all document for data compression. My intention is to only scratch the surface and give you a crude overview. Also, I'm mainly talking about lossless compression here, although some lossy compression ideas are briefly mentioned. A lot of compression talk is available in the world wide web, although it may not be possible to understand everything on the first reading. To build the knowledge, you have to read many documents and understand _something_ from each one so that when you return to a document, you can understand more than the previous time. It's a lot like watching Babylon 5. :-) Some words of warning: I try to give something interesting to read to both advanced and not so advanced readers. It is perfectly all right for you to skip all uninteresting details. I start with a Huffman and LZ77 example so you can get the basic idea before flooding you with equations, complications, and trivia. _____________________________________________________________________ Huffman and LZ77 Example ======================== Let's say I had some simple language like "Chippish" containing only the letters _CDISV_. How would a string like _SIDVICIIISIDIDVI_ compress using a) Huffman encoding, and b) LZ77? How do compression concepts such as information entropy enter into this? A direct binary code would map the different symbols to consequtive bit patterns, such as: Symbol Code 'C' 000 'D' 001 'I' 010 'S' 011 'V' 100 Because there are five symbols, we need 3 bits to represent all of the possibilities, but we also don't use all the possibilities. Only 5 values are used out of the maximum 8 that can be represented in 3 bits. With this code the original message takes 48 bits: SIDVICIIISIDIDVI == 011 010 001 100 010 000 010 010 010 011 010 001 010 001 100 010 For Huffman and for entropy calculation (entropy is explained in the next chapter) we first need to calculate the symbol frequencies from the message. The probability for each symbol is the frequency of appearance divided by the message length. When we reduce the number of bits needed to represent the probable symbols (their code lengths) we can also reduce the average code length and thus the number of bits we need to send. 'C' 1/16 0.0625 'D' 3/16 0.1875 'I' 8/16 0.5 'S' 2/16 0.125 'V' 2/16 0.125 The entropy gives the lower limit for a statistical compression method's average codelength. Using the equation from the next section, we can calculate it as 1.953. This means that however cleverly you select a code to represent the symbols, in average you need at least 1.953 bits per symbol. In this case you can't do better than 32 bits, since there are a total of 16 symbols. Next we create the Huffman tree. We first rank the symbols in decreasing probability order and then combine two lowest-probability symbols into a single composite symbol (C1, C2, ..). The probability of this new symbol is therefore the sum of the two original probabilities. The process is then repeated until a single composite symbol remains: Step 1 Step 2 Step 3 Step 4 'I' 0.5 'I' 0.5 'I' 0.5 C3 0.5\C4 'D' 0.1875 C1 0.1875 C2 0.3125\C3 'I' 0.5/ 'S' 0.125 'D' 0.1875\C2 C1 0.1875/ 'V' 0.125 \C1 'S' 0.125 / 'C' 0.0625/ Note that the composite symbols are inserted as high as possible, to get the shortest maximum code length (compare C1 and 'D' at Step 2). At each step two lowest-probability nodes are combined until we have only one symbol left. Without knowing it we have already created a Huffman tree. Start at the final symbol (C4 in this case), break up the composite symbol assigning 0 to the first symbol and 1 to the second one. The following tree just discards the probabilities as we don't need them anymore. C4 0 / \ 1 / 'I' C3 0 / \ 1 / \ C2 C1 0 / \1 0/ \ 1 'D''S' 'V''C' Symbol Code Code Length 'C' 011 3 'D' 000 3 'I' 1 1 'S' 001 3 'V' 010 3 When we follow the tree from to top to the symbol we want to encode and remember each decision (which branch to follow), we get the code: {'C', 'D', 'I', 'S', 'V'} = {011, 000, 1, 001, 010}. For example when we see the symbol 'C' in the input, we output 011. If we see 'I' in the input, we output a single 1. The code for 'I' is very short because it occurs very often in the input. Now we have the code lengths and can calculate the average code length: 0.0625*3+0.1875*3+0.5*1+0.125*3+0.125*3 = 2. We did not quite reach the lower limit that entropy gave us. Well, actually it is not so surprising because we know that Huffman code is optimal only if all the probabilities are negative powers of two. Encoded, the message becomes: SIDVICIIISIDIDVI == 001 1 000 010 1 011 1 1 1 001 1 000 1 000 010 1 The spaces are only to make the reading easier. So, the compressed output takes 32 bits and we need at least 10 bits to transfer the Huffman tree by sending the code lengths (more on this later). The message originally took 48 bits, now it takes at least 42 bits. Huffman coding is an example of a "variable length code" with a "defined word" input. Inputs of fixed size -- a single, three-bit letter above -- are replaced by a variable number of bits. At the other end of the scale are routines which break the _input_ up into variably sized chunks, and replace those chunks with an often fixed-length _output_. The most popular schemes of this type are Lempel-Ziv, or LZ, codes. Of these, LZ77 is probably the most straightforward. It tries to replace recurring patterns in the data with a short code. The code tells the decompressor how many symbols to copy and from where in the output to copy them. To compress the data, LZ77 maintains a history buffer, which contains the data that has been processed, and tries to match the next part of the message to it. If there is no match, the next symbol is output as-is. Otherwise an (offset,length) -pair is output. Output History Lookahead SIDVICIIISIDIDVI S S IDVICIIISIDIDVI I SI DVICIIISIDIDVI D SID VICIIISIDIDVI V SIDV ICIIISIDIDVI I SIDVI CIIISIDIDVI C SIDVIC IIISIDIDVI I SIDVICI IISIDIDVI I SIDVICII ISIDIDVI I SIDVICIII SIDIDVI --- --- match length: 3 |----9---| match offset: 9 (9, 3) SIDVICIIISID IDVI -- -- match length: 2 |2| match offset: 2 (2, 2) SIDVICIIISIDID VI -- -- match length: 2 |----11----| match offset: 11 (11, 2) SIDVICIIISIDIDVI At each stage the string in the lookahead buffer is searched from the history buffer. The longest match is used and the distance between the match and the current position is output, with the match length. The processed data is then moved to the history buffer. Note that the history buffer contains data that has already been output. In the decompression side it corresponds to the data that has already been decompressed. The message becomes: S I D V I C I I I (9,3) (2,2) (11,2) The following describes what the decompressor does with this data. History Input S S I SI D SID V SIDV I SIDVI C SIDVIC I SIDVICI I SIDVICII I SIDVICIII (9,3) -> SID |----9---| SIDVICIIISID (2,2) -> ID |2| SIDVICIIISIDID (11,2) -> VI |----11----| SIDVICIIISIDIDVI In the decompressor the history buffer contains the data that has already been decompressed. If we get a literal symbol code, it is added as-is. If we get an (offset,length) pair, the offset tells us from where to copy and the length tells us how many symbols to copy to the current output position. For example (9,3) tells us to go back 9 locations and copy 3 symbols to the current output position. The great thing is that we don't need to transfer or maintain any other data structure than the data itself. Compare this to the BASIC interpreter, where all tokens have the high bit set and all normal characters don't (PETSCII codes 0-127). So when the LIST routine sees a normal character it just prints it as-is, but when it hits a special character (PETSCII >= 128) it looks up the corresponding keyword in a table. LZ77 is similar, but an LZ77 LIST would look up the keyword in the data already LISTed to the screen! LZ78 uses a separate table which is expanded as the data is processed. The number of bits needed to encode the message (>52 bits) is somewhat bigger than the Huffman code used (42 bits). This is mainly because the message is too short for LZ77. It takes quite a long time to build up a good enough dictionary (the history buffer). _____________________________________________________________________ Introduction to Information Theory ================================== Symbol Sources -------------- Information theory traditionally deals with symbol sources that have certain properties. One important property is that they give out symbols that belong to a finite, predefined alphabet A. An alphabet can consist of for example all upper-case characters (A = {'A','B','C',..'Z',..}), all byte values (A = {0,1,..255}) or both binary digits (A = {0,1}). As we are dealing with file compression, the symbol source is a file and the symbols (characters) are byte values from 0 to 255. A string or a phrase is a concatenation of symbols, for example 011101, "AAACB". Quite intuitive, right? When reading symbols from a symbol source, there is some probability for each of the symbols to appear. For totally random sources each symbol is equally likely, but random sources are also incompressible, and we are not interested in them here. Equal probabilities or not, probabilities give us a means of defining the concept of symbol self-information, i.e. the amount of information a symbol carries. Simply, the more probable an event is, the less bits of information it contains. If we denote the probability of a symbol A[i] occurring as p(A[i]), the expression -log2(p(A[i])) (base-2 logarithm) gives the amount of information in bits that the source symbol A[i] carries. You can calculate base-2 logarithms using base-10 or natural logarithms if you remember that log2(n) = log(n)/log(2). A real-world example is a comparison between the statements: 1. it is raining 2. the moon of earth has exploded. The first case happens every once in a while (assuming we are not living in a desert area). Its probability may change around the world, but may be something like 0.3 during bleak autumn days. You would not be very surprised to hear that it is raining outside. It is not so for the second case. The second case would be big news, as it has never before happened, as far as we know. Although it seems very unlikely we could decide a very small probability for it, like 1E-30. The equation gives the self-information for the first case as 1.74 bits, and 99.7 bits for the second case. Message Entropy --------------- So, the more probable a symbol is, the less information it carries. What about the whole message, i.e. the symbols read from the input stream? What is the information contents a specific message carries? This brings us to another concept: the entropy of a source. The measure of entropy gives us the amount of information in a message and is calculated like this: H = sum{ -p(A[i])*log2(p(A[i])) }. For completeness we note that 0*log2(0) gives the result 0 although log2(0) is not defined in itself. In essence, we multiply the information a symbol carries by the probability of the symbol and then sum all multiplication results for all symbols together. The entropy of a message is a convenient measure of information, because it sets the lower limit for the average codeword length for a block-variable code, for example Huffman code. You can not get better compression with a statistical compression method which only considers single-symbol probabilities. The average codeword length is calculated in an analogous way to the entropy. Average code length is L = sum{-l(i)*log2(p(A[i])) }, where l(i) is the codeword length for the ith symbol in the alphabet. The difference between L and H gives an indication about the efficiency of a code. Smaller difference means more efficient code. It is no coincidence that the entropy and average code length are calculated using very similar equations. If the symbol probabilities are not equal, we can get a shorter overall message, i.e. shorter _average_ codeword length (i.e. compression), if we assign shorter codes for symbols that are more likely to occur. Note that entropy is only the lower limit for statistical compression systems. Other methods may perform better, although not for all files. Codes ----- A code is any mapping from an input alphabet to an output alphabet. A code can be e.g. {a, b, c} = {0, 1, 00}, but this code is obviously not uniquely decodable. If the decoder gets a code message of two zeros, there is no way it can know whether the original message had two a's or a c. A code is _instantaneous_ if each codeword (a code symbol as opposed to source symbol) in a message can be decoded as soon as it is received. The binary code {a, b} = {0, 01} is uniquely decodable, but it isn't instantaneous. You need to peek into the future to see if the next bit is 1. If it is, b is decoded, if not, a is decoded. The binary code {a, b, c} = {0, 10, 11} on the other hand is an instantaneous code. A code is a _prefix code_ if and only if no codeword is a prefix of another codeword. A code is instantaneous if and only if it is a prefix code, so a prefix code is always a uniquely decodable instantaneous code. We only deal with prefix codes from now on. It can be proven that all uniquely decodable codes can be changed into prefix codes of equal code lengths. _____________________________________________________________________ 'Classic' Code Classification Compression algorithms can be crudely divided into four groups: 1. Block-to-block codes 2. Block-to-variable codes 3. Variable-to-block codes 4. Variable-to-variable codes Block-to-block codes -------------------- These codes take a specific number of bits at a time from the input and emit a specific number of bits as a result. If all of the symbols in the input alphabet (in the case of bytes, all values from 0 to 255) are used, the output alphabet must be the same size as the input alphabet, i.e. uses the same number of bits. Otherwise it could not represent all arbitrary messages. Obviously, this kind of code does not give any compression, but it allows a transformation to be performed on the data, which may make the data more easily compressible, or which separates the 'essential' information for lossy compression. For example the discrete cosine transform (DCT) belongs to this group. It doesn't really compress anything, as it takes in a matrix of values and produces a matrix of equal size as output, but the resulting values hold the information in a more compact form. In lossless audio compression the transform could be something along the lines of delta encoding, i.e. the difference between successive samples (there is usually high correlation between successive samples in audio data), or something more advanced like Nth order prediction. Only the prediction error is transmitted. In lossy compression the prediction error may be transmitted in reduced precision. The reproduction in the decompression won't then be exact, but the number of bits needed to transmit the prediction error may be much smaller. One block-to-block code relevant to Commodore 64, VIC 20 and their relatives is nybble packing that is performed by some C64 compression programs. As nybbles by definition only occupy 4 bits of a byte, we can fit two nybbles into each byte without throwing any data away, thus getting 50% compression from the original which used a whole byte for every nybble. Although this compression ratio may seem very good, in reality very little is gained globally. First, only very small parts of actual files contain nybble-width data. Secondly, better methods exist that also take advantage of the patterns in the data. Block-to-variable codes ----------------------- Block-to-variable codes use a variable number of output bits for each input symbol. All statistical data compression systems, such as symbol ranking, Huffman coding, Shannon-Fano coding, and arithmetic coding belong to this group (these are explained in more detail later). The idea is to assign shorter codes for symbols that occur often, and longer codes for symbols that occur rarely. This provides a reduction in the average code length, and thus compression. There are three types of statistical codes: fixed, static, and adaptive. Static codes need two passes over the input message. During the first pass they gather statistics of the message so that they know the probabilities of the source symbols. During the second pass they perform the actual encoding. Adaptive codes do not need the first pass. They update the statistics while encoding the data. The same updating of statistics is done in the decoder so that they keep in sync, making the code uniquely decodable. Fixed codes are 'static' static codes. They use a preset statistical model, and the statistics of the actual message has no effect on the encoding. You just have to hope (or make certain) that the message statistics are close to the one the code assumes. However, 0-order statistical compression (and entropy) don't take advantage of inter-symbol relations. They assume symbols are disconnected variables, but in reality there is considerable relation between successive symbols. If I would drop every third character from this text, you would probably be able to decipher it quite well. First order statistical compression uses the previous character to predict the next one. Second order compression uses two previous characters, and so on. The more characters are used to predict the next character the better estimate of the probability distribution for the next character. But more is not only better, there are also prices to pay. The first drawback is the amount of memory needed to store the probability tables. The frequencies for each character encountered must be accounted for. And you need one table for each 'previous character' value. If we are using an adaptive code, the second drawback is the time needed to update the tables and then update the encoding accordingly. In the case of Huffman encoding the Huffman tree needs to be recreated. And the encoding and decoding itself certainly takes time also. We can keep the memory usage and processing demands tolerable by using a 0-order static Huffman code. Still, the Huffman tree takes up precious memory and decoding Huffman code on a 1-MHz 8-bit processor is slow and does not offer very good compression either. Still, statistical compression can still offer savings as a part of a hybrid compression system. For example: 'A' 1/2 0 'B' 1/4 10 'C' 1/8 110 'D' 1/8 111 "BACADBAABAADABCA" total: 32 bits 10 0 110 0 111 10 0 0 10 0 0 111 0 10 110 0 total: 28 bits This is an example of a simple statistical compression. The original symbols each take two bits to represent (4 possibilities), thus the whole string takes 32 bits. The variable-length code assigns the shortest code to the most probable symbol (A) and it takes 28 bits to represent the same string. The spaces between symbols are only there for clarity. The decoder still knows where each symbol ends because the code is a prefix code. On the other hand, I am simplifying things a bit here, because I'm omitting one vital piece of information: the length of the message. The file system normally stores the information about the end of file by storing the length of the file. The decoder also needs this information. We have two basic methods: reserve one symbol to represent the end of file condition or send the length of the original file. Both have their virtues. The best compressors available today take into account intersymbol probabilities. Dynamic Markov Coding (DMC) starts with a zero-order Markov model and gradually extends this initial model as compression progresses. Prediction by Partial Matching (PPM), although it really is a variable-to-block code, looks for a match of the text to be compressed in an order-n context and if there is no match drops back to an order n-1 context until it reaches order 0. Variable-to-block codes ----------------------- The previous compression methods handled a specific number of bits at a time. A group of bits were read from the input stream and some bits were written to the output. Variable-to-block codes behave just the opposite. They use a fixed-length output code to represent a variable-length part of the input. Variable-to-block codes are also called free-parse methods, because there is no pre-defined way to divide the input message into encodable parts (i.e. strings that will be replaced by shorter codes). Substitutional compressors belong to this group. Substitutional compressors work by trying to replace strings in the input data with shorter codes. Lempel-Ziv methods (named after the inventors) contain two main groups: LZ77 and LZ78. Lempel-Ziv 1977 +++++++++++++++ In 1977 Ziv and Lempel proposed a lossless compression method which replaces phrases in the data stream by a reference to a previous occurrance of the phrase. As long as it takes fewer bits to represent the reference and the phrase length than the phrase itself, we get compression. Kind-of like the way BASIC substitutes tokens for keywords. LZ77-type compressors use a history buffer, which contains a fixed amount of symbols output/seen so far. The compressor reads symbols from the input to a lookahead buffer and tries to find as long as possible match from the history buffer. The length of the string match and the location in the buffer (offset from the current position) is written to the output. If there is no suitable match, the next input symbol is sent as a literal symbol. Of course there must be a way to identify literal bytes and compressed data in the output. There are lot of different ways to accomplish this, but a single bit to select between a literal and compressed data is the easiest. The basic scheme is a variable-to-block code. A variable-length piece of the message is represented by a constant amount of bits: the match length and the match offset. Because the data in the history buffer is known to both the compressor and decompressor, it can be used in the compression. The decompressor simply copies part of the already decompressed data or a literal byte to the current output position. Variants of LZ77 apply additional compression to the output of the compressor, which include a simple variable-length code (LZB), dynamic Huffman coding (LZH), and Shannon-Fano coding (ZIP 1.x)), all of which result in a certain degree of improvement over the basic scheme. This is because the output values from the first stage are not evenly distributed, i.e. their probabilities are not equal and statistical compression can do its part. Lempel-Ziv 1978 +++++++++++++++ One large problem with the LZ77 method is that it does not use the coding space efficiently, i.e. there are length and offset values that never get used. If the history buffer contains multiple copies of a string, only the latest occurrance is needed, but they all take space in the offset value space. Each duplicate string wastes one offset value. To get higher efficiency, we have to create a real dictionary. Strings are added to the codebook only once. There are no duplicates that waste bits just because they exist. Also, each entry in the codebook will have a specific length, thus only an index to the codebook is needed to specify a string (phrase). In LZ77 the length and offset values were handled more or less as disconnected variables although there is correlation. Because they are now handled as one entity, we can expect to do a little better in that regard also. LZ78-type compressors use this kind of a dictionary. The next part of the message (the lookahead buffer contents) is searched from the dictionary and the maximum-length match is returned. The output code is an index to the dictionary. If there is no suitable entry in the dictionary, the next input symbol is sent as a literal symbol. The dictionary is updated after each symbol is encoded, so that it is possible to build an identical dictionary in the decompression code without sending additional data. Essentially, strings that we have seen in the data are added to the dictionary. To be able to constantly adapt to the message statistics, the dictionary must be trimmed down by discarding the oldest entries. This also prevents the dictionary from becoming full, which would decrease the compression ratio. This is handled automatically in LZ77 by its use of a history buffer (a sliding window). For LZ78 it must be implemented separately. Because the decompression code updates its dictionary in sychronization with the compressor the code remains uniquely decodable. Run-Length Encoding +++++++++++++++++++ Run length encoding also belongs to this group. If there are consecutive equal valued symbols in the input, the compressor outputs how many of them there are, and their value. Again, we must be able to identify literal bytes and compressed data. One of the RLE compressors I have seen outputs two equal symbols to indentify a run of symbols. The next byte(s) then tell how many more of these to output. If the value is 0, there are only two consecutive equal symbols in the original stream. Depending on how many bits are used to represent the value, this is the only case when the output is expanded. Run-length encoding has been used since day one in C64 compression programs because it is very fast and very simple. Part of this is because it deals with byte-aligned data and is essentially just copying bytes from one place to another. The drawback is that RLE can only compress identical bytes into a shorter representation. On the C64, only graphics and music data contain large runs of identical bytes. Program code rarely contains more than a couple of successive identical bytes. We need something better. That "something better" seems to be LZ77, which has been used in C64 compression programs for a long time. LZ77 can take advantage of repeating code/graphic/music data fragments and thus achieves better compression. The drawback is that practical LZ77 implementations tend to became variable-to-variable codes (more on that later) and need to handle data bit by bit, which is quite a lot slower than handling bytes. LZ78 is not practical for C64, because the decompressor needs to create and update the dictionary. A big enough dictionary would take too much memory and updating the dictionary would need its share of processor cycles. Variable-to-variable codes -------------------------- The compression algorithms in this category are mostly hybrids or concatenations of the previously described compressors. For example a variable-to-block code such as LZ77 followed by a statistical compressor like Huffman encoding falls into this category and is used in Zip, LHa, Gzip and many more. They use fixed, static, and adaptive statistical compression, depending on the program and the compression level selected. Randomly concatenating algorithms rarely produces good results, so you have to know what you are doing and what kind of files you are compressing. Whenever a novice asks the usual question: 'What compression program should I use?', they get the appropriate response: 'What kind of data you are compressing?' Borrowed from Tom Lane's article in comp.compression: It's hardly ever worthwhile to take the compressed output of one compression method and shove it through another compression method. Especially not if the second method is a general-purpose compressor that doesn't have specific knowledge of the first compression step. Compression is effective in direct proportion to the extent that it eliminates obvious patterns in the data. So if the first compression step is any good, it will leave little traction for the second step. Combining multiple compression methods is only helpful when the methods are specifically chosen to be complementary. A small sidetrack I want to take: This also brings us conveniently to another truth in lossless compression. There isn't a single compressor which would be able to losslessly compress all possible files (you can see the comp.compression FAQ for information about the counting proof). It is our luck that we are not interested in compressing all files. We are only interested in compressing a very small subset of all files. The more accurately we can describe the files we would encounter, the better. This is called modelling, and it is what all compression programs do and must do to be successful. Audio and graphics compression algorithm may assume a continuous signal, and a text compressor may assume that there are repeated strings in the data. If the data does not match the assumptions (the model), the algorithm usually expands the data instead of compressing it. _____________________________________________________________________ Representing Integers Many compression algorithms use integer values for something or another. Pucrunch is no exception as it needs to represent RLE repeat counts and LZ77 string match lengths and offsets. Any algorithm that needs to represent integer values can benefit very much if we manage to reduce the number of bits needed to do that. This is why efficient coding of these integers is very important. What encoding method to select depends on the distribution and the range of the values. Fixed, Linear ------------- If the values are evenly distributed throughout the whole range, a direct binary representation is the optimal choice. The number of bits needed of course depends on the range. If the range is not a power of two, some tweaking can be done to the code to get nearer the theoretical optimum log2(_range_) bits per value. Value Binary Adjusted 1&2 --------------------------- 0 000 00 000 H = 2.585 1 001 01 001 L = 2.666 2 010 100 010 (for flat distribution) 3 011 101 011 4 100 110 10 5 101 111 11 The previous table shows two different versions of how the adjustment could be done for a code that has to represent 6 different values with the minimum average number of bits. As can be seen, they are still both prefix codes, i.e. it's possible to (easily) decode them. If there is no definite upper limit to the integer value, direct binary code can't be used and one of the following codes must be selected. Elias Gamma Code ---------------- The Elias gamma code assumes that smaller integer values are more probable. In fact it assumes (or benefits from) a proportionally decreasing distribution. Values that use n bits should be twice as probable as values that use n+1 bits. In this code the number of zero-bits before the first one-bit (a unary code) defines how many more bits to get. The code may be considered a special fixed Huffman tree. You can generate a Huffman tree from the assumed value distribution and you'll get a very similar code. The code is also directly decodable without any tables or difficult operations, because once the first one-bit is found, the length of the code word is instantly known. The bits following the zero bits (if any) are directly the encoded value. Gamma Code Integer Bits -------------------------- 1 1 1 01x 2-3 3 001xx 4-7 5 0001xxx 8-15 7 00001xxxx 16-31 9 000001xxxxx 32-63 11 0000001xxxxxx 64-127 13 ... Elias Delta Code ---------------- The Elias Delta Code is an extension of the gamma code. This code assumes a little more 'traditional' value distribution. The first part of the code is a gamma code, which tells how many more bits to get (one less than the gamma code value). Delta Code Integer Bits -------------------------- 1 1 1 010x 2-3 4 011xx 4-7 5 00100xxx 8-15 8 00101xxxx 16-31 9 00110xxxxx 32-63 10 00111xxxxxx 64-127 11 ... The delta code is better than gamma code for big values, as it is asymptotically optimal (the expected codeword length approaches constant times entropy when entropy approaches infinity), which the gamma code is not. What this means is that the extra bits needed to indicate where the code ends become smaller and smaller proportion of the total bits as we encode bigger and bigger numbers. The gamma code is better for greatly skewed value distributions (a lot of small values). Fibonacci Code -------------- The fibonacci code is another variable length code where smaller integers get shorter codes. The code ends with two one-bits, and the value is the sum of the corresponding Fibonacci values for the bits that are set (except the last one-bit, which ends the code). 1 2 3 5 8 13 21 34 55 89 ---------------------------- 1 (1) = 1 0 1 (1) = 2 0 0 1 (1) = 3 1 0 1 (1) = 4 0 0 0 1 (1) = 5 1 0 0 1 (1) = 6 0 1 0 1 (1) = 7 0 0 0 0 1 (1) = 8 : : : : : : : 1 0 1 0 1 (1) = 12 0 0 0 0 0 1 (1) = 13 : : : : : : : : 0 1 0 1 0 1 (1) = 20 0 0 0 0 0 0 1 (1) = 21 : : : : : : : : : 1 0 0 1 0 0 1 (1) = 27 Note that because the code does not have two successive one-bits until the end mark, the code density may seem quite poor compared to the other codes, and it is, if most of the values are small (1-3). On the other hand, it also makes the code very robust by localizing and containing possible errors. Although, if the Fibonacci code is used as a part of a larger system, this robustness may not help much, because we lose the synchronization in the upper level anyway. Most adaptive methods can't recover from any errors, whether they are detected or not. Even in LZ77 the errors can be inherited infinitely far into the future. Comparison between delta, gamma and Fibonacci code lengths ---------------------------------------------------------- Gamma Delta Fibonacci 1 1 1 2.0 2-3 3 4 3.5 4-7 5 5 4.8 8-15 7 8 6.4 16-31 9 9 7.9 32-63 11 10 9.2 64-127 13 11 10.6 The comparison shows that if even half of the values are in the range 1..7 (and other values relatively near this range), the Elias gamma code wins by a handsome margin. Golomb and Rice Codes --------------------- Golomb (and Rice) codes are prefix codes that are suboptimal (compared to Huffman), but very easy to implement. Golomb codes are distinguished from each other by a single parameter m. This makes it very easy to adjust the code dynamically to adapt to changes in the values to encode. Golomb m=1 m=2 m=3 m=4 m=5 m=6 Rice k=0 k=1 k=2 --------------------------------------------------- n = 0 0 00 00 000 000 000 1 10 01 010 001 001 001 2 110 100 011 010 010 0100 3 1110 101 100 011 0110 0101 4 11110 1100 1010 1000 0111 0110 5 111110 1101 1011 1001 1000 0111 6 1111110 11100 1100 1010 1001 1000 7 : 11101 11010 1011 1010 1001 8 : 111100 11011 11000 10110 10100 To encode an integer n (starting from 0 this time, not from 1 as for Elias codes and Fibonacci code) using the Golomb code with parameter m, we first compute floor( n/m ) and output this using a unary code. Then we compute the remainder n mod m and output that value using a binary code which is adjusted so that we sometimes use floor( log2(m) ) bits and sometimes ceil( log2(m) ) bits. Rice coding is the same as Golomb coding except that only a subset of parameters can be used, namely the powers of 2. In other words, a Rice code with the parameter k is equal to Golomb code with parameter m = 2^k. Because of this the Rice codes are much more efficient to implement on a computer. Division becomes a shift operation and modulo becomes a bit mask operation. Hybrid/Mixed Codes ------------------ Sometimes it may be advantageous to use a code that combines two or more of these codes. In a way the Elias codes are already hybrid codes. The gamma code has a fixed huffman tree (a unary code) and a binary code part, the delta code has a gamma code and a binary code part. The same applies to Golomb and Rice codes because they consist of a unary code part and a linear code (adjusted) part. So now we have several alternatives to choose from. We simply have to do a little real-life research to determine how the values we want to encode are distributed so that we can select the optimum code to represent them. Of course we still have to keep in mind that we intend to decode the thing with a 1-MHz 8-bit processor. As always, compromises loom on the horizon. Pucrunch uses Elias Gamma Code, because it is the best alternative for that task and is very close to static Huffman code. The best part is that the Gamma Code is much simpler to decode and doesn't need additional memory. _____________________________________________________________________ Closer Look Because the decompression routines are usually much easier to understand than the corresponding compression routines, I will primarily describe only them here. This also ensures that there really _is_ a decompressor for a compression algorithm. Many are those people who have developed a great new compression algorithm that outperforms all existing versions, only to later discover that their algorithm doesn't save enough information to be able to recover the original file from the compressed data. Also, the added bonus is that once we have a decompressor, we can improve the compressor without changing the file format. At least until we have some statistics to develop a better system. Many lossy video and audio compression systems only document and standardize the decompressor and the file or stream format, making it possible to improve the encoding part of the process when faster and better hardware (or algorithms) become available. RLE --- void DecompressRLE() { int oldChar = -1; int newChar; while(1) { newChar = GetByte(); if(newChar == EOF) return; PutByte(newChar); if(newChar == oldChar) { int len = GetLength(); while(len > 0) { PutByte(newChar); len = len - 1; } } oldChar = newChar; } } This RLE algorithm uses two successive equal characters to mark a run of bytes. I have in purpose left open the question of how the length is encoded (1 or 2 bytes or variable-length code). The decompressor also allows chaining/extension of RLE runs, for example 'a', 'a', 255, 'a', 255 would output 513 'a'-characters. In this case the compression algorithm is almost as simple. void CompressRLE() { int oldChar = -1; int newChar; while(1) { newChar = GetByte(); if(newChar==oldChar) { int length = 0; if(newChar == EOF) return; PutByte(newChar); /* RLE indicator */ /* Get all equal characters */ while((newChar = GetByte()) == oldChar) { length++; } PutLength(length); } if(newChar == EOF) return; PutByte(newChar); oldChar = newChar; } } If there are two equal bytes, the compression algorithm reads more bytes until it gets a different byte. If there was only two equal bytes, the length value will be zero and the compression algorithm expands the data. A C64-related example would be the compression of the BASIC ROM with this RLE algorithm. Or actually expansion, as the new file size is 8200 bytes instead of the original 8192 bytes. Those equal byte runs that the algorithm needs just aren't there. For comparison, pucrunch manages to compress the BASIC ROM into 7288 bytes, the decompression code included. Even Huffman coding manages to compress it into 7684 bytes. "BAAAAAADBBABBBBBAAADABCD" total: 24*8=192 bits "BAA",4,"DBB",0,"ABB",3,"AA",1,"DABCD" total: 16*8+4*8=160 bits This is an example of how the presented RLE encoder would work on a string. The total length calculations assume that we are handling 8-bit data, although only values from 'A' to 'D' are present in the string. After seeing two equal characters the decoder gets a repeat count and then adds that many more of them. Notice that the repeat count is zero if there are only two equal characters. Huffman Code ------------ int GetHuffman() { int index = 0; while(1) { if(GetBit() == 1) { index = LeftNode(index); } else { index = RightNode(index); } if(LeafNode(index)) { return LeafValue(index); } } } My pseudo code of the Huffman decode function is a very simplified one, so I should probably describe how the Huffman code and the corresponding binary tree is constructed first. First we need the statistics for all the symbols occurring in the message, i.e. the file we are compressing. Then we rank them in decreasing probability order. Then we combine the smallest two probabilities and assign 0 and 1 to the binary tree branches, i.e. the original symbols. We do this until there is only one composite symbol left. Depending on where we insert the composite symbols we get different Huffman trees. The average code length is equal in both cases (and so is the compression ratio), but the length of the longest code changes. The implementation of the decoder is usually more efficient if we keep the longest code as short as possible. This is achieved by inserting the composite symbols (new nodes) before all symbols/nodes that have equal probability. "BAAAAAADBBABBBBBAAADABCD" A (11) B (9) D (3) C (1) Step 1 Step 2 Step 3 'A' 0.458 'A' 0.458 C2 0.542 0\ C3 'B' 0.375 'B' 0.375 0\ C2 'A' 0.458 1/ 'D' 0.125 0\ C1 C1 0.167 1/ 'C' 0.042 1/ C3 0 / \ 1 / 'A' C2 0 / \ 1 'B' \ C1 0 / \ 1 'D' 'C' So, in each step we combine two lowest-probability nodes or leaves into a new node. When we are done, we have a Huffman tree containing all the original symbols. The Huffman codes for the symbols can now be gotten by starting at the root of the tree and collecting the 0/1-bits on the way to the desired leaf (symbol). We get: 'A' = 1 'B' = 00 'C' = 011 'D' = 010 These codes (or the binary tree) are used when encoding the file, but the decoder also needs this information. Sending the binary tree or the codes would take a lot of bytes, thus taking away all or most of the compression. The amount of data needed to transfer the tree can be greatly reduced by sending just the symbols and their code lengths. If the tree is traversed in a canonical (predefined) order, this is all that is needed to recreate the tree and the Huffman codes. By doing a 0-branch-first traverse we get: Symbol Code Code Length 'B' 00 2 'D' 010 3 'C' 011 3 'A' 1 1 So we can just send 'B', 2, 'D', 3, 'C', 3, 'A', 1 and the decoder has enough information (when it also knows how we went through the tree) to recreate the Huffman codes and the tree. Actually you can even drop the symbol values if you handle things a bit differently (see the Deflate specification in RFC1951), but my arrangement makes the algorithm much simpler and doesn't need to transfer data for symbols that are not present in the message. Basically we start with a code value of all zeros and the appropriate length for the first symbol. For other symbols we first add the code value with 1 and then shift the value left or right to get it to be the right size. In the example we first assign 00 to 'B', then add one to get 01, shift left to get a 3-bit codeword for 'D' making it 010 like it should. For 'C' add 1, you get 011, no shift because the codewords is the right size already. And for 'A' add one and get 100, shift 2 places to right and get 1. The Deflate algorithm in essence attaches a counting sort algorithm to this algorithm, feeding in the symbols in increasing code length order. Oh, don't worry if you don't understand what the counting sort has to do with this. I just wanted to give you some idea about it if you some day read the deflate specification or the gzip source code. Actually, the decoder doesn't necessarily need to know the Huffman codes at all, as long as it has created the proper internal representation of the Huffman tree. I developed a special table format which I used in the C64 Huffman decode function and may present it in a separate article someday. The decoding works by just going through the tree by following the instructions given by the input bits as shown in the example Huffman decode code. Each bit in the input makes us go to either the 0-branch or the 1-branch. If the branch is a leaf node, we have decoded a symbol and just output it, return to the root node and repeat the procedure. A technique related to Huffman coding is Shannon-Fano coding. It works by first dividing the symbols into two equal-probability groups (or as close to as possible). These groups are then further divided until there is only one symbol in each group left. The algorithm used to create the Huffman codes is bottom-up, while the Shannon-Fano codes are created top-down. Huffman encoding always generates optimal codes (in the entropy sense), Shannon-Fano sometimes uses a few more bits. There are also ways of modifying the statistical compression methods so that we get nearer to the entropy. In the case of 'A' having the probability 0.75 and 'B' 0.25 we can decide to group several symbols together, producing a variable-to-variable code. "AA" 0.5625 0 "B" 0.25 10 "AB" 0.1875 11 If we separately transmit the length of the file, we get the above probabilities. If a file has only one 'A', it can be encoded as length=1 and either "AA" or "AB". The entropy of the source is H = 0.8113, and the average code length (per source symbol) is approximately L = 0.8518, which is much better than L = 1.0, which we would get if we used a code {'A','B'} = {0,1}. Unfortunately this method also expands the number of symbols we have to handle, because each possible source symbol combination is handled as a separate symbol. Arithmetic Coding ----------------- Huffman and Shannon-Fano codes are only optimal if the probabilities of the symbols are negative powers of two. This is because all prefix codes work in the bit level. Decisions between tree branches always take one bit, whether the probabilities for the branches are 0.5/0.5 or 0.9/0.1. In the latter case it would theoretically take only 0.15 bits (-log2(0.9)) to select the first branch and 3.32 bits (-log2(0.1)) to select the second branch, making the average code length 0.467 bits (0.9*0.15 + 0.1*3.32). The Huffman code still needs one bit for each decision. Arithmetic coding does not have this restriction. It works by representing the file by an interval of real numbers between 0 and 1. When the file size increases, the interval needed to represent it becomes smaller, and the number of bits needed to specify that interval increases. Successive symbols in the message reduce this interval in accordance with the probability of that symbol. The more likely symbols reduce the range by less, and thus add fewer bits to the message. 1 Codewords +-----------+-----------+-----------+ | |8/9 YY | Detail |<- 31/32 .11111 | +-----------+-----------+<- 15/16 .1111 | Y | | too small |<- 14/16 .1110 |2/3 | YX | for text |<- 6/8 .110 +-----------+-----------+-----------+ | | |16/27 XYY |<- 10/16 .1010 | | +-----------+ | | XY | | | | | XYX |<- 4/8 .100 | |4/9 | | | +-----------+-----------+ | | | | | X | | XXY |<- 3/8 .011 | | |8/27 | | | +-----------+ | | XX | | | | | |<- 1/4 .01 | | | XXX | | | | | |0 | | | +-----------+-----------+-----------+ As an example of arithmetic coding, lets consider the example of two symbols X and Y, of probabilities 2/3 and 1/3. To encode a message, we examine the first symbol: If it is a X, we choose the lower partition; if it is a Y, we choose the upper partition. Continuing in this manner for three symbols, we get the codewords shown to the right of the diagram above. They can be found by simply taking an appropriate location in the interval for that particular set of symbols and turning it into a binary fraction. In practice, it is also necessary to add a special end-of-data symbol, which is not represented in this simple example. This explanation may not be enough to help you understand arithmetic coding. There are a lot of good articles about arithmetic compression in the net, for example by Mark Nelson. Arithmetic coding is not practical for C64 for many reasons. The biggest reason being speed, especially for adaptive arithmetic coding. The close second reason is of course memory. Symbol Ranking -------------- Symbol ranking is comparable to Huffman coding with a fixed Huffman tree. The compression ratio is not very impressive (reaches Huffman code only is some cases), but the decoding algorithm is very simple, does not need as much memory as Huffman and is also faster. int GetByte() { int index = GetUnaryCode(); return mappingTable[index]; } The main idea is to have a table containing the symbols in descending probability order (rank order). The message is then represented by the table indices. The index values are in turn represented by a variable-length integer representation (these are studied in the next article). Because more probable symbols (smaller indices) take less bits than less probable symbols, in average we save bits. Note that we have to send the rank order, i.e. the symbol table too. "BAAAAAADBBABBBBBAAADABCD" total: 24*8=192 bits Rank Order: A (11) B (9) D (3) C (1) 4*8=32 bits Unary Code: 0 10 110 1110 "100000001101010010101010100001100101110110" 42 bits total: 74 bits The statistics rank the symbols in the order ABDC (most probable first), which takes approximately 32 bits to transmit (we assume that any 8-bit value is possible). The indices are represented as a code {0, 1, 2, 3} = {0, 10, 110, 1110}. This is a simple unary code where the number of 1-bits before the first 0-bit directly give the integer value. The first 0-bit also ends a symbol. When this code and the rank order table are combined in the decoder, we get the reverse code {0, 10, 110, 1110} = {A, B, D, C}. Note that in this case the code is very similar to the Huffman code we created in a previous example. LZ78 ---- LZ78-based schemes work by entering phrases into a dictionary and then, when a repeat occurrence of that particular phrase is found, outputting the dictionary index instead of the phrase. For example, LZW (Lempel-Ziv-Welch) uses a dictionary with 4096 entries. In the beginning the entries 0-255 refer to individual bytes, and the rest 256-4095 refer to longer strings. Each time a new code is generated it means a new string has been selected from the input stream. New strings that are added to the dictionary are created by appending the current character K to the end of an existing string w. The algorithm for LZW compression is as follows: set w = NIL loop read a character K if wK exists in the dictionary w = wK else output the code for w add wK to the string table w = K endloop Input string: /WED/WE/WEE/WEB Input Output New code and string /W / 256 = /W E W 257 = WE D E 258 = ED / D 259 = D/ WE 256 260 = /WE / E 261 = E/ WEE 260 262 = /WEE /W 261 263 = E/W EB 257 264 = WEB B A sample run of LZW over a (highly redundant) input string can be seen in the diagram above. The strings are built up character-by-character starting with a code value of 256. LZW decompression takes the stream of codes and uses it to exactly recreate the original input data. Just like the compression algorithm, the decompressor adds a new string to the dictionary each time it reads in a new code. All it needs to do in addition is to translate each incoming code into a string and send it to the output. A sample run of the LZW decompressor is shown in below. Input code: /WEDEB Input Output New code and string / / W W 256 = /W E E 257 = WE D D 258 = ED 256 /W 259 = D/ E E 260 = /WE 260 /WE 261 = E/ 261 E/ 262 = /WEE 257 WE 263 = E/W B B 264 = WEB The most remarkable feature of this type of compression is that the entire dictionary has been transmitted to the decoder without actually explicitly transmitting the dictionary. The decoder builds the dictionary as part of the decoding process. See also the article "LZW Compression" by Bill Lucier in C=Hacking issue 6 and "LZW Data Compression" by Mark Nelson mentioned in the references section. _____________________________________________________________________ Conclusions =========== That's more than enough for one article. What did we get out of it ? Statistical compression works with uneven symbol probabilities to reduce the average code length. Substitutional compressors replace strings with shorter representations. All popular compression algorithms use LZ77 or LZ78 followed by some sort of statistical compression. And you can't just mix and match different algorithms and expect good results. There are no shortcuts in understanding data compression. Some things you only understand when trying out them yourself. However, I hope that this article has given you at least a vague grasp of how different compression methods really work. I would like to send special thanks to Stephen Judd for his comments. Without him this article would've been much more unreadable than it is now. On the other hand, that's what the magazine editor is for :-) The second part of the story is a detailed talk about pucrunch. I also go through the corresponding C64 decompression code in detail. If you are impatient and can't wait for the next issue, you can take a peek into http://www.cs.tut.fi/%7Ealbert/Dev/pucrunch/ for a preview. _____________________________________________________________________ References ========== * The comp.compression FAQ http://www.cis.ohio-state.edu/hypertext/faq/usenet/ compression-faq/top.html * A Data Compression Review http://www.ics.uci.edu/%7Edan/pubs/DataCompression.html * Data Compression Class http://www.cs.unt.edu/home/srt/5330/ * Mark Nelson's Homepage http://web2.airmail.net/markn/ + LZW Data Compression http://web2.airmail.net/markn/articles/lzw/lzw.htm + Arithmetic Coding Article http://web2.airmail.net/markn/articles/arith/part1.htm + Data Compression with the Burrows-Wheeler Transform http://web2.airmail.net/markn/articles/bwt/bwt.htm * Charles Bloom's Page http://wwwvms.utexas.edu/%7Ecbloom/ * The Redundancy of the Ziv-Lempel Algorithm for Memoryless Sources http://ei0.ei.ele.tue.nl/%7Etjalling/zivlem/zivlem.html * Ross Williams' Compression Pages http://www.ross.net/home/ * DEFLATE Compressed Data Format Specification version 1.3 http://www.funet.fi/pub/doc/rfc/rfc1951.txt * Markus F.X.J. Oberhumer's Compression Links http://wildsau.idv.uni-linz.ac.at/mfx/compress.html * The Lossless Compression (Squeeze) Page http://www.cs.sfu.ca/CC/365/li/squeeze/ ........ .... .. . C=H :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 3D Graphics for the Masses: lib3d and Cool World -------------------------- by Stephen L. Judd sjudd@nwu.edu Well folks, it's time once again for some 3D graphics. This will, I think, be more or less the final word on the subject, at least from me! I'm pooped, and I think these routines pretty much push these algorithms as far as they're going to go. And there are so many other interesting things to move on to! These routines, not to mention this article, are the codification of all those years of algorithms and derivations and everything else. Those past efforts created working prototypes; this one is the production model. Nate Dannenberg suggested that this be done, and who am I to disobey? Besides, after a break of a few years it's going to be fun to rederive all the equations and algorithms from scratch, and do a "for-real" implementation, improving the good ideas and fixing the bad. Right? Right. So that's what I did, and that's what this article does. The first section of the article summarizes the basics of 3D graphics: projections and rotations. Since in my experience many people don't remember their high school math, I've also covered the basic mathematical tools needed, like trigonometry and linear algebra, and other related issues. The next section covers constructing a 3D world: representing objects, navigating through the world, things like that. The third section covers the main library routines and their implementation, including lots of code disassembly. The fourth section covers Cool World, a program which is a demonstration of the 3D library. The final section just summarizes the 3d library routines, calling conventions, parameters used, things like that. Since this article is enormous, I have left out the complete source code; the truly motivated can visit http://stratus.esam.nwu.edu/~judd/fridge/ to check out the full source for both Cool World and the 3d library. The binaries are also present there. By this time you may have asked, "What exactly _is_ this 3d library?" Glad you asked. It is a set of routines that are important for doing 3D graphics: rotations, projections, drawing polygons, that sort of thing. The routines are very flexible, compact, and extremely fast. They can draw to any VIC bank, and still leave enough room for eight sprite definitions. What the routines are not is a "3D world construction kit". A program has to be written which utilizes the routines. Which leads to Cool World. CW is, simply, a program which demonstrates using the 3D library. It is very large. It has some seventeen objects in it -- the initial tetrahedron is the 'center'; straight ahead of it is squaresville; to the left is a bunch of stars; straight down is the Cobra Mk III; straight back is a line of tetrahedrons. It also has some other fun stuff like the starfield and a tune. It doesn't have Kim Basinger, unfortunately. Oh yeah: the _whole point_ of the 3d library is for you to use it in your own programs! You can sell those programs if you like, too. Doesn't bother me; in fact I would be quite flattered to see it used in some cool and popular program. Why re-invent the wheel when the routines are already written? Use the 3d library. Live the 3d library. Do something interesting with it. If nobody uses it, it might as well have never been written, right? Right. You know you want to use it. So use it! But before you use it, you better understand it. So let's start at the very beginning (a very good place to start). --------- Section 1: 3D Basics and review --------- This is just going to be a quick summary. For more detail you ought to go back to some of the earlier articles. First we need to decide on a coordinate system. A convenient system for dealing with the computer is to have the x-axis point to the right and the y-axis to point down the screen -- the usual coordinate system with x=0 y=0 being in the upper-left corner of the screen. The z-axis can then point into the monitor (i.e. z=20 is behind the monitor screen somewhere, and z=-20 is somewhere behind where you're sitting); this keeps the coordinate system right-handed. The next thing is to figure out an equation for projecting from three dimensions into two dimensions. In other words: how to paint a picture. One of the great breakthroughs for art at the beginning of the Renaissance was the understanding of perspecitve. The first thing to notice is that far-away objects look smaller. The next thing to observe is that straight lines seem to meet in the middle -- like looking down a long road or sidewalk or railroad tracks. That's perspective: far-off objects get smaller _towards the center of vision_. Well that's an easy equation: just take the coordinate, and divide by the distance away from us. If we're looking down the z-axis, x' = x/z y' = y/z gives us a pair of projected points. Objects which are far away have a large value for z, which means x' and y' will be proportionally smaller. For really large z, they go to zero -- they go to the center of our vision. Now, how can we make objects appear larger? One way is to stand closer to them -- that changes the perspective. Another way is to magnify them, with a lens. This is how a telescope works, and also how the old Mark-I eyeball works as well. Whereas perspective makes far-off points behave differently than near ones, magnification just expands all points equally. And that's exactly how to put it in the equation: x' = d * x/z y' = d * y/z where d is some constant magnification factor (a number, like 12). And the above are the projection equations. A very important skill is the ability to 'read' an equation. The above equation takes a point, divides by the distance away from us, and then multiplies by the magnification constant. It says that far-off objects will be small, and that all objects are magnified equally. It also implies that the z-coordinates better all be positive or all negative. If an object has some positive z-coordinates and some negative, that means that some of its points are in front of us and some are behind us. In other words, that we are standing inside the object! A proper derivation is as follows: consider a pinhole camera. A light ray bounces off some object at a point (x,y,z) and passes through the pinhole, located at the origin (0,0,0). We then place a photographic plate parallel to the x-y plane, at z'=d, and figure out where the light ray hits the plate. The equation of the light ray is the line (x', y', z') = t*(x,y,z) and it hits the plate when z'=d, which happens when tz = d so when t = d/z. Thus the coordinates on the plate (the film) are x' = d/z * x y' = d/z * y which gives the earlier equations. Moving the film up and down will magnify the image, corresponding to changing the value of d. If d is negative, the image will be inverted. Positive d corresponds to having the film between the pinhole lens and the object, but mathematically it gives the same answer without inverting the object (since x' and y' won't have a minus sign in front of them). Representing 3D objects ----------------------- The important thing to recognize from the above is that straight lines in 3D will still be straight lines in 2D -- the projection doesn't turn straight lines into curves or anything like that. So, to project a straight line from 3D into 2D all that is needed are the _endpoints_ of the line. Project those two endpoints from 3D into 2D, and then all that is needed is to draw a line between the two _projected_ points. Most of the objects we will be dealing with will be made up of a series of flat plates, because these are easier to do calculations with (ever noticed the main difference between the stealth fighter and the stealth bomber?). In other words: polygons. These polygons are just flat objects with several straight sides. All we need are the vertices of each polygon (the endpoints of each of the lines); from those we can reconstruct all the in-between points. A very simple example is a cube. It has six faces. The eight corners of a cube might be located at (+/-1, +/-1, +/-1). Project those eight points and connect the projected points in the right way, and Viola! Violin! 3D graphics. The next thing we will want to do is rotate an object. For this we need a little trig, and it's very helpful to know a little about linear algebra and vectors. What's that? You don't remember this stuff? For shame! But we can fix that up in no time. Trig review in two paragraphs. ----------- Take a look at a triangle sometime. No matter how large or small you draw a particular triangle, it still looks the same because all of the sides and angles are in proportion to one another. Now fix one of the angles at 90 degrees, to form a right triangle. The minute you choose one of the other angles, the opposite angle is determined (since the angles have to add up to 180 degrees). And when you know all the angles you know the _ratios_ of the sides to each other -- you don't know the actual length of the sides, but you know how the triangle looks and hence its proportions. And that is pretty much all of trig. Draw a right triangle, and pick an angle (call that angle theta). The hypoteneuse is the longest side of a triangle, and hence the side opposite the 90 degree angle. The 'adjacent' side is the side which touches the angle theta; the 'opposite' side is the side opposite theta (imagine that!). We _define_ sine, cosine, and tangent as cos(theta) = adjacent/hypoteneuse sin(theta) = opposite/hypoteneuse tan(theta) = sin(theta)/cos(theta) = opposite/adjacent and that's all of trig, right there. Everything else comes from those three definitions. If you can't remember them, just remember the famous Indian Chief SOHCAHTOA, who fought so bravely for the cause of his people and mathematicians everywhere (SOH: sin-opposite-hyp; CAH: cos-adjacent-hyp; TOA: tan-opposite-adjacent). Polar coordinates ----------------- Now we've got some tools to do some useful calculations with, once we remember the Pythagorean theorem, a^2 + b^2 = c^2, where c = the hypoteneuse and a,b are the sides of a right triangle. Before doing rotations it is helpful to understand polar coordinates. Draw a set of normal coordinate axis on a piece of paper, and draw a point somewhere (at 3,2 say). Label this point x,y and draw a line from the origin (0,0) to that point, and call its length "r". Label the angle between that line and the positive x-axis as "theta", and draw a line straight down from x,y to the x-axis. Whaddaya know? It's a right triangle. The length of one side is x, the length of the other side is y, and the length of the hypoteneuse is r. And the trig definitions tell us that cos(theta) = x/r sin(theta) = y/r tan(theta) = y/x. So now we can define sin, cos, and tan for all angles theta just by drawing a little picture. Two coordinates, x and y, are used to locate the point. Another two coordinates in the picture are "r" and "theta", and they are just as good for locating where a point is. In fact, the above equations give the x and y coordinates of a point (r,theta): x = r * cos(theta) y = r * sin(theta) They also give us the r and theta coordinates of a point (x,y): tan(theta) = y/x r^2 = x^2 + y^2 You may also have noticed that the trig formula cos(theta)^2 + sin(theta)^2 = 1 follows from the above trig definitions, since x^2 + y^2 = r^2. In the Cartesian (or rectangular) system there are two coordinates, x and y. The equation x=constant is a vertical line and the equation y=constant is a horizontal line, so this is a system of straight lines which cross each other at right angles. In polar coordinates the equation theta=constant is a radial line, and r=constant gives a circle (constant radius, you know). So polar coordinates consists of circles which intersect radial lines (note that they also intersect at right angles). And the equations above tell how to convert between the two systems. There are many other coordinate systems, btw. There are elliptical coordinates and parabolic coordinates and other strange systems. Why bother? For one thing, if you're solving an equation on a round plate it's awfully convenient to use polar coordinates. For another, we can now do some rotations. (And for another, you can draw cool graphs like r=cos(3*theta)). Rotations --------- Start with a point (r,theta) and rotate it to a new point (r,theta+s) i.e. rotate by an amount s. The original coordinate was x = r*cos(theta) y = r*sin(theta) and the new coordinate is x' = r*cos(theta+s) y = r*sin(theta+s) so by using the trig identities for cos(a+b) and sin(a+b) we arrive at the simple expressions x' = x*cos(s) - y*sin(s) y' = x*sin(s) + y*cos(s) for the rotated coordinates x' and y' in terms of the original coordinates x and y. The above is a two-dimensional rotation. Three-dimensional rotation is done with a series of two-dimensional rotations. The above rotates x and y, but keeps z fixed (I don't see a z anywhere in there, at least). In other words, it rotates about the z-axis. A rotation about the x-axis looks like x' = x*cos(s) - z*sin(s) z' = x*sin(s) + z*cos(s) and a rotation about the y-axis looks like x' = x*cos(s) + z*sin(s) z' = -x*sin(s) + z*cos(s) (the opposite minus sign just comes from the orientation of the y-axis). Rotations in three dimensions do NOT commute. Just by trying with a book it is very easy to see that a rotation of 45 degrees about the x-axis and then 45-degrees about the y-axis gives a very different result from first rotating about the y-axis and then the x-axis. To really make rotations powerful we need a little linear algebra. But first... Radians ("God's units") ------- Just for completeness... what is an angle, really? It's not a length, it's not a direction... what is it? And why are there 360 "angles" in a circle? The answer to the second is "because the ancient Babylonians used base 60 for all their calculations." In other words, degrees are totally arbitrary. There could just as easily be 1000 degrees in a circle. So, what is an angle? Think about a circle. It has two lengths associated with it: the length "across" (the diameter D) and the length "around" (the circumference C). And, like triangles, no matter how large or small the circle is drawn, those lengths stay in proportion. That is, C/D = constant That constant is, of course, pi = 3.1415926... This then gives the equation for the circumference of a circle as C = pi*D = 2*pi*r where r=radius. But what is an angle? Draw two radii in the circle. We _define_ the angle between those two radii as the length of the subtended circumference divided by the radius: angle = length / radius. So again, no matter what the _size_ of the circle is the _angle_ stays the same. The length is just a fraction of the circumference, which is 2*pi*radius; this means that the angle is just a fraction of 2*pi. These are radians. There are 2*pi of them in a circle. A quarter of a circle (90 degrees) is just 1/4 (2*pi) = pi/2 radians. An eighth is pi/4 radians. And so on. These are of course very natural units for an angle. The above definition has angle equal to a length divided by a length; radians have no dimension (whereas degrees are a dimension, just like feet or pounds or seconds are). Degrees are useful for talking and writing, but radians are what is needed for calculations. Vectors and Linear Algebra -------------------------- A vector (in three dimensions) is simply a line drawn from the origin (0,0,0) to some point (x,y,z). Since they always emanate from the origin, it is correct to refer to "the vector (x,y,z)". The important thing is that it has both length _and_ direction. A physical example is the difference between velocity and speed. Speed is just a quantity: for example, "120 Miles per hour". Velocity, on the other hand, has _direction_ -- you might be going straight up, or straight down, or turning around a curve, etc. and the _length_ of the velocity vector gives the speed: 120 MPH. But all we need to worry about here is the geometric meaning, and the difference between the _point_ (Px,Py,Pz) and the _vector_ (Px, Py, Pz). The point P is just a point, but geometrically the vector P is a line extending *from* the origin *to* the point P -- it has a length, and a direction: it points in the direction of (Px, Py, Pz). We will be using vectors for rotations, and to figure out what direction something points, and all sorts of other stuff. The dimension of a vector is the number of elements in that vector. Let P be a vector. A 2D vector might be P=(Px,Py). A three dimensional vector example is P=(Px,Py,Pz). P=(p1,p2,p3,p4,p5,p6) would be a six-dimensional vector. So an n-dimensional vector is just a list of n independent quantities. We'll just be dealing with two and three dimensional vectors here, though, so when you see a sentence like "The vector v1" just think of (v1x, v1y, v1z). The length of a vector is again given by Pythagorus: r^2 = Px^2 + Py^2 + Pz^2 + ... i.e. the sum of the squares of all the elements. This is a good calculation to avoid in algorithms, since it is expensive, but it is useful to know. The simplest thing one can do with a vector is change its length, by multiplying by a constant: c*(Px,Py,Pz) = (c*Px, c*Py, c*Pz). Multiplying by a constant multiplies all elements in the vector by that constant. Just like with triangles all lengths increase proportionally, so it is a vector which points in the same direction but has a different length. Two vector operations that are very useful are the "dot product" and the "cross product". I'll write the dot product of two vectors R and P as either R.P or , and it is defined as R . P = |R| |P| cos(theta) that is, the length of R times the length of P times the cosine of the angle between the two vectors. From this it is easy to show that the dot product may also be written as R . P = Rx*Px + Ry*Py + ... that is, multiply the individual components together and add them up. Note that the dot product gives a _number_ (a scalar), NOT a vector. Note also that the dot product between two vectors separated by an angle greater than pi/2 will be negative, from the first equation, and that the dot product of two perpendicular vectors is zero. The dot product is sometimes referred to as the inner (or scalar) product. The cross-product (sometimes called the vector product or skew product) is denoted by RxP and is given by R x P = (Ry*Pz-Rz*Py, Rz*Px-Rx*Pz, Rx*Py-Ry*Px) As you can see, the result is a _vector_. In fact, this vector is perpendicular to both R and P -- it is perpendicular to the plane that R and P lie in. Its length is given by length = |R| |P| sin(theta) Note that P x R = - R x P; the direction of the resulting vector is usually determined by the "right hand rule". All that is important here is to remember that the cross-product generates perpendicular vectors. We won't be using any cross products in this article. There are lots of other things we can do to vectors. One of the most important is to multiply by a _matrix_. A matrix is like a bunch of vectors grouped together, so it has rows and columns. An example of a 2x2 matrix is [a b] [c d] an example of a 3x3 matrix is [a b c] [d e f] [g h i] and so on. The number of rows doesn't have to equal the number of columns. In fact, an n-dimensional vector is just an n x 1 (read "n by 1") matrix: n rows, but one column. We add matrices together by adding the individual elements: [a1 a2 a3] [b1 b2 b3] [a1+b1 a2+b2 a3+b3] [a4 a5 a6] + [b4 b5 b6] = [a4+b4 a5+b5 a6+b6] [a7 a8 a9] [b7 b8 b9] [a7+b7 a8+b8 a9+b9] We can multiply by a constant, which just multiplies all elements by that constant (just like the vector). Matrices can also be multiplied. The usual rule is "row times column". That is, given two matrices A and B, you take rows of A and dot them with columns of B: [A1 A2] [B1 B2] = [A1*B1+A2*B3 A1*B2+A2*B4] [A3 A4] [B3 B4] [A3*B1+A4*B3 A3*B2+A4*B4] In the above, the (1,1) element is the first row of A (A1 A2) times the first column of B (B1 B3) to get A1*B1+A2*B3. And so on. (With a little practice this becomes very easy). We will be multiplying rotation matrices together, and multiplying matrices times vectors. Although "row times column" is the usual way that this is taught, it can also be looked at as "columns times elements". The easiest example is to multiply a matrix A times a vector x. The first method gives: [a1 a2 a3] [ ] [a1*x1 + a2*x2 + a3*x3] let A = [a4 a5 a6] then Ax = [ ] = [a4*x1 + a5*x2 + a6*x3] [a7 a8 a9] [ ] [a7*x1 + a8*x2 + a9*x3] The right-hand part may be written as [a1] [a2] [a3] x1*[a4] + x2*[a5] + x3*[a6] [a7] [a8] [a9] or, in other words, Ax = x1*column1 + x2*column2 + x3*column3 that is, the components of x times the columns of A, added together. This is a very useful thing to be aware of, as we shall see. Note that normal multiplication commutes: 3*2 = 2*3. In matrix multiplication, this is NOT true. Multiplication in general does NOT commute, and AB is usually different from BA. We can also divide by matrices, but it isn't called division. It's called inversion. Let's say you have an equation like 5*x = b. To solve for x you would just multiply both sides by 1/5 i.e. by the "inverse" of 5. To solve a matrix equation like Ax = b we just multiply both sides by the inverse of A -- call it A'. And in just the same way that 1/a * a is one, a matrix times its inverse is the _identity matrix_ which is the matrix with "1" down the diagonal: [1 0 0] I = [0 1 0] [0 0 1] It is called the identity because IA = A; multiplying by the identity matrix is just like multiplying by one. Inverting a matrix is in general a very expensive operation, and we don't need to go into it here. We will be doing some special inversions later on though, so keep in mind that an inversion un-does a matrix multiplication. Transformations -- more than meets the eye! --------------- Now we have an _extremely_ powerful tool at our disposal. What happens when you multiply a matrix times a vector? You get a new vector, of the same dimension as the old one. That is, it takes the old vector and _transforms_ it to a new one. Take the two-dimensional case: [a b] [x] = [a*x + b*y] [c d] [y] [c*x + d*y] Look familiar? Well if a=cos(s), b=-sin(s), c=cos(s), and d=sin(s) we get the earlier rotation equations, which we can now rewrite as P' = RP where R is the rotation matrix R = [cos(s) -sin(s)] [sin(s) cos(s)]. The way to think about this is that R _operates_ on a vector P. When we apply R to P, it rotates P to a new vector P'. So far we haven't gained much. But in three dimensions, the rotation matrices look like [cos(s) -sin(s) 0] [cos(s) 0 sin(s)] Rz = [sin(s) cos(s) 0] Ry = [ 0 1 0 ] etc. [ 0 0 1] [-sin(s) 0 cos(s)] Try multiplying Rz times a vector (x,y,z) to see that it rotates x and y while leaving z unchanged -- it rotates about the z-axis. Now let's say that we're navigating through some 3D world and have turned, and looked up, and turned a few more times, etc. That is, we apply a bunch of rotations, all out of order: Rx Ry Ry Rz Rx Rz Ry Ry Rx P = P' All of the rotation matrices on the left hand side can be multiplied together into a _single_ matrix R R = Rx Ry Ry Rz Rx Rz Ry Ry Rx which is a _new_ transformation, which is the transformation you would get by applying all the little rotations in that specific order. This new matrix can now be applied to any number of vectors. And this is extremely useful and important. Another incredibly useful thing to realize is that the inverse of a rotation matrix is just its transpose (reflect through the diagonal, i.e. element i,j swaps with element j,i). It's very easy to see for the individual rotation matrices -- the inverse of rotating by an amount s is to rotate by an amount -s, which flips the minus sign on the sin(s) terms above. And if you take the transpose of the accumulated matrix R above, remembering that (AB)^T = B^T A^T, you'll see that R^T just applies all of the inverse rotations in the opposite order -- it undoes each small rotation one at a time (multiply R^T times R to see that you end up with the identity matrix). The important point, though, is that to invert any series of rotations, no matter how complicated, all we have to do is take a transpose. Hidden Faces (orientation) ------------ Finally there is the issue of hidden faces, and the related issue of polygon clipping. In previous articles a number of different methods have been tried. For hidden faces, the issue is to determine whether a polygon faces towards us (in which case it is visible) or away from us (in which case it isn't). One way is to compute a normal vector (for example, to rotate a normal vector along with the rest of the face). A light ray which bounces off of any point on this face will be visible -- will go through the origin -- only if the face faces towards us. The normal vector tells us which direction face is pointing in. If we draw a line from our eye (the origin) to a point on the face, the normal vector will make an angle of 90 degrees with the face when the face is edge-on. So by computing the angle between the normal vector and a vector from the origin to a point on the face we can test for visibility by checking if it is greater than or less than 90 degrees. We have a way of computing the angle between two vectors: the dot-product. Any point on the face will give a vector from the origin to the face, so choose some vertex V on the polygon, then dot it with the normal vector N: = Vx*Nx + Vy*Ny + Vz*Nz = |V| |N| cos(theta) Since cos(theta) is positive for theta<90 and negative for theta>90 all that needs to be done is to compute Vx*Nx + ... and check whether it is positive or negative. If you know additional information about either V or N (as earlier articles did) then this calculation can be simplified by quite a lot (as earlier articles did!). And if you want to be really cheap, you can just use the z-coordinate of the normal vector and skip the dot-product altogether (this only works for objects which are reasonably far away, though). Another method involves the cross-product -- take the cross-product of two vectors in the _projected_ polygon and see whether it points into or out of the monitor. Again, only the direction is of interest, so that usually means that only the z-component of the vector needs to be computed. On the downside, I seem to recall that in practice this method was cumbersome and tended to fail for certain polygons, making them never visible (because of doing integer calculations and losing remainders). The final method is a simple ordering argument: list the points of the polygon in a particular order, say clockwise. If, after rotating, that same point list goes around the polygon in a counter-clockwise order then the polygon is turned around the other way. This is the method that the 3d library uses. It is more or less a freebie -- it falls out automatically from setting up the polygon draw, so it takes no extra computation time for visible polygons. It is best-suited to solid polygon routines, though. Polygon clipping refers to determining when one polygon overlaps another. For convex objects (all internal angles are less than 180 degrees) this isn't an issue, but for concave objects it's a big deal. There are two convex objects in Cool World: the pointy stars and the Cobra Mk III. The pointy stars are clipped correctly, so that tines on the stars are drawn behind each other properly. The Cobra doesn't have any clipping, so you can see glitches when it draws one polyon on top of another when it should be behind it. A general clipping algorithm is pretty tough and time-consuming. It is almost always best to split a concave object up into a group of smaller convex objects -- a little work on your part can save huge amounts of time on the computer's part. And THAT, I think, covers the fundamentals of 3d graphics. Now it's on to constructing a 3D world, and implementing all that we've deduced and computed as an actual computer program. --------- Section 2: Constructing a 3D world --------- Now that we have the tools for making 3D objects, we need to put them all together to make a 3D world. This world might have many different objects in it, all independent and movable. They might see each other, run into each other, and so on. And they of course will have to be displayed on the computer. As we shall see, we can do all this in a very elegant and simple manner. Representing objects -------------------- The object problem boils down to a few object attributes: each object has a _position_ in the world, and each object has an _orientation_. Each object might also have a _velocity_, but velocity is very easy to understand and deal with once the position and orientation problem has been solved. The position tells where an object is -- at least, where the center of the object is. The orientation vector tells in what direction the object is pointing. Velocity tells what direction the object is moving. Different programs will handle velocity in different ways. Although we are supposed to be tolerant of different positions and orientations, in these programs they are all handled the same way and are what will be focused on. If you can't visualize this, just think of some kind of spaceship or fighter plane. It is located somewhere, and it points in a certain direction. The orientation vector is a little line with an arrow at the end -- it points in a certain direction and is anchored at some position. As the object turns, so does the orientation vector. And as it moves, so does the position. Once positions and orientations are known we can calculate where everything is relative to everything else. "Relative" is an important word here. If we want to know how far we are from some object, our actual locations don't matter; just the relative locations. And if we are walking around and suddenly turn, then everything better turn around us and not some other point. Rotations are always about the origin, which means we are the origin -- the center of the universe. Recall also that the way projections work is by assuming we are looking straight down the z-axis, so our orientation better be straight. So to find out what the world looks like from some object we need to do two things. First, all other objects need to be translated to put the specific object at the origin -- shift the coordinate system to put the object at (0,0,0). Second, the orientation vector of the object needs to be on the z-axis for projections to work right -- rotate the coordinate system and all of the objects around us to make the orientation vector be in the right direction. Every time an object moves, its position changes. And every time it turns or tilts it changes its orientation. Let's say that after a while we are located at position P and have an orientation vector V, and want to look at an object located at position Q. Translating to to the origin is easy enough: just subtract P from all coordinates. So the original object will be located at P-P = 0, and the other object will be located at Q-P. What about rotating? The orientation vector comes about by a series of rotations applied to the initial orientation. As was explained earlier, all of those rotations can be summed up as a single rotation matrix R, so if the intial vector was, say, z=(0,0,1) then V = Rz Given a position vector, what we need to do is un-rotate that position vector back onto the z-axis. Which means we just multiply by the _inverse_ of R, R'. For example, if we turn to the left, then the world turns to the right. If we turn left and then look up, the way to un-do that is to look back down and turn right. That's an inverse rotation, and we know from the earlier sections that rotation matrices are very easy to invert. So, after translating and rotating, we are located at the origin and looking straight down the z-axis, whereas the other object Q is located at the rotated translated point Q2 = R' (Q-P) i.e. Q-P translates the object, and R' rotates it relative to us. Readers who are on the ball may have noticed that so far we have only deduced what happens to the _center_ of the object. Quite right. We need to figure out what happens to the points of an object. First it should be clear that we want to define the points of an object relative to the center of the object. It is first necessary so that the object can rotate on its own. And it has all kinds of computational advantages, as we shall see in a later section; among them are that the numbers stay small (and the rotations fast), they are always rotated as a whole (so they don't lose accuracy or get out of proportion), and the points of objects which aren't visible don't have to be rotated at all. So we need to amend the previous statement: we need to figure out what happens to the points of an object _only when that object is visible_. Visibility ---------- When is an object visible? When it is within your field of vision of course. It has to be in front of you, and not too far out to the sides. So, after translating and rotating an object center, Q2 = R' (Q-P), we need to check if Q2 is in front of us (if the z-coordinate is positive, and that it isn't too far away), and that it isn't too far out to either side. The field of vision might be a cone; the easiest one is a little pyramid made up of planes at 45 degrees to one another. That is, that you can see 45 degrees to either side or up and down. This is the easiest because the equation of a line (a plane actually) at 45 degrees is either x=z or x=-z, y=z or y=-z So it is very easy to check the x- and y-coordinates of the new center to see if -z < x < z and -z < y < z. If the object is visible, then the rest of the object needs to be computed and displayed. Computing displayed objects --------------------------- Now let's say this object, which was located at Q, is visible. It has a bunch of points that define the object, relative to the center -- call those points X1 X2 X3 etc. where X1=(x1,y1,z1) etc. -- and it has an orientation W. Again, the orientation vector is computed by performing some series of rotations M on a vector which lies along the z-axis like (0,0,1). First the points need to be rotated along with the orientation vector. This isn't an inverse rotation like before -- the points rotate in the same way as the orientation vector. So apply M to all the points; consider a single point X1: rotated point = M X1 Once the points have been rotated we have to find their actual location. Since they are defined relative to the center of the object, this means just adding them to the center of the object: rotated point + Q = M X1 + Q This is the _actual_ location of the points in the world. Now as before we need to translate and rotate them to get their relative location: X1' = R' (M X1 + Q - P) As before, subtract P and apply the inverse rotation R'. The above equation is the _entire_ equation of the 3D world! We can rewrite this equation as X1' = R' M X1 + R'(Q-P) and recognize that R'(Q-P) was calculated earlier, to see if the object was visible. The above equation can be read as "Rotate the rotated object points backwards to the way we are facing, and add to the rotated and translated center." That is, if we turn one way, the center rotates in the opposite direction, and the entire object rotates in the opposite direction. Physically, if you turn your head sideways you still see the monitor facing you. If instead of turning your head you were to move the monitor, you would also have to rotate the monitor to keep it facing you (if you didn't rotate the monitor, and only changed its position, you would be able to see the sides, etc.). That rotation is in the opposite direction that your head would rotate (head turns to the right, monitor turns to the left). Displaying objects ---------------