Voronoi tesselations. August 25, 2008 at 12:35 pm
As I said in my previous entry, I´m scripting various image processors right now. And, as already mentioned before, my current release deals with Voronoi diagrams. Thereby, it was important to me, that preferably as much tilings as possible might be performed by the image processor. At the present, the whole thing is set up with 100 points moving steady in xy-space and calculating their particular voronoi regions (I get about ~31Ffps averaged in the following example).
Synthesizing on this, I enhanced the composition a bit. So the next example loads a set of images from flickr first, passes through the images and allocates some random points. After that, these points start moving and constantly reading out the colour value of the image at their current xy-position. Then, those values are picked to fill up the detected voronoi regions of each point. I must admit, that this could look a lot more keener if I only could maintain more than 100 points at the same time, anyhow, I think the result looks not so bad after all.
Sehr gut! Voronoi diagrams are cool.
It’s hard to come up with an efficient algorithm capable of producing a realtime animation though. Even with Processing, non-GPU solutions were quite limited regarding sketch area and number of points.
Thx eduardo.
Yes, it´s a little bit like a needle in a haystack to display voronoi diagrams and regions efficiently in flash.
I didn´t work within processing yet, so I thought it would be easier to set up an efficient algorithm for voronoi diagrams with even more points & regions (seems that I´m mistaken in that point)?
I will transform my approach to flash10 in the near future and hope that “real” typed array´s and such will give a performance boost on this. That remains to be seen… ;)
Cheers
_frank
Nice work, Voronoi’s a great starting point for so many pixel effects.
… btw, what kind of algorithm, brute force pixel-by-pixel or something more advanced, did you use ? ( I’ve only written brute-force voronois, so far … )
Thx Petri,
unfortunately the algorithm I use here is very brute force, still trying to enhance the performance.
Maybe I will trash mainly the whole approach and will rewrite the algorithm implying a faster Convex Hull calculation.
damn cool, reminds me i need to look into convex hull algos and all that cool stuff.
Yeah Dominic, you should, it´s pure fun!
[…] posts about Voronoi diagrams [Convex Hull and Things to learn by KP, Delaunay Class by Nicoptere, Voronoi tessels by Frank Reitberger] But all of the representations not what I wanted it to be. Nicoptere’s […]
The brute force algorithm is pretty slow; Fortune’s algorithm would speed it up considerably.
The shading on the region edges in your first example really enhances the slithery quality of the motion!
[…] couldn’t resist, Frank! | […]
[…] for comments on this post. TrackBack URI. Leave a comment. Name (required) Mail (will not be …actionscript microcosmos Voronoi tesselations.eduardo omine, on August 27th, 2008 at 11:53 pm. Sehr gut! Voronoi diagrams are cool. It’s hard to […]