Transformations and Writing Rules

This tutorial is intended to give you the skills necessary to:

  1. Understand the differences between embedding under isometry, similarity, and affinity

  2. Know how to translate hand-written rules to rules for Shape Machine

  3. Understand the difference between sequential and parallel replacement

You can download the tutorial file here: Tutorial 1.3dm.

Part 1: Transformations

When computing with shape grammars, every rule \(u \rightarrow v\) is applied by finding the transformation \(f\) that embeds \(u\) in your design \(w\) (that is, find \(f\) such that \(f(u) \le w\)). When computing by hand, you might not think about what \(f\) actually is. If you’re looking for a triangle and you see a triangle, that’s all the thought that’s needed.

With Shape Machine, some extra care is required. Specifically, you need to tell Shape Machine whether you’re looking for a shape under isometry, similarity, or affinity. Because the geometry Shape Machine operates on is defined with particular dimensions, these distinctions are important.

Isometry

Under isometry, the only matches that can be found are congruent to \(u\). Generally, if you could find it by shifting, rotating, and flipping tracing paper, it can be found under isometry.

More specifically, all isometries are translations, rotations, reflections, and their compositions. Modifying a shape by only these types of transformations allow it to still be found under isometry.

Nitty-gritty math

We can represent transformations as a block matrix \(\mathbf{M}\):

\[\begin{split}\mathbf{M} = \begin{bmatrix} \mathbf{A} & T \\ \mathbf{0} & 1 \end{bmatrix}\end{split}\]

Where \(\mathbf{A}\) is 2x2 (for 2D geometry) or 3x3 (for 3D geometry) matrix, \(T\) is a column vector indicating translation, and \(\mathbf{0}\) is a row vector that fills the bottom row up to the last entry with zeros.

To be an isometry, \(\mathbf{A}\) must be a rotation matrix, possibly with reflection. For this to be true, \(\mathbf{A}\) must satisfy the following properties:

  • \(\mathbf{A}\) must be orthonormal (\(\mathbf{A}^T\mathbf{A}=\mathbf{I}\))

To create \(\mathbf{A}\), rotation and reflection matrices can be composed:

\[\begin{split}\mathbf{Rot}(\theta) = \begin{bmatrix} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{bmatrix}\end{split}\]
\[\begin{split}\mathbf{Refl} = \begin{bmatrix} -1 & 0 \\ 0 & 1 \end{bmatrix}\end{split}\]

To transform a vector \(v\), we start by augmenting it with a 1 to match the dimensions of \(\mathbf{M}\):

\[\begin{split}v_h = \begin{bmatrix} \uparrow \\ v \\ \downarrow \\ 1 \end{bmatrix}\end{split}\]

This is the homogeneous form of \(v\). We can then compute \(v_h' = \mathbf{M} v_h\). At the end, we can compute \(v'\) by dividing everything by the last element of \(v_h'\). Because the bottom row of \(\mathbf{M}\) is all zeros and a final one, this last element of \(v_h'\) will always be 1, so dividing has no effect. In general though, this strategy of using homogeneous coordinates to express transformations can be used when the bottom row of \(\mathbf{M}\) has other numbers, which enables perspective projection.

Since Shape Machine does not support perspective transformations, all transformations can be summarized as:

