Advanced Voronoi Noise Generation

The method for generating Voronoi noise in Simple Voronoi Noise Generation can only be used for groups of points. But Voronoi noise works with so much more than just points. In fact, Voronoi noise generated from other shapes can lead to some really cool effects, like these ghostly rings:

If you have not already, the prerequisite to this post is Simple Voronoi Noise Generation. Go read that before you continue here.

Advanced Voronoi noise generation is simply generating voronoi noise with other shapes. Circles, rectangles, lines, points, even shapes defined on the fly are all free game. Unfortunatly, the freedom that comes with these extra options also adds some complexity to the code. The naive solution is the same as with Simple Voronoi noise: for each point, compare to all objects and find closest, second, third, etc. However, other objects prevents us from using the cell checking, because objects could span multiple cells and some cells might be empty. So instead we use recursion. The basic idea is this:

for every object, pick a "central" point, starting with that point recursively:
see if distance is less than the current stored value for this pixel
if it is, set it to value and tell neighbors to do the same for the current object

However, this leads to lots of overcalculation and overdraw. The following diagram shows the calculated values for two points at opposite corners. Ultimately, half of the calculations from each of the points is discarded.

So how could we change this algorithm so we minimize the number of values that are overcalculated? Simple, we introduce the concept of generations. Essentially, we start with a list of all the centers, Generation 0. Then each generation flags all of it's neighbors if they haven't already been calculated and the flagged points are calculated and become the next generation. Here's what it would look like.

In this way we can only calculate the values we need. Notice that using generations makes it not technically recusion anymore, but it is still very similar to recursion. I will not explain in this tutorial how it works with combine functions that use multiple distances, because the code gets a bit more opaque. The general idea however is to store the distances with the object that caused that distance value.

In pseudo-code it looks at bit like this:

for(VoronoiObject obj : objects)
{
    obj.addAllCenters(flagged);
}
while(!flagged.isEmpty())
{
    current = flagged;
    past.addAll(current);
    flagged = new HashSet();
    for(Location point : current)
    {
        calculatePoint(point);
        flagNeighbors(point);
    }
}

Location is just a subclass that stores a 2D point and a source VoronoiObject.
VoronoiObject is just an interface that provides a method to get the distance to a point given a distance function.

And that's it. See the sources for the subtleties and specific details.

Like always, an applet. I would recommend viewing the noise in black and white, because it looks the best that way.
Controls:
Space = next distance function
X = next combine function
S = new random seed
Shift = toggle color mode
Enter (downloadable version only) = save screenshot


If the applet doesn't load, trying refreshing the webpage. May not work on mobiles.

Demos: https://drive.google.com/folderview?id=0B_jXYEquMamINGVGQTM0cTJzdmM&usp=sharing
Source Code: https://github.com/f4113nb34st/Println/