Pete's GPU Notes

The basic approach is to take a set of points randomly scattered through space, and take the distance to the nearest point as the texture's value. This is the sort of pattern you end up with;

A naive implementation of this would search through all of the scattered points to find the current closest distance, which gets slow very quickly. Steve's implementation cuts down the search space by dividing space into grid cells and placing a single point randomly within each one, like this:

This allows each evaluation to only check against the point in the cell it's currently in, and its neighbours.

This works great for static images, but I really wanted the points to move to get an animated texture. One way to do this would be go back to randomly scattered points, and then sort them into a spatial sorting structure such as a quad-tree each frame to keep the number of neighbours you need to check to a minimum.

I was aiming at a hardware solution, and wanted to draw a simple 2d image of the pattern, rather than procedurally evaluating it at arbitrary points, so I decided to try an idea I first came across in Stylized Video Cubes; using a z-buffer to construct the voronoi diagram.

I draw a quad centered around each point, enable depth testing and use a small pixel shader that outputs the distance from the central point as the z depth, as well as setting the color from a palette indexed on the depth:

The actual size of the quad that's drawn for each point was chosen pretty arbitrarily, to give a nice look for a typical distribution of points.

I then animate each point by giving it a random velocity vector, and wrapping it's position when it heads off the edge of the image (you can either add a slop border the size of a single quad around the edge to wrap to, or if you want a tileable result, render each point multiple times if it's touching a border).

This works pretty nicely, the main issue was what happened if a part of the image isn't covered by any quads, which leaves a gap in the result. I worked around this by clearing the screen to the color indexed by the maximum distance in the palette.

Having a tileable image means that it's possible to do a poor man's fractal noise, by reusing the constructed image for all the sublayers of the fractal pattern. The repetition can be noticeable, especially when its animated, but it's a very low cost operation once you have the basic image.

I experimented doing multiple passes to implement deeper levels of the algorithm, such as using the distance from the second or third nearest neighbor, but this involved rendering a pass that wrote ID values for each point to compare against in the next pass to figure out if the current nearest point was acceptable, and much larger quads, and so I was unable to get decent performance for L2 and higher textures.

I think the best approach for these on hardware would involve a combination of space-sorting strategies to break areas down into a small enough set of possible neighbor points, and then doing the fine-level sorting within a pixel shader. Space sorting would also be a good way to handle the moving points problem with a software implementation, since you don't have the performance advantage you get from an optimized z-buffer in hardware.