Dynamo Fractals Part II: L-Systems and Turtle Graphics

Link to Part I: http://steellworks.blogspot.com/2013/08/dynamo-fractals.html

What's an L-System?

An L-System, short for Lindenmayer System, is a string re-writing algorithm that can be used to produce strings that can then be processed to generate geometry. In a nutshell, you take a starting string, called an axiom, and a list of rewrite rules, called productions, which you use to rewrite the axiom into a new string, which can than be rewritten again and again, ad infinitum.

An example:

Axiom: A

Productions:

A → AB

B → A

0: A
1: AB
2: ABA
3: ABAAB
4: ABAABABA
5: ABAABABAABAAB
6: ABAABABAABAABABAABABA

What's Turtle Graphics?

As mentioned above, you can take a string generated from an L-System and use it to generate geometry. The most popular method of doing this is by using a cursor whose state is manipulated by the symbols in the string produced by the L-System. For fun, we can imagine that this cursor is a turtle.

The turtle has three attributes:  a location (initialized to the origin), an orientation (initialized to the X unit vector), and a pen. It can be commanded relative to the current state of these attributes:  rather than saying "draw a line from (0, 0) to (3, 0)", instead you would say "move forward 3 units while drawing". If you wanted to make a square with end points (0, 0), (3, 0), (3, 3), and (0, 3), you would say "move forward 3 units while drawing, turn 90 degrees, move forward 3 units while drawing, turn 90 degrees, move forward 3 units while drawing, turn 90 degrees, move forward 3 units while drawing".

Obviously that's a lot of text, so each command is represented by a single character:

• + = Turn left
• - = Turn right
• ^ = Pitch up
• & = Pitch down
• \ = Roll counter-clockwise
• / = Roll clockwise
• | = Turn around
• F = Move forward while drawing
• f = Move forward without drawing
• [ = Save current position and orientation
• ] = Restore saved position and orientation

The rotation commands all rotate the same amount, which is determined when the turtle is initialized. The same goes for the distance the movement commands travel.

If we were to create the same square as before using actual Turtle Graphics commands:

Rotation: 90 degrees
Movement: 3 units
Commands: F+F+F+F

How does this relate to L-Systems?

The turtle receives its commands in the form of a string of characters. Any characters which are not one of the commands are simply ignored. This means that we can use L-Systems to generate strings containing Turtle Graphics commands!

Sounds cool, I want to use these in Dynamo!

Great, because I created a Turtle Graphics package that's available for download via the Dynamo Package Manager!

The main interface that the package provides is the Turtle Graphics node:

• start: The axiom of the L-System
• rules: Productions for the L-System
• iterations: Number of times to apply the productions to the L-system product
• initial transform: Starting transformation for the turtle
• move amt: Amount the turtle will move during the F and f commands.
• turn amt: Amount the turtle will turn during the +, -, &, ^, \, and / commands.
• line maker: Function that consumes the two end points of a line drawn with the F command. This is used to generate the output of the Turtle Graphics node.

The Turtle Graphics node returns a list of all the lines it has drawn. In order to give the user some control over how lines are represented, I've provided the line maker input, which takes a function that will receive the two end points of a line, and what it produces will be stored in the final lines list that the node will output.

For simplicity, the rules port takes the productions as a string, consisting of a list of rules separated by newlines, each composed in the following format:

[x]->[rewrite string]

(Where x is a character, and rewrite string is the string of characters to replace x with.)

Example: Sierpiński Arrowhead

Axiom: XF
Productions:
X → YF+XF+Y
Y → XF−YF−X

If you read the previous blog post, you may already understand how this is set up. We plug the axiom and productions (note the format) in as defined, iterations is plugged in from the node's order input, the starting transform is the identity transform if order is odd, and if it's true then start rotated the move amount is calculated so that the triangle's size is proportional only to the scale input (it won't scale with order.) The turn amount is set to 60 degrees.

We use the Line node as the line maker; for each line the turtle draws, Line will receive two end points (in the form of XYZs) and make a line object, which will be returned in the output list of the Turtle Graphics node.

(Note that you could use any node that can receive two XYZs in the place of the Line node, and it will change the data being output. You could, for example, plug in a List node with two input ports, and then the lines output of the Turtle Graphics node will return a list of lists that each contain two XYZs.)

