# 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*^{2}+*y*^{2}), 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*^{2}+*y*^{2})

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

All images are copyright 2005 by Craig S. Kaplan. You are
free to use them for **personal** and **non-commercial** purposes.
Please check with me about any other uses.