Aliasing Artifacts

One day, while playing with a program to render Voronoi diagrams, I accidentally requested the Voronoi diagram of a black point and a white point, both at the origin. Imagine my surprise when my program produced the image above. Eventually I realized what was happening. For every point in the plane, my program was computing the distance from that point to one of the generators at the origin. This number was computed inside the FPU as an 80-bit floating point number, and then rounded to a 64-bit double precision number in order to store it in main memory. This value was then transfered back into the FPU for comparison against the distance to the second generator, also stored as an 80-bit float. In other words, the choice of black or white in the image above is made based on the rounding behaviour of the low-order bits of the squared Euclidean magnitude of pixel centres. The result is a strange, brittle view of the internal logic of the X86 FPU.

These pictures turn out to be closely related to aliasing patterns. The image above is made up of concentric rings, each containing an approximate view of the function sin(x²+y²), sampled at different rates. That function, sometimes called the zone plate function, is a standard test function for sampling and reconstruction algorithms, and has arisen many times in graphics and vision.

I first saw this behaviour on x86 machines around 2000. It's very unpredictable, depending for example on GCC's optimization settings. There is a long-standing debate on whether this is a bug in GCC or merely an aspect of floating-point computation that programmers ought to be aware of. The controversy tends to flow back to GCC bug 323. I dimly recall filing that bug, but perhaps my memory is faulty. I'm not listed as the reporter, so either I'm wrong or someone else filed it on my behalf.

Images from the paper are presented here. They are not offered in thumbnail form, since the process of resampling them to create thumbnails would destroy all the information in the images. For more details, please read the paper.

Aliasing patters from the function sin(x²+y²)

These pictures are fairly well known in computer graphics. They arise simply by sampling the zone plate function at different rates. What's amazing is the wide variety of attractive patterns that arise in the process.

Tom Beddard has created a lovely Flash demo of this function, which allows you to zoom in and out of the zone plate function interactively. Try it out!

Hexagonal aliasing patterns using the same function

What would these patterns look like on a hexagonal pixel grid? Some information would be lost by resampling such images into a square grid, so here I offer fairly coarse PDFs, each containing many small hexagonal cells.

Aliasing patterns from floating-point roundoff

These are the images that originally inspired this exploration.

Aliasing patterns computed explicitly from floating-point roundoff, using the frexp function

In the paper, I demonstrate the correctness of my analysis of these patterns by generating them explicitly with manipulation of floating point numbers.

Papers

Aliasing Artifacts and Accidental Algorithmic Art. Bridges 2005.