"Sierpiński" example, order 8

Other Examples

Included in the Turtle Graphics package are examples of various L-Systems that you can use for reference.

"Plant" example, order 5

"Hilbert 3D" example, order 3

Dynamo Fractals

We've had a very productive and busy few days over here in the factory, but that hasn't stopped me from implementing something very dear to my heart; something I've been toying around with doing for a while now.

What's a Fractal?

Fractals are geometric constructs consisting of self-similar patterns. Most, if not all fractals are generated using simple recursive rules. It is the recursive property of a fractal's definition that gives it it's unique self-similar structure. Wikipedia has a great article, as usual.

For my Dynamo exercise, I looked for fractals which lend themselves to a simpler geometric definition rather than a pixel-by-pixel definition (such as the Mandelbrot or Julia sets). The two I decided to implement are the Sierpiński Arrowhead and the Dragon Curve. Both of these fractals start as a simple geometric figure (a line) and then on each iteration of its recursive creation, all occurrences of the original geometric figure are replaced with a new figure that contains multiple occurrences of the original figure (which can then all be replaced in the next iteration).

These fractals can both be drawn by emulating a pen: we keep track of the direction the pen is facing, and we can make the pen draw lines of a certain length in its current direction. We can turn the pen, and we can draw with the pen. These can be emulated with Transformations: turning applies a rotation to the pen's transformation, and drawing adds a translation (and the end point of the draw operation can be stored as an XYZ for creating line geometry later).

Sierpiński Arrowhead

One of the most famous fractals is the Sierpiński Triangle (also known as the Sierpiński Gasket). It's starting geometry is a solid equilateral triangle, and on each iteration an inverted equilateral triangle is removed from the center of the solid triangle, creating three solid equilateral triangles around the new hole.

The Sierpiński Arrowhead is used to approximate the whole triangle, and is useful for this exercise because it forms one complete curve (one can draw the entire Arrowhead without lifting up a pen). It's starting geometry is a line segment, that is replaced on each iteration with three line segments half the length of the original with 60 degrees between them. This replacement is inverted on every other application: the "bump" will alternate between being right-side-up and upside-down.

Based on this information, the algorithm looks like this:

Let:

• direction = direction of replacement
• length = length of each segment
• order = number of iterations to draw. Input by the user.
• scale = size of the total image. Input by the user.

In:

1. direction is initialized to upside-down. length is initialized to scale/(2^order). If order is odd, then turn 60 degrees (this will keep the triangle upright).
2. If order = 0: draw a line of length length.
3. Recur with order - 1 and direction flipped.
4. Turn 60 degrees in the current direction.
5. Recur with order - 1 and current direction.
6. Turn 60 degrees in the current direction.
7. Recur with order - 1 and direction flipped.

Step 1 is the initialization of a recursive loop, so in Dynamo all of this will be done in a node that wraps a recursive node.

The length initialization is calculated by dividing the starting scale by 2 for each iteration that will occur.

Step 2 is the start of a recursive function. All recursive calls will start there. Step 2 also represents the base case: if we started this algorithm with order as 0, then we would immediately draw a line of length scale along the X axis, which is the correct result.

Steps 3, 5, and 7 draw each of the three sub-sections of a single iteration, separated by turns in the current direction. This is exactly the definition of a single iteration of the arrowhead:  three sub-sections with 60 degrees between them. If order is 1, then the recursive calls will draw lines, and the result will be the one "bump", which is the correct result.

With that in mind, let's look at the Dynamo implementation.

At the top, we calculate the length of all drawn segments and create a translation transformation out of it. Rotation is initialized to -60 degrees. The starting transformation is set to either the identity transformation if the starting order is even, or a 60 degree rotation if the order is odd. We also initialize an accumulator that will store all of the results; since we will be storing the end-points of all the translations (emulating the draw function), we need to supply the starting point, which is the origin. All of this is passed to arrowhead curve, which contains the recursive loop.

Some notes on the inputs:

• order is the current order we are drawing
• result is the accumulated XYZs representing the end points of the drawn lines
• transform is the accumulated transformation that contains all of the translations and rotations corresponding to the draws and turns used to generate the XYZs
• translate is the pre-calculated translation used to draw the segments
• rotation is the rotation amount to be applied for turns in this iteration

