Voronoi Experiment

Voronoi Experiment

I first encountered the Voronoi back in my honours thesis when we were redistributing points on a plane to assist in up- and down-sampling point based 3D models. At the time I was using a library that did not use the plane sweep algorithm by Steve Fortune. This made the overall algorithm inefficient on the scale we were working. Since then I have always had an interest with the Voronoi. I noticed the plane sweep algorithm during my thesis, yet did not have the time to implement it.

I came across this blog post which is an actionscript port of Steve Fortune’s algorithm, which was used by Amit Patel in his world generation experiments. I had seen Amit’s article before and between the two my interest was sparked to fiddle with the Voronoi again. That is what this demo is about, fiddling with the Voronoi and trying the library out.

Interestingly I now realise that we should have made use of Lloyd’s relaxation during the upsampling process. What we were doing was trying to find the best spot to place a new point. What we should have have been doing was putting the point in anywhere (except over another point) and just relax the Voronoi.

Features

  • Fortune’s algorithm, fast enough for animation.
  • Lloyd’s relaxation, great for spacing points.
  • Region filling, great for generating a proximity map.
  • Kruskal’s minimum spanning tree.

Applications

  1. Distributing points on a surface
  2. Determining the closest city, point, site, etc given a reference point
  3. Procedurally generating terrain (see Amit’s post)
  4. Nearest neighbour searches
  5. Largest empty circle in a set of points
  6. Artificial intelligence collision avoidance, e.g. if sites are potential collisions then the edges are safe traversals to avoid collisions
  7. and many more…

Issues

Below are two problems that I ran into and possible solutions that I was too lazy to implement. I will be implementing them if I intend to make use of this library given the same context as when the issue arises.

Overlapping points

The as3-delaunay library does not like it when points (sites) overlap. Thus when adding points I do a check to make sure that I am not adding any sites over existing ones. When animating the sites, it is important to make sure that they avoid each other to prevent this from happening as well. This is currently not done and leads to a bug, which can be fixed by removing points.

Proximity map

There are currently two version of the proximity map generation in this demo. The first one was using Graphics.beginFill to draw the regions and then draw the graphic onto a BitmapData object for the as3-delaunay library. However, I learnt that Graphics.lineTo makes use of anti-aliasing techniques when drawing, which cannot be easily disabled. Thus, on the borders of a region the index in the proximity map is aliased into another index. Sadly, this ends up being the fastest of the two methods.

The second version draws the graphic into a temp object and then the BitmapData.threshold is used to make sure that all values are actually the index value. Afterwhich the temp object is drawn to the proximity map. There are no bounds checking for the affected pixels in either the thresholding or drawing, which makes it even more inefficient as unaffected pixels are drawn over and over.

The first version is used when animating the Voronoi sites. The reason for this is because it is far faster and this keeps the animation fluid. Additionally the bug is less visible when in motion. The second version is used once when the sites are static and thus can take its sweet time. The proximity map is only used for determining which Voronoi cell the mouse pointer is over.

What I am going to look into next is the Bresenham’s line algorithm or the Extremely Fast Line Algorithm suggested at simppa.fi for drawing the region borders and making use of the BitmapData.floodFill method to fill out the region without aliasing. My assumption is that the line algorithm used by the Graphics.lineTo method is Xiaolin Wu’s line algorithm, but that makes little difference as it is an anti-aliased way of drawing lines.

 

  • http://www.redblobgames.com/ amitp

    Looks cool! I disabled antialiasing as much as possible by using stage.quality = ‘low’ . I think this works fine on polygon fills and I think it also works on lines.

    • http://www.avanderw.co.za/ Andrew van der Westhuizen

      Great way of doing it… I could not find anywhere on the net on how to disable the anti-aliasing drawing. Nice solution!