Fractal distraction

It seems I've not got around to much writing recently. This is partly because I've been quite busy at work (conference paper - yey), but also because I had something else to get distracted with. Recently, there has been a lot of interesting distraction in my lab with people making fractals, and various other patterns, so I had a lot of fun getting involved with all that - here are some of the results.

It all started when my friend Jack, in a bout of epic procrastination, created a rotating fern-like fractal. We all spent ages gazing in wonder at it - it's mesmerising, especially once he altered it so that its acceleration changed randomly, meaning its was smooth but still totally unpredictable. There are videos of it here.

The problem was that this is written in C++, and uses the OpenCV software library for drawing, so isn't exactly portable to everybody's machines - and while you do get to watch the video, it's the same every time. This is where I came in, with the plan of making it available to anyone: so I re-implemented it in javascript (a browser-based scripting language). This was a bit tricky, since I'd not done any javascript in years, and that was just to flip some images around on links on websites. Fortunately, once I got the hang of drawing a line, it was reasonably straightforward to translate (except for some odd properties of javascript and the way error reporting consists of it simply not working).  My initial implementation can be seen here, from before I worked out how to have lines of different colours (I haven't bothered with the random acceleration, so motion is a bit more jerky as speed randomly changes). [Note - all these examples work in chrome, and maybe newer versions of firefox... anything else, I can't guarantee]

So, a bit of background to how this works: it's a recursive drawing algorithm, which basically means that at each stage, the algorithm does something, then calls itself, and so on indefinitely (up to a certain limit). The basic step is to "draw two branches", where to draw a branch, it draws two more branches. The interesting patterns result from the angle between subsequent branches being passed down the levels, at each level being relative to the one before, which is what leads to the curling effect. It's quite interesting to play with the different parameters, such as the ratio by which the lines get shorter at each level (turns out a scaling of 0.7 is almost always the best; yes we tried the golden ratio.)

Stacks and colours

It's a well-known fact that any recursive algorithm (one that achieves its aim by repeatedly calling itself) can be implemented instead as an iterative algorithm - that is, a more 'normal' one where the instructions are layed out entirely within one function. Obviously, it's not possible to write it all out explicitly (well, it would be very tedious), since it isn't generally known how far deep to go - but this can be achieved using a structure like a queue to store the future branches that need to be explored. So, basically as a programming exercise, this is what I did. Javascript isn't exactly bursting with sophisticated data structures, but I managed to implement it as a stack, where each item in the stack holds the starting position, angle, length, and the depth of the current branch. It can be strange to imagine how an iterative algorithm can produce patterns like this - but basically, the first branch is put onto the stack; then at each iteration of a loop, the last thing on the stack is read off, drawn, and replaced with its two child branches, and so on until the deepest allowed level. Sometimes iterative algorithms can be (much) more efficient than their recursive equivalents - that might be the case here but I've not checked.

In re-writing it I played with a few other things too. Now the speed of the two main branches vary according to sinusoidal functions, so they reliably speed up, slow down, and change direction. This means there's actually no randomness at all, and yet complex and seemingly unpredictable patterns emerge, and you'd have to watch for a long time until it repeats. Mmmm complexity. The main thing that makes this version look nicer is the colours: the colour of each branch is now determined by its angle, by mapping it to a hue wheel. (Briefly: colour can be represented by hue, saturation, and lightness, where hue is a value that cycles from red, through yellow, green etc, finally via purple back to red. Saturation controls how intense the colour is, and lightness is where it sits between black and full colour).

The great thing about writing in javascript is that not only can anyone with a suitable browser see these, but you can also see the code (right click, view source). So feel free to copy it and have a play around; it may not be the most elegantly written piece of code but hopefully should be reasonably self-explanatory.

Clocks

At some point someone mentioned that the two branches rotating around each other at different speeds are a bit like the hands of a clock... and this gave me an idea. Could it be turned into a clock? Well, first it would need three hands, to do it properly and actually see the motion - fortunately this is pretty easy, and in fact the number of branches at each level was just a parameter in the original code. Generally more than two branches just looked a mess though, so for the clock version I altered the length scaling to thin it out. Secondly, the hands on a clock are different thicknesses and different widths - this required a few more parameters to be passed down the levels, to change length and width of the three branches independently (and to make the lines thinner as they get shorter, lest it become a big mess of overlapping lines). That, plus the hour-ticks, and the Fractal Clock is born:

It gets the current time via a javascript function, so it should always be the correct time wherever you are. The motion of each hand is smoothed by getting the exact, fractional number of hours, minutes and seconds, otherwise the hands tick (you can turn this on/off to see it, but I think the smooth version is nicer). You can read the clock pretty much as a normal clock, by basically just looking at the three main arms coming from the centre (the fractal ends don't point to anything in particular) - but if you look closely, at each junction there is another mini-clock, at some other orientation, and so on down the branches.

Again, in this clock, the colours are determined by the angles, where red is up (so the wheel shown above is rotated, but that's because having red=0 at the top makes sense on a clock face). In fact, this means you could tell the time simply from the colours of the three main hands, without bothering to look at their orientation... and this leads inevitably to this, the Hue Clock:

Yes, you can really tell the time from it. Imagine the hue wheel - red corresponds to straight up, so if the hour panel (the left-most) is red, it means it's midnight (or mid day, it's a 12 hour clock). If the second panel is greeny-yellow, it's quarter past the hour; and the third panel goes all the way around the hue wheel once per minute. Now we can finally tell the time with ease! (As I write this it's lawn green past cyan - that image was taken at orange past cyan, earlier in the hour)

