Something Old, Something New...

In which I explain how this project came about in a roundabout way.

Something Old

So you want to make an image out of a virtual scene. Say you have a 3D model of a potential apartment and you want to check just how much of your room will be visible from the kitchen. How do you do it? Well, you could try path/ray tracing. Take your 3D virtual apartment, specify that the virtual "camera" is floating next to the stove, and figure out which photons coming from the light source will hit your eye. This comes down to tons, and I mean a metric ton of computations, and your processor will probably give you hurt looks after trying this.

Another way to make a pretty picture is rasterization. Instead of playing with light, we just take each 3D object in the scene, and draw it like a painting. Is the mouse close to our eye? Draw it really big. Does the road head off into the distance? Make the lines converge as they reach the horizon. We don't know what's going on with the lighting at first so it's going to take us a little effort to figure out where the shadows go. This is okay though because there are numerous ways of just estimating where light will go. A little fudging can go a long way.

This method might seem like cheating compared to ray tracing, but this saves us a LOT of time. Ray tracing a scene can take days and your processor will be sweating like a teen on their first date (your GPU can help but there's still a lot of pain to share). Ray tracing can do some things that rasterizing can only guess at (such as realistic glass reflections). However, rasterizing can take just milliseconds and with proper tricks, you can still make some very impressive images.

Something New

About a week ago I came across an article that described a fantastic little project by Matt Zucker. He was trying to improve a ray tracer by Andrew Kensler that, in turn, was an homage to Paul Heckbert’s business-card-sized ray tracer (the final code actually fit on a business card!).

The techniques of ray tracing have been well-known for a long time but Zucker, Kensler, and Heckbert wanted the smallest program that could achieve an acceptable result.

Something Borrowed

I want to see if I can apply the same miniaturization treatment to rasterization as was done to ray tracing. The issue here (besides my massive lack of experience) is that rasterization doesn’t make pictures with quite the level of detail as ray tracing. It's not much of a problem but I want to make something that looks and feels impressive. So how can we make a really cool looking picture? Let's try a moving picture! I probably won't get the same level of detail, or as small a code base as the ray tracing projects, but I'll do my best and maybe someone else can write the impressive version. If we can make a beautiful image along the way, that’s just a bonus.

But how can we make a moving image while keeping the size of the code down? The ray tracing guys used the portable pixmap format (PPM) file format that is very easy for a programmer to use. The file just contains a little starting info and then the red-green-blue values for every pixel. That’s a lot of data (next week we'll examine how some files compress this data) which is why modern systems don’t typically use this format, but we don’t really care about size of the output. For my purpose, I only want something that's easy to use and can display moving pictures which PPM files cannot.

Popular image formats like PNG and JPEG don’t have the capability to display anything a still image so those are out. Games typically use OpenGL or DirectX to display the images they make, but these both require special libraries and lots of code that isn’t even guaranteed to work on every system. So much for that.

If I want this to be on a business card and allow anyone to use it, I need to use something like PPM that lets me output the RGB colors for every pixel without worrying about compression or output method (Technical note: the tiny ray tracers mentioned above kind of cheat by not handling the file output themselves. Instead, they just spew the picture’s values to their output and rely on the user to direct that into a file that can then be read).

Many of you have probably guessed where I’m headed at this point: GIFs. You’ve seen them everywhere. Nice looping video-like pictures of cats falling off of things. So, I guess it’s time to find out what GIFs are made of and how we can make them dance.

Something with a Red Gradient

Okay, turns out GIFs are not super easy. They're not as simple as just writing out each pixel and I’m worried about the amount of code I’m going to have to write just to comply with the format. But right now, that’s too much to worry about. I just need to produce a very simple GIF that anyone can view. The GIF used to be, and still is, highly contested but it's pretty much my only hope for making this work so I will follow the immortal advice of Tim Gunn: make it work.

Wikipedia is my savior. People have been making GIFs for years but they rarely see the underlying structure of the file. I need to write this from scratch so I need the basics. There’s a header to start every file. Cool. There’s a description of how big the image is. That’s useful. Then there’s a “global color table?” Okay... A header for the beginning of an image and then, oh no, a bunch of compressed data that’s supposed to be the pixel data. Crap. I was hoping that I could avoid all compression because it just makes things more complicated. But wait! What’s that little section in Wikipedia about uncompressed GIFs? That makes me excited. Except it’s just using the compression and tricking it into not compressing it. Darn. So I still need to learn how this compression thing works and how we’re going to need to format our data. But that’s a Cthulhu-sized problem so we’ll save that for next week. For now, I'll just show you a pretty picture:

Next week might be a little more technical as we get up close and personal with compression but more pretty pictures are sure to follow.