If the order is 0, then we perform a draw by applying the translate to the current transform, and then applying this to an XYZ at the origin to get the appropriate XYZ. The XYZ is added to the accumulator, and the updated accumulator is returned. The updated transform with the translate applied is also returned.

If the order is not 0, the we draw the three sub-sections. We draw the first sub-section with the rotation flipped (which flips the direction). We take the result transform from the first sub-section and rotate it by the current rotation, which emulates the first turn. We pass this turned transform to the second sub-section, along with the current (non-flipped) rotation, and the results of the first sub-section. We turn the result transform again before drawing the third sub-section, which again uses the flipped rotation and the results from the second (and first) sub-section. For all three sub-sections, the order is subtracted by 1, which allows the recursion to approach the base case of order = 0. The results of the third sub-section drawing are then used as the results of the recursive branch.

Sierpinski Arrowhead in Revit, order of 7.

Dragon Curve

The Dragon Curve (also known as the Jurassic Park Curve) is another popular fractal. It is created using 45 and 90 degree angles: its starting geometry is a single line segment, and on each iteration, the single line segment is replaced by two smaller line segments of equal length joined at a 90 degree angle and oriented such that the first new segment forms a 45 degree angle with the original segment. Like the Sierpiński Arrowhead, these replacements alternate between right-side-up and upside-down.

The algorithm looks like this:

Let:

• direction = direction of replacement
• length = length of each segment
• order = number of iterations to draw. Input by the user.
• scale = size of the total image. Input by the user.

In:

1. direction is initialized to right-side-up. length is initialized to scale/2^(.5*order).
2. If order = 0: draw a line of length length.
3. Turn 45 degrees in the current direction.
4. Recur with order - 1 and direction = right-side-up.
5. Turn 90 degrees in the opposite direction.
6. Recur with order - 1 and direction = upside-down.
7. Turn 45 degrees in the current direction.

Step 1 is the initialization of a recursive loop, so in Dynamo all of this will be done in a node that wraps a recursive node.

The length initialization is calculated by dividing the starting scale by the square root of 2 for each iteration that will occur. (Square root of 2 is used because a  45-45-90 right-triangle with a hypotenuse of 1 yields a side-length of root-2 in accordance with the Pythagorean theorem).

Step 2 is the start of a recursive function. All recursive calls will start there. Step 2 also represents the base case: if we started this algorithm with order as 0, then we would immediately draw a line of length scale along the X axis, which is the correct result.

Steps 4 and 6 draw both sub-sections of a single iteration, separated by a 90 degrees turn in the opposite direction. Before and after the sub-sections are drawn, there is a 45 degrees turn in the current direction. This is exactly the definition of a single iteration of the arrowhead:  two sub-sections that form a  45-45-90 right-triangle with the original segment. The first sub-section is drawn right-side up, and the second is drawn upside-down. If order is 1, then the recursive calls will draw lines, and the result will be the one "bump", which is the correct result.

Now let's look at the Dynamo implementation.

This should look familiar if you've already seen the Sierpiński Arrowhead. At the top, we generate the translation transformation to be used for emulating draw. The transformation is initialized to the identity transform, the direction starts right-side-up, and the accumulator is initialized to contain the starting point.

Again, this should be familiar. The base case is set up identically: we perform a draw the same way as before. The recursive case is different but should be straight-forward after seeing the Arrowhead version: first we turn 45 degrees in in the current direction, then we draw the first sub-section right-side up, then we turn 90 degrees in the opposite direction, then we draw the second sub-section, and finally we turn 45 degrees in the current direction. Like last time, the accumulator and the transformation are passed along to the results.

Dragon Curve in Revit, order of 12

Dynamo - Manual Transactions

Hey there, kids! I hope you're all getting ready for the holiday festivities, but maybe some of you are using some of your downtime to tinker with Dynamo on the side. Today, I'll be talking about the Transaction node in Dynamo, and what it can do for your holiday experimentation.

How Dynamo evaluates nodes

I mentioned in my previous blog post that one of Dynamo's internal modes of interacting with the Revit API via Transactions is Manual Transaction mode, and Dynamo only evaluates in this mode when there is a Transaction node in the execution workflow. To summarize again: Dynamo starts evaluating the right-most nodes (nodes with nothing connected to the output). If a node has any inputs, then it first evaluates its inputs, and then passes the evaluated inputs to the node, which is then used to evaluate the node.