Where next for the clock? Is this as minimalist as it can be? Not quite... see, the 'coordinates' of the current time (hour,minute,second), requires three variables. A colour, in the red-green-blue colour space (which is what's used to specify all the colours), needs three variables... you can see where this is going. So here it is, the RGB clock.

Admittedly, it's slightly harder to read the time off it. Basically, the redder it is, the closer it is to midnight (or mid day); the green component gradually increases over the hour, flipping back to no green at :00 (unlike hue, channel brightness is not cyclic); and if you watch it over the course of a minute, the blue component will gradually increase, before going back to 0 at the start of the next minute.

Now that I'd made pretty much the most minimalist clock possible, I moved back to other uses of the fractal. Well, it could have just been a single pixel, but that wouldn't look so good. I probably should have just made it the web page background and got rid of the canvas tag... I'm sure someone else can do that if they want.

The third dimension

The thing that seemed obvious to me with the original fractal is that it's only in two dimensions... and I do like to generalise things. So, my intention since the beginning was to adapt it to 3D. For this, I need some sort of 3D display environment, but didn't want to give up javascript, which doesn't have any sort of 3D environment. So I built one.

The can be done fairly easily because all you actually need to make a 3D environment is the ability to project a point from some 3D coordinate system, to 2D coordinates on the screen. That essentially defines the virtual camera with which you view the world, so you can see things in proper perspective, and freely move around the environment, just by changing the camera parameters. Dealing with the perspective projection of a pin-hole camera is something I've dealt with extensively in my work (it's a rather fundamental concept in computer vision), so now I just needed to use it the other way around, to create a 3D environment as seen from a 2D one. I'd actually done something quite similar before when I implemented a 3D environment with SDL (a basic 2D drawing library), using only a line drawing routine, in pure C (basically to see if I could) - so repeating this in javascript only took a couple of evenings. The biggest job when writing it with SDL one was to write a simple matrix library from scratch, to do all the necessary matrix-vector multiplications... but I realised I this was not strictly necessary, since it was quicker just to hard-code the relevant equations for projection and camera motion.

(Yes, I know I could have used VRML or something, or found some extension for javascript that renders in 3D, or at least matrix algebra; or used some 3D Java in an applet - but I like a challenge, and most of the fun was in proving I could make a 3D environment using only a line-drawing function and no matrix library in pure javascript... that's just the sort of thing I do).

Here's the 3D environment. Basically you can walk around the grid, see some simple, static fractal trees, and play with some particle effects (easy and fun!).

It's quite tempting to turn this into some sort of 3D shooter. Not now.

The simplest thing is to simply put the 2D fractal into some plane in this space - which is quite nice in itself, since then you can walk around and behind it and view it edge-on (this is still possible in the full implementation below).

The next step was to generalise the fern fractal to 3D. This actually required only a few changes: the main one is that the 2D version needs one joint angle per branch, while in 3D, it needs 2 (angle in the plane, and angle out of the plane, is one way to think of it). These two angles define a vector in 3D, which along with a length, specifies the start and end of each line in 3D space. This means that the fern is now fully in 3D, branching out into a volume of a (hemi)sphere, not just a circle. It looks a lot more complicated (it's still completely deterministic), and it's harder to understand what's happening from one view, so it helps to walk around. Controls are explained on the web page, allowing you to change the colour and speed (since there are two angles, one maps to hue, the other to saturation, giving each 3D line a unique colour).

So this is the kind of fun stuff that's been going on in our lab for the last few weeks (I love my lab). What's interesting is that after I ported it to Javascript, we each picked a language to see if we could write it with that - C# was done (that looked very nice); then Visual Basic for Applications (embedded in Microsoft Excel!) was surprising but actually looks great; there was even a cut-down Matlab implementation. It would be fun to try in something a bit more unusual, maybe Lisp, Haskell or assembler. It's a nice way to learn a language, a sort of visual Hello World - I've learned a ton of javascript by doing this, that I'll probably not use again.

That's basically it for the fractals and clocks - I think I've taken them as far as I want to for now (I do actually have work, see). Play with the code and see what you can do. People running Windows can set these to the desktop background (as the active desktop) - having the fractal or hue clocks as the background would be kind of awesome, if not a bit CPU hungry. Android coders might want to make a Hue Clock widget for a phone. It should also be possible to turn these into screensavers, using OpenGL in Linux (my first though on seeing Jack's fractal was "screensaver!" but I don't have the time to get into it right now). Then there's the potential for other types of fractal, or even more dimensions. I'd be interested to know if anyone gets some other adaptations running...