the Delaunay triangulation is really helpful when it comes to physics. It also creates beautiful shapes.

I am writing this one specifically after having read this post on Keith Peters’ blog.

More than a year ago as I was looking for algorithms to create a ‘bacteria generator’, I found the work of flight 404. he was working on his voronoï butterflies. His work is definitely one of my sources of inspiration.

So I became eager to do the same in flash yet at that time I didn’t have the skills to do so.  Earlier this year, I talked to Didier Brun about how crucial and useful the tesselation (triangulation) could be and shown him the various ways I had tried to achieve the port of this (beautiful) algorithm.

He was very interested in Paul Bourke‘s algorithm especially as Paul is giving away the triangulation code in C# (huge thanks to him and huge respect to his work) :)

Didier ported the code in one afternoon (he’s really depressing :) ) yet as he kept the source code for himself, all I knew was that it was possible. Enough for me to give it a go et voilà! (click to draw points, reset to … reset)

• Delaunay.as
• Triangle.as
• Edge.as
• Point.as
• example above

check at the bottom of the page

back to Keith Peters’ post, I have also implemented the Voronoï diagram. the rule is quite simple in fact (joining the centers of the neighbouring triangles). we could also trace the projection of the segment on the screen sides:

• Voronoi.as
• example above

check at the bottom of the page

and as I know Keith loves to make things move, I added that little button on top ^^
it shows that the algorithm computes rather fast with a reasonable set of points ;)

Now this is really promising for triangulation can be used in:

• creating and optimizing 2D (and 3D) meshes
• creating ‘robust’ meshes namely something that does not ‘collapse’ on itself and has no redundant vertices, something to do with ‘minimal structures’ in architecture.
• modeling cells like wood, bubbles, drying mud, skin and creating many other procedural textures
• creating robust 2D models that can be used in physics engines ( my current WIP ^^)
• modeling 2.5D models that can be used in 3D engines
• plus coupled with the new FP10 features, it might just be terrific (the drawTriangles feature howdy!)

I’m already using it in a production workflow to segment objects on the fly and it is working just fine.

for instance, this is an example of an application based on this video

the picture was done by john day check his excellent work here: http://www.behance.net/JonDay

grab the FP10 ZIP or read below

UPDATE
i’ve posted a one class Wonder that does the same as the zip above, faster, with no object creation (only vectors of Int) and mostly without the hassle of the package. it’s available on wonderfl; just follow the link:

delaunay triangulation – wonderfl build flash online

I’ve also added it (along with the voronoi diagram) to the BIGA repo.

I really have to thank Didier. thanks to him I am no longer afraid of porting algorithms from other languages. check the scaleX article ; the port of the C algorithm was done after I did the Delaunay one.

and finally, maybe you’d like to check some resources I collected while studying the whole thing: http://delicious.com/nicoptere/delaunay

and if you want to get inspired, here’s a link giving an idea of what can be achieved
with some patience :) (the base process is a dealunay triangulation)

Tags: actionscript, delaunay, geometry, polygon, source, tesselation, triangle, triangles, triangulation, voronoi