CG Short Open Movie Inspired by L-Systems

IU Home > Projects > dominoesAtDusk
Dominoes at Dusk is a CG Short Open Movie created for an informal talk at the Algorithmic Art Meetup in London. It is inspired by the L-System algorithm used to render the Koch snowflake curve as a sequence of dominoes. The dominoes are animated using an open source physics engine. All image and sound assets used in the movie are rendered digitally by computer.

Dominoes at Dusk

You may watch the full movie of this computer generated domino show on YouTube below.

A playlist documenting stages in the development of the movie is available.

Algorithmic Art Talk

The movie was created for the Algorithmic Art Meetup group in London, UK. The informal talk gives an account of how the movie was produced using a combination of open source (for visual aspects) and proprietary packages (for audio elements). During the talk the L-System algorithm is explained and simple python code presented to implement such a system. The complex process of placing virtual dominoes along the L-System path and their animation using the Bullet physics engine (built in to Blender) is also discussed.

You may watch the talk. Audio begins at 4'04".

Here is the fast algorithm at the heart of the movie, the L-System. The Koch Snowflake curve is rendered with this algorithm and forms the inspiration for the domino path and the central element on the Island:

def systeml_compile(axiom, rules, iterations):
  table = str.maketrans(rules)
  for iteration in range(0, iterations):
    axiom = axiom.translate(table)
  return axiom

You may review the code and digital assets used to render this open movie on Github.

A transcript of the Algorithmic art Meetup at Code Node in London follows.

...typically what happens with whiteboards is you use the wrong pens. So I should say something about Dominoes, maybe I will do that afterwards. Okay so L-Systems. what you do is you have an axiom which is what you start from, a geometric form in the case that we are going to do, and you transform it with a very simple set of rules, and you just keep going. And you get more and more complex shapes if you are doing a geometric L-system, and they are obviously self similar because

they are always acting on themselves so they are fractal in nature. They were invented by a chap, whose surname is Lindenmayer, and he was researching how algae and things like this grow and he wanted a way to look at them formally so rather than just fuzzy qualitative reasoning about why the colonies grew he produced this formalism which you can also use for generating any geometric pattern that looks slightly organic. The one I am going to show in particular is called the Koch snowflake curve and there are many

variations on that particular curve depending on how you start and the rules you use to generate the geometry but I will draw it by hand to show it is possible to produce some art algorithmically but by hand, because if you can do that then you can turn it into a computer program. So as I say we start off with an axiom and if I were doing a complete one I would start with a triangle, in Blender you will see I start with a triangle, but that will take forever so I will start with a straight line. So we are allowed to draw straight lines and the second thing we are allowed to do at this stage is we are allowed to erase the middle third of the line segment.

[Learning to clean the white board using a spray painting technique...]

So I now have two line segments, each of equal length with the middle third removed, and what I am allowed to do now is draw in two lines that are basically at sixty degrees like that. And so this motif is what we will keep repeating over and over

in the curve. Maybe it looks like a tree or a mountain or something. So we do it again, knock out this third and knock out this third, and this is where the self similarity starts to be more evident. So you do it everywhere and then we draw what we did before in all the gaps. Like that. Now we have something which looks more, as you know the punchline, more like a snowflake, or maybe a coastal outline or something like this. I will do one more just because in my mind I did one more, just trying to make the point. So you have to do it everywhere, the middle third of every line. Then you start to see why it is more interesting to have a computer do it.

then fill the gaps something like this. If I had my iPad I was going to zoom in and show you that these segments go all the way down by drawing them all the way down. It is just that original motif everywhere. So the question then becomes how do we turn this into a proper L-System so that a computer can render it for us? I will change colour just because I'm changing colour. So the L-System starts off with an axiom which is a symbol from what they call an alphabet which is just a set of characters and typically there are not very many characters, maybe three or four, and you have a set of production rules. So you say you know this character goes to this string and at each step you take the old string and

every single character and match it with the set of rules, very simple, once through and it produces a new string which is usually longer than you started with. Then the final step which comes later is you say oh well you know this character means draw a straight line this character means set the colour, this characters means turn right sixty degrees so that is kind of the fun part maybe. I am beginning to regret doing so many cuts now. Basically if we were to try and draw this again with a computer what we would first notice is that all these line segments are the same length, ok, so it then becomes very obvious that using a sort of turtle graphics system is a good way to render the final result. That is what I did so I will show you the production rules and then

