Structure Synth Findings

Flash port

Keim has made a Flash port of Structure Synth. Not a lot of info here, but it seems that most of the EisenScript syntax has been implemented. Rules need to be programmatically created though, there is no free-text parser yet.

And if that wasn’t impressive enough, he also has created a version with Screen Space Ambient Occlusion. SSAO is a technique for creating real-time ambient occlusion simply by estimating the amount of oclusion by looking at the depth buffer. I’ve considered implementing it myself in Structure Synth, but had never thought that Flash would be fast enough to accomplish this.

And while I’m at it, Wonderfl is quite impressive in itself. It is a website, which makes it possible to edit and run small Flash programs, but most importantly it makes to easy to build upon other peoples work by forking it.

Art of Illusion

Ezziolai has created a Structure Synth plugin for Art of Illusion.
This thread contains the relevant links and some very good examples of Art Of Illusion renders.

Example image by Jep (found at the Forum thread)

Structure Synth 0.9.5 (“Haiku”) Released

A new version of Structure Synth has been released. It has several new features.

New commands

First of all a new system for generating random colors has been created – it is possible to use multiple palettes, including sampling colors from bitmap pictures. This was covered in a previous blog post.

The EisenScript has been extended with a few other commands: It is now possible to terminate the structure building when a given state reaches either a minimum or a maximum size. A new color blend operator was also introduced.

(The new color blending operator)

The new set seed initial command is also a very interesting addition: this makes it possible to combine randomness with self-similarity.

(Example of a random system, but with fractal properties)

Structure Synth now also supports drag’n'drop of EisenScript files onto the GUI. It is also possible to pass an EisenScript file as an argument to Structure Synth from the command line (this also makes file associations possible).

Licensing and packaging

A new license option is now available for Structure – previously the only option was GPL, but now Structure Synth is dual licensed under both the LGPL and GPL license. This was made possible, after Nokia acquired Trolltech and changed the Qt open-source licensing. I really think this is a wise move by Nokia – it will certainly speed the adoption of this excellent API. The LPGL makes it possible to use Structure Synth functionality in commercial and/or closed-source applications (e.g. VVVV integration would now be a possibility).

The examples and the export templates have also been cleaned – and new SunFlow templates by Neon22 and Groovelock have been added. Also a Blender importer by David Bucciarelli has been added. The PovRay exporter has also been restored.

Finally, Miriam Ruiz has begun creating Ubuntu and Debian packages for Structure Synth. Once approved they should be easily available on these platforms too.

Release Notes

Structure Synth 0.9.5 (“Haiku”) Released

Binaries for XP and Vista.
Mac binaries will hopefully be available soon.
Linux is still source only.

New features:

• New color features: a ‘random color’ operator with different palettes (random hue, random rgb, greyscale, sampling from image, or from user-defined list).
• Now uses two independent (Mersenne Twisters) random number generators: one for geometry and one for colors.
• Upgraded to Qt 4.5.0. Now Structure Synth is dual licensed under GPL and LGPL.
• Added ‘blend {color} {strength}’ operator.
• Added ‘set seed initial’ for syncing random seed.
• Added ‘set maxsize …’ and ‘set minsize …’.
• Added support for specifying a startup .es file on the Commandline (this makes file associations possible).
• Added support for drag’and’drop (drop a .es file onto the clipboard).
• Added simple GUI for manipulating preprocessor defines.
• Added templates by Neon22 and Groovelock to the distribution.

Minor changes and bug fixes:

• Added close icon to tabs.
• Applied more aggressive optimization on Windows build (SSE2/fast fp-math). SSE2 is now required!
• Fixed a bug where a recursive rule (not producing objects) could fill memory.
• Added export of background color to templates.
• BugFix: The scrollwheel can now be used to zoom again.
• PovRay template export has been restored. The Camera export still needs some work, but it should be usable again.

SourceForge.net

Random Colors, Color Pools, and Dual Mersenne Twister Goodness.

I’ve implemented a random color scheme in Structure Synth, using a new ‘color random’ specifier.

But what exactly is a random color? My first attempt was to use the HSV color model and choose a random hue, with full brightness and saturation.

This produces colors like this:

Most of my Nabla pictures used this color scheme. It produces some very strong colors.

Then I tried the RGB model using 3 random numbers, one for each color-channel, which creates this kind of colors:

I decided that it was necessary to be able to switch between different color schemes.

