Blog

Archive
| All posts |

  • Voronoi Diagrams

    published on 1/24/2010 1:55 PM

    [url:Voronoi diagrams|http://en.wikipedia.org/wiki/Voronoi_diagrams) can create some rather nice images and they are useful in quite a few fields. So I though it could be useful to have in Plane9. Trying to create a stable fast algorithm from scratch seemed to be too much work. But I did remember long ago that you can create a voronoi diagram using cones thanks to the z buffer. Since I now have a cone mesh node and a particles system I setup a scene and sure enough it worked. Looked quite nice too.

    But I also wanted to get a real voronoi generator in code. After much searching I settled for Fortune's algorithm and also managed to find a [url:implementation in C++|http://www.cs.hmc.edu/~mbrubeck/voronoi.html) by Matt Brubeck and tried it. Took a while to get it running but it worked. Not fast and with a very annoying bug. Sometimes the added edges would jump quite a distance and then the next frame they would return. The error rate increased as the point count went up. I tried to find the error but though it was just something wrong with the implementation. The original author of that code had also made a [url:very fast Flash 10 version|http://blog.controul.com/2009/05/speedy-voronoi-diagrams-in-as3flash/trackback/). Handling 1000 points in full frame rate in flash. So I wanted to test if that algorithm didn't have this error. So I converted the whole Actionscript code to c++ and that one was fast, very fast. But sure enough, the same error occurred in that version to. My best guess would be precision errors. Since the error seems to show it self in the circle calculation. Changing over all code to use doubles would probably help but not enough and it would then probably be a lot slower. He had also remove line clipping in the optimized version so border cells stretch a long way. For these reasons I decided to go back to square one.

    The [url:original inventor|http://ect.bell-labs.com/who/sjf/) of Fortunes algorithm had also release the code to his implementation. So I grabbed that one and went through it. It was rather messy and no comments at all. Luckily so had other people realized this and also discovered a number of serious memory allocation errors. They had fixed these and been nice enough to [url:release the code|http://www.skynet.ie/~sos/mapviewer/voronoi.php) to those implementations too. So I looked though the one that seemed the most promising and got it running quickly. It was much, much nicer. Well commented and just 2 files. The speed however wasn't as fast as the Flash 10 one so I had to put on my optimization hat and get to work.

    What most programmers seems to miss is that memory allocations are about the slowest things you can do. You should never, ever allocate memory in your main loop if you don't have too and if you think your going to need it the next frame then dont release it. So I pooled all memory allocations in the whole class since the whole point of my implementation was to call the generator every frame and let the points move around in nice ways. As excepted this made a huge impact on the performance as can be "seen" on the image below. What you see is 5000 points running in full framerate on my Core 2 Duo 2.6GHz (Only one core is used). At 10000 it started to get slow but rendering all those lines and points takes quite a lot of resources. For 5000 points it's using a bit less then 1.5Mb of memory so thats not too bad.

    ![http://www.plane9.com/forumimages/2010-01-23-voronoi.png)

    This version also had a nice extra advantage. It's very easy to get what cell each edge belongs to. Without this information all you have is a lot of lines so you can't color the insides of the cells.

    Now you might be wondering that, yes this is all nice but we are not trying to find the closest postoffice among a group of 5000 wherever you are as this algorithm will help you with. We just want pretty pictures. Actually I wondered the same myself. So I wanted a flexible Plane9 node on top of this generator. Expressions are nice so I threw the expression parser in there, some values to adjust line sizes and colors and tried it out. Lets just say I'm a bit surprise just how powerful this combination turned out to be. For an example. Using the expression

    tmp=pointnr;
r1 = rand(&tmp)*95;
pos.x=sin(tmp+time*0.2)*r1;
pos.y=cos(tmp+time*0.2)*r1;

    I got this. ![http://www.plane9.com/forumimages/2010-01-24-voronoi-exp1.png)

    Now by only changing the last "0.2" to "0.1" this is what showed up and this looks even better when animated. ![http://www.plane9.com/forumimages/2010-01-24-voronoi-exp2.png)