you have to imagine I have written some turtle graphics system which of course I have but not on the whiteboard. So we will start off with a line. If you look at L-systems on wikipedia you can find all of this. In fact I took all of the L-systems from the wikipedia page and implemented them in python and you'll see its just a couple of lines of code, it is nothing, so I may not use the same letters as they use on the wikipedia page but I will try to. I think they used F and plus and minus I think. So we are going to start off and say what they call the axiom, which is the seed or the first one, is F a straight line. And then we are going to say that F transforms in some way and basically it is that F transforms to this

which, if you suspend the idea that this is meant to be geometry, at each iteration F becomes smaller, the actual line that you draw, so we want to go to from that well its going to be F and we want to turn that way so we are going to call that plus and stick an F in and then I want to turn that way twice so minus minus and stick another one in. And then plus again and then F. So it is quite a long rule but that is all it is. So we start off with that and at each step you replace F and only the F's with that string. And finally you end up with some massive long string which is, you know, F plus F minus minus all the way along. And if you scale your straight lines

appropriately it'll draw it out. And you know you can do each iteration and have it drawn over the top as you'll see in one of the blend files that is what I do. And that is it. That is L-systems. They are pretty simple but there are so many of them. And I think there are still open problems, things like which shapes can be represented by L-systems? I think that is probably quite an interesting one to look at. As I mentioned at the start these characters really can mean anything so some of them might mean assigning a colour. Maybe Tariq might talk about generating things that look more like trees and plants, and I know that in some of those systems they put extra characters in so that they can get the colours to change and they change near the end of the branch and so you get you know nice realistic looking tree or

weed or flower you know. But this one looks more like a snowflake and I like the idea of it looking like a coastline. I think it looses the look of a mountain pretty quickly. Does anyone have any questions about L-Systems at this stage?

[A question was asked about using special software to do the white board work using an iPad and a projector - no I was just going to use the built in notes app with the pencil]

Okay let me first say something about dominoes. My kids and I watch a reasonable amount of YouTube and at some point all these dominoes videos suddenly started coming up and, you know it is just too easy isn't it? You see them and you think surely I could create an animation in a computer that does something like that. And I like watching them fall over it is quite satisfying isn't it seeing these things and see the waves go through and so on. That is the reason I chose to render the Koch curve in a series of dominoes and you will see them fall over. And the reason they fall over is that in Blender it has a physics engine, and that is what I used to achieve that effect.

So we have the algorithm to generate the path and we've got the algorithm to generate the actual movement in the frames. I did this ages ago when I started seeing these videos. I did a few test renders in Blender just to see what I could get it to do. So this is actually just OpenGL. But it shows you the basic idea. You setup some squares like that, and you turn the physics engine on, and come back twenty minutes later and that is what you have. Although what you also get if you can see it is the ones up in the top, the thing about the physics engine

is is that it is an approximation. So can you see they are still moving If you watch just the top corner, see? Weird. Why does it do that? So you do get some odd effects like that. There are ways that I found to reduce them and there are YouTube videos that talk about it as-well but I guess you always end up with that so what you might end up doing in the end is you can take all of the physics and instead of running in realtime you can bake it to animation f-curves. And then you can go in and say I don't want that one to do that so I am going to delete its f-curve and it doesn't jiggle anymore. That takes a lot of time so I haven't necessarily done that in the video I am going to show you at the end. Again as I say if you move quickly enough over things you can't see the noise in the picture, you can't see that some of the dominoes are still moving.

Part of it comes from the fact that the dimensions of the dominoes are, well I tried to make them fairly realistic, and the bullet physics engine it doesn't like things under a certain size. It says in the manual it becomes unstable. So the other solution is to make the things that you are animating larger and then shrink them down but then what you tend to find is that the time does not really look right and then you have to tweak other things. It's a bit of a trade off. And then this was just something fun that I did want to do but I think just would have taken too long to render so basically I put lights in these dominoes

And what I was going to try and make it do was for the dominoes to light up when they fell. But putting all of these extra pieces in just increases the render time because for it to do it accurately with all the caustics in it just takes for ever. And each of my frames was taking two and a half minutes to render and I really cut down the number of paths. I think I only used sixty four paths which is quite low, and I think to get this to render decently I'd need a lot more and it would have taken days. I didn't actually do that in the end for this project anyway. as I say there is a denoising feature coming to Blender in the next release which I think would help mitigate that problem a bit.

Right so we'll go into Blender. So does everybody here know what Blender is? So it is a digital content creation tool and it lets you go all the way through to creating a full movie. So you start off modelling objects in three dimensional space. You can texture them. You can light them. You can animate them. You can produce video strips from that. Then you can run through a compositing process at the end and finally produce HD or 2K full on videos. And you can do it all within one program. Now I personally think that is great but I know people don't always agree but as somebody was saying earlier, the fact that there is so much stuff in there does mean that