\[v' = \mathbf{A} v + T\]

Similarity

Under similarity, the only matches that can be found are similar to \(u\). Generally, this is anything that can be found under isometry and anything that can be found by growing or shrinking \(u\).

More specifically, all similarities are isometries, uniform scalings, and their compositions. Modifying a shape by only these types of transformations allow it to still be found under similarity.

Nitty-gritty math

This section builds on the information presented in Isometry nitty-gritty. Read that section first.

In order for \(\mathbf{M}\) to be a similarity, \(\mathbf{A}\) must satisfy the following properties:

  • \(\mathbf{A}\) is invertible

  • For every pair of columns \(A_i\) and \(A_j\) in \(\mathbf{A}\) where \(i \ne j\), \(||A_i|| = ||A_j||\) and \(A_i \cdot A = 0\)

To create \(\mathbf{A}\), rotation, reflection, and scaling matrices can be composed:

\[\begin{split}\mathbf{Scale}(s) = \begin{bmatrix} s & 0 \\ 0 & s \end{bmatrix}\end{split}\]

Affinity

Under affinity, the matches that can be found are much broader than under isometry and similarity. This is easily the most confusing type of transformation. Generally, as long as parallel lines are preserved, \(u\) can still be found. This means a square can be matched to any parallelogram, and, by proxy, any triangle can be matched to any other triangle.

More specifically, all affinities are similarities, non-uniform stretches, shears, and their compositions. Modifying a shape by only these types of transformations allow it to still be found under affinity.

Things that cannot be matched under affinity are things that have been “pinched” or “pulled” in a way that make parallel lines no longer parallel.

Nitty-gritty math

This section builds on the information presented in Similarity nitty-gritty. Read that section first.

In order for \(\mathbf{M}\) to be an affinity, \(\mathbf{A}\) must satisfy the following properties:

  • \(\mathbf{A}\) is invertible

To create \(\mathbf{A}\), rotation, reflection, scaling, stretching, and shearing matrices can be composed:

\[\begin{split}\mathbf{Stretch}(s) = \begin{bmatrix} s & 0 \\ 0 & 1 \end{bmatrix}\end{split}\]
\[\begin{split}\mathbf{Shear}(\theta) = \begin{bmatrix} 1 & 0 \\ \tan{\theta} & 1 \end{bmatrix}\end{split}\]

Direct vs. Indirect

Normally, embedding includes matches found by first reflecting \(u\). If you want to avoid including any transformations involving reflection, match under direct isometry/similarity/affinity. To only include transformations involving reflection, match under indirect isometry/similarity/affinity. In Shape Machine, you can search with direct transformations by right-clicking the button corresponding to the transformation you want to use instead of left-clicking.

Nitty-gritty math

This section builds on the information presented in Isometry nitty-gritty. Read that section first.

Whether or not \(\mathbf{M}\) includes a reflection can be determined by checking the determinant of \(\mathbf{A}\):

  • No reflection: \(|\mathbf{A}| > 0\)

  • Reflection: \(|\mathbf{A}| < 0\)

Exercises

Within the tutorial file, the first part at the top serves as a playground for experimenting with the different transformations.

  1. Using the Search by Shape button, observe what happens when you search for the square under each transformation.

    • Why is each quadrilateral found/not found under each transformation?

  2. Using the Replace by Rule button, observe what happens when you attempt to apply the replacement rule under each transformation. Repeat this process with direct replacement (Right-Click the transformation button)

    • Why are the matches different when forcing direct transformations vs allowing indirect?

Part 2: Writing Rules

In Shape Machine, writing rules is similar to writing rules by hand. The biggest difference is that it matters a lot more how you align the left- and right-hand side of the rule.

Take note of the green points at the bottom of the rule template on either side of the vertical bar. These serve as a kind of “anchor” that lets you know how the RHS will be mapped under \(f\). Any geometry in the same place on the LHS and RHS relative to the anchors will be in the exact same place when the rule is applied.

What this means is that if you just want to modify something without moving it, you can create the LHS, copy it from the LHS anchor to the RHS anchor, and change the RHS. This will keep everything in the same place relative to the anchors.

It takes some time to get used to, but once you get the hang of it, writing rules is straightforward if you know what the rule should be.

Exercises

Within the tutorial file, the second part in the middle is a template for implementing George Stiny’s 1980 grammar for creating nested squares.

  1. Create the two rules included in the image.

  2. Apply the first to the initial shape a couple of times.

  3. Apply the second rule when you’ve decided you’ve applied the first enough.

  4. Optional: With an understanding of how to write rules, feel free to update the rule in Part 1 to see what happens under the different transformations!

Part 3: Serial vs. Parallel Application

When applying rules, Shape Machine will ask you which match you want to apply the rule to. You can either choose to apply the rule to only one match or to all of the matches. This has some implications you should be aware of. Within the tutorial file, the third part at the bottom has some rules to experiment with the differences.

Some key insights into the differences:

  • Serial application applies \(u \rightarrow v\) by computing \(w' = w - f_i(u) + f_i(v)\) for chosen match \(i\).

    • Serial application can remove geometry that you might want to keep for subsequent applications of the same rule.

  • Parallel application applies \(u \rightarrow v\) by computing \(w' = w - \sum_{i=1}^{n}f_i(u) + \sum_{i=1}^{n}f_i(v)\).

    • Due to symmetry, parallel application might apply at two different rotations/reflections/etc. in the same place. This could cause unintended geometry if you only want the rule to be applied once at each place.

Exercises

Start with a 3-squares output from Part 2. Make a copy so that you can play with the first and second rules separately.

  1. Run the first rule on the 3-squares in serial a few times. Restart and apply it in parallel.

    • Would you expect to see any difference between running it serially 8 times vs. in parallel once?

  2. Run the second rule on the 3-squares twice, selecting the first match found. You’ll find it can no longer apply to the design any more. Restart and apply it in parallel.

    • Why are the results different?

  3. Run the third rule on the provided grid a couple of times. Restart and run it in parallel.

    • Why are the results different?