Take a look at the following image, in which I've labeled the order nodes are evaluated:

First, Dynamo tries to evaluate the Reference Point node. It sees that the node has an input, so it then tries to evaluate the input, which is the GraphFunction node. That also has inputs, so it start evaluating those, starting with the first (top-most). The multiplication node also has inputs, so it evaluates those. This brings us to the first Number node. It has no inputs, so it can be evaluated as-is. The number -1 is evaluated. Now the other input to the multiplication node needs to be evaluated. The pi node has no inputs, so it just returns 3.4159... Now, the inputs to the multiplication node are satisfied, and we can evaluate the node, which multiplies them. Dynamo will now start evaluating the second input to the GraphFunction node, and the same process will occur.

What the Transaction node does

The Transaction node hooks into this evaluation tree-traversal in order to wrap some of the evaluation in a Revit API transaction. Let's say we had a Transaction node in between the division node and the GraphFunction node. When it would normally come time to attempt to evaluate the division node, it would first run into the new Transaction node. The Transaction node inserts some extra code in the process that initializes a new Revit API transaction, and the continues with the evaluation process. This means that the division node and its inputs will be evaluated with a transaction active. Once the division node has finished being evaluated, it's time for the Transaction node to be evaluated. For its evaluation, it ends the Transaction it created, and then passes its only input along as the result of the evaluation.

Caveats of the Transaction node

When a Transaction node is in the evaluation tree, Dynamo can no longer automatically manage the transactions of its nodes, since the user has explicitly determined when a transaction begins and--more importantly--ends. This means that any node which requires a transaction must be manually connected to a Transaction node by the user. This will prove to be rather inconvenient if you're using a third-party node that uses a transaction internally. However, it mirrors how writing any code for the Revit API involving transactions works, so if you're used to working with it in code, code with it in Dynamo should be familiar.

So when should I use a Transaction node?

Any time you need discreet control of a transaction in a Dynamo workflow. Without a Transaction node in the workflow, Dynamo will automatically detect if any of the nodes require a transaction, and if they do, it will run the entire workflow inside of one. If this functionality cannot accomplish what you need, that's when you use a Transaction node.

As mentioned in my previous blog post, a great example is the Solar Radiation Optimizer sample. It first adjust the value of a family instance parameter, then needs to recalculate the amount of incident solar radiation with the new value applied. The Solar Radiation plugin cannot recalculate until the parameter change has been applied, which requires the transaction the parameter change occurred in to have ended. When I wrote the Solar Radiation Optimizer sample, I used a Transaction node in order to set the new family instance parameter value. After the value was set, the transaction would end, the solar radiation plugin would update and spit out its results to a file, Dynamo would pick up on the change to the file and read in the new data, then compare the data with what it has stored, and then repeat the process until the end of the loop.

Dynamo - Revit Transaction Modes

I'm sitting at an airport bar waiting for my flight back to Boston to start boarding, so I figure now is as good a time as any to discuss how Dynamo interacts with the Revit API via transactions.

All Dynamo nodes know whether or not they require a transaction in order to evaluate. This is necessary in order to make sure that they are run within a transaction, but also so that they aren't run in a transaction if they don't need to be.

Dynamo has three internal "transaction modes" which are set based on various factors.

Automatic

The default mode. If any node in the workflow requires a transaction to evaluate then the whole Dynamo expression is run in a transaction in the Revit idle thread. Otherwise, it is run in its own thread.

Manual

This mode is active if the workflow contains a Transaction node. In this mode, it is up to the user to make sure that all nodes which require a transaction are connected to a Transaction node (either directly or through one or more "parent" nodes). This is desired if you would like to see intermediate results in Revit or if you need a complete Transaction before continuing to evaluate. A good example is the Solar Radiation Optimizer sample, which has to end a Transaction in order for Solar Radiation to update and feed data back into Dynamo.

Debug

Activated when the Debug box is checked in the UI, every node which requires a transaction is evaluated in its own transaction. This allows you to see every node's effect on the document, but is also really slow. Fun fact: this was the first (and for a while, the only) transaction mode.