Li : Dev Actionscript Development Blog

Voronoi Noise

Click on the image to see the demo, right click view source enabled.

'Morley noise' or 'cell noise' can be produced by laying out a random set of points and then coloring each pixel according to the distance to the CLOSEST of the layed out points. This can involve a pretty serious amount of calculation since for each pixel, distances have to be calculated to all the points in order to use the smallest distance to obtain the color value. To speed things up, the points are usually layed out in cells so that a pixel only needs to be checked against the point in the cell and neighboring cells. This reduces calculations. There's a good explanation of this HERE.

What I've done is an attempt to be even quicker. I'm using Hrito's amazingly fast implemantation of a fortune's algorithm ported from c, that finds the Voronoi edges of a random distribution of points. I altered his code a bit so that it can output triangles also. I defined these triangles as a vorono edge joined to the focus points of its neighboring cells. With this, the experiment sweeps the triangles and fills 'em up. Each pixel already knows what point to calculate its distance to, hence reducing the calculations even further. The code has some graphical glitches and is only for demonstration purposes so I can assure that it can be made way faster and better.

Uses of this? I think a LOT. Besides what has been discussed above, this sort of algorithms could be used to obtain very fast Delaunay Triangulations, which can be used for a milliard of things in 3D; they provide an optimal triangulation method for a given set of points. I'm, eager to experiment in these.