So I created a new ‘set colorpool’ command. Besides the color schemes above (‘set colorpool randomhue’, ‘set colorpool randomrgb’, and ‘set colorpool greyscale’) I created two additional color schemes:

One where you specify a list of colors:

(For this image the command was: “set colorpool list:orange,white,white,white,white,white,white,grey”. As is evident it is possible to repeat a given color, to emphasize its occurrence in the image.)

And on where you specify an image which is used to sample colors from:

The command used for the above image was: “set colorpool image:001.PNG”. Whenever a random color is requested (by the ‘random color’ operator), the program will sample a random point from the specified image and use the color of this pixel. This is a quite powerful command, making it possible to imitate the color tonality of another picture.

Now this is all good. But I realized that there are some problems with this approach.

The problem is that geometry and the colors draw numbers from the same random number generator (the C-standard library ‘rand()’ function).

This means that changing the color scheme changes the geometry (since the color schemes use a different number of random numbers for each color – randomhue uses 1 random number per color, the image sampling uses two (X and Y) random numbers per color, the randomrgb uses three).

This is not acceptable, since you’ll want to change the color schemes without changing the geometry. Another problem is that C-standard library ‘rand’ function is not platform independent – so even if you specify a EisenScript together with an initial random seed, you will not get the same structure on different platforms.

I solved this by implementing new random generators in Structure Synth. I now use two independent Mersenne Twister random number generators, so that I have two random streams – one for geometry and one for colors.

Communications of the ACM

I did the cover for the April issue of Communications of the ACM and a few illustrations inside as well.

CACM Readers: for more Structure Synth pictures see either my personal Flickr account or the public Structure Synth pool. If you want to try out the program for youself, it is freely available from SourceForge.

The structures were created in Structure Synth, and raytraced in SunFlow in high resolution (the largest picture was 6000×6000 pixels).

I was about to leave for Japan, when I was asked to make the cover image, so I had a very tight deadline. Despite this, the actual work process went fine, thanks to clear artistic guidance from the graphical editor (Alicia Kubista from Andrij Borys Associates).

By the way, even though the cover notes state that I’m a computer scientist, and even though I’ve worked professionally with software development for the last eight years or so, I am a physicist. Really.

Structure Synth 0.9 Released

I’ve released a new version: Structure Synth v0.9.0 (“Glasnost”).

Binaries for Windows XP and Vista. Source for Linux and Mac. (Mac binary will be available shortly)

New features:

• Template renderers: camera export is now working.
• Implemented a ‘Triangle’ primitive. E.g.: ‘Triangle[0,0,0;1,0,0;0.5,0.5,0.5]‘ is now a valid primitive.
• Added support for ‘#define varname value’ preprocessor substitutions (useful for declaring constant variables).
• A RenderMan template (created by Tom Beddard/Subblue) has been added.

Minor changes and bug fixes:

• Added ‘FastRotate’ button (draws a subset while rotating/translating the view).
• Template Renderer: Missing primitives no longer cancels the renderer, but only warns.
• OpenGL renderer now turns off GLWidget when rendering (makes build phase faster).
• Fixed CR+CR+LF export bug.
• Enabled the Cut,Paste,Copy main menu.
• Removed an extensive memory leak (leaked 16 bytes per created state).
• When resizing the OpenGL window, width/height/aspect ratio is shown.
• Corrected some syntax highlighter bugs.
• Fixed a bug when going into full screen mode (not all chrome was hidden).

Note: the camera export is only implemented for the SunFlow templates (but you can apply the same techniques to all other templates). For PovRay you would probably need to change the coordinate system from a left-handed to a right-handed one (I believe you can do this in the scene description file).

Grammars for Generative Art (Part II)

As discussed in the previous part, formal grammars can be used to generate and manipulate text strings.

The question is how this can be extended to generate pictures, movies, or music.

One possibility would be to interpret the symbolic output as some sort of representation or encoding, which could be unfolded to create the final output.

For instance it would be rather simple to create a grammar, which created an SVG XML file for output. A wide used example of this approach is Lindenmayer systems, where the output is interpreted as a sort of ‘LOGO Turtle Graphics’.

Lindenmayer Systems

Lindenmayer Systems (or simply L-systems) are related to formal grammars, but in contrast to formal grammars which describe the syntax for the infinite number of sentences for a formal language, L-systems describe a generational process for manipulating text strings. They were used by Lindenmayer to simulate plant and tree growth.

