Dark Bit Factory & Gravity

GENERAL => General chat => Topic started by: Xetick on January 24, 2010

Title: My experice down the voronoi diagram road
Post by: Xetick on January 24, 2010

I have been working on a voronoi diagram generator for the past few days. My interest for this little algorithm increased when I saw hellfires neat magnification entry (http://www.dbfinteractive.com/forum/index.php/topic,4255.0.html)

I wrote a little blog post (http://www.plane9.com/forum/entry.php?36-Voronoi-Diagrams) about my experience that might help others out that want to build their own .

If nothing else I recommend you to check out a flash version (http://blog.controul.com/2009/05/speedy-voronoi-diagrams-in-as3flash/) I found.

Title: Re: My experice down the voronoi diagram road
Post by: benny! on January 24, 2010

Interesting stuff and nice blog post.

Here are some more flash examples I know of:

http://www.dasprinzip.com/pExamples/p80_0.html (http://www.dasprinzip.com/pExamples/p80_0.html)

http://www.dasprinzip.com/pExamples/p80_1.html (http://www.dasprinzip.com/pExamples/p80_1.html)

Title: Re: My experice down the voronoi diagram road
Post by: Xetick on January 25, 2010

Thanks.

I haven't seen those links before. The shading in the last one is really nice.

Title: Re: My experice down the voronoi diagram road
Post by: Clyde on January 25, 2010

I remember a dude on the dark bit factor ezboard / yukky forums who did a few examples of Voronoi. not sure if they were animated. I shall see if they still exist there for you if you'd like.

Title: Re: My experice down the voronoi diagram road
Post by: Xetick on January 25, 2010

That would be great! It's always good to get new ideas for scenes.

Title: Re: My experice down the voronoi diagram road
Post by: Clyde on February 02, 2010

Dude, I know i have them someplace I will have a search right now.

Title: Re: My experice down the voronoi diagram road
Post by: hellfire on February 02, 2010

Hi Xetick,

Quote from: Xetick on January 24, 2010

I have been working on a voronoi diagram generator for the past few days. My interest for this little algorithm increased when I saw hellfires neat magnification entry (http://www.dbfinteractive.com/forum/index.php/topic,4255.0.html)

nice to hear :)

Quote

I wrote a little blog post (http://www.plane9.com/forum/entry.php?36-Voronoi-Diagrams) about my experience that might help others out that want to build their own.

Cool.
I used the delaunay triangulation (http://en.wikipedia.org/wiki/Delaunay_triangulation) which solves in O(n*log(n)).
However, when an initial triangulation is given and you're just moving points around (and not generating a completely new set of random points), most of the triangulation keeps constant.
Essentially you just need to recalculate the circumcircles for each triangle and checks the neighbouring vertices of each point.
This way you can easily animate some ten thousands of cells in realtime.