September 18, 2009 at 02:09L-Systems - the mathematical beauty of plants
The beauty of plants has attracted the attention of mathematicians for centuries. The most interesting studied geometric properties of plants, such as the symmetry of leaves relative to the central axis, the radial symmetry of flowers, and the spiral arrangement of seeds in cones. “Beauty is related to symmetry” (H. Weyl. Symmetry). During the growth of living organisms, especially plants, regularly repeating multicellular structures can be clearly seen. In the case of compound leaves, for example, small leaves that are part of a large adult leaf have the same shape as the entire leaf had at an early stage of formation.
In 1968 Hungarian biologist and botanist Aristid Lindenmayer proposed a mathematical model to study the development of simple multicellular organisms, which was later expanded and used to model complex branching structures - various trees and flowers. This model is called the Lindenmayer System, or simply the L-System.
For those who are in the subject and do not want to read the whole story, scroll down, there is a question.
I will shorten the L-System to L in the text.
The main idea of L is the constant rewriting of line items. What is it about? In short, rewriting is a way of getting complex objects by replacing parts of a simple initial object according to some rules. A classic example is a snowflake. In the figure, initiator is the initial object whose faces are replaced with generator. Next, the same thing is done with the new object. In this case, the usual fractal.
Returning to L and drawing an analogy with fractals, we can say that L operates with a string of characters according to special rules, starting with the initial simple axiom. People familiar with the concept of grammar will immediately notice that in fact L is. But the fundamental difference between L and formal grammarsconsists in the fact that the rules apply simultaneously to the entire line, to each character, plus, there are no concepts of terminal and non-terminal characters. That is, the "conclusion" on this grammar can go on indefinitely. The simultaneous application of the rules very quickly becomes clear when you consider where this model came from. In biology, every cell grows, divides and develops in parallel in time. The following picture shows the relationship between context-free (OL), context-sensitive (IL) L and other formal grammars in the Chomsky hierarchy .
Also, as in the Chomsky classification, L have their own classification from simple to complex and powerful.
The simplest example is deterministic context-free L or abbreviated DOL. I don't like formal grammar definitions, so I’ll just say it in my own words. There is a certain set of characters - the alphabet. This alphabet records the line that L. works with. There is an axiom - an initial string of one or more letters and a set of rules of the form a → ab. During each iteration of the algorithm, applying a rule to a letter from the current line, it (letter) is replaced by the set of letters to the right of the arrow. It is easier to consider a concrete example of the development of the multicellular organism Anabaena catenula, which Lindenmeyer studied when he proposed the Model L.
Let our alphabet consist of the following characters, each of which designates a certain cell: a l a r b l b r .
Axiom consists of one character.
ω: a r
And 4 rules.
p1: a r → a l b r
p2: a l → b l a r
p3: b r → a r
p4: b l → a l
Rules say which symbols change to which in the process of organism growth. The picture shows how, by applying the rules, we observe the "division" of cells and development.
So far we have seen how to draw a one-dimensional bacterium, but with the help of the well-known children's programming language LOGO , which proposes to control the turtle and draw figures on the screen, it will be possible to draw two-dimensional and three-dimensional fractals and repeating structures. How? Everything is simple. We take an alphabet in which each symbol means a command for a two-dimensional or three-dimensional turtle:
These commands use the default values of the rotation angle δ, step lengths, and basic vectors of two-dimensional and three-dimensional space. Examples of two-dimensional fractals and L generating them can be seen in the following picture.
Everything that was before this is, in general, continuous curves. Of course, in this way it is very difficult to model plants with their branching topology. To do this, the symbols [and] were added to the alphabet, which indicate the beginning and end of the branch, respectively. When the turtle meets the symbol [, its current state is written onto the stack and pulled out from there when the symbol meets].
Already with such a simple grammar you can generate quite interesting two-dimensional and three-dimensional objects similar to trees.
Of course, science did not stand still, and now we have a solid hierarchy of L starting with the simple DOLs discussed earlier.
Stochastic L.
Stochastic L. add the ability to specify the probability of the execution of a rule, and in the general case are not deterministic, because different rules can have the same symbol on the left. This introduces some element of randomness into the resulting structures.
Context-
sensitive L. As well as context-dependent in formal grammars, in L the syntax of rules is complicated and takes into account the environment of the replaced character.
Parametric L.
A variable parameter (possibly more than one) is added to each symbol, which allows, for example, specifying the angle of rotation for + and -, step length and line thickness, checking the conditions for applying the rule, counting the number of iterations and transmitting “signals” back and forth. An example of a parametric L. Parametric context-sensitive L allow you to simulate the growth of multicellular organisms and plants, taking into account biochemical processes and the environment. For example, our old friend Anabaena catenula in a more complex form. An example from the book [1]. As written in the book, this bacterium consists of two types of cells: vegetative cells and heterocysts
. Typically, vegetative cells are divided into two similar vegetative cells. However, in some cases, vegetative cells turn into heterocysts. Their distribution follows a well-observed pattern in which neighboring heterocysts are separated by approximately the same number of vegetative cells. But how does the body maintain a constant distance between heterocysts during growth? The proposed model describes this phenomenon in terms of biology. It is assumed that the arrangement of heterocysts is regulated by nitrogen compounds produced by these cells, which are transmitted to other cells of the body and consumed in vegetative cells. If the content of these compounds in a young vegetative cell falls below a certain level, this cell turns into a heterocyst.
The L-System below simulates bacterial growth based on the foregoing.
#define assigns values to the constants used in L.
#include loads a heterocyst form, in this case a circle.
Cells are represented by the F (s, t, c) module, where s is the cell length, t is the cell type (0 is heterocyst, 1 and 2 are vegetative cells), and c is the nitrogen concentration.
Here, for example, the recent hypodermic that conquered the Internet is essentially a combination of the simplest L.
This is just a superficial description of the theory and small examples of practical application. What awaits a curious researcher next?
Back in the late 80s, L was used to visualize plant models. Now the capabilities of computers have gone far ahead. Many games and 3d modeling tools use procedural content generation, including L-Systems. As you can see, from a set of simple rules you can get a huge number of different plants and plant whole fields with them.
Of the editors, I myself use L in Houdini , I heard that there are plugins for other packages as well. The so-called Virtual Laboratory allows you to experiment and animate L. The
methods of using grammars are also used in the so-called Shape Grammars , but more on that later.
Some posts on the Internet.
http://avalter.blogspot.com/2009/08/2d-l.html
Generally speaking, the only book available is The Algorithmic Beauty of Plants . Also, old random articles are scattered on the Internet. More or less new ones can be found on springerlink.com for a ton of money or in the institute library for free.
What can I say, the material is not enough.
I myself have absolutely nothing to do with biology, but I am a Master of Mathematics with some innocent hobbies. But I really like the idea of L-Systems. Simplicity with great features. Once upon a time I thought about how DNA contains complete information about me. How can one cram all the information about all cells into each cell? But in any way, one can say that L theory opened my eyes! It’s not written in my DNA what I look like, but how to assemble me (in general terms). Something similar to the rule set in L, only related to protein synthesis.
A simple model so clearly describes our life with you.
Further more - we turn the rules into “DNA” and we grow virtual multicellular ones using the genetic algorithm.
I would like to find people who are also interested in the scientific component of L, share materials and articles. It just so happened that I am currently working on an upgraded L-Systems concept, but I am not able to review what has been written on this topic over the past five years. I do not want to reinvent the wheel.
It was not possible to contact the author of the BOOK, the answering machine says that he left for the coven before January (8
Also, I am looking for information on Shape Grammars for 3d modeling. There is a task to generate spaceships from the parameters, you know such huge gizmos with a bunch of small details are ideal Candidates for SG: Will you really have to write a Houdini plugin in Python?
In 1968 Hungarian biologist and botanist Aristid Lindenmayer proposed a mathematical model to study the development of simple multicellular organisms, which was later expanded and used to model complex branching structures - various trees and flowers. This model is called the Lindenmayer System, or simply the L-System.
For those who are in the subject and do not want to read the whole story, scroll down, there is a question.
I will shorten the L-System to L in the text.
Rewriting.
The main idea of L is the constant rewriting of line items. What is it about? In short, rewriting is a way of getting complex objects by replacing parts of a simple initial object according to some rules. A classic example is a snowflake. In the figure, initiator is the initial object whose faces are replaced with generator. Next, the same thing is done with the new object. In this case, the usual fractal.
Returning to L and drawing an analogy with fractals, we can say that L operates with a string of characters according to special rules, starting with the initial simple axiom. People familiar with the concept of grammar will immediately notice that in fact L is. But the fundamental difference between L and formal grammarsconsists in the fact that the rules apply simultaneously to the entire line, to each character, plus, there are no concepts of terminal and non-terminal characters. That is, the "conclusion" on this grammar can go on indefinitely. The simultaneous application of the rules very quickly becomes clear when you consider where this model came from. In biology, every cell grows, divides and develops in parallel in time. The following picture shows the relationship between context-free (OL), context-sensitive (IL) L and other formal grammars in the Chomsky hierarchy .
The simplest L-Systems.
Also, as in the Chomsky classification, L have their own classification from simple to complex and powerful.
The simplest example is deterministic context-free L or abbreviated DOL. I don't like formal grammar definitions, so I’ll just say it in my own words. There is a certain set of characters - the alphabet. This alphabet records the line that L. works with. There is an axiom - an initial string of one or more letters and a set of rules of the form a → ab. During each iteration of the algorithm, applying a rule to a letter from the current line, it (letter) is replaced by the set of letters to the right of the arrow. It is easier to consider a concrete example of the development of the multicellular organism Anabaena catenula, which Lindenmeyer studied when he proposed the Model L.
Let our alphabet consist of the following characters, each of which designates a certain cell: a l a r b l b r .
Axiom consists of one character.
ω: a r
And 4 rules.
p1: a r → a l b r
p2: a l → b l a r
p3: b r → a r
p4: b l → a l
Rules say which symbols change to which in the process of organism growth. The picture shows how, by applying the rules, we observe the "division" of cells and development.
Turtle interpretation of strings.
So far we have seen how to draw a one-dimensional bacterium, but with the help of the well-known children's programming language LOGO , which proposes to control the turtle and draw figures on the screen, it will be possible to draw two-dimensional and three-dimensional fractals and repeating structures. How? Everything is simple. We take an alphabet in which each symbol means a command for a two-dimensional or three-dimensional turtle:
- F - move forward and draw a line
- f - move forward without drawing anything
- + - turn left
- - - turn right
- & - turn down
- ^ - turn up
- \ - lean to the left
- / - lean to the right
- | - turn around 180 degrees
These commands use the default values of the rotation angle δ, step lengths, and basic vectors of two-dimensional and three-dimensional space. Examples of two-dimensional fractals and L generating them can be seen in the following picture.
Plants and branching structures.
Everything that was before this is, in general, continuous curves. Of course, in this way it is very difficult to model plants with their branching topology. To do this, the symbols [and] were added to the alphabet, which indicate the beginning and end of the branch, respectively. When the turtle meets the symbol [, its current state is written onto the stack and pulled out from there when the symbol meets].
Already with such a simple grammar you can generate quite interesting two-dimensional and three-dimensional objects similar to trees.
More complex grammars.
Of course, science did not stand still, and now we have a solid hierarchy of L starting with the simple DOLs discussed earlier.
Stochastic L.
Stochastic L. add the ability to specify the probability of the execution of a rule, and in the general case are not deterministic, because different rules can have the same symbol on the left. This introduces some element of randomness into the resulting structures.
Context-
sensitive L. As well as context-dependent in formal grammars, in L the syntax of rules is complicated and takes into account the environment of the replaced character.
Parametric L.
A variable parameter (possibly more than one) is added to each symbol, which allows, for example, specifying the angle of rotation for + and -, step length and line thickness, checking the conditions for applying the rule, counting the number of iterations and transmitting “signals” back and forth. An example of a parametric L. Parametric context-sensitive L allow you to simulate the growth of multicellular organisms and plants, taking into account biochemical processes and the environment. For example, our old friend Anabaena catenula in a more complex form. An example from the book [1]. As written in the book, this bacterium consists of two types of cells: vegetative cells and heterocysts
ω : B(2)A(4, 4)
p1 : A(x, y) :y <= 3 → A(x ∗ 2, x + y)
p2 : A(x, y) :y > 3 → B(x)A(x/y, 0)
p3 : B(x) :x < 1 → C
p4 : B(x) :x >= 1 → B(x − 1). Typically, vegetative cells are divided into two similar vegetative cells. However, in some cases, vegetative cells turn into heterocysts. Their distribution follows a well-observed pattern in which neighboring heterocysts are separated by approximately the same number of vegetative cells. But how does the body maintain a constant distance between heterocysts during growth? The proposed model describes this phenomenon in terms of biology. It is assumed that the arrangement of heterocysts is regulated by nitrogen compounds produced by these cells, which are transmitted to other cells of the body and consumed in vegetative cells. If the content of these compounds in a young vegetative cell falls below a certain level, this cell turns into a heterocyst.
The L-System below simulates bacterial growth based on the foregoing.
#define assigns values to the constants used in L.
#include loads a heterocyst form, in this case a circle.
Cells are represented by the F (s, t, c) module, where s is the cell length, t is the cell type (0 is heterocyst, 1 and 2 are vegetative cells), and c is the nitrogen concentration.
#define CH 900 /* high concentration */
#define CT 0.4 /* concentration threshold */
#define ST 3.9 /* segment size threshold */
#include H /* heterocyst shape specification */
#ignore f ∼ H
ω : -(90)F(0,0,CH)F(4,1,CH)F(0,0,CH)
p1 : F(s,t,c) : t=1 & s>=6 → F(s/3*2,2,c)f(1)F(s/3,1,c)
p2 : F(s,t,c) : t=2 & s>=6 → F(s/3,2,c)f(1)F(s/3*2,1,c)
p3 : F(h,i,k) < F(s,t,c) > F(o,p,r) : s>ST|c>CT → F(s+.1,t,c+0.25*(k+r-3*c))
p4 : F(h,i,k) < F(s,t,c) > F(o,p,r) : !(s>ST|c>CT) → F(0,0,CH) ∼ H(1)
p5 : H(s) : s<3 → H(s*1.1)
Hypodermic.
Here, for example, the recent hypodermic that conquered the Internet is essentially a combination of the simplest L.
#define R 1.456
ω : A(1)
p1 : A(s) → F(s)[+A(s/R)][−A(s/R)]More advanced.
This is just a superficial description of the theory and small examples of practical application. What awaits a curious researcher next?
- Modeling the growth of two-dimensional and three-dimensional multicellular organisms
- Tree Growth Animation
- Environmental Impact Modeling
- Simulation of chemical and biological processes and growth functions
- L application for surface generation
- Other diverse use cases, including for modeling real estate and cities
Examples.
Using.
Back in the late 80s, L was used to visualize plant models. Now the capabilities of computers have gone far ahead. Many games and 3d modeling tools use procedural content generation, including L-Systems. As you can see, from a set of simple rules you can get a huge number of different plants and plant whole fields with them.
Of the editors, I myself use L in Houdini , I heard that there are plugins for other packages as well. The so-called Virtual Laboratory allows you to experiment and animate L. The
methods of using grammars are also used in the so-called Shape Grammars , but more on that later.
Some posts on the Internet.
http://avalter.blogspot.com/2009/08/2d-l.html
Books and additional material.
Generally speaking, the only book available is The Algorithmic Beauty of Plants . Also, old random articles are scattered on the Internet. More or less new ones can be found on springerlink.com for a ton of money or in the institute library for free.
What can I say, the material is not enough.
Near-biological thoughts.
I myself have absolutely nothing to do with biology, but I am a Master of Mathematics with some innocent hobbies. But I really like the idea of L-Systems. Simplicity with great features. Once upon a time I thought about how DNA contains complete information about me. How can one cram all the information about all cells into each cell? But in any way, one can say that L theory opened my eyes! It’s not written in my DNA what I look like, but how to assemble me (in general terms). Something similar to the rule set in L, only related to protein synthesis.
A simple model so clearly describes our life with you.
Further more - we turn the rules into “DNA” and we grow virtual multicellular ones using the genetic algorithm.
Scientific thoughts.
I would like to find people who are also interested in the scientific component of L, share materials and articles. It just so happened that I am currently working on an upgraded L-Systems concept, but I am not able to review what has been written on this topic over the past five years. I do not want to reinvent the wheel.
It was not possible to contact the author of the BOOK, the answering machine says that he left for the coven before January (8
Also, I am looking for information on Shape Grammars for 3d modeling. There is a task to generate spaceships from the parameters, you know such huge gizmos with a bunch of small details are ideal Candidates for SG: Will you really have to write a Houdini plugin in Python?