hydra

Hydra is a generative shadowplay.
you can see it here http://barradeau.com/2013/hydra/

I had the idea of doing this for a long time and being unemployed due to Flash’s death, it turned out to be both a good way to learn HTML and the right time to do so.

this article is about how it works, the problems I faced and how I solved them.

here are some outputs of the engine

 

 

 

 

the algorithm

I wanted to keep things as simple as possible ; ideally a child should be able to figure out how it works and get an interesting result. or… well… something.

the algorithm is therefore fairly simple

1. select a random polygon from a library
2. start a stroke on mouseDown
3. slice up the polygon on mouseUp
4. pick one of the slices on mouseDown (red)
5. shrink the selected slice (red)
6. compute a random slice on a random polygon (blue bottom)
7. align the random slice it to the stroke (blue top)
8. grow the new slice (blue top)
9. merge the new polygon with the previous

1 select a random polygon from a library

the first step was probably the easiest, I used the Flash IDE to turn Fonts outline into vector shapes. I used a rather unsophisticated JSFL by Eric Lin
another option is to create a custom font and use the typeface.js generator to convert it to a JSON file describing each character as a series of vectors.

this is a list of the fonts I used:

• http://www.dafont.com/fr/animals.font
• http://www.dafont.com/fr/ding-o-saurs.font
• http://www.dafont.com/fr/heroez.font
• http://www.dafont.com/fr/the-beetles.font
• http://www.dafont.com/tool.font
• http://www.dafont.com/toolz-tfb.font
• http://www.dafont.com/fr/zoologic.font

additionally, I’ve used le monde de Victor to perform tests, this is the one used in the videos below. the final library contains 101 shapes.

once we have the path of each polygon, drawing them to the Canvas is trivial so I won’t cover this but you can refer to the W3C specification and ask internet for tutorials.

one key concept here is the interpolation (aka lerp or lrp) ; the fact of going from a value A to a value B over time. it is used later to inflate/deflate the shapes, it is the most widely used animation technique. the minimal example would go like

this should log a value that oscillates between 0 and 1.

here is a graphic extension of the above on the X and Y axes:

this is an essential concept to understand for anyone willing to animate something on a screen. in the above example, the X coordinate is bound to a lerp and the the Y coordinate as well as the radius of the disc is bound to another lerp (another time value).

2 start a stroke on mouseDown

I was wondering how to create a dashed stroke and found this article. as it’s not supported in all browsers, the trick is to create a fallback method on the context like so:

then to get it to move, we’ll need to store a “dashOffset” value somewhere and say

the rest of the article is pretty clear, it’s worth mentioning that the method is now properly supported by Chrome, FF, IE and Opera.
on a side note, I tried using Hammer.js to handle gestures and it caused some spectacular crashes on iPad so I simply bound the touch events to the mouse events handlers and it did the thing.

as I used rounded coordinates (read below), I needed to inflate the slice axis a bit before the clipping operation so here’s an implementation of the dashed line & a line extrusion:

3 slice up the polygon on mouseUp

I knew this would be the hardest part, mostly because it’s impossible to foresee where the polygon will be cut so it would have to work in all sorts of degenerate cases. it means that we might end up dealing with concave polygons, complex polygons and self-intersecting polygons which are tricky cases to deal with.

after failing badly at handling simple polygons & degenerate cases, I saw this DEMO and started a prototype using the POLYK lib. unfortunately the lib only handles simple polygons. still, it’s handy & I would recommend it for smaller projects that don’t require intense polygon action.

then I searched a bit more and found Javascript Clipper a port of a C++ library. it is extremely robust, rather fast (even in JS) & apart for the use of capital .X / .Y, I found nothing to frown upon so I ended up using it. here’s a live DEMO to see for yourself.

technically, I’m using IntPoints to spare some computations. when the user slices a polygon, the segment is extruded to create a Quad and I perform an XOR operation with Clipper where the subject is the current polygon and the clip is the newly created Quad.

after some time, this part was working pretty nicely but the mayhem was far from over.

4 pick one of the slices on mouseDown

to know which polygon is clicked, I needed a contains method. there are different approaches to solve this, the one I used so far was the one described by Paul Bourke here ( code here ). it appeared to be rather slow & after some research I found another one here that’s way more compact and worked just as fine:

where poly is an array of points & C is a Boolean indicating whether or not the mouse is inside the polygon. it’s quite cryptic yet it works with convex, concave & (self-) intersecting polygons. in my case there was non need to handle complex polygons so I went with it. when the user clicks on a polygon, I test every shape and if one of them contains the mouse Position, it shrinks. later I’ve added the double click to reset the original polygon, this doesn’t use the contains test.

here’s an example of this in action

additionally I had to build a graph of the sliced up pieces ; if 2 pieces share a collinear edge, they’re connected. only the pieces that have exactly one connection are candidates for a click.
imagine a “U” shape and slice it horizontally, the 2 upper legs are valid candidates but the bottom piece can’t be selected.

5 shrink the selected slice

I had some very organic – as in organic matter – yet very mechanic motion in mind. the best example would be the insects’ motion as they stand somewhere between the animal and the machine. on a side note, insects have developed incredibly sophisticated mechanisms to accomplish all kinds of tasks ; if you’re interested in this, I’d recommend searching about Biomimicry.

