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.asTriangle.asEdge.asPoint.asexample 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.asexample 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)
FlashDevelop
HAXE
Michael
on Sep 10th, 2008
@ 12:26 pm:
Very cool, Nico. You’ll give Keith Peters a run for his money! :)
Mr.doob
on Sep 11th, 2008
@ 7:40 pm:
Amazing job Nicolas!
Take a look at this:
http://demoscene.tv/page.php?id=172&lang=uk&vsmaction=view_prod&id_prod=13098
It’s so far the best use of the algo imho :)
Generative Art: Voronoi Fractal | astatic notes
on Oct 2nd, 2008
@ 10:49 am:
[...] found some 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 [...]
nodename » Have you seen this man?
on Oct 13th, 2008
@ 5:40 am:
[...] The program uses Nicolas Barradeau’s Delaunay triangulation code. [...]
Frank Reitberger
on Oct 13th, 2008
@ 4:28 pm:
indeed nice outworkings, nicolas.
Nate Chatellier
on Oct 15th, 2008
@ 12:45 am:
Really nice work! Thanks!
Alan Shaw
on Oct 15th, 2008
@ 6:38 pm:
Check it out:
drawTriangles howdy!
nicoptere
on Oct 16th, 2008
@ 9:55 am:
thank you all.
it’s very gratifying trust me :)
eugene > very nice work.
frank > I bookmarked your blog this time :) (very nice works).
Alan > this is very impressive and very inspiring, congratulations.
Generative art: Delaunay Triangulator | astatic notes
on Nov 7th, 2008
@ 4:50 pm:
[...] the help of Nicoptere Delaunay class I made this small application that can be used to redraw any image from your hard drive and save it [...]
subblue
on Nov 18th, 2008
@ 10:40 pm:
Excellent work Nicolas!
Tom P
on Feb 8th, 2009
@ 5:32 pm:
Hi, Excellent work! I’ve been looking for a delauny implementation in AS3 for a while. I notice that your method for computing the voronoi polygons isn’t quite right though.
If you have a set of long thin delauny triangles you can see the problem most clearly; some pixels which are closer to point A will appear in the polygons of point B or C. A correct method is to draw lines which intersect the mid point of the triangle edges and are perpendicular to them, these should cross each other at the Voronoi polygon’s vertices.
I think that this should stop the flickering when you animate the voronoi regions too.
Hope that makes sense.
-T
2D to 3D Photo with Delaunay triangulation | Neuro Productions
on May 15th, 2009
@ 3:44 pm:
[...] week I stumbled on a great AS3 Delaunay Triangulation class by Nicolas Barradeau (Ported from a triangulate algorithm by Paul Bourke ). And when I hear triangles, I think 3D. [...]
nicoptere
on May 16th, 2009
@ 9:14 pm:
thanks all :)
Tom > very true.
some time I should fix it up.
there are now dozens of delaunay / voronoï triangulators around.
check: astatic notes, nodename and prinzipiell ‘s blogs in the blogroll for 3 awesome (and probably much better) versions.
Muki Muki - Benjamin Jung's Flash Blog » Morphing
on May 20th, 2009
@ 6:33 pm:
[...] explained and implemented it in AS 3.0. You can find one here from Zachary Forest Johnson or here from [...]
Controul > Speedy Voronoi diagrams in as3/flash
on May 22nd, 2009
@ 2:21 am:
[...] toy, even though you don’t see the sources. You get a different tool for the same job by HIDIHO!, he goes through Delaunay triangulation, and then translates to a Voronoi decomposition, the two [...]
Og2t
on Jul 20th, 2009
@ 2:39 pm:
Hi Nicolas!
I’ve just posted an experiment using your Delaunay classes.
Li
on Sep 30th, 2009
@ 12:10 am:
Awesome work!
I am observing though that the Voronoi diagrams drawn are incorrect. If you make a quick test, you’ll easily see that the cells do not always contain the points that are closer to the cell focus point than to any other point.
2D to 3D Photo with Delaunay triangulation | Neuro Productions
on Feb 13th, 2010
@ 3:48 pm:
[...] week I stumbled on a great AS3 Delaunay Triangulation class by Nicolas Barradeau (Ported from a triangulate algorithm by Paul Bourke ). And when I hear triangles, I think 3D. [...]
szataniol
on Sep 7th, 2010
@ 1:25 pm:
Great stuff, thanks for sharing :)
wagster
on Mar 27th, 2011
@ 5:50 pm:
Thanks for this – very useful for generating 2d shapes for rendering in Away3D.
Unfortunately it won’t yet handle concave shapes – any idea how I might approach modifying this class to exclude triangles that lie outside the boundary defined by the Points I pass in?
nicoptere
on Mar 29th, 2011
@ 5:31 am:
Triangulating a polygon is not something delaunay will do for you.
You’d rather check some triangulation methods such as ear cutting http://en.nicoptere.net/?p=16 :)
Delaunay for fun « miaumiau interactive studio
on Jul 27th, 2011
@ 1:54 am:
[...] por la red información sobre el tema, me he encontrado con un post en el blog de Nicolas Barradeau que ya había portado a as3 el código de la triangulación. La [...]
rostok
on Sep 24th, 2011
@ 6:06 pm:
hey, this piece of code works great. thanks for port.
i had some problems with it but after little investigation i found out that some of points i passed to triangulate() were doubled. so please emphasize that all vertices must be unique.
btw. i use it in to setup pathfinding with a*.