L-System Generator Code walkthrough

Alles Rund um Computergrafik, OpenGL, prozeduraler Content Generierung, etc :)

L-System Generator Code walkthrough

Yesterday I posted a new small Javascript Webapp that is able to generate an L-System and it’s visual representation quite easily. You can find the related blog-post here: The first L-System Generator.

Today I want to give you a description about how the app works and walk you through the code in small steps. I will use the first example of the mentioned blog-post.

Overview

The application consists of a few simple parts that I want to describe at a high level before we dive into the code-details :).

At the start of the application, several helper variables are initialized and the basic three.js scene-setup is done.

The HTML part of the application uses oninput and onsubmit events on the inputs and form to update the L-System interactively, when you change the definition. This enables us to actually see any changes immediately.

If the L-System should be generated, which is triggered via a click on the ‚play‘ button or a change of the L-System definition, we get the current definition of the L-System from the form controls and then start the generation process.

The generation of the L-System consists of two (three) parts.

The first part of the generation is the actual string generation from the definition of the L-System.

The second part uses the generated textual representation of the L-System and creates the data (i.e. line endpoints) for the graphic representation of the L-System. With the generated graphic data available, the Application then fits the scene into the viewport, so that you can see all of the generated contents (i.e. lines).

Code

On a high level, the application consists of the standard html elements like the head element with all necessary child elements and includes a style-element for additional styling of the html elements.

The body-element contains a header element (the title), an aside element for the L-System definition elements (the form element) and a main element that finally holds the canvas generated by three.js.

After all the HTML element declarations, the Javascript containing the application logic follows and is the last important part of the application. I will discuss the Javascript part in the following section.

Application details

The application utilizes two small and simple classes State and Stack, which are defined at the top of the script.

State class

The State class is used to represent the state of the ‚turtle‘. This state is used to interpret the textual representation of the L-System. 

The state consists of the three values x, y, and angle. They represent the current 2D position and the heading of the turtle.

The constructor takes all three values and set’s them.

The only two functions that exist in this class are Move and Turn that change the turtle’s position and it’s heading respectively.

Stack class

Since it is possible to push the current state of the turtle onto a stack to save it, I need an easy-to-handle class that performs all needed operations. A saved state can later be restored to reset the turtle’s position and heading to another point. This ability enables the L-System to create branches in the generated objects.

The constructor of the Stack class does not take any arguments and just creates an empty array named State.

The three implemented functions (yet only two are used at the moment) handle the Stack management. It is possible to Push, Pop and Peek elements to and from the State array.

Push takes a State object and adds it to the State array at the end (which creates the behavior of a Stack).

Pop is the opposite to the Push method and takes the last State object from the State array. it removes the last State object from the array and returns it to the caller.

Peek works like the Pop function, but does not remove the State object from the Stack array. This function is not used at the moment, but might be used in the next versions of the applicaion.

Prototype functions

The to_radians function for Number objects is just a small helper method to convert angle values from degrees to radians. This conversion is needed to convert the angle from the L-System definition because the Math.cos and Math.sin functions need the value to be radians.

The replaceAll function for String objects takes two parameters. The first parameter is the value that should be replaced in the string and the second parameter defines the replacement for the found occurences.

Basic setup

After the definitions of the two used classes and extension methods we perform a basic setup. This setup involves the creation of the three.js scene and the generation of the object that should be displayed later.

Most part of this code can (and probably should) be put inside a function. I will do that in the next version of the application quite certainly.

At the start, we determine the main HTML element. It will contain the canvas object we use to draw the generated L-System later.

Then the x- and y- dimensions of the window is used to setup the camera object I use to view the scene. The visible part of the scene is in the range [-maxX, maxX] / [-maxY, maxY] / [-1, 1] because I translate the camera ‚back‘ 10 units and set the visible depth to [9, 11].

The next lines create a new three.js scene with a light grey background color. The renderer object if used to create the canvas and to actually render the defined scene. By appending it’s domElement to the drawingArea element we end up appending the renderer’s canvas element to the main HTML element.

I call a function named ResetCamera to setup a few more camera related values.

At last, a black BasicLineMaterial material and a BufferGeometry geometry object is created. The positions array is later used to set the geometry’s vertex positions, which is set up in the last line of the above code.

Render

This simple function just calls the render function of the renderer object with the defined scene and camera objects. This call leads to the actual drawing of the scene to the canvas object.

GenerateLSystem

The GenerateLSystem is the main entry point in the execution of the application. It is first called when the page was loaded with the parameters null and 0 which means that the call was done manually and that only the initial step of the L-System should be generated. It essentially interprets the defined axiom and renders this interpretation to the canvas.

This function is also called whenever the user clicks on the play button at the bottom of the L-System definition panel or if the user changes any part of the definition of the L-System.

