The LinF Specification

L-Systems are formal string rewriting systems introduced in 1968 by the botanist Aristid Lindenmayer that are used to model fractal images. LinF allows the definition of L-Systems that represent three-dimensional fractals and stochastic fractals.

LinF is a simple language used to describe 3D L-Systems to be interpreted according to the turtle method. A program in LinF is formed by six blocks, none of which are mandatory although it is not possible to generate fractals if some of them are missing. These six blocks are called angles, lines, blanks, axiom, rules and colors. There is no order in which the blocks should appear in a LinF program. A short description of each block is given next:

[axiom] Defines the axiom of the L-System. An axiom is the starting point from which the fractal will be generated.
[lines] Defines which symbols will represent lines in the production rules. When evaluating the production rules, the lines should be drawn.
[blanks] Defines which symbols will represent blanks or transparent lines in the context of a particular LinF program.
[angles] In this section we define the rotation angles that can appear in the fractal description. A rotation angle is constituted by two elements. The first component of a rotation specifies the angle of torsion and the second one specifies the curvature.
[rules] This module of a LinF program describes every production rule that forms the fractal. A production rule is formed by two parts: the left side and the right side. The left side is simply an identifier while the right side is an arbitrary sequence of expressions. As in Chomsky formalism, the grammar rules in LinF are constituted by terminal and non-terminal symbols. Every symbol that appears in the left side of a production rule is considered a non-terminal symbol. Some of the non-terminal symbols do not have any meaning for the fractal representation and are used just to facilitate the grammar specification.
[colors] In this section the fractal designer can specify a list of colors that will be used to draw the fractal. The list will be stored in order of specification within the LinF file. The first lines of the fractal will have the first color in the list. When the { symbol is encountered in the fractal string, the next color becomes the current one. If the symbol } is encountered, the previous color becomes active again. If a number of { exceeding the number of colors stored in the color list is found, then the last color recorded becomes the current color.

The LinF Interpreter

Before understanding how fractals are represented with the LinF formalism, it is worthwhile to comprehend the nature of a basic LinF interpreter. The LinF interpreter is a program that generates fractal figures based on the LinF description of the fractal structure. In this section will be described the structure of cFleo, a simple LinF interpreter developed in C, whose schematic view can be seem below:

The LinF interpreter can be divided into three main constituents: the parser, the evaluator and the rendering machine. The parser is responsible for recognizing the correctness of a LinF file and retrieving from it the meaning of the user-defined symbols, for instance, the name of lines, blanks and angles.

The next component of cFleo is the evaluator. This program is responsible for applying the production rules over the axiom of the fractal and then over the successive strings obtained by the application of the rules. A production rule is formed by two parts. The left side symbol and the right side sequence of symbols. To apply a rule over a string traditionally means to substitute every occurrence of its left side that appears on the string for its right side.

In addition to the simple scheme for defining rules, LinF permits the bounding of some rules to a probabilistic chance of occurrence. This means that during the string evaluation, some symbols which are the left side of a production rule may not be expanded. This pattern of evaluation allows the creation of stochastic L-Systems that are useful to model real entities such as rivers and plants.

The last constituent of cFleo is called the rendering machine. The rendering machine is responsible for displaying the fractal that is represented by a string. In order to implement this part of cFleo, it was used the OpenGL library. This machine has always a state that is represented by the tuple (position, frame, length, color). During the rendering process, the state is continuously being updated while the segments that constitutes the fractal are being drawn according to the state elements. The meaning of each one of the four state elements is described below:

[position] This element specifies a point in 3D space. The next line to be drawn will be displayed as a segment starting at this point.
[frame] This element is composed by a set of three orthonormal vectors t,n,b, whose meaning is explained here. The next line to be drawn will be exhibited in the direction of t.
[length] This element defines the length of the next segment to be drawn.
[color] This element specifies the color of the next segment to be drawn.

The LinF interpreter keeps processing the fractal string in a circular fashion in which firstly the string is expanded by the evaluator and next it is read by the rendering machine, which uses it to display a graphical representation of the fractal in a window. The string that represents a fractal contains symbols that force updates into the rendering machine state during the evaluation process. The semantics of each such symbol is explained in the next section.

Representation of Fractals in LinF

LinF, as an L-System-based formalism, allows fractals to be described by strings that contain finite sequences of symbols. These symbols can be terminals, non-terminals, numbers and reserved words of LinF. LinF has nine reserved symbols that are explained below:

[: Saves the current machine state in a stack.
]: Restores the machine state to the state stored in the top of the stack and pops the stack.
@: Multiplies the current line length by the number previously seen. This symbol is always preceded by a floating point number that specifies the amount used to multiply the current length.
?: This symbol does not have any utility during the drawing process. It is useful only during the process of rule application. It means that the next symbol has a chance of not being expanded by the rule in which it appears on the left side. It should always be preceded by a floating point number in the interval (0,1), which specifies the probability of expansion.
+: Updates the state with a rotation given by an angle specified. This angle will be given by the identifier that follows a sequence of + signs. Note that more than a + sign can be encountered together. It is possible to declare a default rotation in the angle section. In this case, if a sequence of + is not followed by any angle identifier, the default rotation must be assumed.
-: This symbol has the same meaning of
+
{: This symbol forces a change in the color state. When a { is found, the current color is replaced by the next color in the list of colors. If the current color is already the last element of the list, then no modification is carried on.
}: This symbol restores the color state to the previous color.

!: This symbol causes an inversion in the interpretation of the symbos + and -.

Example

angles
  a: (.0, [.1 .. .7])
  b: ([((pi/3) - 0.3) .. ((pi/3) + 0.3)], .0)
  c: (.0, [.1 .. .6])
  d: (.0, pi)

lines f

axiom 2.0@ f

rules
  f = 0.5 @ g v;
  v = { u + b u + b u + b u + b u + b u};
  u = 0.5 ? t;
  t = [+a f];
  j = + c

colors
	0: (4, 4, 2)
	1: (90, 90, 46)
	2: (156, 156, 78)
	3: (188, 188, 120)
	4: (209, 209, 163)