\graphicspath{{l-systems/}}
\section{L-Systems}
From the structure of mountain ranges to the self-similarity of trees and ferns, we see fractal features throughout nature.  The purely mathematical study of fractals tends to focus on the attractors of iterative processes, rather than the intermediate steps in the production of the fractal.  As natural systems cannot have infinite self-similarity, it is important, when using iterative processes to model natural systems, to pay as much attention to the intermediate results of the process as to the final product.  L-Systems are an attempt to model the development of natural systems.

\subsection{Origin}
In 1968, biologist Aristid Lindenmayer invented a formalization of the description of plant growth that lends itself easily to computer implementation.  Today, these formal descriptions are known as parallel rewriting systems, or L-Systems.  Lindenmayer noticed that simple life forms, such as some kinds of algae, had very predictable and easy to model reproductive patterns.  For example, consider a fictitious plant that grows in long filaments the thickness of a single cell, like some forms of algae.  There are two kinds of cells in this imaginary species of algae, type A, and type B.  When type A divides, it produces a cell of type A on the left, and type B on the right.  Type B splits into a cell of type B on the left, and type A on the right.  This is typical of the reproductive patterns of this kind of algae.

We can represent a single filament as a string of letters A and B.  To model one step of cell division, simply replace all occurrences of A with AB, and all occurrences of B with BA.  See Table \ref{tab:ABalgae} for an example of the growth pattern of this algae.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|l|c|}
\hline
&AB\\
\hline
Step 1&ABBA\\
\hline
Step 2&ABBABAAB\\
\hline
Step 3&ABBABAABBAABABBA\\
\hline
Step 4&ABBABAABBAABABBABAABABBAABBABAAB\\
\hline
\end{tabular}
\end{center}
\caption[AB Algae]{The first 5 divisions in the growth of the AB algae.}
\label{tab:ABalgae}
\end{table}

\subsection{Lexical Substitution}
L-Systems are very close to context-free grammars, a fundamental concept in the field of computer science.  The definition of an L-System consists of three major parts: a set of symbols, an axiom, and a set of substitution rules.  The set of symbols is the ``language'' of the L-System; it is the set of characters that make up the string.  In the example above, the set of symbols was ${A,B}$.  To model more complex growth systems, more symbols are used.  The axiom is simply the string used to begin the process, and is also referred to as the initial state.  In the above example, we used ``AB''.  The substitution rules, also referred to as production rules, are the meat of the L-System.  A substitution rule specifies that every occurrence of some symbol should be replaced with a new string.  During each step of processing, every substitution rule is applied in order to produce the next string.  This is the AB algae example modeled as an L-System:

\vspace{1em}

\begin{tabular}{|l|l|}
\hline
L-System name&AB Algae\\
\hline
Symbols&${A,B}$\\
\hline
Axiom&AB\\
\hline
Substitution rules&A $\to$ AB\\
                  &B $\to$ BA\\
\hline
\end{tabular}

\vspace{1em}

\subsection{Graphical Interpretation}
\label{sec:lsys:graphint}
L-Systems, by their definition, grow their strings exponentially.  The results of the growth process quickly become too big for a human to handle, much less make any useful observations.  The strength of the L-System concept is that the grown string can be processed and represented graphically, often with fascinating results.  The standard method of visualizing L-Systems is to create special symbols, and give them a graphical interpretation.  The growth process is iterated several times, the resulting string is interpreted as a series of graphical commands, and the graphical figure is rendered on a computer.  The computer maintains a current position and direction, and it responds to drawing commands such as the following:

\vspace{1em}

\begin{tabular}{cl}
F&Move forward some predefined length, while drawing a line.\\
G&Move forward some predefined length, without drawing a line.\\
$+$&Turn counterclockwise some predefined angle $\delta$.\\
$-$&Turn clockwise some predefined angle $\delta$.\\
\end{tabular}

\vspace{1em}

Repeated substitutions using the production rules can create a string that is extremely large.  It is impossible to tell before rendering how much space the string will require on screen[Peitgen, et al 1992].  Therefore, programs used to render L-Systems must render the entire object in memory, and then discover what scaling factor is required so that the entire object may be viewed on the screen.

With the simple yet powerful definition we have so far, we can render many classical fractals such as the Koch Curve.  The definition of the Koch Curve is simple.  Start with a line segment of length $n$, and divide it into three equal parts of length $\frac{n}{3}$.  Remove the center segment, and replace it with two segments of length $\frac{n}{3}$, joined to the two existing segments.  The process is repeated on every segment in the figure, ad infinitum.  Figure \ref{fig:Koch-lsystem} shows an example of the rendering of the Koch Curve L-System.  How can we model this fractal as an L-System?  

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics{koch1.png}&\includegraphics{koch2.png}\\
\includegraphics{koch3.png}&\includegraphics{koch4.png}\\
&\\
\multicolumn{2}{c}{
\begin{tabular}{|l|l|}
\hline
L-System name&Koch Curve\\
\hline
Axiom&$F$\\
\hline
Substitution rules&F $\to$ F+F--F+F\\
\hline
$\delta$&60 degrees\\
\hline
\end{tabular}
}\\
\end{tabular}
\end{center}
\caption[Koch Curve L-System]{Images produced from the first four steps of the Koch Curve L-System}
\label{fig:Koch-lsystem}
\end{figure}