In L-systems you iteratively apply all the production rules to the output of the previous iteration. L-systems do not have terminal symbols in the same sense as formal grammars do – so the expansion never stops. L-systems may, however, have optional constants which are not replaced and in this sense acts a bit like terminal symbols. In contrast to formal grammars, L-systems are not expected to terminate with a string of constants, they will keep on ‘growing’. Since the expansion never stops, L-systems are usually calculated for a given number of generations.

An example L-system:
 A-> B-A-B B-> A+B+A 

Starting with the symbol ‘A’, this system would yield the following expansion: A, B-A-B, A+B+A-B-A-B-A+B+A, …., and so forth. Notice the difference to formal grammars: if these were production rules in a formal grammar, ‘B-B-A-B-B’ would be a valid sentence: this is not the case for L-systems, since all rules must be applied at each step.

The way L-system traditionally are used for generative purposes is by applying geometric semantics to the output: for instance, we could interpret A and B as moving one step forward, and + and – as turning 60 degrees clockwise or counter-clockwise. With this interpretation we get the following output:

- a fractal Koch curve.

‘The Algorithmic Beauty of Plants’ by Prusinkiewicz and Lindenmayer describes L-systems in details and is now available for free at Algorithmic Botany.

At this point I must admit that I always found L-systems to be quite dull and boring. Usually texts about L-systems are accompanied by Koch or Dragon curves and one or more simple plant or tree structure. However recently I stumbled upon this site: L-systems in Architecture by architect Michael Hansmeyer. Some of his creations are stunning, and the presentation is excellent, complete with step-by-step animations.

(Example image from L-Systems in Architecture.)

Context Free Design Grammar

In L-systems the symbol generation and the geometrical interpretation are two independent steps.

A perhaps more interesting approach is to embed the geometry inside the production rules. This requires a slight extension to the formal grammars.

Chris Coyne created the Context Free Design Grammar, which just like a formal grammar has production rules and non-terminal and terminal symbols – though it only has three terminal symbols: the ‘circle’, ‘square’ and ‘triangle’ geometrical primitives.

The Context Free Design Grammar extends the syntax of the formal grammars by including transformation operators (which are called ‘adjustments’ in CFDG terms). These transformation operators modify the current rendering state. Notice that while (rendering) states are being introduced in the CFDG, the actual expansion of a non-terminal symbol is still context-free. The CFDG also allows different weights to be assigned to each production rules.

Mark Lentczner and John Horigan created a cross-platform (Windows/Mac/Linux) graphical front-end simply called Context Free for CFDG. It is a wonderful little application – it is very easy to use and play around with.

Here is an example of CFDG code:

startshape SEED1

rule SEED1 {
SQUARE{}
SEED1 {y 1.2 size 0.99 rotate 1.5 brightness 0.009}
}

rule SEED1 0.04 {
SQUARE{}
SEED1 {y 1.2 s 0.9 r 1.5 flip 90}
SEED1 {y 1.2 x 1.2 s 0.8 r -60}
SEED1 {y 1.2 x -1.2 s 0.6 r 60  flip 90}
}


yielding the following output:

EisenScript and Structure Synth.

After I discovered Context Free I decided that I wanted to create a similar program for 3D geometry, a project that turned into the Structure Synth application.

In order to describe a grammar for 3D modelling I had to alter the CDFG syntax a little, which resulted in the EisenScript used in Structure Synth (named after the Russian film director Sergei Eisenstein).

I deliberately chose a new name, since I was not sure that the EisenScript was going to be a context free grammar – being slightly more pragmatic, I wanted to sacrifice the purity of CDFG for having more control over the graphical output. In particular, I added the possibility of ‘retiring’ rules: after a rule has reached a certain recursive depth, it can either be terminated or substituted by a new rule. (Actually I am a little in doubt, whether this ‘retiring’ is just a form of shorthand notation for specifying something which would be possible to express in a context free grammar). This ‘retiring’ rule makes it possible to create structure like a Menger sponge.

Also a few other alterations of CFDG were made:

The ‘startrule’ statement: in CFDG startrules are explicitly specified. In EisenScript, a more generic approach is used: statements which can be used in a rule definition, can also be used at the top-level scope. What actually happens is that Structure Synth collects everything at the top-level scope and creates an implicit start rule.

Termination criteria: in CFDG recursion automatically terminates when the objects produced are too small to be visible. This is a very elegant solution, but it is not easy to do in a dynamic 3D world, where the user can move and zoom with the camera. Several options exist in Structure Synth for terminating the rendering.

