Search blog posts
2009-06-04 Piling hexagons
2009-05-02 Voronoi patterns
May 2nd 2009
Another fast algorithm for Voronoi patterns
Voronoi patterns are drawn in the following way. Pick points randomly in the
plane. Then color each pixel according to its distance to the closest among the
chosen points. You get something like this :
or like this
if you use a slightly more elaborate function of the distance.
The trouble is that such an algorithm is not efficiently implemented in Ultra Fractal. The latter computes pixel by pixel : the same algorithm is repeated for each pixel, only the input consisting of the pixel coordinates change. Therefore with a naive algorithm, for each pixel, one has to compute the distances to all of the points (to find the closest one) which requires a huge amount of computations.
One possible improvement is to avoid picking points completely randomly. If
one chooses each of them randomly in a region centered on a vertex of a regular
gird, then, given a pixel, it is possible to find the closed point by computing
only a very small number of distances. This improves the speed of the algorithm
spectacularly. Moreover, by tuning the maximal distance from a point to the
corresponding vertex of the gird, one can interpolate between a completely regular
gird and something close to a true Voronoi pattern, what can be interesting
artistically. For instance the image below, while still retaining some randomness,
is much closer to a regular square tiling than the image above. The trouble with
this kind of algorithms is that the patterns they produce are necessarily too
regular, compared to a genuine Voronoi tiling.
There is a third algorithm which seems to work pretty well. Simply choose the random points as the vertice of regular girds which are randomly scaled and rotated. It is very easy to test the distance of a pixel to the vertice of a gird, so this algorithm is quite fast. If all the girds are large enough and if there are sufficiently many of them, the result is pretty close (at least to the eye) to a true Voronoi pattern, and does not suffer the lack of randomness of the previous algorithm.
Finally, here is an image made with this algorithm. The leaf shapes which are
apparently randomly distributed are actually on the vertice of square girds. The
basic pattern was summed at various scales to produce an interesting image and
give it a fractal flavour.
comments powered by Disqus