\subsubsection{Branching}
The graphical symbols defined so far allow one to create complex and interesting figures, but these figures will always be traced by one line or path, whether or not the line is actually drawn on the screen.  To extend the capabilities of L-Systems and to allow the rendering of more complex plant growth, more powerful graphical symbols are needed.  Most plants of interest don't grow in a straight line; they branch.  To render a branching structure, L-Systems provide a method to save and restore the current position and direction.  To render a branching point in a plant, first render the stem, then save the position and direction, render the left branch, restore the position, and finally render the right branch.  To allow for this, two new symbols are needed:

\vspace{1em}

\begin{tabular}{cp{3in}}
[&Push the current location and position onto a stack.\\
]&Pop the top location and direction off of the stack, and use them for further drawing operations.\\
\end{tabular}

\vspace{1em}

Because the branches of a structure might, themselves, branch again, it is necessary to be able to store many locations at once.  Locations are stacked onto one another in memory.  When the pop command is reached, the most recently pushed location is restored as the current location.  An example of a branching L system is the simple weed shown in Figure \ref{fig:weed-lsystem}.

\begin{figure}[htbp]
\begin{center}
\includegraphics{weed.png}

\vspace{1em}

\begin{tabular}{|l|l|}
\hline
L-System name&Weed\\
\hline
Axiom&$B$\\
\hline
Substitution rules&B $\to$ F[+B]F[-B]+B\\
                  &F $\to$ FF\\
\hline
$\delta$&20 degrees\\
\hline
\end{tabular}
\end{center}
\caption{Weed L-System}
\label{fig:weed-lsystem}
\end{figure}

This L-System has a few notable features.  First of all, the symbol B is used, although it has no graphical definition.  When an L-System rendering program finds a symbol that has no graphical meaning, it will simply ignore it and continue rendering.  This allows for more flexibility in designing the L-System.  In this plant, B represents the full plant.  An intuitive interpretation of this L-System is that the entire plant is reproduced in three branches off of the main trunk.  The infinitely recursive nature of this simple definition is the result of replacing B with a string that also contains B.  Also note the first production rule: F $\to$ FF.  This means that, during every stage of growth, the pre-existing portions of the plant double in length.  This has the effect of making the structure smaller further away from the trunk, much like a real plant.  Figure \ref{fig:weed-lsystem} shows the results of the first several steps of rendering.

\subsection{Fractint}
Fractint has a powerful mode for rendering L-Systems.  The syntax of an L-System is much like the syntax used for defining an IFS.  For example, this is the Koch Curve definition for Fractint:

\vspace{1em}

\begin{verbatim}
   KochCurve {  ; This is the name of the L-System
     Angle 8    ; Set the angle to 45 degrees (360/8)
     Axiom F    ; Initial state
     F=F+F--F+F ; production rule for F
   }
\end{verbatim}

\vspace{1em}

Fractint also defines some more powerful drawing commands:

\vspace{1em}

\begin{tabular}{lp{24em}}
$|$&Turn 180 degrees, or the largest possible turn less than 180 degrees, depending on $\delta$\\
Cnn&Set the color value to nn\\
$>$nn&Increment the color by nn\\
$<$nn&Decrement the color by nn\\
!&Switch the meanings of + and -\\
@nnn&Multiply line segment size by nnn\\
{[}, {]}&Also stores color, line segment size, and ! status\\
\end{tabular}

\vspace{1em}

Fractint comes with many predefined L-Systems.  To render a custom L-System, use the above definition syntax, and write the L-System to a file with extension ``.L''.  Direct Fractint to load this file instead of its default, and select the L-System by name from the menu.

The authors set out to create an L-System reminiscent of a snowflake.  If the Koch Curve is rendered, using ``F+F+F'' (an equilateral triangle) as the axiom, it looks remarkably like a snowflake.  The authors tried to capture this feeling, but using a different style of L-System.  The results are shown in Figures \ref{fig:snowflake1}, \ref{fig:snowflake2}, and \ref{fig:snowflake3}.

\begin{figure}[hbp]
\begin{center}
\includegraphics{snowflake1.png}
\end{center}
\begin{verbatim}

   SnowFlake1 {
     Angle 12
       ; 30 degrees
     Axiom [F]++[F]++[F]++[F]++[F]++[F] 
       ; six 60 degree radial lines
     F=[--F++FFFF++F--]++F--FFFF--F++
       ; replace f with a long pointed bar
   }
\end{verbatim}
\caption{Snowflake L-System 1}
\label{fig:snowflake1}
\end{figure}

\begin{figure}[hbp]
\begin{center}
\includegraphics{snowflake2.png}
\end{center}
\begin{verbatim}

   SnowFlake2 {
     Angle 12                            
       ; 30 degrees
     Axiom  [F]++[F]++[F]++[F]++[F]++[F] 
       ; six 60 degree radial lines
     F=[+F-F-F+]-F+F+F-
       ; replace F with a trapezoid
   }
\end{verbatim}
\caption{Snowflake L-System 2}
\label{fig:snowflake2}
\end{figure}

\begin{figure}[hbp]
\begin{center}
\includegraphics{snowflake3.png}
\end{center}
\begin{verbatim}

   SnowFlake3 {
     Angle 12 
       ; 30 degrees
     Axiom [F]++[F]++[F]++[F]++[F]++[F] 
       ; six 60 degree radial lines
     F=[+FF-F-FF+]-FF+F+FF-
       ; this trapezoid has longer legs
   }
\end{verbatim}
\caption{Snowflake L-System 3}
\label{fig:snowflake3}
\end{figure}