Transformation order: in CFDG transformations (which CFDG refers to as adjustments) in curly brackets are not applied in the order of appearance, and if multiple transformations of the same type are applied, only the last one is actually carried out. For transformations in square brackets in CFDG the order on the other hand is significant. In Structure Synth the transformation order is always significant and no transformations are omitted: transformations are applied starting from the right-most one. Also in CFDG the transformation are specified after the rule call, in EisenScript they must appear before the rule call.

An EisenScript program similar to the one above would look like this:

EisenScript example (click to enlarge)

Of course there are also other obvious differences between CFDG and EisenScript: the transformation rules were altered to new 3D equivalents, and a new set of primitives were chosen. (Take a look at the EisenScript Reference for more details.).

Differences to procedural programming

An EisenScript grammar like the one above looks a lot like a ‘normal’ computer program – the syntax is actually quite close to the syntax of procedural programming languages like C, Java, Pascal, or Basic. And instead of thinking of EisenScript as a grammar and its output as sentences in the language specified by this grammar, it is perhaps easier to think of EisenScript as an ordinary computer language.

The similarities may be a bit deceptive though, since there are two major differences: functions (which are the rules in EisenScript) may have multiple definitions each with a arbitrary weight. And recursion is handled ‘breadth first’.

The last point requires an explanation: Whenever a procedural programming language executes a function or procedure, it does so in sequential order – the individual statements in the function are executed in the order of appearance. If one of the statements is a procedure call, this procedure is executed and must be completed before the next statement is executed. The state of the currently executing function (the return address pointer, local variables, …) are stored in stack frames on a call stack, in order to be able to return after executing a function. Put differently, this means the function call tree for the program is traversed ‘depth-first’.

Recursion in Structure Synth is handled differently. Instead of a call stack, there is generational stack: whenever a rule is encountered, all sub rules and primitives in the rule definition are pushed onto a new stack that will be evaluated at the next generation. This means the rules are traversed ‘breadth first’ – all calls at the same recursive depth are processed at the same time.

