my first Flash on The Beach is over, it was one of the best times I’ve had in a long while.
spending 4 days with talented flashers/designers/creatives/devs from around the world is really a unique experience. I had a chance to attend sessions by people I consider to be the best digital artists but also to find myself new heroes.

[update]an implementation of the incremental convex hull algorithm is available here


along with my elevator pitch siblings I dare say that the climax of this event was the elevator pitch itself.
I rarely reached such a level of stress, I never felt so good than during those 3 minutes.
I had the privilege to meet John Dalziel who was also speaking at the elevator pitch, he wrote a great and indepth article about the process of being a pitcher. you can read it here:
Famous for 3 Minutes John Dalziel’s experience at the Elevator Pitch.

soon the videos will be posted on the FOTB website, you’ll see our faces, our actual speeches and will get a chance to vote for the presentation you like the most. This is a good thing for we (pitchers) were very frustrated not to see the others’ presentations.

MY OWN PRIVATE ELEVATOR PITCH

This is also the point of this article, I’ve done a screencast of my pitch.

you can check it on vimeo : http://vimeo.com/15465709
it’s sometimes lagging, the resolution is way too big for a screencast but it gives an idea.

MOTIVATIONS

I wanted to use 3D, many things are about to change with flash and 3D so I wanted to create an algorithm of dynamic fracture (shatter, break… ) that would break apart any mesh at runtime. I think we should really start thinking big with flash and 3D, if my guess is correct, we’ll soon get a GPU support of some kind and this would mean a “WOW” boost in performance (say Flash would become somewhat like Unity3D). That’s why I chose to work in the field of dynamic 3D algorithms ; there will soon be a lot of things to do, algos to find toolboxes to build etc.
It was very important for me to have the demo run live in the browser and most of what is shown is done at runtime in Flash (only the last mesh was pre-broken for it would have taken too long). the demo is subdivided into 4 parts that show the 3 steps of the algorithm and an implementation into jiglib.

1 – HULLING:

I started reading about fracture algorithms. I found quite a lot of papers most of which would perform either “fast and cheap” or “realistic” fractures, like bullet impacts or bomb explosions. of course I wanted something in between :) going too much into details would take hours so to make it short, the first step was to approximate the mesh to perform the computation faster. This is why I had to find the convex hull of a mesh. I’ve implemented the “incremental” algorithm, you can learn more about how it works here:

• 4 different ways of hulling a set of points
• expected results and a C implementation (that I didn’t use)

this algo has MANY possible uses and can prove especially useful for games and geometry stuff as it approximates the bounding volume of highly detailed objects.

for instance ‘helmut the helmet’ (white mesh) is around 3000 faces while its convex hull (bright yellow mesh) is around 250 faces

2 – BREAKING

the second step of the algo is to break apart portions of the source mesh. we can build an arbitrary hull of a set of points. as we keep references to the building tetrahedra of the hull, we can easily perform a test to check wether a triangle of the source mesh belongs to a given tetraheadra of the hull.
new meshes are created with those faces.
that’s what happens in the video when you see this:

the bits of the source mesh are collected incrementally after the convex hull’s tetrahedra, then new sub meshes are rebuilt.

3 – HALF EDGE data structure

this was somewhat convenient yet some of the new meshes were still split into two or more parts. using the inside/outside tetra test is fast but it doesn’t take into account wether or not the selected triangles are linked. so we often end up getting chunks of mesh that are in two or more parts and when they move it’s kind of weird. fortunately for us there is a solution and it is called the Half Edge data structure.
read:

• http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml
• http://www.cgafaq.info/wiki/Half_edge_general#Data_structures
• http://www-i8.informatik.rwth-aachen.de/OpenMesh/Documentation/OpenMesh-2.0RC3-Documentation/mesh_hds.html
• http://wiki.jpatch3d.org/doku.php?id=dev:halfedge

which I summed up like :

that was it! the new chunks of mesh can now be subdivided in a clever way so that we obtain only isolated meshes.
applying this algo to helmut the helmet would give us the pieces in color:

it is very accurate ; first, ALL the sub meshes have been found (nothing of source mesh remains white) and second you can see very small details being isolated.
downside, it’s very slow :)
huge improvements can still be done and a good idea would be to choose a different data structure depending on the test we need to perform.
Still, this Half edge data structure is Über Powërful, someone I amdire actually does incredible things with it:
W:Blut – Hemesh : a 3D mesh library for Processing
this is inspiring and I’ll keep exploring what can be achieved with it.

4 – FRAGILE

and finally, putting it all together, I wanted to inject the results of my dynamic fracture algorithm on a big mesh (3600+ polygons) into JiglibFlash (a realtime 3D physics engine).

this was kind of the last brick of my “session”, also the part on which I spent the less time (was more of a last minute idea). the results are not really what I expected, bits are wiggly, bounding boxes/spheres are inaccurate, but at least it sort of worked. I liked very much the idea that this ugly & scary cyberdemon ( DOOM3 ) would become as fragile as Glass and tear apart in the wind :)

THANK YOU.

I think I have a couple of people to thank:

- Jean Marc Leroux : he’s the guy behind Minko, not only did he let me play with it but he actively contributed to solving some problems I’d still be dealing with. he implemented some helpers to allow me to work with it and so on.

- John Davey: I found it a pretty unfair, after the last session, not to have given him a big nice thank you. (people would rush on Jared Tarbell’s gifts instead :/ ) even if he’s some kind of a big bear, rude and straight forward, he deserves much respect for organizing this event (Flash on the beach).

- all the people I had a chance to talk to / meet ( even if for a couple of minutes ):
John Dalziel, Jens C. Brynildsen, David Vogeleer, Marc Thiele (& FFK organizer ), Frank Reitberger and his best half Marieke, David Lenaerts, Jared Tarbell, Grégoire Divaret, Julien Terraz, Quasimondo, Tomek Augustyn, Jasper Stocker, Thibault Imbert, Kate Genevieve, Nicola Bortignon, Robert Hodgin, Dave Steward, Roman Hippler (go freelance!), Ralph Hauwert, Dan Sumption, Bertrand Larrieu, Julien Vallée and his best half Eve, Dominic Gräfen and his best half Marieke, Mr doob, Fabrice Closier … + + +
you all made these days unforgettable, so THANK YOU.

one last thing is that I might ask you to vote for me ; amongst the 20 pitchers, 3 will be voted to come back next year, I’d love one of them to be me :)

PS I’ve uploaded a couple of pictures : http://www.flickr.com/photos/barradeau/sets/72157624953095745/
& btw this is my new flickr account

Tags: 3D, actionscript, algorithm, break, convex, convex hull 3D, dynamic, elevator pitch, fotb, fracture, fragile, hull, minko, session, shatter