Plaidophile

Recently I'd been messing around with my research 3D engine for various reasons (mostly of nostalgia), and I came to realize that even now there are several things I had been doing with geometry images that still don't appear to be well-known for them. So, I'd might as well write some of it up.

At its most basic, a geometry image is an "image" where each "pixel" is a point on a surface. At the very least, this point is a position in space (x,y,z); in my implementation I also stored a texture coordinate and a surface normal. All mesh interconnectivity is based on its position on the grid; essentially, each two adjacent rows of points form a triangle strip.

As it turns out, any continuous surface can be stored in this form (a simple method for converting arbitrary triangle meshes to a geometry image was the primary subject of Gu's research, and alternate methods were the primary thrust to the other geometry image research I've seen). However, my interest in it was more to what you could implicitly do easily with this representation.

The first, most obvious thing is that any operation which you can perform on pixel images you can perform on a geometry image. Resizing an image provides a simple way to resize the geometry — providing easy level-of-detail and even upsampling. There are a few fiddly details with how the resize has to take place to avoid introducing visible seams, however. In any case, this also led to continuous level-of-detail and the ability to dynamically change a scene's polygon count (based on various priority heuristics) in order to maintain a consistent framerate.

The next thing is that it is easy to do arbitrary morphing between meshes — at the most basic, you can simply crossfade two images. Of course, it helps if the meshes are fairly well-aligned in the parameter space, but there are many techniques that can help with that, and you can also do feature-based image-warp morphing (like traditional 2D image morphing).

Another thing — and this is what has helped me many times on other completely unrelated projects — is that image compression techniques lead to very simple mesh compression techniques as well. My primary compression mechanism was to use a Haar wavelet transform, and then to store each channel separately. By interleaving the channels on a detail-level basis, it became simple to do progressive compression, such that the mesh would improve in fidelity as more of the data loaded in. (The higher-level concept of "try to organize things as a continuous stream of correlated data and then apply non-destructive filters to improve the compression" became the basis of Kindle/Topaz's compression algorithms.)

Finally, the really neat thing (at least from a visible end-results standpoint) is that it made it very trivial to produce perfectly-optimal shadow volumes. Constructing a shadow volume (used for hard-edged shadows) requires determining which triangles are backfacing from the light source (to generate the end-cap), and then finding the edges of that end-cap to produce the edges of the shadow volume. In the case of a geometry image, this becomes extremely trivial — you simply generate the contour along the transition between front- and back-facing triangles, and with this you generate the shadow volume. (To be fair, there are similar things you can do using half-edge structures in traditional polygonal meshes; I believe this is the technique the Doom 3 engine uses. But I was doing this in 1999.)

In retrospect I really should have pushed harder to write up papers on these things. I still don't see people using geometry images to their fullest, and I missed out on a few graphics job opportunities when I couldn't simply point to actual innovative work I'd done.

It's also a bit disappointing that even with the brief love affair the graphics community had with geometry images, more hasn't been done with them. As far as I know, the only commercial product which uses them is Second Life, and it only uses them in a trivial capacity (more as an easy way for them to represent non-procedural geometry than for them to gain any real algorithmic benefits).

At least the other major piece of research I did (dynamic spatial partitioning) became my master's thesis which has actually been cited by others. It's also quite impressive to see it run on modern hardware, with millions of randomly-moving and dynamically-constructed objects being culled to a simple rectangular viewport at over 200 frames per second. Maybe I should revisit that stuff too.