Voronoi Rocks

Posted: August 12, 2012 in Uncategorized

Finally managed to get a Voronoi map working in Clisk – along with Perlin/Simplex noise this is probably one of the most versatile image generation primitives. Pretty images to follow!

The basic Voronoi diagram is based on filling 2D space with a selection of random points and then colouring the rest of space according to the “closest” of these random points. This creates a pattern that looks like this:

(show (warp (voronoi-points) grain))


The powerful thing about Voronoi maps however is when you start to use them to generate more sophisticated patterns (note a common theme emerging – higher order pattern generation). For example, you can specify formulae that assign a value to each position based on some function of the distance to the nearest and second nearest feature point.

Here’s an example using an interesting fucntion. Note that you can use any mathematical function here – the convention I’ve adopted is that x is the distance to the nearest feature and y is the distance to the second nearest feature:

(def vblocks 
  (v* 5.0 
        `(Math/sqrt (- (* ~'y ~'y) (* ~'x ~'x))))))

(show vblocks)


And of course, once you have the basic pattern you can start composing this to make more complex textures. Here’s one I quite liked using some shading and some plasma to make a “rough rock” effect on top of the voronoi blocks:

(show (render-lit 
        (seamless vplasma) 
          (v+ (v* 0.2 (seamless 0.2 (rotate 0.1 plasma))) 
              (v* 0.6 vblocks))))


Some nice features about this Voronoi map implementation:

  • It automatically tiles seamlessly over the [0..1 , 0..1] square, so you can use it for continuous texture maps. Note that if you apply other transformations (e.g. adding the plasma to the image above) then you will need to make sure that there are also seamless in order to preserve the overall seamless property.
  • It’s pretty efficient – although it does a naive O(n) scan of all the features, the overhead is low and for 10-100 features it performs well

Opportunities / things to fix:

  • It’s only 2D at present. Probably the most useful form, but 3D and 4D would also be nice :-)
  • Syntax still needs a bit of work – in particular not yet happy with the way you pass functions to the voronoi-function operation.
  • There probably needs to be some way of storing a Voronoi map and re-using it so that you get the same features in multiple maps (currently you get different random features each time)
  • As mentioned above, the algorithm is currently O(n) in the number of features. Should be possible to make this O(log n) e.g. using BSP-trees, although this would require a fair bit of work.

Going to experiment with some more Voronoi-inspired patterns over the next few days.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s