User's Manual - Grow


A Topiary Modeling Program


Introduction

Grow is a program for creating synthetic topiary.
It is a batch program and the input files needed by it are divided into categories:
  1. Plant class file: a file for describing the 'biology' of a plant (L-System definition, leaf definition).
  2. Plant attributes file: a file describing some plant parameters (colors, number of generations, drawing parameters etc.).
  3. Irit file: a file containing a surrounding object by which to prune by and the location and direction of 'seeds' from which plants will grow.
These files are used when executing Grow.

Grow is based on the paper 'Synthetic Topiary' and was written by Erez Louidor, Adi Izkovitch and Ido Tal as a project for the Intelligent Systems Lab and was supervised by Dr. Gershon Elber


Environmentally Sensitive L-Systems

This project relies heavily on environmentally sensitive L-Systems. You can define your own L-Systems or use the L-Systems supplied in the examples to grow topiary plants in your objects. Click here if you want to skip the L-System theory and explanataions part.
In order to define environmentally sensitive L-System we will first define general L-Systems.

General L-Systems

An L-System is defined by an initial word called the axiom and by rewriting rules or productions. We start with the axiom as our current word and use the productions to obtain a new word which becomes the (new) current word. Every word is a sequence of modules, and the new word is created by placing successor modules instead of predecessor ones. A module which has no valid productions is copied as is to the next word. We continue this process iteratively a number of times.

In Our Program

The axiom represents the plant as a seed and every iteration causes the plant to grow by a time step. You can however interpret the words in another way, for example as fractals.

Simple L-Systems

To make the concept of an L-System more concrete let's look at a simple example (this example is taken from the book "The algorithmic beauty of plants" by Prusinkiewicz & Lindenmayer):

w: b;
p1: a -> a b;
p2: b -> a;

The rule which has w as its identifier is the axiom and p1 and p2 are the production rules. By these rules the current word of step i is:

  1. b
  2. a
  3. ab
  4. aba
  5. abaab
  6. abaababa
Notice that the productions are "applied in parallel" (unlike regular context free grammars), that is, a production influences the next word and not the current word. The above L-System consists of modules (a and b) which have no parameters (no stored numerical info).

In Our Program

As a principle, everything in our program is case sensitive and in particular the module names (that is, A differs from a). A module name must begin with a letter or an underscore, and may continue with a sequence of letters, underscores or digits (like c identifiers). These rules apply to all identifiers in the L-System.

We should point out that our program works with parametric L-Systems and a module with zero parameters is represented as the module name followed by () (for example a()) in contrast with our first example. This is necessary in order to avoid the ambiguity that arises when allowing modules with multiple letters names (otherwise for example ab can be interpreted as 2 modules named a and b or one module named ab).

The axiom is always the first rule.

A rule's identifier is syntactically like a module name, and is optional as it isn't being used in any way in our program. It is applied however in all of our examples to improve the readability.

At the end of every rule (or axiom) a semicolon (;) sign must appear. To denote an epsilon successor, simply put that sign after the -> (for example: S()->;).

C-style comments are allowed everywhere (/* comment example */). New lines, tabs and blanks are ignored.

Parametric L-Systems

In parametric L-Systems the modules may have parameters attached to them which are represented in the form: module(parameter1, parameter2, ..., paramaterN).

We can extend the above example to be a parametric L-System, for example:

w: b(1);
p1: a(x) -> a(x+2) b(x+0.5);
p2: b(x) -> a(x+1);

By these rules the current word of step i is:

  1. b(1)
  2. a(2)
  3. a(4)b(2.5)
  4. a(6)b(4.5)a(3.5)
  5. a(8)b(6.5)a(5.5)a(5.5)b(4)
  6. a(10)b(8.5)a(7.5)a(7.5)b(6)a(7.5)b(6)a(5)
We can further generalize the concept of L-Systems to include context matching, conditions and probabilities.

In Our Program

The parameters of a module in the predecessor side of a rule are local variable names that are created 'on the fly'. The actual value of the parameters is filled when deriving the words and applying that rule. The variables may be used in other relevant rule parts.
In the successor, each parameter may be a real numbers' expression. An expression is a combination of real numbers (in regular or scientific representation), variable names and built-in operators and functions.
The arity (number of parameters) of every module is determined the first time it is introduced (or is predefined for built-in modules). In any case of arity mismatch, the parser will print an error message.

Context Matching

In addition to the predecessor module (the module which was on the left side of the arrow in the previous examples) we can optionally define a production to have a left and/or right context. A general production would be: label: lc < pred > rc -> succ; where lc and rc are the left and right contexts respectively, pred is the predecessor module, succ the successor modules and label is the production label (optional both for the production and the axiom). A production would be considered valid for a given module if pred would match (that is, be the same type as) that module and the modules to the left and to the right of pred would match lc and rc respectively. Let's illustrate this by an example:

If the current word is: a(5) b(3) a(7) b(6) b(5) then the production b(x) < a(y) > b(z) b(k) -> b(x+y-k); would be valid for the third module a(7) but would be invalid for other modules, specifically the first module a(5) because at least one context doesn't match (in fact both don't). We can also define an ignore list which tells the program to ignore certain modules when matching contexts, for example: the production a(x) > a(y) -> a(x+y) is invalid for the first module a(5) in the above example, if the ignore list is empty. If the ignore list includes module b, the production becomes valid.

In Our Program

