Overview

This post reviews the concept of non-branching L-systems and provides an approach for representing them in Unity, and drawing them in 2 different ways. Line Renderer and OpenGL Lines.

I’ve been reading The Algorithmic Beauty of Plants, which got me interested in the topic.

Drawing

L-Systems

The concept of L-systems is: Begin with a start string (axiom). Apply a set of rewriting rules to each character (if applicable) to create a new string. Do this any number of iterations to create a final axiom. Then, interpret the characters in order as a series of drawing rules.

If we wanted to interpret an axiom, we’d have to prescribe meaning to each of the characters. Lets use

  • F = “Draw forward”.
  • - = “Rotate the forward vector by -90 degrees”;
  • + = “Rotate the forward vector by 90 degrees”; (although unused in the first axiom)

Given the axiom F-F-F-F, drawing based on the rules will generate a square.

Lets define the rewriting rule to generate a curve similar to a menger sponge.

F->FF-F-F-F-FF

This means, replace every F in our axiom with the string FF-F-F-F-FF.

After 1 iteration, the string F-F-F-F will become:

FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF-FF-F-F-F-FF

By interpreting the string based on the draw rules above, here’s what the square deforms to after some iterations:

Drawing

Different sets of drawing and replacement rules produce different shapes.

Implementation

To represent a replacement rule, we will use a class to represent a character, and a corresponding replacement string.

public class ReplacementRule {
    public char character;
    public string replacement;
}

Similar for a draw rule. A character with a corresponding angle. If there’s no angle, we assume it means to draw forward.

public class DrawRule {
    public char character;
    public float angle;
}

We will reference these from our LSystem class, which will have lists of each rule we can populate in the inspector.

public class LSystem {
    [SerializeField] string startAxiom;

    [SerializeField] int iterations;

    [SerializeField] float forwardScale = 0.2f;

    [SerializeField] List<ReplacementRule> replacementRules = new List<ReplacementRule>();

    [SerializeField] List<DrawRule> drawRules = new List<DrawRule>();

    [HideInInspector] public Vector3[] positions;
}

The product of the LSystem class will be the positions array, so a line drawing class can handle those. To compute the positions, it first must generate the final axiom, and then iterate over the string, applying draw rules.

Two dictionaries are created on awake, replacementRuleDict and drawRuleDict to store character mappings for their rules. This makes it simple to lookup a rule for any given character.

I took a simple approach by just creating an empty string and iterating over the axiom, populating the string with rather the replacement rule for the current character, or the current character if no rule applies.

string GenerateAxiom(string start)
{
    string resultAxiom = startAxiom;

    // Rewrite the axiom n times by replacing eligible characters with their replacement string
    for (int i = 0; i < iterations; i++)
    {
        string s = "";

        // Build a new string by replacing each character with the replacement rule
        foreach (char c in resultAxiom)
        {
            // If there's no replacement rule for the character, just leave it in the string
            if (!replacementRuleDict.ContainsKey(c))
            {
                s += c;
                continue;
            }

            ReplacementRule generator = replacementRuleDict[c];
            s += generator.replacement;
        }

        resultAxiom = s;
    }
    return resultAxiom;
}

The code for calculating the positions isn’t that exciting.

It has a forward vector which is rotates when it encounters a draw rule in the axiom that has an angle. If the draw rule for the current character doesn’t have an angle, we assume that means to go forward, so we add forward to the current position, and add it to the list.

void CalculatePositions()
{
    Vector3 pos = Vector3.zero;
    Vector3 forward = Vector3.up * forwardScale;
    positions = new Vector3[MovementCount() + 1];
    int index = 1;

    // Set the start position
    positions[0] = pos;

    // Iterate through the characters in the axiom
    foreach (char c in axiom)
    {
        // Apply the draw rule only if one exists for the current character
        if (drawRuleDict.ContainsKey(c))
        {
            // Get the draw rule for the current character
            DrawRule rule = drawRuleDict[c];
            if (rule.character == c)
            {
                // If the angle is zero, then extend our position along our forward vector
                if (rule.angle == 0f)
                {
                    pos += forward;
                    positions[index] = pos;
                    index++;
                }
                // If the angle is not zero, apply a rotation of that angle to the forward vector
                else
                {
                    forward = Quaternion.AngleAxis(rule.angle, Vector3.forward) * forward;
                }
            }
        }
    }
}

Line renderers are one approach to draw them. The LSystemsLineRenderer class just sets the positions and the code is trivial.

With many points, this can get pretty slow. A faster way to draw lines in Unity is to use OpenGL GL_Lines. These come with less features though, so it’s a trade off.

public void OnRenderObject ()
{
    GL.PushMatrix();
    material.SetPass(0);

    GL.Begin(GL.LINES);

    for (int i = 0; i < lSystem.positions.Length-1; i++) 
    {
        Vector3 position1 = lSystem.positions[i];
        Vector3 position2 = lSystem.positions[i+1];
        GL.Vertex(position1);
        GL.Vertex(position2);
    }

    GL.End();
    GL.PopMatrix();
}

Conclusion

You can check out my LSystems implementation and sample project on Github

This approach is rather limiting, because it only handles continuous space filling curves. I’d like to experiment in the future with branching systems and axial trees.