some bits of Blender seam quite complicated. So for instance these screens are quite busy. But basically you split the screen up and set which type of view you'd like to see and they do also have this feature here, to be honest I am not sure what it is called, but depending on what workflow you are currently doing you can change to, you know, animation and this view has the best default views and so on. So to start with we will load the python source code and go through that. Then I will probably run it and probably generate a curve in front of your very eyes and prove it is not magic and if not we'll go with the backup file which of course is checked in to Github.

This machine is not the one I used to do any of the work so I will probably spend a little time trying to find where I put everything. Blender also has this concept of linked libraries. I used that on this project and it was the first time that I had used it but it was quite useful. So what it let me do was put everything in separate files. The idea being if you want to change a domino you go to the domino file and change it there and then because it is linked everywhere else, everywhere else just picks it up. Because otherwise I tend to find if you have got everything in one file it is too easy to copy it and then you want to tweak a little bit of it but you have copied it and so then you know you are kind of having to change it in two places and then worse you have to remember everywhere that you copied it and so on

I think the linking is quite a powerful feature that you can use. The great thing as well is that you can do it with the code. So I put all the scripts into this file called all scripts. And then I linked it into the other files that needed various bits of the scripts. I did write some general utilities which we don't need to talk about today. There is a script that actually created the L-system. There is one that draws the turtle graphics paths I am speaking about. That is how we get the basic curves. This one that is the helper to render them connects the L-system generator to the turtle graphics generator. And then the final one, this thing called path walker, is the thing that moves along the path placing dominoes. The reason that I wrote that is that originally I thought I was going to light them and I wanted to put very specific

things along all the points, but you know time is a great leveller as they say. I didn't actually get that far but it is all there to actually do it. I will attempt now to simplify the screen as I have such a small laptop. Is that large enough for everyone to read? Yeah? Good. So I will start off with the code to generate the L-system. Now this is all python and it is python 3. I've used python over the years, usually one of the 2.7 varieties but 3 seems quite easy to use. Blender at the lower levels I think

well it is kind of a C, C++ type system. And then python is put onto the top to do all of the interface and a lot of the operators which are the commands that you actually run in the interface. Because it is done that way it is kind of a little bit like in Excel you can record a macro and you can see what commands it executes. You can see what python it is running if you drag down that section and as a programmer that is really useful because it gives you a starting point to say; right I know what to do by clicking these buttons so I can scale it up to do five hundred dominoes and very complicated stuff.

And also because it's all in python all the source code comes with it. So if you look in the Blender distribution as a programmer again, you can just pile in there and find something that does something vaguely like the thing you are hoping to do and use it for inspiration. One of the things you are not supposed to do, and I found this out myself the hard way, but then also I happened to watch a Blender developer video where they actually said it, do not call the operators directly. So it will show you on the screen what the operators are, and you can then go and look at their code, but do not start scripting up call this operator, call this operator, because it just doesn't work out. It either crashes or it is just incredibly slow is one of the problems that you get. So the best thing to do is look inside the code and take the bits that you need to get it to do what you want it to do.

So having said all of that creating the L-system is completely independent of Blender. You could run it in any python on its own. It is quite small. This is actually the original function which I mysteriously appear to have appended slow on the end of. So what we are going to do is start with an axiom, which from what we said before is like 'F'. We are going to start with a set of rules and because python supports dictionaries I just pass those in I think in the natural way so there will be a key in the dictionary which is the 'F' and then that will give you the string F plus F blah blah blah. You also say how many times you would like it to apply the process. Then hopefully the code is more or less straight forward. So it simply says for the number of iterations you asked, the next axiom I called it or the next result

start off by setting it to empty, but then for each symbol in the current axiom, you go through and if the symbol is in the rules, which it kind of has to be for the purposes of writing ok code I did it like that, so if the symbol is in the rules then set the next axiom to be whatever it is so far plus the transformation under the rules of that symbol. And this is just for safety just incase there was a symbol that isn't in the rules because I think again maybe for the colouring scenario maybe, sometimes you will put things in that are not transformed. You know it's like the identity. The two solutions to that are you just put extra things in the dictionary or

[An audience member mentions the plus and minus symbols from the whiteboard]

You are absolutely right and I think that is probably why I had to write this line of code because otherwise the plusses and minuses would disappear wouldn't they?