At first all existing scene elements are removed from the scene to be able to create new children.

The next step actually retrieves the information about the L-System. We need all those parts for the L-System to be fully defined. The axiom defines the start state of the L-System before the generation starts. The rule defines the main (and most interesting) part of the L-System. It defines how the L-System will change in one iteration step. This rule is used in the replaceAll function to generate a new output from the input string (e.g. the axiom).

The iterations count defines how many iterations of the L-System generation process are calculated. The more steps we choose, the more complext the result gets. The angle definition is also very important and controls how far the turtle turns left or right in one step.

The next step of the generation process is the generation of the textual representation of the L-System. This generation of the resulting string is done iteratively in the for loop with a call of the IterateLSystem function. In each iteration the previous result is used as the input and the defined replacement mechanism is performed on this string. The result is then again used in the next iteration if the is another one.

Generation example

A simple example of a few steps of the generation looks like this:
0: F
1: F+F–F+F
2: F+F–F+F+F+F–F+F–F+F–F+F+F+F–F+F

After the textual generation of the L-System is finished by the replacement operations, the next step is to create a visual interpretation of the L-System. This generation step is performed in the function GeneratePositions and results in the generation of the endpoints of all lines that should be displayed.

When the line endpoints are generated it remains to update the actual scene geometry by setting the positions attribute of the geometry object and to let three.js know, that we changed the geometry. After setting this geometry we let three.js recalculate the buindingBox of the geometry.

The boundingBox is necessary later to fit the generated scene into the viewport.

At last we use the geometry to create a LineSegments object and toattach this object to the scene before we render the whole scene to display it on the screen.

IterateLSystem

This function is used to generate the textual representation of the L-System. Each call to this function represents one iteration of the genertion process.

The parameter lhs represents the existing state of the L-System generation from the previous generation step and equals the axoim if this function is called for the first time.

The rule is another string that has the following form:

The predecessor defines the substring that is searched within the lhs string. The successor defines the replacement string that is inserted for each occurrence of the predecessor. In other words all occurrences of the predecessor in the lhs (left hand side) string are replaced with an instance of the successor string. Three iterations are displayed in the section Generation example above.

GeneratePositions

This function is used to generate the data for the visual output of the generated L-System represented by the string rhs. The arguments are the text representation of the L-System and the angle that should be used when the turtle turns left or right. The function returns a set of endpoints (start, end) of lines that should be renderd later by interpreting the string characters.

The function implements the behavior of the turtle graphic. Draw a line, turn left, turn right, save the current state and go back to a saved state.

At the start of the execution some variables are initialized. The vertexPositions array will be returned at the end of the execution and holds all generated line endpoints. The angleStart variable is used to initially turn the turtle to point to the top. The startState then represents the complete state information of the turtle and the currentState always holds the current information of the turtle’s state.

The for loop iterates through the whole L-System rhs and interprets each individual characte in accordanse to the turtle‘ graphics assumptions.

Those assumptions allow five different characters (in this first application) and each occurrence of those characters is handled inside the switch statement.

If the turtle encounters an F character it uses the current position to start a line by saving the position to the array and then moves in the direction it is currently headed 10 units. The turtle draws a line from the previous state’s position to the new position, so it also saves it’s new position to the array.

If the turtle encounters the + or character in the L-System it turns left or right at the turtle’s current position. This doesn’t result in any output but still changes it’s state.

If a [ character occurs nothing obious happens. No line will be drawn and not even the state of the turtle changes in any way. The only thing that happens is that the state of the turtle will be pushed onto a stack of states.

If a ] character occurs, the ‚top‘ state from the stack of states is popped from the stack and the state of the turtle changes immediately from it’s previous state to this restored state. No line will be drawn.

When the loop is finished all created positions are returned to the calling method which will then use this data to create the visual representation of the L-System.

ResetCamera

Since it’s possible that e.g. the browser windows get’s resized and since the scene can be arbitrarily big, I use this method to fit the scene to the viewport.

To be able to fit the generated scene into the viewport, this method first determines the aspect ratio of the viewport. The next step is to determine the minimum- and maximum values of the generated scene.

With this information the newMinX- and Y and the newMaxX- and Y arecalculated and then used to set the camera’s viewing range.

ResizeCanvas

If the size of the viewport changes due to a change of the browser window the camera is reset to handle the new width and height values of the viewport. After resetting the camera a new call to the render function is done to redraw the scene to always be able to see the scene in the correct aspect ratio.

First call to GenerateLSystem

The last line of the code simply performs a call to the GenerateLSystem function with the parameters null and 0.

This call is performed to have a simpel visual output right when the page loads. By adding this line, the user can always at least see the axiom state of the L-System.

Done

Voilá! We are done :)!
Kind regards,

Franz