for the sake of documenting , here’s what I usually go through when I’m after an animation principle (grow/shrink in this case). I tried them all but none of them made it to the final app.

 

I tried to collapse all the shape’s points to the polygon’s centroid. then I tried to use a set of “springs” that would shorten progressively ; after a while, any shape would turn into a straight line (the slice axis) from which I would grow a new shape. I also tried to get the points to follow the shape’s path, fail. then I thought about using the polygon’s convex hull and projecting points onto it…

in practice, everything caused the shape to look ugly because it overlooked the morphology of the polygon ; it was too mechanical. here’s where failing is good ; after all this, I could put a name on what I wanted and this name was a morphological skeleton.

it appears that I did this Binary Skeletonization algorithm some years ago. it retrieves a structure (the medial axis) that gives a rough “skeleton” of a binary (black and white) image. First I tried to compute a geometric medial axis and failed miserably, I took a series of snapshots, never to forget

this was a good start, finding the bisectors was relatively easy but then…extruding the edges went
really
wrong.

so I ported my AS class to Javascript and added a brute force vectorization which gave me this.

this was a debug view, the final version has connected components.

here’s a demo for you to play with (computationally intensive).

 the Hilditch class is here if you need it, here’s how to use it:

then I projected the points of the shape onto the skeleton. the result was much better than all the previous attempts. here’s a sample video.

and here’s the what happens when chaining the transformation

that was it!
I could shrink my shapes in a nice way. I kept the spring-based approach to reset the shape ; it works very well to melt it down (double click anywhere on the hydra page to see what it does).

6 compute a random slice on a random polygon

having solved the picking and slicing algorithms, I thought this part would be a piece of cake but the difficulty here was to find an automatic way to detect the interesting parts of a shape.

the brain is very good at reading the topology of objects. mentally, we do this all the time. I’d recommend reading The Man Who Mistook His Wife for a Hat (Oliver Sacks, 1985 ) if you’re interested in what happens when your brain stops reading the world properly.

a computer on the other hand, is a complete retard when it comes to this. rather, the notion of topology is alien to a machine unless you help it a bit. when you have a set of objects that obey some construction rules (a formal grammar), it’s easier to isolate those rules and imagine an algorithm that will handle them.  in this case, the shapes’ library was very varied which prevented me from taking shortcuts. I searched a way to quantify the polygons & stumbled upon the K-Means Clustering.

in a nutshell, a polygon being a set of 2d points, the K-Means will try to find a given amount of points “clusters” that work together (that have a minimal sum of least squares). the only constraint here is that we must specify the number of clusters ; I chose to have 3 sites which gave me 6 different slice axes per shape.

here’s a video of the K-Means clustering in action

it’s important to note that it’s an emerging process ; it takes a number of iterations to produce stable clusters. you can see the emerging process as the clusters move around to find their final position. it allowed me preprocess all the polygons of the library and isolate slicing axes along which I could cut any polygon before stitching it back to the current shape.

after some research I found an improved version of the K-Means which is called Expectation Maximization Clustering and a javascript implementation by Chris Jormungand. I used the Oriented Bounding Box of the ellipse and selected the edge that was the closest to the shape’s centroid (the red and green dots in the picture below).

the slice axes found with the EM clustering algorithm

7 align the random slice to the stroke

we have a stroke and a new slice to stick to it but it’s not over yet ; for it to work, we need to align the new slice to the slice axis. there’s no rocket science in there yet I went through a lot of trial error. here’s a time lapse of me doing the alignment:

when you see the red rabbit, I’m almost done. below is a clearer view of what happens ; left: pick a random slice, right: align it to an arbitrary axis.

8 grow the new slice

this uses the same algorithm as the shrinking.
as it’s a linear interpolation, rewinding is fairly easy.

9 merge the new polygon with the previous

like slicing, merging is a complex operation so I let the ClipperLib handle it, recursively adding all the parts using a UNION operation.
and we’re done!

some extras

there is some sound when the user cuts the shape and when it shrinks & grows. I used Howler.js to handle this. it is supported erratically among browsers but on desktops at least it was ok-ish. I wanted some concrete sounds, like paper being torn, I found some quality items on freesound.

there is also some blur to mimic a flickering, for now it’s only supported by webkit. tried using the SVG filters too but the computation was disappointingly slow.

on right-click, an option panel appears to let you save the hydra. I wanted to have the possibility to save the hydra both as a picture and as a vector shape. exporting a PNG was straightforward ; I render the polygon normally and use FileSaver.js to save the canvas.
the Vector format was a bit more complicated, first, which vector format? SVG would have been easy to encode but I wanted to be easily editable so I chose the PDF and used this lib jsPDF.

the lib works pretty well, one thing was puzzling though, when drawing something, it uses a turtle. so instead of passing it absolute points locations, you give it a starting point and a series of deltas ; the XY difference between the current point and the next.

I also added a smoothing option which was a straight port of my old smoothing functions along with a Douglas-Peucker simplification method.

the classes are here:

• CubicPath
• Simplify

usage

& that’s it for the technique.

final note

it was my first HTML “app” and my first online art piece. I dare qualifying it as art  because it serves no purpose other than being, it conveys an idea in a performative way and I found nothing to add or remove from it. there’s no manifesto so to speak.
for me, shadows have a great evocative power & I wanted to bring them to life.