The ignore list is optional and is written as the command:
#ignore moduleName1, ..., moduleNameN;
This command must be placed after the L-Systems rules.
Like in the predecessor, modules in the contexts must have variable names as their parameters (if any). Variables declared in the contexts may be used in expression in the rest of the rule.

Condition

To the above definition we can also add a condition which has to be met in order for the production to be considered valid. A general production would be: label: lc < pred > rc : cond -> succ; where cond is the condition. For example: p1: a(x) : x<5 -> b(1.1*x); is valid for a(1) but not for a(7).

In Our Program

The condition is considered true if the exression's result is not 0.0.
The case where several rules match a certain module is generalized in the Probability section.

Probability

For some modules more than one production might be a valid production. We allow a production to have a probability so that if this occurs we will pick at random a production according to its probability. A probability should be a non-negative real and can be a function of the parameters. The sum of probabilities of all the valid productions must be a positive real (not necessarily equal to 1, we normalize the probabilities). If the probability is not supplied it is taken to be 1. An example of productions utilizing probabilities is:

p1: a(x) -> a(x+1) : 1/x;
p2: a(x) -> a(x-1): 1-1/x;

To sum up, the most general production has the form:

 
label: lc < pred > rc : cond -> succ :prob;
 
(where pred and succ are the only mandatory fields).

Environmentally Sensitive L-Systems

In addition to being an L-System an environmentally sensitive L-System has special modules. These modules influence a 3-D "logo style" turtle at derivation time. The turtle is defined by 3 mutually perpendicular unit vectors: H, L, U (the letters stand for Heading, Left and Up, respectively). The special modules are the following: Most of the above modules are rather obvious and self explanatory, the ones which are not are:
% (Prune)
Prune removes all modules beginning with the current % and ending one module to the left of the ] ending the branch which % belongs to. As an example consider [a(1)b(2)%a(7)[a(5)a(6)]a(3)] after the prune symbol is executed we will be left with [a(1)b(2)]. If % belongs to no branch then the current % and all modules to the right of it are removed (as though there is a virtual [ at the start of the word and a virtual ] at the end of it). The prune symbols are executed after the productions leading to the next word have been executed.
[ and ] (Push and Pop)
[ and ] have special rules in respect to context matching.
Right Context Matching
Suppose the current word is a(1)[b(2)b(3)]c(3) and we are given productions:

p1: a(x) > b(y) -> d(x+y);
p2: a(x) > c(y) -> e(x+y);

In this case both productions are valid for the first module a(1). The logic for this is as follows:

For p1: we start out at a(1) and push the turtle's state onto the stack (the pushing action does not change the turtle's state so we ignore it) the next module the turtle encounters is b(2) so a(x) > b(y) is a good matching.

For p2: we start out at a(1) and push the turtle's state onto the stack, next we encounter all sorts of modules (b(2) and b(3)) and after them we pop the turtles state off the stack. At this point the turtle "remembers" only encountering a(1) and we proceed to c(3). At this stage the turtle "remembers" a(1) and c(3) so a(x) > c(y) is a good matching.

More formally: when trying to find a right context match and faced with a [ we can either continue looking to the right of it or jump to its matching ] and look to the right of it.

Left Context Matching
Suppose the current word is b(1)[c(2)c(3)]a(1) and we are given productions:

p1: c(x) < a(y) -> e(x);

p2: b(x) < a(y) -> a(x);

p2 is a valid production for a(1) for the same reasons that p2 of the previous example was a valid production. p1 is not a valid production because after c(3) we pop so the turtle "forgets" c(3).

More formally: when trying to find a left context match (moving from right to left) and faced with a ] we proceed to the module to the left of the matching [.

Query Modules:
A query module like ?P(x,y,z), ?H(x,y,z) and such are written ?P(x,y,z) when they are to the left of the arrow (a(x) ?P(x,y,z) : inside(x,y,z) -> a(x+1);). On the other hand, they are written as ?P(*,*,*) when they are to the right of the arrow (a(x) -> ?P(*,*,*); ). 

Plant Class File

The plant class file defines key features of a plant it includes (in this order):

The Plant Attributes File

This file lets the user define parameters regarding the plant. There are built in system defaults (if some attributes are missing or an attributes file is not specified). The syntax for defining a parameter is:
parameter_name= value;

Below is a list of parameters:


The Irit File

The Irit file is used to contain the following objects:

The Bounding Object

An Irit object which is the bounding object or part of it. Several such objects can be defined in the file or in several files. The bounding object the program will use is the boolean OR of all the bounding objects defined. The object must be a polygonal Irit object.

The Seeds

Seeds from which plants will grow. You may use our Irit functions to create seeds, or make them directly yourself (as an Irit script or data file). A seed object is represented as follows:

The Irit object type is string and the value of the string is "SEED". This object has several attributes:
 
Attribute Name  Attribute Type  Description  Optional 
vector  initial turtle H vector  no 
vector  initial turtle L vector  no 
vector  initial turtle U vector  no 
point  initial turtle position  no 
CLASS_FILENAME  string  L-System class file name  no 
PARAMETERS_FILENAME  string  name of overriding parameters file name  yes 


Executing Grow

After all these files are ready type from the command line:

grow 'List of Irit input files' 'Name of Irit output file'

Both .dat and .bdt Irit formats are supported.
An example:

grow dino.bdt seeds.dat dino-tree.bdt

Will read the binary Irit file dino.bdt and the ASCII Irit file seeds.dat and will write the result to dino-tree.bdt.