Offsite links
Reyes: It's not another damn raytracer.January 12th, 2007
Everybody and their mother has written a raytracer but you hardly ever see any Reyes renderers. It seems so mysterious, as though it were the exclusive domain of big special effects companies. I started writing a simple Reyes renderer in my spare time a few weeks ago to get a feel for it.
The algorithm itself isn't really all that complicated. Getting a simple Reyes renderer off the ground takes more work than a raytracer for sure, but it's nothing that couldn't be done in a day or so. The hard part is getting the splitting and dicing bits working properly.
The basic idea in Reyes is to divide your scene into such tiny pieces that most of problems facing other rendering algorithms go away. For each primitive, you get its screen space bounding box and either choose to split it into more primitives, or dice it into a grid of little tiny, sub-pixel sized quadrilaterals.
Splitting in action. A sphere is recursively split into smaller objects until the screen space bounding box of each object is below some preset size.
After an object has been split into small enough pieces, it is "diced" into a grid of quadrilaterals. The density of the grid is chosen such that no quad is more than about half a pixel in size. Each quad in shaded as normal and then projected onto the screen. Because the quads are so tiny, it's not necessary to interpolate things like the Z value and texture coordinates over them. Determining which pixels, assuming you're rendering into a super-sampled image buffer, a micro polygon contributes to involves looping over the micro polygon's screen space bounding box (there's that phrase again) and doing a simple inside/outide test on each pixel. After the grid has been rasterized, it can safely be thrown away.
It may seem like an awful lot of work for a renderer to do, but it's surprisingly fast. Even with crazy displacement mapping, hundreds of objects, and 16x antialiasing, it's orders of magnitude faster than a raytracer.
The renderer I am writing is more complicated than that of course. A super-sampled "deep" frame buffer that the Reyes algorithm requires will get pretty huge as your render resolution increases. Instead of rendering the whole image at once, it's a good idea to break everything into smaller 16 by 16 pixel "buckets" and handle each one independently. After all the geometry has been split, it is sorted into the buckets. The geometry in each bucket is also sorted front to back.
In addition to the basic algorithm, I've implemented a number of other fun things. I've implemented a multi-resolution geometry cache. This is used not only to allow for raytracing, but also to avoid re-dicing and re-shading geometry that spans multiple buckets. There's also a hierarchical z-buffer which, along with the aforementioned sorting, allows occluded geometry to be identified and skipped. I've also implemented an irradiance cache along with irradiance gradients and neighbor clamping, although it's only used for ambient occlusion at the moment. There are also several different cameras available, including a fisheye lens, which I until now had thought only a raytracer could handle.
Anyway, Reyes is a neat diversion and really not as tough as I thought it would be. There are still some things I'm a little fuzzy on though. Motion blur and depth of field in particular. I know these things are possible in the context of a Reyes renderer, I'm just not sure how exactly.
Obligatory Holiday entryDecember 25th, 2006
Yep, it's Christmas. I'm no Christian but I'm not about to turn down a long weekend and a Christmas bonus because I don't subscribe to a particular creation myth.
Anyway, I'm sorry I haven't paid more attention to the site for the past few months. Work and all this "responsibility" crap have a funny way taking away time from more interesting (or web-worthy) pursuits. I'm not about to waste people's time by posting boring details from my personal life either, so you'll just have to wait until I've got more spare time.
Until then, enjoy this slightly disturbing Christmas image I drew.
Fun with fractals.September 17th, 2006
I recently developed a method of rendering images of the Buddhabrot orders of magnitude more quickly than was possible before by applying the Metropolis-Hastings algorithm to the problem. I've written up a short article about it.
The importance of tools.August 14th, 2006
Starfish Prime is coming along nicely. The soundtrack is great and getting bigger all the time. The graphics are pretty good, although I plan on redoing a number of the character files. If there's one mistake that's setting me back. It's the lack of tools.
The Starfish Prime "engine" has a tonne of functionality. There's a simple but surprisingly versatile keyframe animation system, a complex dialog system, a fairly complete sound system, and a script system to tie everything together. The possibilities for level design seem almost endless. I didn't originally plan for the non-game elements to become so complicated, but there is a degree of polish that I would like to achieve on Starfish Prime. Your average one-man-in-the-basement game is distinctly lacking in the attention to detail department, and that is something I would like to avoid.
My big mistake was not writing the tools needed to actually use all of functionality present. Everything needed to be typed in by hand, so it's a lot of work to make new levels. If I had more foresight, I would have developed WYSIWYG tools in parallel with the underlying systems. Instead, I've got to go back and make them all now. The tool set as it exists now is primitive, but it's already a huge plus. Being able to edit almost every aspect of the game in real-time has saved me countless hours already.
An update of some kind.July 3nd, 2006
I've added a couple of new bits of art to the art page. Speed painting is a good way to stay sharp, but I really ought to be doing more "complete" pieces.
Back from Hong KongMay 26th, 2006
Well, I'm back from Hong Kong. Actually, I got back over a week ago, but I've been so damn busy with work that I just haven't had the time to sit down and think of something to write. May and June are the busiest time of year in my line of work, so it's not a shock that it should be so hectic right now, but the shift from bumming around Hong Kong to working 12 hour days is not a nice one.
I'm happy to report that all of my original fears were unfounded. I didn't freak out. If anything, I think I handled myself rather well what with being on the other side of the planet all alone and all. As with any travel though, there were some unpleasant surprises. My cousin, who was living in Macau at the time, came down with a mysterious brain condition shortly before I arrived that was initially identified as Japanese Encephalitis, but may in fact be something completely different.
Naturally, I visited her in the hospital, but much of my original itinerary was dependent on her not being hospitalized. I did get to see much more of Hong Kong than I originally intended to though, so it's not a complete loss.
I kept a diary of sorts while I was there, but my handwriting is so terrible that I'm having trouble deciphering it. I plan on transcribing it and putting it up, although I don't think there are any great revelations or deep insights into Hong Kong life, but my assorted relatives will probably want to read it anyway.
Hong Kong is the land of cheap tailors, so it's not surprising that I got a suit tailored whilst there. The final cost was a little under $320 Canadian, which is a hell of a lot less than you'd pay for a made-to-measure suit here in Vancouver. The fit is incredible and I can't wait until I can think of a reason to wear it.
Hong Kong is, of course, also the land of shopping. I didn't want to go too far over my $750 personal exemption on duty though, so I couldn't go overboard. Aside from several pairs of shoes and the already mentioned suit, my only major purchase was something I've been lusting after for ages: A brand spanking new pair of AKG k701 headphones.
Mounting terror and Starfish Prime updateApril 24th, 2006
I have to confess, I'm getting really freaked out.
Maybe some back story would help you to understand exactly why I'm freaked. You see, in a mere week, I'm leaving for Hong Kong. I'm leaving alone. I'm going to be on the opposite side of the world and I'm going to be completely on my own. Honestly, the concept is both exciting and terrifying. I've been away from home for several weeks at a time before, but I've always been with people who I knew and there was always someone else running the show. Not this time. I have a cousin teaching grade school in Macau, who I'll visit, but that won't be for a solid week after I've landed. Up until then, I'll need to fend for myself, and I have my doubts about whether or not I will be able to cope. While I have a very good idea of what I'll need to do mechanically once I get there, I really don't know what my psychological reaction will be.
Will I freak out and cower in my hotel room until my cousin comes to save me? Will I step off the plane and start crying? Will I even get on the airplane to begin with. I honestly don't know. More than any technical problem I may encounter, I'm more worried about my own reaction to the entire experience. That is, in itself, worrying.
Anyway, enough blathering.
On the subject of Starfish Prime, I've managed to finish all of the internals. The graphics "engine" is basically done. The SVG parser has a single strange bug, but it can be worked around with a little manual hacking of any afflicted files. There aren't really any "show stopper" bugs any more, although I'm concerned about how it will degrade when run on slower computers. I tried it out on a 1.3ghz P4, which is about the lowest end computer that I'd like to support, and the results weren't pretty. It didn't outright crash, it simply consumed the CPU and caused tremendous mouse lag. I have some idea of why, but I don't actually own a system that slow, so debugging it will be painful.
Vertex shaders have turned out the be rather useful for doing some of the animation. For speed, all SVG input is converted into display lists. While this does result in a tangible increase in frame rate, the opportunities for animation are limited. From the point of view of OpenGL, display lists are essentially atomic. There's no direct access to the vertex information any more. Vertex shaders, being at a lower level in the graphic pipeline are still able to see the vertices and manipulate them. Although they're no good for complicated animation, vertex shaders are great for adding little things, like the leaves of a tree blowing in the wind, or wavy flags.
Raytracers are faster than XApril 7th, 2006
I'm not sure what the point of this entry is, it's just something that bugs me.
This is something I've heard a million times. With a well implemented KD-Tree, raytracers can achieve close to O(Log N) scaling as the scene size increases. A naive Z-Buffer algorithm has O(N) scaling. Therefore, once the scene size grows very large, raytracers are faster than Z-Buffer renderers.
What people seem to forget is that there are spatial sub-division structures that work for non-raytracing methods. If you're careful to sort your primitives front to back, bucket them, and use a hierarchical Z-buffer, such methods can achieve close to O(Log N) scaling as well. Scanline and micropolygon methods are also able to exploit spatial and memory coherence far more effectively than raytracers can.
Most comparisons are only done using triangles anyway. Micropolygon methods like Reyes are able to draw primitives such as Nurbs and Sub-division surfaces very cheaply, raytracers on the other hand can't. Displacement mapping almost comes for free in Reyes, yet it's an area in which raytracers continue to struggle. When using triangles or other mathematically simple primitives, raytracers may perform similarly to Z-Buffer renderers, but once you stray into the realm of parametric surfaces or procedurally generated content, Z-Buffer algorithms take the decisive lead.
That's not to say I don't like raytracing. It's still one of the most flexible rendering methods around. Features like shadows, reflection, refraction, and global illumination are almost trivial to implement in a raytracer but are basically impossible in other methods. For simulation of reality, I wouldn't want to use any other algorithm, if I were doing to special effects for a movie though, the speed and artistic flexibility that comes with Reyes would make it the natural choice.
SVG UpdateApril 3rd, 2006
I've actually gone and implemented a semi-complete SVG Tiny interpreter, although I decided to forgo gradient support in the name of simplicity. I have to admit, the SVG specification is a horrible, horrible thing, but the format itself isn't all that bad.
If you ignore scripting, CSS, and filters, it's really pretty simple. Navigating SVG files is simple enough with an XML library (Expat in this case), and parsing all the object data is straightforward. I am doubtful about the usefulness of the human readability of the format, but it certainly comes in handy when debugging.
StarFish Prime, the game I am working on, makes heavy use of SVG. The conversion from bitmap art assets to vector art assets required some large changes to the program. For one, it was necessary to switch from software blitting to OpenGL. Current computers are simply too slow to redraw more than a few dozen shapes at a reasonable frame rate with anti-aliasing. On the other hand, current video cards are essentially unlimited in this regard. Using OpenGL, Starfish Prime runs at a solid 60hz with 6x multisampling regardless of resolution, all while drawing hundreds of display lists containing thousands of triangles.
I'm really starting to wonder why Adobe doesn't add hardware acceleration to the Flash player.
What happend to Baby SVG?March 14th, 2006
I'm slowly working on a dumb little game called StarFish Prime in my spare time. It's nothing special, basically just a remake of the Greatest Game Ever: Puyo Puyo. Early on during its development, I decided to forgo the use of bitmapped graphics and do everything with vectors.
Why use vectors? Well, for starters I want the game to look good no matter what resolution it's being played at. Using bitmaps would constrain the game to a single resolution, which would either be too big or too small depending on the resolution of the end-user's screen. Vectors, being entirely mathematical in their description, will scale to any resolution. They're also cheap to draw. Modern graphics cards, even low-end ones, can draw tens of millions of triangles per second. OpenGL even includes a tesselator that will convert all of your complicated polygons into triangles for you.
All I needed to find was a good format to store my vector graphics in. SVG seemed like a reasonable choice, being simple to read and write and widely supported amongst vector graphics programs. "Seemed" is the operative word here. It seemed reasonable until I downloaded the format's specification.
SVG has, without a doubt, the longest, most complicated specification of any format ever. The SVG specification is three times longer than the Renderman specification. Renderman is a standard format for representing 3d objects and surface properties that is used heavily in motion pictures. It can pretty much define reality as we visually perceive it, yet Renderman's complete description is a third the size of SVG's description. There's something very wrong with that.
So, what the hell do they need 800 billion pages of specification for anyway? All kinds of pointless stuff. Somewhere along the line, the SVG Working Group forgot with the 'G' in SVG stands for. It used to stand for "Graphics", now it apparently stands for "Gluttonous Mess". Now, one would not normally expect a graphics format to have built in filters, scripting, or animation, right? Wrong.
Just parsing a simple vector image into something that a rasterizer can handle is a nightmare with SVG. To add reliable interactivity and animation, you need to implement two scripting languages. Hell, you need CSS support just to reliably determine basic object properties like colour. It's no wonder that support remains limited. Who knows what the designers were thinking, they certainly weren't planning on doing anything useful, like giving us a simple vector format.
SVG's font handling abilities are perhaps the funniest part of the whole mess. Aside from coming up with an entirely new font format, named SVG Fonts surprisingly enough, the specification also dictates that compliance will probably require you to support TrueDoc PFR, TrueType, OpenType, Type 1, Speedo, and Intellifont formats. TrueDoc and Intellifont are closed formats, TrueType (which itself is a nightmare format from hell) and OpenType have patent issues that prevent their complete implementation, and nobody has ever heard of Speedo. Only Type 1 is at all reasonable, and it's no good for double-byte character sets.
Still though, with font support of such epic scope, you'd think the SVG must have some killer page layout features, right? Wrong again. SVG appears to lack any concept of lines, pages, paragraphs, or formatting. Want your line of text to wrap if it's too long? Well, you'll just have to wait until they add that feature in version 6 of the spec. Seriously, you can make an SVG file that turns green when you roll your cursor over it, but you can't make a line of text wrap.
SVG really is the perfect example of the right format being designed by the wrong people. They should remove some of the gear heads from the SVG working group and replace them with some graphic artists or something. People who still remember that 'G' stands for "graphics". People who realize that laughable animation functionality and crappy text handling are only going to drive people away from the format. I'm still using SVG Tiny for the graphics in Starfish Prime. SVG Tiny lacks most of the bloat of the full specification, so it's not too bad, but could damn well be a whole lot better.
A Tribute to the Fisher AG7.March 7th, 2006
I have to admit, I derive way more pleasure from writing with my AG7 than I should. The solid construction, the ability to write on anything, the fact that it's only pen used by astronauts. I can't think of anything that could be better about these pens. From the smooth, satisfying motion of the clicker to the sleek design sensibilities, it simply gets everything right.
The "Space Pen" is the result of years of research performed by Paul Fisher in the 1950s. Realizing that the world lacked a proper writing insturment for use in space, he worked tirelessly to design a pen that would be up to the standards imposed by NASA. He didn't just succeed, he created some sort of minor god. A veritable Odin amongst pen kind.
Truly the king of pens, the AG7 also has the remarkable property of actually looking at home next to old computer equipment. Put one next to a Univac or something, and suddenly it wouldn't matter how slow and expensive the computer is, there's a fuckin' AG7 sitting next to it, and that's all that matters.
Announcing My ExistenceMarch 6th, 2006
Hello, and welcome to my web site, such that it is right now. There's not a whole lot (more like nothing, actually) up right now, but that will change were soon. This is mainly a place where I can stick up all the various uninteresting stuff I've done in my spare time for all to see.