Consider the following example:
 Procedure recurse() { recurse(); // call myself another(); // call another function } 

A traditional programming language would never reach the ‘another()’ function. It would recurse until the call stack overflowed. In contrast, In Structure Synth the first generation would process both the ‘recurse’ and ‘another’ statement. (When processing the ‘recurse’ statement it would schedule new ‘recurse’ and ‘another’ calls for the next generation).

Well, this concludes part II.

Part III will describe other grammar approaches to generative art and procedural modelling: namely Style Grammars and Shape Grammars.

Grammars for Generative Art (Part I)

For some time, I’ve wanted to write about the origins of Structure Synth – in particular Context Free and the design grammar approach.

Formal Grammars

The structure of both ordinary languages and computer languages have been studied for quite some time.

Formal grammars provide a way to exactly describe the structure of all valid sentences for a language. A formal grammar consists of production rules which describe valid transformations of symbol sequences. For instance a production rule might state that an English sentence consists of either a ‘Simple Sentence’ of a ‘Compound Sentence’.

Of course we cannot stop here – ‘Simple sentence’ is not a terminal symbol – it needs to be replaced and broken down into one or more terminal symbols. The terminal symbols in English would be the actual English words, while the non-terminal symbols would be structural placeholders such as ‘Simple sentence’ or ‘Verb phrase’.

Here is an example for an incomplete grammar for the English language:

 [English Sentence] = [Simple Sentence] | [Compound Sentence] [Simple Sentence] = [Declarative Sentence] | [Interrogative Sentence] | [Imperative Sentence] | [Conditional Sentence] [Declarative Sentence] = [subject] [predicate] [subject] = [simple subject] | [compound subject] [simple subject] = [noun phrase] | [nominative personal pronoun] [nominative personal pronoun] = "I" | "you" | "he" | "she" | "it" | "we" | "they" [predicate] = ([verb] | [verb phrase]) [complement] [verb] = [linking verb] | ... [linking verb] = "am" |"are" |"is" | "was"| "were" | .... 

The rules above are only a tiny fragment (see more here).

Generating output

While formal grammars are perhaps mostly used in Computer Science for parsing and checking the syntax of computer languages, they have interesting applications in other domains. For instance, it is possible to create a formal grammar for a specific domain of a natural language, and then use the grammar to generate random sentences:

SCIgen is an example of a generator, which builds random computer science papers. As can be seen from the example above it is not difficult to generate a valid sentence if the formal grammar is at hand – just pick your start symbol (e.g. ‘English Sentence’) and choose at random one of the possible substitutions. Continue doing this until only terminal symbol are left.

SCIgen actually managed to get one of its generated papers accepted at the WMSCI 2005 conference. Here is a fragment of the grammar used:

 EVAL_ANALYZE_ONE = note the heavy tail on the CDF in EXP_FIG, exhibiting DIFFERENT EVAL_MEASUREMENT EVAL_ANALYZE_ONE = the many discontinuities in the graphs point to DIFFERENT EVAL_MEASUREMENT introduced with our hardware upgrades EVAL_ANALYZE_ONE = bugs in our system caused the unstable behavior throughout the experiments EVAL_ANALYZE_ONE = Gaussian electromagnetic disturbances in our EXP_WHERE caused unstable experimental results EVAL_ANALYZE_ONE = operator error alone cannot account for these results 

Here the upper cased words are the non-terminals, which are to be substituted. The complete grammar (with ~3000 production rules) can be found here: scirules.in. Also more respectable institutions have accepted SCIgen papers – in 2007 the Elsevier journal ‘Applied Mathematics and Computation’ accepted this article (now removed – but read more about this at the SCIgen blog).

Another spectacular (and funny) example of grammar generated text is the Postmodernism generator (based on the Dada Engine). It creates postmodernistic ramblings that would have made Alan Sokal proud!

Context Free Grammars

In the fifties Noam Chomsky categorized the formal grammars into four classes.

This classification can be understood in terms of how the productions rules look: For instance, for the third class – the socalled Context Free Grammars – the left hand side of the production rule is always a single non-terminal symbol (this is also the case for the natural language examples above). This means, that it is possible to apply the production rule no matter where the given non-terminal symbol is placed – the production rule is not dependent on the context of the symbol.

While formal grammars have interesting applications in computer science and natural language research, they are merely tools for analyzing or generating symbol sequences. In Part II I’ll describe the Context Free Design Grammar used in Context Free, and its relation to the EisenScript used in Structure Synth.

In The Blogs

In the past week Structure Synth was first mentioned on Dataisnature (strongly recommended, btw), and from here quickly found its way to Wired Blogs, the MAKE: Blog, and at least five other blogs, generating some 60K hits on the SourceForge pages.

Subblue’s Box pyramid was featured on most blog entries.

I’m really delighted to see Structure Synth getting some attention – hopefully I’ll soon be able to put some time into the further development.

Using Templates in Structure Synth

Although it is possible to use Structure Synth together with third party renderers (such as PovRay, SunFlow and Blender), it requires some… ingenuity.

The template rendering system offers a flexible way to export structures, but as of now the system is not completed and not documented at all. This mini tutorial offers an introduction for early (and adventurous) adopters.

For the tutorial, the following EisenScript may be used:
Nabla.es

Rendering the EisenScript as OpenGL inside Structure Synth results in something like the following:

Not very exciting.

Now, choose ‘Template Render to File… | sunflow.rendertemplate’ and save the resulting text-file as something with an ‘*.sc’ extension (A SunFlow scene description file) – for instance ‘Nabla.sc’.

Start SunFlow, choose ‘Open File’ and import the ‘*.sc’ scene file.

Next, by clicking ‘Render’ a nicely raytraced version of the image should emerge:

A few important points: as of now the camera settings are not exported, so in most cases it is necessary to modify the SunFlow scene file by hand. I’m working on this. Meanwhile, in the scene file look for the following code block:

camera {
type pinhole
eye    3.27743673325 -9.07978439331 9.93055152893
target 0 0 0
up     0 0 1
fov    40
aspect 1
}


For higher resolution images, modify the following lines to the desired resolution:

image {
resolution 500 500
aa 1 2
}


Structure Synth in VVVV

It is always fun to see Structure Synth used in various contexts, so I am happy to see that Julien (Vux) has created a Structure Synth plugin for vvvv. It is a .NET (C#) Assembly wrapping the original C++ Structure Synth code. The license turned out to be a bit tricky, though:

Structure Synth is a GPL licensed application.

This is something I cannot change, because Structure Synth is based on Qt Open Source Edition which requires that the application is GPL’ed.

vvvv on the other hand is a closed source application. The question is whether a closed source application may use an GPL’ed plugin. It turns out that this is a bit fuzzy in the GPL, but as I read the license, an isolated plugin which provides no vital functionality to vvvv should be okay.