Sunday, September 27, 2009

Algorithmic Botany

Plants have proven to be fertile ground for modeling morphogenesis. Much of the pioneering work was carried by a professor of Computer Science at the University of Calgary named Przemyslaw Prusinkiewicz, and his many students and collaborators. Early in his career, Prusinkiewicz, who usually goes by the more English-friendly nickname Shemeck, teamed up with the Hungarian botanist Aristide Lindenmayer, who had invented the class of grammars known as L-systems to serve as a systematic language for describing plant shapes. If your only association with the concept of grammar relates to conjugating verbs, you should know that for linguists, and later for computer scientists, grammars are powerful, formal, quasi-mathematical systems for describing transformations of symbolic structures. In the 1950's the linguist Noam Chomsky had described a hierarchy of grammars of increasing complexity which he used to analyze the organization of sentences in human languages. If you think back to your grammar lessons, you will recall that sentence structures are represented by tree diagrams. Lindenmayer's insight was that grammars could describe the tree-structure of, well, trees, as well as bushes and other plants. A grammar works by applying rules that rewrite parts of a sentence. A simple rule for building a tree might be fork a branch. If you start with a single vertical branch (i.e., a trunk), and apply this rule to it, you will create a trunk with two branches -- a Y shape. If you now apply the rule to the branches you will have a trunk with two internal limbs, each carrying two branches. If you keep going, you will make a tree of progressively greater complexity.

Shemeck's innovation was to marry L-systems to computer graphics, which allowed computers to generate plant shapes. Here's an example, showing the computer-generated plant image, and below the symbolic representation of the grammar that it is based on.  Shemeck early computer graphic work was published in a book, the Algorithmic Beauty of Plants, that is a classic in the field of e-morphogenetics: perhaps its only coffee-table book to date. The book is now freely available in electronic form at Algorithmic Botany, the web site for Shemeck's lab, along with more recent images and publications. The web-site also has Quick-Time animations that show the temporal behavior of these models. Although at first the focus of the work was primarily on producing realistic plant graphics without much concern for biological realism, over time more biology was layered on: for example, plant hormones emmited in one part of the plant and sensed in another to trigger flowering. The modeling was mostly at the level of structural elements like leaves and branches, as opposed to cells or genes. However chapter 7 describes some explorations in the application of L-system graphics to 2 and 3-dimensional systems of cells; some examples are show below.

Others have gone on to apply L-systems for science and art, see for example Laurens Lapre's gallery; the sample below is called an airhorse. He has a program called LParser for experimenting with L-systems; it generates VRML output so you can zoom, pan, rotate, etc.

No comments:

Post a Comment